數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告目錄散列表的設(shè)計(jì)與實(shí)現(xiàn)3（一）設(shè)計(jì)內(nèi)容簡(jiǎn)介3（二）算法設(shè)計(jì)說(shuō)明4（三）測(cè)試結(jié)果8迷宮9（一）設(shè)計(jì)題目：迷宮9（二）需求分析：9（三）概要設(shè)計(jì)：9（四）詳細(xì)設(shè)計(jì)11（五）調(diào)試分析、測(cè)試結(jié)果14（六）設(shè)計(jì)心得體會(huì)15猴子選大王20（一）設(shè)計(jì)題目：猴子選大王20（二）需求分析：20（三）概要設(shè)計(jì)：20（四）詳細(xì)設(shè)計(jì)：21（五）調(diào)試分析、測(cè)試結(jié)果24（六）設(shè)計(jì)心得體會(huì)25（七）附錄25基數(shù)排序27（一）設(shè)計(jì)題目：基數(shù)排序27（二）需求分析：27（三）概要設(shè)計(jì)：27（四）詳細(xì)設(shè)計(jì)：27（五）調(diào)試分析、測(cè)試結(jié)果:30（六）附錄:31校園導(dǎo)游咨詢：34（一）設(shè)計(jì)題目:校園導(dǎo)游咨詢34（三

2、）概要設(shè)計(jì)：35（四）詳細(xì)設(shè)計(jì)：35（五）調(diào)試分析、測(cè)試結(jié)果：39（六）設(shè)計(jì)心得體會(huì)：41（七）附源碼：41藝術(shù)品搬來(lái)搬去45（一）設(shè)計(jì)內(nèi)容簡(jiǎn)介：45（二）算法設(shè)計(jì)說(shuō)明：46（三） 測(cè)試結(jié)果：47（四）分析與探討48大數(shù)運(yùn)算48（一）設(shè)計(jì)內(nèi)容簡(jiǎn)介48（二）算法設(shè)計(jì)說(shuō)明：49（三）測(cè)試結(jié)果52災(zāi)區(qū)救災(zāi)53（一）設(shè)計(jì)內(nèi)容簡(jiǎn)介：53（二）算法設(shè)計(jì)說(shuō)明：54（三）測(cè)試結(jié)果：5556（四）分析與探討56最小生成樹(shù)56（一）設(shè)計(jì)題目：最小生成樹(shù)56（二）需求分析：56（三）概要設(shè)計(jì)：57（四）詳細(xì)設(shè)計(jì)：57（五） 調(diào)試分析，測(cè)試結(jié)果：59（六） 設(shè)計(jì)心得體會(huì):59（七）附錄:60散列表的設(shè)計(jì)與實(shí)現(xiàn)（一）設(shè)

3、計(jì)內(nèi)容簡(jiǎn)介題目：散列表的設(shè)計(jì)與實(shí)現(xiàn)任務(wù)：設(shè)計(jì)散列表實(shí)現(xiàn)電話號(hào)碼查找系統(tǒng)。要求：（1) 設(shè)每個(gè)記錄有下列數(shù)據(jù)項(xiàng)：用戶名、電話號(hào)碼、地址；（2) 從鍵盤(pán)輸入各記錄，以用戶名（漢語(yǔ)拼音形式）為關(guān)鍵字建立散列表；（3) 采用一定的方法解決沖突；（4) 查找并顯示給定電話號(hào)碼的記錄； （二）算法設(shè)計(jì)說(shuō)明在設(shè)計(jì)和實(shí)現(xiàn)哈希表時(shí)需要用到哈希函數(shù)，這是本次的重點(diǎn)，其他的輸入和查找可以通過(guò)以前學(xué)到的順序存儲(chǔ)結(jié)構(gòu)的相關(guān)知識(shí)進(jìn)行解決。先看一下哈希函數(shù)的設(shè)計(jì)和實(shí)現(xiàn)，由于定義的名字是20個(gè)字符，則在輸入后可以很容易知道它的第一個(gè)字母的相對(duì)應(yīng)的阿克什碼，利用阿克什碼%哈希表的長(zhǎng)度就應(yīng)該得到它的位置。然而對(duì)于一些數(shù)據(jù)可能會(huì)有

