西安电子科技大学数据结构课件2 Linear lists

第二章线性表本章内容2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.3.1线性链表2.3.2循环链表2.3.3双向链表2.4一元多项式的表示及相加12.1线性表的类型定义定义：一个线性表是有n个数据元素的有限序列：(a1，a2，…，ai，…，an)。线性表中元素之间的关系是线性关系：存在惟一的第一个元素；存在惟一的最后一个元素；除第一个元素之外，每个元素均只有一个直接前驱；除最后一个元素之外，每个元素均只有一个直接后继。线性表中的元素类型：原子类型：如整数、字符等。结构类型：如表示一个学生信息的数据元素，包含学号、姓名、性别等数据项。一个线性表中元素的个数n(n≥0)定义为线性表的长度，n=0时称为空表。非空线性表中的每个元素都有一个确定的位序。22.1线性表的类型定义线性表的抽象数据类型定义：ADTList{

数据对象：D={ai

|ai

ElemSet,i=1,2,…n,n0}

数据关系：R={<ai-1,ai>|ai-1,aiD,i=1,2,…n}

基本运算：InitList(&L);DestroyList(&L);Length(L);GetElem(L,i,&e);LocateElem(L,e,compare());InsertElem(&L,i,e);DeleteElem(&L,i,&e);……}ADTList32.1线性表的类型定义抽象运算（算法2.1）

例2-1利用两个线性表LA和LB分别表示集合A和B，求一个新的集合A=A∪B。

算法思路：集合中的元素间是松散的关系，只需将在线性表LB中而不在LA中的数据元素追加到LA的尾部即可。voidunion(List&La，ListLb){

La_len=Length(La);Lb_len=Length(Lb);

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

GetElem(Lb,i,e);if(!LocatElem(La,e,equal))

InsertElem(La,++La_len,e);}}//union4特点：存储单元地址连续（需要一段连续空间）逻辑上相邻的数据元素其物理位置也相邻存储密度大（100%）随机存取元素序号与存储位置存在如下关系：2.2线性表的顺序表示和实现顺序表---线性表的顺序存储 内涵：

线性表的顺序存储指用一组地址连续的存储单元依次存储线性表的数据元素。这称为顺序表。a1a2...aian...}d

Loc(ai)=Loc(a1)+(i-1)*d(1≤i≤n)52.2线性表的顺序表示和实现顺序表存储的Ｃ语言实现 由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。下面我们用结构类型来定义顺序表类型。 //----------动态分配------------#defineLIST_INIT_SIZE100 //空间初始分配量#defineLISTINCREMENT10 //空间分配增量typedefstruct{

ElemType*elem; //存储空间基址

intlength; //当前长度

intlistsize; //当前分配的存储容量}SqList；62.2线性表的顺序表示和实现创建一个空的顺序表（算法2.3） StatusInitList_sq(SqList&L){

L.elem=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType)); if(!L.elem)exit(OVERFLOW);

L.length=0;

L.listsize=INIT_SIZE; returnOK;}//InitList_sq72.2线性表的顺序表示和实现线性表上的基本运算插入运算 含义： 将元素e插入到线性表：(a1,a2,…,ai-1,ai,…,an)中，构成新的线性表(a1,a2,…,ai-1,e,ai,…,an)，满足ai-1≤e≤ai,(其中≤为比较关系),即不破坏原线性关系。表的长度为n+1将元素e插入到元素ai-1之后，ai-1的直接后继和ai

的直接前驱就改变了，需要在顺序表的存储结构上反映出来。82.2线性表的顺序表示和实现顺序表上插入运算的实现:a1a2......ai-1anai将元素ai～an（n-i+1个元素）依次向后移动一个位置，腾出要放置e的单元。a1a2......ai-1anaie将元素e放在腾出的第i个空位上。a1a2...aian...ai-1e在线性表L的第i个位置上插入元素e。e92.2线性表的顺序表示和实现以7个元素的顺序表为例进行说明，将元素e插入a5之前。a1a2a5a7a4a3a6KK+1K+4K+6K+3K+2K+5K+7e(1)元素a7向后移动一个位置；(2)元素a6向后移动一个位置；a1a2a5a4a3a6a7KK+1K+4K+6K+3K+2K+5K+7a1a2a5a6a4a3a7KK+1K+4K+6K+3K+2K+5K+7(3)元素a5向后移动一个位置；a1a2a6a4a3a5a7KK+1K+4K+6K+3K+2K+5K+7(4)将元素e插入到空位上。

