數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)題參考答案[]

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

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

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

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

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

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

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

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

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

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

11、E*p=(LNODE*)malloc(sizeof(LNODE);if(!p)exit(OVERFLOW);/*存儲(chǔ)分配失敗*/p-data=e;p-next=NULL;if(*hpt=NULL)*tpt=*hpt=p;else*tpt=(*tpt)-next=p;intDeQueue(LNODE*hpt,LNODE*tpt,QNODE*cp)/*鏈接隊(duì)列出隊(duì)*/LNODE*p=*hpt;if(*hpt=NULL)return1;/*隊(duì)空*/*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)/*等待隊(duì)列

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

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

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

16、應(yīng)依次排隊(duì)等候處理.3 .二叉樹的的應(yīng)用：設(shè)計(jì)一個(gè)表示家譜的二叉樹要求：采用一棵二叉樹表示一逐步形成家譜關(guān)系,對(duì)于給定的父親顯示所有的兒子.由于家譜為樹形,但不是一棵二叉樹,所以在存儲(chǔ)時(shí)要轉(zhuǎn)換成二叉樹的形式.規(guī)定：一個(gè)父親結(jié)點(diǎn)的左子樹表示母親結(jié)點(diǎn),母親結(jié)點(diǎn)的右子樹表示他們的所有兒子,例如,圖1是一個(gè)用二叉樹表示的家譜圖,與之對(duì)應(yīng)的傳統(tǒng)樹形圖家譜圖如圖2所示.這樣就將家譜樹轉(zhuǎn)換成C源程序二叉樹了,而二叉樹的操作是容易實(shí)現(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建立一個(gè)家

18、譜二叉機(jī)(以空格結(jié)尾):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(不存在這樣的父結(jié)點(diǎn)！n);return(btree);voiddisptree(BTreeBT)(BTreestackMaxSize,p;intlevelMaxSize2,top,n,i,width=4;if(BT!=NULL)(printf(n家譜凹入表示法：n);top=1;stacktop=BT;/*根結(jié)點(diǎn)入棧*/leveltop0=width;while(top0)(p=stacktop;/*退棧并凹入顯示該結(jié)點(diǎn)值*/其中n為顯示場(chǎng)寬,字符以右對(duì)齊顯示*/n=leveltop0;

21、for(i=1;iname);-)；for(i=n+1;iright!=NULL)top+;/*將右子樹根結(jié)點(diǎn)入棧*/stacktop=p-right;leveltop0=n+width;leveltop1=2;if(p-left!=NULL)/*顯示場(chǎng)寬增width*/top+;/*將左子樹根結(jié)點(diǎn)入棧*/stacktop=p-left;leveltop0=n+width;leveltop1=1;voidfindson(BTreebt)/*顯示場(chǎng)寬增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);)運(yùn)行結(jié)果建立一個(gè)家譜二叉機(jī)(以空格結(jié)尾)：姓名：張德妻子：陳氏父親：張德兒子：張文兒妻：劉氏父親：張德兒子：張武兒妻：王氏父親：張文兒子：張兵兒妻：李氏父親：張文

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

24、=0;printf(建立原始數(shù)序n);printf(t元素個(gè)數(shù)：)；scanf(%d,&n);while(in)printf(t第個(gè)元素：,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的元素進(jìn)行快速排序*/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(排序結(jié)果：)；disparr();m=1;printf(從大到小排序：n);quicksort(a,0,n-1,0);printf(排序結(jié)果：)；disparr();建立原始數(shù)序元素個(gè)數(shù)：10第1個(gè)元素：9第2個(gè)元素：4第3個(gè)元素：0第4個(gè)元素：2第5個(gè)元素：5第6個(gè)元素：3第7個(gè)元素：8第8個(gè)元素：7第9個(gè)元素：1第10個(gè)元素：6原來的次序：9402538716從小到大排次序：(1) 6402538719(2) 1402536789(3) 0142536789(4) 0142536789(5) 0132456789(6) 0123456789(7) 0123456789(8) 0123456789(9) 0123456789(10) 0123456789排序結(jié)果：0123456789從大到小排序：(1) 9123456780(2) 9123456780(3) 9823456710(4) 9823456710(5) 987