一.鏈表的定義
概念：鏈表是一種物理存盤結構上非連續、非順序的存盤結構，資料元素的邏輯順序是通過鏈表中的指標鏈
接次序實作的,相當于一個一個的結點鏈接在一起就構成了鏈表.如下圖所示.
無頭單向非回圈鏈表：結構簡單，一般不會單獨用來存資料，實際中更多是作為其他資料結構的子結
構，如哈希桶、圖的鄰接表等等，另外這種結構在筆試面試中出現很多，
二.鏈表的實作
1,無頭+單向+非回圈鏈表增刪查改實作
其具體思路如下圖所示
這樣具體的思路就有了,然后是具體的程式代碼
先是頭檔案
1 #include<stdio.h> 2 #include <stdlib.h> 3 #include<malloc.h> 4 #include<assert.h> 5 6 typedef int SLTDataType; 7 8 typedef struct SListNode 9 { 10 SLTDataType data; 11 struct SListNode* next; 12 }SLTNode; 13 14 // 單向+不帶頭+不回圈 15 void SListPrint(SLTNode* plist); //列印鏈表 16 SLTNode* BuySLTNode(SLTDataType x);//創建節點 17 void SListPushBack(SLTNode** pplist, SLTDataType x); //尾插 18 void SListPushFront(SLTNode** pplist, SLTDataType x);// 頭插 19 20 void SListPopBack(SLTNode** pplist); //尾刪 21 void SListPopFront(SLTNode** pplist);//頭刪 22 23 SLTNode* SListFind(SLTNode* plist, SLTDataType x);//查找 24 void SListInsertAfter(SLTNode* pos,SLTDataType x);//pos后插入 25 void SListInsertBefore(SLTNode**pplist,SLTNode* pos,SLTDataType x);//pos前插入 26 void SListEraseAfter(SLTNode* pos);//洗掉指定資料
函式的具體實作
1 #include"SList.h" 2 void SListPrint(SLTNode* plist) 3 { 4 SLTNode* cur=plist; 5 while(cur!=NULL) 6 { 7 printf("%d->",cur->data); 8 cur=cur->next; 9 } 10 printf("NULL\n"); 11 } 12 SLTNode* BuySLTNode(SLTDataType x) 13 { 14 SLTNode *node=(SLTNode*)malloc(sizeof(SLTNode)); 15 node->data=https://www.cnblogs.com/etta-7/p/x; 16 node->next=NULL; 17 return node; 18 } 19 void SListPushBack(SLTNode** pplist, SLTDataType x) //尾插 20 { 21 SLTNode* newnode = BuySLTNode(x); 22 if(*pplist==NULL) 23 { 24 *pplist=newnode ; 25 } 26 else 27 { 28 SLTNode*tail=*pplist; 29 while(tail->next!=NULL) 30 { 31 tail=tail->next; 32 } 33 tail->next=newnode; 34 } 35 } 36 void SListPushFront(SLTNode** pplist, SLTDataType x) //頭插 37 { 38 SLTNode* newnode = BuySLTNode(x); 39 newnode->next=*pplist; 40 *pplist=newnode; 41 } 42 void SListPopBack(SLTNode** pplist)//尾刪 43 { 44 if(*pplist==NULL) 45 { 46 return ; 47 } 48 else if((*pplist)->next==NULL) 49 { 50 free(*pplist); 51 *pplist=NULL; 52 } 53 else 54 { 55 SLTNode* prev=NULL; 56 SLTNode*tail=*pplist; 57 while(tail->next!=NULL) 58 { 59 prev=tail; 60 tail=tail->next; 61 } 62 free(tail); 63 tail->next=NULL; 64 prev->next=NULL; 65 } 66 } 67 void SListPopFront(SLTNode** pplist)//頭刪 68 { 69 if(*pplist==NULL) 70 { 71 return ; 72 } 73 else 74 { 75 SLTNode* node = *pplist; 76 *pplist = node->next; 77 free(node); 78 } 79 } 80 SLTNode* SListFind(SLTNode* plist, SLTDataType x)// 查找節點 81 { 82 SLTNode* cur = plist; 83 while(cur) 84 { 85 if(cur->data=https://www.cnblogs.com/etta-7/p/=x) 86 { 87 return cur; 88 } 89 cur=cur->next; 90 } 91 return NULL; 92 } 93 void SListInsertAfter(SLTNode* pos,SLTDataType x) //插入節點到指定位置的后面 94 { 95 assert(pos); 96 SLTNode* newnode = BuySLTNode(x); 97 newnode->next=pos->next; 98 pos->next=newnode; 99 } 100 void SListInsertBefore(SLTNode**pplist,SLTNode* pos,SLTDataType x) 101 { 102 assert(pos); 103 SLTNode* newnode = BuySLTNode(x); 104 if(pos==*pplist)//認為是頭插 105 { 106 newnode->next=pos; 107 *pplist=newnode; 108 } 109 else 110 { 111 SLTNode* prev = NULL; 112 SLTNode* cur = *pplist; 113 while(cur!=pos) 114 { 115 prev=cur; 116 cur=cur->next; 117 } 118 prev->next=newnode; 119 newnode->next=pos; 120 } 121 } 122 void SListEraseAfter(SLTNode* pos)//指定某一節點后續位置 123 { 124 assert(pos); 125 if(pos->next==NULL) 126 { 127 return ; 128 } 129 else 130 { 131 SLTNode*next=pos->next; 132 pos->next=next->next; 133 free(next); 134 } 135 }
主函式呼叫
#include"SList.h" void Test() { SLTNode* plist=NULL; SListPushBack(&plist,2); SListPushBack(&plist,3); SListPushBack(&plist,4); SListPushBack(&plist,5); SListPushFront(&plist,6); SListPrint(plist); SListPopBack(&plist); SListPrint(plist); SListPopFront(&plist); SLTNode* pos = SListFind(plist, 3); SListInsertAfter(pos,40); SListPrint(plist); SListInsertBefore(&plist,pos,300); SListPrint(plist); SListEraseAfter(pos); SListPrint(plist); } int main() { Test(); return 0; }
本文來自博客園，作者：ETTA-7，轉載請注明原文鏈接：https://www.cnblogs.com/etta-7/
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/412839.html
標籤：C