1、數(shù)據(jù)結(jié)構(gòu)第一章 緒論課程介紹：1、計(jì)算機(jī)應(yīng)用技術(shù)專業(yè)的核心課程； 數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的一門專業(yè)技術(shù)基礎(chǔ)課。該課程是計(jì)算機(jī)科學(xué)的算法理論基礎(chǔ)和軟件設(shè)計(jì)的技術(shù)基礎(chǔ)，主要研究信息的邏輯結(jié)構(gòu)及其基本操作在計(jì)算機(jī)中的表示和實(shí)現(xiàn)。2、應(yīng)用軟件開(kāi)發(fā)必備理論知識(shí)； 1）人機(jī)對(duì)弈 樹(shù)形結(jié)構(gòu) 2）如何實(shí)現(xiàn)打印時(shí)次序不亂 隊(duì)列 3）漢字輸入時(shí)如何使常用字排在前面 查找方法 4）圖書(shū)館書(shū)目檢索 線性表 5）城市的交通布線及信號(hào)燈的顯示 圖本課程是一門綜合理論課程，理論性比較強(qiáng)，比較抽象，同時(shí)也比較枯燥。教學(xué)上主要采用課堂講授的方式來(lái)學(xué)習(xí)，為了激發(fā)同學(xué)的學(xué)習(xí)興趣，同時(shí)也采用游戲式、啟發(fā)式、討論式、自主式多種

2、教學(xué)方法相輔。希望同學(xué)們能積極主動(dòng)的參與進(jìn)來(lái)，使我們的課堂變得生動(dòng)活潑。學(xué)習(xí)目標(biāo)：了解數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念掌握邏輯數(shù)據(jù)結(jié)構(gòu)線性表樹(shù)圖熟悉常用查找方法原理及使用方法熟悉常用排序方法原理及使用方法掌握常用算法1.1 什么是數(shù)據(jù)結(jié)構(gòu) 1.2 基本概念和術(shù)語(yǔ)1.3 抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)1.4 算法和算法分析 1.1 什么是數(shù)據(jù)結(jié)構(gòu)一般來(lái)說(shuō)，用計(jì)算機(jī)解決一個(gè)具體問(wèn)題時(shí)，大致需要經(jīng)過(guò)下列幾個(gè)步驟：具體問(wèn)題數(shù)學(xué)模型算法程序例子：圖書(shū)館的書(shū)目檢索系統(tǒng)人機(jī)對(duì)弈問(wèn)題交通燈的管理例 1 書(shū)目自動(dòng)檢索系統(tǒng)例 2 人機(jī)對(duì)奕問(wèn)題例 3 多叉路口交通燈管理問(wèn)題例 4 城市間的通信布線問(wèn)題數(shù)據(jù)結(jié)構(gòu)定義: 是一門研究非數(shù)值計(jì)

3、算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等等的學(xué)科。1.2基本概念和術(shù)語(yǔ)數(shù)據(jù)是對(duì)客觀事物的符號(hào)表示，在計(jì)算機(jī)科學(xué)中是指所有能輸入計(jì)算機(jī)并能被計(jì)算機(jī)處理的符號(hào)的總稱。數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。例如一個(gè)棋盤(pán)格局、一個(gè)城市結(jié)點(diǎn)、線性表中一條記錄等。 一個(gè)數(shù)據(jù)元素是由若干個(gè)數(shù)據(jù)項(xiàng)組成的。數(shù)據(jù)項(xiàng)是數(shù)據(jù)元素的詳細(xì)描述，是數(shù)據(jù)處理中不可分割的最小單位。數(shù)據(jù)對(duì)象是具有相同性質(zhì)的數(shù)據(jù)元素的集合。 數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。在任何問(wèn)題中，數(shù)據(jù)元素都不是孤立存在的，而是在它們之間存在著某種關(guān)系，這種數(shù)據(jù)元素相互之間的關(guān)系

4、稱為結(jié)構(gòu)。 根據(jù)數(shù)據(jù)元素之間的不同特性，通常有下列四類基本結(jié)構(gòu)：集合：集合結(jié)構(gòu)中的所有元素都“屬于同一集合”，即只要滿足同屬于一個(gè)集合就是集合結(jié)構(gòu)，這是一種極為松散的結(jié)構(gòu)。線性結(jié)構(gòu)：該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對(duì)一關(guān)系。樹(shù)形結(jié)構(gòu)：該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對(duì)多關(guān)系。圖形結(jié)構(gòu)：該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著多對(duì)多的關(guān)系，圖形結(jié)構(gòu)也稱為網(wǎng)狀結(jié)構(gòu)?；窘Y(jié)構(gòu)圖例：線形結(jié)構(gòu)：元素關(guān)系為“一對(duì)一”樹(shù)形結(jié)構(gòu)：元素關(guān)系為“一對(duì)多”圖狀結(jié)構(gòu)：元素關(guān)系為“多對(duì)多”集合結(jié)構(gòu)：元素關(guān)系為“同屬于”思考：對(duì)四種基本結(jié)構(gòu)分別舉出例子大街上熙熙攘攘的人群是“集合”火車站上排隊(duì)買票的長(zhǎng)龍是“線性結(jié)構(gòu)”四世同堂的大家族是“樹(shù)形結(jié)

