數(shù)據(jù)結(jié)構(gòu)與算法：第一章 緒論

1數(shù)據(jù)結(jié)構(gòu)與算法

DataStructureandAlgorithm數(shù)據(jù)結(jié)構(gòu)與算法課程定位專業(yè)核心課程本科階段計算機專業(yè)最難課程之一全國碩士入學考試計算機專業(yè)必考課程之一是編寫優(yōu)秀、高質(zhì)量代碼的重要基礎(chǔ)能夠處理數(shù)值與非數(shù)值數(shù)據(jù)24數(shù)據(jù)結(jié)構(gòu)課程的地位——針對數(shù)值與非數(shù)值計算的程序設(shè)計問題，研究計算機的操作對象以及它們之間的關(guān)系和操作?！墙橛跀?shù)學、計算機硬件和計算機軟件三者之間的一門核心課程。5數(shù)據(jù)結(jié)構(gòu)課程的地位關(guān)系對象關(guān)系操作數(shù)學軟件硬件對象關(guān)系操作Data_Structure=（D,R）作業(yè)閱讀每章電子檔的輔導材料；每章習題精選、部分考研試題；上機實驗(由數(shù)據(jù)結(jié)構(gòu)課程設(shè)計完成）作業(yè)郵箱：uir_ds11@126.com電子檔作業(yè)文件名格式：學號+章節(jié)名稱（20190701+線性表）67學時數(shù)：60學分：4教材：嚴蔚敏等，數(shù)據(jù)結(jié)構(gòu)（C語言版）最新版，清華大學出版社。參考書：[1]周延森，數(shù)據(jù)結(jié)構(gòu)，北京郵電大學出版社，2018年12月課程安排、教材及參考資料8內(nèi)容安排章內(nèi)容學時

章內(nèi)容學時

1緒論27圖102線性表68動態(tài)存儲管理略3棧和隊列49查找64串410內(nèi)部排序85數(shù)組和廣義表411外部排序26樹和二叉樹1212文件略實驗內(nèi)容安排從第一章開始，每章都有相應(yīng)的編程設(shè)計題，由課程設(shè)計課來完成；實驗要求有相應(yīng)的報告，具體看相關(guān)格式；《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計》是獨立課程；實驗主要由同學自主完成，在機房上機，由老師指導完成。910第1章緒論第2章線性表(重點）第3章棧和隊列第4章串第5章數(shù)組和廣義表第6章樹和二叉樹（重點）全書目錄第7章圖（重點）第9章查找第10章內(nèi)部排序（重點）第11章外部排序第1章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)（重點）1.2學習數(shù)據(jù)結(jié)構(gòu)的意義1.3數(shù)據(jù)結(jié)構(gòu)涵蓋的主要內(nèi)容1.4什么是抽象數(shù)據(jù)類型1.5算法效率的度量（重點）111.1什么是數(shù)據(jù)結(jié)構(gòu)1、定義：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合及其之上的運算，表示為：12（數(shù)值或非數(shù)值）Data_Structure=（D,R）元素有限集關(guān)系有限集1.1什么是數(shù)據(jù)結(jié)構(gòu)132、從數(shù)據(jù)處理的角度定義

數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)值與非數(shù)值計算的程序設(shè)計算法以及元素之間的關(guān)系和運算等的學科。