4、發(fā)生一些沖突，這就需要我們解決沖突，對(duì)于這個(gè)沖突我是將待處理的沖突記錄后移一位，若還沖突則還后移直到有空位或者記錄滿為止。再看一下按照電話號(hào)碼查找時(shí)，由于不是按照電話號(hào)碼排序進(jìn)行的在查找電話號(hào)碼時(shí)只能是從頭到尾進(jìn)行逐一檢查對(duì)比，若對(duì)應(yīng)的電話號(hào)碼相同則輸出其他的信息，直到最后仍沒(méi)有則輸出相關(guān)提示信息。其相應(yīng)的數(shù)據(jù)結(jié)構(gòu)如下：typedef char keytype20;typedef structkeytype name;/姓名int teleno; /電話號(hào)碼char address100;/家庭住址rectype;/記錄的類型typedef structrectype recordm;/哈希表

5、中有m個(gè)記錄int flagm;/標(biāo)記，若有記錄則標(biāo)記為1，否則為0int currentsize;/當(dāng)前哈希表中已被占用的個(gè)數(shù)hashitem;其中調(diào)用的相關(guān)函數(shù)：inithash(h);/初始化哈希表，將記錄清空inputrecord(h);/想哈希表中輸入記錄信息，需要調(diào)用到上述哈希處理printrecord(h);/輸出已經(jīng)輸入的信息findrecord(h);/根據(jù)電話號(hào)碼查找記錄saverecord(h);/保存輸入到程序中的記錄到當(dāng)前文件夾中對(duì)于整程序則有如下流程圖：在輸入信息時(shí)為了解決沖突，需要設(shè)計(jì)一個(gè)哈希函數(shù)，下面是我自己設(shè)計(jì)的哈希函數(shù)：bool hash(hashitem

6、&h,rectype inrecord)int key=(int)inr0%m;while(true)if (h.flagkey=0)/如果原記錄不存在，則進(jìn)行賦值h.flagkey=1;h.recordkey=inrecord;return true; else/原記錄存在/if(h.recordkey.teleno=inrecord.teleno)if(strcmp(h.recordk,inr)=0)cout哈希表中記錄h.recordk已存在了endl;return false;elsekey+;/coutjkjk;考慮

7、到?jīng)]有輸入數(shù)據(jù)時(shí)，不能進(jìn)行查找和輸出，所以要在調(diào)用檢查這種情況，這樣就可以避免不必要的錯(cuò)誤。if(h.currentsize=0)cout記錄為空，請(qǐng)輸如信息endl;return false;輸入數(shù)據(jù)時(shí)也需要考慮是否已經(jīng)輸入過(guò)，為了解決這個(gè)問(wèn)題，在調(diào)用進(jìn)行哈希處理時(shí)就需要在附加在已經(jīng)發(fā)生沖突的位置進(jìn)行比較，若有相同記錄則輸入過(guò)則給予相關(guān)提示。（三）測(cè)試結(jié)果 在沒(méi)有輸入任何數(shù)據(jù)的情況下，會(huì)有提示信息按照電話號(hào)碼查找相關(guān)記錄（四）分析與探討在設(shè)計(jì)哈希表時(shí)考慮到便捷和操作的方便（因?yàn)檩斎胄彰麜r(shí)必須至少輸入一個(gè)字母），利用首字母的阿克什碼，然而這樣的發(fā)生沖突的概率會(huì)很大，這就需要一個(gè)更不易發(fā)生沖突的

8、哈希函數(shù)，其中一種哈希函數(shù)，就是將姓名的每個(gè)字符的阿克什碼的值相加在進(jìn)行處理，這樣較我的方法更科學(xué)，也更不易發(fā)生沖突。 對(duì)于一個(gè)好的哈希函數(shù)在時(shí)間和空間復(fù)雜度上不是很高，同時(shí)發(fā)生沖突的機(jī)會(huì)較少，這樣的函數(shù)才是一個(gè)真正的好函數(shù)。迷宮 （一）設(shè)計(jì)題目：迷宮（二）需求分析：任務(wù)：可以輸入一個(gè)任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出；要求：在上交資料中請(qǐng)寫(xiě)明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；（三）概要設(shè)計(jì)： 在迷宮設(shè)計(jì)中，由于不能使用遞歸則可以借助棧來(lái)實(shí)現(xiàn)在迷宮中的前進(jìn)和后退。同時(shí)在還需要設(shè)計(jì)

