多平台统一管理软件接口,如何实现多平台统一管理软件接口
389
2022-06-06
循环链表设计与API实现
基本概念
循环链表的定义:将单链表中最后一个数据元素的next指针指向第一个元素
循环链表拥有单链表的所有操作
新增功能:游标的定义
在循环链表中可以定义一个“当前”指针,这个指针通常称为游标,可以通过这个游标来遍历链表中的所有元素。
循环链表新操作
将游标重置指向链表中的第一个数据元素
CircleListNode* CircleList_Reset(CircleList* list);
获取当前游标指向的数据元素
CircleListNode* CircleList_Current(CircleList* list);
将游标移动指向到链表中的下一个数据元素
CircleListNode* CircleList_Next(CircleList* list);
直接指定删除链表中的某个数据元素
CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node); // 根据元素的值 删除 元素 pk根据元素的位置 删除 元素
最后加了一个循环链表的应用:求解约瑟夫问题
约瑟夫问题-循环链表典型应用
n 个人围成一个圆圈,首先第 1 个人从 1 开始一个人一个人顺时针报数,报到第 m 个人,令其出列。然后再从下一 个人开始从 1 顺时针报数,报到第 m 个人,再令其出列,…,如此下去,求出列顺序。
代码:
// circlelist.h // 循环链表API声明 #ifndef _CIRCLELIST_H_ #define _CIRCLELIST_H_ typedef void CircleList; typedef struct _tag_CircleListNode { struct _tag_CircleListNode *next; }CircleListNode; // 创建链表 CircleList* CircleList_Create(); // 销毁链表 void CircleList_Destroy(CircleList* list); // 清空链表 void CircleList_Clear(CircleList* list); // 获取链表的长度 int CircleList_Length(CircleList* list); // 在pos位置插入结点node int CircleList_Insert(CircleList* list,CircleListNode* node, int pos); // 获取pos位置的结点 CircleListNode* CircleList_Get(CircleList* list, int pos); // 删除pos位置的结点 CircleListNode* CircleList_Delete(CircleList* list, int pos); // 根据结点的值进行数据删除 CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node); // 重置游标 CircleListNode* CircleList_Reset(CircleList* list); // 获取当前游标所指结点 CircleListNode* CircleList_Current(CircleList* list); // 将原始游标所指结点返回给上层,然后让游标移到下一个结点 CircleListNode* CircleList_Next(CircleList* list); #endif
// circlelist.cpp // 循环链表API实现 #include <iostream> #include <cstdio> #include "circlelist.h" typedef struct _tag_CircleList { CircleListNode header; CircleListNode *silder; int length; }TCircleList; // 创建链表 CircleList* CircleList_Create() { TCircleList *ret = (TCircleList *)malloc(sizeof(TCircleList)); if (ret == NULL) { return NULL; } // 初始化 ret->header.next = NULL; ret->silder = NULL; ret->length = 0; return ret; } // 销毁链表 void CircleList_Destroy(CircleList* list) { if (list == NULL) { return; } free(list); return; } // 清空链表 void CircleList_Clear(CircleList* list) { if (list == NULL) { return; } TCircleList *tList = (TCircleList *)list; tList->header.next = NULL; tList->silder = NULL; tList->length = 0; return; } // 获取链表的长度 int CircleList_Length(CircleList* list) { if (list == NULL) { return -1; } TCircleList *tList = (TCircleList *)list; return tList->length; } // 在pos位置插入结点node int CircleList_Insert(CircleList* list, CircleListNode* node, int pos) { if (list == NULL || node == NULL || pos < 0) { return -1; } TCircleList *tList = (TCircleList *)list; CircleListNode *cur = (CircleListNode *)tList; for (int i = 0; i < pos; ++i) { cur = cur->next; } node->next = cur->next; cur->next = node; // 如果是第一次插入 if (tList->length == 0) { tList->silder = node; } ++tList->length; // 记得长度加1 // 如果是头插法 if (cur == (CircleListNode *)tList) { // 获取最后一个元素 CircleListNode *last = CircleList_Get(tList, tList->length - 1); last->next = cur->next; } return 0; } // 获取pos位置的结点 CircleListNode* CircleList_Get(CircleList* list, int pos) { // 因为是循环链表,所以这里不需要排除pos>length的情况 if (list == NULL || pos < 0) { return NULL; } TCircleList *tList = (TCircleList *)list; CircleListNode *cur = (CircleListNode *)tList; for (int i = 0; i < pos; ++i) { cur = cur->next; } return cur->next; } // 删除pos位置的结点 CircleListNode* CircleList_Delete(CircleList* list, int pos) { TCircleList *tList = (TCircleList *)list; CircleListNode *ret = NULL; if (tList != NULL && pos >= 0 && tList->length > 0) { CircleListNode *cur = (CircleListNode *)tList; for (int i = 0; i < pos; ++i) { cur = cur->next; } // 若删除头结点,需要求出尾结点 CircleListNode *last = NULL; if (cur == (CircleListNode *)tList) { last = CircleList_Get(tList, tList->length - 1); } ret = cur->next; cur->next = ret->next; --tList->length; // 若删除头结点 if (last != NULL) { tList->header.next = ret->next; last->next = ret->next; } // 若删除的元素为游标所指的元素 if (tList->silder == ret) { tList->silder = ret->next; } // 若删除元素后链表长度为0 if (tList->length == 0) { tList->header.next = NULL; tList->silder = NULL; } } return ret; } // 根据结点的值进行数据删除 CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node) { TCircleList *tList = (TCircleList *)list; CircleListNode *ret = NULL; if (list != NULL && node != NULL) { CircleListNode *cur = (CircleListNode *)tList; int i = 0; for (i = 0; i < tList->length; ++i) { if (cur->next == node) { ret = cur->next; break; } cur = cur->next; } // 如果找到 if (ret != NULL) { CircleList_Delete(tList, i); } } return ret; } // 重置游标 CircleListNode* CircleList_Reset(CircleList* list) { TCircleList *tList = (TCircleList *)list; CircleListNode* ret = NULL; if (list != NULL) { tList->silder = tList->header.next; ret = tList->silder; } return NULL; } // 获取当前游标所指结点 CircleListNode* CircleList_Current(CircleList* list) { TCircleList *tList = (TCircleList *)list; CircleListNode* ret = NULL; if (list != NULL) { ret = tList->silder; } return ret; } // 将原始游标所指结点返回给上层,然后让游标移到下一个结点 CircleListNode* CircleList_Next(CircleList* list) { TCircleList *tList = (TCircleList *)list; CircleListNode* ret = NULL; if (list != NULL && tList->silder != NULL) { ret = tList->silder; tList->silder = ret->next; } return ret; }
joseph.h
// 用循环链表API求解约瑟夫问题 #include <cstdio> #include "circlelist.h" const int maxp = 8; struct Person { CircleListNode circlenode; int id; }; void joseph() { Person s[maxp]; for (int i = 0; i < maxp; ++i) { s[i].id = i + 1; } CircleList *list = NULL; list = CircleList_Create(); // 插入元素 for (int i = 0; i < maxp; ++i) { // 尾插法 int ret = CircleList_Insert(list, (CircleListNode *)&s[i], CircleList_Length(list)); if (ret < 0) { printf("function CircleList_Insert err: %d\n", ret); } } // 遍历链表 for (int i = 0; i < CircleList_Length(list); ++i) { Person *tmp = (Person *)CircleList_Get(list, i); if (tmp == NULL) { printf("function CircleList_Get err.\n"); } printf("age: %d\n", tmp->id); } // 求解约瑟夫问题 while (CircleList_Length(list) > 0) { Person* pv = NULL; for (int i = 1; i < 3; i++) { CircleList_Next(list); } pv = (Person*)CircleList_Current(list); printf("%d ", pv->id); CircleList_DeleteNode(list, (CircleListNode *)pv); //根据结点的值,进行结点元素的删除 } printf("\n"); CircleList_Destroy(list); }
main.cpp
// 循环链表测试程序 #include <iostream> #include <cstdio> #include "circlelist.h" #include "joseph.h" const int maxn = 5; struct Student { CircleListNode circlenode; char name[32]; int age; }; void play01() { Student s[maxn]; for (int i = 0; i < maxn; ++i) { s[i].age = i + 1; } CircleList *list = NULL; list = CircleList_Create(); // 创建链表 // 插入元素 for (int i = 0; i < maxn; ++i) { // 尾插法 int ret = CircleList_Insert(list, (CircleListNode *)&s[i], CircleList_Length(list)); if (ret < 0) { printf("function CircleList_Insert err: %d\n", ret); } } // 遍历链表 // 这里遍历打印两边,可以证明这是一个循环链表 for (int i = 0; i < 2 * CircleList_Length(list); ++i) { Student *tmp = (Student *)CircleList_Get(list, i); if (tmp == NULL) { printf("function CircleList_Get err.\n"); } printf("age: %d\n", tmp->age); } // 删除结点,通过结点位置 while (CircleList_Length(list)) { Student *tmp = (Student *)CircleList_Delete(list, CircleList_Length(list) - 1); if (tmp == NULL) { printf("function CircleList_Delete err.\n"); } printf("age: %d\n", tmp->age); } // 销毁链表 CircleList_Destroy(list); } int main() { play01(); // 为了测试数据的生命周期,所以另写一个函数调用运行 joseph(); return 0; }
双向链表设计与API实现
为什么需要双向链表?
双向链表的定义
在单链表的结点中增加一个指向其前驱的pre指针
双向链表拥有单链表的所有操作
插入操作
插入操作异常处理
插入第一个元素异常处理
在0号位置处插入元素;
删除操作
双向链表的新操作
双向链表重要技术场景
循环链表插入结点技术场景
循环链表删除结点技术场景
优点:双向链表在单链表的基础上增加了指向前驱的指针
功能上双向链表可以完全取代单链表的使用
双向链表的Next,Pre和Current操作可以高效的遍历链表中的所有元素
缺点:代码复杂
代码示例:
dlinklist.h
// 双向链表API声明 #ifndef _DLINKLIST_H_ #define _DLINKLIST_H_ typedef void DLinkList; typedef struct _tag_DLinkListNode { _tag_DLinkListNode *next; _tag_DLinkListNode *pre; }DLinkListNode; // 创建链表 DLinkList* DLinkList_Create(); // 销毁链表 void DLinkList_Destroy(DLinkList *list); // 清空链表 void DLinkList_Clear(DLinkList *list); // 获取链表长度 int DLinkList_Length(DLinkList *list); // 在pos位置,插入结点node int DLinkList_Insert(DLinkList *list, DLinkListNode *node, int pos); // 获取pos位置的结点,返回给上层 DLinkListNode* DLinkList_Get(DLinkList *list, int pos); // 删除pos位置的结点 DLinkListNode* DLinkList_Delete(DLinkList *list, int pos); // 删除值为node的结点 DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node); // 重置游标 DLinkListNode* DLinkList_Reset(DLinkList* list); // 获取当前游标所指的结点 DLinkListNode* DLinkList_Current(DLinkList* list); // 获取游标当前所指结点,然后让游标指向下一个结点 DLinkListNode* DLinkList_Next(DLinkList* list); // 获取游标当前所指结点,然后让游标指向前一个结点 DLinkListNode* DLinkList_Pre(DLinkList* list); #endif
dlinklist.cpp
// 循环链表API实现 #include <cstdio> #include <malloc.h> #include "dlinklist.h" typedef struct _tag_DLinkList { DLinkListNode header; DLinkListNode *slider; int length; }TDLinkList; // 创建链表 DLinkList* DLinkList_Create() { TDLinkList *ret = (TDLinkList *)malloc(sizeof(TDLinkList)); if (ret != NULL) { ret->header.next = NULL; ret->header.pre = NULL; ret->slider = NULL; ret->length = 0; } return ret; } // 销毁链表 void DLinkList_Destroy(DLinkList *list) { if (list != NULL) { free(list); } return; } // 清空链表 void DLinkList_Clear(DLinkList *list) { TDLinkList *tList = (TDLinkList *)list; if (tList != NULL) { tList->header.next = NULL; tList->header.pre = NULL; tList->slider = NULL; tList->length = 0; } return; } // 获取链表长度 int DLinkList_Length(DLinkList *list) { TDLinkList *tList = (TDLinkList *)list; int ret = -1; if (tList != NULL) { ret = tList->length; } return ret; } // 在pos位置,插入结点node int DLinkList_Insert(DLinkList *list, DLinkListNode *node, int pos) { TDLinkList *tList = (TDLinkList *)list; int ret = -1, i = 0; if (list != NULL && node != NULL && pos >= 0) { ret = 0; DLinkListNode *cur = (DLinkListNode *)tList; DLinkListNode *next = NULL; for (i = 0; i < pos && cur->next != NULL; ++i) { cur = cur->next; } next = cur->next; cur->next = node; node->next = next; // 当链表插入第一个结点时需要进行特殊处理 if (next != NULL) { next->pre = node; } node->pre = cur; if (tList->length == 0) { tList->slider = node; // 当链表插入第一个元素处理游标 } // 若在0位置插入,需要特殊处理,新来的结点next前pre指向NULL if (cur == (DLinkListNode *)tList) { node->pre = NULL; } ++tList->length; } return ret; } // 获取pos位置的结点,返回给上层 DLinkListNode* DLinkList_Get(DLinkList *list, int pos) { TDLinkList *tList = (TDLinkList *)list; DLinkListNode* ret = NULL; int i = 0; if (list != NULL && pos >= 0 && pos < tList->length) { DLinkListNode *cur = (DLinkListNode *)tList; for (i = 0; i < pos; ++i) { cur = cur->next; } ret = cur->next; } return ret; } // 删除pos位置的结点 DLinkListNode* DLinkList_Delete(DLinkList *list, int pos) { TDLinkList *tList = (TDLinkList *)list; DLinkListNode* ret = NULL; int i = 0; if (tList != NULL && pos >= 0) { DLinkListNode *cur = (DLinkListNode *)tList; DLinkListNode *next = NULL; for (i = 0; i < pos && cur->next != NULL; ++i) { cur = cur->next; } ret = cur->next; next = ret->next; cur->next = next; if (next != NULL) { next->pre = cur; if (cur == (DLinkListNode *)tList) { // 第0个位置,需要特殊处理 next->pre = NULL; } } if (tList->slider == ret) { tList->slider = next; } --tList->length; } return ret; } // 删除值为node的结点 DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node) { TDLinkList *tList = (TDLinkList *)list; DLinkListNode* ret = NULL; int i = 0; if (tList != NULL) { DLinkListNode *cur = (DLinkListNode *)tList; for (i = 0; i < DLinkList_Length(tList); ++i) { if (cur->next == node) { ret = cur->next; break; } cur = cur->next; } if (!ret) { DLinkList_Delete(tList, i); } } return ret; } // 重置游标 DLinkListNode* DLinkList_Reset(DLinkList* list) { TDLinkList *tList = (TDLinkList *)list; DLinkListNode* ret = NULL; if (tList != NULL) { tList->slider = tList->header.next; ret = tList->slider; } return ret; } // 获取当前游标所指的结点 DLinkListNode* DLinkList_Current(DLinkList* list) { TDLinkList *tList = (TDLinkList *)list; DLinkListNode* ret = NULL; if (tList != NULL) { ret = tList->slider; } return ret; } // 获取游标当前所指结点,然后让游标指向下一个结点 DLinkListNode* DLinkList_Next(DLinkList* list) { TDLinkList *tList = (TDLinkList *)list; DLinkListNode* ret = NULL; if (tList != NULL && tList->slider != NULL) { ret = tList->slider; tList->slider = ret->next; } return ret; } // 获取游标当前所指结点,然后让游标指向前一个结点 DLinkListNode* DLinkList_Pre(DLinkList* list) { TDLinkList *tList = (TDLinkList *)list; DLinkListNode* ret = NULL; if (tList != NULL && tList->slider != NULL) { ret = tList->slider; tList->slider = ret->pre; } return ret; }
main.cpp
// 循环线表测试程序 #include <cstdio> #include "dlinklist.h" const int maxn = 5; struct Student { DLinkListNode node; int age; }; void play() { Student s[maxn]; for (int i = 0; i < maxn; ++i) { s[i].age = i + 21; } DLinkList *list = NULL; list = DLinkList_Create(); // 创建链表 // 插入结点 for (int i = 0; i < maxn; ++i) { int ret = DLinkList_Insert(list, (DLinkListNode *)&s[i], DLinkList_Length(list)); if (ret < 0) { return; printf("function DLinkList_Insert err.\n"); } } // 遍历链表 for (int i = 0; i < DLinkList_Length(list); ++i) { Student *tmp = (Student *)DLinkList_Get(list, i); if (tmp == NULL) { printf("function DLinkList_Get err.\n"); return; } printf("age: %d\n", tmp->age); } DLinkList_Delete(list, DLinkList_Length(list) - 1); // 删除尾结点 DLinkList_Delete(list, 0); // 删除头结点 // 用游标遍历链表 for (int i = 0; i < DLinkList_Length(list); ++i) { Student *tmp = (Student *)DLinkList_Next(list); if (tmp == NULL) { printf("function DLinkList_Next err.\n"); return; } printf("age: %d\n", tmp->age); } printf("\n"); DLinkList_Reset(list); DLinkList_Next(list); Student *tmp = (Student *)DLinkList_Current(list); if (tmp == NULL) { printf("function DLinkList_Current err.\n"); return; } printf("age: %d\n", tmp->age); DLinkList_DeleteNode(list, (DLinkListNode*)tmp); tmp = (Student *)DLinkList_Current(list); if (tmp == NULL) { printf("function DLinkList_Current err.\n"); return; } printf("age: %d\n", tmp->age); printf("length: %d\n", DLinkList_Length(list)); DLinkList_Pre(list); tmp = (Student *)DLinkList_Current(list); if (tmp == NULL) { printf("function DLinkList_Current err.\n"); return; } printf("age: %d\n", tmp->age); printf("length: %d\n", DLinkList_Length(list)); DLinkList_Destroy(list); return; } int main() { play(); return 0; }
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论,来抢沙发吧~