循环链表是首尾相连的单链表

?循环链表是首尾相连的单链表。

?循环链表最后一个结点的link指针不为NULL，而是指向了表的前端。

?为简化操作，在循环链表中常使用头结点。

?循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地

址。

?带头结点循环链表操作与单链表操作类似，仅判断当前结点是否为尾结点不同：

p!=null p!=L

3. 一元多项式的相加算法

?扫描两个多项式，若都未检测完：

◆若当前被检测项指数相等，系数相加。若未变成0，则将结果加到结果多

项式。

◆若当前被检测项指数不等，将指数小者加到结果多项式。

?若一个多项式已检测完，将另一个多项式剩余部分复制到结果多项式。

多项式相加算法

void polyadd(Polylist polya, Polylist polyb)

/*此函数用于将两个多项式相加，然后将和多项式存放在多项式polya中，并将多项式ployb 删除*/

{

Polynode *p, *q, *pre, *temp;

int sum;

p=polya->next; /*令p和q分别指向polya和polyb多项式链表中的第一个结点*/ q=polyb->next;

pre=polya; /* pre指向和多项式的尾结点*/

while (p!=NULL && q!=NULL) /*当两个多项式均未扫描结束时*/

{

if (p->exp < q->exp)

/*如果p指向的多项式项的指数小于q的指数，将p结点加入到和多项式中*/ {

pre->next=p;

pre=p;

p=p->next;

}

else

实验二 链表操作实现

实验二链表操作实现 实验日期： 2017 年 3 月 16 日 实验目的及要求 1. 熟练掌握线性表的基本操作在链式存储上的实现； 2. 以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点； 3. 掌握线性表的链式存储结构的定义和基本操作的实现； 4. 通过本实验加深对C语言的使用（特别是函数的参数调用、指针类型的应用）。 实验容 已知程序文件linklist.cpp已给出学生身高信息链表的类型定义和基本运算函数定义。 （1）链表类型定义 typedef struct { int xh; /*学号*/ float sg; /*身高*/ int sex; /*性别，0为男生，1为女生*/ } datatype; typedef struct node{ datatype data; /*数据域*/ struct node *next; /*指针域*/ } LinkNode, *LinkList; （2）带头结点的单链表的基本运算函数原型 LinkList initList();/*置一个空表（带头结点）*/ void createList_1(LinkList head);/*创建单链表*/ void createList_2(LinkList head);/* 创建单链表*/ void sort_xh(LinkList head);/*单链表排序*/ void reverse(LinkList head);/*对单链表进行结点倒置*/ void Error(char *s);/*自定义错误处理函数*/ void pntList(LinkList head);/*打印单链表*/ void save(LinkList head,char strname[]);/*保存单链表到文件*/

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

《数据结构》实验报告 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; }

实现单链表的各种基本运算

实现单链表的各种基本运算 一、实验目的 了解单链表表的结构特点及有关概念，掌握单链表的各种基本操作算法思想及其实现。 二、实验内容 编写一个程序，实现顺序表的各种基本运算： 1、初始化单链表； 2、单链表的插入； 3、单链表的输出； 4、求单链表的长度 5、判断单链表是否为空； 6、输出单链表的第i位置的元素； 7、在单链表中查找一个给定元素在表中的位置； 8、单链表的删除； 9、释放单链表 三、算法思想与算法描述简图

主函数main void InitList(LinkList*&L) 初始化单链表L void DestroyList(LinkList*&L)//释放单链表L int ListEmpty(LinkList*L)//判断单链表L是否为空集 int Listlength(LinkList*L)//返回单链表L的元素个数 void DispList(LinkListt*L)//输出单链表L int GetElem(LinkList*L,int i,char e)/*ElemType e)获 取单链表L中的第i个元素*/ int LocateEmpty(LinkList*L,char e)/*ElemType e)在单 链表L中查找元素e*/ int ListInsert(LinkList*&L,int i,char e)/*ElemType e) 在单链表中第i个位置上插入元素e*/ int ListDelete(LinkList*&L,int i,char &e)/*ElemType e)在单链表L中删除第i个元素*/

四、实验步骤与算法实现 #include #include typedef char ElemType; typedef struct LNode//定义单链表 { ElemType data; struct LNode *next; }LinkList; void InitList(LinkList*&L) { L=(LinkList*)malloc(sizeof(LinkList));//创建头结点 L->next=NULL;//头结点赋值为空 } void DestroyList(LinkList*&L)//销毁单链表（释放单链表L占用的内存空间即逐一释放全部结点的空间） { LinkList*p=L,*q=p->next; while(q!=NULL) {free(p); p=q; q=p->next;} free(p); } int ListEmpty(LinkList*L)//判线性表是否为空表ListEmpty(L) { return(L->next==NULL);}//若单链表L没有数据结点,则返回真,否则返回假。 int ListLength(LinkList*L)//求线性表的长度ListLength(L) { LinkList*p=L;int i=0; while(p->next!=NULL)

数据结构课程设计单链表操作

《数据结构课程设计》报告 题目：单链表操作 专业：计算机科学与技术 班级： 单链表操作 针对带头结点的单循环链表，编写实现以下操作的算法函数。

实现要求： ⑴单链表建立函数create：先输入数据到一维数组A[M]中，然后根据一维 数组A[M]建立一个单循环链表，使链表中个元素的次序与A[M]中各元素的次序相同，要求该函数的时间复杂度为O(m)； ⑵定位查找函数Locate：在所建立的单循环链表中查找并返回值为key的 第1个元素的结点指针；若找不到，则返回NULL； ⑶求出该链表中值最大和次大的元素值，要求该算法的时间复杂度为O(m)， 最大和次大的元素值通过指针变量带回，函数不需要返回值； ⑷将链表中所有值比key(值key通过形参传入)小的结点作为值为key的结 点前驱，所有值比key大的结点作为值为key的结点后继，并尽量保持原有结点之间的顺序，要求该算法的时间复杂度为O(m); ⑸设计一个菜单，具有上述处理要求和退出系统功能。 ⒈本人完成的工作： 一、定义结构体：LNode 二、编写以下函数： （1）建立单循环链表 （2）建立定位查找函数 （3）求出链表中最大和次大值 （4）将链表中的值和输入的Key比较，小的作为key前驱结点，大的作为key 的后继结点 三、设计具有上述处理要求和退出系统菜单 ⒉所采用的数据结构：单链表 数据结构的定义： typedef struct Node //定义结点的结构体 { DataType data; //数据域 struct Node *next; //指针域

}LNode; //结点的类型 ⒊所设计的函数 （1）Create(void) LNode *Create(void) //建立单循环链表，链表头结点head作为返回值{ int i,j,n,A[M]; //建立数组A【M】 LNode *head,*p,*move; head=(LNode*)malloc(sizeof(LNode)); //创建空单循环链表head->next=head; move=head; printf("请输入数组元素的个数："); //输入数组 scanf("%d",&n); printf("请输入数组："); for(i=0;idata=A[j]; p->next=move->next; move->next=p; move=move->next; } return head; //返回头指针

