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

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

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

更改次序為：<a6,a2>,<a2,a3>,<a3,a4>,<a4,a5>,<a5,a1>一維數(shù)組變成了： {a6，a2，a3，a4，a5，a1}19第19頁，課件共50頁，創(chuàng)作于2023年2月數(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頁，課件共50頁，創(chuàng)作于2023年2月數(shù)據(jù)結(jié)構(gòu)的形式表示數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，用一個二元組表示為：Data_Structure=（D,S）D為數(shù)據(jù)元素組成的有限集S為數(shù)據(jù)元素之間關(guān)系的有限集21第21頁，課件共50頁，創(chuàng)作于2023年2月數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)的存儲結(jié)構(gòu)22第22頁，課件共50頁，創(chuàng)作于2023年2月什么叫數(shù)據(jù)的邏輯結(jié)構(gòu)？指數(shù)據(jù)元素之間的邏輯關(guān)系。即從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲無關(guān)，是獨立于計算機的。邏輯結(jié)構(gòu)可細(xì)分為4類：集合結(jié)構(gòu)：僅同屬一個集合線性結(jié)構(gòu):一對一（1:1)

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

圖結(jié)構(gòu):多對多(m:n)非線性線性23第23頁，課件共50頁，創(chuàng)作于2023年2月例：用圖形表示下列數(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頁，課件共50頁，創(chuàng)作于2023年2月（2）S=(D,R)

D={di|1≤i≤5}

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

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

14001346元素4∧

…….

……..

…….

1400

元素21536

…….

……..

…….1536元素31346

鏈?zhǔn)酱鎯?/p>

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

32第32頁，課件共50頁，創(chuàng)作于2023年2月抽象數(shù)據(jù)類型的定義抽象數(shù)據(jù)類型可以用以下的三元組來表示：

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

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

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

C，使得對所有的

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頁，課件共50頁，創(chuàng)作于2023年2月在難以精確計算基本操作執(zhí)行次數(shù)，只需求出它關(guān)于n的增長率或階即可。for(i=2;i<=n;++i) for(j=2;j<=i-1;++j) { ++x; a[i][j]=x； }45第45頁，課件共50頁，創(chuàng)作于2023年2月有些情況下，算法中基本操作的重復(fù)執(zhí)行次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同。voidbu