希爾排序適用於鏈式存儲嗎

『壹』 希爾排序法特點

希爾排序的實質就是分組插入排序，該方法又稱縮小增量排序，因希爾於1959年提出而得名。該方法的基本思想是：先將整個待排元素序列分割成若干個子序列，由相隔某個「增量」的元素組成的，分別進行直接插入排序，然後依次縮減增量再進行排序，待整個序列中的元素基本有序，增量足夠小時，再對全體元素進行一次直接插入排序。因為直接插入排序在元素基本有序的情況下，接近最好情況，效率是很高的，因此希爾排序在時間效率上比前兩種方法有較大提高。希爾排序法屬於插入類排序，是將整個無序列分割成若干小的子序列分別進行插入排序的方法。希爾排序的特點
希爾排序演算法與步長有直接關系。步長依次遞減，數組的局部越來越有序了。希爾排序演算法思想
因為希爾排序是通過比較相距一定間隔的元素來工作的。所以先要自定義步長的范圍。然後選擇一個當前元素，依次按照步長來尋找指定步長的元素進行比較，比較選擇出最小的元素，如果比當前元素小於指定步長的元素，就進行交換，相反就退出當前的循環查找比較。

『貳』 1． 用c語言編寫順序存儲結構下的順序查找法和鏈式存儲結構下的順序查找法。

是啊！而且非常重要它在筆試中佔30%！！！
這是我找到的一些資料：第一章 數據結構與演算法
1.1 演算法
1、演算法是指解題方案的准確而完整的描述。換句話說，演算法是對特定問題求解步驟的一種描述。
*：演算法不等於程序，也不等於計算方法。程序的編制不可能優於演算法的設計。
2、演算法的基本特徵
（1）可行性。針對實際問題而設計的演算法，執行後能夠得到滿意的結果。
（2）確定性。每一條指令的含義明確，無二義性。並且在任何條件下，演算法只有唯一的一條執行路徑，即相同的輸入只能得出相同的輸出。
（3）有窮性。演算法必須在有限的時間內完成。有兩重含義，一是演算法中的操作步驟為有限個，二是每個步驟都能在有限時間內完成。
（4）擁有足夠的情報。演算法中各種運算總是要施加到各個運算對象上，而這些運算對象又可能具有某種初始狀態，這就是演算法執行的起點或依據。因此，一個演算法執行的結果總是與輸入的初始數據有關，不同的輸入將會有不同的結果輸出。當輸入不夠或輸入錯誤時，演算法將無法執行或執行有錯。一般說來，當演算法擁有足夠的情報時，此演算法才是有效的；而當提供的情報不夠時，演算法可能無效。
*：綜上所述，所謂演算法，是一組嚴謹地定義運算順序的規則，並且每一個規則都是有效的，且是明確的，此順序將在有限的次數下終止。
3、演算法復雜度主要包括時間復雜度和空間復雜度。
（1）演算法時間復雜度是指執行演算法所需要的計算工作量，可以用執行演算法的過程中所需基本運算的執行次數來度量。
（2）演算法空間復雜度是指執行這個演算法所需要的內存空間。
1.2 數據結構的基本概念
1、數據結構是指相互有關聯的數據元素的集合。
2、數據結構主要研究和討論以下三個方面的問題：
（1）數據集合中各數據元素之間所固有的邏輯關系，即數據的邏輯結構。
數據的邏輯結構包含：1）表示數據元素的信息；2）表示各數據元素之間的前後件關系。
（2）在對數據進行處理時，各數據元素在計算機中的存儲關系，即數據的存儲結構。
數據的存儲結構有順序、鏈接、索引等。
1）順序存儲。它是把邏輯上相鄰的結點存儲在物理位置相鄰的存儲單元里，結點間的邏輯關系由存儲單元的鄰接關系來體現。由此得到的存儲表示稱為順序存儲結構。
2）鏈接存儲。它不要求邏輯上相鄰的結點在物理位置上亦相鄰，結點間的邏輯關系是由附加的指針欄位表示的。由此得到的存儲表示稱為鏈式存儲結構。
3）索引存儲：除建立存儲結點信息外，還建立附加的索引表來標識結點的地址。
*：數據的邏輯結構反映數據元素之間的邏輯關系，數據的存儲結構（也稱數據的物理結構）是數據的邏輯結構在計算機存儲空間中的存放形式。同一種邏輯結構的數據可以採用不同的存儲結構，但影響數據處理效率。
（3）對各種數據結構進行的運算。
3、數據結構的圖形表示
一個數據結構除了用二元關系表示外，還可以直觀地用圖形表示。在數據結構的圖形表示中，對於數據集合D中的每一個數據元素用中間標有元素值的方框表示，一般稱之為數據結點，並簡稱為結點；為了進一步表示各數據元素之間的前後件關系，對於關系R中的每一個二元組，用一條有向線段從前件結點指向後件結點。
4、數據結構分為兩大類型：線性結構和非線性結構。
（1）線性結構（非空的數據結構）條件：1）有且只有一個根結點；2）每一個結點最多有一個前件，也最多有一個後件。
*：常見的線性結構有線性表、棧、隊列和線性鏈表等。
（2）非線性結構：不滿足線性結構條件的數據結構。
*：常見的非線性結構有樹、二叉樹和圖等。
1.3 線性表及其順序存儲結構
1、線性表由一組數據元素構成，數據元素的位置只取決於自己的序號，元素之間的相對位置是線性的。線性表是由n(n≥0)個數據元素組成的一個有限序列，表中的每一個數據元素，除了第一個外，有且只有一個前件，除了最後一個外，有且只有一個後件。線性表中數據元素的個數稱為線性表的長度。線性表可以為空表。
*：線性表是一種存儲結構，它的存儲方式：順序和鏈式。
2、線性表的順序存儲結構具有兩個基本特點：（1）線性表中所有元素所佔的存儲空間是連續的；（2）線性表中各數據元素在存儲空間中是按邏輯順序依次存放的。
*：由此可以看出，在線性表的順序存儲結構中，其前後件兩個元素在存儲空間中是緊鄰的，且前件元素一定存儲在後件元素的前面，可以通過計算機直接確定第i個結點的存儲地址。
3、順序表的插入、刪除運算（學吧學吧獨家稿件）
（1）順序表的插入運算：在一般情況下，要在第i（1≤i≤n）個元素之前插入一個新元素時，首先要從最後一個（即第n個）元素開始，直到第i個元素之間共n-i+1個元素依次向後移動一個位置，移動結束後，第i個位置就被空出，然後將新元素插入到第i項。插入結束後，線性表的長度就增加了1。
*：順性表的插入運算時需要移動元素，在等概率情況下，平均需要移動n/2個元素。
（2）順序表的刪除運算：在一般情況下，要刪除第i（1≤i≤n）個元素時，則要從第i+1個元素開始，直到第n個元素之間共n-i個元素依次向前移動一個位置。刪除結束後，線性表的長度就減小了1。
*：進行順性表的刪除運算時也需要移動元素，在等概率情況下，平均需要移動（n-1）/2個元素。插入、刪除運算不方便。
1.4 棧和隊列
1、棧及其基本運算（學吧學吧獨家稿件）
棧是限定在一端進行插入與刪除運算的線性表。
在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧頂元素總是最後被插入的元素，棧底元素總是最先被插入的元素。即棧是按照「先進後出」或「後進先出」的原則組織數據的。
棧具有記憶作用。
棧的基本運算：1）插入元素稱為入棧運算；2）刪除元素稱為退棧運算；3）讀棧頂元素是將棧頂元素賦給一個指定的變數，此時指針無變化。
棧的存儲方式和線性表類似，也有兩種，即順序棧和鏈式棧。
2、隊列及其基本運算
隊列是指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。尾指針（Rear）指向隊尾元素，頭指針（front）指向排頭元素的前一個位置（隊頭）。
隊列是「先進先出」或「後進後出」的線性表。
隊列運算包括：1）入隊運算：從隊尾插入一個元素；2）退隊運算：從隊頭刪除一個元素。
循環隊列及其運算：所謂循環隊列，就是將隊列存儲空間的最後一個位置繞到第一個位置，形成邏輯上的環狀空間，供隊列循環使用。在循環隊列中，用隊尾指針rear指向隊列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置，因此，從頭指針front指向的後一個位置直到隊尾指針rear指向的位置之間，所有的元素均為隊列中的元素。
*：循環隊列中元素的個數=rear-front。
1.5 線性鏈表（學吧學吧獨家稿件）
1、線性表順序存儲的缺點（學吧學吧獨家稿件）：（1）插入或刪除的運算效率很低。在順序存儲的線性表中，插入或刪除數據元素時需要移動大量的數據元素；（2）線性表的順序存儲結構下，線性表的存儲空間不便於擴充；（3）線性表的順序存儲結構不便於對存儲空間的動態分配。
2、線性鏈表：線性表的鏈式存儲結構稱為線性鏈表，是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接來實現的。因此，在鏈式存儲方式中，每個結點由兩部分組成：一部分用於存放數據元素的值，稱為數據域；另一部分用於存放指針，稱為指針域，用於指向該結點的前一個或後一個結點（即前件或後件），如下圖所示：

