數(shù)據(jù)結(jié)構(gòu)高靜

數(shù)據(jù)結(jié)構(gòu)高靜第1頁(yè)，共50頁(yè)，2023年，2月20日，星期六學(xué)時(shí)數(shù)：60（44＋16）教材：嚴(yán)蔚敏等，數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版），清華大學(xué)出版社，參考書(shū)：[1]李春保，數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析（C語(yǔ)言篇），清華大學(xué)出版社，2001年1月。￥282第2頁(yè)，共50頁(yè)，2023年，2月20日，星期六內(nèi)容安排章內(nèi)容學(xué)時(shí)章內(nèi)容學(xué)時(shí)1序論27圖62線性表48動(dòng)態(tài)存儲(chǔ)管理略3棧和隊(duì)列49查找44串210內(nèi)部排序65數(shù)組和廣義表411外部排序略6樹(shù)和二叉樹(shù)612文件略3第3頁(yè)，共50頁(yè)，2023年，2月20日，星期六數(shù)據(jù)結(jié)構(gòu)課程的地位是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門(mén)核心課程關(guān)系對(duì)象關(guān)系操作數(shù)學(xué)軟件硬件對(duì)象關(guān)系操作4第4頁(yè)，共50頁(yè)，2023年，2月20日，星期六第1章序論1.1數(shù)據(jù)結(jié)構(gòu)討論了什么1.2數(shù)據(jù)結(jié)構(gòu)基本概念1.3抽象數(shù)據(jù)類(lèi)型概念1.4算法效率的度量作業(yè)5第5頁(yè)，共50頁(yè)，2023年，2月20日，星期六1.1數(shù)據(jù)結(jié)構(gòu)討論了什么程序設(shè)計(jì)＝算法＋結(jié)構(gòu)程序設(shè)計(jì)：算法：結(jié)構(gòu)：為計(jì)算機(jī)處理問(wèn)題來(lái)編制一組指令集。處理問(wèn)題的策略。問(wèn)題的數(shù)學(xué)模型。6第6頁(yè)，共50頁(yè)，2023年，2月20日，星期六數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題例：一個(gè)人在地球上所受重力。G=m×g； 預(yù)報(bào)人口增長(zhǎng)問(wèn)題。 微分方程計(jì)算機(jī)內(nèi)的數(shù)值運(yùn)算依靠方程式。7第7頁(yè)，共50頁(yè)，2023年，2月20日，星期六非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題計(jì)算機(jī)主要進(jìn)行大量的非數(shù)值運(yùn)算，稱(chēng)非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題。8第8頁(yè)，共50頁(yè)，2023年，2月20日，星期六例1圖書(shū)館書(shū)目檢索問(wèn)題登錄號(hào)：書(shū)名：作者名：分類(lèi)號(hào)：出版單位：出版時(shí)間：價(jià)格：書(shū)目卡片書(shū)目文件按書(shū)名按作者名按分類(lèi)號(hào)索引表線性表9第9頁(yè)，共50頁(yè)，2023年，2月20日，星期六非數(shù)值運(yùn)算的例子圖書(shū)館書(shū)目檢索問(wèn)題。算法：模型：使用什么方法來(lái)查找書(shū)目文件，按書(shū)名、作者名、分類(lèi)號(hào)順序排列的索引表。10第10頁(yè)，共50頁(yè)，2023年，2月20日，星期六例2人機(jī)對(duì)奕問(wèn)題樹(shù)……..……..…...…...…...…...11第11頁(yè)，共50頁(yè)，2023年，2月20日，星期六非數(shù)值運(yùn)算的例子人機(jī)對(duì)弈問(wèn)題。算法：模型：下棋（對(duì)弈）的規(guī)則和策略。棋盤(pán)和棋譜是怎么表示的。12第12頁(yè)，共50頁(yè)，2023年，2月20日，星期六數(shù)據(jù)結(jié)構(gòu)討論了什么數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中描述現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型和在計(jì)算機(jī)中表示的方法，以及數(shù)學(xué)模型進(jìn)行的操作在計(jì)算機(jī)中如何實(shí)現(xiàn)。13第13頁(yè)，共50頁(yè)，2023年，2月20日，星期六1.2基本概念和術(shù)語(yǔ)數(shù)據(jù):對(duì)客觀事物的符號(hào)表示，在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱(chēng)。是計(jì)算機(jī)處理的信息某種特定符號(hào)的表示形式。數(shù)據(jù)元素：數(shù)據(jù)是一個(gè)集合，在這個(gè)集合中的每一個(gè)個(gè)體叫做數(shù)據(jù)元素。數(shù)據(jù)元素是數(shù)據(jù)的基本單位。一個(gè)數(shù)據(jù)元素由若干個(gè)數(shù)據(jù)項(xiàng)組成。（最小單位）14第14頁(yè)，共50頁(yè)，2023年，2月20日，星期六學(xué)生信息表姓名年齡班級(jí)專(zhuān)業(yè)張三204班軟件李四192班信息管理王五201班信息管理數(shù)據(jù)項(xiàng)數(shù)據(jù)元素15第15頁(yè)，共50頁(yè)，2023年，2月20日，星期六1.2基本概念和術(shù)語(yǔ)三者之間的關(guān)系：數(shù)據(jù)>數(shù)據(jù)元素>數(shù)據(jù)項(xiàng)例：班級(jí)通訊錄>個(gè)人記錄>姓名、年齡……16第16頁(yè)，共50頁(yè)，2023年，2月20日，星期六1.2基本概念和術(shù)語(yǔ)數(shù)據(jù)對(duì)象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。如：整數(shù)數(shù)據(jù)對(duì)象是集合N={0,±1,±2,±3,±4,...}字母字符數(shù)據(jù)對(duì)象是集合C={‘A’,’B’,...,’Z’}。17第17頁(yè)，共50頁(yè)，2023年，2月20日，星期六1.2基本概念和術(shù)語(yǔ)數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)元素之間的關(guān)系稱(chēng)為結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)定義也可以是帶結(jié)構(gòu)的數(shù)據(jù)元素的集合。