9、迷宮的大小、迷宮的出入口、根據(jù)輸入的入口來(lái)尋找迷宮的出口，并把路徑輸出來(lái)。在這個(gè)編程中由于不知道所走路勁步數(shù)，所以采用了鏈?zhǔn)綏?shí)現(xiàn)每一步的移動(dòng)，若找到出路則前進(jìn)否則返回下一步改變方向來(lái)實(shí)現(xiàn)相關(guān)的移動(dòng)，所以棧在其間起到了工具作用。在設(shè)計(jì)迷宮大小和出入口時(shí)，采用的是根據(jù)操作者實(shí)現(xiàn)的，但迷宮的具體路障和通道是隨機(jī)實(shí)現(xiàn)的。當(dāng)然，重點(diǎn)是如何從出口來(lái)找出口。求迷宮的一條通路的偽碼如下：設(shè)當(dāng)前初始位置為出口：do 若當(dāng)前位置可通，則 將該位置插入到棧頂；/納入路徑 若該位置為出口位置。則結(jié)束當(dāng)前程序；/求得的路徑放在棧中 否則切換當(dāng)前位置的東臨位置（即向右）為新的當(dāng)前的位置； 否則 若棧不為空且棧頂元素尚有

10、其他位置未被探索，則設(shè)定新的當(dāng)前位置為沿著順時(shí)針旋轉(zhuǎn)得到的棧頂位置的下一個(gè)臨快； 若棧不為空且棧頂位置的四周均不通 則刪去棧頂元素；/后退一步，從路徑中刪去該通塊 若棧不空，則重新測(cè)試新的棧頂位置，直到找到一個(gè)可通的相鄰塊或出棧至棧空； /否則while(棧不為空)本程序的模塊 主程序從main()函數(shù)中進(jìn)行，包括輸入迷宮的大小等信息，然后調(diào)用迷宮模塊，在迷宮模塊中也調(diào)用了棧的模塊。棧模塊實(shí)現(xiàn)棧抽象數(shù)據(jù)類型迷宮模塊實(shí)現(xiàn)迷宮抽象數(shù)據(jù)類型各模塊之間的關(guān)系如下： 主程序模塊 迷宮模塊棧模塊（四）詳細(xì)設(shè)計(jì) 1坐標(biāo)的位置類型： typedef struct int r; int c;postype;2.

11、迷宮類型：typedef structint col,row;/迷宮的大小int arrranglerangle; /0表示障礙，1表示是可走的通道，-1表示外界的圍墻 /2表示已經(jīng)走過(guò)， 3表示已經(jīng)知道其不能通過(guò)mazetype;void initmaze(mazetype &m,int col,int row)/按照用戶的輸入的行數(shù)row和列數(shù)col列的二維數(shù)組（元素值為1或0）/設(shè)置迷宮的錯(cuò)初值，加上邊緣的一圈的值 void printmaze(mazetype m)/根據(jù)已經(jīng)進(jìn)行二維數(shù)組的標(biāo)記值來(lái)輸出迷宮（或者其通路）bool pass(mazetype m,postype pos)/