線性鏈表分為單鏈表、雙向鏈表和循環鏈表三種類型。
在單鏈表中，每一個結點只有一個指針域，由這個指針只能找到其後件結點，而不能找到其前件結點。因此，在某些應用中，對於線性鏈表中的每個結點設置兩個指針，一個稱為左指針，指向其前件結點；另一個稱為右指針，指向其後件結點，這種鏈表稱為雙向鏈表，如下圖所示：

3、線性鏈表的基本運算
（1）在線性鏈表中包含指定元素的結點之前插入一個新元素。
*：在線性鏈表中插入元素時，不需要移動數據元素，只需要修改相關結點指針即可，也不會出現「上溢」現象（學吧學吧獨家稿件）。
（2）在線性鏈表中刪除包含指定元素的結點。
*：在線性鏈表中刪除元素時，也不需要移動數據元素，只需要修改相關結點指針即可。
（3）將兩個線性鏈表按要求合並成一個線性鏈表。
（4）將一個線性鏈表按要求進行分解。
（5）逆轉線性鏈表。
（6）復制線性鏈表。
（7）線性鏈表的排序。
（8）線性鏈表的查找。
*：線性鏈表不能隨機存取。
4、循環鏈表及其基本運算
在線性鏈表中，其插入與刪除的運算雖然比較方便，但還存在一個問題，在運算過程中對於空表和對第一個結點的處理必須單獨考慮，使空表與非空表的運算不統一。為了克服線性鏈表的這個缺點，可以採用另一種鏈接方式，即循環鏈表。
與前面所討論的線性鏈表相比，循環鏈表具有以下兩個特點：1）在鏈表中增加了一個表頭結點，其數據域為任意或者根據需要來設置，指針域指向線性表的第一個元素的結點，而循環鏈表的頭指針指向表頭結點；2）循環鏈表中最後一個結點的指針域不是空，而是指向表頭結點。即在循環鏈表中，所有結點的指針構成了一個環狀鏈。
下圖a是一個非空的循環鏈表，圖b是一個空的循環鏈表：

循環鏈表的優點主要體現在兩個方面：一是在循環鏈表中，只要指出表中任何一個結點的位置，就可以從它出發訪問到表中其他所有的結點，而線性單鏈表做不到這一點；二是由於在循環鏈表中設置了一個表頭結點，在任何情況下，循環鏈表中至少有一個結點存在，從而使空表與非空表的運算統一。
*：循環鏈表是在單鏈表的基礎上增加了一個表頭結點，其插入和刪除運算與單鏈表相同。但它可以從任一結點出發來訪問表中其他所有結點，並實現空表與非空表的運算的統一。
1.6 樹與二叉樹（學吧學吧獨家稿件）
1、樹的基本概念
樹是一種簡單的非線性結構。在樹這種數據結構中，所有數據元素之間的關系具有明顯的層次特性。
在樹結構中，每一個結點只有一個前件，稱為父結點。沒有前件的結點只有一個，稱為樹的根結點，簡稱樹的根。每一個結點可以有多個後件，稱為該結點的子結點。沒有後件的結點稱為葉子結點。
在樹結構中，一個結點所擁有的後件的個數稱為該結點的度，所有結點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。
2、二叉樹及其基本性質
（1）什麼是二叉樹
二叉樹是一種很有用的非線性結構，它具有以下兩個特點：1）非空二叉樹只有一個根結點；2）每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。
*：根據二叉樹的概念可知，二叉樹的度可以為0（葉結點）、1（只有一棵子樹）或2（有2棵子樹）。
（2）二叉樹的基本性質（學吧學吧獨家稿件）
性質1 在二叉樹的第k層上，最多有 個結點。
性質2 深度為m的二叉樹最多有個 個結點。
性質3 在任意一棵二叉樹中，度數為0的結點（即葉子結點）總比度為2的結點多一個。性質4 具有n個結點的二叉樹，其深度至少為 ，其中 表示取 的整數部分。
3、滿二叉樹與完全二叉樹
滿二叉樹：除最後一層外，每一層上的所有結點都有兩個子結點。
完全二叉樹：除最後一層外，每一層上的結點數均達到最大值；在最後一層上只缺少右邊的若干結點。
*：根據完全二叉樹的定義可得出：度為1的結點的個數為0或1。
下圖a表示的是滿二叉樹，下圖b表示的是完全二叉樹：

