數(shù)據(jù)結(jié)構(gòu)課程PPT第1章緒論

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)教材教材: : 數(shù)據(jù)結(jié)構(gòu)教程（第數(shù)據(jù)結(jié)構(gòu)教程（第4版）版） 李春葆等，李春葆等， 清華大學出版社清華大學出版社 2012年年 （另配套學習指導和上機指導兩書，作為參考）（另配套學習指導和上機指導兩書，作為參考）參考書參考書: : 1.1.數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C語言版）嚴蔚敏，吳偉民語言版）嚴蔚敏，吳偉民 清華大學出版社清華大學出版社 1997 2.數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅc數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC+描述）殷人昆等描述）殷人昆等 清華大學清華大學出版社出版社 1999C語言語言 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 軟件工程軟件工程掌握基本編掌握基本編程方法程方法掌握數(shù)據(jù)組掌握數(shù)據(jù)組織和數(shù)據(jù)處織

2、和數(shù)據(jù)處理的方法理的方法掌握大型軟掌握大型軟件開發(fā)方法件開發(fā)方法學習識字學習識字學習寫作文學習寫作文學習寫小說學習寫小說基本要求課程關(guān)系與語文學習過程類比動手能力（上機）前期課程前期課程數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)計算機基礎(chǔ)計算機基礎(chǔ)C語言語言離散數(shù)學離散數(shù)學后期課程后期課程操作系統(tǒng)操作系統(tǒng)編譯原理編譯原理數(shù)據(jù)庫原理數(shù)據(jù)庫原理軟件工程軟件工程承上承上啟下啟下計算機科學課程體系（偏軟）計算機科學課程體系（偏軟）學習和講授方法學習和講授方法l 演譯法演譯法先學習先學習/ /講授理論知識，用知識解決問題。講授理論知識，用知識解決問題。l 歸納法歸納法先解決具體問題，由此歸納出解決問題的理論知先解決具體問題，由此

3、歸納出解決問題的理論知識。識。只有歸納法才能產(chǎn)生新的知識！只有歸納法才能產(chǎn)生新的知識！編寫程序編寫程序1編寫程序編寫程序2編寫程序編寫程序n.具有編程的基本能力具有編程的基本能力用計算機求解問題的基本思路用計算機求解問題的基本思路講授課時：講授課時：72上機課時：上機課時：36評分方式：評分方式：平時：平時：10上機：上機：10，作業(yè)：作業(yè)：10期末考試：期末考試：70授課安排授課安排第第1章章 緒論緒論 1.2 算法及其描述算法及其描述 1.1 什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)1.3 算法分析算法分析 本章小結(jié)本章小結(jié)1.4 數(shù)據(jù)結(jié)構(gòu)算法程序數(shù)據(jù)結(jié)構(gòu)算法程序 數(shù)據(jù)：數(shù)據(jù)：是所有能被輸入到計算機中

4、是所有能被輸入到計算機中, ,且能被計算機處理的且能被計算機處理的符號的集合。它是計算機操作的對象的總稱符號的集合。它是計算機操作的對象的總稱, ,也是計算機也是計算機處理的信息的某種特定的符號表示形式。處理的信息的某種特定的符號表示形式。數(shù)據(jù)元素：數(shù)據(jù)元素：是數(shù)據(jù)是數(shù)據(jù)( (集合集合) )中的一個中的一個“個體個體”, ,是數(shù)據(jù)的基是數(shù)據(jù)的基本單位。本單位。 數(shù)據(jù)對象：數(shù)據(jù)對象：是具有相同性質(zhì)的若干個數(shù)據(jù)元素的集合。是具有相同性質(zhì)的若干個數(shù)據(jù)元素的集合。 1.1.1 數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)結(jié)構(gòu)的定義1.1 1.1 什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu) 例如，例如，200402班為一個學生數(shù)據(jù)對象，其中的

5、班為一個學生數(shù)據(jù)對象，其中的“張三張三”是一個數(shù)據(jù)元素。是一個數(shù)據(jù)元素。 數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)：是指數(shù)據(jù)以及數(shù)據(jù)元素相互之間的聯(lián)系。可以看是指數(shù)據(jù)以及數(shù)據(jù)元素相互之間的聯(lián)系。可以看作是相互之間存在著某種特定關(guān)系的數(shù)據(jù)元素的集合。作是相互之間存在著某種特定關(guān)系的數(shù)據(jù)元素的集合。 因此，可時把數(shù)據(jù)結(jié)構(gòu)看成是因此，可時把數(shù)據(jù)結(jié)構(gòu)看成是帶結(jié)構(gòu)帶結(jié)構(gòu)的的數(shù)據(jù)元素的集合數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)包括如下幾個方面：數(shù)據(jù)結(jié)構(gòu)包括如下幾個方面： 數(shù)據(jù)元素之間的邏輯關(guān)系，即數(shù)據(jù)的數(shù)據(jù)元素之間的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)。數(shù)據(jù)元素及其關(guān)系在計算機存儲器中的存儲方式，即數(shù)據(jù)元素及其關(guān)系在計算機存儲器中的存儲方式，

6、即數(shù)據(jù)的數(shù)據(jù)的存儲結(jié)構(gòu)存儲結(jié)構(gòu)，也稱為數(shù)據(jù)的，也稱為數(shù)據(jù)的物理結(jié)構(gòu)物理結(jié)構(gòu)。施加在該數(shù)據(jù)上的操作，即數(shù)據(jù)的施加在該數(shù)據(jù)上的操作，即數(shù)據(jù)的運算運算。 例例1.1 有一個學生表如表有一個學生表如表1.1所示。這個表中的數(shù)據(jù)元所示。這個表中的數(shù)據(jù)元素是學生記錄，每個數(shù)據(jù)元素由四個數(shù)據(jù)項（即學號、素是學生記錄，每個數(shù)據(jù)元素由四個數(shù)據(jù)項（即學號、姓別、性別和班號）組成。姓別、性別和班號）組成。邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)存儲結(jié)構(gòu)存儲結(jié)構(gòu)運算實現(xiàn)運算實現(xiàn)學號學號姓名姓名性別性別班號班號1張斌張斌男男99018劉麗劉麗女女990234李英李英女女990120陳華陳華男男990212王奇王奇男男990126董強董強男男9

