CH2数据结构课件

第二章线性表线性结构特点：在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外，集合中的每个数据元素均只有一个前驱除最后一个外，集合中的每个数据元素均只有一个后继第二章线性表线性结构特点：在数据元素的非空有限集中12.1线性表的逻辑结构定义：一个线性表是n个数据元素的有限序列例英文字母表（A,B,C,…..Z)是一个线性表例数据元素2.1线性表的逻辑结构例英文字母表（A,B,C,….2例一副扑克的点数（2，3，4，…，J，Q，K，A）从以上例子可看出线性表的逻辑特征是：在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1；其余的内部结点ai(2≦i≦n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。

线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。例一副扑克的点数3特征：元素个数n—表长度，n=0空表1<i<n时ai的直接前驱是ai-1，a1无直接前驱ai的直接后继是ai+1，an无直接后继元素同构，且不能出现缺项特征：4抽象数据类型线性表的定义：ADTList{数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n>=0}数据关系：Rl={〈ai-1，ai〉|ai-1，ai∈D，i=1,2,…,n}基本操作：InitList(&L)DestroyList(&L)ClearList(&L)ListEmpty(L)ListLength(L)GetElem(L,I,&e)LocateElem(L,e,compare())PriorElem(L,cur_e,&pre_e)NextElem(L,cur_e,&next_e)ListInsert(&L,i,e)ListDelete(&L,i,&e)ListTraverse(L,visit())}ADTList抽象数据类型线性表的定义：5算法2.1利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=A∪B。voidunion(List&La，ListLb){La-len=listlength(La);Lb-len=listlength(Lb);for(I=1;I<=lb-len;I++){getelem(lb，I，e);if(!locateelem(la，e，equal))listinsert(la，++la-en，e)}}

算法的时间复杂度：O（ListLength(LA)×ListLength(LB)）