数据结构循环链表插入和删除源代码代码

typedef struct LNode//结点类型 { int data;//数值域 struct LNode *next;//指针域 }CrLNode,*CrLinklist; #include"Base.h" #include"construct.h" #include"circulate_operation.c" int main() { CrLinklist L; int i,choice,n,e; printf("请输入链表元素个数:"); scanf("%d",&n); L=Initlist_L(n); printf("请选择执行语句，选择输入1，执行插入操作或选择输入2，执行删除操作:"); scanf("%d",&choice); switch(choice) { case 1: { printf("请输入插入元素的位置:"); scanf("%d",&i); if(i<=0||i>n) printf("您输入的值不合法"); else printf("请输入插入元素的值："); scanf("%d",&e); L=ListInsert_L(L,i,e); printf("插入后的链表为："); printlist_L(L); };break; case 2: { printf("请输入删除元素的位置:"); scanf("%d",&i); if(i<=0||i>n) printf("您输入的值不合法"); else L=ListDelete_L(L,i); printf("删除后的链表为");

printlist_L(L); };break; } } CrLinklist Initlist_L(int n)//创建带头结点的单链表 { CrLinklist L; CrLinklist P; int i; L=(CrLinklist)malloc(sizeof(CrLNode)); L->next=L;/* 先建立一个带头结点的单链表*/ printf("请输入%d个数据\n",n); for(i=n;i>0;--i) { P=(CrLinklist)malloc(sizeof(CrLNode)); /* 生成新结点*/ scanf("%d",&P->data); /* 输入元素值*/ P->next=L->next; /* 插入到表头*/ L->next=P; } return L; } CrLinklist ListInsert_L(CrLinklist L,int i,int e)//单链表的插入 { CrLinklist P,S; int j; P=L; j=0; while(P&&jnext; ++j; }//寻找第i-1个节点 if(!P||j>i-1) return ERROR; S=(CrLinklist)malloc(sizeof(CrLNode));//生成新节点 S->data=e; S->next=P->next;//插入到S中 P->next=S; return L; } CrLinklist ListDelete_L(CrLinklist L,int i)//单链表的删除 { CrLinklist P,S;

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

