您好,登錄后才能下訂單哦!
這篇文章將為大家詳細(xì)講解有關(guān)C語言如何實(shí)現(xiàn)單鏈表,小編覺得挺實(shí)用的,因此分享給大家做個(gè)參考,希望大家閱讀完這篇文章后可以有所收獲。
C語言實(shí)現(xiàn)單鏈表實(shí)現(xiàn)方法
鏈表和我們之前實(shí)現(xiàn)過的順序表一樣,都是簡單的數(shù)據(jù)結(jié)構(gòu),鏈表分為單向鏈表、雙向鏈表、循環(huán)鏈表。而單向鏈表又分為兩種實(shí)現(xiàn)方法,一種為帶頭節(jié)點(diǎn)的單鏈表,一種為不帶頭節(jié)點(diǎn)的單鏈表。我們來具體看看不帶頭節(jié)點(diǎn)的單鏈表的實(shí)現(xiàn)
單鏈表:它是一種鏈?zhǔn)酱鎯Φ木€性表,用一組地址任意的存儲單元存放線性表的數(shù)據(jù)元素,稱存儲單元為一個(gè)節(jié)點(diǎn)。
今天我們來實(shí)現(xiàn)一些單鏈表的簡單接口
先看看單鏈表的結(jié)構(gòu): (為了通用性,我們將類型重命名為DataType)
typedef int DataType; //鏈表 typedef struct Node { DataType *data; struct Node *next; }Node, *pNode, *pList;
接下來看看我們要實(shí)現(xiàn)的接口:
void InitLinkList(pList *pplist);//初始化鏈表 pNode BuyNode(DataType d);//創(chuàng)建鏈表節(jié)點(diǎn) void PushBack(pList *pplist, DataType d);//尾插 void PopBack(pList *pplist);//尾刪 void PushFront(pList *pplist, DataType d);//頭插 void PopFront(pList *pplist);//頭刪 void PrintList(pList plist);//打印鏈表 pNode Find(pList plist, DataType d);//查找指定元素 void Remove(pList *pplist, DataType d);//刪除指定的一個(gè)元素 void RemoveAll(pList *pplist, DataType d);//刪除指定的所有元素 void Insert(pList *pplist, pNode pos, DataType d);//指定位置的后面插入 void Erase(pList *pplist, pNode pos);//指定位置刪除 void DestroyList(pList *pplist);//銷毀鏈表
來看看每個(gè)接口的具體實(shí)現(xiàn):
pNode BuyNode(DataType d) { pNode newNode = (pNode)malloc(sizeof(Node)); if (newNode == NULL) { perror("malloc"); exit(EXIT_FAILURE); } newNode->data = d; newNode->next = NULL; return newNode; } void InitLinkList(pList *pplist) { assert(pplist); *pplist = NULL; } void PushBack(pList *pplist, DataType d) { assert(pplist); pNode newNode = BuyNode(d); pNode cur = *pplist; //鏈表沒有節(jié)點(diǎn) if (*pplist == NULL) { *pplist = newNode; return; } //鏈表有節(jié)點(diǎn) while (cur->next != NULL) { cur = cur->next; } cur->next = newNode; } void PopBack(pList *pplist) { pNode cur = *pplist; pNode prev = NULL; assert(pplist); //鏈表沒有節(jié)點(diǎn) if (*pplist == NULL) { return; } //鏈表有一個(gè)節(jié)點(diǎn) if (cur->next == NULL) { free(*pplist); *pplist = NULL; return; } //鏈表有兩個(gè)及兩個(gè)以上節(jié)點(diǎn) while (cur->next != NULL) { prev = cur;//prev中保存的是cur之前的那個(gè)節(jié)點(diǎn) cur = cur->next; } prev->next = NULL; free(cur); } void PushFront(pList *pplist, DataType d) { pNode newNode = BuyNode(d); //pNode cur = *pplist; assert(pplist); ////鏈表沒有節(jié)點(diǎn) //if (*pplist == NULL) //{ // *pplist = newNode; //} ////鏈表有節(jié)點(diǎn) newNode->next = *pplist; *pplist = newNode; } void PopFront(pList *pplist) { pNode cur = *pplist; assert(pplist); //鏈表為空 if (*pplist == NULL) { return; } *pplist = cur->next; free(cur); cur = NULL; } void PrintList(pList plist) { pNode cur = plist; while (cur) { printf("%d-->", cur->data); cur = cur->next; } printf("NULL\n"); } pNode Find(pList plist, DataType d) { pNode cur = plist; while (cur) { if (cur->data == d) { return cur; } cur = cur->next; } return NULL; } void Remove(pList *pplist, DataType d) { pNode cur = *pplist; pNode prev = NULL; assert(pplist); if (cur == NULL) { return; } while (cur) { if (cur->data == d) { pNode del = cur; if (cur == *pplist) { *pplist = cur->next; } prev->next = cur->next; free(del); del = NULL; return; } else { prev = cur; cur = cur->next; } } } void RemoveAll(pList *pplist, DataType d) { pNode cur = *pplist; pNode prev = NULL; assert(pplist); if (*pplist == NULL) { return; } while (cur) { if (cur->data == d) { pNode del = cur; if (cur == *pplist) { *pplist = cur->next; } else { prev->next = cur->next; } cur = cur->next; free(del); del = NULL; } else { prev = cur; cur = cur->next; } } } //在pos后面插入一個(gè)元素 void Insert(pList *pplist, pNode pos, DataType d) { pNode newNode = BuyNode(d); assert(pplist); assert(pos); if (*pplist == NULL) { PushFront(pplist, d); return; } newNode->next = pos->next; pos->next = newNode; } void Erase(pList *pplist, pNode pos) { assert(pplist); assert(pos); //要?jiǎng)h除的是尾節(jié)點(diǎn) if (pos->next == NULL) { PopBack(pplist); } //刪除的是非尾節(jié)點(diǎn) else { pNode del = pos->next; pos->data = pos->next->data; pos->next = pos->next->next; free(del); del = NULL; } } void DestroyList(pList *pplist) { assert(pplist); pNode cur = *pplist; while (cur) { pNode del = cur; cur = cur->next; printf("del:%d\n", del->data); free(del); del = NULL; } }
由于這些接口都較為簡單,所以不進(jìn)行具體的測試展示,讀者可以自行測試
關(guān)于“C語言如何實(shí)現(xiàn)單鏈表”這篇文章就分享到這里了,希望以上內(nèi)容可以對大家有一定的幫助,使各位可以學(xué)到更多知識,如果覺得文章不錯(cuò),請把它分享出去讓更多的人看到。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。