您好,登錄后才能下訂單哦!
這篇文章將為大家詳細講解有關(guān)C語言鏈表有什么用,小編覺得挺實用的,因此分享給大家做個參考,希望大家閱讀完這篇文章后可以有所收獲。
鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu),數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的 。
代碼
struct Slist { int* a; struct Slist* next; };
邏輯結(jié)構(gòu):
物理結(jié)構(gòu):
注意:
從上圖可以看出,鏈式結(jié)構(gòu)在邏輯上是連續(xù)的,但是在物理上是不一定是連續(xù)的。
這些結(jié)點一般是從堆上申請出來的。
從堆上申請的空間,是按照一定的策劃來分配的,兩次申請的空間可能連續(xù),大概率是不連續(xù)的。
實際中鏈表的結(jié)構(gòu)非常多樣,以下情況組合起來就有8種鏈表結(jié)構(gòu):
1. 單向或者雙向
①單向
②雙向
2.帶頭或者不帶頭
①帶頭
②不帶頭
3.循環(huán)或者非循環(huán)
①循環(huán)
②非循環(huán)
雖然有這么多種結(jié)構(gòu)的鏈表,但是我們實際中最常用的只有兩種結(jié)構(gòu):
1. 無頭單向非循環(huán)鏈表
2.帶頭雙向循環(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)最復(fù)雜,一般用在單獨存儲數(shù)據(jù)。實際中使用的鏈表數(shù)據(jù)結(jié)構(gòu),都是帶頭雙向循環(huán)鏈表。另外這個結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜,但是使用代碼實現(xiàn)以后會發(fā)現(xiàn)結(jié)構(gòu)會帶來很多優(yōu)勢,實現(xiàn)反而簡單了,后面我們代碼實現(xiàn)了就知道了。
單鏈表結(jié)構(gòu)
typedef int SLTDateType; typedef struct SListNode { SLTDateType data; struct SListNode* next; }SListNode;
單鏈表需要的功能
// 動態(tài)申請一個節(jié)點 SListNode* BuySListNode(SLTDateType x); // 單鏈表打印 void SListPrint(SListNode* plist); // 單鏈表尾插 void SListPushBack(SListNode** pplist, SLTDateType x); // 單鏈表的頭插 void SListPushFront(SListNode** pplist, SLTDateType x); // 單鏈表的尾刪 void SListPopBack(SListNode** pplist); // 單鏈表頭刪 void SListPopFront(SListNode** pplist); // 單鏈表查找 SListNode* SListFind(SListNode* plist, SLTDateType x); // 單鏈表在pos位置之后插入x // 分析思考為什么不在pos位置之前插入? void SListInsertAfter(SListNode* pos, SLTDateType x); // 單鏈表刪除pos位置之后的值 // 分析思考為什么不刪除pos位置? void SListEraseAfter(SListNode* pos); // 單鏈表的銷毀 void SListDestory(SListNode** pplist);
功能實現(xiàn)
SListNode* BuySListNode(SLTDateType x) { SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); if (newnode == NULL) { exit(-1); } newnode->data = x; return newnode; } void SListPrint(SListNode* plist) { if (plist == NULL) { printf("NULL\n"); return; } else { while (plist) { printf("%d->", plist->data); plist = plist->next; } printf("NULL\n"); } } void SListPushBack(SListNode** pplist, SLTDateType x) { SListNode* tail = *pplist; SListNode* newnode = BuySListNode(x); newnode->next = NULL; if (tail == NULL) { *pplist = newnode; } else { while (tail->next) { tail = tail->next; } tail->next = newnode; } } void SListPushFront(SListNode** pplist, SLTDateType x) { SListNode* newnode = BuySListNode(x); newnode->next = *pplist; *pplist = newnode; } void SListPopBack(SListNode** pplist) { assert(*pplist); SListNode* tail = *pplist; SListNode* Pretail = NULL; if (tail->next == NULL) { *pplist = NULL; return; } else { while (tail->next) { Pretail = tail; tail = tail->next; } free(tail); tail = NULL; Pretail->next = NULL; } } void SListPopFront(SListNode** pplist) { assert(*pplist); SListNode* front = *pplist; *pplist = front->next; free(front); front = NULL; } SListNode* SListFind(SListNode* plist, SLTDateType x) { assert(plist); SListNode* pos = plist; while (pos && pos->data != x) { pos = pos->next; } return pos; } void SListInsertAfter(SListNode* pos, SLTDateType x) { assert(pos); SListNode* newnode = BuySListNode(x); newnode->next = pos->next; pos->next = newnode; } void SListEraseAfter(SListNode* pos) { assert(pos); assert(pos->next); SListNode* node = pos->next; pos->next = node->next; free(node); } void SListDestory(SListNode** pplist) { SListNode* node = *pplist; SListNode* PreNode = NULL; while (node) { PreNode = node->next; free(node); node = PreNode; } }
雙向鏈表的結(jié)構(gòu)
SListNode* BuySListNode(SLTDateType x) { SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); if (newnode == NULL) { exit(-1); } newnode->data = x; return newnode; } void SListPrint(SListNode* plist) { if (plist == NULL) { printf("NULL\n"); return; } else { while (plist) { printf("%d->", plist->data); plist = plist->next; } printf("NULL\n"); } } void SListPushBack(SListNode** pplist, SLTDateType x) { SListNode* tail = *pplist; SListNode* newnode = BuySListNode(x); newnode->next = NULL; if (tail == NULL) { *pplist = newnode; } else { while (tail->next) { tail = tail->next; } tail->next = newnode; } } void SListPushFront(SListNode** pplist, SLTDateType x) { SListNode* newnode = BuySListNode(x); newnode->next = *pplist; *pplist = newnode; } void SListPopBack(SListNode** pplist) { assert(*pplist); SListNode* tail = *pplist; SListNode* Pretail = NULL; if (tail->next == NULL) { *pplist = NULL; return; } else { while (tail->next) { Pretail = tail; tail = tail->next; } free(tail); tail = NULL; Pretail->next = NULL; } } void SListPopFront(SListNode** pplist) { assert(*pplist); SListNode* front = *pplist; *pplist = front->next; free(front); front = NULL; } SListNode* SListFind(SListNode* plist, SLTDateType x) { assert(plist); SListNode* pos = plist; while (pos && pos->data != x) { pos = pos->next; } return pos; } void SListInsertAfter(SListNode* pos, SLTDateType x) { assert(pos); SListNode* newnode = BuySListNode(x); newnode->next = pos->next; pos->next = newnode; } void SListEraseAfter(SListNode* pos) { assert(pos); assert(pos->next); SListNode* node = pos->next; pos->next = node->next; free(node); } void SListDestory(SListNode** pplist) { SListNode* node = *pplist; SListNode* PreNode = NULL; while (node) { PreNode = node->next; free(node); node = PreNode; } }
雙向鏈表的功能
//創(chuàng)建鏈表返回頭結(jié)點 LTNode* ListInit(); // 雙向鏈表銷毀 void ListDestory(LTNode* phead); // 雙向鏈表打印 void ListPrint(LTNode* phead); // 雙向鏈表尾插 void ListPushBack(LTNode* phead, LTDateType x); // 雙向鏈表尾刪 void ListPopBack(LTNode* phead); // 雙向鏈表頭插 void ListPushFront(LTNode* phead, LTDateType x); // 雙向鏈表頭刪 void ListPopFront(LTNode* phead); // 雙向鏈表查找 LTNode* ListFind(LTNode* phead, LTDateType x); // 雙向鏈表在pos的前面進行插入 void ListInsert(LTNode* pos, LTDateType x); // 雙向鏈表刪除pos位置的節(jié)點 void ListErase(LTNode* pos);
功能實現(xiàn)
LTNode* ListInit() { //哨兵位頭結(jié)點 LTNode* phead = (LTNode*)malloc(sizeof(LTNode)); if (phead == NULL) { printf("開辟空間失敗!!!\n"); exit(-1); } phead->next = phead; phead->prev = phead; return phead; } void ListDestory(LTNode* phead) { assert(phead); LTNode* cur = phead; LTNode* p = NULL; LTNode* tail = phead->prev; while (cur != tail) { p = cur; cur = cur->next; free(p); } free(tail); } void ListPrint(LTNode* phead) { assert(phead); LTNode* front = phead->next; while (front != phead) { printf("%d ", front->data); front = front->next; } printf("\n"); } void ListPushBack(LTNode* phead, LTDateType x) { assert(phead); LTNode* tail = phead->prev; LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { printf("開辟空間失敗!!\n"); exit(-1); } newnode->data = x; tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; } void ListPopBack(LTNode* phead) { assert(phead); assert(phead != phead->next); LTNode* tail = phead->prev; LTNode* TailFront = tail->prev; TailFront->next = phead; phead->prev = TailFront; free(tail); } void ListPushFront(LTNode* phead, LTDateType x) { assert(phead); LTNode* next = phead->next; LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { printf("開辟空間失敗!!\n"); exit(-1); } newnode->data = x; phead->next = newnode; newnode->prev = phead; newnode->next = next; next->prev = newnode; } void ListPopFront(LTNode* phead) { assert(phead); assert(phead != phead->next); LTNode* head = phead->next;//頭結(jié)點 phead->next = head->next; head->next->prev = phead; free(head); } LTNode* ListFind(LTNode* phead, LTDateType x) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } void ListInsert(LTNode* pos, LTDateType x) { assert(pos); LTNode* posPrev = pos->prev; LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { printf("開辟空間失敗!!\n"); exit(-1); } newnode->data = x; posPrev->next = newnode; newnode->prev = posPrev; newnode->next = pos; pos->prev = newnode; } void ListErase(LTNode* pos) { assert(pos); LTNode* posPrev = pos->prev; LTNode* posNext = pos->next; posPrev->next = posNext; posNext->prev = posPrev; free(pos); }
關(guān)于“C語言鏈表有什么用”這篇文章就分享到這里了,希望以上內(nèi)容可以對大家有一定的幫助,使各位可以學(xué)到更多知識,如果覺得文章不錯,請把它分享出去讓更多的人看到。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。