C語言數(shù)據(jù)結(jié)構(gòu)與算法之鏈表(二)

更新時間：2021年12月13日 14:24:41 作者：玄澈_

在這篇文章中，我們將拋開令人頭禿的指針和結(jié)構(gòu)體，我們將另外使用一種數(shù)組來實現(xiàn)的方式，叫做模擬鏈表。讓來跟隨小編一起學(xué)習(xí)學(xué)習(xí)吧

引入

在上一節(jié)的學(xué)習(xí)中我們介紹了C語言如何實現(xiàn)鏈表，但是，在這一章，我們將拋開令人頭禿的指針和結(jié)構(gòu)體，我們將另外使用一種數(shù)組來實現(xiàn)的方式，叫做模擬鏈表。讓我們一起來看看。

模擬鏈表介紹

鏈表中的每一個結(jié)點都只有兩個部分。

我們可以使用一個數(shù)組date來儲存每序列中的每一個數(shù)。那每一個數(shù)右邊的數(shù)是誰，這一點該如何解決呢？在上一章的內(nèi)容中我們是使用指針來解決的，這里我們只需再用一個數(shù)組right來存放序列中每一個數(shù)右邊的數(shù)是誰就可以了。具體要怎么做呢？

上面的兩個數(shù)組中，第一個整型數(shù)組date是用來存放序列中的具體數(shù)字的，另外一個整型數(shù)組right是用來存放當前序列中每一個元素右邊的元素在數(shù)組date中位置的。

例如right【1】的值為2，就表示當前序列中1號元素右邊的元素存放在date【2】中；如果是0，例如right【9】的值為0，就表示當前序列中9號元素的右邊沒有元素。

現(xiàn)在需要在8面前插入一個6，只需將6直接存在數(shù)組date的末尾即date【10】 = 6.

接下來只需要將right【3】改為10，表明新序列中3號元素右邊的元素存放在date【10】中。再將right【10】的值改為4，表示新序列中10號元素右邊的元素存放在date【4】中。

這樣我們通過right數(shù)組就可以從頭到尾遍歷整個序列了（序列的每個元素的值存放在對應(yīng)的數(shù)組date中），如下

插入代碼實現(xiàn)

	//從鏈表的頭部開始遍歷
	t = 1;
	while(t != 0)
	{
		//如果當前結(jié)點下一個結(jié)點的值大于待插入數(shù)，將數(shù)插到中間
		if(date[right[t]] > date[len])
		{
			right[len] = right[t];   //新插入的數(shù)的下一個結(jié)點標號等于當前結(jié)點的下一個標號
			right[t] = len;			 //當前結(jié)點的下一個結(jié)點編號就是新插入數(shù)的編號
			break;					 //插入完成跳出循環(huán)
		}
		t = right[t];
	}

代碼實現(xiàn)??

#include <stdio.h>
int main()
{
	int date[101],right[101];
	int i,n,t,len;
	//讀入已有的數(shù)
	scanf("%d",&n);
	for(i = 1;i <= n;i++)
		scanf("%d",&date[i]);
	len = n;
 
	//初始化數(shù)組right
	for(i = 1;i <= n;i++)
	{
		if(i != n)
			right[i] = i + 1;
		else
			right[i] = 0;
	}
 
	//直接在數(shù)組date的末尾加一個數(shù)
	len++;
	scanf("%d",&date[len]);
 
	//從鏈表的頭部開始遍歷
	t = 1;
	while(t != 0)
	{
		//如果當前結(jié)點下一個結(jié)點的值大于待插入數(shù)，將數(shù)插到中間
		if(date[right[t]] > date[len])
		{
			right[len] = right[t];   //新插入的數(shù)的下一個結(jié)點標號等于當前結(jié)點的下一個標號
			right[t] = len;			 //當前結(jié)點的下一個結(jié)點編號就是新插入數(shù)的編號
			break;					 //插入完成跳出循環(huán)
		}
		t = right[t];
	}
 
 
	//輸出鏈表中的所有數(shù)
	t = 1;
	while(t != 0)
	{
		printf("%d",date[t]);
		t = right[t];
	}
 
	return 0;
}

到此這篇關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)與算法之鏈表(二)的文章就介紹到這了,更多相關(guān)C語言數(shù)據(jù)結(jié)構(gòu) 鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: