C語言鏈表與單鏈表詳解

更新時間：2022年02月10日 11:55:57 作者：誠摯的喬治

鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的，本章帶你詳細(xì)了解鏈表與單鏈表

??鏈表是什么及鏈表的優(yōu)勢

鏈表是一種介于數(shù)組的另外一種數(shù)據(jù)結(jié)構(gòu)：

我們知道數(shù)組可以存放很多的元素，這些元素都是呈線性排列，也就是一個挨著一個連續(xù)存放

但是當(dāng)元素足夠多時，還能繼續(xù)正常的存放嗎？

事實上的不可以的，雖然系統(tǒng)的內(nèi)存足夠大，但是這些內(nèi)存不都是連續(xù)的，這就導(dǎo)致會出現(xiàn)沒有足夠的空間去存儲這些元素。

其次就是數(shù)組的大小需要你去申請，如果你申請的空間足夠大，就會導(dǎo)致內(nèi)存的浪費

而鏈表就很好的解決了這兩個問題

??鏈表的組成

鏈表的作用就是相當(dāng)與數(shù)組一樣，儲存你數(shù)據(jù)的

但又不同于數(shù)組，鏈表把每一個游離的數(shù)據(jù)進(jìn)行連接，連接的方法通過的是指針，也就是地址，

每一個鏈表都是由一個個結(jié)點組成，結(jié)點包含，一個是為我們存放數(shù)據(jù)的空間，另一個是存放下一個結(jié)點地址的空間，也就是所謂的數(shù)據(jù)域和地址域。

鏈表有時候包括了頭結(jié)點，它是為了方便而設(shè)計的結(jié)點，這個頭結(jié)點一般只包含地址域，也就是結(jié)點1的地址，一般情況下，頭結(jié)點的數(shù)據(jù)域一般無意義。

最后的結(jié)點，指向的是NULL，用來限制鏈表的大小

??單向鏈表結(jié)點的定義

說完鏈表的組成是結(jié)點，那單向鏈表的結(jié)點是如何定義的呢

struct  Node  //鏈表的結(jié)點 
 
{
 
             int data;                   //結(jié)點的值
 
             struct Node  *next;    //下一個結(jié)點的地址
 
};

??單項鏈表的創(chuàng)建

//創(chuàng)建所需的結(jié)點
struct Node* createList(int n)
{
	struct Node* first, * t, * last; int i;
	first = (struct Node*)malloc(sizeof(struct Node));
	//給第一個結(jié)點數(shù)據(jù)賦個值
	scanf_s("%d", &first->data);
	last = first ;
	//在創(chuàng)建其他的結(jié)點
	for (i = n - 1; i > 0; i--)
	{
		//再首尾中間插入結(jié)點.并賦值
		t= (struct Node*)malloc(sizeof(struct Node));
		scanf_s("%d", &t->data);
		last->next = t;
		last=t;
	}
	last->next = NULL;//防止野指針的存在
	return first;
}

??其中的first，last，還有t，都是指針變量，用來存放各個節(jié)點的地址

sizeof(struct listnode)函數(shù)返回結(jié)構(gòu)體Node類型占用的字節(jié)數(shù)

malloc(sizeof(struct Node))函數(shù)功能：系統(tǒng)從內(nèi)存的空閑空間中，申請存放一個結(jié)點的存儲空間。

(struct listnode *)malloc(sizeof(struct Node))，函數(shù)返回一個指針（地址），指向剛分配給結(jié)構(gòu)體的第一個字節(jié)的地址。

malloc函數(shù)在頭文件stdlib.h中定義

??打印出鏈表各個結(jié)點的數(shù)據(jù)

//再創(chuàng)建函數(shù)進(jìn)行打印出各個結(jié)點的值
void printList(struct Node* first)
{
	//把每一個字節(jié)數(shù)據(jù)域的都打印出來
	struct Node* p = first;
	while (p != NULL)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

其中傳入函數(shù)的是結(jié)構(gòu)體指針

從第一個結(jié)點的數(shù)據(jù)域開始打印，到最后的NULL結(jié)束

（訪問下一個數(shù)據(jù)域不能用p++，因為鏈表不是連續(xù)的，地址也不是連續(xù)的，如果要訪問下一個數(shù)據(jù)，需要用p = p->next）

??釋放向系統(tǒng)申請的空間

void destoryList(struct Node* first)
{
	struct Node* p = first, *tmp;
 
	while (p != NULL)
	{
		tmp = p->next;
		free(p);
		p = tmp;
	}
}

這里的 struct Node* p = first, *tmp;

就相當(dāng)于 struct Node*p=first;

struct Node *tmp;

??例題

??從鍵盤輸入一組整數(shù)，創(chuàng)建單向鏈表，并輸出鏈表中的數(shù)據(jù)。

樣例輸入：2 5 7 6 3 4

樣例輸出：2 5 7 6 3 4

?? 解答如下：

#include<stdio.h>
#include<stdlib.h>
#define N 6
//鏈表
struct Node
{
	int data;
	struct Node* next;
};
//創(chuàng)建所需的結(jié)點
struct Node* createList(int n)
{
	struct Node* first, * t, * last; int i;
	first = (struct Node*)malloc(sizeof(struct Node));
	//給第一個結(jié)點數(shù)據(jù)賦個值
	scanf_s("%d", &first->data);
	last = first ;
	//在創(chuàng)建其他的結(jié)點
	for (i = n - 1; i > 0; i--)
	{
		//再首尾中間插入結(jié)點.并賦值
		t= (struct Node*)malloc(sizeof(struct Node));
		scanf_s("%d", &t->data);
		last->next = t;
		last=t;
	}
	last->next = NULL;//防止野指針的存在
	return first;
}
//再創(chuàng)建函數(shù)進(jìn)行打印出各個結(jié)點的值
void printList(struct Node* first)
{
	//把每一個字節(jié)數(shù)據(jù)域的都打印出來
	struct Node* p = first;
	while (p != NULL)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}
//釋放頭結(jié)點申請的空間
void destoryList(struct Node* first)
{
	struct Node* p = first, *tmp;
 
	while (p != NULL)
	{
		tmp = p->next;
		free(p);
		p = tmp;
	}
}
 
 
 
int main()
{
	struct Node* list;
	list = createList(N);
	printList(list);//輸出頭節(jié)點為list的鏈表   、、、、、、
	destoryList(list);
	printf("\n");
	return 0;
}

到此這篇關(guān)于C語言鏈表與單鏈表詳解的文章就介紹到這了,更多相關(guān)C語言鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: