緒論

什么是數(shù)據(jù)結(jié)構(gòu)？

不同于計(jì)算機(jī)操作培訓(xùn)，注意與程序設(shè)計(jì)的區(qū)別。

Example 1

求n個(gè)數(shù)的最大值、次最大值。

//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;
}

遍歷方法共需進(jìn)行 n − 1 + n − 2 = 2 n − 3 n-1+n-2=2n-3 n−1+n−2=2n−3次比較。

變題

有n個(gè)足球隊(duì)比賽，問至少多少次比賽才能找到冠軍和亞軍。

解：
實(shí)際中通常采用錦標(biāo)賽方法。（淘汰制）
設(shè)有8個(gè)數(shù)分別為5，7，3，6，8，9，4，2
兩兩為一組進(jìn)行比較，大的勝出，小的淘汰。

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

共進(jìn)行了 8 / 2 + 4 / 2 + 2 / 2 = 7 8/2+4/2+2/2=7 8/2+4/2+2/2=7次比較。

故變題尋找冠軍的比較次數(shù)為 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

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

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

2.故變題尋找亞軍的比較次數(shù)為 l o g 2 n − 1 log_2{n}-1 log2​n−1

錦標(biāo)賽方法共需 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程序編寫出來。

討論

​ 處理一般實(shí)際工程問題的方法。

• 找出解決方案。
• 找出最優(yōu)解。（最節(jié)省資源：CPU和內(nèi)存）

Example 2

判斷表達(dá)式中括號(hào)是否匹配

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");
}

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

Example 3

交叉路口交通管理系統(tǒng)

• 把可以走通的道路設(shè)為頂點(diǎn)
• 如果兩個(gè)頂點(diǎn)有沖突，用頂點(diǎn)之間的連線表示

變題 著色算法

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

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

Example 4

如何快速走出迷宮？

以上問題現(xiàn)階段并不作要求，目的是向大家介紹下數(shù)據(jù)結(jié)構(gòu)的研究問題。

現(xiàn)在我們是否能回答出剛開始時(shí)問大家的問題呢？數(shù)據(jù)結(jié)構(gòu)是什么？

數(shù)據(jù)結(jié)構(gòu)是研究的是非數(shù)值計(jì)算的程序設(shè)計(jì)方法。

總結(jié)

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