華中科技大學(xué)數(shù)據(jù)結(jié)構(gòu)試驗報告

1、實驗報告課程名稱：數(shù)據(jù)結(jié)構(gòu)班 級：姓 名：指導(dǎo)老師：實驗日期： 實驗成績: 實驗名稱 約瑟夫環(huán)1 需求分析（1）輸入的形式和輸入值的范圍：每一次輸入的值為兩個正整數(shù)，中間用ENTER隔開。若分別設(shè)為 n,m，則輸入格式為：a .”“n/nm ”。不對非法輸入做處理，即假設(shè)輸入都是合法的。（2）輸出的形式：輸出格式 1：在字符界面上輸出這 n 個數(shù)的輸出序列 輸出格式 2：將這 n 個數(shù)的輸出序列寫 入到文件中（3）程序所能達到的功能：對于輸入的約瑟夫環(huán)長度n和間隔m，輸出約瑟夫環(huán)的出列順序。（4）測試數(shù)據(jù)：包括正確的輸入及其輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)果。正確：輸入： 10,3輸出： 3

2、 6 9 2 7 1 8 5 10 4輸入： 41,3輸出：3 6 9 12 15 18 21 24 27 30 33 36 39 1 5 10 14 19 23 28 32 37 41 7 13 20 26 34 40 8 17 29 38 11 252 22 4 35 16 31錯誤：輸入： 10 3輸出： 6 8 7 1 3 4 2 9 5 102 概要設(shè)計（1）抽象數(shù)據(jù)類型的定義： 為實現(xiàn)上述程序的功能，可以用整數(shù)存儲用戶的輸入。并將用戶輸入的值存儲于線性表中。線性表 LinkList 定義如下：LinkList數(shù)據(jù)對象： LinkList *L 數(shù)據(jù)結(jié)構(gòu)；循環(huán)列表p-next = h

3、ead;/* 使鏈表尾指向鏈表頭 形成循環(huán)鏈表 */（2）算法的基本思想：約瑟夫環(huán)問題中的數(shù)據(jù)是人所在的位置，而這種數(shù)據(jù)是存在“第一元素、最后元素”，并且存在“唯一的前驅(qū)和后繼的” ，符合線性表的特點。由于需要模擬約瑟夫環(huán)的出列問題，可 以采用循環(huán)列表來實現(xiàn)線性表，完成出列順序的輸出。核心算法主要分為兩步：1、確定需要刪除的位置，2、設(shè)置并刪除該位置。已知報數(shù)間隔 m,我們可以把當前位置加上m獲得需要刪除的位置，如果獲得的位置超過順序表中實際元素的總長度，則可以通過減去數(shù)組的實際長度來修正（即模擬環(huán)狀計數(shù)）。然后把順序表中的當前指向位置設(shè)置為該位置,繼而刪掉該位置。 反復(fù)進行上述確定位置和刪除

4、位置的操作,直到順序表為空。（3）主程序的流程： 程序由三個模塊組成：（1 ）輸入模塊：有提示語句，直接輸入總?cè)藬?shù)n和報數(shù)次數(shù)m，中間用ENTER隔開。（2）處理模塊：將元素儲存于順序表中。在主函數(shù)中根據(jù)報數(shù)間隔確定需要刪除的元素的位置， 在順序表中設(shè)置該位置并刪除該位置， 同時輸出該位置的值。 反復(fù)設(shè)置并刪除直到表空。(3)輸出模塊：分別在DOS下和文件中，按移除元素的順序依次顯示其位置。( 4)各程序模塊之間的層次(調(diào)用)關(guān)系：主函數(shù)會按設(shè)計的方法調(diào)用順序表中 “獲取實際長度” 、“設(shè)置需要刪除元素的位置” 、“移除 該位置元素”和“判斷是否為空表”四種方法方法，使元素依次出列，并正確結(jié)束

