CHAP2线性表(数据结构)

1线性表是一种最简单的线性结构第二章线性表2.1 线性表及其基本运算2.2 线性表的顺序存储结构2.3 线性表的链式存储结构线性表的逻辑结构、物理结构，以及它们之间的相互关系；定义与之相适应的运算；设计相应的算法；分析算法的效率。32.1线性表的逻辑结构2.3线性表类型的实现

链式映象2.4一元多项式的表示2.2线性表类型的实现

顺序映象42.1线性表及其基本运算

一、线性表（linear_list）线性表是n个数据元素的有限序列，记为：

L=（a1,a2,…,an）

数据元素之间的关系是：

ai-1领先于ai，ai领先于ai+1。称ai-1是ai的直接前驱元素；ai+1是ai的直接后继元素。除a1外，每个元素有且仅有一个直接前驱元素，除an外，每个元素有且仅有一个直接后继元素。线性表中数据元素的个数n(n>=0)称为线性表的长度，当n=0时，称为空表。6（a1,a2,…ai-1，ai,ai＋1

，…,an）数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长线性终点7【例1】26个英文字母组成的字母表

（A，B，C、…、Z）【例2】某校从2000年到2005年各种型号的计算机拥有量的变化情况()。

（150，236，321，400，500，600）数据元素ai（1≤i≤n）只是个抽象符号，其具体含义在不同情况下可以不同。8【例3】学生健康情况登记表。姓名学号性别年龄

健康情况王小林790631

男18

健康陈红790632

女20

一般刘建平790633

男21

健康张立立790634

男17

神经衰弱……..……..…….…….…….92.线性表逻辑结构特征(非空有限集)(1)集合中必存在唯一的一个“第一元素”；(2)集合中必存在唯一的一个“最后元素”(3)除最后元素在外，均有唯一的后继；(4)除第一元素之外，均有唯一的前驱。线性结构是一个数据元素的有序（次序）集103.抽象数据类型线性表的定义ADTList{

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

为线性表的表长;

称n=0

时的线性表为空表。}数据关系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}{设线性表为(a1，a2,...，ai，...，an),

称i为ai在线性表中的位序。}11

基本操作：

结构初始化操作结构销毁操作

引用型操作

加工型操作

}ADTList12

InitList(&L)操作结果：构造一个空的线性表L。初始化操作13

结构销毁操作DestroyList(&L)初始条件：线性表L已存在。销毁线性表L。操作结果：14ListEmpty(L)ListLength(L)PriorElem(L,cur_e,&pre_e)NextElem(L,cur_e,&next_e)

GetElem(L,i,&e)LocateElem(L,e,compare())ListTraverse(L,visit())引用型操作15加工型操作

ClearList(&L)PutElem(&L,i,&e)ListInsert(&L,i,e)ListDelete(&L,i,&e)

INITIATE（L）

初始化操作 设定一个空的线性表LLENGTH（L）

求长度函数值为L中数据元素的个数GET（L，i）

取元素函数1<=i<=LENGTH(L)时返回L中第i个数据元素，否则为空元素NULL。i称为该数据元素在L中的位序PRIOR（L，elm）

求前驱函数

elm为L中的一个数据元素，若它的位序大于1，则函数值为elm前驱，否则为NULLNEXT（L，elm）

求后继函数 若elm的位序小于表长，则函数值为elm的后继，否则为NULLLOCATE（L，x）

定位函数给定值x，若x不在表中，则返回0，否则，返回x在表中第一次出现时的位序INSERTE（L,i,b）前插操作在第i个元素之前插入新元素b，i的取值范围为：1<=i<=n+1；i=n+1表示在表尾插入，n为表长DELETE（L，i）

删除操作删除线性表L中的第i个元素，1<=i<=nEMPTY(L)

判空表函数 若L为空表，则返回布尔值“true”，否则返回布尔值“false”CLEAR（L）