ee102.2线性表的顺序表示和实现用类C语言实现顺序表的插入StatusListInsert_sq(SqList&L,inti,ElemTypex){//将元素x插入在线性表L的第i个元素位置上if(i<1||i>L.length+1)returnERROR;if(L.length>=L.Listsize){

newbase=(ElemType*)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);

L.elem=newbase;

L.listsize+=INCREMENT;}q=&(L.elem[i-1]);//q为插入位置,C语言数组下标从0开始

for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;*q=x;L.length++; returnOK;}//ListInsert_sq①判定输入是否合法②判定空间是否够用③修改顺序表的参数④移动元素并插入，可改用数组下标实现112.2线性表的顺序表示和实现顺序表上插入运算效率分析：

时间复杂度 从算法流程上看，查找插入位置、插入元素的时间消耗是常数级，算法执行时间主要消耗在插入前元素的移动上，而移动元素的个数与插入位置i有关。

最好情况:在表尾插入，不移动元素，T(n)=O(1)最坏情况:在表头插入，移动n个元素，T(n)=O(n)平均复杂度 设pi为在第i个元素之前插入一个元素的概率，且P1=P2=…=Pi=…=Pn=1/(n+1)，则平均移动次数为： 即T(n)=O(n)

。空间复杂度不需要额外空间，S(n)=O(1)。122.2线性表的顺序表示和实现线性表上的基本运算删除 含义： 将元素ai从线性表：(a1,a2,…,ai-1,ai,ai＋1,…,an)中删除，构成新的线性表(a1,a2,…,ai-1,ai＋1,…,an)，删除后不破坏原线性关系。表的长度为n-1将元素ai删除之后，ai-1的直接后继和ai＋1

的直接前驱就改变了，需要在顺序表的存储结构上反映出来。132.2线性表的顺序表示和实现顺序表上删除运算的实现:a1a2...ai-1an...aiai+1a1a2...ai-1an...ai+1anStatusListDelete_Sq(SqList&L,inti,ElemType&e){第一步：判断参数是否合法合理，否则出错；第二步：在物理空间中找到删除位置；第三步：删除(将后续元素位置依次前移)；第四步：删除后的善后工作(修改表长)}//ListDelete_Sq请同学们课后自学顺序表的删除算法及复杂度分析。14内容回顾线性表的逻辑定义元素的一个有限序列元素之间满足线性关系线性表的抽象数据类型定义ADTList{

数据对象：D={ai

|ai

ElemSet,i=1,2,…n,n0}

数据关系：R={<ai-1,ai>|ai-1,aiD,i=1,2,…n}

基本运算：……}ADTList线性表的顺序存储－－顺序表a1…a1a2...aian...…a2aian15内容回顾顺序表的优缺点优点：不需要额外的存储空间来表示元素间的逻辑关系可以随机地存取表中的任意一个元素缺点：插入和删除元素时要移动大量的元素必须事先进行空间分配，表的容量难以扩充(新算法已解决)顺序表的基本运算的复杂度插入T(n)=O(n)，S(n)=O(1)删除T(n)=O(n)，S(n)=O(1)16内容回顾用类C语言实现顺序表的插入StatusListInsert_sq(Sqlist&L,inti,ElemTypex){if(i<1||i>L.length+1)returnERROR;if(L.length>=L.Listsize){

newbase=(ElemType*)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);

L.elem=newbase;

L.listsize+=INCREMENT;}q=&(L.elem[i-1]);//q为插入位置,C语言数组下标从0开始for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;*q=x;L.length++; returnOK;}//ListInsert_sq类C语言书写的算法与C程序之间的差别：(1)算法中除形式参数外,变量不作定义，在C程序中必须定义；(2)算法中使用的元素类型(ElemType)没有定义，C程序中必须定义，常量OK、ERROR、OVERFLOW等在第一章统一定义；(3)算法中的比较运算符(equal、less)未作定义，C程序中必须定义；(4)必要的头文件(用作输入输出的stdio.h及内存申请的stdlib.h)，在C程序中必须包含。172.3线性表的链式表示和实现线性表的链式存储思路a1a2...aian...存储结构……a1a2aian逻辑结构实现方式对每一个元素的存储单位进行扩充，在包含元素值存储的同时，在结点中存储与当前元素有直接关系的其他元素(直接前趋／直接后继)存储单位的地址(指针)。链式存储单位结构示意图：ai

