文档库 最新最全的文档下载
当前位置:文档库 › 不带头节点的双向循环链表

不带头节点的双向循环链表

不带头节点的双向循环链表
不带头节点的双向循环链表

长治学院

课程设计任务书

课程名称:数据结构课程设计

设计题目:双向循环链表

系别:计算机系

专业:网络工程

学生姓名: 许玮玲学号: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

第一章需求分析

用户需求分析

该实习完成的是一个简单的双循环链表的使用,功能比较简单,要在实际中应用还需进一步的改进和完善,它实现的功能如下

1、完成双向链表的录入。

2、实现双向链表的删除节点,插入节点,寻找节点等各种操作

使用的开发工具:TURBOC2系统

第二章开发过程

2.1系统目标

设计本程序的目的主要是便于大家更好和更方便的了解双循环链表,了解其与单循环链表的区别,以及没有头结点的双循环链表和带头结点的双循环链表的区别和联系,达到更方便和快捷的应用双循环链表进行各种操作和为应用双循环链表的系统提供基础的目的。

2.2 合理的设计数据库

尽量合理地减少数据库数据的冗余,使重复的数据保持在最小限度,这样将不必要的多占用存储空间,减少产生混乱影响的危险,还能提高计算机的运行速度。

2.3设计出友好的界面

界面的友好与否是用户评价一个软件优劣的重要方面之一,使用户有一个良好的心情。

2.4实现基本功能和一些特殊功能的操作

该系统要求除了能实现学生信息的录入,删除,插入等基本功能之外,还要求能够根据用户的需要进行操作。

第3页共11页 3

2.5功能划分

本系统的功能主要包括两大部分,一:双向链表的各种操作。二:存盘·密码·排序等操作系统基本操作。

第一部分包括不带头结点的双循环链表的建立,结点删除,结点插入(前插和后插),寻找结点,寻找结点的前驱和后继,链表的判空等各种操作。

第二部分包括密码,存盘,排序等复杂操作。是该系统能够更方便和安全的使用

2.6系统功能分析

本系统的功能主要是对双向链表系统的操作:双向链表的各种操作。和存盘·密码·排序等操作系统基本操作。不带头结点的双循环链表的建立,结点删除,结点插入(前插和后插),寻找结点,寻找结点的前驱和后继,链表的判空等各种操作。密码,存盘,排序等复杂操作。是该系统能够更方便和安全的使用。

第三章系统设计

3.1 系统设计的方法

系统设计是把需求转化为软件系统的最重要的环节。系统设计的优劣在根本上决定了软件系统的质量。系统设计的五个方面的内容:体系结构设计、模块设计、数据结构设计与算法设计、用户界面设计。

3.2. 数据结构设计概述

数据结构是一门研究非数值计算的程序程序设计问题中计算机的操作对象以及他们之间的关系和操作等的学科。“数据结构”的研究不仅涉及到计算机硬件的研究范围,而且和计算机软件的研究有着更密切的关系,无论是编译程序还是操作系统,都涉及到数据单元在存储器中的分配问题。良好的数据结构设计,可以提高数据信息的存储效率,保证数据信息的完整性和一直性。同时,一个合理的数据结构有利于程序的实现。这里选用TURBOC2作为编程环境。

4

3.3系统的界面设计

系统通过建立窗口完成登录,如图2

printf(“&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&\n”) printf(“& &\n”);

pri ntf(“& &\n”);

printf(“& &\n”);

printf(“& &\n”);

printf(“& &\n”);

printf(“& 欢迎使用本软件 &\n”);

printf(“& 请输入密码 &\n”);

printf(“& &\n”);

printf(“& &\n”);

printf(“& &\n”);

printf(“& &\n”);

printf(“& 本软件仅供课程设计使用 &\n”);

printf(“& 作者:郑君许玮玲 &\n”);

printf(“& 联系方式:2178172 &\n”);

printf(“& &\n”);

printf(“& &\n”);

printf(“& &\n”);

printf(“& &\n”);

printf(“& &\n”);

printf(“& &\n”);

printf(“& &\n”);

printf(“&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&\n”);

printf(" 密码:");

3.4 应用程序代码设计

各种函数名称如下:S *InitList(S *L);

void SetList(S *L);