7、9025王萍王萍女女9901表表1.1 學生表學生表 邏輯結(jié)構(gòu)表示邏輯結(jié)構(gòu)表示1（1）邏輯結(jié)構(gòu)）邏輯結(jié)構(gòu) 該表中的記錄順序反映了數(shù)據(jù)元素之間的邏輯關(guān)系該表中的記錄順序反映了數(shù)據(jù)元素之間的邏輯關(guān)系, ,為為線性線性關(guān)系關(guān)系。用學號標識每個學生記錄，這種邏輯關(guān)系可以表示為：。用學號標識每個學生記錄，這種邏輯關(guān)系可以表示為： , 其中尖括號其中尖括號“”表示元素表示元素ai和和ai+1之間是相鄰的，即之間是相鄰的，即ai在在ai+1之前，之前，ai+1在在ai之后。之后。邏輯結(jié)構(gòu)表示邏輯結(jié)構(gòu)表示2 數(shù)據(jù)在計算機存儲器中的存儲方式就是數(shù)據(jù)在計算機存儲器中的存儲方式就是存儲結(jié)構(gòu)存儲結(jié)構(gòu)。 邏輯結(jié)構(gòu)邏輯結(jié)

8、構(gòu)存儲結(jié)構(gòu)存儲結(jié)構(gòu)映射映射映射應滿足兩個條件：映射應滿足兩個條件： 存儲元素存儲元素 存儲關(guān)系存儲關(guān)系存放學生表的結(jié)構(gòu)體數(shù)組存放學生表的結(jié)構(gòu)體數(shù)組Stud定義為：定義為： struct int no; /存儲學號存儲學號 char name8; /存儲姓名存儲姓名 char sex2; /存儲性別存儲性別 char class4; /存儲班號存儲班號 Stud7=1,“張斌張斌”,“男男”,“9901”, 5,王萍王萍,女女,9901;C/C+語言中，通常采用結(jié)構(gòu)體數(shù)組和鏈表兩種方式實現(xiàn)語言中，通常采用結(jié)構(gòu)體數(shù)組和鏈表兩種方式實現(xiàn)其存儲結(jié)構(gòu)。其存儲結(jié)構(gòu)。（2）存儲結(jié)構(gòu)）存儲結(jié)構(gòu) 結(jié)構(gòu)體數(shù)組結(jié)構(gòu)

9、體數(shù)組Stud各元素在內(nèi)存中順序存放，即第各元素在內(nèi)存中順序存放，即第i（1i6）個學生對應的元素個學生對應的元素Studi存放在第存放在第i+1個學生對應的元素個學生對應的元素Studi+1之前，之前，Studi+1正好在正好在Studi之后。之后。9901女女王萍王萍59901男男張斌張斌1 1Stud0Stud6Stud數(shù)組起始地址數(shù)組起始地址存儲結(jié)構(gòu)表示存儲結(jié)構(gòu)表示1存放學生表的鏈表的節(jié)點類型存放學生表的鏈表的節(jié)點類型StudType聲明為：聲明為：typedef struct studnode int no; /存儲學號存儲學號 char name8; /存儲姓名存儲姓名 char

10、sex2; /存儲性別存儲性別 char class4; /存儲班號存儲班號 struct studnode *next;/存儲指向下一個學生的指針存儲指向下一個學生的指針 StudType；鏈表首節(jié)點地址鏈表首節(jié)點地址head1張斌張斌男男 99018劉麗劉麗女女 990234李英李英女女 990120陳華陳華男男 990212王奇王奇男男 990126董強董強男男 99025王萍王萍女女 9901 學生表構(gòu)成的鏈表如右學生表構(gòu)成的鏈表如右圖所示。其中的圖所示。其中的head為第為第一個數(shù)據(jù)元素的指針。一個數(shù)據(jù)元素的指針。 學生表構(gòu)成的鏈表學生表構(gòu)成的鏈表存儲結(jié)構(gòu)表示存儲結(jié)構(gòu)表示2對于對于“

11、學生表學生表”這種數(shù)據(jù)結(jié)構(gòu)，可以進行一系列的運算：這種數(shù)據(jù)結(jié)構(gòu)，可以進行一系列的運算：（3）運算實現(xiàn)）運算實現(xiàn)增加一個學生記錄；增加一個學生記錄；刪除一個學生記錄；刪除一個學生記錄；查找性別為查找性別為“女女”的學生記錄；的學生記錄；查找班號為查找班號為“9902”的學生記錄；的學生記錄； 例如，查找學號為例如，查找學號為20的學生的姓名：的學生的姓名： 對于對于Stud數(shù)組：從數(shù)組：從Stud0開始比較，開始比較，Stud0.no不等于不等于20，再與再與Stud1.no比較，比較，直到，直到Stud3.no等于等于20，返回，返回S。 9902男男陳華陳華209901男男

12、張斌張斌1Stud0Stud3i3運算的實現(xiàn)過程運算的實現(xiàn)過程1對于對于head為首節(jié)點指針的為首節(jié)點指針的鏈表：鏈表：從從p=head所指節(jié)點開始比較，所指節(jié)點開始比較，p- -no不等于不等于20，從它的，從它的next得得到下一個節(jié)點的地址，再與下到下一個節(jié)點的地址，再與下一個節(jié)點的一個節(jié)點的no域比較，域比較，直，直到某節(jié)點的到某節(jié)點的no域等于域等于20，返回，返回其其p- -name域。域。head1張斌張斌男男 99018劉麗劉麗女女 990234李英李英女女 990120陳華陳華男男 990212王奇王奇男男 990126董強董強男男 99025王萍王萍女女 9901p運算的實

13、現(xiàn)過程運算的實現(xiàn)過程2結(jié)論：結(jié)論： 同一邏輯結(jié)構(gòu)可以對應多種存儲結(jié)構(gòu)。同一邏輯結(jié)構(gòu)可以對應多種存儲結(jié)構(gòu)。 同樣的運算，在不同的存儲結(jié)構(gòu)中，其實現(xiàn)過程是不同同樣的運算，在不同的存儲結(jié)構(gòu)中，其實現(xiàn)過程是不同的。的。思考題：思考題：數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)有什么不同？數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)有什么不同？ 為了更確切地描述一種數(shù)據(jù)結(jié)構(gòu)，通常采用二元組表為了更確切地描述一種數(shù)據(jù)結(jié)構(gòu)，通常采用二元組表示：示： B=(D,R) 其中，其中，B是一種數(shù)據(jù)結(jié)構(gòu)，它由數(shù)據(jù)元素的集合是一種數(shù)據(jù)結(jié)構(gòu)，它由數(shù)據(jù)元素的集合D和和D上二元關(guān)系的集合上二元關(guān)系的集合R所組成。其中：所組成。其中： D=di| 1in,n0 R

