欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語言實現(xiàn)動態(tài)鏈表的示例代碼

 更新時間:2022年05月16日 10:05:09   作者:歐拉恒等式  
本文主要介紹了C語言實現(xiàn)動態(tài)鏈表的示例代碼,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu),數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(鏈表中每一個元素稱為結(jié)點)組成,結(jié)點可以在運行時動態(tài)生成。每個結(jié)點包括兩個部分:一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域,另一個是存儲下一個結(jié)點地址的指針域。

結(jié)構(gòu)體定義已經(jīng)函數(shù)聲明

節(jié)點結(jié)構(gòu)體定義

typedef struct SNode{
	void *pdata;	//存儲數(shù)據(jù),這個數(shù)據(jù)可以是任意類型
	struct SNode *next;	//節(jié)點的下一個節(jié)點地址
}SNode;
typedef struct SNode*  SLink;	//定義一個鏈表

函數(shù)聲明

//創(chuàng)建一個鏈表
SLink create_slink();
//初始化一個鏈表
void init_slink(SLink *link);
//判斷鏈表是否為空
bool is_empty(SLink link);
//獲得鏈表存儲的個數(shù)
size_t size(SLink link);
//插入元素  元素存儲在pdata,一共size個字節(jié)
int insert(SLink link,size_t index,void *pdata,size_t size);
//獲得指定下標(biāo)的節(jié)點元素,并且返回其地址
void *get(SLink link,size_t index);
//刪除一個節(jié)點
int remove_data(SLink link,size_t index);
//鏈表逆序
SLink reverse(SLink link);
//清空鏈表
void clear(SLink link);
//銷毀鏈表
void destroy(SLink link);
//遍歷鏈表(通過函數(shù)指針完成用戶需要的要求)
void foreach(SLink link,void (*func)(const void *));
//通過值查找某個節(jié)點
void *find(SLink link,void *pdata,int (*compare)(const void *,const void*));
//通過值刪除所有需要刪除的節(jié)點
int remove_all(SLink link,void *pdata,int (*compare)(const void *,const void *));
//鏈表排序,通過冒泡排序
void sort(SLink link,int (*compare)(const void *,const void *));

函數(shù)實現(xiàn)

創(chuàng)建一個鏈表

首先動態(tài)鏈表一般有一個頭結(jié)點(也不是必須有,但是頭結(jié)點可以讓后面的算法變得簡單些),這個頭結(jié)點不存儲數(shù)據(jù),只存放第一個節(jié)點(存放數(shù)據(jù)的節(jié)點,也叫作首節(jié)點)的地址,所以我們可以讓節(jié)點的pdata為null。
具體實現(xiàn)如下:
首先我們寫一個函數(shù)實現(xiàn)生成一個節(jié)點,這樣在我們以后只要有插入節(jié)點的操作就可以用這個靜態(tài)方法來實現(xiàn);這個函數(shù)我們需要傳數(shù)據(jù)的地址,數(shù)據(jù)的大小(這樣我們才能把數(shù)據(jù)拷貝到節(jié)點里面去),還有下一個節(jié)點的地址;

static SNode *create_node(void *pdata,size_t size,SNode *next){
	SNode *node = malloc(sizeof(SNode));	//先用malloc申請一塊動態(tài)內(nèi)存
	if(pdata == NULL){	//如果傳進來的數(shù)據(jù)地址為null
		node->pdata = NULL;	
	}else{
		node->pdata = malloc(size);	//否則為數(shù)據(jù)也申請一塊大小為size的動態(tài)內(nèi)存,
		memcpy(node->pdata,pdata,size);	//把pdata指向的數(shù)據(jù)通過memcpy拷貝到node->pdata里去,拷貝size個字節(jié)
	}
	node->next = next;	//讓節(jié)點指向下一個節(jié)點
	return node;	//返回這個節(jié)點
}

所以有了上面這個靜態(tài)方法,后面的創(chuàng)建一個鏈表還是插入一個節(jié)點就變得很簡單了
因為我們剛開始創(chuàng)建的是一個空鏈表,即只有一個頭結(jié)點,因此不傳數(shù)據(jù)

SLink create_slink(){
	//return create_node(NULL,0,NULL);
	SNode *head = create_node(NULL,0,NULL);		
	return  head;
}

