數(shù)據(jù)結(jié)構(gòu)教學(xué)課件市公開課金獎(jiǎng)市賽課一等獎(jiǎng)?wù)n件

1、信息物理工程學(xué)院測(cè)繪所 宋迎春電話箱：csusyc數(shù)據(jù)結(jié)構(gòu)退出第1頁(yè)數(shù)據(jù)結(jié)構(gòu):考評(píng)方式： 出勤 + 作業(yè) + 測(cè)驗(yàn)第2頁(yè) 開設(shè)本課程背景 數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)相關(guān)專業(yè)一門主要專業(yè)基礎(chǔ)課。它主要研究計(jì)算機(jī)加工對(duì)象邏輯結(jié)構(gòu)、在計(jì)算機(jī)中表示形式以及實(shí)現(xiàn)各種基本操作算法。它是學(xué)習(xí)操作系統(tǒng)、編譯原理、數(shù)據(jù)庫(kù)原理等計(jì)算機(jī)專業(yè)關(guān)鍵課程基礎(chǔ)，掌握好這門課程內(nèi)容，是學(xué)習(xí)計(jì)算機(jī)其它相關(guān)課程必備條件。第3頁(yè) 本課程講述主要內(nèi)容 本課程將分別講述數(shù)據(jù)結(jié)構(gòu)基本概念、線性表、棧和隊(duì)列、串和數(shù)組、樹形結(jié)構(gòu)、圖結(jié)構(gòu)、查找、排序和文件等內(nèi)容。 學(xué)習(xí)本課程基本方法l上課認(rèn)真聽(tīng)講； l仔細(xì)閱讀教材中大量例題，

2、從而體會(huì)并最終掌握數(shù)據(jù)結(jié)構(gòu)中基本概念； l獨(dú)立完成每個(gè)章節(jié)后面練習(xí)題。第4頁(yè)第1章 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)概論 本章主要介紹以下內(nèi)容 數(shù)據(jù)結(jié)構(gòu)研究主要內(nèi)容 數(shù)據(jù)結(jié)構(gòu)中包括基本概念 算法概念、描述方法以及評(píng)價(jià)標(biāo)準(zhǔn)第5頁(yè) 1.1 數(shù)據(jù)結(jié)構(gòu)研究主要內(nèi)容 1.2 基本概念和術(shù)語(yǔ) 1.3 算法第6頁(yè)1.1 數(shù)據(jù)結(jié)構(gòu)研究主要內(nèi)容 當(dāng)今計(jì)算機(jī)應(yīng)用特點(diǎn)： l所處理數(shù)據(jù)量大且含有一定關(guān)系； l對(duì)其操作不再是單純數(shù)值計(jì)算，而更多地是需要對(duì)其進(jìn)行組織、管理和檢索。 應(yīng)用舉例1學(xué)籍檔案管理 假設(shè)一個(gè)學(xué)籍檔案管理系統(tǒng)應(yīng)包含以下表1-1所表示學(xué)生信息。第7頁(yè)表1-1第8頁(yè) 特點(diǎn)： l每個(gè)學(xué)生信息占據(jù)一行，全部學(xué)生信息按學(xué)號(hào)次序依次

3、排列組成一張表格； l表中每個(gè)學(xué)生信息依據(jù)學(xué)號(hào)大小存在著一個(gè)前后關(guān)系，這就是我們所說(shuō)線性結(jié)構(gòu)； l對(duì)它操作通常是插入某個(gè)學(xué)生信息，刪除某個(gè)學(xué)生信息，更新某個(gè)學(xué)生信息，按條件檢索某個(gè)學(xué)生信息等等。 應(yīng)用舉例2輸出n個(gè)對(duì)象全排列 輸出n個(gè)對(duì)象全排列能夠使用下列圖1-1所表示形式描述。第9頁(yè)圖 1-1 3個(gè)對(duì)象全排列過(guò)程第10頁(yè) 特點(diǎn)： l在求解過(guò)程中，所處理數(shù)據(jù)之間含有層次關(guān)系，這是我們所說(shuō)樹形結(jié)構(gòu)； l對(duì)它操作有：建立樹形結(jié)構(gòu)，輸出最低層結(jié)點(diǎn)內(nèi)容等等。 應(yīng)用舉例3制訂教學(xué)計(jì)劃 在制訂教學(xué)計(jì)劃時(shí)，需要考慮各門課程開設(shè)次序。有些課程需要先導(dǎo)課程，有些課程則不需要，而有些課程又是其它課程先導(dǎo)課程。比如

