第六章數據的組織結構與算法6.1數據結構的基本概念6.2常用的幾種數據結構6.3算法6.4程序設計方法16.1數據結構的基本概念6.1.1數值計算與非數值計算數據是描述客觀事物的數值、字符以及能輸入機器且能被處理的各種符號集合。換句話說，數據對客觀事物采用計算機能夠識別、存貯和處理形式所進行的描述。簡言之，數據就是計算機化的信息。數學模型有定量模型和定性模型兩類之分，定量模型指的是可以用數值方程表示的一類計算模型，而定性模型則是指非數值性的數據結構,如表、樹和圖等及其運算。2

數據結構（DataStructure）問題起源于程序設計的發展。第一個8008芯片只有4K的內存，微軟的最初成立就是為這個芯片的機器編寫BASIC語言，優化在每一處都非常重要。逐漸地，人們注意了數據表示與操作的結構化，把一些確實能夠有效解決問題的數據表示和算法總結出來，如表、棧、隊、樹、圖（稍后會介紹這些術語）等被單獨抽出研究，而這些方法便形成一門學問，這就是“數據結構”這門學科的來源。6.1.2數據結構的起源3數據結構有邏輯上的數據結構和物理上的數據結構之分。邏輯上的數據結構反映成分數據之間的邏輯關系。物理上的數據結構反映成分數據在計算機內部的存儲安排。6.1.3對數據結構的理解41.表示對象/實體及其關系在計算機中的表示。只有對象及其相互關系已存儲（表示）在計算機中，才能被進一步處理；2.操作：對對象/實體進行處理、訪問。數據結構的一般定義：相互之間存在著一定關系的數據元素的集合及定義在其上的操作（運算）稱為數據結構。51.插入：在數據結構中的指定位置增添新的數據元素2.刪除：刪去數據結構中指定的數據元素。3.查找：在數據結構中尋找某個特定要求的數據元素。4.排序：（在線性結構中）重新安排數據元素之間的邏輯順序關系，使之按某個關鍵字值由小到大或由大到小的次序排列。5.遍歷：按某一次序訪問數據結構中的每一個數據元素。6.1.4對數據結構中數據元素的操作6

[例6.1]解一元二次方程ax2+bx+c=0.利用計算機解此方程，第一個問題就是如何在計算機中表示該方程。分析該方程，可知決定方程的是方程的三個系數值：a、b、c，而它們的次序表示它們分別屬于那一項，其他符號是為增加可讀性而引入的，因此，可用這三個系數的線性排列在計算機中表示該方程。例如：3x2-x+1=0表示為（3,-1,1）x2-3=0表示為(1,0,-3)在數據結構中，將若干個數線性排列的數（元素）稱為線性表，因此，一元二次方程ax2+bx+c=0就在計算機中表示為線性表（a,b,c）。解方程實質上是對線性表(a,b,c)進行操作。6.1.5數據結構能解決什么問題7定義變量X和一個線性表，如數組intS[3];

S[2]，S[1]，S[0]可以分別存放三個系數值輸入S[2]，S[1]，S[0]三個系數值輸入任意一個值X開始S[2]*X*X+S[1]*X+S[0]<1E-5？輸出X結束YESNO8[例6-2]電話號碼查詢系統設有一個電話號碼薄，它記錄了N個人的名字和其相應的電話號碼，假定按如下形式安排：(a1,b1)(a2,b2)…(ai，bi)其中ai，bi(i=1，2…n)分別表示某人的名字和對應的電話號碼。要求設計一個算法，當給定任何一個人的名字時，該算法能夠打印出此人的電話號碼，如果該電話簿中根本就沒有這個人，則該算法也能夠報告沒有這個人的標志。假定名字和其電話號碼邏輯上已安排成N元向量的形式，它的每個元素是一個數對(ai，bi)，1≤i≤n。9[例6-3]家族成員的族譜表示一個家族的族譜就構成了一個層次結構，在數據結構中，稱為樹。圖6-2給出了這種族譜關系。10一般般用用示示意意圖圖表表示示數數據據結結構構。。用小小圓圓圈圈代代表表數數據據元元素素，用小小圓圓圈圈之之間間的的連連線線代代表表小小圓圓圈圈對對應應的的數數據據元元素素具具有有的的關關系系，，如果果強強調調關關系系的的方方向向性性，，可可用用帶帶箭箭頭頭的的線線段段表表示示關關系系。。具體體地地講講，，若若d1和d2表示示兩兩個個數數據據元元素素，，它它們們具具有有關關系系＜＜d1,d2＞，，則則表表示示為為如如圖圖6-3所所示示的的結結構構。。圖中中表表示示的的只只是是一一個個抽抽象象關關系系，，不不代代表表具具體體意意義義。。對對于于具具體體的的應應用用，，也也可可以以表表示示家家族族關關系系中中的的父父子子關關系系。。例例如如，，＜＜d1,d2＞可代表d1是d2的父親。數數據結構的的圖示116.2常用用的幾種數據據結構根據數據元素素之間的關系系的不同，將將數據結構的的邏輯結構分分為集合結構構、線性結構構、樹狀結構構和圖結構（（圖6-4））。12