14、=rj | 1jm,m0 邏輯結(jié)構(gòu)的描述或表示：邏輯結(jié)構(gòu)的描述或表示：一種通用的邏輯結(jié)構(gòu)表示方法一種通用的邏輯結(jié)構(gòu)表示方法di表示集合表示集合D中的第中的第i個節(jié)點或數(shù)據(jù)元素。個節(jié)點或數(shù)據(jù)元素。n為為D中節(jié)點的個數(shù)，特別地，若中節(jié)點的個數(shù)，特別地，若n=0，則，則D是一個空集，是一個空集，因而因而B也就無結(jié)構(gòu)可言，有時也可以認為它具有任一結(jié)構(gòu)。也就無結(jié)構(gòu)可言，有時也可以認為它具有任一結(jié)構(gòu)。rj表示集合表示集合R中的第中的第j個關(guān)系，每個關(guān)系用序偶表示。個關(guān)系，每個關(guān)系用序偶表示。m為為R中關(guān)系的個數(shù)中關(guān)系的個數(shù),特別地，若特別地，若m=0，則，則R是一個空集，是一個空集，表明集合表明集合D中的

15、元素間不存在任何關(guān)系，彼此是獨立的。中的元素間不存在任何關(guān)系，彼此是獨立的。其中：其中：序偶序偶（x,yD） x為第一元素，為第一元素，y為第二元素。為第二元素。x為為y的的前驅(qū)元素前驅(qū)元素。y為為x的的后繼元素后繼元素。若某個節(jié)點沒有前驅(qū)元素，則稱該節(jié)點為若某個節(jié)點沒有前驅(qū)元素，則稱該節(jié)點為開始元素開始元素；若某個節(jié)點沒有后繼元素，則稱該節(jié)點為若某個節(jié)點沒有后繼元素，則稱該節(jié)點為終端元素終端元素。 說明：說明：表示有向關(guān)系，表示有向關(guān)系，(x,y)表示無向關(guān)系。表示無向關(guān)系。采用離散數(shù)學的表示方法。采用離散數(shù)學的表示方法。每個關(guān)系的用序偶表示：每個關(guān)系的用序偶表示：區(qū)號區(qū)號城市名城市名說明說

16、明010Beijing首都首都021Shanghai直轄市直轄市027Wuhan湖北省省會湖北省省會029Xian陜西省省會陜西省省會025Nanjing江蘇省省會江蘇省省會City=(D,R)D=010,021,027,029,025R=rr=,區(qū)號為關(guān)鍵字區(qū)號為關(guān)鍵字例如，有一個如下表所示的城市表，假設(shè)城市名是唯一的，例如，有一個如下表所示的城市表，假設(shè)城市名是唯一的，給出其邏輯結(jié)構(gòu)的二元組表示。給出其邏輯結(jié)構(gòu)的二元組表示。城市表城市表City中共有中共有5個記錄，其邏輯結(jié)構(gòu)的二元組表示如下：個記錄，其邏輯結(jié)構(gòu)的二元組表示如下：又例如，有如下數(shù)據(jù)即一個矩陣：又例如，有如下數(shù)據(jù)即一個矩陣：

17、119105471281362 對應的二元組表示為對應的二元組表示為B=(D,R)，其中：，其中： D=2,6,3,1,8,12,7,4,5,10,9,11 R=r1,r2 其中，其中，r1表示行關(guān)系，表示行關(guān)系，r2表示列關(guān)系表示列關(guān)系 r1=, , r2=, , 一個二維數(shù)組一個二維數(shù)組 可以可以利用圖形形象地表示邏輯結(jié)構(gòu)利用圖形形象地表示邏輯結(jié)構(gòu)。 例如，上述例如，上述“學生表學生表”數(shù)據(jù)結(jié)構(gòu)用下圖的圖形表示。數(shù)據(jù)結(jié)構(gòu)用下圖的圖形表示。學生表數(shù)據(jù)結(jié)構(gòu)圖示學生表數(shù)據(jù)結(jié)構(gòu)圖（1）線性結(jié)構(gòu)）線性結(jié)構(gòu) 節(jié)點之間關(guān)系：一對一。節(jié)點之間關(guān)系：一對一。 特點：特點：開始節(jié)點和

18、終端節(jié)點都是唯一的開始節(jié)點和終端節(jié)點都是唯一的, ,除了開始節(jié)點和終除了開始節(jié)點和終端節(jié)點以外端節(jié)點以外, ,其余節(jié)點都有且僅有一個前驅(qū)節(jié)點其余節(jié)點都有且僅有一個前驅(qū)節(jié)點, ,有且僅有一個有且僅有一個后繼節(jié)點。線性表就是典型的線性結(jié)構(gòu)。后繼節(jié)點。線性表就是典型的線性結(jié)構(gòu)。1.1.2 邏輯結(jié)構(gòu)類型邏輯結(jié)構(gòu)類型 （2）樹形結(jié)構(gòu)）樹形結(jié)構(gòu) 節(jié)點之間關(guān)系：一對多。節(jié)點之間關(guān)系：一對多。 特點：特點：開始節(jié)點唯一，終端節(jié)點不唯一。除終端節(jié)開始節(jié)點唯一，終端節(jié)點不唯一。除終端節(jié)點以外，每個節(jié)點有一個或多個后續(xù)節(jié)點；除開始節(jié)點以外，每個節(jié)點有一個或多個后續(xù)節(jié)點；除開始節(jié)點外，每個節(jié)點有且僅有一個前驅(qū)節(jié)點。點

19、外，每個節(jié)點有且僅有一個前驅(qū)節(jié)點。 （3）圖形結(jié)構(gòu)）圖形結(jié)構(gòu) 節(jié)點之間關(guān)系：多對多。節(jié)點之間關(guān)系：多對多。 特點：特點：沒有開始節(jié)點和終端節(jié)點，所有節(jié)點都可沒有開始節(jié)點和終端節(jié)點，所有節(jié)點都可能有多個前驅(qū)節(jié)點和多個后繼節(jié)點。能有多個前驅(qū)節(jié)點和多個后繼節(jié)點。1.1.3 存儲結(jié)構(gòu)類型存儲結(jié)構(gòu)類型（2）鏈式存儲方法）鏈式存儲方法 （3）索引存儲方法）索引存儲方法 （4） 散列（哈希）存儲方法散列（哈希）存儲方法 （1）順序存儲方法）順序存儲方法 前面通過示例已介紹前面通過示例已介紹第第9 9章介紹章介紹 （1）數(shù)據(jù)類型）數(shù)據(jù)類型 高級程序語言中高級程序語言中,一般須對程序中出現(xiàn)的每個變量、常量或一般

