数据结构C语言描述(耿国华)第二章.pptx

《数据结构C语言描述(耿国华)第二章.pptx》由会员分享，可在线阅读，更多相关《数据结构C语言描述(耿国华)第二章.pptx（85页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2023/2/141第2章 线性表 2.1 线性表的概念及运算 2.2 线性表的顺序存储 2.3 线性表的链式存储 2.4 一元多项式的表示及相加第1页/共85页2023/2/1422.1 2.1 线性表的概念及运算线性表的逻辑结构 线性表的抽象数据类型定义 第2页/共85页2023/2/143线性表的定义线性表(Linear List)是由n(n0)个类型相同的数据元素a1,a2,，an组成的有限序列，记做（a1,a2,，ai-1，ai，ai+1，an）。数据元素之间是一对一的关系，即每个数据元素最多有一个直接前驱和一个直接后继。线性表的逻辑结构图为：第3页/共85页2023/2/144线性

2、表的特点同一性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象。有穷性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数。有序性：线性表中相邻数据元素之间存在着序偶关系。第4页/共85页2023/2/145线性表的抽象数据类型定义抽象数据类型定义：ADT LinearList数据元素：D=ai|aiD0,i=1,2,，n n0，D0为某一数据对象 关系：|ai,ai+1D0，i=1,2,n-1 基本操作：（1）InitList（L）操作前提：L为未初始化线性表。操作结果：将L初始化为空表。（2）DestroyList(L)操作前提：线性表L已存在。操作结果：将L销毁。（3）C

3、learList(L)操作前提：线性表L已存在。操作结果：将表L置为空表。ADT LinearList第5页/共85页2023/2/1462.2 2.2 线性表的顺序存储线性表的顺序存储结构 线性表顺序存储结构上的基本运算 第6页/共85页2023/2/147顺序存储结构的定义 线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。采用顺序存储结构的线性表通常称为顺序表。假设线性表中每个元素占k个单元，第一个元素的地址为loc(a1)，则第k个

4、元素的地址为：loc(ai)=loc(a1)+(i-1)k第7页/共85页2023/2/148顺序存储结构示意图存储地址 内存空间状态 逻辑地址 Loc(a1)a11 Loc(a1)+(2-1)k a2 2 loc(a1)+(i-1)k ai i loc(a1)+(n-1)k an n.loc(a1)+(maxlen-1)k 空闲第8页/共85页2023/2/149顺序存储结构的C语言定义#definemaxsize=线性表可能达到的最大长度；typedef struct ElemType elemmaxsize；/*线性表占用的数组空间*/int last；/*记录线性表中最后一个元素在数组

5、elem 中的位置（下标值），空表置为-1*/SeqList；注意区分元素的序号和数组的下标，如a1的序号为1，而其对应的数组下标为0。第9页/共85页2023/2/1410线性表顺序存储结构的基本运算线性表的基本运算：1.查找操作 2.插入操作 3.删除操作4.顺序表合并算法线性表顺序存储结构的优缺点分析第10页/共85页2023/2/1411查找操作线性表的两种基本查找运算1.1.按序号查找GetData(L,i)：要求查找线性表L中第i个数据元素，其结果是L.elemi-1或L-elemi-1。2.2.按内容查找Locate（L,e）:要求查找线性表L中与给定值e相等的数据元素，其结果是

6、：若在表L中找到与e相等的元素，则返回该元素在表中的序号；若找不到，则返回一个“空序号”，如-1。线性表的查找运算算法描述为：第11页/共85页2023/2/1412线性表的查找运算 int Locate(SeqList L，ElemType e)i=0;/*i为扫描计数器，初值为0，即从第一个元素开始比较*/while(i=L.last)&(L.elemi!=e)i+;/*顺序扫描表，直到找到值为key的元素,或扫描到表尾而没找到*/if (i=L.last)return(i);/*若找到值为e的元素，则返回其序号*/else return(-1);/*若没找到，则返回空序号*/第12页/共

