1.1數(shù)據(jù)結(jié)構(gòu)基本概念2

1、第 1章 數(shù)據(jù)結(jié)構(gòu) 1.1 數(shù)據(jù)結(jié)構(gòu)的基本概念與算法 1.2 線性表 1.3 棧和隊(duì)列1.4 樹和二叉樹 1.5 查找1.6 內(nèi)部排序ABCDEFG姓名 學(xué)號 成績 班級 李紅 9761059 95 機(jī)97.6 1065865計(jì)算機(jī)是一門研究用計(jì)算機(jī)進(jìn)行信息表示和處理的科學(xué)。這里面涉及到兩個問題： 信息的表示 信息的處理 而信息的表示和存儲又直接關(guān)系到處理信息的程序的效率。隨著計(jì)算機(jī)的普及，信息量的增加，信息范圍的拓寬，使許多系統(tǒng)程序和應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)又相當(dāng)復(fù)雜。因此，為了編寫出一個“好”的程序，必須分析待處理的對象的特征及各對象之間存在的關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)這門課所要研究的問題。什么

2、是數(shù)據(jù)結(jié)構(gòu) 下面文字的含義： 漆黑的頭發(fā)沒有麻子腳不大周正 演繹 漆黑的頭發(fā)，沒有麻子，腳不大，周正。結(jié)論：描述一個古代美人！ 演繹 漆黑的頭發(fā)沒有，麻子，腳不大周正。結(jié)論：描述了一個古代丑女人，還是個瘸子。結(jié)論 兩個不同的演繹表現(xiàn)為不同的結(jié)果，一個是古代美人，一個確實(shí)古代丑女人，原因只是文字的不同組合造成！也就是說：相同的文字（數(shù)據(jù)）經(jīng)過不同的組合（結(jié)構(gòu)）會得到不同的結(jié)果，這就是我們要介紹的數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)及其之間的關(guān)系（結(jié)構(gòu)）。1.1 數(shù)據(jù)結(jié)構(gòu)的基本概念與算法1.數(shù)據(jù)結(jié)構(gòu)的定義1). 數(shù)據(jù)： 信息載體，能夠被計(jì)算機(jī)識別、存儲和加工處理。可以是數(shù)值數(shù)據(jù)(整數(shù)、實(shí)數(shù))，也可以是非數(shù)值數(shù)據(jù)(聲音、

3、圖像等) 。2). 數(shù)據(jù)項(xiàng): 是數(shù)據(jù)的具有獨(dú)立含義的不可分割的最小標(biāo)識單位,如成績表中學(xué)號,姓名等.3). 數(shù)據(jù)元素： 一個數(shù)據(jù)元素由若干數(shù)據(jù)項(xiàng)組成,是數(shù)據(jù)的基本單位，通常作為一個整體進(jìn)行考慮和處理(又稱結(jié)點(diǎn)、記錄)。 1.1.1數(shù)據(jù)結(jié)構(gòu)的基本概念學(xué)號姓名系別住址電話981111李洪機(jī)械六舍5371111982111王剛電子四舍5372111983211王將計(jì)算機(jī)五舍5373211983212張強(qiáng)機(jī)械六舎53722214個數(shù)據(jù)元素5個數(shù)據(jù)項(xiàng)1個數(shù)據(jù)項(xiàng)1個數(shù)據(jù)元素4). 數(shù)據(jù)對象: 具有相同性質(zhì)的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個子集。 例: 成績表 學(xué)號姓名系別住址電話981111李洪機(jī)械六舍537

