C語(yǔ)言鏈表詳解及代碼分析

更新時(shí)間：2021年06月28日 10:16:13 作者：code.com

這篇文章主要介紹了C語(yǔ)言鏈表詳解及代碼分析,說(shuō)明了鏈表的定義與概念,通過(guò)詳細(xì)的代碼展示了基于鏈表的增刪改查功能,希望本文能對(duì)你有所幫助

什么是鏈表

鏈表是一種常見(jiàn)的重要的數(shù)據(jù)結(jié)構(gòu)。它是動(dòng)態(tài)地進(jìn)行存儲(chǔ)分配的一種結(jié)構(gòu)。鏈表和數(shù)組比較，不用事先確定存儲(chǔ)空間，而是根據(jù)需要開(kāi)辟內(nèi)存單元。
下圖1是最簡(jiǎn)單的一種鏈表（單向鏈表）的結(jié)構(gòu)

第 0 個(gè)結(jié)點(diǎn)稱為頭結(jié)點(diǎn)，它存放有第一個(gè)結(jié)點(diǎn)的首地址，它沒(méi)有數(shù)據(jù)，只是一個(gè)指針變量。以下的每個(gè)結(jié)點(diǎn)都分為兩個(gè)域，一個(gè)是數(shù)據(jù)域，存放各種實(shí)際的數(shù)據(jù)，如學(xué)號(hào) num，姓名 name，性別 sex 和成績(jī) score 等。另一個(gè)域?yàn)橹羔樣?，存放下一結(jié)點(diǎn)的首地址。鏈表中的每一個(gè)結(jié)點(diǎn)都是同一種結(jié)構(gòu)類型。

環(huán)境構(gòu)建

用的Visual Studio 2019軟件

在這里插入圖片描述

在源文件中添加C文件

在這里插入圖片描述

建立靜態(tài)鏈表

包含所需要的頭文件

#include<stdio.h> //標(biāo)準(zhǔn)輸入輸出頭文件
#include<stdlib.h>//包含了C、C++語(yǔ)言的最常用的系統(tǒng)函數(shù)

宏定義相關(guān)變量

#define LEN sizeof(struct Student)//宏定義節(jié)點(diǎn)長(zhǎng)度得命名
#define TYPE struct Student//宏定義結(jié)構(gòu)體變量命名

創(chuàng)建一個(gè)結(jié)構(gòu)體

struct Student//定義一個(gè)學(xué)生類型結(jié)構(gòu)體，包括學(xué)號(hào)，分?jǐn)?shù)
{
	long num;
	float score;
	struct Student* next;//next是指針變量，指向結(jié)構(gòu)體變量
};
//指向結(jié)構(gòu)體對(duì)象得指針變量既可以指向結(jié)構(gòu)體變量，也可以指向結(jié)構(gòu)體數(shù)組中得元素

主函數(shù)

int main()
{
	TYPE* head,*p;//定義頭指針
	struct Student a,b,c;//定義三個(gè)結(jié)構(gòu)體變量
	a.num = 101; a.score = 20;//分別對(duì)三個(gè)結(jié)點(diǎn)賦值
	b.num = 102; b.score = 20;
	c.num = 103; c.score = 20;
	/*1、A.B則A為對(duì)象或者結(jié)構(gòu)體
      2、A->B則A為指針，->是成員提取，A->B是提取A中的成員B，A只能是指向類、結(jié)構(gòu)、聯(lián)合的指針；*/
	head = &a;
	a.next = &b;
	b.next = &c;
	c.next = NULL;
	p = head;//把首地址給變量
	do
	{
		printf("%ld %5.1f\n",p->num,p->score);//輸出每個(gè)結(jié)點(diǎn)信息
		p = p->next;//使P指向下一個(gè)結(jié)點(diǎn)
	} while (p != NULL);//直到指針域指向空值
	return 0;
}

結(jié)果展示

在這里插入圖片描述

說(shuō)明

將第一個(gè)結(jié)點(diǎn)的起始地址賦值給頭指針head,將第二個(gè)結(jié)點(diǎn)的起始地址賦值給第一個(gè)結(jié)點(diǎn)的next成員，將第二個(gè)結(jié)點(diǎn)的起始地址賦給第一個(gè)結(jié)點(diǎn)的next…第三個(gè)結(jié)點(diǎn)的next賦值為NULL，這就形成了簡(jiǎn)單的鏈表。

建立動(dòng)態(tài)鏈表

所謂建立動(dòng)態(tài)鏈表是指在程序執(zhí)行過(guò)程中從無(wú)到有地建立起一個(gè) 鏈表，即一個(gè)一個(gè)地開(kāi)辟結(jié)點(diǎn)和輸入各結(jié)點(diǎn)數(shù)據(jù)，并建立起前后相連的關(guān)系。

