單鏈表

實(shí)際中鏈表的結(jié)構(gòu)非常多樣，以下情況組合起來就有8種鏈表結(jié)構(gòu)：

單向、雙向

帶頭、不帶頭

循環(huán)、非循環(huán)

雖然有這么多的鏈表的結(jié)構(gòu)，但是我們實(shí)際中最常用還是兩種結(jié)構(gòu)：

無頭單向非循環(huán)鏈表：結(jié)構(gòu)簡單，一般不會(huì)單獨(dú)用來存數(shù)據(jù)。實(shí)際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié) 構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在學(xué)校的考試中出現(xiàn)很多。

帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨(dú)存儲(chǔ)數(shù)據(jù)。實(shí)際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向 循環(huán)鏈表。另外這個(gè)結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實(shí)現(xiàn)以后會(huì)發(fā)現(xiàn)結(jié)構(gòu)會(huì)帶來很多優(yōu)勢，實(shí)現(xiàn)反而 簡單了

實(shí)現(xiàn)不帶頭單鏈表以及相關(guān)操作

頭文件

#pragma oncetypedef int SLDateType;//一個(gè)結(jié)點(diǎn) typedef struct SLNode{SLDateType value;struct SLNode *next; } SListNode;//不帶頭動(dòng)態(tài)鏈表 typedef struct SList{SListNode *first; }SList;//初始化 void SListInit(SList *list); //銷毀 void SListDestroy(SList *list); //增 //頭插 void SListPushFront(SList *list, SLDateType value); //尾插 void SListPushBack(SList *list, SLDateType value);//刪 //頭刪 void SListPopFront(SList *list); //尾刪 void SListPopBack(SList *list);//打印 void SListPrint(const SList *list);//改 void SListUpdata(SListNode *node, SLDateType value);//查 //去查找鏈表中遇到的第一個(gè)value，如果沒找到，返回NULL SListNode *SListFind(const SList *list, SLDateType value);//打印 void SListPrint(const SList *list);void SListInsertBefore(SList *list, SListNode *pos, SLDateType value); // 在pos的后面插入 void SListInsertAfter(SListNode *pos,SLDateType value); // 刪除pos位置的節(jié)點(diǎn) void SListEraseAfter(SListNode *pos); void ListRemove();

功能實(shí)現(xiàn)

#include"SList.h" #include<stdlib.h> #include<assert.h> #include<malloc.h> #include<stdio.h>//初始化 void SListInit(SList *list){assert(list != NULL);list->first = NULL; }//申請新結(jié)點(diǎn) SListNode* BuyNode(SLDateType value){SListNode *node = (SListNode*)malloc(sizeof(SListNode));assert(node);node->value = value;node->next = NULL;return node; } //頭插 void SListPushFront(SList *list, SLDateType value){SListNode *node = (SListNode*)malloc(sizeof(SListNode));assert(node);node->value = value;node->next = list->first;list->first = node; }//頭刪 void SListPopFront(SList *list){assert(list != NULL); //鏈表存在assert(list->first != NULL); //鏈表不為空，里面有結(jié)點(diǎn)SListNode *old_first = list->first;list->first = list->first->next;free(old_first); } //尾插 void SListPushBack(SList *list, SLDateType value){assert(list != NULL);if (list->first == NULL){ //鏈表中沒有結(jié)點(diǎn)的情況就跟頭插的情況是一樣的SListPushFront(list, value);return;}//鏈表中有結(jié)點(diǎn)的情況SListNode *cur;for (cur = list->first; cur->next != NULL; cur = cur->next);//cur就是最后一個(gè)結(jié)點(diǎn)SListNode *node = BuyNode(value);cur->next = node; }//尾刪 void SListPopBack(SList *list){assert(list != NULL);assert(list->first != NULL);//只有一個(gè)結(jié)點(diǎn)if (list->first->next == NULL){SListPopFront(list);return;}SListNode *cur = list->first;while (cur->next->next != NULL){cur = cur->next;}free(cur->next);cur->next = NULL; }//銷毀 void SListDestroy(SList *list){assert(list != NULL);SListNode *cur = list->first;SListNode *next;while (cur!=NULL){next = cur->next;free(cur);cur = cur->next;}list->first = NULL; }//打印 void SListPrint(const SList *list){for (SListNode *cur = list->first; cur != NULL; cur = cur->next){printf("%d--->", cur->value);}printf("\n"); }//改 void SListUpdata(SListNode *node, SLDateType value){node->value = value; }//去查找鏈表中遇到的第一個(gè)value，如果沒找到，返回NULL SListNode *SListFind(const SList *list, SLDateType value){for (SListNode *cur = list->first; cur != NULL; cur = cur->next){if (cur->value == value){return cur;}}return NULL; }//pos 一定是鏈表中有效結(jié)點(diǎn) //向后面插入 void SListInsertAfter(SListNode *pos, SLDateType value){SListNode *node = BuyNode(value); //申請結(jié)點(diǎn)node->next = pos->next;pos->next = node; }// 刪除pos后面位置的節(jié)點(diǎn) void SListEraseAfter(SListNode *pos){SListNode *next = pos->next;pos->next = next->next;free(next);}//向pos前面插入 void SListInsertBefore(SList *list, SListNode *pos, SLDateType value){SListNode *cur;SListNode *node = BuyNode(value);for (cur = list->first; cur->next != pos; cur = cur->next);node->next = pos;cur->next = node; }

測試用例

#include"SList.h" #include<stdlib.h> #include<assert.h> #include<stdio.h>void TestList1(){SList list;SListInit(&list);assert(list.first == NULL);/*SListPushFront(&list, 1);SListPushFront(&list, 2);SListPushFront(&list, 3);//3 2 1*/SListPushBack(&list, 11);SListPushBack(&list, 12);SListPushBack(&list, 13);//3 2 1 11 12 13/*SListPopBack(&list);SListPopBack(&list);SListPopBack(&list);*/SListNode *n12 = SListFind(&list, 12);assert(n12 != NULL);SListPrint(&list);SListInsertAfter(n12, 103);SListPrint(&list);SListEraseAfter(n12);SListPrint(&list);SListInsertBefore(&list,n12, 101);SListPrint(&list);printf("大成功\n"); }int main() {TestList1();system("pause");return 0; }

總結(jié)

以上是生活随笔為你收集整理的再写单链表（不带头单链表）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。