選擇適當?shù)慕M織方式按照某種關(guān)系來組織大量的數(shù)據(jù)，以一定的存儲方式把它們存儲到計算機，并在這些數(shù)據(jù)上定義相應(yīng)的運算，以提高計算機處理效率的學科。數(shù)據(jù)(data)——所有能被計算機識別、存儲和處理的符號的集合（包括數(shù)字、字符、聲音、圖像等信息）。數(shù)據(jù)元素(dataelement)——是數(shù)據(jù)的基本單位，具有完整確定的實際意義(又稱元素、結(jié)點，頂點、記錄等）。數(shù)據(jù)項(Dataitem)——構(gòu)成數(shù)據(jù)元素的項目。是具有獨立含義的最小標識單位（又稱字段、域、屬性等）。14數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項術(shù)語簡介：15三者之間的關(guān)系：數(shù)據(jù)>數(shù)據(jù)元素>數(shù)據(jù)項例：班級通訊錄>個人記錄>姓名、年齡……數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項術(shù)語簡介：1.2學習數(shù)據(jù)結(jié)構(gòu)的意義

計算機內(nèi)的數(shù)值運算依靠方程式，而非數(shù)值運算（如表、樹、圖等）則要依靠數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是一門學科，主要針對數(shù)值與非數(shù)值計算的程序設(shè)計問題，研究計算機的數(shù)據(jù)對象以及它們之間的關(guān)系和操作等等。161.2學習數(shù)據(jù)結(jié)構(gòu)的意義17好的程序設(shè)計＝好算法＋好的數(shù)據(jù)結(jié)構(gòu)

同樣的數(shù)據(jù)對象，用不同的數(shù)據(jù)結(jié)構(gòu)來表示，運算效率可能有明顯的差異。

常規(guī)的編程語言無法處理非數(shù)值對象，數(shù)據(jù)結(jié)構(gòu)善于處理非數(shù)值數(shù)據(jù)對象。1.3數(shù)據(jù)結(jié)構(gòu)涵蓋的內(nèi)容181.3數(shù)據(jù)結(jié)構(gòu)涵蓋的內(nèi)容1920指數(shù)據(jù)元素之間的邏輯關(guān)系。即從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲無關(guān)，是獨立于計算機的。1、邏輯結(jié)構(gòu)定義1.3.1數(shù)據(jù)的邏輯結(jié)構(gòu)21集合結(jié)構(gòu)：

僅同屬一個集合線性結(jié)構(gòu):

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

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

多對多(m:n)非線性線性邏輯結(jié)構(gòu)可細分為4類：2、邏輯結(jié)構(gòu)類型1.3.1數(shù)據(jù)的邏輯結(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)}22解：上述表達式可用圖形表示為：bcaefd此結(jié)構(gòu)為線性的。例1：用圖形表示下列數(shù)據(jù)結(jié)構(gòu)，并指出它們是屬于線性結(jié)構(gòu)還是非線性結(jié)構(gòu)。1.3.1數(shù)據(jù)的邏輯結(jié)構(gòu)

d1d5d2d4d323該結(jié)構(gòu)是非線性的。解：上述表達式可用圖形表示為：（2）S=(D,R)D={di|1≤i≤5}R={(di,dj),i<j}1.3.1數(shù)據(jù)的邏輯結(jié)構(gòu)24從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為()兩大類。動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)A順序結(jié)構(gòu)、鏈式結(jié)構(gòu)B線性結(jié)構(gòu)、非線性結(jié)構(gòu)C初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)D提交單選題1分1.3.2物理結(jié)構(gòu)答：物理結(jié)構(gòu)亦稱存儲結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲器內(nèi)的表示（或映像）。它依賴于計算機系統(tǒng)。25存儲結(jié)構(gòu)可分為4大類：順序、鏈式、索引、散列1、物理結(jié)構(gòu)定義1.3.2物理結(jié)構(gòu)26例：數(shù)組inta[2]={3,4}4030430300041503023030004154法1：地址內(nèi)容法2：地址內(nèi)容4字節(jié)后續(xù)元素地址順序存儲鏈式存儲structLinkList{intdata;LinkList*next};1.3.2物理結(jié)構(gòu)在數(shù)據(jù)的邏輯結(jié)構(gòu)上定義的操作算法,它在數(shù)據(jù)的存儲結(jié)構(gòu)上實現(xiàn)。272、數(shù)據(jù)的運算1.3.2物理結(jié)構(gòu)28最常用的數(shù)據(jù)運算有5種：插入、刪除、修改、查找、排序。其中，前面三種運算在每章中都有涉及，而后兩種運算專門有章節(jié)介紹2、數(shù)據(jù)的運算1.4什么是抽象數(shù)據(jù)類型291.4.1數(shù)據(jù)類型與抽象數(shù)據(jù)類型的區(qū)別？1.4.2抽象數(shù)據(jù)類型如何定義？1.4.3抽象數(shù)據(jù)類型如何表示和實現(xiàn)？

抽象數(shù)據(jù)類型和偽碼是學習數(shù)據(jù)結(jié)構(gòu)的工具抽象數(shù)據(jù)類型類似于面向?qū)ο笾械念?.4.1數(shù)據(jù)類型與抽象數(shù)據(jù)類型的區(qū)別30數(shù)據(jù)類型：是一個值的集合和定義在該值上的一組操作的總稱。抽象數(shù)據(jù)類型：由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型。它由基本的數(shù)據(jù)類型構(gòu)成，并包括一組相關(guān)的服務(wù)（或稱操作、函數(shù)等）。它與數(shù)據(jù)類型實質(zhì)上是一個概念，但其特征是使用與實現(xiàn)分離，實行封裝和信息隱蔽（獨立于計算機）1.4.2抽象數(shù)據(jù)類型如何定義31抽象數(shù)據(jù)類型可以用以下的三元組來表示：

ADT=（D，R，P）ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對象：<數(shù)據(jù)對象的定義>

數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>

基本操作：<基本操作的定義>}ADT抽象數(shù)據(jù)類型名ADT常用定義格式數(shù)據(jù)對象D上的關(guān)系集D上的操作集1.4.2抽象數(shù)據(jù)類型如何定義1.4.3抽象數(shù)據(jù)類型如何表示和實現(xiàn)

