數(shù)據(jù)結(jié)構(gòu)c語言版期末復(fù)習(xí)匯總

1、1數(shù)據(jù)結(jié)構(gòu)（C語言版）期末復(fù)習(xí)匯總第一章緒論數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)：是一門研究非數(shù)值計算程序設(shè)計中的操作對象，以及這些對象之間的關(guān)系和操作的學(xué)科。數(shù)據(jù)結(jié)構(gòu)是一門綜合性的專業(yè)課程，是一門介于數(shù)學(xué)、計算機(jī)硬件、計算機(jī)軟件之間的一門核心課程。是設(shè)計和實現(xiàn)編譯系統(tǒng)、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序和大型應(yīng)用程序的基礎(chǔ)。數(shù)據(jù)數(shù)據(jù)：是客觀事物的符號表示，是所有能輸入到計算機(jī)中并被計算機(jī)程序處理的符號的總稱。如數(shù)學(xué)計算中用到的整數(shù)和實數(shù)，文本編輯中用到的

2、字符串，多媒體程序處理的圖形、圖像、聲音及動畫等通過特殊編碼定義后的數(shù)據(jù)。數(shù)據(jù)的邏輯結(jié)構(gòu)劃分：線、樹、圖線、樹、圖算法的定義及特性算法算法：是為了解決某類問題而規(guī)定的一個有限長的操作序列。五個特性：有窮性、確定性、可行性、輸入、輸出有窮性、確定性、可行性、輸入、輸出評價算法優(yōu)劣的基本標(biāo)準(zhǔn)（4個）：正確性、可讀性、健壯性、高效性及低存儲量正確性、可讀性、健壯性、高效性及低存儲量第二章線性表線性表的定義和特點：線性表：線性表：由n(n≥0)

3、個數(shù)據(jù)特性相同的元素構(gòu)成的有限序列。線性表中元素個數(shù)n(n≥0)定義為線性表的長度，n=0時稱為空表。非空線性表或線性結(jié)構(gòu)，其特點：非空線性表或線性結(jié)構(gòu)，其特點：（1）存在唯一的一個被稱作“第一個第一個”的數(shù)據(jù)元素；（2）存在唯一的一個被稱作“最有一個最有一個”的數(shù)據(jù)元素；（3）除第一個之外，結(jié)構(gòu)中的每個數(shù)據(jù)元素均只有一個前驅(qū)前驅(qū)；（4）除最后一個之外，結(jié)構(gòu)中的每個數(shù)據(jù)元素均只有一個后繼后繼。順序表的插入：n個元素在i位插入，應(yīng)移動（n

4、i1）位元素。順序表存儲結(jié)構(gòu)的優(yōu)缺點：順序表存儲結(jié)構(gòu)的優(yōu)缺點：優(yōu)點：邏輯相鄰，物理相鄰；可隨機(jī)存取任一元素；存儲空間使用緊湊；缺點：插入、刪除操作需要移動大量的元素；預(yù)先分配空間需按最大空間分配，利用不充分；表容量難以擴(kuò)充；線性表的應(yīng)用：一般線性表的合并：★★★一般線性表的合并：★★★算法2.1：LA=(75311)LB=(263)合并后LA=(7531126)算法思想算法思想：擴(kuò)大線性表LA，將存在于線性表LB中而不存在于線性表LA中

5、的數(shù)據(jù)元素插入到線性表LA中去。只要從線性表LB中依次取得每個數(shù)據(jù)元素，并依值在線性表LA中進(jìn)行查訪，若不存在，則插入之。有序表的合并：★★★有序表的合并：★★★算法2.2：LA=(35811)LB=(2689111520)則LC=(23568911111520)算法思想算法思想：首先創(chuàng)建一個空表LC，通過比較指針pa和pb所指向的元素的值，依次從LA3單鏈表特點：單鏈表特點：它是一種動態(tài)結(jié)構(gòu)，整個存儲空間為多個鏈表共用；不需預(yù)先分配空

6、間；指針占用額外存儲空間；不能隨機(jī)存取，查找速度慢。第三章棧和隊列棧的類型定義：棧的類型定義：棧(Stack)是限制在表的一端進(jìn)行插入和刪除運(yùn)算的線性表，通常稱插入、刪除的這一端為棧頂(Top)，另一端為棧底(Bottom)。當(dāng)表中沒有元素時稱為空棧。假設(shè)棧S=(a1，a2，a3，…an)，則a1稱為棧底元素稱為棧底元素，an為棧頂元素為棧頂元素。棧中元素按a1，a2，a3，…an的次序進(jìn)棧次序進(jìn)棧，退棧的第一個元素應(yīng)為棧頂元素。即，棧

7、的修改是按后進(jìn)先出的原則進(jìn)行的。因此，棧稱為后進(jìn)先出后進(jìn)先出表（LIFO）。棧的進(jìn)棧、出棧順序：棧的進(jìn)棧、出棧順序：例：★★★例：★★★對于一個棧，給出輸入項對于一個棧，給出輸入項A、B、C，如果輸入項序列由，如果輸入項序列由ABC組成，試給出所有可能的輸組成，試給出所有可能的輸出序列。出序列。A進(jìn)A出B進(jìn)B出C進(jìn)C出ABCA進(jìn)A出B進(jìn)C進(jìn)C出B出ACBA進(jìn)B進(jìn)B出A出C進(jìn)C出BACA進(jìn)B進(jìn)B出C進(jìn)C出A出BCAA進(jìn)B進(jìn)C進(jìn)C出B出A出

8、CBA不可能產(chǎn)生輸出序列CAB棧的應(yīng)用：數(shù)值轉(zhuǎn)換[大題]算法思想：首先將按照上述計算過程中得到的八進(jìn)制樹的各位依次進(jìn)棧，然后將棧中的八算法思想：首先將按照上述計算過程中得到的八進(jìn)制樹的各位依次進(jìn)棧，然后將棧中的八進(jìn)制數(shù)依次出棧輸出，輸出結(jié)果就是該是十進(jìn)制數(shù)轉(zhuǎn)換得到的八進(jìn)制數(shù)。進(jìn)制數(shù)依次出棧輸出，輸出結(jié)果就是該是十進(jìn)制數(shù)轉(zhuǎn)換得到的八進(jìn)制數(shù)。N=(Ndivd)dNmodd（其中：div為整除運(yùn)算，mod為求余運(yùn)算）例如(1348)10=(2