循環單鏈表

循環單鏈表的插入操作（分為四種情況，歸結為三類）

循環單鏈表的刪除操作（分為四種情況，歸結為三類）

//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); CircleListNode* CircleList_Get(CircleList* list, int pos); int CircleList_Insert(CircleList* list, CircleListNode* node, int pos); CircleListNode* CircleList_Delete(CircleList* list, int pos);//addCircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node); CircleListNode* CircleList_Reset(CircleList* list); CircleListNode* CircleList_Current(CircleList* list); CircleListNode* CircleList_Next(CircleList* list);#endif=============================================================================== //circlelist.cpp函數的實現 #include <stdio.h> #include <malloc.h> #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; }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<pos; i++){current = current->next;}ret = current->next;}return ret; }/* 在循環鏈表中插入結點（分為圖示的4種情況）： 總結：①、②、③、④這四種情況的前兩步代碼是一樣的，只不過②、④兩個情況多了一步代碼 ①、③：根據圖示，這兩種情況是一種情況 ②、④：這兩種情況都是在 “ pos = 0 ” 的位置插入元素，但是有一點點的不同②：④：與②進行對比，④需要找到最后一個結點的位置，使它指向插入的新結點 */ 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;}CircleListNode* current = (CircleListNode*)sList;for(i=0; (i<pos) && (current->next != NULL); i++)//定位current{current = current->next;}//case①②③④：執行代碼第1、2步node->next = current->next; //1current->next = node; //2//case③：if（鏈表是空表，只有頭結點，沒有其他結點）if( sList->length == 0 ){node->next = node; //代碼第3步sList->slider = node;}sList->length++; //注：必須在此處長度++，因為此時已經在pos=0處插入了結點，所以長度+1//case④：if（鏈表除了頭結點外，還有其他結點）if(sList->length > 0)// 若鏈表有其他結點，且插入位置 pos = 0。 {if( current == (CircleListNode*)sList )//if(pos == 0) //if（插入位置是pos=0）{CircleListNode* last = CircleList_Get(sList, sList->length - 1); //獲取最后一個元素last->next = current->next; //代碼第3步}}return ret; }/* 在循環鏈表中刪除結點（分為圖示的4種情況）： 總結：①、②、③、④這四種情況的前一步代碼是一樣的，只不過③、④兩個情況多了一步代碼 ①、②：根據圖示，這兩種情況是一種情況 ③、④：這兩種情況都是在 “ pos = 0 ” 的位置刪除元素，但是有一點點的不同 ---------------------------------------------------------------------------③：除了頭結點外，只有一個鏈表結點④：與③進行對比，④需要找到最后一個結點的位置，使它指向被刪除結點的后繼 */ CircleListNode* CircleList_Delete(CircleList* list, int pos) // O(n) {CircleListNode* ret = NULL;TCircleList* cList = (TCircleList*)list;CircleListNode* current = &cList->header;for(int i=0;i<pos;i++){current = current->next; //待刪結點的前驅}if(current == &cList->header) //如果刪除位置：pos = 0{if(cList->length == 1) //case③：如果只有一個鏈表結點{ret = current->next;current->next = NULL;cList->length = 0;cList->slider = NULL;return ret;}else if(cList->length > 1) //case④：如果不止一個鏈表結點{CircleListNode* ret = current->next;CircleListNode* last = CircleList_Get(list,CircleList_Length(list)-1);current->next = current->next->next;last->next = current->next;cList->length--;//若刪除的元素為游標所指的元素if( cList->slider == ret ){cList->slider = ret->next;}return ret;}}//如果刪除位置：pos！= 0ret = current->next;current->next = current->next->next;cList->length--;//若刪除的元素為游標所指的元素if( cList->slider == ret ){cList->slider = ret->next;}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在循環鏈表中的位置ifor(i=0; i<sList->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; } ====================================================================================== //main.cpp測試代碼 #include <stdio.h> #include <stdlib.h> #include "CircleList.h"struct Value {CircleListNode header; //Linux內核int v; };void print_1(CircleList* list) {for(int i=0; i<CircleList_Length(list); i++){CircleListNode* p = CircleList_Get(list,i);struct Value *q = (struct Value*)p;printf("%d\n",q->v);} }void print_2(CircleList* list) {CircleList_Reset(list);//重置游標位置為pos=0for(int i=0; i<CircleList_Length(list); i++){struct Value* pv = (struct Value*)CircleList_Next(list);//用游標進行遍歷printf("%d\n", pv->v);} } void main() {CircleList* list = CircleList_Create();struct Value v1, v2, v3, v4, v5, v6, v7, 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, 0); //1CircleList_Insert(list, (CircleListNode*)&v2, 1); //2CircleList_Insert(list, (CircleListNode*)&v3, 2); //3CircleList_Insert(list, (CircleListNode*)&v4, 3); //4CircleList_Insert(list, (CircleListNode*)&v5, 0); //5CircleList_Insert(list, (CircleListNode*)&v6, 0); //6CircleList_Insert(list, (CircleListNode*)&v7, CircleList_Length(list)); //7CircleList_Insert(list, (CircleListNode*)&v8, 0); //8print_1(list);printf("\n"); //刪除數據CircleList_Delete(list,0);CircleList_Delete(list,3);CircleList_Delete(list,CircleList_Length(list));print_2(list);printf("\n"); //銷毀鏈表CircleList_Destroy(list);system("pause");return ; }

總結

以上是生活随笔為你收集整理的第十天2017/04/23（1、企业财富库：“循环单链表”的设计与实现）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。