數(shù)據(jù)結(jié)構(gòu)和算法

數(shù)據(jù)結(jié)構(gòu)和算法第1頁，共54頁，2023年，2月20日，星期五數(shù)據(jù)結(jié)構(gòu)(DataStructure)是指相互之間具有(存在)一定聯(lián)系(關(guān)系)的數(shù)據(jù)元素的集合。元素之間的相互聯(lián)系(關(guān)系)稱為邏輯結(jié)構(gòu)。數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)有四種基本類型集合：結(jié)構(gòu)中的數(shù)據(jù)元素除了“同屬于一個集合”外，沒有其它關(guān)系。線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系。樹型結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關(guān)系。圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關(guān)系。第2頁，共54頁，2023年，2月20日，星期五數(shù)據(jù)結(jié)構(gòu)的存儲方式數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的存儲包括數(shù)據(jù)元素的存儲和元素之間的關(guān)系的表示。元素之間的關(guān)系在計算機中有兩種不同的表示方法：順序表示和非順序表示。由此得出兩種不同的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。順序存儲結(jié)構(gòu)：用數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)(關(guān)系)。鏈?zhǔn)酱鎯Y(jié)構(gòu)：在每一個數(shù)據(jù)元素中增加一個存放另一個元素地址的指針(pointer)，用該指針來表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)(關(guān)系)。第3頁，共54頁，2023年，2月20日，星期五邏輯結(jié)構(gòu)和物理結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)非線性結(jié)構(gòu)集合圖狀結(jié)構(gòu)有向圖無向圖樹形結(jié)構(gòu)一般樹二叉樹線性結(jié)構(gòu)一般線性表線性表推廣廣義表數(shù)組串受限線性表棧和隊列數(shù)據(jù)邏輯結(jié)構(gòu)層次關(guān)系圖圖1-4