表置空操作 将L置为空表183.组合基本运算，实现复杂运算

例

2-2(构造A)例

2-3(归并A.B)例

2-1(A＝A∪B)19

假设:有两个集合A和B分别用两个线性表LA和LB表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合A＝A∪B。【例2-1】

20

要求对线性表作如下操作：扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。上述问题可演绎为：211．从线性表LB中依次察看每个数据元素;2．依值在线性表LA中进行查访;3．若不存在，则插入之。GetElem(LB,i)→e

LocateElem(LA,e,equal())

ListInsert(LA,n+1,e)操作步骤：22

GetElem(Lb,i,e);//取Lb中第i个数据元素赋给eif(!LocateElem(La,e,equal()))

ListInsert(La,++La_len,e);

//La中不存在和e相同的数据元素，则插入之voidunion(List&La,ListLb){La_len=ListLength(La);//求线性表的长度

Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){}}//union23

已知一个非纯集合B，试构造一个纯集合A，使A中只包含B中所有值各不相同的数据元素。仍选用线性表表示集合【例

2-2】24集合B集合A从集合B

取出物件放入集合A要求集合A中同样物件不能有两件以上因此，算法的策略应该和例2-1相同25voidpurge(List&La,ListLb){

La_len=ListLength(La);Lb_len=ListLength(Lb);}//purge

GetElem(Lb,i,e);//取Lb中第i个数据元素赋给eif(!LocateElem(La,e,equal()))

ListInsert(La,++La_len,e);

//La中不存在和e相同的数据元素，则插入之for(i=1;i<=Lb_len;i++){}InitList(La);//构造(空的)线性表LA26若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，即ai≥ai-1

或ai≤ai-1(i=2,3,…,n)，则称该线性表为有序表(OrderedList)。试改变结构，以有序表表示集合。27例如：（2，3，3，5，6，6，6，8，12）对集合B而言，

值相同的数据元素必定相邻对集合A而言，

数据元素依值从小至大的顺序插入因此，数据结构改变了，解决问题的策略也相应要改变。28voidpurge_order(List&La,ListLb)

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

for(i=1;i<=Lb_len;i++){

}}//purge_order

GetElem(Lb,i,e);//取Lb中第i个数据元素赋给eif(ListEmpty(La)||!equal(en,e))

{

ListInsert(La,++La_len,e);en=e;}

//La中不存在和e相同的数据元素，则插入之29则

归并两个“其数据元素按值非递减有序排列”的有序表LA和LB，求得有序表LC也具有同样特性。设

La=(a1,…,ai,…,an)

Lb=(b1,…,bj,…,bm)

Lc=(c1,…,ck,…,cm+n)【例

2-3】k=1,2,…,m+n301．初始化LC为空表；基本操作：2．分别从LA和LB中取得当前元素ai

和bj；3．若ai≤bj，则将ai

插入到LC中，否则将

bj插入到LC中；4．重复2和3两步，直至LA或LB中元素被取完为止；5．将LA表或LB表中剩余元素复制插入到

LC表中。31

//La和Lb均非空，i=j=1,k=0GetElem(La,i,ai);GetElem(Lb,j,bj);