void PrintList(S *L);

void LocatePos(S *L);

void InsFirst(S *L);

void DelFirst(S *L);

第5页共11页 5

void Append(S *L1,S *L2);

void Remove(S *L);

void InsBefore(S *L);

void InsAfter(S *L);

void SetCurElem(S *L);

void GetCurElem(S *L);

void ListEmpty(S *L);

void ListLength(S *L);

void Gethead(S *L);

void GetLast(S *L);

void PriorPos(S *L);

void NextPos(S *L);

各种程序代码如下

main()

{

FILE *fp;

char ch,a[6]="123456",b[6],name[10]="code";

int i=0,n;

if((fp=fopen("code","r"))==NULL)

{

fp=fopen(name,"w");

fputs(a,fp);

}

fclose(fp);

fp=fopen("code","r");

fgets(a,7,fp);

while(i<3)

{

interface1();

gets(b);

n=testcode(a,b);

if(n==6)

{

interface2();

break;

}

i++;

6

}

if(i==3)

{

printf(" 谢谢使用本软件\n");

printf(" 请联系正确密码后使用\n");

printf(" 按回车结束.\n");

getch();

exit(0);

}

printf(" 请选择您需要的操作:");

scanf("%d",&n);

while(n>20)

{

printf(" 输入错误,请重新输入:"); scanf("%d",&n);

}

select(n);

while(1)

{

interface2();

printf(" 请选择您需要的操作:");

scanf("%d",&n);

while(n>20)

{

printf(" 无此项操作,请重新选择:");

scanf("%d",&n);

printf("\n");

}

select(n);

}

getch();

}

各种函数代码如下

void LocatePos(S *L)

{/* 输出链表中的已知结点的数据元素的值*/

第7页共11页7

int i=0,Locate;

LNode *p=L->head;

printf("输出的链表中的第几个结点?\n");

scanf("%d",&Locate);

while(p->next!=L->head)

{

i++;

if(i==Locate)

{

printf("%d\n",p->data);

break;

}

else

p=p->next;

}

if(p==L->tail)

{

i++;

if(i==Locate)

printf("%d ",p->data);

else

printf("输入有误\n");

}

}

void InsFirst(S *L)

{ /*将结点插入到首结点之前*/

LNode *q;

q=(LNode *)malloc(sizeof(LNode));

printf("输入插入数据.\n");

scanf("%d",&q->data);

q->next=L->head;

L->head->pre=q;

L->tail->next=q;

q->pre=L->tail;

L->head=q;

}

void DelFirst(S *L)

{/*删除链表的首结点,并返回*/

8

int i;

LNode *p=L->head->next;

L->tail->next=p;

p->pre=L->tail;

free(L->head);

L->head=p;

}

void Append(S *L1,S *L2)

{ /*将一串结点链接在链表的最后一个结点,并改变链表的尾指针指向新的尾结点*/

LNode *p=L1->tail,*q=L2->head;

while(q->next!=L2->head)

{

p->next=q;

q->pre=p;

p=p->next;

q=q->next;

}

p->next=q;

q->pre=p;

p=q;

p->next=L1->head;

L1->head->pre=p;

L1->tail=p;

}

void InsBefore(S *L)

{ /*将结点插入到链表中某结点之前,并改变指针位置,指向新插入的结点*/

int i;

LNode *p=L->head,*s;

int data=0,Locate=0;

s=(LNode *)malloc(sizeof(LNode));

printf("输入插入数据.\n");

scanf("%d",&data);

s->data=data;

printf("输入插入位置.\n");

scanf("%d",&Locate);

while(p->next!=L->head)

{

第9页共11页9

if(p->data!=Locate)

p=p->next;

else

{

if(p==L->head)

{

s->next=p;

p->pre=s;

s->pre=L->tail;

L->tail->next=s;

L->head=s;

break;

}

else

s->pre=p->pre;

p->pre->next=s;

s->next=p;

p->pre=s;

break;

}

}

if(p->data!=Locate)

printf("错误.\n");

else

s->pre=p->pre;

p->pre->next=s;

s->next=p;

p->pre=s;

;

}

10

第四章调试与操作说明

