數(shù)據(jù)結構實驗題參考答案[]

1、【實驗題】1 .狐貍逮兔子圍繞著山頂有10個圓形排列的洞,狐貍要吃兔子,兔子說：“可以,但必須找到我,我就藏身于這十個洞中,你先到1號洞找,第二次隔1個洞(即3號洞)找,第三次隔2個洞(即6號洞)找,以后如此類推,次數(shù)不限.但狐貍從早到晚進進出出了1000次,仍沒有找到兔子.問兔子究竟藏在哪個洞里？(提示：這實際上是一個反復查找線性表的過程.)【數(shù)據(jù)描述】定義一個順序表,用具有10個元素順序表來表示這10個洞.每個元素分別表示圍著山頂?shù)囊粋€洞,下標為洞的編號.#defineLIST_INIT_SIZE10/線性表存儲空間的初始分配量typedefstructElemType*elem;/存儲空

2、間基址intlength;/當前長度intlistsize;/當前分配的存儲容量(以sizeof(ElemType)為單位)SqList;【算法描述】statusInitList_Sq(SqList&L)/構造一個線性表LL.elem=(ElemType)malloc(LIST_INIT_SIZE*sizeof(ElemType);If(!L.elem)returnOVERFLOW;/存儲分配失敗L.length=0;/空表長度為0L.listsize=LIST_INIT_SIZE;/初始存儲容量returnOK;/InitList_SqstatusRabbit(SqList&L)/構造狐貍逮

3、兔子函數(shù)intcurrent=0;/定義一個當前洞口號的記數(shù)器,初始位置為第一個洞口for(i=0;iLIST_INIT_SIZE;i+)L.elemi=1;/給每個洞作標記為1,表示狐貍未進之洞L.elemLIST_INIT_SIZE-1=L.elem0=0;/首先進入第一個洞,標記進過的洞為0.for(i=2;i=1000;i+)current=(current+i)%LIST_INIT_SIZE;實現(xiàn)順序表的循環(huán)引用L.elemi=0;/標記進過的洞為0/第二次隔1個洞找,第三次隔2個洞找,以后如此類推,經(jīng)過一千次printf(兔子可能藏在如下的洞中：)for(i=0;iLIST_INI

4、T_SIZE;i+)if(L.elemi=1)printf(“第個洞n,i+1);/輸出未進過的洞號returnOK;/end【C源程序】#include#include#defineOK1#defineOVERFLOW-2typedefintstatus;typedefintElemType;#defineLIST_INIT_SIZE10/*線性表存儲空間的初始分配量*/typedefstructElemType*elem;/*存儲空間基址*/intlength;/*當前長度*/intlistsize;/*當前分配的存儲容量(以sizeof(ElemType)為單位)*/SqList;sta

5、tusInitList_Sq(SqList*L)/*構造一個線性表L*/(*L).elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!(*L).elem)returnOVERFLOW;/*存儲分配失敗*/(*L).length=0;/*空表長度為0*/(*L).listsize=LIST_INIT_SIZE;/*初始存儲容量*/returnOK;/*InitList_Sq*/statusRabbit(SqList*L)/*構造狐貍逮兔子函數(shù)*/inti,current=0;/*定義一個當前洞口號的記數(shù)器,初始位置為第一個洞口*/

6、for(i=0;iLIST_INIT_SIZE;i+)(*L).elemi=1;/*給每個洞作標記為1,表示狐貍未進之洞*/(*L).elemLIST_INIT_SIZE-1=0;(*L).elem0=0;/*第一次進入第一個洞,標記進過的洞為0*/for(i=2;i=1000;i+)current=(current+i)%LIST_INIT_SIZE;/*實現(xiàn)順序表的循環(huán)引用*/(*L).elemcurrent=0;/*標記進過的洞為0*/*第二次隔1個洞找,第三次隔2個洞找,以后如此類推,經(jīng)過一千次*/printf(n兔子可能藏在如下的洞中：);for(i=0;iLIST_INIT_SIZ

7、E;i+)if(*L).elemi=1)printf(n此洞是第出洞,i+1);/*輸出未進過的洞號*/returnOK;voidmain()SqList*L;InitList_Sq(L);Rabbit(L);getch();【測試數(shù)據(jù)】最后的輸出結果為：2479【說明】本算法思路比擬簡單,采用了順序表表示圍著山頂?shù)?0個洞,首先對所有洞設置標志為1,然后通過1000次循環(huán),對每次所進之洞修改標志為0,最后輸出標志為1的洞.2 .銀行客戶某銀行有一個客戶辦理業(yè)務站,在單位時間內(nèi)隨機地有客戶到達,設每位客戶的業(yè)務辦理時間是某個范圍內(nèi)的隨機值.設只有一個窗口,一位業(yè)務人員,要求程序模擬統(tǒng)計在設定時

