第一篇：《算法分析與設計》實驗指導書-

計算機科學與技術學院

算法分析與設計

實驗指導書

于洪 編寫 2011年8月

目 錄

實驗一實驗二實驗三實驗四附錄1 附錄2 排序問題求解…………………………..…..………3 背包問題求解…………………………..…………..5 最短路徑問題求解………………..………………..8 N-皇后問題求解…………………………………..10關于文件的操作……………………………….….12 關于如何統(tǒng)計運算時間…………………………..13

實驗一

排序問題求解

實驗目的

1）以排序（分類）問題為例，掌握分治法的基本設計策略。2）熟練掌握一般插入排序算法的實現(xiàn)； 3）熟練掌握快速排序算法的實現(xiàn)； 4)理解常見的算法經(jīng)驗分析方法； 實驗環(huán)境

計算機、C語言程序設計環(huán)境 實驗學時

2學時，必做實驗。實驗內(nèi)容與步驟 1.生成實驗數(shù)據(jù).要求：編寫一個函數(shù)datagenetare，生成2000個在區(qū)間[1,10000]上的隨機整數(shù)，并將這些數(shù)輸出到外部文件data.txt中。這些數(shù)作為后面算法的實驗數(shù)據(jù)。2.實現(xiàn)直接插入排序算法.要求：實現(xiàn)insertionsort算法。

算法的輸入是data.txt；

輸出記錄為文件：resultsIS.txt；同時記錄運行時間為TimeIS。直接插入算法思想：

Procedure insertionsort(A,n)

A(0)=-?

for j=2 to n do item=A(j);i=j-1 while item

repeat End insertionsort 3.實現(xiàn)快速排序算法.要求：實現(xiàn)QuickSort 算法。

算法的輸入是data.txt；

輸出記錄為文件：resultsQS.txt；同時記錄運行時間為TimeQS。

快速排序算法思想： Procedure QuickSort（p,q）

integer p,q；global n,A(1:n)

if p< q then

j ← q+1

call Partition(p, j)

call QuickSort(p, j-1)

call QuickSort(j+1, q)

end if end QuickSort

實驗報告：

實驗報告應包括以下內(nèi)容：

用A(m)劃分集合A的函數(shù)： Procedure partition(m,p)

integer m,p, I;global A(m:p-1)v=A(m);I=m Loop

loop I=I+1 until A(I)>=v repeat loop p=p-1 until A(p)<=v repeat if I

then call interchange(A(i), A(p))

Else exit Endif Repeat

A(m)=A(p);A(p)=v End partition（1）題目；

（2）2個算法的基本思想描述；（3）算法理論分析（參考教材）；

（4）程序流程圖；

（5）給出data.txt、resultsIS.txt、resultsQS.txt三個文件任選其一的清單；

TimeIS、TimeQS的記錄結(jié)果；

（6）實驗分析；以表或者圖的形式給出這2個算法的經(jīng)驗對比分析結(jié)果；并和理論分析結(jié)論進行對比。

（7）說明本次調(diào)試實驗的心得體會、經(jīng)驗等。如果程序未通過，應分析其原因。

實驗二

背包問題求解

實驗目的

1）以背包問題為例，掌握貪心法的基本設計策略。

2）熟練掌握各種貪心策略情況下的背包問題的算法并實現(xiàn)；其中：量度標準分別?。盒б嬖隽縋、物品重量w、P/w比值；

3)分析實驗結(jié)果來驗證理解貪心法中目標函數(shù)設計的重要性。

實驗環(huán)境

計算機、C語言程序設計環(huán)境

實驗學時

2學時，必做實驗。

實驗內(nèi)容與步驟

1.理解需要求解背包問題.（1）背包問題的描述：已知有n種物品和一個可容納M重量的背包，每種物品i的重量為益，這里，0?xi?1wi。假定將物品i的一部分

xi放入背包就會得到

pixi的效，pi?0。顯然，由于背包容量是M，因此，要求所有選中要裝入背包的物品總重量不得超過M.。如果這n件物品的總重量不超過M，則把所有物品裝入背包自然獲得最大效益?，F(xiàn)需解決的問題是，在這些物品重量的和大于M的情況下，該如何裝包，使得得到更大的效益值。由以上敘述，可將這個問題形式表述如下：

極 大 化目標函數(shù)

約束條件

?1?i?npixi

?w1?i?nixi?M

0?xi?1,pi?0,wi?0,1?i?n（2）用貪心策略求解背包問題

首先需確定最優(yōu)的量度標準。這里考慮三種策略： 策略1：按物品價值p降序裝包，策略2：按物品重w升序裝包 策略3：按物品價值與重量比值p/w的降序裝包

（3）分別以上面三種策略分別求以下情況背包問題的解： n=7，M=15，（p1,?,p7）=（10，5，15，7，6，18，3）（w1,?,w7）=（2，3，5，7，1，4，1）。以策略3為例的背包問題的貪心算法描述：

procedure GREEDY-KNAPSACK(P,W,M,X,n)//P（1：n）和W（1：n）分別含有按P（i）/W（i）≥P（i+1）/ W（i+1）排序的n件物品的效益值和重量。M是背包的容量，而X（1：n）是解向量。//

real P(1：n)，W（1：n）,X（1：n），M，cu；

integer i，n;X?0

//將解向量初始化為零 cu?M //cu是背包剩余容量 for i?1 to n do

if W(i)>cu then exit endif

X(i)?1

cu?cu-W(i)repeat if i≤n then X(i)?cu/W(i)endif end GREEDY-KNAPSACK 2.以策略1作為量度標準求解要求問題，記錄解向量為X1、目標函數(shù)的值fp1（即最后裝好包后背包的效益值

?1?i?n、背包的重量fw1； pixi）3.以策略2作為量度標準求解要求問題，記錄解向量為X21、目標函數(shù)的值fp2（即最后裝好包后背包的效益值

?1?i?n、背包的重量fw2；

pixi）4.以策略3作為量度標準求解要求問題，記錄解向量為X3、目標函數(shù)的值fp3即最后裝好包后背包的效益值實驗報告：

實驗報告應包括以下內(nèi)容：

?1?i?n、背包的重量fw3；

pixi）（1）題目；

（2）算法的基本思想描述；（3）程序流程圖；

（4）給出3個程序任意之一的程序清單；

（5）實驗分析；通過實驗結(jié)果對比分析說明哪種策略好。

（6）說明本次調(diào)試實驗的心得體會、經(jīng)驗等。如果程序未通過，應分析其原因。

Tips：

1.解向量的表示。需要注意：因為算法中涉及到排序，如何保證各種物品的原始命名（如果以第幾種，即序號，來命名物品）關系需要考慮。

#define MAX 200 typedef struct Solution //定義的解向量

{

int x[MAX];表示該號物品放了多少在背包里，這里0?xi?

1int order[MAX];表示物品的序號，相當于其名字

}Solution;Solution X;所以，初始化時，為： for(i=0;i

{

X.order[i]=i;

X.x[i]=0;

}

2.主要函數(shù)：

void GreedyKnapsack(float profit[],float weight[],float x[],int m, int n){

float cu;

int i;

cu=float(m);

for(i=0;i

{

x[i]=0;

}

for(i=0;i

{

if(weight[i]>cu)

break;

x[i]=1;

cu=cu-weight[i];

}

if(i

{

x[i]=cu/weight[i];

} } 實驗三

最短路徑問題求解

實驗目的：

1）以最短路徑問題為例，掌握動態(tài)規(guī)劃的基本設計策略； 2）掌握dijkstra貪心法求解最短路徑問題并實現(xiàn)；

3）掌握動態(tài)規(guī)劃方法Floyd算法求解最短路徑問題并實現(xiàn)； 3）分析實驗結(jié)果。實驗環(huán)境

計算機、C語言程序設計環(huán)境 實驗學時

2學時，必做實驗。實驗內(nèi)容與步驟

1.以下圖作為輸入，利用dijkstra貪心法獲取由結(jié)點1到其余結(jié)點最短路徑長度，輸出保存到外部文件dijkstra－output1.txt 3 4 5 2 1 2.然后改寫你的程序，求得所有各點之間的最短距離;輸出保存到文件dijkstra－output2.txt.3.以上圖作為輸入，利用Floyd算法求得所有各點直接的最短距離;輸出保存到文件floyd－output1.txt.實驗報告

實驗報告應包括以下內(nèi)容：

（1）題目；

（2）寫出算法設計思想；

（3）程序清單；（4）運行的結(jié)果；

（5）對運行情況所作的分析以及本次調(diào)試程序所取的經(jīng)驗。如果程序未通過，應分析其原因。

Tips: 主要函數(shù)

void dijkstra::algorithm()//算法函數(shù) { initialize();int count=0;int i;int u;while(count

u=minimum();

set[++count]=u;

mark[u]=1;

for(i=1;i<=num_of_vertices;i++)

{

if(graph[u][i]>0)

{

if(mark[i]!=1)

{

if(pathestimate[i]>pathestimate[u]+graph[u][i])

{

pathestimate[i]=pathestimate[u]+graph[u][i];

predecessor[i]=u;

}

}

}} }}

//-------------float graph[maxsize][maxsize];//成本矩陣，鄰接矩陣 //floyd algorithm

for(k = 0;k < n;k ++)

{

// graph[i][j] = min {graph[i][j]}, graph[i][k] + graph[k][j]

for(i = 0;i < n;i ++)

//每次找到最優(yōu)的路徑代替原來的路徑

for(j = 0;j < n;j ++)

if(graph[i][j] > graph[i][k] + graph[k][j])//狀態(tài)轉(zhuǎn)換條件

{

graph[i][j] = graph[i][k] + graph[k][j];//狀態(tài)轉(zhuǎn)換方程

}

}

實驗四：N-皇后問題求解

實驗目的：

1）以Q-皇后問題為例，掌握回溯法的基本設計策略。2）掌握回溯法解決Q-皇后問題的算法并實現(xiàn)； 3）分析實驗結(jié)果。

實驗環(huán)境 計算機、C語言程序設計環(huán)境

實驗學時 2學時，必做實驗。

實驗內(nèi)容與步驟

1.用回溯法求解N-Queen，參考教材算法思想，并實現(xiàn)你的算法。要求：用鍵盤輸入N；輸出此時解的個數(shù)，并統(tǒng)計運算時間。2.給出N=4,5,6時，N-Queen解的個數(shù)。

3.嘗試增大N，觀察運行情況；并理解該算法的時間復雜度。實驗報告

實驗報告應包括以下內(nèi)容：

（1）題目；

（2）寫出算法設計思想；

（3）運行的結(jié)果；

（4）對運行情況所作的分析以及本次調(diào)試程序所取的經(jīng)驗。（5）如果程序未通過，應分析其原因。

Tips: 主要函數(shù)等

while(k>0)//對所有行執(zhí)行以下語句

{

X[k] = X[k]+1;//移到下一列

while(X[k]<=n &&!PLACE(k))

{

X[k] = X[k]+1;//移到下一列，再判斷

}

if(X[k] <= n)//找到一個位置

{

if(k==n)//一個完整的解

{

//print

printf(“the soution is:n”);

for(t=1;t<=n;t++)

printf(“%3d”,X[t]);

printf(“n”);

count +=1;

}

else

{k=k+1;X[k]=0;} //轉(zhuǎn)向下一行

}

else

k=k-1;//回溯

}

printf(“n the number of the solutions is %d n”, count);

bool PLACE(int k){ i=1;while(i

if(X[i]==X[k] || abs(X[i]-X[k])==abs(i-k))

return false;

i=i+1;} return true;}

附錄1關于文件的操作

以背包問題為例：

1，例如外部文件為knapsack-input.txt：

2, 讀入文件的操作： FILE* fp;

/* Open for read(will fail if file “knapsack-input.txt” does not exist)*/

if((fp = fopen(“knapsack-input.txt”, “r”))== NULL)

printf(“The file 'knapsack-input.txt' was not openedn”);

else

printf(“The file 'knapsack-input.txt' was openedn”);

//讀輸入文件，寫n,M,p[MAX],w[MAX] fscanf(fp,“n=%dn”,&n);

fscanf(fp,“M=%dn”,&M);

for(i=0;i

for(i=0;i

fscanf(fp,“%f”,&weight[i]);fscanf(fp,“n”);

/* Close stream */

if(fclose(fp))

printf(“The file 'knapsack-input.txt' was not closedn”);附錄2關于如何統(tǒng)計運算時間

#include “time.h” …….//----start time-----設置計時開始

double duration;

clock_t finish, start;start = clock();

……

//----finish time-----設置計時結(jié)束

finish = clock();

duration =(double)(finish-start)/ CLOCKS_PER_SEC;

printf(“nThe CPU time is %2.6f seconds:n”, duration);

// 統(tǒng)計時間duration

第二篇：算法設計與分析 實驗指導書1

實驗1 遞歸與分治

一、實驗目的：

利用C/C++/JAVA等程序設計語言，實現(xiàn)本章節(jié)中分治算法、遞歸，漢諾塔問題/二分搜索算法/合并排序/快速排序等經(jīng)典算法。通過本實驗章節(jié)掌握遞歸、分治算法的設計思想及實現(xiàn)技巧，加深對課程知識的理解。

二、實驗學時：2

三、實驗任務：

利用高級程序設計語言，編程實現(xiàn)以下問題： 1）遞歸：排列問題，漢諾塔問題；

2）分治：遞歸實現(xiàn)的合并排序及非遞歸的自然合并排序；

四、實驗要求

1，設計過程

理解課本中源代碼或偽代碼的思想，結(jié)合流程圖等工具描述實驗任務的設計過程，并獨自完成代碼編寫、調(diào)試及測試過程。2，代碼及注釋

提交包含完整源代碼及關鍵代碼注釋的實驗報告。3，運行效果圖及測試數(shù)據(jù)

實驗報告中應有能體現(xiàn)源代碼正確編譯、運行的實驗運行效果圖及多組測試數(shù)據(jù)集。

4，心得體會

將實驗過程中所遇到的問題以及解決問題的方式、方法以及調(diào)試過程加以概括，并總結(jié)該實驗過程中的收獲。

第三篇：算法與數(shù)據(jù)結(jié)構(gòu)實驗指導書

北 京 郵 電 大 學

計 算 機 科 學 與 技 術 學 院

算 法 與 數(shù) 據(jù) 結(jié) 構(gòu)

實 驗 指 導 書

楊俊、徐塞虹、漆濤 編著

2006年9月 算法與數(shù)據(jù)結(jié)構(gòu) 實驗指導書

目錄

實驗要求....................................................................................................................................3 試驗

一、約瑟夫環(huán)..............................................................................…………………..……4 試驗

二、長整數(shù)四則運算運算………………………………………………………………4 實驗三、八皇后.....................................……..........................................................................5 實驗

四、騎士遍歷......................................……………………..............................................5 實驗

五、桌面計算器...............................……………..............................................................6 實驗

六、平衡排序二叉樹....................…...…….....................................................................6 試驗

七、多重集合的實現(xiàn)……......................................………………………………………7 試驗

八、圖論………………………………………………………………………….……..8 實驗

八、內(nèi)部排序性能的比較..........………………….............................................................8 教材及主要參考文獻………………………………………………………………………………..9 2 北京郵電大學 計算機科學與技術學院 算法與數(shù)據(jù)結(jié)構(gòu) 實驗指導書

實驗要求

一、本課程在講課期間需要做上機實驗，目的之一是檢查學生對所學算法的掌握和理解程度；其次是鍛煉學生的團隊合作精神。

二、成績：

1、編碼：占整個實驗成績的50%；

2、測試：占整個實驗成績的20%；

3、文檔：占整個實驗成績的30%。

三、按時提交上機文檔，實驗文檔包含以下各項：

1、問題描述：實驗題目、內(nèi)容和要求；

2、算法思路：實驗小組對問題的解決方法的文字描述；

3、算法描述：用類算法語言等對算法進行描述；

4、源程序及驅(qū)動程序：上機實驗編制的代碼源程序及程序運行環(huán)境；

5、測試數(shù)據(jù)：對算法的測試用例；

6、結(jié)果分析和結(jié)論：對算法及測試結(jié)果的分析及結(jié)論；

7、心得體會：通過實驗獲得的心得體會；

8、分工及簽名：最后是小組成員的分工及簽名。

北京郵電大學 計算機科學與技術學院-1-算法與數(shù)據(jù)結(jié)構(gòu) 實驗指導書

實驗

一、約瑟夫環(huán)

一、實驗類別：設計型實驗。

二、問題描述：約瑟夫環(huán)問題是：n個人p0,p1,…pn 圍坐成一個圓環(huán)。每個人pk持有一個秘密的數(shù)字ck。0 < ck <= m。開始時隨機選取一個數(shù) c = c0。每個人從p0 開始從1開始報數(shù)。報到數(shù)c 的人出對。然后以出隊的人的秘密數(shù)字作為新的c 值。從出隊者的下一個人順時針從1 開始再報數(shù)。直到所有的人全部出隊。

三、實驗目的：檢查學生對各種線性表的實現(xiàn)的掌握程度。

四、實驗學時：2小時

五、實驗組人數(shù)：1人。

六、實驗設備環(huán)境：計算機。

七、實驗原理及要點（知識點）：各種隊列的實現(xiàn)。

八、實驗內(nèi)容和要求：至少用3種以上的線性表來完成此試驗。可以在帶頭節(jié)點的和不帶頭節(jié)點的線性表、循環(huán)的和非循環(huán)線性表、動態(tài)鏈表和靜態(tài)鏈表以及向量（數(shù)組）之間選擇三種。從空表開始，為每個人生成一個隨機數(shù)。然后將此人加入到線性表之中。

九、可研究與探索的問題：給出各種實現(xiàn)的優(yōu)缺點比較。

十、驗收及實驗報告要求：現(xiàn)場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。給出各種線性表實現(xiàn)的優(yōu)缺點分析。

實驗

二、長整數(shù)四則運算

一、實驗類別：驗證實驗。

二、問題描述：計算機CPU本身可以做32位或者64位的整數(shù)四則運算。本試驗要求對任意大小的整數(shù)實現(xiàn)其四則運算。將一個整數(shù)N表示為

N = ±(d0 + d1*B + d2*B2 + ….+ bk*Bk)

其中 1< B <= 256 為一個取定的整數(shù)。0 <= dk < B。用線性表存儲{bk}。給出整數(shù)的四則運算程序。

三、實驗目的：對具體的問題選擇適當?shù)木€性表實現(xiàn)。

四、實驗學時：2小時

五、實驗組人數(shù)：3人。

六、實驗設備環(huán)境：計算機。

七、實驗原理及要點（知識點）：各種隊列的實現(xiàn)。

八、實驗內(nèi)容和要求：至少用2種以上的線性表來完成此試驗。比較不同線性表實現(xiàn)的速度。

九、可研究與探索的問題：1）對具體問題選擇合適的線性表實現(xiàn)。2）B 的選取問題?？?否選擇更大的基B。B的選擇所應考慮的因素。

十、驗收及實驗報告要求：現(xiàn)場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。能夠得出用向量（數(shù)組）實現(xiàn)的線性表速度最快。

實驗三、八皇后問題

一、實驗類別：設計型實驗。

二、問題描述：在n*n 的國際象棋棋盤上放置n個皇后，使每個皇后不受其他皇后的攻擊。

三、實驗目的：檢查學生對堆棧和遞歸程序掌握程度。

四、實驗學時：2小時

五、實驗組人數(shù)：1人。

六、實驗設備環(huán)境：計算機。

七、實驗原理及要點（知識點）：遞歸程序與堆棧

八、實驗內(nèi)容和要求： 分別用遞歸和堆棧完成此試驗。統(tǒng)計程序運行時間與問題規(guī)模n 的關系。

九、可研究與探索的問題：問題的復雜度。當n 比較大時，討論提高程序運行的方法。

十、驗收及實驗報告要求：現(xiàn)場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。找出程序運行速度的瓶頸。

實驗

四、騎士遍歷

一、實驗類別：設計型實驗。

二、問題描述：在國際象棋n*n的棋盤中，一匹馬從棋盤中任意一格出發(fā)，要求用n2-1步走完所有的n2個格子。每個格子走且只走過一次。應如何走？ 試給出算法實現(xiàn)。

三、實驗目的：檢查學生對堆棧與回溯算法的掌握。

四、實驗學時：2小時

五、實驗組人數(shù)：3人。

六、實驗設備環(huán)境：計算機。

七、實驗原理及要點（知識點）：堆棧與回溯

八、實驗內(nèi)容和要求：用堆棧完成此試驗。統(tǒng)計程序運行時間與問題規(guī)模n 的關系。

九、可研究與探索的問題：怎樣枚舉所有馬下一步可走的位置。選擇下一步所走位置的策略。注意由于這個程序非常耗時，在初期程序調(diào)試時應取較小的n。

十、驗收及實驗報告要求：現(xiàn)場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。找出程序運行速度的瓶頸。給出不同選擇策略的程序運行 速度的比較結(jié)果。

實驗

五、桌面計算器（表達式求值）

一、實驗類別：設計型實驗。

二、問題描述：模仿Unix系統(tǒng)下的dc命令。輸入表達式字符串，按回車鍵后給出表達式的值。操作數(shù)為實數(shù)。

1）操作符有 “+”、“-”、“*”、“/”、“^”（乘方）

2）還可以有臨時變量。用法如 pi = 3.1415926，r = 3, r*pi^2 3）還可以有事先定義的函數(shù)如：“sin()”（正弦）、“cos()”（余弦）、“l(fā)og()”（對數(shù)）、“l(fā)n()”（自然對數(shù)）等函數(shù)。

三、實驗目的：檢查學生用堆棧解決實際問題。為本課程后續(xù)的內(nèi)容提供伏筆。也為后繼的課程如編譯原理預習。

四、實驗學時：2小時

五、實驗組人數(shù)：3人。

六、實驗設備環(huán)境：計算機。

七、實驗原理及要點（知識點）：堆棧，線性表，命令行參數(shù)的處理。

八、實驗內(nèi)容和要求：學生應至少應實現(xiàn)處理五個運算符：“+”、“-”、“*”、“/”、“^”（乘方）。可以用一個線性表來存儲臨時變量。另一個線性表來存儲預定義的函數(shù)名。

九、可研究與探索的問題：查找臨時變量名的不同方法。如哈希表，二叉樹。

十、驗收及實驗報告要求：現(xiàn)場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。

實驗

六、平衡排序二叉樹

一、實驗類別：設計型實驗。

二、問題描述：隨機生成一組整數(shù)p0,p1,…pn－１。將這組整數(shù)按生成的次序插入到一個平衡排序二叉樹中。然后將p0,p1,…pn－１隨機重新排列為q0,q1,…qn－１。再按照次次序?qū)⑦@些整數(shù)從生成的平衡排序二叉樹刪除。

三、實驗目的：平衡排序二叉樹的插入和刪除。

四、實驗學時：2小時

五、實驗組人數(shù)：3人。

六、實驗設備環(huán)境：計算機。

七、實驗原理及要點（知識點）：平衡排序二叉樹的插入和刪除中的旋轉(zhuǎn)。

八、實驗內(nèi)容和要求：統(tǒng)計在平衡排序二叉樹的插入和刪除過程中各種旋轉(zhuǎn)的出現(xiàn)次數(shù)。

九、可研究與探索的問題：研究平衡排序二叉樹與一般的排序二叉樹在插入和刪除方面的性能比較。

十、驗收及實驗報告要求：現(xiàn)場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。給出在均勻的隨機分布下，平衡排序二叉樹與一般排序二叉樹的性能比較。

實驗

七、多重集合的實現(xiàn)

一、實驗類別：設計型實驗。

二、問題描述：實現(xiàn)數(shù)學上多重集合。所謂的多重集合類似于集合，但是一件東西可以放置多個副本。就如一個菜籃子里面可以放兩個蘋果。

三、實驗目的：查找結(jié)構(gòu)的各種實現(xiàn)。

四、實驗學時：2小時

五、實驗組人數(shù)：3人。

六、實驗設備環(huán)境：計算機。

七、實驗原理及要點（知識點）：平衡排序二叉樹的插入和刪除、遍歷，查找。哈希查找結(jié)構(gòu)。

八、實驗內(nèi)容和要求： 假設集合中包含的元素是可以排序的。將多重集合封裝成一個類。具體的實現(xiàn)可以是中序線索化的平衡排序二叉樹，或者帶父節(jié)點指針的平衡排序二叉樹。多重集合的界面如下：

template //假設類型 T 是可以排序的 class Multi_set

{

Multi_set(void);//構(gòu)造函數(shù)，初始化為空集合~Multi_set(void);//析構(gòu)函數(shù)

Multi_set& operator=(Multi_set const a);//重載運算符=

bool contains(T const& v)const;//如果集合包含v 則返回true，否則返回false

Multi_set& operator+=(Multi_set const&a);//將集合a 并到自身中。

Multi_set& operator-=(Multi_set const& a);//自身減去集合a

Multi_set& operator-=(T const& a);//自身減去一個元素a

};//~class Multi_set

//返回集合a,b的并

template Multi_set Mult_set:: operator+(Multi_set const& a，Multi_set const& b);

//返回集合a,b的差

template Multi_set Mult_set:: operator-(Multi_set const& a，Multi_set const& b);

//返回 a –{v}

template

Multi_set Multi_set::operator-(Multi_set const& a,T const& v);

九、可研究與探索的問題：哈希函數(shù)的選取。比較哈希與平衡排序二叉樹的優(yōu)缺點、性能和速度。

十、驗收及實驗報告要求：現(xiàn)場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。給出平衡排序二叉樹實現(xiàn)的多重集合和用哈希實現(xiàn)的多重集合的性能比較。

實驗

八、圖論

一、實驗類別：設計型實驗。

二、問題描述：實現(xiàn)圖論中的各種算法。

1）最小代價生成樹的Krscal 算法和Prim算法。2）單源點的最短路徑的Dijstra 算法。3）深度優(yōu)先遍歷與廣度優(yōu)先遍歷。4）拓撲排序

5）求所有節(jié)點之間的最短路徑Floyd算法

（在這五個小題中只要選作一個即可。）

三、實驗目的：學習根據(jù)不同的運算來選取不同的存儲結(jié)構(gòu)。

四、實驗學時：2小時

五、實驗組人數(shù)：3人。

六、實驗設備環(huán)境：計算機。

七、實驗原理及要點（知識點）：圖論中的各種算法及其復雜度。根據(jù)不同的操作來決定圖的存儲結(jié)構(gòu)。

八、實驗內(nèi)容和要求：至少實現(xiàn)上面五個小題目中的一個。從文件中讀入一個圖的信息。

九、可研究與探索的問題：高級數(shù)據(jù)結(jié)構(gòu)如堆、并查集在圖論算法中的應用。

十、驗收及實驗報告要求：現(xiàn)場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。給出在均勻的隨機分布下，平衡排序二叉樹與一般排序二叉樹的性能比較。

實驗

九、內(nèi)部排序性能的比較

一、實驗類別：設計型實驗。

二、問題描述：隨機生成一組整數(shù)p0,p1,…pn－１。對這組數(shù)據(jù)進行排序。

三、實驗目的：比較不同排序算法的性能。

四、實驗學時：2小時

五、實驗組人數(shù)：3人。

六、實驗設備環(huán)境：計算機。

七、實驗原理及要點（知識點）：各種內(nèi)部排序算法。

八、實驗內(nèi)容和要求： 1）實現(xiàn)插入排序，選擇排序，希爾排序，堆排序以及快速排序。2）快速排序的多種版本。3）對單鏈表實現(xiàn)歸并排序。4）基數(shù)排序。

5）對小型問題（n = 10）、中型問題（n = 1000）以及大型問題（n = 1百萬）分別統(tǒng)計不同排序算法的鍵值比較次數(shù)、鍵值移動次數(shù)以及程序運行時間。

26）排序算法的時間復雜度可以有O(n)和 O(n log n)。對相同復雜度的算法，給出他們運行時間與時間復雜度的比值。

九、可研究與探索的問題：研究快速排序算法的不同改進方法。自省排序算法。只需要移動而不需要交換的快速排序方法。

十、驗收及實驗報告要求：現(xiàn)場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。給出在均勻的隨機分布下，對大中小問題的最快的排序算法。

教材及主要參考文獻

[1] 嚴蔚敏、吳偉民，數(shù)據(jù)結(jié)構(gòu)習題集，清華大學出版社，1999年

[2] John R.Hubbard, Data Structures with C++, China Machine Press, 2002.[3] Mark Allen Weiss, Data Structures and Problem Solving Using C++, 2ed, 清華大學出版社。2004年。[4] Robert Sedgewick，Algorithms in C Part 1 – 4: Fundamentals, Data Structures, Sorting, rdSearching, 3, 中國電力出版社，2003年。

[5] 嚴蔚敏、吳偉民，數(shù)據(jù)結(jié)構(gòu)(C語言版)，清華大學出版社，2006年

第四篇：系統(tǒng)分析與設計實驗指導書

系統(tǒng)分析與設計實驗指導書

前言

信息系統(tǒng)分析與設計是一門研究管理信息系統(tǒng)開發(fā)與維護的普遍原理和技術的工程學科。隨著信息系統(tǒng)概念及應用的發(fā)展，成功的經(jīng)驗與失敗的教訓使人們認識到：信息系統(tǒng)建設過程是復雜的社會過程，系統(tǒng)觀點是系統(tǒng)建設的重要思想武器，科學的開發(fā)過程和規(guī)范的項目管理要比開發(fā)技術本身更為重要，嚴格遵循系統(tǒng)分析與設計的方法論可以大大提高信息系統(tǒng)開發(fā)的成功率，顯著減少系統(tǒng)開發(fā)和維護中的問題。

按該課程的特點，實驗內(nèi)容包括軟件開發(fā)的兩大方法學的專題訓練，即結(jié)構(gòu)化（生命周期學）的方法學和面向?qū)ο蟮姆椒▽W，通過對一個具體的信息系統(tǒng)項目，要求學生利用結(jié)構(gòu)化軟件開發(fā)技術或面向?qū)ο蟮能浖_發(fā)技術完成對該項目的開發(fā)。因此設置四個實驗項目，從項目開發(fā)的準備工作，系統(tǒng)分析過程，系統(tǒng)設計過程，到文檔的整理和完善，覆蓋軟件開發(fā)的主要過程，此外又引入我國國家《計算機開發(fā)規(guī)范》，以規(guī)范技術文檔的書寫標準，提高實驗教學質(zhì)量。

通過實驗訓練，達到如下目的：

使學生進一步了解和掌握系統(tǒng)分析與設計原理，提高對實際項目的分析和設計能力，通過實驗課程，熟悉和基本掌握軟件開發(fā)方法學、軟件開發(fā)的過程，文檔資料的編寫格式及規(guī)范，全面領會和貫通所學習的理論知識，從而培養(yǎng)學生綜合運用所學課程知識，分析解決問題的能力，培養(yǎng)學生理論聯(lián)系實際作風，實事求是，嚴肅認真的科學態(tài)度和良好的工作作風，為今后從事科學研究工作打下基礎。

目

錄

實驗一：項目開發(fā)的準備工作--------------------1 實驗二：系統(tǒng)分析過程----------------------------1 實驗三：系統(tǒng)設計過程----------------------------2 實驗四：系統(tǒng)文檔整理----------------------------3

附錄一：--------------5 附錄二：--------------6 附錄三：--------------11

實驗一：項目開發(fā)的準備工作

實驗學時：2

實驗類型：驗證性

一、目的與任務

目的：確定課題，組織組員，合理分工，熟悉軟件開發(fā)環(huán)境，培養(yǎng)團隊精神。

任務：學習軟件開發(fā)小組的組織和管理，合理分工，將項目開發(fā)各階段的任務明確，并熟悉相應的軟件開發(fā)環(huán)境。

