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

第五章計算機軟件技術(shù)基礎(chǔ)

硬件是計算機系統(tǒng)的基礎(chǔ)，但沒有軟件的計算機是無法工作的。事實上，計算機能廣泛地應(yīng)用于各個領(lǐng)域完全是因為有了豐富的計算機軟件，人們?yōu)榱擞糜嬎銠C解決各類問題，有針對性地開發(fā)了各種各樣的軟件。本章將學(xué)習(xí)計算機軟件和計算機軟件開發(fā)的相關(guān)知識，重點掌握一些基本概念，如什么是軟件，程序設(shè)計語言的分類及構(gòu)成、軟件開發(fā)過程等。5.1計算機軟件系統(tǒng)5.1.1軟件的概念與特點

軟件是計算機系統(tǒng)中與硬件相互依存的另一部分，它由程序、數(shù)據(jù)及其相關(guān)文檔三部分組成。①程序：按照事先設(shè)計的功能和性能要求執(zhí)行的計算機指令序列。②數(shù)據(jù)：使程序能夠正常操縱信息的數(shù)據(jù)結(jié)構(gòu)。③文檔：與程序開發(fā)、維護和使用有關(guān)的資料。

軟件的特點:①抽象性②復(fù)雜性③維護長期性④高成本性5.1計算機軟件系統(tǒng)5.1.2軟件的分類

按軟件功能劃分：①系統(tǒng)軟件：能與計算機硬件緊密配合在一起，使計算機系統(tǒng)的各個部件、相關(guān)的軟件和數(shù)據(jù)協(xié)調(diào)、高效地工作。②支撐軟件：又稱為軟件開發(fā)環(huán)境。是介于系統(tǒng)軟件和應(yīng)用軟件之間的中間層軟件，是支撐各種軟件的開發(fā)與維護的軟件。③應(yīng)用軟件：針對特定領(lǐng)域開發(fā)，為特定目的服務(wù)的軟件。另外，軟件還可以按工作方式、服務(wù)對象進行劃分。5.1計算機軟件系統(tǒng)

計算機軟件系統(tǒng)中所包括的各種軟件之間的關(guān)系不是并列的，而是有一定的層次關(guān)系。5.1.3計算機軟件的層次結(jié)構(gòu)5.2程序設(shè)計語言簡單來講，程序設(shè)計就是用計算機語言編寫程序。程序=算法+數(shù)據(jù)結(jié)構(gòu)

編寫計算機程序時使用的語言稱為程序設(shè)計語言(ProgrammingLanguage)，程序設(shè)計語言分為機器語言、匯編語言和高級語言三種。

對數(shù)據(jù)操作的步驟如何表示、組織和存儲數(shù)據(jù)5.2程序設(shè)計語言5.2.1機器語言

機器語言是指由二進制代碼按照一定規(guī)則組成的命令集合，也稱機器指令集合。機器語言是唯一能被計算機直接理解和執(zhí)行的程序設(shè)計語言，屬低級語言。機器語言的一條語句就是一條指令，機器指令的格式如下：操作碼操作數(shù)例如：計算256+16結(jié)果的機器代碼如下(以十六進制表示)：B80001；把256放入累加器AX051000；把16與AX中值相加，結(jié)果存入AX5.2程序設(shè)計語言5.2.2匯編語言

為了解決機器語言難記憶、可讀性差的缺點，人們把機器指令中的操作碼和操作數(shù)用英文助記符來表示，這種助記符語言稱為匯編語言，也屬于低級語言。MOVAX，256；把256放入累加器AXADDAX，16；把16與AX中值相加，結(jié)果存入AX

匯編語言編寫的程序?qū)儆诜柍绦?，計算機不能直接識別和執(zhí)行，必須翻譯成計算機能識別的機器指令后才能在計算機上執(zhí)行，其翻譯過程如下：5.2程序設(shè)計語言5.2.3高級語言