邏輯結(jié)構(gòu)與所采用的存儲結(jié)構(gòu)線性表樹圖順序存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)復(fù)合存儲結(jié)構(gòu)邏輯結(jié)構(gòu)物理結(jié)構(gòu)第4頁，共54頁，2023年，2月20日，星期五數(shù)據(jù)結(jié)構(gòu)的運算數(shù)據(jù)結(jié)構(gòu)的主要運算包括：⑴建立(Create)一個數(shù)據(jù)結(jié)構(gòu)；⑵消除(Destroy)一個數(shù)據(jù)結(jié)構(gòu)；⑶從一個數(shù)據(jù)結(jié)構(gòu)中刪除(Delete)一個數(shù)據(jù)元素⑷把一個數(shù)據(jù)元素插入(Insert)到一個數(shù)據(jù)結(jié)構(gòu)中；⑸對一個數(shù)據(jù)結(jié)構(gòu)進行訪問(Access)；⑹對一個數(shù)據(jù)結(jié)構(gòu)(中的數(shù)據(jù)元素)進行修改(Modify)；⑺對一個數(shù)據(jù)結(jié)構(gòu)進行排序(Sort)；⑻對一個數(shù)據(jù)結(jié)構(gòu)進行查找(Search)。第5頁，共54頁，2023年，2月20日，星期五線性表線性結(jié)構(gòu)是最常用、最簡單的一種數(shù)據(jù)結(jié)構(gòu)。而線性表是一種典型的線性結(jié)構(gòu)。其基本特點是線性表中的數(shù)據(jù)元素是有序且是有限的。在這種結(jié)構(gòu)中：①存在一個唯一的被稱為“第一個”的數(shù)據(jù)元素；②存在一個唯一的被稱為“最后一個”的數(shù)據(jù)元素；③除第一個元素外，每個元素均有唯一一個直接前驅(qū)；④除最后一個元素外，每個元素均有唯一一個直接后繼。第6頁，共54頁，2023年，2月20日，星期五線性表的順序存儲在高級語言(如C語言)環(huán)境下，數(shù)組具有隨機存取的特性，因此，借助數(shù)組來描述順序表。順序存儲結(jié)構(gòu)中，很容易實現(xiàn)線性表的一些操作：初始化、賦值、查找、修改、插入、刪除、求長度等第7頁，共54頁，2023年，2月20日，星期五線性表的鏈?zhǔn)酱鎯τ靡唤M任意的存儲單元存儲線性表中的數(shù)據(jù)元素。用這種方法存儲的線性表簡稱線性鏈表。存儲鏈表中結(jié)點的一組任意的存儲單元以是連續(xù)的或不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置。為了正確表示結(jié)點間的邏輯關(guān)系，在存儲每個結(jié)點值的同時，還必須存儲指示其直接后繼結(jié)點的地址(或位置)，稱為指針(pointer)或鏈(link)，這兩部分組成了鏈表中的結(jié)點結(jié)構(gòu)鏈表是通過每個結(jié)點的指針域?qū)⒕€性表的n個結(jié)點按其邏輯次序鏈接在一起的。每一個結(jié)只包含一個指針域的鏈表，稱為單鏈表。為操作方便，總是在鏈表的第一個結(jié)點之前附設(shè)一個頭結(jié)點(頭指針)head指向第一個結(jié)點。第8頁，共54頁，2023年，2月20日，星期五雙向鏈表雙向鏈表(DoubleLinkedList)指的是構(gòu)成鏈表的每個結(jié)點中設(shè)立兩個指針域，一個指向其直接前趨的指針域prior，一個指向其直接后繼的指針域next。這樣形成的鏈表中有兩個方向不同的鏈，故稱為雙向鏈表。和單鏈表類似，雙向鏈表一般增加頭指針也能使雙鏈表的某些運算變得方便。將頭結(jié)點和尾結(jié)點鏈接起來也能構(gòu)成循環(huán)鏈表，并稱之為雙向循環(huán)鏈表。雙向鏈表是為了克服單鏈表的單向性的缺陷而引入的。第9頁，共54頁，2023年，2月20日，星期五雙向鏈表的結(jié)點及其類型定義datanextprior雙向鏈表結(jié)點形式……非空雙向鏈表head?a2a1an?空雙向鏈表head??帶頭結(jié)點的雙向鏈表形式第10頁，共54頁，2023年，2月20日，星期五棧和隊列棧和隊列是兩種應(yīng)用非常廣泛的數(shù)據(jù)結(jié)構(gòu)，它們都來自線性表數(shù)據(jù)結(jié)構(gòu)，都是“操作受限”的線性表。棧在計算機的實現(xiàn)有多種方式：硬堆棧：利用CPU中的某些寄存器組或類似的硬件或使用內(nèi)存的特殊區(qū)域來實現(xiàn)。這類堆棧容量有限，但速度很快；軟堆棧：這類堆棧主要在內(nèi)存中實現(xiàn)。實現(xiàn)方式又有動態(tài)方式和靜態(tài)方式兩種。第11頁，共54頁，2023年，2月20日，星期五棧的基本概念棧(Stack)：是限制在表的一端進行插入和刪除操作的線性表。又稱為后進先出LIFO(LastInFirstOut)或先進后出FILO(FirstInLastOut)線性表。棧頂(Top)：允許進行插入、刪除操作的一端，又稱為表尾。用棧頂指針(top)來指示棧頂元素。棧底(Bottom)：是固定端，又稱為表頭。空棧：當(dāng)表中沒有元素時稱為空棧。第12頁，共54頁，2023年，2月20日，星期五棧的順序存儲表示棧的順序存儲結(jié)構(gòu)簡稱為順序棧，和線性表相類似，用一維數(shù)組來存儲棧。根據(jù)數(shù)組是否根據(jù)需要增大，又分為靜態(tài)順序棧和動態(tài)順序棧。靜態(tài)順序棧實現(xiàn)簡單，但不能根據(jù)需要增大棧的存儲空間；動態(tài)順序棧根據(jù)需要增大棧的存儲空間，但實現(xiàn)稍為復(fù)雜。第13頁，共54頁，2023年，2月20日，星期五棧的鏈?zhǔn)酱鎯Ρ硎緱５逆準(zhǔn)酱鎯Y(jié)構(gòu)稱為鏈棧，是運算受限的單鏈表。其插入和刪除操作只能在表頭位置進行。因此，鏈棧沒有必要像單鏈表那樣附加頭結(jié)點，棧頂指針top就是鏈表的頭指針第14頁，共54頁，2023年，2月20日，星期五棧的應(yīng)用由于棧具有的“后進先出”的固有特性，因此，棧成為程序設(shè)計中常用的工具和數(shù)據(jù)結(jié)構(gòu)。以下是幾個棧應(yīng)用的例子后綴表達式計算中綴表達式變后綴表達式棧與遞歸調(diào)用的實現(xiàn)第15頁，共54頁，2023年，2月20日，星期五隊列隊列(Queue)：也是運算受限的線性表。是一種先進先出(FirstInFirstOut，簡稱FIFO)的線性表。只允許在表的一端進行插入，而在另一端進行刪除。隊首(front)：允許進行刪除的一端稱為隊首。隊尾(rear)：允許進行插入的一端稱為隊尾。隊列中沒有元素時稱為空隊列。在空隊列中依次加入元素a1,a2,…,an之后，a1是隊首元素，an是隊尾元素。顯然退出隊列的次序也只能是a1,a2,…,an，即隊列的修改是依先進先出的原則進行的第16頁，共54頁，2023年，2月20日，星期五循環(huán)隊列為充分利用向量空間，克服“假溢出”現(xiàn)象，將隊列分配的向量空間看成為一個首尾相接的圓環(huán)，并稱這種隊列為循環(huán)隊列(CircularQueue)。123450(a)空隊列frontrear123450(b)d,e,b,g入隊frontdebgrear123450(c)d,e出隊bgfrontrear第17頁，共54頁，2023年，2月20日，星期五隊列的鏈?zhǔn)奖硎竞蛯崿F(xiàn)隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)簡稱為鏈隊列，它是限制僅在表頭進行刪除操作和表尾進行插入操作的單鏈表。需要兩類不同的結(jié)點：數(shù)據(jù)元素結(jié)點，隊列的隊首指針和隊尾指針的結(jié)點第18頁，共54頁，2023年，2月20日，星期五樹與二叉樹第19頁，共54頁，2023年，2月20日，星期五樹和二叉樹樹型結(jié)構(gòu)是一類非常重要的非線性結(jié)構(gòu)。直觀地，樹型結(jié)構(gòu)是以分支關(guān)系定義的層次結(jié)構(gòu)。樹在計算機領(lǐng)域中也有著廣泛的應(yīng)用，例如在編譯程序中，用樹來表示源程序的語法結(jié)構(gòu)；在數(shù)據(jù)庫系統(tǒng)中，用樹來組織信息；在分析算法的行為時，用樹來描述其執(zhí)行過程等等。本章將詳細討論樹和二叉樹數(shù)據(jù)結(jié)構(gòu)，主要介紹樹和二叉樹的概念、術(shù)語，二叉樹的遍歷算法。樹和二叉樹的各種存儲結(jié)構(gòu)以及建立在各種存儲結(jié)構(gòu)的操作及應(yīng)用等。第20頁，共54頁，2023年，2月20日，星期五樹的定義樹(Tree)是n(n≧0)個結(jié)點的有限集合T，若n=0時稱為空樹，否則：有且只有一個特殊的稱為樹的根(Root)結(jié)點；若n>1時，其余的結(jié)點被分為m(m>0)個互不相交的子集T1,T2,T3…Tm，其中每個子集本身又是一棵樹，稱其為根的子樹(Subtree)。這是樹的遞歸定義，即用樹來定義樹，而只有一個結(jié)點的樹必定僅由根組成第21頁，共54頁，2023年，2月20日，星期五樹的基本術(shù)語結(jié)點(node)：一個數(shù)據(jù)元素及其若干指向其子樹的分支。結(jié)點的度(degree)、樹的度：結(jié)點所擁有的子樹的棵數(shù)稱為結(jié)點的度。樹中結(jié)點度的最大值稱為樹的度。樹的示例形式AABDCEGFHIMJNKL(a)

