循環鏈表的定義:將單鏈表中最後一個數據元素的next指針指向第一個元素
循環鏈表擁有單鏈表的所有操作:
創建鏈表
銷毀鏈表
獲取鏈表長度
清空鏈表
獲取第pos個元素操作
插入元素到位置pos
刪除位置pos處的元素
在循環鏈表中可以定義一個“當前”指針,這個指針通常稱為游標,可以通過這個游標來遍歷鏈表中的所有元素。
循環鏈表新操作:
獲取當前游標指向的數據元素
將游標重置指向鏈表中的第一個數據元素
將游標移動指向到鏈表中的下一個數據元素
直接指定刪除鏈表中的某個數據元素
插入元素的分析
添加第一個元素如圖:
在最後一個位置插入元素如圖:
刪除節點
優點:功能強了。循環鏈表只是在單鏈表的基礎上做了一個加強,循環鏈表可以完全取代單鏈表的使用,循環鏈表的Next和Current操作可以高效的遍歷鏈表中的所有元素
缺點:代碼復雜度提高了
n個人圍成一個圓圈,首先第1個人從1開始一個人一個人順時針報數,報到第m個人,令其出列。然後再從下一個人開始從1順時針報數,報到第m個人,再令其出列,…,如此下去,求出列順序。
CircleList.h #ifndef _CIRCLELIST_H_ #define _CIRCLELIST_H_ typedef void CircleList; /* typedef struct _tag_CircleListNode CircleListNode; struct _tag_CircleListNode { CircleListNode* next; }; */ 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); int CircleList_Insert(CircleList* list, CircleListNode* node, int pos); CircleListNode* CircleList_Get(CircleList* list, int pos); CircleListNode* CircleList_Delete(CircleList* list, int pos); //add CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node); CircleListNode* CircleList_Reset(CircleList* list); CircleListNode* CircleList_Current(CircleList* list); CircleListNode* CircleList_Next(CircleList* list); #endif
CircleList.c #include#include #include "CircleList.h" typedef struct _tag_CircleList { CircleListNode header; CircleListNode* slider; int length; } TCircleList; CircleList* CircleList_Create() // O(1) { TCircleList* ret = (TCircleList*)malloc(sizeof(TCircleList)); if (ret == NULL) { return NULL; } ret->length = 0; ret->header.next = NULL; ret->slider = NULL; return ret; } void CircleList_Destroy(CircleList* list) // O(1) { if (list == NULL) { return ; } free(list); } void CircleList_Clear(CircleList* list) // O(1) { TCircleList* sList = (TCircleList*)list; if (sList == NULL) { return ; } sList->length = 0; sList->header.next = NULL; sList->slider = NULL; } int CircleList_Length(CircleList* list) // O(1) { TCircleList* sList = (TCircleList*)list; int ret = -1; if (list == NULL) { return ret; } ret = sList->length; return ret; } int CircleList_Insert(CircleList* list, CircleListNode* node, int pos) // O(n) { int ret = 0, i=0; TCircleList* sList = (TCircleList*)list; if (list == NULL || node== NULL || pos<0) { return -1; } //if( ret ) { CircleListNode* current = (CircleListNode*)sList; for(i=0; (i next != NULL); i++) { current = current->next; } //current->next 0號節點的地址 node->next = current->next; //1 current->next = node; //2 //若第一次插入節點 if( sList->length == 0 ) { sList->slider = node; } sList->length++; //若頭插法 if( current == (CircleListNode*)sList ) { //獲取最後一個元素 CircleListNode* last = CircleList_Get(sList, sList->length - 1); last->next = current->next; //3 } } return ret; } CircleListNode* CircleList_Get(CircleList* list, int pos) // O(n) { TCircleList* sList = (TCircleList*)list; CircleListNode* ret = NULL; int i = 0; if (list==NULL || pos<0) { return NULL; } //if( (sList != NULL) && (pos >= 0) && (sList->length > 0) ) { CircleListNode* current = (CircleListNode*)sList; for(i=0; i next; } ret = current->next; } return ret; } CircleListNode* CircleList_Delete(CircleList* list, int pos) // O(n) { TCircleList* sList = (TCircleList*)list; CircleListNode* ret = NULL; int i = 0; if( (sList != NULL) && (pos >= 0) && (sList->length > 0) ) { CircleListNode* current = (CircleListNode*)sList; CircleListNode* last = NULL; for(i=0; i next; } //若刪除第一個元素 if( current == (CircleListNode*)sList ) { last = (CircleListNode*)CircleList_Get(sList, sList->length - 1); } //求要刪除的元素 ret = current->next; current->next = ret->next; sList->length--; //判斷鏈表是否為空 if( last != NULL ) { sList->header.next = ret->next; last->next = ret->next; } //若刪除的元素為游標所指的元素 if( sList->slider == ret ) { sList->slider = ret->next; } //若刪除元素後,鏈表長度為0 if( sList->length == 0 ) { sList->header.next = NULL; sList->slider = NULL; } } return ret; } CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node) // O(n) { TCircleList* sList = (TCircleList*)list; CircleListNode* ret = NULL; int i = 0; if( sList != NULL ) { CircleListNode* current = (CircleListNode*)sList; //查找node在循環鏈表中的位置i for(i=0; i length; i++) { if( current->next == node ) { ret = current->next; break; } current = current->next; } //如果ret找到,根據i去刪除 if( ret != NULL ) { CircleList_Delete(sList, i); } } return ret; } CircleListNode* CircleList_Reset(CircleList* list) // O(1) { TCircleList* sList = (TCircleList*)list; CircleListNode* ret = NULL; if( sList != NULL ) { sList->slider = sList->header.next; ret = sList->slider; } return ret; } CircleListNode* CircleList_Current(CircleList* list) // O(1) { TCircleList* sList = (TCircleList*)list; CircleListNode* ret = NULL; if( sList != NULL ) { ret = sList->slider; } return ret; } CircleListNode* CircleList_Next(CircleList* list) // O(1) { TCircleList* sList = (TCircleList*)list; CircleListNode* ret = NULL; if( (sList != NULL) && (sList->slider != NULL) ) { ret = sList->slider; sList->slider = ret->next; } return ret; }
#include#include #include "CircleList.h" struct Value { CircleListNode header; int v; }; void main() { int i = 0; CircleList* list = CircleList_Create(); struct Value v1; struct Value v2; struct Value v3; struct Value v4; struct Value v5; struct Value v6; struct Value v7; struct Value v8; v1.v = 1; v2.v = 2; v3.v = 3; v4.v = 4; v5.v = 5; v6.v = 6; v7.v = 7; v8.v = 8; CircleList_Insert(list, (CircleListNode*)&v1, CircleList_Length(list)); CircleList_Insert(list, (CircleListNode*)&v2, CircleList_Length(list)); CircleList_Insert(list, (CircleListNode*)&v3, CircleList_Length(list)); CircleList_Insert(list, (CircleListNode*)&v4, CircleList_Length(list)); CircleList_Insert(list, (CircleListNode*)&v5, 5); CircleList_Delete(list, 0); for(i=0; i<2*CircleList_Length(list); i++) { struct Value* pv = (struct Value*)CircleList_Get(list, i); printf("%d\n", pv->v); } printf("\n"); while( CircleList_Length(list) > 0 ) { struct Value* pv = (struct Value*)CircleList_Delete(list, 0); printf("%d\n", pv->v); } printf("\n"); CircleList_Insert(list, (CircleListNode*)&v1, CircleList_Length(list)); CircleList_Insert(list, (CircleListNode*)&v2, CircleList_Length(list)); CircleList_Insert(list, (CircleListNode*)&v3, CircleList_Length(list)); CircleList_Insert(list, (CircleListNode*)&v4, CircleList_Length(list)); CircleList_Insert(list, (CircleListNode*)&v5, CircleList_Length(list)); CircleList_Insert(list, (CircleListNode*)&v6, CircleList_Length(list)); CircleList_Insert(list, (CircleListNode*)&v7, CircleList_Length(list)); CircleList_Insert(list, (CircleListNode*)&v8, CircleList_Length(list)); for(i=0; i v); } printf("\n"); CircleList_Reset(list); while( CircleList_Length(list) > 0 ) { struct Value* pv = NULL; for(i=1; i<3; i++) { CircleList_Next(list); } pv = (struct Value*)CircleList_Current(list); printf("%d\n", pv->v); CircleList_DeleteNode(list, (CircleListNode*)pv); } CircleList_Destroy(list); system("pause"); return ; }