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

軟件技術(shù)基礎(chǔ)第1頁，共44頁，2023年，2月20日，星期日計算機領(lǐng)域的知識需求第2頁，共44頁，2023年，2月20日，星期日課程目的本課程以非計算機專業(yè)的本、專科學(xué)生為對象，通過本課程的學(xué)習(xí)，使其掌握有關(guān)計算機軟件技術(shù)的基礎(chǔ)關(guān)知識和方法，培養(yǎng)學(xué)生利用計算機解決問題的意識和能力，為計算機在其專業(yè)應(yīng)用中奠定基礎(chǔ)，同時也為其深入學(xué)習(xí)計算機知識打下良好的基礎(chǔ)。第3頁，共44頁，2023年，2月20日，星期日參考資料1、嚴(yán)蔚敏等，數(shù)據(jù)結(jié)構(gòu)（C語言版），清華大學(xué)2、徐孝凱，數(shù)據(jù)結(jié)構(gòu)實用教程，清華大學(xué)出版社，1999，10.3、李平等，數(shù)據(jù)結(jié)構(gòu)，電子工業(yè)出版社，2000，1.4、鄭人杰等，實用軟件工程，清華大學(xué)出版社，1997，4.5、江正戰(zhàn)主編，三級偏軟考試教程，東南大學(xué)出版社，2002，6第4頁，共44頁，2023年，2月20日，星期日本課程主要教學(xué)內(nèi)容理論教學(xué)(32學(xué)時):1、數(shù)據(jù)結(jié)構(gòu)（第1---5章）2、軟件工程（第6章：軟件的設(shè)計與開發(fā)）上機實踐(10學(xué)時):1、地點---計算中心2、上機參考教材(電子版)---軟件應(yīng)用技術(shù)基礎(chǔ)實驗指導(dǎo)書第5頁，共44頁，2023年，2月20日，星期日實驗參考教材實驗參考教材:(1)寧正元,易金聰?shù)?數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與上機實驗指導(dǎo),2000,9(2)李春葆,數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析,1999,4第6頁，共44頁，2023年，2月20日，星期日計算機領(lǐng)域的知識需求第7頁，共44頁，2023年，2月20日，星期日計算機領(lǐng)域的知識需求第8頁，共44頁，2023年，2月20日，星期日計算機領(lǐng)域的知識需求第9頁，共44頁，2023年，2月20日，星期日第一章：軟件基礎(chǔ)相關(guān)知識概述計算機基礎(chǔ)知識（已學(xué)習(xí)）程序設(shè)計、計算方法（已學(xué)習(xí)）數(shù)據(jù)處理基本知識（數(shù)據(jù)結(jié)構(gòu)、算法）（本課程）數(shù)據(jù)庫技術(shù)（相關(guān)課程）操作系統(tǒng)編譯原理網(wǎng)絡(luò)系統(tǒng)（相關(guān)課程）軟件工程（本課程）第10頁，共44頁，2023年，2月20日，星期日軟件基礎(chǔ)相關(guān)知識概述討論：什么是程序？什么是軟件？第11頁，共44頁，2023年，2月20日，星期日程序與軟件程序是計算機指令序列，這些指令由非常簡單的四則運算、邏輯運算、數(shù)據(jù)傳送及跳轉(zhuǎn)指令組合而成。程序?qū)嵸|(zhì)上是用某種計算機語言描述的某一問題的解決步驟。1、程序的靜態(tài)與動態(tài)屬性2、程序語言的抽象符號表達(dá)3、對數(shù)據(jù)施行算法的過程4、分層嵌套第12頁，共44頁，2023年，2月20日，星期日程序與軟件1983年，IEEE組織明確地給軟件作了定義：軟件是計算機程序、方法和規(guī)則相關(guān)的文檔以及在計算機上運行它時所必需的數(shù)據(jù)。軟件的特性1、功能、性能相對完備2、具有使用性能的軟設(shè)備3、信息商品4、只有過時而無“磨損”軟件程序第13頁，共44頁，2023年，2月20日，星期日軟件分類系統(tǒng)軟件應(yīng)用軟件（為釋放硬件潛能、方便使用而配備的軟件）操作系統(tǒng)編譯/解釋系統(tǒng)數(shù)據(jù)庫管理軟件各種服務(wù)程序…辦公軟件套件多媒體處理軟件程序開發(fā)工具環(huán)境計算機輔助設(shè)計/制造軟件…（解決某一應(yīng)用領(lǐng)域問題的軟件）第14頁，共44頁，2023年，2月20日，星期日