除了創(chuàng)建一個鏈表,我們還可以初始化一個鏈表,(即在其他函數(shù)里先定義一個節(jié)點)再給它初始化。
這里我們傳進來一個鏈表的地址,鏈表類型為SNode *,它的地址即為SNode **類型,因為只有傳遞一個元素得地址,我們才能在一個函數(shù)中改變這個元素得值(函數(shù)間的傳參是值賦值)。

void init_slink(SLink *link){
	*link = create_node(NULL,0,NULL);	//同樣調(diào)用生成節(jié)點的靜態(tài)方法
}

判斷鏈表是否為空

所謂空鏈表就是指只有一個頭結(jié)點,這個頭結(jié)點并不存儲數(shù)據(jù),只是記錄首節(jié)點的地址,如果這個首節(jié)點的地址為空,那么這就是一個空鏈表

bool is_empty(SLink link){
	return link->next == NULL;	
}

獲得鏈表中節(jié)點的個數(shù)

鏈表中的節(jié)點是指存儲了元素的節(jié)點,所以不能包含頭結(jié)點,我們只需要把這個節(jié)點遍歷一遍,如果某個節(jié)點的下一個地址(next)為空,那這個節(jié)點就是尾結(jié)點

}
size_t size(SLink link){
	size_t cnt = 0;	//用來記錄節(jié)點個數(shù)
	SNode *node = link->next;	//從首節(jié)點開始算起
	while(node != NULL){	//遍歷這個鏈表
		++cnt;
		node = node->next;
	}
	return cnt;
}

在某個特定的位置插入一個元素

在index的位置插入一個元素,就是我們需要把index的位置變成我們新插入的節(jié)點。
在鏈表中插入一個節(jié)點,并不像在線性表(數(shù)組)中那么復(fù)雜,在線性表中插入一個元素我們需要把插入節(jié)點后面的元素都往后移,這樣增加了很多負擔(dān),但是在鏈表中的插入節(jié)點(或者刪除節(jié)點),都只需要改變一下附近節(jié)點的指針指向就OK了,所以操作變得簡單了很多,下面我們來詳細講解一下如何插入一個節(jié)點。

首先肯定是找到我們插入的位置

插入

如上圖所示,我們需要在下標(biāo)為3的位置插入一個節(jié)點,那我們該怎么做呢?
是的我們可以想辦法獲得下標(biāo)為2這個節(jié)點,然后斷開2和3之間的連線,再把new節(jié)點插入進去

在這里插入圖片描述

如圖,我們把2節(jié)點的next指向了新插入的new節(jié)點,把new的next指向了3的節(jié)點,那2和3之間的連系就順利成章的斷掉了,那我們的插入就算完成了。
所以我們來看一下代碼
首先當(dāng)然是獲得我們需要插入位置的前一個節(jié)點,即上圖的2節(jié)點

static SNode *get_prev_node(SLink link,size_t index){	//獲得前一個節(jié)點
	SNode *node = link;//從頭結(jié)點開始找,比如我們插入在鏈表首插入一個節(jié)點就是插入到頭結(jié)點后面
	//我們在鏈表尾插入一個節(jié)點就是當(dāng)node->next為null的時候插入
	size_t i;
	for(i=0;i<index && node != NULL;i++){
		node = node->next;	
	}
	return node;	//這里的返回值可能為null,比如當(dāng)node為尾結(jié)點的時候,它的node->next就為null
}

插入操作

int insert(SLink link,size_t index,void *pdata,size_t size){
	if(pdata == NULL){	//如果沒有傳進來數(shù)據(jù),那就插入失敗
		return -1;	
	}
	SNode *prev = get_prev_node(link,index);
	if(prev == NULL){	//獲得插入位置的前一個節(jié)點,當(dāng)它為Null時也不能插入數(shù)據(jù),
		return -1;	
	}
	SNode *node = create_node(pdata,size,prev->next);	//調(diào)用生成節(jié)點的靜態(tài)方法生成一個節(jié)點,
	//并且傳入pdata,size,如上圖所示,新插入的節(jié)點的next指向的是原本前一個節(jié)點prev的next
	prev->next = node; //把prev->next重新指向新插入的節(jié)點,這樣插入就完成了
	//完成了new節(jié)點旁邊兩條線的鏈接工作
	//prev->next = create_node(pdata,size,prev->next);
	return 0;
}

