C語言數據結構與算法之鏈表(二)

Posted on by

引入

在上一節的學習中我們介紹瞭C語言如何實現鏈表，但是，在這一章，我們將拋開令人頭禿的指針和結構體，我們將另外使用一種數組來實現的方式，叫做模擬鏈表。讓我們一起來看看。

模擬鏈表介紹

鏈表中的每一個結點都隻有兩個部分。

我們可以使用一個數組date來儲存每序列中的每一個數。那每一個數右邊的數是誰，這一點該如何解決呢？在上一章的內容中我們是使用指針來解決的，這裡我們隻需再用一個數組right來存放序列中每一個數右邊的數是誰就可以瞭。具體要怎麼做呢？

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

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

現在需要在8面前插入一個6，隻需將6直接存在數組date的末尾即date【10】 = 6.

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

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

插入代碼實現

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

代碼實現  

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

到此這篇關於C語言數據結構與算法之鏈表(二)的文章就介紹到這瞭,更多相關C語言數據結構 鏈表內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：