线性表(代码分解）

完整篇代码链接：https://www.cnblogs.com/ouyang_wsgwz/p/7695713.html

线性表的基本操作

抽象数据类型线性表的定义：

ADT List {

　　数据对象：D＝{ a_i | a_i ∈ ElemSet, i = 1, 2, ... , n, n≥0 }

　　数据关系：R1＝{ < a_i-1 ,a_i > |  a_i-1 , a_i ∈ D,  i = 2, ... , n }

 

　　基本操作：

　　　　InitList( &L )

　　　　　　操作结果：构造一个空的线性表 L 。

　　　　DestroyList( &L )

　　　　　　初始条件：线性表 L 已存在。

　　　　　　操作结果：销毁线性表 L 。
　　　　ClearList( &L )

　　　　　　初始条件：线性表 L 已存在。

　　　　　　操作结果：将 L 重置为空表。

　　　　ListEmpty( L )

　　　　　　初始条件：线性表L已存在。

　　　　　　操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE。

　　　　ListLength( L )

　　　　　　初始条件：线性表 L 已存在。

　　　　　　操作结果：返回 L 中元素个数。

　　　　GetElem( L, i, &e )
　　　　　　初始条件：线性表 L 已存在，1≤i≤LengthList(L)。

　　　　　　操作结果：用 e 返回 L 中第 i 个元素的值。

　　　　LocateElem( L, e, compare( ) )

　　　　　　初始条件：线性表 L 已存在，compare( ) 是元素判定函数。

　　　　　　操作结果：返回 L 中第1个与 e 满足关系 compare( ) 的元素的位序。若这样的元素不存在，则返回值为0。

　　　　PriorElem( L, cur_e, &pre_e )
　　　　　　初始条件：线性表 L 已存在。

　　　　　　操作结果：若 cur_e 是 L 中的数据元素，则用 pre_e 返回它的前驱，否则操作失败，pre_e 无定义。

　　　　NextElem( L, cur_e, &next_e )

　　　　　　初始条件：线性表 L 已存在。

　　　　　　操作结果：若 cur_e 是 L 中的数据元素，则用 next_e 返回它的后继，否则操作失败，next_e 无定义。

　　　　ListInsert( &L, i, e )

　　　　　　初始条件：线性表 L 已存在，1≤i≤LengthList(L) + 1。

　　　　　　操作结果：在 L 的第 i 个元素之前插入新的元素 e，L 的长度增1。

　　　　ListDelete( &L, i, &e )

　　　　　　初始条件：线性表 L 已存在且非空，1≤i≤LengthList(L)。

　　　　　　操作结果：删除 L 的第 i 个元素，并用 e 返回其值，L 的长度减1。

　　　　ListTraverse(L, visit( ))

　　　　　　初始条件：线性表 L 已存在，visit( ) 为元素的访问函数。

　　　　　　操作结果：依次对 L 的每个元素调用函数 visit( )。一旦 visit( ) 失败，则操作失败。

} ADT List

对上述定义的抽象数据类型线性表，还可以进行一些更复杂的操作。

　　例如将两个线性表合并成一个线性表：

　　1.新集合 A = A U B

void union(List &La, List &Lb) {
    // 将所有在线性表Lb中但不在La中的数据元素插入到La中

    //求线性表的长度
    La_len = ListLength(La);
    Lb_len = ListLenght(Lb);

    for (i = 1; i <= Lb_len; i++) {
        GetElem(Lb, i, e);            //取Lb中第i个数据元素赋给e
        if (!LocateElem(La, e, equal))
            ListInsert(La, ++La_len, e);
            //La中不存在和e相同的数据元素，则插之
    }
}// union

　　2.新的线性表 LC = LA + LB ,其中LA, LB, LC，都是非递减有序排列

void MergeList(List La, List Lb, List &Lc) {
    // 已知线性表La和Lb中的数据元素按值非递减排列。
    // 归并La和Lb得到新的线性表Lc, Lc的数据元素也按值非递减排列。

    InitList(Lc);
    i = j = 1;    k = 0;
    La_len = ListLength(La); Lb_ListLength(Lb);
    while ((i <= La_len) && (i <= Lb_len)) { // La和Lb均非空
        GetElem(La, i, ai); GetElem(Lc, ++k, bj);
        if (ai <= bj) {
            ListInsert(Lc, ++k, ai);
            ++i;
        }
        else {
            ListIsnert(Lc, ++k, bj);
            ++j;
        }
        
        while (i <= La_len) {
            GetElem(La, i++, ai);
            ListInsert(Lc, ++k, ai);
        }
        while (j <= Lb_len) {
            GetElem(Lb, j++, bj);
            ListInsert(Lc, ++k, bj);
        }
    }
}// MergeList

线性表的顺序表示

1.静态分配

#define MaxSize 50　　            //定义线性表的最大长度
typedef struct {
    ElemType data[MaxSize];        //顺序表的元素
    int length;                    //顺序表的当前长度
}SqList;                        //顺序表的类型定义

2.动态分配

#define InitSize 100        //表长度的初始定义
typedef struct {            
    ElemType *data;            //指示动态分配数组的指针
    int MaxSize, length;    //数组的最大容量和当前个数
} SeqList;                    //动态分配数组顺序表的类型定义

顺序表上基本操作的实现

1.插入操作（将元素e插入到顺序表L中第i个位置）

bool ListInsert(SqList &L, int i, ElemType e) {
    if (i < 1 || i > L.length + 1)            //判断i的范围是否有效
        return false;
    if (L.length >= MaxSize)                //当前存储空间已满，不能插入
        return false;
    for (int j = L.length; j >= i; j--)        //将第i个元素及之后的元素后移
        L.data[j] = L.data[j - 1];    
    L.data[i - 1] = e;                        //在位置i处放入e
    L.length++;                                //线性表长度加1
    return true;
}

　　最好情况：在表尾插入（即 i = n+1），元素后移语句将不执行，时间复杂度为O(1)。

　　最坏情况：在表头插入（即 i = 1），元素后移语句将执行n次，时间复杂度为O(n)。

　　平均情况：假设p_i （p_i = 1/(n+1)）是在第i个位置上插入一个结点的概率，则在长度为n的线性表中插入一个结点时，所需移动的结点的平均次数为

　　　　

　　 因此，线性表插入算法的平均时间复杂度为O(n)。

2.删除操作（实现删除顺序表L中第i个位置的元素）

bool ListDelete(SqList &L, int i, ElemType &e) {
    if (i < 1 || i > L.length)
        return false;
    e = L.data[i - 1];;
    for (int j = i; j < L.length; j++) {
        L.data[j - 1] = L.data[j];
    }
    L.length--;
    return true;
}

同上，时间复杂度也为O(n)

3.按值查找（查找顺序表中值为e的元素，如果查找成功，返回元素位序，否则返回0）

int LocateElem(SqList L, ElemType e) {
    int i;
    for (i = 0; i < L.length; i++)
        if (L.data[i] == e)
            return i + 1;
    return 0;                            //退出循环查找失败
}

时间复杂度也为O(n)。

线性表的链式表示

单链表（线性表的链式存储）中的结点类型为：

typedef struct LNode {        //定义单链表结点类型
    ElemType data;            //数据域
    struct LNode *next;        //指针域
} LNode, *LinkList;

1.采用头插法建立单链表

LinkList List_HeadInsert(LinkList &L) {
    LNode *s; int x;
    L = (LinkList)malloc(sizeof(LNode));        //创建头结点
    L->next = NULL;                                //初始化为空链表
    scanf("%d", &x);                            //输入结点的值
    while (x != 9999) {                            //输入9999表示结束
        s = (LNode *)malloc(sizeof(LNode));        //创建新结点
        s->data = x;
        s->next = L->next;
        L->next = s;                            //将新结点插入表中，L为头指针
        sealed("%d", &x);
    }
    return L
}

采用头插法建立单链表时，读入数据的顺序与生成的链表中的元素的顺序是相反的。每个节点插入的时间为O(1)，设单链表长为n，则总时间复杂度为O(n)。

2.采用尾插法建立单链表

LinkList List_TailInsert(LinkList &L) {
    int x;                                    //设元素类型为整型
    L = (Link    List)malloc(sizeof(LNode));    
    LNode *s, *r = L;                        //r为表尾指针
    scanf("%d", &x);                        //输入结点的值
    while (x != 9999){                        //输入9999表示结束
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;                                //r指向新的表尾结点
        scanf("%d", &x);
    }
    r->next = NULL;                            //尾结点指针置空
    return L;
}

时间复杂度跟头插法相同

3.按序号查找结点值

 （取出单链表L带头结点中的第i个位置的结点指针）

LNode *GetElem(LinkList L, int i) {
    int j = 1;
    LNode *p = L->next;
    if (i == 0) return L;
    if (i < 1) return NULL;
    while (p && j < i) {
        p = p->next;
        j++;
    }
    return p;
}

按序号查找操作的时间复杂度为O(n)

4.按值查找表结点

（查找单链表L带头节点中数据域等于e的结点指针，否则返回NULL）

LNode *LocateElem(LinkList L, ElemType e) {
    LNode *p = L->next;                    
    while (p != NULL && p->data != e)    //从第1个结点开始查找data域为e的结点
        p = p->next;
    return p;                            //找到后返回该结点指针，否则返回NULL
}

5.插入结点操作

　　插入结点操作将值为x的新结点插入到单链表的第i个位置上。代码片段如下：

　　 p = GetElem(L, i - 1); s->next = p->next; p->next = s; 

　　本算法主要的时间开销在于查找第i-1个元素，时间复杂度为O(n)。若在给定的结点后面插入新结点，则时间复杂度仅为O(1)。

　　扩展：对某一结点进行前插操作。

//将*s结点插入到*p之前的主要代码片段
s->next = p->next;        //修改指针域，不能颠倒
p->next = s;
temp = p->data;            //交换数据域部分
p->data = s->data;
s->data = temp;

6.删除结点操作

p = GetElem(L, i - 1);    //查找删除位置的前驱结点
q = p->next;            //令q指向被删除结点
p->next = q->next;        //将*q结点从链中“断开”
free(q);                //释放结点的存储空间

和插入算法一样。该算法的主要时间也耗费在查找操作上，时间复杂度为O(n)。

　　扩展：删除结点*p。

　　要删除某个给定的结点*p，通常的做法是先从链表的头结点开始顺序找到其前驱结点，然后再执行删除操作，算法的时间复杂度为O(n)。

　　其实，删除结点*p的操作可用删除*p的后继结点操作来实现，实质就是将其后继节点的值赋予其自身，然后删除后继结点，也能使得时间复杂度为O(1)。

　　代码片段如下：

q = p->next;                //令q指向*p的后继结点
p->data = p->next->data;    //和后继结点交换数据域
p->next = q->next;            //将*q结点从链中断开
free(q);                    //释放后继结点的存储空间

7.求表长操作

　　求表长操作就是计算单链表种数据结点（不含头结点）的个数，需要从第一个结点开始顺序依次访问表中的每个结点，在访问时，计数器变量加1，直到空结点为止。算法的时间复杂度为O(n)。

 

双链表

双链表中结点类型的描述如下：

typedef struct DNode {                //定义双链表结点类型
    ElemType data;                    //数据域
    struct DNode *prior, *next;        //前驱和后继指针
}DNode, *DLinklist;

1.双链表的插入操作

在双链表中p所指的结点之后插入结点*s，代码片段如下：

  //双链表的插入操作 s->next = p->next; //将结点*s插入到结点*p之后 p->next->prior = s; s->prior = p; p->next = s; 

2.双链表的删除操作

代码片段如下：

//p 为 q的前一个节点
//删除q节点
p->next = q->next;    
q->next->prior = p;
free(q);

注：在建立双链表的操作中，也可采用如同单链表的头插法和尾插法，但在操作上需要注意指针的变化和单链表有所不同。

循环单链表

　　在循环单链表中，表尾结点*r 的next 域指向L，故表中没有之指针域为NULL的结点，因此，循环单链表的判空条件不是头结点的指针是否为空，而是它是否等于头结点。

　　循环单链表的插入、删除算法与单链表的几乎一样，所不同的是若操作是在表尾进行，则执行的操作不同，以让单链表继续保持循环的性质。正因为循环单链表是一个“环”，因此在任何一个位置上的插入和删除操作都是等价的，无须判断是否是表尾。

　　在单链表中只能从表头结点开始往后顺序遍历整个链表，而循环单链表可以从表中的任意一个结点开始遍历整个链表。有时对单链表常做的操作是在表头和表尾进行的，此时对循环单链表不设头指针而仅设尾指针，从而使得操作效率更高。其原因是，若设的是头指针，对表尾进行操作需要O(n)的时间复杂度，而若设的是尾指针 r，r->next 即为头指针，对于表头和表尾进行操作都只需要O(1)的时间复杂度。

循环双链表

　　由循环单链表的定义推出循环双链表，不同的是在循环双链表中，头结点的prior 指针还要指向表尾结点。

　　在循环双链表L中，某结点*p 为尾结点时，p->next == L; 当循环单链表为空表时，其头结点的 prior 和 next 都等于 L。

静态链表

　　静态链表是借助数组来描述线性表的链式存储结构，结点也有数据域data 和指针域 next，与前面讲的链表中的指针不同的是，这里的指针是结点的相对地址（数组下标），又称游标。

和顺序表一样，静态链表也要预先分配一块连续的内存空间。

　　静态链表的结构类型描述如下：

#define MaxSize 50        //静态链表的最大长度
typedef struct {        //静态链表结构类型的定义
    ElemType data;        //存储数据元素
    int next;            //下一个元素的数组的下标
} SLinkList[MaxSize];

静态链表以 next ==  -1;作为其结束的标志。静态链表的插入、删除操作与动态链表的相同，只需要修改指针，而不需要移动指针，而不需要移动元素。总体来说，静态链表没有单链表使用起来方便。

顺序表和链表的比较

1.存取方式

　　顺序表可以顺序存取，也可以随机存取，链表只能从表头存取元素。

2.逻辑结构与物理结构

　　采用顺序存储时，逻辑上相邻的元素，其对应的物理存储位置也是相邻的。而采取链式存储时，逻辑上相邻的元素，其物理存储位置则不一定相邻，其对相应的逻辑关系是通过指针链接来表示的。

　　注意区别存取方式和存储方式

3.查找、插入和删除

　　对于按值查找，顺序表无序时，两者的时间复杂度为O(n)；顺序表有序时，可采用折半查找，此时的时间复杂度为O(log₂n)。

　　对于按序号查找，顺序表支持随机访问（即根据数组的下标访问即可），时间复杂度为O(1)，而链表的平均时间复杂度为O(n)。顺序表的插入、删除操作，平均需要移动半个表长的元素。链表的插入、删除操作，只需要修改相关结点的指针域即可。由于链表的每个结点都带有指针域，因而在存储空间上要比顺序存储付出的代价大，而存储密度的不够大。

4.空间分配

　　顺序表在静态存储分配的情形下，一旦存储空间装满就不能扩充，若再加入新元素，则会出现内存溢出，因此需要预先分配足够大的存储空间。预先分配过大，可能会导致顺序表后部大量闲置，造成资源浪费；预先分配内存过小，又会造成溢出。动态存储分配虽然存储空间可以扩充，但需要移动大量的元素，导致操作效率降低。而且若内存中没有更大块的连续存储空间，则会导致分配失败。链式存储的结点空间只在需要时申请分配，只要内存中有空间就可以分配，操作灵活、高效。