4、，計(jì)算機(jī)專業(yè)課程開設(shè)情況以下表1-2所表示：第11頁(yè)表1-2第12頁(yè)課程先后關(guān)系圖形描形式：c1c9c4c2c12c10c11c5c3c6c7c8圖 1-2 計(jì)算機(jī)專業(yè)必修課程開設(shè)先后關(guān)系第13頁(yè) 特點(diǎn) l課程之間先后關(guān)系用圖結(jié)構(gòu)描述； l經(jīng)過(guò)實(shí)施創(chuàng)建圖結(jié)構(gòu)，按要求將圖結(jié)構(gòu)中頂點(diǎn)進(jìn)行線性排序。 結(jié)論 計(jì)算機(jī)操作對(duì)象關(guān)系愈加復(fù)雜，操作形式不再是單純數(shù)值計(jì)算，而更多地是對(duì)這些含有一定關(guān)系數(shù)據(jù)進(jìn)行組織管理，我們將此稱為非數(shù)值性處理。要使計(jì)算機(jī)能夠更有效地進(jìn)行這些非數(shù)值性處理，就必須搞清楚這些操作對(duì)象特點(diǎn)，在計(jì)算機(jī)中表示方式以及各個(gè)操作詳細(xì)實(shí)現(xiàn)伎倆。這些就是數(shù)據(jù)結(jié)構(gòu)這門課程研究主要內(nèi)容。第14頁(yè)1.2

5、 基本概念和術(shù)語(yǔ) 數(shù)據(jù) 是對(duì)客觀事物符號(hào)表示。在計(jì)算機(jī)科學(xué)中其含義是指全部能夠輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理符號(hào)集合。 數(shù)據(jù)元素 是數(shù)據(jù)集合中一個(gè)實(shí)體，是計(jì)算機(jī)程序中加工處理基本單位。第15頁(yè) 數(shù)據(jù)元素按其組成可分為簡(jiǎn)單型數(shù)據(jù)元素和復(fù)雜型數(shù)據(jù)元素。簡(jiǎn)單型數(shù)據(jù)元素由一個(gè)數(shù)據(jù)項(xiàng)組成，所謂數(shù)據(jù)項(xiàng)就是數(shù)據(jù)中不可再分割最小單位；復(fù)雜型數(shù)據(jù)元素由多個(gè)數(shù)據(jù)項(xiàng)組成，它通常攜帶著一個(gè)概念多方面信息。 數(shù)據(jù)結(jié)構(gòu) 簡(jiǎn)單地說(shuō)，就是相互之間存在一個(gè)或各種特定關(guān)系數(shù)據(jù)元素集合。常見(jiàn)數(shù)據(jù)結(jié)構(gòu)有：線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)。 邏輯結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)中所說(shuō)“關(guān)系”實(shí)際上是指數(shù)據(jù)元素之間邏輯關(guān)系，又稱此為邏輯結(jié)構(gòu)。第16頁(yè) 存放

6、結(jié)構(gòu)（物理結(jié)構(gòu)） 是指數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)存放器中詳細(xì)實(shí)現(xiàn)。與孤立數(shù)據(jù)元素表示形式不一樣，數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素不但要表示其本身實(shí)際內(nèi)容，還要表示清楚數(shù)據(jù)元素之間邏輯結(jié)構(gòu)。 常見(jiàn)存放結(jié)構(gòu) 次序存放結(jié)構(gòu)：特點(diǎn)是借助于數(shù)據(jù)元素相對(duì)存放位置來(lái)表示數(shù)據(jù)元素之間邏輯結(jié)構(gòu)； 鏈?zhǔn)酱娣沤Y(jié)構(gòu)：特點(diǎn)是借助于指示數(shù)據(jù)元素地址指針表示數(shù)據(jù)元素之間邏輯結(jié)構(gòu)。第17頁(yè)1.3 算法 1.3.1 算法概念 算法是處理某個(gè)特定問(wèn)題一個(gè)方法或一個(gè)過(guò)程。 計(jì)算機(jī)對(duì)數(shù)據(jù)操作能夠分為數(shù)值性和非數(shù)值性兩種類型。在數(shù)值性操作中主要進(jìn)行是算術(shù)運(yùn)算；而在非數(shù)值性操作中主要進(jìn)行是檢索、排序、插入、刪除等等。第18頁(yè) 設(shè)計(jì)算法基本過(guò)程 l經(jīng)過(guò)對(duì)問(wèn)題進(jìn)行

