軟基軟件技術(shù)基礎(chǔ)_ds

1、軟件技術(shù)基礎(chǔ)霍永青Phone：61831246Office：科B24221、課程內(nèi)容數(shù)據(jù)結(jié)構(gòu)：計(jì)算機(jī)軟件基礎(chǔ)，描述計(jì)算機(jī)內(nèi)數(shù)據(jù) 的邏輯關(guān)系，是計(jì)算機(jī)操控對象的抽 象模型。操作系統(tǒng)：計(jì)算機(jī)核心軟件的集合，是計(jì)算機(jī)系 統(tǒng)的邏輯抽象。數(shù)據(jù)庫 ：計(jì)算機(jī)數(shù)據(jù)處理的延伸發(fā)展。幫助用 戶有效地組織大量數(shù)據(jù)。軟件工程：軟件開發(fā)的一般步驟和方法。網(wǎng)絡(luò)基礎(chǔ)：網(wǎng)絡(luò)基礎(chǔ)、協(xié)議及編程接口。32、課程安排課堂講授40學(xué)時，半期考試2學(xué)時，復(fù)習(xí)、作業(yè)講評2學(xué)時，上機(jī)實(shí)驗(yàn)20學(xué)時。 數(shù)據(jù)結(jié)構(gòu)-22學(xué)時 操作系統(tǒng)-18學(xué)時 數(shù)據(jù)庫-自學(xué) 軟件工程-自學(xué) 網(wǎng)絡(luò)基礎(chǔ)-自學(xué)4第一章數(shù)據(jù)結(jié)構(gòu)1.1 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)知識線

2、性結(jié)構(gòu)（線性表、棧隊(duì)列、數(shù)組、串）非線性結(jié)構(gòu)（樹及二叉樹、圖）查找與排序數(shù)據(jù)結(jié)構(gòu)Data Structure5數(shù)據(jù)結(jié)構(gòu)中的一些基本概念數(shù)據(jù)：客觀事物采用計(jì)算機(jī)進(jìn)行識別、存儲和加工所進(jìn)行的描述。（數(shù)值性數(shù)據(jù)、非數(shù)值性數(shù)據(jù)）單位？數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，也是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位。又稱為結(jié)點(diǎn)、記錄數(shù)據(jù)對象（Data Object）：性質(zhì)相同的數(shù)據(jù)元素的集合，數(shù)據(jù)的子集。數(shù)據(jù)項(xiàng)組成 7例：學(xué)號姓名英語數(shù)學(xué)物理1趙一9085932錢二8892803孫三708077.數(shù)據(jù)數(shù)據(jù)元素（節(jié)點(diǎn)）數(shù)據(jù)項(xiàng)數(shù)據(jù)對象車型生產(chǎn)商顏色載重價(jià)格DF141二汽蘭5噸13萬88什么是數(shù)據(jù)結(jié)構(gòu)？數(shù)據(jù)結(jié)構(gòu) 討論計(jì)算機(jī)系統(tǒng)中數(shù)據(jù)

3、的組織形式及其相互關(guān)系 是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。 是對數(shù)據(jù)元素之間的邏輯關(guān)系、數(shù)據(jù)的存儲方式以及對數(shù)據(jù)的操作的抽象描述。數(shù)據(jù)結(jié)構(gòu)的三個層次某一數(shù)據(jù)對象的所有數(shù)據(jù)成員之間的關(guān)系。數(shù)據(jù)結(jié)構(gòu)定義: 數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)存儲結(jié)構(gòu)操作9數(shù)據(jù)元素之間關(guān)系的描述1、二元組：B （ D， R ）D：元素集合R：元素間關(guān)系的集合關(guān)系：主要抽象為前驅(qū)與后繼關(guān)系，表明結(jié)構(gòu)中，一個元素的前一個元素是誰，它的后一個元素又是誰。（一）數(shù)據(jù)的邏輯結(jié)構(gòu)102、圖示法 圖形要素：結(jié)點(diǎn)和有向線段結(jié)點(diǎn)：表示一個數(shù)據(jù)元素，一般以方形框代表 不管多么復(fù)雜的結(jié)點(diǎn)，都看作是一個結(jié)點(diǎn)K i有向線段：表示元素之間的關(guān)系：

