C語言學習之鏈表的實現詳解
一、鏈表的概念
鏈表是一種物理存儲結構上非連續、非順序的存儲結構,數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的
二、鏈表的結構
(1)單鏈表
(2)帶頭結點的單鏈表
(3)雙向鏈表
(4)循環單鏈表
(5)雙向循環鏈表
註釋:
(1)無頭單向非循環鏈表:結構簡單,一般不會單獨用來存數據。實際中更多是作為其他數據結構的子結構,如哈希桶、圖的鄰接表等等。
(2)帶頭雙向循環鏈表:結構最復雜,一般用在單獨存儲數據。實際中使用的鏈表數據結構,都是帶頭雙向循環鏈表。另外這個結構雖然結構復雜,但是使用代碼實現以後會發現結構會帶來很多優勢,實現反而簡單瞭。
三、順序表和鏈表的區別和聯系
(1)順序表:
優點: 空間連續,支持隨機訪問。
缺點: 中間或前面部分的插入刪除時間復雜度為O(n),並且增容代價比較大。
(2)鏈表
優點: 任意位置插入刪除時間復雜度為O(1) 2.沒有增容問題,插入一個開辟一個空間。
缺點: 以節點為單位存儲,不支持隨機訪問。
四、鏈表的實現
(1)單鏈表的增刪查找等操作
#pragma once #include"common.h" typedef struct SListNode { ElemType data; struct SListNode* next; }SListNode; typedef struct SList { SListNode* head; }SList; /// /// //單鏈表的函數接口聲明 void SListInit(SList* plist); static SListNode* _Buynode(ElemType x); void SListPushBack(SList* plist, ElemType item);//1 void SListPushFront(SList* plist, ElemType item);//2 void SListShow(SList* plist);//3 void SListPopBack(SList* plist);//4 void SListPopFront(SList* plist);//5 void SListInsertVal(SList* plist, ElemType val);//7 void SqListDeleteByVal(SList* plist, ElemType val);//9 SListNode* SListFind(SList* plist, ElemType key);//10 size_t SListLength(SList* plist);//11 void SListSort(SList* plist);//13 void SListReverse(SList* plist);//14 void SListClear(SList* plist);//15 void SListDestroy(SList* plist); /// /// //單鏈表的函數接口實現 void SListInit(SList* plist) { plist->head = NULL; } static SListNode* _Buynode(ElemType x) { SListNode* s = (SListNode*)malloc(sizeof(SListNode)); assert(s != NULL); s->data = x; s->next = NULL; return s; } //1 void SListPushBack(SList* plist, ElemType item) { assert(plist != NULL); SListNode* s = _Buynode(item); //插入的節點為第一個節點 if (plist->head == NULL) { plist->head = s; return; } //O(n) SListNode* p = plist->head; //查找鏈表的尾部節點 while (p->next != NULL) { p = p->next; } p->next = s; } //2 void SListPushFront(SList* plist, ElemType item) { assert(plist != NULL); SListNode* s = _Buynode(item); s->next = plist->head; plist->head = s; } //3 void SListShow(SList* plist) { assert(plist != NULL); SListNode* p = plist->head; while (p != NULL) { printf("%d-->", p->data); p = p->next; } printf("Over.\n"); } //4 void SListPopBack(SList* plist) { assert(plist != NULL); SListNode* p = plist->head; if (plist->head == NULL) { printf("單鏈表為空,輸出失敗!\n"); return; } if (p->next == NULL) { plist->head = NULL; return; } SListNode* prev = NULL; while (p->next != NULL) { prev = p; p = p->next; } prev->next = NULL; free(p); } //5 void SListPopFront(SList* plist) { assert(plist != NULL); SListNode* p = plist->head; if (plist->head == NULL) { printf("單鏈表為空,輸出失敗!\n"); return; } plist->head = p->next; free(p); } //6 //7 void SListInsertVal(SList* plist, ElemType val) { assert(plist != NULL); SListNode* prev = NULL; SListNode* p = plist->head; SListNode* s = _Buynode(val); while (p != NULL && val > p->data) { prev = p; p = p->next; } if (prev == NULL) { s->next = p; plist->head = s; } else { s->next = prev->next; prev->next = s; } } //10 SListNode* SListFind(SList* plist, ElemType key) { assert(plist != NULL); SListNode* p = plist->head; while (p != NULL && p->data != key) p = p->next; return p; } //9 void SqListDeleteByVal(SList* plist, ElemType val) { assert(plist != NULL); SListNode* prev = NULL; SListNode* p = SListFind(plist, val); if (p == NULL) { printf("要刪除的節點不存在.\n"); return; } if (p == plist->head) plist->head = p->next; else { prev = plist->head; while (prev->next != p) prev = prev->next; //刪除 prev->next = p->next; } free(p); } //11 size_t SListLength(SList* plist) { assert(plist != NULL); size_t len = 0; SListNode* p = plist->head; while (p != NULL) { len++; p = p->next; } return len; } //13 void SListSort(SList* plist) { assert(plist != NULL); SListNode* p = plist->head->next; SListNode* q, * t, * prev = NULL; plist->head->next = NULL; //斷開鏈表 t = plist->head; while (p != NULL) { q = p->next; while (t != NULL && p->data > t->data) { prev = t; t = t->next; } if (prev == NULL) { p->next = plist->head; plist->head = p; } else //if(prev->next!=NULL) { p->next = prev->next; prev->next = p; } p = q; t = plist->head; } } //14 void SListReverse(SList* plist) { assert(plist != NULL); SListNode* p = plist->head->next; SListNode* q; if (p->next == NULL) return; //斷開第一個節點 plist->head->next = NULL; while (p != NULL) { q = p->next; p->next = plist->head; plist->head = p; p = q; } } //15 void SListClear(SList* plist) { assert(plist != NULL); SListNode* p = plist->head; while (p != NULL) { plist->head = p->next; free(p); p = plist->head; } } void SListDestroy(SList* plist) { SListClear(plist); plist->head = NULL; } ```c
(2)帶頭的雙循環鏈表的實現
#pragma once #include"common.h" / //帶頭的雙循環鏈表 typedef struct DCListNode { ElemType data; struct DCListNode* next; struct DCListNode* prev; }DCListNode; typedef struct DCList { DCListNode* head; }DCList; static DCListNode* _Buydnode(ElemType x); void DCListInit(DCList* plist); void DCListDestroy(DCList* plist); void DCListPushBack(DCList* plist, ElemType x);//1 void DCListPushFront(DCList* plist, ElemType x);//2 void DCListShow(DCList* plist);//3 void DCListPopBack(DCList* plist);//4 void DCListPopFront(DCList* plist);//5 void DCListInsertByVal(DCList* plist, ElemType val);//7 void DCListDeleteByVal(DCList* plist, ElemType val);//9 size_t DCListLength(DCList* plist);//11 void DCListSort(DCList* plist);//13 void DCListReverse(DCList* plist);//14 void DCListClear(DCList* plist);//15 DCListNode* DCListFind(DCList* plist, ElemType key);//10 static DCListNode* _Buydnode(ElemType x) { DCListNode* s = (DCListNode*)malloc(sizeof(DCListNode)); assert(s != NULL); s->data = x; s->next = s->prev = s; return s; } void DCListInit(DCList* plist) { plist->head = _Buydnode(0); } //1 void DCListPushBack(DCList* plist, ElemType x) { assert(plist != NULL); DCListNode* s = _Buydnode(x); s->prev = plist->head->prev; s->prev->next = s; s->next = plist->head; plist->head->prev = s; } //2 void DCListPushFront(DCList* plist, ElemType x) { assert(plist != NULL); DCListNode* s = _Buydnode(x); s->next = plist->head->next; s->next->prev = s; plist->head->next = s; s->prev = plist->head; } //3 void DCListShow(DCList* plist) { assert(plist != NULL); DCListNode* p = plist->head->next; while (p != plist->head) { printf("%d->", p->data); p = p->next; } printf("Over.\n"); } //4 void DCListPopBack(DCList* plist) { assert(plist != NULL); DCListNode* p = plist->head->prev; if (plist->head->next == plist->head) //if(p == plist->head) { printf("循環雙鏈表隻有頭結點,操作失敗.\n"); return; } plist->head->prev = p->prev; p->prev->next = plist->head; free(p); } //5 void DCListPopFront(DCList* plist) { assert(plist != NULL); DCListNode* p = plist->head->next; if (p == plist->head) { printf("循環雙鏈表隻有頭結點,操作失敗.\n"); return; } plist->head->next = p->next; p->next->prev = plist->head; free(p); } //7 void DCListInsertByVal(DCList* plist, ElemType val) { assert(plist != NULL); DCListNode* p = plist->head->next; while (p != plist->head && p->data < val) { p = p->next; } DCListNode* s = _Buydnode(val); s->next = p; s->prev = p->prev; p->prev->next = s; p->prev = s; } //9 void DCListDeleteByVal(DCList* plist, ElemType val) { assert(plist != NULL); DCListNode* p = DCListFind(plist, val); if (p == NULL) return; p->next->prev = p->prev; p->prev->next = p->next; free(p); } //10 DCListNode* DCListFind(DCList* plist, ElemType key) { assert(plist != NULL); DCListNode* p = plist->head->next; if (p == plist->head) { printf("雙循環鏈表隻有頭結點,查找失敗.\n"); return 0; } while (p != plist->head && p->data != key) { p = p->next; } if (p != plist->head) return p; return NULL; } //11 size_t DCListLength(DCList* plist) { assert(plist != NULL); size_t len = 0; DCListNode* p = plist->head->next; while (p != plist->head) { len++; p = p->next; } return len; } //13 void DCListSort(DCList* plist) { assert(plist != NULL); DCListNode* p = plist->head->next; DCListNode* q = p->next; //斷開鏈表 p->next = plist->head; plist->head->prev = p; while (q != plist->head) { p = q; q = q->next; //尋找p插入的位置 DCListNode* t = plist->head->next; while (t != plist->head && t->data < p->data) t = t->next; p->next = t; p->prev = t->prev; p->next->prev = p; p->prev->next = p; p = q; } } //14 void DCListReverse(DCList* plist) { assert(plist != NULL); DCListNode* p = plist->head->next; DCListNode* q = p->next; //斷開鏈表 p->next = plist->head; plist->head->prev = p; while (q != plist->head) { p = q; q = q->next; p->next = plist->head->next; p->prev = plist->head; p->next->prev = p; p->prev->next = p; //plist->head->next = p; } } //15 void DCListClear(DCList* plist) { assert(plist != NULL); DCListNode* p = plist->head->next; while (p != plist->head) { p->next->prev = p->prev; p->prev->next = p->next; free(p); p = plist->head->next; } } void DCListDestroy(DCList* plist) { DCListClear(plist); free(plist->head); plist->head = NULL; }
以上就是C語言學習之鏈表的實現詳解的詳細內容,更多關於C語言鏈表的資料請關註WalkonNet其它相關文章!