if(ai<=bj){//将ai插入到Lc中

ListInsert(Lc,++k,ai);++i;}else{//将bj插入到Lc中

ListInsert(Lc,++k,bj);++j;}32voidMergeList(ListLa,ListLb,List&Lc){

InitList(Lc);//构造空的线性表Lci=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);}//merge_listwhile((i<=La_len)&&(j<=Lb_len))

{//La和Lb均不空}while(i<=La_len)

//若La不空while(j<=Lb_len)//若Lb不空33

while(i<=La_len){GetElem(La,i++,ai);ListInsert(Lc,++k,ai);

}

//插入La表中剩余元素

while(j<=Lb_len){GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);

}

//插入Lb表中剩余元素342.2线性表的顺序表示和实现351.定义：用一组地址连续的存储单元

依次存放线性表中的数据元素。

a1a2

…ai-1ai

…an线性表的起始地址，称作线性表的基地址2.2.1线性表的顺序存储结构362.实现：可用C/C++的一维数组实现a1a2an01n-112n内存单元数组下标元素序号m-1373．结点ai

的存储地址

以“存储位置相邻”表示有序对<ai-1，ai>

即：LOC(ai)=LOC(ai-1)+C

一个数据元素所占存储量↑所有数据元素的存储位置均取决于第一个数据元素的存储位置。

LOC(ai)=LOC(a1)+(i-1)×C

↑基地址38【例1】一个大小为10的一维数组A，每个数组元素用相邻的8个字节存储。假设存储数组元素A[０]的第一个字节的地址是1020，则A[6]的第一个字节的地址是

1068LOC(a6)=LOC(a1)+8*(6-0)=1020+8×(6-0)=1068解：地址计算通式为：LOC(ai)=LOC(a1)+L*（i-1）39#defineMAXNUM

<顺序表最大元素个数>typedefstruct{

}Sqlist；4.顺序存储结构（1）静态分配的顺序存储结构Elemtypeelem[MAXNUM];intlength;40静态顺序表：lengthelem[MAXNUM]3265896例如：MAXNUM=1241（2）动态分配的顺序存储结构※typedefstruct{

}SqList;//俗称顺序表const

intLIST_INIT_SIZE=80;//线性表存储空间的初始分配量ElemType*elem;//存储空间基址int

listsize;//当前分配的存储容量intlength;

//当前长度42动态顺序表*elemlengthlistsize例如：742000H2000H472000H3578432.2.2顺序表的基本操作InitList(&L)//结构初始化LocateElem(L,e,compare())//查找ListInsert(&L,i,e)//插入元素ListDelete(&L,i,&e)//删除元素//(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType))//free(T)StatusListCreate_Sq(SqList&L,intn)44预定义常量和类型：//函数结果状态代码#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-2//Status是函数的类型，其值是函数结果状态代码typedefintStatus;45StatusInitList_Sq(SqList&L){//构造一个空的线性表

}//InitList_Sq算法时间复杂度：O(1)L.elem=new

ElemType[LIST_INIT_SIZE];if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZEreturnOK;1.初始化动态分配内存设置顺序表的大小46例如：在顺序表中查找元素23754138546217L.elemL.lengthL.listsizee=38pppppi12341850p2.查找元素47

int

LocateElem_Sq(SqListL,ElemTypee){

//

在顺序表中查询第一个满足判定条件的数据元素，

//若存在，则返回它的位序，否则返回0}//LocateElem_Sq

O(ListLength(L))算法的时间复杂度为：i=1;

//i的初值为第1元素的位序p=L.elem;

//p的初值为第1元素的存储位置while(i<=L.length&&(*p++!=e))++i;if(i<=L.length)returni;elsereturn0;48线性表操作

ListInsert(&L,i,e)的实现：首先分析:插入元素时，线性表的逻辑结构发生什么变化？3.插入元素49

(a1,…,ai-1,ai,…,an)改变为

(a1,…,ai-1,e,ai,…,an)a1a2

…ai-1ai

…ana1a2

…ai-1

…aiean<ai-1,ai><ai-1,e>,<e,ai>表的长度增加1502118307542568721183075例如：ListInsert_Sq(L,5,66)L.length-10pppq87564266q=&(L.elem[i-1]);//q指示插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;p*q=e;实现步骤：移动元素插入元素51L.length>=L.listsize//当前存储空间已满，不能插入i<1||i>L.length+1//

插入位置不合法

事先应判断:插入位置i是否合法?表是否已满?注意：52算法思想：1、进行合法性检查：

1<=i<=L.length+12、检查线性表是否已满

3、将第n个至第i个元素逐一后移一个单元4、在第i个位置处插入新元素5、将表的长度加1.53

StatusListInsert_Sq(SqList&L,inti,ElemTypee){

//

在顺序表L的第i个元素之前插入新的元素e,}//ListInsert_Sq

算法时间复杂度为:O(ListLength(L))q=&(L.elem[i-1]);//q指示插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;

//插入位置及之后的元素右移*q=e;//插入e++L.length;//表长增1returnOK;if(i<1||i>L.length+1)returnERROR;元素右移if(L.length>=L.listsize

)returnOVERFLOW;54考虑移动元素的平均情况:

