1、軟件技術(shù)基礎(chǔ),電子科技大學(xué)通信與信息工程學(xué)院 軟件技術(shù)基礎(chǔ)課題組 教師:孟中樓 Email：,SCIE, University of Electronic Science and Technology of China,2,課程簡介,教材和參考資料 教材：軟件技術(shù)基礎(chǔ)（第3版），黃迪明等編著，電子科技大學(xué)出版社，出版日期2009年7月 參考資料： 1數(shù)據(jù)結(jié)構(gòu)清華大學(xué)出版社，嚴蔚敏等 2計算機操作系統(tǒng)西安電子科技大學(xué)出版社，湯子瀛,SCIE, University of Electronic Science and Technology of China,3,課程簡介,課程安排 講授學(xué)時安排（4

2、8學(xué)時）： 第一章 數(shù)據(jù)結(jié)構(gòu) 26學(xué)時 第二章 操作系統(tǒng) 22學(xué)時 軟件技術(shù)基礎(chǔ) QQ群554768353,SCIE, University of Electronic Science and Technology of China,4,課程簡介,考核方式 平時考核占15%，包括課堂出勤，平時作業(yè) 中期考試占5%，采用開卷考試方式 期末考試占80%，采用閉卷考試方式,SCIE, University of Electronic Science and Technology of China,5,1、數(shù)據(jù)結(jié)構(gòu)的基本概念,幾個基本問題 什么是數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義,S

3、CIE, University of Electronic Science and Technology of China,6,1、數(shù)據(jù)結(jié)構(gòu)的基本概念,本章主要講述內(nèi)容 1.1 數(shù)據(jù)結(jié)構(gòu)中的基本術(shù)語 1.2 數(shù)據(jù)的邏輯結(jié)構(gòu) 1.3 數(shù)據(jù)的存儲結(jié)構(gòu) 1.4 算法,SCIE, University of Electronic Science and Technology of China,7,1.1數(shù)據(jù)結(jié)構(gòu)中的基本術(shù)語,一、數(shù)據(jù)及數(shù)據(jù)元素的概念 數(shù)據(jù)是客觀事物在計算機內(nèi)的抽象描述 數(shù)據(jù)指一些事實，或一些數(shù)，或一些符號集合 數(shù)據(jù)的基本單位：數(shù)據(jù)元素 組成數(shù)據(jù)的“事實”、“數(shù)值”或“符號”稱為數(shù)據(jù)元素

4、 數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成,三者之間的關(guān)系,例：班級通訊錄 個人記錄 姓名、年齡,數(shù)據(jù) 數(shù)據(jù)元素 數(shù)據(jù)項,SCIE, University of Electronic Science and Technology of China,8,1.1數(shù)據(jù)結(jié)構(gòu)中的基本術(shù)語,例1、學(xué)生花名冊,數(shù)據(jù)元素,數(shù)據(jù),學(xué)生名字的集合,每個學(xué)生的名字,例2、學(xué)生成績表,數(shù)據(jù),數(shù)據(jù)元素,數(shù)據(jù)項,學(xué)生成績的集合,每個學(xué)生的成績,名字,成績,SCIE, University of Electronic Science and Technology of China,9,1.1數(shù)據(jù)結(jié)構(gòu)中的基本術(shù)語,二、數(shù)據(jù)結(jié)構(gòu)的概念 結(jié)

5、構(gòu)是指事物間的相互關(guān)系和約束。 數(shù)據(jù)結(jié)構(gòu)討論計算機系統(tǒng)中數(shù)據(jù)的組織形式及其相互關(guān)系 數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種和多種特定關(guān)系的數(shù)據(jù)元素的集合，表示為：,Data_Structure=（D, R）,元素有限集,關(guān)系有限集,SCIE, University of Electronic Science and Technology of China,10,1.1數(shù)據(jù)結(jié)構(gòu)中的基本術(shù)語,元素集合,元素間的關(guān)系,運算,計 算 機 系 統(tǒng),元素在計算機系統(tǒng)里的表示 字符？字串？整數(shù)？ 元素間的邏輯關(guān)系邏輯結(jié)構(gòu) 元素在計算機系統(tǒng)中的存儲方式，物理空間關(guān)系存儲結(jié)構(gòu) 操作指令的集合 算法,SCIE, Univer

6、sity of Electronic Science and Technology of China,11,三、數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)的存儲結(jié)構(gòu) 邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間關(guān)系的描述 存儲結(jié)構(gòu)：數(shù)據(jù)元素在計算機系統(tǒng)存儲器中的存放方式,例：班級里的同學(xué),可能有各種各樣的邏輯關(guān)系。比如班長、班委、群眾等。形成相應(yīng)的邏輯結(jié)構(gòu)。,上課時，大家的座次形成存儲結(jié)構(gòu),座次（存儲結(jié)構(gòu)）可能與邏輯關(guān)系有關(guān)，也可能無關(guān)。,1.1數(shù)據(jù)結(jié)構(gòu)中的基本術(shù)語,SCIE, University of Electronic Science and Technology of China,12,邏輯結(jié)構(gòu),四、小結(jié)： 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的