4、1111982111王剛電子四舍5372111983211王將計(jì)算機(jī)五舍5373211983212張強(qiáng)機(jī)械六舎53722211.數(shù)據(jù)結(jié)構(gòu)的定義1). 數(shù)據(jù)：2). 數(shù)據(jù)項(xiàng): 3). 數(shù)據(jù)元素： 關(guān)鍵碼：值唯一能區(qū)別不同的數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)數(shù)據(jù)對象-由4個記錄組成,表中每行是一個記錄,每個記錄由5個數(shù)據(jù)項(xiàng)組成.1.1 數(shù)據(jù)結(jié)構(gòu)的基本概念與算法1.1.1數(shù)據(jù)結(jié)構(gòu)的基本概念1.數(shù)據(jù)結(jié)構(gòu)的定義1). 數(shù)據(jù)：2). 數(shù)據(jù)項(xiàng): 3). 數(shù)據(jù)元素： 4). 數(shù)據(jù)對象: 5).數(shù)據(jù)結(jié)構(gòu): 相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。 研究 內(nèi)容數(shù)據(jù)的邏輯結(jié)構(gòu)： 各數(shù)據(jù)元素之間的邏輯關(guān)系數(shù)據(jù)的存儲結(jié)構(gòu)： 各數(shù)據(jù)

5、元素在計(jì)算機(jī)中的存儲關(guān)系對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算： 添加，刪除，排序等。1.1 數(shù)據(jù)結(jié)構(gòu)的基本概念與算法1.1.1數(shù)據(jù)結(jié)構(gòu)的基本概念1.數(shù)據(jù)結(jié)構(gòu)的定義1). 數(shù)據(jù)：2). 數(shù)據(jù)項(xiàng): 3). 數(shù)據(jù)元素： 4). 數(shù)據(jù)對象: 5).數(shù)據(jù)結(jié)構(gòu): 相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。 研究 目的一是提高數(shù)據(jù)處理的速度.二是盡量節(jié)省在數(shù)據(jù)處理過程中所占用的計(jì)算機(jī)存儲空間.1.1 數(shù)據(jù)結(jié)構(gòu)的基本概念與算法1.1.1數(shù)據(jù)結(jié)構(gòu)的基本概念1.數(shù)據(jù)結(jié)構(gòu)的定義2.數(shù)據(jù)的邏輯結(jié)構(gòu)集合元素間為松散的關(guān)系 (屬于關(guān)系)線性結(jié)構(gòu)元素間為一對一關(guān)系樹形結(jié)構(gòu)元素間為一對多關(guān)系圖狀結(jié)構(gòu)元素間為多對多關(guān)系1.1 數(shù)據(jù)結(jié)構(gòu)

6、的基本概念與算法1.1.1數(shù)據(jù)結(jié)構(gòu)的基本概念集合、樹型、圖形結(jié)構(gòu)屬于非線性結(jié)構(gòu)學(xué)號姓名語文數(shù)學(xué)C語言1001張三8554921002李四9284641003王五877473.通迅錄、成績單、花名冊線性結(jié)構(gòu)電子字典、家譜、目錄樹型結(jié)構(gòu)HBCDEFGAHGFECDBA計(jì)算機(jī)中的目錄結(jié)構(gòu)問題樹交通線路、通信網(wǎng)絡(luò)圖狀結(jié)構(gòu)圖形結(jié)構(gòu)特點(diǎn)結(jié)點(diǎn)間的連結(jié)是任意的AEBCD樹型結(jié)構(gòu)特點(diǎn)結(jié)點(diǎn)間具有分層次的連接關(guān)系3.數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu) 數(shù)據(jù)的存儲結(jié)構(gòu)是指數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲器內(nèi)的表示（又稱映象）。 存儲結(jié)構(gòu)研究的是邏輯結(jié)構(gòu)用計(jì)算機(jī)語言實(shí)現(xiàn)，依賴于計(jì)算機(jī)語言。 一種數(shù)據(jù)結(jié)構(gòu)可以根據(jù)需要采用多種不同的存儲結(jié)構(gòu)，

7、常用的存儲結(jié)構(gòu)有順序、鏈接與索引等存儲方式。 數(shù)據(jù)的存儲結(jié)構(gòu)不同，解決問題的方法就有所不同，數(shù)據(jù)處理的效率也是不同的。 1.1 數(shù)據(jù)結(jié)構(gòu)的基本概念與算法1.1.1數(shù)據(jù)結(jié)構(gòu)的基本概念3.數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)(1)順序存儲方式：邏輯上相鄰的元素存儲在物理位置相鄰的存儲單元中。主要用于線性結(jié)構(gòu)。通常借助于數(shù)組來實(shí)現(xiàn)。1.1 數(shù)據(jù)結(jié)構(gòu)的基本概念與算法1.1.1數(shù)據(jù)結(jié)構(gòu)的基本概念順序存儲結(jié)構(gòu)的線性表線性表(a0, a1, a2, a3)存儲單元的地址即物理地址如，C語言的數(shù)組a2a3a1a0a1a03.數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)(1)順序存儲方式：邏輯上相鄰的元素存儲在物理位置相鄰的存儲單元中。主要用于線性結(jié)構(gòu)。

