1, 循环链表可以解决星期, 月份, 24 小时等循环的数据.
2, 循环链表的结构:
3, 代码
- /*******************************************************************************************************
- 文件名: CircleList.c
- 头文件: CircleList.h
- 功能: 可以复用 带有增 删 改 查 功能的循环链表
- 难点: 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;// 返回删除的链表元素
- }
来源: http://www.bubuko.com/infodetail-3095862.html