關(guān)于在鏈表首或者鏈表尾插入數(shù)據(jù)

這里其實很簡單,就是新插入的節(jié)點的前一個節(jié)點為頭結(jié)點或者尾結(jié)點的問題,大家可以自己寫一下

獲得指定下標(biāo)的節(jié)點的元素

這個操作比較簡單,只需要在滿足條件下把這個下標(biāo)遍歷完就可以了,沒有什么難點

void *get(SLink link,size_t index){
	SNode *node = link->next;	//這里我們不能從頭結(jié)點開始遍歷,因為頭結(jié)點并不存儲數(shù)據(jù)所以只能從首節(jié)點開始遍歷
	size_t i;
	for(i=0;i<index && node != NULL;i++){
		node = node->next;	
	}
	if(node == NULL){
		return NULL;	
	}
	return node->pdata;	//遍歷完成并且返回這個數(shù)據(jù)的地址即可
}

刪除一個節(jié)點

刪除可以說是插入的反過來的操作

在這里插入圖片描述

比如上圖,我們需要刪除3這個節(jié)點,那我們該怎么辦呢?其實比插入更簡單,我們只需要讓2的next指向需要刪除節(jié)點的next(也就是3的next),并且把3節(jié)點給釋放掉,把里面的數(shù)據(jù)也釋放掉就OK了
首先我們也可以寫一個靜態(tài)方法來實現(xiàn)刪除某個節(jié)點

static void remove_node(SNode *prev){	//這里的prev為需要被刪除的節(jié)點的前一個節(jié)點
	SNode *node = prev->next;	//記錄被刪除的節(jié)點
	SNode *next = node->next;	//記錄被刪除的節(jié)點的下一個節(jié)點
	free(node->pdata);
	free(node);
	prev->next = next;
}

然后刪除節(jié)點的操作

int remove_data(SLink link,size_t index){
	SNode *prev = get_prev_node(link,index);	//獲得被刪除節(jié)點的前一個節(jié)點
	if(link == NULL || prev == NULL || prev->next == NULL){
	//如果鏈表不存在或者被刪除節(jié)點的前一個節(jié)點不存在或者被刪除的節(jié)點不存在,那就刪除失敗
		return -1;	
	}
	remove_node(prev);
	return 0;
}

大家自己也可以寫一下刪除首節(jié)點或者尾結(jié)點

鏈表逆序

所謂鏈表逆序就是將鏈表的存儲順序反過來,

在這里插入圖片描述

比如上圖,它的逆序結(jié)果是什么呢?
我們來看一下,就是讓5節(jié)點的next指向4節(jié)點,4指向3,3指向2,2指向1,1的next指向NULL,然后再把頭結(jié)點指向5,就完成了逆序,如下圖所示

在這里插入圖片描述

那我們該怎么用代碼實現(xiàn)呢?

SLink reverse(SLink link){
	if(link==NULL || link->next == NULL || link->next->next == NULL){	
	//如果鏈表不存在或者只存在頭結(jié)點或者只存在一個節(jié)點,那么我們就不需要進行逆序操作
		return link;	
	}	
	SNode *prev = link->next;//記錄第一個節(jié)點	
	SNode *curr = link->next->next;//記錄第二個節(jié)點
	SNode *next;
	while(curr != NULL){	//只要當(dāng)前節(jié)點不為空就繼續(xù)執(zhí)行下去
		next = curr->next;	//記錄curr的下一個節(jié)點
		curr->next = prev;	//讓指針反過來指向,即當(dāng)前節(jié)點的指針指向前一個節(jié)點
		prev = curr;	//然后往后移
		curr = next;
	}
	//最后還有兩條線沒有連上
	//即以前的首節(jié)點(即上圖的節(jié)點1)的next應(yīng)該指向null,首節(jié)點再變?yōu)閜rev,即上圖的節(jié)點5
	link->next->next = NULL;	//
	link->next = prev;
	return link;
}

鏈表的清空

清空鏈表只需要一個一個的遍歷,把節(jié)點里的數(shù)據(jù)釋放掉,再釋放掉該節(jié)點

void clear(SLink link){
	SNode *node = link->next;	//從首節(jié)點開始遍歷
	while(node != NULL){
		SNode *next = node->next;		//記錄需要被釋放的節(jié)點的下一個節(jié)點
		free(node->pdata);
		free(node);
		node = next;
	}
	link->next = NULL;
}