假设在第

i个元素之前插入的概率为，

则在长度为n的线性表中插入一个元素所需移动元素次数的期望值为：

若假定在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素的期望值为：55线性表操作

ListDelete(&L,i,&e)的实现：首先分析：删除元素时，线性表的逻辑结构发生什么变化？4.删除元素56

(a1,…,ai-1,ai,ai+1,…,an)改变为

(a1,…,ai-1,ai+1,…,an)ai+1…an<ai-1,ai>,<ai,ai+1><ai-1,ai+1>表的长度减少1a1a2

…ai-1ai

ai+1

…ana1a2

…ai-1

572118307542568721183075L.length-10pppq8756p=&(L.elem[i-1]);q=L.elem+L.length-1;for(++p;p<=q;++p)*(p-1)=*p;例如：ListDelete_Sq(L,5,e)p实现步骤：移动元素58(L.length=0)//当前存储空间为空，不能删除(i<1)||(i>L.length)//

删除位置不合法

事先应判断:删除位置i是否合法?表是否为空?注意：59算法思想：1、进行合法性检查：

1<=i<=L.length2、检查线性表是否为空

3、将第i+1个至第n个元素逐一前移一个单元4、将表的长度减1.60StatusListDelete_Sq(SqList&L,inti,ElemType&e){}//ListDelete_Sqfor(++p;p<=q;++p)*(p-1)=*p;//

删除元素--L.length;//表长减1returnOK;算法时间复杂度为:

O(ListLength(L))p=&(L.elem[i-1]);//p为被删除元素的位置e=*p;//被删除元素的值赋给eq=L.elem+L.length-1;//表尾元素的位置if((i<1)||(i>L.length))returnERROR;元素左移if(L.length==0)returnERROR;61考虑移动元素的平均情况:

假设删除第

i个元素的概率为

,则在长度为n的线性表中删除一个元素所需移动元素次数的期望值为：若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值为：62typedefintElemType;

