1.线性表

1线性表

线性结构的特点: 在数据元素的非空有限集中。

							<1>存在惟一的一个被称为“第一个”的数据元素；
							<2>存在惟一的一个被称为“最后一个”的数据元素；
							<3>除第一个之外，集合中的每个数据元素均只有一个前驱；
							<4>除最后一个之外，集合中的每个数据元素均只有一个后继。
1
2
3
4

线性表：是最常用且最简单的一种数据结构。简言之，一个线性表是n个数据元素的有限序列。

线性表和数组的区别：
从概念上来看，线性表是一种抽象数据类型；数组是一种具体的数据结构。
线性表与数组的逻辑结构是不一样的，线性表是元素之间具有1对1的线性关系的数据元素的集合，而数组是一组数据元素到数组下标的一一映射 。
并且从物理性质来看， 数组中相邻的元素时连续地存储在内存中的；线性表只是一个抽象的数学结构，并不具有具体的物理形式，线性表需要通过其它具有物理形式的数据结构来实现。在线性表的具体实现中，表中相邻的元素不一定存储在连续的内存空间中，除非表是用数组来实现。
对于数组，可以利用其下标在一个操作内随机存取任意位置上的元素；对于线性表，只能根据当前元素找到其前驱或后继，因此要存取需要为i的元素，一般不能在一个操作内实现，除非表是用数组实现的。

在稍微复杂的线性表中，一个数据元素可以由若干个数据项组成。在这种情况下常把数据元素称为记录，含有大量记录的线性表又称为文件。并且线性表中的数据元素可以是各种各样的但同一线性表中必定具有相特性，即属同一数据对象，相邻数据元素之间存在着序偶关系。（连续的）

线性表中元素的个数n(n $\ge 0$)定义为线性表的长度，n=0时称为空表。在非空表中的每个数据元素都有一个确定的位置，如$a_1$是第一个数据元素，$a_n$是最后一数据元素，$a_i$是第i个数据元素，称i为数据元素$a_i$在线性表中的位序。（在线性表中第几个）

线性表是一个相当灵活的数据结构，它的长度可根据需求增长或者缩短，即对线性表的数据元素不仅可以进行访问，还可以进行插入和删除等。

1.1线性表的顺序表示和实现

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。（有点数组的味道）

假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置（通常称为线性表的起始位置或者基地址）。则线性表中的第i+1个数据元素的存储位置LOC($a_{i+1}$)和第i个数据元素的存储位置LOC($a_i$) 之间满足下列关系：
$$\begin{gathered} LOC(a_{i+1})=LOC(a_i)+l \\ LOC(a_i)=LOC(a_1)+(i-1)\ast l \end{gathered}$$
线性表的这种机内表示称作线性表的顺序存储结构或顺序映像(sequential mapping)，通常，这种存储结构的线性表称为顺序表（亦可以理解为动态数组，但是是可以插入或者删改的动态数组）。它的特点是，以元素在计算机内”物理位置相邻“来表示线性表中数据元素之间的逻辑关系。每一个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数。由此，只要确定了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。

1.1.1线性表的定义

由于线性表的长度可变，且所需最大的存储空间随问题不同而不同，在C语言中可用动态分配的一维数组。

#define List_Init_Size 100 //线性表存储空间的初始分配量
#define ListIncreMent 10   //线性表存储空间的分配增量
#define ElemType int
#define Status int

//定义线性表
typedef struct 
{
    ElemType *elem; //存储空间基地址
    int length;      //当前长度
    int listsize;    //当前分配的存储容量(以sizeof(ElemType)为单位)
}SqList;
1
2
3
4
5
6
7
8
9
10
11
12

在这段代码中，ElemType *elem; 是定义了一个结构体 SqList 中的成员变量。这里，ElemType 是一个类型的占位符，它表示该线性表存储的元素的类型。
ElemType *elem; 的意思是声明了一个指针 elem，这个指针指向某种类型为 ElemType 的数据。在这个上下文中，通常 elem 用来指向存储线性表元素的数组的首地址。
你可以将 ElemType *elem; 理解为指向数组的指针。实际上，这个指针指向线性表中存储元素的数组的起始地址，而数组的每个元素的类型是 ElemType。
在使用这个线性表时，你可以通过这个指针访问线性表中的元素，类似于数组的使用。例如，elem[0] 就表示线性表中的第一个元素，elem[1] 表示第二个元素，以此类推。

