資料結構（C語言）——單鏈表的創建及基本功能的實作
1. 鏈表型別
2. 單鏈表的定義
單鏈表是由一連串的 “結點” 組成的，這里我們可以把每一個 “結點” 理解為一個小盒子，這個盒子內部由兩部分組成：一部分用來儲存資料，我們把它稱為 “資料域” ，另一部分用來存放指標，及指向下一個結點的地址，我們把它稱為 “指標域” ，像這樣，我們從某一個結點訪問其指標域即可以找到下一個節點，像這樣通過尋找地址的方式進行鏈式連接，即構成了單鏈表，
1.單鏈表結構示意圖（頭部）：
2. 單鏈表結構圖示（中間部分）：
3.單鏈表結構示意圖（尾部）：
3.單鏈表的存盤結構
單鏈表為鏈式儲存結構，與順序表不同，鏈表不限制資料的物理存盤狀態，換句話說，使用鏈表存盤的資料元素，其物理存盤位置是隨機的，
4.學習單鏈表須弄明白的一些基本概念
一. 單鏈表必須元素（如下圖）
1. 頭指標
頭指標，顧名思義，即為一個指標，指向的是頭結點的地址
2. 頭結點
a. 在單鏈表中設定頭節點的作用是為了方便單鏈表的特殊操作（如：簡化插入、洗掉操作），這樣可以保持單鏈表操作的統一性，
b. 頭結點同樣包含了資料域和指標域，其資料域中可存值或者不存值，其指標域指向第一個結點
3. 中間結點
包含資料域指標域，通過結點地址以鏈式相連，
4.尾結點
注意尾結點的指標域為空(NULL)，
5.資料域
資料域包含多種型別，可以為整型，或者陣列型，結構體型等等，
6.指標域
頭結點指標域內的指標指向第一個結點的地址，第一個結點指標域的指標域指向第二個結點的地址，直到最后指向尾結點的空(NULL)，
5.代碼部分
1.創建結點型別
a.資料域為int型
typedef int ElemType; //定義ElemType為int型，這里的型別根據實際情況而定(可以為陣列或者結構體型別)，這里假設為int
typedef struct LinkList //定義結點型別，即LinkList型
{
ElemType data; //資料域，這里用的int形代替（這樣宣告是為了方便修改資料型別）
struct LinkList *next; //指標域，指向LinkList型的結點
}LinkListNode; //定義結點變數,名稱為LinkListNode
b.資料域為結構體型別
typedef struct ElemType //定義結構體型別的資料域，名稱為Elemtype
{
int ElemType_1; //ElemType型別中包含的元素
char ElemType_2;
double ElemType_3;
}Elem; //變數名為Elem
typedef struct LinkList
{
Elem data; //該處的資料域為一個結構體型別
struct LinkList *next;
}LinkListNode;
2.創建結點函式
LinkListNode *LinkListNodeCreat(ElemType e) //隨機讀入一個型別為ElemType的值(這里是int型)
{
/************************************************************************************************/
LinkListNode *pTmp = (LinkListNode*)malloc(sizeof(LinkListNode)); //為結點隨機分配記憶體空間
if(!pTmp)
{
printf("節點記憶體分配失敗！\n");
return NULL; //判空操作
}
memset(pTmp,0x00,sizeof(LinkListNode)); //初始化分配的記憶體空間為0
/************************************************************************************************/
//以上是一套基本的創建結點的操作
pTmp->data = e; //將int型資料域存入該結點
pTmp->next = NULL; //記住一定將新節點的指標域賦為空！！
return pTmp; //回傳指標
}
3.1插入函式(頭插法)
這里我們要將一個新結點插入到頭結點之后，讓該節點作為第一個結點，
int LinkListHeadInsert(LinkListNode *L,ElemType e)//這里L是頭結點
{
LinkListNode *NewNode = LinkListNodeCreat(e); //這里先創建一個名叫NewNode的新結點
NewNode->next = L->next;//將頭結點中指標域的值賦給新結點的指標域中 PS:此時頭結點的指標域有兩種情況 1.頭結點后無節點，此時相當于將NULL賦給新節點的指標域 2.頭結點的指標域指向原鏈表的第一個結點，此時將頭結點的指標域的值賦給新結點指標域，讓新結點指標域指向原鏈表的第一個結點
L->next = NewNode; //再將新結點指標域的值賦給頭結點的指標域，使頭結點的下一個結點為新結點
return OK;
}
3.2輸入函式
int LinkListInput(LinkListNode *L)
{
int i = 0,ElemNum = 0,Element = 0;
printf("請輸入要插入結點的個數：\n"); //插入多少個回圈多少次
scanf("%d",&ElemNum);
printf("請輸入鏈表當中的元素：\n");
for(i=0 ;i<ElemNum;i++)
{
scanf("%d",&Element);
LinkListHeadInsert(L,Element); //直接呼叫頭插法函式，頭插法在呼叫創建結點
}
return OK;
}
4.輸出函式
先判斷鏈表是否為空，為空則不能列印輸出！
int LinkListPrint(LinkListNode *L)
{
if(L->next==NULL) //判斷頭結點是否為空，是則不列印
{
printf("當前鏈表為空\n");
system("pause");
return 0;
}
LinkListNode *pTmp = L->next;//將pTmp的地址賦值為第一個結點的地址,若沒有結點則為NULL
printf("當前鏈表元素為：\n");
while (pTmp) //判斷是否有結點
{
printf("%d ",pTmp->data);//列印出資料域的值
pTmp = pTmp->next; //位移至下一個結點的地址
}
printf("\n");
system("pause");
return OK;
}
5.洗掉所有元素函式
先判斷鏈表是否為空，為空則不能洗掉！
int ListDelete(LinkListNode *L)
{
if(L->next==NULL) //判斷頭結點是否為空，是則無法洗掉
{
printf("當前鏈表無元素\n");
system("pause");
return FALSE;
}
LinkListNode *HeadTmp = L; //將頭指標的值賦給HeadTmp，作用是回圈，直至空
LinkListNode *TestTmp; //中間過渡暫存指標
while(HeadTmp)
{
TestTmp=HeadTmp;
HeadTmp=HeadTmp->next;
free(TestTmp); //清除結點
}
L->next=NULL; //記住這里將頭結點的指標域賦值為空！！ 否則使用上面的輸出函式會報錯，因為之后的結點已經被free了，但L還指向的是一個已經被清除的結點
printf("洗掉成功！\n");
system("pause");
return OK;
}
6.退出函式
這里和上面洗掉所有元素函式思想一樣，只是把頭結點也給free了
int OutList(LinkListNode *L)
{
if(L->next==NULL)
{
return OK;
}
LinkListNode *HeadTmp = L;
LinkListNode *TestTmp;
while(HeadTmp)
{
TestTmp=HeadTmp;
HeadTmp=HeadTmp->next;
free(TestTmp);
}
free(L); //free掉頭結點
return OK;
}
全部代碼：
這里主要看一下選單函式和主函式
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define OK 0
#define ERROR -1
#define TRUE 1
#define FALSE 0
//創建結點型別
typedef int ElemType; //定義ElemType為int型，這里的型別根據實際情況而定(可以為陣列或者結構體型別)，這里假設為int
typedef struct LinkList //定義結點型別，即LinkList型
{
ElemType data; //資料域，這里用的int形代替（這樣宣告是為了方便修改資料型別）
struct LinkList *next; //指標域，指向LinkList型的結點
}LinkListNode;
//************************************************
//創建節點函式
LinkListNode *LinkListNodeCreat(ElemType e) //隨機讀入一個型別為ElemType的值(這里是int型)
{
LinkListNode *pTmp = (LinkListNode*)malloc(sizeof(LinkListNode)); //為結點隨機分配記憶體空間
if(!pTmp)
{
printf("節點記憶體分配失敗！\n");
return NULL; //判空操作
}
memset(pTmp,0x00,sizeof(LinkListNode)); //初始化分配的記憶體空間為0
pTmp->data = e; //將int型資料域存入該結點
pTmp->next = NULL; //記住一定將新節點的指標域賦為空！！
return pTmp; //回傳指標
}
//************************************************
//頭插功能函式
int LinkListHeadInsert(LinkListNode *L,ElemType e)//這里L是頭結點
{
LinkListNode *NewNode = LinkListNodeCreat(e); //這里先創建一個名叫NewNode的新結點
NewNode->next = L->next;//將頭結點中指標域的值賦給新結點的指標域中 PS:此時頭結點的指標域有兩種情況 1.頭結點后無節點，此時相當于將NULL賦給新節點的指標域 2.頭結點的指標域指向原鏈表的第一個結點，此時將頭結點的指標域的值賦給新結點指標域，讓新結點指標域指向原鏈表的第一個結點
L->next = NewNode;//再將新結點指標域的值賦給頭結點的指標域，使頭結點的下一個結點為新結點
return OK;
}
//*************************************************
//輸入函式
int LinkListInput(LinkListNode *L)
{
int i = 0,ElemNum = 0,Element = 0;
printf("請輸入要插入結點的個數：\n"); //插入多少個回圈多少次
scanf("%d",&ElemNum);
printf("請輸入鏈表當中的元素：\n");
for(i=0 ;i<ElemNum;i++)
{
scanf("%d",&Element);
LinkListHeadInsert(L,Element); //直接呼叫頭插法函式，頭插法在呼叫創建結點
}
return OK;
}
//*************************************************
//輸出函式
int LinkListPrint(LinkListNode *L)
{
if(L->next==NULL) //判斷頭結點是否為空，是則不列印
{
printf("當前鏈表為空\n");
system("pause");
return 0;
}
LinkListNode *pTmp = L->next;//將pTmp的地址賦值為第一個結點的地址,若沒有結點則為NULL
printf("當前鏈表元素為：\n");
while (pTmp) //判斷是否有結點
{
printf("%d ",pTmp->data);//列印出資料域的值
pTmp = pTmp->next; //位移至下一個結點的地址
}
printf("\n");
system("pause");
return OK;
}
//************************************************
//洗掉所有元素函式
int ListDelete(LinkListNode *L)
{
if(L->next==NULL) //判斷頭結點是否為空，是則無法洗掉
{
printf("當前鏈表無元素\n");
system("pause");
return FALSE;
}
LinkListNode *HeadTmp = L; //將頭指標的值賦給HeadTmp，作用是回圈，直至空
LinkListNode *TestTmp; //中間過渡暫存指標
while(HeadTmp)
{
TestTmp=HeadTmp;
HeadTmp=HeadTmp->next;
free(TestTmp); //清除結點
}
L->next=NULL; //記住這里將頭結點的指標域賦值為空！！ 否則使用上面的輸出函式會報錯，因為之后的結點已經被free了，但L還指向的是一個已經被清除的結點
printf("洗掉成功！\n");
system("pause");
return OK;
}
//************************************************
//退出函式
int OutList(LinkListNode *L)
{
if(L->next==NULL)
{
return OK;
}
LinkListNode *HeadTmp = L;
LinkListNode *TestTmp;
while(HeadTmp)
{
TestTmp=HeadTmp;
HeadTmp=HeadTmp->next;
free(TestTmp);
}
free(L); //free掉頭結點
return OK;
}
//************************************************
//選單函式
int menu()
{
int n;
system("cls");
printf("===============================鏈表的基本功能實作=============================\n|\t\t\t\t\t\t\t\t |\n");
printf("|\t 1.增添元素 2.洗掉所有元素 3.查看元素 |\n");
printf("|\t |\n");
printf("|\t +--------------+ |\n");
printf("|\t | 4.退出 | |\n");
printf("|\t +--------------+ |\n");
printf("==============================================================================\n");
printf("請輸入指令[1-4]:");
scanf("%d",&n);
return n;
}
int main()
{
int n;
LinkListNode *L = LinkListNodeCreat(0);//創建頭結點L,頭指標(及為頭結點的地址)
do
{
n=menu();
switch(n)
{
case 1:
LinkListInput(L);
break;
case 2:
ListDelete(L);
break;
case 3:
LinkListPrint(L);
break;
}
}
while(n!=4);
OutList(L); //退出函式
printf("退出成功!\n");
system("pause");
return 0;
}
最后：
鏈表屬于資料結構中較簡單的內容，學起來不難的,理解了之后就很容易了,不要被那些人說的嚇到了，筆者目前計算機大一在讀，水平有限，所寫僅供參考學習，如有錯誤，請在評論區指正、討論，ps:愿本萌新在以后的學習能多點思考不受禁錮， 知識的學習也能跟得上發際線上移的速度~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/276644.html
標籤：其他