软件英才网软件行业驰名招聘网站 一步一步写算法（之循环单向链表） 前面的博客中，我们曾经有一篇专门讲到单向链表的内容。那么今天讨论的链表和上次讨论的链表有什么不同呢？重点就在这个"循环"上面。有了循环，意味着我们可以从任何一个链表节点开始工作，可以把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);

第三章 单链表 题目和答案

第2章自测卷答案 一、填空 1.顺序表中逻辑上相邻的元素的物理位置相互相邻。单链表中逻辑上相邻的元素的物理位置不 相邻。 2.在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点值域指示。 3．在n个结点的单链表中要删除已知结点*p，需找到它的地址。 二、判断正误（在正确的说法后面打勾，反之打叉） 1. 链表的每个结点中都恰好包含一个指针。X 2. 链表的物理存储结构具有同链表一样的顺序。X 3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。X 4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。Y 5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。Y 6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。X 7. 线性表在物理存储空间中也一定是连续的。X 8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。X 9. 顺序存储方式只能用于存储线性结构。X 10. 线性表的逻辑顺序与存储顺序总是一致的。X 三、单项选择题 （A）1. 链接存储的存储结构所占存储空间： （A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 （B）只有一部分，存放结点值 （C）只有一部分，存储表示结点间关系的指针 （D）分两部分，一部分存放结点值，另一部分存放结点所占单元数 （B）2. 链表是一种采用存储结构存储的线性表； （A）顺序（B）链式（C）星式（D）网状 （D）3. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址: （A）必须是连续的（B）部分地址必须是连续的 （C）一定是不连续的（D）连续或不连续都可以 （B）4．线性表Ｌ在情况下适用于使用链式结构实现。 （Ａ）需经常修改Ｌ中的结点值（Ｂ）需不断对Ｌ进行删除插入 （Ｃ）Ｌ中含有大量的结点（Ｄ）Ｌ中结点结构复杂 （C）5．单链表的存储密度 （Ａ）大于1；（Ｂ）等于1；（Ｃ）小于1；（Ｄ）不能确定 （A）6、在单链表的一个结点中有个指针。

数据结构实验 建立双向循环链表以及插入删除操作

实验一 要求：①建立双向循环链表 ②实现链表的插入、删除 运行程序点此处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≤表长

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

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

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

向量法求解Josephus问题 智能一班林潇 2220101468 一．实验题目描述 Josephus问题可描述如下： 设有n个人围成一个环，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人从新开始报数，数到第m的人又出列，如此重复，直至所有人均出列为止。求这些人出列的顺序。 二．实验目的 熟练掌握线性表的链表实现基本操作。 三．实现功能 以循环单链表为存储结构，求解Josephus问题。 四．算法步骤 编写一个独立的函数模块求解Josephus问题，该函数仅通过参数与外界进行数据交换，不使用其它非局部变量，实现方案应具有良好的健壮性。另编写一个主函数作为驱动，在主函数中处理数据的输入与输出。 五．程序结构描述 程序主要包括一个驱动功能的主函数，包括要排列数组元素的输入，开始报数的位置，所报数字的输入。还有一个独立函数模块来实现Josephus问题，主函数通过调用该函数来实现元素的出列，并将出列元素按顺序重新存入数组，并将出列元素按顺序输出。 六．程序代码 #define N 10 #include #include typedef struct LNode{//建立节点类型 int message; struct LNode *next; }LNode,*LinkList; void Josephus(LinkList L,int s,int m,int n,int e,int a[]); void main(){ int i,s,m,e;

