數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)任務(wù)書一和二

目 錄實(shí)驗(yàn)1 順序表的應(yīng)用2實(shí)驗(yàn)2 鏈表的應(yīng)用5實(shí)驗(yàn)3 棧的應(yīng)用6實(shí)驗(yàn)4 隊(duì)列的應(yīng)用7實(shí)驗(yàn)5 樹的應(yīng)用9實(shí)驗(yàn)6 圖的應(yīng)用10實(shí)驗(yàn)7 圖的應(yīng)用11實(shí)驗(yàn)8 查找與排序120 實(shí)驗(yàn)要求一、實(shí)驗(yàn)步驟 問題分析充分地分析和理解問題本身，弄清要求做什么，包括功能要求、性能要求、設(shè)計(jì)要求和約束以及基本數(shù)據(jù)特性，數(shù)據(jù)間的聯(liá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ì)著重解決程序的模塊設(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)包括如下內(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 線性表的順序存儲(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 #include /順序表的定義#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 InsertList(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=LocateList(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 position 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);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;ilength;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）學(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)類型。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 #includetypedef int ElemType;typedef struct node ElemType 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-next; 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 Listlen(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&jnext;if(!p-next&ji-1) printf(Wrong positionn );else q=(NODE *)malloc(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); scanf(%d%d,&i,&element); Ins(head,i,element); Output(head); getch();2、應(yīng)用題：（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人，再將他投入大海，如此循環(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è)旅客為止。本游