二、內(nèi)容、要求與安排方式

1、實驗內(nèi)容與要求：

根據(jù)各組選擇的課題，實行項目經(jīng)理制，各組推薦一名組長，統(tǒng)一管理整個項目的實施過程，并和理調(diào)整資源和負責項目全局；根據(jù)項目的難易合理分配組員的任務，對問題達成一直的看法；針對項目的實施，熟悉相應的軟件開發(fā)工具的使用環(huán)境。

2、實驗安排方式：

本實驗為開放實驗，各組可同時進行實驗，每組2—3人。3．準備參考資料和閱讀相關的國家有關軟件開發(fā)的標準文檔。

三、思考題

1． 2． 3． 項目開發(fā)首先要做的事是什么？

你認為該軟件應具備的最重要的特性是什么。你認為怎樣分工是最合理的？

實驗二：系統(tǒng)分析過程

實驗學時：4

實驗類型：驗證性

一、目的與任務

目的：確定項目的可實施性，在此基礎上完成系統(tǒng)的邏輯功能模型的建立。任務：采用不同的軟件開發(fā)技術，完成對項目的分析過程，給出系統(tǒng)的邏 1 輯功能模型，數(shù)據(jù)字典以及規(guī)格說明書。

二、內(nèi)容、要求與安排方式