高級語言是一類程序設(shè)計語言的統(tǒng)稱，它采用接近人類自然語言的表示方法，并遵循一定的語法規(guī)則來編寫程序。實現(xiàn)求整數(shù)的絕對值的程序段：intintVar,result;scanf(“%d”,&intVar);if(intVar>=0)result=intVar;elseresult=-1*intVar;printf(“%d的絕對值是：%d”,intVar,result);5.2程序設(shè)計語言高級語言程序的翻譯和執(zhí)行過程如下：

高級語言編寫的程序也屬于符號程序，不能直接在計算機上執(zhí)行，必須通過程序的翻譯才能執(zhí)行，其翻譯成指令代碼的方法主要有編譯和解釋兩種。5.2程序設(shè)計語言5.2程序設(shè)計語言5.2.4程序設(shè)計語言的構(gòu)成程序設(shè)計語言的構(gòu)成主要包括以下幾個方面：

(1)數(shù)據(jù)類型包括基本數(shù)據(jù)類型和構(gòu)造數(shù)據(jù)類型兩大類。

基本數(shù)據(jù)類型：是由程序設(shè)計語言內(nèi)置的，其特點是不能再分解為其它的類型。在主流的程序設(shè)計語言中一般包括：整數(shù)類型、實數(shù)類型、字符類型、布爾類型等。構(gòu)造數(shù)據(jù)類型：是由基本數(shù)據(jù)類型按照某種方式組合構(gòu)成的。常見的構(gòu)造數(shù)據(jù)類型有：數(shù)組類型、記錄類型(結(jié)構(gòu)體)等等。(2)運算符和表達式

在程序設(shè)計中使用表達式可完成各種各樣的運算。表達式通常包括：常量、變量、運算符和函數(shù)調(diào)用等。5.2程序設(shè)計語言(3)語句

程序是對計算機要執(zhí)行的操作的描述，高級語言源程序的基本組成單位就是語句。語句按功能可以分為兩類：①用于描述操作運算的操作運算語句，如賦值語句；②用于控制操作運算的流程控制語句，如分支控制語句。(4)控制結(jié)構(gòu)①順序結(jié)構(gòu)，按照語句出現(xiàn)的先后順序依次執(zhí)行。②分支結(jié)構(gòu)，根據(jù)給定條件判斷，決定程序執(zhí)行的順序。③循環(huán)結(jié)構(gòu)，循環(huán)(重復(fù))是計算機解題的一個重要特征。5.2程序設(shè)計語言(5)輸入/輸出

高級程序設(shè)計語言中通常以函數(shù)或語句的形式提供輸入輸出操作?，F(xiàn)代高級程序設(shè)計語言通常都提供通過窗口、文本框、按鈕、組合框、圖表等圖形組件進行輸入輸出。(6)子程序

子程序就是將需要重復(fù)使用的程序段或分解的子問題編寫為一個邏輯上獨立的子程序，當程序中需要使用子程序時，再對其進行調(diào)用。使用子程序的好處是降低了程序的復(fù)雜度，使程序的結(jié)構(gòu)清晰，提高了程序設(shè)計的效率。一般程序設(shè)計語言中有兩種子程序：函數(shù)(Function)和過程(Procedure)，它們的主要區(qū)別是函數(shù)有返回值，而過程不能有返回值。C語言舉例:順序題目：用*號輸出字母C的圖案。

1.程序分析：可先用'*'號在紙上寫出字母C，再分行輸出。

2.程序源代碼：

#include"stdio.h"#include"conio.h"main(){clrscr();printf("HelloC-world!\n");printf("*****\n");printf("**\n");printf("**\n");printf("**\n");printf("**\n");printf("**\n");printf("*****\n");getch();}C語言舉例:選擇題目：輸入三個整數(shù)x,y,z，請把這三個數(shù)由小到大輸出。

1.程序分析：我們想辦法把最小的數(shù)放到x上，先將x與y進行比較，如果x>y則將x與y的值進行交換，然后再用x與z進行比較，如果x>z則將x與z的值進行交換，這樣能使x最小。

2.程序源代碼：

#include"stdio.h"

#include"conio.h"

main()

