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

C語言實(shí)現(xiàn)單鏈表的快速排序算法

 更新時(shí)間:2022年01月20日 09:52:20   作者:CUP-GYC  
大家好,本篇文章主要講的是C語言實(shí)現(xiàn)單鏈表的快速排序算法,感興趣的同學(xué)趕快來看一看吧,對(duì)你有幫助的話記得收藏一下

背景

傳統(tǒng)QuickSort算法最大不足之處在于,由于其基于可索引存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)(一般為數(shù)組或索引表),因而無法用于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的實(shí)際應(yīng)用非常廣泛,例如動(dòng)態(tài)存儲(chǔ)管理、動(dòng)態(tài)優(yōu)先級(jí)調(diào)度等等,故本文針對(duì)于單向鏈表,以QuickSort的分治策略為基礎(chǔ),提出一種可用于單向鏈表的快速排序算法。

設(shè)計(jì)思路

將單向鏈表的首節(jié)點(diǎn)作為樞軸節(jié)點(diǎn),然后從單向鏈表首部的第二個(gè)節(jié)點(diǎn)開始,逐一遍歷所有后續(xù)節(jié)點(diǎn),并將這些已遍歷節(jié)點(diǎn)的key與樞軸節(jié)點(diǎn)的key進(jìn)行比較,根據(jù)比較結(jié)果,重新將這些節(jié)點(diǎn)鏈接為less和more兩個(gè)單向鏈表,less中所包含節(jié)點(diǎn)的key均小于樞軸節(jié)點(diǎn)的 key;more中所包含節(jié)點(diǎn)的key均大于或等于樞軸節(jié)點(diǎn)的key。然后再對(duì)得到的兩個(gè)單鏈表進(jìn)行遞歸操作,將進(jìn)行內(nèi)部遞歸排序最后連接到樞軸上。同時(shí)為達(dá)到在每次劃分后將規(guī)模更小的兩個(gè)單向鏈表鏈接到樞軸節(jié)點(diǎn)上,必須記錄各自的尾節(jié)點(diǎn)位置,即需要設(shè)置兩個(gè)指向尾節(jié)點(diǎn)的指針。less鏈表的首節(jié)點(diǎn)指針設(shè)定為lessHead,尾節(jié)點(diǎn)指針設(shè)定為lessTail;more鏈表的首節(jié)點(diǎn)指針設(shè)定為 moreHead,尾節(jié)點(diǎn)指針設(shè)定為moreTail。當(dāng)前正在遍歷的節(jié)點(diǎn)指針設(shè)定為current。當(dāng)單向鏈表遍歷結(jié)束后,亦即完成了一趟劃分, 如此遞歸進(jìn)行,便可完成整個(gè)單向鏈表的排序。除此之外,為了簡(jiǎn)化將 less和more單向鏈表鏈接到樞軸節(jié)點(diǎn)前、后部的過程,還需設(shè)定兩個(gè)指向單向鏈表尾節(jié)點(diǎn)的指針 lessTail和moreTail。在遞歸過程中,得到的單鏈表的長度會(huì)依次減小,直到長度減小到一的時(shí)候即為遞歸出口。

算法主要步驟