8、間內(nèi),業(yè)務人員的總空閑時間和客戶的平均等待時間.假定模擬數(shù)據(jù)已按客戶到達的先后順序依次存于某個正文數(shù)據(jù)文件中.對應每位客戶有兩個數(shù)據(jù),到達時間和需要辦理業(yè)務的時間.復習概念：與棧相對應,隊列是一種先進先出的線性表.它只允許在表的一端進行插入,而在另一端進行刪除元素.允許插入的一端稱隊尾,允許刪除的一端稱隊頭.插入與刪除分別稱為入隊與出隊.隊列示意圖見圖3-2:出隊ala2an-1an進隊KM【數(shù)據(jù)描述】typedefstructintarrive;inttreat;/客戶的信息結構QNODEtypedefstructnodeQNODEdata;Structnode*next;/隊列中的元素信息

9、LNODELNODE*front,*rear;/隊頭指針和隊尾指針【算法描述】設置統(tǒng)計初值；設置當前時鐘時間為0;翻開數(shù)據(jù)文件,準備讀；讀入第一位客戶信息于暫存變量中；do/約定每輪循環(huán),處理完一位客戶if等待隊列為空,并且還有客戶/等待隊列為空時累計業(yè)務員總等待時間；時鐘推進到暫存變量中的客戶的到達時間；暫存變量中的客戶信息進隊；讀取下一位客戶信息于暫存變量；累計客戶人數(shù)；從等待隊列出隊一位客戶；將該客戶的等待時間累計到客戶的總等待時間；設定當前客戶的業(yè)務辦理結束時間；while下一位客戶的到達時間在當前客戶處理結束之前暫存變量中的客戶信息進隊；讀取下一位客戶信息于暫存變量；時鐘推進到當前客

10、戶辦理結束時間；while還有未處理的客戶；計算統(tǒng)計結果,并輸出；【C源程序】#include#include#defineOVERFLOW-2typedefstructintarrive;inttreat;/*客戶的信息結構*/QNODE;typedefstructnodeQNODEdata;structnode*next;/*隊列中的元素信息*/LNODE;LNODE*front,*rear;/*隊頭指針和隊尾指針*/QNODEcurr,temp;charFname120;FILE*fp;voidEnQueue(LNODE*hpt,LNODE*tpt,QNODEe)/*隊列進隊*/LNOD