完全二叉樹還具有如下兩個特性：
性質5 具有n個結點的完全二叉樹深度為 。
性質6 設完全二叉樹共有n個結點，如果從根結點開始，按層序（每一層從左到右）用自然數1，2，…，n給結點進行編號，則對於編號為k（k=1，2，…，n）的結點有以下結論：
①若k=1，則該結點為根結點，它沒有父結點；若k>1，則該結點的父結點的編號為INT(k/2)。
②若2k≤n，則編號為k的左子結點編號為2k；否則該結點無左子結點（顯然也沒有右子結點）。
③若2k+1≤n，則編號為k的右子結點編號為2k+1；否則該結點無右子結點。
4、二叉樹的存儲結構
在計算機中，二叉樹通常採用鏈式存儲結構。
與線性鏈表類似，用於存儲二叉樹中各元素的存儲結點也由兩部分組成：數據域和指針域。但在二叉樹中，由於每一個元素可以有兩個後件（即兩個子結點），因此，用於存儲二叉樹的存儲結點的指針域有兩個：一個用於指向該結點的左子結點的存儲地址，稱為左指針域；另一個用於指向該結點的右子結點的存儲地址，稱為右指針域。
*：一般二叉樹通常採用鏈式存儲結構，對於滿二叉樹與完全二叉樹來說，可以按層序進行順序存儲。
5、二叉樹的遍歷（學吧學吧獨家稿件）
二叉樹的遍歷是指不重復地訪問二叉樹中的所有結點。二叉樹的遍歷可以分為以下三種：
（1）前序遍歷（DLR）：若二叉樹為空，則結束返回。否則：首先訪問根結點，然後遍歷左子樹，最後遍歷右子樹；並且，在遍歷左右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹。
（2）中序遍歷（LDR）：若二叉樹為空，則結束返回。否則：首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹；並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。
（3）後序遍歷（LRD）：若二叉樹為空，則結束返回。否則：首先遍歷左子樹，然後遍歷右子樹，最後訪問根結點，並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後遍歷右子樹，最後訪問根結點。
1.7 查找技術（學吧學吧獨家稿件）
查找：根據給定的某個值，在查找表中確定一個其關鍵字等於給定值的數據元素。
查找結果：（查找成功：找到；查找不成功：沒找到。）
平均查找長度：查找過程中關鍵字和給定值比較的平均次數。
1、順序查找
基本思想：從表中的第一個元素開始，將給定的值與表中逐個元素的關鍵字進行比較，直到兩者相符，查到所要找的元素為止。否則就是表中沒有要找的元素，查找不成功。
在平均情況下，利用順序查找法在線性表中查找一個元素，大約要與線性表中一半的元素進行比較，最壞情況下需要比較n次。
順序查找一個具有n個元素的線性表，其平均復雜度為O（n）。
下列兩種情況下只能採用順序查找：
1）如果線性表是無序表（即表中的元素是無序的），則不管是順序存儲結構還是鏈式存儲結構，都只能用順序查找。
2）即使是有序線性表，如果採用鏈式存儲結構，也只能用順序查找。
2、二分法查找
思想：先確定待查找記錄所在的范圍，然後逐步縮小范圍，直到找到或確認找不到該記錄為止。
前提：必須在具有順序存儲結構的有序表中進行。
查找過程：
1）若中間項（中間項mid=(n-1)/2，mid的值四捨五入取整）的值等於x，則說明已查到；
2）若x小於中間項的值，則在線性表的前半部分查找；
3）若x大於中間項的值，則在線性表的後半部分查找。
特點：比順序查找方法效率高。最壞的情況下，需要比較log2n次。
*：二分法查找只適用於順序存儲的線性表，且表中元素必須按關鍵字有序（升序）排列。對於無序線性表和線性表的鏈式存儲結構只能用順序查找。在長度為n的有序線性表中進行二分法查找，其時間復雜度為O（log2n）。
1.8 排序技術（學吧學吧獨家稿件）
排序是指將一個無序序列整理成按值非遞減順序排列的有序序列，即是將無序的記錄序列調整為有序記錄序列的一種操作。
1、交換類排序法（方法：冒泡排序，快速排序）。
2、插入類排序法（方法：簡單插入排序，希爾排序）。
3、選擇類排序法（方法：簡單選擇排序，堆排序）。
總結：各種排序法比較：

本章應考點撥：本章內容在筆試中會出現5-6個題目，是公共基礎知識部分出題量比較多的一章，所佔分值也比較大，約10分。

『叄』 常用的數據排序演算法有哪些,各有什麼特點舉例結合一種排序演算法並應用數組進行數據排序。

排序簡介
排序是數據處理中經常使用的一種重要運算,在計算機及其應用系統中,花費在排序上的時間在系統運行時間中佔有很大比重;並且排序本身對推動演算法分析的發展也起很大作用。目前已有上百種排序方法，但尚未有一個最理想的盡如人意的方法，本章介紹常用的如下排序方法，並對它們進行分析和比較。

1、插入排序（直接插入排序、折半插入排序、希爾排序）；
2、交換排序（起泡排序、快速排序）；
3、選擇排序（直接選擇排序、堆排序）；
4、歸並排序；
5、基數排序；