{

intx,y,z,t;

scanf("%d%d%d",&x,&y,&z);

if(x>y)

{t=x;x=y;y=t;}/*交換x,y的值*/

if(x>z)

{t=z;z=x;x=t;}/*交換x,z的值*/

if(y>z)

{t=y;y=z;z=t;}/*交換z,y的值*/

printf("smalltobig:%d%d%d\n",x,y,z);

getch();

}

C語言舉例:循環(huán)題目：打印出所有的“水仙花數(shù)”，所謂“水仙花數(shù)”是指一個三位數(shù)，其各位數(shù)字立方和等于該數(shù)本身。例如：153是一個“水仙花數(shù)”，因為153=1的三次方＋5的三次方＋3的三次方。

1.程序分析：利用for循環(huán)控制100-999個數(shù)，每個數(shù)分解出個位，十位，百位。

2.程序源代碼：

#include"stdio.h"

#include"conio.h"

main()

{

inti,j,k,n;

printf("'waterflower'numberis:");

for(n=100;n<1000;n++)

{

i=n/100;/*分解出百位*/

j=n/10%10;/*分解出十位*/

k=n%10;/*分解出個位*/

if(i*100+j*10+k==i*i*i+j*j*j+k*k*k)

printf("%-5d",n);

}

getch();

}

編寫程序，求s=s1+s2+s3+s4的值，其中：

s1=1+1/2+1/3+…+1/50s2=1+1/2+1/3+…+1/100s3=1+1/2+1/3+…+1/150s4=1+1/2+1/3+…+1/200分析：解決此問題可以先編寫一函數(shù)，用于計算1+1/2+1/3+…+1/n的值，然后，通過調(diào)用該函數(shù)來求s的值。C語言舉例:子程序floatcount(intn){floatsum=0;inti;for(i=1;i<=n;i++)sum+=1.0/i;returnsum;}main(){floats;s=count(50)+count(100)+count(150)+count(200);printf(“s=%8.2f\n”,s);}5.3數(shù)據(jù)結(jié)構(gòu)5.3.1什么是數(shù)據(jù)

數(shù)據(jù)是對客觀事物的描述，對計算機來說，數(shù)字、字符、圖形、色彩、聲音等都是數(shù)據(jù)。數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位。一個數(shù)據(jù)元素可以是一個單個數(shù)據(jù)也可以由若干個數(shù)據(jù)項組成，數(shù)據(jù)項是數(shù)據(jù)不可分割的最小單位。

例：公司員工數(shù)據(jù)的存儲(一個員工信息可以構(gòu)造一個一維數(shù)組的數(shù)據(jù)結(jié)構(gòu))姓名性別出生日期職位工資張軍男1975.5.6總經(jīng)理2080.00李芳女1980.12.12項目經(jīng)理1800.00王明男1979.4.19程序員1500.00劉杰男1974.6.23系統(tǒng)分析員1750.005.3數(shù)據(jù)結(jié)構(gòu)5.3.2數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容

數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)間的相互關(guān)系,即數(shù)據(jù)的組織形式。數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容包括數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)和數(shù)據(jù)結(jié)構(gòu)運算三個方面：(1)數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)元素之間的邏輯上的相互關(guān)系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)，它描述數(shù)據(jù)的組織形式。元素之間是一對一關(guān)系例如:公司員工數(shù)據(jù)表中每個成員關(guān)系元素之間是多對多關(guān)系例如:華農(nóng)與周邊地區(qū)的位置關(guān)系元素之間是一對多關(guān)系例如:一對夫婦和他們的全部子孫元素之間是松散關(guān)系例如:自然數(shù)的全體5.3數(shù)據(jù)結(jié)構(gòu)(2)數(shù)據(jù)的物理結(jié)構(gòu)

數(shù)據(jù)在計算機存儲器中的存儲方式，稱為數(shù)據(jù)的物理結(jié)構(gòu)或存儲結(jié)構(gòu)。它包括：①順序存儲方式，把邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元中。②鏈式存儲方式，每個結(jié)點分為數(shù)據(jù)域和指針域兩部分，數(shù)據(jù)域存儲數(shù)據(jù)元素，指針域存儲與該結(jié)點具有邏輯關(guān)系的結(jié)點的地址。③索引存儲方式，數(shù)據(jù)元素存放在一個不連續(xù)存儲區(qū)域里。再建一個附加的索引表，索引表中的第i項表示第i個元素的存儲地址。④散列存儲方式，數(shù)據(jù)元素均勻地分布在連續(xù)的存儲區(qū)域里，用散列函數(shù)計算各結(jié)點的存儲地址。5.3數(shù)據(jù)結(jié)構(gòu)