7、邏輯結(jié)構(gòu)，數(shù)據(jù)在計算機系統(tǒng)中的存儲結(jié)構(gòu)和數(shù)據(jù)操作的集合 把數(shù)據(jù)以一定的邏輯結(jié)構(gòu)組織起來，以適當(dāng)?shù)姆绞酱鎯υ谟嬎銠C系統(tǒng)的存儲器里，其最終目的是為了有效處理數(shù)據(jù)，提高數(shù)據(jù)處理運算速度（教材P3),存儲結(jié)構(gòu),算法,1.1數(shù)據(jù)結(jié)構(gòu)中的基本術(shù)語,要素,目標(biāo),三個要素都與我們所要實現(xiàn)的目標(biāo)相關(guān),有效處理數(shù)據(jù),提高數(shù)據(jù)處理運算速度,SCIE, University of Electronic Science and Technology of China,13,數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間關(guān)系的描述 一、描述法 二元組 關(guān)系：一般抽象為前驅(qū)與后繼關(guān)系， 即表明結(jié)構(gòu)中，一個元素的前一個元素是誰，它的后一個元素

8、又是誰,B （ K， R ）,K：元素集合,R：元素間關(guān)系的集合,1.2數(shù)據(jù)的邏輯結(jié)構(gòu),SCIE, University of Electronic Science and Technology of China,14,二、圖示法 圖形要素： 結(jié)點和有向線段 結(jié)點：表示一個數(shù)據(jù)元素，一般以方形框代表 不管多么復(fù)雜的結(jié)點，都看作是一個結(jié)點 有向線段：表示元素之間的關(guān)系。 箭尾指向的結(jié)點是前驅(qū)。 箭頭指向的結(jié)點是后繼,K i,K h,K j,Ki的前驅(qū),Ki的后繼,1.2數(shù)據(jù)的邏輯結(jié)構(gòu),SCIE, University of Electronic Science and Technology of

9、 China,15,數(shù)據(jù)的存儲結(jié)構(gòu)（物理結(jié)構(gòu)） 是數(shù)據(jù)元素在計算機系統(tǒng)存儲器中的存放方式 也可以說，是數(shù)據(jù)邏輯結(jié)構(gòu)在存儲器中的存放方式,1.3數(shù)據(jù)的存儲結(jié)構(gòu),存儲器的特點：由地址連續(xù)的單元構(gòu)成,SCIE, University of Electronic Science and Technology of China,16,0300,0301,0302,0303,0304,0305,0306,0307,0308,0309,K1,K2,K3,K4,K1,K2,K3,K4,1.3數(shù)據(jù)的存儲結(jié)構(gòu),邏輯結(jié)構(gòu),物理結(jié)構(gòu),SCIE, University of Electronic Science and

10、 Technology of China,17,0300,0301,0302,0303,0304,0305,0306,0307,0308,0309,K1,K2,K3,K4,K5,K6,K1,K2,K3,K4,K5,K6,1.3數(shù)據(jù)的存儲結(jié)構(gòu),邏輯結(jié)構(gòu),物理結(jié)構(gòu),SCIE, University of Electronic Science and Technology of China,18,1.3數(shù)據(jù)的存儲結(jié)構(gòu),思考：為什么數(shù)據(jù)邏輯結(jié)構(gòu)與物理結(jié)構(gòu)沒有完全統(tǒng)一？,存儲器的特點：由地址連續(xù)的單元構(gòu)成。線性關(guān)系,存儲單元間位置上的線性關(guān)系有時不能 直接反映復(fù)雜的邏輯關(guān)系,SCIE, Universi

11、ty of Electronic Science and Technology of China,19,幾種物理存儲方式 一、順序存儲方法 連續(xù)順序地存放數(shù)據(jù)元素 若數(shù)據(jù)的邏輯結(jié)構(gòu)也是順序（線性）的，則邏輯結(jié)構(gòu)和物理結(jié)構(gòu)完全統(tǒng)一了 連續(xù)存放的數(shù)據(jù)元素可以在內(nèi)存中容易找到,1.3數(shù)據(jù)的存儲結(jié)構(gòu),SCIE, University of Electronic Science and Technology of China,20,二、鏈接存儲方法 元素在內(nèi)存中不一定連續(xù)存放 在元素中附加指針項，通過指針可以找到關(guān)系元素,元素指針,結(jié)點,元素,指針,1.3數(shù)據(jù)的存儲結(jié)構(gòu),聯(lián)想：在一套叢書中每一本書中夾一

12、個卡片，記錄下一本書在書架上的位置,SCIE, University of Electronic Science and Technology of China,21,0300,0310,0320,0330,0340,0350,0370,0380,K1,K2,K3,K4,K5,K6,K1,K2,K3,K4,K5,K6,通過指針，可以方便地找到關(guān)系結(jié)點,指向后繼結(jié)點的指針,1.3數(shù)據(jù)的存儲結(jié)構(gòu),邏輯結(jié)構(gòu),物理結(jié)構(gòu),SCIE, University of Electronic Science and Technology of China,22,三、索引存儲方法 為放在內(nèi)存中的元素建立索引表 元素