7、85页2023/2/1413插入操作 线性表的插入运算是指在表的第i(1in+1)个位置，插入一个新元素e，使长度为n的线性表(e1，ei-1，ei，en)变成长度为n+1的线性表（e1，,ei-1，e e，ei，en）。线性表的插入运算算法。第13页/共85页2023/2/1414插入算法示意图已知：线性表(4,9,15,28,30,30,42,51,62)，需在第4个元素之前插入一个元素“21”。则需要将第9个位置到第4个位置的元素依次后移一个位置，然后将“21”插入到第4个位置，序号移动元素插入元素123456781094915283030425162491528303042625149

8、1521283030426251第14页/共85页2023/2/1415插入运算int InsList(SeqList*L,int i,ElemType e)int k;if(iL-last+2)/*首先判断插入位置是否合法*/printf(“插入位置i值不合法”)；return(ERROR);if(L-last=maxsize-1)printf(“表已满无法插入”)；return(ERROR);for(k=L-last;k=i-1;k-)/*为插入元素而移动位置*/L-elemk+1=L-elemk;L-elemi-1=e;/*在C语言中数组第i个元素的下标为i-1*/L-last+;ret

9、urn(OK);算法演示（此处连接算法演示程序）。第15页/共85页2023/2/1416删除操作 线性表的删除运算是指将表的第i(1in)个元素删去，使长度为n的线性表 (e1，,ei-1，ei，ei+1，en)，变成长度为n-1的线性表(e1，,ei-1，ei+1，en)。算法思路示意 算法实现第16页/共85页2023/2/1417删除算法示意算法示意将线性表(4,9,15,21,28,30,30,42,51,62)中的第5个元素删除。序号123456781094915212830304262514915213030425162删除28后第17页/共85页2023/2/1418删除算法算

10、法 int DelList(SeqList*L,int i,ElemType*e)/*在顺序表L中删除第i个数据元素，并用指针参数e返回其值*/int k;if(iL-last+1)printf(“删除位置不合法！”)；return(ERROR)；*e=L-elemi-1;/*将删除的元素存放到e所指向的变量中*/for(k=i;ilast;k+)L-elemk-1=L-elemk;/*将后面的元素依次前移*/L-last-;return(OK);第18页/共85页2023/2/1419合并算法已知：有两个顺序表LA和LB，其元素均为非递减有序排列，编写一个算法，将它们合并成一个顺序表LC，要

11、求LC也是非递减有序排列。算法思想：设表LC是一个空表，为使LC也是非递减有序排列，可设两个指针i、j分别指向表LA和LB中的元素，若LA.elemiLB.elemj，则当前先将LB.elemj插入到表LC中，若LA.elemiLB.elemj，当前先将LA.elemi插入到表LC中，如此进行下去，直到其中一个表被扫描完毕，然后再将未扫描完的表中剩余的所有元素放到表LC中。算法实现此处连接算法演示 第19页/共85页2023/2/1420顺序表合并算法实现void merge(SeqList*LA,SeqList*LB,SeqList*LC)i=0;j=0;k=0;while(ilast&jl

12、ast)if(LA-elemielemj)LC-elemk=LA-elemi;i+;k+;else LC-elemk=LB-elemj;j+;k+;while(ilast)/*当表LA长则将表LA余下的元素赋给表LC*/LC-elemk=LA-elemi;i+;k+;while(jlast)/*当表LB长则将表LB余下的元素赋给表LC*/LC-elemk=LB-elemj;j+;k+;LC-last=LA-last+LB-last;第20页/共85页2023/2/1421顺序存储结构的优点和缺点优点：1.无需为表示结点间的逻辑关系而增加额外的存储空间；2.可方便地随机存取表中的任一元素。缺点：

13、1.插入或删除运算不方便，除表尾的位置外，在表的其它位置上进行插入或删除操作都必须移动大量的结点，其效率较低；2.由于顺序表要求占用连续的存储空间，存储分配只能预先进行静态分配。因此当表长变化较大时，难以确定合适的存储规模。第21页/共85页2023/2/14222.3 2.3 线性表的链式存储链表定义：采用链式存储结构的线性表称为链表。现在我们从两个角度来讨论链表：1.从实现角度看，链表可分为动态链表和静态链表；2.从链接方式的角度看，链表可分为单链表、循环链表和双链表。第22页/共85页2023/2/1423l单链表 l单链表上的基本运算 l循环链表 l双向链表 l*静态链表 l顺序表和链

