單鏈表的實作以及相關操作
記錄自己學習的知識如果有錯誤的地方多多包涵請您指出，我會加以改造，都是自己的理解一個成長的愛好者，
1>什么是單鏈表？
不同于線性表中的順序儲存，每個節點只存放資料元素（而且分配時是連續的物理地址），而單鏈表每個節點除了存放資料還有存放指向下一個節點的指標（而且分配時不需要連續的物理地址空間）
所以在理論上兩者實作方式不同
順序表優缺點 單鏈表優缺點
優點：可以隨機存取，存取密度高 優點：不需要連續的地址空間，移動元素比較便利
缺點：需要連續的空間地址，移動元素不方便 缺點：不可以隨機存取，同時需要耗費一定的空間去存放指標
2>定義一個單鏈表
typedef的含義與用法:typedef是在計算機編程語言中用來為復雜的宣告定義簡單的別名，它與宏定義有些差異，它本身是一種存盤類的關鍵字，與auto、extern、mutable、static、register等關鍵字不能出現在同一個運算式中（可以對資料型別進行重新定義）
例如：對int i進行賦值
在沒有對資料型別進行重定義時:int i=5
對資料型別進行重定義后:i=5;
由此可見因為單鏈表是一種鏈式節點的表他的型別是struct（結構型）所以使用重定義后可以是撰寫代碼時更加簡便提升效率
typedef struct LNode //定義單鏈表的型別
{
int data;//每個節點存放的資料元素
struct LNode *next;//指標指向下一個節點
}LNode,*LinkList;//對struct LNode進行重命名，用LinkList去表示指向struct LNode的指標同時LNode *和LinkList是等價的但是強調的物件不同：LNode *->節點 LinkList->鏈表（可以著重去區分兩者代表含義）
3>初始化單鏈表（帶頭節點和不帶頭節點）
不帶頭節點
void InitList(LinkList &L)//不帶頭節點
{
L=NULL;//空表暫時沒有資料
if（L==NULL）
{
printf("初始化成功");
}
}空表對L=NULL的操作是為了防止計算機內部的臟資料
不帶頭節點不利于撰寫代碼，因為對于第一個資料節點的處理和后續節點的處理需要用不同的邏輯同樣對空表和非空表的處理也需要用不同的邏輯
帶頭節點
void InitList(LinkList &L)
{
L = (LNode*)malloc(sizeof(LNode));//分配一個頭節點
if (L==NULL)//校驗記憶體分配
{
printf("記憶體分配失敗");
}
else {
L->next = NULL;
}
}對鏈表的初始化主要是分配一個頭節點，應注意對分配情況的校驗，L->next=NULL是因為當前表只有一個頭節點應指向為空，同時頭指標不存盤資料
4>對單鏈表添加資料
這里是用尾插法對單鏈表進行資料的輸入
思路:經過初始化以后現在的單鏈表是一個空表->單鏈表不同于線性表具有連續的地址空間（每個資料直接的連續通過指標鏈接）->類似于a,b進行資料交換
同理對于節點可以用類似的方法使用一個節點去保持資料，一個節點去指向下一個節點的指標域，完成對上一個節點的賦值后移動到下一個節點
所以回圈賦值不會影響，D節點的內容，因為已經移動到了下一個節點
void CreatList(LinkList &L)//輸入資料
{
LNode *P,*D;//DATA是用來保持每次輸入的資料，P的作用是指向單鏈表尾部
L = (LNode*)malloc(sizeof(LNode));//創建頭節點
L->next = NULL;//初始化單鏈表，一開始為空表
P = L;//空表時頭節點也是尾部節點
int n;//輸入資料的個數
printf("請輸入資料的個數:");
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
D = (LinkList)malloc(sizeof(LNode));//給D節點開辟一個空間
printf("data[%d]=",i);
scanf("%d",&D->data);//每次輸入的資料到D
D->next=P->next;//第一個節點已經填充，將移動下一個節點
P->next = D;//D代表的是一個節點,P->next是指向下一個節點
P = D;
}
}5>輸出單鏈表的資料
對于單鏈表的輸出，同理需要定義一個新節點去指向頭節點L，利用回圈條件去列印全體陣列
void ShowList(LinkList L)
{
LNode * P;
P =(LNode*)malloc(sizeof(LNode));//分配空間
P = L->next;//單鏈表從P點開始遍歷，等同于從頭節點開始
int i = 0;//記錄位序
printf("列印單鏈表\n");
while (P!=NULL)//只要節點不為空就可以繼續輸出
{
printf("data[%d]=%d\n",i,P->data);
i++;
P = P->next;
}
}
6>單鏈表的插入
元素的插入（1按位序插入 2節點后插 3節點前插）
按位序插入（帶頭節點）
思路：找到第i-1個節點—>將元素插入其后（將第i-1個元素的指標指向插入元素，將插入元素的指標指向第i+1個元素）
void ListInsert(LinkList &L, int i, int e)//插入資料
{
if (i < 1)
printf("插入位置不合法");
else {
LNode *p;//用來指向查詢元素的指標
int number = 0;//記錄節點的位置
p = L;//查詢節點應從頭開始，所以指向頭節點
while (p != NULL && number < i - 1)
{
p = p->next;//只是尋找到第i-1節點
number++;
}
if (p == NULL)
printf("插入位置不合法");
printf("插入位置為%d是%d\n", i, e);
LNode*s = (LNode*)malloc(sizeof(LNode));//為插入元素分配一個節點
s->data = e;//將e賦值新節點的資料域
s->next = p->next;//將插入元素的指標指向第i+1個元素
p->next = s;//將第i-1和插入元素連接
}
}
對于頭指標不要輕易使用如果使用頭指標會造成存盤空間的混亂和資料的混亂，所以重新定義一個新的節點*p去指向查詢的元素同時還需要一個記錄節點的資料，
LNode*s = (LNode*)malloc(sizeof(LNode))是為插入元素分配一個節點
s ->data = e;將e賦值新節點的資料域
s->next = p->next;將插入元素的指標指向第i+1個元素
p->next = s;將第i-1和插入元素連接
s->next = p->next;將插入元素的指標指向第i+1個元素
p->next = s;將第i-1和插入元素連接（不可以顛倒，則s節點就會指向s節點）則后面的資料就會混亂
不帶頭節點插入元素（按位）
void ListInsert(LinkList &L, int i, int e)//無頭節點插入
{
if (i < 1)
printf("插入位置不合法");
if (i == 1)//插入到頭節點
{
LNode* s = (LNode*)malloc)(sizeof(LNode));//分配空間
s->data = e;//元素傳遞給頭節點
s->next = L;//和單鏈表進行鏈接
L = s;//現在s就是頭節點方便變數
}
else {
LNode *p;//用來指向查詢元素的指標
int number = 0;//記錄節點的位置
p = L;//查詢節點應從頭開始，所以指向頭節點
while (p != NULL && number < i - 1)
{
p = p->next;//只是尋找到第i-1節點
number++;
}
if (p == NULL)
printf("插入位置不合法");
printf("插入位置為%d是%d\n", i, e);
LNode*s = (LNode*)malloc(sizeof(LNode));//為插入元素分配一個節點
s->data = e;//將e賦值新節點的資料域
s->next = p->next;//將插入元素的指標指向第i+1個元素
p->next = s;//將第i-1和插入元素連接
}
}不帶頭節點主要需要考慮插入第一個位置時的情況，其他位置與帶頭節點相同
7>洗掉單鏈表的資料(帶頭節點）
思路：找到第i-1個節點—>將元素洗掉后（將第i-1個元素的指標指向第i+1個元素資料域）同時還需要釋放掉第i個節點的空間
void ListDelet(LinkList &L, int i)
{
if (i < 1)
printf("洗掉位置不合法");
LNode *p;//用來指向查詢元素的指標
int number = 0;//記錄節點的位置
p = L;//查詢節點應從頭開始，所以指向頭節點
while (p != NULL && number < i - 1)
{
p = p->next;//只是尋找到第i-1節點
number++;
}
if (p == NULL)
printf("洗掉內容為空");
LNode*q = p->next;
int e;
e = q->data;//記錄洗掉的資料
p->next = q->next;
free(q);//釋放掉該節點
printf("洗掉元素%d成功\n",e);
}
類似于對資料的插入洗掉的要點再去洗掉第i個元素將第i-1個節點直接指向第i+1即可
不帶頭節點
類似于帶頭節點主要在于第一個節點的洗掉需要將第一個節點下一個節點作為頭節點繼續指向下一個節點
8>單鏈表的查找（按位/按值）
查找的本質還是要遍歷單鏈表，還需要一個計數器去計算遍歷到第幾個節點
void GetElem(LinkList L, int i)
{
if (i < 0)
printf("查詢位置不合法");
else {
LNode* P;//創建一個記錄節點的指標
int number = 0;//記錄查詢到幾個節點
P = L->next;//指向頭節點，從頭節點開始查詢變數
if (i == 0)
printf("頭節點為空");//頭節點不存放資料
while (P != NULL && number < i)
{
P = P->next;//尋找到第i節點
number++;
}
printf("查詢第%d個元素為%d\n", i,P->data );
}
}
按 值查找
void GetElem_data(LinkList L, int e)
{
LNode*P;//分配一個節點
P = L->next;
int number = 1;
while (P!=NULL&&P->data!=e)
{
P = P->next;
number++;
}
if (P = NULL)
{
printf("單鏈表中沒有該元素");
}
else
printf("鏈表中有該元素位置位%d",number);
}
如果單鏈表中沒有查詢元素隨著指標移動到最后一個節點的指標指向的為NULL，如果有該元素則會不滿足data!=e這個條件就會跳出回圈
9>整體代碼
對于vissual studioC4996報錯 在專案屬性->C++預處理中添加_CRT_SECURE_NO_WARNINGS即可
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode //定義單鏈表的型別
{
int data;//每個節點存放的資料元素
struct LNode *next;//指標指向下一個節點
}LNode,*LinkList;//對struct LNode進行重命名，用LinkList去表示指向struct LNode的指標
void InitList(LinkList &L)//初始化單鏈表
{
L = (LNode*)malloc(sizeof(LNode));//分配一個頭節點
if (L==NULL)//校驗記憶體分配
{
printf("記憶體分配失敗");
}
else {
L->next = NULL;
}
}
void CreatList(LinkList &L)//輸入資料
{
LNode *P,*D;//DATA是用來保持每次輸入的資料，P的作用是指向單鏈表尾部
L = (LNode*)malloc(sizeof(LNode));//創建頭節點
L->next = NULL;//初始化單鏈表，一開始為空表
P = L;//空表時頭節點也是尾部節點
int n;//輸入資料的個數
printf("請輸入資料的個數:");
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
D = (LinkList)malloc(sizeof(LNode));//給D節點開辟一個空間
printf("data[%d]=",i);
scanf("%d",&D->data);//每次輸入的資料到D
D->next=P->next;//第一個節點已經填充，將移動下一個節點
P->next = D;//D代表的是一個節點,P->next是指向下一個節點
P = D;
}
}
void ShowList(LinkList L)
{
LNode * P;
P =(LNode*)malloc(sizeof(LNode));//分配空間
P = L->next;//單鏈表從P點開始遍歷，等同于從頭節點開始
int i = 0;//記錄位序
printf("列印單鏈表\n");
while (P!=NULL)//只要節點不為空就可以繼續輸出
{
printf("data[%d]=%d\n",i,P->data);
i++;
P = P->next;
}
}
void ListInsert(LinkList &L, int i, int e)//插入資料
{
if (i < 1)
printf("插入位置不合法");
else {
LNode *p;//用來指向查詢元素的指標
int number = 0;//記錄節點的位置
p = L;//查詢節點應從頭開始，所以指向頭節點
while (p != NULL && number < i - 1)
{
p = p->next;//只是尋找到第i-1節點
number++;
}
if (p == NULL)
printf("插入位置不合法");
printf("插入位置為%d是%d\n", i, e);
LNode*s = (LNode*)malloc(sizeof(LNode));//為插入元素分配一個節點
s->data = e;//將e賦值新節點的資料域
s->next = p->next;//將插入元素的指標指向第i+1個元素
p->next = s;//將第i-1和插入元素連接
}
}
void ListInsert_no(LinkList L, int i, int e)//無頭節點插入
{
if (i < 1)
printf("插入位置不合法");
if (i == 1)//插入到頭節點
{
LNode* s = (LNode*)malloc(sizeof(LNode));//分配空間
s->data = e;//元素傳遞給頭節點
s->next = L;//和單鏈表進行鏈接
L = s;//現在s就是頭節點方便變數
}
else {
LNode *p;//用來指向查詢元素的指標
int number = 0;//記錄節點的位置
p = L;//查詢節點應從頭開始，所以指向頭節點
while (p != NULL && number < i - 1)
{
p = p->next;//只是尋找到第i-1節點
number++;
}
if (p == NULL)
printf("插入位置不合法");
printf("插入位置為%d是%d\n", i, e);
LNode*s = (LNode*)malloc(sizeof(LNode));//為插入元素分配一個節點
s->data = e;//將e賦值新節點的資料域
s->next = p->next;//將插入元素的指標指向第i+1個元素
p->next = s;//將第i-1和插入元素連接
}
}
void ListDelet(LinkList &L, int i)
{
if (i < 1)
printf("洗掉位置不合法");
LNode *P;//用來指向查詢元素的指標
int number = 0;//記錄節點的位置
P = L;//查詢節點應從頭開始，所以指向頭節點
while (P != NULL && number < i - 1)
{
P = P->next;//只是尋找到第i-1節點
number++;
}
if (P== NULL)
printf("洗掉內容為空");
LNode*Q = P->next;
int e;
e = Q->data;//記錄洗掉的資料
P->next = Q->next;
free(Q);//釋放掉該節點
printf("洗掉元素%d成功\n",e);
}
void GetElem(LinkList L, int i)
{
if (i < 0)
printf("查詢位置不合法");
else {
LNode* P;//創建一個記錄節點的指標
int number = 0;//記錄查詢到幾個節點
P = L->next;//指向頭節點，從頭節點開始查詢變數
if (i == 0)
printf("頭節點為空");//頭節點不存放資料
while (P != NULL && number < i)
{
P = P->next;//尋找到第i節點
number++;
}
printf("查詢第%d個元素為%d\n", i,P->data );
}
}
void GetElem_data(LinkList L, int e)
{
LNode*P;//分配一個節點
P = L->next;
int number = 1;
while (P!=NULL&&P->data!=e)
{
P = P->next;
number++;
}
if (P = NULL)
{
printf("單鏈表中沒有該元素");
}
else
printf("鏈表中有該元素位置位%d",number);
}
void main()
{
LinkList L;
InitList(L);//初始化一個帶頭節點的單鏈表
CreatList(L);//輸入元素
ListInsert(L,3,99);//插入元素（按位）
ListInsert_no(L, 1, 11);//不帶頭節點
ListDelet(L, 3);//洗掉節點資料
GetElem(L,3);//按位查找
GetElem_data(L,3);//按值查找
ShowList(L);//列印表
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/250686.html
標籤：其他