[工學(xué)]太原理工大學(xué)《程序設(shè)計(jì)》課程設(shè)計(jì)

1、程序設(shè)計(jì)課程設(shè)計(jì)姓 名：郭雨晴學(xué) 號(hào)：2010004407班 級(jí)：軟件1003班指導(dǎo)教師：呼克佑、李誌成 績(jī)：2012年6月設(shè)計(jì)題目一1 文本文件單詞的檢索與計(jì)數(shù)1.1【問(wèn)題描述】設(shè)計(jì)C或C+程序，統(tǒng)計(jì)在這樣的英文文本文件中，出現(xiàn)了多少個(gè)單詞，每個(gè)單詞出現(xiàn)了幾次。連續(xù)的英文字符都認(rèn)為單詞(不包括數(shù)字)，單詞之間用空格或標(biāo)點(diǎn)符號(hào)分隔。 1.2【設(shè)計(jì)需求及分析】要統(tǒng)計(jì)英文文本文件中出現(xiàn)了哪些單詞，就要從文件中讀取字符，讀取出來(lái)的連續(xù)英文字符認(rèn)為是一個(gè)單詞，遇空格或標(biāo)點(diǎn)符號(hào)單詞結(jié)束。使用線(xiàn)性表記錄單詞以及每個(gè)單詞出現(xiàn)的次數(shù)。線(xiàn)性表中的單詞按字典順序存儲(chǔ)。線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)如下：#define LI

2、ST_INIT_SIZE 100 /線(xiàn)性表存儲(chǔ)空間的初始分配量#define LISTINCREMENT 10 /線(xiàn)性表存儲(chǔ)空間的分配增量typedef struct char word21 /存儲(chǔ)單詞，不超過(guò)20個(gè)字符 int count; /單詞出現(xiàn)的次數(shù) ElemType;typedef struct ElemType *elem; /存儲(chǔ)空間基址 int length; /當(dāng)前長(zhǎng)度int listsize; /當(dāng)前分配的存儲(chǔ)容量 Sqlist;1.3【設(shè)計(jì)功能的實(shí)現(xiàn)】（用C或C+語(yǔ)言描述）#include <stdio.h>#include <string.h>

3、#include <stdlib.h>#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef structchar word21;int count; ElemType;typedef structElemType *elem;int length;int listsize; SqList;int InitList(SqList *p)p->elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(p->elem=NULL) return 0;p->

4、;length=0;p->listsize=LIST_INIT_SIZE;return 1;int LocateElem(SqList *p,char *word)int low,high,mid;low=0;high=p->length-1;while(low<=high)mid=(low+high)/2;if(strcmp(word,p->elemmid.word)=0) /表中進(jìn)行二分查找p->elemmid.count+;return 0;else if(strcmp(word,p->elemmid.word)<0)high=mid-1;els