1、實驗內(nèi)容與要求：（1）結(jié)構(gòu)化分析

明白項目的業(yè)務流程圖，繪制數(shù)據(jù)流程圖，編寫數(shù)據(jù)字典，數(shù)據(jù)加工處理的描述，實體關系圖（ER圖），需求規(guī)格說明書。

（2）面向?qū)ο蠓治?/p>

弄清信息系統(tǒng)的業(yè)務流程，繪制系統(tǒng)的用例圖，書寫用例規(guī)格說明；初步繪制系統(tǒng)的靜態(tài)結(jié)構(gòu)——類圖；初步繪制系統(tǒng)動態(tài)行為——順序圖、協(xié)作圖、活動圖、狀態(tài)圖。最后利用Word寫出系統(tǒng)的需求規(guī)格說明書。

2、實驗安排方式：

本實驗為開放實驗，各組可同時進行實驗，每組2—3人。

三、思考題

1． 2． 3． 4． 需求分析在軟件開發(fā)中真的有那么重要嗎？

分析系統(tǒng)流程圖，流程圖和數(shù)據(jù)流圖的區(qū)別和各自的特點。怎樣寫合乎規(guī)范的數(shù)據(jù)流圖和數(shù)據(jù)詞典？ 怎樣組織對該工作的評審？

實驗三：系統(tǒng)設計過程

實驗學時：4

實驗類型：技能性

一、目的與任務

目的：在實驗二基礎上完成系統(tǒng)的體系結(jié)構(gòu)的建立和系統(tǒng)詳細設計，并給出相應的規(guī)格說明書。

任務：認真分析實驗二的結(jié)果，給出系統(tǒng)合理的體系結(jié)構(gòu)，描繪系統(tǒng)結(jié)構(gòu)圖，并合理劃分系統(tǒng)的各組成模塊，最后給出系統(tǒng)的各部分設計規(guī)格說明書。

二、內(nèi)容、要求與安排方式

1、實驗內(nèi)容與要求：（1）結(jié)構(gòu)化設計

軟件體系結(jié)構(gòu)圖（HIPO圖或模塊結(jié)構(gòu)圖）設計，模塊處理流程設計，輸出設計（主要指打印輸出設計），存儲文件格式設計（數(shù)據(jù)庫結(jié)構(gòu)設計），輸入設計（主要指數(shù)據(jù)錄入卡設計），代碼設計，系統(tǒng)設計說明書

（2）面向?qū)ο笤O計

設計系統(tǒng)合理的體系結(jié)構(gòu)；在Rational Rose環(huán)境中對實驗二的分析模型進行細化、精化，使之成為計算機能夠?qū)崿F(xiàn)的物理模型。最后利用Word寫出系統(tǒng)的設計規(guī)格說明書。

2、實驗安排方式：

本實驗為開放實驗，各組可同時進行實驗，每組2—3人。

三、思考題

1．系統(tǒng)設計和需求分析的關系是什么？兩者必須先后關聯(lián)嗎？ 2．怎樣描繪系統(tǒng)的體系結(jié)構(gòu)？ 3．怎樣繪制復合規(guī)范的流程圖。4．怎樣組織對設計階段工作的評審？

實驗四：系統(tǒng)文檔整理

實驗學時：2

實驗類型：驗證性

一、目的與任務

目的：系統(tǒng)運行和軟件后期制作。

任務：總結(jié)軟件開發(fā)中的得失，正確書寫軟件說明書和用戶手冊。

二、內(nèi)容、要求與安排方式

1、實驗內(nèi)容與要求：

完善系統(tǒng)所涉及的程序框圖，源程序，模擬運行數(shù)據(jù)，打印報表，軟件使用說明書和用戶手冊等。

2、驗安排方式：

本實驗為開放實驗，各組可同時進行實驗，每組2—3人。

三、思考題

1.怎樣合理選擇軟件開發(fā)的工具？

2．怎樣進行用戶說明手冊和使用手冊的編寫。3．總結(jié)項目實施中的得失。

附錄一：

實驗要求

軟件工程實驗要求學生采用“項目小組”的形式，結(jié)合具體的開發(fā)項目進行設計。具體要求如下：

1． 班級按項目小組進行分組，每組不得超過4人

2． 每個項目小組選出項目負責人或項目經(jīng)理，由項目經(jīng)理召集項目組成員討論、選定開發(fā)項目

3．項目開的每項任務要落實到人且規(guī)定該任務的起止日期和時間 4．每個項目小組可以參照附錄中給定的文檔規(guī)范標準提供項目文檔 5．題目自定或采用附錄二中的題目

6．軟件開發(fā)的方法學自定（結(jié)構(gòu)化或面向?qū)ο蟮姆椒▽W）

附錄一：實驗題目

題目一：“教務管理系統(tǒng)之子系統(tǒng)——學院課程安排”

1． 系統(tǒng)簡介

每個學期的期中，學校教務處向各個學院發(fā)出下各學期的教學計劃，包括課程名稱、課程代碼、課時、班級類別（本科、?？啤⒊扇私逃?、研究生）、班號等；學院教學主管人員根據(jù)教學任務和要求給出各個課程的相關限制（如：任課教師的職稱、上課的班數(shù)、最高和最低周學時數(shù)等）；任課教師自報本人授課計劃，經(jīng)所在教研室協(xié)調(diào)任可，將教學計劃上交學院主管教學計劃的人員，批準后上報學校教務處，最終由教務處給出下個學期全學院教師的教學任務書。

假設上述排課過程全部由人工操作，現(xiàn)要求為上述過程實現(xiàn)計算機自動處理過程。2． 限定條件

（1）每位教師的主講課程門數(shù)不超過2門/學期：講師以下職稱的教師不能承擔學院定主課的主講任務。

（2）學院中層干部的主講課時不能超過4學時/周。

（3）本學期出現(xiàn)嚴重教學事故的教師不能承擔下各學期的主講任務。

（4）本系統(tǒng)的輸入項至少包括：教務處布置的教學計劃，學院教師自報的授課計劃和學院定的有關授課限制條件。

（5）本系統(tǒng)的輸出項至少包括：教務處最終下達全院教師的教學任務書和學院各個班級下各學期的課程表（可以不含上課地點）。

題目二：“學校教材定購系統(tǒng)”

1． 系統(tǒng)簡介

本系統(tǒng)可以細化為兩個子系統(tǒng)：銷售系統(tǒng)和采購系統(tǒng)。

銷售系統(tǒng)的主要工作過程為：首先由教師或?qū)W生提交購書單，經(jīng)教材發(fā)行人員審核是有效購書單后，開發(fā)票、登記并返給教師或?qū)W生領書單，教師或?qū)W生可以到書庫領書。

采購系統(tǒng)的主要工作過程為：若是教材脫銷，則登記缺書，發(fā)缺書單給書庫采購人員；一旦新書入庫后，即發(fā)進書通知給教材發(fā)行人員。

以上功能要求在計算機上實現(xiàn)。2． 技術要求和限制條件

（1）當書庫中的各種書籍數(shù)量發(fā)生變化（包括進書和出書）時，都應修改相關的書庫記錄，如庫存表或進/出庫表。

（2）在實現(xiàn)上述銷售和采購的工作過程時，需考慮有關的合法性驗證。

6（3）系統(tǒng)的外部項至少包括：教師、學生和教材工作人員。

（4）系統(tǒng)的相關數(shù)據(jù)存儲至少包括：購書表、庫存表、缺書登記表、待購教材表、進庫表和出庫表。

題目三：“機票預定系統(tǒng)”

