目录

一丶线性表

1.1 线性表的抽象数据类型

1.2 线性表的顺序存储的结构代码

1.3 顺序表的操作

1.3.1 元素获取

1.3.2 元素插入

1.3.2 元素删除

1.3.3 完整代码

1.4 线性表顺序存储结构优缺点

1.5 线性表的链式存储的结构代码

1.6 单链表的操作

1.6.1 元素的读取

1.6.2 元素插入

1.6.2 元素删除

1.7 单链表的整表创建

1.7.1 头插法建立单链表

1.7.2 尾插法建立单链表

1.7 单链表的整表删除

1.8 链式结构与顺序结构优缺点

一丶线性表

线性表（List）：由零个或多个数据元素组成的有限序列。

注意：若元素存在多个,则第一个元素无前驱,而最后一个元素无后继,其他元素都有且只有一个前驱和后继。

1.1 线性表的抽象数据类型

ADT 线性表（List）

Data

线性表的数据对象集合为{a1,a2,...,an},每个元素的类型均为DataType。其中,除第一个元素a1外,每一个元素有且只有一个直接前驱元素,除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。

Operation InitList( L )：初始化操作，建立一个空的线性表L。 ListEmpty( L )：判断线性表是否为空表，若为空返回true，否则返回false。 ClearList( *L )：将线性表清空。 GetElem( L , i , *e )：将线性表L中的第i个位置元素值返回给e。 LocateElem( L , e )：在线性表L中查I找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功。否则，返回0表示失败。

ListInsert( L , i , e)：在线性表L中第i个位置插入新元素e。 ListDelete( L , i , *e )：删除线性表L中第i个位置元素，并用e返回其值。 ListLength(L)：返回线性表L的元素个数。

endADT

1.2 线性表的顺序存储的结构代码

#define MAXSIZE 20
typedef int ElemType;
typedef struct
{
    ElemType data[MAXSIZE];
    int length;  //线性表当前长度
}SqList;

1.3 顺序表的操作

1.3.1 元素获取

//元素的获取(用e返回L中第i个元素的值)
int GetElem(SqList L,int i, ElemType* e)
{
    if (L.length == 0 || i<1 || i>L.length)
    {
        return 0;
    }
    *e = L.data[i - 1];
    return 1;
} 

1.3.2 元素插入

//元素的插入
int ListInsert(SqList* L, int i, ElemType e)
{
    int k;
    if (L->length == MAXSIZE)//线性表已满
    {
        return 0;
    }
    if (i<1 || i>L->length + 1)//当i不在范围内时
    {
        return 0;
    }
    if (i <= L->length)  //若插入位置不在表尾
    {
        //将要插入位置后数据元素向后移动一位
        for (k = L->length - 1; k >= i - 1; k--)
        {
            L->data[k + 1] = L->data[k];
        }
    }
    L->data[i - 1] = e;
    L->length++;
    return 1;
}

1.3.2 元素删除

//元素的删除（删除L中第i个元素，并用e返回其值，L的长度-1）
int ListInsert(SqList* L, int i, ElemType  *e)
{
    int k;
    if (L->length == MAXSIZE)
    {
        return 0;
    }
    if (i<1 || i>L->length + 1)
    {
        return 0;
    }
    *e = L->data[i - 1];  //删除元素
    if (i <= L->length)  
    {
        for (k = i; klength; k++) //元素向前移动
        {
            L->data[k -1] = L->data[k];
        }
    }
   
    L->length--;
    return 1;
}

1.3.3 完整代码

#include
#define MAXSIZE 20
typedef int ElemType;
typedef struct
{
    ElemType data[MAXSIZE];
    int length;  //线性表当前长度
}SqList;
​
//元素的获取(用e返回L中第i个元素的值)
int GetElem(SqList L,int i, ElemType* e)
{
    if (L.length == 0 || i<1 || i>L.length)
    {
        return 0;
    }
    *e = L.data[i - 1];
    return 1;
} 
​
//元素的删除（删除L中第i个元素，并用e返回其值，L的长度-1）
int ListInsert(SqList* L, int i, ElemType  *e)
{
    int k;
    if (L->length == MAXSIZE)//线性表已满
    {
        return 0;
    }
    if (i<1 || i>L->length + 1)//当i不在范围内时
    {
        return 0;
    }
    *e = L->data[i - 1];
    if (i <= L->length)  //若插入位置不在表尾
    {
        //将要插入位置后数据元素向后移动一位
        for (k = i; klength; k++)
        {
            L->data[k -1] = L->data[k];
        }
    }
   
    L->length--;
    return 1;
}
//元素的插入 
int ListDelete(SqList* L, int i, ElemType *e)
{
    int k;
    if (L->length == MAXSIZE)//线性表已满
    {
        return 0;
    }
    if (i<1 || i>L->length)//当i不在范围内时
    {
        return 0;
    }
    if (i <= L->length)  //若插入位置不在表尾
    {
        //将要插入位置后数据元素向后移动一位
        for (k = L->length - 1; k >= i - 1; k--)
        {
            L->data[k + 1] = L->data[k];
        }
    }
    L->data[i - 1] = e;
    L->length++;
    return 1;
}