14、表的比较链表第23页/共85页2023/2/1424单链表 结点（Node）为了正确地表示结点间的逻辑关系，必须在存储线性表的每个数据元素值的同时，存储指示其后继结点的地址（或位置）信息，这两部分信息组成的存储映象叫做结点（Node）。单链表：链表中的每个结点只有一个指针域，我们将这种链表称为单链表。单链表包括两个域：数据域用来存储结点的值；指针域用来存储数据元素的直接后继的地址（或位置）。头指针：指向链表头结点的指针。第24页/共85页2023/2/1425单链表的示例图头指针H存储地址数据域指针域1 D 437 B 1313 C 119 H NULL25 F 3731 A 737 G 19

15、43 E 2531第25页/共85页2023/2/1426带头结点的单链表示意图有时为了操作的方便，还可以在单链表的第一个结点之前附设一个头结点。带头结点的空单链表 带头结点的单链表 Ha1a2Han 第26页/共85页2023/2/1427单链表的存储结构描述typedef struct Node /*结点类型定义*/ElemType data；struct Node *next；Node,*LinkList；/*LinkList为结构指针类型*/第27页/共85页2023/2/1428单链表上的基本运算线性表的基本运算：1.建立单链表 2.单链表查找 3.单链表插入操作 4.单链表删除 算