12、求解迷宮m中，從start到end的一條路徑/若存在則返回true，否則返回falsestack s;initstack(s);postype curpos=start;/設(shè)置當(dāng)前坐標(biāo)為入口位置；int curstep=1; /當(dāng)前的步數(shù)bool find=false; /是否找到出口elemtype e;do if(pass(m,curpos)/如果當(dāng)前位置可以通過(guò)（不是障礙物且未曾留下足跡） footprint(m,curpos);/在當(dāng)前位置標(biāo)記為2 e.step=1; e.seat=curpos; e.di=1;/初始化為向東臨位置移動(dòng)（即向右） push(s,e);/將已經(jīng)周的的放入

13、棧中 if(curpos.c=end.c&curpos.r=end.r)/如果找到了出口則終止，并返回true find=true; return find; else/在其東臨位置上移動(dòng)，當(dāng)前步數(shù)加一 curpos=nextpos(curpos,1); curstep+; else/當(dāng)前位置不能通過(guò) if(!stackempty(s) pop(s,e);/將已經(jīng)走過(guò)的最近位置彈出，數(shù)據(jù)保存在e中 while(e.di=4&!(stackempty(s)/當(dāng)方向改變一周后仍不能找到可通過(guò)的路徑 markprint(m,e.seat);/留下不能通過(guò)的標(biāo)記 pop(s,e);/刪除站定元素 cu

14、rstep-; /while if(e.di4)/不能通過(guò)則改變方向 e.di+;/方向順時(shí)針改變一下 push(s,e); curpos = nextpos(e.seat,e.di); /求下一個(gè)節(jié)點(diǎn) /if /if /elsewhile(!stackempty(s)&!find);/(!stackempty(s)&!find);/當(dāng)棧不為空且沒(méi)有找到出口return false;/沒(méi)有找到出口則返回false 從入口口到出口的查找的流程圖（五）調(diào)試分析、測(cè)試結(jié)果 （1）由于是不確定的步驟，采用的是易于操作的鏈?zhǔn)綏＃@樣就不免了時(shí)間和空間的浪費(fèi)。 （2）對(duì)于設(shè)計(jì)迷宮，可能會(huì)覺(jué)得會(huì)很繁瑣，剛開(kāi)

15、始也是自己設(shè)計(jì)迷宮圖，但由于是隨機(jī)設(shè)定迷宮的大小這就需要利用隨機(jī)數(shù)來(lái)設(shè)計(jì)一個(gè)迷宮圖。而利用%運(yùn)算則可以解決這個(gè)問(wèn)題，因?yàn)樵谠O(shè)置迷宮數(shù)組時(shí)，1就代表通道，而0就是障礙，隨意一個(gè)隨機(jī)數(shù)%2得到的就是0或者1就可以自由設(shè)計(jì)迷宮了。 （3）來(lái)利用到進(jìn)出棧時(shí)為計(jì)算進(jìn)出棧的情況，特設(shè)定了curstep來(lái)調(diào)試程序的執(zhí)行。那下面就介紹一下設(shè)計(jì)的迷宮界面情況： （六）設(shè)計(jì)心得體會(huì) 在知識(shí)方面,在設(shè)計(jì)迷宮時(shí)需要用到一些基本的如棧的相關(guān)信息，來(lái)解決不能使用遞歸的問(wèn)題，遞歸在使用過(guò)程中雖然簡(jiǎn)介但不易理解通過(guò)棧的使用來(lái)加強(qiáng)我們對(duì)遞歸的使用。 在對(duì)問(wèn)題的理解上我們通過(guò)對(duì)相關(guān)知識(shí)的理解和認(rèn)識(shí)，來(lái)解決一些實(shí)際問(wèn)題。附： *迷

16、宮的相關(guān)信息*/#define rangle 100typedef structint col,row;/int arrranglerangle; /0表示障礙，1表示是可走的通道，-1表示外界的圍墻 /2表示已經(jīng)走過(guò)， 3表示已經(jīng)知道其不能通過(guò)mazetype;void initmaze(mazetype &m,int col,int row)/按照用戶的輸入的行數(shù)row和列數(shù)col列的二維數(shù)組（元素值為1或0）/設(shè)置迷宮的錯(cuò)初值，加上邊緣的一圈的值m.col=col;m.row=row;int i;/根據(jù)隨機(jī)產(chǎn)生數(shù)進(jìn)行初始化這個(gè)二維數(shù)組for(i=1;im.row+2;i+)for(int

17、 j=1;jm.col+2;j+)/srand(time(0);int n=rand()%101+100;m.arrij=n%2;/得到的值是1或者0，即恰好是路或是通道/圍墻的標(biāo)記for(i=0;im.col+2;i+)m.arr0i=-1;m.arrm.row+1i=-1;for(i=0;im.row+2;i+)m.arri0=-1;m.arrim.col+1=-1;void printmaze(mazetype m)/根據(jù)已經(jīng)進(jìn)行二維數(shù)組的標(biāo)記值來(lái)輸出迷宮（或者其通路）int i,j;for(i = 0; i m.row+2; i+) for(j = 0; j m.col+2; j+)

18、if(m.arrij = 0) cout; /障礙，在dos界面上是白色的else if(m.arrij =-1)cout;/圍墻else if(m.arrij =2)cout; else cout ; coutn; bool pass(mazetype m,postype pos)/若在迷宮m中，當(dāng)前位置pos不是障礙物0，不是圍墻-1，以前沒(méi)有經(jīng)過(guò)2且不是不可通過(guò)3 則可以通過(guò)，并返回trueif(m.arrpos.rpos.c!=0&m.arrpos.rpos.c!=-1&m.arrpos.rpos.c!=2&m.arrpos.rpos.c!=2&m.arrpos.rpos.c!=3)r

19、eturn true;else return false;void footprint(mazetype &m,postype pos)/在迷宮中的pos的位置留下足跡，證明已經(jīng)經(jīng)過(guò)這個(gè)位置m.arrpos.rpos.c=2;void markprint(mazetype &m,postype pos)/在迷宮的pos位置，留下不能通過(guò)的標(biāo)記m.arrpos.rpos.c=3;postype nextpos(postype curpos, int dir) /根據(jù)不同的方向來(lái)進(jìn)行移動(dòng)postype returnpos; switch (dir) case 1:/向右 returnpos.r=c

20、urpos.r; returnpos.c=curpos.c+1; break; case 2:/向下 returnpos.r=curpos.r+1; returnpos.c=curpos.c; break; case 3:/向左 returnpos.r=curpos.r; returnpos.c=curpos.c-1; break; case 4:/向上 returnpos.r=curpos.r-1; returnpos.c=curpos.c; break; return returnpos;void main()mazetype m;int col,row;postype start,end

21、;loop:coutrow;coutcol;initmaze(m,col,row);cout迷宮圖：n;printmaze(m);coutstart.rstart.c;coutend.rend.c;if(start.rm.row|start.cm.col|start.r=0|start.c=0|end.rm.row|end.cm.col|end.r=0|end.c=0)/查看輸入數(shù)據(jù)的準(zhǔn)確性cout輸出有誤！n;else if(mazepath(m,start,end)/若找到了相關(guān)路徑則輸出路徑信息printmaze(m);else /如果沒(méi)有找到相關(guān)路徑則輸出提示信息cout沒(méi)有可通的出路

22、n;char ch;coutch;if(ch=y|ch=y)goto loop;else if (ch=n|ch=n)return ;猴子選大王（一）設(shè)計(jì)題目：猴子選大王（二）需求分析：任務(wù)：一堆猴子都有編號(hào)，編號(hào)是1，2，3 .m ,這群猴子（m個(gè)）按照1-m的順序圍坐一圈，從第1開(kāi)始數(shù)，每數(shù)到第n個(gè)，該猴子就要離開(kāi)此圈，這樣依次下來(lái)，直到圈中只剩下最后一只猴子，則該猴子為大王。要求：（注：分別順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)）輸入數(shù)據(jù)：輸入m,n。 m,n 為整數(shù)，nm ? 1 : i+1);（m表示猴子的個(gè)數(shù)），這樣首尾便可以相連，對(duì)于已經(jīng)出列的猴子還要給予標(biāo)記，另外需要借助一個(gè)計(jì)時(shí)器來(lái)表示間

23、隔數(shù)，在經(jīng)過(guò)已經(jīng)出列的的猴子時(shí)不予計(jì)數(shù)。2 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)的約瑟夫環(huán)是通過(guò)創(chuàng)建循環(huán)鏈表來(lái)實(shí)現(xiàn)的，直至只剩下一個(gè)猴子時(shí)就輸出有關(guān)猴子的信息。鏈?zhǔn)郊s瑟夫可以動(dòng)態(tài)分配結(jié)點(diǎn)，同時(shí)可以較容易地實(shí)現(xiàn)循環(huán)結(jié)構(gòu)，在每次猴子出列時(shí)就把這個(gè)結(jié)點(diǎn)給刪除了，這樣在數(shù)間隔數(shù)時(shí)就不用再進(jìn)行計(jì)數(shù)。主程序所以總程序的控制流程圖為： 順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)退出 （四）詳細(xì)設(shè)計(jì)： 順序存儲(chǔ)： typedef struct int no;/序號(hào)int flag;/標(biāo)記 1表示尚未出圈 0表示已經(jīng)出圈monkey2; 其流程圖：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：typedef struct nodeint no;node *next;monke

