数据结构第2章线性表

1、12本本 章章 主主 要要 内内 容容复习复习C语言语言线性表的顺序存储结构线性表的顺序存储结构线性表的链式存储结构线性表的链式存储结构线性表的应用线性表的应用第第2章作业章作业实验实验1实验实验23提问：提问：数据结构研究的三方面？数据结构研究的三方面？接下来从这三方面来介绍线性表，简单介绍逻辑结接下来从这三方面来介绍线性表，简单介绍逻辑结构，重点介绍线性表的两种存储结构和基本运算。构，重点介绍线性表的两种存储结构和基本运算。提问：提问：存储结构有哪两种？存储结构有哪两种？顺序存储结构顺序存储结构用数组实现。用数组实现。链式存储结构链式存储结构用指针实现，动态分配存储空间。用指针实现，动态分

2、配存储空间。如：存储如：存储10个整数。个整数。4如：存储如：存储10个整数。个整数。（1）顺序存储）顺序存储int a10;（2）链式存储）链式存储动态分配空间，用动态分配空间，用malloc函数函数struct node int data; struct node *next;a1a2a3a1a25线性结构的特点：线性结构的特点：“一对一一对一”，“一个接一个的排一个接一个的排列列”线性表的例子：线性表的例子：学生信息表学生信息表一个字符串一个字符串线性表线性表具有相同数据类型的具有相同数据类型的n(n=0)个数据元素个数据元素的有限序列，通常记为：的有限序列，通常记为：(a1，a2， a

3、i-1，ai，ai+1，an)其中其中n为表长，为表长， n0 时称为空表。时称为空表。直接前驱直接前驱直接后继直接后继线性表的逻辑结构线性表的逻辑结构6线性表的基本运算：插入、删除、查找线性表的基本运算：插入、删除、查找线性表按存储结构分类：线性表按存储结构分类：（1）顺序表）顺序表（2）链表）链表72.1 线性表的顺序存储结构线性表的顺序存储结构编程：输入一组整数（以编程：输入一组整数（以-1结束）并输出。结束）并输出。提问：提问：一组整数是线性表吗？一组整数是线性表吗？提问：提问：如何存储一组整数？如何存储一组整数？顺序存储顺序存储（顺序表）（顺序表）链式存储链式存储（链表）（链表）a1

4、a2a3a1a28编程：输入一组整数（以编程：输入一组整数（以-1结束）并输出。结束）并输出。采用顺序存储：采用顺序存储：#define MAXSIZE 100int dataMAXSIZE;void input( ) /输入输入 scanf(“%d”,&x); int i; while(x!=-1) datai=x; i+; scanf(“%d”,&x); void print( ) /输出输出 for(i=0; ? ;i+) printf(“%5d”, datai);编程：输入一组整数（以编程：输入一组整数（以-1结束）并输出。结束）并输出。采用顺序存储：采用顺序存储：#d

5、efine MAXSIZE 100int dataMAXSIZE;void input( ) /输入输入 scanf(“%d”,&x); int i; while(x!=-1) datai=x; i+; scanf(“%d”,&x); void print( ) /输出输出 for(i=0; ? ;i+) printf(“%5d”, datai);2.1 线性表的顺序存储结构线性表的顺序存储结构int last; /存放数据元素的实际个数存放数据元素的实际个数last=i;i last=-1; 2、建立一个顺序表、建立一个顺序表（输入一组整数，存入顺序表（输入一组整数，存入顺序