在系统的制作过程中,我们遇到了很多错误.出现错误时,按提示进行初步定位错误在什么地方进而仔细检查是代码错误还是其他系统性的错误从而根据错误进行修改,操作时一定要注意规范程度免的带来不必要的麻烦,给系统的正常运行又设置了障碍。调试时出现没定义之类的错误,经发现是代码出错.

第五章课程设计总结与体会

由于我的经验不足及阅历颇浅,因此,在该系统的设计方面还有很多不足,比如功能过少,代码不够优化等问题,我会在以后的学习、工作的过程中,根据工作的具体要求不断的修改,完善,争取使该系统慢慢趋向完美。

一般来说,应用程序有两部分组成,一部分是界面,另一部分是数据处理,特别是数据操作。一个典型的数据结构应用程序有数据结构、界面等组成。在设计应用程序时,应仔细考虑每个组件将提供的功能以及该组件与其他组件之间的关系。

谢辞:

在本系统是我第一次尝试这么大的软件编程。在刚开发系统完毕准备开始写论文时我对论文的写法是一片空白,因为在此之前我还没有接触过这一类的文章的写作,并且涉及到我是否能够毕业的问题所以我迟迟无法下手写作。在查了许多资料后,我才开始我的第一篇论文的写作之旅。

参考文献:

[1] 《数据结构(C语言版)》,严蔚敏,吴伟民,清华大学出版社,2007。

[2] 《C程序设计(第三版)》,谭浩强,清华大学出版社,2005.

第11页共11页11

12

C语言链表的建立、插入和删除

数组作为存放同类数据的集合,给我们在程序设计时带来很多的方便,增加了灵活性。但数组也同样存在一些弊病。如数组的大小在定义时要事先规定,不能在程序中进行调整,这样一来,在程序设计中针对不同问题有时需要3 0个大小的数组,有时需要5 0个数组的大小,难于统一。我们只能够根据可能的最大需求来定义数组,常常会造成一定存储空间的浪费。我们希望构造动态的数组,随时可以调整数组的大小,以满足不同问题的需要。链表就是我们需要的动态数组。它是在程序的执行过程中根据需要有数据存储就向系统要求申请存储空间,决不构成对存储区的浪费。 链表是一种复杂的数据结构,其数据之间的相互关系使链表分成三种:单链表、循环链表、双向链表,下面将逐一介绍。 7.4.1 单链表 图7 - 3是单链表的结构。 单链表有一个头节点h e a d,指向链表在内存的首地址。链表中的每一个节点的数据类型为结构体类型,节点有两个成员:整型成员(实际需要保存的数据)和指向下一个结构体类型节点的指针即下一个节点的地址(事实上,此单链表是用于存放整型数据的动态数组)。链表按此结构对各节点的访问需从链表的头找起,后续节点的地址由当前节点给出。无论在表中访问那一个节点,都需要从链表的头开始,顺序向后查找。链表的尾节点由于无后续节点,其指针域为空,写作为N U L L。 图7 - 3还给出这样一层含义,链表中的各节点在内存的存储地址不是连续的,其各节点的地址是在需要时向系统申请分配的,系统根据内存的当前情况,既可以连续分配地址,也可以跳跃式分配地址。 看一下链表节点的数据结构定义: struct node { int num; struct node *p; } ; 在链表节点的定义中,除一个整型的成员外,成员p是指向与节点类型完全相同的指针。在链表节点的数据结构中,非常特殊的一点就是结构体内的指针域的数据类型使用了未定义成功的数据类型。这是在C中唯一规定可以先使用后定义的数据结构。 ?单链表的创建过程有以下几步: 1 ) 定义链表的数据结构。 2 ) 创建一个空表。 3 ) 利用m a l l o c ( )函数向系统申请分配一个节点。 4 ) 将新节点的指针成员赋值为空。若是空表,将新节点连接到表头;若是非空表,将新 节点接到表尾。 5 ) 判断一下是否有后续节点要接入链表,若有转到3 ),否则结束。 ?单链表的输出过程有以下几步 1) 找到表头。

《数据结构》实验报告 设计循环单链表

