线性表的类型定义
线性表是n个数据元素的有限序列。在稍复杂的线性表中，一个数据元素可以由若干个数据项组成，此时把数据元素称为记录，含有大量记录的线性表称为文件。例如：
| 姓名 | 年龄 | 学号 | 成绩 |
|---|---|---|---|
| 张一 | 19 | 001 | 100 |
| 王二 | 19 | 002 | 95 |
- 每一行称作数据元素
- 姓名、年龄、学号和成绩称为数据项
由此可见，线性表中数据元素可以是各式各样的，但同一线性表中的元素必定具有相同特性。相邻数据元素之间存在着序偶关系。除首尾，每个元素都有唯一前驱和唯一后继。
- 抽象数据类型线性表的定义
ADT List{
数据对象：D = {ai | ai ∈ ElemSet, i =1,2, ... , n, n≥0}
数据关系：R1 = {<ai-1,ai> | ai-1, ai∈D， i=2 ,3, ..., 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已存在
操作结果：用e返回L中第i个元素
LocateElem( L, e, compare() )
初始条件：线性表L已存在，compare()是数据元素判定函数
操作结果：返回L中第一个与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返回其后继；否则操作失败，pre_e无定义
ListInsert(& L, i ,e )
初始条件：线性表L已存在, 1<= i <= ListLength(L)+1
操作结果：在L的第i个位置之前插入e，L的长度自增一
ListDelete(& L , i , &e)
初始条件：线性表L已存在且非空，1<= i <= ListLength(L)
操作结果：删除L中第i个元素，并用e返回其值，L长度减一
ListTraverse( L, visit() )
初始条件：线性表L已存在
操作结果：对L中每个数据元素调用visit(), 一旦visit()失败，则操作失败
}ADT List
/*
对抽象类型线性表，还可以进行一些更为复杂的操作。如，合并或拆分表等
*/
算法 2.1——归并线性表
- 归并
用LA和LB表示A和B两个集合，现要求一个新的集合A = A∪B。即扩大LA，将存在于LB而不存在于LA的元素插入到LA中 - 算法实现
void union(List &La, List Lb){
La_len = ListLength(La);Lb_len = ListLength(Lb);
for (i=1; i<=Lb_len; ++i){
GetElem(Lb, i, e); //遍历Lb中元素
if( !ListLocate(La, e, equal) ){ //判断e是否在La中
ListInsert(La, ++La_len, e ); //将e插入至La末尾
}
}
}
算法2.2——归并排序
- 归并排序
线性表La和Lb中元素按值非递减有序排列，要求将La和Lb合并，并保证值非递减。
如La = （1，2，3，3，5）；Lb = （2，2，4，8）
归并为：Lc = （1，2，2，2，3，3，4，5，8）
相对于一个排序一个长表，将两个短表排序后归并的效率要更高一些
问题解析
将Lc设置为空表，然后将La和Lb中元素逐个插入Lc即可。插入元素满足c = a≤ b?a:b，其中a，b分别属于La和Lb算法实现
void MergeList(List La, List Lb, List &Lc){
InitList(Lc);
i = j = 1; k = 0;
La_len = ListLength(La);
Lb_len = ListLength(Lb);
while((i<=La_len)&&(j<=Lb_len)){ //当La和Lb均非空时
GetElem(La, i, ai);
GetElem(Lb, j, bj);
if(ai <= bj){
ListInsert(Lc, ++k, ai);
++i;
}
else{
ListInsert(Lc, ++k, bj);
++j;
}
}
while(i <= La_len){ //La非空时
GetElem(La, i++, e);
ListInsert(Lc, ++k, e);
}
while(j <= Lb_len){
GetElem(Lb, j++, e);
ListInsert(Lc, ++k, e);
}
}
上述两个算法的时间复杂度取决于抽象数据类型List定义中基本操作的执行时间。如GetElem（定位）和ListInsert与表长无关，因此时间复杂度为O(1)，LocateElem（逐个元素操作）与表长有关，则算法2.1时间复杂度为O(ListLength(La) * ListLength(Lb))，2.2为O(ListLength(La) + ListLength(Lb))。
线性表的顺序表示和实现
线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。他的特点是，为表中相邻的元素a1和a2赋以相邻的存储位置LOC(a1)和LOC(a2)。换句话说，以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系。
假设每个元素需占用m个存储单元，并以所占的第一个单元的存储地址作为元素的存储位置。则线性表的第i个元素ai的存储位置满足LOC(ai) = LOC(a1) + (i-1)*m。式中LOC(a1)称作线性表的起始位置或基地址。
顺序表只要确定了存储的起始位置，就可以随机存取线性表中任一数据元素，因此顺序存储结构是一种随机存取的存储结构。
- C语言中常用一维动态数组描述数据结构中的顺序存储结构。描述如下
//---线性表的动态分配顺序存储结构--- #define LIST_INIT_SIZE 100 //线性表存储空间初始分配量 #define LISTINCREMENT 10 //线性表存储空间分配增量 typedef struct{ ElemType *elem; //存储空间基地址，等价于数组名 int length; //当前长度 int listsize; //当前分配的存储容量 }SqList;
- typedef是自定义数据类型 Sqlist是自定义数据类型名
顺序表的初始化操作就是
- 为顺序表分配一个预定义大小(LIST_INIT_SIZE)的数组空间
- 将线性表当前长度设为“0”（具体参见算法2.3）
- 一旦因插入元素导致空间不足（大于listsize）时，可进行再分配，即为顺序表增加一个大小为存储LISTINCREMENT个数据元素的空间
- 上述代码等价于
struct List{
ElemType* elem;
int length;
int listsize;
}
#typedef List SqList;
算法 2.3——初始化线性表
- 算法实现
Status InitList_Sq(SqList &L){ //SqList是自定义的数据类型
L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));// malloc分配一个满足他的存储空间，并返回指向它的指针
if(! L.elem) {exit(OVERFLOW);} //存储分配失败，溢出
L.length = 0; //空表长度为0
L.listsize = LIST_INIT_SIZE; //初始存储容量
return OK;
}
顺序存储结构下线性表元素的插入与删除
由于逻辑上相邻的数据元素在物理位置上也是相邻的，因此必须移动元素才能反应这个逻辑关系的变化。
算法 2.4——插入
- 插入：在第i（1≤ i≤ n）个元素之前插入一个元素时，需将第n至第i（共n-i+1）个元素向后移动一个位置
- 算法实现
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 ERROR;
if (L.length > L.listsize){ // 当前长度大于当前分配的存储容量，即当前存储空间已满 增加分配
newbase = (ElemType* )realloc(L.elem, (L.listsize+LISTCREMENT)*sizeof(ElemType));
if(!newbase)
exit(OVERFLOW); //若重新分配失败，证明溢出
L.elem = newbase; //新基地址，相当于数组名
L.listsize += LISTINCREMENT; //增加存储容量
}
q = &(L.elem[i-1]) //q是插入位置，elem等价于数组名
for (p = &(L.elem[L.length-1]); p>= q; --p){ //从末尾开始，将q及以后的所有元素向右移动
*(p+1) = *p;
}
*q = e; //插入e
++L.length; //表长增一
return OK;
}// ListInsert_Sq
算法 2.5——删除
- 删除：删除第i（1≤ i≤ n）个元素时，需将第i至第n（共n-i）个元素向前移动一个位置
- 算法实现
Status ListDelete_Sq(SqList& L, int i, ElemType &e){ //用e返回被删除的元素
//i的合法值为1<= i <= L.length，与插入操作不同
if(i<1 || i>L.length)
return ERROR;
p = &(L.elem[i-1]);
e = *p;
q = &(L.elem[L.length-1]); //等价于 q = L.elem+L.length-1
for(p ; p<= q; p++ ){
*(p-1) = *p;
}
--L.length;
} //ListDelete_Sq
插入与删除算法时间主要耗费在移动元素上，故移动元素的操作为基本操作，而移动元素的个数取决于插入或删除的位置。
插入和删除元素的时间复杂度
- 插入元素时间复杂度：假设Pi是在第i个元素元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时所需移动元素的期望值（平均次数）为：
（1） -
删除元素时间复杂度：假设Qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素时所需移动元素的期望值（平均次数）为：
（2）
不失一般性，可以假定在线性表的任何位置上插入或删除元素都是等概率的，即
则式(1)和式(2)可分别简化为
（3）
（4）
由此可见，平均需要移动约一半的元素。若表长为n，算法ListInsert_Sq和ListDelete_Sq的时间复杂度为O(n)。
算法 2.6——顺序表的union
- 归并（顺序表）：基本操作是“进行两个元素的比较”，若L中存在与e相同的元素ai，则比较次数为1<= i <= L.length，否则为表长，即算法LocateElem_Sq的时间复杂度为O(L.length)，所以对于La和Lb而言，其时间复杂度为O(La.length*Lb.length)
- 算法实现
int LocateElem_Sq(SqList L, ElemType e, Status ( *compare)(ElemType, ElemType)){
//在顺序线性表L中查找第1个与e满足compare()的位序
//若找到则返回位序，否则返回0
i = 1;
np = L.elem; //数组名，第一个元素存储位置
while (i <= L.length && !( *compare) ( *p++, e)){ //判断是否存在满足compare函数的元素
i++;
}
if( i <= L.length){
return i;
}
return 0;
}
算法 2.7——顺序表的归并
- 归并排序（顺序表） 显然顺序表归并的基本操作是“元素赋值”，算法时间复杂度为O(La.length + Lb.length)。已知La和Lb中元素单调非减排列，现要求构造Lc归并排列。
- 算法实现
void MergeList_Sq( SqList La, SqList Lb, SqList& Lc){
//用Lc返回新的列表
pa = La.elem; pb = Lb.elem;
//需要为Lc的三个属性都赋值
Lc.listsize = Lc.length = La.length + Lb.length; //伪代码连续赋值
pc = Lc.elem = (ElemType* )malloc(sizeof(ElemType )* Lc.listsize);
if(! pc)
exit(OVERFLOW);
pa_last = La.elem + La.length -1; //取末尾位置
pb_last = Lb.elem + Lb.length -1;
while( pa <= pa_last && pb <= pb_last ){
if(*pa >= *pb)
*pc++ = *pb++;
else
*pc++ = *pa++;
}
while (pa <= La.length){
*pc++ = *pa++;
}
while (pb <= Lb.length){
*pc++ = *pb++;
}
} //MergeList_Sq
顺序表的优缺点
- 优点
- 节省存储空间
- 对第i个节点操作易于实现
- 容易查找一个节点的前驱和后继
- 缺点
- 插入和删除操作困难
线性表的链式表示和实现
不要求逻辑上相邻的元素在物理位置上也相邻
一个线性表由若干个结点组成，每个结点至少含有两个域：数据域（信息域）和指针域（链域），这样的结点形成存储的线性表称作链表
在使用链表时，关心的只有它所表示的线性表中数据元素之间的逻辑顺序，而不是在存储器中的实际位置。
线性链表（单链表）
- 逻辑关系
数据元素之间的逻辑关系是由结点中的指针指示的。指针为数据元素之间的逻辑关系的映像，逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻。 - 头结点
本身不存放数据，指针域指向第一个元素的地址。使对第一个元素的操作与对其他元素的操作保持一致。用头指针指向头结点。 -
结构示意图
结构指针
typedef struct Lnode{
//单链表存储结构
ElemType data; //数据域
struct Lnode *next; //单链表指针域
}LNode, *LinkList; // 此行直接定义了 链LNode 和 头指针LinkList 类型名
LinkList L; //LinkList是指针类型的struct Lnode,L为单链表的头指针
链表的嵌套定义：嵌套定义的前提是已知所需分配的空间。链表可嵌套定义是因为所有指针变量所需空间大小是确定的，不受指针基类型的影响。
算法 2.8——GetElem在单链表中的实现
- 在单链表中取元素：在单链表中，取得第i个元素的信息，必须从头指针出发寻找。
- 算法实现
Status GetElem_L(LinkList L, int i, ElemType& e){
//假设L是带头结点链表的头指针， 用e返回获得的结果
p = L->next; j =1; //初始化指针，使p指向第一个结点；用j作为计数器
while(p && j<i){
p = p->next;
++j;
}
if( !p||j>i)
return ERROR;
e = p -> data;
return OK:
}
GetElem时间复杂度
while循环体中的语句频度和被查元素在表中位置有关，若1< i≤ n则频度为 i-1，否则为n。因此时间复杂度为线性O(n)。
算法 2.9——单链表插入新结点
- 插入： 为在a和b元素中插入新元素x，根据插入操作的逻辑定义，首先要修改结点a中的指针域，令其指向结点x，而结点x的指针域指向结点b。假设s为指向结点x的指针，则上述操作的语句描述为： s->next = p->next; p->next = s
-
插入元素原理图
- 算法实现
Status ListInsert_L (LinkList& L, int i, ElemType e){
//在带头结点的单链表L中第i个位置前插入元素e
p = L; j = 0; //初始化p为头指针
while( p && j < i-1){ //寻找 i-1结点
p = p->next;
++j;
}
if(!p || j>i-1){
return ERROR;
}
s = (ElemType* ) malloc( sizeof( ElemType));
s -> data = e; s -> next = p -> next;
p -> next = s;
return OK;
}
算法 2.10——单链表删除结点
删除元素原理图
算法实现
Status ListDelete_L(LinkList& l, int i, ElemType& e){
//删除单链表L第i个元素并用e返回值
p = L; j = 0;
while(p ->next && j<i-1 ){ //寻找第i个结点，并令p指向其前驱
p = p->next;
++j;
}
if ( !( p->next) || j>i-1) //插入位置不合法
return ERROR;
q = p->next; p->next = q->next; //删除结点
e = q->data;
free(q); //释放被删除的结点
return OK;
}
二者的时间复杂的都是O(n)
malloc函数
假设p是LinkList类型变量，则执行p = (LinkList) malloc (sizeof ( LNode))语句的含义是，生成一个LNode型的结点，并将其起始位置赋给p。反之free( p)是回收一个LNode型结点，回收后的空间可以备作再次生成节点的空间。
算法 2.11——逆向建立单链表
- 逆向建立单链表：从表尾到表头，时间复杂度为O（n）
- 算法实现
void CreateList_L( LinkList& L, int n){
//逆序输入n个元素的值，建立带表头节点的单链表L
L = (LinkList )malloc( sizeof( LNode));
L -> next = NULL; //建立一个带有头结点的空表
for ( i=n; i>0; --i){
p = (LinkList) malloc (sizeof ( LNode));
scanf(& p->data);
p->next = L->next;
L->next = p; //逆序插入结点
}
}
算法 2.12——合成有序链表
- 合成：链表的归并排列。
- 算法实现
void MergeList_L(LinkList La, LinkList Lb, LinkList &Lc){
// 已知La和Lb为 内容元素非减的 单链表
pa = La->next; pb = Lb->next; //使pa和pb指向第一个元素
pc = Lc = La; //用La的头节点作为Lc的头节点
while (pa && pb){
if(pa->data <= pb->data){
pc->next = pa; //将pa插入到pc后
pc = pa; //平移pc指针，应该等价于pc = pc->next;
pa = pa->next; //平移pa指针
}
else{
pc->next = pb;
pc = pb;
pb = pb->next;
}
pc -> next = pa? pa:pb;
free(Lb); //不可释放La，因为此时La和Lc共用一个地址。
} //MergeLsit_L
有时可以借用一维数组来描述线性链表，结构如下
//------线性表的静态单链表存储结构------
#define MAXSIZE 100
typedef struct{
ElemType elem;
int cur;
} component, SLinkList[MAXSIZE];
此种类型在不设“指针”的情况下使用链表结构。
上述结构中，数组的一个分量代表一个节点，同时用游标cur代替指针指示结点在数组中的相对位置。数组的第零分量可以看成是头节点，其指针域指示链表的第一个结点。这种存储结构仍需预先分配出一个较大的空间，但在插入和删除元素时不需要修改移动元素，只需要修改指针，仍具有链式存储结构的主要优点。我们称这种存储方式为静态链表。
下图展示了 在SUN后插入GUO并删除ZHOU的操作。
假设S为SLinkList型变量，则S[0].cur指示第一个结点在数组中的位置。设 i = S[0].cur; 则S[i].cur表示第二个结点在数组中的位置。i = S[i].cur实为指针的后移(等价于 p = p -> next)
算法 2.13——静态链表定位函数
- 定位：查找第一个值为e的元素。若找到则返回位序，否则返回0
- 算法实现
int LocateElem_SL(SLinkList L, ElemType e){
i = S[0].cur;
while (i && S[i].data !=e){
i = S[i].cur; //遍历，之道数据域等于e
}
return i;
} // LocateElem_SL
类似的，静态链表可以实现插入和删除操作。所不同的是，malloc和free两个函数需要自己编写。为了分辨哪些分量未被使用，可以将所有未被使用过的以及被删除的分量用游标构成一个备用的链表，每当进行插入操作时从备用链表上取得第一个结点作为待插入的新结点；反之将删除下来的新结点插入到备用链表后。
算法 2.14——静态链表的初始化
- 算法实现
void InitSpace_SL(SLinkList &space){
// space[0].cur作为头指针
for ( i=0; i<MAXSIZE-1; ++i){
space[i].cur = i+1;
}
space[MAXSIZE-1].cur=0;
}
算法 2.15——静态链表分配空间
- 分配：在插入新结点，给新结点分配空间实际上就是为结点从备用链表中分配一个结点下标
- 算法实现
int Malloc_SL(SLinkList &space){
// 若备用链表非空则返回分配的结点下标，否则返回0
i = space[0].cur;
if(space[0].cur){ // 如果备用链表非空
space[0].cur = space[i].cur; // 连接备用链表头结点和第二个结点
}
return i;
} // Malloc_SL
算法 2.16——静态链表回收结点
- 将结点回收，即将该结点放回备用链表中
- 算法实现
void Free_SL(SLinkList &space, int k){
// 将下标为k的空闲结点回收到备用链表
space[k].cur = space[0].cur;
space[0].cur = k;
}
算法 2.17——集合运算（A/B）∪（B/A）
- 对称差：假设由终端输入集合元素，先建立表示集合A的静态链表S，而后在输入集合B的元素的同时查找S表，若存在和B相同的元素，则从S表中删除，否则插入S表
- 算法实现
void difference_SL(SLinkList &space, int &S){
// 依次输入A和B的元素，在一堆数组space中建立表示（A/B）∪（B/A）
// 的静态链表，S为其头指针。假设备用空间足够大，space[0].cur为其头指针。
InitSpace_SL(space);
S = Malloc_SL(space); // 生成S的头结点
r = S; // r指向S的末尾
scanf(m,n); // 输入A和B的元素个数
for(j = 1; j <= m; ++j){
i = Malloc_SL(space); // 分配结点
scanf(space[i].data);
space[r].cur = i; r = i; // 插入到表尾
} //for
space[r].cur = 0; //伪结点的指针为空
for(j = 1; j <= n; ++j){
scanf(b); p = S;
k = space[S].cur; // k指向A中的第一个结点
while(k != space[r].cur && space[k].data != b){
p = k; k = space[k].cur;
} //while
if( k == space[r].cur){ // 当前表中不存在该元素，插入在r所指结点之后，且r的位置不变
i = Malloc_SL(space);
space[i].data = b;
space[i].cur = space[r].cur;
space[r].cur = i;
} //if
else{
space[p].cur = space[k].cur;
Free_SL(space,k);
if (r == k) //若删除的是r所指结点，则需修改尾指针
r = p;
} //else
} //for
} //difference