int a[10]; printf("请输入Josephus环的元素"); //输入组成Josephus环的元素 for(i=0;i<10;i++) scanf("%d",&a[i]); printf("请输入开始报数位置及所报数字"); //输入开始报数位置及所报数字 scanf("%d %d",&s,&m); LinkList L;//建立单循环连的头结点 L=(LinkList)malloc(sizeof(LNode)); L->message=a[0]; L->next=NULL; Josephus(L,s,m,N,e,a); } void Josephus(LinkList L,int s,int m,int n,int e,int a[]){ LinkList p,q; int i,j; //将组成Josephus环的元素储存到单链中 for(i=n-1;i>0;i--){ p=(LinkList)malloc(sizeof(LNode)); p->message=a[i]; p->next=L->next; L->next=p; } LinkList H; H=L; for(i=0;inext; H->next=L;//尾部节点的指针指向头结点 p=L; for(i=1;i

c++的循环链表实现的约瑟夫环问题

#include"iostream.h" #include"stdlib.h" #define maxsize 100//最大人数 struct Node{ int no;//第几个人 Node*next; }; class Josephring { private: Node*head; int totalnum; public: Josephring() { head=new Node; head->no=1; head->next=head; } void CreateJosephus(int n);//创建m个节点的链表 void show(); void Joseph(int k,int m);//约瑟夫环问题求解,从第k个人开始数数，数到m的人出列}; void Josephring::CreateJosephus(int n) { Node*s=head; totalnum=n; for(int i=2;i<=n;i++) { Node*w=new Node; w->no=i; w->next=head; s->next=w; s=w; } } void Josephring::show() { cout<no<<"\t"; Node*q=head->next; while(q!=head) {