《数据结构》实验报告 1、实验名称:设计循环单链表 2、实验日期: 2013-3-26 3、基本要求: 1)循环单链表的操作,包括初始化、求数据元素个数、插入、删除、取数据元素; 2)设计一个测试主函数实际运行验证所设计循环单链表的正确性。 4、测试数据: 依次输入1,2,3,4,5,6,7,8,9,10,删除5,再依次输出数据元素。 5、算法思想或算法步骤: 主函数主要是在带头结点的循环单链表中删除第i个结点,其主要思想是在循环单链表中寻找到第i-1个结点并由指针p指示,然后让指针s指向a[i]结点,并把数据元素a[i]的值赋给x,最后把a[i]结点脱链,并动态释放a[i]结点的存储空间。 6、模块划分: 1)头文件LinList.h。头文件LinList.h中包括:结点结构体定义、初始化操作、求当前数据个数、插入一个结点操作、删除一个结点操作以及取一个数据元素操作; 2)实现文件dlb.cpp。包含主函数void main(void),其功能是测试所设计的循环单链表的正确性。

7、数据结构: 链表中的结点的结构体定义如下: typedef struct Node { DataType data; struct Node *next; }SLNode; 8、源程序: 源程序存放在两个文件中,即头文件LinList.h和实现文件dlb.cpp。//头文件LinList.h typedef struct Node { DataType data; struct Node *next; }SLNode; void ListInitiate(SLNode **head) //初始化 { *head=(SLNode *)malloc(sizeof(SLNode)); //申请头结点,由head指示其地址 (*head)->next=*head; }

双向循环链表的建立插入与删除

创建双向循环链表的源代码: #include #include #define OVERFLOW -2 #define ERROR 0 #define OK 1 typedef int status; //双向循环链表的存储结构 typedef struct DuLNode { int data; int Length; struct DuLNode *prior; struct DuLNode *next; } DuLNode,*DuLinkList; //构建一个空的双向循环链表 void InitList(DuLNode **p) { *p=(DuLNode *)malloc(sizeof(DuLNode)); if(*p) { (*p)->next=(*p)->prior=*p; (*p)->Length=0; } else exit(OVERFLOW); } //双向循环链表的创建 void Create(DuLinkList &L,int n) { //输入n个元素的值,建立带头结点的双线循环链表L DuLinkList p=L,q; int i; for(i=1;i<=n;i++) { q=(DuLinkList)malloc(sizeof(DuLNode)); printf("您该输入第%d个元素的值了:",i); scanf("%d",&q->data); p->next =q; q->prior=p; q->next=L; L->prior =q; p=q;

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 #include #define OVERFLOW -2 #define ERROR 0 #define OK 1 typedef int status; //双向循环链表的存储结构 typedef struct DuLNode { int data; int Length; struct DuLNode *prior; struct DuLNode *next; } DuLNode,*DuLinkList; //构建一个空的双向循环链表

单循环链表基本操作

/*1、CreateList( ):创建一个带头结点的空的单循环链表; 2、InsertList( ):输入一组数据,以0表示输入结束, 并依次建立各个元素结点,逐个插入到单循环链表尾 3、DeleteList( ):删除单循环链表的从第i个数据元素开始的m个数据元素,同时释放被删结点空间 4. ListPrint( ):将单向循环链表的数据元素从表头到表尾依次显示 5. DevList( ):将此单循环链表拆分成两个单循环链表,其中一个包含所有的数据元素为偶数的结点, 另一个包含所有的数据元素为奇数的结点.*/ #include #include typedef struct node{ int data; struct node *next; }LNode,*linklist; void createlist(linklist &L) {linklist p=L; p->next=p; } void insertlist(linklist &L) {int x; linklist p=L,q; scanf("%d",&x); while(x!=0) {q=(linklist)malloc(sizeof(LNode)); q->data=x;q->next=NULL; p->next=q; p=q; scanf("%d",&x); } q->next=L; } void printlist(linklist L) {linklist p=L->next ; if(p==L)printf("这是一个空表!\n"); while(p!=L){printf("%2d",p->data);p=p->next;} printf("\n"); } void deletelist(linklist &L,int i,int m) {linklist p=L,q; for(int n=1;nnext; if(p==L)p=p->next; }

C语言_双向循环链表、增删查改、判断回文、排序、论文+代码

数学与计算机学院 课程设计说明书 课程名称: 数据结构与算法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)建立一个单向链表,实现其内元素非递减排序。

数据结构--单链表的插入和删除