集合：數據元素間間除了“同屬屬于一個集合合”外，別無無其它關系。。

線性結構：數據元素間間存在一個對對一個的關系系。

樹形結構：數據元素間間存在一個對對多個的關系系。

圖或網狀結構構：數據元素間間存在多個對對多個的關系系。6.2常用用的幾種數據據結構131.棧(stack)棧是只能在某某一端插入和和刪除的特殊殊線性表。進行刪除和插插入的一端稱稱棧頂，另一堆稱棧底。插入一般稱為為進棧（Push），刪除則稱為出棧（Pop）。棧也稱為后進進先出表（LIFO：LastIn,FirstOut）。操作系統中的的中斷調用及及返回就是采采用棧結構線線性結構14隊列是限定在在一端進行插插入，另一端端進行刪除和和特殊線性表表。通常把隊列的的刪除和插入入分別稱為出出隊和入隊。。允許出隊的的一端稱為隊隊頭，允許入入隊的一端稱稱為隊尾。所所有需要進隊隊的數據項，，只能從隊尾尾進入，隊列列中的數據項項只能從隊頭頭離去。由于于總是先入隊隊的元素先出出隊（先排隊隊的人先買完完東西），這這種表也稱為為先進先表（（FIFO：：FirstIn,FirstOut））表。2.隊列151.鏈表是指指用一組任意意的存儲單元元來依次存放放線性表的數數據元素。2.在存儲每每個結點值的的同時，必須須存儲指示其其后繼（或前前趨）結點的的地址（或位位置）信息，，這個信息稱稱為指針(pointer)或鏈(link)。如果鏈表表的每一個結結點只有一個個指針域，則則這種鏈表稱稱為單鏈表結結點結構，如如圖6-9(a)所示；；如果鏈表的的每一個結點點有兩個指針針域，則這種種鏈表稱為雙雙鏈表結點結結構。一個指指針域指向其其前趨結點，，一個指針域域向其后繼結結點。如圖6-9(b)所示。3.鏈表16[例6.4]單循環鏈表的的應用單循環鏈表的的一個典型例例子是約瑟夫環（JosephCircle），其描述如下下：編號為1,2,...,n的n個人人按順時針方方向圍坐一圈圈，每人持有有一個密碼（（正整數）。。現在給定一一個隨機數m>0，從編編號為1的人人開始，按順順時針方向1開始順序報報數，報到m時停止。報報m的人出圈圈，同時留下下他的密碼作作為新的m值值，從他在順順時針方向上上的下一個人人開始，重新新從1開始報報數，如此下下去，直至所所有的人出列列為止。17當n和m較大時，，用人工工求解約約瑟夫環環問題是是相當繁繁瑣的。。采用單循循環鏈表表就容易易解決。。其基本思思路是：：ｎ人圍成一一圈，把把一人看看成一個個結點，，ｎ人之間的的關系采采用鏈接接方式，，即每一一結點有有一個前前趨結點點和一個個后繼結結點，每每一個結結點有一一個指針針指向下下一個結結點，最最后一個個結點指指針指向向第一個個結點。。這就是是單循環環鏈的數數據結構構。當ｍ人出列時時，將ｍ結點的前前趨結點點指針指指向ｍ結點的后后繼結點點指針，，即把ｍ結點驅出出循環鏈鏈。181．樹的的定義樹是由一一個或多多個結點點組成的的有限集集合，如如圖6-12所所示。樹樹結構19必有一個個特定的的稱為根（ROOT）的的結點，，根的每每個分支支稱為子樹（sub-tree）），子樹樹也是一一棵樹樹中的每每一個結結點都可可以不止止一個直直接后繼繼，結點點的后繼繼結點稱稱為該結結點的““子結點點”（Children）除根結點點外的所所有結點點有且只只有一個個直接前前趨,結結點的前前趨結點點稱為該該結點的的“父結結點”（（Parent）同一父結結點的子子結點稱稱為“兄兄弟”（（Sibling）結點下不不再有分分支的稱稱為樹葉葉（leaf）），或者者葉子結結點樹結構的的特點20二叉樹的的特點：：樹中的的每個結結點最多多只有兩兩棵子樹樹，即樹樹中任何何結點的的度數不不得大于于２。二叉樹的的子樹有有左右之之分，稱稱為左子子樹和右右子樹。。而且子子樹的左左右次序序是重要要的，即即使在只只有一棵棵子樹的的情況下下，也應應分清楚楚。例如如圖6-13是是兩棵不不同的二二叉樹。。2．二叉叉樹21所謂遍歷歷二叉樹樹，就是是按一定的的規則和和順序走走遍二叉叉樹的所所有結點點，使每一一個結點點都被訪訪問一次次，而且且只被訪訪問一次次。二叉樹的的遍歷可可分為先序遍歷歷中序遍歷歷后序遍歷歷3．二叉叉樹的遍遍歷221．先序序遍歷遞遞歸算法法定義：：若二叉樹樹非空，，則依次次執行操操作：(1)訪問問根結點點；(2)遍遍歷左左子樹；；(3)遍遍歷右子子樹。ABDGECF2.中序遍歷歷遞歸算算法定義義：若二叉樹樹非空，，則依次次執行操操作：(1)遍歷左左子樹；；(2)訪問問根結點點；(3)遍遍歷右子子樹。GDBEACF3．后序序遍歷遞遞歸算法法定義：：若二叉樹樹非空，，則依次次執行操操作：(1)遍歷左左子樹；；(2)遍歷歷右子樹樹；(3)訪訪問根結結點。GDEBFCA23一個圖由由有限的的頂點（（Vertices））和邊（（Edge）組組成，所所以可形形式化地地用G＝（V，E））代表一個個圖。圖圖中的結結點稱為為頂點，，頂點之之間的連連線代表表邊。圖圖結構24圖(Graph)是由由非空的的頂點集集合和一一個描述述頂點之之間關系系――邊邊（或者者弧）的的集合組組成。其形式化化定義為為：G＝＝（V，，E）V＝{vi|vi∈∈dataobject}E＝{(vi,vj)|vi,vj∈V∧P(vi,vj)}其中，G表示一一個圖，，V是圖圖G中頂頂點的集集合，E是圖G中邊的的集合，，集合E中P(vi,vj)表示頂頂點vi和頂點點vj之之間有一一條直接接連線，，即偶對對(vi,vj)表示示一條邊邊。圖圖結構25下圖（無無向圖G1）給給出了一一個圖的的示例，，在該圖圖中：集合V＝＝{v1,v2,v3,v4}；集合E＝＝{(v1,v3),(v1,v4),(v2,v3),(v2,v4),(V3,V4)}圖圖結構26如果數據據結構中中，數據據元素之之間不考考慮關系系問題（（無前趨趨/后繼繼之分）），則稱稱這種結結構為集合。在集合合中，各各元素是是“平等等”的，，它們的的共同關關系是：：都屬于于同一個個集合。。集合276.3算算法算算法的特特性算法是對對問題求求解過程程的一種種描述，，是為解解決一個個或一類類問題給給出的一一個確定定的、有有限長的的操作序序列。1.有窮窮性2.確定定性3.可行行性4.有輸輸入5.有輸輸出28算法的五五個特性性（1）有窮性：：對任何合合法的輸輸入值，，一個算算法必須須總是在在執行有有窮步之之后結束束，且每每一步都都可在有有窮時間間內完成成；（2）確定性：：算法中每每一條指指令必須須有確切切的含義義，不會會產生二二義性，，對于相相同的輸輸入只能能得出相相同的輸輸出。（3）可行性：：即算法中中描述的的操作都都可以通通過已經經實現的的基本運運算執行行有限次次來實現現的。（4）輸入：一個算法法有0個個或多個個輸入，，這些輸輸入取自自于某個個特定的的數據對對象的集集合，它它可以使使用輸入語句句從外部提提供，也也可以在在算法內內通過賦初值給定。（5）輸出：一個算法法有一個個或多個個的輸出出，這些些輸出是是同輸入入有著某某些特定定關系的的量。29在設計算算法時，，通常應應考慮以以下原則則：首先設計計的算法法必須是是“正確的”其次應有有很好的的“可讀性”，還必必須具有有“健壯性”最后還應應考慮所所設計算算法的復復雜性，，即有““高效率與與低存儲儲量”。什什么是““好”的的算法30算法的正正確性所謂算法法的正確性，也稱可可靠性或或有效性性，是指指：程序不含含語法錯錯誤。程序對于于幾組輸輸入的數數據能夠夠得出滿滿足規格格說明要要求的結結果。程序對于于精心選選擇的典典型、苛苛刻而帶帶有刁難難性的幾幾組輸入入數據能能夠得出出滿足規規格說明明要求的的結果。。程序對于于一切合合法的輸輸入數據據都能產產生滿足足規格說說明要求求的結果果。31在算法是是正確的的前提下下，算法法的可讀性是擺在第第一位的的。可讀讀性好有有助于人人們對算算法的理理解，難難懂的程程序易隱隱藏較多多錯誤，，難以調調試和修修改。算法的效率指的是算算法執行行時計算算機資源源的消耗耗，它包包括運行行時間代代價和存存儲空間間代價。。算法的健壯性指的是，，算法應應對非法法輸入的的數據做做出恰當當反映或或進行相相應處理理。它強強調的是是，如果果輸入非非法數據據時，算算法應能能加以識識別并做做出處理理，而不不是產生生誤動作作或陷入入癱瘓。。32算法的復復雜性是是算法運運行所需需要的計計算機資資源的量量。算法法的復雜雜性是算算法效率率的度量量，是評評價算法法優劣的的重要依依據。算法的復復雜性有有時間復雜雜性和空間復雜雜性之分。需要的時時間資源源的量，，即算法法的運行行速度，，稱作時間復雜雜性。需要的空空間（即即存儲器器）資源源的量稱稱作空間復雜雜性。算算法復雜雜性331．自然然語言自然語言言是人們們日常所所用的語語言，如如漢語、、英語、、德語等等。例如，求求3個數中中最大者者的問題題，可以以描述為為：①比較較前兩個個數。②將①①中較大大的數與與第三個個數進行行比較。。③步驟驟②中較較大的數數即為所所求。算算法的表表示342．流程程圖流程圖是是描述算算法的常常用工具具。它采采用美國國國家標標準化協協會ANSI（（AmericanNationalStandardInstitute）規定定的一組組圖形符符號來表表示算法法起止框判斷框處理框輸入/輸出框注釋框流向線連接點353．偽代代碼偽代碼是是用介于于自然語語言和計計算機語語言之間間的文字字和符號號來描述述算法的的工具。。它不用用圖形符符號，因因此書寫寫方便格格式緊湊湊，易于于理解，，便于向向計算機機程序設設計語言言過渡。。例：求兩兩個數的的較大者者，用偽偽代碼描描述算法法如下：：FindthebiggerInput:twonumbers:a,b1.if(thefirstnumberaisgreaterthanorequaltothesecondnumberb)then1.1returnaelse1.2returnbendifend364．計算算機程序序設計語語言一般而言言，計算算機程序序設計語語言描述述的算法法是清晰晰的、簡簡明的，，最終也也能由計計算機處處理的，，然而也也不是完完善無缺缺。它需需要設計計者用特特定程序序設計語語言編寫寫的算法法，限制制了與他他人的交交流；容容易陷入入描述計計算步驟驟的細節節而忽視視算法的的本質。。376.4程程序設設計方法法計計算機程程序的性性質計算機程序包包含兩方面的的內容：對象及對象之之間關系(數數據結構)；；描述對這些對對象進行處理理的加工規則則(算法)。。38目的性—程序有明確確的目的，程程序運行時能能完成賦予它它的功能。分步性—程序為完成成其復雜的功功能，由一系系列計算機可可執行的步驟驟組成。有序性—程序的執行行步驟是有序序的，不可隨隨意改變程序序步驟的執行行順序。有限性—程序是有限限的指令序列列，程序所包包含的步驟是是有限的。操作性—有意義的程程序總是對某某些對象進行行操作，使其其改變狀態，，完成其功能能。計算機程序具具有以下性質質：39數據結構是數數據構造的邏邏輯表示形式式，算法是處處理問題的方方法和步驟，，最后問題的的解由計算機機程序給出。。這是程序員員在程序設計計時應考慮的的主要問題。。程程序設計計與數據結構構、算法之間間的關系401.程序的控制結結構一個可以用順序、選擇、、循環和跳轉轉(如goto語句)四種程程序結構解決決的問題，也也一定能用順順序、選擇、、循環三種程程序結構解決決。但確實存在這這樣的問題，，它可以用順順序、選擇、、循環三種程程序結構解決決，但不能用用其中任何兩兩種解決。換句話說，順順序、選擇、、循環三種程程序結構構成成了一個最小小完備集。我我們將這三種種程序結構叫叫基本程序結構構。結結構化程序序設計41三種基本結構構的圖示：順序結構選擇結構42循環結構的圖圖示：當型(While型)循循環結構直到型(Until型)循環43順序程序設計計44分支結構45循環結構462.結構化程程序設計方法法結構化程序設設計方法主要要包括程序結結構的自頂向向下和模塊化化設計方法。。47程序設計的一一般步驟如下下：1.分析問題題對要解決的問問題，首先必必須分析清楚楚，明確題目目的要求，列列出所有已知知量，找出題題目的求解范范圍、解的精精度等。2.建立數學學模型對實際問題進進行分析之后后，找出它的的內在規律，，就可以建立立數學模型。。只有建立了了模型的問題題，才能可能能利用計算機機來解決。3.確定算法法建立數學模型型后，還不能能著手編程序序，必須根據據數據結構，，確定解決問問題的算法。。一般確定算算法要注意：：算法的邏輯結結構盡可能簡簡單；算法所要求的的存貯量應盡盡可能少；在滿足題目條條件要求下，，使所需的計計算量最小。程程序設計的的步驟484.編寫程序序把整個程序看看作一個整體體，先全局后后局部，自頂頂向下，一層層一層分解處處理，如果某某些子問題的的算法相同而而僅參數不同同，可以用子子程序來表示示。5.調試運行行；6.分析結果果；7.寫出程序序的文檔主要是對程序序中的變量、、函數或過程程作必要的說說明，解釋編編程思路，需需要時給出程程序流程圖，，并討論運行行結果。499、靜夜四無無鄰，荒居居舊業貧。。。1月-231月-23Sunday,January1,202310、雨中中黃葉葉樹，，燈下下白頭頭人。。。20:48:1820:48:1820:481/1/20238:48:18PM11、以我我獨沈沈久，，愧君君相見見頻。。。1月-2320:48:1820:48Jan-2301-Jan-2312、故人江海別別，幾度隔山山川。。20:48:1920:48:1920:48Sunday,January1,202313、乍見翻翻疑夢，，相悲各各問年。。。1月-231月-2320:48:1920:48:19January1,202314、他鄉生白白發，舊國國見青山。。。01一月月20238:48:19下下午20:48:191月-2315、比不了了得就不不比，得得不到的的就不要要。。。。一月238:48下午午1月-2320:48January1,202316、行動動出成成果，，工作作出財財富。。。2023/1/120:48:1920:48:1901January202317、做前，能夠夠環視四周；；做時，你只只能或者最好好沿著以腳為為起點的射線線向前。。8:48:19下午8:48下下午20:48:191月-239、沒有失敗敗，只有暫暫時停止成成功！。1月-231月-23Sunday,January1,202310、很很多多事事情情努努力力了了未未必必有有結結果果，，但但是是不不努努力力卻卻什什么么改改變變也也沒沒有有。。。。20:48:1920:48:1920:481/1/20238:48:19PM11、成功就就是日復復一日那那一點點點小小努努力的積積累。。。1月-2320:48:1920:48Jan-2301-Jan-2312、世間成成事，不不求其絕絕對圓滿滿，留一一份不足足，可得得無限完完美。。。20:48:1920:48:1920:48Sunday,January1,202313、不知知香積積寺，，數里里入云云峰。。。1月-231月-2320:48:1920:48:19January1,202314、意意志志堅堅強強的的人人能能把把世世