顺序表的初始化操作就是为顺序表分配一个预定义大小的数组空间，并将线性表的当前长度设置为0。listsize指示顺序表当前分配的存储空间大小，一旦因插入元素而空间不足时，可进行再分配，即为顺序表增加一个大小为存储ListIncreMent个数据元素的空间。

1.1.2初始化线性表

malloc函数说明

//初始化线性表
Status InitList_Sq(SqList &L)
{
    //构造一个空的线性表L。
    L.elem = (ElemType *)malloc(List_Init_Size * sizeof(ElemType));

    if(! L.elem) exit(0); //存储分配失败,停止运行
    L.length = 0;                //空表长度为0
    L.listsize = List_Init_Size; //初始存储容量
    return 1;
}
1
2
3
4
5
6
7
8
9
10
11

在这段代码中，&L 是传递结构体 SqList 的引用给函数 InitList_Sq。这样做的目的是允许函数修改调用者传递给它的实参，即允许函数对传入的结构体进行修改。
具体来说：
SqList &L: 函数的参数声明部分，表示传递一个 SqList 类型的引用。引用是 C++ 中的一种机制，它允许在函数内部直接操作调用者提供的实际变量，而不是复制一份变量的值。
Status ListDelete_Sq(SqList &L, int i, ElemType &e): 函数声明部分，表示函数接受一个 SqList 类型的引用作为参数。&L 表示传递 L 的引用，这样函数内部对 L 的修改会影响到调用者的原始 L。
int flag = InitList_Sq(L);: 在调用 InitList_Sq 函数时，传递的是结构体 SqList 的引用。这样 InitList_Sq 函数内对 L 的修改会影响到调用者的 L。

1.1.3线性表的插入

我们要注意的是，C语言中数组的下标是从“0”开始的，因此，若L是SqList类型的顺序表，则表中第i个元素是L.elem[i-1]。
在线性表的顺序存储结构中，由于逻辑上相邻的数据元素在物理位置上也是相邻的，因此，除非i=n+1，否则必须移动元素才能反映这个逻辑关系的变化。

如上图演示一样，为了在线性表的第4个和第5个元素之间插入一个值为25的数据元素，则需将第5~8个元素依次往后移动一个位置。一般情况下，在第$i(1\le i\le n)$个元素之前插入一个元素时，需要将n至第i（共n-i+1）个元素向后移动一个位置。
realloc函数说明