8、通常借助于數(shù)組來實(shí)現(xiàn)。(2)鏈?zhǔn)酱鎯Ψ绞剑簩壿嬌舷噜彽脑夭灰笃湮锢淼刂废噜?，元素間邏輯關(guān)系通過附加的指針字段來表示。通常借助于指針類型實(shí)現(xiàn)。 1.1 數(shù)據(jù)結(jié)構(gòu)的基本概念與算法1.1.1數(shù)據(jù)結(jié)構(gòu)的基本概念鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表存儲單元的地址即物理地址指針域：存放下一個結(jié)點(diǎn)的地址a0,a1在邏輯上相鄰,而在機(jī)內(nèi)存儲時,存儲單元的地址(100,108)并不相鄰.鏈?zhǔn)酱鎯Ψ绞教攸c(diǎn)：每個結(jié)點(diǎn)由兩部分組成：一部分存放數(shù)據(jù)，另一部分 存儲指向前件或后件結(jié)點(diǎn)的指針域。邏輯上相鄰的結(jié)點(diǎn)物理上不必相連。數(shù)據(jù)運(yùn)算(插入和刪除等)靈活。a2a3a1a01.1 數(shù)據(jù)結(jié)構(gòu)的基本概念與算法1.1.1數(shù)據(jù)結(jié)構(gòu)的基本概念6

9、.數(shù)據(jù)類型及其分類 數(shù)據(jù)類型（Data Type）是程序設(shè)計(jì)語言中所允許使用的變量類型。 一個變量類型不僅定義了相應(yīng)變量可以設(shè)定的值的的集合，還規(guī)定了對變量允許進(jìn)行的一組運(yùn)算及其規(guī)則。 例：C語言中的整型變量，其值為某個區(qū)間上整數(shù)，定義在其上的操作為：加，減、乘、除和求余數(shù)等算術(shù)運(yùn)算。 分類：（1）非結(jié)構(gòu)的原子類型 （2）結(jié)構(gòu)類型（2）結(jié)構(gòu)類型：結(jié)構(gòu)類型的值是由若干成分按某種結(jié)構(gòu)組成的，因此是可分解的，并且它的成分可以是非結(jié)構(gòu)的，也可以是結(jié)構(gòu)的。（1）非結(jié)構(gòu)的原子類型：原子類型的值是不可分解的。如：程序設(shè)計(jì)語言中的基本類型（整型，實(shí)型，字符型，指針類型和空類型）。結(jié)構(gòu)類型舉例： struct

10、stuchar nm8; / 學(xué)號char name18; / 姓名char sex; / 性別;struct stu s1; / 學(xué)生類型1.算法的定義： 算法(A1gorithm)是對特定問題求解步驟的精確描述，它是指令或語句的有限序列 。1.1 數(shù)據(jù)結(jié)構(gòu)的基本概念與算法1.1.2 算法及算法分析 有窮性： 一個算法應(yīng)包含有限個操作步驟，而且每一步都應(yīng)在有限時間內(nèi)完成。 確定性：算法中每一條指令必須有確切的含義，確保不會產(chǎn)生二義性。 可行性：算法中指定的操作都是可以通過基本運(yùn)算執(zhí)行有限次后實(shí)現(xiàn)。 輸入：一個算法有零個或多個的輸入，這些輸入取自于某個特定的對象集合。 輸出：一個算法有一個或多

