网站布局建设,广州市酒店网站设计,2013年以前pc网站建设,莆田网站建设方法文章目录 【 1. 基本原理 】【 2. 循环链表的创建 】2.1 循环链表结点设计2.2 循环单链表初始化 【 3. 循环链表的 插入 】【 4. 循环单链表的 删除操作 】【 5. 循环单链表的遍历 】【 6. 实例 - 循环链表的 增删查改 】【 7. 双向循环链表 】 【 1. 基本原理 】
对于单链表以… 文章目录 【 1. 基本原理 】【 2. 循环链表的创建 】2.1 循环链表结点设计2.2 循环单链表初始化 【 3. 循环链表的 插入 】【 4. 循环单链表的 删除操作 】【 5. 循环单链表的遍历 】【 6. 实例 - 循环链表的 增删查改 】【 7. 双向循环链表 】 【 1. 基本原理 】
对于单链表以及双向链表其就像一个小巷无论怎么样最终都能从一端走到另一端然而循环链表则像一个有传送门的小巷因为循环链表当你以为你走到结尾的时候其实你又回到了开头。循环链表和非循环链表其实创建的过程以及思路几乎完全一样唯一不同的是非循环链表的尾结点指向空NULL而 循环链表的尾指针指向的是链表的开头。通过将单链表的尾结点指向头结点的链表称之为 循环单链表Circular linkedlist。如下图所示
【 2. 循环链表的创建 】
2.1 循环链表结点设计
以单循环链表为例对于循环单链表的结点可以完全参照于单链表的结点设计如图 data表示数据其可以是简单的类型如int,double等等也可以是复杂的结构体struct类型next表示指针它永远指向自身的下一个结点 对于 只有一个结点的存在这个next指针则永远指向自身对于一个 循环链表的尾部结点next永远指向开头。 其代码可以表示为
typedef struct list
{int data;struct list *next;
}list;
//data为存储的数据next指针为指向下一个结点2.2 循环单链表初始化
如同单链表的创建我们需要先创建一个头结点并且给其开辟内存空间但与单链表不同的是我们需要在开辟内存空间成功之后将头结点的next指向head自身。我们可以创建一个init函数来完成这件事情为了以后的重复创建和插入我们可以考虑 在init重创建的结点next指向空而在主函数调用创建之后手动 将head头结点的next指针指向自身。这样的操作方式可以方便过后的创建单链表直接利用多次调用的插入函数即可完成整体创建。C语言实现可以表示为
//初始结点
list *initlist()
{list *head(list*)malloc(sizeof(list));if(headNULL){printf(创建失败退出程序);exit(0);}else{head-nextNULL;return head;}
}在主函数重调用
//初始化头结点
list *headinitlist();
head-nexthead;【 3. 循环链表的 插入 】
对于插入数据的操作基本与单链表的插入操作相同我们可以创建一个独立的结点通过将需要插入的结点的上一个结点的next指针指向该节点再由需要插入的结点的next指针指向下一个结点的方式完成插入操作。 C 代码可以表示为
//插入元素
//三个参数分别是链表位置参数
list *insert_list(list *head,int pos,int data)
{list *nodeinitlist(); //新建结点list *phead; //p表示新的链表list *t;tp;node-datadata;if(head!NULL){for(int i1;ipos;i){tt-next; //走到需要插入的位置处}node-nextt-next;t-nextnode;return p;}return p;
}【 4. 循环单链表的 删除操作 】
如图所示循环单链表的删除操作可以参考单链表的删除操作其都是 找到需要删除的结点将其前一个结点的next指针直接指向删除结点的下一个结点 即可但需要注意的是尾节点和头结点的特判尤其是尾结点因为删除尾节点后尾节点前一个结点就成了新的尾节点这个新的尾节点需要指向的是头结点而不是空其重点可以记录为【删除节点的前一节点.next删除结点.next】这样的操作可以省去头尾结点的特判 C 代码
//删除元素
int delete_list(list *head)
{if(head NULL) {printf(链表为空\n);return 0;}//建立临时结点存储头结点信息目的为了找到退出点//如果不这么建立的化需要使用一个数据进行计数标记计数达到链表长度时自动退出//循环链表当找到最后一个元素的时候会自动指向头元素这是我们不想让他发生的list *temp head; //作为遍历的前一个节点 list *ptr head-next;//作为遍历的当前节点int del;printf(请输入你要删除的元素);scanf(%d,del);while(ptr ! head) {if(ptr-data del) {if(ptr-next head) //如果是最后一个尾节点{temp-next head;free(ptr);return 1;}temp-next ptr-next; //核心删除操作代码free(ptr);//printf(元素删除成功\n);return 1;}temp temp-next;ptr ptr-next;}printf(没有找到要删除的元素\n);return 0;
}【 5. 循环单链表的遍历 】
与普通的单链表和双向链表的遍历不同循环链表需要进行结点的判断找到尾节点的位置由于尾节点的next指针是指向头结点的所以不能使用链表本身是否为空NULL的方法进行简单的循环判断我们需要通过判断结点的next指针是否等于头结点的方式进行是否完成循环的判断。此外还有一种计数的方法即建立一个计数器count0每一次next指针指向下一个结点时计数器加一当count数字与链表的节点数相同的时候即完成循环这样做有一个 问题就是获取到链表的节点数同时也需要完成一次遍历才可以达成目标。C代码
//遍历元素
int display(list *head)
{if(head ! NULL) {list *p head;//遍历头节点到最后一个数据while(p-next ! head ) {printf(%d ,p-next-data);p p-next;}printf(\n); //习惯性换行//把最后一个节点赋新的节点过去return 1;}else{printf(头结点为空!\n);return 0;}
}【 6. 实例 - 循环链表的 增删查改 】 #includestdio.h
#includestdlib.h
typedef struct list{int data;struct list *next;
}list;
//data为存储的数据next指针为指向下一个结点//初始结点
list *initlist(){list *head(list*)malloc(sizeof(list));if(headNULL){printf(创建失败退出程序);exit(0);}else{head-nextNULL;return head;}
}//创建--插入数据
int create_list(list *head){int data; //插入的数据类型printf(请输入要插入的元素);scanf(%d,data);list *nodeinitlist();node-datadata;//初始化一个新的结点准备进行链接if(head!NULL){list *phead;//找到最后一个数据while(p-next!head){pp-next;}p-nextnode;node-nexthead;return 1;}else{printf(头结点已无元素\n);return 0;}}//插入元素
list *insert_list(list *head,int pos,int data){//三个参数分别是链表位置参数list *nodeinitlist(); //新建结点list *phead; //p表示新的链表list *t;tp;node-datadata;if(head!NULL){for(int i1;ipos;i){tt-next;}node-nextt-next;t-nextnode;return p;}return p;
}//删除元素
int delete_list(list *head) {if(head NULL) {printf(链表为空\n);return 0;}//建立零时结点存储头结点信息目的为了找到退出点//如果不这么建立的化需要使用一个数据进行计数标记计数达到链表长度时自动退出//循环链表当找到最后一个元素的时候会自动指向头元素这是我们不想让他发生的list *temp head; list *ptr head-next;int del;printf(请输入你要删除的元素);scanf(%d,del);while(ptr ! head) {if(ptr-data del) {if(ptr-next head) { //循环结束的条件换成ptr-next headtemp-next head;free(ptr);return 1;}temp-next ptr-next;free(ptr);//printf(元素删除成功\n);return 1;}temp temp-next;ptr ptr-next;}printf(没有找到要删除的元素\n);return 0;
}//遍历元素
int display(list *head) {if(head ! NULL) {list *p head;//遍历头节点到最后一个数据while(p-next ! head ) {printf(%d ,p-next-data);p p-next;}printf(\n); //习惯性换行 ( o^•ェ•)o ┏━┓//把最后一个节点赋新的节点过去return 1;} else {printf(头结点为空!\n);return 0;}
}int main(){//初始化头结点//list *headinitlist();head-nexthead;通过插入元素完善链表/for(int i0;i5;i){ //只是演示使用不具体提供输入create_list(head);}display(head);插入元素headinsert_list(head,1,10);display(head);删除元素delete_list(head);display(head);return 0;
}【 7. 双向循环链表 】
循环链表还有一个进阶的概念练习同双向链表与单链表的关系一样循环单链表也有一个孪生兄弟——双向循环链表其设计思路与单链表和双向链表的设计思路一样就是 在原有的双向链表的基础上将尾部结点和头部结点进行互相连接。
