一篇文章帶你入門C語(yǔ)言數(shù)據(jù)結(jié)構(gòu):緒論

更新時(shí)間：2021年08月03日 15:18:46 作者：AKA你的閨蜜

這篇文章主要介紹了C語(yǔ)言的數(shù)據(jù)解構(gòu)基礎(chǔ)，希望對(duì)廣大的程序愛(ài)好者有所幫助，同時(shí)祝大家有一個(gè)好成績(jī),需要的朋友可以參考下，希望能給你帶來(lái)幫助

緒論

什么是數(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ì)比賽，問(wèn)至少多少次比賽才能找到冠軍和亞軍。

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

錦標(biāo)賽1

毋庸置疑的是，無(wú)論怎么分組，顯然最大值永遠(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

錦標(biāo)賽2

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

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

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

課后思考：將該模型用C程序編寫(xiě)出來(lái)。

討論

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

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

計(jì)算機(jī)模型

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ù)是否相等來(lái)判斷括號(hào)是否匹配，很容易就可以舉出反例 f = ) a + b ( f=)a+b( f=)a+b( ，所有該方法是不成熟的。