學習重點
1、掌握排序的基本概念和各種排序方法的特點，並能加以靈活應用；
2、掌握插入排序(直接插入排序、折半插入排序、希爾排序)、交換排序（起泡排序、快速排序）、選擇排序（直接選擇排序、堆排序）、二路歸並排序的方法及其性能分析方法；
3、了解基數排序方法及其性能分析方法。

排序（sort）或分類

所謂排序，就是要整理文件中的記錄，使之按關鍵字遞增(或遞減)次序排列起來。其確切定義如下：
輸入：n個記錄R1，R2，…，Rn，其相應的關鍵字分別為K1，K2，…，Kn。
輸出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。

1．被排序對象--文件
被排序的對象--文件由一組記錄組成。
記錄則由若干個數據項(或域)組成。其中有一項可用來標識一個記錄，稱為關鍵字項。該數據項的值稱為關鍵字(Key)。
注意：
在不易產生混淆時，將關鍵字項簡稱為關鍵字。

2．排序運算的依據--關鍵字
用來作排序運算依據的關鍵字，可以是數字類型，也可以是字元類型。
關鍵字的選取應根據問題的要求而定。
【例】在高考成績統計中將每個考生作為一個記錄。每條記錄包含准考證號、姓名、各科的分數和總分數等項內容。若要惟一地標識一個考生的記錄，則必須用"准考證號"作為關鍵字。若要按照考生的總分數排名次，則需用"總分數"作為關鍵字。

排序的穩定性

當待排序記錄的關鍵字均不相同時，排序結果是惟一的，否則排序結果不唯一。
在待排序的文件中，若存在多個關鍵字相同的記錄，經過排序後這些具有相同關鍵字的記錄之間的相對次序保持不變，該排序方法是穩定的；若具有相同關鍵字的記錄之間的相對次序發生變化，則稱這種排序方法是不穩定的。
注意：
排序演算法的穩定性是針對所有輸入實例而言的。即在所有可能的輸入實例中，只要有一個實例使得演算法不滿足穩定性要求，則該排序演算法就是不穩定的。

排序方法的分類

1．按是否涉及數據的內、外存交換分
在排序過程中，若整個文件都是放在內存中處理，排序時不涉及數據的內、外存交換，則稱之為內部排序(簡稱內排序)；反之，若排序過程中要進行數據的內、外存交換，則稱之為外部排序。
注意：
① 內排序適用於記錄個數不很多的小文件
② 外排序則適用於記錄個數太多，不能一次將其全部記錄放人內存的大文件。

2．按策略劃分內部排序方法
可以分為五類：插入排序、選擇排序、交換排序、歸並排序和分配排序。

排序演算法分析

1．排序演算法的基本操作
大多數排序演算法都有兩個基本的操作：
(1) 比較兩個關鍵字的大小；
(2) 改變指向記錄的指針或移動記錄本身。
注意：
第(2)種基本操作的實現依賴於待排序記錄的存儲方式。

2．待排文件的常用存儲方式
（1） 以順序表(或直接用向量)作為存儲結構
排序過程：對記錄本身進行物理重排（即通過關鍵字之間的比較判定，將記錄移到合適的位置）

（2） 以鏈表作為存儲結構
排序過程：無須移動記錄，僅需修改指針。通常將這類排序稱為鏈表(或鏈式)排序；

（3） 用順序的方式存儲待排序的記錄，但同時建立一個輔助表(如包括關鍵字和指向記錄位置的指針組成的索引表)
排序過程：只需對輔助表的表目進行物理重排（即只移動輔助表的表目，而不移動記錄本身）。適用於難於在鏈表上實現，仍需避免排序過程中移動記錄的排序方法。

3．排序演算法性能評價
（1） 評價排序演算法好壞的標准
評價排序演算法好壞的標准主要有兩條：
① 執行時間和所需的輔助空間
② 演算法本身的復雜程度

（2） 排序演算法的空間復雜度
若排序演算法所需的輔助空間並不依賴於問題的規模n，即輔助空間是O(1)，則稱之為就地排序(In-PlaceSou)。
非就地排序一般要求的輔助空間為O(n)。

（3） 排序演算法的時間開銷
大多數排序演算法的時間開銷主要是關鍵字之間的比較和記錄的移動。有的排序演算法其執行時間不僅依賴於問題的規模，還取決於輸入實例中數據的狀態。

文件的順序存儲結構表示

#define n l00 //假設的文件長度，即待排序的記錄數目
typedef int KeyType； //假設的關鍵字類型
typedef struct{ //記錄類型
KeyType key； //關鍵字項
InfoType otherinfo；//其它數據項，類型InfoType依賴於具體應用而定義
}RecType；
typedef RecType SeqList[n+1]；//SeqList為順序表類型，表中第0個單元一般用作哨兵
注意：
若關鍵字類型沒有比較算符，則可事先定義宏或函數來表示比較運算。
【例】關鍵字為字元串時，可定義宏"#define LT(a，b)(Stromp((a)，(b))<0)"。那麼演算法中"a<b"可用"LT(a，b)"取代。若使用C++，則定義重載的算符"<"更為方便。

按平均時間將排序分為四類：

（1）平方階(O(n2))排序
一般稱為簡單排序，例如直接插入、直接選擇和冒泡排序；

（2）線性對數階(O(nlgn))排序
如快速、堆和歸並排序；

（3）O(n1+￡)階排序
￡是介於0和1之間的常數，即0<￡<1，如希爾排序；

（4）線性階(O(n))排序
如桶、箱和基數排序。

各種排序方法比較

簡單排序中直接插入最好，快速排序最快，當文件為正序時，直接插入和冒泡均最佳。

影響排序效果的因素

因為不同的排序方法適應不同的應用環境和要求，所以選擇合適的排序方法應綜合考慮下列因素：
①待排序的記錄數目n；
②記錄的大小(規模)；
③關鍵字的結構及其初始狀態；
④對穩定性的要求；
⑤語言工具的條件；
⑥存儲結構；
⑦時間和輔助空間復雜度等。

不同條件下，排序方法的選擇