算法2.1利用两个线性表LA和LB分别表示两个集合A和B，6算法2.2巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。算法2.2巳知线性表LA和线性表LB中的数据元素按值非递减有7voidmergelist(listla，listlb，list&lc){initlist(lc);I=j=1;k=0;la-len=listlength(la);lb-len=listlength(lb);while((I<=la-len)&&(j<=lb-len)){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){getelem((la，I++，ai);listinsert(lc，++k，ai);}while(j<=lb-len){getelem((lb，j++，bj);listinsert(lc，++k，bj);}}算法的时间复杂度：O（ListLength(LA)+ListLength(LB)）

voidmergelist(listla，listl82.2线性表的顺序存储结构顺序表：定义：用一组地址连续的存储单元存放一个线性表叫~元素地址计算方法：LOC(ai)=LOC(a1)+(i-1)*LLOC(ai+1)=LOC(ai)+L其中：L—一个元素占用的存储单元个数LOC(ai)—线性表第i个元素的地址特点：实现逻辑上相邻—物理地址相邻实现随机存取实现：可用C语言的一维数组实现2.2线性表的顺序存储结构9a1a2an01n-112n内存V数组下标元素序号M-1typedefintDATATYPE;#defineM1000DATATYPEdata[M];例typedefstructcard{intnum;charname[20];charauthor[10];charpublisher[30];floatprice;}DATATYPE;DATATYPElibrary[M];备用空间数据元素不是简单类型时,可定义结构体数组或动态申请和释放内存DATATYPE*pData=(DATATYPE*)malloc(M*sizeof(DATATYPE));free(pData);a1a2an01n-112n内存V数组下标元素序号M-1ty10由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。又因为除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，所以我们用结构类型来定义顺序表类型。#defineListSize100typedefintDataType;typedefstruct{DataTypedata[ListSize];intlength;}Sqlist;由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型11插入定义：线性表的插入是指在第i（1in+1）个元素之前插入一个新的数据元素x，使长度为n的线性表变为n+1

变成长度为n+1的线性表

需将第i至第n共（n-i+1)个元素后移算法插入变成长度为n+1的线性表需将第i至第n共（n-i12VoidInsertList(Sqlist*L，DataTypex，intI){

intj;if(I<1||I>l.length+1){

printf(“Positionerror”);

returnERROR;}

if(l.length>=ListSize){

printf(“overflow”);

exit(overflow);}

for(j=l.length-1;j>=I-1;j--)

l.data[j+1]=l.data[j];l.data[I-1]=x;l.length++;}VoidInsertList(Sqlist*L，DataT13内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1an-1x内存a1a2aiai+1an01i-1V数组下标n-1in114分析算法的复杂度

这里的问题规模是表的长度，设它的值为。该算法的时间主要化费在循环的结点后移语句上，该语句的执行次数（即移动结点的次数）是。由此可看出，所需移动结点的次数不仅依赖于表的长度，而且还与插入位置有关。当i=n+1时，由于循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，其时间复杂度O（1）；当i=1时，结点后移语句将循环执行n次，需移动表中所有结点，这是最坏情况，其时间复杂度为O（n）。分析算法的复杂度15算法时间复杂度T(n)设Pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为：

也就是说，在顺序表上做插入运算，平均要移动表上一半结点。当表长n较大时，算法的效率相当低。虽然Eis(n)中n的的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为O(n)。动态算法时间复杂度T(n)也就是说，在顺序表上做插入运算，平均16删除定义：线性表的删除是指将第i（1in）个元素删除，使长度为n的线性表

变成长度为n-1的线性表

需将第i+1至第n共（n-i)个元素前移算法删除变成长度为n-1的线性表需将第i+1至第n共（n17

VoiddeleteList(Sqlist*L，inti){intj;if(i<1||i>l.length){printf(“Positionerror”);returnERROR}for(j=i;j<=l.length-1;j++)l.data[j-1]=l.data[j];l.length--;}VoiddeleteList(Sqlist*L，int18内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2ai+1V数组下标01i-1n-2in-112i元素序号i+1n-1nanai+2内存a1a2aiai+1an01i-1V数组下标n-1in119算法评价设Qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素所需移动的元素次数的平均次数为：故在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低。算法评价故在顺序表中插入或删除一个元素时，平均移动表的一半元20顺序存储结构的优缺点优点逻辑相邻，物理相邻可随机存取任一元素存储空间使用紧凑缺点插入、删除操作需要移动大量的元素预先分配空间需按最大空间分配，利用不充分表容量难以扩充顺序存储结构的优缺点212.3线性表的链式存储结构特点：用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息结点

数据域：元素本身信息指针域：指示直接后继的存储位置数据域指针域结点2.3线性表的链式存储结构数据域指针域结点22ZHAOQIANSUNLIZHOUWUZHENGWANG^H例线性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925数据域指针域LIQIANSUNWANGWUZHAOZHENGZHOU存储地址1713192531374331H头指针ZHAOQIANSUNLIZHOUWUZHENGWANG^H23实现Typedefchardatatype;typedefstructnode{

datatype

data;structnode*link;}listnode;listnode*h,*p;datalinkp结点（*p）(*p)表示p所指向的结点(*p).datap->data表示p指向结点的数据域(*p).linkp->link表示p指向结点的指针域线性链表定义：结点中只含一个指针域的链表叫~，也叫单链表实现Typedefchardatatype;lis24typedeflistnode*linklist;listnode*p;linklisthead;注意区分指针变量和结点变量这两个不同的概念。P为动态变量，它是通过标准函数生成的，即p=(listnode*)malloc(sizeof(listnode));函数malloc分配了一个类型为listnode的结点变量的空间，并将其首地址放入指针变量p中。一旦p所指的结点变量不再需要了，又可通过标准函数free(p)释放所指的结点变量空间。指针变量P（其值为结点地址）和结点变量*P之间的关系。typedeflistnode*linkl25一、建立单链表假设线性表中结点的数据类型是字符，我们逐个输入这些字符型的结点，并以换行符‘\n’为输入结束标记。动态地建立单链表的常用方法有如下两种：

1、头插法建表该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。a2…...h头结点an-10an^一、建立单链表a2…...h头结点an-10an26linklistcreatelistf(void){

charch;

linklisthead;

listnode*p;

head=null;

ch=getchar();

while(ch!=‵\n′){

p=(listnode*)malloc(sizeof(listnode));

p–>data=ch;

p–>next=head;

head=p;

ch=getchar();}

return(head);

}linklistcreatelistf(void)272、尾插法建表头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。2、尾插法建表28linklistcreater(){charch;linklisthead;listnode*p，*r;//(，*head;)head=NULL;r=NULL;while((ch=getchar()!=‵\n′){p=(listnode*)malloc(sizeof(listnode));p–>data=ch;if(head==NULL)head=p;elser–>next=p;r=p;}if(r!=NULL)r–>next=NULL;return(head);}linklistcreater(){29说明：第一个生成的结点是开始结点，将开始结点插入到空表中，是在当前链表的第一个位置上插入，该位置上的插入操作和链表中其它位置上的插入操作处理是不一样的，原因是开始结点的位置是存放在头指针（指针变量）中，而其余结点的位置是在其前趋结点的指针域中。算法中的第一个if语句就是用来对第一个位置上的插入操作做特殊处理。算法中的第二个if语句的作用是为了分别处理空表和非空表两种不同的情况，若读入的第一个字符就是结束标志符，则链表head是空表，尾指针r亦为空，结点*r不存在；否则链表head非空，最后一个尾结点*r是终端结点，应将其指针域置空。说明：第一个生成的结点是开始结点，将开始结点插入到空表中，是30如果我们在链表的开始结点之前附加一个结点，并称它为头结点，那么会带来以下两个优点：

a、由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上的操作一致，无需进行特殊处理；

b、无论链表是否为空，其头指针是指向头结点在的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。如果我们在链表的开始结点之前附加一个结点，并称它为头结点，那31ha1a2头结点an^…...h空表^头结点：在单链表第一个结点前附设一个结点叫～头结点指针域为空表示线性表为空ha1a2头结点an^…...h空表^头结点：在32linklistcreatelistr1(){charch;linklisthead=(linklist)malloc(sizeof(listnode));listnode*p，*r；r=head;

while((ch=getchar())!=‵\n′{p=(listnode*)malloc(sizeof(listnode));p–>data=ch;r–>next=p;r=p;}r–>next=NULL;return(head);}linklistcreatelistr1(){33上述算法里动态申请新结点空间时未加错误处理，可作下列处理：p=(listnode*)malloc(sizeof(listnode))if(p==NULL)error(〝Nospacefornodecanbeobtained〞);returnERROR;以上算法的时间复杂度均为O(n)上述算法里动态申请新结点空间时未加错误处理，可作下列处理：34二、查找运算1、按序号查找在链表中，即使知道被访问结点的序号i，也不能象顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。设单链表的长度为n，要查找表中第i个结点，仅当1≦i≦n时，i的值是合法的。但有时需要找头结点的位置，故我们将头结点看做是第0个结点，其算法如下：二、查找运算35Listnode*getnode(linklisthead，inti){intj;listnode*p;p=head;j=0;while(p–>next&&j<I){p=p–>next;j++;}if(i==j)returnp;elsereturnNULL;}Listnode*getnode(linklisthe362、按值查找按值查找是在链表中，查找是否有结点值等于给定值key的结点，若有的话，则返回首次找到的其值为key的结点的存储位置；否则返回NULL。查找过程从开始结点出发，顺着链表逐个将结点的值和给定值key作比较。其算法如下：Listnode*locatenode(linklisthead，intkey){listnode*p=head–>next;while(p&&p–>data!=key)p=p–>next;returnp;}该算法的执行时间亦与输入实例中的的取值key有关，其平均时间复杂度的分析类似于按序号查找，也为O(n)。2、按值查找37pabxs三、插入运算插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，我们必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点*p，并令结点*p的指针域指向新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化，插入过程如：s->next=p->next;p->next=s;pabxs三、插入运算s->next=p->next;p->38具体算法如下：voidinsertnode(linklisthead，datetypex，inti){listnode*p，*q;p=getnode(head，i-1);if(p==NULL)error(〝positionerror〞);q=(listnode*)malloc(sizeof(listnode));q–>data=x;q–>next=p–next;p–>next=q;}

设链表的长度为n，合法的插入位置是1≦i≦n+1。注意当i=1时，getnode找到的是头结点，当i=n+1时，getnode找到的是结点an。因此，用i-1做实参调用getnode时可完成插入位置的合法性检查。算法的时间主要耗费在查找操作getnode上，故时间复杂度亦为O(n)。具体算法如下：设链表的长度为n，合法的插入位置是1≦i≦n39pabc四、删除运算删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以我们必须首先找到ai-1的存储位置p。然后令p–>next指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间，将其归还给“存储池”。此过程为：p->link=p->link->link;pabc四、删除运算p->link=p->link->lin40具体算法如下：voiddeletelist(linklisthead，inti){listnode*p，*r;p=getnode(head，i-1);if(p==NULL||

p–>next==NULL)returnERROR;r=p–>next;p–>next=r–>next;free(r);}设单链表的长度为n，则删去第i个结点仅当1≦i≦n时是合法的。注意，当i=n+1时，虽然被删结点不存在，但其前趋结点却存在，它是终端结点。因此被删结点的直接前趋*p存在并不意味着被删结点就一定存在，仅当*p存在（即p!=NULL）且*p不是终端结点（即p–>next!=NULL）时，才能确定被删结点存在。显然此算法的时间复杂度也是O(n)。具体算法如下：设单链表的长度为n，则删去第i个结点仅当1≦41单链表特点它是一种动态结构，整个存储空间为多个链表共用不需预先分配空间指针占用额外存储空间不能随机存取，查找速度慢静态单链表

单链表特点静态单链表42循环链表(circularlinkedlist)循环链表是表中最后一个结点的指针指向头结点，使链表构成环状特点：从表中任一结点出发均可找到表中其他结点，提高查找效率操作与单链表基本一致,循环条件不同单链表p或p->link=NULL循环链表p或p->link=Hhh空表循环链表(circularlinkedlist)hh空表43双向链表（doublelinkedlist）在循环链表中，访问结点的特点：访问后继结点，只需要向后走一步，而访问前驱结点，就需要转一圈。

结论：循环链表并不适用于经常访问前驱结点的情况。

解决方法：在需要频繁地同时访问前驱和后继结点的时候，使用双向链表。

双向链表：就是每个结点有两个指针域。一个指向后继结点，另一个指向前驱结点。双向链表（doublelinkedlist）44结点定义typedefstructnode{datatypeelement;structnode*prior,*next;}JD;priorelementnextL空双向循环链表：非空双向循环链表：LABbcapp->prior->next=p=p->next->proir;结点定义typedefstructnodepriorel45bcaPvoiddel_dulist(JD*p){p->prior->next=p->next;

p->next->prior=p->prior;free(p);}删除算法描述算法评价：T(n)=O(1)p->prior->next=p->next;p->next->prior=p->prior;bcaPvoiddel_dulist(JD*p)删除算法46voidins_dulist(JD*p,intx){JD*s;s=(JD*)malloc(sizeof(JD));s->element=x;

s->prior=p->prior;

p->prior->next=s;s->next=p;

p->prior=s;}算法描述算法评价：T(n)=O(1)xSbaP插入voidins_dulist(JD*p,intx)算法472.4线性表的应用举例——一元多项式的表示及相加一元多项式的表示：可用线性表P表示但对S(x)这样的多项式浪费空间一般其中用数据域含两个数据项的线性表表示其存储结构可以用顺序存储结构，也可以用单链表2.4线性表的应用举例可用线性表P表示但对S(x)这样的48单链表的结点定义coefexpnext-1A703198517^-1B81227-98^-1C70111227517^一元多项式相加typedefstructnode{intcoef,exp;structnode*next;}JD;单链表的结点定义coefexpnext-1A7049设p,q分别指向A,B中某一结点，p,q初值是第一结点比较p->exp与q->expp->exp<q->exp:p结点是结果多项式中的一项，p后移,q不动p->exp>q->exp:q结点是结果多项式中的一项，将q插在p之前,q后移,p不动p->exp=q->exp:系数相加0：从A表中删去p,释放p,q，p,q后移0：修改p系数域,释放q，p,q后移直到p或q为NULL若q==NULL，结束若p==NULL，将B中剩余部分连到A上即可运算规则设p,q分别指向A,B中某一结点，p,q初值是第一结点比较p50q-1pa703198517^-1pb81227-98^ppreq-1pa7011198517^-1pb81227-98^ppre-1pa70111227517^算法描述q-1pa703151voidadd_poly(JD*pa,JD*pb){JD*p,*q,*u,*pre;intx;p=pa->next;q=pb->next;pre=pa;while((p!=NULL)&&((q!=NULL)){if(p->exp<q->exp){pre=p;p=p->next;}elseif(p->exp==q->exp){x=p->coef+q->coef;if(x!=0){p->coef=x;pre=p;}else{pre->next=p->next;free(p);}

p=pre->next;u=q;q=q->next;free(u);}else{u=q->next;q->next=p;pre->next=q;pre=q;q=u;}}if(q!=NULL)pre->next=q;free(pb);}voidadd_poly(JD*pa,JD*pb)52线性表的应用举例

——约瑟夫（Joseph）问题

编号为1，2，···，n的n个人按顺时针方向围坐在一张圆桌旁，每个人手中持有一个密码（正整数）。首先输入一个正整数作为报数上限值m，然后，从第一个人开始按顺时针方向自1开始顺序报数，报到m的人离开桌旁，并将他手中的密码作为新的m值，从顺时针方向的下一个就坐在桌旁的人人开始重新从1报数，如此下去，直至所有人全部离开桌旁为止。线性表的应用举例

——约瑟夫（Joseph）问题53——假设有7个人，编号从1到7，他们手中的密码分别是3，1，7，2，4，8，4，最初的m=2，通过报数，这7个人离开桌旁的顺序应该是：2，3，5，4，7，6，1。数据结构的分析：这个问题的主角是n个人，每个人需要描述的信息有：编号、密码和是否在桌旁的状态。假设有7个人，他们的信息可以表示成下面的形式。——假设有7个人，编号从1到7，他们手中的密码分别是54CH2数据结构课件55算法描述：让n个人围坐在一张圆桌旁；for(i=1;i<=n;i++){从1开始报数，报到m停止；报到m的人离开桌子；}#defineLIST_MAX_LENGTH7#definenLIST_MAX_LENGTHtypedefintEntryType;

//将EntryType定义为int类型voidJoseph(intcode[],intn)顺序存储结构：最终的算法实现——算法描述：顺序存储结构：最终的算法实现——56{//通过一维数组code带入n个人手中的密码，n是开始就坐在桌旁的人数SQ_LISTpeople;inttemp,m;//m是报数的上限值

scanf(“%d”,&m);//输入最初的mif(InitList(&people)==ERROR)exitERROR;for(i=1;i<=n;i++)if(ListInsert(&people,i,code[i-1])==ERROR)exitERROR;position=0;//记录当前报数人的编号count=0;//记录当前所报的数目{//通过一维数组code带入n个人手中的密码，n是开始就坐57for(i=1;i<=n;i++){do{//报数position=(position+1)%n;GetElem(people,position,&temp);if(temp>0)count++;}while(count!=m);printf(“%d”,position);//输出当前离开桌旁人的编号GetElem(people,position,&m);people.temp[position-1]=-people.temp[position-1];//将密码变为负值}}for(i=1;i<=n;i++){58链式存储结构：使用一个不带头结点的循环单链表结构。结点结构为：图2-10Nocodenext链式存储结构：图2-10No59用C语言定义typedefstruct{//循环链表中每个结点的数据域部分的类型intNo;//编号intcode;//密码}INFO;typedefINFOEntryType;用C语言定义60算法voidJoseph(intcode[],intn){LINK_LISTpeople;NODE*position,*pre;//position指向当前报数的结点if(InitList(&people)==ERROR)exitERROR;//初始化链表peoplefor(i=1;i<=n;i++)//以n个人的信息为数据域内容向链表插入n个结点if(ListInsert(&people,i,code[i-1])==ERROR)exitERROR;算法61position=people.head;//让position指向最后一个结点，以便报数从第一个开始while(position->next!=people.head)position=NextElem(people,position);scanf(“%d”,&m);//输入最初的mfor(i=1;i<n;i++){count=0;//报数处理do{position=NextElem(people,position);count++;}while(count!=m);position=people.head;62printf(“%d”,position->item.No);//离开桌子处理m=position->item.code;pre=PriorElem(people,position);pre->next=position->next;free(position);position=pre;}printf(“%d”,position->item.No);//处理最后一个人free(position);}printf(“%d”,position->item.No63重点：线性表的顺序存储；线性表的链式存储；顺序表的插入、删除单链表的插入、删除难点：双向链表的系列操作

线性表的应用。

重点：线性表的顺序存储；64第二章线性表线性结构特点：在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外，集合中的每个数据元素均只有一个前驱除最后一个外，集合中的每个数据元素均只有一个后继第二章线性表线性结构特点：在数据元素的非空有限集中652.1线性表的逻辑结构定义：一个线性表是n个数据元素的有限序列例英文字母表（A,B,C,…..Z)是一个线性表例数据元素2.1线性表的逻辑结构例英文字母表（A,B,C,….66例一副扑克的点数（2，3，4，…，J，Q，K，A）从以上例子可看出线性表的逻辑特征是：在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1；其余的内部结点ai(2≦i≦n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。

线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。例一副扑克的点数67特征：元素个数n—表长度，n=0空表1<i<n时ai的直接前驱是ai-1，a1无直接前驱ai的直接后继是ai+1，an无直接后继元素同构，且不能出现缺项特征：68抽象数据类型线性表的定义：ADTList{数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n>=0}数据关系：Rl={〈ai-1，ai〉|ai-1，ai∈D，i=1,2,…,n}基本操作：InitList(&L)DestroyList(&L)ClearList(&L)ListEmpty(L)ListLength(L)GetElem(L,I,&e)LocateElem(L,e,compare())PriorElem(L,cur_e,&pre_e)NextElem(L,cur_e,&next_e)ListInsert(&L,i,e)ListDelete(&L,i,&e)ListTraverse(L,visit())}ADTList抽象数据类型线性表的定义：69算法2.1利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=A∪B。voidunion(List&La，ListLb){La-len=listlength(La);Lb-len=listlength(Lb);for(I=1;I<=lb-len;I++){getelem(lb，I，e);if(!locateelem(la，e，equal))listinsert(la，++la-en，e)}}

算法的时间复杂度：O（ListLength(LA)×ListLength(LB)）

算法2.1利用两个线性表LA和LB分别表示两个集合A和B，70算法2.2巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。算法2.2巳知线性表LA和线性表LB中的数据元素按值非递减有71voidmergelist(listla，listlb，list&lc){initlist(lc);I=j=1;k=0;la-len=listlength(la);lb-len=listlength(lb);while((I<=la-len)&&(j<=lb-len)){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){getelem((la，I++，ai);listinsert(lc，++k，ai);}while(j<=lb-len){getelem((lb，j++，bj);listinsert(lc，++k，bj);}}算法的时间复杂度：O（ListLength(LA)+ListLength(LB)）

voidmergelist(listla，listl722.2线性表的顺序存储结构顺序表：定义：用一组地址连续的存储单元存放一个线性表叫~元素地址计算方法：LOC(ai)=LOC(a1)+(i-1)*LLOC(ai+1)=LOC(ai)+L其中：L—一个元素占用的存储单元个数LOC(ai)—线性表第i个元素的地址特点：实现逻辑上相邻—物理地址相邻实现随机存取实现：可用C语言的一维数组实现2.2线性表的顺序存储结构73a1a2an01n-112n内存V数组下标元素序号M-1typedefintDATATYPE;#defineM1000DATATYPEdata[M];例typedefstructcard{intnum;charname[20];charauthor[10];charpublisher[30];floatprice;}DATATYPE;DATATYPElibrary[M];备用空间数据元素不是简单类型时,可定义结构体数组或动态申请和释放内存DATATYPE*pData=(DATATYPE*)malloc(M*sizeof(DATATYPE));free(pData);a1a2an01n-112n内存V数组下标元素序号M-1ty74由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。又因为除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，所以我们用结构类型来定义顺序表类型。#defineListSize100typedefintDataType;typedefstruct{DataTypedata[ListSize];intlength;}Sqlist;由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型75插入定义：线性表的插入是指在第i（1in+1）个元素之前插入一个新的数据元素x，使长度为n的线性表变为n+1

变成长度为n+1的线性表

需将第i至第n共（n-i+1)个元素后移算法插入变成长度为n+1的线性表需将第i至第n共（n-i76VoidInsertList(Sqlist*L，DataTypex，intI){

intj;if(I<1||I>l.length+1){

printf(“Positionerror”);

returnERROR;}

if(l.length>=ListSize){

printf(“overflow”);

exit(overflow);}

for(j=l.length-1;j>=I-1;j--)

l.data[j+1]=l.data[j];l.data[I-1]=x;l.length++;}VoidInsertList(Sqlist*L，DataT77内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1an-1x内存a1a2aiai+1an01i-1V数组下标n-1in178分析算法的复杂度

这里的问题规模是表的长度，设它的值为。该算法的时间主要化费在循环的结点后移语句上，该语句的执行次数（即移动结点的次数）是。由此可看出，所需移动结点的次数不仅依赖于表的长度，而且还与插入位置有关。当i=n+1时，由于循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，其时间复杂度O（1）；当i=1时，结点后移语句将循环执行n次，需移动表中所有结点，这是最坏情况，其时间复杂度为O（n）。分析算法的复杂度79算法时间复杂度T(n)设Pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为：

也就是说，在顺序表上做插入运算，平均要移动表上一半结点。当表长n较大时，算法的效率相当低。虽然Eis(n)中n的的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为O(n)。动态算法时间复杂度T(n)也就是说，在顺序表上做插入运算，平均80删除定义：线性表的删除是指将第i（1in）个元素删除，使长度为n的线性表

变成长度为n-1的线性表

需将第i+1至第n共（n-i)个元素前移算法删除变成长度为n-1的线性表需将第i+1至第n共（n81

VoiddeleteList(Sqlist*L，inti){intj;if(i<1||i>l.length){printf(“Positionerror”);returnERROR}for(j=i;j<=l.length-1;j++)l.data[j-1]=l.data[j];l.length--;}VoiddeleteList(Sqlist*L，int82内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2ai+1V数组下标01i-1n-2in-112i元素序号i+1n-1nanai+2内存a1a2aiai+1an01i-1V数组下标n-1in183算法评价设Qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素所需移动的元素次数的平均次数为：故在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低。算法评价故在顺序表中插入或删除一个元素时，平均移动表的一半元84顺序存储结构的优缺点优点逻辑相邻，物理相邻可随机存取任一元素存储空间使用紧凑缺点插入、删除操作需要移动大量的元素预先分配空间需按最大空间分配，利用不充分表容量难以扩充顺序存储结构的优缺点852.3线性表的链式存储结构特点：用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息结点

数据域：元素本身信息指针域：指示直接后继的存储位置数据域指针域结点2.3线性表的链式存储结构数据域指针域结点86ZHAOQIANSUNLIZHOUWUZHENGWANG^H例线性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925数据域指针域LIQIANSUNWANGWUZHAOZHENGZHOU存储地址1713192531374331H头指针ZHAOQIANSUNLIZHOUWUZHENGWANG^H87实现Typedefchardatatype;typedefstructnode{

datatype

data;structnode*link;}listnode;listnode*h,*p;datalinkp结点（*p）(*p)表示p所指向的结点(*p).datap->data表示p指向结点的数据域(*p).linkp->link表示p指向结点的指针域线性链表定义：结点中只含一个指针域的链表叫~，也叫单链表实现Typedefchardatatype;lis88typedeflistnode*linklist;listnode*p;linklisthead;注意区分指针变量和结点变量这两个不同的概念。P为动态变量，它是通过标准函数生成的，即p=(listnode*)malloc(sizeof(listnode));函数malloc分配了一个类型为listnode的结点变量的空间，并将其首地址放入指针变量p中。一旦p所指的结点变量不再需要了，又可通过标准函数free(p)释放所指的结点变量空间。指针变量P（其值为结点地址）和结点变量*P之间的关系。typedeflistnode*linkl89一、建立单链表假设线性表中结点的数据类型是字符，我们逐个输入这些字符型的结点，并以换行符‘\n’为输入结束标记。动态地建立单链表的常用方法有如下两种：

1、头插法建表该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。a2…...h头结点an-10an^一、建立单链表a2…...h头结点an-10an90linklistcreatelistf(void){

charch;

linklisthead;

listnode*p;

head=null;

ch=getchar();

while(ch!=‵\n′){

p=(listnode*)malloc(sizeof(listnode));

p–>data=ch;

p–>next=head;

head=p;

ch=getchar();}

return(head);

}linklistcreatelistf(void)912、尾插法建表头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。2、尾插法建表92linklistcreater(){charch;linklisthead;listnode*p，*r;//(，*head;)head=NULL;r=NULL;while((ch=getchar()!=‵\n′){p=(listnode*)malloc(sizeof(listnode));p–>data=ch;if(head==NULL)head=p;elser–>next=p;r=p;}if(r!=NULL)r–>next=NULL;return(head);}linklistcreater(){93说明：第一个生成的结点是开始结点，将开始结点插入到空表中，是在当前链表的第一个位置上插入，该位置上的插入操作和链表中其它位置上的插入操作处理是不一样的，原因是开始结点的位置是存放在头指针（指针变量）中，而其余结点的位置是在其前趋结点的指针域中。算法中的第一个if语句就是用来对第一个位置上的插入操作做特殊处理。算法中的第二个if语句的作用是为了分别处理空表和非空表两种不同的情况，若读入的第一个字符就是结束标志符，则链表head是空表，尾指针r亦为空，结点*r不存在；否则链表head非空，最后一个尾结点*r是终端结点，应将其指针域置空。说明：第一个生成的结点是开始结点，将开始结点插入到空表中，是94如果我们在链表的开始结点之前附加一个结点，并称它为头结点，那么会带来以下两个优点：

a、由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上的操作一致，无需进行特殊处理；

b、无论链表是否为空，其头指针是指向头结点在的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。如果我们在链表的开始结点之前附加一个结点，并称它为头结点，那95ha1a2头结点an^…...h空表^头结点：在单链表第一个结点前附设一个结点叫～头结点指针域为空表示线性表为空ha1a2头结点an^…...h空表^头结点：在96linklistcreatelistr1(){charch;linklisthead=(linklist)malloc(sizeof(listnode));listnode*p，*r；r=head;

while((ch=getchar())!=‵\n′{p=(listnode*)malloc(sizeof(listnode));p–>data=ch;r–>next=p;r=p;}r–>next=NULL;return(head);}linklistcreatelistr1(){97上述算法里动态申请新结点空间时未加错误处理，可作下列处理：p=(listnode*)malloc(sizeof(listnode))if(p==NULL)error(〝Nospacefornodecanbeobtained〞);returnERROR;以上算法的时间复杂度均为O(n)上述算法里动态申请新结点空间时未加错误处理，可作下列处理：98二、查找运算1、按序号查找在链表中，即使知道被访问结点的序号i，也不能象顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。设单链表的长度为n，要查找表中第i个结点，仅当1≦i≦n时，i的值是合法的。但有时需要找头结点的位置，故我们将头结点看做是第0个结点，其算法如下：二、查找运算99Listnode*getnode(linklisthead，inti){intj;listnode*p;p=head;j=0;while(p–>next&&j<I){p=p–>next;j++;}if(i==j)returnp;elsereturnNULL;}Listnode*getnode(linklisthe1002、按值查找按值查找是在链表中，查找是否有结点值等于给定值key的结点，若有的话，则返回首次找到的其值为key的结点的存储位置；否则返回NULL。查找过程从开始结点出发，顺着链表逐个将结点的值和给定值key作比较。其算法如下：Listnode*locatenode(linklisthead，intkey){listnode*p=head–>next;while(p&&p–>data!=key)p=p–>next;re