例如:線性表是一種邏輯結(jié)構(gòu),若采用順序存儲方式，可稱其為順序表；若采用鏈式存儲方法，可稱其為鏈表。

右圖為某學(xué)生各科成績表分別采用順序和鏈式存儲的情形。前者存儲在一片連續(xù)空間，后者則存儲在非連續(xù)空間。5.3數(shù)據(jù)結(jié)構(gòu)(3)數(shù)據(jù)結(jié)構(gòu)的運算

數(shù)據(jù)結(jié)構(gòu)的運算是定義在數(shù)據(jù)邏輯結(jié)構(gòu)上的操作，如插入、刪除、查找、排序等。每一種數(shù)據(jù)結(jié)構(gòu)都有一個運算及其規(guī)則的集合。

比如一張表格，可能需要進行查找、增加、修改、刪除記錄等，進行這樣的操作已不是加減乘除這樣一些算術(shù)運算，在數(shù)據(jù)結(jié)構(gòu)中，運算常常涉及算法的問題。

5.3數(shù)據(jù)結(jié)構(gòu)5.3.3常見數(shù)據(jù)結(jié)構(gòu)介紹(了解)(1)數(shù)組

數(shù)組屬于線性數(shù)據(jù)結(jié)構(gòu)，是在計算機內(nèi)存中使用一組連續(xù)的存儲單元保存數(shù)據(jù)類型相同的一組數(shù)據(jù)，這些數(shù)據(jù)擁有相同的變量名，稱為數(shù)組名。5.3數(shù)據(jù)結(jié)構(gòu)(2)鏈表

鏈表(LinkedList)是采用鏈式存儲的線性表。線性鏈表的結(jié)點由數(shù)據(jù)域和指針域兩個部分組成，數(shù)據(jù)域存儲數(shù)據(jù)元素，指針域存儲一個指向直接后繼結(jié)點的指針。5.3數(shù)據(jù)結(jié)構(gòu)(3)二叉樹

二叉樹是一種常用的非線性數(shù)據(jù)結(jié)構(gòu)，其定義為：二叉樹是一個結(jié)點的集合，該集合或者為空，或者滿足下面兩個條件：①有且僅有一個稱為根的結(jié)點。②其它結(jié)點分為兩個互不相交的集合T1、T2。T1和T2均為二叉樹，并且在T1和T2之間存在順序關(guān)系(T1在T2之前)，分別稱為根的左子樹和右子樹。二叉樹的5種基本形態(tài)5.3數(shù)據(jù)結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)5.3數(shù)據(jù)結(jié)構(gòu)遍歷二叉樹

遍歷二叉樹是非常重要的一種運算?！氨闅v”的含義是對結(jié)構(gòu)中的每個數(shù)據(jù)都訪問一次且僅訪問一次?？梢杂腥N訪問路徑：①前序遍歷:訪問根結(jié)點;前序遍歷左子樹;前序遍歷右子樹②中序遍歷:中序遍歷左子樹;訪問根結(jié)點;中序遍歷右子樹③后序遍歷:后序遍歷左子樹;后序遍歷右子樹;訪問根結(jié)點①前序遍歷：ABDEFGC②中序遍歷：DBFEGAC③后序遍歷：DFGEBCA5.4算法5.4.1算法的基本概念

算法是指為解決給定問題而需實施的有窮操作步驟的描述。5.4.2算法的描述方法(1)用自然語言描述算法(2)用流程圖描述算法(3)使用偽代碼描述算法(4)用程序設(shè)計語言描述算法

算法的描述方法有以下四種：5.4算法5.4.3查找算法(了解)