6、表L中）中）void Create_SeqList(SeqList *L) int i; datatype x; scanf(“%d”,&x); i=0; while(x!=-1) L - datai=x; i+; scanf(“%d”,&x); L - last=i-1; 2.1 线性表的顺序存储结构线性表的顺序存储结构112.1 线性表的顺序存储结构线性表的顺序存储结构3、输出顺序表、输出顺序表（练习）（练习）void Print_SeqList(SeqList L) int i; for(i=0;ilast=MAXSIZE-1) /*判表满判表满*/ printf(“fu

7、lln”);return; if(iL-last+2) /*判判i的合法性的合法性*/ printf(“i is errorn”);return; for(j=L-last;j=i-1;j-) /*将将an至至ai后移后移*/ L-dataj+1=L-dataj; L-datai-1=x; /*插入插入 x */ L-last+; /*表长加表长加1 */132.1 线性表的顺序存储结构线性表的顺序存储结构（2）“插入插入”算法的时间复杂度分析算法的时间复杂度分析 顺序表的顺序表的“插入插入”操作的时间主要耗费在元素操作的时间主要耗费在元素的移动上（即：移动元素是基本操作），那么的移动上（即：

8、移动元素是基本操作），那么T(n)指的就是移动次数。指的就是移动次数。 在第在第i个位置插入需移动个位置插入需移动n-i+1个元素，设插入个元素，设插入概率为概率为Pi，则平均移动次数为：，则平均移动次数为：1n1ii1)i(nPEis nOnTninnEisnPnii112)1(1111则若认为（即等概率情况下）（即等概率情况下）142.1 线性表的顺序存储结构线性表的顺序存储结构T(n)一般又可指最坏情况下的一般又可指最坏情况下的“插入插入”的最坏情况就是：在第的最坏情况就是：在第1个位置上插入，个位置上插入，需移动需移动n个元素，故个元素，故T(n)=O(n)152.1 线性表的顺序存储

9、结构线性表的顺序存储结构5、删除、删除将顺序表将顺序表L的第的第i个元素删除（个元素删除（1in）。）。 将将ai+1 至至an前移；前移； 表长减表长减1。练习：练习：编写顺序表的编写顺序表的“删除删除”算法。算法。void Delete_SeqList(SeqList *L, int i) a1.ai-1aiai+1.an162.1 线性表的顺序存储结构线性表的顺序存储结构（1）“删除删除”算法：算法：教材教材P15【 算法算法2-3】。void Delete_SeqList(SeqList *L, int i) int j; if(L-last=-1) /*判表空判表空*/ printf

10、(“emptyn”);return; if(iL-last+1) /*判判i的合法性的合法性*/ printf(“i is errorn”);return; for(j=i;jlast;j+) /*将将ai+1 至至an前移前移*/ L-dataj-1=L-dataj; L-last-; /*表长减表长减1 */172.1 线性表的顺序存储结构线性表的顺序存储结构（2）“删除删除”算法的时间复杂度分析算法的时间复杂度分析 删除第删除第i个，需移动个，需移动n-i个元素，个元素， 设等概率，则设等概率，则Pi= 1/n， 则平均移动次数为：则平均移动次数为：niideinPE1)( nOnTni

11、nnEnPnidei121)(11则若认为（等概率情况下）（等概率情况下）故在故在顺序表中插入或删除顺序表中插入或删除一个元素时，平均移动一个元素时，平均移动表中的一半元素，当表中的一半元素，当n很大时，很大时，效率很低效率很低。18练习：练习：（1）在一个长度为）在一个长度为n的顺序表的第的顺序表的第i个元素之前插个元素之前插入一个新元素，需后移入一个新元素，需后移_个元素。个元素。（2）将一个长度为）将一个长度为n的顺序表的第的顺序表的第i个元素删除，个元素删除，需移动需移动_个元素。个元素。思考：思考：（1）在一个递增有序的顺序表）在一个递增有序的顺序表 L中插入元素中插入元素x后后仍有

12、序。仍有序。（2）将顺序表）将顺序表 L中的元素逆置。中的元素逆置。 实验实验1：顺序表顺序表2.1 线性表的顺序存储结构线性表的顺序存储结构n-i+1n-i192.1.3 顺序表应用举例顺序表应用举例P17 【例例2-4】将两个递增有序的顺序表将两个递增有序的顺序表A和和B合并合并成一个递增有序的顺序表成一个递增有序的顺序表C。如：如：A=(3,5,8,11) B=(2,6,9,15,20)合并后：合并后：C=(2,3,5,6,8,9,11,15,20)算法思想：算法思想：从第一个元素开始，依次比较从第一个元素开始，依次比较A、B表中相应元素，将较小表中相应元素，将较小者赋给者赋给C表。表。

13、设两个设两个“指针指针”i和和j分别指向分别指向A、B表中某个元素。若表中某个元素。若i所指所指元素元素j所指元素，则将所指元素，则将i所指元素赋给所指元素赋给C，且让，且让i指向指向A下一下一个元素；否则，将个元素；否则，将j所指元素赋给所指元素赋给C，让，让j指向指向B下一个元素。下一个元素。（注意：注意：i, j并非指针变量，而是整型变量，其值为所指元并非指针变量，而是整型变量，其值为所指元素下标，我们只是将其理解成素下标，我们只是将其理解成“指针指针”，故，故i所指元素就是所指元素就是以以i为下标的元素，即为下标的元素，即A.datai）2.1 线性表的顺序存储结构线性表的顺序存储结构

14、20反复执行，直到反复执行，直到A或或B表中的元素全部合并完；表中的元素全部合并完；然后再将另一个表的剩余元素依次赋给然后再将另一个表的剩余元素依次赋给C。算法：算法：教材教材P17void Merge(SeqList a, SeqList b, SeqList *c) int i,j,k; i=j=k=0; 2.1 线性表的顺序存储结构线性表的顺序存储结构while(i=a.last&j=b.last) /*合并合并*/ if(a.dataidatak+=a.datai+; else c-datak+=b.dataj+;while(idatak+=a.datai+;while(jda

15、tak+=b.dataj+;c-last=k-1;21算法的时间复杂度分析：算法的时间复杂度分析： 设设A表有表有m个元素，个元素，B表有表有n个元素，基本操作个元素，基本操作是比较和赋值。是比较和赋值。 每比较一次，就将一个元素赋给每比较一次，就将一个元素赋给C。A、B共有共有m+n个元素，故需赋值个元素，故需赋值m+n次，最多需比较次，最多需比较m+n-1次。次。思考：思考：将两个递增有序的顺序表将两个递增有序的顺序表A、B，归并成一个递减，归并成一个递减有序的顺序表有序的顺序表C。将两个递减有序的顺序表将两个递减有序的顺序表A、B，归并成一个递减，归并成一个递减有序的顺序表有序的顺序表C

16、。将两个递减有序的顺序表将两个递减有序的顺序表A、B，归并成一个递增，归并成一个递增有序的顺序表有序的顺序表C。（从最后一个起，将较小者插入到表尾）（从最后一个起，将较小者插入到表尾）2.1 线性表的顺序存储结构线性表的顺序存储结构（从最后一个起，将较大者插入到表尾）（从最后一个起，将较大者插入到表尾）（从第一个起，将较大者插入到表尾）（从第一个起，将较大者插入到表尾）故故T(n)=O(m+n)22顺序表（顺序存储结构）的优缺点顺序表（顺序存储结构）的优缺点（1）优点）优点逻辑上相邻的元素，物理位置也相邻。逻辑上相邻的元素，物理位置也相邻。可随机访问。可随机访问。（2）缺点）缺点插入、删除操作

17、需要移动大量的元素，效率低。插入、删除操作需要移动大量的元素，效率低。需要预先分配足够大的存储空间。需要预先分配足够大的存储空间。2.1 线性表的顺序存储结构线性表的顺序存储结构问：问：什么情况下适宜采用顺序存储，什么情况下不适宜？什么情况下适宜采用顺序存储，什么情况下不适宜？232.2 线性表的链式存储结构线性表的链式存储结构什么是链式存储？用一组任意的存储单元存储各元什么是链式存储？用一组任意的存储单元存储各元素。为了表示元素间的逻辑关系，需增加指针域来素。为了表示元素间的逻辑关系，需增加指针域来指向其后继或前驱。指向其后继或前驱。链表的每个结点由两部分组成：链表的每个结点由两部分组成：

18、数据域：存放数据元素信息数据域：存放数据元素信息 指针域：存放后继或前驱的地址指针域：存放后继或前驱的地址链表可分为：链表可分为： 单链表：只包含一个指针域单链表：只包含一个指针域next，指向后继，指向后继 双链表：包含两个指针域双链表：包含两个指针域 next指向后继指向后继 prior指向前驱指向前驱数据域数据域指针域指针域24data nextH头结点头结点线性表的链式存储结构线性表的链式存储结构一、单链表一、单链表1、单链表的存储结构、单链表的存储结构每个结点由数据域每个结点由数据域(data)和一个指针域和一个指针域(next)构成；构成；最后一个结点的指针为空最后一个结点的指针为

19、空(NULL)；设一个设一个 头指针头指针H指向第一个结点；指向第一个结点；为方便对第一个结点和其他结点进行统一处理，通常在第为方便对第一个结点和其他结点进行统一处理，通常在第一个结点之前附设一个结点，称为一个结点之前附设一个结点，称为头结点头结点。 如：如：L=(a1，a2， ，an) 单链表形式：单链表形式：a1a2andata nextHa2ana1思考：思考：一个带头结点的单链表一个带头结点的单链表L为空为空表的条件：表的条件：一个不带头结点的单链表一个不带头结点的单链表L为为空表的条件：空表的条件：L-next=NULLL=NULL25线性表的链式存储结构线性表的链式存储结构要访问单

20、链表中任一个元素必须从头指针出发，故要访问单链表中任一个元素必须从头指针出发，故单链表是单链表是“顺序存取顺序存取”。单链表可由头指针唯一确定单链表可由头指针唯一确定（也就是说，一个单链表（也就是说，一个单链表可简单理解成是一个头指针，而头指针是结点指针，故单可简单理解成是一个头指针，而头指针是结点指针，故单链表类型是结点指针类型）链表类型是结点指针类型）。单链表结点类型及单链表类型的定义单链表结点类型及单链表类型的定义 struct node datatype data; struct node *next; /*next是指向结构体本身的指针是指向结构体本身的指针*/ typedef LN

21、ode, * LinkList;26线性表的链式存储结构线性表的链式存储结构LinkList H； /*定义了一个头指针为定义了一个头指针为H的单链表的单链表*/第第1个结点的数据域为个结点的数据域为 ，指针域为，指针域为设设p指向第指向第i个结点个结点ai，则，则p-next指向？指向？p-data表示？表示？p-next-data表示？表示？第第2个结点的数据域为个结点的数据域为 ，指针域为，指针域为H为空表的条件：为空表的条件：a1a2aiai+1anPHH-dataH-nextH-next-dataH-next-nextH=NULL27线性表的链式存储结构线性表的链式存储结构2、单链表

22、（带头结点）的基本操作、单链表（带头结点）的基本操作建立、输出、求表长、查找、插入、删除。建立、输出、求表长、查找、插入、删除。（1）建立单链表）建立单链表基本思路：先建立一个空表，再将各元素结点逐个基本思路：先建立一个空表，再将各元素结点逐个插入到表中。插入到表中。三种方法：尾插法三种方法：尾插法 头插法头插法 按条件插入按条件插入注意：注意：教材教材P19算法算法2-5和算法和算法2-6分别是采用分别是采用头插法和尾插法建立一个头插法和尾插法建立一个不带头结点不带头结点的单链表。接的单链表。接下来介绍的操作都是对带头结点的单链表。下来介绍的操作都是对带头结点的单链表。28线性表的链式存储结

23、构线性表的链式存储结构xsp（1）先申请一个结点，将）先申请一个结点，将x存入，用指针存入，用指针S指向指向 s=(LNode *)malloc(sizeof(LNode); s-data=x;（2）插入（修改指针）插入（修改指针） s-next=p-next; p-next=s;注：注：这两句顺序不能交换。这两句顺序不能交换。如：在一个单链表的如：在一个单链表的p所指结点之后插入一个新元素所指结点之后插入一个新元素x。29尾插法：将各元素结点逐个插入到表尾。尾插法：将各元素结点逐个插入到表尾。设头指针设头指针L，设指针，设指针r指向当前表尾结点。指向当前表尾结点。)建立一个空表。建立一个空表

24、。L=(LNode *)malloc(sizeof(LNode);L-next=NULL; r=L;线性表的链式存储结构线性表的链式存储结构rL30输入一个数输入一个数x1申请一个结点申请一个结点s=(LNode *)malloc(sizeof(LNode);s-data=x1; 插入到表尾插入到表尾r-next=s; r=s;)将各元素结点插入到表尾。将各元素结点插入到表尾。x1sr线性表的链式存储结构线性表的链式存储结构rLx1x2srrL31)将最后一个结点的将最后一个结点的next域置空。域置空。x1xnr-next=NULL;线性表的链式存储结构线性表的链式存储结构rL【例例】定义一

25、个函数：输入一组正整数，以定义一个函数：输入一组正整数，以-1标志标志结束，将这些正整数作为结束，将这些正整数作为data域建立一个单链表。域建立一个单链表。32LinkList Create_LinkList( ) /*尾插法尾插法*/ LinkList L; LNode *r,*s; int x; L=(LNode *)malloc(sizeof(LNode); L-next=NULL; r=L; /*建立空表建立空表L*/ scanf(“%d”, &x); while(x!=-1) s=(LNode *)malloc(sizeof(LNode); /*申请一个结点申请一个结点*/

26、 s-data=x; r-next=s; /*插入插入*/ r=s; scanf(“%d”, &x); r-next=NULL; /*将最后一个结点的将最后一个结点的next域置空域置空*/ return L;线性表的链式存储结构线性表的链式存储结构33线性表的链式存储结构线性表的链式存储结构34线性表的链式存储结构线性表的链式存储结构35头插法头插法（练习）（练习）将各元素结点逐个插入到表头。将各元素结点逐个插入到表头。注意：注意：输入元素的顺序与生成的单链表中各元素的输入元素的顺序与生成的单链表中各元素的顺序正好相反。顺序正好相反。线性表的链式存储结构线性表的链式存储结构36Lin

27、kList Create_LinkList( ) /*头插法头插法*/ LinkList L; LNode *s; int x; L=(LNode *)malloc(sizeof(LNode); L-next=NULL; /*建立空表建立空表L*/ scanf(“%d”, &x); while(x!=-1) s=(LNode *)malloc(sizeof(LNode); /*申请一个结点申请一个结点*/ s-data=x; s-next=L-next; L-next=s; /*插入插入*/ scanf(“%d”, &x); return L;线性表的链式存储结构线性表的链式存

28、储结构37while( ) p=p-next; printf(“%8d”, p-data);（2）输出单链表）输出单链表算法：算法：void Print_LinkList(LinkList L) LNode *p; p=L; 线性表的链式存储结构线性表的链式存储结构p-next!=NULL38while( ) p=p-next; n+;（3）求表长）求表长（练习）（练习）算法：算法：教材教材P21【算法算法2-6】int Length_LinkList(LinkList L) LNode *p; int n; p=L; n=0; return(n);线性表的链式存储结构线性表的链式存储结构p-

29、next!=NULL39（4）查找）查找按序号查找按序号查找查找第查找第i个元素个元素Get_LinkList(L,i)按值查找按值查找查找其值等于查找其值等于x的元素的元素Locate_LinkList(L,x)线性表的链式存储结构线性表的链式存储结构a1aianPLPj=0j+j=i结束结束P结束结束a1anPLx=x结束结束P结束结束P查找算法的时间复杂度为查找算法的时间复杂度为O(n)40LNode *Get_LinkList (LinkList L, int i) LNode *p;int j;p=L;j=0;while(jnext!=NULL)p=p-next;j+;if(jnex

30、t;while(p!=NULL&p-data!=x) /两个循环条件的顺序不能交换两个循环条件的顺序不能交换p=p-next;return p;线性表的链式存储结构线性表的链式存储结构42线性表的链式存储结构线性表的链式存储结构（5）插入）插入 在在*p后插入后插入*s设设p指向单链表中某结点，指向单链表中某结点，s指向待插入的值为指向待插入的值为x的新的新结点，将结点，将*s插入到插入到*p的后面，插入操作如下图所示。的后面，插入操作如下图所示。注意：两个指针的操作顺序不能交换。注意：两个指针的操作顺序不能交换。sps-next=p-next;p-next=s;43线性表的链式存储结

31、构线性表的链式存储结构在在*p前插入前插入*s先找先找*p的前驱的前驱*q，再插入。，再插入。sqp设单链表头指针为设单链表头指针为L，操作如下：，操作如下：q=L;while ( ) q=q-next; /*找找*p的直接前驱的直接前驱*/s-next=q-next; q-next=s;q-next!=p后插操作的后插操作的时间复杂性时间复杂性为为O(1)，前，前插操作因为插操作因为要找要找 *p 的前的前驱，时间性驱，时间性能为能为O(n)。44【例例】编写算法：在单链表编写算法：在单链表L的第的第i个位置上插入个位置上插入元素元素x。线性表的链式存储结构线性表的链式存储结构a1aiai-

32、1anPLsx算法思路：算法思路：(1) 找到第找到第i-1个结点；若存在继续个结点；若存在继续(2)，否则结束，否则结束(2) 申请、填装新结点；申请、填装新结点；(3) 将新结点插入。结束。将新结点插入。结束。“插入插入”操作的时间主要耗费在查找第操作的时间主要耗费在查找第i-1个结点上，个结点上，故故T(n)=O(n)。45void Insert_LinkList(LinkList L, int i, datatype x ) LNode *p,*s; p=Get_LinkList(L, i-1); /查找第查找第i-1个结点个结点 if(p=NULL) /第第i-1个结点不存在个结点不

33、存在 printf(“ i is errorn”); return; s=(LNode *)malloc(sizeof(LNode); /申请、填装结点申请、填装结点 s-data=x; s-next=p-next; p-next=s; /将新结点插入将新结点插入线性表的链式存储结构线性表的链式存储结构46（6）删除）删除（练习）（练习）删除删除*p的后继的后继q=p-next; p-next=q-next; free(q);该操作的时间复杂性为该操作的时间复杂性为O(1)。删除删除*p 先找到先找到*p的前驱的前驱*q，再删除。，再删除。显然找显然找*p前驱的时间复杂性为前驱的时间复杂性为O

34、(n)。删除运算：删除运算：Delete_LinkList( L, i )算法思路：算法思路：(1) 找到第找到第i-1个结点；若存在继续个结点；若存在继续(2)，否则结束；，否则结束；(2) 若存在第若存在第i个结点则继续个结点则继续(3)，否则结束；，否则结束；(3) 删除第删除第i个结点，结束。个结点，结束。线性表的链式存储结构线性表的链式存储结构47由此可见：在单链表上进行插入、删除操由此可见：在单链表上进行插入、删除操作，必须先找到插入作，必须先找到插入/删除位置的前一个结点。删除位置的前一个结点。单链表不具有随机访问的特点，只能从头单链表不具有随机访问的特点，只能从头指针开始。指针

35、开始。void Delete_LinkList(LinkList L, int i) LNode *p,*s; p=Get_LinkList(L, i-1); /查找第查找第i-1个结点个结点 if(p=NULL) printf(“ 第第i-1个结点不存在个结点不存在n”); else if(p-next=NULL) printf(“ 第第i个结点不存在个结点不存在n”); else s=p-next; p-next=s-next; free(s); /删除删除 线性表的链式存储结构线性表的链式存储结构48练习：练习：（1）在一个单链表中，已知）在一个单链表中，已知q所指结点是所指结点是p所指

36、结点的前所指结点的前驱结点，若在驱结点，若在q和和p之间插入之间插入s所指结点，则执行所指结点，则执行_。A. snext =pnext;pnext=s;B. pnext =snext;snext=p;C. qnext=s;snext=p;D. pnext=s;snext=q;（2）在一个单链表中，若在一个单链表中，若p所指结点不是最后结点，在所指结点不是最后结点，在*p之后插入之后插入s所指结点，则执行所指结点，则执行_。A. snext =p;pnext=s;B. snext =pnext;pnext=s;C. snext =pnext;p =s;D. pnext =s;snext=p;线

37、性表的链式存储结构线性表的链式存储结构CB49练习：练习：（3）在一个单链表中，若删除在一个单链表中，若删除p所指结点的后继所指结点的后继结点，则执行结点，则执行_。A. pnext =pnext next;B. p=pnext ; pnext =pnext next;C. pnext =pnext ;D. p =pnext next;线性表的链式存储结构线性表的链式存储结构A50线性表的链式存储结构线性表的链式存储结构二、循环单链表二、循环单链表1、特点：、特点：最后一个结点的最后一个结点的next域不再为空而是指向头结点；域不再为空而是指向头结点；从任一结点出发可访问到所有结点。从任一结点

38、出发可访问到所有结点。a1anL2、循环单链表的操作与非循环单链表基本一致，差别仅在、循环单链表的操作与非循环单链表基本一致，差别仅在于算法中的判断条件。如：于算法中的判断条件。如：一个带头结点的循环单链表一个带头结点的循环单链表L为空的条件：为空的条件：一个带头结点的一个带头结点的非非循环单链表循环单链表L为空的条件：为空的条件：练习：练习：编写算法：求一个循环单链表的长度。编写算法：求一个循环单链表的长度。L-next=LL-next=NULL51线性表的链式存储结构线性表的链式存储结构3、有时对链表常做的操作是在表尾、表头进行，、有时对链表常做的操作是在表尾、表头进行，此时可以不设头指针

39、，而设一个尾指针此时可以不设头指针，而设一个尾指针R来标识链来标识链表，使得操作效率得以提高。表，使得操作效率得以提高。a1anR此时，表尾结点由此时，表尾结点由R指向，表头结点由指向，表头结点由R-next指向。指向。P25例如例如52线性表的链式存储结构线性表的链式存储结构应用举例应用举例：约瑟夫环问题约瑟夫环问题 已知已知n个人（以编号个人（以编号1，2，3.n分别表示）围坐分别表示）围坐在一张圆桌周围。从编号为在一张圆桌周围。从编号为k的人开始报数，数到的人开始报数，数到m的那个人出列；他的下一个人又从的那个人出列；他的下一个人又从1开始报数，开始报数，数到数到m的那个人又出列；依此规

40、律重复下去，直到的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。求所有人出列的顺序。圆桌周围的人全部出列。求所有人出列的顺序。【示例示例】 n = 9, k = 1, m = 5 出局人的顺序为出局人的顺序为5, 1, 7, 4, 3, 6, 9, 2, 8。 53【方法方法1： 循环单链表循环单链表 】基本思路：基本思路： (1) 建立一个不带头结点的循环单链表；建立一个不带头结点的循环单链表； (2) 找到第一个报数的人找到第一个报数的人k号（用号（用p指向）及其前驱指向）及其前驱k-1号号（用（用r指向）指向） ； (3) 不断不断删除第删除第m个结点，即报到个结点，即报到m

41、的人的人依次出列依次出列，直至直至剩剩下一个结点为止下一个结点为止；(4) 最后一个人出列最后一个人出列。线性表的链式存储结构线性表的链式存储结构54void Josephus(int n,int k,int m)/n为总人数，为总人数，k为第一个开始报数的人，为第一个开始报数的人，m为出列者喊到的数为出列者喊到的数 LinkList L;LNode *p,*r;int i;/r指向指向p所指结点的前驱所指结点的前驱 L=create(n);/建立一个不带头结点的循环单链表建立一个不带头结点的循环单链表 /找到第一个报数的人找到第一个报数的人k号及其前驱号及其前驱k-1号号 p=L;i=1;

42、for(i=2;inext; if(k=1)/若第一个报数的人是第一个结点若第一个报数的人是第一个结点1号，则其前驱号，则其前驱是最后一个结点是最后一个结点n号号 r=L;while(r-next!=L) r=r-next; 线性表的链式存储结构线性表的链式存储结构55 while(p-next!=p) /循环删除第循环删除第m个结点，即报到个结点，即报到m的人的人依次出列依次出列，直到剩下一个结点为止。，直到剩下一个结点为止。 /找到第找到第m个结点（用个结点（用p指向）及第指向）及第m-1个结点（用个结点（用r指向）指向） for(i=2;inext; printf(%5d,p-data)

43、; r-next=p-next;free(p); p=r-next; printf(%5dn,p-data); /最后一个人出列最后一个人出列线性表的链式存储结构线性表的链式存储结构56线性表的链式存储结构线性表的链式存储结构【方法方法2：数组：数组】将数组想象成一个环状，用将数组想象成一个环状，用“模运算模运算”模拟环状数模拟环状数组。组。57线性表的链式存储结构线性表的链式存储结构三、双链表三、双链表 1、 双链表的存储结构双链表的存储结构可双向访问可双向访问 双链表结点类型及双链表类型定义双链表结点类型及双链表类型定义 struct dlnode datatype data; struc

44、t dlnode *prior, *next; priordatanexttypedef DLNode, *DLinkList;58线性表的链式存储结构线性表的链式存储结构2、双链表的基本操作、双链表的基本操作（1）插入）插入在在*p之前插入之前插入*s在在*p之后插入之后插入*s（练习）（练习）pss-prior=p-prior; s-next=p;p-prior-next=s; p-prior=s;（或者（或者p-prior=s; s-prior-next=s;）先修改待插结先修改待插结点的指针域点的指针域59（2）删除）删除删除删除*p删除删除*p的后继（练习）的后继（练习）线性表的链式

45、存储结构线性表的链式存储结构pp-prior-next=p-next;p-next-prior=p-prior;free(p);60练习：练习：在一非空双链表中在一非空双链表中p所指结点之前插入所指结点之前插入q所指结点，所指结点，应执行应执行_。 A . qnext=p; qprior=pprior; pprior=q; pprior next=q; B. pprior=q; qnext=p; pprior next=q; qprior =pprior;C. qprior =pprior; qnext=p; pprior next=q; pprior=q;D. 以上都不对。以上都不对。线性表

46、的链式存储结构线性表的链式存储结构C61链表（链式存储结构）的优缺点链表（链式存储结构）的优缺点（1）优点）优点适宜作插入、删除操作。适宜作插入、删除操作。 （2）缺点）缺点不能随机访问；增加额外的存储空间。不能随机访问；增加额外的存储空间。线性表的链式存储结构线性表的链式存储结构62线性表的应用线性表的应用P29【例例2-9】将两个将两个递增递增有序的单链表有序的单链表A、B，归并，归并成一个成一个递减递减有序的单链表有序的单链表C，要求用，要求用A、B中的原结中的原结点形成，不能重新申请结点。点形成，不能重新申请结点。算法思路：算法思路：先建立一个空表先建立一个空表C，再依次比较，再依次比较A、B表中的相表中的相应元素，将应元素，将较小者较小者插入到插入到C的的表头表头，得到的，得到的C表则为递减有表则为递减有序的。序的。如：如：A=(3,5,8,11) B=(2,6,9,15,20)合并后：合并后：C=(20,15,11,9,8,