數(shù)據(jù)結構復習.doc

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