C++編程語言實現(xiàn)單鏈表詳情

更新時間：2021年10月08日 08:51:09 作者：tyl2021

這篇文章主要介紹的是利用C語言實現(xiàn)單鏈表，實現(xiàn)的是鏈表中最簡單的一種單鏈表且每個結(jié)點(diǎn)中只含有一個指針域，下面將詳細(xì)舉例說明,需要的朋友可以參考一下

一、單鏈表簡單介紹

首先，我們再回顧一下線性表的兩種存儲方式——順序存儲與鏈?zhǔn)酱鎯?/p>

上圖左邊為順序存儲，右邊為鏈?zhǔn)酱鎯?br />

之前我們利用數(shù)組來實現(xiàn)順序表，對于順序表的優(yōu)點(diǎn)缺點(diǎn)，總結(jié)來說就是，查找方便，增刪復(fù)雜。

線性表之順序存儲的優(yōu)缺點(diǎn)

而鏈表特點(diǎn)可以說恰恰相反，增刪方便，查找復(fù)雜。

今天實現(xiàn)的是鏈表中最簡單的一種——單鏈表（每個結(jié)點(diǎn)中只含有一個指針域）

對于鏈表我們只知道它每個結(jié)點(diǎn)的存儲的物理地址是不連續(xù)的，但邏輯上還是符合線性表“一對一”的特點(diǎn)。因此，我們就需要用“線”（指針）把這些不連續(xù)的結(jié)點(diǎn)按順序連接起來。

鏈表的結(jié)點(diǎn)在內(nèi)存中存儲不連續(xù)

通過指針把每個結(jié)點(diǎn)按順序連起來

到這里我們可以發(fā)現(xiàn)，要想表示鏈表中的結(jié)點(diǎn)，光存儲結(jié)點(diǎn)的數(shù)據(jù)是不夠的，還得有指針。因此，單鏈表的結(jié)點(diǎn)結(jié)構(gòu)如下：

數(shù)據(jù)域存儲數(shù)據(jù)，指針域存儲指針

//================線性表的單鏈表存儲結(jié)構(gòu)=================
typedef struct LNode {
ElemType data;//數(shù)據(jù)域
struct LNode *next;//指針域
}LNode;

注意：因為指針是指向每個結(jié)點(diǎn)的，也就是指向struct LNode這個自定義的結(jié)構(gòu)體類型，所以指針的類型就是struct LNode*。

二、下面我們先實現(xiàn)單鏈表的初始化。

單鏈表的初始化其實就是創(chuàng)建幾個結(jié)點(diǎn)，然后用指針把他們連接起來。

先創(chuàng)建一個頭指針，實際上就是創(chuàng)建一個頭結(jié)點(diǎn)，然后頭指針指向頭結(jié)點(diǎn)就OK

LNode* CreateList_L(int n) {//順位序輸入n個元素的值，建立帶表頭結(jié)點(diǎn)的單鏈線性表L
 LNode *p = (LNode*)malloc(sizeof(LNode));//創(chuàng)建頭結(jié)點(diǎn)（p也就是頭指針）
 LNode *temp = p;//聲明一個指針指向頭結(jié)點(diǎn),用于遍歷鏈表(不是頭指針，因為它只是暫時指向頭結(jié)點(diǎn))
 //生成鏈表
 for (int i = n; i > 0; --i) 
 {
  LNode *node = (LNode *)malloc(sizeof(LNode));//創(chuàng)建結(jié)點(diǎn)
  if (node){//分配地址成功
   scanf_s("%c", &(node->data));
   node->next = NULL;
   //建立新結(jié)點(diǎn)與直接前驅(qū)結(jié)點(diǎn)的邏輯關(guān)系
   temp->next = node;
   temp = temp->next;
  }
  else {//如果分配地址失敗，則返回錯誤信息
    printf("結(jié)點(diǎn)創(chuàng)建失?。n");
  }
 }
 return p;
}

三、實現(xiàn)單鏈表的插入與刪除數(shù)據(jù)

單鏈表插數(shù)據(jù)情況

觀察可知，我們要實現(xiàn)插入操作，需要的操作是一樣的。

S1：將后繼結(jié)點(diǎn)的指針賦給新結(jié)點(diǎn)的指針域；

S2：將前驅(qū)節(jié)點(diǎn)的指針域改為指向新結(jié)點(diǎn)的指針。

注意：S1和S2不能換順序。

