C語言數據結構之緒論的示例分析

小編給大家分享一下C語言數據結構之緒論的示例分析，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

緒論

什么是數據結構？

不同于計算機操作培訓，注意與程序設計的區別。

Example 1

求n個數的最大值、次最大值。

//1.遍歷 - 最樸素的方法
int main()
{
	int arr[10] = { 22,334,552,1,4,6,78,23,55,98 };
	int i = 0;
	int temp = 0;
	int max1 = arr[0];
	int max2 = arr[1];
	for (i = 1; i < 10; i++)
	{
		if (arr[i] > max1)
		{
			temp = max1;
			max1 = arr[i];
			arr[i] = temp;
		}
	}
	printf("%d\n", max1);
	for (i = 2; i < 10; i++)
	{
		if (arr[i] > max2)
		{
			temp = max2;
			max2 = arr[i];			arr[i] = temp;
		}
	}
	printf("%d\n", max2); 
	return 0;
}

遍歷方法共需進行 n ? 1 + n ? 2 = 2 n ? 3 n-1+n-2=2n-3 n?1+n?2=2n?3次比較。

變題

有n個足球隊比賽，問至少多少次比賽才能找到冠軍和亞軍。

解：
實際中通常采用錦標賽方法。（淘汰制）
設有8個數分別為5，7，3，6，8，9，4，2
兩兩為一組進行比較，大的勝出，小的淘汰。

毋庸置疑的是，無論怎么分組，顯然最大值永遠不會被淘汰。故最大值為9。

共進行了 8 / 2 + 4 / 2 + 2 / 2 = 7 8/2+4/2+2/2=7 8/2+4/2+2/2=7次比較。

故變題尋找冠軍的比較次數為 n / 2 + n / 2 2 + … + n / 2 k = n ? 1 n/2+n/2^2+…+n/2^k=n-1 n/2+n/22+…+n/2k=n?1

次最大值肯定是被最大值給比下去了，不然它就是最大值了。所以順著這個思路，把所有和最大值進行過直接比較的數字跳出來，重新進行比較。

就是如圖所示帶*的數字，個數記為k，稍加思索則得出 k = l o g 2 n k=log_2{n} k=log2n

2.故變題尋找亞軍的比較次數為 l o g 2 n ? 1 log_2{n}-1 log2n?1

錦標賽方法共需 n ? 1 + l o g 2 n ? 1 = n + l o g 2 n ? 2 n-1+log_2{n}-1=n+log_2{n}-2 n?1+log2n?1=n+log2n?2次比較。

課后思考：將該模型用C程序編寫出來。

討論

處理一般實際工程問題的方法。

• 找出解決方案。

• 找出最優解。（最節省資源：CPU和內存）

Example 2

判斷表達式中括號是否匹配

Z = ( ( a + b ) + c ) ? 2 + ( 3 ? 5 ) / 7 ? ( ( 6 + 2 ) / 8 + a )

void match(char* ch)
{
	int count = 0;
	int i = 0; 
	while (ch[i]!= ';') 
	{
		if(ch[i] == '(')
			count++;
		else if (ch[i] ==')')
			count--; 
		i++;
	}
	if (count != 0)
		printf("%s\n","no match");
	else 
		printf("%s\n","match");
}

當然，上述代碼是由左向右數括號數是否相等來判斷括號是否匹配，很容易就可以舉出反例 f = ) a + b ( f=)a+b( f=)a+b( ，所有該方法是不成熟的。

Example 3

交叉路口交通管理系統

• 把可以走通的道路設為頂點

• 如果兩個頂點有沖突，用頂點之間的連線表示

變題 著色算法

在狀態圖中，相鄰（有連線）的頂點不能是同一種狀態。故對于頂點的不同狀態，我們用不同的顏色去表示。由于四色定理，多余5叉的路口不能用少于4種顏色來表示。

在狀態圖中至少需要多少種顏色來表示？

Example 4

如何快速走出迷宮？

以上問題現階段并不作要求，目的是向大家介紹下數據結構的研究問題。

現在我們是否能回答出剛開始時問大家的問題呢？數據結構是什么？

數據結構是研究的是非數值計算的程序設計方法。

以上是“C語言數據結構之緒論的示例分析”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！