310计14-循环链表与双向链表及线性表的应用举例

1、DATA STRUCTURE 线性表的链式存储结构 第第2章线性表章线性表 （相应教材范围（相应教材范围2.3.2-2.4） 教学主题：教学主题：循环链表与双向链表及线性表的应用举例循环链表与双向链表及线性表的应用举例 教学内容：教学内容：2.3.2 2.3.2 循环链表；循环链表；2.3.3 2.3.3 双向链表；双向链表；2.4 2.4 一元多项一元多项 式的表示及相加式的表示及相加 教学目的：教学目的：掌握循环链表的概念掌握循环链表的概念；掌握双向链表的的表示与实掌握双向链表的的表示与实 现现；线性表的应用举例；线性表的应用举例 教学重点：教学重点：双向链表的的表示与实现双向链表的的表示

2、与实现；线性表的应用举例；线性表的应用举例 教学难点：教学难点：双向链表的存储表示双向链表的存储表示；线性表的应用举例；线性表的应用举例 教学课时：教学课时：2 2 DATA STRUCTURE 数据结构及其基本概念 2.3.2 循环链表循环链表 循环链表（循环链表（Circular linked List)时一种头尾相接的链表。时一种头尾相接的链表。 它的特点是表中最后一个结点的指针域指向头结点，整个链表它的特点是表中最后一个结点的指针域指向头结点，整个链表 形成一个环。由此从表中任一结点出发均可找到表中其它结点。形成一个环。由此从表中任一结点出发均可找到表中其它结点。 单循环链表单循环链表

3、：在单链表中，将终端结点的指针域：在单链表中，将终端结点的指针域NULL改改 为指向表头结点的或开始结点，就得到了单链形式的循环链表，为指向表头结点的或开始结点，就得到了单链形式的循环链表， 并简单称为单循环链表。并简单称为单循环链表。 为了使空表和非空表的处理一致，循环链表中也可设置一为了使空表和非空表的处理一致，循环链表中也可设置一 个头结点。这样，空循环链表仅有一个自成循环的头结点表示。个头结点。这样，空循环链表仅有一个自成循环的头结点表示。 DATA STRUCTURE 数据结构及其基本概念 循环链表的操作和线性表基本一致，差别仅在于算法中的循环链表的操作和线性表基本一致，差别仅在于算

4、法中的 循环条件不是循环条件不是p或者或者pnext是否为空是否为空，而是它们是否等于头，而是它们是否等于头 指针。指针。 DATA STRUCTURE 数据结构及其基本概念 在很多实际问题中，表的操作常常是在表的在很多实际问题中，表的操作常常是在表的首尾位置首尾位置上进上进 行，此时头指针表示的单循环链表就显得不够方便行，此时头指针表示的单循环链表就显得不够方便.如果改用尾如果改用尾 指针指针rear来表示单循环链表，则查找开始结点来表示单循环链表，则查找开始结点a1和终端结点和终端结点an 都很方便，它们的存储位置分别是都很方便，它们的存储位置分别是(rearnext) next和和rea

5、r， 显然，查找时间都是显然，查找时间都是O(1)。因此，实际中多采用尾指针表示单。因此，实际中多采用尾指针表示单 循环链表。循环链表。 由于循环链表中没有由于循环链表中没有NULL指针，故涉及遍历操作时，其指针，故涉及遍历操作时，其 终止条件终止条件就不再像非循环链表那样判断就不再像非循环链表那样判断p或或pnext是否为空，是否为空， 而是判断它们是否等而是判断它们是否等某一指定指针，如头指什或尾指针等。某一指定指针，如头指什或尾指针等。 。 DATA STRUCTURE 数据结构及其基本概念 例例、在链表上实现将两个线性表、在链表上实现将两个线性表(a1，a2，a3，an)和和(b1，b

6、2， b3，bn)链接成一个线性表的运算。链接成一个线性表的运算。 linklist connect(linklist heada，linklist headb) linklist p=headanext; headanext=(headbnext)next free(headbnext); headbnext=p; return(headb); DATA STRUCTURE 数据结构及其基本概念 2.3.3双链表双链表 链式存储结构的结点中只有一个指示直接后继的指针域，链式存储结构的结点中只有一个指示直接后继的指针域， 因此从某个结点出发只能顺时针往后寻查其它结点。若要寻查因此从某个结点出发