1.4 线性表顺序存储结构优缺点

优点： 一无须为表示表中元素之间的逻辑关系而增加额外的存储空间。 一可以快速地存取表中任意位置的元素。

缺点： 一插入和删除操作需要移动大量元素。 一当线性表长度变化较大时，难以确定存储空间的容量。 一容易造成存储空间的“碎片。

1.5 线性表的链式存储的结构代码

typedef struct Node
{
    ElemType data;          //数据域
    struct Node* next;      //指针域
}Node;
typedef struct Node* linkList;

1.6 单链表的操作

1.6.1 元素的读取

//元素读取(用e返回L中第i个元素的值)
int GetElem(linkList L, int i, ElemType* e)
{
    int j;
    linkList p;
    p = L->next;
    j = 1;
    while (p && j < i)
    {
        p = p->next;
        j++;
    }
    if (!p || j > i)
    {
        return 0;
    }
    *e = p->data;
    return 1;
}

1.6.2 元素插入

//元素的插入（在L中第i个位置之前插入新的数据元素e，工的长度加1）
int ListInsert(linkList* L, int i, ElemType e)
{
    int j;
    linkList p, s;
    p = *L;
    j = 1;
    while (p && j < i)  //用于寻找第i个结点
    {
        p = p->next;
        j++;
    }
    if (!p || j > i)
    {
        return 0;
    }
    s = (linkList)malloc(sizeof(Node));//分配内存地址
    s->data = e;
    s->next = p->next;
    p->next = s;
    return 1;
}

1.6.2 元素删除

//元素的删除（删除L的第i个数据元素,并用e返回其值，L的长度-1）
int ListDelete(linkList* L, int i, ElemType *e)
{
    int j;
    linkList p, q;
    p = *L;
    j = 1;
    while (p->next && j < i)
    {
        p = p->next;
        j++;
    }
    if (!(p->next) || j > i)
    {
        return 0;
    }
    q = p->next;
    p->next = q->next;
    *e = q->data;
    free(q);
    return 1;
}

1.7 单链表的整表创建

1.7.1 头插法建立单链表

头插法从一个空表开始,生成新结点,读取数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上,直到结束为止。简单来说,就是把新加进的元素放在表头后的第一个位置。

//头插法建立单链表
void CreateListHead(linkList* L, int n)
{
    linkList p;
    int i;
    srand(time(0));//初始话随机数种子
    *L = (linkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    for (i = 0; i < n; i++)      //通过for循环赋值
    {
        p = (linkList)malloc(sizeof(Node));
        p->data = rand()%100 + 1;   //可用scanf函数
        p->next = (*L)->next;   //类似于元素插入
        (*L)->next = p;
    }
}

1.7.2 尾插法建立单链表

//尾插法建立单链表
void CreateListTail(linkList* L, int n)
{
    linkList p,r;
    int i;
    srand(time(0));//初始话随机数种子
    *L = (linkList)malloc(sizeof(Node));
    r = *L;
    for (i = 0; i < n; i++)      //通过for循环赋值
    {
        p = (linkList)malloc(sizeof(Node));
        p->data = rand() %100 +1;   //可用scanf函数
        r->next = p;
        r = p;  // r指向最后一个结点
    }
}

1.7 单链表的整表删除

//删除单链表
int ClearList(linkList* L)
{
    linkList p, q;
    p = (*L)->next;
    while (p)
    {
        q = p->next;
        free(p);
        p = q;
    }
    (*L)->next = NULL;
    return 1;
}

1.8 链式结构与顺序结构优缺点

存储分配方式: 一顺序存储结构用一段连续的存储单元依次存储线性表的数据元素。 一单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素。

时间性能： 一查找 顺序存储结构0(1)·单链表0(n) 一插入和删除 顺序存储结构需要平均移动表长一半的元素，时间为0(n) 单链表在计算出某位置的指针后, 插入和删除时间仅为0(1)

空间性能: 一顺序存储结构需要预分配存储空间,分大了,容易造成空间浪费，分小了，容易发生溢出。 一单链表不需要分配存储空间，只要有就可以分配,元素个数也不受限制。

综上所述对比,我们得出一些经验性的结论: 一若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。 一若需要频繁插入和删除时，宜采用单链表结构。