鏈表的銷毀

這個更為簡單,只需要先清空里面的節(jié)點,在把頭結(jié)點釋放掉即可

void destroy(SLink link){
	clear(link);	
	free(link);
}

鏈表的遍歷

鏈表的遍歷也無需多說,我們只需要從首節(jié)點開始遍歷,并且把節(jié)點的數(shù)據(jù)傳給函數(shù)指針,這樣也更加靈活,一直遍歷到null為止

void foreach(SLink link,void (*func)(const void *)){
	SNode *node = link->next;	//從首節(jié)點開始遍歷
	for(;node != NULL; node = node->next){
		func(node->pdata);	//把節(jié)點的數(shù)據(jù)傳給func這個函數(shù),
		//然后用戶需要對這個數(shù)據(jù)進行什么樣的處理由用戶自己決定,不僅僅是局限于把這些數(shù)據(jù)給打印出來
		//這樣的好處是對數(shù)據(jù)的處理更加靈活了
	}
}

按特定的元素查找節(jié)點

我們也是從首節(jié)點開始遍歷,對首節(jié)點里的數(shù)據(jù)進行比較,如果找到相同的數(shù)據(jù),那就返回這個數(shù)據(jù)的地址

void *find(SLink link,void *pdata,int (*compare)(const void *,const void*)){
	SNode *node = link->next;	//從首節(jié)點開始查找
	for(;node != NULL; node = node->next){
		if(compare(node->pdata,pdata)==0){	//如果該節(jié)點的數(shù)據(jù)和帶查找的數(shù)據(jù)相等
			return node->pdata;		//那就返回這個數(shù)據(jù)的地址
		}	
	}
	return NULL;	//如果沒有找到就返回null
}

這里的compare也是函數(shù)指針,都是同樣的道理,對于需要找什么由用戶自己決定,不在局限于查找某個特定的元素
比如在一個學(xué)生信息的結(jié)構(gòu)體中,我們可以按學(xué)號進行查找,也可以按姓名進行查找,也可以按年齡、班級、等等進行查找,讓這些使用起來更加靈活
比如我給大家寫一個查找的函數(shù),就按學(xué)生的學(xué)號進行查找

int compare(const void* v1,const void* v2){
	Stu *stu1 = (Stu *)v1;
	Stu *stu2 = (Stu *)v2;
	return v1->no-v2->no;
}

按某些特定的條件刪除所有符合情況的節(jié)點

這個刪除的操作其實和上面的刪除特定下標(biāo)的節(jié)點的操作大同小異,都是找到待刪除節(jié)點的前一個節(jié)點,然后進行操作,這里找到后并不急于退出,而是繼續(xù)往下查找,直到找完整個鏈表并且刪除所有符合條件的節(jié)點

int remove_all(SLink link,void *pdata,int (*compare)(const void *,const void *)){	
	SNode *prev = link;
	int cnt = 0;
	while(prev->next != NULL){
		if(compare(prev->next->pdata,pdata)==0){	//找到待刪除節(jié)點的前一個節(jié)點
			remove_node(prev);	//刪除該節(jié)點
			cnt++;	//刪除的個數(shù)++
		}else{
			prev = prev->next;	//否則沒找到就是往下繼續(xù)查找
		}
	}
	return cnt>0?0:-1;
}

鏈表的排序

排序我這里選擇冒泡排序,如果大家想看更多的排序方法也可以看我以前寫的博客,我總共寫了12種排序方法
這里的排序和我以前寫的幾乎一模一樣,我就不再多說了,唯一需要講解的還是函數(shù)指針的應(yīng)用,比如我們可以選擇對學(xué)生的學(xué)號進行排序,也可以對學(xué)生的姓名、成績、身高、年齡等等都可以進行升降序的排序

void sort(SLink link,int (*compare)(const void *,const void *)){
	if(link->next == NULL || link->next->next == NULL){
		return;	
	}	

	size_t i;
	SNode *tail = NULL;
	SNode *n = link->next;
	for(;n != NULL;n = n->next){
		SNode *node;
		bool swap = false;
		for(node = link->next;node->next != tail;node = node->next){
			SNode *prev = node;
			SNode *next = prev->next;
			if(compare(prev->pdata,next->pdata)>0){
			//這里選擇的排序方式或者進行排序的元素
				swap(prev->pdata,next->pdata);
				swap = true;
			}
		}
		tail = node;
		if(!swap){
			break;	
		}
	}
}