24、y,list;采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)可以利用循環(huán)鏈表，這樣就可以很容易實(shí)現(xiàn)約瑟夫環(huán)。猴子選大王的關(guān)鍵函數(shù)如下：node* creat(int m)/創(chuàng)建一個(gè)含有m個(gè)結(jié)點(diǎn)的循環(huán)鏈表，使得第m個(gè)的next指針指向第一個(gè)void trave(node *p,int n)/在循環(huán)鏈表中報(bào) n 的猴子出列,直至最后一個(gè)被輸出int i;node *q=p; /cout出列順序：next!=p)/當(dāng)循環(huán)鏈表不是只剩下一個(gè)結(jié)點(diǎn)for (i=1;inext;if (p-next!=p) /不是只剩下一個(gè)時(shí)q=p-next;/coutnonext=q-next;i+;delete q;p=p-next;/while

25、coutn最終的猴王：nonext!=p) 。輸入猴子的總數(shù)和間隔數(shù)，最后輸出最后的大王的序號(hào)。（六）設(shè)計(jì)心得體會(huì)猴子選大王就是約瑟夫環(huán)的應(yīng)用的實(shí)例，且是必須用兩種存儲(chǔ)結(jié)構(gòu)。在利用順序存儲(chǔ)時(shí)可以借助輔助結(jié)構(gòu)體標(biāo)記每一個(gè)猴子的序號(hào)和是否出列，然后按照while(jm ? 1 : i+1);j+=jophusi.flag; /若已出圈則 +0 就意味著跳過(guò)來(lái)實(shí)現(xiàn)循環(huán)。這樣就可以很容易來(lái)將數(shù)組循環(huán)化。（七）附錄利用順序存儲(chǔ)結(jié)構(gòu)void monkeyarray() int i,j,n,m;coutm;monkey2 *jophus=new monkey2m+1;/動(dòng)態(tài)分配m+1個(gè)數(shù)for( i=1;i

26、=m;i+)jophusi.no=i;jophusi.flag=1;int space;coutspace;i=1,j=1,n=0;/i=1表示從第一個(gè)開(kāi)始報(bào)數(shù)，j=1表示默認(rèn) /cout出圈序列為:endl;while(true)while(jm ? 1 : i+1);j+=jophusi.flag; /若已出圈則 +0 就意味著跳過(guò)/cout jophusi.no;jophusi.flag=0;/出圈就標(biāo)記一下n+;/用于標(biāo)記出圈猴子的個(gè)數(shù)/if(n%10=0) coutendl;/每10個(gè)一行if (n=m)cout最終選出的大王為：jophusi.noendl;break;j=0;co