StatusListCreate_Sq(SqList&L,intn){//创建顺序表}//ListCreate_SqreturnOK;for(inti=1;i<=n;++i){ cin>>x; L.elem[i-1]=x; ++L.length; }5.创建顺序表632.2.3利用上述定义的顺序结构可以实现其它更复杂的操作例

2-5(逆置顺序表)例

2-6(调整顺序)例

2-4(归并A、B)64则

归并两个“其数据元素按值非递减有序排列”的有序表LA和LB，求得有序表LC也具有同样特性。（用顺序表实现）设

La=(a1,…,ai,…,an)

Lb=(b1,…,bj,…,bm)

Lc=(c1,…,ck,…,cm+n)【例

2-4】k=1,2,…,m+n65LA＝（1，3，4，9，10）LB＝（2，5，6，7，8）LC＝(1，2，3，4，5，6，7，8，9，10)Legth=5

Legth=5

Legth=10例如：6613942567PaPa_lastPb_lastPbLaLb8LcPc1234567810910算法思路ElemType*pa,*pb,*pc,*pa_last,*pb_last;pa=La->elem;pa_last=La->elem+La->length-1;pb=Lb->elem;pb_last=Lb->elem+Lb->length-1;Lc->listsize=Lc->length=La->length+Lb->length;if(*pa<=*pb)*pc++=*pa++;else*pc++=*pb++;pa<=pa_last&&pb<=pb_last

第二步归并（将剩余元素插入到Lc末尾）第一步归并结束第二步归并结束67

while((i<LA.length)&&(j<LB.length)) if(LA.elem[i]<=LB.elem[j]){

LC.elem[k]=LA.elem[i]; i++;k++; } else{

LC.elem[k]=LB.elem[j]; j++;k++;}

voidMerge_sq(SqList&LC,SqListLA,SqListLB){

i=0,j=0,k=0;

LC.length=LA.length+LB.length;68

while(j<LB.length){ LC.elem[k]=LB.elem[j]; j++;k++;

}

while(i<LA.length){ LC.elem[k]=LA.elem[i]; i++;k++;

}

}//Merge_sq69设有一个顺序表A，包含n个数据元素。编写一个算法，将顺序表A逆置，只允许在原表的存储空间外再增加一个附加的工作单元。【例2-5】70LA＝（21，62，8，9，11，25，20）

LA＝（20，25，11，9，8，62，21）逆置后：

i逆置前：

j附加单元tempLA＝（20，62，8，9，11，25，21）

temp＝LA(i);LA(i)=LA(j);LA(j)=temp

i

j71

temp=L.elem[i];L.elem[i]=L.elem[n-i-1];L.elem[n-i-1]=temp;

for(i=0;i<m;++i){}voidinvert_sq(SqList&L)

{

n=L.length;i=0,m=n/2;}//invert_sq72设有一个顺序表A，包含n个数据元素。调整顺序表A，使其左边的所有元素均小于0，使其右边的所有元素均大于0。【例2-6】73LA＝（-62，-8，-25，20，9，8，21）调整前：LA＝（21，-62，8，9，-8，-25，20）

iLB＝（）xy调整后：LB＝（21）yxLA＝（21，-62，8，9，-8，-25，20）

iLB＝（-6221）yxLA＝（21，-62，8，9，-8，-25，20）

i与0比较74

if(LA.elem[i]<0){ LB.elem[x]=LA.elem[i];x++;}//前置

else{LB.elem[y]=LA.elem[i]; y--; }for(i=0;i<n;i++)voidadjust_sq(SqList&LA)

{

InitList_Sq(LB);

n=LA.length;x=0;y=n-1;}//adjust_sqfor(i=0;i<n;++i)LA.elem[i]=LB.elem[i];DestroyList(LB);75优点：逻辑相邻，物理相邻可随机存取任一元素存储空间使用紧凑缺点：插入、删除操作需要移动大量的元素预先分配空间需按最大空间分配，利用不充分表容量难以扩充顺序存储结构的优缺点762.3.1单链表2.3.2单向循环链表2.3.3双链表2.3.4双向循环链表2.3线性表的链式存储结构771.概述用一组地址任意的存储单元存放线性表中的数据元素。2.3.1单链表以元素(数据元素的映象)

+指针(指示后继元素存储位置)=结点数据域指针域结点结构数据域：元素本身信息指针域：指示直接后继的存储位置78ZHAOQIANSUNLIZHOUWUZHENGWANG^H例线性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925数据域指针域LIQIANSUNWANGWUZHAOZHENGZHOU存储地址1713192531374331H头指针79

以线性表中第一个数据元素

的存储地址作为线性表的地址，称作线性表的头指针。头结点

a1a2…...an^头指针头指针

有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。空指针以“结点的序列”表示线性表

称作链表h空表^单链表的一般图示法80上例链表的逻辑结构示意图有以下两种形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH区别：①无头结点②有头结点81

typedefstructLNode{ElemTypedata;//数据域

structLnode*next;//指针域

}LNode,*LinkList;

2.结点和单链表的C语言描述LinkListL；//L为单链表的头指针数据域指针域结点结构823.单链表的运算GetElem(L,i,e)//取第i个数据元素ListInsert(&L,i,e)//插入数据元素ListDelete(&L,i,e)//删除数据元素ClearList(&L)//重置线性表为空表CreateList(&L,n)

//生成含n个数据元素的链表83(1)单链表元素的读取GetElem(L,i,&e)L1p5^j=1假设i=2j<ij=j+1=2j=i找到！！！84L1p5^j=1j<ij=j+1=2j<i假设i=4j=j+1=3j<i=∧没找到！！！非法位置85L1p5^j=1j>i假设i=0没找到！！！非法位置86

StatusGetElem_L(LinkListL,inti,ElemType&e){//L是带头结点的链表的头指针，以e返回第i个元素}//GetElem_L算法时间复杂度为:O(ListLength(L))p=L->next;j=1;//p指向第一个结点，j为计数器while(p&&j<i){p=p->next;++j;}//

顺指针向后查找，直到p指向第i个元素

//

或p为空if(!p||j>i)

returnERROR;//第i个元素不存在e=p->data;//取得第i个元素returnOK;循环条件分析：

p=L->next;j=1；while(p&&j<i){p=p->next;++j;}两个条件有６种组合：1．P=NULLANDj<i空表且i>1或i>表长+1，异常，返回NULL2．P=NULLANDj=i空表且i=1或i=表长+1，异常，返回NULL3．P=NULLANDj>i空表且i<1，异常，返回NULL4．P!=NULLANDj<i继续循环5．P!=NULLANDj=i确定第i个结点，正常出循环6．P!=NULLANDj>ii<1，异常，返回NULL88

(2)插入操作

ListInsert(&L,i,e)xsbapabps->next=p->next;p->next=s;插入前插入后89

因此，在单链表中第i个结点之前进行插入的基本操作为:

找到线性表中第i-1个结点(定位)，然后修改其指向后继的指针。算法思路：在链表中插入结点只需要修改指针。但同时，若要在第i个结点之前插入元素，修改的是第i-1个结点的指针。90StatusListInsert_L(LinkList&L,inti,ElemTypee){

//L为带头结点的单链表的头指针，

//在链表中第i个结点之前插入新的元素e

}//LinstInsert_L算法的时间复杂度为:O(ListLength(L))……p=L;j=0;while(p&&j<i-1)

{p=p->next;++j;}

//

寻找第i-1个结点if(!p||j>i-1)

returnERROR;//

i大于表长或者小于191s=new

LNode;

//生成新结点s->data=e;s->next=p->next;p->next=s;//插入returnOK;92(3)删除操作ListDelete(&L,i,&e)cabpq=p->next;qp->next=q->next;deleteq;93

在单链表中删除第

i个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。算法思路：94StatusListDelete_L(LinkList&L,inti,ElemType&e){

//删除以L为头指针(带头结点)的单链表中第i个结点

}//ListDelete_L算法的时间复杂度为:O(ListLength(L))p=L;j=0;while(p->next&&j<i-1){p=p->next;++j;}

//寻找第i个结点，并令p指向其前趋if(!(p->next)||j>i-1)

returnERROR;//删除位置不合理q=p->next;p->next=q->next;

//删除并释放结点e=q->data;deleteq;returnOK;95(4)清空操作ClearList(&L)voidClearList(&L){//将单链表重新置为一个空表

while(L->next){

p=L->next;L->next=p->next;

}}//ClearListDeletep;算法时间复杂度：O(ListLength(L))96（5）如何从线性表得到单链表？链表是一个动态的结构，它不需要预分配空间，因此生成链表的过程是一个结点“逐个插入”的过程。97头插法思路：^Ldatanextpdatanextpp->next=L->nextL->next=p(1)建立一个“空表”；(2)输入数据元素an，建立结点并插入；(3)输入数据元素an-1，建立结点并插入；(4)依次类推，直至输入a1为止。逆位序输入该方法生成链表的结点次序与输入顺序相反。98voidCreateList_L(LinkList&L,intn){//逆序输入n个数据元素，建立带头结点的单链表}//CreateList_L算法的时间复杂度为:O(Listlength(L))L=newLNode;L->next=NULL;

//先建立一个带头结点的单链表for(i=n;i>0;--i){p=newLNode;

cin>>

p->data;//输入元素值

p->next=L->next;L->next=p;//插入}99尾插法思路（正位序输入）：^Ldatanextppdatanextp->next=L->nextL->next=pp->next=L->next->nextL->next->next=pL->next->next->.......->next???100尾插法思路：^Ldatanextpspdatanextp->next=s->nexts->next=p注意：

⒈采用尾插法建表，生成的链表中结点的次序和输入顺序一致。

⒉必须增加一个尾指针s,使其始终指向当前链表的尾结点。101voidCreateList_L(LinkList&L,intn){//正序输入n个数据元素，建立带头结点的单链表}//CreateList_L算法的时间复杂度为:O(Listlength(L))L=newLNode;L->next=NULL;S=L;//

建立带头结点/尾指针的单链表for(i=1;i<=n;++i){p=newLNode;

cin>>

p->data;//输入元素值

p->next=S->next;S->next=p;S=p;//插入}102则

归并两个“其数据元素按值非递减有序排列”的有序表LA和LB，求得有序表LC也具有同样特性。（用单链表实现）设

La=(a1,…,ai,…,an)

Lb=(b1,…,bj,…,bm)

Lc=(c1,…,ck,…,cm+n)【例

2-7】链表的应用。k=1,2,…,m+n103算法分析：搜索：需要两个指针搜索两个链表；比较：比较结点数据域中数据的大小；插入：将两个结点中数据小的结点插入新链表。1043

5

8

11^

2

6

7

12^9

Pa、Pb用于搜索La和Lb，Pc指向新链表当前结点LaLbPbPaLcPc=∧不需要重建结点空间，只要修改指针即可105voidMergeList_L(LinkListLa,LinkListLb,LinkList&Lc){//合并两个有序表

}//MergeList_Lpa=La->next;pb=Lb->next;//p指向第一个结点

Lc=pc=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;}

106假如x=3y=6算法思路：138459L^Pqqq【例2-8】设计一个算法，要求删除线性表中介于x和y之间的数据。107voiddel_LQ(LinkListL,intx,inty){}//del_LQp=L;while(p->next){if(p->next->data>=x&&p->next->data<=y) {

q=p->next; p->next=q->next; delete(q); } else p=p->next;}线性表链式存储结构的特点：(1).