11、E*p=(LNODE*)malloc(sizeof(LNODE);if(!p)exit(OVERFLOW);/*存儲分配失敗*/p-data=e;p-next=NULL;if(*hpt=NULL)*tpt=*hpt=p;else*tpt=(*tpt)-next=p;intDeQueue(LNODE*hpt,LNODE*tpt,QNODE*cp)/*鏈接隊列出隊*/LNODE*p=*hpt;if(*hpt=NULL)return1;/*隊空*/*cp=(*hpt)-data;*hpt=(*hpt)-next;if(*hpt=NULL)*tpt=NULL;free(p);return0;voidm

12、ain()intdwait=0,clock=0,wait=0,count=0,have=0,finish;printf(nenterfilename:);scanf(%s,Fname);/*輸入裝客戶模擬數(shù)據(jù)的文件的文件名*/if(fp=fopen(Fname,r)=NULL)/*翻開數(shù)據(jù)文件*/printf(cannotopenfile%s,Fname);return;front=NULL;rear=NULL;have=fscanf(fp,%d%s,&temp.arrive,&temp.treat);do/*約定每輪循環(huán),處理一位客戶*/if(front=NULL&have=2)/*等待隊列

13、為空,但還有客戶*/*/dwait+=temp.arrive-clock;/*累計業(yè)務員總等待時間*/clock=temp.arrive;/*時鐘推進到暫存變量中的客戶的到達時間EnQueue(&front,&rear,temp);/*暫存變量中的客戶信息進隊*/have=fscanf(fp,%d%d,&temp.arrive,&temp.treat);count+;/*累計客戶人數(shù)*/DeQueue(&front,&rear,&curr);/*出隊一位客戶信息*/wait+=clock-curr.arrive;/*累計到客戶的總等待時間*/finish=clock+curr.treat;/*

14、設定業(yè)務辦理結束時間；*/while(have=2&temp.arrive=finish)/*下一位客戶的到達時間在當前客戶處理結束之前*/EnQueue(&front,&rear,temp);/*暫存變量中的客戶信息進隊*/have=fscanf(fp,%d%d,&temp.arrive,&temp.treat);clock=finish;/*時鐘推進到當前客戶辦理結束時間*/while(have=2|front!=NULL);printf(結果：業(yè)務員等待時間dn客戶平均等待時間%fn,dwait,(double)wait/count);printf(模擬總時間：%dn客戶人數(shù)：%d,n總

15、等待時間：dn,clock,count,wait);getch();/*main_end*/【測試藪據(jù)】設數(shù)據(jù)裝在一個數(shù)據(jù)文件data.dat中,內(nèi)容為：106138顯示結果為：enterfilename:data.datenterfilename:data.dat結果：業(yè)務員等待時間10客戶平均等待時間25.500000模擬總時間：72,客戶人數(shù)：2,總等待時間：51【說明】在計算程序中,程序按模擬環(huán)境中的事件出同順序逐一處理事件：當一個事件結束時,下一個事件隔一段時間才發(fā)生,那么程序邏輯的模擬時鐘立即推進到下一事件的發(fā)生時間；如一個事件還未處理結束之前,另有其他事件等待處理,那么這些事件就

16、應依次排隊等候處理.3 .二叉樹的的應用：設計一個表示家譜的二叉樹要求：采用一棵二叉樹表示一逐步形成家譜關系,對于給定的父親顯示所有的兒子.由于家譜為樹形,但不是一棵二叉樹,所以在存儲時要轉(zhuǎn)換成二叉樹的形式.規(guī)定：一個父親結點的左子樹表示母親結點,母親結點的右子樹表示他們的所有兒子,例如,圖1是一個用二叉樹表示的家譜圖,與之對應的傳統(tǒng)樹形圖家譜圖如圖2所示.這樣就將家譜樹轉(zhuǎn)換成C源程序二叉樹了,而二叉樹的操作是容易實現(xiàn)的.#include#include#include#defineMaxWidth40#defineMaxSize30typedefstructtreenodecharname1

17、0;structtreenode*left,*right;*BTree;BTreefindfather(BTreep,charxm)BTreebt;if(p=NULL)return(NULL);elseif(strcmp(p-name,xm)=0)return(p);elsebt=findfather(p-left,xm);if(bt!=NULL)return(bt);elsereturn(findfather(p-right,xm);BTreecreatree()intn,m,i,contin=1,first=1;charxm10;BTreebtree,s,t,p;printf(n建立一個家

18、譜二叉機(以空格結尾):n);while(contin)if(first=1)btree=(BTree)malloc(sizeof(structtreenode);printf(t姓名：)；gets(btree-name);btree-right=NULL;s=(BTree)malloc(sizeof(structtreenode);printf(t妻子：)；gets(s-name);s-left=s-right=NULL;btree-left=s;first=0;elseprintf(t父親：)；gets(xm);if(strcmp(xm,)=0)contin=0;else(p=findfa

19、ther(btree,xm);if(p!=NULL)(p=p-left;if(p=NULL)/*沒有妻子*/printf(t沒有兒子(由于沒有妻子)n);else(while(p-right!=NULL)p=p-right;s=(BTree)malloc(sizeof(structtreenode);s-right=NULL;p-right=s;printf(t兒子：);gets(s-name);printf(t兒妻：);gets(xm);if(strcmp(xm,)!=0)(t=(BTree)malloc(sizeof(structtreenode);strcpy(t-name,xm);t-

20、left=t-right=NULL;s-left=t;elses-left=NULL;elseprintf(不存在這樣的父結點！n);return(btree);voiddisptree(BTreeBT)(BTreestackMaxSize,p;intlevelMaxSize2,top,n,i,width=4;if(BT!=NULL)(printf(n家譜凹入表示法：n);top=1;stacktop=BT;/*根結點入棧*/leveltop0=width;while(top0)(p=stacktop;/*退棧并凹入顯示該結點值*/其中n為顯示場寬,字符以右對齊顯示*/n=leveltop0;

21、for(i=1;iname);-)；for(i=n+1;iright!=NULL)top+;/*將右子樹根結點入棧*/stacktop=p-right;leveltop0=n+width;leveltop1=2;if(p-left!=NULL)/*顯示場寬增width*/top+;/*將左子樹根結點入棧*/stacktop=p-left;leveltop0=n+width;leveltop1=1;voidfindson(BTreebt)/*顯示場寬增width*/charxm10;BTreep;printf(n查找指定父親的所有兒子n);printf(父親：);gets(xm);p=findf

22、ather(bt,xm);if(p=NULL)printf(不存在$的父親！n,xm);elsep=p-left;p=p-right;if(p=NULL)printf(%s沒有兒子！n,xm);elseprintf(%s有以下兒子！nt);while(p!=NULL)printf(%8s,p-name);p=p-right;)main()(BTreebt;bt=creatree();disptree(bt);findson(bt);)運行結果建立一個家譜二叉機(以空格結尾)：姓名：張德妻子：陳氏父親：張德兒子：張文兒妻：劉氏父親：張德兒子：張武兒妻：王氏父親：張文兒子：張兵兒妻：李氏父親：張文

23、兒子：張強兒妻：父親：張武兒子：張華兒妻：父親：家譜凹入表示法：張德陳氏張文劉氏張兵李氏一張強一張武王氏張華一查找指定父親的所有兒子父親：張德有以下兒子！張武張文4 .最短路徑假設有n個城市組成一個公路網(wǎng)(有向的),并用代價鄰接矩陣表示該網(wǎng)絡,編寫一個指定城市v到其他各城市的最短路徑的函數(shù).方法：直接采用Dijkstra算法,略.5 .排序?qū)τ趯τ谳斎氲臄?shù)字按從小到大和從大到小兩種順序進行排序,并顯示中間排序過程.提示可以采用快速排序方法進行數(shù)字的兩種排序.C源程序#include#defineMAX100voiddisparr();intaMAX,n,m;voidcreatarr()inti

24、=0;printf(建立原始數(shù)序n);printf(t元素個數(shù)：)；scanf(%d,&n);while(in)printf(t第個元素：,i+1);scanf(%d,&ai);i+;intcmp(intlval,intrval,intorder)if(order=1)if(lvalrval)return(1);elsereturn(0);voidquicksort(intx,intl,intr,intorder)/*把xl至xr的元素進行快速排序*/inti=l,j=r,k,temp;temp=xl;while(ij)while(ij&cmp(temp,xj,order)j-;/*/if(i

25、j)xi=xj;i+;while(ij&cmp(xi,temp,order)i+;/*/if(ij)xj=xi;j-;xi=temp;printf(t(%d),m+);for(k=0;kn;k+)if(k=l)printf();if(k=i)printf();printf(%d,xk);if(k=i)printf();if(k=r)printf();printf(n);if(li)quicksort(x,l,i-1,order);if(ir)quicksort(x,j+1,r,order);voiddisparr()inti;for(i=0;in;i+)printf(%d,ai);printf

26、(nn);main()creatarr(a);m=1;printf(n原來的次序：);disparr();printf(從小到大排次序：n);quicksort(a,0,n-1,1);printf(排序結果：)；disparr();m=1;printf(從大到小排序：n);quicksort(a,0,n-1,0);printf(排序結果：)；disparr();建立原始數(shù)序元素個數(shù)：10第1個元素：9第2個元素：4第3個元素：0第4個元素：2第5個元素：5第6個元素：3第7個元素：8第8個元素：7第9個元素：1第10個元素：6原來的次序：9402538716從小到大排次序：(1) 6402538719(2) 1402536789(3) 0142536789(4) 0142536789(5) 0132456789(6) 0123456789(7) 0123456789(8) 0123456789(9) 0123456789(10) 0123456789排序結果：0123456789從大到小排序：(1) 9123456780(2) 9123456780(3) 9823456710(4) 9823456710(5) 987