(1)若n較小(如n≤50)，可採用直接插入或直接選擇排序。
當記錄規模較小時，直接插入排序較好；否則因為直接選擇移動的記錄數少於直接插人，應選直接選擇排序為宜。
(2)若文件初始狀態基本有序(指正序)，則應選用直接插人、冒泡或隨機的快速排序為宜；
(3)若n較大，則應採用時間復雜度為O(nlgn)的排序方法：快速排序、堆排序或歸並排序。
快速排序是目前基於比較的內部排序中被認為是最好的方法，當待排序的關鍵字是隨機分布時，快速排序的平均時間最短；
堆排序所需的輔助空間少於快速排序，並且不會出現快速排序可能出現的最壞情況。這兩種排序都是不穩定的。
若要求排序穩定，則可選用歸並排序。但本章介紹的從單個記錄起進行兩兩歸並的 排序演算法並不值得提倡，通常可以將它和直接插入排序結合在一起使用。先利用直接插入排序求得較長的有序子文件，然後再兩兩歸並之。因為直接插入排序是穩定的，所以改進後的歸並排序仍是穩定的。

4)在基於比較的排序方法中，每次比較兩個關鍵字的大小之後，僅僅出現兩種可能的轉移，因此可以用一棵二叉樹來描述比較判定過程。
當文件的n個關鍵字隨機分布時，任何藉助於"比較"的排序演算法，至少需要O(nlgn)的時間。
箱排序和基數排序只需一步就會引起m種可能的轉移，即把一個記錄裝入m個箱子之一，因此在一般情況下，箱排序和基數排序可能在O(n)時間內完成對n個記錄的排序。但是，箱排序和基數排序只適用於像字元串和整數這類有明顯結構特徵的關鍵字，而當關鍵字的取值范圍屬於某個無窮集合(例如實數型關鍵字)時，無法使用箱排序和基數排序，這時只有藉助於"比較"的方法來排序。
若n很大，記錄的關鍵字位數較少且可以分解時，採用基數排序較好。雖然桶排序對關鍵字的結構無要求，但它也只有在關鍵字是隨機分布時才能使平均時間達到線性階，否則為平方階。同時要注意，箱、桶、基數這三種分配排序均假定了關鍵字若為數字時，則其值均是非負的，否則將其映射到箱(桶)號時，又要增加相應的時間。
(5)有的語言(如Fortran，Cobol或Basic等)沒有提供指針及遞歸，導致實現歸並、快速(它們用遞歸實現較簡單)和基數(使用了指針)等排序演算法變得復雜。此時可考慮用其它排序。
(6)本章給出的排序演算法，輸人數據均是存儲在一個向量中。當記錄的規模較大時，為避免耗費大量的時間去移動記錄，可以用鏈表作為存儲結構。譬如插入排序、歸並排序、基數排序都易於在鏈表上實現，使之減少記錄的移動次數。但有的排序方法，如快速排序和堆排序，在鏈表上卻難於實現，在這種情況下，可以提取關鍵字建立索引表，然後對索引表進行排序。然而更為簡單的方法是：引人一個整型向量t作為輔助表，排序前令t[i]=i(0≤i<n)，若排序演算法中要求交換R[i]和R[j]，則只需交換t[i]和t[j]即可；排序結束後，向量t就指示了記錄之間的順序關系：
R[t[0]].key≤R[t[1]].key≤…≤R[t[n-1]].key
若要求最終結果是：
R[0].key≤R[1].key≤…≤R[n-1].key
則可以在排序結束後，再按輔助表所規定的次序重排各記錄，完成這種重排的時間是O(n)。

『肆』 計算機二級選擇題干貨（五）——數據結構和演算法

1、線性表、棧和隊列等數據結構所表達和處理的數據以線性結構為組織形式。棧是一種特殊的線性表，這種線性表只能在固定的一端進行插入和刪除操作，允許插入和刪除的一端稱為棧頂，另一端稱為棧底。一個新元素只能從棧頂一端進入，刪除時，只能刪除棧頂的元素，即剛剛被插入的元素。所以棧又稱後進先出表（Last In First Out）；隊列可看作是插入在一端進行，刪除在另一端進行的線性表，允許插入的一端稱為隊尾，允許刪除的一端稱為隊頭。在隊列中，只能刪除隊頭元素，隊列的最後一個元素一定是最新入隊的元素。因此隊列又稱先進先出表（First In First Out）。

2、棧和隊列都是一種特殊的操作受限的線性表，只允許在端點處進行插入和刪除。二者的區別是：棧只允許在表的一端進行插入或刪除操作，是一種"後進先出"的線性表；而隊列只允許在表的一端進行插入操作，在另一端進行刪除操作，是一種"先進先出"的線性表。

3、棧是一種特殊的線性表，這種線性表只能在固定的一端進行插入和刪除操作，允許插入和刪除的一端稱為棧頂，另一端稱為棧底。一個新元素只能從棧頂一端進入，刪除時，只能刪除棧頂的元素，即剛剛被插入的元素。所以棧又稱先進後出表（FILO-First In Last Out）。線性表可以順序存儲，也可以鏈式存儲，而棧是一種線性表，也可以採用鏈式存儲結構。

4、棧和隊列都是一種特殊的操作受限的線性表，只允許在端點處進行插入和刪除。二者的區別是：棧只允許在表的一端進行插入或刪除操作，是一種"後進先出"的線性表；而隊列只允許在表的一端進行插入操作，在另一端進行刪除操作，是一種"先進先出"的線性表。

5、在棧中，棧底指針不變，棧中元素隨棧頂指針的變化而動態變化

top=0表示棧空，top=50表示棧滿。入棧操作首先將top加1，然後將新元素插入到top指針指向的位置；退棧操作首先將top指針指向的元素賦給一個指定的變數，然後將top減1。棧頂指針top動態反映了棧中元素的變化情況。

6、棧是一種先進後出的線性表，棧實際上也是線性表，只不過是一種特殊的線性表。隊列是指允許在一端進行插入、而在另一端進行刪除的線性表，隊列是一種"先進先出"或"後進後出"的線性表

隊列是指允許在一端進行插入、而在另一端進行刪除的線性表。它又稱為"先進先出"或"後進後出"的線性表，體現了"先來先服務"的原則。