20、須對程序中出現(xiàn)的每個變量、常量或表達式表達式,明確說明它們所屬的數(shù)據(jù)類型。不同類型的變量明確說明它們所屬的數(shù)據(jù)類型。不同類型的變量,其所其所能取的值的范圍不同能取的值的范圍不同,所能進行的操作不同。所能進行的操作不同。 數(shù)據(jù)類型數(shù)據(jù)類型是一個值的集合和定義在此集合上的一組操作是一個值的集合和定義在此集合上的一組操作的總稱。的總稱。1.1.4 數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型 如如C/C+中的中的int就是整型數(shù)據(jù)類型。它是所有整數(shù)的集合就是整型數(shù)據(jù)類型。它是所有整數(shù)的集合（在（在16位計算機中為位計算機中為3276832767的全體整數(shù)）和相關(guān)的整的全體整數(shù)）和相關(guān)的整數(shù)運算（如、等）。數(shù)

21、運算（如、等）。int i=2,j=5,k;k=i+j;.因為因為i、j和和k都屬于都屬于int，而，而int提提供了各種運算，所以可以進行相供了各種運算，所以可以進行相應運算。應運算。int i=9999999999;i*; （2）抽象數(shù)據(jù)類型）抽象數(shù)據(jù)類型 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型（Abstract Data Type簡寫為簡寫為ADT）指的是）指的是用戶進行軟件系統(tǒng)設(shè)計時從問題的數(shù)學模型中抽象出來的邏用戶進行軟件系統(tǒng)設(shè)計時從問題的數(shù)學模型中抽象出來的邏輯數(shù)據(jù)結(jié)構(gòu)和邏輯數(shù)據(jù)結(jié)構(gòu)上的運算，而不考慮計算機的具輯數(shù)據(jù)結(jié)構(gòu)和邏輯數(shù)據(jù)結(jié)構(gòu)上的運算，而不考慮計算機的具體存儲結(jié)構(gòu)和運算的具體實現(xiàn)算法。體

22、存儲結(jié)構(gòu)和運算的具體實現(xiàn)算法。 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型=邏輯結(jié)構(gòu)抽象運算邏輯結(jié)構(gòu)抽象運算 抽象數(shù)據(jù)類型實質(zhì)上就是描述一個求解問題本身（與計算抽象數(shù)據(jù)類型實質(zhì)上就是描述一個求解問題本身（與計算機無關(guān)），計算機人員就是在理解問題基礎(chǔ)上實現(xiàn)用計算機機無關(guān)），計算機人員就是在理解問題基礎(chǔ)上實現(xiàn)用計算機求解問題的過程。求解問題的過程。例如，抽象數(shù)據(jù)類型復數(shù)的定義：例如，抽象數(shù)據(jù)類型復數(shù)的定義：ADT Complex 數(shù)據(jù)對象：數(shù)據(jù)對象： D=e1,e2 | e1,e2均為實數(shù)均為實數(shù)數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： R= | e1是復數(shù)的實數(shù)部分，是復數(shù)的實數(shù)部分，e2 是復數(shù)的是復數(shù)的 虛數(shù)部分虛數(shù)部分 復數(shù)形

23、式：復數(shù)形式：e1+e2i或或（e1，e2）基本操作：基本操作： AssignComplex(&z,v1,v2)：構(gòu)造復數(shù)：構(gòu)造復數(shù)Z。 DestroyComplex(&z)：復數(shù)：復數(shù)z被銷毀。被銷毀。 GetReal(z,&real)：返回復數(shù)：返回復數(shù)z的實部值。的實部值。 GetImag(z,&Imag)：返回復數(shù)：返回復數(shù)z的虛部值。的虛部值。 Add(z1,z2,&sum)：返回兩個復數(shù)：返回兩個復數(shù)z1、z2的和。的和。 ADT Complex運算功能描述運算功能描述思考題：思考題：數(shù)據(jù)類型和抽象數(shù)據(jù)類型有什么不同？數(shù)據(jù)類型和抽象數(shù)據(jù)類型有

24、什么不同？1.2.1 什么是算法什么是算法 數(shù)據(jù)元素之間的關(guān)系有邏輯關(guān)系和物理關(guān)系，對應的操數(shù)據(jù)元素之間的關(guān)系有邏輯關(guān)系和物理關(guān)系，對應的操作有作有邏輯結(jié)構(gòu)上的操作功能邏輯結(jié)構(gòu)上的操作功能和和具體存儲結(jié)構(gòu)上的操作實現(xiàn)具體存儲結(jié)構(gòu)上的操作實現(xiàn)。 通常把具體存儲結(jié)構(gòu)上的操作實現(xiàn)步驟或過程稱為算法。通常把具體存儲結(jié)構(gòu)上的操作實現(xiàn)步驟或過程稱為算法。屬屬ADT的一部分的一部分算法實現(xiàn)算法實現(xiàn)1.2 算法及其描述算法及其描述 算法的五個重要的特性算法的五個重要的特性 （1） 有窮性：在有窮步之后結(jié)束。有窮性：在有窮步之后結(jié)束。（2） 確定性：無二義性。確定性：無二義性。 （3） 可行性：可通過基本運算有

25、限次執(zhí)行來實現(xiàn)?？尚行裕嚎赏ㄟ^基本運算有限次執(zhí)行來實現(xiàn)。（4） 有輸入有輸入 （5） 有輸出有輸出 表示存在數(shù)據(jù)處理表示存在數(shù)據(jù)處理例如，考慮下列兩段描述：例如，考慮下列兩段描述：（1）描述一）描述一void exam1() int n2; while (n%20) nn+2; printf(%dn,n);華中科大考研題華中科大考研題 （2） 描述二描述二void exam2() int x,y; y=0; x=5/y; printf(“%d,%dn”,x,y); 這兩段描述均不能滿足算法的特征，試問它們違反了這兩段描述均不能滿足算法的特征，試問它們違反了哪些特征？哪些特征？ 解：解：（1）算