包含所需要的頭文件

#include<stdio.h> //標(biāo)準(zhǔn)輸入輸出頭文件
#include<stdlib.h>//包含了C、C++語(yǔ)言的最常用的系統(tǒng)函數(shù)
#include<malloc.h>//動(dòng)態(tài)存儲(chǔ)分配函數(shù)頭文件

宏定義相關(guān)變量

#define LEN sizeof(struct Student)//宏定義節(jié)點(diǎn)長(zhǎng)度得命名
#define TYPE struct Student//宏定義結(jié)構(gòu)體變量命名

創(chuàng)建一個(gè)結(jié)構(gòu)體

struct Student//定義一個(gè)學(xué)生類型結(jié)構(gòu)體，包括學(xué)號(hào)，分?jǐn)?shù)
{
	long num;
	float score;
	struct Student* next;//next是指針變量，指向結(jié)構(gòu)體變量
};
//指向結(jié)構(gòu)體對(duì)象得指針變量既可以指向結(jié)構(gòu)體變量，也可以指向結(jié)構(gòu)體數(shù)組中得元素

建立鏈表函數(shù)

TYPE* Creat(void)//定義函數(shù)，此函數(shù)返回一個(gè)指向鏈表頭的指針
{
	TYPE* head;//定義頭指針
	TYPE* p1,*p2;//定義兩個(gè) 指針變量用來(lái)相互保存
	number = 0;//開(kāi)始時(shí)，結(jié)點(diǎn)清零
	p1 = p2 = (TYPE*)malloc(LEN);//創(chuàng)建存儲(chǔ)空間
	printf("請(qǐng)按格式輸入學(xué)生學(xué)號(hào)，分?jǐn)?shù)\n");//輸出提示信息
	printf("例如101,1 并以0,0結(jié)束\n");
	scanf("%ld,%f", &p1->num, &p1->score);//按格式輸入第一個(gè)結(jié)點(diǎn)的信息
	head = NULL;//第一個(gè)結(jié)點(diǎn)頭指針賦空值
	while (p1->num!=0)//循環(huán)直到輸入學(xué)生學(xué)號(hào)為0，就結(jié)束
	{
		number++;//結(jié)點(diǎn)自增
		if (number == 1)//如果只有一個(gè)結(jié)點(diǎn)，那么頭指針指向第一個(gè)輸入的結(jié)點(diǎn)
			head = p1;
		else
			p2->next = p1;//如果大于1個(gè)，那么要用next保存前一個(gè)結(jié)點(diǎn)的信息
		p2 = p1;//保存前一個(gè)結(jié)點(diǎn)信息
		p1 = (TYPE*)malloc(LEN);//開(kāi)辟新的結(jié)點(diǎn)
		scanf("%ld,%f", &p1->num, &p1->score);//輸入下一個(gè)結(jié)點(diǎn)信息
	}
	p2->next = NULL;//循環(huán)結(jié)束，將指向信息賦空值
	return (head);//返回首地址
}

主函數(shù)

int main()
{
	TYPE* pt;//定義一個(gè)結(jié)構(gòu)體指針變量
	pt = Creat();//函數(shù)返回鏈表第一個(gè)結(jié)點(diǎn)的地址
	printf("\nnum:%ld\nscore:%5.lf\n", pt->num,pt->score);//輸出第一個(gè)結(jié)點(diǎn)的成員值
	return 0;
}

結(jié)果展示

在這里插入圖片描述

== 文中最后結(jié)果顯示的是第一個(gè)結(jié)點(diǎn)的內(nèi)容，作為有強(qiáng)大功能的鏈表，對(duì)他的操作當(dāng)然有許多，比如：鏈表的創(chuàng)建，修改，刪除，插入，輸出，排序，反序，清空鏈表的元素，求鏈表的長(zhǎng)度等等。==

鏈表的輸出

用循環(huán)直接可以輸出鏈表

輸出函數(shù)

void print(TYPE * head)
{
	TYPE * p;//定義指針
	printf("\nNOW These %d records are:\n");//輸出顯示信息
	p = head;//使p指向第一個(gè)結(jié)點(diǎn)
	if(head!=NULL)//輸出第一個(gè)結(jié)點(diǎn)后的信息
		do {
			printf("%ld %5.1f\n",p->num,p->score);
			p = p->next;//指向下個(gè)結(jié)點(diǎn)
		} while (p != NULL);
}

主函數(shù)