4、箭尾指向的結(jié)點(diǎn)是前驅(qū)箭頭指向的結(jié)點(diǎn)是后繼K hK jKi的前驅(qū)Ki的后繼11邏輯結(jié)構(gòu)有且僅有一個開始數(shù)據(jù)元素，有且僅有一個結(jié)束數(shù)據(jù)元素，其他數(shù)據(jù)元素最多只有一個直接前趨和直接后繼。代表：線性表每個數(shù)據(jù)元素可能有多個直接前趨和直接后繼。有且僅有一個稱為“根”的元素?zé)o直接前趨，其他元素有且僅有一個直接前趨。樹圖每一個數(shù)據(jù)元素的直接前趨和直接后繼個數(shù)沒有限制。非線性結(jié)構(gòu)線性結(jié)構(gòu)12（二）數(shù)據(jù)的存儲結(jié)構(gòu)存儲結(jié)構(gòu)（物理結(jié)構(gòu)）順序存儲方法散列存儲方法（地址轉(zhuǎn)移法）鏈接存儲方法索引存儲方法主要用于線性數(shù)據(jù)結(jié)構(gòu)，如線性表、數(shù)組數(shù)據(jù)元素分為數(shù)據(jù)項(xiàng)和指針項(xiàng)兩部分，如鏈表稠密索引（Dense Index)稀疏索引（

5、Sparse Index）數(shù)據(jù)元素在存儲器中的存放方式思考：為什么數(shù)據(jù)邏輯結(jié)構(gòu)與物理結(jié)構(gòu)不能完全統(tǒng)一？131、順序存儲方法連續(xù)順序地存放數(shù)據(jù)元素，若數(shù)據(jù)的邏輯結(jié)構(gòu)也是順序（線性）的，則邏輯結(jié)構(gòu)和物理結(jié)構(gòu)就完全統(tǒng)一了。K1K2K3K40300030103020303030403050306030703080309K1K2K3K4140300030103020303030403050306030703080309K1K2K3K4K5K6K1K2K3K4K5K6存儲器的特點(diǎn)：由地址連續(xù)的單元構(gòu)成單元間的線性關(guān)系不能反映非線性邏輯關(guān)系152、鏈接存儲方法元素在內(nèi)存中不一定連續(xù)存放在元素中附加指針項(xiàng)，通

6、過指針可以找到關(guān)系元素元素指針結(jié)點(diǎn)元素指針160300031003200330030403500370030203080390K1K2K3K4K5K6K1K2K3K4K5K6通過指針，可以方便地找到關(guān)系結(jié)點(diǎn)指向后繼結(jié)點(diǎn)的指針指向前驅(qū)結(jié)點(diǎn)的指針173、索引存儲方法為放在內(nèi)存中的元素建立索引表0300030103020303030403050306030703080309K1K2K3K41234索引表元素可以離散存放通過查索引表找到需要的元素索引號184、散列存儲方法結(jié)點(diǎn)中設(shè)一關(guān)鍵值，利用關(guān)鍵值和公式算出結(jié)點(diǎn)位置 （地址）例：以用戶姓名為關(guān)鍵值DJS公式為字母的序號相加04 + 10 + 19 =

