實(shí)驗(yàn)任務(wù)書(2015)(1)

1、目 錄0 實(shí)驗(yàn)要求2實(shí)驗(yàn)1 線性表的順序存儲(chǔ)結(jié)構(gòu)3實(shí)驗(yàn)2 鏈表的應(yīng)用6實(shí)驗(yàn)3 棧的應(yīng)用9實(shí)驗(yàn)4 隊(duì)列的應(yīng)用10實(shí)驗(yàn)5 樹的應(yīng)用11實(shí)驗(yàn)6 圖的應(yīng)用12實(shí)驗(yàn)7 圖的應(yīng)用13實(shí)驗(yàn)8 查找與排序14140 實(shí)驗(yàn)要求一、實(shí)驗(yàn)步驟 問題分析充分地分析和理解問題本身，弄清要求做什么，包括功能要求、性能要求、設(shè)計(jì)要求和約束以及基本數(shù)據(jù)特性，數(shù)據(jù)元素之間的關(guān)系等。 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)針對(duì)要求解決的問題，考慮各種可能的數(shù)據(jù)結(jié)構(gòu)，并且力求從中找出最佳方案(必須連同算法一起考慮)，確定主要的數(shù)據(jù)結(jié)構(gòu)及全局變量。對(duì)引入的每種數(shù)據(jù)結(jié)構(gòu)和全局變量要詳細(xì)說明其功能、初值和操作特點(diǎn)。 算法設(shè)計(jì)算法設(shè)計(jì)分概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)。概要設(shè)計(jì)

2、著重解決程序的模塊設(shè)計(jì)問題，這包括考慮如何把被開發(fā)的問題程序自頂向下分解成若干順序模塊，并決定模塊的接口，即模塊間的相互關(guān)系以及模塊之間的信息交換問題。詳細(xì)設(shè)計(jì)則要決定每個(gè)模塊內(nèi)部的具體算法，包括輸入、處理和輸出，采用類C語言描述。 測(cè)試用例設(shè)計(jì)準(zhǔn)備典型測(cè)試數(shù)據(jù)和測(cè)試方案，測(cè)試數(shù)據(jù)要有代表性、敏感性，測(cè)試方案包括模塊測(cè)試和模塊集成測(cè)試。 上機(jī)調(diào)試對(duì)程序進(jìn)行編譯，糾正程序中可能出現(xiàn)的語法錯(cuò)誤。測(cè)試前，先運(yùn)行一遍程序看看究竟將會(huì)發(fā)生什么，如果錯(cuò)誤較多，則根據(jù)事先設(shè)計(jì)的測(cè)試方案并結(jié)合現(xiàn)場(chǎng)情況進(jìn)行錯(cuò)誤跟蹤，包括打印執(zhí)行路徑或輸出中間變量值等手段。二、實(shí)驗(yàn)報(bào)告每次實(shí)驗(yàn)結(jié)束后，均應(yīng)撰寫實(shí)驗(yàn)報(bào)告。實(shí)驗(yàn)報(bào)告應(yīng)

3、包括如下內(nèi)容： 1、問題描述：簡(jiǎn)述題目要解決的問題是什么。2、設(shè)計(jì)：概要設(shè)計(jì)采用抽象數(shù)據(jù)類型描述，詳細(xì)設(shè)計(jì)包括存儲(chǔ)結(jié)構(gòu)的定義、主要操作算法設(shè)計(jì)等。用類C語言或用框圖描述。3、調(diào)試報(bào)告：調(diào)試過程中遇到的問題是如何解決的；對(duì)設(shè)計(jì)和編碼的討論和分析。4、運(yùn)行結(jié)果?？梢再N相應(yīng)的運(yùn)行結(jié)果截圖。5、算法分析與改進(jìn)：算法的時(shí)間復(fù)雜度和空間復(fù)雜度分析；算法改進(jìn)的設(shè)想。6、經(jīng)驗(yàn)和體會(huì)所有實(shí)驗(yàn)做完后，上交上機(jī)實(shí)驗(yàn)源程序和相應(yīng)的運(yùn)行結(jié)果截圖。源程序要加注釋。如果題目規(guī)定了測(cè)試數(shù)據(jù)，則截圖結(jié)果要包含這些測(cè)試數(shù)據(jù)和運(yùn)行輸出，當(dāng)然還可以含有其它測(cè)試數(shù)據(jù)和運(yùn)行輸出（有時(shí)需要多組數(shù)據(jù)）。三、實(shí)驗(yàn)學(xué)時(shí)16學(xué)時(shí)實(shí)驗(yàn)1 線性表的順