只有根結(jié)點(b)

一般的樹第22頁，共54頁，2023年，2月20日，星期五樹的基本術(shù)語葉子(left)結(jié)點、非葉子結(jié)點樹中度為0的結(jié)點稱為葉子結(jié)點(或終端結(jié)點)。相對應(yīng)地，度不為0的結(jié)點稱為非葉子結(jié)點(或非終端結(jié)點或分支結(jié)點)。除根結(jié)點外，分支結(jié)點又稱為內(nèi)部結(jié)點。孩子結(jié)點、雙親結(jié)點、兄弟結(jié)點一個結(jié)點的子樹的根稱為該結(jié)點的孩子結(jié)點(child)或子結(jié)點；相應(yīng)地，該結(jié)點是其孩子結(jié)點的雙親結(jié)點(parent)或父結(jié)點。森林(forest)：是m(m≧0)棵互不相交的樹的集合。顯然，若將一棵樹的根結(jié)點刪除，剩余的子樹就構(gòu)成了森林。第23頁，共54頁，2023年，2月20日，星期五樹的表示形式倒懸樹。是最常用的表示形式嵌套集合。是一些集合的集體，對于任何兩個集合，或者不相交，或者一個集合包含另一個集合廣義表形式凹入法表示形式樹的表示形式(a)嵌套集合形式(b)廣義表形式(A(B(E(K,L),F),C(G(M,N)),D(H,I,J)HIJDFBKLECMNGA第24頁，共54頁，2023年，2月20日，星期五二叉樹二叉樹(Binarytree)是n(n≥0)個結(jié)點的有限集合。若n=0時稱為空樹，否則：有且只有一個特殊的稱為樹的根(Root)結(jié)點；若n>1時，其余的結(jié)點被分成為二個互不相交的子集T1,T2，分別稱之為左、右子樹，并且左、右子樹又都是二叉樹。由此可知，二叉樹的定義是遞歸的。二叉樹在樹結(jié)構(gòu)中起著非常重要的作用。因為二叉樹結(jié)構(gòu)簡單，存儲效率高，樹的操作算法相對簡單，且任何樹都很容易轉(zhuǎn)化成二叉樹結(jié)構(gòu)。上節(jié)中引入的有關(guān)樹的術(shù)語也都適用于二叉樹。第25頁，共54頁，2023年，2月20日，星期五二叉樹的基本形態(tài)AAAA(a)(b)(c)(d)(e)(a)空二叉樹(b)單結(jié)點二叉樹(c)右子樹為空(d)左子樹為空(e)左、右子樹都不空二叉樹的基本形態(tài)第26頁，共54頁，2023年，2月20日，星期五二叉樹的性質(zhì)性質(zhì)1：在非空二叉樹中，第i層上至多有2i-1個結(jié)點(i≧1)。性質(zhì)2：深度為k的二叉樹至多有2k-1個結(jié)點（k≧1)。性質(zhì)3：對任何一棵二叉樹，若其葉子結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1。第27頁，共54頁，2023年，2月20日，星期五滿二叉樹一棵深度為k且有2k-1個結(jié)點的二叉樹稱為滿二叉樹(FullBinaryTree)。滿二叉樹的特點：每一層上的結(jié)點數(shù)總是最大結(jié)點數(shù)。所有的支結(jié)點都有左、右子樹?？蓪M二叉樹的結(jié)點進行連續(xù)編號，若規(guī)定從根結(jié)點開始，按“自上而下、自左至右”的原則進行。第28頁，共54頁，2023年，2月20日，星期五完全二叉樹完全二叉樹(CompleteBinaryTree)：如果深度為k，由n個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為k的滿二叉樹中編號從1到n的結(jié)點一一對應(yīng)，該二叉樹稱為完全二叉樹?；蛏疃葹閗的滿二叉樹中編號從1到n的前n個結(jié)點構(gòu)成了一棵深度為k的完全二叉樹。其中2k-1≦n≦2k-1完全二叉樹是滿二叉樹的一部分，而滿二叉樹是完全二叉樹的特例。完全二叉樹的特點是，若完全二叉樹的深度為k，則所有的葉子結(jié)點都出現(xiàn)在第k層或k-1層。對于任一結(jié)點，如果其右子樹的最大層次為l，則其左子樹的最大層次為l或l+1。第29頁，共54頁，2023年，2月20日，星期五894101151213614157213894101152112673(a)滿二叉樹(b)完全二叉樹1362455674213(c)非完全二叉樹特殊形態(tài)的二叉樹第30頁，共54頁，2023年，2月20日，星期五二叉樹的存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)用一組地址連續(xù)的存儲單元依次“自上而下、自左至右”存儲完全二叉樹的數(shù)據(jù)元素對于完全二叉樹上編號為i的結(jié)點元素存儲在一維數(shù)組的下標(biāo)值為i-1的分量中對于一般的二叉樹，將其每個結(jié)點與完全二叉樹上的結(jié)點相對照，存儲在一維數(shù)組中第31頁，共54頁，2023年，2月20日，星期五abcdhiejklfg(a)完全二叉樹(b)非完全二叉樹abcdefgh???123456789101112