//===============================算法2.9==========================
Status ListInsert_L(LNode *L, int i, ElemType e) {
 //在帶頭結(jié)點(diǎn)的單鏈表L中第i個位置之前插入元素e
 int j = 0;
 LNode *p = L;
 while (p&&j < i - 1) {
  p = p->next;
  ++j;
 }//尋找第i-1個結(jié)點(diǎn)
 if (!p || j > i - 1)return ERROR;//i小于1或者大于表長時
 LNode* s = (LNode*)malloc(sizeof(LNode));//生成新的結(jié)點(diǎn)
 s->data = e; s->next = p->next;//S1
 p->next = s;//S2
 return OK;
}

單鏈表刪除數(shù)據(jù)示意圖

觀察可知，只需要將待刪結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的指針域的值換成待刪結(jié)點(diǎn)的后繼結(jié)點(diǎn)的指針即可。

//=====================算法2.10=================================
Status ListDelete_L(LNode *L, int i, ElemType *e) {
 //在帶頭結(jié)點(diǎn)的單鏈表L中，刪除第i個元素，并由e返回其值
 LNode *p = L;
 int j = 0;
 while (p->next&&j < i - 1) {//尋找第i個結(jié)點(diǎn)，并令p指向其前驅(qū)
  p = p->next; ++j;
 }
 if (!(p->next) || j > i - 1)return ERROR;//刪除位置不合理
 LNode *q = p->next; p->next = q->next;//刪除并釋放結(jié)點(diǎn)
 *e = q->data; free(q);
 return OK;
}
三、參考代碼實現(xiàn)與截圖
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define ElemType char
typedef int Status;
//================線性表的單鏈表存儲結(jié)構(gòu)==================
typedef  struct LNode {
 ElemType data;//數(shù)據(jù)域
 struct LNode *next;//指針域
}LNode;
LNode* CreateList_L(int n) {//順位序輸入n個元素的值，建立帶表頭結(jié)點(diǎn)的單鏈線性表L
 LNode *p = (LNode*)malloc(sizeof(LNode));//創(chuàng)建頭結(jié)點(diǎn)
 LNode *temp = p;//聲明一個指針指向頭結(jié)點(diǎn),用于遍歷鏈表(不是頭指針)
 //生成鏈表
 for (int i = n; i > 0; --i) 
 {
  LNode *node = (LNode *)malloc(sizeof(LNode));//創(chuàng)建結(jié)點(diǎn)
  if (node){//分配地址成功
   scanf_s("%c", &(node->data));
   node->next = NULL;
   //建立新結(jié)點(diǎn)與直接前驅(qū)結(jié)點(diǎn)的邏輯關(guān)系
   temp->next = node;
   temp = temp->next;
  }
  else {//如果分配地址失敗，則返回錯誤信息
    printf("結(jié)點(diǎn)創(chuàng)建失?。n");
  }
 }
 return p;
}
//===============================算法2.9==========================
Status ListInsert_L(LNode *L, int i, ElemType e) {
 //在帶頭結(jié)點(diǎn)的單鏈表L中第i個位置之前插入元素e
 int j = 0;
 LNode *p = L;
 while (p&&j < i - 1) {
  p = p->next;
  ++j;
 }//尋找第i-1個結(jié)點(diǎn)
 if (!p || j > i - 1)return ERROR;//i小于1或者大于表長時
 LNode* s = (LNode*)malloc(sizeof(LNode));//生成新的結(jié)點(diǎn)
 s->data = e; s->next = p->next;
 p->next = s;
 return OK;
}
//=====================算法2.10=================================
Status ListDelete_L(LNode *L, int i, ElemType *e) {
 //在帶頭結(jié)點(diǎn)的單鏈表L中，刪除第i個元素，并由e返回其值
 LNode *p = L;
 int j = 0;
 while (p->next&&j < i - 1) {//尋找第i個結(jié)點(diǎn)，并令p指向其前驅(qū)
  p = p->next; ++j;
 }
 if (!(p->next) || j > i - 1)return ERROR;//刪除位置不合理
 LNode *q = p->next; p->next = q->next;//刪除并釋放結(jié)點(diǎn)
 *e = q->data; free(q);
 return OK;
}
void display(LNode *L) {
 LNode *temp =L;//將temp指針重新指向頭結(jié)點(diǎn)
 //只要temp指針指向的結(jié)點(diǎn)的next不是Null，就執(zhí)行輸出語句。
 while (temp->next) {
  temp = temp->next;
  printf("%c", temp->data);
 }
 printf("\n");
}
int   main() {
 LNode *L = NULL;
 L=CreateList_L(5);
 display(L);
 ListInsert_L(L, 2, 'Y');
 display(L);
 ElemType e;
 ListDelete_L(L, 2, &e);
 display(L);
 printf("返回值為：%c", e);
 system("pause");
 return 0;
}