逻辑上相邻的元素，其物理位置不一定相邻；元素之间的邻接关系由指针域指示。(2).链表是非随机存取存储结构；对链表的存取必须从头指针开始。(3).链表是一种动态存储结构；链表的结点可调用new()申请和delete()释放。(4).插入删除运算非常方便；只需修改相应指针值。109单链表的特点：1．它是一种动态结构，整个存储空间为多个链表共用。2．指针占用额外存储空间。3．在链表中，元素的“位序”概念淡化，结点的“位置”概念加强。4．不能随机存取，查找速度慢,但是插入、删除操作很方便。1101.定义：最后一个结点的指针域的指针又指回第一个结点的链表，使链表构成环状。a1a2…...an

带头结点的单循环链表h空表2.3.2单向循环链表111特点：从表中任一结点出发均可找到表中其他结点，提高查找效率。单循环链表a1a2…...an

带头结点的单循环链表112typedefstructLNode{

ElemTypedata; structLNode*next;}LNode,*CircleLinkList;2.存储结构（和单链表相同）113与单链表基本一致,它们仅在循环终止条件上有所不同。3.基本操作单链表：p==NULL或p->next==NULL循环链表：p==L或p->next==L114头插法LdatanextpdatanextpL->next=p;（1）单向循环链表创建p->next=L->next;115头插法voidCreatListF(CircleLinkList&L){

}//CreatListFcharch;

