第五讲循环链表和双向链表
1．了解并掌握循环链表和双链表的概念。
2．熟悉双向链表的的表示与实现。
教学重点：
双向链表的表示与实现
教学难点：
双向链表的存储表示
授课内容
2．4循环链表和双向链表
2．4．1循环链表
对于单链表而言，最后一个结点的指针域是空指针，如果将该链表头指针置入该指针域，则使得链表头尾结点相连，就构成了单循环链表。如图2.16所示。在单循环链表上的操作基本上与非循环链表相同，只是将原来判断指针是否为NULL变为是否是头指针而已，没有其它较大的变化。
图2.16带头结点的单循环链表
对于单链表只能从头结点开始遍历整个链表，而对于单循环链表则可以从表中任意结点开始遍历整个链表，不仅如此，有时对链表常做的操作是在表尾、表头进行，此时可以改变一下链表的标识方法，不用头指针而用一个指向尾结点的指针R来标识，可以使得操作效率得以提高。
例如对两个单循环链表H1 、H2的连接操作，是将H2的第一个数据结点接到H1的尾结点，如用头指针标识，则需要找到第一个链表的尾结点，其时间复杂性为O(n)，而链表若用尾指针R1、R2来标识，则时间性能为O(1)。操作如下：
p=R1–>next;/*保存R1 的头结点指针*/
R1->next=R2->next->next;/*头尾连接*/
free(R2->next);/*释放第二个表的头结点*/
R2->next=p;/*组成循环链表*/
这一过程可见图2.17。
图2.17两个用尾指针标识的单循环链表的连接
2．4．2双向链表
以上讨论的单链表的结点中只有一个指向其后继结点的指针域next，因此若已知某结点的指针为p，其后继结点的指针则为p->next ，而找其前驱则只能从该链表的头指针开始，顺着各结点的next域进行，也就是说找后继的时间性能是O(1)，找前驱的时间性能是O(n)，如果也希望找前驱的时间性能达到O(1)，则只能付出空间的代价：每个结点再加一个指向前驱的指针域，结点的结构为如图2.18所示，用这种结点组成的链表称为双向链表。
双向链表结点的定义如下：
typedef struct dlnode
{datatype data;
struct dlnode*prior,*next;
}DLNode,*DLinkList;
图2.18
和单链表类似，双向链表通常也是用头指针标识，也可以带头结点和做成循环结构，图2.19是带头结点的双向循环链表示意图。显然通过某结点的指针p即可以直接得到它的后继结点的指针p->next，也可以直接得到它的前驱结点的的指针p->prior。这样在有些操作中需要找前驱时，则勿需再用循环。从下面的插入删除运算中可以看到这一点。
设p指向双向循环链表中的某一结点，即p中是该结点的指针，则p->prior->next表示的是*p结点之前驱结点的后继结点的指针，即与p相等；类似，p->next->prior表示的是*p结点之后继结点的前驱结点的指针，也与p相等，所以有以下等式：
图2.19带头结点的双循环链表
双向链表中结点的插入：设p指向双向链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p的前面，插入示意图如图2.20所示。
图2.20双向链表中的结点插入
操作如下：
s->prior=p->prior;
p->prior->next=s;
s->next=p;
p->prior=s;
指针操作的顺序不是唯一的，但也不是任意的，操作①必须要放到操作④的前面完成，否则*p的前驱结点的指针就丢掉了。读者把每条指针操作的涵义搞清楚，就不难理解了。
双向链表中结点的删除：
设p指向双向链表中某结点，删除*p。操作示意图如图2.21所示。
图2.21双向链表中删除结点
操作如下：
①p->prior->next=p->next;
②p->next->prior=p->prior;
free(p);
创建双向循环链表的源代码： #include
L->Length ++; } } //结点的输出 void Display( DuLinkList L) { DuLinkList p; printf("双向循环链表中的结点的数据为:"); for(p=L->next ;p->next !=L;) { printf("%d",p->data); printf(" 、"); p=p->next ; } printf("%d\n",p->data ); } int main() { DuLinkList L; int n,i; InitList(&L) ; printf("你想创建几个循环节点就输入几就行啦，请输入:"); scanf("%d",&n); Create(L,n); Display(L); } 双向循环链表插入源代码： #include
数学与计算机学院 课程设计说明书 课程名称: 数据结构与算法A设计实践 课程代码: 6015059 题目一: 线性表的链式表示和实现 题目二: 利用栈实现表达式求解 年级/专业/班: 2011/信科/2班 学生姓名: XXX 学号: XXX 开始时间:2014 年 5 月28 日 完成时间:2014 年 6 月28 日 课程设计成绩： 指导教师签名：年月日
目录 摘要 (1) 1 引言 (2) 2 实验一 (3) 2.1整体设计思路 (3) 2.2编码 (3) 2.3程序演示 (6)
摘要 随着计算机的普遍应用与日益发展，其应用早已不局限于简单的数值运算，数据结构与算法的学习就是为以后利用计算机资源高效地开发非数值处理的计算机程序打下坚实的理论、方法和技术基础。数据结构与算法旨在分析研究计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构，从而使建立在其上的解决问题的算法达到最优。 本次数据结构实践的第一个实验是线性表的链式表示和实现，要求动态地建立循环链表并实现循环链元素的插入，删除，查询；使用双向链的结构实现判断一个录入的字符串是否是回文；建立一个单向链表，实现其内元素非递减排序。 关键词：数据结构与算法线性表链式结构栈表达式求解
1 引言 1.1问题的提出 数据结构课程设计是重要地实践性教学环节。在进行了程序设计语言课和《数据结构与算法》课程教学的基础上，设计实现相关的数据结构经典问题，有助于加深对数据结构课程的认识。本课程设计是数据结构中的一个关于线性表链式表示的实现还有用栈实现表达式求解，此课程设计要求对栈存储结构和链表存储结构非常熟悉，并能熟练使用它们。 1.2C语言 C语言既有高级语言的特点，又具有汇编语言的特点；既是一个成功的系统设计语言，有时一个使用的程序设计语言；既能用来编写不依赖计算机硬件的应用程序，又能用来编写各种系统程序；是一种受欢迎、应用广泛的程序设计语言。 1.3C语言发展过程 1973年，美国贝尔实验室的D.M.RITCHIE在B语言的基础上最终设计出了一种新的语言，他取了BCPL的第二个字母作为这种语言的名字，这就是C语言。 1977年Dennis M.Ritchie 发表了不依赖于具体机器系统的C语言编译文本《可移植的C语言编译程序》。 1978年Brian W.Kernighian和Dennis M.Ritchie出版了名著《The C Programming Language》，从而使C语言成为目前世界上流行最广泛的高级程序设计语言。 1.4任务 题目一：线性表的链式表示和实现 第一个实验主要是实现一些线性表的基本操作。包括（1）动态地建立循环链表；（2）实现循环链元素的插入，删除，查询；（3）使用双向链的结构实现判断一个录入的字符串是否是回文；（4）建立一个单向链表，实现其内元素非递减排序。
用双向循环链表求解约瑟夫环 学校：东北大学 专业：计算机科学与技术
1.问题描述 Josephus排列问题定义如下：假设n个竞赛者排成一个环形。给定一个正整数m≤n，从第1人开始，沿环计数，第m人出列。这个过程一直进行到所有人都出列为止。最后出列者为优胜者。全部出列次序定义了1，2，…n的一个排列。称为（n，m）Josephus排列。例如，（7，3）Josephus排列为3,6,2,7,5,1,4。【实验要求】 设计求解Josephus排列问题程序。 （1）采用顺序表、单链表或双向循环链表等数据结构。 （2）采用双向循环链表实现Josephus排列问题，且奇数次顺时针轮转，偶数次逆时针轮转。 （3）推荐采用静态链表实现Josephus排列问题。 2.需求分析 本程序要求根据输入的人数n和给定的正整数m，求得约瑟夫排列，且奇数次顺时针轮转，偶数次逆时针轮转。故可利用双向循环链表建立存储结构，利用双向循环链表的遍历与删除操作实现功能要求。 3.概要设计 1.抽象数据类型定义： typedef struct DuLNode { int data; struct DuLNode *prior; struct DuLNode *next; }DuLNode,*DuLinkList; //定义双向循环链表 2.基本操作 int InitList_Dul(DuLinkList &L) //建立一个只含头结点的空双向循环链表 int CreateList_DuL(DuLinkList &L,int n) //建立一个带头结点的含n个元素的 双向循环链表L int ListDelete_DuL(DuLinkList &L,DuLinkList x) //删除指针x指向的结点 3.设计思路 首先建立一个双向循环链表作为存储结构，每个结点的数据域存储每个人的编号，然后根据给定的m值对整个链表进行遍历，找到所要找的结点后，输出该结点的数据域的值，并在双向循环链表中删除该结点，重复这样的操作，一直到所有的人都出列，依次输出的数列即为所求的Josephus排列。 4.详细设计 typedef struct DuLNode { int data; struct DuLNode *prior;
#include
int i=-1; List *p,*data1,*q,*Last; data1=(List *)malloc(sizeof(List)); p=(List *)malloc(sizeof(List)); q=(List *)malloc(sizeof(List)); data1=head->next;//记住第一个数据地址 p=head->next; while(p->next!=NULL) { q=p; //q是前一个节点 p=p->next; //p是后一个节点 p->pre=q; //后一个节点的【前继指针】指向前一个节点的地址} Last=p; //p 就是【最后一个数据】的地址 data1->pre=Last; //【第一个元素】的【前继指针】指向【最后一个元素】的地址Last->next=data1; //【最后一个元素】的【后继指针】指向【第一个元素】的地址//双向链表构成 p=Last; printf("\n\n"); while(p->data!=1) { printf("%d ",p->data); p=p->pre; } printf("%d \n",p->data); }
list是双向循环链表，，每一个元素都知道前面一个元素和后面一个元素。在STL 中，list和vector 一样，是两个常被使用的容器。和vector不一样的是，list不支持 对元素的任意存取。list中提供的成员函数与vector类似，不过list提供对表首元素的操作 push_front、pop_front，这是vector不具备的。禾口vector另一点不同的是，list的迭代器不会存在失效的情况，他不像vector会保留备份空间，在超过容量额度时重新全部分配内存，导致迭代器失效；list没有备份空间的概念，出入一个元素就申请一个元素的空间，所以它的迭代器不会失效。还是举《C++之vector》中的 例子： int data[6]={3,5,7,9,2,4}; list< int> lidata(data, data+6); lidata.push_back(6); list初始化时，申请的空间大小为6，存放下了data中的6个元素，当向lidata插入第7个元素“6”，list申请新的节点单元，插入到list链表中，数据存放结构如图1所示： 插入节点"6拆之后的list 图1 list的存储结构 list每次增加一个元素，不存在重新申请内存的情况，它的成本是恒定的。而vector每当增加关键元素的时候，都需要重新申请新的更大的内存空间，会调用元素的自身的复制构造函数，存在构造成本。在销毁旧内存的时候，会调用析构函数, 存在析构成本。所以在存储复杂类型和大量元素的情况下，list比vector更有优势！ List是一个双向链表,双链表既可以向前又向后链接他的元素。
实验一 要求：①建立双向循环链表 ②实现链表的插入、删除 运行程序点此处Demo_1.exe 实验程序源代码： #include "stdafx.h" #include
p->next =q; q->prior=p; q->next=L; L->prior =q; p=q; L->Length ++; } } //查找元素的位置 DuLinkList GetElemP(DuLinkList h,int i) { int j; DuLinkList p=h; for(j=1;j<=i;j++) p=p->next ; return p; } //结点的插入 status Listinsert(DuLNode *m,int i,int e) { //在带头结点的双链循环线性表L中第i个位置之前插入元素e，i的合法值为1≤i≤表长 DuLinkList p,q; if(i<1||i>(m->Length)) // i值不合法 return ERROR; p=GetElemP(m,i); if(!p) return ERROR; q=(DuLinkList)malloc(sizeof(DuLNode)); if(!q) return OVERFLOW; q->data=e; q->prior=p->prior; p->prior->next=q; q->next=p; p->prior=q; m->Length++; printf("您在双向循环链表第%d个位置之前插入了一结点元素:%d\n",i,e); return OK; } //结点的删除 status ListDelete(DuLinkList L,int i) { //删除带头结点的双链循环线性表L的第i个元素，i的合法值为1≤i≤表长
主要的数据类型有两个带头结点的双向循环链表，这两个链表与MFC应用程序自动生成的对象类型混合使用，如下： typedef struct { //单个雨滴 COLORREF color;//雨滴颜色 bool visibility; //可见性 float radius; //半径 float x;//雨滴中心位置 x float y;//雨滴中心位置 y float xvelocity;//雨滴速率 vx float yvelocity;//雨滴速率 vy } droplet; struct dropletchain {//所有雨滴组成的链表 struct dropletchain * pre; droplet * drop; struct dropletchain * next; }; typedef struct {//单个涟漪 COLORREF color;//颜色 float xdrop;//涟漪中心 x float ydrop;//涟漪中心 y float radius;//涟漪半径 int shown;//是否绘制涟漪（这个参数在判断是否需要重绘时用到） }ripple; struct ripplechain {// 所有涟漪组成的链表 struct ripplechain * pre; ripple * aripple; struct ripplechain * next; }; 对链表的操作混杂在类CCrainDlg（mfc 的对话框类）中。 三、大致的程序流程： a) 在程序的初始化阶段定义了两个链表 struct dropletchain dc; struct ripplechain rc; 这两个都是空的链表,且 dc.drop=NULL; dc.pre=&dc; dc.next=&dc; rc.aripple=NULL;
#include
typedef struct node { ElemType data; struct node *prior, *next; }DLink; void InitList(DLink **L); //初始化运算 int GetLength(DLink *L); //求表长运算 int GetElem(DLink *L, int num, ElemType *e); //求线性表中第i个元素运算int Locate(DLink *L, ElemType x); //按值查找运算 int InsElem(DLink *L, ElemType x, int i); //插入节电运算 int DelElem(DLink *L, int num); //删除结点运算 void DispList(DLink *L); //输出线性表 #endif [cpp] view plaincopyprint? #include
List-DuLinkedList-双向循环链表-Locate(L,x) 2.38 设有一个双向循环链表，每个结点中除了有prior、data和next三个域外，还增设了一个访问频度域freq。在链表被启用之前，频度域freq的值均初始化为零，而每当对链表进行一次Locate(L, x)的操作后，被访问的结点（即元素值等于x的结点）中的频度域freq的值便增加1，同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的Locate操作的算法。#include
数据结构之双向链表地Java 实现 单链表只能从前往后遍历,如果链表地长度较大, 遍历到链表后半部分地时候想要往前查找,就只能回到开头,重新遍历了. 双向链表提供了这个能力, 即允许前向遍历, 也允许后向遍历整个链表. 原因是双向链表地每个节点都有两个指向其他节点地引用. 但这也是其缺点, 因为在插入、删除地时候需要处理四个链接点地引用, 占用地空间也大了一些. 如将头节点和尾节点链接起来, 即成为双向循环链表. b5E2RGbCAP 下面是java 代码： package test 。 public class DoubleLink { public Link first 。 public Link last 。 public DoubleLink< ) {// 构造器, 初始化 this.first = null 。 https://www.doczj.com/doc/e68819274.html,st = null 。 } public boolean isEmpty< ) {// 判断是否为空 return first == null 。 } public void insertFirst link.next = first 。 first = link 。 } public void insertLast JAVA循环双链表的建立 import java.util.Scanner; //循环双向链表的结点类 class DuLNode { private Object data;// 存放结点值 private DuLNode prior; // 前驱结点的引用 private DuLNode next; // 后继结点的引用 public DuLNode() {// 无参数时的构造函数 this(null); } public DuLNode(Object data) {// 构造值为data 的结点this.data = data; this.prior = null; this.next = null; } public Object getData() { return data; } public DuLNode getNext() { return next; } public DuLNode getPrior() { return prior; } public void setData(Object data) { this.data = data; } public void setNext(DuLNode next) { this.next = next; } public void setPrior(DuLNode prior) { this.prior = prior; } } //双向链表类 public class DuLinkList{ private DuLNode head;// 双向循环链表的头结点// 双向链表的构造函数 public DuLinkList() { head = new DuLNode(); // 初始化头结点 head.setPrior(head);// 初始化头结点的前驱和后继 山东建筑大学计算机科学与技术学院 课程设计说明书 题目：双向链表的创建和操作的实现 树的创建及相关操作的实现课程：数据结构与算法 院（部）：计算机学院 专业：网络工程 班级：网络101 学生姓名：王天未 学号：20XX111200 指导教师：伊静 完成日期：20XX-7-6 目录 课程设计任务书1................................................ II 课程设计任务书2............................................... III 双向循环链表的创建及相关操作的实现 (4) 一、问题描述 (4) 二、数据结构 (4) 三、逻辑设计 (5) 四、编码 (6) 五、测试数据 (11) 六、测试情况 (11) 树的创建及相关操作的实现 (15) 一、问题描述 (15) 二、数据结构 (15) 三、逻辑设计 (16) 四、编码 (19) 五、测试数据 (26) 六、测试情况 (26) 结论 (28) 参考文献 (29) 课程设计指导教师评语 (30) 课程设计任务书1 指导教师（签字）：教研室主任（签字） 课程设计任务书2 指导教师（签字）：教研室主任（签字） 双向循环链表的创建及相关操作的实现一、问题描述 1、每个节点的next域构成了一个循环单链表 2、每个节点的prev域构成了另一个循环单链表 二、数据结构 针对所处理的树： 1、画出双向循环链表的存储结构 2、使用所选用语言的功能，描述该存储结构的实现 private static class Node 长治学院 课程设计任务书 课程名称：数据结构课程设计 设计题目：双向循环链表 系别：计算机系 专业：网络工程 学生姓名: 许玮玲学号:07407336 起止日期:2008年11月12日~2008年12月15 日指导教师:孙俊杰 第1页共11页 1 目录 第一章需求分析-----------------------------------------------------------3 第二章开发过程-----------------------------------------------------------3 2.1系统目标----------------------------------------------------------------------3 2.2合理的设计流程图----------------------------------------------------------3 2.3设计出友好的界面----------------------------------------------------------3 2.4实现基本功能和和一些特殊的功能-------------------------------------3 2.5功能划分----------------------------------------------------------------------4 2.6系统功能分析----------------------------------------------------------------4 第三章详细设计----------------------------------------4 3.1系统设计方法-------------------------------------------4 3.2数据结构设计------------------------------------------4 3.3系统界面设计-------------------------------------------5 3.4应用程序代码设计---------------------------------------5 第四章调试与操作说明----------------------------------11 第五章课程设计与体会-----------------------------------11 2 #include q=(DLNode*)malloc(sizeof(DLNode)); s=root; if(root==NULL) //头指针为空，则删除不成功 { cout<<"删除不成功"< 第五讲循环链表和双向链表 1．了解并掌握循环链表和双链表的概念。 2．熟悉双向链表的的表示与实现。 教学重点： 双向链表的表示与实现 教学难点： 双向链表的存储表示 授课内容 2．4循环链表和双向链表 2．4．1循环链表 对于单链表而言，最后一个结点的指针域是空指针，如果将该链表头指针置入该指针域，则使得链表头尾结点相连，就构成了单循环链表。如图2.16所示。在单循环链表上的操作基本上与非循环链表相同，只是将原来判断指针是否为NULL变为是否是头指针而已，没有其它较大的变化。 图2.16带头结点的单循环链表 对于单链表只能从头结点开始遍历整个链表，而对于单循环链表则可以从表中任意结点开始遍历整个链表，不仅如此，有时对链表常做的操作是在表尾、表头进行，此时可以改变一下链表的标识方法，不用头指针而用一个指向尾结点的指针R来标识，可以使得操作效率得以提高。 例如对两个单循环链表H1 、H2的连接操作，是将H2的第一个数据结点接到H1的尾结点，如用头指针标识，则需要找到第一个链表的尾结点，其时间复杂性为O(n)，而链表若用尾指针R1、R2来标识，则时间性能为O(1)。操作如下： p=R1–>next;/*保存R1 的头结点指针*/ R1->next=R2->next->next;/*头尾连接*/ free(R2->next);/*释放第二个表的头结点*/ R2->next=p;/*组成循环链表*/ 这一过程可见图2.17。 图2.17两个用尾指针标识的单循环链表的连接 2．4．2双向链表 以上讨论的单链表的结点中只有一个指向其后继结点的指针域next，因此若已知某结点的指针为p，其后继结点的指针则为p->next ，而找其前驱则只能从该链表的头指针开始，顺着各结点的next域进行，也就是说找后继的时间性能是O(1)，找前驱的时间性能是O(n)，如果也希望找前驱的时间性能达到O(1)，则只能付出空间的代价：每个结点再加一个指向前驱的指针域，结点的结构为如图2.18所示，用这种结点组成的链表称为双向链表。 双向链表结点的定义如下： typedef struct dlnode {datatype data; struct dlnode*prior,*next; }DLNode,*DLinkList; 图2.18 和单链表类似，双向链表通常也是用头指针标识，也可以带头结点和做成循环结构，图2.19是带头结点的双向循环链表示意图。显然通过某结点的指针p即可以直接得到它的后继结点的指针p->next，也可以直接得到它的前驱结点的的指针p->prior。这样在有些操作中需要找前驱时，则勿需再用循环。从下面的插入删除运算中可以看到这一点。 设p指向双向循环链表中的某一结点，即p中是该结点的指针，则p->prior->next表示的是*p结点之前驱结点的后继结点的指针，即与p相等；类似，p->next->prior表示的是*p结点之后继结点的前驱结点的指针，也与p相等，所以有以下等式： 课程设计报告 课程名称数据结构 课题名称双链表创建演示 专业计算机科学与技术 班级计算机0703 学号200703010334 姓名张理 指导教师陈淑红李杰君 2009 年11 月7 日 湖南工程学院 课程设计任务书 课程名称数据结构 课题双链表创建演示 专业班级计算机0703 学生姓名张理 学号200703010334 指导老师陈淑红李杰君 审批 任务书下达日期2009 年10 月8 日任务完成日期2009 年11 月7 日 1设计内容与设计要求 1.1设计内容 1.1.1 算术24游戏演示 由系统随机生成4张扑克牌，用户利用扑克牌的数字及运算符号“+”、 “—”、“*”、“/”及括号“（”和“）”从键盘上输入一个计算表达式，系统运行后得出计算结果，如果结果等于24，则显示“Congratulation!”，否则显示“I ncorrect!” 设计思路：从键盘输入中缀表达式，然后将中缀表达式转换为后缀表达式，利用后缀表达式求值。 1.1.2 迷宫探索 随机生成一个迷宫图，迷宫大小为N*N，N预定义为常数，修改N的值可以改变迷宫的大小。用白色表示可走的路，蓝色表示墙壁不可以通过。系统设计两种运行方式：一种是系统自动探索（用递归方法实现）；另一种是由人工操作探索通路。 设计思路：程序首先要考虑迷宫的表示，这是一个二维关系图，所以可选择二维数组来存储。数组元素只有两种值0和1，分别代表通路和墙壁。图形的显示可以根据数组元素的值来确定。如果是人工探索，则依据按键来确定探索物的位置坐标，利用循环语句实现。如果是系统自动探索，可采用递归算法实现。 1.1.3 二叉树遍历演示 演示遍历二叉树的过程，所以首先建立二叉树，并用图形显示出树的形状。建立的过程是采用前序便利的方法来创建，设计两种生成树的方式：一种是系统随机生成，另一种是人工输入。考虑到屏幕界面的有限性，限定二叉树不超过5层，最多26个字符，输入字符小数点“.”代表NULL。初始树为某种颜色的结点，三种情况的遍历采用填充另外一种醒目的颜色，来表示当前遍历的结点，同时显示该结点的访问序号。同时在遍历的过程中在遍历图形的下方显示出遍历序列。 1.1.4 数组应用 按照行优先顺序将用户随机输入的数据建成2维数组并以图形方式逐步显JAVA循环双链表的建立
推荐-双向循环链表的创建及相关操作的实现课程设计说明书 精品
不带头节点的双向循环链表
双向循环链表使用实例
第五讲循环链表和双向链表
数据结构课程设计报告-双链表创建与演示
相关主题
文本预览