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

1、【實(shí)驗(yàn)題實(shí)驗(yàn)題】1狐貍逮兔子狐貍逮兔子圍繞著山頂有10個(gè)圓形排列的洞，狐貍要吃兔子，兔子說：“可以，但必須找到我，我就藏身于這十個(gè)洞中，你先到１號(hào)洞找，第二次隔１個(gè)洞（即3號(hào)洞）找，第三次隔２個(gè)洞（即6號(hào)洞）找，以后如此類推，次數(shù)不限。”但狐貍從早到晚進(jìn)進(jìn)出出了1000次，仍沒有找到兔子。問兔子究竟藏在哪個(gè)洞里？（提示：這實(shí)際上是一個(gè)反復(fù)查找線性表的過程。）【數(shù)據(jù)描述】定義一個(gè)順序表，用具有10個(gè)元素順序表來表示這10個(gè)洞。每個(gè)元素分別

2、表示圍著山頂?shù)囊粋€(gè)洞，下標(biāo)為洞的編號(hào)。#defineLIST_INIT_SIZE10線性表存儲(chǔ)空間的初始分配量typedefstructElemTypeelem存儲(chǔ)空間基址intlength當(dāng)前長(zhǎng)度intlistsize當(dāng)前分配的存儲(chǔ)容量（以sizeof(ElemType)為單位）SqList【算法描述】statusInitList_Sq(SqListIf(!L.elem)returnOVERFLOW存儲(chǔ)分配失敗L.length=0空表

3、長(zhǎng)度為0L.listsize=LIST_INIT_SIZE初始存儲(chǔ)容量returnOKInitList_SqstatusRabbit(SqList定義一個(gè)當(dāng)前洞口號(hào)的記數(shù)器，初始位置為第一個(gè)洞口f(i=0i#include#defineOK1#defineOVERFLOW2typedefintstatustypedefintElemType#defineLIST_INIT_SIZE10線性表存儲(chǔ)空間的初始分配量后順序依次存于某個(gè)正文數(shù)據(jù)

4、文件中。對(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ì)列示意圖見圖32：出隊(duì)←a1a2……an1←an進(jìn)隊(duì)隊(duì)頭隊(duì)尾【數(shù)據(jù)描述】typedefstructintarriveinttreat客戶的信息結(jié)構(gòu)QNODE；typedefstructnodeQNOD

5、EdataStructnodenext隊(duì)列中的元素信息LNODELNODEfrontrear隊(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ì)一位