7、詳細(xì)地分析，抽象出對(duì)應(yīng)數(shù)學(xué)模型； l確定使用數(shù)據(jù)結(jié)構(gòu)，并在此基礎(chǔ)上設(shè)計(jì)對(duì)此數(shù)據(jù)結(jié)構(gòu)實(shí)施各種操作算法； l選取某種語(yǔ)言將算法轉(zhuǎn)換成程序； l調(diào)試并運(yùn)行這些程序。第19頁(yè) 算法應(yīng)該含有以下五個(gè)特征 （1）有窮性：一個(gè)算法必須在執(zhí)行有窮步之后結(jié)束。 （2）確定性：算法中每一步，必須有確切含義，在他人了解時(shí)不會(huì)產(chǎn)生二義性。 （3）可行性：算法中描述每一步操作都能夠經(jīng)過(guò)已經(jīng)有基本操作執(zhí)行有限次實(shí)現(xiàn)。 （4）輸入：一個(gè)算法應(yīng)該有零個(gè)或多個(gè)輸入。 （5）輸出：一個(gè)算法應(yīng)該有一個(gè)或多個(gè)輸出。這里所說(shuō)輸出是指與輸入有某種特定關(guān)系量。第20頁(yè) 舉例 問(wèn)題：按從小到大次序重新排列x，y，z三個(gè)數(shù)值內(nèi)容。 算法： （

8、1）輸入x，y，z三個(gè)數(shù)值； （2）從三個(gè)數(shù)值中挑選出最小者并換到x中； （3）從y，z中挑選出較小者并換到y(tǒng)中； （4）輸出排序后結(jié)果。第21頁(yè) 1.3.2 算法描述 選擇算法描述語(yǔ)言準(zhǔn)則 （1）該語(yǔ)言應(yīng)該含有描述數(shù)據(jù)結(jié)構(gòu)和算法基本功效； （2）該語(yǔ)言應(yīng)該盡可能地簡(jiǎn)捷，方便于掌握、了解； （3）使用該語(yǔ)言描述算法應(yīng)該能夠比較輕易地轉(zhuǎn)換成任何一個(gè)程序設(shè)計(jì)語(yǔ)言。 “類C”描述語(yǔ)言是經(jīng)過(guò)對(duì)C語(yǔ)言進(jìn)行精心篩選保留一個(gè)關(guān)鍵子集，并為了便于描述，又做了若干擴(kuò)展修改，從而，增強(qiáng)了語(yǔ)言描述功效。第22頁(yè) 1. 預(yù)定義常量及類型 #define TRUE 1 #define FALSE 0 #define O

9、K 1 #define ERROR 0 #define OVERFLOW -1 數(shù)據(jù)元素被約定為EntryType 類型，用戶需要依據(jù)詳細(xì)情況，自行定義該數(shù)據(jù)類型。第23頁(yè) 2. 算法描述為以下函數(shù)形式： 函數(shù)類型 函數(shù)名（函數(shù)參數(shù)表） 語(yǔ)句序列； 為了簡(jiǎn)化函數(shù)書寫，提升算法描述清楚度，我們要求除函數(shù)參數(shù)表中參數(shù)需要說(shuō)明數(shù)據(jù)類型外，函數(shù)中使用局部變量能夠不做變量說(shuō)明，必要時(shí)給出對(duì)應(yīng)注釋即可。另外，在書寫算法時(shí)，應(yīng)該養(yǎng)成對(duì)重點(diǎn)語(yǔ)句段落添加注解良好習(xí)慣。第24頁(yè) 3. 在算法描述中能夠使用賦值語(yǔ)句形式有： 簡(jiǎn)單賦值 變量名 = 表示式； 串聯(lián)賦值 變量名1 = 變量名2 = . = 變量名n =

