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

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

学校：东北大学

专业：计算机科学与技术

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;

struct DuLNode *next;

}DuLNode,*DuLinkList; //定义双向循环链表

int InitList_Dul(DuLinkList &L) //建立一个只含头结点的空双向循环链表{

L=(DuLinkList) malloc(sizeof(DuLNode));

if(!L) return ERROR;

L->data=0;

L->next=L;

L->prior=L;

return OK;

}

int CreateList_DuL(DuLinkList &L,int n) //建立一个带头结点的含n个元

素的双向循环链表L {

DuLinkList p,q;

int i;

q=L;

for(i=0;i

{

p=(DuLinkList)malloc(sizeof(DuLNode));

p->data=i+1; //m值的自动获取

p->next=q->next;

q->next=p;

p->prior=q;

L->prior=p;

q=p;

}

return OK;

}

int ListDelete_DuL(DuLinkList &L,DuLinkList x) //删除指针x指向的结点{

x->prior->next=x->next;

x->next->prior=x->prior;

free(x);

return 0;

}

int main()

{

int n,m;

int i=1;

cin>>n;

DuLinkList S;

InitList_Dul(S);

CreateList_DuL(S,n);

cin>>m;

DuLinkList a=S->next;//a指向第一个结点（不是头结点）

if(m%2==1) //奇数次顺时针转

{

while(!(S->next==S->prior)) //当剩下最后一个人时（此时还有头结点）时退出循环

{

if(i==m)

{

DuLinkList p;

if(a->data==0)

a=a->next;//跳过头结点

p=a;

a=a->next;

cout<data<<" ";

ListDelete_DuL(S,p); //删除节点p

i=1;

}

else

{

if(a->data==0)

a=a->next;//跳过头结点

a=a->next;

i++;

}

}

cout<next->data<

free(S->next);

free(S); //释放除头结点和最后一个结点

}

else //偶数次逆时针转

{

while(!(S->next==S->prior)) //当剩下最后一个人时（此时还有头结点）

时退出循环{

if(i==m)

{

DuLinkList p;

if(a->data==0)

a=a->prior; //跳过头结点

p=a;

a=a->prior;

cout<data<<" ";

ListDelete_DuL(S,p); //删除节点p

i=1;

}

else

{

if(a->data==0)

a=a->prior; //跳过头结点

a=a->prior;

i++;

}

}

cout<next->data<

free(S->next);

free(S); //释放除头结点和最后一个结点

}

return 0;

}

5.调试分析

1.遇到的问题：

（1）开始对双向循环链表的删除操作的指针改变顺序出现了问题，导致删除结点时出现了错误；

（2）双向循环链表中带有头结点，而头结点的数据域是空的（该程序中设为0），因此在对双向循环链表进行遍历和删除操作时，必须判断该结点是否是头结点，如果是，必须跳过该结点；

2.收获：

（1）通过对双向循环链表的建立、遍历、删除等操作的实现，对指针和链表了解得更加透彻，掌握得更加牢固；

（2）对头结点问题的特殊处理，使自己解决问题的能力有了提升。

6.测试结果

说明：若m是奇数，顺时针遍历双向循环链表；若m是偶数，逆时针遍历双向循环链表。

附录：程序源代码

/*****************************************************************************

约瑟夫环问题求解

东北大学计算机科学与技术

*****************************************************************************/ #include

#include

#include

using namespace std;

# define OK 1

# define ERROR 0

typedef struct DuLNode

{

int data;

struct DuLNode *prior;

struct DuLNode *next;

}DuLNode,*DuLinkList; //定义双向循环链表

int InitList_Dul(DuLinkList &L) //建立一个只含头结点的空双向循环链表{

L=(DuLinkList) malloc(sizeof(DuLNode));

if(!L) return ERROR;

L->data=0;

L->next=L;

L->prior=L;

return OK;

}

int CreateList_DuL(DuLinkList &L,int n) //建立一个带头结点的含n个元素的双向循环链表L {

DuLinkList p,q;

int i;

q=L;

for(i=0;i

{

p=(DuLinkList)malloc(sizeof(DuLNode));

p->data=i+1; //m值的自动获取

p->next=q->next;

q->next=p;

p->prior=q;

L->prior=p;

q=p;

}

return OK;

}

int ListDelete_DuL(DuLinkList &L,DuLinkList x) //删除指针x指向的结点

{

x->prior->next=x->next;

x->next->prior=x->prior;

free(x);

return 0;

}

int main()

