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

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

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

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

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

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

7、 33ZXM26 + 24 + 13 = 6319數(shù)據(jù)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)小結(jié)1、物理結(jié)構(gòu)是元素在內(nèi)存中的存儲(chǔ)方式，與元素間固有的邏輯關(guān)系是相對(duì)獨(dú)立的兩個(gè)問(wèn)題物理結(jié)構(gòu)著眼于結(jié)點(diǎn)在內(nèi)存中的定位2、簡(jiǎn)單的邏輯結(jié)構(gòu)可能和物理結(jié)構(gòu)一致例：線性邏輯關(guān)系與順序存儲(chǔ)方法3、利用物理結(jié)構(gòu)在內(nèi)存中找到一個(gè)結(jié)點(diǎn)，而為什么要找這個(gè)結(jié)點(diǎn)卻由元素間的邏輯關(guān)系決定!任何一個(gè)算法的設(shè)計(jì)取決于選定的數(shù)據(jù)邏輯結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴于采用的存儲(chǔ)結(jié)構(gòu)。20（三）數(shù)據(jù)的操作插入：遍歷：刪除：查找：排序：更新：在數(shù)據(jù)結(jié)構(gòu)的各個(gè)元素中移動(dòng)，逐一查看所有數(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)具有三個(gè)層次，故在對(duì)數(shù)據(jù)結(jié)構(gòu)命名的時(shí)候可以將數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)甚至操作結(jié)合起來(lái)給數(shù)據(jù)結(jié)構(gòu)進(jìn)行命名。線性表存儲(chǔ)方式順序表順序存儲(chǔ)方式鏈表鏈接存儲(chǔ)方式操作棧插入和刪除在同一端隊(duì)列插入在一端 刪除在另一端僅是一種線性結(jié)構(gòu)22常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)線性結(jié)構(gòu)樹(shù)結(jié)構(gòu)圖結(jié)構(gòu)A1A2A3A4A4A3A2A1內(nèi)存45hA3A216hA1內(nèi)存01h16h45h順序表（數(shù)組）鏈表56h56hA423數(shù)據(jù)類型數(shù)據(jù)類型（Data Type）：一組性質(zhì)相同值的集合和定義在這個(gè)值的集合上的一組操作的總稱。非結(jié)構(gòu)的原子類型構(gòu)造類型如

9、C 語(yǔ)言中的基本數(shù)據(jù)類型：int 、float 、 char 、*（指針型）等等如在 C 語(yǔ)言中利用基本數(shù)據(jù)類型構(gòu)造的結(jié)構(gòu)類型24 算法與程序相似：都是解決問(wèn)題的方法和步驟區(qū)別：聯(lián)系：程序用某種程序設(shè)計(jì)語(yǔ)言來(lái)實(shí)現(xiàn)算法程序使用程序設(shè)計(jì)語(yǔ)言算法可以使用框圖及其他語(yǔ)言算法的實(shí)現(xiàn)必須借助于程序設(shè)計(jì)語(yǔ)言中提供的數(shù)據(jù)類型及其運(yùn)算。數(shù)據(jù)結(jié)構(gòu)的選擇對(duì)數(shù)據(jù)處理的效率起著至關(guān)重要的作用。程序算法數(shù)據(jù)結(jié)構(gòu)描述方法26算法基本概念定義：算法是為解決某一特定類型問(wèn)題規(guī)定的運(yùn)算規(guī)則的有窮集合。特性： 輸入 有0個(gè)或多個(gè)輸入 輸出 有一個(gè)或多個(gè)輸出(處理結(jié)果) 確定性 每步定義都是確切、無(wú)歧義的 有窮性 算法應(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í)行時(shí)間相關(guān)的因素：1算法選用的策略2問(wèn)題的規(guī)模3編寫程序的語(yǔ)言4編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量5計(jì)算機(jī)執(zhí)行指令的速度29 一個(gè)特定算法的“運(yùn)行工作量”的大小，只依賴于問(wèn)題的規(guī)模（通常用整數(shù)量n表示），或者說(shuō)，它是問(wèn)題規(guī)模的函數(shù)。30 假如，隨著問(wèn)題規(guī)模 n 的增長(zhǎng)，算法執(zhí)行時(shí)間的增長(zhǎng)率和 f(n) 的增長(zhǎng)率相同，則可記作：T (n) = O(f(n)稱T

11、 (n) 為算法的(漸近)時(shí)間復(fù)雜度。31如何估算 算法的時(shí)間復(fù)雜度？時(shí)間復(fù)雜度度量運(yùn)行時(shí)間 = 算法中每條語(yǔ)句執(zhí)行時(shí)間之和。每條語(yǔ)句執(zhí)行時(shí)間 = 該語(yǔ)句的執(zhí)行次數(shù)（頻度） * 語(yǔ)句執(zhí)行一次所需時(shí)間。語(yǔ)句執(zhí)行一次所需時(shí)間取決于機(jī)器的指令性能和速度和編譯所產(chǎn)生的代碼質(zhì)量，很難確定。設(shè)每條語(yǔ)句執(zhí)行一次所需時(shí)間為單位時(shí)間，則一個(gè)算法的運(yùn)行時(shí)間就是該算法中所有語(yǔ)句的頻度之和。28時(shí)間復(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ù)最多的語(yǔ)句（

12、第5句）進(jìn)行計(jì)算： 語(yǔ)句頻度為：F(n)=n3 時(shí)間復(fù)雜度：T(n)=O(F(n)=O(n3)2934 4）思考下列程序段的時(shí)間復(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;訪問(wèn)結(jié)構(gòu)中的變量對(duì)結(jié)構(gòu)變量取成員 使用 . 符號(hào)對(duì)使用指向結(jié)構(gòu)的指針取成員 使用 - 符號(hào)my_type * my_pointer ; 結(jié)構(gòu)指針變量my_pointer = &my_struct;K = my_pointer-x;47結(jié)構(gòu)體指針的概念存放結(jié)構(gòu)體首地址一個(gè)結(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語(yǔ)言

14、語(yǔ)句賦值語(yǔ)句條件語(yǔ)句分支語(yǔ)句注意多條語(yǔ)句時(shí)大括號(hào)的使用多條語(yǔ)句時(shí)不需使用大括號(hào)switch (分支變量） case 分支值1：語(yǔ)句；break;if （條件） 語(yǔ)句；條件為真else 語(yǔ)句；條件為假50C語(yǔ)言語(yǔ)句while循環(huán)for循環(huán)do while循環(huán)while（條件 ） 語(yǔ)句；for（初始化語(yǔ)句；條件；步進(jìn)語(yǔ)句） 語(yǔ)句；do 語(yǔ)句；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(&