我再來寫一個對學(xué)生的姓名按照升序進行排序的方法

int cmopare(const void *v1,const void* v2){
	Stu *s1 = (Stu *)v1;
	Stu *s2 = (Stu *)v2;
	return strcmp(s1->name,s2->name);
}

總結(jié)

一個鏈表的功能的實現(xiàn)就這樣完成了,實現(xiàn)的功能也比較齊全,由于存儲的數(shù)據(jù)可以是任意類型的數(shù)據(jù),可以是整型,也可以是浮點型,結(jié)構(gòu)體類型等等都可以存儲,并且在實現(xiàn)的過程中也大量用到了函數(shù)指針,這樣讓這些操作的適用性更加廣泛,可以在許多項目中直接使用。

到此這篇關(guān)于C語言實現(xiàn)動態(tài)鏈表的示例代碼的文章就介紹到這了,更多相關(guān)C語言 動態(tài)鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • C++實現(xiàn)簡單的掃雷游戲(控制臺版)

    C++實現(xiàn)簡單的掃雷游戲(控制臺版)

    這篇文章主要為大家詳細介紹了C++實現(xiàn)簡單的掃雷游戲,控制臺版的掃雷游戲希望大家喜歡,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2016-05-05
  • C++ sort排序函數(shù)用法詳解

    C++ sort排序函數(shù)用法詳解

    本文主要介紹了C++ sort排序函數(shù)用法詳解,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2022-06-06
  • Qt學(xué)習(xí)教程之對話框消失動畫效果

    Qt學(xué)習(xí)教程之對話框消失動畫效果

    這篇文章主要給大家介紹了關(guān)于Qt學(xué)習(xí)教程之對話框消失動畫效果的相關(guān)資料,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2018-07-07
  • C++實現(xiàn)ini文件讀寫的示例代碼

    C++實現(xiàn)ini文件讀寫的示例代碼

    這篇文章主要介紹了C++如何實現(xiàn)讀寫ini配置文件,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
    2022-05-05
  • C++設(shè)計模式之訪問者模式

    C++設(shè)計模式之訪問者模式

    這篇文章主要介紹了C++設(shè)計模式之訪問者模式,本文講解了什么是訪問者模式、訪問者模式的UML類圖、訪問者模式的實現(xiàn)代碼等內(nèi)容,需要的朋友可以參考下
    2014-10-10
  • 使用QT連接USB攝像頭的方法

    使用QT連接USB攝像頭的方法

    這篇文章主要為大家詳細介紹了使用QT連接USB攝像頭的方法,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2022-08-08
  • C語言開發(fā)中的常見錯誤詳解

    C語言開發(fā)中的常見錯誤詳解

    這個分欄是對于使用C語言編程過程中可能會出現(xiàn)的一些錯誤而進行的說明,更多的錯誤示例將會在后面的內(nèi)容里進行演示。希望這個分欄的內(nèi)容可以幫助剛學(xué)編程的小白少走一些彎路,以及吸取更多的編碼經(jīng)驗
    2022-05-05
  • 詳細對比C語言中的chmod()函數(shù)和fchmod()函數(shù)

    詳細對比C語言中的chmod()函數(shù)和fchmod()函數(shù)

    這篇文章主要介紹了C語言中的chmod()函數(shù)和fchmod()函數(shù)的詳細對比,兩個都是用于修改文件權(quán)限但是請注意實際使用上的差異,需要的朋友可以參考下
    2015-09-09
  • Qt中QtWebEngine加載本地網(wǎng)頁跨域問題的總結(jié)

    Qt中QtWebEngine加載本地網(wǎng)頁跨域問題的總結(jié)

    本文主要介紹了Qt中QtWebEngine加載本地網(wǎng)頁跨域問題的總結(jié),文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2022-04-04
  • C++實現(xiàn)各種排序算法類匯總

    C++實現(xiàn)各種排序算法類匯總

    這篇文章主要介紹了C++實現(xiàn)各種排序算法類,需要的朋友可以參考下
    2014-07-07

最新評論