7、帶鏈的隊列也是線性鏈表，在線性鏈表中指向線性表中的第一個結點的指針稱為頭指針，頭指針為NULL或0時稱為空表，指向隊尾元素的指針稱為尾指針。隊列在隊尾插入元素，稱為入隊運算；在隊頭刪除元素，稱為退隊運算。帶鏈隊列在開辟存儲空間時，可以按照存儲空間地址增大的方向開辟，也可以按照存儲空間地址減少的方向開辟。

8、所謂循環隊列，就是將隊列存儲空間的最後一個位置繞到第1個位置，形成邏輯上的環狀空間，供隊列循環使用。所以循環隊列還是屬於線性結構。循環隊列的頭指針front指向隊列的第一個元素的前一位置，隊尾指針rear指向隊列的最後一個元素，循環隊列的動態變化需要頭尾指針共同反映循環隊列的長度是：(sq.rear-sq.front+maxsize)%maxsize，所以循環隊列的長度是由隊頭和隊尾指針共同決定的

 在循環隊列中，用隊尾指針rear指向隊列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置。

 循環隊列主要有兩種基本運算：入隊運算與退隊運算。每進行一次入隊運算，隊尾指針就進一。每進行一次退隊運算，排頭指針就進一。當rear或front的值等於隊列的長度+1時，就將rear或front的值置為1。一般情況下，rear大於front，因為入隊的元素肯定比出隊的元素多。特殊的情況是rear到達數組的上限之後又從數組的低端開始，此時，rear是小於front的。

循環隊列就是將隊列存儲空間的最後一個位置繞到第一個位置，形成邏輯上的環狀空間，供隊列循環使用。在實際應用中，隊列的順序存儲結構一般採用循環隊列的形式。因此，循環隊列不是隊列的一種鏈式存儲結構。循環隊列是一種存儲結構，因此循環隊列是一種物理結構，而不是邏輯結構。循環隊列是隊列的順序存儲結構，因此循環隊列是線性結構。

9、循環隊列不同於循環鏈表，循環隊列是順序存儲結構，循環鏈表是鏈式存儲結構。雙向鏈表是鏈式存儲結構，其中每個結點都有左指針和右指針，不同於二叉樹結點的左子樹指針和右子樹指針。非線性結構和線性結構是數據的邏輯結構，順序和鏈式是數據的存儲結構，例如二叉樹是非線性結構，也可以按照層序進行順序存儲。

10、非線性結構的邏輯特徵是一個結點元素可能對應多個直接前驅和多個後驅。常見的非線性結構有：樹（二叉樹等），圖（網等）。

11、由於二叉樹的存儲結構中每一個存儲結點有兩個指針域，因此，二叉樹的鏈式存儲結構也稱為二叉鏈表，二叉鏈表屬於非線性結構。

12、遍歷是指不重復的訪問所有結點。線性單鏈表每個結點只有一個指針域，由這個指針只能找到後件結點，但不能找到前件結點。雙向鏈表中的每個結點設置兩個指針，左指針指向其前件結點，右指針指向其後件結點。循環鏈表中增加了一個表頭結點，循環鏈表中的所有結點的指針構成了一個環狀鏈。二叉鏈表即二叉樹的鏈式存儲結構，每個存儲結點有兩個指針域，左指針域指向該結點的左子結點的存儲地址，右指針域指向該結點的右子結點的存儲地址。

13、線性表的順序存儲結構具有兩個基本特點：（1）線性表中所有元素所佔的存儲空間是連續的;（2）線性表中各元素在存儲空間中是按邏輯順序依次存放的。

14、循環鏈表具有以下兩個特點：(1)在循環鏈表中增加了一個表頭結點，其數據域為任意或者根據需要來設置，指針域指向線性表的第一個元素的結點。循環鏈表的頭指針指向表頭結點。(2)循環鏈表中最後一個結點的指針域不是空，而是指向表頭結點。即在循環鏈表中，所有結點的指針構成了一個環狀鏈。

15、在循環鏈表中，只要指出表中任何一個結點的位置，就可以從它出發訪問到表中其他所有的結點，而線性單鏈表做不到這一點。

16、根據二叉樹的性質：二叉樹第i（i≥1）層上至多有2i-1個結點。

17、所謂滿二叉樹是指這樣的一種二叉樹：除最後一層外，每層上的所有結點都有兩個子結點。這就是說，在滿二叉樹中，每一層上的結點數都達到最大值，即在滿二叉樹的第K層上有2K-1個結點，且深度為m的滿二叉樹有2m個結點。

18、在任意一顆樹中，結點總數=總分支數目+1

19、二叉樹的性質：在任意一棵二叉樹中，度為0的結點（即葉子結點）總是比度為2的結點多一個。本題中度為2的結點數為n，故葉子結點數為n+1個。

二叉樹的性質：在任意一棵二叉樹中，度為0的結點（即葉子結點）總是比度為2的結點多一個。

20、在用完全二叉樹表示堆，樹中所有非葉子結點值均不小於其左右子樹的根結點值，因此，堆頂元素必為序列的n個元素中的最大項。

21、作為一個演算法，一般應具有以下幾個基本特徵。

 可行性

 確定性

 有窮性

擁有足夠的情報

22、計算機演算法是指解題方案的准確而完整的描述

演算法的有窮性，是指演算法必須在有限的時間內做完，即演算法必須能在執行有限個步驟之後終止。

23、希爾排序法的基本思想是：將整個無序序列分割成若干小的子序列分別進行插入排序。所以希爾排序法屬於插入類排序，但它對簡單插入排序做了很大的改進。

24、快速排序的基本思想是，通過一趟排序將待排序記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，再分別對這兩部分記錄繼續進行排序，以達到整個序列有序；插入排序的基本操作是指將無序序列中的各元素依次插入到已經有序的線性表中，從而得到一個新的序列；選擇排序的基本思想是：掃描整個線性表，從中選出最小的元素，將它交換到表的最前面（這是它應有的位置），然後對剩下的子表採用同樣的方法，直到表空為止；歸並排序是將兩個或兩個以上的有序表組合成一個新的有序表。

25、在單鏈表中，增加頭結點的目的是______。

頭結點不僅標識了表中首結點的位置，而且根據單鏈表（包含頭結點）的結構，只要掌握了表頭，就能夠訪問整個鏈表，因此增加頭結點目的是為了便於運算的實現。