L=newLNode;//头指针

L->next=L;

//链表开始为空

ch=getchar();//读入第1个字符

while(ch!='\n'){

p=newLNode;//生成新结点

p->data=ch;

p->next=L->next;L->next=p;

ch=getchar();

//读入下一字符

}

116尾插法Ldatanextprpdatanextp->next=Lr->next=p;117尾插法voidCreatListR(CircleLinkList&L){

}//CreatListR

L=newLNode;//头指针

L->next=L;

//链表开始为空

r=L;//设置尾指针初值

ch=getchar();//读入第1个字符

while(ch!='\n'){

p=newLNode;

p->data=ch;

p->next=L;//将新结点插到r之后

r->next=p;

r=p;//尾指针指向新表尾

ch=getchar();

//读入下一字符

}//endwhile118（2）单向循环链表元素的读取L1p5j=1假设i=2j<ij=j+1=2j=i找到！！！119L1p5j=1j<ij=j+1=2j<i假设i=4j=j+1=3j<i=L没找到！！！120L1p5j=1j>i假设i=0没找到！！！121xsbapabps->next=p->next;p->next=s;插入前插入后（3）单向循环链表的插入（同单链表）122cabpq=p->next;qp->next=q->next;deleteq;（4）单向循环链表的删除（同单链表）1232.3.3双向链表∧∧L空双向链表：非空双向链表：∧L∧ABbcapp->prior->next=p=p->next->prior;priordatanext124结构定义typedefstructDBLNode{ElemTypedata;

