前言

大家好~
在學習C語言的程序中，動態鏈表的相關操作總是會把我弄得有點暈，思路是有的，但是寫完代碼之后就很容易被自己繞暈，
于是今天想把我在鏈表的創建、輸出、插入洗掉的程序中出現的問題總結一下，理清一下自己的思路，防止以后再犯同樣的錯，

關于鏈表

鏈表是一種常見的重要的資料結構，
它是動態地進行存盤分配的一種結構，鏈表有一個頭指標變數，它存放一個地址，該地址指向一個元素，
鏈表中每一個元素稱為結點，每個結點都應包括兩個部分：一為用戶需要用的實際資料，二為下一個結點的地址，
可以看出，頭指標 head 指向第一個元素，第一個元素又指向第二個元素……
直到最后一個元素，該元素不再指向其他元素，它稱為表尾，它的地址部分放一個 NULL（表示空地址）鏈表到此結束，

可以得出：
1. 鏈表中各元素在記憶體中可以不是連續存放的，要找某一元素，必須先找到上一個元素，根據它提供的下一元素地址才能找到下一個元素，
2. 如果不提供頭指標 head 則整個鏈表無法訪問，

題目

動態建立一個長度為4的鏈表，用于存盤學生的資訊（姓名與學號），并輸出；且實作插入與洗掉功能，所有功能通過寫成函式來實作，

C語言代碼

PS：我使用的是 Visual Studio 2019，里面的scanf_s就等同于scanf，但字串的輸入需要在后面標注字串的大小，否則系統會報錯，除錯不了，

引入函式：

#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#define LEN sizeof(struct student)

定義結構體：

typedef struct student
{
	char name[20];
	int num;
	struct student* next;
}STU;
int n = 0;

一、動態鏈表的創建

代碼如下：

STU* create()
{
	STU* p1, * p2, * head;
	char name[20];
	int num;
	head = NULL;
	p1 = p2 = (STU*)malloc(LEN); //開創一個空間用于存放結構體內的資料
	printf("請輸入學號與姓名：（格式：學號，姓名）\n");
	scanf_s("%d,%s", &p1->num, &p1->name, 20);
	while (p1->num != 0) //num=0時，鏈表創建結束
	{
		n++; //輸入了多少個學生的資料
		if (n == 1)
			head = p1; //把第一個結點的地址賦給head指標
		else
			p2->next = p1; //如果輸入的不是第一個結點的資料，就讓其內的next指標指向下一個結點的開頭
		p2 = p1; //p2指標移動到p1指標處（下一個結點的開頭）
		p1 = (STU*)malloc(LEN);//p1又指向新開創結點的開頭
		scanf_s("%d,%s", &p1->num, &p1->name, 20);
	}
	p2->next = NULL; //如果輸入的num=0，跳出回圈，最后一個結點的next指標指向空指標（即指向NULL值）
	return head; //回傳第一個結點的地址（這樣才能找到后面的所有結點）
}

二、動態鏈表的輸出

代碼如下：

void print(STU* head) //輸出學生資訊的函式
{
	STU* p;
	p = head; //p取head的地址之后，二者同時指向第一個結點的開頭
	n == 0;
	printf("\n");
	if (head != NULL)
	{
		do
		{
			printf("學號：%d 姓名：%s\n", p->num, p->name);
			p = p->next; //把next的地址（即下一個結點的開頭）賦給p
			n++;
		} while (p != NULL);
	}
	printf("\n現在共有%d個學生的資訊：\n", n);
}

三、動態鏈表的插入

（1）找到位置p（ai-1）
（2）生成新結點s，資料域賦值
（3）新結點指標域指向ai（ai的地址存放在ai-1的指標域）
（4）ai-1的指標域指向新結點s

代碼如下：

STU* insert_link(STU* head) //插入結點的函式
{
	STU* p;
	printf("請輸入需要插入資料的位置：\n");
	int m;
	scanf_s("%d", &m);
	p = head; //p與head指向第一個結點的開頭
	int i = 1; //插入位置
	printf("請輸入需要插入的資料 : （格式：學號，姓名）\n");
	STU* j;
	j = (STU*)malloc(LEN);
	scanf_s("%d,%s",  &j->num, &j->name, 20);
	if (m == 1) //如果要在第一個位置插入資料
	{
		j->next = head; //新的結點的next指標直接指向頭結點，新的資料就會成為第一個結點
		head = j; //head指標又指向第一個結點的開始
		return head; //回傳插入資料后的頭結點
	}
	else
	{
		while (i < m - 1)
			/*m-1意味著：如果要在第5個位置插入資料，
			則需要讓第4個結點的next指向插入資料的開頭*/
		{
			p = p->next; //回圈找到需要插入資料的上一個結點的next所在位置
			i++;
		}
	}
	j->next = p->next; //把p的next地址賦給j的next地址，即新的結點可插入兩個結點的中間
	p->next = j; //p的next指向j的地址
	return head; //回傳第一個結點的地址
}

四、動態鏈表的洗掉

（1）找到要洗掉的結點前一個結點p（原因是洗掉結點的位置在前一個結點的指標域）
（2）把p->next指向ai的下一個結點（把ai從鏈上摘除）
（3）釋放ai空間

代碼如下：