13、可以離散存放 通過查索引表找到需要的元素,0300,0301,0302,0303,0304,0305,0306,0307,0308,0309,K1,K2,K3,K4,1,2,3,4,索引表,索引號,1.3數(shù)據(jù)的存儲結(jié)構(gòu),聯(lián)想：圖書館的查書卡,SCIE, University of Electronic Science and Technology of China,23,四、散列存儲方法 結(jié)點中設(shè)一關(guān)鍵值，利用關(guān)鍵值和相應(yīng)散列函數(shù)算出結(jié)點位置（地址）,例：以用戶姓名為關(guān)鍵值,DJS,算式：字母的序號相加,041019 33,ZXM,262413 63,1.3數(shù)據(jù)的存儲結(jié)構(gòu),DJS放在33號地址

14、單元 ZXM放在63號地址單元,聯(lián)想：通過書的名字就能確定書的位置,SCIE, University of Electronic Science and Technology of China,24,小結(jié)：數(shù)據(jù)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu) 1、物理結(jié)構(gòu)是元素在內(nèi)存中的存儲方式，與元素間固有的邏輯關(guān)系是相對獨立的兩個問題 物理結(jié)構(gòu)著眼于結(jié)點在內(nèi)存中的定位 2、簡單的邏輯結(jié)構(gòu)可能和物理結(jié)構(gòu)一致 例：線性邏輯關(guān)系與順序存儲方法 3、利用物理結(jié)構(gòu)在內(nèi)存中找到一個結(jié)點，而為什么要找這個結(jié)點卻由元素間的邏輯關(guān)系決定 任何一個算法的設(shè)計取決于選定的數(shù)據(jù)邏輯結(jié)構(gòu)，而算法的實現(xiàn)依賴于采用的存儲結(jié)構(gòu) 4、邏輯結(jié)構(gòu)與存儲結(jié)

15、構(gòu)是一個問題的兩個方面,1.3數(shù)據(jù)的存儲結(jié)構(gòu),SCIE, University of Electronic Science and Technology of China,25,例：一個樹形關(guān)系結(jié)構(gòu)用索引方式存儲,1,2,3,4,5,6,0300,0301,0302,0303,0304,0305,0306,0307,0308,0309,K1,K2,K3,K4,K5,K6,1.3數(shù)據(jù)的存儲結(jié)構(gòu),SCIE, University of Electronic Science and Technology of China,26,1.3數(shù)據(jù)的存儲結(jié)構(gòu),SCIE, University of Elect

16、ronic Science and Technology of China,27,一、算法的概念及特點 算法是為解決某一特定類型問題規(guī)定的運算規(guī)則的有窮集合 有窮性 確定性 有效性 輸入 輸出,特 點,非無限執(zhí)行，必須在有限步驟內(nèi)結(jié)束,非二義，下一步必須是明確的,每一步是可執(zhí)行的,外部輸入零個或多個,至少一個,1.4算法,SCIE, University of Electronic Science and Technology of China,28,二、算法與程序 相似：都是解決問題的方法和步驟，是指令的集合 區(qū)別： 算法具有有窮性 描述方法 聯(lián)系：程序用某種程序設(shè)計語言來實現(xiàn)算法,程序使用

17、程序設(shè)計語言,算法可以使用框圖及其他語言,1.4算法,類似： While(1) 的語句段，在程序中允許 但在算法中不允許,SCIE, University of Electronic Science and Technology of China,29,三、算法語言 算法應(yīng)有嚴格的描述語言（確定性） 一般使用類PASCAL語言 在本課程中使用類C語言，即語言風(fēng)格類似于C 描述一個算法時必須滿足： 對輸入和輸出的描述 描述語句準(zhǔn)確、無二義 保證算法的有窮性和有效性,1.4算法,SCIE, University of Electronic Science and Technology of Chi

18、na,30,1.4算法,算法的寫作規(guī)范,int seq_search( elemtype s ,keytype k, int n),int low, high, mid;,sn.key = k; i = 0;,while(s i .key != k) i+;,if(i n) return i; else return -1;,SCIE, University of Electronic Science and Technology of China,31,四、在數(shù)據(jù)結(jié)構(gòu)中常見的問題 創(chuàng)建、插入、刪除、更新、檢索、排序 注意：每個問題都有一種或多種算法 找到效率最高的 以最容易理解的方式設(shè)計 設(shè)計的算法不容易出錯或出錯情況較少,1.4算法,SCIE, University of Electronic Science and Technology of China,32,五、算法和數(shù)據(jù)結(jié)構(gòu)的關(guān)系 算法是建立在數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上的 合理的數(shù)據(jù)結(jié)構(gòu)常?？梢杂行У暮喕惴?只有明確了算法，才能較好的設(shè)計數(shù)據(jù)結(jié)構(gòu) 程序