ai

182.3线性表的链式表示和实现链表---线性表的链式存储内涵： 线性表的链式存储指用任意的存储单元存放线性表中的元素，每个元素与其直接前驱和（或）直接后继之间的关系用指针来存储。这称为链表。术语结点：数据元素及与其有直接关系的元素的地址构成的存储单位。数据域指针域datanext（a）链表结点结构示意图datapriornextdata（b）（c）nextdata（d）prior192.3.1单链表的表示和实现单链表 链表中，如果每个结点中只包含一个指针域，则称之为线性链表或单链表。单链表的存储： 每个结点存储当前元素的直接后继。 线性表(a1,a2,…,ai-1,ai,ai＋1,…,an)

逻辑结构………………110ai135………………130a2143135ai+1180………………160anNull165a1130170ai-1110………………单链表示意图a1

a2

ai-1

…ai

ai+1

an^…Head单链表的内存镜像指向单链表中第一个结点的头指针可惟一确定一个单链表。Head165202.3.1单链表的表示和实现单链表的C语言实现//----------用结构指针描述------------typedef

struct

LNode{

ElemTypedata; //数据域

struct

LNode*next; //指针域}LNode,*LinkList;与之对应的结点结构示意图单链表构建示意图(表头插入法)Headpan^a1

Headppan-1pHead…ai

…ai

LinkList212.3.1单链表的表示和实现带头结点的单链表单链表示意图a1

a2

ai-1

…ai

ai+1

an^…Head

头结点除指针域外可以存储链表的其他信息，如链表的长度、链表的说明等信息，也可以不存储任何信息。带头结点的空链表Head

^头结点222.3.1单链表的表示和实现单链表上的查找运算在单链表中，必须从头指针出发进行查找：查找第i个元素查找指定的元素是否在表中...若找到，则返回该元素的值，否则返回ERROR。在单链表上查找第i个元素的示意图pk=1单链表查找示意图a1

a2

…ai

an^…Head

232.3.1单链表的表示和实现单链表上的查找运算在单链表中，必须从头指针出发进行查找：查找第i个元素查找指定的元素是否在表中...若找到，则返回该元素的值，否则返回ERROR。在单链表上查找第i个元素的示意图pk=2单链表查找示意图a1

a2

…ai

an^…Head

242.3.1单链表的表示和实现单链表上的查找运算在单链表中，必须从头指针出发进行查找：查找第i个元素查找指定的元素是否在表中...若找到，则返回该元素的值，否则返回ERROR。在单链表上查找第i个元素的示意图pk=i单链表查找示意图a1

a2

…ai

an^…Head

找到，返回P指向的结点的数据。问题：i<0或i>n呢？252.3.1单链表的表示和实现用类C语言实现单链表上的查询(查找第i个元素)：StatusGetElem_L(LinkListL,inti,ElemType&e){//L是带头结点的单链表的头指针//当第i个元素存在时，将该元素的值赋给e并返回OK，否则返回ERRORp=L->next;k=1;//初始化，p指向第一个结点，k为计数器while(p&&k<i){//顺指针向后查找，直到p指向第i个元素或p为空

p=p->next;++k;} //循环的退出条件为k=i或到达单链表结尾(P为空)if(!p||k>i)returnERROR;//第i个元素不存在e=p->data;returnOK;}//GetElem_L思考:①本算法为何没有考虑i值的合法性？

②查找指定元素是否在表中如何实现？

③查找算法的复杂度？a1

a2

…ai

an^…L

262.3.1单链表的表示和实现单链表上的插入运算(第i个位置上插入新的结点)逻辑运算(a1,a2,…,ai-1,ai,ai+1,…,an)(a1,a2,…,ai-1,e,ai,ai+1,…,an)在元素ai之前插入一个新元素e单链表上的实现示意图……a1

ai

an^L

ai-1

ai+1

基本步骤：①找到第i-1个元素所在结点；②申请一个新结点s并填入e值；③

修改s的指针域指向p的下一结点；p①es②③272.3.1单链表的表示和实现单链表上的插入运算(第i个位置上插入新的结点)逻辑运算(a1,a2,…,ai-1,ai,ai+1,…,an)(a1,a2,…,ai-1,e,ai,ai+1,…,an)在元素ai之前插入一个新元素e单链表上的实现示意图基本步骤：①找到第i-1个元素所在结点；p②申请一个结点s并填入e值；e③

修改s的指针域指向p的下一结点；s④修改p的指针域指向s。①②③思考：第③④步是否可交换？……a1

ai

an^L

ai-1

ai+1

④282.3.1单链表的表示和实现插入的类C语言实现StatusListInsert_L(LinkList&L,inti,ElemTypee){

//在带头结点的单链表L中第i个位置之前插入元素e

p=L;k=0;//初始化，p指向头结点，k为计数器

while(p&&k<i-1){//逐步移动指针p，直到p指向第i-1个元素或p为空

p=p->next;++k;}//①if(!p||k>i-1)returnERROR;//无法插入

if(!(s=(LinkLinst)malloc(sizeof(LNode))))//申请元素e的结点空间

returnOVERFLOW;

//内存无空闲单元，无法申请到空间

s->data=e;

//②

s->next=p->next;

//③插入元素e的结点

p->next=s; //④returnOK;}//LinstInsert_L复杂度：

①查找：T1(n)=O(n)

②插入：T2(n)=O(1)

T(n)=O(n)a1

a2

…ai

an^…L

292.3.1单链表的表示和实现单链表上的删除运算(把第i个位置的结点删除)逻辑运算(a1,a2,…,ai-1,ai,ai+1,…,an)(a1,a2,…,ai-1,ai+1,…,an)删除结点ai单链表上的实现示意图a1

…ai

an^…L

ai-1

ai+1

基本步骤：①找到第i-1个元素所在结点；p①②增设临时指针q指向p的下一结点(待删除的结点)；q②302.3.1单链表的表示和实现单链表上的删除运算(把第i个位置的结点删除)逻辑运算(a1,a2,…,ai-1,ai,ai+1,…,an)(a1,a2,…,ai-1,ai+1,…,an)删除结点ai单链表上的实现示意图基本步骤：①找到第i-1个元素所在结点；③

修改结点p的指针域，指向第i-1个结点(p->next=p->next->next)；②增设临时指针q指向p的下一结点(待删除的结点)；④

删除结点q，释放内存空间。a1

…ai

an^…L

ai-1

ai+1

③p①q②312.3.1单链表的表示和实现单链表上的删除运算(把第i个位置的结点删除)逻辑运算(a1,a2,…,ai-1,ai,ai+1,…,an)(a1,a2,…,ai-1,ai+1,…,an)删除结点ai单链表上的实现示意图基本步骤：①找到第i-1个元素所在结点；③

修改结点p的指针域，指向第i-1个结点(p->next=p->next->next)；②增设临时指针q指向p的下一结点(待删除的结点)；④

删除结点q，释放内存空间。p①③④a1

…ai

an^…L

ai-1

ai+1

q②322.3.1单链表的表示和实现StatusListDelete_L(LinkList&L,inti,ElemType&e){//在带头结点的单链表L中，删除第i个元素，并由e返回其值

p=L;k=0;//初始化，p指向头结点，k为计数器

while(p->next&&k<i-1){

//逐一移动指针p，直到p指向第i-1个元素或p为空

p=p->next;++k;}if(!p->next||j>i-1)returnERROR;//无法删除

q=p->next;

//* 令q指向待删除的元素结点；

p->next=q->next;//*e=q->data;free(q);returnOK;}//ListDelete_L删除的类C语言实现思考：①

while语句中的p->next可否用p替代？

②用*注释的两条语句可否位置交换？

③本算法的T(n)和S(n)?a1

…ai

an^…L

ai-1

ai+1

pq332.3.1单链表的表示和实现链表的优缺点优点：插入、删除时无须移动元素，只需修改指针根据需要申请存储空间，且不要求连续的存储空间缺点：对表中的元素只能进行顺序访问用指针指示元素之间的逻辑关系（直接前驱、后继），存储空间利用率低自学内容：单链表的表头插入构造算法(算法2.11)34内容回顾链表－－线性表的链式存储……a1a2aian逻辑结构单链表示意图a1

a2

ai-1

…ai

ai+1

an^…Heada1

a2

…ai

an^…Head

带头结点的单链表示意图35内容回顾单链表上的查找运算(查找第i个元素)a1

a2

…ai

an^…Head

计数器kpk=2pk=i查找失败的情形：(1)i<=0：此时k>i(2)i>n：此时p==NULLp(初始化)k=1计数器k找到，返回P指向的结点的数据。36内容回顾单链表上的插入运算(在第i个元素前插入新的元素)p①es②a1

…ai

an^…L

ai-1

ai+1

③②s=(LinkLinst)malloc(sizeof(LNode))基本操作对应语句：

①

p=L;k=0;

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

s->next=p->next;④

p->next=s;④37内容回顾单链表上的删除运算(删除第i个元素)③p①q②基本操作对应语句：

①

p=L;k=0;

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

③

p->next=q->next;

④

e=q->data;free(q);

特别注意：修改指针的语句次序一定要小心处理，否则会出现意想不到的错误。a1

…ai

an^…L

ai-1

ai+1

ai

④382.3.1单链表的表示和实现用表头插入法建立带头结点的单链表基本步骤： (1)建立头结点；L=(LinkList)malloc(sizeof(LNode));L->next=NULL;an

…a2

L^a1 (2)建立新结点p，填入元素；p=(LinkList)malloc(sizeof(LNode));P->data=ai (3)将新结点p插入到头结点之后，修改头结点指针域指向p；p->next=L->next;L->next=p;

^ (4)重复(2)(3)步直到插入所有结点，结束。注：表头插入法建立的链表是输入元素序列的逆序！392.3.1单链表的表示和实现用类C语言实现表头插入算法：an

an-1

…ai

a1^…Head

voidCreateList_L(LinkLinst&L,intn){ //用表头插入法逆序建立带头结点的单链表

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;//新结点插入到表头 }}算法复杂度：T(n)=O(n),S(n)=O(1)402.3.1单链表的表示和实现用C语言实现表头插入算法：

LinkList

CreateList_LH(intn){

inti;//声明本函数的内部变量类型

LinkListhead;//head为指向链表的指针类型

LNode*p; //p为指向结点的指针类型 head=NULL;for(i=n;i>0;--i){//从后向前输入元素p=(LNode*)malloc(sizeof(LNode));//未做溢出判定，应加

scanf(“%d”,&p–>data);//将键盘输入置入p的数据域p–>next=head;head=p;}return(head);//返回指向链表的头指针}//-------用结构指针描述---------typedef

struct

LNode{

ElemTypedata; //数据域

struct

LNode*next;//指针域}LNode,*LinkList;412.3.1单链表的表示和实现用表尾插入法建立带头结点的单链表基本步骤： (1)建立头结点，并附设一个指针r一直指向最后一个结点；

L=(LinkList)malloc(sizeof(LNode));L.next=NULL;r=L;L^ (2)申请一个新的结点空间，存入元素值；

p=(LinkList)malloc(sizeof(LNode)); p->data=ai;p->next=NULL; (3)将新结点插入链表尾部，r指向最后结点；a1^rrra2^r…an^rr

r->next=p;r=p; (4)重复(2)(3)直到最后一个结点，结束。r作业：用类C语言写出该算法。是否每次申请结点都要给其指针域赋空值？422.3.1单链表的表示和实现用表尾插入法建立不带头结点的单链表基本步骤： (1)初始化头指针Head和指向最后结点的指针r；

head=NULL;r=NULL; (2)申请一个新的结点并令p指向该结点，存入元素值； (3)将新结点插入到表尾； r->next=p;r=p;?

①当r指向非空结点时使用上面的语句

②当r指向空地址时head=p;r=p; (4)重复(2)(3)直到最后一个结点，结束。L^ra1

Lra2

rr…an

rr^注:表尾插入法建立的链表与输入元素顺序一致！432.3.1单链表的表示和实现用表尾插入法建立不带头结点的单链表(元素为字符，C语言)：LinkList

CreateList_LT(

){charch;LinkListhead;

LNode*p,*r;//p指向新申请的结点，r指向链表的尾结点head=NULL;r=NULL;

while((ch=getchar()!=‘\n’){p=(LNode*)malloc(sizeof(LNode));if(!p)returnNULL;p–>data=ch;

if(head==

NULL) //插入第一个结点 head=p;else

r–>next=p; //插入第二个及以后的结点r=p;}if(r!=NULL)r–>next=NULL;return(head);}442.3.1单链表的表示和实现说明：

第一个生成的结点(开始结点)要插入到链表尾部，此时指向最后一个结点的指针r指向的是空地址，插入时需要修改的是指针变量r，而随后插入其余结点时，指向最后一个结点的指针r指向的是一个存在的结点，插入时需要修改该结点的指针域r->next。故在算法中应加以区分。 对于表尾插入法，因为随后的插入要修改前一结点的指针域，故可以在申请结点后不处理指针域，而在结束前对尾结点指针域赋空值。452.3.1单链表的表示和实现说明：

如果我们在链表的开始结点之前附加一个头结点，那么会带来以下两个优点：a.由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上的操作一致，无需进行特殊处理；b.无论链表是否为空，其头指针是指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。462.3.1单链表的表示和实现两个有序单链表的合并(Lc=La∪Lb)La

9

14

15

2740^Lb

7

14

20

^Lc

7

9

14

141520

2740^处理思路：(1)设置三个指针pa、pb、pc分别指向La、Lb、Lc的当前结点；(2)比较pa、pb所指结点的元素值大小，将元素值小的结点链接到pc所指结点之后；(3)重复(2)，直到pa、pb中某一指针为空，将另一非空指针链追加到pc之后，算法结束。472.3.1单链表的表示和实现用类C语言实现归并算法：voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){//归并两个非递减单链表La、Lb到Lc中，且使Lc非递减

pa=La->next;pb=Lb->next;

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; } }//while pc->next=pa?pa:pb; free(Lb);}//MergeList_L算法复杂度：?T(n)=O(na)+O(nb)＝O(nLa+nLb)482.3.2循环单链表和双向链表循环单链表

线性表：(a1，a2，…，ai，…，an)taila2a1anan-1…(a)循环单链表带尾指针的循环单链表的特点：通过表尾指针可以一步得到表头指针；对于简单的两个表的合并可以通过简单操作完成(T(n)=O(1))；492.3.2循环单链表和双向链表循环单链表的合并tailbb2b1bmbn-1…(b)循环单链表Lbtailaa2a1anan-1…(a)循环单链表La502.3.2循环单链表和双向链表tailbb2b1bmbn-1…(b)循环单链表Lb…tailaa2a1anan-1(a)循环单链表La循环单链表的合并pa①②512.3.2循环单链表和双向链表tailbb2b1bmbn-1…(b)循环单链表Lb…tailaa2a1anan-1(a)循环单链表La循环单链表的合并pa①②③522.3.2循环单链表和双向链表tailbb2b1bmbn-1…(b)循环单链表Lba2a1anan-1…循环单链表的合并②③(a)循环单链表La53内容回顾单链表的建立方法表头插入法建立单链表建立的链表是元素输入次序的逆序表尾插入法建立单链表建立的链表与元素输入次序一致带头结点的单链表的优点 使得指向链表的起始结点(第一个元素所在的结点)的指针与指向其它元素结点的指针形式上相同(都是存储在前一结点的指针域里)，而可以在算法上一致处理。 与此对应，在不带头结点的单链表上，指向起始结点的指针是一个指针变量，而指向其他结点的指针是前一结点结构的指针域，因此在遍历、插入、删除等操作时必须特殊处理起始结点。循环单链表的优点 使得对链表的某些操作简化542.3.2循环单链表和双向链表双向链表的结点结构：Datanextprior双向链表的C语言描述：typedef

struct

DuLNode{

ElemTypedata;

struct

DuLNode*prior;

struct

DuLNode*next;}DuLNode,*DulinkList;双向链表

线性表：(a1，a2，…，ai，…，an)heada1∧a2an-1anai…∧双向链表示意图…55head∧ai-1ai+1anai…∧…a12.3.2循环单链表和双向链表双向链表上的插入操作(将元素e插入到链表的第i个结点前)基本步骤：(1)定位指针p指向结点ai-1;pe

s(2)建立新结点s并赋e;(3)修改s的next指针域指向p下一结点：s->next=p->next;(5)修改p的next指针域指向s结点：p->next=s;(6)修改s下一结点的prior指针域指向s：s->next->prior=s;(4)修改s的prior指针域指向p结点：s->prior=p;问题：①修改指针的步骤是否可随意？②不带头结点？562.3.2循环单链表和双向链表双向链表上的删除操作(删除第i个结点)head

∧ai-1ai+1anai…∧…a1∧基本步骤：(1)定位指针p指向结点ai;p(2)修改p的前一结点的next指针域指向p下一结点：p->prior->next=p->next;(3)修改p的下一结点的prior指针域指向p前一结点：p->next->prior=p->prior;(3)释放结点p。572.3.2循环单链表和双向链表双向链表上的删除操作(删除第i个结点)p基本步骤：(1)定位指针p指向结点ai;(2)修改p的前一结点的next指针域指向p下一结点：p->prior->next=p->next;(3)修改p的下一结点的prior指针域指向p前一结点：p->next->prior=p->prior;(4)释放结点p。head

∧ai-1ai+1an…∧…a1∧582.3.2循环单链表和双向链表双向循环链表

head带头结点的空双向循环链表head

^a1an-1anai…^…带头结点的非空双向循环链表592.4一元多项式的表示及相加一元多项式的形式：A(x)=p0+p1x+p2x2+…+pixi+…+pnxn存储形式(a)顺序存储pip0p1...p2pn...pi……Head

(b)单链表方式存储pip0

p1

pi

pn^问题：各存储方式的优缺点和使用场合？

Head(c)单链表方式存储pi和ip1

1p5

5…pi

i…pn^n602.4一元多项式的表示及相加例A(x)=7+3x+9x8+

5x17-8x100B(x)=8x+22x7-9x8C(x)=A(x)+B(x)=7+11x+22x7+5x17-8x100存储方式的选择－－以单链表存储多项式系数和指数+headA703198517-8^100headB81227-9^8//-------多项式的项---------typedef

struct{floatcoef; //系数

int

expn;//指数}term,ElemType;//-------多项式结点---------typedef

struct

LNode{

ElemTypedata;//数据域

struct

LNode*next;//指针域}*polynomial;612.4一元多项式的表示及相加一元多项式的相加实现headA703198517-8^100headB81227-9^8headC^qaqbqc//-------多项式结点---------typedef

struct

LNode{

ElemTypedata;//数据域

struct

LNode*next;//指针域}*polynomial;622.4一元多项式的表示及相加一元多项式的相加实现headA703198517-8^100headB81227-9^8headC^qb7^0qcqcqaqa632.4一元多项式的表示及相加一元多项式的相加实现headB81227-9^8qbheadA703198517-8^100qaheadC^7^0qc11^1qaqbqc642.4一元多项式的表示及相加一元多项式的相加实现headA703198517-8^100qaheadB81227-9^8qbheadC^7^011^1qc22^7qbqc652.4一元多项式的表示及相加一元多项式的相加实现headA703198517-8^100qaheadB81227-9^8qbheadC^7^011^122^7qcqaqb662.4一元多项式的表示及相加一元多项式的相加实现headC^7^011^122^7qcheadA703198517-8^100qaheadB81227-9^8qb5^17qaqc672.4一元多项式的表示及相加一元多项式的相加实现headB81227-9^8qbheadA703198517-8^100qaheadC^7^011^122^75^17qc-8^100qaqc682.4一元多项式的表示及相加上机实现提示(1)编写单链表创建算法(函数)；(2)编写多项式加、减法算法；(3)编写多项式表达式的输出算法；(4)编写主函数，两次调用建表函数建立单链表；调用加法函数创建结果链表；调用减法函数创建结果链表；调用输出函数将结果链表转为表达式输出。69约瑟夫环(JosephCircle)问题描述： 编号为1,2,...,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。现在给定一个随机数m>0，从编号为1的人开始，按顺时针方向1开始顺序报数，报到m时停止。报m的人出圈，同时留下他的密码作为新的m值，从他在顺时针方向上的下一个人开始，重新从1开始报数，如此下去，直至所有的人全部出列为止。 请编写程序求出圈的顺序。70约瑟夫环(JosephCircle)例：4596157318213224m：密码k：计数出队序列：startk=1571约瑟夫环(JosephCircle)例：4596157318213224m：密码k：计数出队序列：startk=2572约瑟夫环(JosephCircle)例：4596157318213224m：密码k：计数出队序列：startk=3573约瑟夫环(JosephCircle)例：4596157318213224m：密码k：计数出队序列：startk=4574约瑟夫环(JosephCircle)例：m：密码k：计数出队序列：start4596157318213224k=55存入密码75约瑟夫环(JosephCircle)例：96157318213224m：密码k：计数出队序列：startk=14576约瑟夫环(JosephCircle)例：96157318213224m：密码k：计数出队序列：start5k=4477约瑟夫环(JosephCircle)例：961573113224m：密码k：计数出队序列：start5k=18278约瑟夫环(JosephCircle)例：961573113224m：密码k：计数出队序列：start52k=8879约瑟夫环(JosephCircle)例：1573113224m：密码k：计数出队序列：start52k=19680约瑟夫环(JosephCircle)例：1573113224m：密码k：计数出队序列：start52k=99681约瑟夫环(JosephCircle)例：3113224m：密码k：计数出队序列：start52k=1156782约瑟夫环(JosephCircle)例：3113224m：密码k：计数出队序列：start5267k=151583约瑟夫环(JosephCircle)例：3113m：密码k：计数出队序列：start52674k=12284约瑟夫环(JosephCircle)例：3113m：密码k：计数出队序列：start52674k=222285约瑟夫环(JosephCircle)例：31m：密码k：计数出队序列：start526743k=1186约瑟夫环(JosephCircle)例：m：密码k：计数出队序列：start526743k=13187约瑟夫环(JosephCircle)存储结构4596157318213224tailp需要的变量：k：计数p:指向当前结点pre：指向p的前驱结点上机实现提示：①编写建立循环链表算法②编写结点输出算法(带输入参数k)③编写主程序pre88Joseph问题代码#include<stdio.h>#include<stdlib.h>typedef

structnode{

intcode;/*游戏者的编号*/u