18第18頁(yè)，共50頁(yè)，2023年，2月20日，星期六數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)元素的集合數(shù)據(jù)結(jié)構(gòu)的兩個(gè)要素：數(shù)據(jù)元素、結(jié)構(gòu)（數(shù)據(jù)元素之間的關(guān)系）。例：一維數(shù)組{a1，a2，a3，a4，a5，a6} 數(shù)據(jù)元素之間有這樣一個(gè)次序關(guān)系

<a1,a2>,<a2,a3>,<a3,a4>,<a4,a5>,<a5,a6>

更改次序?yàn)椋?lt;a6,a2>,<a2,a3>,<a3,a4>,<a4,a5>,<a5,a1>一維數(shù)組變成了： {a6，a2，a3，a4，a5，a1}19第19頁(yè)，共50頁(yè)，2023年，2月20日，星期六數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)元素的集合例：2行3列的二維數(shù)組{a1，a2，a3，a4，a5，a6}行的次序關(guān)系： row={<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}列的次序關(guān)系： col={<a1,a4>,<a2,a5>,<a3,a6>a1a2a3a4a5a620第20頁(yè)，共50頁(yè)，2023年，2月20日，星期六數(shù)據(jù)結(jié)構(gòu)的形式表示數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，用一個(gè)二元組表示為：Data_Structure=（D,S）D為數(shù)據(jù)元素組成的有限集S為數(shù)據(jù)元素之間關(guān)系的有限集21第21頁(yè)，共50頁(yè)，2023年，2月20日，星期六數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)22第22頁(yè)，共50頁(yè)，2023年，2月20日，星期六什么叫數(shù)據(jù)的邏輯結(jié)構(gòu)？指數(shù)據(jù)元素之間的邏輯關(guān)系。即從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。邏輯結(jié)構(gòu)可細(xì)分為4類(lèi)：集合結(jié)構(gòu)：僅同屬一個(gè)集合線性結(jié)構(gòu):一對(duì)一（1:1)