4、序存儲(chǔ)結(jié)構(gòu)實(shí)驗(yàn)?zāi)康? 熟悉C語言的上機(jī)環(huán)境，掌握使用VC環(huán)境上機(jī)調(diào)試線性表的基本方法；2 掌握線性表的順序存儲(chǔ)結(jié)構(gòu)及其線性表的基本操作：插入、刪除、查找等。3 掌握線性表合并等運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)。實(shí)驗(yàn)要求1 認(rèn)真閱讀和掌握本實(shí)驗(yàn)的程序。2 上機(jī)運(yùn)行程序，觀察程序的運(yùn)行結(jié)果。3 按照你對(duì)線性表的操作需要，重新改寫主程序并運(yùn)行。實(shí)驗(yàn)內(nèi)容（基礎(chǔ)題必做，應(yīng)用題、提高題可選）1. 基礎(chǔ)題：線性表基本操作的實(shí)現(xiàn)這個(gè)程序中演示了順序表的創(chuàng)建、插入、刪除和查找，（1）請(qǐng)修改并記錄運(yùn)行結(jié)果；（2）按照你自己對(duì)線性表測(cè)試的需要，增加新的操作，重新改寫主程序并記錄運(yùn)行結(jié)果。#include <stdi

5、o.h>#include <stdlib.h>/順序表的定義#define ListSize 100typedef int ElemType;typedef structElemType *elem; /*存放表元素的空間基地址*/ int length;/*當(dāng)前的表長(zhǎng)度*/ int listsize; /*能容納的最大元素個(gè)數(shù)*/SeqList;void CreateList(SeqList &L,int n);void PrintList(SeqList L,int n);int LocateList(SeqList L,int x);void InsertLis

6、t(SeqList &L,int x,int i);void DeleteList(SeqList &L,int i);void main() SeqList L;int i,x;int n=10;/*THE LENGTH OF LIST*/L.length=0;clrscr();CreateList(L,n);/*CREATE THE LIST*/PrintList(L,n);/*PRINT THE LIST*/printf("INPUT THE SEARCH ELEMENT");scanf("%d",&x);i=LocateL

7、ist(L,x);printf("the search position is %dn",i);/*順序表查找*/printf("input the position of insert:n");scanf("%d",&i);printf("input the value of insertn");scanf("%d",&x);InsertList(L,x,i);/*順序表插入*/PrintList(L,n);/*打印順序表*/printf("input the pos

8、ition of deleten");scanf("%d",&i);DeleteList(L,i);/*順序表刪除*/PrintList(L,n);getch();/*打印順序表*/*順序表的建立：*/void CreateList(SeqList &L,int n)L. elem =(ElemType *)malloc(ListSize *sizeof(ElemType);if(!L.elem) exit(0);L.listsize= ListSize;int i;printf("please input n numbersn"

9、;);for(i=1;i<=n;i+)scanf("%d",&L. elem i);L.length=n;/*順序表的打?。?/void PrintList(SeqList L,int n)int i;printf("the sqlist isn");for(i=1;i<=n;i+)printf("%d ",L.elem i);/*順序表的查找：*/int LocateList(SeqList L,int x)int i;for(i=1;i<=10;i+) if(L. elem i)=x) return(i)

10、; else return(0);/*順序表的插入：*/void InsertList(SeqList &L, int x, int i)int j;for(j=L->length;j>=i;j-)L-> elem j+1=L-> elem j;L-> elem i=x;L.length+;/*順序表的刪除：*/void DeleteList(SeqList &L,int i) int j;for(j=i;j<=(L.length)-1;j+)L. elem j=L. elem j+1;2.應(yīng)用題（1）求集合A、B的并集C。（2）歸并兩個(gè)有序

11、表La和Lb成一個(gè)新的有序表Lc。有序指值非遞減。3.提高題（1）學(xué)生成績(jī)管理本題目是對(duì)學(xué)生成績(jī)管理的簡(jiǎn)單模擬，用菜單選擇方式完成下列功能：輸入學(xué)生數(shù)據(jù)；輸出學(xué)生數(shù)據(jù)；學(xué)生數(shù)據(jù)查詢；添加學(xué)生數(shù)據(jù)；修改學(xué)生數(shù)據(jù)；刪除學(xué)生數(shù)據(jù)。本題目的數(shù)據(jù)是一組學(xué)生的成績(jī)信息，每條學(xué)生的成績(jī)信息由學(xué)號(hào)、姓名和成績(jī)組成。（2）考試報(bào)名管理本項(xiàng)目是對(duì)考試報(bào)名管理的簡(jiǎn)單模擬，用菜單選擇方式完成下列功能：輸入考生信息；輸出考生信息；查詢考生信息；添加考生信息；修改考生信息；刪除考生信息。本題目的數(shù)據(jù)是一組考生信息，每條考生信息由準(zhǔn)考證號(hào)、姓名、性別、年齡、報(bào)考類別等信息組成。實(shí)驗(yàn)2 鏈表的應(yīng)用實(shí)驗(yàn)?zāi)康? 定義單鏈表的結(jié)點(diǎn)