算法+數(shù)據(jù)結(jié)構(gòu)=程序(NiklausWirth)(Algorithm+Datastructure=Program)

程序：為計算機處理問題編寫的一組指令。

算法：處理問題的策略。

數(shù)據(jù)結(jié)構(gòu)：問題的數(shù)學(xué)模型。程序設(shè)計的實質(zhì)是數(shù)據(jù)的表示和數(shù)據(jù)處理,為此應(yīng)提出問題的數(shù)學(xué)模型和設(shè)計相應(yīng)的算法。第15頁，共44頁，2023年，2月20日，星期日1.

研究數(shù)據(jù)之間的客觀聯(lián)系。

2.

研究具有某種邏輯關(guān)系的數(shù)據(jù)在計算機存儲器內(nèi)的存儲方式。3.研究如何在數(shù)據(jù)的各種結(jié)構(gòu)(邏輯的和物理的)的基礎(chǔ)上對數(shù)據(jù)實施一系列有效的基本操作。邏輯結(jié)構(gòu)存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容算法什么是數(shù)據(jù)結(jié)構(gòu)？第16頁，共44頁，2023年，2月20日，星期日基本操作（對數(shù)據(jù)的處理），通常包含四方面的內(nèi)容：（1）查找數(shù)據(jù)；（2）插入數(shù)據(jù)；（3）刪除數(shù)據(jù)；（4）數(shù)據(jù)排序；第17頁，共44頁，2023年，2月20日，星期日是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，表示為：（數(shù)值或非數(shù)值）Data_Structure=（D,R）——是指同一數(shù)據(jù)元素類型中各元素之間存在的關(guān)系。元素有限集關(guān)系有限集數(shù)據(jù)結(jié)構(gòu)第18頁，共44頁，2023年，2月20日，星期日例如：圖書館的書目檢索問題登錄號書名作者分類號………………172832離散數(shù)學(xué)樊映川S01…172833理論力學(xué)羅遠(yuǎn)祥S01…172834高等數(shù)學(xué)華羅庚S01…172835線性代數(shù)灤汝書S02………………書名登錄號……高等數(shù)學(xué)172832,172834…理論力學(xué)172833…線性代數(shù)172835………作者登錄號……樊映川172832…華羅庚172834…灤汝書172835………類別登錄號……L172833…S172832,172834………第19頁，共44頁，2023年，2月20日，星期日數(shù)據(jù)是描述客觀事物的數(shù)、字符以及所有能輸入到計算機中并為計算機程序處理的對象的集合。數(shù)據(jù)的基本單位，有時一個數(shù)據(jù)元素也可以由若干個數(shù)據(jù)項組成。數(shù)據(jù)結(jié)構(gòu)的基本概念1.數(shù)據(jù)2.數(shù)據(jù)元素例如：描述一年四季的季節(jié)名：春、夏、秋、冬表示數(shù)值的各個數(shù)：18、11、35、23、16、…表示家庭成員的各成員名：父親、兒子、女兒數(shù)據(jù)元素一般具有某種共同特征第20頁，共44頁，2023年，2月20日，星期日對數(shù)據(jù)元素之間邏輯關(guān)系的描述。它可以用一個數(shù)據(jù)元素的集合和定義在這個集合上的若干關(guān)系來表示。4.數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的基本概念具有相同特性的數(shù)據(jù)元素的集合，為數(shù)據(jù)的一個子集。3.數(shù)據(jù)對象第21頁，共44頁，2023年，2月20日，星期日數(shù)據(jù)結(jié)構(gòu)的基本概念一個數(shù)據(jù)結(jié)構(gòu)通常應(yīng)包含兩方面的信息①表示數(shù)據(jù)元素的信息②表示各數(shù)據(jù)元素之間的前后件關(guān)系例如：“春”是“夏”的前件（直接前驅(qū)）“夏”是“春”的后件（直接后繼）“父親”是“兒子”和“女兒”的前件（直接前驅(qū)）“兒子”和“女兒”是“父親”的后件（直接后繼）第22頁，共44頁，2023年，2月20日，星期日B=(D,R)B:數(shù)據(jù)結(jié)構(gòu)D:數(shù)據(jù)元素的集合;R:D上關(guān)系的集合 D中各數(shù)據(jù)元素之間的前后件關(guān)系一般用二元組來表示。例如，a與b是D中的兩個數(shù)據(jù)，則二元組（a，b）表示a是b的前件，b是a的后件。例如：B=(D,R)D={春、夏、秋、冬}R={(春、夏),(夏、秋),(秋、冬)}B=(D,R)D={父親、兒子、女兒}R={(父親、兒子),(父親、女兒)}第23頁，共44頁，2023年，2月20日，星期日數(shù)據(jù)結(jié)構(gòu)還可以直觀地用圖來表示春夏秋冬結(jié)點前后件關(guān)系父親兒子女兒根結(jié)點葉子結(jié)點孫子內(nèi)部結(jié)點第24頁，共44頁，2023年，2月20日，星期日