1． 系統(tǒng)簡介

航空公司為給旅客乘機提供方便，需要開發(fā)一個機票預定系統(tǒng)。各個旅行社把預定機票的旅客信息（姓名、性別、工作單位、身份證號碼（護照號碼）、旅行時間、旅行始發(fā)地和目的地，航班艙位要求等）輸入到系統(tǒng)中，系統(tǒng)為旅客安排航班。當旅客交付了預訂金后，系統(tǒng)打印出取票通知和帳單給旅客，旅客在飛機起飛前一天憑取票通知和帳單交款取票，系統(tǒng)核對無誤即打印出機票給旅客。此外航空公司為隨時掌握各個航班飛機的乘載情況，需要定期進行查詢統(tǒng)計，以便適當調(diào)整。2． 技術要求和限制條件

（1）在分析系統(tǒng)功能時要考慮有關證件的合法性驗證（如身份證、取票通知和交款發(fā)票）等。

（2）對于本系統(tǒng)還應補充以下功能：

? 旅客延誤了取票時間的處理 ? 航班取消后的處理 ? 旅客臨時更改航班的處理

（3）系統(tǒng)的外部輸入項至少包括：旅客、旅行社和航空公司。

題目四：“實驗室設備管理系統(tǒng)”

1． 系統(tǒng)簡介

每學年要對實驗室設備使用情況進行統(tǒng)計、更新。其中：（1）對于已徹底損壞的做報廢處理，同時詳細記錄有關信息。

（2）對于由嚴重問題（故障）的要及時修理，并記錄修理日期、設備名、編號、修理廠家、修理費用、責任人等。

（3）對于急需修改但又缺少的設備，需以“申請表”的形式送交上級領導請求批準購買。新設備購入后要立即進行設備登記（包括類別、設備名、編號、型號、規(guī)格、單價、數(shù)量、購置日期、生產(chǎn)廠家、保質(zhì)期和經(jīng)辦人等信息），同時更新申請表的內(nèi)容。

（4）隨時對現(xiàn)有設備及其修理、報廢情況進行統(tǒng)計、查詢，要求能夠按類別和時間段等查詢。

2． 技術要求及限制條件

7（1）所有工作由專門人員負責完成，其他人不得任意使用。

（2）每件設備在做入庫登記時均由系統(tǒng)按類別加自動順序號編號，形成設備號；設備報廢時要及時修改相應的設備記錄，且有領導認可。

（3）本系統(tǒng)的數(shù)據(jù)存儲至少包括：設備記錄、修理記錄、報廢記錄、申請購買記錄。（4）本系統(tǒng)的輸入項至少包括：新設備信息、修理信息、申請購買信息、具體查詢統(tǒng)計要求。

本系統(tǒng)的輸出項至少包括：設備購買申請表、修理/報廢設備資金統(tǒng)計表。

題目五：人事管理系統(tǒng)的設計系統(tǒng)簡介和設計要求：（1）信息要求

本系統(tǒng)應該包含與人事管理相關的信息，如部門信息、職員信息，其中職員信息應該包含職員的基本信息（如職員的編號、姓名、性別等）職員的其他信息如（如：主要社會關系、獎懲情況等）。（2）功能要求

本系統(tǒng)的基本功能要求如下： ? 部門信息維護；

? 職員信息維護（含職員的部門調(diào)整）； ? 職員信息查詢（不確定查詢）； ? 人事信息查詢(如人才結(jié)構(gòu)的統(tǒng)計查詢)? 用戶管理（含用戶權限的設置）

? 輔助功能（如學歷索引表、職稱索引表的維護等）

題目六：工資管理系統(tǒng)的設計

系統(tǒng)簡介和設計要求：（1）信息要求

本系統(tǒng)應該包含與工資管理相關的信息，如部門信息、職員工資信息，其中職員工資信息應該包含與支援工資相關的基本信息（如：職員的編號、姓名、基本工資、各種津貼以及其他應發(fā)工資項目，水電、煤氣等各項扣款，以及公積金、會費等）、職員的其他信息（如工資調(diào)整情況）等。

（2）功能要求

本系統(tǒng)的基本功能要求如下： ? 部門信息維護；

? 職員工資信息維護； ? 顯示打印職員工資表； ? 打印職員工資發(fā)放表； ? 打印部門工資匯總表；

? 用戶管理（含用戶權限的設置）。

題目七：畢業(yè)生管理信息系統(tǒng)

設計要求：（1）信息要求

本系統(tǒng)應該包含與畢業(yè)生管理相關的信息，如畢業(yè)生基本信息、畢業(yè)生就業(yè)信息、其中畢業(yè)生基本信息應該包括：畢業(yè)生的編號、姓名、性別、民族、籍貫、畢業(yè)時間、專業(yè)、政治面貌等信息；畢業(yè)生就業(yè)信息應該包括：畢業(yè)生的編號、就業(yè)時間、工作單位、工作性質(zhì)、職務、地址等。

（2）功能要求

本系統(tǒng)的基本功能要求如下： ? 畢業(yè)生基本信息維護； ? 畢業(yè)生就業(yè)信息維護；

? 畢業(yè)生就業(yè)情況查詢（不確定查詢）； ? 按專業(yè)劃分的就業(yè)情況統(tǒng)計； ? 用戶管理（含用戶權限的設置）。

題目八：建立一個分布式、互動式的遠程教學平臺

為教師教學、學生學習提供比較完整的教學解決方案。其主要功能包括通知發(fā)布、參考資料發(fā)布、電子課件發(fā)布、學生作業(yè)提交、幫助教師批改學生作業(yè)、幫助學生復查批改后的作業(yè)。

題目九：開發(fā)一個基于WEB的網(wǎng)上機票查詢和銷售系統(tǒng)

該系統(tǒng)可以錄入航班和機票信息，用戶可以查詢航班時刻表、查詢機票可用信息和機票折扣信息，用戶可以通過WEB訂票。

題目十：開發(fā)一個基于WEB的網(wǎng)上投稿系統(tǒng)

該系統(tǒng)可以接受作者的電子投稿，以及作者信息（如姓名、單位、通信地址、電話、E-Mail等）注冊，并能供投稿人查詢稿件處理情況，以及在稿件處理后（退稿、錄用、修改后再審等），能自動發(fā)送E-Mail通知投稿人。

題目十一：開發(fā)一個基于Web的BBS系統(tǒng)

包含一般BBS所具有的功能，如用戶注冊、用戶信息管理、發(fā)貼功能、貼子管理、主題詞查詢、用戶信息修改和查詢等。

題目十二：開發(fā)一個基于Web的網(wǎng)上書店

該系統(tǒng)可以分類錄入書籍和相關信息（如名稱、頁數(shù)、出版商、摘要、目錄等），用戶可以注冊、登錄，注冊用戶享受打折服務，所有用戶都可以查詢、瀏覽書籍。注冊用戶可以定購書籍并查詢訂單。

附錄三：

軟件開發(fā)文檔指南 可行性研究報告

可行性研究報告的編寫目的是：說明該軟件開發(fā)項目的實現(xiàn)在技術、經(jīng)濟和社會條件方面的可行性；評述為了合理地達到開發(fā)目標而可能先擇的各種方案；說明論證所選定的方案?？尚行匝芯繄蟾娴木帉憙?nèi)容要求如下：

1.1 引言

1.1.1 編寫目的 1.1.2 背景

1.1.3 定義

1.1.4 參考資料

1.2 可行性研究的前提

1.2.1 要求

1.2.2 目標

1.2.3 條件、假定和限制

1.2.4 進行可行性研究的方法

1.2.5 評價尺度

1.3 對現(xiàn)有系統(tǒng)的分析

1.3.1 數(shù)據(jù)流程和處理流程

1.3.2 工作負荷

1.3.3 費用開支

1.3.4 人員

1.3.5 設備

1.3.6 局限性

1.4 所建議的系統(tǒng)

1.4.1 對所建議系統(tǒng)的說明

1.4.2 數(shù)據(jù)流程各處理流程

1.4.3 改進之處

1.4.4 影響

1.4.4.1 對象設備的影響

1.4.4.2 對軟件的影響

1.4.4.3 對用戶單位機構(gòu)的影響

1.4.4.4 對系統(tǒng)動行的影響