单链表的插入和删除实验日志 指导教师刘锐实验时间2010 年10 月11 日 学院数理专业数学与应用数学 班级学号姓名实验室S331-A 实验题目:单链表的插入和删除 实验目的:了解和掌握线性表的逻辑结构和链式存储结构,掌握单链表的基本算法及相关的时间性能分析。 实验要求:建立一个数据域定义为字符串的单链表,在链表中不允许有重复的字符串;根据输入的字符串,先找到相应的结点,后删除之。 实验主要步骤: 1、分析、理解程序(相关程序见附录) 。 2、调试程序,并设计输入字符串数据(如:aa, bb , cc , dd, ee,#),测试程序的如下功能: 不允许重复字符串的插入;根据输入的字符串,找到相应的结点并删除。 3、修改程序: (1)增加插入结点的功能。 (2)将建立链表的方法改为头插入法。 实验结果: 1、不允许重复字符串的插入功能结果如下:

3、删除和插入结点的功能如下:

心得体会: 通过这次实验我学会了单链表的建立和删除,基本了解了线性表的逻辑结构和链式存储结构,掌握了单链表的基本算法,使我受益匪浅。在调试程序的过程中,遇见了一系列的问题,后来在同学的帮助下,修改了几个语句后,终于把它给调试出来了。有时候一个标点符号的问题就可能导致程序无法运行。所以在分析调试程序的时候一定要仔细。 附加程序代码: 1、调试之后的程序如下(其中蓝色字体部分为修改过的): #include"stdio.h" #include"string.h" #include"stdlib.h" #include"ctype.h" typedef struct node //定义结点 { char data[10]; //结点的数据域为字符串 struct node *next; //结点的指针域 }ListNode; typedef ListNode * LinkList; // 自定义LinkList单链表类型 LinkList CreatListR1(); //函数,用尾插入法建立带头结点的单链表ListNode *LocateNode(); //函数,按值查找结点

约瑟夫环问题单循环链表解法讲解

约瑟夫环问题单循环链表解法 Description 约瑟夫环问题;有N个人围成一个环,从第一个人开始报数,报到M的人退出环,并且由他的M值来代替原有的M值,要求输出离开环的顺序。 Input 第一行有2个数,M和N。(0 第二行有 N 个数,表示每个人的 M 值。 Output 按照样例的格式,输出所有人退出环的顺序。 Sample Input 4 6 5 4 2 3 4 2 Sample Output 4,1,2,3,6,5 Source #include"iostream" #include"cstdio" #include"cstdlib" using namespace std; typedef struct cnode{ int label; int data; struct cnode *next; }cnode; int m,n,i,value,j; cnode *p,*q;

int main( { cin>>m>>n; cnode *clist; q=(cnode *malloc(sizeof(cnode; clist=q; for(i=1;i<=n;i++ { //cin>>value; cin>>value; p=(cnode *malloc(sizeof(cnode; //p=new cnode; p->label=i; p->data=value; p->next=NULL; q->next=p; q=p; if(i==nq->next=clist->next; } p=clist; //cout< label< for(i=1;i<=n;i++ { for(j=1;j { p=p->next; } q=p->next; m=q->data;

用双向循环链表求解约瑟夫环

用双向循环链表求解约瑟夫环 学校:东北大学 专业:计算机科学与技术

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;

List-DuLinkedList-将单向循环链表改为双向的

List-DuLinkedList-将单向循环链表改为双向的 2.32 已知有一个单向循环链表,其每个结点中含有三个域:prior,data和next, 其中data为数据域,next为指向后继结点的指针域,prior也为指针域,但它的值为NULL。试编写算法将此单向循环链表改写为双向循环链表,即使prior成为指向前驱结点的指针域#include #include #define N 6 typedef struct DuLNode { //双向循环链表结点 char data; struct DuLNode *prior; struct DuLNode *next; } DuLNode, *DuLinkedList; void createLinkedList(DuLinkedList &L) { //创建双向循环链表(暂时只设NEXT指针)DuLinkedList p; int i; L = (DuLinkedList)malloc(sizeof(DuLNode)); L->data = NULL; L->next = L; L->prior = NULL; for(i=N; i>0; i--) { p = (DuLinkedList)malloc(sizeof(DuLNode)); p->data = getchar(); p->next = L->next; L->next = p; } } void singleToDu(DuLinkedList &L) { //将Prior指针添加上 DuLinkedList p, q; p = L; q = p->next; while(q != L) { q->prior = p; p = q; q = q->next; } q->prior = p; } void printList(DuLinkedList L) { //打印双向循环链表 DuLinkedList p; if(L->prior) { printf("链表的前驱指针存在,现采用反向遍历\n"); p = L->prior; while(p != L) {printf("%c ", p->data); p = p->prior;} } else { printf("链表的前驱指针不存在,将采用正向遍历\n"); p = L->next; while(p != L) {printf("%c ", p->data); p = p->next;} } }

单链表转换成双向循环链表

#include #include struct linklist { int data; struct linklist *pre; struct linklist *next; }; typedef struct linklist List; void One_To_Double(List *head); void main() { int i=1,sum; List *head,*q,*p; head=(List *)malloc(sizeof(List)); head->pre=NULL; printf("输入链表的长度:"); scanf("%d",&sum); p=(List *)malloc(sizeof(List)); p->data=i; head->next=p; p->next=NULL; p->pre=head; i++; while(i<=sum) { q=(List *)malloc(sizeof(List)); q->data=i; q->next=NULL; q->pre=NULL; p->next=q; p=q; i++; } p=head->next; while(p!=NULL) { printf("%d ",p->data); p=p->next; } One_To_Double(head); } void One_To_Double(List *head) {

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); }

双向链表基本操作

双向链表 输入一个双向链表,显示些双向链表并对此双向链表排序运行结果: 源程序: #include #include #include

typedef struct Link/*双向链表结构体*/ { int data; struct Link *lift; struct Link *right; }linkx,*linky; linky Init();/*建立双向链表*/ void PrLink(linky p);/*输出双向链表*/ linky Sort(linky head);/*对双向链表排序*/ linky Swap(linky head,linky one,linky two);/*任意交换双向链表两个结点的地址*/ void main(void) { linky head; head=Init(); head=Sort(head); PrLink(head); } linky (Init())/*建立链表*/ { linky p,q,head; int n=0; head=p=q=(linky)malloc(sizeof(linkx)); printf("排序前的链表: "); scanf("%d",&p->data);/*输入数据*/ head->lift=NULL; n++; while(n!=10)/*一直输入到规定的数字个数停止*/ { q=p;

p=(linky)malloc(sizeof(linkx)); scanf("%d",&p->data);/*输入数据*/ q->right=p; p->lift=q; n++; } p->right=NULL; return(head); } linky Swap(linky head,linky one,linky two)/*任意交换两个结点*/ {linky temp; if(one->lift==NULL&&two->right==NULL)/*首和尾巴的交换*/ { if(one->right==two)/*只有两个结点的情况下*/ { two->right=one; two->lift=NULL; one->lift=two; one->right=NULL; head=two; } else/*有间隔的首尾交换*/ { one->right->lift=two; two->lift->right=one; two->right=one->right; one->lift=two->lift; two->lift=one->right=NULL; head=two;/*尾结点成为头结点*/ }

一步一步写算法(之循环单向链表)

软件英才网软件行业驰名招聘网站 一步一步写算法(之循环单向链表) 前面的博客中,我们曾经有一篇专门讲到单向链表的内容。那么今天讨论的链表和上次讨论的链表有什么不同呢?重点就在这个"循环"上面。有了循环,意味着我们可以从任何一个链表节点开始工作,可以把root定在任何链表节点上面,可以从任意一个链表节点访问数据,这就是循环的优势。 那么在实现过程中,循环单向链表有什么不同? 1)打印链表数据 1void print_data(const LINK_NODE* pLinkNode) 2{ 3 LINK_NODE* pIndex = NULL; 4if(NULL == pLinkNode) 5return; 6 7 printf("%d\n", pLinkNode->data); 8 pIndex = pLinkNode->next; 9while(pLinkNode != pIndex){ 10 printf("%d\n", pIndex->data); 11 pIndex = pIndex ->next; 12 } 13} 以往,我们发现打印数据的结束都是判断指针是否为NULL,这里因为是循环链表所以发生了变化。原来的条件(NULL != pLinkNode)也修改成了这里的(pLinkNode != pIndex)。同样需要修改的函数还有find函数、count统计函数。 2)插入数据 14STATUS insert_data(LINK_NODE** ppLinkNode, int data) 15{ 16 LINK_NODE* pNode; 17if(NULL == ppLinkNode) 18return FALSE; 19 20if(NULL == *ppLinkNode){ 21 pNode = create_link_node(data); 22 assert(NULL != pNode);

C++链表的插入删除及查找

/*从键盘读入一个字符串,把它存入一个链表(每个结点存储1个字符),并按相反的次序将字符串输出到显示屏。 要求至少写出以下方法或函数,初始化链表、插入结点、删除结点、查找、显示、销毁链表*/ #include using namespace std; struct Node { char ch; Node *next; Node *last; }; void CreatList(Node *&head)//创建双向链表,引用参数是表头指针 { char str[100]; cout<<"请输入字符串!"<>str; Node *s,*p; for(int i=0;str[i];i++)//把每个数组元素包含的字符赋给双向链表的一个节点 { s=new Node; s->ch=str[i]; if(head==NULL) { head=s; head->last=NULL; } else {p->next=s;s->last=p;} p=s; } p->next=NULL; return; } void Insert(Node *&head,char ch,int n)//插入节点,n为插入的位置 { Node *s,*p; s=new Node; s->ch=ch; s->next=s->last=NULL; if(head==NULL) { head=s;

return; } if(n==1) { s->next=head; head->last=s; head=s; return; } p=head; for(int i=1;inext!=NULL;i++)//p指向n的前一个位置p=p->next; if(p->next!=NULL) { s->next=p->next; p->next->last=s; p->next=s; s->last=p; return; } p->next=s; s->last=p; return; } int Find(Node *head,char ch)//查找节点,返回节点位置 { Node *p; int i=1; p=head; while(p) { if(p->ch==ch) return i; p=p->next; i++; } return 0; } void Delete(Node *&head,char ch)//删除节点,删除第一个ch字符{ Node *p; if(head==NULL)

双向循环链表list

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 #include #define OVERFLOW -2 #define ERROR 0 #define OK 1 typedef int status; //双向循环链表的存储结构 typedef struct DuLNode { int data; int Length; struct DuLNode *prior; struct DuLNode *next; } DuLNode,*DuLinkList; //构建一个空的双向循环链表 void InitList(DuLNode **p) { *p=(DuLNode *)malloc(sizeof(DuLNode)); if(*p) { (*p)->next=(*p)->prior=*p; (*p)->Length=0; } else exit(OVERFLOW); } //双向循环链表的创建 void Create(DuLinkList &L,int n) { //输入n个元素的值,建立带头结点的双线循环链表L DuLinkList p=L,q; int i; for(i=1;i<=n;i++) { q=(DuLinkList)malloc(sizeof(DuLNode)); printf("您该输入第%d个元素的值了:",i); scanf("%d",&q->data);

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≤表长

在单向链表中删除偶元素结点

实验报告名称:线性表及其应用 实验目的: 1.掌握单向链表的存储特点及其实现。 2.掌握单向链表的插入、删除算法及其应用算法的程序实现。实验报告(实验内容、实验步骤、实验运行结果分析、实验小结) 实验内容: 在单向链表中删除所有的偶数元素结点。 #include #include #define NULL 0 typedef struct node //定义链表元素结构体 { int data; struct node *next; }node,*link; link createlink(int n) //建链表 { int i,x; link p,q,head; p=(link)malloc(sizeof(node)); //分配空间 p->next=NULL; q=p; head=p; printf("请输入线性表L的元素:\n"); for(i=1;i<=n;i++) {scanf("%d",&x); p=(link) malloc(sizeof(node)); p->data=x; p->next=NULL; q->next=p; q=p; } return(head); //返回头节点指针 } void print(link head) //输出链表 { printf("线性表L的元素为:\n"); link p; p=head->next; while(p) {printf("%3d",p->data); p=p->next; } printf("\n");

} void shanou(link head) { link p,q; q=head; p=head->next; while(p) { if((p->data%2!=0)) { p=p->next; q=q->next; } else {q->next=p->next; p=p->next; } } printf("shanou后的链式表为:\n"); p=head->next; while(p) {printf("%3d",p->data); p=p->next; } printf("\n"); } void main() {link head; int n; printf("请输入线性表L的长度:\n"); scanf("%d",&n); head=createlink(n); print(head); shanou(head); } 运行结果:

数据结构C语言版 循环链表表示和实现

数据结构C语言版循环链表表示和实现.txt37真诚是美酒,年份越久越醇香浓烈;真诚是焰火,在高处绽放才愈显美丽;真诚是鲜花,送之于人,手有余香。/* 数据结构C语言版循环链表表示和实现 P35 编译环境:Dev-C++ 4.9.9.2 日期:2011年2月10日 */ #include #include #include typedef int ElemType; // 线性表的单链表存储结构 typedef struct LNode { ElemType data; struct LNode *next; }LNode, *LinkList; // 要好好区分什么是头结点((*L)->next),尾结点(*L),以及第一个结 // 点(*L)->next->next,设立尾指针的单循环链表(头尾相接,即头结点 // 与尾结点是一样的,它们都没数据域. // 构造一个空的循环链表L int InitList_CL(LinkList *L) { // 产生头结点,并使L指向此头结点 *L = (LinkList)malloc(sizeof(struct LNode)); if(!*L) exit(0); // 指针域指向头结点,这样就构成了一个循环,空表循环,*L为表尾 (*L)->next = *L; return 1; } // 销毁循环链表L int DestroyList_CL(LinkList *L) { LinkList q, p = (*L)->next; // p指向头结点 while(p != *L) // 没到表尾,*L为表尾 { q = p->next; free(p);

单循环链表解决Josephus问题

//假设n个人围坐在圆桌周围,现在从第s个开始报数,数到m的那个人出局,下一个开始重新报数,如此反复,知道所有的人都出局为止。 #define _CRT_SECURE_NO_WARNINGS #include #include typedef struct cirlist{ int data; struct cirlist *next; }CirNode, *Cirlist; Cirlist CreateList_L(Cirlist L, int n)//正序输出链表; { Cirlist p = NULL, s; L = (Cirlist)malloc(sizeof(CirNode)); L->next = L;//建立头结点; s = L;//用一个中间变量承接L,保持L的地址不变; printf("输入链表的值:\n"); for (int i = 0; i < n; i++)//尾插法 { p = (Cirlist)malloc(sizeof(CirNode)); scanf("%d", &p->data); s->next = p; s = p; } p->next = L; return L;//如果不用s中间变量,利用尾插法L的地址是变化的; } void jopus(Cirlist L, int n, int s, int m) { Cirlist p = L->next, q = L; int i, j; for (i = 1; i < s; i++) { p = p->next; } for (i = 0; i < n; i++) { for (j = 1; j < m; j++) { q = p; p = p->next; if (p == L) { q = p; p = p->next;

循环双向链表

#include #include "Dlink.h" int main(void) { DLink *L; int i = 0; ElemType e = '0'; //认真体会C语言拷贝传递的思想 InitList(&L); InsElem(L, 'a', 1); InsElem(L, 'b', 2); InsElem(L, 'c', 3); InsElem(L, 'd', 4); InsElem(L, 'e', 5); printf("线性表"); DispList(L); printf("长度:%d/n",GetLength(L)); i = 3; GetElem(L, i, &e); printf("第%d个元素:%c/n", i, e); e = 'a'; printf("元素%c是第%d个元素/n", e, Locate(L, e)); i = 4; printf("删除第%d个元素/n", i); DelElem(L, i); printf("线性表:"); DispList(L); /**/ return 0; } [cpp] view plaincopyprint? #ifndef DLINK #define DLINK typedef char ElemType;

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 #include "Dlink.h" #include /************************************************ ** 函数名:void InitList(DLink **L) ** 功能:初始化线性表运算 ** 描述:无 ** 作者:/***/ *************************************************/ void InitList(DLink **L) { *L = (DLink *)malloc(sizeof(DLink)); (*L)->prior = (*L)->next = *L; } /************************************************ ** 函数名:int getLength(DLink *L) ** 功能:获取链表的长度 ** 描述:无 ** 作者:/***/ *************************************************/ int GetLength(DLink *L)

相关文档
相关文档 最新文档