27、utendl;基數(shù)排序（一）設(shè)計(jì)題目：基數(shù)排序（二）需求分析：假設(shè)有n個(gè)待排序記錄，記錄ri的關(guān)鍵字為keyi, keyi由d位十進(jìn)制數(shù)字組成，即keyi=ki1 ki2 ki3 kid ,試分別采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)基數(shù)排序。（提示：為提高基數(shù)排序效率，采用順序儲(chǔ)結(jié)構(gòu)的方式可以仿造稀疏矩陣轉(zhuǎn)置中的交換方法實(shí)現(xiàn)。（三）概要設(shè)計(jì)：基數(shù)排序是一種對(duì)多關(guān)鍵字的排序，是先從最低位的關(guān)鍵字開(kāi)始的進(jìn)行排序，再將，然后在對(duì)高一位的進(jìn)行排序，依次重復(fù)，直至到最高位即可，這樣便成了一個(gè)有序序列。這個(gè)程序又有分三個(gè)模塊：鏈?zhǔn)交鶖?shù)排序、順序結(jié)構(gòu)基數(shù)排序和主程序。（四）詳細(xì)設(shè)計(jì)：基數(shù)排序就是在對(duì)數(shù)字排序時(shí)

28、，先將數(shù)字低位對(duì)齊，再在每個(gè)相同位置對(duì)應(yīng)的數(shù)字進(jìn)行分配，如571第一輪先將它放在第一個(gè)的桶里，第二次分配時(shí)將他放在第七個(gè)捅里，這樣只是分配，還需要按照將每個(gè)桶進(jìn)行收集，這就是基數(shù)排序的基本思想。鏈?zhǔn)酱鎯?chǔ)題目要求要順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種結(jié)構(gòu)來(lái)實(shí)現(xiàn)，鏈?zhǔn)酱鎯?chǔ)采用靜態(tài)鏈表，這樣既節(jié)省空間，在時(shí)間上提高了效率。typedef struct int data; /數(shù)據(jù)，如571 datatype keysmax_num_of_key; /每個(gè)數(shù)據(jù)的所有關(guān)鍵字，571的5，7，1 int next; /next指什么？好糾結(jié)的問(wèn)題 slcell; /靜態(tài)鏈表的節(jié)點(diǎn)類型typedef struct slli

29、st slcell *r; /靜態(tài)鏈表的可利用空間，r0為頭結(jié)點(diǎn) int recnum; /靜態(tài)鏈表的當(dāng)前長(zhǎng)度 int keynum; /當(dāng)前數(shù)據(jù)的關(guān)鍵字個(gè)數(shù)sllist, * sllist; /靜態(tài)鏈表類型typedef int arrtyperadix; /指針數(shù)組類型，聲明兩個(gè)指針數(shù)組，一個(gè)頭指針，一個(gè)尾指針void creatlist(sllist &sll) /向程序中輸入數(shù)字，根據(jù)這些數(shù)字確定關(guān)鍵字的長(zhǎng)度和個(gè)數(shù)，同時(shí)創(chuàng)建一個(gè)靜態(tài)鏈表void distribute(slcell *r, int i, arrtype front, arrtype end) /對(duì)靜態(tài)鏈表記錄第i個(gè)關(guān)鍵字

