數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí).doc

算法（algorithm）解決某一特定問題的具體步驟的描述，是指令的有限序列棧: 是只準(zhǔn)在一端進(jìn)行插入和刪除操作的線性表，允許插入和刪除的一端叫棧頂，另一端叫棧底，最后插入的最先刪除。隊(duì)列：是允許從一頭插入另一端刪除的線性表，允許刪除的叫對頭，允許插入的叫隊(duì)尾，最先插入的最先刪除。循環(huán)隊(duì)列：遞歸：在一個(gè)函數(shù)結(jié)束本函數(shù)之前，直接或間接調(diào)用本身函數(shù)數(shù)據(jù)：描述客觀事物的符號(hào)數(shù)據(jù)元素： 數(shù)據(jù)的基本單位數(shù)據(jù)結(jié)構(gòu)： 數(shù)據(jù)元素和數(shù)據(jù)元素關(guān)系集合數(shù)據(jù)項(xiàng):有獨(dú)立含義的數(shù)據(jù)的最小單位數(shù)據(jù)結(jié)構(gòu)的兩要素：數(shù)據(jù)元素集合、數(shù)據(jù)元素之間的關(guān)系集合數(shù)據(jù)結(jié)構(gòu)的形式定義為：數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組Data_Structure （D，R） 其中，D是數(shù)據(jù)元素的有限集，R是D上關(guān)系的有限集。數(shù)據(jù)結(jié)構(gòu)概念包括：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)（物理）結(jié)構(gòu)、數(shù)據(jù)的操作算法的評(píng)價(jià)： 正確性、可讀性、健壯性、效率高效和低存儲(chǔ)算法特性：有窮性、確定性、可行性、輸入、輸出線性表：在數(shù)據(jù)元素非空的有限集合中，存在唯一叫做“第一個(gè)”和最后一個(gè)的數(shù)據(jù)元素線性表定義：一個(gè)線性表是n個(gè)數(shù)據(jù)元素的有限序列順序表：用一組地址連續(xù)的存儲(chǔ)單元存放一個(gè)線性表順序表的特點(diǎn)：實(shí)現(xiàn)物理地址相鄰，隨機(jī)存取，用一維數(shù)組實(shí)現(xiàn)順序表優(yōu)點(diǎn)：實(shí)現(xiàn)物理地址相鄰，可隨機(jī)存取，結(jié)構(gòu)緊湊順序表缺點(diǎn)：空間浪費(fèi)，表容量難以擴(kuò)充，插入或刪除操作需要大量移動(dòng)線性鏈表：節(jié)點(diǎn)中只含一個(gè)指針域的鏈表線性鏈表的特點(diǎn)：用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素利用指針實(shí)現(xiàn)了用不相鄰的存儲(chǔ)單元存放邏輯上相鄰的數(shù)據(jù)元素每個(gè)數(shù)據(jù)元素，出來存儲(chǔ)本身信息外，還需存儲(chǔ)其直接后繼的信息單鏈表特點(diǎn)它是一種動(dòng)態(tài)結(jié)構(gòu)，整個(gè)存儲(chǔ)空間為多個(gè)鏈表共用不需要預(yù)先分配空間指針占用額外存儲(chǔ)空間不能隨機(jī)存取，查找速度慢循環(huán)鏈表循環(huán)鏈表中最后一個(gè)節(jié)點(diǎn)的指針指向頭節(jié)點(diǎn)，是鏈表構(gòu)成環(huán)狀特點(diǎn)：從表中任一節(jié)點(diǎn)出發(fā)均可找到表中其他節(jié)點(diǎn)，提高查找效率約瑟夫環(huán)棧：限定僅在表尾進(jìn)行插入或刪除操作的線性表入棧算法int push(int s,int x,int top) if(top=M) printf(overflow); return(-M); stop=x; return(+top);出棧算法：int pop(int s,int top,int *q) if(top=0) printf(stack empty); return(0); *q=s-top; return(top);棧的應(yīng)用：回文和進(jìn)制轉(zhuǎn)換，斐波那契計(jì)算器隊(duì)列：隊(duì)列是限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表（先進(jìn)先出）隊(duì)尾允許插入的一端對頭允許刪除的一端判斷隊(duì)空和隊(duì)滿：少用一個(gè)空間： 隊(duì)空：front = rear 隊(duì)滿：(rear +) M = front入棧算法：void en_cycque(int sq,int front,int rear,int x) if(rear+1)%M)=front) printf(overflow); else rear=(rear+1)%M; sqrear=x; 出棧算法：int dl_cycque(int sq,int front,int rear,int *q) if(front=rear) return(0); else front=(front+1)%M; *q=sqfront; return(1); 隊(duì)列的應(yīng)用：走迷宮、劃分子集查找方法評(píng)價(jià)：查找速度、占用存儲(chǔ)空間多少、算法本身復(fù)雜程度、平均查找長度平均查找長度ASL：為確定記錄在表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)的期望值折半查找：使用條件：采用順序存儲(chǔ)結(jié)構(gòu)的有序表分塊查找：查找過程：將表分成幾塊，快內(nèi)無序，塊間有序；先確定待查記錄所在快，再在快內(nèi)查找適用條件：分塊有序表哈希查找：在記錄的關(guān)鍵字與記錄的存儲(chǔ)地址之間建立的一種對應(yīng)關(guān)系基本思想：在記錄的存儲(chǔ)地址和它的關(guān)鍵字之間建立一個(gè)確定的對應(yīng)關(guān)系，這樣，不經(jīng)過比較，一次存取就能得到所查元素的查找方法沖突：key1key2，但H(key1)=H(key2)的現(xiàn)象同義詞：具有相同函數(shù)值的兩個(gè)關(guān)鍵字哈希函數(shù)的構(gòu)造方法：直接定址法（不會(huì)發(fā)生沖突）、平方取中法（適用于不知道全部關(guān)鍵字的情況）、折疊法（種類：移位疊加、間界疊加，適用關(guān)鍵字位數(shù)很多，且每位上數(shù)字分布大致均勻情況）、除留余數(shù)法、隨機(jī)數(shù)法（適用于關(guān)鍵字長度不等的情況）選取哈希函數(shù)，考慮的因素：計(jì)算哈希函數(shù)所需時(shí)間關(guān)鍵字長度哈希表長度關(guān)鍵字分布情況記錄的查找頻率處理沖突的方法：開放定址法分類：u 線性探測再散列：di=1,2,3,m-1u 二次探測再散列：di=1,-1,2,-2,3,k(km/2)u 偽隨機(jī)探測再散列：di=偽隨機(jī)數(shù)序列 再哈希法鏈地址法方法：將所有關(guān)鍵字為同義詞的記錄存儲(chǔ)在一個(gè)單鏈表中，并用一維數(shù)組存放頭指針 排序：一個(gè)數(shù)據(jù)元素（記錄）的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列排序分類v 按待排序記錄所在位置l 內(nèi)部排序：待排序記錄存放在內(nèi)存l 外部排序：排序過程中需對外存進(jìn)行訪問的排序v 按排序依據(jù)原則l 插入排序：直接插入排序、折半插入排序、希爾排序l 交換排序：冒泡排序、快速排序l 選擇排序：簡單選擇排序、堆排序l 歸并排序：2-路歸并排序l 基數(shù)排序直接插入排序：整個(gè)排序過程為n-1趟插入，即先將序列中第一個(gè)記錄看成一個(gè)有序子序列，然后從第2個(gè)記錄開始，逐個(gè)進(jìn)行插入，直至整個(gè)序列有序折半插入排序：用折半查找方法確定插入位置的排序希爾排序：先取一個(gè)正整數(shù)d1n，把所有相隔d1的記錄放一組，組內(nèi)進(jìn)行直接插入排序；然后去d2d1，重復(fù)上述分組和排序操作；直至di = 1，即所有記錄放進(jìn)一個(gè)組中排序?yàn)橹姑芭菖判颍嚎焖倥判颍夯舅枷耄和ㄟ^一趟排序，將待排序記錄分割成獨(dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄進(jìn)行排序，以達(dá)到整個(gè)序列有序堆排序：N個(gè)元素的序列(k1,k2,kn),當(dāng)且僅當(dāng)滿足下列關(guān)系時(shí)，稱之為堆歸并排序?qū)蓚€(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表基數(shù)排序多關(guān)鍵字排序鏈?zhǔn)交鶖?shù)排序步驟：我的錯(cuò)題：快速排序在最壞情況下的時(shí)間復(fù)雜度為0(n2)若需要利用形參直接訪問實(shí)參時(shí)，應(yīng)將形參變量說明為（引用）參數(shù)在線性表的散列存儲(chǔ)中，處理沖突的常用方法有_和_兩種當(dāng)待排序的記錄數(shù)較大，排序碼較隨機(jī)且對穩(wěn)定性不作要求時(shí)，宜采用_排序；當(dāng)待排序的記錄數(shù)較大，存儲(chǔ)空間允許且要求排序是穩(wěn)定時(shí)，宜采用_排序。 對n個(gè)記錄的文件進(jìn)行快速排序，所需要的輔助存儲(chǔ)空間大致為O（1og2n） 在堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為_，整個(gè)堆排序過程的時(shí)間復(fù)雜度為_。后綴算式9 2 3 +- 10 2 / -的值為_。中綴