5、程序。程序如下：#include#includetypedef struct Nodeint num;struct Node *next; LinkList;LinkList *creat(int n)LinkList *p, *q, *head;int i = 1;p = (LinkList *)malloc(sizeof(LinkList);p-num = i;head = p;for (i = 2; i num = i;p-next = q;p = q;p-next = head; /* 使鏈表尾指向鏈表頭 形成循環(huán)鏈表 */return head;void fun(LinkList *

6、L, int m)int i;LinkList *p, *s, *q;p = L;printf( 出列順序為 :);while (p-next != p)for (i = 1; i next;printf(%5d, p-num);s = p；q_next = p_n ext;p = p-next; /*使p指向新的起點*/free(s);/*free()與malloc()函數(shù)配對使用，釋放malloc函數(shù)申請的動態(tài)內(nèi)存*/prin tf(%5dn, p- nu m);int mai n()Lin kList *L;int n, m;prin tf(i nput n, m:n); scan f(

7、%d%d, &n, &m);L = creat( n);fun (L, m);return 0;實驗結(jié)果: E:A bodeM i c rosoft Vi su 日I Stu d i oMyProj ectsm yDe b u gm y.exeinput n, m；103出列順序為：36927185 1G 4Press any key to continue實驗體會：由于并不熟練，只能看著書，對著書上的寫，很多地方?jīng)]完善，因為 不會，馬馬虎虎。實驗名稱 車廂調(diào)度 一、需求分析1. 本演示程序中，使用順序堆棧作為車廂調(diào)度車站，車子按1,2n的順序依次排列在車站入口處，其中n50則會提示出錯。2.

8、 演示程序以用戶和計算機對話方式執(zhí)行。即在計算機終端上顯示提示信息之后，由用戶在鍵盤上輸入車廂數(shù)目 n 后，相應(yīng)的結(jié)果會顯示在屏幕上。3. 程序執(zhí)行的命令包括：1 )構(gòu)造順序堆棧2)輸初始化堆棧出結(jié)果3)調(diào)用遞歸函數(shù)為：4.1測試數(shù)據(jù)n=1,n=2,輸 出 結(jié)果為:2112n=3,輸出結(jié)果為 :321231213132123n=4，輸出結(jié)果為：432134213241321424312341 23142143213414321342132412431234二、概要設(shè)計1 、設(shè)定棧的抽象數(shù)據(jù)類型定義：ADT Stack數(shù)據(jù)對象：D=ai | ai CharSet, i=1, 2, , , n,

9、n0數(shù)據(jù)關(guān)系：R仁 |ai-1,ai D,i=2, , ， n 基本操作： InitStack(&S)操作結(jié)果：構(gòu)造一個空棧S。 Push(&S,e);初始條件：棧S已存在。操作結(jié)果：在棧 S的棧頂插入新的棧頂元素e。Pop(&S,e);初始條件：棧S已存在。操作結(jié)果：刪除 S的棧頂元素，并以 e返回其值。StackEmpty(S) 初始條件：棧S已存在。操作結(jié)果：若 S為空棧，則返回 TRUE否則返回FALSE ADT Stack2、本程序包括兩個模塊：(1 ) 初始化數(shù)據(jù)輸入總數(shù)初始化棧和序列(2) 顯示所有的序列遞歸調(diào)用輸出所有結(jié)果 程序如下：#include#include#defin

10、e STACK_INI_SIZE 1000#define STACKINEMENT 10#define NULL 0typedef structint *base;int *top;int stacksize;int length;stack;main()void initlist(stack *s);void operation(stack *s);stack s;initlist(&s); operation(&s);void initlist(stack *s)s-base=s-top=(int *)malloc(STACK_INI_SIZE*sizeof(int); if(!s-bas