12、類型。2 熟悉對(duì)單鏈表的一些基本操作和具體的函數(shù)定義。3 通過單鏈表的定義掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)。4 熟悉單鏈表的應(yīng)用場(chǎng)合。實(shí)驗(yàn)要求1 獨(dú)立完成；2 準(zhǔn)備好測(cè)試數(shù)據(jù)，程序調(diào)試正確，有執(zhí)行結(jié)果。實(shí)驗(yàn)內(nèi)容（基礎(chǔ)題必做，應(yīng)用題、提高題任選）1基礎(chǔ)題：按照教材中抽象數(shù)據(jù)類型線性表的定義，演示單鏈表的基本操作，按照自己的意圖編寫基本操作函數(shù)和主函數(shù)進(jìn)行測(cè)試。示例：這個(gè)程序演示了單鏈表的創(chuàng)建和插入操作。程序如下：#include <stdio.h>#include<stdlib.h>typedef int ElemType;typedef struct node ElemT

13、ype data; struct node *next; NODE;typedef NODE *LinkList;/*/LinkList Create()NODE *p,*head;int x;head=(NODE *)malloc(sizeof(NODE);head->next=NULL;printf("Input data,-1 to End!n");scanf("%d",&x);while(x!=-1) p=(NODE *)malloc(sizeof(NODE); p->data=x; p->next=head->n

14、ext; head->next=p; scanf("%d",&x);return(head);/*/void Output(LinkList head) NODE *p; p=head; printf("Begin to dump the LinkList.n"); while(p->next!=NULL) printf("->%d",p->next->data); p=p->next; printf("nThe LinkList ended!n");/*/int Lis

15、tlen(LinkList head) int i=0; NODE *p=head; while(p->next!=NULL) i+; p=p->next; return(i);/*/void Ins(LinkList head,int i,int e)NODE *p=head,*q;int j=0;while(p->next&&j<i-1)j+;p=p->next;if(!p->next&&j>i-1) printf("Wrong positionn" );else q=(NODE *)malloc