樹(shù)結(jié)構(gòu):一對(duì)多（1:n)

圖結(jié)構(gòu):多對(duì)多(m:n)非線性線性23第23頁(yè)，共50頁(yè)，2023年，2月20日，星期六例：用圖形表示下列數(shù)據(jù)結(jié)構(gòu)，并指出它們是屬于線性結(jié)構(gòu)還是非線性結(jié)構(gòu)。（1）S=(D,R)D={a,b,c,d,e,f}R={(a,e),(b,c),(c,a),(e,f),(f,d)}解：上述表達(dá)式可用圖形表示為：bcaefd此結(jié)構(gòu)為線性的。24第24頁(yè)，共50頁(yè)，2023年，2月20日，星期六（2）S=(D,R)

D={di|1≤i≤5}

R={(di,dj),i<j}

d1d5d2d4d3該結(jié)構(gòu)是非線性的。解：上述表達(dá)式可用圖形表示為：25第25頁(yè)，共50頁(yè)，2023年，2月20日，星期六數(shù)據(jù)的存儲(chǔ)（物理）結(jié)構(gòu)—數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的實(shí)現(xiàn)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)密切相關(guān) 算法設(shè)計(jì) 邏輯結(jié)構(gòu) 算法實(shí)現(xiàn) 存儲(chǔ)結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu)分為：順序存儲(chǔ)結(jié)構(gòu)——借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素間的邏輯關(guān)系鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系26第26頁(yè)，共50頁(yè)，2023年，2月20日，星期六元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲(chǔ)地址存儲(chǔ)內(nèi)容Loc(元素i)=Lo+（i-1)*m順序存儲(chǔ)27第27頁(yè)，共50頁(yè)，2023年，2月20日，星期六1536元素21400元素11346元素3∧元素41345h存儲(chǔ)地址存儲(chǔ)內(nèi)容指針1345元素1

14001346元素4∧

…….

……..

…….

1400

元素21536

…….

……..

…….1536元素31346

鏈?zhǔn)酱鎯?chǔ)

h28第28頁(yè)，共50頁(yè)，2023年，2月20日，星期六在不同的編程環(huán)境中，存儲(chǔ)結(jié)構(gòu)可以有多種描述方法。當(dāng)用高級(jí)程序設(shè)計(jì)語(yǔ)言進(jìn)行編程時(shí)，通?？梢杂酶呒?jí)程序語(yǔ)言提供的“數(shù)據(jù)類(lèi)型”來(lái)描述它。29第29頁(yè)，共50頁(yè)，2023年，2月20日，星期六數(shù)據(jù)類(lèi)型數(shù)據(jù)類(lèi)型可以看作是指一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱(chēng)。例C語(yǔ)言中，提供int,char,float,double等基本數(shù)據(jù)類(lèi)型，數(shù)組、結(jié)構(gòu)體、共用體、枚舉等構(gòu)造數(shù)據(jù)類(lèi)型，還有指針、空(void)類(lèi)型等。用戶也可用typedef自己定義數(shù)據(jù)類(lèi)型typedefstruct{intnum;charname[20];floatscore;}STUDENT;STUDENTstu1,stu2,*p;30第30頁(yè)，共50頁(yè)，2023年，2月20日，星期六抽象數(shù)據(jù)類(lèi)型抽象數(shù)據(jù)類(lèi)型是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。其定義僅取決于它的一組邏輯特性，而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無(wú)關(guān)，即不論起內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變，都不影響其外部的使用。31第31頁(yè)，共50頁(yè)，2023年，2月20日，星期六抽象數(shù)據(jù)類(lèi)型一個(gè)抽象數(shù)據(jù)類(lèi)型的軟件模塊通常包括三個(gè)部分：定義表示實(shí)現(xiàn)

32第32頁(yè)，共50頁(yè)，2023年，2月20日，星期六抽象數(shù)據(jù)類(lèi)型的定義抽象數(shù)據(jù)類(lèi)型可以用以下的三元組來(lái)表示：

