C語言鏈表與單鏈表詳解

Posted on by

📌鏈表是什麼及鏈表的優勢

鏈表是一種介於數組的另外一種數據結構：

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

但是當元素足夠多時，還能繼續正常的存放嗎？

事實上的不可以的，雖然系統的內存足夠大，但是這些內存不都是連續的，這就導致會出現沒有足夠的空間去存儲這些元素。

其次就是數組的大小需要你去申請，如果你申請的空間足夠大，就會導致內存的浪費

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

📌鏈表的組成

鏈表的作用就是相當與數組一樣，儲存你數據的

但又不同於數組，鏈表把每一個遊離的數據進行連接，連接的方法通過的是指針，也就是地址，

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

鏈表有時候包括瞭頭結點，它是為瞭方便而設計的結點，這個頭結點一般隻包含地址域，也就是結點1的地址，一般情況下，頭結點的數據域一般無意義。

最後的結點，指向的是NULL，用來限制鏈表的大小

📌單向鏈表結點的定義

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

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

📌單項鏈表的創建

//創建所需的結點
struct Node* createList(int n)
{
	struct Node* first, * t, * last; int i;
	first = (struct Node*)malloc(sizeof(struct Node));
	//給第一個結點數據賦個值
	scanf_s("%d", &first->data);
	last = first ;
	//在創建其他的結點
	for (i = n - 1; i > 0; i--)
	{
		//再首尾中間插入結點.並賦值
		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，都是指針變量，用來存放各個節點的地址

sizeof(struct listnode)函數返回結構體Node類型占用的字節數

malloc(sizeof(struct Node))函數功能：系統從內存的空閑空間中，申請存放一個結點的存儲空間。

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

malloc函數在頭文件stdlib.h中定義 

📌打印出鏈表各個結點的數據

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

其中傳入函數的是結構體指針

從第一個結點的數據域開始打印，到最後的NULL結束

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

📌釋放向系統申請的空間

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;

就相當於 struct Node*p=first;

              struct Node *tmp;

📌例題

🔒從鍵盤輸入一組整數，創建單向鏈表，並輸出鏈表中的數據。

樣例輸入：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;
};
//創建所需的結點
struct Node* createList(int n)
{
	struct Node* first, * t, * last; int i;
	first = (struct Node*)malloc(sizeof(struct Node));
	//給第一個結點數據賦個值
	scanf_s("%d", &first->data);
	last = first ;
	//在創建其他的結點
	for (i = n - 1; i > 0; i--)
	{
		//再首尾中間插入結點.並賦值
		t= (struct Node*)malloc(sizeof(struct Node));
		scanf_s("%d", &t->data);
		last->next = t;
		last=t;
	}
	last->next = NULL;//防止野指針的存在
	return first;
}
//再創建函數進行打印出各個結點的值
void printList(struct Node* first)
{
	//把每一個字節數據域的都打印出來
	struct Node* p = first;
	while (p != NULL)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}
//釋放頭結點申請的空間
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);//輸出頭節點為list的鏈表   、、、、、、
	destoryList(list);
	printf("\n");
	return 0;
}

到此這篇關於C語言鏈表與單鏈表詳解的文章就介紹到這瞭,更多相關C語言 鏈表內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：