線性表的鏈式存盤結構

資料結構系列文章 第二章 單鏈表結構

前言

提示：本系列文章均使用Visual Studio 2019編程，編程語言為c語言，

一、單鏈表的建立

為了使單鏈表中每個資料元素與其直接后繼的資料元素之間存在邏輯關系，除了存盤其本身的資訊之外，還需要存盤一個指示其直接后繼存盤位置的資訊（存盤后繼元素的存盤地址，即指標），

存盤資料元素資訊的域稱為資料域，將存盤直接后繼位置的域稱為指標域，其中指標域中存盤的資訊稱為指標或鏈，同時這兩部分資訊組成資料元素的存盤映像稱為結點，結點由存放資料元素的資料域存放后繼結點地址的指標域組成，n個結點鏈從而結合成一個鏈表，即為線性表的鏈式存盤結構，又由于鏈表的每個結點中只包含一個指標域，所以稱為單鏈表，

代碼

#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

//單鏈表的建立
typedef int Status;
typedef int ElemType;
typedef struct Node
{
	ElemType data;           //資料域
	struct Node *next;       //指標域
}Node;
typedef struct Node* LinkList;   //將Node替換為LinkList

二、單鏈表的讀取

由于單鏈表與線性表的順序存盤結構不一樣，當我們要查找任意一個元素的存盤位置時，單鏈表的查找得從頭開始找，我們來看看怎么查找吧，可以說
單鏈表的讀取分為以下幾步：（例如讀取鏈表中第n個元素的值）
1、首先宣告一個指標p（結點）指向單鏈表的第一個結點，即p=L->next,同時設定一個計數器j從1開始計數；
2、開始查找，當j<n時，遍歷整個鏈表，讓p的指標向后移動查找下一個結點，同時計數器j累加1（由于沒有定義表長，所以不知道要進行多少次回圈陳述句，所以不用for陳述句）；
3、若至鏈表末尾，指標p仍為空，即未找到該元素，第n個元素不存在，回傳錯誤；
4、否則，查找成功，用e回傳L中第n個元素的資料；
5、回傳成功，

代碼

//單鏈表的讀取
typedef int Status;
Status GetElem(LinkList L, int n, ElemType* e)
{
	int j=1;                      //j為計數器
	LinkList p;                   //宣告一結點
	p = L->next;                  //讓p指向鏈表L的第一個結點
	while (p &&j<n)               //當p為慷訓者計數器j等于n時，結束回圈
	{
		p = p->next;              //讓p指向下一個結點
		++j;
	}
	if (!p || j > n)
		return ERROR;             //第n個元素不存在
	*e = p->data;                 //取第n個元素的資料
	return OK;
}

三、單鏈表的插入

對于實作單鏈表的插入操作，我們以以下圖示來解釋，我們設要插入的元素e的結點為s，我們要實作將結點s插入到結點p和p->next之間，即可以將p的后繼結點改為s的后繼結點，再把結點s變成p的后繼結點，通過代碼改變其指標實作即s->next=p->next ; p->next=s，（特別注意這兩句的順序不可寫反）

單鏈表的插入分為以下幾步：（例如鏈表中第i個資料元素位置之前插入資料元素e）
1、首先宣告一個指標p（結點）指向單鏈表的第一個結點并且宣告一個空結點s,同時設定一個計數器j從1開始計數；
2、由于要找第i-1個結點，因為要插入的是第i個結點，當j<i且p為空時，遍歷整個鏈表，讓p的指標向后移動查找下一個結點，同時計數器j累加1（回圈用于遍歷到需要插入的結點）；
3、若至鏈表末尾，指標p仍為空，即未找到該元素，第i個元素不存在，回傳錯誤；
4、否則此時查找成功，此時用動態分配函式生成一個新結點s，即分配整型存盤單元，并將連續的整型存盤單元的首地址存盤到指標變數s當中；
5、將資料元素e賦值給s->data；
6、將p結點的后綴結點賦值給s的后繼并將s賦值給p的后繼；
7、回傳成功，

代碼