11、個的輸出，這些輸出是同輸入有著某些特定關(guān)系的量。1.算法概念 算法(A1gorithm)是對特定問題求解步驟的精確描述，它是指令或語句的有限序列 。1.1 數(shù)據(jù)結(jié)構(gòu)的基本概念與算法1.1.2 算法及算法分析 首先要從具體問題抽象出一個適當(dāng)?shù)臄?shù)學(xué)模型；然后設(shè)計(jì)一個解此數(shù)學(xué)模型的算法；最后采用一種計(jì)算機(jī)語言編出程序，調(diào)試、修改直至得到最終答案。用計(jì)算機(jī)解決一個具體問題時，大致需要經(jīng)過下列幾個步驟：1.1 數(shù)據(jù)結(jié)構(gòu)的基本概念與算法1.1.2 算法及算法分析 算法設(shè)計(jì)的要求 （1）正確性 （2） 可讀性 （3）健壯性 （4）效率與低存儲量 執(zhí)行結(jié)果應(yīng)滿足預(yù)先的功能和性能要求思路清晰、層次分明、簡單明了

12、、易讀易懂輸入數(shù)據(jù)非法時，算法能作適當(dāng)處理，不致于引起嚴(yán)重后果有效使用存儲空間和較高的時間效率1.1 數(shù)據(jù)結(jié)構(gòu)的基本概念與算法評價算法標(biāo)準(zhǔn) 算法所占用計(jì)算機(jī)資源，即時間代價(算法所需要的時間）和空間代價（算法所需要的存儲空間）。 算法所需要的時間包括：程序運(yùn)行時所需要的數(shù)據(jù)總量；源程序進(jìn)行編譯所需要的時間；計(jì)算機(jī)執(zhí)行每條指令所需要的時間；程序中指令重復(fù)執(zhí)行的次數(shù)，而本條正是討論算法中的重點(diǎn)內(nèi)容 （?？迹?1.1.2 算法及算法分析 1.1 數(shù)據(jù)結(jié)構(gòu)的基本概念與算法1.1.3 算法分析技術(shù)初步 1.時間復(fù)雜度： 算法中基本操作重復(fù)執(zhí)行的次數(shù)依據(jù)算法中最大語句頻度來估算，它是問題規(guī)模n的某個函數(shù)f

13、(n)，算法的時間量度記作T(n)O(f（n) 表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱作算法的漸近時間復(fù)雜度，簡稱時間復(fù)雜度。 時間復(fù)雜度： T (n)=O( f (n) ) T (n)：算法中所有語句頻度之和n：問題規(guī)模。 T (n) 是n的某個函數(shù)。O：數(shù)量級。當(dāng)問題規(guī)模趨向無窮時， T (n)的數(shù)量級稱為時間復(fù)雜度。 x+=5; 單個語句的頻度為1，則 程序段的時間復(fù)雜度為 for(i=0;in; i+) for(j=0 ;jn;j+) x+=5; 最優(yōu)算法：隨n的增大， T (n)增長較慢的算法。T(n)=O(1)則：T(n)= O(n2)for(i=1

14、;i=n;+i) for(j=1;j=n;+j) cij=0; for(k=1;k=n;+k) cij+=aik*bkj; 由于是一個三重循環(huán)，每個循環(huán)從1到n，則總次數(shù)為: nnn=n3時間復(fù)雜度為T(n)=O(n3)for(i=1;i=n;+i) +x; y+; 語句頻度為：2n其時間復(fù)雜度為：O(n) for(i=2;i=n;+i) for(j=2;j=i-1;+j) +x; aij=x;語句頻度為： 1+2+3+n-2 =(1+n-2) (n-2)/2 =(n-1)(n-2)/2 =n2-3n+2 時間復(fù)雜度為O(n2)時間復(fù)雜度：平均時間復(fù)雜度：所有可能的輸入實(shí)例均以等概率出現(xiàn)的情況

15、下，算法的期望運(yùn)行時間。最壞時間復(fù)雜度：最壞情況下算法的時間復(fù)雜度。 算法的時間復(fù)雜度不僅與問題規(guī)模有關(guān),而且與輸入數(shù)據(jù)有關(guān),即輸入數(shù)據(jù)所有的可能取值范圍及輸入各種數(shù)據(jù)或數(shù)據(jù)集的概率有關(guān)以下六種計(jì)算算法時間的多項(xiàng)式是最常用的。其關(guān)系為： O(1)O(logn)O(n)O(nlogn) O(n2)O(n3)1.1 數(shù)據(jù)結(jié)構(gòu)的基本概念與算法2.空間復(fù)雜度： 定義：算法運(yùn)行從開始到結(jié)束所需的存儲空間量,包括 固定部分和可變部分。固定部分：此部分空間與所處理數(shù)據(jù)的大小和規(guī)模無關(guān)。通常用來保存本身所用的程序代碼、常量、變量等。 可變部分：此部分空間與處理的數(shù)據(jù)的大小和規(guī)模有關(guān)，即執(zhí)行算法時所需額外空間。

16、 1.1.2 算法及算法分析 思考題研究數(shù)據(jù)結(jié)構(gòu)的目的是什么？數(shù)據(jù)結(jié)構(gòu)研究哪三方面的問題?關(guān)系如何?在數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)項(xiàng)、數(shù)據(jù)元素及數(shù)據(jù)對象的關(guān)系？數(shù)據(jù)的邏輯結(jié)構(gòu)分為哪兩大類？各有何特點(diǎn)？數(shù)據(jù)的存儲結(jié)構(gòu)中的順序存儲與鏈?zhǔn)酱鎯Ω饔惺裁刺攸c(diǎn)？什么是算法？有何特點(diǎn)？算法設(shè)計(jì)的基本要求？算法設(shè)計(jì)的方法？如何評價算法？什么是時間復(fù)雜度？時間復(fù)雜度與哪些因素有關(guān)？什么是空間復(fù)雜度？包括哪兩部分？習(xí)題講解 1. 數(shù)據(jù)處理的最小單位是_。 A. 數(shù)據(jù) B. 數(shù)據(jù)元素 C. 數(shù)據(jù)項(xiàng) D. 數(shù)據(jù)結(jié)構(gòu)2. 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的_。 A. 存儲結(jié)構(gòu) B. 物理結(jié)構(gòu) C. 邏輯結(jié)構(gòu) D. 物理和存儲