int main()
{
	TYPE * pt;//定義一個(gè)結(jié)構(gòu)體指針變量
	pt = Creat();//函數(shù)返回鏈表第一個(gè)結(jié)點(diǎn)的地址
	print(pt);//輸出調(diào)用
	return 0;
}

鏈表的修改

修改函數(shù)

修改鏈表節(jié)點(diǎn)值很簡(jiǎn)單。下面是一個(gè)傳入鏈表和要修改的節(jié)點(diǎn)，來(lái)修改值的函數(shù).

void change(TYPE* head, int n) //修改指定位置的結(jié)點(diǎn)的信息
{
	TYPE* p = head;//傳入首地址
	int i = 0;
	while (i < n && p != NULL) {
		p = p->next;
		i++;
	}//找到相應(yīng)的位置結(jié)點(diǎn)
	if (p != NULL) {
		printf("輸入要修改的值\n");
		scanf("%ld,%f", &p->num, &p->score);//輸入下一個(gè)結(jié)點(diǎn)信息
	}
	else 
		printf("節(jié)點(diǎn)不存在\n");
	}

主函數(shù)

int main()
{
	TYPE* pt;//定義一個(gè)結(jié)構(gòu)體指針變量
	pt = Creat();//函數(shù)返回鏈表第一個(gè)結(jié)點(diǎn)的地址
	change(pt,2);//修改相關(guān)結(jié)點(diǎn)的信息,假設(shè)修改第2+1個(gè)
	print(pt);//輸出調(diào)用
	return 0;
}

##鏈表的刪除

刪除鏈表的元素也就是把前節(jié)點(diǎn)的指針域越過(guò)要?jiǎng)h除的節(jié)點(diǎn)指向下下個(gè)節(jié)點(diǎn)。即：p->next = q->next;然后放出q節(jié)點(diǎn)的空間，即free(q);

在這里插入圖片描述

刪除函數(shù)

void delet(TYPE* head, int n) {
	TYPE* p = head, * in;//定義兩邊指針
	int i = 0;
	while (i < n && p != NULL) {
		in = p;//找到左邊的
		p = p->next;//找到右邊的
		i++;
	}
	if (p != NULL) {
		in->next = p->next;//將左右鏈接
		free(p);//釋放中間結(jié)點(diǎn)
	}
	else {
		printf("節(jié)點(diǎn)不存在\n");
	}

}

主函數(shù)

int main()
{
	TYPE* pt;//定義一個(gè)結(jié)構(gòu)體指針變量
	pt = Creat();//函數(shù)返回鏈表第一個(gè)結(jié)點(diǎn)的地址
	delet(pt,1);//刪除第1+1個(gè)結(jié)點(diǎn)
	print(pt);//輸出調(diào)用
	return 0;
}

輸出結(jié)果

在這里插入圖片描述

##鏈表的插入
我們可以看出來(lái)，插入節(jié)點(diǎn)就是用插入前節(jié)點(diǎn)的指針域鏈接上插入節(jié)點(diǎn)的數(shù)據(jù)域，再把插入節(jié)點(diǎn)的指針域鏈接上插入后節(jié)點(diǎn)的數(shù)據(jù)域。根據(jù)圖，插入節(jié)點(diǎn)也就是：e->next = head->next; head->next = e;
增加鏈表節(jié)點(diǎn)用到了兩個(gè)結(jié)構(gòu)體指針和一個(gè)int數(shù)據(jù)。

在這里插入圖片描述

插入函數(shù)

void insert(TYPE* head, int n) {//鏈表的插入
	TYPE* p = head, * in;
	int i = 0;
	while (i < n && p != NULL) {
		p = p->next;
		i++;//找到相應(yīng)結(jié)點(diǎn)
	}
	if (p != NULL) {
		in = (TYPE*)malloc(sizeof(TYPE));//開(kāi)辟新的空間
		printf("輸入要插入的值\n");
		scanf("%ld,%f", &in->num, &in->score);//輸入新的結(jié)點(diǎn)信息
		in->next = p->next;//填充in節(jié)點(diǎn)的指針域，也就是說(shuō)把in的指針域指向p的下一個(gè)節(jié)點(diǎn)
		p->next = in;//填充p節(jié)點(diǎn)的指針域，把p的指針域重新指向in
	}
	else {
		printf("節(jié)點(diǎn)不存在\n");
	}

}

主函數(shù)

int main()
{
	TYPE* pt;//定義一個(gè)結(jié)構(gòu)體指針變量
	pt = Creat();//函數(shù)返回鏈表第一個(gè)結(jié)點(diǎn)的地址
	insert(pt, 1);//從1+1后插入
	print(pt);//輸出調(diào)用
	return 0;
}