- 浏览: 434415 次
文章分类
最新评论
-
barryzhong:
这篇文章挺不错。令人汗颜的是,那可是微软06年的文章。现在都快 ...
推荐一篇关于多租户Multi-Tenant数据架构的文章 -
Mybeautiful:
设计模式只是一个思路或是方案,碰到某种问题是有什么办法比较好的 ...
再见了模式
数据结构学习笔记(3.线性表之循环链表)
本节知识点:
1.为什么选择循环链表:因为有很多生活中结构是循环的,是单链表解决不了的,比如星期、月份、24小时,对于这些循环的数据,循环链表就体现出它的优势了。
2.循环链表的结构:
循环链表就是从头结点后面开始,尾节点的next不再是NULL了,而是头结点后面的第一个链表元素,如上图。
3.如何创建一个循环链表:
步骤一:
步骤二:
无论是头插法,还是尾插法都没有关系,都可以创建完成这个循环链表。
4.如何将一个单向链表改写成一个循环链表:
第一步 (改写插入函数):
a.把插入位置pos的允许范围改成0~~~无穷大
ret=( NULL != node) && ( NULL != Node) && (pos >= 0);
b.把两种方式的头插法情况加入程序,第一种是pos值为0和1的情况,如图:
这种情况分为两部:先把node插入到head和第一个元素直接,然后再把链表尾指向node元素(node表示插入元素)。
代码如下:
if(node == (CircleListNode* )head) { Last =(CircleListNode* )Get_CircleListNode(lhead, lhead->length); //获得链表最后一个元素 Last->next = Node; //把头插法的数据连接到 链表的最后一个元素的后面 }
头插法的第二种情况,是循环链表,循环了一圈回来了,与第一种不同的是此时插入的相对位置和第一种的相对位置不一样。(其实这种方法跟普通插入是一样的) 如图:
第二步(改写删除函数):
a.也是把pos值的取值范围改成0 到 无穷大,但是同时记得判断length要大于0 ,要保证链表中有数据,不然删什么呀~~~~
if(( NULL != lhead) && (pos > 0) && (lhead->length>0))
b.对于删除第一个元素有两种情况 这里是难点:首先要在删除链表元素的 前面 判断是否要删除第一个元素(此时的情况是pos为1的情况),然后删除链表元素,再判断是否是删除第一个元素的第二种情况(链表循环一圈后,到达链表第一个元素,此时元素的前一个链表不再是head头结点了)。如图:
代码如下:
if(node == (CircleListNode* )head) { Last =(CircleListNode* )Get_CircleListNode(lhead, lhead->length); } ret = node->next; node->next = ret->next; /*判断是不是循环了一圈后回来的情况 */ if((first == ret) &&(NULL == Last)) { Last =(CircleListNode* )Get_CircleListNode(lhead, lhead->length); } /*判断是否要删除链表中的第一个元素*/ if( Last != NULL ) { Last->next = ret->next; lhead->head.next = ret->next; }
图中红笔的代码是:
ret = node->next; node->next = ret->next;
图中蓝笔的代码是:
if( Last != NULL ) { Last->next = ret->next; lhead->head.next = ret->next; }
c.当length为0的是,即链表长度为0的时候,记得给头结点的next赋值为NULL
第三步 (改写获得链表元素函数)
a.记得把pos给成 0 到 无穷大,然后判断length链表长度是否为0 ,如果为0 就不能获取。
5.游标的引入:
在循环链表中一般可以定义一个游标,对于这样一个封装好的可复用循环链表,定义一个游标是十分方便的。例如:如果想依次获得链表中的每一个元素,利用get函数,太过低效了O(n2),想想利用这样一个游标去遍历的话,复杂度仅仅是O(n)。还有就是在循环链表中,游标可以在链表中进行转圈,例如:可以解决约瑟夫环问题。
6.指定删除链表中某一个元素的函数CircleListNode* CircleList_Del(CircleList* head,CircleListNode* node),其实也不是很高效,获得了当前游标的值的时候,再去调用CircleList_Del函数,这个轮询函数获得了pos,再去调用Del_CircleListNode然后又遍历了一边,把复杂的搞到了O(n2)。其实完全可以在找到pos的时候直接删除掉这个链表元素,这样的复杂度是O(n)。
7.我还觉得获得当前游标得值的函数CircleList_Slider的返回值有些问题,我觉得如果返回的是当前游标的上一个链表元素的值会更好,因为这个是一个单向链表,如果得到了上一个链表元素的值,就可以通过游标实现,删除啊,插入啊等高效的操作了。
本节代码:
CricleList.c:
/******************************************************************************************************* 文件名:CircleList.c 头文件:CircleList.h 时间: 2013/08/17 作者: Hao 功能: 可以复用 带有增 删 改 查 功能的循环链表 难道: 1.typedef struct Str_CircleList CircleListNode; //这个结构体是链表的真身 struct Str_CircleList //每一个链表元素的结构都会包含这个结构 因为当给链表元素强制类型 { //转换成(CircleListNode* )的时候 其实就是要开始对每个元素中的 CircleListNode进行赋值了 CircleListNode* next; }; 这个链表结构在链表元素中起到的作用 是本节的难点 2.切记一个问题 就是已经是链表中元素的 千万不要再往链表中添加了 否则链表一定出现无穷的错误 3.对于pos值的问题 add、get、del三个函数中 的链表都是 从1开始的到length 0是链表头 在add函数中pos为0的时候是和pos为1的情况是一样的 都是头插法 0~~~~~无穷大 在get函数中pos为0的时候是获得链表头 地址 0~~~~~length 在del函数中pos为0的时候是无效的 del失败 1~~~~~length *******************************************************************************************************/ #include <stdio.h> #include <stdlib.h> #include <malloc.h> #include "CircleList.h" typedef struct str_list_head //这个是链表头 其实也可以当作一个没有前驱的 链表元素 元素的内容是链表长度 { //CircleListNode* next; CircleListNode head; //这个参数要特别重视 每一个链表元素结构的第一个参数一定是 CircleListNode //因为在寻找链表元素后继的时候 其实就是将链表元素强制类型转换成 CircleListNode* 然后给next进行赋值 其实就是给 CircleListNode变量赋值 CircleListNode* slider; int length; //链表长度 }list_head; /******************************************************************************************************* 函数名: Creat_CircleListHead 函数功能:创建一个链表的链表头 并给链表头分配空间 参数: void 返回值:ret 成功返回链表头地址 失败返回NULL *******************************************************************************************************/ CircleList* Creat_CircleListHead(void) { list_head* ret = NULL; ret = (list_head* )malloc( sizeof(list_head)*1 ); if(NULL != ret) //malloc分配成功 { ret->length = 0; //ret -> next = NULL; ret->head.next = NULL; ret->slider = NULL; } return (CircleList* )ret; } /******************************************************************************************************* 函数名:Destroy_CircleListHead 函数功能:释放一个链表头指针 参数:CircleList* head 链表头指针 返回值: ret 释放成功返回1 释放失败返回0 *******************************************************************************************************/ int Destroy_CircleListHead(CircleList* head) { int ret = 0; list_head* lhead = (list_head* )head; if( NULL != lhead ) { free(lhead); ret = 1; } return ret; } /******************************************************************************************************* 函数名:Get_Length 函数功能:获得链表的长度 参数: CircleList* head 链表头指针 返回值: ret 成功返回链表长度 失败返回0 *******************************************************************************************************/ int Get_Length(CircleList* head) { int ret = 0; list_head* lhead = (list_head* )head; if( NULL != lhead ) { ret = lhead -> length; } return ret; } /******************************************************************************************************* 函数名:Clean_CircleListHead 函数功能: 清空链表 参数: CircleList* head 链表头指针 返回值:ret 成功返回1 失败返回0 *******************************************************************************************************/ int Clean_CircleListHead(CircleList* head) { int ret = 0; list_head* lhead = (list_head* )head; if( NULL != lhead ) { lhead -> length = 0; //lhead -> next = NULL; lhead -> head.next = NULL; lhead->slider = NULL; ret = 1; } return ret; } /******************************************************************************************************* 函数名:Add_CircleList 函数功能:往链表里面添加一个链表元素 如果pos的值是0(就是链表头)和1(链表的第一元素 链表元素个数是从1开始算的)都是头插法 pos的值大于链表长度是尾插法 这里面pos值得注意的是 i=1 pos为a的时候 是把链表元素插入第a个元素的位置 当i=0 pos为a的时候 是把链表元素插入 第a个元素位置的后面 切忌:这里面0位置是链表头指针 从1开始是链表元素 参数: CircleList* head链表头指针 CircleListNode* Node插入元素的指针(被强制类型转化成CircleListNode*) int pos 插入位置 pos的有效值范围是 从0到无穷大 返回值: ret 插入成功返回1 插入失败返回0 *******************************************************************************************************/ int Add_CircleList(CircleList* head, CircleListNode* Node, int pos) { int ret = 0; int i = 0; list_head* lhead = (list_head* )head; CircleListNode* node = (CircleListNode* )head; CircleListNode* Last = NULL; ret=( NULL != node) && ( NULL != Node) && (pos >= 0); if(1 == ret) { for(i=1; ( (i<pos) && (node->next != NULL) ); i++) { node = node->next; } Node -> next = node -> next; node -> next = Node; if(lhead->length == 0)//第一次插入元素的时候把游标 指向这个元素 { lhead->slider = Node; } lhead -> length++; //这个一定要在后面调用 lhead->length值的前面更新 /*判断是否为头插法 所谓头插法 就是pos为0和1的情况 其实也就是没有进for循环的情况 剩下的无论pos为多少 进入多少次循环都没有头插法*/ if(node == (CircleListNode* )head) { Last =(CircleListNode* )Get_CircleListNode(lhead, lhead->length); //获得链表最后一个元素 Last->next = Node; //把头插法的数据连接到 链表的最后一个元素的后面 } } return ret; } /******************************************************************************************************* 函数名:Get_CircleListNode 函数功能:获得链表中第pos个元素位置的链表元素 链表是从1开始的 0是链表头 pos为0的时候表示get链表头 参数: CircleList* head链表头指针 int pos获得链表元素的位置 pos的有效取值范围是 1 到 length 0是链表头 返回值: CircleListNode*类型 第pos个链表元素的地址 *******************************************************************************************************/ CircleListNode* Get_CircleListNode(CircleList* head, int pos) { int ret = 0; int i = 0; list_head* lhead = (list_head* )head; /*本来pos应该是有上限的 但是变成了循环链表pos理论上说就可以无穷大了 但是get函数应该是在链表中有值的情况下才成立的 即(lhead->length>0)*/ ret=( NULL != lhead) && (pos >= 0) && (lhead->length>0); if(1 == ret) { CircleListNode* node = (CircleListNode* )head; for(i=0; i<pos; i++) //执行 pos次 得到的是第pos位置的node { node = node->next; } return (CircleListNode*)node; } return NULL; } /******************************************************************************************************* 函数名:Del_CircleListNode 函数功能:删除链表中第pos位置的链表元素 参数: CircleList* head链表头指针 int pos删除链表元素的位置 pos是删除的链表元素的位置 跟get和add中的 pos是配套的 有效取值范围依然是 1到 length 在这个函数里面由于不能删除链表头 所以pos为0的时候无效 返回值: CircleListNode* ret这个返回值很重要 因为这个删除仅仅是把链表元素踢出了链表 并没有free开辟的内存 应该通过这个返回的地址free 释放内存 删除成功返回 删除链表元素的地址 删除失败返回 NULL *******************************************************************************************************/ CircleListNode* Del_CircleListNode(CircleList* head, int pos) { CircleListNode* ret = NULL; CircleListNode* Last = NULL; int i = 0; list_head* lhead = (list_head* )head; CircleListNode* first = lhead->head.next; if(( NULL != lhead) && (pos > 0) && (lhead->length>0)) { CircleListNode* node = (CircleListNode* )head; for(i=1; i<pos; i++)//执行 pos次 得到的是第pos位置的node 这个方法行不通 { //因为要想删除第pos位置的node 应该先找到它上一个链表元素 node = node->next; //所以这里面i=1 比get函数少执行了一次 得到第pos-1位置的node } /*判断是不是 pos为1的 情况删除头节点后面的第一个元素(这个是没有进入for循环的) 跟循环一圈后的情况不一样 */ /*循环一圈的是进入for循环的情况 此时的node不再是head了 而是链表最后一个元素*/ if(node == (CircleListNode* )head) { Last =(CircleListNode* )Get_CircleListNode(lhead, lhead->length); } ret = node->next; node->next = ret->next; /*判断是不是循环了一圈后回来的情况 */ if((first == ret) &&(NULL == Last)) { Last =(CircleListNode* )Get_CircleListNode(lhead, lhead->length); } /*判断是否要删除链表中的第一个元素*/ if( Last != NULL ) { Last->next = ret->next; lhead->head.next = ret->next; } if( lhead->slider == ret)//如果删除的元素恰恰就是游标指向的元素 要把游标往后面移动一位 { lhead->slider = ret->next; } lhead->length--; //这个一定要写在 Get_CircleListNode 后面 不然的话 pos就为0了 /*判断链表是否 减到了空 如果链表中不再有元素 就把head.next赋值为NULL*/ /*单向链表不需要这个的原因 是因为单向链表的最后一个元素的next就是NULL 而双向链表没有NULL的了*/ if(0 == lhead->length) { lhead->head.next = NULL; lhead->slider = NULL; } } return (CircleListNode*)ret; } /******************************************************************************************************* 函数名: CircleList_Slider 函数功能:获得当前游标指向的数据 参数: CircleList* head 返回值:成功返回 CircleListNode* ret 失败返回NULL *******************************************************************************************************/ CircleListNode* CircleList_Slider(CircleList* head) { CircleListNode* ret = NULL; list_head* lhead = (list_head* )head; if( (NULL != lhead)&&(NULL != lhead->slider) )//保证slider是有效的 { ret = lhead->slider; } return ret; } /******************************************************************************************************* 函数名: CircleList_Reset 函数功能:重置游标 让游标指向head头节点后面的第一个元素 参数: CircleList* head 返回值:成功返回 当前游标的指向CircleListNode* ret 失败返回NULL *******************************************************************************************************/ CircleListNode* CircleList_Reset(CircleList* head) { CircleListNode* ret = NULL; list_head* lhead = (list_head* )head; if(NULL != lhead) { lhead->slider = lhead->head.next; ret = lhead->slider; } return ret; } /******************************************************************************************************* 函数名: CircleList_Next 函数功能:使游标指向下一个元素 参数: CircleList* head 返回值:成功返回 前游标的指向CircleListNode* ret 失败返回NULL *******************************************************************************************************/ CircleListNode* CircleList_Next(CircleList* head) { CircleListNode* ret = NULL; list_head* lhead = (list_head* )head; if((NULL != lhead)&&(NULL != lhead->slider)) //保证游标是有效的 { ret = lhead->slider; lhead->slider = ret->next; } return ret; } /******************************************************************************************************* 函数名: CircleList_Del 函数功能:删除链表中的某个指定元素 参数: CircleList* head CircleListNode* node为指定的元素 返回值:成功返回 删除的链表元素 失败返回NULL *******************************************************************************************************/ CircleListNode* CircleList_Del(CircleList* head,CircleListNode* node) { //这个函数主要是用来删除游标的返回值的 CircleListNode* ret = NULL; list_head* lhead = (list_head* )head; int i=0; if((NULL != head)&&(NULL != node)) { CircleListNode* current = (CircleListNode*)lhead; for(i=1; i<=lhead->length; i++) { if(node == current->next) { ret = current->next; break; } current = current->next; } if(NULL == ret) //说明没有找到node { printf("put error!!!\n"); } else //找到了node { Del_CircleListNode(lhead,i); } } return ret;//返回删除的链表元素 }
CircleList.h:
#ifndef __CircleList_H__ #define __CircleList_H__ typedef void CircleList; //这个是为了 封装方便 typedef struct Str_CircleList CircleListNode; //这个结构体是链表的真身 struct Str_CircleList //每一个链表元素的结构都会包含这个结构 因为当给链表元素强制类型 { //转换成(CircleListNode* )的时候 其实就是要开始对每个元素中的 CircleListNode进行赋值了 CircleListNode* next; }; CircleList* Creat_CircleListHead(void); int Destroy_CircleListHead(CircleList* head); int Get_Length(CircleList* head); int Clean_CircleListHead(CircleList* head); int Add_CircleList(CircleList* head, CircleListNode* Node, int pos); CircleListNode* Get_CircleListNode(CircleList* head, int pos); CircleListNode* Del_CircleListNode(CircleList* head, int pos); CircleListNode* CircleList_Del(CircleList* head,CircleListNode* node); CircleListNode* CircleList_Next(CircleList* head); CircleListNode* CircleList_Reset(CircleList* head); CircleListNode* CircleList_Slider(CircleList* head); #endif
main.c:
#include <stdio.h> #include <stdlib.h> #include "CircleList.h" typedef struct _tag_str { CircleListNode head; int i; }str; int main(int argc, char *argv[]) { str str1,str2,str3,str4,str5,str6; str *strp; int i=0; str1.i=1; str2.i=2; str3.i=3; str4.i=4; str5.i=5; str6.i=6; CircleList* head; head = Creat_CircleListHead(); Add_CircleList(head, (CircleListNode*)&str1, 0); Add_CircleList(head, (CircleListNode*)&str2, 0); Add_CircleList(head, (CircleListNode*)&str3, 0); Add_CircleList(head, (CircleListNode*)&str4, 0); Add_CircleList(head, (CircleListNode*)&str5, 5); for(i=1; i<=2*Get_Length(head); i++) { strp = (str* )Get_CircleListNode(head, i); printf("%d\n",strp->i); } printf("\n"); printf("%d\n",Get_Length(head)); strp = (str* )Del_CircleListNode(head, 6); printf("%d\n",strp->i); printf("%d\n",Get_Length(head)); printf("\n"); for(i=1; i<=2*Get_Length(head); i++) { strp = (str* )Get_CircleListNode(head, i); printf("%d\n",strp->i); } printf("\n"); printf("%d\n",Get_Length(head)); strp = (str* )Del_CircleListNode(head, 1); printf("%d\n",strp->i); printf("%d\n",Get_Length(head)); printf("\n"); for(i=1; i<=2*Get_Length(head); i++) { strp = (str* )Get_CircleListNode(head, i); printf("%d\n",strp->i); } printf("\n"); for(i=1; i<=3; i++) { strp = (str* )Del_CircleListNode(head, 1); printf("%d\n",strp->i); } /*CircleList_Reset(head); CircleList_Next(head); CircleList_Del(head,(CircleListNode*)&str3); strp = (str* )CircleList_Slider(head); printf("%d\n",strp->i); printf("\n"); for(i=1; i<=2*Get_Length(head); i++) { strp = (str* )Get_CircleListNode(head, i); printf("%d\n",strp->i); } printf("\n");*/ Destroy_CircleListHead(head); return 0; }
相关推荐
数据结构算法——1008.线性表去重 定义线性表节点的结构.pdf
数据结构 实验报告 实验一.线性表的操作
Java数据结构 线性表,链表,哈希表是常用的数据结构,在进行Java开发时,JDK已经为我们提供了一系列相应的类来实现基本的数据结构
数据结构---线性表之双链表,创建、插入、删除,完整的C代码
数据结构---线性表之单链表,包括单链表的创建、插入、删除等,C语言编写
配合严蔚敏老师教材伪代码,尽量保存原来的代码,包含小部分修改。
数据结构C语言版线性表算法2.4-数据结构c语言版严蔚敏顺序线性表12个基本操作及算法的实现... 定义线性表节点的结构.pdf数据结构C语言版线性表算法2.4-数据结构c语言版严蔚敏顺序线性表12个基本操作及算法的实现... ...
数据结构 线性表 实验代码 C++ 链表 C/C++的数组/链表四种都写了。虽说基本操作能实现,但感觉还有很多要改进的地方,下学期学数据结构这门课时再改了 hust 赵明
数据结构教学课件:线性表链表.ppt
2.线性表.ppt
算法-理论基础- 线性表- 循环链表(包含源程序).rar
主要讲解了 线性表的一些知识。很适合数据结构的学习者使用
数据结构实验报告(1) 学院: 专业: 班级: "姓名 " "学号 " "实验组" " "实验时间 "2011-10-28 "指导教师" "成绩 " " "实验项目名称 "线性表的顺序存储结构 " "实 "1. 熟练掌握线性表的基本操作在顺序存储和链式...
2.线性表子系统.pdf
线性表双向链表链表详细代码,有三个小的程序,调试通过。
1.线性表.cpp
实验报告 "课程 "数据结构 "实验名称 "实验一 线性表 " "学号 " "姓名 " "实验日期:" " 实验一 线性表 实验目的: 1.理解线性表的逻辑结构特性; 2.熟练掌握线性表的顺序存储结构的描述方法,以及在该存储结构下的...
4.线性表顺序存储结构.pdf
线性表实现.pdf线性表实现.pdf线性表实现.pdf线性表实现.pdf
山东大学数据结构实验4线性表报告2012年