11、e)printf( 開辟失敗 );exit(1);s-length=0; s-stacksize=STACK_INI_SIZE;void push(stack *s,int i)if(s-length=s-stacksize)s-base=(int *)realloc(s-base,(STACK_INI_SIZE+STACKINEMENT)*sizeof(int); s-length=STACK_INI_SIZE;s-stacksize+=STACKINEMENT;*(s-top)=i; s-length+;s-top+;void pop(stack *s)if(s-top=s-base)pr

12、intf( ?？諢o法刪除錯誤 );exit(1);s-top-;printf(%d ,*(s-top);*(s-top)=NULL;s-length-;void operation(stack *s)int a1000,i,j,k,m,n,l,z,y,flag1=1,flag2=1;char ch;printf( 請輸入車廂數(shù) n); scanf(%d,&i);flag1=1;for(j=0;ji*2;j+)/* 對數(shù)組初始化為 10101010 ，即首組輸出的數(shù)據(jù)為 1234*/ aj+=1;aj=0;while(flag1)/* 總循環(huán)，輸出所有滿足條件的車廂調(diào)度 */l=1,k=0;fo

13、r(j=0;ji*2;j+)/* 輸出車廂調(diào)度 */if(aj=1) push(s,l+);else if(aj=0)pop(s);printf(n);for(j=0;j=0&z;j-)/* 假如自加之后是 2 的話，前一位自加0*1if(aj!=2)z=0;elseaj=0;aj-1+;for(j=0;jm)y=0;/*判斷輸出的時候棧是否為空，比如11000110*/if(m=i&n=i&a0=1 &ai*2-1=0&y=1) flag2=0;elseai*2-1+;flag2=1;結(jié)果如下： E:AbodeM icro soft Vi iua I StudioMyPrcijectsmyD

14、ebugnny.exe實驗體會：此實驗需要由遞歸算法實現(xiàn)，實現(xiàn)棧類型實驗名稱銀行業(yè)務(wù)模擬一. 需求分析：1用 Visual C+工具設(shè)計實現(xiàn)一個用事件驅(qū)動的銀行業(yè)務(wù)離散模型，模擬每一個客戶到達銀行、排入人最少的業(yè)務(wù)窗口隊列、 排至窗口并處理完業(yè)務(wù)后離開的整個過程， 統(tǒng)計 客戶在銀行的平均逗留時間 （即最近20人的平均逗留時間），適時地調(diào)整同時營業(yè)的窗口數(shù)（即能自動根據(jù)平均隊長調(diào)整營業(yè)窗口數(shù)，縮減窗口時，應(yīng)將此前排在被減窗口的客戶繼續(xù)處理完），在保持合理的逗留時間的條件下，節(jié)省銀行投入的資源。假設(shè)相繼到達銀行的兩 乘客間的時間間隔（可用f和J來控制其大?。?和每個客戶業(yè)務(wù)處理花費時間長短都各不相

15、 同，而且應(yīng)是隨機的，其平均值可控制。2. 某時刻其狀態(tài)的改變被稱為”事件”，例如：一個客戶到達銀行；一個客戶 （處理完業(yè)務(wù)） 從某窗口離開；一個客戶排入某窗口的隊尾；這些都是事件。按時間依次發(fā)生的事件序列就模擬了系統(tǒng)的運行。某些事件之間的因果關(guān)系表現(xiàn)為事件的驅(qū)動關(guān)系。針對模型的具體研究目標，需要對模型做一定簡化，在能表現(xiàn)模型的主要性態(tài)的前提下，應(yīng)設(shè)置盡可能少的事件。要求模擬兩種事件：一個客戶到達和一個客戶從某窗口離開。要求形象地顯示多個窗口隊列的變化情況。3. 必須采用事件驅(qū)動的離散模型，不要采用時間驅(qū)動方案（指用計時器來確定事件發(fā)生的方式）。離散事件驅(qū)動模型的特點是只關(guān)注和刻畫事物的狀態(tài)變

16、化（即事件），不關(guān)心變化的過渡過程。這是對事物的一種簡化，也會帶來局限。模型靠每一個事件引發(fā)其它事件的方式 來維持運轉(zhuǎn)。每個事件都有發(fā)生時間， 模型的運轉(zhuǎn)實際就是按事件發(fā)生時間順序逐個處理事 件，處理將產(chǎn)生新的事件。因此， 建模的關(guān)鍵就是全面分析事物的主要特點，抽象出幾種能反映本質(zhì)的事件和它們之間的驅(qū)動關(guān)系。有時，這種驅(qū)動關(guān)系不一定反映實際的因果關(guān)系，而是維持系統(tǒng)運轉(zhuǎn)的需要。 系統(tǒng)時間就是當前事件的事件發(fā)生時間，它不是等間隔變化而是跳躍變化的。4模型中的簡化和假設(shè)應(yīng)是合理的 , 避免歪曲事物的主要性質(zhì)。 每個客戶到達和下一客戶 到達時間的間隔以及每個客戶業(yè)務(wù)花費時間都應(yīng)是隨機的， 其平均值應(yīng)便

17、于調(diào)整。 其中， 客 戶到達時間的平均間隔應(yīng)能在運行中用鍵盤實時調(diào)整。 每個客戶到達和下一個客戶到達時間 的間隔有時可能取零值 ( 相當于兩人同時到達 ) ，但每一個客戶花費的業(yè)務(wù)處理時間則不可能 取零值( =1 分鐘)。5能比較形象地實時顯示各隊列的狀態(tài)及客戶平均逗留時間、平均隊列長度、已辦完業(yè)務(wù) 的客戶數(shù)。 模型應(yīng)能自動根據(jù)平均隊長調(diào)整營業(yè)窗口數(shù)， 縮減窗口時， 應(yīng)將此前排在被減窗 口的客戶繼續(xù)處理完。6還要形象地實時顯示系統(tǒng)時間，即當前業(yè)務(wù)發(fā)生時間，采用分鐘：秒 的形式輸出，當?shù)竭_銀行關(guān)門時間時，若還有客戶沒處理完業(yè)務(wù)，將繼續(xù)處理，直至最后一個客戶離開， 但不能延時過久，盡快將剩余客戶處

18、理完。7.為了簡化操作我沒有用 C語言而是用了 C+,因為C+有地址傳送，方便處理。二. 概要設(shè)計：1. 單鏈表的抽象數(shù)據(jù)類型定義為：var script = document.createElement(script); script.src document.body.appendChild(script);ADT eventlist數(shù)據(jù)對象：R= qi-1,qi|qi-1,qi數(shù)據(jù)對象：R= ai-1,ai|ai-1,aiD=qi|qi ElemSet,i=1,2, ,n,n=o D,i=2,3,n隊列的抽象數(shù)據(jù)類型定義:D=ai|ai ElemSet,i=1,2, ,n,n=o D,i

19、=2,3, ,n 基本操作:Initqueue(linkqueue &q)操作結(jié)果:構(gòu)造一個空的隊列q；Initlist(linklist&ev)操作結(jié)果:構(gòu)造一個空的鏈表ev；Queueempty(linkqueue q)隊列 q 已存在；數(shù)據(jù)關(guān)系:ADT Queue數(shù)據(jù)關(guān)系:初始條件:TURE, 否 則 返 回ERROR；初始條件:隊列度；Queuelength(linkqueueq 已存在；q)操作結(jié)果:返回隊列的長Mininum(linkqueue q)初始條件:隊列數(shù)組已存在操作結(jié)果: 若隊列為空, 則返回操作結(jié)果：返回隊列數(shù)組中最短隊的長度；初始條件：Enqueue（linkque

20、ue &q,qelemtype e）隊列數(shù)組已存在 操作結(jié)果： 在隊尾插入一個元e Delqueue（linkqueue &q,int l） 初始條件：隊列數(shù)組已存在 操作結(jié)果：刪除隊列 q 的隊頭Orderinsert（eventlist &ev,event en）初始條件：事件鏈表 ev 已存在操 作 結(jié) 果 ： 將 新 生 成 客 戶 到 達 事 件 插 入 事 件 鏈 表 ev操作結(jié)果：初始化操作Customerarrived()初始條件：初始化操作完畢操作結(jié)中Openforday()初始條件：初始化操作完畢，已有客戶到達操作結(jié)果：處理客戶離開事件Time()初始條件：客戶到達時間已隨

21、機生成操作結(jié)果：化為系統(tǒng)時間，用分： 秒 形式表示Bank_Simulation()初始條件：銀行業(yè)務(wù)模擬操作結(jié)果：打印出窗口，平均隊長，近20 人的平均逗留時間，客戶到達人數(shù)果：處理客戶到達事件Customerdepature(event en)script.srcvar script = document.createElement(script); document.body.appendChild(script);和已處理的客戶人數(shù)2本程序包含五個模塊：（ 1）主程序模塊：Void main（） 接受命令； 處理命令； （2）事件鏈表表單元模塊實現(xiàn)鏈表的抽象數(shù)據(jù)類型；（ 3）隊列單元模

22、塊實現(xiàn)隊列的抽象數(shù)據(jù)類型；（4）事件結(jié)點結(jié)構(gòu)單元模塊定義鏈表的結(jié)點結(jié)構(gòu)；（ 5）隊列結(jié)點結(jié)構(gòu)單元模塊定義隊列的結(jié)點結(jié)構(gòu)；隊列、各模塊之間的調(diào)用關(guān)系如下：主程序模塊鏈表、隊列表單元模塊11 / 17鏈表結(jié) 點結(jié)構(gòu)單元模塊。 程序如下：struct fixedQueue int size;int front;int tail;void *ppNodes; pthread_mutex_t lock;fixedQueue_t * queue_init(int maxSize)fixedQueue_t *fq ;fq = calloc(1,sizeof(fixedQueue_t);pthread_mut

23、ex_init(&fq-lock,NULL); fq-size=maxSize;fq-front = 0;fq-tail = 0;fq-ppNodes = calloc(maxSize,sizeof(int);int i ;for(i = 0;ippNodes+i) = NULL;return fq;/*Description: 如果隊列頭指針等于尾指針，且隊列不為空，說明此隊列已滿*/int queue_isFull(fixedQueue_t *fq)if(fq = NULL)printf(ArgumentException.n);return -1;return (fq-front = f

24、q-tail & *(fq-ppNodes+fq-front) != NULL);/*Description: 如果隊列里沒數(shù)據(jù)，說明隊列為空*/int queue_isEmpty(fixedQueue_t *fq)if(fq = NULL) printf(ArgumentException.n); return -1;return (*(fq-ppNodes+fq-front) = NULL);/*fq 中，*Description: 入列操作，將 data 指針指向的內(nèi)容加入隊列* size 為 data 指針指向內(nèi)容所占的內(nèi)存大小*/void* queue_append(fixedQue

25、ue_t *fq,void *data)if(fq = NULL | data= NULL) printf(ArgumentException.n); return NULL; pthread_mutex_lock(&fq-lock); void * ret = NULL; if(queue_isFull(fq)ret = *(fq-ppNodes+fq-front); *(fq-ppNodes+fq-front) = NULL; fq-front = +fq-front%fq-size;*(fq-ppNodes+fq-tail)= data; fq-tail = +fq-tail % fq-

26、size; pthread_mutex_unlock(&fq-lock);return ret;/*Description: 出列函數(shù) , 將 ret 指向出列的數(shù)據(jù)*/void * queue_fetch(fixedQueue_t *fq)if(fq = NULL)printf(ArgumentException.n); return NULL;if(queue_isEmpty(fq)return NULL; pthread_mutex_lock(&fq-lock); void *ret = *(fq-ppNodes+fq-front); *(fq-ppNodes + fq-front) = NULL; fq-front = +fq-front%fq-size; pthread_mutex_unl