5、elow=mid+1;return low+1; /返回插入點(diǎn)序號(hào)int InsertList(SqList *p,int i,char *word)int j;ElemType *base;if(p->length>=p->listsize)base=(ElemType*)realloc(p->elem,(p->listsize+LISTINCREMENT)*sizeof(ElemType);if(base=NULL) return 0;p->listsize=p->listsize+LISTINCREMENT; /擴(kuò)充表長(zhǎng)p->elem=ba

6、se;for(j=p->length;j>=i;j-)p->elemj=p->elemj-1;strcpy(p->elemi-1.word,word);p->elemi-1.count=1;p->length+;return 1;void PrintList(SqList *p,int num)FILE *fw;int i;int no=num;fw=fopen("F:單詞計(jì)數(shù).txt","w");fprintf(fw,"文章共有%d個(gè)單詞n以下按字典順序排序顯示出現(xiàn)次數(shù)n*n",no);fp

7、rintf(fw,"單詞 出現(xiàn)次數(shù)n",no);for(i=0;i<p->length;i+)fprintf(fw,"%-24s %-5dn",p->elemi.word,p->elemi.count);fprintf(fw,"*n");fclose(fw);/主函數(shù)void main()SqList L;char word21,ch,filename30,filename150;int num=0,i,j=0,mark=0;FILE *fp;InitList(&L);printf("請(qǐng)將文件

8、放入F盤(pán)，并輸入文件名:n");scanf("%s",&filename);sprintf(filename1,"F:%s.txt",filename);getchar();if(fp=fopen(filename1,"r")=NULL)printf("打開(kāi)文件失敗，請(qǐng)確認(rèn)文件名與文件路徑！n");getchar();exit(0);ch=fgetc(fp);while(ch!=EOF)if(ch>='A'&&ch<='Z')|(ch&g

9、t;='a'&&ch<='z') ch=ch>='A'&&ch<='Z'?ch+32:ch;wordj+=ch;mark=1;elseif (mark=1)if (j>20)printf("文章中部分單詞太長(zhǎng)不予統(tǒng)計(jì)");num+;wordj='0'mark=0;j=0;i=LocateElem(&L,word);if(i>0)InsertList(&L,i,word);ch=fgetc(fp);fclose(fp);

10、printf("統(tǒng)計(jì)結(jié)束！單詞計(jì)數(shù).txt文件已經(jīng)在F盤(pán)生成。");PrintList(&L,num);getchar();1.3.1 實(shí)現(xiàn)順序表的基本操作順序表的初始化：InitList(SqList &L)順序表上查找指定的單詞：LocateElem(SqList &L,char *s) 若找到，單詞的出現(xiàn)次數(shù)增1，返回0，否則返回該單詞的插入位置。在順序表上插入新的單詞：InsertList(SqList &L,int i，char *s) 要求按字典順序有序。新單詞的出現(xiàn)次數(shù)為1.輸出順序表上存儲(chǔ)的單詞統(tǒng)計(jì)信息：PrintList(S

11、qList &L) 輸出文件中每個(gè)單詞出現(xiàn)的次數(shù)以及文件中總的單詞數(shù)(可輸出到文件中)。1.3.2 統(tǒng)計(jì)單詞數(shù)統(tǒng)計(jì)過(guò)程如下：（1）輸入要統(tǒng)計(jì)單詞的文本文件名，打開(kāi)相應(yīng)的文件；（2）初始化順序表；（3）從文本文件中讀取字符，直到文件結(jié)束。具體描述如下：While (讀文件沒(méi)有結(jié)束) 過(guò)濾單詞前的非字母字符； 讀取一個(gè)單詞，已字符串形式存儲(chǔ)在一個(gè)字符數(shù)組中； 在線(xiàn)性表中查找該單詞，若找到，單詞的出現(xiàn)次數(shù)加1，否則返回其插入位置； 上一步中，若沒(méi)找到，則進(jìn)行插入操作； 處理下一個(gè)單詞。（4） 關(guān)閉文件，輸出統(tǒng)計(jì)結(jié)果。1.4【實(shí)例測(cè)試及運(yùn)行結(jié)果】1.4.1 運(yùn)行實(shí)例一 文章：TUT 運(yùn)行結(jié)果：

12、 程序顯示： 1.4.1 運(yùn)行實(shí)例二文章：Beautiful運(yùn)行結(jié)果： 程序顯示： 設(shè)計(jì)題目二2停車(chē)場(chǎng)管理2.1【問(wèn)題描述】設(shè)停車(chē)場(chǎng)是一個(gè)可停放n輛汽車(chē)的狹長(zhǎng)通道，且只有一個(gè)大門(mén)可供汽車(chē)進(jìn)出。汽車(chē)在停車(chē)場(chǎng)內(nèi)按車(chē)輛到達(dá)時(shí)間的先后順序，依次由北向南排列（大門(mén)在最南端，最先到達(dá)的第一輛車(chē)停放在停車(chē)場(chǎng)的最北端）,若停車(chē)場(chǎng)內(nèi)已停滿(mǎn)n輛汽車(chē)，則后來(lái)的汽車(chē)只能在門(mén)外的便道上等候，一旦有車(chē)開(kāi)走，則排在便道上的第一輛車(chē)即可開(kāi)入；當(dāng)停車(chē)場(chǎng)內(nèi)某輛車(chē)要離開(kāi)時(shí)，在它之后進(jìn)入的車(chē)輛必須先退出車(chē)場(chǎng)為它讓路，待該輛車(chē)開(kāi)出大門(mén)外，其他車(chē)輛再按原次序進(jìn)入車(chē)場(chǎng)，每輛停放在車(chē)場(chǎng)的車(chē)在它離開(kāi)停車(chē)場(chǎng)時(shí)必須按它停留的時(shí)間長(zhǎng)短交納費(fèi)用。試為

13、停車(chē)場(chǎng)編制按上述要求進(jìn)行管理的模擬程序。2.2【設(shè)計(jì)需求及分析】以棧模擬停車(chē)場(chǎng)，以隊(duì)列模擬車(chē)場(chǎng)外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車(chē)“到達(dá)”或“離去”信息、汽車(chē)牌照號(hào)碼以及到達(dá)或離去的時(shí)刻。對(duì)每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出信息為：若是車(chē)輛到達(dá)，則輸出汽車(chē)在停車(chē)場(chǎng)內(nèi)或便道上的停車(chē)位置；若是車(chē)輛離去，則輸出汽車(chē)在停車(chē)場(chǎng)內(nèi)停留的時(shí)間和應(yīng)交納的費(fèi)用（在便道上停留的時(shí)間不收費(fèi)）。棧以順序結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表結(jié)構(gòu)實(shí)現(xiàn)。2.3【設(shè)計(jì)功能的實(shí)現(xiàn)】（用C或C+語(yǔ)言描述）#include<stdio.h>#include <string.h>

14、#include<math.h>#include<stdlib.h>#define MAX 10#define price 0.05 typedef struct time int hour;int min;time; typedef struct carnode char num10; time reach; time leave; carnode; typedef struct carstack carnode *stackMAX+1; int top; carstack; typedef struct qnode carnode *data; struct qno

15、de *next; qnode; typedef struct node qnode *head; qnode *rear; linkqueue; void initstack(carstack *s) int i; s->top=0; for(i=0;i<=MAX;i+) s->stacks->top=NULL; int initqueue(linkqueue *Q) Q->head=(qnode *)malloc(sizeof(qnode); if(Q->head!=NULL) Q->head->next=NULL; Q->rear=Q

16、->head; return 1; else return -1; /車(chē)輛到達(dá) int arrival(carstack *enter,linkqueue *w) carnode *p; qnode *t; p=(carnode *)malloc(sizeof(carnode); printf("n請(qǐng)您輸入車(chē)牌號(hào)："); scanf("%s",&p->num); if(enter->top<MAX) enter->top+; printf("n該車(chē)停在的位置：%d號(hào)",enter->top)

17、; printf("n請(qǐng)您輸入車(chē)到達(dá)的時(shí)間："); scanf("%d:%d",&(p->reach.hour),&(p->reach.min); enter->stackenter->top=p; return 1; else /沒(méi)有空車(chē)位 printf("對(duì)不起，停車(chē)場(chǎng)已滿(mǎn)請(qǐng)您停在便道上！"); t=(qnode *)malloc(sizeof(qnode); t->data=p; t->next=NULL; w->rear->next=t; w->rear=t

18、; return 1; void print(carnode *p,int room)/汽車(chē)離站時(shí)繳費(fèi)顯示 printf("n車(chē)輛離開(kāi)的時(shí)間："); scanf("%d:%d",&p->leave.hour,&p->leave.min); printf("n離開(kāi)車(chē)輛的車(chē)牌號(hào)為:%s",p->num); printf("n其到達(dá)時(shí)間為：%02d:%02d",p->reach.hour,p->reach.min); printf("n其離開(kāi)時(shí)間為：%02d:%02

19、d",p->leave.hour,p->leave.min); printf("n應(yīng)繳費(fèi)用為：%.2f元",(p->leave.hour-p->reach.hour)*60+(p->leave.min-p->reach.min)*price); free(p); /車(chē)輛離開(kāi) void leave(carstack *enter,carstack *temp,linkqueue *w) int room; carnode *p,*t; qnode *q; if(enter->top>0)/有車(chē) while(1) pri

20、ntf("n請(qǐng)您輸入車(chē)在停車(chē)場(chǎng)上的位置:"); scanf("%d",&(room); if(room>=1&&room<=enter->top) break; while(enter->top>room)/位置不在棧頂?shù)钠?chē)出棧 temp->top+; temp->stacktemp->top=enter->stackenter->top; enter->stackenter->top=NULL; enter->top-; p=enter->st

21、ackenter->top; enter->stackenter->top=NULL; enter->top-; while(temp->top>=1)/當(dāng)暫時(shí)存儲(chǔ)汽車(chē)的棧結(jié)構(gòu)中有汽車(chē)時(shí) enter->top+; enter->stackenter->top=temp->stacktemp->top; temp->stacktemp->top=NULL; temp->top-; print(p,room); /判斷便道上是否有車(chē)及停車(chē)場(chǎng)上是否已滿(mǎn) if(w->head!=w->rear)&&

22、amp;enter->top<MAX)/車(chē)站有空位且便道上有車(chē)時(shí) q=w->head->next; t=q->data; enter->top+; printf("n請(qǐng)便道上的%s號(hào)車(chē)進(jìn)入第%d位置。",t->num,enter->top); printf("n請(qǐng)輸入現(xiàn)在的時(shí)間："); scanf("%d:%d",&(t->reach.hour),&(t->reach.min); w->head->next=q->next; if(q=w-&

23、gt;rear) w->rear=w->head; enter->stackenter->top=t; free(q); else printf("n便道里沒(méi)有車(chē)！"); else printf("n現(xiàn)在停車(chē)場(chǎng)里沒(méi)有車(chē)了！"); /顯示停車(chē)場(chǎng)的信息 void list1(carstack *s) int i; if(s->top>0) printf("n停車(chē)場(chǎng)："); printf("n停車(chē)位置t到達(dá)時(shí)間t車(chē)牌號(hào)n"); for(i=1;i<=s->top;i+) p

24、rintf(" %dt",i); printf(" %02d:%02d ",s->stacki->reach.hour,s->stacki->reach.min); printf("t%s",s->stacki->num); else printf("n對(duì)不起，暫無(wú)停車(chē)場(chǎng)里的信息！"); /顯示便道上的 void list2(linkqueue *w) qnode *p; p=w->head->next; if(w->head!=w->rear) prin

25、tf("n等待車(chē)輛的號(hào)碼為："); printf("n*"); while(p!=NULL) puts(p->data->num); p=p->next; printf("n*"); else printf("n便道里沒(méi)有車(chē)！"); void list(carstack s,linkqueue w) int flag,tag; flag=1; while(flag) printf("n請(qǐng)選擇："); printf("ntt1、停車(chē)場(chǎng)信息ntt2、便道信息ntt3、返回

26、主菜單n"); while(1) scanf("%d",&flag); if(flag>=1|flag<=10)break; else printf("選擇錯(cuò)誤，請(qǐng)重新選擇！n"); switch(flag) case 1: list1(&s); break; case 2: list2(&w); break; case 3: flag=0; break; default: break; /主函數(shù)void main()carstack enter,temp;linkqueue wait;int a;int b

27、=1;initstack(&enter);initstack(&temp);initqueue(&wait);while(b) printf("n*n");printf("t1、汽車(chē)進(jìn)站登記n");printf("t2、汽車(chē)出站登記n"); printf("t3、停車(chē)場(chǎng)情況顯示n");printf("t4、退出系統(tǒng)n");printf("*n");printf("請(qǐng)選擇項(xiàng)目：");scanf("%d",&

28、a);while(b)if(a=1|a=2|a=3|a=4)break;elseprintf("n錯(cuò)誤！退出系統(tǒng)n");b=0;break;switch(a)case 1:arrival(&enter,&wait); break;case 2:leave(&enter,&temp,&wait); break;case 3:list(enter,wait); break;case 4:exit(0);default:break;2.4【實(shí)例測(cè)試及運(yùn)行結(jié)果】設(shè)n=2，輸入數(shù)據(jù)為：（A,1,5）,（A,2,10）,（D,1,15）,（A,3

29、,20）,（A,4,25）,（A5,30）,（D,2,35）,（D,4,40）,（E,0,0）。其中：A表示到達(dá)（arrival）；D表示離去（departure）；E表示輸入結(jié)束（end）。2.5【實(shí)現(xiàn)提示】實(shí)驗(yàn)主要由兩個(gè)棧，一個(gè)隊(duì)列組成，將停車(chē)場(chǎng)和汽車(chē)離開(kāi)時(shí)退出車(chē)輛設(shè)定為棧，將便道上車(chē)輛情況用隊(duì)列表示。系統(tǒng)功能主要是汽車(chē)進(jìn)站、汽車(chē)出站、停車(chē)場(chǎng)情況、退出程序。在實(shí)驗(yàn)的過(guò)程中遇到的主要問(wèn)題是如何實(shí)現(xiàn)汽車(chē)離開(kāi)后，后面車(chē)輛推出，待車(chē)輛離開(kāi)后，其它車(chē)輛再進(jìn)入，并且，如果便道上停有車(chē)輛也進(jìn)入停車(chē)場(chǎng)。這個(gè)涉及到數(shù)據(jù)結(jié)構(gòu)的知識(shí)。主要用到的是關(guān)于堆棧和隊(duì)列的部分知識(shí)。因?yàn)橥＼?chē)場(chǎng)內(nèi)的車(chē)具有“后進(jìn)先出”的特點(diǎn)，

30、所以要用到棧。便道盡管只有一個(gè)空位，但它符合隊(duì)列“先進(jìn)先出”的特點(diǎn)，所以用隊(duì)列表示。而需設(shè)一個(gè)棧，臨時(shí)停放為給要離去的汽車(chē)讓路而從停車(chē)場(chǎng)退出來(lái)的汽車(chē)，也用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)。輸入數(shù)據(jù)按到達(dá)或離去的時(shí)刻有序。棧中每個(gè)元素表示一輛汽車(chē)，包含兩個(gè)數(shù)據(jù)項(xiàng)：汽車(chē)的牌照號(hào)碼和進(jìn)入停車(chē)場(chǎng)的時(shí)刻。程序的難度主要在于運(yùn)算指針的變化狀況，例如，當(dāng)一輛汽車(chē)離開(kāi)后，其后面的車(chē)輛的停車(chē)位會(huì)依次向前，且便道上的車(chē)進(jìn)入停車(chē)場(chǎng)最后一位，就要求我們會(huì)運(yùn)用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，即w->head->next=q->next; if(q=w->rear) w->rear=w->head; enter->

31、;stackenter->top=t; free(q); 設(shè)計(jì)題目三3交通咨詢(xún)系統(tǒng)設(shè)計(jì)（最短路徑問(wèn)題）3.1【問(wèn)題描述】在交通網(wǎng)絡(luò)非常發(fā)達(dá),交通工具和交通方式不斷更新的今天,人們?cè)诔霾睢⒙糜位蜃銎渌鲂袝r(shí)，不僅關(guān)心節(jié)省交通費(fèi)用，而且對(duì)里程和所需要的時(shí)間等問(wèn)題也感興趣。對(duì)于這樣一個(gè)人們關(guān)心的問(wèn)題，可用一個(gè)圖結(jié)構(gòu)來(lái)表示交通網(wǎng)絡(luò)系統(tǒng)，利用計(jì)算機(jī)建立一個(gè)交通咨詢(xún)系統(tǒng)。圖中的頂點(diǎn)表示城市，邊表示城市之間的交通關(guān)系。這個(gè)交通系統(tǒng)可以回答出行旅客提出的各種路徑選擇問(wèn)題。例如，問(wèn)題之一：“一位旅客要從A城到B城，他希望選擇一條途中中轉(zhuǎn)次數(shù)最少的路線(xiàn)?！奔僭O(shè)圖中每一站都需要換車(chē)，那么這個(gè)問(wèn)題反映到圖上就是

32、要找一條從頂點(diǎn)A到頂點(diǎn)B的所含邊數(shù)目最少的路徑。我們只需要從頂點(diǎn)A出發(fā)對(duì)圖作廣度優(yōu)先搜索，一旦遇到頂點(diǎn)B就終止。由此所得廣度優(yōu)先生成樹(shù)上，從根頂點(diǎn)A到頂點(diǎn)B的路徑就是中轉(zhuǎn)次數(shù)最少的路徑。路徑上A與B之間的頂點(diǎn)就是路徑的中轉(zhuǎn)站，但這只是一類(lèi)最簡(jiǎn)單的圖的最短路徑問(wèn)題。系統(tǒng)還可以回答諸如此類(lèi)的等等的路徑選擇問(wèn)題。設(shè)計(jì)一個(gè)交通咨詢(xún)系統(tǒng)，為出差、旅游或做其他出行的客人提供各種路徑選擇信息查詢(xún)服務(wù)。3.2【設(shè)計(jì)需求及分析】設(shè)計(jì)一個(gè)交通咨詢(xún)系統(tǒng)，能讓旅客咨詢(xún)從任一個(gè)城市頂點(diǎn)到另一城市頂點(diǎn)之間的最短路徑（里程）或最低花費(fèi)或最少時(shí)間等問(wèn)題。對(duì)于不同的咨詢(xún)要求，可輸入城市間的路程或所需時(shí)間或所需費(fèi)用。本設(shè)計(jì)共分三

33、部分，一是建立交通網(wǎng)絡(luò)圖的存儲(chǔ)結(jié)構(gòu)；二是解決單源最短路徑問(wèn)題；三是實(shí)現(xiàn)任兩個(gè)城市頂點(diǎn)之間的最短路徑問(wèn)題。3.2.1建立圖的存儲(chǔ)結(jié)構(gòu)鄰接矩陣是表示圖形中頂點(diǎn)之間相鄰關(guān)系的矩陣。圖的鄰接矩陣是定義如下的n階方陣：設(shè)G=（V，E）是一個(gè)圖，結(jié)點(diǎn)集為。G的鄰接矩陣當(dāng)鄰接矩陣的行表頭、列表頭順序一定時(shí)，一個(gè)圖的鄰接矩陣表示是唯一的。圖的鄰接矩陣表示，除了需用一個(gè)二維數(shù)組存儲(chǔ)頂點(diǎn)之間的相鄰關(guān)系的鄰接矩陣外，通常還需要使用一個(gè)具有n個(gè)元素的一維數(shù)組來(lái)存儲(chǔ)頂點(diǎn)信息，其中下標(biāo)為i的元素存儲(chǔ)頂點(diǎn)i的信息。因此，圖的鄰接矩陣的存儲(chǔ)結(jié)構(gòu)定義如下：#definf MVNum 50 /最大頂點(diǎn)數(shù)typedef struc

34、t VertexType vexsMVNum; /頂點(diǎn)數(shù)組，類(lèi)型假定為char型 Adjmatrix arcsMVNumMVNum; /鄰接矩陣，假定為int型MGraph;3.2.2單源最短路徑最短路徑的提法很多。在這里先討論單源最短路徑問(wèn)題：即已知有向圖（帶權(quán)），我們希望找出從某個(gè)源點(diǎn)SV到G中其余各頂點(diǎn)的最短路徑。為了敘述方便，我們把路徑上的開(kāi)始點(diǎn)稱(chēng)為源點(diǎn)，路徑的最后一個(gè)頂點(diǎn)為終點(diǎn)。那么，如何求得給定有向圖的單源最短路徑呢？迪杰斯特拉（Dijkstra）提出按路徑長(zhǎng)度遞增產(chǎn)生諸點(diǎn)的最短路徑算法，稱(chēng)之為迪杰斯特拉算法。迪杰斯特拉算法求最短路徑的實(shí)現(xiàn)思想是：設(shè)G=（V，E）是一個(gè)有向圖，結(jié)點(diǎn)

35、集為，cost是表示G的鄰接矩陣，costij表示有向邊<i,j>的權(quán)。若不存在有向邊<i,j>，則costij的權(quán)為無(wú)窮大（這里取值為32767）。設(shè)S是一個(gè)集合，其中的每個(gè)元素表示一個(gè)頂點(diǎn)，從源點(diǎn)到這些頂點(diǎn)的最短距離已經(jīng)求出。設(shè)頂點(diǎn)v1為源點(diǎn)，集合S的初態(tài)只包含一個(gè)元素，即頂點(diǎn)v1。數(shù)組dist記錄從源點(diǎn)到其他頂點(diǎn)當(dāng)前的最短距離，其初值為disti=costv1i,i=1,2,n。從S之外的頂點(diǎn)集合V-S中選出一個(gè)頂點(diǎn)w，使distw的值最小。于是從源點(diǎn)到達(dá)w只通過(guò)S中頂點(diǎn)，把w加入集合S中，調(diào)整dist中記錄的從源點(diǎn)到V-S中每個(gè)頂點(diǎn)v的距離：從原來(lái)的distv和

36、distw+costwv中選擇較小的值作為新的distv。重復(fù)上述過(guò)程，直到V-S為空。最終結(jié)果是：S記錄了從源點(diǎn)到該頂點(diǎn)存在最短路徑的頂點(diǎn)集合，數(shù)組dist記錄了源點(diǎn)到V中其余各頂點(diǎn)之間的最短路徑，path是最短路徑的路徑數(shù)組，其中pathi表示從源點(diǎn)到頂點(diǎn)i之間的最短路徑的前驅(qū)頂點(diǎn)。因此，迪杰斯特拉算法可用自然語(yǔ)言描述如下：初始化S和D，置空最短路徑終點(diǎn)集，置初始的最短路徑值；Sv1=TRUE; Dv1=0； /S集初始時(shí)只有源點(diǎn)，源點(diǎn)到源點(diǎn)的距離為0；While (S集中頂點(diǎn)數(shù)<n)開(kāi)始循環(huán)，每次求得v1到某個(gè)v頂點(diǎn)的最短路徑，并加v到S集中；Sv=TRUE；更新當(dāng)前最短路徑及距離

37、；3.2.3任意一對(duì)頂點(diǎn)間最短路徑任意一對(duì)頂點(diǎn)間最短路徑問(wèn)題，是對(duì)于給定的有向網(wǎng)絡(luò)圖G=（V，E），要對(duì)G中任意一對(duì)頂點(diǎn)有序?qū)Α皏,w(vw)”,找出v到w的最短路徑。要解決這個(gè)問(wèn)題，我們可以依次把有向網(wǎng)絡(luò)圖中每個(gè)頂點(diǎn)作為源點(diǎn)，重復(fù)執(zhí)行前面討論的迪杰斯特拉算法n次，即可以求得每對(duì)頂點(diǎn)之間的最短路徑。這里還可以用另外一種方法，稱(chēng)作費(fèi)洛伊德（Floyd）算法。費(fèi)洛伊德（Floyd）算法算法的基本思想是：假設(shè)求從頂點(diǎn) vi到vj的最短路徑。如果從vi到vj存在一條長(zhǎng)度為arcsij的路徑，該路徑不一定是最短路徑，還需要進(jìn)行n次試探。首先考慮路徑<vi,v1>和<v1,vj>是

38、否存在。如果存在，則比較<vi,vj>和< vi,v1,vj >的路徑長(zhǎng)度，取長(zhǎng)度較短者為當(dāng)前所求得的最短路徑。該路徑是中間頂點(diǎn)序號(hào)不大于1的最短路徑。其次，考慮從vi到vj是否包含有頂點(diǎn)v2為中間頂點(diǎn)的路徑<vi,v2,vj>，若沒(méi)有，則說(shuō)明從vi到vj的當(dāng)前最短路徑就是前一步求出的；若有，那么<vi,v2,vj>可分解為<vi,v2>和<v2,vj>,而這兩條路徑是前一次找到的中間頂點(diǎn)序號(hào)不大于1的最短路徑，將這兩條路徑長(zhǎng)度相加就得到路徑<vi,v2,vj>的長(zhǎng)度。將該長(zhǎng)度與前一次中求出的從vi到vj的中間

39、頂點(diǎn)序號(hào)不大于1的最短路徑比較，取其長(zhǎng)度較短者作為當(dāng)前求得的從vi到vj的中間頂點(diǎn)序號(hào)不大于2的最短路徑。依此類(lèi)推，直到頂點(diǎn)vn加入當(dāng)前從vi到vj的最短路徑后，選出從vi到vj的中間頂點(diǎn)序號(hào)不大于n的最短路徑為止。由于圖G中頂點(diǎn)序號(hào)不大于n，所以vi到vj的中間頂點(diǎn)序號(hào)不大于n的最短路徑，已考慮了所有頂點(diǎn)作為中間頂點(diǎn)的可能性，因此，它就是vi到vj的最短路徑。3.3【設(shè)計(jì)功能的實(shí)現(xiàn)】（用C或C+語(yǔ)言描述）3.3.1 建立有向圖的存儲(chǔ)結(jié)構(gòu)void CreatGraph(Graph *m) int i, j;int head, tail, weight;char ch;printf("

40、輸入地點(diǎn)個(gè)數(shù)和路線(xiàn)條數(shù)：n"); scanf("%d%d",&(m->vexnum), &(m->arcnum);if(m->vexnum<1 | m->arcnum<0)printf("輸入有誤n");printf("按回車(chē)鍵退出n");ch = getchar();ch = getchar();exit(0); m->arcs = (ArcCell *)malloc(sizeof(ArcCell *)*(m->vexnum); for(i=0; i<m

41、->vexnum; i+)m->arcsi = (ArcCell *)malloc(sizeof(ArcCell)*(m->vexnum);for(j=0; j<m->vexnum; j+)(m->arcsij).adj = 0; (m->arcsii).adj = 1;(m->arcsii).weight = 0;printf("輸入帶權(quán)有向圖的弧（按弧頭、弧尾、權(quán)值的順序,頂點(diǎn)序號(hào)由零開(kāi)始）n"); for(i=0; i<m->arcnum; i+)scanf("%d%d%d",&h

42、ead, &tail, &weight);if(head<0 | tail<0 | weight <0)printf("輸入有誤n");printf("按回車(chē)鍵退出n");ch = getchar();ch = getchar();exit(0);(m->arcsheadtail).weight = weight;(m->arcsheadtail).adj = 1;void PrintGraph(Graph *m)int v = m->vexnum;int i,j;for(i=0; i<v; i+

43、)for(j=0; j<v; j+)if(m->arcsij.adj)printf("%-5d",(m->arcs)ij.weight);else printf(" ");printf("n");BiTree BiTreePathGrow(BiTree cold, int *travel, int v,int w) int u = travelvw; if(u=-1)return cold;cold = (BiTree)malloc(sizeof(Node);cold->data = u;cold->lc

44、hild = NULL;cold->rchild = NULL;if(traveluw>=0)BiTreePathGrow(cold->rchild,travel,u,w);if(travelvu>=0)BiTreePathGrow(cold->lchild,travel,v,u);return cold;void InOrderTraversalBiTree(BiTree cold, void (*fun)(int) if(!cold)return;InOrderTraversalBiTree(cold->lchild,fun);fun(cold->

45、data);InOrderTraversalBiTree(cold->rchild,fun);void PrintData(int travel)printf("%-5d",travel);3.3.2 迪杰斯特拉算法void ShortestPathbyDIJ(Graph *m, int v0) int V = m->vexnum;int v,w,i,j;int min;int *remote; char *final; int *travel; int *pain; final = (char *)malloc(sizeof(char)*V);travel =

46、 (int *)malloc(sizeof(int *)*V); pain = (int *)malloc(sizeof(int)*(V-2);remote = (int *)malloc(sizeof(int)*V);for(v=0; v<V; v+)finalv = 0;painv = 0;if(m->arcsv0v.adj)remotev = m->arcsv0v.weight;else remotev = INFINITY;travelv = (int *)malloc(sizeof(int)*(V-2); remotev0 = 0;finalv0 = 1; for(

47、i=0; i<V; i+) /i為計(jì)數(shù)器，循環(huán) vexnum-1 次min = INFINITY;for(w=0; w<m->vexnum; w+)if(finalw=0 && remotew<min)v = w;min = remotew;/計(jì)算后的路徑finalv = 1; for(w=0; w<V; w+)if(finalw=0) if(m->arcsvw).adj)if( (min + (m->arcsvw).weight) < remotew)remotew = min + (m->arcsvw.weight);/

48、更新路徑for(j=0; j<painv; j+)travelwj = travelvj;painw = painv+1;travelwj = v;/*=輸出最短路徑start=*/for(i=0; i<V; i+)if(i != v0)printf("從%d點(diǎn)出發(fā)到%d點(diǎn)",v0,i);if(remotei < INFINITY)printf("的最短路徑（總權(quán)值為%d）為：n%d-",remotei,v0);if(paini)printf("<%d>->",m->arcsv0traveli

49、0.weight);for(v=1; v< paini ; v+) printf("%d-<%d>->",traveliv-1,(m->arcs traveliv-1 traveliv ).weight);v-;printf("%d-<%d>->",traveliv, (m->arcs traveliv i).weight); printf("%dn",i);elseprintf("<%d>->%dn",m->arcsv0i.weight

50、,i);elseprintf(" 此路不通()n");printf("n"); /*=輸出最短路徑end=*/ 3.3.3 費(fèi)洛伊德算法void ShortestPathbyFLOYD(Graph *night,int meet,int bye)BiTree BiTreePathGrow(BiTree, int *travel, int v,int w); /由路徑創(chuàng)建二叉樹(shù)void InOrderTraversalBiTree(BiTree cold, void (*fun)(int); /中序遍歷二叉樹(shù)void PrintData(int);int

51、u, v, w;int pain = night->vexnum;int *travel; int *remote; int forget;BiTree cold;travel = (int *)malloc(sizeof(int *)*pain);remote = (int *)malloc(sizeof(int *)*pain);/初始化for(v=0; v<pain; v+)travelv = (int *)malloc(sizeof(int)*pain);remotev = (int *)malloc(sizeof(int)*pain);for(w=0; w<pain

52、; w+)travelvw = -1;if(night->arcsvw.adj)remotevw = night->arcsvw.weight;else remotevw = INFINITY;for(v=0; v<pain; v+)for(w=0; w<pain; w+)if(v!=w)for(u=0; u<pain; u+)if(v!=u && w!=u)if(forget=remotevu+remoteuw) < remotevw) travelvw = u;remotevw = forget; /輸出最短路徑（通過(guò)二叉樹(shù)）printf("從%d點(diǎn)到%d點(diǎn)",meet,bye);if(remotemeetbye < INFINITY)printf("的最