步驟1:算法接收兩個(gè)指針,其中l(wèi)istHead指 向單向鏈表首節(jié)點(diǎn),listTail為空指針,劃分過程中,listTail將指向單向鏈表的尾節(jié)點(diǎn),劃分后用于鏈接less單向鏈表到樞軸節(jié)點(diǎn)前。
步驟2:如果單向鏈表listHead僅有一個(gè)節(jié)點(diǎn),則說明已有序,本層遞歸結(jié)束,返回listHead。
步驟3:令lessHead、lessTail、moreHead和 moreTail為空,令current為listHead的next域,即單向鏈表的第二個(gè)節(jié)點(diǎn)。
步驟4:如果current節(jié)點(diǎn)為空,則轉(zhuǎn)入步驟13。
步驟5:如果current節(jié)點(diǎn)的key小于樞軸節(jié)點(diǎn)(即listHead)的key,則current節(jié)點(diǎn)應(yīng)鏈接到 less單向鏈表,轉(zhuǎn)入步驟6;否則,current節(jié)點(diǎn)應(yīng)鏈 接到more單向鏈表,轉(zhuǎn)入步驟9。
步驟6:修改lessTail指針使其指向current 節(jié)點(diǎn)。如果lessHead為空,則轉(zhuǎn)入步驟7;否則轉(zhuǎn)入步驟8。
步驟7:將less節(jié)點(diǎn)鏈接為單鏈表的首節(jié)點(diǎn)。
步驟8:將current節(jié)點(diǎn)鏈接為less單鏈表的尾結(jié)點(diǎn);
步驟9:修改moreTail指針使其指向current 節(jié)點(diǎn)。如果moreHead為空,則轉(zhuǎn)入步驟10;否則轉(zhuǎn)入步驟11。
步驟10:將currnet節(jié)點(diǎn)鏈接為more單向鏈表的首節(jié)點(diǎn)。
步驟11:將currnet節(jié)點(diǎn)鏈接為more單向鏈表的尾節(jié)點(diǎn)。
步驟12:將current節(jié)點(diǎn)移動(dòng)到單向鏈表的下一個(gè)節(jié)點(diǎn)。
步驟13:如果more單向鏈表不為空,則轉(zhuǎn)入步驟14;否則轉(zhuǎn)入步驟18。
步驟14:標(biāo)記more單向鏈表的結(jié)束位置,即 置moreTail的next域?yàn)榭铡?br />步驟15:遞歸調(diào)用本算法,繼續(xù)劃分more單 向鏈表,傳人moreHead和moreTail。步驟16將經(jīng)過遞歸排序的more單向鏈表 鏈接到樞軸節(jié)點(diǎn)后。
步驟17:修改listTail指針使其指向more— Tail,以便本層遞歸結(jié)束后供上層遞歸過程使用。
步驟18:由于more單向鏈表為空,則樞軸節(jié) 點(diǎn)便是尾節(jié)點(diǎn),即置listHead的next域?yàn)榭铡?步驟19:修改listTail指針使其指向listHead。
步驟20:如果less單向鏈表不為空,則轉(zhuǎn)入 步驟21;否則轉(zhuǎn)入步驟24。
步驟21:標(biāo)記less單向鏈表的結(jié)束位置,即 置lessTail的next域?yàn)榭铡?br />步驟22:遞歸調(diào)用本算法,繼續(xù)劃分less單 向鏈表,傳人lessHead和lessTail。 步驟23將經(jīng)過遞歸排序的less單向鏈表鏈 接到樞軸節(jié)點(diǎn)前。
步驟24:由于less單向鏈表為空,則樞軸節(jié) 點(diǎn)便是首節(jié)點(diǎn),即置lessHead為listHead。
步驟25:本層遞歸結(jié)束,返回lessHead。
示意圖如下:

在這里插入圖片描述

在這里插入圖片描述

在這里插入圖片描述

快速排序算法實(shí)現(xiàn)

Linklist Quicksort(Linklist *listHead, Linklist *listTail)
{
	Lnode *current;
	Lnode* lessHead = NULL, *lessTail = NULL, *moreHead = NULL, *moreTail = NULL;
	current = (*listHead)->next;//每次取首節(jié)點(diǎn)為樞紐,current指向第二個(gè)節(jié)點(diǎn)用于遍歷
	if ((*listHead)->next != NULL)//當(dāng)鏈表節(jié)點(diǎn)數(shù)不為1時(shí)(說明鏈表未排好序)
	{
		for (current = (*listHead)->next; current; current = current->next)
		{
			if (current->key < (*listHead)->key)
			{
				if (lessHead == NULL)
					lessHead = current;
				else
					lessTail->next = current;
				lessTail = current;
			}//current結(jié)點(diǎn)key小于樞紐key時(shí)放入less鏈表
			else
			{
				if (moreHead == NULL)
					moreHead = current;
				else
					moreTail->next = current;
				moreTail = current;
			}//current結(jié)點(diǎn)key大于樞紐key時(shí)放入more鏈表
		}
		//根據(jù)樞紐結(jié)點(diǎn)將T鏈表分為less和more兩個(gè)鏈表
		if (moreTail)
			moreTail->next = NULL;
		if (lessTail)
			lessTail->next = NULL;
		//將more鏈表尾結(jié)點(diǎn)next域置空
		if (moreHead != NULL)
		{
			moreTail->next = NULL;
			Quicksort(&moreHead, &moreTail);
			(*listHead)->next = moreHead;
			*listTail = moreTail;
		}
		//若moreHead不空,則current為more鏈表的尾結(jié)點(diǎn),對(duì)more鏈表進(jìn)行遞歸處理,將more鏈表接在樞紐節(jié)點(diǎn)后
		else
		{
			(*listHead)->next = NULL;
			*listTail = *listHead;
		}
		//若moreHead為空,則只有l(wèi)ess鏈表(即結(jié)點(diǎn)key全小于樞紐),將樞紐結(jié)點(diǎn)接在less節(jié)點(diǎn)后
		if (lessHead != NULL)
		{
			lessTail->next = NULL;
			Quicksort(&lessHead, &lessTail);
			lessTail->next = *listHead;
			*listHead = lessHead;
		}
		//若lesseHead不空,對(duì)less鏈表進(jìn)行遞歸處理,再將樞紐節(jié)點(diǎn)接在less鏈表后
		else
		{
			lessHead = *listHead;
		}
		//若lesseHead為空,則樞紐結(jié)點(diǎn)作為首節(jié)點(diǎn)
		return lessHead;
	}
	else
		return *listHead;
}

