日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學(xué)無先后，達(dá)者為師

網(wǎng)站首頁 編程語言 正文

C語言鏈表與單鏈表詳解_C 語言

作者：誠摯的喬治 ? 更新時間： 2022-04-16 編程語言

?鏈表是什么及鏈表的優(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)存的浪費(fèi)

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

?鏈表的組成

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

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

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

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

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

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

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

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

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

//創(chuàng)建所需的結(jié)點(diǎn)
struct Node* createList(int n)
{
	struct Node* first, * t, * last; int i;
	first = (struct Node*)malloc(sizeof(struct Node));
	//給第一個結(jié)點(diǎn)數(shù)據(jù)賦個值
	scanf_s("%d", &first->data);
	last = first ;
	//在創(chuàng)建其他的結(jié)點(diǎn)
	for (i = n - 1; i > 0; i--)
	{
		//再首尾中間插入結(jié)點(diǎn).并賦值
		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é)點(diǎn)的地址

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

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

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

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

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

//再創(chuàng)建函數(shù)進(jìn)行打印出各個結(jié)點(diǎn)的值
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é)點(diǎn)的數(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é)點(diǎn)
struct Node* createList(int n)
{
	struct Node* first, * t, * last; int i;
	first = (struct Node*)malloc(sizeof(struct Node));
	//給第一個結(jié)點(diǎn)數(shù)據(jù)賦個值
	scanf_s("%d", &first->data);
	last = first ;
	//在創(chuàng)建其他的結(jié)點(diǎn)
	for (i = n - 1; i > 0; i--)
	{
		//再首尾中間插入結(jié)點(diǎn).并賦值
		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é)點(diǎn)的值
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é)點(diǎ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);//輸出頭節(jié)點(diǎn)為list的鏈表   、、、、、、
	destoryList(list);
	printf("\n");
	return 0;
}

原文鏈接：https://z-ming.blog.csdn.net/article/details/122400440

欄目分類
最近更新