緒論

什么是數據結構？

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

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=log2​n

2.故變題尋找亞軍的比較次數為 l o g 2 n − 1 log_2{n}-1 log2​n−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+log2​n−1=n+log2​n−2次比較。

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

討論

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

• 找出解決方案。
• 找出最優(yōu)解。（最節(jié)省資源：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

交叉路口交通管理系統

• 把可以走通的道路設為頂點
• 如果兩個頂點有沖突，用頂點之間的連線表示

變題 著色算法

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

在狀態(tài)圖中至少需要多少種顏色來表示？

Example 4

如何快速走出迷宮？

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

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

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

總結

本篇文章就到這里了，希望能給你帶來幫助，也希望您能夠多多關注腳本之家的更多內容！

最新評論