16、法应用示例：1.求单链表的长度 2.求两个集合的差 第28页/共85页2023/2/1429建立单链表头插法建表算法描述：从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头结点之后，直至读入结束标志为止。c1 sLL ci-1 c2 c1 ci sc1 第29页/共85页2023/2/1430头插法建表算法Linklist CreateFromHead()LinkList L;Node *s;int flag=1;/*设置一个标志，初值为1，当输入“$”时，flag为0，建表结束*/L=(Linklist)malloc(sizeof(N

17、ode)；/*为头结点分配存储空间*/L-next=NULL;while(flag)c=getchar();if(c!=$)/*为读入的字符分配存储空间*/s=(Node*)malloc(sizeof(Node);s-data=c;s-next=L-next;L-next=s;else flag=0;第30页/共85页2023/2/1431尾插法建表C1 srLc1 rsc2 Lc1 rsL第31页/共85页2023/2/1432尾插法建表算法Linklist CreateFromTail()/*将新增的字符追加到链表的末尾*/LinkList L;Node*r,*s;int flag=1;L

18、=(Node*)malloc(sizeof(Node);/*为头结点分配存储空间*/L-next=NULL;r=L;/*r指针始终动态指向链表的当前表尾*/while(flag)/*标志，初值为1。输入“$”时flag为0，建表结束*/c=getchar();if(c!=$)s=(Node*)malloc(sizeof(Node);s-data=c;r-next=s;r=s else flag=0;r-next=NULL;第32页/共85页2023/2/1433单链表查找按序号查找 算法描述：设带头结点的单链表的长度为n，要查找表中第i个结点，则需要从单链表的头指针L出发，从头结点（L-nex

19、t）开始顺着链域扫描，用指针p指向当前扫描到的结点,初值指向头结点（pL-next），用j做记数器，累计当前扫描过的结点数（初值为0），当j=i 时，指针p所指的结点就是要找的第i个结点。算法实现，算法演示。第33页/共85页2023/2/1434按序号查找算法实现/*在带头结点的单链表L中查找第i个结点，若找到(1in)，则返回该结点的存储位置;否则返回NULL*/Node*Get(LinkList L,int i)Node *p；p=L；j=0；/*从头结点开始扫描*/while(p-next!=NULL)&(jnext；j+；/*扫描下一结点*/*已扫描结点计数器*/if（i=j）ret

20、urn p；/*找到了第i个结点*/else return NULL；/*找不到，i0或in*/第34页/共85页2023/2/1435l按值查找算法描述：按值查找是指在单链表中查找是否有结点值等于e的结点，若有的话，则返回首次找到的其值为e的结点的存储位置，否则返回NULL。查找过程从单链表的头指针指向的头结点出发，顺着链逐个将结点的值和给定值e作比较。算法实现，算法演示。单链表查找第35页/共85页2023/2/1436按值查找算法实现/*在带头结点的单链表L中查找其结点值等于key的结点，若找到则返回该结点的位置p，否则返回NULL*/Node*Locate(LinkList L,Ele

21、mType key)Node*p;p=L-next;/*从表中第一个结点比较*/while(p!=NULL)if(p-data!=key)p=p-next;else break;/*找到结点key，退出循环*/return p;第36页/共85页2023/2/1437单链表插入操作算法描述：要在带头结点的单链表L中第i个数据元素之前插入一个数据元素e，需要首先在单链表中找到第i-1个结点并由指针pre指示，然后申请一个新的结点并由指针s指示，其数据域的值为e，并修改第i-1个结点的指针使其指向s，然后使s结点的指针域指向第i个结点。esa1an ai-1aiespreLa1an preai-1

22、ai第37页/共85页2023/2/1438单链表插入操作算法实现void InsList(LinkList L,int i,ElemType e)/*在带头结点的单链表L中第i个结点之前插入值为e的新结点。*/Node*pre,*s;pre=L;int k=0;while(pre!=NULL&knext;k=k+1;if(k!=i-1)printf(“插入位置不合理！”)；return;s=(Node*)malloc(sizeof(Node);/*为e申请一个新的结点*/s-data=e;/*将待插入结点的值e赋给s的数据域*/s-next=pre-next;pre-next=s;第38页/

23、共85页2023/2/1439单链表删除算法描述：欲在带头结点的单链表L中删除第i个结点，则首先要通过计数方式找到第i-1个结点并使p指向第i-1个结点，而后删除第i个结点并释放结点空间。pa1ai-1aian pa1Lan ai-1aiai+1rL第39页/共85页2023/2/1440单链表删除算法实现void DelList(LinkList L,int i,ElemType*e)/*在带头结点的单链表L中删除第i个元素，并保存其值到变量*e中*/Node*p,*r;p=L;int k=0;while(p-next!=NULL&knext;k=k+1;if(k!=i-1)/*即while

24、循环是因为p-next=NULL而跳出的*/printf(“删除结点的位置i不合理！”);return ERROR;r=p-next;p-next=p-next-next /*删除结点r*/free(r);/*释放被删除的结点所占的内存空间*/第40页/共85页2023/2/1441求单链表的长度算法描述：可以采用“数”结点的方法来求出单链表的长度，用指针p依次指向各个结点,从第一个元素开始“数”，一直“数”到最后一个结点（p-next=NULL）。intListLength(LinkList L)/*L为带头结点的单链表*/Node*p;p=L-next;j=0;/*用来存放单链表的长度*/

25、while(p!=NULL)p=p-next;j+;return j;算法演示链接。第41页/共85页2023/2/1442两个有序单链表的合并有两个单链表LA和LB，其元素均为非递减有序排列，编写一个算法，将它们合并成一个单链表LC，要求LC也是非递减有序排列。要求：利用新表LC利用现有的表LA和LB中的元素结点空间，而不需要额外申请结点空间。例如LA=(2,2,3),LB=(1,3,3,4),则LC=(1,2,2,3,3,3,4)。【算法描述】要求利用现有的表LA和LB中的结点空间来建立新表LC,可通过更改结点的next域来重建新的元素之间的线性关系，为保证新表仍然递增有序，可以利用尾插入

26、法建立单链表的方法，只是新建表中的结点不用malloc，而只需要从表LA和LB中选择合适的点插入到新表LC中即可。第42页/共85页2023/2/1443第43页/共85页2023/2/1444两个有序单链表的合并的算法实现LinkList MergeLinkList(LinkList LA,LinkList LB)/*将递增有序的单链表LA和LB合并成一个递增有序的单链表LC*/Node*pa,*pb;LinkList LC；/*将LC初始置空表。pa和pb分别指向两个单链表LA和LB中的第一个结点,r初值为LC*/pa=LA-next;pb=LB-next;LC=LA;LC-next=NU

27、LL；r=LC;/*初始化操作*/第44页/共85页2023/2/1445两个有序单链表的合并的算法实现（续）/*当两个表中均未处理完时，比较选择将较小值结点插入到新表LC中。*/while(pa!=NULL&pb!=NULL)if(pa-datadata)r-next=pa;r=pa;pa=pa-next;elser-next=pb;r=pb;pb=pb-next;if(pa)/*若表LA未完，将表LA中后续元素链到新表LC表尾*/r-next=pa;else/*否则将表LB中后续元素链到新表LC表尾*/r-next=pb;free(LB);return(LC);/*MergeLinkLis

28、t*/第45页/共85页2023/2/1446循环链表循环链表(Circular Linked List)是一个首尾相接的链表。特点：将单链表最后一个结点的指针域由NULL改为指向头结点或线性表中的第一个结点，就得到了单链形式的循环链表，并称为循环单链表。在循环单链表中，表中所有结点被链在一个环上。带头结点循环单链表示意图。第46页/共85页2023/2/1447带头结点的循环单链表示意图 La1ai-1aian La1ai-1aian rear*(rear-next)*rear空链表带头结点的一般形式 带尾结点的一般形式 第47页/共85页2023/2/1448循环单链表合并为一个循环单链表

29、已知：有两个带头结点的循环单链表LA、LB，编写一个算法，将两个循环单链表合并为一个循环单链表，其头指针为LA。算法思想：先找到两个链表的尾，并分别由指针p、q指向它们，然后将第一个链表的尾与第二个表的第一个结点链接起来，并修改第二个表的尾Q，使它的链域指向第一个表的头结点。第48页/共85页2023/2/1449循环单链表合并算法实现LinkList merge_1(LinkList LA,LinkList LB)/*此算法将两个链表的首尾连接起来*/Node*p,*q;p=LA;q=LB;while(p-next!=LA)p=p-next;/*找到表LA的表尾*/while(q-next!

30、=LB)q=q-next;/*找到表LB的表尾*/q-next=LA;/*修改表LB 的尾指针，使之指向表LA 的头结点*/p-next=LB-next;/*修改表LA的尾指针，使之指向表LB 中的第一个结点*/free(LB);return(LA);第49页/共85页2023/2/1450双向链表 双向链表：在单链表的每个结点里再增加一个指向其前趋的指针域prior。这样形成的链表中就有两条方向不同的链，我们称之为双(向)链表(Double Linked List)。双向链表的结构定义：typedef struct Dnode ElemType data；struct DNode*prior

31、，*next；DNode,*DoubleList；第50页/共85页2023/2/1451双链表的结构定义双链表的结点结构 后继指针域prior data next前驱指针域数据域第51页/共85页2023/2/1452双向循环链表示意图 a1 a2 a3LL空的双向循环链表 非空的双向循环链表 第52页/共85页2023/2/1453双向链表的前插操作算法描述：欲在双向链表第i个结点之前插入一个的新的结点，则指针的变化情况如图所示。es bp a 第53页/共85页2023/2/1454双向链表的前插操作算法实现void DlinkIns(DoubleList L,int i,ElemTyp

32、e e)DNode *s,*p;/*首先检查待插入的位置i是否合法*/*若位置i合法，则让指针p指向它*/s=(DNode*)malloc(sizeof(DNode);if(s)s-data=e;s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;return TRUE;else return FALSE;算法演示连接。第54页/共85页2023/2/1455双向链表的删除操作算法描述：欲删除双向链表中的第i个结点，则指针的变化情况如图所示。a b cp第55页/共85页2023/2/1456双向链表的删除操作算法实现intDlinkDel(Do

33、ubleList L,int i,ElemType*e)DNode *p;/*首先检查待插入的位置i是否合法*/*若位置i合法，则让指针p指向它*/*e=p-data;p-prior-next=p-next;p-next-prior=p-prior;free(p);return TRUE;第56页/共85页2023/2/1457静态链表基本概念：游标实现链表的方法：定义一个较大的结构数组作为备用结点空间（即存储池）。当申请结点时，每个结点应含有两个域：data域和next域。data域存放结点的数据信息，next域为游标指示器，指示后继结点在结构数组中的相对位置（即数组下标）。数组的第0个分量

34、可以设计成表的头结点，头结点的next域指示了表中第一个结点的位置，为0表示静态单链表的结束。我们把这种用游标指示器实现的单链表叫做静态单链表(Static Linked List)。静态链表的结构定义，静态链表的插入和删除操作示例。基本操作：初始化、分配结点与结点回收、前插操作、删除。第57页/共85页2023/2/1458静态链表的结构定义#define Maxsize=链表可能达到的最大长度typedef struct ElemType data;int cursor;Component,StaticListMaxsize;第58页/共85页2023/2/1459静态链表的插入和删除操作

35、示例已知：线性表 a，b，c，d，f，g，h，i），Maxsize=11 0123456789100123456789101a 2b 3c 4d 9f 6g 8h 8i 0e 51a 2b 3c 4d 9f 6g 7h 8i 0e 51a 2b 3c 4d 5f 6g 7h 8i 0012345678910(a)初始化(b)插入e后(c)删除h后 第59页/共85页2023/2/1460静态链表初始化算法描述：初始化操作是指将这个静态单链表初始化为一个备用静态单链表。设space为静态单链表的名字，av为备用单链表的头指针，其算法如下：void initial(StaticList space

36、,int*av)int k;space0-cursor=0;/*设置静态单链表的头指针指向位置0*/for(k=0;kcursor=k+1;/*连链*/spaceMaxsize-1.cursor=0;/*标记链尾*/*av=1;/;/*设置备用链表头指针初值*/第60页/共85页2023/2/1461静态链表分配结点与结点回收分配结点int getnode(int*av)/*从备用链表摘下一个结点空间，分配给待插入静态链表中的元素*/int i=*av;*av=space*av.cur;return i;结点回收void freenode(int*av,int k)/*将下标为 k的空闲结点插

37、入到备用链表*/spacek.cursor=*av;*av=k;第61页/共85页2023/2/14622.4 2.4 一元多项式的表示及相加一元多项式可按升幂的形式写成：Pn(x)=p0+p1xe1+p2xe2+pnxen，其中ei为第i项的指数，pi是指数ei的项的系数，(且1e1e2en)假设Qm(x)是一个一元多项式，则它也可以用一个线性表Q来表示。即：Q=(q0，q1，q2，qm)若假设mcoef=c;s-exp=e;rear-next=s;/*在当前表尾做插入*/rear=s;scanf(“%d,%d”,&c,&e);rear-next=NULL;/*将表的最后一个结点的next置

38、NULL，以示表结束*/return(head);第67页/共85页2023/2/1468一元多项式的单链表表示示意图说明：图示分别为多项式A(x)=7+3x+9x8+5x17B(x)=8x+22x7-9x8-17 03 15 17 9 88 1 -122 7 -9 8 第68页/共85页2023/2/1469两个一元多项式相加运算规则：两个多项式中所有指数相同的项的对应系数相加，若和不为零，则构成“和多项式”中的一项；所有指数不相同的项均复抄到“和多项式”中。算法实现，算法演示若p-expexp，则结点p所指的结点应 是“和多项式”中的一项，令指针p后移；若p-expq-exp，则结点q所指

39、的结点应是“和多项式”中的一项，将结点q插入在结点p之前，且令指针q在原来的链表上后移；若p-exp=q-exp，则将两个结点中的系数相加，当和不为零时修改结点p的系数域，释放q结点；若和为零，则和多项式中无此项，从A中删去p结点，同时释放p和q结点。第69页/共85页2023/2/1470两个多项式相加算法实现void polyadd(Polylist polya;Polylist polyb)/*p和q分别指向polya和polyb链表中的当前计算结点*/*pre指向和多项式链表中的尾结点*/while p!=NULL&q!=NULL）if （p-expexp）/*将p结点加入到和多项式中

40、*/else if(p-exp=q-exp）/*若指数相等，则相应的系数相加。若系数为0则删除p，q节点*/else/*将q结点加入到和多项式中*/./*将多项式polya或polyb中剩余的结点加入到和多项式中*/第70页/共85页2023/2/14712.5 顺序表和链表的比较 1基于空间的考虑 2基于时间的考虑 3基于语言的考虑 第71页/共85页2023/2/1472线性表链式存储方式的比较 操作名称链表名称找表头结点找表尾结点找P结点前驱结点带头结点单链表LL-next时间耗费O(1)一重循环时间耗费O(n)顺P结点的next域无法找到P结点的前驱带头结点循环单链表（头指针）LL-n

41、ext时间耗费O(1)一重循环时间耗费O(n)顺P结点的next域可以找到P结点的前驱时间耗费O(n)带尾指针的循环单链表RR-nextO(1)R时间耗费O(1)顺P结点的next域可以找到P结点的前驱时间耗费O(n)带头结点双向循环链表LL-nextO(1)L-prior时间耗费O(1)P-prior时间耗费O(1)第72页/共85页2023/2/14732.6 总结与提高主要知识点 1、线性表的特征：线性表中每个数据元素有且仅有一个直接前驱和一个直接后继，第一个结点无前驱，最后一个结点无后继。2、线性表存储方式：线性表顺序存储（顺序表）：采用静态分配方式，借助于C语言的数组类型，申请一组连

42、续的地址空间，依次存放表中元素，其逻辑次序隐含在存储顺序之中。第73页/共85页2023/2/14742.6 总结与提高线性表链式存储（链表）：采用动态分配方式，借助于C语言的指针类型，动态申请与动态释放地址空间，故链表中的各结点的物理存储可以是不连续的。当表长度变化时仅需适当变化指针的联接，适合于表中元素个数动态变化。3、单链表的操作特点：顺链操作技术 指针保留技术 4、链表处理中的相关技术第74页/共85页2023/2/1475典型题例 例例1 1：已知顺序表L中的数据元素类型为int。设计算法将其调整为左右两部分，左边的元素（即排在前面的）均为奇数，右边所有元素（即排在后面的）均为偶数，

43、并要求算法的时间复杂度为O(n)，空间复杂度为O（1）。第75页/共85页2023/2/1476例1【问题分析】初见此题，可能会想到额外申请1个顺序表空间，之后依次从顺序表L中选择奇数放入新表前部分，选择偶数放在新表的后半部分。但是题目要求空间复杂度为O(1),很显然上述方法是不可行的。既然要求空间复杂度为O(1)，说明只能借助1个辅助空间。分析题目要求，其实我们只需要将位于表左半部分的偶数与位于表右半部分的奇数通过一个辅助变量进行交换即可，为此我们可以设置两个位置指示器i和j,i初值为0，j初值为L-last,当L-elemi为偶数，L-elemj为奇数时，则将L-elemi 与L-elem

44、j交换；否则，L-elemi为奇数,i+,L-elemj为偶数，j+。这样既可以保证算法的时间复杂度为O(n),亦可保证空间复杂度为O（1）。第76页/共85页2023/2/1477【算法描述】AdjustSqlist(SeqList *L)/*int i=0,j=L-last;while(ielemi%2!=0)i+;/*从表的左半部分开始检测，若为奇数，则i加1,直到找到偶数为止*/while(L-elemj%2=0)j-；/*从表的右半部分开始检测，若为偶数，则j减1,直到找到奇数为止*/if(ielemi;L-elemi=L-elemj;L-elemj=t;/*交换*/*end of

45、AdjustSqlist*/第77页/共85页2023/2/1478例2：算法实现带头结点单链表的就地逆置问题。【问题分析】逆置就是使得表中内容由原来的（a1,a2,，ai-1，ai，ai+1，an）变为（an,an-1,，ai+1，ai，ai-1，a1）。就地逆置就是不需要额外申请结点空间，只需要利用原有的表中的节点空间。若对顺序表中的元素进行逆置，可以借助于“交换”前后相应元素；对单链表中的元素进行逆置，则不能按“交换”思路，因为对于链表中第i个结点需要顺链查找第n-i+1(链表长度为n)个结点，逆置链表的时间复杂度将达O（n2）。第78页/共85页2023/2/1479 算法思路：算法思

46、路：逆置后的单链表初始为空，表中的结点不是新生成的，而是从原链表中依次“删除”，再逐个头插入到逆置表中（类同算法2.5头查法创建链表）。设逆置链表的初态为空表，“删除”已知链表中的第一个结点，然后将它“插入”到逆置链表的“表头”，即使它成为逆置链表中“新”的第一个结点，如此循环，直至原链表为空表止。根据单链表的特点，通过头指针L我们可以顺着每个结点的next域，依次访问到a1,a2,a3an-1,an；2）我们可以借鉴前面讲到过的头插入法建链表的方法，因为头插入法建链表又称为逆序建表法3）唯一不同的是，我们不需要重新申请结点空间，而只需要从原有单链表上依次“摘下”结点，之后插入到单链表头结点和

47、表中第一个结点之间即可。如图所示第79页/共85页2023/2/1480a1an a2ai(a)初始状态Lp为原链表当前处理结点断开L-next,使逆置表初始为空表(b)将单链表L初始为空表a1an a2aiLpqq指向原链表当前处理结点的下一个paia2a1 Lan a3q(c)将p指向的结点插入到逆置表L的表头第80页/共85页2023/2/1481例2【算法描述】void ReverseList(LinkList L)/*逆置带头结点的单链表L*/p=L-next;/*P为原链表的当前处理结点*/L-next=NULL;/*逆置单链表初始为空表*/while(p!=NULL)/*当原链表

48、未处理完*/q=p-next;/*q指针保留原链表当前处理结点的下一个结点*/p-next=L-next;L-next=p;/*将当前处理结点p插入到逆置表L的表头*/p=q;/*p指向下一个待插入的结点*/*end of while*/*end of ReverstList*/【思考】已知一个带头结点的单链表L，设计算法实现：以表中第一个元素作为标准，将单链表中所有值小于第一个元素的结点均放在第一个元素结点之前，所有值大于第一个元素的结点均放在第一个元素结点之后。（提示：此题可以利用头插法）第81页/共85页2023/2/1482例3、建立一个带头结点的线性链表，用以存放输入的二进制数，链表

49、中每个结点的data域存放一个二进制位。并在此链表上实现对二进制数加1的运算。【问题分析问题分析】建链表：带二进制数可用带头结点的单链表存储，第一个结点存储二进制数的最高位，依次存储，最后一个结点存储二进制数的最低位。二进制加法规则：实现二进制数加1运算，方向从低位往高位找到第一个值为0的位，从该位开始，对后面所有低位进行求反运算。链表实现二进制加1时，从高位往低位与运算方向正好相反，从第一个结点开始找，找出最后一个值域为0的结点，把该结点值域赋为1，其后所有结点的值域赋为0。若在链表中未找到值域为0的结点，则表示该二进制数各位均为1，此时，申请一新结点，值域为1，插入到头结点与原链表的第一个

50、结点之间，成为新链表的第一个结点，其后所有结点的值域赋为0。第82页/共85页2023/2/1483【算法描述】void BinAdd(LinkList l)/*用带头结点的单链表L存储二进制数，实现加1运算*/Node*q,*r,*temp,*s;q=l-next;r=l;while(q!=NULL)/*查找最后一个值域为0的结点*/if(q-data=0)r=q;q=q-next;第83页/共85页2023/2/1484if (r!=l)r-data=1;/*将最后一个值域为0的结点的值域赋为1*/else /*未找到值域为0的结点*/temp=r-next;s=(Node*)malloc