7、 33ZXM26 + 24 + 13 = 6319數(shù)據(jù)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)小結(jié)1、物理結(jié)構(gòu)是元素在內(nèi)存中的存儲方式，與元素間固有的邏輯關(guān)系是相對獨(dú)立的兩個問題物理結(jié)構(gòu)著眼于結(jié)點(diǎn)在內(nèi)存中的定位2、簡單的邏輯結(jié)構(gòu)可能和物理結(jié)構(gòu)一致例：線性邏輯關(guān)系與順序存儲方法3、利用物理結(jié)構(gòu)在內(nèi)存中找到一個結(jié)點(diǎn)，而為什么要找這個結(jié)點(diǎn)卻由元素間的邏輯關(guān)系決定!任何一個算法的設(shè)計(jì)取決于選定的數(shù)據(jù)邏輯結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴于采用的存儲結(jié)構(gòu)。20（三）數(shù)據(jù)的操作插入：遍歷：刪除：查找：排序：更新：在數(shù)據(jù)結(jié)構(gòu)的各個元素中移動，逐一查看所有數(shù)據(jù)元素向數(shù)據(jù)結(jié)構(gòu)中添加新元素修改或替代數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素在數(shù)據(jù)結(jié)構(gòu)中去除指定的元素

8、在數(shù)據(jù)結(jié)構(gòu)中查找滿足條件的元素把數(shù)據(jù)結(jié)構(gòu)中的元素按要求重新排序21數(shù)據(jù)結(jié)構(gòu)的命名 由于數(shù)據(jù)結(jié)構(gòu)具有三個層次，故在對數(shù)據(jù)結(jié)構(gòu)命名的時候可以將數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)甚至操作結(jié)合起來給數(shù)據(jù)結(jié)構(gòu)進(jìn)行命名。線性表存儲方式順序表順序存儲方式鏈表鏈接存儲方式操作棧插入和刪除在同一端隊(duì)列插入在一端 刪除在另一端僅是一種線性結(jié)構(gòu)22常見的數(shù)據(jù)結(jié)構(gòu)線性結(jié)構(gòu)樹結(jié)構(gòu)圖結(jié)構(gòu)A1A2A3A4A4A3A2A1內(nèi)存45hA3A216hA1內(nèi)存01h16h45h順序表（數(shù)組）鏈表56h56hA423數(shù)據(jù)類型數(shù)據(jù)類型（Data Type）：一組性質(zhì)相同值的集合和定義在這個值的集合上的一組操作的總稱。非結(jié)構(gòu)的原子類型構(gòu)造類型如

9、C 語言中的基本數(shù)據(jù)類型：int 、float 、 char 、*（指針型）等等如在 C 語言中利用基本數(shù)據(jù)類型構(gòu)造的結(jié)構(gòu)類型24 算法與程序相似：都是解決問題的方法和步驟區(qū)別：聯(lián)系：程序用某種程序設(shè)計(jì)語言來實(shí)現(xiàn)算法程序使用程序設(shè)計(jì)語言算法可以使用框圖及其他語言算法的實(shí)現(xiàn)必須借助于程序設(shè)計(jì)語言中提供的數(shù)據(jù)類型及其運(yùn)算。數(shù)據(jù)結(jié)構(gòu)的選擇對數(shù)據(jù)處理的效率起著至關(guān)重要的作用。程序算法數(shù)據(jù)結(jié)構(gòu)描述方法26算法基本概念定義：算法是為解決某一特定類型問題規(guī)定的運(yùn)算規(guī)則的有窮集合。特性： 輸入 有0個或多個輸入 輸出 有一個或多個輸出(處理結(jié)果) 確定性 每步定義都是確切、無歧義的 有窮性 算法應(yīng)在執(zhí)行有窮步