1）集合：集合中任何兩個結(jié)點之間都沒有邏輯關(guān)系，組織形式松散。數(shù)據(jù)結(jié)構(gòu)的基本概念2）線性結(jié)構(gòu)：元素之間存在著一對一的關(guān)系。依次排列形成一條“鎖鏈”。3）樹形結(jié)構(gòu)：數(shù)據(jù)元素之間存在著一對多的關(guān)系，具有分支、層次特性。4）圖狀結(jié)構(gòu)：數(shù)據(jù)元素之間存在多對多的關(guān)系，元素之間互相纏繞，具有分支、層次特性。第25頁，共44頁，2023年，2月20日，星期日數(shù)據(jù)在計算機中的表示，包括數(shù)據(jù)元素的表示和關(guān)系的表示。1）順序存儲方式（向量存儲）2）鏈?zhǔn)酱鎯Ψ绞?）索引存儲方式4）散列存儲方式5.數(shù)據(jù)的存儲結(jié)構(gòu)6.數(shù)據(jù)結(jié)構(gòu)按照某種邏輯結(jié)構(gòu)組織的一組數(shù)據(jù),按一定的存儲方式將它們映射到計算機的存儲器中，并且在這些數(shù)據(jù)上定義了一個運算的集合，運算的結(jié)果保持原來的結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)的基本概念第26頁，共44頁，2023年，2月20日，星期日數(shù)據(jù)結(jié)構(gòu)涵蓋的內(nèi)容第27頁，共44頁，2023年，2月20日，星期日算法：是對特定問題求解步驟的一種描述。算法的基本特征：可行性：算法的每一步都是能夠?qū)崿F(xiàn)的，即可操作的。確定性：算法的每一步必須是確切定義的。對于相同輸入必須得到相同結(jié)果。有窮性：一個算法必須在執(zhí)行有窮步之后結(jié)束。有輸出：算法執(zhí)行完畢，必須有一個或若干個輸出結(jié)果。算法的基本概念第28頁，共44頁，2023年，2月20日，星期日算法描述語言采用類C語言來描述一、符號與表達(dá)式二、賦值語句三、控制轉(zhuǎn)移語句 如：go,if等語句四、循環(huán)五、其他語句：exit、ruturn、——設(shè)計一種既脫離某種具體的程序設(shè)計語言，又具有各種程序設(shè)計語言的共同特點的形式化語言來描述第29頁，共44頁，2023年，2月20日，星期日1.3算法設(shè)計基本方法常用算法一、枚舉法例：百元買百雞（P12）強力攻擊二、歸納法找規(guī)律第30頁，共44頁，2023年，2月20日，星期日三、遞推法例1：階乘函數(shù)Fn=N*Fn-1已知：F0=1;四、遞歸法例1：階乘函數(shù)例2：hano塔第31頁，共44頁，2023年，2月20日，星期日遞歸函數(shù)的經(jīng)典問題——漢諾塔問題在世界剛被創(chuàng)建的時候有一座鉆石寶塔（塔A），其上有64個金碟。所有碟子按從大到小的次序從塔底堆放至塔頂。緊挨著這座塔有另外兩個鉆石寶塔（塔B和塔C）。從世界創(chuàng)始之日起，婆羅門的牧師們就一直在試圖把塔A上的碟子移動到塔C上去，其間借助于塔B的幫助。每次只能移動一個碟子，任何時候都不能把一個碟子放在比它小的碟子上面。當(dāng)牧師們完成任務(wù)時，世界末日也就到了。