查找(Searching)也稱檢索，設(shè)表F中有n個結(jié)點，Ki是記錄Ri的關(guān)鍵字，現(xiàn)給定關(guān)鍵字K，在F中尋找關(guān)鍵字與K相同的結(jié)點R的過程，叫做查找。(1)順序查找

順序查找是線性表的最簡單的查找算法。它是用給定的值與表中的每個結(jié)點的關(guān)鍵字逐個進行比較運算，若找到相等的關(guān)鍵字則查找成功，否則查找失敗。順序查找算法的優(yōu)點是適用范圍廣，對線性表中結(jié)點邏輯次序無關(guān)，即不要求按關(guān)鍵字排序。對線性表的物理存儲結(jié)構(gòu)也沒有要求，順序存儲與鏈式存儲均可。5.4算法(2)折半查找

折半查找的基本思想是：先取表的中間位置的結(jié)點關(guān)鍵字與所給定的關(guān)鍵字進行比較，如果相等，則查找成功。如果給定值比該結(jié)點的關(guān)鍵字大，則所找結(jié)點在表的后半部分；否則所找結(jié)點在表的前半部分，然后再把選定的部分表的中間結(jié)點的關(guān)鍵字與給定關(guān)鍵字進行比較。如此反復(fù)進行，直到查找成功或者查找失敗為止。5.4算法例:5.4算法5.4.4排序算法(了解)

排序(Sort)是數(shù)據(jù)處理中的一種重要運算，它的功能是將一組數(shù)據(jù)元素(或記錄)從任意序列排列成一個按關(guān)鍵字排序的序列。按照排序過程中涉及的存儲器的不同將排序分為內(nèi)部排序和外部排序兩類，其中內(nèi)部排序是指整個排序過程都在內(nèi)存中進行的排序。5.4算法(1)直接插入排序

算法的基本思想如下：①開始時，把第一個記錄看成是已經(jīng)排好序的子序列，這時子序列中只有一個記錄；②從第二個記錄起到最后一個記錄，依次將每個記錄與前面子序列的記錄按關(guān)鍵字比較，確定記錄插入的位置；③將記錄插入到子序列中，子序列記錄個數(shù)加1，直至子序列長度與待排序列長度相等時結(jié)束。5.4算法(1)直接插入排序5.4算法5.4.4排序算法(了解)(2)冒泡排序冒泡排序的算法思想是：①將第n個記錄的關(guān)鍵字與將第n-1個記錄的關(guān)鍵字進行比較，若為逆序則將兩個記錄進行位置的交換，否則保持原來順序；②將第n-1個記錄的關(guān)鍵字與將第n-2個記錄的關(guān)鍵字進行比較；③重復(fù)上述排序過程，直到全部關(guān)鍵字均比較一遍；④上面三步的比較交換過程稱為第一趟排序，其結(jié)果是使關(guān)鍵字最小的記錄被交換到了第1個記錄的位置，完成一趟排序；⑤第二趟排序從第n個記錄到第2個記錄進行同樣的操作，結(jié)果是使關(guān)鍵字次小的記錄被交換到了第2個記錄的位置；依次類推，第i趟排序是從第n個記錄到第i個記錄依次比較交換。5.4算法(2)冒泡排序main(){inta[11],i,j,t;printf(“input10numbers:\n”);for(i=1;i<11;i++)scanf(“%d”,&a[i]);printf(“\n”);for(j=1;j<=9;j++)for(i=1;i<=10-j;i++)if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;}printf(“%Thesortednumbers:\n”);for(i=1;i<11;i++)printf(“%d”,a[i]);}給數(shù)組a提供初值a[i]與a[i+1]交換輸出a數(shù)組5.5軟件工程簡介5.5.1軟件工程提出

早期,在軟件開發(fā)過程中出現(xiàn)了許多嚴重阻礙軟件發(fā)展的問題，主要表現(xiàn)在以下幾個方面：①軟件開發(fā)無計劃性。②軟件開發(fā)過程無規(guī)范。③軟件產(chǎn)品無評測手段。1990年電氣電子工程師協(xié)會(IEEE)給出了軟件工程的一個定義：“軟件工程是把系統(tǒng)化的、規(guī)范的、可度量的方法