10、后結(jié)束 有效性 每一條運(yùn)算應(yīng)足夠基本，可執(zhí)行算法的性能標(biāo)準(zhǔn)： 正確性、可使用性、可讀性、效率、健壯性2527算法效率的 衡量方法和準(zhǔn)則通常有兩種衡量算法效率的方法: 事后統(tǒng)計(jì)法事前分析估算法缺點(diǎn)：1必須執(zhí)行程序 2其它因素掩蓋算法本質(zhì)28和算法執(zhí)行時間相關(guān)的因素：1算法選用的策略2問題的規(guī)模3編寫程序的語言4編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量5計(jì)算機(jī)執(zhí)行指令的速度29 一個特定算法的“運(yùn)行工作量”的大小，只依賴于問題的規(guī)模（通常用整數(shù)量n表示），或者說，它是問題規(guī)模的函數(shù)。30 假如，隨著問題規(guī)模 n 的增長，算法執(zhí)行時間的增長率和 f(n) 的增長率相同，則可記作：T (n) = O(f(n)稱T

11、 (n) 為算法的(漸近)時間復(fù)雜度。31如何估算 算法的時間復(fù)雜度？時間復(fù)雜度度量運(yùn)行時間 = 算法中每條語句執(zhí)行時間之和。每條語句執(zhí)行時間 = 該語句的執(zhí)行次數(shù)（頻度） * 語句執(zhí)行一次所需時間。語句執(zhí)行一次所需時間取決于機(jī)器的指令性能和速度和編譯所產(chǎn)生的代碼質(zhì)量，很難確定。設(shè)每條語句執(zhí)行一次所需時間為單位時間，則一個算法的運(yùn)行時間就是該算法中所有語句的頻度之和。28時間復(fù)雜度計(jì)算示例1. for (i=0; in; i+)2. for (j=0; jn; j+)3. bij=0;4. for (k=0; kn; k+)5. bij=bij+aik*akj;6. 我們以執(zhí)行次數(shù)最多的語句（

12、第5句）進(jìn)行計(jì)算： 語句頻度為：F(n)=n3 時間復(fù)雜度：T(n)=O(F(n)=O(n3)2934 4）思考下列程序段的時間復(fù)雜度 1、x=x+1; 2、for (j=0; jn; j+) x=x+1; 3、for (j=0; jn; j+) for (k=0; kn; k+) x=x+1; 4、for (j=2; j=n; j+) for (k=2; kreal;45結(jié)構(gòu)類型的定義typedef struct my_typeint x;int y;my_type;利用結(jié)構(gòu)類型聲明變量my_type my_struct ;46結(jié)構(gòu)的使用my_type my_struct ; 結(jié)構(gòu)變量K =

13、 my_struct . x;訪問結(jié)構(gòu)中的變量對結(jié)構(gòu)變量取成員 使用 . 符號對使用指向結(jié)構(gòu)的指針取成員 使用 - 符號my_type * my_pointer ; 結(jié)構(gòu)指針變量my_pointer = &my_struct;K = my_pointer-x;47結(jié)構(gòu)體指針的概念存放結(jié)構(gòu)體首地址一個結(jié)構(gòu)體變量的指針就是該變量所占據(jù)的內(nèi)存段的起始地址。結(jié)構(gòu)體指針可以作為函數(shù)參數(shù)，傳遞結(jié)構(gòu)體的首地址結(jié)構(gòu)體指針48部分運(yùn)算符賦值變量1 = 變量2邏輯判斷相等 ： = 或條件：| 與條件：&邏輯運(yùn)算或運(yùn)算：|與運(yùn)算：&非運(yùn)算：！j = j+1; j += 1; j+;等價(jià)加1：+減1：- -49C語言

14、語句賦值語句條件語句分支語句注意多條語句時大括號的使用多條語句時不需使用大括號switch (分支變量） case 分支值1：語句；break;if （條件） 語句；條件為真else 語句；條件為假50C語言語句while循環(huán)for循環(huán)do while循環(huán)while（條件 ） 語句；for（初始化語句；條件；步進(jìn)語句） 語句；do 語句；while （條件）51for( j = 0; j 10; j+) . 等價(jià)j = 0;while( j 10)j + ;j 0;do j +; while(j 10)j = 0;while( jy?x:y); int max(int *x,int *y) return(*x*y?*x:*y); 函數(shù)調(diào)用：c=max(a,b); c=max(&