第32頁，共44頁，2023年，2月20日，星期日漢諾塔問題可以通過以下三個步驟實現(xiàn)：（1）將塔A上的n-1個碟子借助塔C先移到塔B上。（2）把塔A上剩下的一個碟子移到塔C上。（3）將n-1個碟子從塔B借助塔A移到塔C上。顯然，這是一個遞歸求解的過程第33頁，共44頁，2023年，2月20日，星期日第34頁，共44頁，2023年，2月20日，星期日算法4.2——漢諾塔算法

1voidHanoi(intn,charA,charB,charC)

//第一列為語句行號2{3if(n==1)Move(A,C);//Move是一個抽象操作，表示將碟子從A移到C上4else{5Hanoi(n-1,A,C,B);6Move(A,C);7Hanoi(n-1,B,A,C);8}9}C++描述第35頁，共44頁，2023年，2月20日，星期日Hanio(3,A,B,C)Hanio(2,A,C,B)Hanio(1,A,B,C)Move(A,C)Move(A,B)Hanio(1,C,A,B)Hanio(1,A,B,C)Hanio(2,A,C,B)Move(C,B)Hanio(1,C,A,B)Move(A,C)Hanio(2,B,A,C)Hanio(1,B,C,A)Move(B,C)Hanio(1,A,B,C)Hanio(1,B,C,A)Move(A,C)Hanio(2,B,A,C)Move(B,A)Hanio(1,A,B,C)結(jié)束第36頁，共44頁，2023年，2月20日，星期日五、分治法例：折半查找六、回溯法（高級算法）例1：8皇后問題七、迭代法例：求X3-X-1=0在x=1.5附近的一個根第37頁，共44頁，2023年，2月20日，星期日算法頻度統(tǒng)計法以語句執(zhí)行的次數(shù)的多少作為算法的時間量度的分析方法稱為頻度統(tǒng)計法。一條語句的頻度是指該語句被執(zhí)行的次數(shù)，而整個算法的頻度是指算法中所有語句的頻度之和。假如隨著問題規(guī)模n的增長，算法執(zhí)行時間的增長率和f(n)的增長率相同，則記作T(n)=O(f(n))，稱T(n)為算法的時間復(fù)雜性。時間復(fù)雜度第38頁，共44頁，2023年，2月20日，星期日時間復(fù)雜度第39頁，共44頁，2023年，2月20日，星期日時間復(fù)雜度第40頁，共44頁，2023年，2月20日，星期日例如：1）x:=x+1;2）For