10、表示式； 成組賦值 （變量名1，.，變量名n）=（表示式1，.，表示式n）； 結(jié)構(gòu)賦值 結(jié)構(gòu)名1 = 結(jié)構(gòu)名2； 結(jié)構(gòu)名 =（值1，值2，.，值n）； 條件賦值 變量名 = 條件表示式 ? 表示式1：表示式2； 交換賦值 變量名1 變量名2；第25頁(yè)4. 在算法描述中能夠使用選擇結(jié)構(gòu)語(yǔ)句形式有：條件語(yǔ)句1 if （表示式） 語(yǔ)句；條件語(yǔ)句2 if （表示式） 語(yǔ)句； else 語(yǔ)句；開關(guān)語(yǔ)句1 switch （表示式） case 值1：語(yǔ)句序列1；break； case 值2：語(yǔ)句序列2；break； . case 值n：語(yǔ)句序列n；break； default：語(yǔ)句序列n+1； 第26頁(yè)開關(guān)

11、語(yǔ)句2 switch case 條件1：語(yǔ)句序列1；break； case 條件2：語(yǔ)句序列2；break； . case 條件n：語(yǔ)句序列n；break； default：語(yǔ)句序列n+1； 第27頁(yè) 5. 在算法描述中能夠使用循環(huán)結(jié)構(gòu)語(yǔ)句形式有： for循環(huán)語(yǔ)句 for （表示式1；循環(huán)條件表示式；表示式2） 語(yǔ)句； while循環(huán)語(yǔ)句 while （循環(huán)條件表示式） 語(yǔ)句； do-while循環(huán)語(yǔ)句 do 語(yǔ)句序列； while （循環(huán)條件表示式）； 6. 在描述算法中能夠使用結(jié)束語(yǔ)句形式有： 函數(shù)結(jié)束語(yǔ)句 return 表示式； return; case或循環(huán)結(jié)束語(yǔ)句 break; 異常

12、結(jié)束語(yǔ)句 exit（異常代碼）； 第28頁(yè) 7. 在算法描述中能夠使用輸入輸出語(yǔ)句形式有： 輸入語(yǔ)句 scanf( 格式串，變量名1，.，變量名n)； 輸出語(yǔ)句 printf( 格式串，表示式1，.，表示式n); 方括號(hào)（ ）中內(nèi)容是能夠省略部分。 8. 在算法描述中使用注釋格式為： 單行注釋 /文字序列 9. 在算法描述中能夠使用擴(kuò)展函數(shù)有： 求最大值 max（表示式1，.，表示式n）；這個(gè)函數(shù)返回參數(shù)表中n個(gè)表示式計(jì)算結(jié)果中最大值。 求最小值 min（表示式1，.，表示式n）；這個(gè)函數(shù)返回參數(shù)表中n個(gè)表示式計(jì)算結(jié)果中最小值。第29頁(yè) 【算法1-1】用類C描述將三個(gè)數(shù)值排序算法。 viod

13、Three_Sort( int *x,int *y,int *z) /將x,y,z三個(gè)指針?biāo)甘緝?nèi)容按從小到大次序重新排列 if (*y*x&*y*z) *x*y; /挑選出最小數(shù)值并換到 x指針?biāo)复娣艈卧?else if (*z*x&*z*y) *x*z; if (*z*y) *y*z; /在y和z所指示存放單元中挑選出較小者換到y(tǒng)中 第30頁(yè) 1.3.3 算法評(píng)價(jià) 算法評(píng)價(jià)標(biāo)準(zhǔn) (1) 正確性：要求算法能夠正確地執(zhí)行預(yù)先要求功效，并到達(dá)所期望性能要求。 (2) 可讀性：為了便于了解、測(cè)試和修改算法，算法應(yīng)該含有良好可讀性。 (3) 健壯性：算法中擁有對(duì)輸入數(shù)據(jù)、打開文件、讀取文件統(tǒng)計(jì)、分配內(nèi)存空間等操作結(jié)果檢測(cè)，并經(jīng)過(guò)與用戶對(duì)話形式做出對(duì)應(yīng)處理選擇。 (4) 時(shí)間與空間效率：算法時(shí)間與空間效率是指將算法變換為程序后，該程序在計(jì)算機(jī)上運(yùn)行時(shí)所花費(fèi)時(shí)間及所占據(jù)空間度量。第31頁(yè) 算法時(shí)間效率 算法時(shí)間效率主要由兩個(gè)原因決定： l所需處理問(wèn)題數(shù)據(jù)量大小，數(shù)據(jù)量大，所花費(fèi)時(shí)間就多； l在處理問(wèn)題過(guò)程中，基本操作執(zhí)行次數(shù)。時(shí)間特征分析 假如我們將一個(gè)算法所花費(fèi)時(shí)間設(shè)計(jì)成