30、進(jìn)行分配 /靜態(tài)鏈表l的r域中記錄已按(keys0.keysi-1有序)。 /本算法按第i個(gè)關(guān)鍵字keysi建立radix個(gè)子表，使同一子表中記錄的keysi相同。/front0.radix-1和end0.radix-1分別指向各子表中第一個(gè)和最后一個(gè)記錄。void collect(slcell *r, int i, arrtype front, arrtype end)/本算法按keysi自小到大地將f0.radix-1所指各子表依次鏈接成為一個(gè)鏈表，收集各個(gè)子表，使靜態(tài)鏈表有一定的順序順序存儲(chǔ)結(jié)構(gòu)： 和靜態(tài)鏈表不同，用順序存儲(chǔ)的時(shí)候可以便于進(jìn)行數(shù)據(jù)收集和查找，但沒(méi)有鏈表那樣移動(dòng)記錄時(shí)快捷。

31、typedef struct int data; /數(shù)據(jù)，如571datatype keysmax_num_of_key; /每個(gè)數(shù)據(jù)的所有關(guān)鍵字，571的5，7，1 cell; typedef structcell band50;int size;row;/0-9的分組時(shí)的結(jié)構(gòu)typedef struct cell *r; /可利用空間，r0為頭結(jié)點(diǎn) int recnum; /數(shù)組的當(dāng)前長(zhǎng)度 int keynum; /當(dāng)前數(shù)據(jù)的關(guān)鍵字個(gè)數(shù)list, *list; /一系列的關(guān)鍵字存放的數(shù)組void creatlista(list &sll) /和鏈?zhǔn)交鶖?shù)排序一樣需要進(jìn)行創(chuàng)建一個(gè)存放所有輸入信

32、息的數(shù)組void arraydist(list &l ,int i,row *r) /將記錄的第i個(gè)關(guān)鍵字進(jìn)行比較，分配到向量r里面void arraycollect(list &l,int i,row *r) /將r的數(shù)據(jù)收集到數(shù)組l中 無(wú)論是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都需要判斷關(guān)鍵字的最大長(zhǎng)度和個(gè)數(shù)，我們可以根據(jù)輸入的數(shù)字來(lái)確定關(guān)鍵字的長(zhǎng)度和個(gè)數(shù)，可以先將輸入的數(shù)字當(dāng)作字符來(lái)處理其長(zhǎng)度，再將這些字符轉(zhuǎn)換為數(shù)字。 cout輸入要進(jìn)行排序的數(shù)據(jù):str;/str是char*length=strlen(str);length=(lengthstrlen(str)?length:strlen(s

33、tr);/求關(guān)鍵字最長(zhǎng)值key=atoi(str);/將數(shù)字字符轉(zhuǎn)換為數(shù)字（五）調(diào)試分析、測(cè)試結(jié)果:操作界面（以0作為數(shù)據(jù)輸入結(jié)束的標(biāo)志）在設(shè)計(jì)順序存儲(chǔ)結(jié)構(gòu)時(shí)，可以按照鏈?zhǔn)交鶖?shù)排序的思想進(jìn)行操作，在分配分組時(shí)，采用的結(jié)構(gòu)體row會(huì)有一定的局限性，可以通過(guò)動(dòng)態(tài)分配來(lái)實(shí)現(xiàn)。（六）附錄:typedef struct int data; /數(shù)據(jù)，如571 datatype keysmax_num_of_key; /每個(gè)數(shù)據(jù)的所有關(guān)鍵字，571的5，7，1 int next; /next指什么？好糾結(jié)的問(wèn)題 slcell; /靜態(tài)鏈表的節(jié)點(diǎn)類型typedef struct sllist slcell *

34、r; /靜態(tài)鏈表的可利用空間，r0為頭結(jié)點(diǎn) int recnum; /靜態(tài)鏈表的當(dāng)前長(zhǎng)度 int keynum; /當(dāng)前數(shù)據(jù)的關(guān)鍵字個(gè)數(shù)sllist, * sllist; /靜態(tài)鏈表類型typedef int arrtyperadix; /指針數(shù)組類型，聲明兩個(gè)指針數(shù)組，一個(gè)頭指針，一個(gè)尾指針void creatlist(sllist &sll)/first creat a sllist when we input some nunbers int key, i=1,j,length;char str100; cout輸入要進(jìn)行排序的數(shù)據(jù):str;length=strlen(str);/cou

