數據結構討論的是數據的邏輯結構

數據結構討論的是數據的邏輯結構第1頁，共21頁，2023年，2月20日，星期六1.1數據結構

1.1.1數據結構隨著計算機軟、硬件的發(fā)展，計算機的應用范圍在不斷擴大，計算機所處理的數據的數量也在不斷擴大，計算機所處理的數據已不再是單純的數值數據，而更多的是非數值數據。需要處理的數據并不是雜亂無章的，它們一定有內在的聯系，只有弄清楚它們之間的本質的聯系，才能使用計算機對大量的數據進行有效的處理。第2頁，共21頁，2023年，2月20日，星期六某電信公司的市話用戶信息表格如下圖所示：序號用戶名電話號碼用戶住址街道名門牌號00001萬方林3800235北京西路165900002吳金平3800667北京西路209900003王

冬5700123瑤湖大道198700004王

三5700567瑤湖大道200800005江

凡8800129學府大道5035這里序號、用戶名、電話號碼等項稱為基本項，它是有獨立意義的最小標識單位，而用戶住址稱為組合項，組合項是由一個或多個基本項或組合項組成，是有獨立意義的標識單位，每一行稱為一個結點，每一個組合項稱為一個字段。使用計算機處理用戶信息表中的數據時，必須弄清楚下面3個問題：第3頁，共21頁，2023年，2月20日，星期六1數據的邏輯結構這些數據之間有什么樣的內在聯系？除最前和最后兩個結點之外，表中所有其它的結點都有且僅有一個和它相鄰位于它之前的一個結點，也有且僅有一個和它相鄰位于它之后的一個結點，這些就是用戶信息表的邏輯結構。2數據的存儲結構

將用戶信息表中的所有結點存入計算機時，就必須考慮存儲結構，使用C語言進行設計時，常見的方式是用一個結構數組來存儲整個用戶信息表，每一個數組元素是一個結構，它對應于用戶信息表中的一個結點。數據在計算機的存儲方式稱為存儲結構。第4頁，共21頁，2023年，2月20日，星期六3數據的運算集合

數據處理必涉及到相關的運算，在上述用戶信息表中，可以有刪除一個用戶、增加一個用戶和查找某個用戶等操作。應該明確指明這些操作的含義。比如刪除操作，是刪除序號為5的用戶還是刪除用戶名為王三的用戶是應該明確定義的，如果需要可以定義兩個不同的刪除操作，為一批數據定義的所有運算（或稱操作）構成一個運算（操作）集合。對待處理的數據，只有分析清楚上面3個方面的問題，才能進行有效的處理！

數據結構就是指按一定的邏輯結構組成的一批數據，使用某種存儲結構將這批數據存儲于計算機中，并在這些數據上定義了一個運算集合。第5頁，共21頁，2023年，2月20日，星期六1.1.2數據的邏輯結構

數據的邏輯結構是數據和數據之間所存在的邏輯關系，它可以用一個二元組B=（K，R）來表示，其中K是數據、即結點的有限集合；R是集合K上關系的有限集合，這里的關系是從集合K到集合K的關系，這里一般只涉及到一個關系的邏輯結構。例如，有5個人，分別記為a,b,c,d,e,其中a是b的父親，b是c的父親，c是d的父親,d是e的父親，如果只討論他們之間所存在的父子關系，則可以用下面的二元組形式化地予以表達。B=（K，R）其中：K={a,b,c,d,e}R={r}r={<a,b>,<b,c>,<c,d>,<d,e>}第6頁，共21頁，2023年，2月20日，星期六邏輯結構的圖形表示方式，對K中的每個結點ki用一個方框表示，而結點之間的關系用帶箭頭的線段表示，這5人之間的邏輯結構用圖形的方式表達如下圖