整個(gè)程序源代碼

#include<stdio.h>
#include<malloc.h> 
typedef struct Lnode
{
	int key;
	struct Lnode* next;
}Lnode, *Linklist;
//鏈表結(jié)構(gòu)體類型
Linklist createList(Linklist L, int n)
{
	L = (Linklist)malloc(sizeof(Lnode));
	L->next = NULL;
	Lnode *p, *r;
	r = L;
	p = (Lnode*)malloc(sizeof(Lnode));
	scanf("%d", &r->key);
	for (int i = 1; i < n; i++)
	{
		p = (Lnode*)malloc(sizeof(Lnode));
		scanf("%d", &p->key);
		r->next = p;
		r = p;
	}
	r->next = NULL;
	return L;
}
//初始初始化及尾插法(正序)創(chuàng)建單鏈表
Linklist getTail(Linklist L)
{
	while (L->next)
		L = L->next;
	return L;
}
//得到尾指針
void Print(Linklist L)
{
	Lnode *p;
	p = L;
	while (p)
	{
		printf("%d ", p->key);
		p = p->next;
	}
}
//遍歷單鏈表
Linklist Quicksort(Linklist *listHead, Linklist *listTail)
{
	Lnode *current;
	Lnode* lessHead = NULL, *lessTail = NULL, *moreHead = NULL, *moreTail = NULL;
	current = (*listHead)->next;//每次取首節(jié)點(diǎn)為樞紐,current指向第二個(gè)節(jié)點(diǎn)用于遍歷
	if ((*listHead)->next != NULL)//當(dāng)鏈表節(jié)點(diǎn)數(shù)不為1時(shí)(說明鏈表未排好序)
	{
		for (current = (*listHead)->next; current; current = current->next)
		{
			if (current->key < (*listHead)->key)
			{
				if (lessHead == NULL)
					lessHead = current;
				else
					lessTail->next = current;
				lessTail = current;
			}//current結(jié)點(diǎn)key小于樞紐key時(shí)放入less鏈表
			else
			{
				if (moreHead == NULL)
					moreHead = current;
				else
					moreTail->next = current;
				moreTail = current;
			}//current結(jié)點(diǎn)key大于樞紐key時(shí)放入more鏈表
		}
		//根據(jù)樞紐結(jié)點(diǎn)將T鏈表分為less和more兩個(gè)鏈表
		if (moreTail)
			moreTail->next = NULL;
		if (lessTail)
			lessTail->next = NULL;
		//將more鏈表尾結(jié)點(diǎn)next域置空
		if (moreHead != NULL)
		{
			moreTail->next = NULL;
			Quicksort(&moreHead, &moreTail);
			(*listHead)->next = moreHead;
			*listTail = moreTail;
		}
		//若moreHead不空,則current為more鏈表的尾結(jié)點(diǎn),對(duì)more鏈表進(jìn)行遞歸處理,將more鏈表接在樞紐節(jié)點(diǎn)后
		else
		{
			(*listHead)->next = NULL;
			*listTail = *listHead;
		}
		//若moreHead為空,則只有l(wèi)ess鏈表(即結(jié)點(diǎn)key全小于樞紐),將樞紐結(jié)點(diǎn)接在less節(jié)點(diǎn)后
		if (lessHead != NULL)
		{
			lessTail->next = NULL;
			Quicksort(&lessHead, &lessTail);
			lessTail->next = *listHead;
			*listHead = lessHead;
		}
		//若lesseHead不空,對(duì)less鏈表進(jìn)行遞歸處理,再將樞紐節(jié)點(diǎn)接在less鏈表后
		else
		{
			lessHead = *listHead;
		}
		//若lesseHead為空,則樞紐結(jié)點(diǎn)作為首節(jié)點(diǎn)
		return lessHead;
	}
	else
		return *listHead;
}
int main()
{
	Lnode* L = NULL;
	int n;
	printf("請(qǐng)輸入元素個(gè)數(shù)\n");
	scanf("%d", &n);
	printf("請(qǐng)輸入元素\n");
	L = createList(L, n);
	Lnode* listTail;
	listTail = getTail(L);
	Quicksort(&L, &listTail);
	printf("排序后元素序列為\n");
	Print(L);
	return 0;
}