abcdefghijkl

(c)完全二叉樹的順序存儲形式1234567891011abcde?h?

?

fg(d)非完全二叉樹的順序存儲形式第32頁，共54頁，2023年，2月20日，星期五鏈?zhǔn)酱鎯Y(jié)構(gòu)設(shè)計不同的結(jié)點結(jié)構(gòu)可構(gòu)成不同的鏈?zhǔn)酱鎯Y(jié)構(gòu)。二叉鏈表結(jié)點。有三個域：一個數(shù)據(jù)域，兩個分別指向左右子結(jié)點的指針域三叉鏈表結(jié)點。除二叉鏈表的三個域外，再增加一個指針域，用來指向結(jié)點的父結(jié)點LchilddataRchildLchilddataparentRchild(a)二叉鏈表結(jié)點(b)三叉鏈表結(jié)點鏈表結(jié)點結(jié)構(gòu)形式第33頁，共54頁，2023年，2月20日，星期五二叉樹的鏈?zhǔn)酱鎯π问接幸豢靡话愕亩鏄?，以二叉鏈表和三叉鏈表方式存儲的結(jié)構(gòu)圖二叉樹及其鏈?zhǔn)酱鎯Y(jié)構(gòu)(a)二叉樹afedcbg(c)三叉鏈表