26、演算法分析是指對一個演算法的運行時間和佔用空間做定量的分析，一般計算出相應的數量級，常用時間復雜度和空間復雜度表示。分析演算法的目的就是要降低演算法的時間復雜度和空間復雜度，提高演算法的執行效率。

27、演算法是指解題方案的准確而完整的描述。但演算法不等於程序，也不等於計算方法。當然，程序也可以作為演算法的一種描述，但程序通常還需要考慮很多與方法和分析無關的細節問題，這是因為在編寫程序時要受到計算機系統運行環境的限制。通常，程序的編制不可能優於演算法的設計。作為一個演算法，一般應具有可行性、確定性、有窮性、擁有足夠情報四個基本特徵。因此設計演算法時不僅僅要考慮結果的可靠性，即不僅考慮演算法結果的可行性，還要考慮步驟的確定性，時間和步驟的有窮性等。因此，演算法是一組嚴謹地定義運算順序的規則，並且每一個規則都是有效的，且是明確的，此順序將在有限的次數下終止。

28、一個演算法通常由兩種基本要素組成：一是對數據對象的運算和操作，二是演算法的控制結構。因此設計演算法時不僅需要考慮數據結構的設計，還要考慮數據的操作和運算及各操作之間的執行順序。

29、在有向圖中，若任意兩個頂點都連通，則稱該圖是強連通圖，這樣的有向圖的形狀是環狀，因而至少應有n條邊。

30、當數據表A中每個元素距其最終位置不遠，說明數據表A按關鍵字值基本有序，在待排序序列基本有序的情況下，採用插入排序所用時間最少。

31、數據的邏輯結構在計算機存儲空間中的存放形式稱為數據的存儲結構（也稱數據的物理結構）。

32、假設線性表的長度為n，則在最壞情況下，冒泡排序需要經過n/2遍的從前往後掃描和n/2遍的從後往前掃描，需要比較次數為n(n-1)/2。快速排序法的最壞情況比較次數也是n(n-1)/2

（1）冒泡排序法：是一種最簡單的交換類排序法，它是通過相鄰數據元素的交換逐步將線性表變成有序。假設線性表的長度為n，則在最壞情況下，冒泡排序需要經過n/2遍的從前往後的掃描和n/2遍的從後往前的掃描，需要比較的次數為n(n-1)/2次。

 （2）簡單插入排序法：在簡單插入排序法中，每一次比較後最多移掉一個逆序，因此，這種排序方法的效率與冒泡排序法相同。在最壞情況下，簡單插入排序需要n(n-1)/2次比較。

 （3）簡單選擇排序法：對於長度為n的序列，選擇排序需要掃描n-1遍，每一遍掃描均從剩下的子表中選出最小的元素，然後將該最小的元素與子表中的第一個元素進行交換。簡單選擇排序法在最壞情況下需要比較n(n-1)/2次。

 （4）堆排序法：堆排序的方法為：①首先將一個無序序列建成堆。②然後將堆頂元素（序列中的最大項）與堆中最後一個元素交換（最大項應該在序列的最後）。在最壞情況下，堆排序需要比較的次數為。

 假設線性表的長度為16，那麼冒泡排序、直接插入排序、簡單選擇排序都需要比較120次，而堆排序需要比較64次。

33、對於長度為n的線性表，在最壞的情況下，快速排序所需要的比較次數為n(n-1)/2；冒泡排序所需要的比較次數為n(n-1)/2；直接插入排序所需要的比較次數為n(n-1)/2；堆排序所需要的比較次數為。

34、在進行順序查找過程中，如果線性表中的第一個元素就是被查找元素，則只需做一次比較就查找成功，查找效率最高；但如果被查找的元素是線性表中的最後一個元素，或者被查找的元素根本就不在線性表中，則為了查找這個元素需要與線性表中所有的元素進行比較，這是順序查找的最壞情況。所以對長度為n的線性表進行順序查找，在最壞情況下需要比較n次。

35、二分法查找只適用於順序存儲的有序表。在此所說的有序表是指線性表中的元素按值非遞減排列（即從小到大，但允許相鄰元素值相等）。

二分法檢索要求線性表結點按關鍵值排序且以順序方式存儲。在查找時，首先與表的中間位置上結點的關鍵值比較，若相等則檢索成功；否則根據比較結果確定下一步在表的前半部分或後半部分繼續進行。二分法檢索的效率比較高，設線性表有n個元素，則最多的檢索次數為大於log2n(2為底數)的最小整數，最少的檢索次數為1。

36、一般來說，一種數據的邏輯結構根據需要可以表示成多種存儲結構，常用的存儲結構有順序、鏈接、索引等存儲結構。而採用不同的存儲結構，其數據處理的效率是不同的。

37、順序存儲結構就是用一組地址連續的存儲單元依次存儲該線性表中的各個元素，鏈式存儲結構中各數據結點的存儲序號是不連續的，並且各結點在存儲空間中的位置關系與邏輯關系也不一致。兩者都可以存儲線性的、有序的邏輯結構，順序結構使用的是連續物理空間，鏈式結構可以使用零散的物理空間存儲，鏈式結構更靈活，不存在誰節約空間的說法

38、順序存儲結構中，數據元素存放在一組地址連續的存儲單元中，每個數據元素地址可通過公式LOC(ai)=LOC(a1)+(i-1)L計算得到，從而實現了隨機存取。對於鏈式存儲結構，要對某結點進行存取，都得從鏈的頭指針指向的結點開始，這是一種順序存取的存儲結構。

39、鏈式存儲結構克服了順序存儲結構的缺點：它的結點空間可以動態申請和釋放；它的數據元素的邏輯次序靠結點的指針來指示，不需要移動數據元素。故鏈式存儲結構下的線性表便於插入和刪除操作。

40、線性表的順序存儲結構的存儲空間只用於存放結點數據，而鏈式存儲結構的存儲空間不僅要存放結點數據，還要存放數據的指針，所以線性表的鏈式存儲結構所需要的存儲空間一般要多於順序存儲結構