16、(sizeof(NODE); q->data=e; q->next=p->next; p->next=q;/*/main() LinkList head; int length; int i,element; clrscr(); head=Create(); Output(head); length=Listlen(head); printf("the length of the link is %dn",length); printf("Input the insert position and element:n"); sca

17、nf("%d%d",&i,&element); Ins(head,i,element); Output(head); getch();2.應(yīng)用題（1）求集合A、B的并集C。（2）歸并兩個(gè)有序表La和Lb成一個(gè)新的有序表Lc。有序指值非遞減。3.提高題（1）約瑟夫生者死者游戲： 30個(gè)旅客同乘一條船，因?yàn)閲?yán)重超載，加上風(fēng)高浪大，危險(xiǎn)萬分；因此船長(zhǎng)告訴乘客，只有將全船一半的旅客投入海中，其余人才能幸免遇難。無奈，大家只得同意這種辦法，并議定30個(gè)人圍成一圈，由第一個(gè)人開始，依次報(bào)數(shù)，數(shù)到第9人，便把他投入大海中，然后從他的下一個(gè)人數(shù)起，數(shù)到第9人，再將他投入大海

18、，如此循環(huán)，直到剩下15個(gè)乘客為止。問哪些位置是將被扔下大海的位置。本游戲的數(shù)學(xué)建模如下：假設(shè)n個(gè)旅客排成一個(gè)環(huán)形，依次順序編號(hào)1，2，n。從某個(gè)指定的第1號(hào)開始，沿環(huán)計(jì)數(shù)，每數(shù)到第m個(gè)人就讓其出列，且從下一個(gè)人開始重新計(jì)數(shù)，繼續(xù)進(jìn)行下去。這個(gè)過程一直進(jìn)行到剩下k個(gè)旅客為止。本游戲要求用戶輸入的內(nèi)容包括： 1） 旅客的個(gè)數(shù)，也就是n的值； 2） 離開旅客的間隔數(shù)，也就是m的值；3） 所有旅客的序號(hào)作為一組數(shù)據(jù)要求存放在某種數(shù)據(jù)結(jié)構(gòu)中。本游戲要求輸出的內(nèi)容包括1） 離開旅客的序號(hào)； 2） 剩余旅客的序號(hào)。（2）一元多項(xiàng)式求和有兩個(gè)指數(shù)遞減的一元多項(xiàng)式，寫一程序求這兩個(gè)多項(xiàng)式的和。提示：用帶表頭結(jié)

19、點(diǎn)的單鏈表作為多項(xiàng)式的存儲(chǔ)表示；要建立兩個(gè)單鏈表；多項(xiàng)式相加就是要把一個(gè)單鏈表中的結(jié)點(diǎn)插入到另一個(gè)單鏈表中去，要注意插入、刪除操作中指針的正確修改。實(shí)驗(yàn)3 棧的應(yīng)用實(shí)驗(yàn)?zāi)康? 會(huì)定義順序棧和鏈棧的類型。2 掌握棧的插入和刪除在操作上的特點(diǎn)。3 熟悉對(duì)棧的一些基本操作和具體的函數(shù)定義。實(shí)驗(yàn)要求1 獨(dú)立完成；2 程序調(diào)試正確，有執(zhí)行結(jié)果。實(shí)驗(yàn)內(nèi)容（基礎(chǔ)題必做，應(yīng)用題、提高題任選）1. 基礎(chǔ)題：按照教材中抽象數(shù)據(jù)類型棧的定義，采用順序存儲(chǔ)結(jié)構(gòu)（用動(dòng)態(tài)數(shù)組）或鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，編寫主函數(shù)演示順序棧/鏈棧的基本操作。2. 應(yīng)用題：（1）判斷給定的字符串是否中心對(duì)稱。（2）數(shù)制轉(zhuǎn)換（3）表達(dá)式括號(hào)匹配問題3.

20、 提高題（1）算符優(yōu)先算法為表達(dá)式求值（2）迷宮求解實(shí)驗(yàn)4 隊(duì)列的應(yīng)用實(shí)驗(yàn)?zāi)康? 掌握隊(duì)列的存儲(chǔ)結(jié)構(gòu)及基本操作。2 掌握循環(huán)隊(duì)列的設(shè)置及循環(huán)隊(duì)列的各種基本操作的實(shí)現(xiàn)。3 通過具體的應(yīng)用實(shí)例，進(jìn)一步熟悉和掌握隊(duì)列的實(shí)際應(yīng)用。實(shí)驗(yàn)要求1 獨(dú)立完成；2 程序調(diào)試正確，有執(zhí)行結(jié)果。實(shí)驗(yàn)內(nèi)容（基礎(chǔ)題必做，應(yīng)用題任選）1、 基礎(chǔ)題：按照教材中抽象數(shù)據(jù)類型隊(duì)列的定義，采用順序存儲(chǔ)結(jié)構(gòu)（循環(huán)隊(duì)列）或鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，編寫主函數(shù)演示循環(huán)隊(duì)列/鏈隊(duì)列的基本操作。2、 應(yīng)用題：舞伴問題：假設(shè)在周末舞會(huì)上，男士們和女士們進(jìn)入舞廳時(shí)，各自排成一隊(duì)，跳舞開始時(shí)，依次從男隊(duì)和女隊(duì)的隊(duì)頭上各出一人配成舞伴，若兩隊(duì)初始人數(shù)不相同，

21、則較長(zhǎng)的那一隊(duì)中未配對(duì)者等待下一輪舞曲。設(shè)計(jì)一個(gè)函數(shù)partner()，模擬上述舞伴配對(duì)問題?；疽螅?) 由鍵盤輸入數(shù)據(jù)，每對(duì)數(shù)據(jù)包括姓名和性別；2) 輸出結(jié)果包括配成舞伴的女士和男士的姓名，以及未配對(duì)者的隊(duì)伍名稱和隊(duì)頭者的姓名； 實(shí)驗(yàn)5 樹的應(yīng)用實(shí)驗(yàn)?zāi)康? 熟悉二叉樹結(jié)點(diǎn)的結(jié)構(gòu)和對(duì)二叉樹的基本操作。2 掌握對(duì)二叉樹每一種操作的具體實(shí)現(xiàn)。3 學(xué)會(huì)利用遞歸方法編寫對(duì)二叉樹這種遞歸數(shù)據(jù)結(jié)構(gòu)進(jìn)行處理的算法。4 在二叉樹基本操作的基礎(chǔ)上掌握對(duì)二叉樹的一些其它操作的具體實(shí)現(xiàn)方法。5 掌握構(gòu)造哈夫曼樹以及哈夫曼編碼的方法。實(shí)驗(yàn)要求1 獨(dú)立完成；2 程序調(diào)試正確，有執(zhí)行結(jié)果。實(shí)驗(yàn)內(nèi)容（基礎(chǔ)題必做，應(yīng)用題

22、任選）1. 基礎(chǔ)題：按照教材中抽象數(shù)據(jù)類型二叉樹的定義，采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，編寫主函數(shù)演示二叉樹的基本操作（不少于5個(gè)），如：(1) Status InitBTree( BiTree &BT ) /初始化二叉樹BT (2) Status CreateBTree(BiTree &BT, char *a ) /根據(jù)先序序列a建立二叉鏈表存儲(chǔ)結(jié)構(gòu) (3)Status EmptyBTree(BiTree BT) /檢查二叉樹BT是否為空，空返回Yes，否則返回No (4) int DepthBTree(BiTree BT) /求二叉樹BT的深度并返回該值 (5) Status Fin

23、dBTree(BiTree BT, TElemType x) /查找二叉樹BT中值為x的結(jié)點(diǎn)，若查找成功返回該結(jié)點(diǎn)地址，否則返回Error (6) void PreOrder(BiTree BT) /先序遍歷二叉樹BT(7) void InOrder(BiTree BT) /中序遍歷二叉樹BT(8) void PostOrder(BiTree BT) /后序遍歷二叉樹BT(9) void LevelOrder(BiTree BT ) /按層次遍歷二叉樹BT (10) void PrintBTree(BiTree BT ) /輸出二叉樹BT 2應(yīng)用題家譜管理：本題目對(duì)家譜管理進(jìn)行簡(jiǎn)單的模擬，以實(shí)

24、現(xiàn)查看祖先和子孫個(gè)人信息、插入家族成員、刪除家族成員等功能。實(shí)驗(yàn)6 圖的應(yīng)用實(shí)驗(yàn)?zāi)康? 掌握?qǐng)D的各種存儲(chǔ)結(jié)構(gòu)，特別要熟練掌握鄰接矩陣和鄰接表存儲(chǔ)結(jié)構(gòu)。2 遍歷是圖各種應(yīng)用的算法的基礎(chǔ)，要熟練掌握?qǐng)D的深度優(yōu)先遍歷和廣度優(yōu)先遍歷算法，復(fù)習(xí)棧和隊(duì)列的應(yīng)用。實(shí)驗(yàn)要求1 獨(dú)立完成；2 程序調(diào)試正確，有執(zhí)行結(jié)果。實(shí)驗(yàn)內(nèi)容1、基礎(chǔ)題（至少做一個(gè)）（1）圖的鄰接矩陣定義及實(shí)現(xiàn)：定義圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)，并編寫圖的初始化、建立圖、深度優(yōu)先/廣度優(yōu)先輸出圖、輸出圖的每個(gè)頂點(diǎn)的度等基本操作實(shí)現(xiàn)函數(shù)。以下圖為例，建立一個(gè)驗(yàn)證操作實(shí)現(xiàn)的主函數(shù)進(jìn)行測(cè)試。0124653（2）圖的鄰接表的定義及實(shí)現(xiàn)：定義圖的鄰接表存儲(chǔ)結(jié)構(gòu)，并編寫圖的初始化、建立圖、深度優(yōu)先/廣度優(yōu)先輸出圖、輸出圖的每個(gè)頂點(diǎn)的度等基本操作實(shí)現(xiàn)函數(shù)。同時(shí)在主函數(shù)中調(diào)用這些函數(shù)進(jìn)行驗(yàn)證（以下圖為例）。001122334實(shí)驗(yàn)7 圖的應(yīng)用實(shí)驗(yàn)?zāi)康?. 掌握?qǐng)D的最短路徑概念。2. 掌握生成最小生成樹的Prim算法（用鄰接矩陣表示圖）/克魯斯卡爾算法。3. 理解求最短路徑的DijKstra算法（用鄰接矩陣表示圖）。實(shí)驗(yàn)要求1 獨(dú)立完成；2 程序調(diào)試正確，有執(zhí)行結(jié)果。實(shí)驗(yàn)內(nèi)容（基礎(chǔ)題必做，應(yīng)用題任選）1、基礎(chǔ)題編寫用鄰接矩陣表示有向帶權(quán)圖時(shí)圖的基本操作的實(shí)現(xiàn)函數(shù)，主要包括： 初始化鄰接矩陣表示的有向帶權(quán)圖 建立鄰接矩陣表