ADT=（D，S，P）數(shù)據(jù)對(duì)象D上的關(guān)系集D上的操作集ADT抽象數(shù)據(jù)類(lèi)型名{數(shù)據(jù)對(duì)象：<數(shù)據(jù)對(duì)象的定義>數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>基本操作：<基本操作的定義>}ADT抽象數(shù)據(jù)類(lèi)型名ADT常用定義格式33第33頁(yè)，共50頁(yè)，2023年，2月20日，星期六抽象數(shù)據(jù)類(lèi)型的定義示例抽象數(shù)據(jù)類(lèi)型三元組的定義：ADTTriplet{數(shù)據(jù)對(duì)象：D={e1,e2,e3∈ElemSet(定義了關(guān)系運(yùn)算的某個(gè)集合)數(shù)據(jù)關(guān)系：R1={<e1,e2>,<e2,e3>}基本操作：InitTriplet(&T,v1,v2,v3)操作結(jié)果：構(gòu)造了三元組T，元素e1,e2和e3分別被賦以參數(shù)v1,v2,v3的值。34第34頁(yè)，共50頁(yè)，2023年，2月20日，星期六抽象數(shù)據(jù)類(lèi)型的定義示例DestroyTriplet(&T)操作結(jié)果：三元組T被銷(xiāo)毀。Get(T,I,&e)初始條件：三元組T已存在，1≤i≤3。操作結(jié)果：用e返回T的第i元的值。put(T,I,&e)初始條件：三元組T已存在，1≤i≤3。操作結(jié)果：改變T的第i元的值為e。IsAscending(T)初始條件：三元組T已存在，1≤i≤3。操作結(jié)果：如果T的三個(gè)元素按升序排列，則返回1，否則 返回0。35第35頁(yè)，共50頁(yè)，2023年，2月20日，星期六抽象數(shù)據(jù)類(lèi)型的定義示例IsDescending(T)初始條件：三元組T已存在。操作結(jié)果：如果T的三個(gè)元素按降序排列，則返回1，否則返回0。Max(T,&e)初始條件：三元組T已存在。操作結(jié)果：用e返回T的三個(gè)元素中的最大值。Min(T,&e)初始條件：三元組T已存在。操作結(jié)果：用e返回T的三個(gè)元素中的最小值。}ADTTriplet36第36頁(yè)，共50頁(yè)，2023年，2月20日，星期六抽象數(shù)據(jù)類(lèi)型的表示與實(shí)現(xiàn)抽象數(shù)據(jù)類(lèi)型可通過(guò)固有數(shù)據(jù)類(lèi)型來(lái)表示和實(shí)現(xiàn)，即利用處理器中已存在的數(shù)據(jù)類(lèi)型來(lái)說(shuō)明新的結(jié)構(gòu)，用已經(jīng)實(shí)現(xiàn)的操作來(lái)組合新的操作。但上機(jī)時(shí)要用具體語(yǔ)言實(shí)現(xiàn)，如C或C++37第37頁(yè)，共50頁(yè)，2023年，2月20日，星期六算法（algorithm）—解決某一特定問(wèn)題的具體步驟的描述，是指令的有限序列算法特性—（1）有窮性：一個(gè)算法要在有窮步之后結(jié)束，而且每一步要在有窮的時(shí)間內(nèi)完成。（2）確定性：算法中每一步都必須有確切定義的，不能產(chǎn)生二義。（3）可行性：算法是可以通過(guò)計(jì)算機(jī)能夠執(zhí)行的。（4）輸入：每一個(gè)算法都要有0個(gè)或者多個(gè)輸入。（5）輸出：每一個(gè)算法都要有1個(gè)或者多個(gè)輸出。對(duì)于相同的輸入，相對(duì)應(yīng)的輸出是確定的。1.4算法和算法分析38第38頁(yè)，共50頁(yè)，2023年，2月20日，星期六1.4算法和算法分析算法的描述—采用C語(yǔ)言算法的評(píng)價(jià)—衡量算法優(yōu)劣的標(biāo)準(zhǔn)正確性(correctness)可讀性(readability)健壯性(robustness)效率與低存儲(chǔ)量39第39頁(yè)，共50頁(yè)，2023年，2月20日，星期六算法效率——用依據(jù)該算法編制的程序在計(jì)算機(jī)上執(zhí)行所消耗的時(shí)間來(lái)度量

1.事后統(tǒng)計(jì)——利用計(jì)算機(jī)內(nèi)記時(shí)功能，不同算法的程序可以用一組或多組相同的統(tǒng)計(jì)數(shù)據(jù)區(qū)分優(yōu)劣

缺點(diǎn)：必須先運(yùn)行依據(jù)算法編制的程序所得時(shí)間統(tǒng)計(jì)量依賴(lài)于硬件、軟件等環(huán)境因素，掩蓋算法本身的優(yōu)劣2.事前分析估計(jì) 和算法執(zhí)行時(shí)間相關(guān)的因素:依據(jù)的算法選用何種策略問(wèn)題的規(guī)模程序語(yǔ)言編譯程序產(chǎn)生機(jī)器代碼質(zhì)量機(jī)器執(zhí)行指令速度同一個(gè)算法用不同的語(yǔ)言、不同的編譯程序、在不同的計(jì)算機(jī)上運(yùn)行，效率均不同，———所以使用絕對(duì)時(shí)間單位衡量算法效率不合適40第40頁(yè)，共50頁(yè)，2023年，2月20日，星期六算法效率的度量可以認(rèn)為一個(gè)特定的算法“運(yùn)行工作量”的大小，只依賴(lài)于問(wèn)題的規(guī)模（通常用整數(shù)n來(lái)表示）。算法=控制結(jié)構(gòu)（順序、分支和循環(huán)三種）+原操作（指固有數(shù)據(jù)類(lèi)型的操作）。事前分析估計(jì)法：從算法中選取一種對(duì)于所研究的問(wèn)題（或算法類(lèi)型）來(lái)說(shuō)是基本操作的原操作，以該基本操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間量度。41第41頁(yè)，共50頁(yè)，2023年，2月20日，星期六例1：N×N矩陣相乘for(i=1;i<=n;i++)for(j=1;j<=n;j++){ c[i][j]=0; for(k=1;k<=n;k++) c[i][j]=c[i][j]+a[i][k]*b[k][j];} f(n)=n3T(n)=O(n3)①②①被重復(fù)執(zhí)行的次數(shù)是n*n，②被重復(fù)執(zhí)行的次數(shù)是n*n*n。因?yàn)棰诒恢貜?fù)執(zhí)行的次數(shù)和程序執(zhí)行的時(shí)間成正比。選取的原則是最深層循環(huán)內(nèi)的語(yǔ)句中的原操作為基本操作。42第42頁(yè)，共50頁(yè)，2023年，2月20日，星期六算法的時(shí)間復(fù)雜度一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)f(n)，算法的時(shí)間量度記作T(n)=O(f(n))它表示隨問(wèn)題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，稱(chēng)作算法的時(shí)間復(fù)雜度。43第43頁(yè)，共50頁(yè)，2023年，2月20日，星期六漸進(jìn)符號(hào)（O）的定義：當(dāng)且僅當(dāng)存在一個(gè)正的常數(shù)

C，使得對(duì)所有的

nn0

，有f(n)Cg(n)，則

f(n)=O(g(n))

2=O(1) //常量階3n+3=O(n)//線形階10n2+4n+2=O(n2) //平方階6*2n+n2=O(2n) //指數(shù)階例：44第44頁(yè)，共50頁(yè)，2023年，2月20日，星期六在難以精確計(jì)算基本操作執(zhí)行次數(shù)，只需求出它關(guān)于n的增長(zhǎng)率或階即可。for(i=2;i<=n;++i) for(j=2;j<=i-1;++j) { ++x; a[i][j]=x； }45第45頁(yè)，共50頁(yè)，2023年，2月20日，星期六有些情況下，算法中基本操作的重復(fù)執(zhí)行次數(shù)還隨問(wèn)題的輸入數(shù)據(jù)集不同而不同。voidb