抽象數(shù)據(jù)類型可以通過固有的數(shù)據(jù)類型（如整型、實型、字符型等）來表示和實現(xiàn)。33注1：它有些類似C語言中的結(jié)構(gòu)體（struct)類型，但增加了相關(guān)的操作（函數(shù)）。注2：教材中用類C語言（介于偽碼和C語言之間）作為描述工具。其描述語法匯總在教材P10-11上。但上機時要用具體語言實現(xiàn)，如C或C++等34教材中例1-6和例1-7分別給出了抽象數(shù)據(jù)類型“三元組”的定義、表示和實現(xiàn)，請自己先試讀一遍。當課程內(nèi)容學習到50%以后，你再回頭看這個例子，會發(fā)現(xiàn)自己已能完全看懂了！提示：1.5算法效率的度量(重點）1.5.1什么是算法？如何評判算法的好壞？1.5.2時間復(fù)雜度和空間復(fù)雜度如何表示？1.5.3計算舉例35討論：1.5.1什么是算法？如何評判一個算法的好壞？36算法的基本特性：有窮性、確定性、可行性、必有輸出程序設(shè)計的實質(zhì)：好算法＋好結(jié)構(gòu)算法是對特定問題求解步驟的一種描述，它是指令的有限序列，是一系列輸入轉(zhuǎn)換為輸出的計算步驟。1.5.1什么是算法？如何評判一個算法的好壞？37常用時間復(fù)雜度來衡量算法評價指標（前3個定性，后2個定量）正確性、可讀性、健壯性、效率與低存儲量需求常用空間復(fù)雜度來衡量1.5.2時間復(fù)雜度和空間復(fù)雜度如何表示？38注：1）O（）為漸近符號。2）空間復(fù)雜度S(n)按數(shù)量級遞增順序也與上表類似。復(fù)雜度高復(fù)雜度低時間復(fù)雜度T(n)按數(shù)量級遞增順序為：多項式階常見函數(shù)的增長率391.5算法效率的度量(重點與考點）3n+2=O(n)因為3n+24n

forn26*2n+n2=O(2n)

因為6*2n+n27*2n

forn440例：漸進符號（O）的定義：當且僅當存在一個正的常數(shù)C，使得對所有的

nn0

，有f(n)Cg(n)，則：f(n)=O(g(n))1.5.3計算舉例（時間復(fù)雜度）時間復(fù)雜度：程序語句中運行最多次數(shù)的多少決定時間復(fù)雜度411.5.3計算舉例（時間復(fù)雜度）42該算法的運行時間由程序中所有語句的頻度（即該語句重復(fù)執(zhí)行的次數(shù)）之和構(gòu)成。解：分析：顯然，語句①的頻度是1。設(shè)語句2的頻度是f(n)，則有：算法的時間復(fù)雜度由嵌套最深層語句的頻度決定例：分析以下程序段的時間復(fù)雜度。

i=1;①while(i<=n)

i=i*2;②即f(n)≤log2n，取最大值f(n)=log2n所以該程序段的時間復(fù)雜度T(n)=1+f(n)=1+log2n=O(log2n)1、定義：指的是在程序運行過程中所需的額外內(nèi)存空間，不包括數(shù)據(jù)對象變量本身所需的內(nèi)存空間2、案例：實現(xiàn)兩數(shù)互換inta[2],inttemp;temp=a[1],a[1]=a[2],a[2]=temp;431.5.3計算舉例（空間復(fù)雜度）44i=1;while(i<=n)i=i*3;該算法時間復(fù)雜度為()。O(log2n)AO(log3n)BO(log2n)CO(n1/3)D提交單選題1分45下面程序段的時間復(fù)雜度為（）。(n>1)sum=1；for(i=0;sum<n;i++)sum+=1;

O(log2n)AO(n)BO(nlog2n)CO(n1/2)D提交單選題1分46設(shè)n是描述問題規(guī)模的非負整數(shù),下面程序片段的時間復(fù)雜度是()。

x=2;while(x<n/2)x=2*x;O(log2n)AO(n)BO(nlog2n)CO(n2)D提交單選題1分本章小結(jié)數(shù)據(jù)結(jié)構(gòu)課程——數(shù)據(jù)結(jié)構(gòu)＋算法＝程序，涉及數(shù)學、計算機硬件和軟件數(shù)據(jù)結(jié)構(gòu)定義——指互相有關(guān)聯(lián)的數(shù)據(jù)元素的集合，可用data_Structure=(D,R)表示數(shù)據(jù)結(jié)構(gòu)內(nèi)容——數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和基本運算

數(shù)據(jù)結(jié)構(gòu)學習工具——抽象數(shù)據(jù)類型和偽碼（類C）算法效率指標——時間效率和空間