一篇文章帶你入門C語言數(shù)據(jù)結構:緒論

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

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

緒論

什么是數(shù)據(jù)結構？

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

Example 1

求n個數(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;
}

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

變題

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

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

錦標賽1

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

共進行了 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

錦標賽2

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

就是如圖所示帶*的數(shù)字，個數(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

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

討論

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

找出解決方案。
找出最優(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");
}

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