//單鏈表的插入
typedef int Status;
Status ListInsert(LinkList* L, int i, ElemType e)
{
	int j = 1;
	LinkList p, s;
	p = *L;
	while (p && j<i)             //當p為慷訓者計數器j等于i時，結束回圈(即尋找第i個結點)
	{
		p = p->next;
		++j;
	}
	if (!p || j > i)
		return ERROR;                            //第i個元素不存在
	s = (LinkList)malloc(sizeof(Node));      //malloc()是動態分配函式，用來向系統請求分配記憶體空間，即分配整型存盤單元，并將連續的整型存盤單元的首地址存盤到指標變數s當中
	s->data = e;
	s->next = p->next;               //將p的后綴結點賦值給s的后繼
	p->next = s;                     //將s賦值給p的后繼
	return OK;
}

四、單鏈表的洗掉

對于實作單鏈表的插入操作，我們以以下圖示來解釋，我們要洗掉的結點是q，只要繞過它的前繼結點的指標，直接指向它的后繼結點就行,即①q=p->next②p->next=q->next，我們可以用一步來描述，這一步是p->next=p->next->next，

單鏈表的洗掉分為以下幾步：（例如洗掉鏈表中第i個資料元素）
1、首先宣告一個指標p（結點）指向單鏈表的第一個結點，同時設定一個計數器j從1開始計數；
2、當j<i且p為空時，遍歷整個鏈表，讓p的指標向后移動查找下一個結點，同時計數器j累加1（回圈用于遍歷到需要洗掉的結點）；
3、若至鏈表末尾，指標p仍為空，即未找到該元素，第i個元素不存在，回傳錯誤；
4、否則此時查找成功，將準備洗掉的結點p->next賦值給q；
5、執行洗掉操作，p->next=q->next；
6、將q結點中的資料賦給e，作為回傳，用e回傳其值；
7、使用free（）函式，釋放q結點；
8、回傳成功，

代碼

//單鏈表的洗掉
typedef int Status;
Status ListDelete(LinkList *L, int i, ElemType *e)
{
	int j = 1;
	LinkList p, q;
	p = *L;
	while (p->next && j < i)             //遍歷尋找第i個元素
	{
		p = p->next;
		++j;
	}
	if (!(p->next) || j > i)
		return ERROR;                    //第i個元素不存在
	q = p->next; 
	p->next = q->next;                  
	*e = q->data;                       //將q結點中的資料給e
	free(q);                //free（）函式，讓系統回收此結點，釋放記憶體
	return OK;
}

五、單鏈表的整表創建

1.頭插法建立單鏈表

頭插法創建單鏈表，即始終讓新結點處于表中第一的位置，最后輸入的元素和輸出的元素順序剛好相反，從一個空表開始，生成新結點，讀取資料存放到新結點的資料域中，然后將新結點插入到當前鏈表的表頭位置上，直到結束為止，（先讓新結點的next指向頭結點之后，然后讓表頭的next指向新結點）

代碼

#include <stdio.h>
#include <stdlib.h>
typedef int Status;
typedef int ElemType;
typedef struct Node* LinkList;    //將Node替換為LinkList，即結構指標LinkList
typedef struct Node               //定義一個結構體
{
	ElemType data;           //資料域
	struct Node* next;       //指標域
}Node;

Status ListInit(LinkList& L)
{
	L = (LinkList)malloc(sizeof(Node));                 //生成新結點
	if (!L)
		exit(1);                   //當單鏈表L為空時，執行exit（1）即表示例外退出
	L->next = NULL;                //否則創建一個帶頭結點的單鏈表，初始化指向NULL
	return 1;                      //return（1）代表函式非正常終止
}

//頭插法
void CreateListHead(LinkList* L, int n)
{
	LinkList p;
	int i;
	*L = (LinkList)malloc(sizeof(Node));
	(*L)->next = NULL;              //創建一個帶頭結點的單鏈表，初始化指向NULL
	for (i = 0; i < n; i++)
	{
		p = (LinkList)malloc(sizeof(Node));     //生成新結點
		scanf("%d", &i);
		p->data = i;
		p->next = (*L)->next;
		(*L)->next = p;               //插入到表頭
	}
}

//遍歷函式
void TraverseList(LinkList* L)
{
	Node* p, * q;
	p = *L;
	while (p->next != NULL)       //遍歷輸出資料元素
	{
		q = p->next;
		printf("%d ", q->data);
		p = p->next;
	}
}