{

while(1){ //主程序循环执行

int n,m;

int i=1;

cout<<"请输入竞赛者人数n:"<

cin>>n;

DuLinkList S;

InitList_Dul(S);

CreateList_DuL(S,n);

cout<<"请输入正整数m:"<

cin>>m;

cout<<"("<

DuLinkList a=S->next;//a指向第一个结点（不是头结点）

if(m%2==1) //奇数次顺时针转

{

while(!(S->next==S->prior)) //当剩下最后一个人时（此时还有头结点）时退出循环{

if(i==m)

{

DuLinkList p;

if(a->data==0)

a=a->next;//跳过头结点

p=a;

a=a->next;

cout<data<<" ";

ListDelete_DuL(S,p); //删除节点p

i=1;

}

else

{

if(a->data==0)

a=a->next;//跳过头结点

a=a->next;

i++;

}

}

cout<next->data<

free(S->next);

free(S);//释放除头结点和最后一个结点

}

else//偶数次逆时针转

{

while(!(S->next==S->prior))//当剩下最后一个人时（此时还有头结点）时退出循环{

if(i==m)

{

DuLinkList p;

if(a->data==0)

a=a->prior;//跳过头结点

p=a;

a=a->prior;

cout<data<<" ";

ListDelete_DuL(S,p); //删除节点p

i=1;

}

else

{

if(a->data==0)

a=a->prior;//跳过头结点

a=a->prior;

i++;

}

}

cout<next->data<next);

free(S);//释放除头结点和最后一个结点

}

} //while(1)

return 0;

}

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

《数据结构》实验报告 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）建立一个单向链表，实现其内元素非递减排序。

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

约瑟夫环问题单循环链表解法 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);

双向循环链表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≤表长

数据结构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;

主要的数据类型有两个带头结点的双向循环链表

主要的数据类型有两个带头结点的双向循环链表，这两个链表与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 #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)

单循环链表解决约瑟夫问题

//用单循环链表解决约瑟夫问题 #include using namespace std; typedef struct Lnode { int data; Lnode *next; }Lnode; class JosephusCircle { public: void creat_list(); void Josephus(); private: int n; int s; int m; Lnode *head; }; void JosephusCircle::creat_list() //初始化 { cout<<"请依次输入，约瑟夫圈人数、报数起始位置、报几个数："<>n>>s>>m; if(m==0) { cout<<"报数的个数不许为0！"; cout<next=head; tail=head; for(int i=0;idata=(i+1); tail->next=p; tail=p; p->next=head->next; } }

void JosephusCircle::Josephus() { Lnode *p=head->next; Lnode *q=head; //q指针紧随其后 int j=1; while (j!=s) //找到报数起点 { p=p->next; q=q->next; ++j; } while (p!=q) { for(int i=0;inext; q=q->next; } cout<data<<' '; //输出前n-1个出圈人编号 p=p->next; //删除节点 q->next=p; } cout<data; //输出最后一个出圈人编号} void main() { JosephusCircle Jose; Jose.creat_list(); cout<<"出圈顺序为："<

List-DuLinkedList-双向循环链表-Locate(L,x)

List-DuLinkedList-双向循环链表-Locate(L,x) 2.38 设有一个双向循环链表，每个结点中除了有prior、data和next三个域外，还增设了一个访问频度域freq。在链表被启用之前，频度域freq的值均初始化为零，而每当对链表进行一次Locate(L, x)的操作后，被访问的结点（即元素值等于x的结点）中的频度域freq的值便增加1，同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的Locate操作的算法。#include #include typedef struct LinkNode { //双向循环链表 char data; struct LinkNode *prior; struct LinkNode *next; int freq; } DuLNode, *DuLinkedList; void createLinkedList(DuLinkedList &L, int n) { //创建双向循环链表 int i; DuLinkedList p; L = (DuLinkedList)malloc(sizeof(DuLNode)); L->next = L->prior = L; L->freq = 0; for(i=n; i>0; i--) { p = (DuLinkedList)malloc(sizeof(DuLNode)); scanf("%c",&(p->data)); p->freq = 0; p->prior = L; p->next = L->next; L->next->prior = p; L->next = p; } } void printList(DuLinkedList L) { //打印双向循环链表 DuLinkedList p = L->next; while(p != L) { printf("节点值%c，使用频率为%d。\n", p->data, p->freq); p = p->next; } } void locate(DuLinkedList &L, char x) { //查找位置，并变换位置 DuLinkedList q , p = L->next; while(p != L && p->data != x) p = p->next; if(p == L) return ; p->freq += 1; q = p->prior; while(q->freq < p->freq && q != L) { p->prior = q->prior; q->next = p->next; q->prior->next = p; p->next->prior = q; q->prior = p; p->next = q; q = p->prior; } } void main() { DuLinkedList L; int n; printf("请输入节点的个数："); scanf("%d", &n);