C語言實現(xiàn)無頭單向鏈表的示例代碼
一、易錯的接口實現(xiàn)
1.1 新節(jié)點開辟函數(shù)
由于創(chuàng)建一個新節(jié)點是頻繁的操作,所以封裝為一個接口最佳。
鏈表節(jié)點的屬性有:(1)數(shù)值。(2)指向下一個節(jié)點的地址。(3)自身地址。
static SLTNode* BuySListNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); //開辟失敗 if (newnode == NULL) { printf("malloc fail\n"); exit(-1); } //初始化 newnode->data = x; newnode->next = NULL; return newnode; }
數(shù)值和next地址都由此函數(shù)初始化,自身地址則由函數(shù)的返回值返回。
要注意使用malloc函數(shù)時,可能存在開辟空間失敗的情況,這時會返回NULL。
1.2 尾插
尾插的難點在于存在特殊情況。
當(dāng)對非空鏈表和空鏈表進行尾插時,所需代碼不同。
對非空鏈表尾插時,算法是:找到此鏈表的尾部,即遍歷此鏈表,直至自定義的結(jié)構(gòu)體指針tail的下一個節(jié)點為NULL,結(jié)束遍歷。在tail的后面插入一個新節(jié)點。
對空鏈表尾插時,算法是:直接把新節(jié)點作為鏈表的頭節(jié)點。
void SListPushBack(SLTNode** pphead, SLTDataType x) { assert(pphead); //找尾 SLTNode* tail = *pphead; if (tail == NULL) { tail = BuySListNode(x); *pphead = tail; } else { while (tail->next != NULL) { tail = tail->next; } SLTNode* newnode = BuySListNode(x); tail->next = newnode; } }
1.3 尾刪
此接口也有特殊情況處理。
當(dāng)鏈表有一個以上的節(jié)點時,算法:遍歷鏈表到尾部,free掉tail所在內(nèi)存,改變tail之前一個節(jié)點的next,為NULL。
需要一個結(jié)構(gòu)體指針變量prev來記錄tail的前一個節(jié)點。
當(dāng)鏈表只有一個節(jié)點時,算法:tail一開始就在尾部,直接free掉tail,再把prev指針(初值為NULL)賦值給頭節(jié)點*pphead。
如果不單獨考慮這種情況的話,會因為NULL->next而出現(xiàn)內(nèi)存錯誤。
當(dāng)鏈表沒有節(jié)點時,是不可以調(diào)用尾刪的,直接用assert函數(shù)報錯。
void SListPopBack(SLTNode** pphead) { assert(pphead); assert(*pphead);//沒有節(jié)點斷言報錯 SLTNode* prev = NULL; SLTNode* tail = *pphead; while (tail->next != NULL) { prev = tail; tail = tail->next; } free(tail); tail = NULL; if (prev != NULL) prev->next = NULL; else *pphead = prev; }
二、常見簡單接口
2.1 打印鏈表
void SListPrint(SLTNode* phead) { SLTNode* cur = phead; while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }
2.2 節(jié)點計數(shù)器
int SListSize(SLTNode* phead) { //計數(shù)器 int count = 0; SLTNode* cur = phead; while (cur) { count++; cur = cur->next; } return count; }
2.3 判斷是否為空鏈表
bool SListEmpty(SLTNode* phead) { return phead == NULL; }
2.4 通過值查找節(jié)點
SLTNode* SListFind(SLTNode* phead, SLTDataType data) { //通過數(shù)據(jù)查找節(jié)點-遍歷節(jié)點,判斷值是否相等 SLTNode* cur = phead; while (cur) { if (cur->data == data) return cur; cur = cur->next; } return NULL; }
2.5 頭插
void SListPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode = BuySListNode(x); newnode->next = *pphead; *pphead = newnode; }
2.6 頭刪
void SListPopFront(SLTNode** pphead) { assert(pphead); assert(*pphead); SLTNode* next = (*pphead)->next; free(*pphead); *pphead = NULL; *pphead = next; }
2.7 在任意節(jié)點后插入節(jié)點
void SListInsert(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newnode = BuySListNode(x); SLTNode* next = pos->next; pos->next = newnode; newnode->next = next; }
2.8 在任意節(jié)點后刪除節(jié)點
void SListErase(SLTNode* pos) { assert(pos); assert(pos->next); SLTNode* next = pos->next; pos->next = next->next; free(next); next = NULL; }
2.9 銷毀鏈表
void SListDestroy(SLTNode** pphead) { assert(pphead); SLTNode* cur, * nextnode; cur = *pphead; nextnode = NULL; while (cur) { nextnode = cur->next; free(cur); cur = nextnode; } *pphead = NULL; }
三、頭文件相關(guān)內(nèi)容
3.1 引用的庫函數(shù)
#include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h>
3.2 結(jié)構(gòu)體聲明
typedef int SLTDataType;//重定義可便于修改值的數(shù)據(jù)類型 1 typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode;//重定義可減少代碼冗余
到此這篇關(guān)于C語言實現(xiàn)無頭單向鏈表的示例代碼的文章就介紹到這了,更多相關(guān)C語言無頭單向鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
美化你的代碼 vb(VBS)代碼格式化的實現(xiàn)代碼
雖然VB.NET出現(xiàn)很久了,但還有好多人仍然在使用VB6。我在實現(xiàn)一些小功能的時候也喜歡用VB6,畢竟誰都不想每天的美好心情被VS那烏龜般的啟動速度影響2012-05-05C/C++中CJSON的使用(創(chuàng)建與解析JSON數(shù)據(jù))
cJSON是一個超輕巧的JSON解析器,本文主要介紹了C/C++中CJSON的使用(創(chuàng)建與解析JSON數(shù)據(jù)),具有一定的參考價值,感興趣的可以了解一下2021-09-09udp socket客戶端和udp服務(wù)端程序示例分享
這篇文章主要介紹了udp socket客戶端和udp服務(wù)端程序示例,需要的朋友可以參考下2014-03-03C語言實現(xiàn)銷售管理系統(tǒng)設(shè)計
這篇文章主要為大家詳細介紹了C語言實現(xiàn)銷售管理系統(tǒng)設(shè)計,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下2022-03-03