//数据域

structDBLNode*prior;

//指向前驱的指针域

structDBLNode*next;

//

指向后继的指针域}DBLNode,*DBLinkList;priordatanext1252.3.4双向循环链表L空双向循环链表：非空双向循环链表：LABbcapp->prior->next=p=p->next->proir;1261.结构定义typedefstructDBLNode{ElemTypedata;

//数据域

structDBLNode*prior;

//指向前驱的指针域

structDBLNode*next;

//

指向后继的指针域}DBLNode,*DBLinkList;priordatanext1272.双向循环链表的操作InitDBList(&DL)LocateDBList(DL,i)LocateDBNode(DL,key)InsertDBNode(&DL,i,x)DeleteDBNode(&DL,inti)CreateDBList(&DL)128voidInitDblList(DBLinkList&DL)

{//初始化双向循环链表

}//InitDblListDL=newDBLNode;if(DL==NULL){cout<<"存储分配错!\n";exit(1); }DL->prior=DL->next=DL;

//表头结点的链指针指向自己(1)初始化双向循环链表129DBLNode*LocateDBList(DBLinkListDL,inti)

{//按位查找

}//LocateDBListp=DL->next;

j=1;while(p!=DL&&j<i){ p=p->next;j++; } if(p==DL||j>i)returnNULL; elsereturnp;(2)在双向循环链表中按位查找130DBLNode*LocateDBNode(DBLinkListDL,ElemTypekey)

{//按值查找

}//LocateDBNodep=DL->next;

while(p!=DL&&key!=p->data) p=p->next; if(p==DL)returnNULL; elsereturnp;(3)在双向循环链表中按值查找131(4)双向循环链表的前插操作算法voiddinsertbefor(DBLNode*p，ElemTypex){

q=newDBLNode;q—>data=x;

//数据域

q—>prior=p—>prior;

q—>next=p;

p—>prior—>next=q;

p—>prior=q;}算法时间复杂度为:

O(1)xqbaP132intInsertDblNode(DBLinkList&DL,inti,ElemTypex)

{//前插法

}//InsertDblNodep=LocateDBList(DL,i);//指针定位于插入位置if(!p)returnERROR;q=newDBLNode;//分配结点q->data=x;q->prior=p->prior;q->next=p;//插入结点p->prior->next=q; p->prior=q;133(5)双向链表的后插操作算法voi