所示。若ki∈K，kj∈R，<ki,kj>∈r，則稱ki是kj的相對于關系r的前驅結點，kj是ki的相對于關系r的后繼結點，因為一般只討論具有一種關系的邏輯結構，即R={r}，所以簡稱ki是kj前驅，kj是ki的后繼。如果某個結點沒有前驅結點，稱之為開始結點；如果某個結點沒有后繼結點，稱之為終端結點；既不是開始結點也不是終端結點的結點稱為內部結點。第7頁，共21頁，2023年，2月20日，星期六1.1.3數據的存儲結構數據的邏輯結構是獨立于計算機的，它與數據在計算機中的存儲無關，要對數據進行處理，就必須將數據存儲在計算機中。如果將數據在計算機中無規(guī)律地存儲，那么在處理時是非常糟的，是沒有用的。試想一下，如果一本英漢字典中的單詞是隨意編排的，這本字典誰會用！對于一個數據結構B=（K，R），必須建立從結點集合到計算機某個存儲區(qū)域M的一個映象，這個映象要直接或間接地表達結點之間的關系R。數據在計算機中的存儲方式稱為數據的存儲結構。數據的存儲結構主要有4種。第8頁，共21頁，2023年，2月20日，星期六數據的存儲結構主要有4種。1順序存儲順序存儲通常用于存儲具有線性結構的數據。將邏輯上相鄰的結點存儲在連續(xù)存儲區(qū)域M的相鄰的存儲單元中，使得邏輯相鄰的結點一定是物理位置相鄰。對于一個數據結構B=（K，R）其中K={k1,k2,k3,k4,k5,k6,k7,k8,k9}R={r}r={<k1,k2>,<k2,k3>,<k3,k4>,<k4,k5>,<k5,k6>,<k6,k7>,<k7,k8>,<k8,k9>}它的順序存儲方式如圖所示第9頁，共21頁，2023年，2月20日，星期六2鏈式存儲鏈式存儲方式是給每個結點附加一個指針段，一個結點的指針所指的是該結點的后繼的存儲地址，因為一個結點可能有多個后繼，所以指針段可以是一個指針，也可以是一個多個指針。例，數據的邏輯結構B=（K，R）

其中

K={k1,k2,k3,k4,k5}R={r}R={<k1,k2>,<k2,k3>,<k3,k4>,<k4,k5>}這是一個線性結構，它的鏈式存儲如圖所示。第10頁，共21頁，2023年，2月20日，星期六3索引存儲在線性結構中，設開始結點的索引號為1，其它結點的索引號等于其前繼結點的索引號加1，則每一個結點都有唯一的索引號，索引號就是根據結點的索引號確定該結點的存儲地址。4散列存儲散列存儲的思想是構造一個從集合K到存儲區(qū)域M的一個函數h，該函數的定義域為K，值域為M，K中的每個結點ki在計算機中的存儲地址由h(ki)確定。第11頁，共21頁，2023年，2月20日，星期六1.1.4數據的運算集合

對于一批數據，數據的運算是定義在數據的邏輯結構之上的，而運算的具體實現就依賴于數據的存儲結構。數據的運算集合要視情況而定，一般而言，數據的運算包括插入、刪除、檢索、輸出、排序等。插入：在一個結構中增加一個新的結點。刪除：在一個結構刪除一個結點。檢索：在一個結構中查找滿足條件的結點。輸出：將一個結構中所有結點的值打印、輸出。排序：將一個結構中所有結點按某種順序重新排列。第12頁，共21頁，2023年，2月20日，星期六在程序設計中，數據和運算是兩個不可缺少的因素。所有的程序設計活動都是圍繞著數據和其上的相關運算而進行的。從機器指令、匯編語言中的數據沒有類型的概念，到現在的面向對象程序設計語言中抽象數據類型概念的出現，程序設計中的數據經歷了一次次抽象，數據的抽象經歷了三個發(fā)展階段。1.2數據類型和抽象數據類型從無類型的二進制數到基本數據類型的產生從基本數據類型到用戶自定義類型的產生從用戶自定義類型到抽象數據類型的出現第13頁，共21頁，2023年，2月20日，星期六1.2.1數據類型數據類型（或簡稱類型）反映了數據的取值范圍以及對這類數據可以施加的運算。1.2.2數據結構