41、在進行順序查找過程中，如果線性表中的第1個元素就是被查找元素，則只需做一次比較就查找成功，查找效率最高；但如果被查找的元素是線性表中的最後一個元素，或者被查找的元素根本就不在線性表中，則為了查找這個元素需要與線性表中所有的元素進行較，這是順序查找的最壞情況。所以對長度為n的線性表進行順序查找，在最壞情況下需要比較n次

42、對於長度為n的有序線性表，在最壞情況下，二分查找只需要比較 次，而順序查找需要比較n次。二分法查找只適用於順序存儲的有序表，如果採用鏈式存儲結構，也只能用順序查找,所以，對長度為n的有序鏈表進行查找，最壞情況下需要的比較次數為n

43、根據數據結構中各數據元素之間前後件關系的復雜程度，一般將數據結構分為兩大類型：線性結構與非線性結構。

44、如果一個非空的數據結構滿足下列兩個條件：（1）有且只有一個根結點；（2）每一個結點最多有一個前件，也最多有一個後件。則稱該數據結構為線性結構，又稱線性表。

45、有一個以上根結點的數據結構肯定是非線性結構，循環鏈表、雙向鏈表是線性結構；線性表、棧與隊列、線性鏈表都是線性結構，而二叉樹是非線性結構。

46、在鏈表中，如果有兩個結點的同一個指針域的值相等，則該鏈表一定是非線性結構

47、線性表的鏈式存儲結構稱為線性鏈表，為了適應線性表的鏈式存儲結構，計算機存儲空間被劃分為一個一個小塊，每一小塊占若干位元組，通常稱這些小塊為存儲結點。每一個存儲結點分為兩部分：一部分用於存儲數據元素的值，稱為數據域；另一部分用於存放下一個數據元素的存儲序號，即指向後件的結點，稱為指針域。在鏈式存儲結構中，存儲數據結構的存儲空間可以不連續，各數據結點的存儲順序與數據元素之間的邏輯關系可以不一致。為了要在線性鏈表中插入一個新元素，首先要給該元素分配一個新結點，以便用於存儲該元素的值，然後將存放新元素值的結點鏈接到線性表中指定的位置。在線性鏈表的插入過程中不發生數據無素移動的現象，只需改變有關結點的指針即可，從而提高了插入的效率。為了在線性鏈表中刪除包含指定元素的結點，首先要在線性鏈表中找到這個結點，然後將要刪除結點放回到可利用棧。在線性鏈表中刪除一個元素後，不需要移動表的數據元素，只需改變被刪元素所在結點的前一個結點的指針域即可。因此，進行插入與刪除時，不需要移動表中的元素。

48、在先左後右的原則下，根據訪問根結點的次序，二叉樹的遍歷可以分為3種：前序遍歷、中序遍歷和後序遍歷。

前序遍歷是指在訪問根結點、遍歷左子樹與遍歷右子樹這三者中，首先訪問根結點，然後遍歷左子樹，最後遍歷右子樹；並且遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹。

後序遍歷指在訪問根結點、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然後遍歷右子樹，最後訪問根結點；並且遍歷左、右子樹時，仍然先遍歷左子樹，然後遍歷右子樹，最後訪問根結點。

二叉樹的中序遍歷指在訪問根結點、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹；並且遍歷左、右子樹時，仍然先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。

49、鏈表有線性鏈表，也有非線性鏈表。線性鏈表和二叉樹鏈表的結點都有兩個指針域，前者是線性結構，後者是非線性結構。線性單鏈表中的結點只有一個指針，葉子結點一般是對樹結構而言，樹結構是非線性結構，不是線性表。

50、演算法的復雜度主要包括時間復雜度和空間復雜度：演算法在運行過程中需輔助存儲空間的大小稱為演算法的空間復雜度；演算法的時間復雜度是指執行演算法所需要的計算工作量，即演算法執行過程中所需要的基本運算次數，為了能夠比較客觀地反映出一個演算法的效率，在度量一個演算法的工作量時，不僅應該與所使用的計算機、程序設計語言以及程序編制者無關，而且還應該與演算法實現過程中的許多細節無關。為此，可以用演算法在執行過程中所需基本運算的執行次數來度量演算法的工作量。二者沒有直接關系。

51、一個演算法的空間復雜度，一般是指執行這個演算法所需要的內存空間。一個演算法所佔用的存儲空間包括程序所佔的空間、輸入的初始數據所佔的存儲空間以及演算法執行過程中所需要的額外空間。其中額外空間包括演算法程序執行過程中的工作單元以及某種數據結構所需要的附加存儲空間。如果額外空間相對於問題規模來說是常數，則稱該演算法是原地(in place)工作的。

52、我們通常用時間復雜度和空間復雜度來衡量演算法效率，演算法的時間復雜度是指執行演算法所需要的計算工作量；演算法所執行的基本運算次數與問題的規模有關，而一個演算法的空間復雜度，一般是指執行這個演算法所需要的內存空間；一般來說，一種數據的邏輯結構根據需要可以表示成多種存儲結構。

所謂演算法的時間復雜度，是指執行演算法所需要的計算工作量。為了能夠比較客觀地反映出一個演算法的效率，在度量一個演算法的工作量時，不僅應該與所使用的計算機、程序設計語言以及程序編制者無關，而且還應該與演算法實現過程中的許多細節無關。為此，可以用演算法在執行過程中所需基本運算的執行次數來度量演算法的工作量。

53、子程序調用是一種層次關系，子程序調用功能模塊，調用功能模塊的個數也不確定，可以是一個，也可以是多個。二叉樹是一種很有用的非線性結構，二叉樹不同於樹形結構。二叉樹具有以下兩個特點：①非空二叉樹只有一個根結點；②每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。選項D規定每個結點只能有兩個後件。在子程序調用中，調用的功能模塊可以是多個，可以調用超過兩個功能模塊。

54、結構圖的深度表示控制的層數結構圖的深度表示控制的層數

55、數據結構是指反映數據元素之間關系的數據元素集合的表示。更通俗地說，數據結構是指帶有結構的數據元素的集合。所謂結構實際上就是指數據元素之間的前後件關系。線性結構與非線性結構都可以是空的數據結構。一個空的數據結構究竟是屬於線性結構還是屬於非線性結構，還要根據具體情況來確定。如果對該數據結構的運算是按線性結構的規則來處理的，則屬於線性結構；否則屬於非線性結構。