第1章 c程式設計
程式設計＝資料描述＋演算法設計，即程式＝資料結構＋演算法。用計算機去解決問題過程：首先用資料結構的知識表示出問題，然後設計出解決問題的演算法，最後寫出程式在計算機上執行輸出問題解決的結果。
本章我們將對c的主要知識作回顧，為學習資料結構奠定基礎。
1.1 表示式
算術運算：5/3 值為1，2.5/5 值為0.5,10%3 值為1，'a'+1 值為66
賦值運算：a=3+5 a值為8，式值為8。b=a=3+5 a,b值均為8，式值為8。
a+=3 即a=a+3; a-=3; a*=3; a/=3;a%=3.i++ ,++i,即i=i+1;i...,...
i.區別：x=i++;與x=++i;
關係運算：3==2，式值為0，3！=2，式值為1。
邏輯運算：01,!(x<0). 注：「非零」為1。
條件運算：b>=0?a+b:a-b,即a+︱b︱
逗號運算: a=6,a*3,a+3 式值為9
1.2 函式與引數
1.2.1傳值引數
例1.1 輸入四個數，輸出其中的最大數。
int max(int x,int yx,y是形參*/
main()
1.2.1傳址引數
例1.2輸入二個數到變數a與b，交換變數a與b的值後輸出。
swap(int *x,int *yx,y為傳址引數*/
main()
例1.3 輸入n個數，公升序排列後輸出。
sort(int a,int n) /*陣列名作為引數，為位址引數*/
}main()
1.2.3 遞迴函式
例1.4 計算n!
遞迴函式f (n) 的乙個遞迴定義（假定是直接遞迴）必須滿足如下條件：
包含乙個基本部分，其中對於n 的乙個或多個值，f (n)必須是直接定義的（即非遞迴）。如本例中f(1)=1。
遞迴部分，右側所出現的所有f 的引數都必須有乙個比n 小，以便重複運用遞迴部分來改變右側出現的f ，直至出現f 的基本部分。
long f(int n)
main()
例1.5 計算fibonacci序列：
int fib(int n)
main()
例1.6．hanoi tower問題：
1. 有三根桿子a,b,c。a桿上有n只碟子
2. 每次移動乙隻碟子,小的只能疊在大的上面
3. 把所有碟子從a桿經c杆全部移到b桿上.
遞迴求解：
基本部分：若n=1，只有1只碟子，直接將它從a杆移到b杆；
遞迴部分：若n>1，上面n-1只碟子從a桿經b杆移動到c杆，將a桿上第n只碟子移到b杆；然後再將n-1只碟子從c桿經a杆移到b杆。
han(int n,char a,char b,char c)
}main()
例1.7 [排列] 通常我們希望檢查n 個不同元素的所有排列方式以確定乙個最佳的排列。比如，a，b 和c 的排列方式有：
abc, acb, bac, bca, cab 和cba。n 個元素的排列方式共有n！種。
輸出n個不同元素的所有排列。
由於採用非遞迴的c函式來輸出n個元素的所有排列很困難，可以開發乙個遞迴函式來實現。令e=表示n 個元素的集合，ei為e中移去元素e i 以後所獲得的集合，p(x) 表示集合x 的全部排列，ei.p(x)表示在p(x) 中的每個排列的前面均加上ei 所得排列。
例如，如果e= ，那麼e1= ，p(e1 ) = ( b c, c b)，e1 .p(e1) = (a b c, a c b)。
當n=3並且e=（a,b,c）時，按照前面的遞迴定義可得p(e) =a.p() +b.p()+c.
p()=ab.p()+ac.p()+ba.
p()+bc.p()+ca.p()+cb.
p()=(abc,acb,bac,bca,cab,cba)。
注意a.p()實際上包含兩個排列方式：abc 和acb，a 是它們的字首，p()是它們的字尾。同樣地，ac.p()表示字首為ac、字尾為p()的排列。
設函式p(list,k,m)表示字首為list[0]...list[k-1],字尾為list [k]...list[m] 的排列。
呼叫p(list,0,n-1)得到list[0]…list[n-1]的所有n!個排列。當k=m時，僅有乙個字尾list[m]，因此list[0]…list[m] 即是所要產生的輸出。
當kperm(int a,int s,int e)
else
for(i=s;i<=e;i++)
}main()
1.3簡單演算法
1、分離數字
例1.8.尋找滿足下列條件的數n：（1）n是不超過７位的平方數，（2）n是回文數。所謂回文數是指這樣的數，它的各位數碼是左右對稱的。例如1，121、676、94249
2、累加,記數。
例1.9.輸入一組非零整數,以0作為結束標記.輸出這組數的平均值及其中正整數與負整數的個數.
3、遞推和迭代。
遞推:前項（後項）推出後項（前項）。迭代：舊值推出新值。
例1.10.已知fibonacci序列的前兩項是1,1.輸出項值不大於100的fibonacci序列.
例1.11.將乙個十進位制數轉換為乙個二進位制數。
4、找出最大數和最小數。
例1.11. 找n個整數中的最大數.
例1.12. 找n個整數中的最大數和次大數.
5、高精度計算：
例1.12.計算n! (n<=100)
（unsigned long:0～4294967295, 13!=6227020800,100!為158位）
（1）將被乘數按數字存放在陣列a中從0單元到k單元，乘數存放在變數n中；
（2）n與a的每一數字作豎式乘法，乘積按數字存放在陣列a中；
int mul(int a,int k,int n)
for(;c>0;i++) /*將最後的進製按數字分離存放*/
return i-1;
}main()
6、窮舉搜尋法
窮舉法也叫列舉法,它的基本思想是依題目的部分條件確定答案的大致範圍,在此範圍內對所有可能的情況逐一驗證,直到全部情況驗證完。若某個情況經驗證符合題目的全部條件,則為本題的乙個答案。若全部情況經驗證後都不符合題目的全部條件,則本題無答案。
用窮舉法解題時，答案所在的範圍總是要求是有限的，怎樣才能使我們不重複的、乙個不漏、乙個不增的逐個列舉答案所在範圍的所有情況，就是本節所講的「列舉方法」。列舉方法按答案的資料型別,常用的有下面三種：
順序列舉：順序列舉是指答案範圍內的各種情況很容易與自然數對應甚至就是自然數,可以按自然數的變化順序去列舉。
《資料結構》實驗講義
精品文件！歡迎 大家 閱讀！實驗三順序棧的基本操作 實驗目的 1 熟悉將演算法轉換成程式 的過程。2 了解單順序棧的邏輯結構特性，熟練掌握順序棧儲存結構的c 語言描述方法。3 熟練掌握順序棧的基本操作 入棧 出棧等，掌握順序棧的訪問特性。實驗內容 1 分別建立包含6個資料元素的單鏈表 2 從鍵盤輸入...
new資料結構複習題
一 填空 資料結構按物理結構可分為線性結構和集合。在單鏈表中，要刪除某一指定的結點，必須先找到該結點的 結點。對於乙個具有n個結點的單鏈表，在 p結點後插入乙個新結點的時間複雜度是 在給定值x的結點後插入乙個新結點的時間複雜度是 性結構 樹形結構和圖形結構中，直接前驅和直接後繼結點之間分別存在著 1...
資料結構講義 嚴蔚敏版
第0章複習提示 1 一 教材內容 1 二 複習提示 1 1.經典演算法 1 2.緒論 1 3.線性表 2 4.棧和佇列 2 5.串 2 6.樹和二叉樹 2 7.圖 3 8.查詢表 3 9.內部排序 3 第1章緒論 5 一 基礎知識 5 二 演算法 5 三 習題 6 第2章線性表 7 一 基礎知識和演...