a?

?

b?

c?

d?

e?

f??

g?T(b)二叉鏈表

a?

b?c?

d?e?g??f?T第34頁，共54頁，2023年，2月20日，星期五遍歷二叉樹及其應(yīng)用遍歷二叉樹(TraversingBinaryTree)是指按指定的規(guī)律對二叉樹中的每個結(jié)點訪問一次且僅訪問一次。所謂訪問是指對結(jié)點做某種處理。如：輸出信息、修改結(jié)點的值等。二叉樹是一種非線性結(jié)構(gòu)，每個結(jié)點都可能有左、右兩棵子樹，因此，需要尋找一種規(guī)律，使二叉樹上的結(jié)點能排列在一個線性隊列上，從而便于遍歷。二叉樹的基本組成：根結(jié)點、左子樹、右子樹。若能依次遍歷這三部分，就是遍歷了二叉樹。第35頁，共54頁，2023年，2月20日，星期五遍歷二叉樹若以L、D、R分別表示遍歷左子樹、遍歷根結(jié)點和遍歷右子樹，則有六種遍歷方案：DLR、LDR、LRD、DRL、RDL、RLD。若規(guī)定先左后右，則只有前三種情況三種情況，分別是：DLR——先(根)序遍歷。LDR——中(根)序遍歷。LRD——后(根)序遍歷。第36頁，共54頁，2023年，2月20日，星期五構(gòu)建二叉搜索樹又名二叉排序樹用遞歸的方法構(gòu)建樹實現(xiàn)對樹的增刪改查功能第37頁，共54頁，2023年，2月20日，星期五算法第38頁，共54頁，2023年，2月20日，星期五查找算法順序查找從表中的第一個元素開始，將給定的值與表中逐個元素的關(guān)鍵字進行比較，直到兩者相符，查到所要找的元素為止。否則就是表中沒有要找的元素，查找不成功。平均要與表中一半以上元素進行比較，最壞情況下需要比較n次。如果線性表為無序表，則不管是順序存儲結(jié)構(gòu)還是鏈?zhǔn)酱鎯Y(jié)構(gòu)，都只能用順序查找。即使是有序線性表，如果采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，也只能用順序查找。第39頁，共54頁，2023年，2月20日，星期五查找算法二分法查找先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認找不到該記錄為止。前提：必須在具有順序存儲結(jié)構(gòu)的有序表中進行。特點：比順序查找方法效率高。最壞的情況下，需要比較log2n次。第40頁，共54頁，2023年，2月20日，星期五查找算法二分法查找第41頁，共54頁，2023年，2月20日，星期五排序算法排序是將一批(組)任意次序的記錄重新排列成按關(guān)鍵字有序的記錄序列的過程，其定義為：給定一組記錄序列：{R1,R2,…,Rn}，其相應(yīng)的關(guān)鍵字序列是{K1,K2,…,Kn}。確定1,2,…n的一個排列p1,p2,…,pn，使其相應(yīng)的關(guān)鍵字滿足如下非遞減(或非遞增)關(guān)系：Kp1≤Kp2≤…≤Kpn的序列{Kp1,Kp2,…,Kpn}，這種操作稱為排序。關(guān)鍵字Ki可以是記錄Ri的主關(guān)鍵字，也可以是次關(guān)鍵字或若干數(shù)據(jù)項的組合。Ki是主關(guān)鍵字：排序后得到的結(jié)果是唯一的；Ki是次關(guān)鍵字：排序后得到的結(jié)果是不唯一的。第42頁，共54頁，2023年，2月20日，星期五排序算法若記錄序列中有兩個或兩個以上關(guān)鍵字相等的記錄：Ki=Kj(i≠j，i,j=1,2,…n)，且在排序前Ri先于Rj(i<j)，排序后的記錄序列仍然是Ri先于Rj，稱排序方法是穩(wěn)定的，否則是不穩(wěn)定的。排序算法有許多，但就全面性能而言，還沒有一種公認為最好的。每種算法都有其優(yōu)點和缺點，分別適合不同的數(shù)據(jù)量和硬件配置。評價排序算法的標(biāo)準(zhǔn)有：執(zhí)行時間和所需的輔助空間，其次是算法的穩(wěn)定性。若排序算法所需的輔助空間不依賴問題的規(guī)模n，即空間復(fù)雜度是O(1)，則稱排序方法是就地排序，否則是非就地排序。第43頁，共54頁，2023年，2月20日，星期五排序的分類待排序的記錄數(shù)量不同，排序過程中涉及的存儲器的不同，有不同的排序分類。待排序的記錄數(shù)不太多，所有的記錄都能存放在內(nèi)存中進行排序，稱為內(nèi)部排序；待排序的記錄數(shù)太多，所有的記錄不可能存放在內(nèi)存中，排序過程中必須在內(nèi)、外存之間進行數(shù)據(jù)交換，這樣的排序稱為外部排序。第44頁，共54頁，2023年，2月20日，星期五內(nèi)部排序的基本操作對內(nèi)部排序地而言，其基本操作有兩種：比較兩個關(guān)鍵字的大??；存儲位置的移動，從一個位置移到另一個位置。第一種操作是必不可少的；而第二種操作卻不是必須的，取決于記錄的存儲方式，具體情況是：記錄存儲在一組連續(xù)地址的存儲空間：記錄之間的邏輯順序關(guān)系是通過其物理存儲位置的相鄰來體現(xiàn)，記錄的移動是必不可少的；記錄采用鏈?zhǔn)酱鎯Ψ绞剑河涗浿g的邏輯順序關(guān)系是通過結(jié)點中的指針來體現(xiàn)，排序過程僅需修改結(jié)點的指針，而不需要移動記錄；記錄存儲在一組連續(xù)地址的存儲空間：構(gòu)造另一個輔助表來保存各個記錄的存放地址(指針)：排序過程不需要移動記錄，而僅需修改輔助表中的指針，排序后視具體情況決定是否調(diào)整記錄的存儲位置。第45頁，共54頁，2023年，2月20日，星期五冒泡排序依次比較相鄰的兩個數(shù)，將小數(shù)放在前面，大數(shù)放在后面。即在第一趟：首先比較第1個和第2個數(shù)，將小數(shù)放前，大數(shù)放后。然后比較第2個數(shù)和第3個數(shù)，將小數(shù)放前，大數(shù)放后，如此繼續(xù)，直至比較最后兩個數(shù)，將小數(shù)放前，大數(shù)放后。至此第一趟結(jié)束，將最大的數(shù)放到了最后。在第二趟：仍從第一對數(shù)開始比較（因為可能由于第2個數(shù)和第3個數(shù)的交換，使得第1個數(shù)不再小于第2個數(shù)），將小數(shù)放前，大數(shù)放后，一直比較到倒數(shù)第二個數(shù)（倒數(shù)第一的位置上已經(jīng)是最大的），第二趟結(jié)束，在倒數(shù)第二的位置上得到一個新的最大數(shù)（其實在整個數(shù)列中是第二大的數(shù)）。如此下去，重復(fù)以上過程，直至最終完成排序。由于在排序過程中總是小數(shù)往前放，大數(shù)往后放，相當(dāng)于氣泡往上升，所以稱作冒泡排序。第46頁，共54頁，2023年，2月20日，星期五插入排序采用的是以“玩橋牌者”的方法為基礎(chǔ)的。即在考察記錄Ri之前，設(shè)以前的所有記錄R1,R2,….,Ri-1已排好序，然后將Ri插入到已排好序的諸記錄的適當(dāng)位置。最基本的插入排序是直接插入排序(StraightInsertionSort)。第47頁，共54頁，2023年，2月20日，星期五直接插入排序?qū)⒋判虻挠涗汻i，插入到已排好序的記錄表R1,R2,….,Ri-1中，得到一個新的、記錄數(shù)增加1的有序表。直到所有的記錄都插入完為止。設(shè)待排序的記錄順序存放在數(shù)組R[1…n]中，在排序的某一時刻，將記錄序列分成兩部分：R[1…i-1]：已排好序的有序部分；R[i…n]：未排好序的無序部分。顯然，在剛開始排序時，R[1]是已經(jīng)排好序的。第48頁，共54頁，2023年，2月20日，星期五直接插入排序示例設(shè)有關(guān)鍵字序列為：7,4,-2,19,13,6，直接插入排序的過程如圖初始記錄的關(guān)鍵字：[7]4-219136第一趟排序：[47]-219136第二趟排序：[-247]19136第三趟排序：[-24719]13