26、法是一個死循環(huán)，違反了算法的有窮性）算法是一個死循環(huán)，違反了算法的有窮性特征。特征。 （2）算法包含除零錯誤，違反了算法的可行性特征）算法包含除零錯誤，違反了算法的可行性特征。思考題：思考題：算法和程序有什么不同？算法和程序有什么不同？ 1.2.2 算法描述算法描述 本書中采用本書中采用C/C+語言描述算法。語言描述算法。 說明：說明：C+語言中提供了一種語言中提供了一種引用引用運算符運算符“&”，引用，引用是個別名，當建立引用時，程序用另一個已定義的變量是個別名，當建立引用時，程序用另一個已定義的變量或?qū)ο螅繕耍┑拿殖跏蓟?，從那時起，引用作為或?qū)ο螅繕耍┑拿殖跏蓟?，從那時

27、起，引用作為目標的別名而使用，對引用的改動實際就是對目標的改目標的別名而使用，對引用的改動實際就是對目標的改動。動。 注意：注意：Turbo C不支持引用類型，不支持引用類型，VC+、Dev C+支支持引用類型。持引用類型。 編寫一個函數(shù)編寫一個函數(shù)swap1(x,y)，當執(zhí)行語句，當執(zhí)行語句swap1(a,b)時，交時，交換換a和和b的值。的值。 void swap1(int x,int y) int tmp; tmp=x;x=y;y=tmp; 注意：注意：a和和b的值不會發(fā)生了交換。的值不會發(fā)生了交換。 為此，采用指針的方式來回傳形參的值，需將上述函數(shù)為此，采用指針的方式來回傳形參的值，需

28、將上述函數(shù)改為：改為： void swap2(int *x,int *y) int tmp; tmp=*x;/將將x的值放在的值放在tmp中中 *x=*y; /將將x所指的值改為所指的值改為*y *y=tmp； /將將y所指的值改為所指的值改為tmp 上述函數(shù)的調(diào)用改為上述函數(shù)的調(diào)用改為swap2(&a,&b)，顯然遠不如采用引，顯然遠不如采用引用方式簡潔。所以本書后面很多算法都采用引用形參。用方式簡潔。所以本書后面很多算法都采用引用形參。“引用引用”的概念的概念例如：例如： int a=4; /a為普通的整型變量為普通的整型變量 int &b=a; /b是是a的引用變

29、量的引用變量 這里說明這里說明b變量是變量變量是變量a的引用，的引用，b也等于也等于4，之后這兩，之后這兩個變量同步改變。當個變量同步改變。當a改變時改變時b也同步改變，同樣，當也同步改變，同樣，當b改改變時變時a也同步改變。也同步改變。void main() int a=2; int &b=a; printf(a=%d,b=%dn,a,b); /輸出：輸出：a=2,b=2 b+; printf(a=%d,b=%dn,a,b); /輸出：輸出：a=3,b=3 a+; printf(a=%d,b=%dn,a,b); /輸出：輸出：a=4,b=4 引用常用于函數(shù)形參中，采用引用型形參時，在

30、函數(shù)調(diào)用引用常用于函數(shù)形參中，采用引用型形參時，在函數(shù)調(diào)用時將形參的改變回傳給實參，例如，有如下函數(shù)（其中的形參時將形參的改變回傳給實參，例如，有如下函數(shù)（其中的形參均為引用型形參）：均為引用型形參）： void swap(int &x,int &y) /形參前的形參前的“&”符號不是指針運算符符號不是指針運算符 int tmp=x; x=y;y=tmp 當用執(zhí)行語句當用執(zhí)行語句swap(a,b)時，時，a和和b的值發(fā)生了交換。的值發(fā)生了交換。void fun1(int n) int m=2; fun2(m); printf(“%dn”,m);void fun2(int

31、 x) x+; printf(“%dn”,x);實參實參普通形參普通形參fun1(m)fun2(x)實參到形參單向?qū)崊⒌叫螀蜗蛑祩鬟f值傳遞普通的參數(shù)傳遞普通的參數(shù)傳遞void fun1(int n) int m=2; fun2(m); printf(“%dn”,m);void fun2(int &x) x+; printf(“%dn”,x);實參實參引用型形參引用型形參fun1(m)fun2(x)實參到形參單向?qū)崊⒌叫螀蜗蛑祩鬟f值傳遞引用類型的參數(shù)傳遞引用類型的參數(shù)傳遞形參回傳給實參，實參和形參回傳給實參，實參和形參可步發(fā)生改變形參可步發(fā)生改變 例例1.3 編寫一個算法編寫一個算法

32、, 讀入三個整數(shù)讀入三個整數(shù)x、y和和z的值，要求從大的值，要求從大到小輸出這三個數(shù)。到小輸出這三個數(shù)。 解：解：依次輸入依次輸入x、y和和z這三個整數(shù)，通過比較交換后，使得這三個整數(shù)，通過比較交換后，使得xyz，然后輸出，然后輸出x、y和和z。 在算法中應考慮對這三個元素作盡可能少的比較和移動，在算法中應考慮對這三個元素作盡可能少的比較和移動，如下述算法在最壞的情況下只需進行如下述算法在最壞的情況下只需進行3次比較和次比較和7次移動。次移動。用用C/C+描述算法示例描述算法示例void Descending() printf(輸入輸入x,y,z); scanf(%d,%d,%d,&x

33、,&y,&z); if (x=y if (yz if (x=temp) y=temp； else y=x;x=temp; printf(%d,%d,%dn,x,y,z); 1.3 算法分析算法分析 1.3.2 算法時間復雜度分析算法時間復雜度分析 1.3.3 算法空間復雜度分析算法空間復雜度分析 1.3.1 算法設(shè)計的目標算法設(shè)計的目標1.3.1 算法設(shè)計的目標算法設(shè)計的目標算法設(shè)計應滿足以下幾條目標：算法設(shè)計應滿足以下幾條目標：（1）正確性）正確性 要求算法能夠正確地執(zhí)行預先規(guī)定的功能和要求算法能夠正確地執(zhí)行預先規(guī)定的功能和性能要求。這是最重要也是最基本的標準。性能要求。這是

34、最重要也是最基本的標準。（2）可使用性）可使用性 要求算法能夠很方便地使用。這個特性也要求算法能夠很方便地使用。這個特性也叫做用戶友好性。叫做用戶友好性。（3）可讀性）可讀性 算法應該易于人的理解，也就是可讀性好。算法應該易于人的理解，也就是可讀性好。為了達到這個要求，算法的邏輯必須是清晰的、簡單的為了達到這個要求，算法的邏輯必須是清晰的、簡單的和結(jié)構(gòu)化的。和結(jié)構(gòu)化的。（4）健壯性）健壯性 要求算法具有很好的容錯性，即提供異常處要求算法具有很好的容錯性，即提供異常處理，能夠?qū)Σ缓侠淼臄?shù)據(jù)進行檢查。不經(jīng)常出現(xiàn)異常中理，能夠?qū)Σ缓侠淼臄?shù)據(jù)進行檢查。不經(jīng)常出現(xiàn)異常中斷或死機現(xiàn)象。斷或死機現(xiàn)象。（5）