1.4.4.5 對開發(fā)的影響

1.4.4.6 對地點和設施的影響

1.4.4.7 對經(jīng)費開支的影響

1.4.5 局限性

1.4.6 技術條件方面的可行性

1.5 可選擇其他系統(tǒng)方案

1.5.1 可選擇的系統(tǒng)方案1

1.5.2 可選擇的系統(tǒng)方案2

……

1.6 投資及收益分析

1.6.1 支出

1.6.1.1 基本建設投資

1.6.1.2 其他一次性支出

1.6.1.3 非一次性支出

1.6.2 收益

1.6.2.1 一次性收益

1.6.2.2 非一次性收益

1.6.2.3 不可定量的收益

1.6.3 收益/投資比

1.6.4 投資回收周期

1.6.5 敏感性分析

1.7 社會條件方面的可行性

1.7.1 法律方面的可行性

1.7.2 使用方面的可行性

1.8 結(jié)論 2 項目開發(fā)計劃

編制項目開發(fā)計劃的目的是用文件的形式，把對于在開發(fā)過程中各項工作的負責人員、開發(fā)進度所需經(jīng)費預算、所需軟、硬件條件等問題作出安排記載下來，以便根據(jù)本計劃開展和檢查本項目的開發(fā)工作。編制內(nèi)容要求如下：

2.1 引言

2.1.1 編寫目的 2.1.2 背景

2.1.3 定義

2.1.4 參考資料

2.2 項目概述

2.2.1 工作內(nèi)容

2.2.2 主要參加人員

2.2.3 產(chǎn)品及成果

2.2.3.1 程序

2.2.3.2 文件

2.2.3.3 服務

2.2.3.4 非移交產(chǎn)品

2.2.4 驗收標準

2.2.5 完成項目的最遲期限

2.2.6 本計劃的審查者與批準者

2.3 實施總計劃

2.3.1 工作任務的分解

2.3.2 接口人員

2.3.3 進度

2.3.4 預算

2.3.5 關鍵問題

2.4 支持條件

2.4.1 計算機系統(tǒng)支持

2.4.2 需要用戶承擔的工作

2.4.3 需由外單位提供的條件

2.5 專題計劃要點 3 軟件需求說明書

軟件需求說明書的編制是為了使用戶的軟件開發(fā)者雙方對該軟件的起初規(guī)定有一個共同的理解，使之成為整個開發(fā)工作的基礎。編制軟件需求說明書的內(nèi)容要求如下：

3.1 引言

3.1.1 編寫的目的 3.1.2 背景

3.1.3 定義

3.1.1 參考資料

3.2 任務概述

3.2.1 目標

3.2.2 用戶的點

3.2.3 假定與約束

3.3 需求規(guī)定

3.3.1 對功能的規(guī)定

3.3.2 對性能的規(guī)定

3.3.2.1 精度

3.3.2.2 時間特性要求

3.3.2.3 靈活性

3.3.3 輸入輸出要求

3.3.4 數(shù)據(jù)管理能力的要求

3.3.5 故障處理要求

3.3.6 其它的專門的要求

3.4 運行環(huán)境規(guī)定

3.4.1 設備

3.4.2 支持軟件

3.4.3 接口

3.4.4 控制 4 數(shù)據(jù)需求說明書

數(shù)據(jù)要求說明書的編制目的是為了向整個開發(fā)時期提供關于處理數(shù)據(jù)的描述和數(shù)據(jù)采集要求的技術信息。編制數(shù)據(jù)要求說明書的內(nèi)容要求如下：

4.1 引言

4.1.1 編寫目的 4.1.2 背景

4.1.3 定義

4.1.4 參考資料

4.2 數(shù)據(jù)的邏輯描述

4.2.1 靜態(tài)數(shù)據(jù)

4.2.2 動態(tài)輸入數(shù)據(jù)

4.2.3 動態(tài)輸出數(shù)據(jù)

4.2.4 內(nèi)部生成數(shù)據(jù)

4.2.5 數(shù)據(jù)約定

4.3 數(shù)據(jù)的采集

4.3.1 要求和范圍

4.3.2 輸入的承擔者

4.3.3 處理

4.3.4 影響 5 概要設計說明書

概要設計說明書可稱作系統(tǒng)設計說明書，這里說的系統(tǒng)是指程序系統(tǒng)，編制的目的是說 15 明對程序的系統(tǒng)的設計考慮，包括程序系統(tǒng)的基本處理流程、程序系統(tǒng)的組織結(jié)構(gòu)、模塊劃分、功能分配、接口設計、運行設計、數(shù)據(jù)結(jié)構(gòu)設計和出錯處理設計等，為程序的詳細設計提供基礎。編制概要設計說明書的內(nèi)容要求如下：

5.1 引言

5.1.1 編寫目的 5.1.2 背景

5.1.3 定義

5.1.4 參考資料

5.2 總體設計

5.2.1 需求規(guī)定

5.2.2 運行環(huán)境

5.2.3 基本設計概念和處理流程

5.2.4 結(jié)構(gòu)

5.2.5 功能需求與程序的關系

5.2.6 人工處理過程

5.2.7 尚未解決的問題

5.3 接口設計

5.3.1 用戶接口

5.3.2 內(nèi)部接口

5.3.3 外部接口

5.4 運行設計

5.4.1 運行模塊組合 5.4.2 運行控制

5.4.3 運行時間

5.5 系統(tǒng)數(shù)據(jù)結(jié)構(gòu)設計

5.5.1 邏輯結(jié)構(gòu)設計要點

5.5.2 物理結(jié)構(gòu)設計要點

5.5.3 數(shù)據(jù)結(jié)構(gòu)與程序的關系

5.6 系統(tǒng)出錯處理設計

5.6.1 出錯信息

5.6.2 補救措施

5.6.3 系統(tǒng)維護設計 6 詳細設計說明書

詳細說明書可稱作程序設計說明書。編制目的是說明一個軟件系統(tǒng)各個層次中的每一個程序（每個模塊或子程序）的設計考慮，如果一個軟件系統(tǒng)比較簡單，層次很少，本文件可以不單獨編寫，有關內(nèi)容合并概要設計說明書。對詳細設計說明書的內(nèi)容要不得要求如下：

6.1 引言

6.1.1 編寫目的 6.1.2 背景

6.1.3 定義

6.1.4 參考資料

6.2 程序系統(tǒng)的組織結(jié)構(gòu)

6.3 程序1（標識符）設計說明

6.3.1 程序描述

6.3.2 功能

6.3.3 性能

6.3.4 輸入項

6.3.5 輸出項

6.3.6 算法

6.3.7 流程邏輯

6.3.8 接口

6.3.9 存儲分配

6.3.10 注釋設計

6.3.11 限制條件

6.3.12 測試計劃

6.3.13 尚未解決的問題

6.4 程序2（標識符）設計說明

…… 數(shù)據(jù)庫設計說明書

數(shù)據(jù)庫設計說明書的編制目的是對于設計中的數(shù)據(jù)庫所有標識、邏輯結(jié)構(gòu)和理結(jié)構(gòu)作出具體的設計規(guī)定。其內(nèi)容要求如下：

7.1 引言

7.1.1 編寫目的 7.1.2 背景

7.1.3 定義

7.1.4 參考資料

7.2 外部設計

7.2.1 標識符和狀態(tài)

7.2.2 使用它的程序

7.2.3 約定

7.2.4 專門指導

7.2.5 支持軟件

7.3 結(jié)構(gòu)設計

7.3.1 概念結(jié)構(gòu)設計

7.3.2 邏輯結(jié)構(gòu)設計

7.3.3 理結(jié)構(gòu)設計

7.4 運用設計

7.4.1 數(shù)據(jù)字典設計

7.4.2 安全保密設計 8 用戶手冊

用戶手冊的編制是要使用非專門術語的語言，充分地描述該軟件系統(tǒng)工程所具有的功能及基本的使用方法。使用戶（或潛在用戶）通過本手冊能夠了解該軟件的用途，并且能夠確定在什么情況下，如何使用它。具體的內(nèi)容要求如下：

8.1 引言

8.1.1 編寫目的 8.1.2 背景

8.1.3 定義

8.1.4 參考資料

8.2 用途

8.2.1 功能

8.2.2 性能

8.2.2.1 精度

