華中科技電子與信息工程系大二上學(xué)期學(xué)習(xí)數(shù)構(gòu)數(shù)據(jù)結(jié)構(gòu)課件

數(shù)據(jù)結(jié)構(gòu)劉應(yīng)狀華中科技大學(xué)電信系講授內(nèi)容關(guān)系（結(jié)構(gòu)）第一章 緒論第二章 線性表第三章 棧和隊(duì)列第四章

串第五章 數(shù)組和廣義表第六章 樹(shù)和二叉樹(shù)第七章

圖第九章 查找第十章 內(nèi)部排序操作第一章

緒

論內(nèi)容

什么是數(shù)據(jù)結(jié)構(gòu)？為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)？基本概念和術(shù)語(yǔ)抽象數(shù)據(jù)類(lèi)型的表示和實(shí)現(xiàn)算法和算法分析1、什么是數(shù)據(jù)結(jié)構(gòu)？考察兩個(gè)例子：例1：字典的排序與查找問(wèn)題隨機(jī)排序： 查找方法：兩種排序有序排列： 查找方法：例2：檔案管理問(wèn)題按照兩種方式管理：1）隨機(jī)存放：相應(yīng)的查找方法：順序查找2）按照下面方式存放：查找方法學(xué)

校計(jì)算機(jī)系電信系其它系自控系教師學(xué)生其他人員99級(jí)2000級(jí)2001級(jí)2002級(jí)………………………例子的結(jié)論同樣的對(duì)象（字、檔案等），用不同的

存放（表示）方式和查找（操作）方法，效率有明顯的差異。抽象對(duì)象、對(duì)象之間的關(guān)系、操作“數(shù)據(jù)結(jié)構(gòu)”的研究?jī)?nèi)容（見(jiàn)教材P3）2、為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)？數(shù)學(xué)軟件硬件這是由“數(shù)據(jù)結(jié)構(gòu)”所研究的內(nèi)容和我們所學(xué)習(xí)的專(zhuān)業(yè)共同決定的關(guān)系對(duì)象關(guān)系操作對(duì)象關(guān)系操作3、基本概念和術(shù)語(yǔ)數(shù) 據(jù)：是對(duì)客觀事物的符號(hào)表示，客觀世界上所有的事物（如：文字、圖象、聲音等）都可以用數(shù)據(jù)來(lái)表示。在計(jì)算機(jī)科學(xué)中，它是指所有能夠被計(jì)算機(jī)所處理的符號(hào)的總稱(chēng)。數(shù)據(jù)元素：數(shù)據(jù)的基本單位，一個(gè)數(shù)據(jù)元素又可以分為若干個(gè)數(shù)據(jù)項(xiàng)，數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位。數(shù)據(jù)對(duì)象：性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。比如：正整數(shù)對(duì)象是集合N={0，2，3….}，字母對(duì)象是集合C={‘A’，’B’，…}數(shù)據(jù)結(jié)構(gòu)：相互之間存在關(guān)系的數(shù)據(jù)元素的集合。這里，數(shù)據(jù)元素之間的關(guān)系稱(chēng)為結(jié)構(gòu)，也就是說(shuō)數(shù)據(jù)結(jié)構(gòu)是具有某種結(jié)構(gòu)的數(shù)據(jù)元素的集合。通常，數(shù)據(jù)元素之間的關(guān)系有以下四種：1）集合結(jié)構(gòu)：數(shù)據(jù)元素之間只有“屬于同一個(gè)集合”的關(guān)系，沒(méi)有其他關(guān)系。如下圖所示：集合結(jié)構(gòu)2）線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。如下圖所示：線性結(jié)構(gòu)3）樹(shù)形結(jié)構(gòu)：數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。如下圖所示：樹(shù)形結(jié)構(gòu)4）圖狀結(jié)構(gòu)：數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。如下圖所示：圖狀結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的數(shù)學(xué)定義：Data_Structure

=

(D,S)其中，D表示數(shù)據(jù)元素的有限集合，S是D上關(guān)系的有限集合。舉例：見(jiàn)教材P5以上對(duì)數(shù)據(jù)結(jié)構(gòu)的定義是一種邏輯上的定義，它定義了數(shù)據(jù)元素（操作對(duì)象）之間的邏輯

關(guān)系。因此，我們又稱(chēng)為數(shù)據(jù)的邏輯結(jié)構(gòu)。在數(shù)據(jù)結(jié)構(gòu)中，僅僅討論數(shù)據(jù)的邏輯結(jié)構(gòu)是

不夠的，我們還必須知道這種邏輯結(jié)構(gòu)在計(jì)

算機(jī)中是如何表示的。我們將數(shù)據(jù)的邏輯結(jié)

構(gòu)在計(jì)算機(jī)中的表示（映象）叫做數(shù)據(jù)的物理結(jié)構(gòu)（又稱(chēng)存儲(chǔ)結(jié)構(gòu)）。數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中有兩種映射方式：順序映象和非順序映象。由此得到兩種不同的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)：邏輯上相鄰的兩個(gè)元素，在存儲(chǔ)器中仍然相鄰。所有的元素在存儲(chǔ)器中是按照順序存放的。用數(shù)組即可實(shí)現(xiàn)順序存儲(chǔ)。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：邏輯上相鄰的兩個(gè)元素，在存儲(chǔ)器中不一定相鄰。它需要借助于指針來(lái)實(shí)現(xiàn)的。數(shù)據(jù)類(lèi)型：是一個(gè)值的集合和定義在該值上的一組操作的總稱(chēng)。抽象數(shù)據(jù)類(lèi)型：是一個(gè)數(shù)學(xué)模型加上定義在該模型上的一組操作。抽象數(shù)據(jù)類(lèi)型的定義僅僅取決于它的一組邏輯特性，而與它在計(jì)算機(jī)內(nèi)如何表示和實(shí)現(xiàn)無(wú)關(guān)，它與數(shù)據(jù)類(lèi)型實(shí)質(zhì)上是一個(gè)概念。抽象數(shù)據(jù)類(lèi)型可以用以下的三元組來(lái)表示：ADT

=

（D，S，P）其中，D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系集，P是D上的操作集。以后，我們采用以下格式定義抽象數(shù)據(jù)類(lèi)型（ADT）ADT抽象數(shù)據(jù)類(lèi)型名{數(shù)據(jù)對(duì)象：<數(shù)據(jù)對(duì)象的定義>數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>基本操作：<基本操作的定義>}ADT抽象數(shù)據(jù)類(lèi)型名4、抽象數(shù)據(jù)類(lèi)型的表示和實(shí)現(xiàn)抽象數(shù)據(jù)類(lèi)型可以通過(guò)固有的數(shù)據(jù)類(lèi)型（如：整型、實(shí)型、字符型等）來(lái)表示和實(shí)現(xiàn)。為了使算法具有更好的可讀性，本課程將用介于偽碼和C語(yǔ)言之間的類(lèi)C語(yǔ)言作為描述工具。有關(guān)類(lèi)C語(yǔ)言的描述語(yǔ)法見(jiàn)教材P10-115、算法和算法分析算法的定義是對(duì)特定問(wèn)題求解步驟的一種描述，它是指令的有限序列。算法的特性1、有窮性2、確定性3、可行性4、輸入、輸出算法設(shè)計(jì)的要求1、正確性2、可讀性3、健壯性4、效率與低存儲(chǔ)量需求算法效率的量度1、計(jì)算時(shí)間2、算法的規(guī)模時(shí)間復(fù)雜度算法中基本操作的重復(fù)次數(shù)，通常用O(f(n))表示，如