數據結構是計算機科學中廣泛使用的一個術語，在計算機科學中具有非常重要的作用。數據結構包括三個方面的內容：一組數據中各數據之間的邏輯關系；這組數據在計算機中的存儲方式；對這組數據所能施加的運算的集合。數據結構是數據存在的形式。所有的數據都是按照數據結構進行分類的。簡單數據類型對應于簡單的數據結構；構造數據類型對應于復雜的數據結構。第14頁，共21頁，2023年，2月20日，星期六1.2.3抽象數據類型

抽象數據類型是與表示無關的數據類型，是一個數據模型及定義在該模型上的一組運算。對一個抽象數據類型進行定義時，必須給出它的名字及各運算的運算符名，即函數名，并且規(guī)定這些函數的參數性質。一旦定義了一個抽象數據類型及具體實現，程序設計中就可以像使用基本數據類型那樣，十分方便地使用抽象數據類型。1.2.4抽象數據類型的描述和實現

抽象數據類型的描述包括給出抽象數據類型的名稱、數據的集合、數據之間的關系和操作的集合等方面的描述。抽象數據類型的設計者根據這些描述給出操作的具體實現，抽象數據類型的使用者依據這些描述使用抽象數據類型。第15頁，共21頁，2023年，2月20日，星期六抽象數據類型描述的一般形式如下：ADT抽象數據類型名稱{

數據對象：

……

數據關系：

……

操作集合：操作名1：

…………

操作名n：}ADT抽象數據類型名稱第16頁，共21頁，2023年，2月20日，星期六1.3算法和算法分析

1.3.1算法

為了求解某問題，必須給出一系列的運算規(guī)則，這一系列的運算規(guī)則是有限的，表達了求解問題方法和步驟，這就是一個算法。

一個算法可以用自然語言描述，也可以用高級程序設計語言描述，也可以用偽代碼描述。本書采用C語言對算法進行描述。第17頁，共21頁，2023年，2月20日，星期六算法具有五個基本特征：①有窮性，算法的執(zhí)行必須在有限步內結束。②確定性，算法的每一個步驟必須是確定的無二義性的。③輸入，

算法可以有0個或多個輸入。④輸出，

算法一定有輸出結果⑤可行性，算法中的運算都必須是可以實現的。算法具有有窮性，程序不需要具備有窮性。一般的程序都會在有限時間內終止，但有的程序卻可以不在有限時間內終止，如一個操作系統在正常情況下是永遠都不會終止的。第18頁，共21頁，2023年，2月20日，星期六1.3.2算法的時間和空間復雜性

一個算法的優(yōu)劣主要從算法的執(zhí)行時間和所需要占用的存儲空間兩個方面衡量，算法執(zhí)行時間的度量不是采用算法執(zhí)行的絕對時間來計算的，因為一個算法在不同的機器上執(zhí)行所花的時間不一樣，在不同時刻也會由于計算機資源占用情況的不同，使得算法在同一臺計算機上執(zhí)行的時間也不一樣，所以對于算法的時間復雜性，采用算法執(zhí)行過程中其基本操作的執(zhí)行次數，稱為計算量來度量。算法中基本操作的執(zhí)行次數一般是與問題規(guī)模有關的，對于結點個數為n的數據處理問題，用T(n)表示算法基本操作的執(zhí)行次數。第19頁，共21頁，2023年，2月20日，星期六在評價算法的時間復雜性時，不考慮兩算法執(zhí)行次數之間的細小區(qū)別，而只關心算法的本質差別。為此，引入一個所謂的O()記號，則T1(n)=2n=O(n),T2(n)=n+1=O(n)。一個函數f(n)是O(g(n))的，則一定存在正常數c和m，使對所有的n>m，都滿足f(n)<c*g(n)。下面的表格給出了一些具體函數的O()的表示，如圖所示。f(n)O(g(n))量級35O(1)常數階2n+7