cout<no<<"\t"; q=q->next; } } void Josephring::Joseph(int k,int m) { Node*p=head;//工作指针 int j=1;//计数器 while(j!=k) { j++; p=p->next;//指针后移 }//找到第k个人开始数1的那个人 for(int i=1;i<=totalnum;i++) { Node*w=p;//指针w指向开始数1的第k个人 Node*q=NULL;//w的前驱指针 j=1;//计数器，为了找到数m的那个人 while(j!=m) { j++; q=w; w=w->next; }//找到了数m的那个人 cout<no<<"\t";//输出此人的编号 q->next=w->next;//此人出列并删除节点 p=q->next; } } int main() { int people,k,m;//圆桌上的总数,k为从第几个人开始数,m为数到m的那个人出列Josephring josephus; cout<<"请输入圆桌上人的总数(10~100): "; cin>>people; while(people>maxsize||people<0) { cout<<"超出范围,请重新输入: "; cin>>people; cout<

单循环链表基本操作

单循环链表基本操作 /* (程序名) */ #include #include #include #include #include #include /* malloc()等*/ #include /* INT_MAX等*/ #include /* EOF(=^Z或F6),NULL */ #include /* atoi() */ #include /* eof() */ #include /* floor(),ceil(),abs() */ #include /* exit() */ /* 函数结果状态代码*/ #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 /* #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行*/ typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等*/ typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */ typedef int ElemType; /* c2-2.h 线性表的单链表存储结构*/ struct LNode { ElemType data; struct LNode *next; }; typedef struct LNode *LinkList; /* 另一种定义LinkList的方法*/ //////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////// //////// 单循环链表基本操作 //////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////// /* bo2-4.c 设立尾指针的单循环链表(存储结构由c2-2.h定义)的12个基本操作*/ Status InitList_CL(LinkList *L) { /* 操作结果：构造一个空的线性表L */ *L=(LinkList)malloc(sizeof(struct LNode)); /* 产生头结点,并使L指向此头结点*/ if(!*L) /* 存储分配失败*/ exit(OVERFLOW);

建立非循环单链表的过程

建立非循环单链表的过程 因为链表是离散存储的，每一个结点之间通过指针来链接。所以要想创建一个非循环单链表，应该是先确定一个头结点（里面不存放任何有效数据），再确定一个尾结点（指针域为空，表明链表结束），然后在中间不断的用循环语句开辟一个个的新结点（用malloc 函数实现）。如下图： 我们先假定每一个结点的类型是： Struct Node { Int data; Struct Node *pNext; }; 为简单起见，我们规定结点中只存储整型数据。 现在让我们开始。 第一步：建立头结点和尾结点 因为链表创建的过程是不断的在头结点和尾结点之间插入新的结点。如果只有一个头结点的话，操作起来很不方便。 先定义两个指针变量： 然后用malloc 函数开辟一个结点。因为此时链表中只有一个结点，所以这个结点当然是头结点。 现在头结点有了，并且头指针指向了它，还需不需要另外创建一个尾结点呢？不需要。为什么呢？我们只要让头指针和尾指针同时指向这个结点就可以了。也就是说，在链表中只有一个结点的情况时，这个结点既可以看作是头结点，同时也可以看作是尾结点。当然，因为尾结点最后没有结点了，所以我们还要让尾结点的指针域为空。 好，头结点和尾结点都有了，并且都有一个指针变量指向了它们。那么现在就要开始创建新的结点了。 如何创建？当然要用循环。用for 循环或者while 循环都可以。喜欢哪样用哪样。我们就用for 循环吧。 要用循环，首先要解决两个问题。1、我要创建几个结点2、每个结点的值如何存储这些都好解决，无非是定义变量。 头结点尾结点 ····· 新结点1新结点2新结点n

下面开始循环： 当然，这段代码还不够。最重要的功能还没有。我们还需要用malloc 函数动态开辟结点，并且让新开辟的结点和头结点与尾结点链接起来。下面把代码补充完整。 下面用图来解释一下这段代码： 简单起见，我们假定num=2,那for 循环就要循环两次。 第一次循环： pHead pTail 循环之前的链表的情况是这样的，这个结点既是头结点也是尾结点

实验二 链表操作实现

实验二链表操作实现 实验日期：2017 年 3 月16 日 实验目的及要求 1. 熟练掌握线性表的基本操作在链式存储上的实现； 2. 以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点； 3. 掌握线性表的链式存储结构的定义和基本操作的实现； 4. 通过本实验加深对C语言的使用（特别是函数的参数调用、指针类型的应用）。实验内容 已知程序文件已给出学生身高信息链表的类型定义和基本运算函数定义。 （1）链表类型定义 typedef struct { int xh; /*学号*/ float sg; /*身高*/ int sex; /*性别，0为男生，1为女生*/ } datatype; typedef struct node{ datatype data; /*数据域*/ struct node *next; /*指针域*/ } LinkNode, *LinkList; （2）带头结点的单链表的基本运算函数原型 LinkList initList();/*置一个空表（带头结点）*/ void createList_1(LinkList head);/*创建单链表*/ void createList_2(LinkList head);/* 创建单链表*/ void sort_xh(LinkList head);/*单链表排序*/ void reverse(LinkList head);/*对单链表进行结点倒置*/ void Error(char *s);/*自定义错误处理函数*/ void pntList(LinkList head);/*打印单链表*/ void save(LinkList head,char strname[]);/*保存单链表到文件*/

C语言单向循环链表实现实现约瑟夫环

C语言实现约瑟夫环问题------单向循环链表实现 问题描述： 有n个人围成一圈进行报数游戏，从第一个人开始报到m的人出圈，接下来有从下一个人开始，。。。。。。。一次这样往复，直到最后一个人也出圈，求他们的出圈顺序？（例如8个人，凡报3的人出圈，则他们出圈顺序是3 ，6, 1，，5 ，2 ，8，4 ，7） #include #include typedef struct node{ int value; struct node *next; }NODE; //*********************建立循环链表(尾插法建立)***********// NODE *createlink(int number)

{ NODE *head=NULL,*p=NULL,*q=NULL; int i=1; head=(struct node*)malloc(sizeof(struct node)); //***建立第一个节点***// head->value=i; p=head; for(i=2;i<=number;i++) //***建立剩下的number-1节点****// { q=(struct node*)malloc(sizeof(struct node)); if(q==0) return 0; p->next=q; p=q; p->value=i; } p->next=head; return head; } //*****************建立约瑟夫环********************// void jose(NODE *p,int number,int n) {

循环单链表合并实验报告

实验题目：两个有序循环链表的顺序与逆序合并 实验目的: 掌握循环单链表的建立与输出，掌握循环单链表元素的删除与插入，熟悉C语言函数调用的相关知识。 实验内容：将两个带头结点的有序循环链表（链表中的元素设为从小到大排列），分别按照从小到大和从大到小的顺序合并成一个带头结点的有序循环链表并输出。 一．需求分析 1．本演示程序中，分别要求输入两个链表的长度及每个节点的数据域（注：均要求是整型数据），数据之间要求以空格分开，输入完毕后键入回车键（程序执行时均会有输入提醒）。链表长度数据的输入范围为0—4294967295，链表节点数据域的数据输入范围为-2147483648-2147483647。 2．本演示程序以用户和计算机的对话方式执行，即在计算机终端显示“提示信息”之后，由用户在键盘上输入相应的数据与操作。并在选择操作之后，最终输出两个链表的合并结果，为了体现合并后的链表仍为循环单链表，在一次输出完毕遇到头结点之后跳过头结点再多输出一位。 3．程序所能达到的功能包括： 1）构造循环链表 2）输出循环链表（跳过头结点之后多输出一位） 2）两个循环链表的顺序合并 4）两个循环链表的逆序合并 4. 输入及输出结果： 链表长度： 4 6 两个链表的数据：1 5 12 78 6 12 56 99 120 156 顺序合并结果为：1 5 12 12 56 78 99 120 156 1 逆序合并结果为：156 120 99 78 56 12 12 5 1 156 二．概要设计 为实现以上操作，应采用循环单链表为存储结构 1本程序主要包括五个函数 1）主函数 通过对其他各个函数的调用完成对两个循环单链表的初始化以及对两个链表的 顺序与逆序合并并输出。 2）创建链表 首先创建一个空的循环单链表，然后用尾插法插入新的节点从而创建一个循环单 链表，最后返回头指针。 3）输出链表 接收主函数传递的链表头指针之后，输出头结点之后的每个节点的数据域，当遇 到头结点之后，跳过头结点，后输出头结点之后的节点的数据。 4）链表的顺序合并 先定义一个新的头结点，后比较两个链表的数据大小，未达到两个链表末尾时直 接把较小数据插入新合成的链表末尾，当有一个链表比较完之后，把另一个链表 的剩余部分直接插入到新合成的链表尾，并检测到这个剩余未比较完的表尾，让 其指向新合成链表的的头结点，从而构成一个循环链表，并返回头指针。 5）链表的逆序合并 先创建一个新的空循环单链表，后比较两个链表的数据大小，未达到两个链表末 尾时直接把较小数据用头插法插入到新合成的循环单链表中，当有一个链表比较

双向循环链表使用实例

#include using namespace std; typedef struct DLNode{ //定义一个双向循环链表char data; DLNode *next; DLNode *back; }DLNode,*DLnode; int Creat(DLnode root) //创建一个带头节点的双向链表{ root=(DLNode*)malloc(sizeof(DLNode)); //为头节点申请空间 if(root==NULL) return 0; //创建不成功返回0 root->next=root->back=NULL; //使next和back指针都指向root return 1; //创建成功返回1 } int Insert(DLnode &root,char x) //插入元素 { DLNode *p; DLnode s; s=root; p=(DLNode*)malloc(sizeof(DLNode)); if(p==NULL) //插入不成功，返回0 { cout<<"插入不成功"<data=x; //插入成功返回1 p->back=s->back; p->next=s; s->back->next=p; s->back=p; free(p); free(s); return 1; } int Delete(DLnode &root) //删除 { DLNode *p,*q; DLnode s; p=(DLNode*)malloc(sizeof(DLNode));

q=(DLNode*)malloc(sizeof(DLNode)); s=root; if(root==NULL) //头指针为空，则删除不成功 { cout<<"删除不成功"<next; while(p!=s) //头指针不为空，删除#号前面的字符{ if(p->data!='#') p=p->next; else { q=p->back; q->back->next=q->next; q->next->back=q->back; } } free(p); free(q); cout<<"删除成功"<next; while(p!=root) { cout<data; } cout<