null第二章 线性表第二章 线性表 数据元素之间满足线性关系的表称为线性表，是一种最基本、最简单的数据结构类型。本章讨论线性表的逻辑和存储结构、相关算法的实现以及线性表应用举例。
2.1线性表的定义及基本操作
2.1.1 定义：线性表(Linear List)是若干数据元素的一个线性序列，记为：
L=(a0,∙∙∙∙ai-1aiai+1∙∙∙∙∙∙an-1)
其中：L为表名，ai(0≤i≤n-1)为数据元素；n为表长，n>0 时，L为非空表，否则为空表。
2.1.2 线性表的逻辑结构和特征
线性表L可用二元组形式描述： L= (D,R)
数据元素集合: D={ai | ai∈datatype ,i=0,1,2, ∙∙∙∙∙∙∙∙∙n-1 ,n≥0}
关系集合: R={
| ai , ai+1∈D, 0≤i≤n-2}
表长n=0时，L为空表；关系符在这里称为有序对，表示任意相邻的两个元素之间的一种先后次序关系，称ai是ai+1的直接前驱, ai+1是ai的直接后继，当表长n≤1时，关系集R为空集。例2-1 线性表的例子例2-1 线性表的例子 L1=(A,B,……,Z) 元素为字符； L2=(6,7, ……,105) 元素为整数；
学生记录表：
线性表的特征：对非空表,a0是表头,无前驱；an-1是表尾,无后继；其它的每个元素ai有且仅有一个直接前驱(ai-1)和一个直接后继(ai+1)。
2.1.3 线性表的抽象数据类型表示
设线性表 L=(a0,a1, ……,an-1)，对 L的抽象数据类型表示：a0
a1
..
..
a31线性表的抽象数据类型表示线性表的抽象数据类型表示ADT List{ 数据元素集：D={ai|ai∈datatype,i=0,1,2, ……n-1,n≥0}
数据关系集：R={|ai, ai+1∈D,0≤i≤n-2}
基本操作集：P
ListInit(&L)
操作结果：构造一个空的线性表L。
ListDestroy(&L)
初始条件：线性表L存在。操作结果：撤销线性表L。
ListClear(&L)
初始条件：线性表L存在。操作结果：将L置为一张空表。
ListLength(L)
初始条件：线性表L存在。操作结果：返回L中元素个数(即表长n)。
ListEmpty(L)
初始条件：线性表L存在。操作结果：L为空表时返回TRUE，否则返回FALSE。 线性表的抽象数据类型表示线性表的抽象数据类型表示GetElem(L,i)
初始条件：线性表L存在，且0≤i≤n1。操作结果：返回L中第i个元素的值(或指针)。
LocateElem(L,e)
初始条件：线性表L存在，且e∈datatype。
操作结果：若e在L中，返回e的序号(或指针)；否则返回e不在表中的信息（实际应用中如-1或NULL）。
即： i 当元素e=ai∈L,且ai是第一个与e相等时；
LocateElem(L,e)=
-1 e不属于L时。
PreElem(L, cur)
初始条件：线性表L存在，且cur∈datatype。操作结果：若cur在L中且不是表头，返回cur的直接前驱，否则返回NULL。
SuccElem(L,cur)
初始条件：线性表L存在，且cur∈datatype。操作结果：若cur在L中且不是表尾元素，返回cur的直接后继的值，否则返回NULL。线性表的抽象数据类型表示线性表的抽象数据类型表示 ListInsert(&L,i,e)
初始条件：线性表L存在，且e∈datatype。
操作结果：若0≤i≤n-1，将e插入到ai之前，若i=n，将e插到表尾，表长增加1，函数返回TURE；i为其他值时返回FALSE，L无变化。
即： 插入前：(a0,a1,---,ai-1,ai,ai+1-------,an-1)
插入后：(a0,a1,---,ai-1, e, ai,ai+1-------,an-1)
ListDel(&L,i)
初始条件：线性表L存在。
操作结果：若0≤i≤n-1，将第ai从表中删除，函数返回TURE， 否则函数返回FALSE，L无变化。
即： 删除前: (a0,a1,---,ai-1,ai,ai+1-------,an-1)
删除后: (a0,a1,---,ai-1，ai+1-------,an)
ListTraverse(L)
初始条件：线性表L存在。 操作结果：依次对表中的元素利用visit()函数进行访问。
}ADT List； 线性表的操作线性表的操作 以上运算是对线性表L施加的一些基本运算，对线性表L的运算还有：
合并、拆分、复制、排序等等。
例2-2 设线性表La=(a0a1, ……,am-1), Lb= (b0b1, ……,bn-1)，求La∪Lb =>La，如图2.1所示。
算法思路：依次取Lb中的bi(i=0,1,…,n-1)，若bi不在La中，则将其插入。
算法描述： void Union(list *La, list *Lb)
{int i,k; datatype x;
for(i=0; i
说明
关于失联党员情况说明岗位说明总经理岗位说明书会计岗位说明书行政主管岗位说明书
符
如果说明 sqlink L; L=(sqlink)malloc(sizeof(sqlist)); 则指针L指向一个线性表：
ai表示为L->data[i] (0≤i≤L->last)
图2.3
2.2.2基本运算的相关算法2.2.2基本运算的相关算法 关于线性表的运算，有些实现起来是相当简单的，例如：
置空表：ListClear(L),令L->last=-1；取ai:GetElem(L,i), 取L->data[i]；
求表长：ListLength(L), 取L->last之值加1即可。
所以主要讨论插入、删除、定位等算法的实现。
1.前插： 将一给定值e插在元素ai之前，即实现ListInsert(L,i,e)。
算法思路：若表存在空闲空间,且0≤i≤L->last+1,将(L->data[L->last]～L->data[i])顺序下移一个数据单位，然后将e插入L->data[i]处。
算法描述：
int ListInsert(sqlink L,int i,datatype e )
{ if(L->last>=maxsize-1){ ERROR(L); return(0); }
else if(i<0||i>L->last+1) {ERROR(i); return(0);}
else{ for(int j=L->last;j>=i;j--)
L->data[j+1]=L->data[j];
L->data[i]=e; L->last++;
return(1);}}基本运算的相关算法基本运算的相关算法算法分析：算法的主要时耗在数据元素的移动上，即算法中for 语句上，故以插入一个元素的平均移动次数刻画算法的T(n)(n为表长)。设e插入ai (0≤i≤n)处的概率pi均等，即pi=1/(n+1),而插入e时的元素移动次数Ci=n-i,则平均移动次数为：
T(n)= pi Ci = n/2=O(n)。基本运算的相关算法基本运算的相关算法2.删除：将表中第i个元素ai从表中删除，即实现ListDel(L,i)。
算法思路： 若参数i满足：0≤i≤L->last, 将表中L->data[i+1]∽L->data[L->last] 部分顺序向上移动一个元素位置，挤掉L->data[i]。
算法描述：
int ListDel(sqlink L,int i)
{ if (i<0||i>L->last) {ERROR(L);return(0);}
else{ for(int j=i+1;j<=L->last;j++)
L->data[j-1]=L->data[j];
L->last--;
return(1);}
}
算法分析：设删除ai (0≤i≤n-1)的概率pi均等,即pi=1/n,删除ai的元素移动次数Ci=n-(i+1), 则平均移动次数为：
T(n)= pi Ci = (n-1)/2=O(n)。基本运算的相关算法基本运算的相关算法3.定位：确定给定元素e在表L中第一次出现的位置（或序号）。即实现LocateElem(L,e)。算法对应的存储结构如图所示。
算法思路：设一扫描变量i(初值=0)，判断当前表中元素ai是否等于e，若相等，则返回当前i值（表明e落在表的第i位置）；否则i加1，继续往下比较。若表中无一个元素与e相等，则返回-1 。
算法描述：
int LocateElem(sqlink L,datatype e)
{ int i=0;
while(i<=L->last&&L->data[i]!=e)
i++;
if(i<=L->last) return(i);
else return(-1);}
算法分析：算法时耗主要在while语句中元素e与ai的比较次数上，用平均比较次数来刻画算法的T(n)。设元素ai (0≤i≤n-1)与e相等的概率pi均等，即pi=1/n,查找ai与e相等的比较次数Ci=i+1,则平均的比较次数为：
T(n)= pi Ci = (n+1)/2=O(n)。 2.3 线性表的链式存储结构 2.3 线性表的链式存储结构 线性表的顺序存储结构有存储密度高及能够随机存取等优点，但存在以下几点不足：(1)插入、删除等运算耗时，且存在元素在存储器中成片移动的现象；(2)要求系统提供一片较大的连续存储空间。
下面讨论线性表的链式存储结构，即链表。是第二章的重点。
2.3.1单链表
将线性表L=(a0,a1,……,an-1)中各元素分布在存储器的不同存储块，称为节点，通过地址或指针建立它们之间的联系，所得到的存储结构为链表结构。表中元素ai的节点形式如图2.4所示。
图2.4
其中，data域存放数据元素ai，而next域是一个指针，指向ai的直接后继ai+1所在的节点。于是，线性表L=( a0,a1,……,an-1)的结构如图2.5所示:
单链表单链表例2-4 设线性表L=(赵，钱，孙，李，周，吴，郑，王)，各元素在存储器中的分布如图2.6所示。
图2.6
带头节点的单链表：单链表单链表 节点描述：typedef struct node //节点类型
{ datatype data; //节点的数据域
struct node *next; //节点的后继指针域
}linknode, *link;
若说明linknode A; link p; 则结构变量A为所描述的节点，而指针变量p为指向此类型节点的指针（或p的值为节点的地址），如图2.8所示:
设p指向链表中节点ai，如图2.9所示:
获取ai，写作：p->data；而取ai+1,写作：p->next->data。 另外，若指针p的值为NULL，则它不指向任何节点, 此时取p->data或p->next是错误的。2.3.2单链表的基本操作2.3.2单链表的基本操作 可调用C中malloc()函数向编译系统申请节点的存储空间，若说明：
link p; p=(link)malloc(sizeof(linknode));
则获得了一个类型为linknode的节点，且该节点的地址已存入指针变量P中：
1．建立单链表
算法思路：依次读入L=(a0,.....,an-1)中每一ai(设为整型)，若ai≠结束符(-1)，则将ai形成一节点，链入表尾，最后返回链表的头节点指针H。
算法描述：link Createlist()
{ datatype a; link H ,p,r;
H=r=(link)malloc(sizeof(linknode));
scanf(“%d”,&a); //输入数据元素
while(a!=-1)
{ p=(link)malloc(sizeof(linknode)); //申请新节点
p->data=a; r->next=p; r=p; //存入数据,将新节点链入表尾
scanf(“%d”,&a);}
r->next=NULL;return(H);} //表尾的后继置空 建立单链表 建立单链表设L=(2，4，8，-1)，则建表过程如下：
设表长为n，显然此算法的时间复杂度为T(n)=O(n)。从此算法可以看到，链表的结构是动态形成的，即算法运行前，表结构是不存在的，而通过算法的运行，得到一个如图所示的单链表。
2．链表查找 （1）按序号查找：即实现GetElem(L,i)。
算法思路：从链表的a0起，判断是否为第i节点，若是则返回该节点的指针，否则查找下一节点,依次类推。
算法描述：Link GetElem(link H, int i)
{ int j=-1; link p=H; if(i<0) return(NULL);
while(p->next&&jnext;j++;}
if(i==j) return(p); else return(NULL);}//查找失败,即i>表长
}单链表运算单链表运算（2）按值查找（定位） ： 即实现LocateElem(L,e)。
算法思路：从节点a0起，依次判断某节点是否等于e,若是,返回该节点的地址，否则查找下一节点a1,依次类推。若表中不存在e,则返回NULL。
算法描述：link LocateElem(link H,datatype e)
{ link p=H->next;
while(p&&p->data!=e) p=p->next;
return(p); //若p->data=x则返回指针p;否则p必为空，返回NULL
}
此算法的时间复杂度T(n)也为O(n)。
3．前插
即实现ListInsert(L, i, e)。讨论将x插入表中节点ai之前的情况。
算法思路：调用算法GetElem(H,i-1)，获取节点ai-1的指针p(ai 之前驱)，然后申请一个q节点，存入e，并将其插入p节点之后。插入时的指针变化如图2.14所示。 单链表插入单链表插入
图2.14
算法描述：void ListLinsert(link H, int i,datatype e)
{ link p, q;
if(i==0) p=H;else p=GetElem(H,i-1); //取节点ai-1的指针
if(p==NULL) ERROR(i); //参数i出错
else { q=(link)malloc(sizeof(linknode))； //申请插入节点
q->data=e; //存入数据
q->next=p->next; //插入新节点
p->next=q;}}
此算法的时间主要花费在函数Getlist(H,i-1)上，故T(n)=O(n)，但插入时未引起元素的移动，这一点优于顺序结构的插入。单链表删除单链表删除4．删除
即实现ListDel(L,i)。
图2.15
算法思路：同插入法，先调用函数GetElem(H,i-1),找到节点ai的前驱，然后如图2.15所示，将节点ai删除之。
算法描述：Void Ldelete(link H,int i)
{ link p,q;
if(i==0) p=H;else p=GetElem(H,i-1); //求ai-1的地址
if(p&&p->next) //若p及p->next所在的节点存在
{ q=p->next; p->next=q->next; free(q);} //删除
else ERROR(i) ; //参数i出错
}
同插入法，此算法的T(n)=O(n)。q例2-5 将单链表倒置例2-5 将单链表倒置算法思路：依次取原链表中节点，将其作为新链表首节点插入H节点之后。
图.16
算法描述：void L1n-Ln1(link H)
{ link p,q; p=H->next; //令指针p指向节点a0
H->next=NULL; //将原链表置空
while(p) { q=p; p=p->next;
q->next=H->next; //将节点ai插入到头节点之后
H->next=q;} }例2-6例2-6 设节点data域为整型，求链表中相邻两节点data值之和为最大的第一节点的指针。如图2.17所示的链表，它应返回值为4的节点所在的指针。
算法思路：设p,q 分别为链表中相邻两节点指针，求p->data+q->data为最大的那一组值，返回其相应的指针p即可。(本例应返回“4”的地址)
算法描述：link Adjmax(link H)
{ link p,p1,q; int m0,m1; p=H->next;
p1=p; if(p1==NULL) return(p1); //表空返回
q=p->next; if(q==NULL) return(p1); //表长=1时的返回
m0=p->data+q->data; //相邻两节点data值之和
while(q->next)
{ p=q; q=q->next; //取下一对相邻节点的指针
m1=p->data+q->data;
if(m1>m0){ p1=p; m0=m1;} }//取和为最大的第一节点指针
return(p1); }《数据结构》上机题1《数据结构》上机题1《数据结构》上机题（C语言程序）
1．输入数据（设为整型）建立单链表，并求相邻两节点data值之和为最大的第一节点。
例如输入：2 6 4 7 3 0（0为结束符），建立：
所求结果=4
程序结构： 类型说明；
建表函数：Creatlist(L); 求值函数：Adjmax(L);
main()
{ 变量说明；
调用Creatlist(L)建表；调用Adjmax(L)求值；
打印数据；释放链表空间；
Y 继续？
N
停止
}
例2-7例2-7 设两单链表A、B按data值（设为整型）递增有序，设计算法，将表A和B合并成一表A，且表A也按data值递增有序。如图2.18：
算法思路：设指针p、q分别指向表A和B中的节点，若p->data≤q->data则p节点进入结果表，否则q节点进入结果表。
算法描述：void Merge(link A, link B)
{ link r,p,q; p=A->next; q=B->next; free(B);r=A;
while(p&&q)
{ if(p->data<=q->data){ r->next=p;r=p; p=p->next;}
else { r->next=q;r=q; q=q->next;} }
if(p==NULL) p=q; r->next=p; } //收尾处理 2.3.3单向循环链表2.3.3单向循环链表 单向循环链表是单链表的一种改进，若将单链表的首尾节点相连，便构成单向循环链表结构，如图2.20所示:
若操作频繁在尾部进行，可设表尾指针R(省去H) 。这样,为获得表尾an-1，取R->data即可，不必遍历到表尾，而取a0：(R->next->next)->data;
例2-8 设ra和rb分别为两循环链表的尾指针，设计算法实现表ra和rb的连接。
P=B->next; B->next=A->next; A->next=P->next; free(P); R2.3.4 双向循环链表2.3.4 双向循环链表 在单链表L中，查找ai的后继 Next(L,ai)，耗时仅为O(1)，因为取ai之后继指针即可。但查找ai的直接前驱Prior(L,ai)，则需从链表的头指针开始，找到节点ai前一节点即是。故Prior(L,ai)依赖表长n，耗时为O(n)。另外，若链表中有一指针值被破坏，则整个链表脱节。这是单链表的不足，为此，引入双向链表。先定义双向链表中的节点：
其中，data和next同单链表，增加一指针prior，其指向本节点的直接前驱。
节点描述：typedef struct dnode
{ datatype data; struct dnode *prior,*next;
}dlinknode,*dlink;
表L = (a0,.....,an-1) (设n=2) 的双向循环链表如图2.24所示:
双向循环链表（插入）双向循环链表（插入） 设p为链表中某节点的指针，有对称性：
(p->prior)->next==p==(p->next)->prior
双向链表的查找基本上同单链表。下面讨论双向循环链表的插入和删除。
1.插入：即实现在表L的第i节点前插入一节点x的运算，如图2.25所示:
算法思路：调用查找Getlist(L,i)，获取节点ai的指针p 。若p存在，申请一q节点，存入元素x，然后修改指针，将q节点插入p节点之前。
算法描述：void Dinsert(dlink L,int i,datatype x)
{ dlink p,q; p=Getlist(L,i);
if(p==NULL) ERROR(i);
else{ q=(dlink)malloc(sizeof(dlinknode)); q->data=x;
q->prior=p->prior; q->next=p; (p->prior)->next=q; p->prior=q;}}
此算法的时耗主要在查找运算Getlist(L,i)上，故T(n)=O(n)。双向循环链表（删除）双向循环链表（删除）2. 删除：即实现删除链表中第i节点的运算，如图2.26所示。
算法思路：调用Getlist(L,i)，获取ai的指针p，若p存在，则修改指针删除之。
图2.26
算法描述：Void Ddelete(dlink L,int i)
{ dlink p=Getlist(L,i);
if(p==NULL) ERROR(i);
else{ (p->prior)->next=p->next;
(p->next)->prior=p->prior;
free(p); }}
同插入运算，该算法的T(n)=O(n)。
2.3.5 静态链表（略） 2.4 线性表应用举例2.4 线性表应用举例 讨论两个例子：Josephu（约瑟夫）问题和一元多项式的表示及相加。
2.4.1. Josephu问题：设编号为：1，2，…，n的n个人围坐一圈。约定编号为k(1≤k≤n)的人从1开始计数，数到m的那个人出列，他的下一位又从1开始计数，数到m的那个人又出列，依次类推，直到所有人出列为止。
例2-9 设n=8，k=3，m=4时，如图2.28所示:
出列序列为：(6，2，7，4，3，5，1，8)。
算法思路：用一个不带头节点的循环链表来处理Josephu问题：先构成一个有n个节点的单循环链表，然后从第k节点起从1计数，计到m时，对应节点从链表中删除；然后再从被删除节点的下一个节点起又从1开始计数……，直到所有节点都出列时算法结束。应用举例(Josephu)应用举例(Josephu)算法描述(简化)：
void Josephu(link L,int n, int k, int m)
{ int i; link p,r ;L=NULL; //置空表
for(i=1;i<=n;i++) //建立循环链表
{ p=(link)malloc(sizeof(linknode));
p->data=i;
if(L==NULL) L=p;
else r->next=p; r=p;}
p->next=L; //环起来 p=L;
for(i=1;i<=k-1;i++)
{ r=p; p=p->next; } //找到第k个节点
while(p->next!=p) //节点数>1时
{ for(i=1;i<=m-1;i++) { r=p; p=p->next; } //报数
r->next=p->next; //删除当前出列的p节点
printf (“%d”,p->data); //打印序号
free(p); p=r->next;} //取下一报数的起点指针
printf (“%d\n”,p->data); free(p);} //打印最后一个节点的序号图2.29多项式表示与相加多项式表示与相加 算法的第一个for循环的时间复杂度为O(n)；第二个for循环的时间复杂度为O(k)，显然O(k)≤O(n)；而while循环执行次数为n，每执行一次while循环，里面的for 循环执行的时间为O(m)。故此时算法的时间复杂度为：
T(n,m)=O(n)+O(k)+O(n*m)=O(n*m)
2.4.2 一元多项式的表示与相加
设一元n次多项式： pn(x)=p0+p1x1+…+pixi+…+pnxn
其中n+1个系数可形成一个线性表：p(p0, p1,…, pn)，而x的指数i(0≤i≤n)对应pi的序号。无疑Pn(x)中有许多系数为0的项，如：
p2000(x)=1+3X1000+2X2000
对应的线性表就是P(1,0，……，0,3, ……,2).显然这些0元素对存储空间是一种浪费，且处理起来费时，所以去掉Pn(x)中系数为0的项，写作：
Pn(x)=P1xe1+P2xe2+..........+Pmxem
其中: Pi(1≤i≤m)≠0,且0≤e1expexp ，则pa节点应为和的一项；
若pa->exp>pb->exp ，则pb节点应为和的一项；
若pa->exp=pb->exp ，则两节点对应系数相加：
sum=pa->coef+pb->coef
若sum≠0，相加结果应为和的一项。
如图2.31中两多项式的链表相加的结果如图2.32所示: 多项式表示与相加多项式表示与相加算法描述：void Addpoly(link pa,link pb)
{ link pc,pre,u ; float sum;
pc=pa; pre=pa; pa=pa->next; u=pb; pb=pb->next; free(u);
while(pa&&pb)
{ if(pa->expexp) { pre=pa; pa=pa->next;} // pa为和的一项
else if(pa->exp>pb->exp) // pb为和的一项
{u=pb->next;pb->next=pa; pre->next=pb; pre=pb;pb=u;}
else { sum=pa->coef+pb->coef; //指数相同，系数相加
if(sum!=0.0) { pa->coef=sum; pre=pa;} //修改系数
else {pre->next=pa->next;free(pa);} //删除pa节点
pa=pre->next;
u=pb; pb=pb->next; //删除对应的pb节点
free(u);} }
if(pb) pre->next=pb;} //将pb的剩余项链入结果表
设两链表的表长分别为m和n，则此算法的时间复杂度为T(m,n)=O(m+n)。 第二章小结第二章小结 线性表第二章习题第二章习题1.设线性表La=(a0a1, ……,am-1), Lb= (b0b1, ……,bn-1)，利用线性表基本运算，求La – Lb =>La 、 La ∩ Lb =>Lc 运算的算法实现。
2.设学生记录表S ：
（按学号Sno有序）
(1)设计表S 的顺序存储结构;
(2)写出将一学生记录x 插入到表中正确位置的算法:insert-s(S,x);
(3)写出从表中删除Sno=y 的记录: delete-s(S,y)。LaLbLbLa红：La – Lb 蓝：La ∩ Lb 第二章习题第二章习题3. 设循环链表：
试写出从表R中某p节点开始, 查找data=d的节点指针的算法： search(R,p,d). (算法前应包括对节点的说明)
4. 设链表A、B 如下：
写出判断A 表和B 表是否相等的算法：equal(A,B).
（两表相等的充分必要条件：表长相等，且两表中元素也对应相等。）
浙公网安备 33021202002483