5、構(gòu)”濟(jì)南一日游線路是“圖結(jié)構(gòu)”示例：linear=(D, R)D=1,2,3,4,5,6,7,8,9 R=, , ,邏輯圖為：示例：tree=(D, R)D=a,b,c,d,e,f,g,h,i,j,k,lR=(a,b),(a,c),(a,d),(b,e),(b,f),(b,g),(c,h),(c,i),(c,j),(d,k),(d,l)邏輯圖為:習(xí)題：設(shè)數(shù)據(jù)元素的集合為D=d1, d2, d3, d4, d5，畫(huà)出各關(guān)系R對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)B=(D, R)的圖形，并判斷其所屬邏輯結(jié)構(gòu)的類型？ R=(d1, d2), (d2, d4), (d1, d3), (d2, d5) R=(d5, d4),

6、(d4, d3), (d3, d1), (d1, d2) R=(di, dj)| i j數(shù)據(jù)結(jié)構(gòu)分類：數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的物理結(jié)構(gòu)。從實(shí)際問(wèn)題中抽象出來(lái)的數(shù)學(xué)模型，結(jié)構(gòu)中的“關(guān)系”描述的是數(shù)據(jù)元素之間的邏輯關(guān)系，因此又稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。集合、線性結(jié)構(gòu)、樹(shù)、圖 數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（又稱映像）稱為數(shù)據(jù)的物理結(jié)構(gòu)，或稱存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中的表示方法（數(shù)據(jù)的物理結(jié)構(gòu)）有兩種：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)分類數(shù)據(jù)結(jié)構(gòu)的物理結(jié)構(gòu)分類數(shù)據(jù)類型：數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)值的集合上的一組操作的總稱。數(shù)據(jù)類型分為兩類1、原子類型 基本數(shù)據(jù)類型有：

7、整型（int）：存儲(chǔ)整型量，如123，-7浮點(diǎn)型（float）：表示實(shí)型數(shù)據(jù)（帶有小數(shù)點(diǎn)），如3.14159等字符型（char）：表示單個(gè)字符，如a 2、結(jié)構(gòu)類型，如數(shù)組、結(jié)構(gòu)體。數(shù) 組：用于保存一批相同類型的數(shù)據(jù)；結(jié)構(gòu)體（structure）是一種數(shù)據(jù)類型，它把互相聯(lián)系的數(shù)據(jù)組合成一個(gè)整體。例：1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)抽象數(shù)據(jù)類型：抽象數(shù)據(jù)類型（ADT）是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型的定義取決于它的一組邏輯特性，而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無(wú)關(guān)，即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變，都不影響其外部的使用。本書(shū)中所定義的抽象數(shù)據(jù)類型，既可以是整型

8、、實(shí)型、字符型或某種結(jié)構(gòu)體類型，具體使用時(shí)只需將它重新定義一下即可。 抽象數(shù)據(jù)類型可以用三元組表示：ADT = (D, S, P) 其中，D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系集，P是對(duì)D的基本操作集。1.4 算法和算法分析算法（algorithm）解決某一特定問(wèn)題的具體步驟的描述，是指令的有限序列，其中每個(gè)指令表示一個(gè)或多個(gè)操作。算法的特性有窮性：一條指令都只能執(zhí)行有限次，算法必須在執(zhí)行有限步后結(jié)束確定性：算法中每條指令的含義必須明確，不允許有二義性可行性：算法應(yīng)該在有限時(shí)間內(nèi)執(zhí)行完畢輸入：算法開(kāi)始前必須給算法中用到的變量賦初值，即算法的輸入可包含零個(gè)數(shù)據(jù)或多個(gè)數(shù)據(jù)(也稱為輸入數(shù)據(jù))，這些輸入數(shù)據(jù)取自確定的對(duì)象集合輸出：算法有一個(gè)或多個(gè)輸出算法設(shè)計(jì)的要求正確性可讀性健壯性效率與低存儲(chǔ)量需求算法效率的度量：時(shí)間復(fù)雜度和空間復(fù)雜度設(shè)：執(zhí)行每條語(yǔ)句所需時(shí)間為單位時(shí)間，則：算法耗費(fèi)時(shí)間=基本語(yǔ)句的重復(fù)執(zhí)行的次數(shù)之和。例1：NXN矩陣相乘for(i=1;i=n;i+) for(j=1;j=n;j+) cij=0; for(k=1;k=n;k+) cij=cij+aik*bkj; +x;s=0For (i=1;i=n;+i)+x;s+=xFor(j=1;j=n;+j) for(k=1;k=n;+k)+x;s+=x;O(1)、O(n)、O(n2)練習(xí)：For(i