35、高效率與低存儲量需求）高效率與低存儲量需求 通常算法的效率主要指算法通常算法的效率主要指算法的執(zhí)行時間。對于同一個問題如果有多種算法可以求解，的執(zhí)行時間。對于同一個問題如果有多種算法可以求解，執(zhí)行時間短的算法效率高。算法存儲量指的是算法執(zhí)行執(zhí)行時間短的算法效率高。算法存儲量指的是算法執(zhí)行過程中所需的最大存儲空間。效率和低存儲量這兩者都過程中所需的最大存儲空間。效率和低存儲量這兩者都與問題的規(guī)模有關(guān)。與問題的規(guī)模有關(guān)。 一個算法是由控制結(jié)構(gòu)（順序、分支和循環(huán)三種）和一個算法是由控制結(jié)構(gòu)（順序、分支和循環(huán)三種）和原操作（指固有數(shù)據(jù)類型的操作，如原操作（指固有數(shù)據(jù)類型的操作，如n+等）構(gòu)成的，則等）

36、構(gòu)成的，則算法時間取決于兩者的綜合效果。算法時間取決于兩者的綜合效果。1.3.2 算法時間復雜度分析算法時間復雜度分析 控制語句控制語句1原操作原操作控制語句控制語句n原操作原操作一個算法的構(gòu)成一個算法的構(gòu)成例如：例如：void fun(int a,int n) int i; for (i=0;in;i+) ai=2*i; for (i=0;in;i+) printf(“%d “,ai); printf(“n”);算法描述的語言不同算法描述的語言不同算法執(zhí)行的環(huán)境不同算法執(zhí)行的環(huán)境不同其他因素其他因素所以不能用絕對執(zhí)行時間進行比較。所以不能用絕對執(zhí)行時間進行比較。同一問題可以采用多種算法實現(xiàn)。

37、如何比較同一問題可以采用多種算法實現(xiàn)。如何比較算法執(zhí)行效率？算法執(zhí)行效率？ 為了便于比較同一問題的不同算法，通常從算法中為了便于比較同一問題的不同算法，通常從算法中選取一種對于所研究的問題來說是基本運算的選取一種對于所研究的問題來說是基本運算的原操作原操作（以下將基本運算的原操作簡稱為（以下將基本運算的原操作簡稱為基本運算基本運算）。）。 算法執(zhí)行時間大致為基本運算所需的時間與其運算次算法執(zhí)行時間大致為基本運算所需的時間與其運算次數(shù)（也稱為數(shù)（也稱為頻度頻度）的乘積。）的乘積。 被視為算法基本運算的一般是最深層循環(huán)內(nèi)的語句。被視為算法基本運算的一般是最深層循環(huán)內(nèi)的語句。 在一個算法中在一個算法