STU* delete_link(STU* head)//洗掉結點的函式
{
	STU* p1, * p2;
	printf("請輸入需要洗掉資料的位置：\n");
	int m;
	scanf_s("%d", &m);
	p1 = head;
	if (m == 1) //如果洗掉的是第一個結點
	{
		p2 = p1->next; //直接把下一個地址作為回傳值
		free(p1); //釋放記憶體
		return p2;
	}
	else
	{
		int i = 1;
		while (i < m - 1)
		{
			p1 = p1->next;
			i++;
		}
		p2 = p1->next;
		p1->next = p1->next->next; //p1的next指向了需要洗掉的結點的next指向的結點（即越過了中間需要洗掉的結點）
		free(p2); //釋放需要洗掉的結點的空間
		return head; //回傳第一個結點的地址
	}
}

五、總代碼

#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#define LEN sizeof(struct student)

typedef struct student
{
	char name[20];
	int num;
	struct student* next;
}STU;
int n = 0;
STU* create()
{
	STU* p1, * p2, * head;
	char name[20];
	int num;
	head = NULL;
	p1 = p2 = (STU*)malloc(LEN);//開創一個空間用于存放結構體內的資料
	printf("請輸入學號與姓名：（格式：學號，姓名）\n");
	scanf_s("%d,%s", &p1->num, &p1->name, 20);
	while (p1->num != 0)//num=0時，鏈表創建結束
	{
		n++;//輸入了多少個學生的資料
		if (n == 1)
			head = p1;//把第一個結點的地址賦給head指標
		else
			p2->next = p1;//如果輸入的不是第一個結點的資料，就讓其內的next指標指向下一個結點的開頭
		p2 = p1;//p2指標移動到p1指標處（下一個結點的開頭）
		p1 = (STU*)malloc(LEN);//p1又指向新開創結點的開頭
		scanf_s("%d,%s", &p1->num, &p1->name, 20);
	}
	p2->next = NULL;//如果輸入的num=0，跳出回圈，最后一個結點的next指標指向空指標（即指向NULL值）
	return head;//回傳第一個結點的地址（這樣才能找到后面的所有結點）
}
STU* insert_link(STU* head)//插入結點的函式
{
	STU* p;
	printf("請輸入需要插入資料的位置：\n");
	int m;
	scanf_s("%d", &m);
	p = head;//p與head指向第一個結點的開頭
	int i = 1;//插入位置
	printf("請輸入需要插入的資料 : （格式：學號，姓名）\n");
	STU* j;
	j = (STU*)malloc(LEN);
	scanf_s("%d,%s",  &j->num, &j->name, 20);
	if (m == 1)//如果要在第一個位置插入資料
	{
		j->next = head;//新的結點的next指標直接指向頭結點，新的資料就會成為第一個結點
		head = j;//head指標又指向第一個結點的開始
		return head;//回傳插入資料后的頭結點
	}
	else
	{
		while (i < m - 1)
			/*m-1意味著：如果要在第5個位置插入資料，
			則需要讓第4個結點的next指向插入資料的開頭*/
		{
			p = p->next;//回圈找到需要插入資料的上一個結點的next所在位置
			i++;
		}
	}
	j->next = p->next;//把p的next地址賦給j的next地址，即新的結點可插入兩個結點的中間
	p->next = j;//p的next指向j的地址
	return head;//回傳第一個結點的地址
}

STU* delete_link(STU* head)//洗掉結點的函式
{
	STU* p1, * p2;
	printf("請輸入需要洗掉資料的位置：\n");
	int m;
	scanf_s("%d", &m);
	p1 = head;
	if (m == 1) //如果洗掉的是第一個結點
	{
		p2 = p1->next; //直接把下一個地址作為回傳值
		free(p1); //釋放記憶體
		return p2;
	}
	else
	{
		int i = 1;
		while (i < m - 1)
		{
			p1 = p1->next;
			i++;
		}
		p2 = p1->next;
		p1->next = p1->next->next;//p1的next指向了需要洗掉的結點的next指向的結點（即越過了中間需要洗掉的結點）
		free(p2);//釋放需要洗掉的結點的空間
		return head;//回傳第一個結點的地址
	}
}

void print(STU* head)//輸出學生資訊的函式
{
	STU* p;
	p = head;//p取head的地址之后，二者同時指向第一個結點的開頭
	n == 0;
	printf("\n");
	if (head != NULL)
	{
		do
		{
			printf("學號：%d 姓名：%s\n", p->num, p->name);
			p = p->next;//把next的地址（即下一個結點的開頭）賦給p
			n++;
		} while (p != NULL);
	}
	printf("\n現在共有%d個學生的資訊：\n", n);
}


void main()
{
	STU* pointer;
	pointer = create();//創建動態鏈表，回傳第一個結點的地址賦給pointer
	n = 0;//n清零，為了保證之后函式里，從第一個結點開始遍歷
	print(pointer);//輸出鏈表
	pointer = insert_link (pointer);
	n = 0;
	print(pointer);//輸出鏈表
	pointer = delete_link(pointer);
	n = 0;
	print(pointer);//輸出鏈表
	free(pointer);//釋放占用的記憶體
	system("pause");
}

總結

以上就是關于動態鏈表的一些具體操作，在整理之后，我對鏈表的結構和一些內容也有了更加深入的了解，
如果大家對于這個內容和代碼還有更好的建議，請多多指正~謝謝！