C/C++语言实现单链表（带头结点）
生活随笔
收集整理的這篇文章主要介紹了
C/C++语言实现单链表（带头结点）
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
徹底理解鏈表中為何使用二級指針或者一級指針的引用
數據結構之鏈表-鏈表實現及常用操作(C++篇)
C語言實現單鏈表，主要功能為空鏈表創建，鏈表初始化（頭插法），鏈表元素讀取，按位置插入，（有序鏈表）按值插入，按位置刪除，按值刪除，清空鏈表，銷毀鏈表。
關鍵思路：（1）將結點創建結構體；（2）鏈表中添加頭結點，以便統一操作；（3）使用結點一級指針和二級指針的異同點；（4）鏈表的最小操作單位是結點；（5）操作的起始位置是頭結點還是第一個結點，及起始索引是0還是1.
#include <stdio.h>
#include <stdlib.h>
#include <time.h> //涉及到結構體自引用
typedef struct Node{
int data;
struct Node *next;
}Node; //創建空鏈表
//必須用二級指針，涉及到頭指針的創建
int iniList(Node **List){
*List = (Node *)malloc(sizeof(Node));
if (NULL == *List){
return ;
} (*List)->next = NULL; //創建頭結點
return ;
} //初始化鏈表(頭插法)
//必須二級指針
int iniListHead(Node **List, int n){
*List = (Node *)malloc(sizeof(Node));
if (NULL == *List){
return ;
}
(*List)->next = NULL;
srand(time()); int i = ;
while (i < n){
Node *tmpNode = (Node *)malloc(sizeof(Node));
if (NULL == tmpNode){
return ;
}
tmpNode->data = rand() % + ;
tmpNode->next = (*List)->next;
(*List)->next = tmpNode; ++i;
}
return ;
} //初始化鏈表(尾插法)
//必須二級指針
//需要借助輔助變量pCurrent，將每次尾插的新元素當做當前元素
int iniListTail(Node **List, int n){
*List = (Node *)malloc(sizeof(Node));
if (NULL == *List){
return ;
}
(*List)->next = NULL;
srand(time()); Node *pCurrent = *List; int i = ;
while (i < n){
Node *tmpNode = (Node *)malloc(sizeof(Node));
if (NULL == tmpNode){
return ;
}
tmpNode->data = rand() % + ;
tmpNode->next = NULL;
pCurrent->next = tmpNode;
pCurrent = tmpNode; ++i;
}
return ;
} //清空鏈表(不刪除頭結點)
//一級，二級指針均可
//首先找到鏈表地址，然后移動至表尾
//判斷條件為指針域是否為空，即到達結尾
int deleteList(Node *List){ //這種方法無法刪除尾結點
//Node *p= List;
//Node *q = NULL;
//
//while (p->next){
// q = p;
// free(p);
// p = q->next;
//} Node *p = List->next;
Node *q = NULL; while (p){
q = p->next;
free(p);
p = q;
} List->next = NULL;
return ;
} //銷毀鏈表
//必須使用二級指針，銷毀頭結點和頭指針
//最后將鏈表頭指針置空
int desrotyList(Node **List){ Node *p = *List;
Node *q = NULL; //如果為空鏈表，直接刪除頭結點
//如果不是空鏈表，從頭結點開始刪除
while (p){
q = p->next;
free(p);
p = q;
}
(*List) = NULL; //下面是從第一個結點開始刪除
//最后釋放掉頭結點
//Node *p = (*List)->next;
//Node *q = NULL;
//
//while (p){
// q = p->next;
// free(p);
// p = q;
//}
//free(*List);
//(*List) = NULL; return ;
} //鏈表獲取元素
//一級，二級指針均可
//頭結點無意義，從第一個結點開始遍歷，i從1開始
//每次都指向下一結點，到pos-1即可
int getList(Node *List, int pos, int *element){
Node *p = List->next; int i = ;
while (p && i < pos){
p = p->next;
++i;
}
*element = p->data;
return ;
} //鏈表按位置插入
//一級，二級指針均可
//從頭結點開始，有可能插入在第一個位置,遍歷從1開始
int insertListPos(Node *List, int pos, int value){
Node *p = List; int i = ;
while (p && i < pos){
p = p->next;
++i;
}
Node *tmpNode = (Node *)malloc(sizeof(Node));
tmpNode->data = value;
tmpNode->next = p->next;
p->next = tmpNode;
return ;
} //有序鏈表，按值插入
//一二級指針均可
int insertListValue(Node *List, int value){
Node *pCur = List->next;
Node *pPer = List;
while (pCur && pCur->data < value){
pPer = pCur;
pCur = pCur->next;
} Node *tmpNode = (Node *)malloc(sizeof(Node));
if (NULL == tmpNode){
return ;
}
tmpNode->data = value;
tmpNode->next = pPer->next;
pPer->next = tmpNode;
return ;
} //鏈表按位置刪除
//一二級指針均可
//記得釋放結點內存
//如果刪除第一個結點，需要操縱頭結點
int deleteListPos(Node *List, int pos){
Node *p = List; int i = ;
while (p && i < pos){
p = p->next;
++i;
}
if (NULL == p->next)
return ; Node *tmpNode = p->next;
p->next = p->next->next; free(tmpNode);
return ;
} //鏈表按值刪除元素
//一二級指針均可
//從第一個結點開始
int deleteListValue(Node *List, int value){
Node *pCur = List->next;
Node *pPer = List; while (pCur && pCur->data != value){
pPer = pCur;
pCur = pCur->next;
}
if (pCur == NULL){ //空鏈表不刪除任何結點
return ;
}
else{
pPer->next = pCur->next;
free(pCur);
}
return ;
} int main(){ Node *testList = NULL;
iniList(&testList);
//iniListHead(&testList, 3);
//iniListTail(&testList, 3); insertListPos(testList, , );
insertListPos(testList, , );
insertListPos(testList, , );
insertListPos(testList, , );
//insertListPos(testList, 1, 1);
insertListValue(testList, ); //deleteListPos(testList, 1);
//deleteListValue(testList, 4); //deleteList(testList); //printf("%d\n", testList);
//desrotyList(&testList);
//printf("%d\n", testList); Node * tmpNode = testList->next;
while (tmpNode){
printf("%d\n", tmpNode->data);
tmpNode = tmpNode->next;
} printf("----------------------\n"); int a = ;
getList(testList, , &a);
printf("%d\n", a); system("pause"); return ;
}
C語言完整代碼
通過C++實現C語言的鏈表，主要區別：（1）struct可以不通過typedef，直接使用Node；（2）將malloc和free更換為new和delete
#include<iostream>
#include<ctime> using namespace std; struct Node{
int data;
Node *next;
}; //創建空鏈表
//必須用二級指針，涉及到頭指針的創建
int iniList(Node **List){
*List = new Node; (*List)->next = NULL; //創建頭結點
return ;
} //初始化鏈表(頭插法)
//必須二級指針
int iniListHead(Node **List, int n){
*List = new Node; (*List)->next = NULL;
srand(time()); int i = ;
while (i < n){
Node *tmpNode = new Node; tmpNode->data = rand() % + ;
tmpNode->next = (*List)->next;
(*List)->next = tmpNode; ++i;
}
return ;
} //初始化鏈表(尾插法)
//必須二級指針
//需要借助輔助變量pCurrent，將每次尾插的新元素當做當前元素
int iniListTail(Node **List, int n){
*List = new Node; (*List)->next = NULL;
srand(time()); Node *pCurrent = *List; int i = ;
while (i < n){
Node *tmpNode = new Node; tmpNode->data = rand() % + ;
tmpNode->next = NULL;
pCurrent->next = tmpNode;
pCurrent = tmpNode; ++i;
}
return ;
} //清空鏈表(不刪除頭結點)
//一級，二級指針均可
//首先找到鏈表地址，然后移動至表尾
//判斷條件為指針域是否為空，即到達結尾
int deleteList(Node *List){ //這種方法無法刪除尾結點
//Node *p= List;
//Node *q = NULL;
//
//while (p->next){
// q = p;
// free(p);
// p = q->next;
//} Node *p = List->next;
Node *q = NULL; while (p){
q = p->next;
delete p;
p = q;
} List->next = NULL;
return ;
} //銷毀鏈表
//必須使用二級指針，銷毀頭結點和頭指針
//最后將鏈表頭指針置空
int desrotyList(Node **List){ Node *p = *List;
Node *q = NULL; //如果為空鏈表，直接刪除頭結點
//如果不是空鏈表，從頭結點開始刪除
while (p){
q = p->next;
delete p;
p = q;
}
(*List) = NULL; //下面是從第一個結點開始刪除
//最后釋放掉頭結點
//Node *p = (*List)->next;
//Node *q = NULL;
//
//while (p){
// q = p->next;
// free(p);
// p = q;
//}
//free(*List);
//(*List) = NULL; return ;
} //鏈表獲取元素
//一級，二級指針均可
//頭結點無意義，從第一個結點開始遍歷，i從1開始
//每次都指向下一結點，到pos-1即可
int getList(Node *List, int pos, int *element){
Node *p = List->next; int i = ;
while (p && i < pos){
p = p->next;
++i;
}
*element = p->data;
return ;
} //鏈表按位置插入
//一級，二級指針均可
//從頭結點開始，有可能插入在第一個位置,遍歷從1開始
int insertListPos(Node *List, int pos, int value){
Node *p = List; int i = ;
while (p && i < pos){
p = p->next;
++i;
}
Node *tmpNode = new Node;
tmpNode->data = value;
tmpNode->next = p->next;
p->next = tmpNode;
return ;
} //有序鏈表，按值插入
//一二級指針均可
int insertListValue(Node *List, int value){
Node *pCur = List->next;
Node *pPer = NULL;
while (pCur && pCur->data < value){
pPer = pCur;
pCur = pCur->next;
} Node *tmpNode = new Node;
if (NULL == tmpNode){
return ;
}
tmpNode->data = value;
tmpNode->next = pPer->next;
pPer->next = tmpNode;
return ;
} //鏈表按位置刪除
//一二級指針均可
//記得釋放結點內存
//如果刪除第一個結點，需要操縱頭結點
int deleteListPos(Node *List, int pos){
Node *p = List; int i = ;
while (p && i < pos){
p = p->next;
++i;
}
Node *tmpNode = p->next;
p->next = p->next->next; delete tmpNode;
return ;
} //鏈表按值刪除元素
//一二級指針均可
//從第一個結點開始
int deleteListValue(Node *List, int value){
Node *pCur = List->next;
Node *pPer = List; while (pCur && pCur->data != value){
pPer = pCur;
pCur = pCur->next;
}
if (pCur == NULL){
return ;
}
else{
pPer->next = pCur->next;
delete pCur;
}
return ;
}
C++完整代碼
結點結構體
將結點創建為結構體，其中包含數據域和指針域成員，指針域涉及結構體自引用。指針域成員之所以為結點類指針，一是為了編譯時能明確結構體大小，二是為了指向下一個結點，因此初始化時不用開辟內存，只需要賦值為NULL即可。當然了，開辟內存也是可以的，這樣在刪除結點，及清空鏈表時需要記得將其釋放，多此一舉，不提倡。
//涉及到結構體自引用
typedef struct Node{
int data;
struct Node *next;
}Node;
空鏈表創建（二級指針）
空鏈表創建時，建議創建頭結點。在插入和刪除第一個位置的元素時，需要用結點的二級指針移動頭指針，但普通結點的插入和刪除并不需要移動頭指針。為了便于操作的統一（指插入和刪除操作），這里先創建頭結點。
另外，在創建空鏈表時，需要傳入二級指針，主要是為了操作頭指針，只要涉及操作頭指針的都需要使用二級指針。
//創建空鏈表
//必須用二級指針，涉及到頭指針的創建
int iniList(Node **List){
*List = (Node *)malloc(sizeof(Node));
if (NULL == *List){
return ;
} (*List)->next = NULL; //創建頭結點，將其指針域置空
return ;
}
鏈表初始化（二級指針）
鏈表初始化，即是創建空鏈表，并對鏈表中的n個元素進行賦值。一般來說，有頭插法、尾插法兩種，頭插法是在頭結點后插入，尾插法是在鏈表尾插入。
頭插法
頭插法一般思路：（1）創建帶頭結點的空鏈表；（2）創建新結點，對新結點賦值；（3）新結點指向頭結點的下一個結點，頭結點指向新結點。
//初始化鏈表(頭插法)
//必須二級指針
int iniListHead(Node **List, int n){
*List = (Node *)malloc(sizeof(Node));
if (NULL == *List){
return ;
}
(*List)->next = NULL;
srand(time()); int i = ;
while (i < n){
Node *tmpNode = (Node *)malloc(sizeof(Node));
if (NULL == tmpNode){
return ;
}
tmpNode->data = rand() % + ;
tmpNode->next = (*List)->next;
(*List)->next = tmpNode; ++i;
}
return ;
}
尾插法
尾插法一般思路：（1）創建帶頭結點的空鏈表；（2）創建新結點，對新結點數據域賦值，指針域置空；（3）建立臨時變量指向頭結點，頭結點指向新結點；（4）將臨時變量往后移動，指向新結點。
//初始化鏈表(尾插法)
//必須二級指針
//需要借助輔助變量pCurrent，將每次尾插的新元素當做當前元素
int iniListTail(Node **List, int n){
*List = (Node *)malloc(sizeof(Node));
if (NULL == *List){
return ;
}
(*List)->next = NULL;
srand(time()); Node *pCurrent = *List; int i = ;
while (i < n){
Node *tmpNode = (Node *)malloc(sizeof(Node));
if (NULL == tmpNode){
return ;
}
tmpNode->data = rand() % + ;
tmpNode->next = NULL;
pCurrent->next = tmpNode;
pCurrent = tmpNode; ++i;
}
return ;
}
鏈表元素讀取（一、二級指針）
鏈表元素讀取，需要涉及到索引位置。我們知道頭結點的數據域沒有意義，因此起始位置從第一個結點開始，遍歷值從1開始，到pos-1為止，此時p指向pos結點。
//鏈表獲取元素
//一級，二級指針均可
//頭結點無意義，從第一個結點開始遍歷，i從1開始
//每次都指向下一結點，到pos-1即可
int getList(Node *List, int pos, int *element){
Node *p = List->next; int i = ;
while (p && i < pos){
p = p->next;
++i;
}
*element = p->data;
return ;
}
按位置插入（一、二級指針）
插入時，需要考慮任意位置，由于頭結點的設立，我們不需要單獨考慮第一個位置的結點插入。
一般思路：（1）起始位置從頭結點開始，遍歷值從1開始，到pos-1為止，此時指向pos-1結點；（2）創建新結點，給新結點數據域賦值；（3）新結點指向pos位置的下一結點，pos位置指向新結點。
//鏈表按位置插入
//一級，二級指針均可
//從頭結點開始，有可能插入在第一個位置,遍歷從1開始
int insertListPos(Node *List, int pos, int value){
Node *p = List; int i = ;
while (p && i < pos){
p = p->next;
++i;
}
Node *tmpNode = (Node *)malloc(sizeof(Node));
tmpNode->data = value;
tmpNode->next = p->next;
p->next = tmpNode;
return ;
}
有序鏈表按值插入（一、二級指針）
有序鏈表中涉及到按值插入，按值刪除時，需要建立兩個臨時變量，不同于按位置插入，我們可以在pos前一個停止遍歷，按值插入，我們需要遍歷找到插入位置，操作插入位置的前一個結點。
一般思路：（1）從第一個結點開始遍歷；（2）創建per變量標記當前結點的前一結點；（3）創建新結點，操作per結點；（4）常規插入操作。
//有序鏈表，按值插入
//一二級指針均可
int insertListValue(Node *List, int value){
Node *pCur = List->next;
Node *pPer = NULL;
while (pCur && pCur->data < value){
pPer = pCur;
pCur = pCur->next;
} Node *tmpNode = (Node *)malloc(sizeof(Node));
if (NULL == tmpNode){
return ;
}
tmpNode->data = value;
tmpNode->next = pPer->next;
pPer->next = tmpNode;
return ;
}
按位置刪除（一、二級指針）
刪除時，由于頭結點的設立，因此不需要特殊考慮第一個位置的操作和頭指針的移動。需要設置臨時變量是釋放p->next后，后面還會使用p->next的結點，這樣會造成訪問出錯。
一般思路：（1）起始位置從頭結點開始，遍歷從1開始，到pos-1為止，此時指向pos-1結點；（2）創建臨時變量，指向pos結點；（3）將pos-1結點指向pos的下一結點，釋放掉pos結點。
//鏈表按位置刪除
//一二級指針均可
//記得釋放結點內存
//如果刪除第一個結點，需要操縱頭結點
int deleteListPos(Node *List, int pos){
Node *p = List; int i = ;
while (p && i < pos){
p = p->next;
++i;
}
Node *tmpNode = p->next;
p->next = p->next->next; free(tmpNode);
return ;
}
按值刪除（一、二級指針）
按值刪除與按值插入一樣，需要兩個臨時變量。
一般思路：（1）起始位置從第一個結點開始，（2）設立per結點指針保存當前結點的上一結點；（3）常規刪除操作。
//鏈表按值刪除元素
//一二級指針均可
//從第一個結點開始
int deleteListValue(Node *List, int value){
Node *pCur = List->next;
Node *pPer = List; while (pCur && pCur->data != value){
pPer = pCur;
pCur = pCur->next;
}
if (pCur == NULL){ //空鏈表不刪除任何結點
return ;
}
else{
pPer->next = pCur->next;
free(pCur);
}
return ;
}
清空鏈表（一、二級指針）
清空鏈表，只是將鏈表中的結點刪除，并釋放掉結點空間，保留頭結點，并將頭結點的指針域置空。
一般思路：（1）起始位置從第一個結點開始；（2）設置臨時變量q指向當前結點p的下一結點，釋放掉當前結點p，將臨時變量q賦給p；（3）最后將頭結點的指針置空。
//清空鏈表(不刪除頭結點)
//一級，二級指針均可
//首先找到鏈表地址，然后移動至表尾
//判斷條件為指針域是否為空，即到達結尾
int deleteList(Node *List){ //這種方法無法刪除尾結點，當p->next是尾結點上一節點時，走一遍程序
//Node *p= List;
//Node *q = NULL;
//
//while (p->next){
// q = p;
// free(p);
// p = q->next;
//} Node *p = List->next;
Node *q = NULL; while (p){
q = p->next;
free(p);
p = q;
} List->next = NULL;
return ;
}
銷毀鏈表（二級指針）
銷毀鏈表，是在清空鏈表的基礎上，刪除頭結點，將頭指針置空，涉及到頭指針的操作，需要二級指針。
思路一：（1）與清空鏈表操作相同，從第一個結點開始刪除；（2）最后釋放掉頭結點，將頭指針置空
思路二：（1）起始位置從頭結點開始刪除；（2）將頭指針置空
//銷毀鏈表
//必須使用二級指針，銷毀頭結點和頭指針
//最后將鏈表頭指針置空
int desrotyList(Node **List){ Node *p = *List;
Node *q = NULL; //如果為空鏈表，直接刪除頭結點
//如果不是空鏈表，從頭結點開始刪除
while (p){
q = p->next;
free(p);
p = q;
}
(*List) = NULL; //下面是從第一個結點開始刪除
//最后釋放掉頭結點
//Node *p = (*List)->next;
//Node *q = NULL;
//
//while (p){
// q = p->next;
// free(p);
// p = q;
//}
//free(*List);
//(*List) = NULL; return ;
}
二級指針和一級指針插入解析
-------------------------------------------------------------------------------------------------------------
如果上面的資料對你有啟發，麻煩點個推薦，讓更多人的人看到哦。
關注公眾號【兩猿社】，懂點互聯網，懂點IC的程序猿，帶你豐富項目經驗哦。
總結
以上是生活随笔為你收集整理的C/C++语言实现单链表（带头结点）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 闺蜜结婚送一只泰迪熊可以嘛，两只不好拿，
- 下一篇： 开黑游戏哪个平台还有组队一起玩的呀？