38、中, ,進行基本運算的次數(shù)越少進行基本運算的次數(shù)越少, ,其運行時間也就其運行時間也就相對地越少；基本運算次數(shù)越多相對地越少；基本運算次數(shù)越多, ,其運行時間也就相對地越多。其運行時間也就相對地越多。 所以所以, ,通常把算法中包含基本運算次數(shù)的多少稱為算法的通常把算法中包含基本運算次數(shù)的多少稱為算法的時間復雜度，也就是說，一個算法的時間復雜度是指該算法的時間復雜度，也就是說，一個算法的時間復雜度是指該算法的基本運算次數(shù)基本運算次數(shù)。 算法中基本運算次數(shù)算法中基本運算次數(shù)T(n)是問題規(guī)模是問題規(guī)模n的某個函數(shù)的某個函數(shù)f(n)，記作，記作： T(n)=O(f(n) 記號記號“O”讀作讀作“大

39、大O”，它表示隨問題規(guī)模，它表示隨問題規(guī)模n的增大算法的增大算法執(zhí)行時間的增長率和執(zhí)行時間的增長率和f(n)的增長率相同。的增長率相同。“O”的形式定義為：的形式定義為： 若若f(n)是正整數(shù)是正整數(shù)n的一個函數(shù)，則的一個函數(shù)，則T(n)=O(f(n)表示存在一表示存在一個正的常數(shù)個正的常數(shù)M，使得當，使得當nn0時都滿足：時都滿足： |T(n)|M|f(n)| 也就是只求出也就是只求出T(n)的最高階，忽略其低階項和的最高階，忽略其低階項和常系數(shù)，這樣既可簡化常系數(shù)，這樣既可簡化T(n)的計算，又能比較客觀的計算，又能比較客觀地反映出當?shù)胤从吵霎攏很大時算法的時間性能。很大時算法的時間性能。

40、 例如，例如，T(n)=3n2-5n+10000=O(n2)本質(zhì)上講，是一種最高本質(zhì)上講，是一種最高數(shù)量級的比較數(shù)量級的比較一個沒有循環(huán)的算法的基本運算次數(shù)與問題規(guī)模一個沒有循環(huán)的算法的基本運算次數(shù)與問題規(guī)模n無關(guān)，記作無關(guān)，記作O(1)，也稱作常數(shù)階。，也稱作常數(shù)階。一個只有一重循環(huán)的算法的基本運算次數(shù)與問題規(guī)模一個只有一重循環(huán)的算法的基本運算次數(shù)與問題規(guī)模n的增長的增長呈線性增大關(guān)系，記作呈線性增大關(guān)系，記作O(n)，也稱線性階。，也稱線性階。其余常用的還有平方階其余常用的還有平方階O(n2)、立方階、立方階O(n3)、對數(shù)階、對數(shù)階O(log2n)、指數(shù)階指數(shù)階O(2n)等。等。 各種不

41、同數(shù)量級對應的值存在著如下關(guān)系：各種不同數(shù)量級對應的值存在著如下關(guān)系： O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(2n)O(n!)思考題：思考題：為什么要進行算法的時間復雜度分析？為什么要進行算法的時間復雜度分析？ 例例1.4 求兩個求兩個n階方陣的相加階方陣的相加C=A+B的算法如下的算法如下,分分析其時間復雜度。析其時間復雜度。 #define MAX 20 /定義最大的方階定義最大的方階 void matrixadd(int n,int AMAXMAX, int BMAXMAX,int CMAXMAX) int i,j; for (i=0;in;i+)fo

42、r (j=0;jn;j+) Cij=Aij+Bij; 該 算 法 中 的 基 本 運 算 是 兩 重 循 環(huán) 中 最 深 層 的 語 句該 算 法 中 的 基 本 運 算 是 兩 重 循 環(huán) 中 最 深 層 的 語 句Cij=Aij+Bij，分析它的頻度，即：，分析它的頻度，即： T(n)= =O(n2) 102101010*11ninininjnnnnn例例1.5 分析以下算法的時間復雜度。分析以下算法的時間復雜度。int fun(int n) int i,j,k,s; s=0; for (i=0;i=n;i+) for (j=0;j=i;j+) for (k=0;k=j;k+) s+; r

43、eturn(s);基本語句或基本操作基本語句或基本操作 解：解：該算法的基本操作是語句該算法的基本操作是語句s+，其頻度：，其頻度： T(n)= =O(n3)則該算法的時間復雜度為則該算法的時間復雜度為O(n3)。 niijjk0001例例1.6 分析以下算法的時間復雜度分析以下算法的時間復雜度。void func(int n) int i=0,s=0; while (sn) i+; s=s+i; 基本語句基本語句 解：解：對于對于while循環(huán)語句，設(shè)執(zhí)行的次數(shù)為循環(huán)語句，設(shè)執(zhí)行的次數(shù)為m，i從從0開始遞增開始遞增1，直到，直到m為止，有：為止，有： s=0+1+2+(m-1)=m(m-1)

44、/2， 并滿足并滿足s=m(m-1)/2n，則有，則有m 。 T(n)=O( ) 所以，該算法的時間復雜度為所以，該算法的時間復雜度為O( )。 nnn 例例1.7 有如下算法：有如下算法： void fun(int a,int n,int k) /數(shù)組數(shù)組a共有共有n個元素個元素 int i;if (k=n-1) for (i=0;in;i+) /n次次 printf(%dn,ai);else for (i=k;in;i+)/n-k次次ai=ai+i*i; fun(a,n,k+1); 調(diào)用上述算法的語句為調(diào)用上述算法的語句為fun(a,n,0)，求其時間復雜度。，求其時間復雜度。 解：解：設(shè)

45、設(shè)fun(a,n,0)的時間復雜度為的時間復雜度為T(n)，則，則fun(a,n,k)的執(zhí)的執(zhí)行時間為行時間為T1(n,k)，由，由fun()算法可知：算法可知： T1(n,k)=n 當當k=n-1時時 T1(n,k)= (n-k)+T1(n,k+1) 其他情況其他情況 則則 T(n)=T1(n,0)=n+T1(n,1)=n+(n-1)+T1(n,2)=n+(n-1)+2+T1(n,n-1)=n+(n-1)+ +2+n=O(n2) 所以調(diào)用所以調(diào)用fun(a,n,0)的時間復雜度為的時間復雜度為O(n2)。 空間復雜度是對一個算法在運行過程中空間復雜度是對一個算法在運行過程中臨時占用的存儲空間

46、臨時占用的存儲空間大小的量度，一般也作為問題規(guī)模大小的量度，一般也作為問題規(guī)模n的函數(shù)，以數(shù)量級形式給出的函數(shù)，以數(shù)量級形式給出,記作：記作： S(n) = O(g(n) 若所需額外空間相對于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法若所需額外空間相對于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為為原地工作原地工作。若所需存儲量依賴于特定的輸入，則通常按最壞。若所需存儲量依賴于特定的輸入，則通常按最壞情況考慮。情況考慮。1.3.3 算法空間復雜度分析算法空間復雜度分析 例例1.8 分析例分析例1.4和例和例1.5的空間復雜度。的空間復雜度。 解：解：由于這兩個算法中臨時變量的個數(shù)與問題規(guī)模由于這兩個算法中臨時變量

47、的個數(shù)與問題規(guī)模n無關(guān)，所以空間復雜度均為無關(guān)，所以空間復雜度均為O(1)。1.4 數(shù)據(jù)結(jié)構(gòu)算法程序數(shù)據(jù)結(jié)構(gòu)算法程序 數(shù)據(jù)結(jié)構(gòu)算法程序數(shù)據(jù)結(jié)構(gòu)算法程序的作者：的作者：N.Wirth（1934年），瑞士計算機科學家，年），瑞士計算機科學家，1960年獲加利福尼亞大學伯克利分校博士學位。曾任年獲加利福尼亞大學伯克利分校博士學位。曾任斯坦福大學、蘇黎世聯(lián)邦理工學院教授。發(fā)明多斯坦福大學、蘇黎世聯(lián)邦理工學院教授。發(fā)明多種計算機語言（包括種計算機語言（包括Pascal、Modula和和Oberon等），并為軟件工程領(lǐng)域作出過開拓性的貢獻。等），并為軟件工程領(lǐng)域作出過開拓性的貢獻。于于1980年獲得計算機

48、科學界最高獎年獲得計算機科學界最高獎圖靈獎圖靈獎（/wiki/Turing_Award）。）。C#語言創(chuàng)始人：語言創(chuàng)始人：Anders Hejlsberg（安德斯，海斯博（安德斯，海斯博格）格）Wirth的學生：的學生：數(shù)據(jù)結(jié)構(gòu)領(lǐng)域做出突出貢獻的計算機科學家：數(shù)據(jù)結(jié)構(gòu)領(lǐng)域做出突出貢獻的計算機科學家：Donald Knuth（1938年），算法和程序設(shè)年），算法和程序設(shè)計技術(shù)的先驅(qū)者，計算機排版系統(tǒng)計技術(shù)的先驅(qū)者，計算機排版系統(tǒng)TEX和和METAFONT的發(fā)明者，他因這些成就和大量的發(fā)明者，他因這些成就和大量創(chuàng)造性的影響深遠的著作（創(chuàng)造性的影響深遠的著

49、作（19部書和部書和160篇論篇論文）而譽滿全球。作為斯坦福大學計算機程文）而譽滿全球。作為斯坦福大學計算機程序設(shè)計藝術(shù)的榮譽退休教授，序設(shè)計藝術(shù)的榮譽退休教授，他當前正全神他當前正全神貫注于完成其關(guān)于計算機科學的史詩性的七貫注于完成其關(guān)于計算機科學的史詩性的七卷集。卷集。這一偉大工程在這一偉大工程在1962年他還是加利福年他還是加利福尼亞理工學院的研究生時就開始了。他于尼亞理工學院的研究生時就開始了。他于1974年獲得計算機科學界最高獎年獲得計算機科學界最高獎圖靈獎圖靈獎。C.A.R.Hoare（1934年），英國計算機科學年），英國計算機科學家，畢業(yè)于牛津大學，他最重要的工作包括：家，畢業(yè)

50、于牛津大學，他最重要的工作包括：快速排序算法快速排序算法，Hoare邏輯，形式語言通信時邏輯，形式語言通信時序進程（序進程（CSP）等。于）等。于1980年獲得計算機科年獲得計算機科學界最高獎學界最高獎圖靈獎圖靈獎。1.4.1 程序和數(shù)據(jù)結(jié)構(gòu)程序和數(shù)據(jù)結(jié)構(gòu)沃思沃思指出：程序就是在數(shù)據(jù)的某些特定的表示方法指出：程序就是在數(shù)據(jù)的某些特定的表示方法和結(jié)構(gòu)的基礎(chǔ)上，對抽象算法的具體表述，所以說程序和結(jié)構(gòu)的基礎(chǔ)上，對抽象算法的具體表述，所以說程序離不開數(shù)據(jù)結(jié)構(gòu)。離不開數(shù)據(jù)結(jié)構(gòu)。1.4.2 算法和程序算法和程序由程序設(shè)計語言描述的算法就是計算機程序。對一個由程序設(shè)計語言描述的算法就是計算機程序。對一個求解

51、問題而言，算法就是解題的方法，沒有算法，程求解問題而言，算法就是解題的方法，沒有算法，程序就成了無本之末，無源之水。序就成了無本之末，無源之水。有了算法，將它表示成程序是不困難的。算法是程序有了算法，將它表示成程序是不困難的。算法是程序的核心。算法在程序設(shè)計，也可以說軟件開發(fā)，甚至的核心。算法在程序設(shè)計，也可以說軟件開發(fā)，甚至可以說在整個計算機科學中的地位都是極其重要的?？梢哉f在整個計算機科學中的地位都是極其重要的。1.4.3 算法和數(shù)據(jù)結(jié)構(gòu)算法和數(shù)據(jù)結(jié)構(gòu)求解的問題可以通過抽象數(shù)據(jù)類型描述，它由數(shù)據(jù)的邏求解的問題可以通過抽象數(shù)據(jù)類型描述，它由數(shù)據(jù)的邏輯結(jié)構(gòu)和抽象運算兩部分組成。輯結(jié)構(gòu)和抽象運算

52、兩部分組成。一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以映射成多種存儲結(jié)構(gòu)，抽象運一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以映射成多種存儲結(jié)構(gòu)，抽象運算在不同的存儲結(jié)構(gòu)上實現(xiàn)可以對應多種算法，在同一算在不同的存儲結(jié)構(gòu)上實現(xiàn)可以對應多種算法，在同一種存儲結(jié)構(gòu)上實現(xiàn)也可能有多種算法，通過算法的時間種存儲結(jié)構(gòu)上實現(xiàn)也可能有多種算法，通過算法的時間復雜度和空間復雜度等分析，可以得到好的算法。復雜度和空間復雜度等分析，可以得到好的算法。 好算法與以下因素有關(guān)：好算法與以下因素有關(guān)：算法的正確性、可讀性和可維護性等。算法的正確性、可讀性和可維護性等。算法的時間和空間復雜度。算法的時間和空間復雜度。存儲結(jié)構(gòu)的存儲能力存儲結(jié)構(gòu)的存儲能力。如果存儲結(jié)構(gòu)

53、存儲能力強、存儲。如果存儲結(jié)構(gòu)存儲能力強、存儲信息多，算法將會較好設(shè)計。反之對于過于簡單的存儲信息多，算法將會較好設(shè)計。反之對于過于簡單的存儲結(jié)構(gòu)，可能就要設(shè)計一套比較復雜的算法。在這一點上，結(jié)構(gòu)，可能就要設(shè)計一套比較復雜的算法。在這一點上，經(jīng)常體現(xiàn)時間與空間的矛盾，往往存儲能力是與所使用經(jīng)常體現(xiàn)時間與空間的矛盾，往往存儲能力是與所使用的空間大小成正比的。的空間大小成正比的。存儲結(jié)構(gòu)應與所選擇的算法相適應。存儲結(jié)構(gòu)應與所選擇的算法相適應。存儲結(jié)構(gòu)是實現(xiàn)算存儲結(jié)構(gòu)是實現(xiàn)算法的基礎(chǔ)，也會影響算法的設(shè)計，其選擇要充分考慮算法的基礎(chǔ)，也會影響算法的設(shè)計，其選擇要充分考慮算法的各種操作，應與算法的操作相

54、適應。法的各種操作，應與算法的操作相適應。數(shù)據(jù)存儲結(jié)構(gòu)會影響算法的好壞，因此在選擇存儲結(jié)構(gòu)數(shù)據(jù)存儲結(jié)構(gòu)會影響算法的好壞，因此在選擇存儲結(jié)構(gòu)時，也要考慮其對算法的影響。存儲結(jié)構(gòu)對算法的影響主時，也要考慮其對算法的影響。存儲結(jié)構(gòu)對算法的影響主要在兩方面：要在兩方面：問題描述問題描述：有若干學生數(shù)據(jù)（學生數(shù)小于：有若干學生數(shù)據(jù)（學生數(shù)小于50），），每個學生數(shù)據(jù)包含學號（每個學生學號是唯一的，每個學生數(shù)據(jù)包含學號（每個學生學號是唯一的，但學生記錄不一定按學號順序存放）、姓名、班但學生記錄不一定按學號順序存放）、姓名、班號和若干門課程成績（每個學生所選課程數(shù)目可號和若干門課程成績（每個學生所選課程數(shù)目可能不等，但最多不超過能不等，但最多不超過6門）。門）。要求要求：設(shè)計一個程序輸出每個學生的學號、姓名：設(shè)計一個程序輸出每個學生的學號、姓名和平均分以及每門課程（課程編號從和平均分以及每門課程（課