C語言深入講解鏈表的使用
現(xiàn)實生活中的火車就像一個完整的鏈表,現(xiàn)在我們來深入理解一下鏈表這個數(shù)據(jù)結(jié)構(gòu)。
一、鏈表的概念
概念:鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu),數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈 接次序?qū)崿F(xiàn)的 。
注:
1、從上圖中可看出,鏈式結(jié)構(gòu)在邏輯上是連續(xù)的,但是在物理上不一定連續(xù)。
2、從現(xiàn)實中的結(jié)點一般是通過malloc函數(shù)申請的,所以其內(nèi)存分配是在堆區(qū)。
3、從堆上申請的空間,是按照一定的策略來分配的,則一個節(jié)點的大小為8個字節(jié)。
二、鏈表的分類
實際中鏈表的結(jié)構(gòu)非常多樣,以下情況組合起來就有8種鏈表結(jié)構(gòu):
1. 單向或者雙向鏈表
2. 帶頭或者不帶頭(是否有自帶哨兵位頭結(jié)點)
第二個鏈表的d1指向了我們的哨兵位頭結(jié)點。
3. 循環(huán)或者非循環(huán)鏈表
4. 無頭單向非循環(huán)鏈表和帶頭雙向循環(huán)鏈表
1. 無頭單向非循環(huán)鏈表:結(jié)構(gòu)簡單,一般不會單獨用來存數(shù)據(jù)。實際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié) 構(gòu),如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。
2. 帶頭雙向循環(huán)鏈表:結(jié)構(gòu)最復雜,一般用在單獨存儲數(shù)據(jù)。實際中使用的鏈表數(shù)據(jù)結(jié)構(gòu),都是帶頭雙向 循環(huán)鏈表。另外這個結(jié)構(gòu)雖然結(jié)構(gòu)復雜,但是使用代碼實現(xiàn)以后會發(fā)現(xiàn)結(jié)構(gòu)會帶來很多優(yōu)勢,實現(xiàn)反而 簡單了。
3、鏈表的實現(xiàn)(代碼和注釋)
無頭+單向+非循環(huán)鏈表增刪查改實現(xiàn)
頭文件:
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> //要求存儲的數(shù)據(jù)從0開始,依次存儲 //靜態(tài)的順序表 //問題:開小了,不夠用,開大了,存在浪費。 //struct SeqList //{ // int a[N]; // int size;//記錄存儲了多少個數(shù)據(jù)。 //}; typedef int SLDateType;//宏定義我們的 SLDateType是int類型的 //動態(tài)的順序表 typedef struct SeqList { SLDateType* a; int size; //存儲數(shù)據(jù)個數(shù) int capacity;//存儲空間大小 }SL, SeqList; void SeqListPrint(SeqList* psl);//鏈表的打印 void SeqListInit(SeqList* psl);//鏈表的初始化 void SeqListDestroy(SeqList* psl);//鏈表的銷毀 void SeqListCheckCapacity(SeqList* psl);//檢查內(nèi)存空間是否足夠 //時間復雜度是o(1) void SeqListPushBack(SeqList* psl, SLDateType x);//鏈表的尾插 void SeqListPopBack(SeqList* psl);//鏈表的尾刪 //時間復雜度是o(n) void SeqListPushFront(SeqList* psl, SLDateType x);//鏈表的頭插 void SeqListPopFront(SeqList* psl);//鏈表的頭刪 void SeqListInsert(SeqList* psl, size_t pos, SLDateType x); // 刪除pos位置的數(shù)據(jù) void SeqListErase(SeqList* psl, size_t pos); // 順序表查找 int SeqListFind(SeqList* psl, SLDateType x);
鏈表的函數(shù)實現(xiàn)部分的代碼:
#include"SeqList.h" #include<assert.h> void SeqListPrint(SeqList* psl)//結(jié)構(gòu)體指針傳參 { for (int i = 0; i < psl->size; ++i) { printf("%d ", psl->a[i]); } printf("\n"); } void SeqListInit(SeqList* psl) { assert(psl);//斷言psl不為空 psl->a = NULL;//a就相當于是鏈表的頭 psl->size = 0; psl->capacity = 0; } void SeqListDestroy(SeqList* psl)//鏈表的刪除 { assert(psl); free(psl->a);//free掉鏈表中a這個節(jié)點的位置 psl->a = NULL;//將a指向空 psl->capacity = psl->size = 0;//將鏈表的內(nèi)存大小置為0 } void SeqListCheckCapacity(SeqList* psl)//檢查鏈表的內(nèi)存,如果不夠就增容。 { assert(psl); if (psl->size == psl->capacity) { //capacity == 0,所以要先特判一下capacity 的值 size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;//初始節(jié)點數(shù)為4,如果內(nèi)存現(xiàn)在為0就擴大一倍 SLDateType* tmp = realloc(psl->a, sizeof(SLDateType) * newCapacity);//申請空間 if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } else { psl->a = tmp; psl->capacity = newCapacity;//原來的空間變?yōu)樾驴臻g } } } void SeqListPushBack(SeqList* psl, SLDateType x) { //如果滿了,要擴容 if (psl->size == psl->capacity) { //capacity == 0,所以要先特判一下capacity 的值 size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2; SLDateType* tmp = realloc(psl->a, sizeof(SLDateType) * newCapacity); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } else { psl->a = tmp; psl->capacity = newCapacity; } } psl->a[psl->size] = x; psl->size++; } void SeqListPopBack(SeqList* psl) { assert(psl); if (psl->size > 0) { psl->size--;//尾刪就size--就好了 } } void SeqListPushFront(SeqList* psl, SLDateType x) { assert(psl); SeqListCheckCapacity(psl); int end = psl->size - 1; while (end >= 0)//所有的數(shù)據(jù)往后挪1位 { psl->a[end + 1] = psl->a[end]; --end; } psl->a[0] = x;//兩種操作是等價的 psl->size++; //SeqListInsert(psl, 0, x);在頭部插入。 } void SeqListPopFront(SeqList* psl) { assert(psl); if (psl->size > 0) { int begin = 1; while (psl->size > begin) { psl->a[begin - 1] = psl->a[begin]; ++begin; } --psl->size; } } void SeqListInsert(SeqList* psl, size_t pos, SLDateType x) { // 暴力檢查 assert(psl); // 溫和檢查 if (pos > psl->size) { printf("pos 越界:%d\n", pos); return; //exit(-1); } // 暴力檢查 //assert(pos <= psl->size); SeqListCheckCapacity(psl); //int end = psl->size - 1; //while (end >= (int)pos) //{ // psl->a[end + 1] = psl->a[end]; // --end; //} size_t end = psl->size; while (end > pos) { psl->a[end] = psl->a[end - 1]; --end; } psl->a[pos] = x; psl->size++; }
4、鏈表oj題(小試牛刀)
包含三種情況
畫個圖分析:
思路:情況一和情況二都可以用prev和cur指針遍歷數(shù)組的兩個元素, if cur指針不等于6,prev指針和cur指針都往前走,如果cur = 6,prev跳到cur的下一個位置
如果是第三種情況,則需先找到head != val的位置,再重復進行如上操作。
代碼示例:
struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* prev = NULL; struct ListNode* cur = head; while(cur) { if(cur->val != val)//當cur這個位置的值不等于val時往下走 { prev = cur;//prev跳到cur位置 cur = cur->next;//cur指針繼續(xù)往下走 } else { struct ListNode* next = cur->next;//定義一個新的指針 if(prev == NULL)//頭刪,head為空的狀態(tài) { free(cur); head = next;//繼續(xù)往后面走 cur = next; } else { free(cur);//free掉cur這個節(jié)點 prev->next = next;//跳過了cur這個點 cur = next;//cur繼續(xù)往后走 } } } return head; }
思路1:反轉(zhuǎn)指針方向
思路二:用三個指針, n1, n2, n3 分別存放NULL, head, head->next;
代碼示例:
struct ListNode* reverseList(struct ListNode* head) { if(head == NULL) return NULL; struct ListNode* n1, *n2, *n3; n1 = NULL; n2 = head; n3 = n2->next;//n3的地址是n2的下一位 while(n2) { n2->next = n1;//n2 的下一位指向 n1;起到掉頭的作用 n1 = n2; n2 = n3; if(n3) n3 = n3->next; } return n1; }
方法2:頭插法
殊途同歸。newhead 相當于之前的n1, cur = n2, next = n3; struct ListNode* reverseList(struct ListNode* head) { struct ListNode* NewHead = NULL; struct ListNode* cur = head; while(cur) { struct ListNode* next = cur->next; //頭插 cur->next = NewHead;//代表鏈表的指向方向。 NewHead = cur;//接著把地址傳過來(更新) cur = next;//(更新) } return NewHead; }
思路:快慢指針法
struct ListNode* middleNode(struct ListNode* head) { struct ListNode* slow, * fast; slow = fast = head;//剛開始slow和fast指針都指向頭 while(fast && fast->next) //想的是結(jié)束的條件,寫的是繼續(xù)的條件 { slow = slow->next; fast = fast->next->next;//fast 每次走兩步 } return slow; }
總結(jié)
這里我?guī)Т蠹覐逆湵淼母拍?,鏈表的分類,鏈表的簡單實現(xiàn)以及3題oj題四個方面帶大家認識鏈表
到此這篇關(guān)于C語言深入講解鏈表的使用的文章就介紹到這了,更多相關(guān)C語言鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Qt物聯(lián)網(wǎng)管理平臺之實現(xiàn)告警短信轉(zhuǎn)發(fā)
系統(tǒng)在運行過程中,會實時采集設備的數(shù)據(jù),當采集到的數(shù)據(jù)發(fā)生報警后,可以將報警信息以短信的形式發(fā)送給指定的管理員。本文將利用Qt實現(xiàn)告警短信轉(zhuǎn)發(fā),感興趣的可以嘗試一下2022-07-07C++實現(xiàn)圖的鄰接矩陣存儲和廣度、深度優(yōu)先遍歷實例分析
這篇文章主要介紹了C++實現(xiàn)圖的鄰接矩陣存儲和廣度、深度優(yōu)先遍歷,實例分析了C++實現(xiàn)圖的遍歷技巧,非常具有實用價值,需要的朋友可以參考下2015-04-04VS2019項目打包生成.exe文件與Setup的步驟實現(xiàn)
這篇文章主要介紹了VS2019項目打包生成.exe文件與Setup的步驟實現(xiàn),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2020-03-03C 語言實現(xiàn)一個簡單的 web 服務器的原理解析
這篇文章主要介紹了C 語言實現(xiàn)一個簡單的 web 服務器的原理解析,本文給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-11-11