35、tlengthri.data = key; for(j = 1; j keynum; j+)/將各位上的數(shù)據(jù)轉(zhuǎn)化為數(shù)組中的元素 sll-ri.keysj = key % 10; key=key / 10; sll-ri-1.next=i+; cinstr;length=(lengthstrlen(str)?length:strlen(str);key=atoi(str); coutlengthkeynum=length; sll-recnum = i-1;/從一開(kāi)始的 sll-rsll-recnum.next=0;/r0相當(dāng)于頭結(jié)點(diǎn)void print(sllist &sll) for(int

36、 p=sll-r0.next; p; p=sll-rp.next) coutrp.data ; coutendl;void distribute(slcell *r, int i, arrtype front, arrtype end) /靜態(tài)鏈表l的r域中記錄已按(keys0.keysi-1有序)。 /本算法按第i個(gè)關(guān)鍵字keysi建立radix個(gè)子表，使同一子表中記錄的keysi相同。 /front0.radix-1和end0.radix-1分別指向各子表中第一個(gè)和最后一個(gè)記錄。 for(int j=0; jradix; +j) frontj = 0; /各子表初始化為空表 for(int

37、 p=r0.next; p; p=rp.next) j=rp.keysi; /映射第i個(gè)關(guān)鍵字 if(!frontj) frontj = p; /若frontj為空，則把記錄連接到frontj的頭指針上 else rendj.next = p; /若frontj的頭指針已經(jīng)連接過(guò)了，說(shuō)明已j為關(guān)鍵字的數(shù)據(jù)已經(jīng)有了，/這時(shí)把上一個(gè)以j為關(guān)鍵字的數(shù)據(jù)指向當(dāng)前的這個(gè)數(shù)，即下標(biāo)為p的數(shù)據(jù) endj = p; /尾指針重新指到每次更新的數(shù)據(jù)上 /distributevoid collect(slcell *r, int i, arrtype front, arrtype end) /本算法按keysi自

38、小到大地將f0.radix-1所指各子表依次鏈接成為一個(gè)鏈表 for(int j=0; !frontj; j+); /找到第一個(gè)不為空的子表 r0.next=frontj; /重整靜態(tài)鏈表 int k=endj; /k為當(dāng)前子表的尾指針for(+j; jr=(slcell *)malloc(max_space*sizeof(slcell); sll-recnum=0; sll-keynum=10; creatlist(sll); cout排序前:endl; print(sll); arrtype front,end; for(int i = 1; i keynum; i+) /按lsd法對(duì)各關(guān)

39、鍵字進(jìn)行分配和收集 distribute(sll-r, i,front,end); /第i趟分配 collect(sll-r, i,front,end); /第i趟收集 /cout第i分配和收集:endl; cout排序后：v的路徑。 首先引進(jìn)一個(gè)輔助向量d，它的分量di表示當(dāng)前找到的從始點(diǎn)v到終點(diǎn)vi的最短路徑的長(zhǎng)度。它的初態(tài)為：若從v到vi有弧則di為弧上的權(quán)值，否則di為，顯然，長(zhǎng)度為： dj=mindi|viv的路徑就是從v出發(fā)的長(zhǎng)度最小的路徑，此路徑為（v，vi）。 下一條最短路徑（v，vk）的最短路徑可能是直接兩點(diǎn)間的，也可可能是（v，vj，vk）。 當(dāng)然加入了點(diǎn)vk后可能使得v到

40、其他點(diǎn)的路徑變短這就還需要我們進(jìn)行調(diào)整了。 綜上所述，可以確定這個(gè)程序的偽碼為：void shortestpath_dij(school sh,int v0,int pmax_scenic,int d) 初始化各個(gè)v0到各個(gè)頂點(diǎn)的路徑，若和v0不相連則為，否則為其權(quán)值清空v0到各個(gè)頂點(diǎn)的路徑for（）/當(dāng)小于學(xué)校景點(diǎn)數(shù),求v0到其他各個(gè)頂點(diǎn)的最短路徑 當(dāng)前所知離v0頂點(diǎn)最近距離的頂點(diǎn)vi 標(biāo)記一下vi代表著已經(jīng)被訪問(wèn)了 pi記錄當(dāng)前的結(jié)點(diǎn)的順序 如果加入vi后，v0-vi-vj的距離小于v0-vj的距離，則調(diào)整v0到vj的距離,對(duì)未被訪問(wèn)的結(jié)點(diǎn)執(zhí)行這個(gè)判斷。其詳細(xì)代碼如下：void shortestpath_dij(school sh,int v0,int pmax_scenic,int d) /用迪杰斯特拉算法求有向網(wǎng)g的v