17、結(jié)構(gòu)3. 下面敘述正確的是_。 A. 算法的執(zhí)行效率與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān) B. 算法的空間復(fù)雜度是指算法程序中指令（或語句）的條數(shù) C. 算法的有窮性是指算法必須能在執(zhí)行有限個步驟之后終止 D. 以上三種描述都不對4. 算法的時間復(fù)雜度是指_。 A. 執(zhí)行算法程序所需要的時間 B. 算法程序的長度 C. 算法執(zhí)行過程中所需要的基本運(yùn)算次數(shù) D. 算法程序中的指令條數(shù) 5. 算法的空間復(fù)雜度是指_。 A. 算法程序的長度 B. 算法程序中的指令條數(shù) C. 算法程序所占的存儲空間 D. 算法執(zhí)行過程中所需要的存儲空間CCCCD習(xí)題講解 6. 算法一般都可以用哪幾種控制結(jié)構(gòu)組合而成_。 A. 循環(huán)、

18、分支、遞歸 B. 順序、循環(huán)、嵌套C. 循環(huán)、遞歸、選擇 D. 順序、選擇、循環(huán)7.數(shù)據(jù)的存儲結(jié)構(gòu)是指_。 A）存儲在外存中的數(shù)據(jù) B）數(shù)據(jù)所占的存儲空間量 C）數(shù)據(jù)在計(jì)算機(jī)中的順序存儲方式 D）數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示8. 在下列選項(xiàng)中，哪個不是一個算法應(yīng)該具有的基本特征_。 A. 確定性 B. 可行性 C. 無窮性 D. 擁有足夠的情報(bào)9. 在計(jì)算機(jī)中，算法是指_。 A. 查詢方法 B. 加工方法 C. 解題方案的準(zhǔn)確而完整的描述 D. 排序方法10. 算法分析的目的是_。 A. 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B. 找出算法中輸入和輸出之間的關(guān)系 C. 分析算法的易懂性和可靠性 D. 分析算法的效率以求改進(jìn)DDCCD習(xí)題講解 11.算法具有五個特性，以下選項(xiàng)中不屬于算法特性的是_。 A）有窮性 B）簡潔性 C）