第一篇：2010年自學考試《數據結構》各章復習要點總結
2010年自學考試《數據結構》各章復習要點總結(5)龍耒為你整理：
第九章 查找
查找的同時對表做修改操作(如插入或刪除)則相應的表稱之為動態查找表，否則稱之為靜態查找表。
衡量查找算法效率優劣的標準是在查找過程中對關鍵字需要執行的平均比較次數(即平均查找長度ASL)。
線性表查找的方法：
·順序查找：逐個查找，ASL=(n+1)/2;
·二分查找：取中點int(n/2)比較，若小就比左區間，大就比右區間。用二叉判定樹表示。ASL=(∑(每層結點數*層數))/N;·分塊查找：要求“分塊有序”，將表分成若干塊內部不一定有序，并抽取各塊中的最大關鍵字及其位置建立有序索引表。
二叉排序樹(BST)定義是二叉排序樹是空樹或者滿足如下性質的二叉樹：
·若它的左子樹非空，則左子樹上所有結點的值均小于根結點的值;
·若它的右子樹非空，則右子樹上所有結點的值均大于根結點的值;
·左、右子樹本身又是一棵二叉排序樹。
二叉排序樹的插入、建立、刪除的算法平均時間性能是O(nlog2n)。
二叉排序樹的刪除操作可分三種情況進行處理：
·*P是葉子，則直接刪除*P，即將*P的雙親*parent中指向*P的指針域置空即可。
·*P只有一個孩子*child，此時只需將*child和*p的雙親直接連接就可刪去*p。
·*p有兩個孩子，則先將*p結點的中序后繼結點的數據到*p，刪除中序后繼結點。
關于B-樹(多路平衡查找樹)。它適合在磁盤等直接存取設備上組織動態的查找表，是一種外查找算法。建立的方式是從下向上拱起。散列技術：將結點按其關鍵字的散列地址存儲到散列表的過程稱為散列。
散列函數的選擇有兩條標準：簡單和均勻。
常見的散列函數構的造方法：
·平方取中法：hash=int((x^2)0)
·除余法：表長為m，hash=x%m
·相乘取整法：hash=int(m*(x*A-int(x*A));A=0.618
·隨機數法：hash=random(x)。
處理沖突的方法：
開放定址法： 一般形式為hi=(h(key)+di)%m1≤i≤m-1，開放定址法要求散列表的裝填因子α≤1。
·開放定址法類型：
·線性探查法：address=(hash(x)+i)%m;·二次探查法：address=(hash(x)+i^2)%m;
·雙重散列法：address=(hash(x)+i*hash(y))%m;
·拉鏈法： 是將所有關鍵字為同義詞的結點鏈接在同一個單鏈表中。
·拉鏈法的優點：
·拉鏈法處理沖突簡單，且無堆積現象;
·鏈表上的結點空間是動態申請的適于無法確定表長的情況;
·拉鏈法中α可以大于1，結點較大時其指針域可忽略，因此節省空間;
·拉鏈法構造的散列表刪除結點易實現。
·拉鏈法也有缺點：當結點規模較小時，用拉鏈法中的指針域也要占用額外空間，還是開放定址法省空間。
第十章 文件
文件是性質相同的記錄的集合。記錄是文件中存取的基本單位，數據項是文件可使用的最小單位，數據項有時稱字段或者屬性。
文件
·邏輯結構是一種線性結構。
·操作有：檢索和維護。并有實時和批量處理兩種處理方式。
文件
·存儲結構是指文件在外存上的組織方式。
·基本的組織方式有：順序組織、索引組織、散列組織和鏈組織。
·常用的文件組織方式：順序文件、索引文件、散列文件和多關鍵字文件。
評價一個文件組織的效率，是執行文件操作所花費的時間和文件組織所需的存儲空間。
檢索功能的多寡和速度的快慢，是衡量文件操作質量的重要標志。
順序文件是指按記錄進入文件的先后順序存放、其邏輯順序和物理順序一致的文件。主關鍵字有序稱順序有序文件，否則稱順序無序文件。
一切存儲在順序存儲器(如磁帶)上的文件都只能順序文件，只能按順序查找法存取。順序文件的插入、刪除和修改只能通過復制整個文件實現。
索引文件的組織方式：通常是在主文件之外建立一張索引表指明邏輯記錄和物理記錄之間一一對應的關系，它和主文件一起構成索引文件。
索引非順序文件中的索引表為稠密索引。索引順序文件中的索引表為稀疏索引。
若記錄很大使得索引表也很大時，可對索引表再建立索引，稱為查找表。是一種靜態索引。
索引順序文件常用的有兩種：
·ISAM索引順序存取方法：是專為磁盤存取文件設計的，采用靜態索引結構。
·VSAM虛擬存儲存取方法：采用B+樹作為動態索引結構，由索引集、順序集、數據集組成。
散列文件是利用散列存儲方式組織的文件，亦稱為直接存取文件。
散列文件
·優點是：文件隨機存放，記錄不需要排序;插入刪除方便;存取速度快;不需要索引區，節省存儲空間。
·缺點是：不能進行順序存取，只能按關鍵字隨機存取，且詢問方式限地簡單詢問，需要重新組織文件。
多重表文件：對需要查詢的次關鍵字建立相應的索引，對相同次關鍵字的記錄建一個鏈表并將鏈表頭指針、長度、次關鍵字作為索引表的索引項。
倒排表：次關鍵字索引表稱倒排表，主文件和倒排表構成倒排文件。
第二篇：2010年自學考試《數據結構》各章復習要點總結
11-12-2數據結構復習指導
第一章：
知識點：數據結構的定義；數據元素關系的基本結構類型；數據元素的不同存儲結構；算法的重要特性；評價算法的重要指標； 如何由程序代碼估算算法的復雜度（大O描述）。
第二章：
知識點：線性表不同的存儲方式及其各自特點；順序表及鏈表的基本操作（插入、刪除等）與其具體代碼實現。
第三章：
知識點：棧和隊列的結構特點；二者基本操作的思想；鏈隊列和循環隊列的基本操作；循環隊列如何判空和判滿。
第四章：
知識點：串的相關定義與基本操作；模式匹配的定義與思想。
第五章：
知識點：數組的定義與順序實現方式；數組順序存儲中元素地址的計算；稀疏矩陣的壓縮存儲方式與元素地址的特點；廣義表的定義與基本操作（表頭，表尾，判長度、深度）。
第六章：
知識點：樹的基本術語；（滿/完全）二叉樹的定義與各種性質特點；二叉樹不同的存儲與遍歷方式；一般樹的存儲結構；樹與森林的遍歷方式；赫夫曼樹與編碼的求法。
第七章：
知識點：（有向/無向/完全）圖的概念與其特點；（強）聯通圖的定義與特點；圖的不同存儲結構及其操作；圖的不同方式的遍歷；最小生成樹的定義與其不同的求解方法；拓撲排序的定義與思想；關鍵（最短）路徑的定義與思想。
第九章：
知識點：順序查找、折半查找的思想及其具體代碼實現和復雜度分析；索引查找的思想；二叉排序樹的思想及操作；平衡二叉樹的定義與操作；B-樹的定義與特點；哈希表（函數）的定義；哈希函數的構造方法與處理沖突的方法。
第十章：
知識點：各種排序方法的思想與其復雜度、穩定性分析。
注：以上涉及到的復雜度分析，其推導過程不做要求。
第三篇：2010年自學考試《數據結構》各章復習要點總結
2010年自學考試《數據結構》各章復習要點總結(3)龍耒為你整理：
第五章 多維數組和廣義表
數組一般用順序存儲的方式表示。存儲的方式有：
·行優先順序，也就是把數組逐行依次排列。PASCAL、C
·列優先順序，就是把數組逐列依次排列。FORTRAN
地址的計算方法：
·按行優先順序排列的數組：LOCa(ij)=LOCa(11)+((i-1)*n+(j-1))*d.·按列優先順序排列的數組：LOCa(ij)=LOCa(11)+((j-1)*n+(i-1))*d.矩陣的壓縮存儲：為多個相同的非零元素分配一個存儲空間;對零元素不分配空間。
特殊矩陣的概念：所謂特殊矩陣是指非零元素或零元素分布有一定規律的矩陣。
稀疏矩陣的概念：一個矩陣中若其非零元素的個數遠遠小于零元素的個數，則該矩陣稱為稀疏矩陣。
特殊矩陣的類型：
·對稱矩陣：滿足a(ij)=a(ji)。元素總數n(n+1)/2.I=max(i，j)，J=min(i，j)，LOCa(ij)=LOC(sa[0])+(I*(I+1)/2+J)*d.·三角矩陣：
·上三角陣：k=i*(2n-i+1)/2+j-i，LOCa(ij)=LOC(sa[0])+k*d.·下三角陣：k=i*(i+1)/2+j，LOCa(ij)=LOC(sa[0])+k*d.·對角矩陣：k=2i+j，LOCa(ij)=LOC(sa[0])+k*d.稀疏矩陣的壓縮存儲方式用三元組表把非零元素的值和它所在的行號列號做為一個結點存放在一起，用這些結點組成的一個線性表來表示。但這種壓縮存儲方式將失去隨機存儲功能。加入行表記錄每行的非零元素在三元組表中的起始位置，即帶行表的三元組表。
廣義表是n(n≥0)個元素的有限序列，其中的元素是原子或者是一個廣義表。
廣義表表頭和表尾的概念：
·若廣義表LS非空(n≥1)，則這個廣義表的第一個元素就是表頭。
·其余的元素組成的表稱為LS的表尾，所以表尾必是一個子表。
廣義表有兩種表示法，一種是括號表示法，一種是圖形表示法。
廣義表與樹(形結構)相對應，這個廣義表就是純表。
如果一個廣義表的結點又可以被其他結點所共享，則這個表稱為再入表。
允許遞歸的表稱為遞歸表。
線性表∈純表(樹)∈再入表∈遞歸表。可見，廣義表是對線性表和樹的推廣。
廣義表有兩個特殊的基本運算：
·取表頭head(LS)：取表中的第一個數據元素，不能對空表操作。
·取表尾tail(LS);取除表頭外，其余數據元素構成的子表，不能對空表操作。
第六章 樹
樹是n個結點的有限集合，非空時必須滿足：只有一個稱為根的結點;其余結點形成m個不相交的子集，并稱根的子樹。
根是開始結點;結點的子樹數稱度;度為0的結點稱葉子(終端結點);度不為0的結點稱分支結點(非終端結點);除根外的分支結點稱內部結點;
有序樹是子樹有左，右之分的樹;無序樹是子樹沒有左，右之分的樹;森林是m個互不相交的樹的集合;
樹的四種不同表示方法：
·樹形表示法;
·嵌套集合表示法;
·凹入表示法;
·廣義表表示法。
二叉樹的定義：是n≥0個結點的有限集，它是空集(n=0)或由一個根結點及兩棵互不相交的分別稱作這個根的左子樹和右子樹的二叉樹組成。
二叉樹不是樹的特殊情形，與度數為2的有序樹不同。
二叉樹的4個重要性質：
·二叉樹上第i層上的結點數目最多為2^(i-1)(i≥1);
·深度為k的二叉樹至多有(2^k)-1個結點(k≥1);
·在任意一棵二叉樹中，若終端結點的個數為n0，度為2的結點數為n2，則n0=n2+1;
·具有n個結點的完全二叉樹的深度為int(log2n)+1。滿二叉樹是一棵深度為k，結點數為(2^k)-1的二叉樹;完全二叉樹是滿二叉樹在最下層自右向左去處部分結點;
二叉樹的順序存儲結構就是把二叉樹的所有結點按照層次順序存儲到連續的存儲單元中。(存儲前先將其畫成完全二叉樹)
樹的存儲結構多用的是鏈式存儲。BinTNode的結構為lchild|data|rchild，把所有BinTNode類型的結點，加上一個指向根結點的BinTree型頭指針就構成了二叉樹的鏈式存儲結構，稱為二叉鏈表。它就是由根指針root唯一確定的。共有2n個指針域，n+1個空指針。
根據訪問結點的次序不同可得三種遍歷：先序遍歷(前序遍歷或先根遍歷)，中序遍歷(或中根遍歷)、后序遍歷(或后根遍歷)。時間復雜度為O(n)。
利用二叉鏈表中的n+1個空指針域來存放指向某種遍歷次序下的前趨結點和后繼結點的指針，這些附加的指針就稱為“線索”，加上線索的二叉鏈表就稱為線索鏈表。線索使得查找中序前趨和中序后繼變得簡單有效，但對于查找指定結點的前序前趨和后序后繼并沒有什么作用。
樹和森林及二叉樹的轉換是唯一對應的。
轉換方法：
·樹變二叉樹：兄弟相連，保留長子的連線。
·二叉樹變樹：結點的右孩子與其雙親連。
·森林變二叉樹：樹變二叉樹，各個樹的根相連。
樹的存儲結構：
·有雙親鏈表表示法：結點data | parent，對于求指定結點的雙親或祖先十分方便，但不適于求指定結點的孩子及后代。
·孩子鏈表表示法：為樹中每個結點data | next設置一個孩子鏈表firstchild，并將data | firstchild存放在一個向量中。
·雙親孩子鏈表表示法：將雙親鏈表和孩子鏈表結合。
·孩子兄弟鏈表表示法：結點結構leftmostchild |data | rightsibing，附加兩個分別指向該結點的最左孩子和右鄰兄弟的指針域。樹的前序遍歷與相對應的二叉樹的前序遍歷一致;樹的后序遍歷與相對應的二叉樹的中序遍歷一致。
樹的帶權路徑長度是樹中所有葉結點的帶權路徑長度之和。樹的帶權路徑長度最小的二叉樹就稱為最優二叉樹(即哈夫曼樹)。
在葉子的權值相同的二叉樹中，完全二叉樹的路徑長度最短。
哈夫曼樹有n個葉結點，共有2n-1個結點，沒有度為1的結點，這類樹又稱為嚴格二叉樹。
變長編碼技術可以使頻度高的字符編碼短，而頻度低的字符編碼長，但是變長編碼可能使解碼產生二義性。如00、01、0001這三個碼無法在解碼時確定是哪一個，所以要求在字符編碼時任一字符的編碼都不是其他字符編碼的前綴，這種碼稱為前綴碼(其實是非前綴碼)。
哈夫曼樹的應用最廣泛地是在編碼技術上，它能夠容易地求出給定字符集及其概率分布的最優前綴碼。哈夫曼編碼的構造很容易，只要畫好了哈夫曼樹，按分支情況在左路徑上寫代碼0，右路徑上寫代碼1，然后從上到下到葉結點的相應路徑上的代碼的序列就是該結點的最優前綴碼。
第四篇：2010年自學考試《數據結構》各章復習要點總結
2010年自學考試《數據結構》各章復習要點總結(2)2010年自學考試《數據結構》四至六章復習要點總結。
第四章 串
串是零個或多個字符組成的有限序列。
·空串：是指長度為零的串，也就是串中不包含任何字符(結點)。
·空白串：指串中包含一個或多個空格字符的串。
·在一個串中任意個連續字符組成的子序列稱為該串的子串，包含子串的串就稱為主串。
·子串在主串中的序號就是指子串在主串中首次出現的位置。
·空串是任意串的子串，任意串是自身的子串。
串分為兩種：
·串常量在程序中只能引用不能改變;
·串變量的值可以改變。
串的基本運算有：
·求串長strlen(char*s)
·串復制strcpy(char*to，char*from)
·串聯接strcat(char*to，char*from)
·串比較charcmp(char*s1，char*s2)
·字符定位strchr(char*s，charc)
。串是特殊的線性表(結點是字符)，所以串的存儲結構與線性表的存儲結構類似。串的順序存儲結構簡稱為順序串。
順序串又可按存儲分配的不同分為：
·靜態存儲分配：直接用定長的字符數組來定義。優點是涉及串長的操作速度快，但不適合插入、鏈接操作。
·動態存儲分配：是在定義串時不分配存儲空間，需要使用時按所需串的長度分配存儲單元。
串的鏈式存儲就是用單鏈表的方式存儲串值，串的這種鏈式存儲結構簡稱為鏈串。鏈串與單鏈表的差異只是它的結點數據域為單個字符。
為了解決“存儲密度”低的狀況，可以讓一個結點存儲多個字符，即結點的大小。
順序串上子串定位的運算：又稱串的“模式匹配”或“串匹配”，是在主串中查找出子串出現的位置。在串匹配中，將主串稱為目標(串)，子串稱為模式(串)。這是比較容易理解的，串匹配問題就是找出給定模式串P在給定目標串T中首次出現的有效位移或者是全部有效位移。最壞的情況下時間復雜度是O((n-m+1)m)，假如m與n同階的話則它是O(n^2)。鏈串上的子串定位運算位移是結點地址而不是整數。
第五章 多維數組和廣義表
數組一般用順序存儲的方式表示。存儲的方式有：
·行優先順序，也就是把數組逐行依次排列。PASCAL、C
·列優先順序，就是把數組逐列依次排列。FORTRAN
地址的計算方法：
·按行優先順序排列的數組：LOCa(ij)=LOCa(11)+((i-1)*n+(j-1))*d.·按列優先順序排列的數組：LOCa(ij)=LOCa(11)+((j-1)*n+(i-1))*d.矩陣的壓縮存儲：為多個相同的非零元素分配一個存儲空間;對零元素不分配空間。
特殊矩陣的概念：所謂特殊矩陣是指非零元素或零元素分布有一定規律的矩陣。
稀疏矩陣的概念：一個矩陣中若其非零元素的個數遠遠小于零元素的個數，則該矩陣稱為稀疏矩陣。
特殊矩陣的類型：
·對稱矩陣：滿足a(ij)=a(ji)。元素總數n(n+1)/2.I=max(i，j)，J=min(i，j)，LOCa(ij)=LOC(sa[0])+(I*(I+1)/2+J)*d.·三角矩陣：
·上三角陣：k=i*(2n-i+1)/2+j-i，LOCa(ij)=LOC(sa[0])+k*d.·下三角陣：k=i*(i+1)/2+j，LOCa(ij)=LOC(sa[0])+k*d.·對角矩陣：k=2i+j，LOCa(ij)=LOC(sa[0])+k*d.稀疏矩陣的壓縮存儲方式用三元組表把非零元素的值和它所在的行號列號做為一個結點存放在一起，用這些結點組成的一個線性表來表示。但這種壓縮存儲方式將失去隨機存儲功能。加入行表記錄每行的非零元素在三元組表中的起始位置，即帶行表的三元組表。
廣義表是n(n≥0)個元素的有限序列，其中的元素是原子或者是一個廣義表。
廣義表表頭和表尾的概念：
·若廣義表LS非空(n≥1)，則這個廣義表的第一個元素就是表頭。
·其余的元素組成的表稱為LS的表尾，所以表尾必是一個子表。
廣義表有兩種表示法，一種是括號表示法，一種是圖形表示法。
廣義表與樹(形結構)相對應，這個廣義表就是純表。
如果一個廣義表的結點又可以被其他結點所共享，則這個表稱為再入表。
允許遞歸的表稱為遞歸表。
線性表∈純表(樹)∈再入表∈遞歸表。可見，廣義表是對線性表和樹的推廣。
廣義表有兩個特殊的基本運算：
·取表頭head(LS)：取表中的第一個數據元素，不能對空表操作。
·取表尾tail(LS);取除表頭外，其余數據元素構成的子表，不能對空表操作。
第六章 樹
樹是n個結點的有限集合，非空時必須滿足：只有一個稱為根的結點;其余結點形成m個不相交的子集，并稱根的子樹。
根是開始結點;結點的子樹數稱度;度為0的結點稱葉子(終端結點);度不為0的結點稱分支結點(非終端結點);除根外的分支結點稱內部結點;
有序樹是子樹有左，右之分的樹;無序樹是子樹沒有左，右之分的樹;森林是m個互不相交的樹的集合;
樹的四種不同表示方法：
·樹形表示法;
·嵌套集合表示法;
·凹入表示法;
·廣義表表示法。
二叉樹的定義：是n≥0個結點的有限集，它是空集(n=0)或由一個根結點及兩棵互不相交的分別稱作這個根的左子樹和右子樹的二叉樹組成。
二叉樹不是樹的特殊情形，與度數為2的有序樹不同。
二叉樹的4個重要性質：
·二叉樹上第i層上的結點數目最多為2^(i-1)(i≥1);
·深度為k的二叉樹至多有(2^k)-1個結點(k≥1);
·在任意一棵二叉樹中，若終端結點的個數為n0，度為2的結點數為n2，則n0=n2+1;
·具有n個結點的完全二叉樹的深度為int(log2n)+1。滿二叉樹是一棵深度為k，結點數為(2^k)-1的二叉樹;完全二叉樹是滿二叉樹在最下層自右向左去處部分結點;
二叉樹的順序存儲結構就是把二叉樹的所有結點按照層次順序存儲到連續的存儲單元中。(存儲前先將其畫成完全二叉樹)
樹的存儲結構多用的是鏈式存儲。BinTNode的結構為lchild|data|rchild，把所有BinTNode類型的結點，加上一個指向根結點的BinTree型頭指針就構成了二叉樹的鏈式存儲結構，稱為二叉鏈表。它就是由根指針root唯一確定的。共有2n個指針域，n+1個空指針。
根據訪問結點的次序不同可得三種遍歷：先序遍歷(前序遍歷或先根遍歷)，中序遍歷(或中根遍歷)、后序遍歷(或后根遍歷)。時間復雜度為O(n)。
利用二叉鏈表中的n+1個空指針域來存放指向某種遍歷次序下的前趨結點和后繼結點的指針，這些附加的指針就稱為“線索”，加上線索的二叉鏈表就稱為線索鏈表。線索使得查找中序前趨和中序后繼變得簡單有效，但對于查找指定結點的前序前趨和后序后繼并沒有什么作用。
樹和森林及二叉樹的轉換是唯一對應的。
轉換方法：
·樹變二叉樹：兄弟相連，保留長子的連線。
·二叉樹變樹：結點的右孩子與其雙親連。
·森林變二叉樹：樹變二叉樹，各個樹的根相連。
樹的存儲結構：
·有雙親鏈表表示法：結點data | parent，對于求指定結點的雙親或祖先十分方便，但不適于求指定結點的孩子及后代。
·孩子鏈表表示法：為樹中每個結點data | next設置一個孩子鏈表firstchild，并將data | firstchild存放在一個向量中。
·雙親孩子鏈表表示法：將雙親鏈表和孩子鏈表結合。
·孩子兄弟鏈表表示法：結點結構leftmostchild |data | rightsibing，附加兩個分別指向該結點的最左孩子和右鄰兄弟的指針域。樹的前序遍歷與相對應的二叉樹的前序遍歷一致;樹的后序遍歷與相對應的二叉樹的中序遍歷一致。
樹的帶權路徑長度是樹中所有葉結點的帶權路徑長度之和。樹的帶權路徑長度最小的二叉樹就稱為最優二叉樹(即哈夫曼樹)。
在葉子的權值相同的二叉樹中，完全二叉樹的路徑長度最短。
哈夫曼樹有n個葉結點，共有2n-1個結點，沒有度為1的結點，這類樹又稱為嚴格二叉樹。
變長編碼技術可以使頻度高的字符編碼短，而頻度低的字符編碼長，但是變長編碼可能使解碼產生二義性。如00、01、0001這三個碼無法在解碼時確定是哪一個，所以要求在字符編碼時任一字符的編碼都不是其他字符編碼的前綴，這種碼稱為前綴碼(其實是非前綴碼)。
哈夫曼樹的應用最廣泛地是在編碼技術上，它能夠容易地求出給定字符集及其概率分布的最優前綴碼。哈夫曼編碼的構造很容易，只要畫好了哈夫曼樹，按分支情況在左路徑上寫代碼0，右路徑上寫代碼1，然后從上到下到葉結點的相應路徑上的代碼的序列就是該結點的最優前綴碼。
第五篇：2010年自學考試《數據結構》各章復習要點總結
數據結構各章復習要點總結
第一章 概 論
數據就是指能夠被計算機識別、存儲和加工處理的信息的載體。
數據元素是數據的基本單位，可以由若干個數據項組成。數據項是具有獨立含義的最小標識單位。
數據結構的定義：
·邏輯結構：從邏輯結構上描述數據，獨立于計算機。
·線性結構：一對一關系。
·線性結構：多對多關系。
·存儲結構：是邏輯結構用計算機語言的實現。
·順序存儲結構：如數組。
·鏈式存儲結構：如鏈表。
·稠密索引：每個結點都有索引項。
·稀疏索引：每組結點都有索引項。
·散列存儲結構：如散列表。
·對數據的操作：定義在邏輯結構上，每種邏輯結構都有一個運算集合。
·常用的有：檢索、插入、刪除、更新、排序。
·數據類型：是一個值的集合以及在這些值上定義的一組操作的總稱。
·原子類型：由語言提供。
·結構類型：由用戶借助于描述機制定義，是導出類型。
抽象數據類型ADT：
·是抽象數據的組織和與之的操作。相當于在概念層上描述問題。
·優點是將數據和操作封裝在一起實現了信息隱藏。
程序設計的實質是對實際問題選擇一種好的數據結構，設計一個好的算法。算法取決于數據結構。
算法是一個良定義的計算過程，以一個或多個值輸入，并以一個或多個值輸出。
評價算法的好壞的因素：
·算法是正確的;
·執行算法的時間;
·執行算法的存儲空間(主要是輔助存儲空間);
·算法易于理解、編碼、調試。
時間復雜度：是某個算法的時間耗費，它是該算法所求解問題規模n的函數。
漸近時間復雜度：是指當問題規模趨向無窮大時，該算法時間復雜度的數量級。
評價一個算法的時間性能時，主要標準就是算法的漸近時間復雜度。
算法中語句的頻度不僅與問題規模有關，還與輸入實例中各元素的取值相關。
時間復雜度按數量級遞增排列依次為：常數階O(1)、對數階O(log2n)、線性階O(n)、線性對數階O(nlog2n)、平方階O(n^2)、立方階O(n^3)、……k次方階O(n^k)、指數階O(2^n)。
空間復雜度：是某個算法的空間耗費，它是該算法所求解問題規模n的函數。
算法的時間復雜度和空間復雜度合稱算法復雜度。
第二章 線性表
線性表是由n≥0個數據元素組成的有限序列。n=0是空表;非空表，只能有一個開始結點，有且只能有一個終端結點。
線性表上定義的基本運算：
·構造空表：Initlist(L)
·求表長：Listlength(L)
·取結點：GetNode(L，i)
·查找：LocateNode(L，x)
·插入：InsertList(L，x，i)
·刪除：Delete(L，i)
順序表是按線性表的邏輯結構次序依次存放在一組地址連續的存儲單元中。在存儲單元中的各元素的物理位置和邏輯結構中各結點相鄰關系是一致的。地址計算：LOCa(i)=LOCa(1)+(i-1)*d;(首地址為1)/考試 大收集整理/
在順序表中實現的基本運算：
·插入：平均移動結點次數為n/2;平均時間復雜度均為O(n)。
·刪除：平均移動結點次數為(n-1)/2;平均時間復雜度均為O(n)。
線性表的鏈式存儲結構中結點的邏輯次序和物理次序不一定相同，為了能正確表示結點間的邏輯關系，在存儲每個結點值的同時，還存儲了其后繼結點的地址信息(即指針或鏈)。這兩部分信息組成鏈表中的結點結構。一個單鏈表由頭指針的名字來命名。
單鏈表運算：
·建立單鏈表
·頭插法：s->next=head;head=s;生成的順序與輸入順序相反。平均時間復雜度均為O(n)。
·尾插法：head=rear=null;if(head=null)head=s;else r->next=s;r=s;平均時間復雜度均為O(n)
·加頭結點的算法：對開始結點的操作無需特殊處理，統一了空表和非空表。
·查找
·按序號：與查找位置有關，平均時間復雜度均為O(n)。
·按值：與輸入實例有關，平均時間復雜度均為O(n)。
·插入運算：p=GetNode(L，i-1);s->next=p->next;p->next=s;平均時間復雜度均為O(n)
·刪除運算：p=GetNode(L，i-1);r=p->next;p->next=r->next;free(r);平均時間復雜度均為O(n)
單循環鏈表是一種首尾相接的單鏈表，終端結點的指針域指向開始結點或頭結點。鏈表終止條件是以指針等于頭指針或尾指針。
采用單循環鏈表在實用中多采用尾指針表示單循環鏈表。優點是查找頭指針和尾指針的時間都是O(1)，不用遍歷整個鏈表。
雙鏈表就是雙向鏈表，就是在單鏈表的每個結點里再增加一個指向其直接前趨的指針域prior，形成兩條不同方向的鏈。由頭指針head惟一確定。
雙鏈表也可以頭尾相鏈接構成雙(向)循環鏈表。
雙鏈表上的插入和刪除時間復雜度均為O(1)。
順序表和鏈表的比較：
·基于空間：
·順序表的存儲空間是靜態分配，存儲密度為1;適于線性表事先確定其大小時采用。
·鏈表的存儲空間是動態分配，存儲密度<1;適于線性表長度變化大時采用。
·基于時間：
·順序表是隨機存儲結構，當線性表的操作主要是查找時，宜采用。
·以插入和刪除操作為主的線性表宜采用鏈表做存儲結構。
·若插入和刪除主要發生在表的首尾兩端，則宜采用尾指針表示的單循環鏈表。
第三章 棧和隊列
棧(Stack)是僅限制在表的一端進行插入和刪除運算的線性表，稱插入、刪除這一端為棧頂，另一端稱為棧底。表中無元素時為空棧。棧的修改是按后進先出的原則進行的，我們又稱棧為LIFO表(Last In First Out)。通常棧有順序棧和鏈棧兩種存儲結構。
棧的基本運算有六種：
·構造空棧：InitStack(S)
·判棧空：StackEmpty(S)
·判棧滿：StackFull(S)
·進棧：Push(S，x)
·退棧：Pop(S)
·取棧頂元素：StackTop(S)在順序棧中有“上溢”和“下溢”的現象。
·“上溢”是棧頂指針指出棧的外面是出錯狀態。
·“下溢”可以表示棧為空棧，因此用來作為控制轉移的條件。
順序棧中的基本操作有六種：
·構造空棧
·判棧空
·判棧滿
·進棧
·退棧
·取棧頂元素
鏈棧則沒有上溢的限制，因此進棧不要判棧滿。鏈棧不需要在頭部附加頭結點，只要有鏈表的頭指針就可以了。
鏈棧中的基本操作有五種：
·構造空棧
·判棧空
·進棧
·退棧
·取棧頂元素
隊列(Queue)是一種運算受限的線性表，插入在表的一端進行，而刪除在表的另一端進行，允許刪除的一端稱為隊頭(front)，允許插入的一端稱為隊尾(rear)，隊列的操作原則是先進先出的，又稱作FIFO表(First In First Out).隊列也有順序存儲和鏈式存儲兩種存儲結構。
隊列的基本運算有六種：
·置空隊：InitQueue(Q)
·判隊空：QueueEmpty(Q)
·判隊滿：QueueFull(Q)
·入隊：EnQueue(Q，x)
·出隊：DeQueue(Q)
·取隊頭元素：QueueFront(Q)
順序隊列的“假上溢”現象：由于頭尾指針不斷前移，超出向量空間。這時整個向量空間及隊列是空的卻產生了“上溢”現象。
為了克服“假上溢”現象引入循環向量的概念，是把向量空間形成一個頭尾相接的環形，這時隊列稱循環隊列。
判定循環隊列是空還是滿，方法有三種：
·一種是另設一個布爾變量來判斷;
·第二種是少用一個元素空間，入隊時先測試((rear+1)%m = front)? 滿：空;
·第三種就是用一個計數器記錄隊列中的元素的總數。
隊列的鏈式存儲結構稱為鏈隊列，一個鏈隊列就是一個操作受限的單鏈表。為了便于在表尾進行插入(入隊)的操作，在表尾增加一個尾指針，一個鏈隊列就由一個頭指針和一個尾指針唯一地確定。鏈隊列不存在隊滿和上溢的問題。在鏈隊列的出隊算法中，要注意當原隊中只有一個結點時，出隊后要同進修改頭尾指針并使隊列變空。
點擊咨詢 