7、只能顺时针往后寻查其它结点。若要寻查 结点的直接前趋，则须从表头指针出发。结点的直接前趋，则须从表头指针出发。 双向链表双向链表(Double linked list):在单链表的每个结点里再增在单链表的每个结点里再增 加一个指向其直接前趋的指针域加一个指向其直接前趋的指针域prior。这样就形成的链表中有。这样就形成的链表中有 两个方向不同的链，故称为双向链表。形式描述为：两个方向不同的链，故称为双向链表。形式描述为： typedef struct DuLNode ElemType data; struct DuLNode *prior; struct DuLNode *next; DuLN

8、ode, *DuLinkList; DATA STRUCTURE 数据结构及其基本概念 2.3.3双链表双链表 链式存储结构的结点中只有一个指示直接后继的指针域，链式存储结构的结点中只有一个指示直接后继的指针域， 因此从某个结点出发只能顺时针往后寻查其它结点。若要寻查因此从某个结点出发只能顺时针往后寻查其它结点。若要寻查 结点的直接前趋，则须从表头指针出发。结点的直接前趋，则须从表头指针出发。 双向链表双向链表(Double linked list):在单链表的每个结点里再增在单链表的每个结点里再增 加一个指向其直接前趋的指针域加一个指向其直接前趋的指针域prior。这样就形成的链表中有。这样

9、就形成的链表中有 两个方向不同的链，故称为双向链表。形式描述为：两个方向不同的链，故称为双向链表。形式描述为： typedef struct DuLNode ElemType data; struct DuLNode *prior; struct DuLNode *next; DuLNode, *DuLinkList; DATA STRUCTURE 数据结构及其基本概念 和单链表类似，双链表一般也是由头指针唯一确定的，增加头指针也和单链表类似，双链表一般也是由头指针唯一确定的，增加头指针也 能使双链表上的某些运算变得方便，将头结点和尾结点链接起来也能构成能使双链表上的某些运算变得方便，将头结点

10、和尾结点链接起来也能构成 循环链表，并称之为循环链表，并称之为双向链表双向链表。 设指针设指针p指向某一结点，则双向链表结构的对称性可用下式描述：指向某一结点，则双向链表结构的对称性可用下式描述： (pprior)next=p=(pnext)prior，即结点，即结点*p的存储位置既存放在的存储位置既存放在 其前趋结点其前趋结点*(pprior)的直接后继指针域中，也存放的直接后继指针域中，也存放 在它的后继结点在它的后继结点 *(pnext)的直接前趋指针域中。的直接前趋指针域中。 DATA STRUCTURE 数据结构及其基本概念 在双向链表中，有些操作如：在双向链表中，有些操作如：Lis

11、tLength、GetElem和和LocateElem等仅等仅 需涉及一个方向的指针，则它们的算法描述和线性表的操作相同，但在插需涉及一个方向的指针，则它们的算法描述和线性表的操作相同，但在插 入、删除时有很大的不同，在双向链表中需同时修改两个方向的指针。下入、删除时有很大的不同，在双向链表中需同时修改两个方向的指针。下 图图2.15、2.16所示为在带头结点的双链循环线性表中第所示为在带头结点的双链循环线性表中第i个位置之前插入元素个位置之前插入元素 e和删除带头结点的双链循环线性表和删除带头结点的双链循环线性表L的第的第i个元素的情况。个元素的情况。 DATA STRUCTURE 数据结构

12、及其基本概念 双向链表的前插操作算法如下：双向链表的前插操作算法如下： void dinsertbefor(dlistnode *p，datatype x) dlistnode *q=malloc(sizeof(dlistnode); qdata=x; qprior=pprior; qnext=p; ppriornext=q; pprior=q; 双向链表的删除操作算法如下：双向链表的删除操作算法如下： void ddeletenode(dlistnode *p) ppriornext=pnext; pnextprior=pprior; free(p); 注意：与单链表的插注意：与单链表的插 入和删除操作不同的入和删除操作不同的 是，在双链表中插入是，在双链表中插入 和删除必须同时修改和删除必须同时修改 两个方向上的指针。两个方向上的指针。 DATA STRUCTURE 线性表的链式存储结构 拓展思考（典型应用）：拓展思考（典型应用）： 1 1、多项式相加多项式相加 2 2、约瑟夫（约瑟夫（JosephJoseph）问题）问题 DATA STRUCTURE 线性表的链式存储结构 解答疑问：解答疑问：学生根据本节内容