8.2.2.2 時間特性

8.2.2.3 靈活性

8.2.3 安全保密

8.3 運行環(huán)境

8.3.1 硬設備

8.3.2 支持軟件

8.3.3 數(shù)據(jù)結(jié)構(gòu)

8.4 使用過程

8.4.1 安裝與初始化

8.4.2 輸入

8.4.2.1 輸入數(shù)據(jù)的現(xiàn)實背景

8.4.2.2 輸入格式

8.4.2.3 輸入舉例

8.4.3 輸出

8.4.3.1 輸出數(shù)據(jù)的現(xiàn)實背景

8.4.3.2 輸出格式

8.4.3.3 輸出舉例

8.4.4 文卷查詢

8.4.5 出錯處理與恢復

8.4.6 終端操作

操作手冊

操作手冊的編制是為了向操作人中提供該軟件每一個運行的具體過程和有關知識，包括操作方法的細節(jié)。具體的內(nèi)容要求如下：

9.1 引言

9.1.1 編寫目的 9.1.2 背景

9.1.3 定義

9.1.2 參考資料

9.2 軟件概述

9.2.1 軟件的結(jié)構(gòu)

9.2.2 程序表

9.2.3 文卷表

9.3 安裝與初始化

9.4 運行說明

9.4.1 運行表

9.4.2 運行步驟

9.4.3 運行1（標識符）說明

9.4.3.1 運行控制

9.4.3.2 操作信息

9.4.3.3 輸入-輸出文卷

9.4.3.4 輸出文段

9.4.3.5 輸出文段的復制

9.4.3.6 啟動恢復過程

9.4.4 運行2（標識符）說明

9.5 非常規(guī)過程

9.6 遠程操作 10 模塊開發(fā)卷宗

模塊開發(fā)卷宗是在模塊開發(fā)過程中逐步編寫出來的，每完成一個模塊或一級密切相關的 20 模塊的復審時編寫一份，應該把所有的模塊開發(fā)卷宗匯集在一起。編寫的目的是記錄和匯總低層次開發(fā)的進度和結(jié)果，以便于對整個模塊開發(fā)工作的管理和復審，并為將來的維護提供非常有用的技術信息。具體的內(nèi)容要求如下：

10.1 標題

10.2 模塊開發(fā)情況表

10.3 功能說明

10.4 設計說明

10.5 源代碼清單

10.6 測試說明

10.7 復審的結(jié)論 11 測試計劃

11.1 引言

11.1.1 編寫目的 11.1.2 背景

11.1.3 定義

11.1.4 參考資料

11.2 計劃

11.2.1 軟件說明

11.2.2 測試內(nèi)容

11.2.3 測試1（標識符）

11.2.3.1 進度安排

11.2.3.2 條件

11.2.3.3 測試資料

11.2.3.4 測試培訓

11.2.4 測試2（標識符）

……

11.3 測試設計說明

11.3.1 測試1（標識符）21

11.3.1.1 控制

11.3.1.2 輸入

11.3.1.3 輸出

11.3.1.4 過程

11.3.2 測試2（標識符）

……

11.4 評價準則

11.4.1 范圍

11.4.2 數(shù)據(jù)整理

11.4.3 尺度 12 測試分析報告

測試分析報告的編寫是為了把組裝測試和確認測試的結(jié)果、發(fā)現(xiàn)及分析寫成文件加發(fā)記載，具體的編寫內(nèi)容要求如下：

12.1 引言

12.1.1 編寫目的 12.1.2 背景

12.1.3 定義

12.1.4 參考資料

12.2 測度概要

12.3 測試結(jié)果及發(fā)現(xiàn)

12.3.1 測試1（標識符）

12.3.2 測試2（標識符）

……

12.4 對軟件功能的結(jié)論

12.4.1 功能1（標識符）

12.4.1.1 能力

12.4.1.2 限制

12.4.2 功能2（標識符）

……

12.5 分析摘要

12.5.1 能力

12.5.2 缺陷和限制

12.5.3 建議

12.5.4 評價

12.6 測試資源消耗 13 開發(fā)進度月報

開發(fā)進度月報的編制目的是及時向有關管理部門匯報項目開發(fā)的進展和情況，以便函及時發(fā)現(xiàn)或處理開發(fā)過程中出現(xiàn)的問題。一般地，開發(fā)進度月報是以項目組為單位每月編寫的。如果被開發(fā)的軟件系統(tǒng)規(guī)模比較大，整個工程項目被劃分給若干個分項目組承擔，開發(fā)進度月報將以項目組為單位按月編寫。具體的內(nèi)容要求如下：

13.1 標題

13.2 工程進度與狀態(tài)

13.2.1 進度

13.2.2 狀態(tài)

13.3 資源耗用與狀態(tài)

13.3.1 資源耗用

13.3.1.1 工時

13.3.1.2 機時

13.3.2 狀態(tài)

13.4 經(jīng)費支出與狀態(tài)

13.4.1 經(jīng)費支出

13.4.1.1 支持性費用

13.4.1.2 設備購置費

13.4.2 狀態(tài)

13.5 下個月的工作計劃

13.6 建議

14 項目開發(fā)總結(jié)報告

項目開發(fā)總結(jié)報告的編制是為了總結(jié)本項目開發(fā)工作的經(jīng)驗，說明實際取得的開發(fā)結(jié)果以及對整個開發(fā)工作的各個方面的評價。具體的內(nèi)容要求如下：

14.1 引言

14.1.1 編寫目的 14.1.2 背景

14.1.3 定義

14.1.4 參考資料

14.2 實際開發(fā)結(jié)果

14.2.1 產(chǎn)品

14.2.2 主要功能和性能

14.2.3 基本流程

14.2.4 進度

14.2.5 費用

14.3 開發(fā)工作評價

14.3.1 對生產(chǎn)效率的評價

14.3.2 對產(chǎn)品質(zhì)量的評價

14.3.3 對技術方法的評價

14.3.4 出錯原因的分析

第五篇：數(shù)據(jù)結(jié)構(gòu)算法設計與分析

數(shù)據(jù)結(jié)構(gòu)算法設計與分析、計算機網(wǎng)絡、計算機組成原理、操作系統(tǒng)原理、編譯原理、數(shù)據(jù)庫原理及應用、軟件工程、軟件測試等計算機基礎理論課程；

網(wǎng)頁制作、程序設計Java、JSP程序設計、Oracle、XML程序設計、計算機網(wǎng)絡、SSH（Struts+Spring+Hibernate）框架、Java EE程序設計、Ajax程序設計、Linux+PHP+MySQL程序設計、Android手機開發(fā)、UML系統(tǒng)分析與設計、性能測試、自動化軟件測試、軟件質(zhì)量保證、畢業(yè)設計及項目綜合實訓等。

數(shù)據(jù)結(jié)構(gòu)、計算機網(wǎng)絡、計算機組成原理、操作系統(tǒng)原理、編譯原理、數(shù)據(jù)庫原理及應用、金融學概論、西方經(jīng)濟學等基礎理論課程；

網(wǎng)頁制作、程序設計Java、JSP程序設計、J2EE程序設計、SQL Server數(shù)據(jù)庫、Oracle數(shù)據(jù)庫、Linux操作系統(tǒng)、UML系統(tǒng)分析與設計、軟件工程、XML程序設計、SSH框架、金融市場學、ERP財務管理、管理信息系統(tǒng)、投資銀行學、商業(yè)銀行學、國際金融管理、畢業(yè)設計及項目綜合實訓等專業(yè)課程。

數(shù)據(jù)結(jié)構(gòu)、計算機網(wǎng)絡、計算機組成原理、操作系統(tǒng)原理、數(shù)據(jù)庫原理及應用、軟件工程、軟件測試等計算機基礎理論課程；

網(wǎng)頁制作、程序設計Java、JSP程序設計、J2EE程序設計、XML程序設計、Ajax程序設計、SSH框架、Android手機開發(fā)、Linux+PHP+MySQL程序設計、SQL Server數(shù)據(jù)庫、Linux操作系統(tǒng)、UML系統(tǒng)分析與設計、軟件項目管理、行業(yè)標準與規(guī)范、IT服務管理、IT職業(yè)英語、畢業(yè)設計及項目綜合實訓等專業(yè)課程