整個(gè)程序已在Visual Studio 2017上運(yùn)行通過

測(cè)試案例

(1)一般數(shù)據(jù)樣例

在這里插入圖片描述

(2)只有一個(gè)數(shù)據(jù)時(shí)

在這里插入圖片描述

(2)有重復(fù)數(shù)據(jù)時(shí)

在這里插入圖片描述

總結(jié)

到此這篇關(guān)于C語言實(shí)現(xiàn)單鏈表的快速排序算法的文章就介紹到這了,更多相關(guān)C語言快速排序算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • C++ std::map幾種遍歷方式(正序倒序)

    C++ std::map幾種遍歷方式(正序倒序)

    這篇文章主要介紹了C++ std::map幾種遍歷方式,包含正序遍歷和倒序遍歷,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2024-02-02
  • C++回溯法實(shí)例分析

    C++回溯法實(shí)例分析

    這篇文章主要介紹了C++回溯法,實(shí)例講述了回溯法的原理與實(shí)現(xiàn)方法,最后給出了回溯法解決八皇后的實(shí)例,需要的朋友可以參考下
    2014-09-09
  • c++指針參數(shù)傳遞和引用參數(shù)傳遞的區(qū)別解析

    c++指針參數(shù)傳遞和引用參數(shù)傳遞的區(qū)別解析

    這篇文章主要介紹了c++指針參數(shù)傳遞和引用參數(shù)傳遞的區(qū)別解析,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2023-07-07
  • C語言實(shí)現(xiàn)五子棋游戲

    C語言實(shí)現(xiàn)五子棋游戲

    這篇文章主要為大家詳細(xì)介紹了C語言五子棋游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2020-02-02
  • C++空類及沒有成員變量的類的大小實(shí)例分析

    C++空類及沒有成員變量的類的大小實(shí)例分析

    這篇文章主要介紹了C++空類及沒有成員變量的類的大小,對(duì)于初學(xué)者更好的了解C++的指針及類的存儲(chǔ)結(jié)構(gòu)很有幫助,需要的朋友可以參考下
    2014-07-07
  • C++語言 STL容器list總結(jié)

    C++語言 STL容器list總結(jié)

    這篇文章主要介紹了C++語言 STL容器list總結(jié)的相關(guān)資料,需要的朋友可以參考下
    2016-10-10
  • C++解析wav文件方法介紹

    C++解析wav文件方法介紹

    最近將項(xiàng)目改為跨平臺(tái),于是音頻模塊從微軟的XAudio2改用OpenAL庫。之前使用MSDN的代碼,所以現(xiàn)在改為了C++標(biāo)準(zhǔn)的寫法,適用性更廣
    2022-09-09
  • 關(guān)于統(tǒng)計(jì)數(shù)字問題的算法

    關(guān)于統(tǒng)計(jì)數(shù)字問題的算法

    本文介紹了統(tǒng)計(jì)數(shù)字問題的算法,計(jì)算出書的全部頁碼中分別用到多少次數(shù)字0,1,2,3,.....9,并有每一步的解題思路,需要的朋友可以參考下
    2015-08-08
  • c++ using定義類型別名的具體使用

    c++ using定義類型別名的具體使用

    本文主要介紹了c++ using定義類型別名的具體使用,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2023-08-08
  • C語言關(guān)于自定義數(shù)據(jù)類型之枚舉和聯(lián)合體詳解

    C語言關(guān)于自定義數(shù)據(jù)類型之枚舉和聯(lián)合體詳解

    枚舉顧名思義就是把所有的可能性列舉出來,像一個(gè)星期分為七天我們就可以使用枚舉,聯(lián)合體是由關(guān)鍵字union和標(biāo)簽定義的,和枚舉是一樣的定義方式,不一樣的是,一個(gè)聯(lián)合體只有一塊內(nèi)存空間,什么意思呢,就相當(dāng)于只開辟最大的變量的內(nèi)存,其他的變量都在那個(gè)變量占據(jù)空間
    2021-11-11

最新評(píng)論