//主函式
int main(int argc, char const* argv[])                  
{
	int n;
	LinkList L;
	ListInit(L);
	printf("請輸入創建資料元素的個數：");
	scanf("%d", &n);
	CreateListHead(&L, n);
	printf("頭插法創建單鏈表如下：");
	TraverseList(&L);
	printf("\n");
	return 0;
}

測驗輸入五個資料元素：0、1、2、3、4，
（輸出的順序與輸入的順序是相反的）

2.尾插法建立單鏈表

第二種方法就是尾插法，也就是將所加入的新結點全部插在終端結點的后面依次排下去，就相當于正常排隊的思維來運行程式， 其中
q->next = p;這一陳述句即將表尾終端結點q的指標指向新的下一個結點p，然后q=p；這一陳述句q就相當于一個中繼（是當前鏈表的最后結點），在進行下一個元素的創建時，q本來是上一個資料元素的結點，但后面仍有結點，所以這時應該將這個p結點（也就是當前鏈表的最后結點）賦值給q，此時q又是當前鏈表的尾結點，回圈結束后q->next = NULL;即讓這個鏈表的指標域置空，以便在之后遍歷時可以知道是其當前鏈表尾部，

代碼

#include<stdio.h>
#include<stdlib.h>
typedef int Status;
typedef int ElemType;
typedef struct Node* LinkList;             //將Node替換為LinkList，即結構指標LinkList
typedef struct Node                        //定義一個結構體
{
    ElemType data;                 //資料域
    struct Node* next;             //指標域
}Node;

Status ListInit(LinkList& L)
{
    L = (LinkList)malloc(sizeof(Node));                 //生成新結點
    if (!L)
        exit(1);                   //當單鏈表L為空時，執行exit（1）即表示例外退出
    L->next = NULL;                //否則創建一個帶頭結點的單鏈表，初始化指向NULL
    return 1;                      //return（1）代表函式非正常終止
}

//尾插法
void CreatListTail(LinkList& L, int n)
{
    LinkList p, q;
    q = L;
    int a;
    for (int i = 0; i < n; i++)
    {
        p = (LinkList)malloc(sizeof(Node));              //生成新結點
        scanf("%d", &a);
        p->data = a;
        q->next = p;                             //將當前的新結點定義為單鏈表尾終端結點
        q = p;
    }
    q->next = NULL;                              //表示當前單鏈表結束
}

//遍歷函式
void TraverseList(LinkList& L)              //輸出單鏈表函式
{
    LinkList r;
    r = L->next;
    while (r)
    {
        printf("%d ", r->data);
        r = r->next;
    }
}

//主函式
int main(int argc, char const* argv[])                  
{
    int n;
    LinkList L;
    ListInit(L);
    printf("請輸入創建資料元素的個數：");
    scanf("%d", &n);
    CreatListTail(L, n);
    printf("尾插法創建單鏈表如下：");
    TraverseList(L);
    printf("\n");
    return 0;
}

測驗輸入五個資料元素：0、1、2、3、4，
（輸出的順序與輸入的順序相同）

六、單鏈表的整表洗掉

當要洗掉這個單鏈表時，即在記憶體中釋放它時，我們給出以下演算法：
1、宣告一結點p和q；
2、將第一個結點賦值給p；
3、回圈陳述句：將下一結點賦值給q，釋放p，將q賦值給p，

代碼

#include<stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
typedef int Status;
typedef int ElemType;
typedef struct Node* LinkList;    //將Node替換為LinkList，即結構指標LinkList
typedef struct Node               //定義一個結構體
{
	ElemType data;           //資料域
	struct Node* next;       //指標域
}Node;

Status ClearList(LinkList* L)
{
	LinkList p, q;           
	p = (*L)->next;               //p指向第一個結點
	while (p)                    //回圈到表尾結束
	{
		q = p->next;
		free(p);
		p = q;
	}
	(*L)->next = NULL;             //頭指標指標域為空
	return OK;
}

總結

以上就是本次的筆記內容，本文僅僅通過文字和代碼簡單介紹了單鏈表結構的各項操作，建議自己分析總結其各個操作并結合自己的編程能力選擇編程語言再寫一遍代碼從而加深印象，可以使自己的編程能力提升，其實資料結構不難，要有心地去學習和總結，才能事半功倍，若有錯誤歡迎指正，