//向线性表中dii个位置后插入一个元素e
Status ListInsert_Sq(SqList &L, int i, ElemType e)
{
    //在顺序表L中第i个元素之前插入新的元素e
    // i的合法值为 1≤i≤ListLength_Sq(L) + 1

    if(i < 1 || i > L.length + 1) return 0; //i值不合法
    if(L.length >= L.listsize)              //存储空间已满，需要增加分配
    {
         ElemType *newbase;
         newbase = (ElemType *) realloc(L.elem, (L.listsize + ListIncreMent) * sizeof (ElemType));
         if(!newbase) exit(0);

         L.elem = newbase;
         L.listsize += ListIncreMent;
    }

    int* q = &(L.elem[i-1]); //q为插入位置
    for (int* p = &(L.elem[L.length - 1]); p >= q; --p) 
        *(p+1) = *p; //插入位置及之后的元素右移

    *q = e; //插入e
    ++L.length;
    return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

1.1.4线性表的删除

如图2.4，为了删除第四个数据元素，必须将从第5~8个元素依次向前移动一个位置。
一般情况下，删除第$i(1\le i\le n)$个元素时需要将从第i+1至第n（共n-i）个元素依次向钱移动一个位置。

//删除线性表中的一个元素
Status ListDelete_Sq(SqList &L, int i, ElemType &e)
{
    //在顺序线性表中删除第i个元素，并用e返回其值
    //i的合法值为1 ≤ i ≤ ListLength_Sq(L)
    if((i < 1) || (i > L.length)) return 0;   //i值不合法

    int* p = &(L.elem[i-1]);                  //p为被删除元素的位置
    e = *p;
    int* q = L.elem + L.length - 1;           //表尾元素的位置

    for(++p; p <= q; ++ p)
        *(p-1) = *p;                          //被删除元素之后的元素左移

    --L.length;
    return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

在顺序存储结构的线性表中某个位置上插入或删除一个数据元素时，其时间主要耗费在移动元素上，而移动元素的个数取决于插入或删除元素的位置。
假设$p_i$是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时所需要移动元素次数的期望值（平均次数）为
$$E_{is}=\sum _{i=1}^{n+1}{p}_i(n-i+1)$$
假设$q_i$是删除第i个元素的概率，则在长度为n的线性表中删除一个元素时所需移动元素次数的期望值（平均次数）为
$$E_{dl}=\sum _{i=1}^n{q}_i(n-i)$$
不失一般性，我们可以假定在线性表的任何位置上插入或删除元素都是等概率的，即：
$$p_i=\frac{1}{n+1},q_i=\frac{1}{n}$$

即：
$$\begin{gathered} E_{is}=\frac{1}{n+1}\sum _{i=1}^{n+1}(n-i+1)=\frac{n}{2} \\ {E}_{dl}=\frac{1}{n}\sum _{i=1}^n(n-i)=\frac{n-1}{2} \end{gathered}$$

在进行插入和删除操作，时间复杂度为O(n)。顺序表的“求表长”和取第i个数据元素的时间复杂度均为O(1)。在顺序表L中查访是否存在和e相同的数据元素的最简便方法是，令e和L中的数据元素逐个比较时间复杂度为O(L.length)。

1.1.5在顺序表中查找元素

//在顺序表中查找元素
int LocateElem_Sq(SqList &L, int e){

    //若找到,则返回其在L中的位序,否则返回0

    int i = 1;              //i的初值为第一个元素的位序
    int *p  = L.elem;       //p的初值为第一个元素的存储位

    while(i <= L.length){
        if(*p == e) break;
        ++i;
    }

    if(i <= L.length) return i;
    else return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1.1.6顺序表的合并

//顺序表的合并
void MergeList_Sq(SqList La, SqList Lb, SqList &Lc)
{
    // 已知顺序线性表La和Lb的元素按值非递减排列
    // 归并La和Lb得到新的顺序表Lc,Lc的元素也按值非递减排列

    int *pa = La.elem, *pb = Lb.elem; 
    Lc.listsize = Lc.length = La.length + Lb.length;
    int *pc = Lc.elem = (ElemType *) malloc(Lc.listsize * sizeof(ElemType));
    if(!Lc.elem) exit(0);  //存储分配失败

    int *pa_last = La.elem + La.length - 1; //获取La尾项位置
    int *pb_last = Lb.elem + Lb.length - 1;

    while(pa <= pa_last && pb <= pb_last)  //归并
    {
        if(*pa <= *pb) *pc++ = *pa++;
        else *pc++ = *pb++;
    }

    while(pa <= pa_last) *pc++ = *pa ++; //插入La剩余的元素
    while(pb <= pb_last) *pc++ = *pb ++; //插入Lb剩余的元素
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

代码汇总

#include
#include

#define List_Init_Size 100 //线性表存储空间的初始分配量
#define ListIncreMent 10   //线性表存储空间的分配增量
#define ElemType int
#define Status int

//定义线性表
typedef struct 
{
    ElemType *elem; //存储空间基地址
    int length;      //当前长度
    int listsize;    //当前分配的存储容量(以sizeof(ElemType)为单位)
}SqList;

//初始化线性表
Status InitList_Sq(SqList &L)
{
    //构造一个空的线性表L。
    L.elem = (ElemType *)malloc(List_Init_Size * sizeof(int));

    if(! L.elem) exit(0); //存储分配失败,停止运行
    L.length = 0;                //空表长度为0
    L.listsize = List_Init_Size; //初始存储容量
    return 1;
}

//向线性表中第i个位置后插入一个元素e
Status ListInsert_Sq(SqList &L, int i, ElemType e)
{
    //在顺序表L中第i个元素之前插入新的元素e
    // i的合法值为 1≤i≤ListLength_Sq(L) + 1

    if(i < 1 || i > L.length + 1) return 0; //i值不合法
    if(L.length >= L.listsize)              //存储空间已满，需要增加分配
    {
         ElemType *newbase;
         newbase = (ElemType *) realloc(L.elem, (L.listsize + ListIncreMent) * sizeof (ElemType));
         if(!newbase) exit(0);

         L.elem = newbase;
         L.listsize += ListIncreMent;
    }

    int* q = &(L.elem[i-1]); //q为插入位置
    for (int* p = &(L.elem[L.length - 1]); p >= q; --p) 
        *(p+1) = *p; //插入位置及之后的元素右移

    *q = e; //插入e
    ++L.length;
    return 1;
}

//删除线性表中的一个元素
Status ListDelete_Sq(SqList &L, int i)
{
    //在顺序线性表中删除第i个元素
    //i的合法值为1 ≤ i ≤ ListLength_Sq(L)
    if((i < 1) || (i > L.length)) return 0;   //i值不合法

    int* p = &(L.elem[i-1]);                  //p为被删除元素的位置
    int* q = L.elem + L.length - 1;           //表尾元素的位置

    for(++p; p <= q; ++ p)
        *(p-1) = *p;                          //被删除元素之后的元素左移

    --L.length;
    return 1;
}

//打印所有元素
void output(SqList &L)
{
    // printf("当前顺序表的长度:%d\n", L.length);

    for(int i = 0; i < L.length; i ++)
        printf("%d ", L.elem[i]);
    printf("\n");
}

//在顺序表中查找元素
int LocateElem_Sq(SqList &L, int e){

    //在顺序线性表L中查找第一个值与e满足compare()的元素的位序
    //若找到,则返回其在L中的位序,否则返回0

    int i = 1;              //i的初值为第一个元素的位序
    int *p  = L.elem;       //p的初值为第一个元素的存储位

    while(i <= L.length){
        if(*p == e) break;
        ++i, ++*p;
    }
    if(i <= L.length) return i;
    else return 0;
}

//顺序表的合并
void MergeList_Sq(SqList La, SqList Lb, SqList &Lc)
{
    // 已知顺序线性表La和Lb的元素按值非递减排列
    // 归并La和Lb得到新的顺序表Lc,Lc的元素也按值非递减排列

    int *pa = La.elem, *pb = Lb.elem; 
    Lc.listsize = Lc.length = La.length + Lb.length;
    int *pc = Lc.elem = (ElemType *) malloc(Lc.listsize * sizeof(ElemType));
    if(!Lc.elem) exit(0);  //存储分配失败

    int *pa_last = La.elem + La.length - 1; //获取La尾项位置
    int *pb_last = Lb.elem + Lb.length - 1;

    while(pa <= pa_last && pb <= pb_last)  //归并
    {
        if(*pa <= *pb) *pc++ = *pa++;
        else *pc++ = *pb++;
    }

    while(pa <= pa_last) *pc++ = *pa ++; //插入La剩余的元素
    while(pb <= pb_last) *pc++ = *pb ++; //插入Lb剩余的元素
}

int main()
{
    //合并两个线性表
    SqList La, Lb, Lc;
    InitList_Sq(La);
    InitList_Sq(Lb);

    ListInsert_Sq(La, 1, 3);
    ListInsert_Sq(La, 1, 1);
    printf("La:");
    output(La);

    ListInsert_Sq(Lb, 1, 3);
    ListInsert_Sq(Lb, 1, 2);
    ListInsert_Sq(Lb, 1, 1);
    printf("Lb:");
    output(Lb);

    MergeList_Sq(La, Lb, Lc);
    printf("Lc:");
    output(Lc);

    //查找元素是否存在顺序表中
    int flag1 = LocateElem_Sq(Lb, 2);

    if(flag1 == 0) printf("2不在顺序表Lb中\n");
    else printf("2在顺序表Lb中\n");

    //删除顺序表中的元素
    ListDelete_Sq(Lc, 1);
    printf("Lc: ");
    output(Lc);


    
    return 0; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159

1.2线性表的链式表示和实现

线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，因此可以随机存取表中任一元素，它的存储位置可以用一个简单、直观的公式来表示。然而，从另一方面看，这个特点也铸成了这种存储结构的弱点：在作插入删除操作时，需要移动大量元素。（是不需要移动大量元素，但是需要从头遍历到该操作的位置。）
而链式存储结构，由于它不要求逻辑上相邻的元素在物理位置上也相邻，因此它没有顺序存储结构所具有的弱点，但同时也失去了顺序表可随机存取的优点。

1.2.1线性链表

线性链表的链式结构的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素$a_i$于其直接后继元素$a_{i+1}$之间的逻辑关系，对数据元素$a_i$来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。着两部分信息组成数据元素$a_i$的存储映像，称为结点。它包括两个域：其中存储数据元素信息的称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称作指针或链。n个结点（$a_i(1\le i\le n)$ 的存储映像）链结成一个链表，即为线性表
$$a_1,a_2,a_3,...,a_n$$
的链式存储结构。由于次链表的每个结点中只包含一个指针域，故又称为线性链表或单链表。

如图所示为线性表：
（ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG）
整个链表的存取必须从头指针开始进行，头指针指示链表中第一个结点（即第一个数据元素的存储映像）的存储位置。同时，由于最后一个数据元素没有直接后继，则线性链表中最后一个结点的指针为“空”（NULL）。

用线性链表表示线性表时，数据元素之间的逻辑关系是由节点中的指针指示的。换句话说，指针为数据元素之间的逻辑关系的映像，则逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻，由此，这种存储结构为非顺序映像或链式映像。
通常我们把链表画成用箭头相连的结点的序列，结点之间的箭头表示链域中的指针。如上图的线性链表刻画成下图所示的形式，这是因为在使用链表时，关心的只是它所表示的线性表中数据元素之间的逻辑关系，而不是每个数据元素在存储器中的实际位置。

由上述可见，单链表可由头指针唯一确定，在C语言中可用“结构指针”来描述。

#include
#include

#define List_Init_Size 100 //线性表存储空间的初始分配量
#define ListIncreMent 10   //线性表存储空间的分配增量
#define ElemType int
#define Status int

typedef struct LNode{
    ElemType      data;
    struct LNode  *next;
}LNode, *LinkList;
1
2
3
4
5
6
7
8
9
10
11
12

假设L是LinkList型的变量，则L为单链表的头指针，它指向表中第一个结点。若L为“空”（L=NULL），则表示的线性表为“空”表，其长度n为“零”。有时，我们在单链表的第一个结点直接附设一个结点，称之为头节点。头节点的数据域可以不存储任何信息，也可存储如线性表的长度等类的附加信息，头结点的指针域存储指向第一个结点的指针（即第一个元素节点的存储位置）。如下图所示，此时，单链表的头指针指向头结点。若线性表为空表，则头结点的指针域为“空”，如下图所示：

1.2.2获取该位置的元素

在线性表的顺序存储结构中，由于逻辑上相邻的两个元素在物理位置上紧邻，则每个元素的存储位置都可以从线性表的起始位置计算得到。而在单链表中，任何两个元素的存储位置之间没有固定的联系。然而，每个元素的存储位置都包含在其直接前驱结点的信息之中。假设p是指向线性表中第i个数据元素（结点$a_i$）的指针，则p->next是指向第i+1个数据元素（结点$a_{i+1}$）的指针。换句话说，若p->data=$a_i$，则p->next->data=$a_{i+1}$。由此，在单链表中，取得第i个数据元素必须从头指针出发寻找，因此，单链表是表是非随机存取的存储结构。
单链表中函数GetElem在单链表中的实现。时间复杂度O(N)

Status GetElem_L(LinkList L, int i, ElemType &e)
{
    //L为带头结点的单链表的头指针。
    //当第i个元素存在时，其值赋给e并返回1，否则返回0。

    LinkList p = L->next;
    int j = 1;

    while(p && j < i)
    {
        p = p->next;
        ++j;
    }

    if(!p || j > i) return 0;
    e = p->data;
    return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1.2.3线性链表的插入

假设我们要在线性表的两个数据元素a和b之间插入一个数据元素x，已知p为其单链表存储结构中指向结点a的指针。如图a所示。
为插入数据元素x，首先要生产一个数据域为x的结点，然后插入在单链表中。根据插入操作的逻辑定义，还需要修改节点a中的指针域，令其指向结点x，而结点x中的指针域应指向结点b，从而实现3个元素a、b和x之间逻辑关系的变化。插入后的单链表如图b所示。假设s为指向结点x的指针，则上述指针修改用语句描述即为：
s->next = p->next; p->next = s;

时间复杂度O(n)

Status ListInsert_L(LinkList &L, int i, ElemType e)
{
    //在带头结点的单链线性表L中第i个位置之前插入
    LinkList p = L;
    int j = 0;

    while(p && j < i-1)
    {
        p = p->next;
        ++j;
    }

    if(!p || j > i) return 0;
    LinkList s = (LinkList) malloc(sizeof (LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1.2.4线性链表的删除

反之，如下图所示在线性表中删除元素b时，为在单恋表中实现元素a、b和c之间逻辑关系的变化，仅需要修改结点a中的指针域即可。假设p为指向结点a的指针，则修改指针的语句为：
p->next = p->next->next;
时间复杂度O(n)

Status ListDelete_L(LinkList &L, int i, ElemType &e){
    //带头结点的单链线性表L中，删除第i个元素，并由e返回其值
    LinkList p = L;
    int j = 0;

    while(p->next && j < i-1)
    {
        p = p->next;
        ++j;
    }

    if(!(p->next) || j > i - 1) return 0; //删除位置不合理
    LinkList q = p->next;                 //删除并释放结点
    p->next = q->next;
    e = q->data;  free(q);

    return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

我们分别引用了C语言的两个标准函数malloc和free。通常，在没有“指针”数据类型的高级语言中俊存在与其相对应的过程或函数。假设p和q是LinkList型的变量，则执行p=(LinkList) malloc(sizeof (LNode))的作用是由系统生成一个LNode型的结点，同时将该节点的起始位置赋给指针变量p；反之，执行free(q)的作用是由系统回收一个LNode型的结点，回收后的空间可以备作再次生成结点时用。因此，单链表和顺序存储结构不同，它是一种动态结构。整个可用存储空间可为多个链表共同享用，每个链表占用的空间不需预先分配划定，而是可以由系统应需求即时生成。因此，建立线性表的链式存储结构的过程就是一个动态生成链表的过程。即从“空表”的初始状态起，依次建立各元素结点，并逐个插入链表。

1.2.5线性链表的建立

时间复杂度O(n)

void CreateList_L(LinkList &L, int n)
{
    // 逆位序输入n个元素的值，建立带表头结点的单链线性表L。
    L = (LinkList) malloc(sizeof (LNode));
    L->next = NULL;                                     //先建立一个带头结点的单链表

    for (int i = n; i > 0; --i)
    {
        LinkList p = (LinkList) malloc(sizeof (LNode)); //生成新结点
        scanf("%d", &p->data);
        p->next = L->next;
        L->next = p;                                    //插入到表头
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

每次都是把一个数插到头结点后面，所以顺序是相反的。

1.2.6将两个有序链表合并为一个有序链表

假设头指针为La和Lb的单链表分别为线性表LA和LB的存储结构，现要归并La和Lb得到单链表Lc，按照线性顺序表的合并的思想，需要设立三个指针pa，pb和pc，其中pa和pb分别指向La表和Lb表中当前待比较插入的结点，而pc指向Lc表中当前最后一个结点，若pa->data $\le$pb->data，则将pa所指结点链接到pc所指结点之后，否则将pb所指结点链接到pc所指结点之后。显然，指针的初始状态为：当LA和LB为非空表时，pa和pb分别指向La和Lb表中第一个结点，否则为空；pc指向空表Lc中的头结点。由于链表的长度为隐含的，则第一个循环执行的条件时pa和pb皆非空，当其中一个为空时，说明有一个表的元素已归并完，则只要将另一个表的剩余段链接在pc所指结点之后即可。由此得到归并两个单链表的算法。要求两个链表的是有序排列的。

void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc)
{
    LinkList pa = La->next, pb = Lb->next;
    LinkList pc = La;
    Lc = La;

    while(pa && pb)
    {
        if(pa->data <= pb->data)
        {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        }
        else
        {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }
    pc->next = pa ? pa : pb;
    free(Lb);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24