算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

1、.算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告系 （院）： 計(jì)算機(jī)科學(xué)學(xué)院 專業(yè)班級(jí)： 教技1001班 姓 名： 戴征淼 學(xué) 號(hào)： 201003886 指導(dǎo)教師： 詹澤梅 設(shè)計(jì)時(shí)間： 2012.6.16 - 2012.6.24 設(shè)計(jì)地點(diǎn)： 4號(hào)樓2號(hào)機(jī)房 目錄1、 設(shè)計(jì)方案及實(shí)現(xiàn)過(guò)程*第3頁(yè)2、 實(shí)現(xiàn)代碼*第4頁(yè)3、 測(cè)試*第19頁(yè)4、 難點(diǎn)與收獲*第21頁(yè)一、 設(shè)計(jì)方案及實(shí)現(xiàn)過(guò)程這次課程設(shè)計(jì)要求實(shí)現(xiàn)無(wú)向圖、有向圖、無(wú)向網(wǎng)以及有向網(wǎng)的一些基本操作以及應(yīng)用，大體的方案是先進(jìn)入界面后，選擇無(wú)向圖、有向圖、無(wú)向網(wǎng)、無(wú)向網(wǎng)中的一個(gè)，然后創(chuàng)建相應(yīng)的圖或者網(wǎng)，創(chuàng)建好后，在此基礎(chǔ)上選擇進(jìn)行相關(guān)的操作，具體的函數(shù)放在main函

2、數(shù)前面，通過(guò)多次函數(shù)調(diào)用已達(dá)到具體操作的實(shí)現(xiàn)。有向圖、無(wú)向網(wǎng)、有向網(wǎng)的操作和無(wú)向圖類似，在這里不一一列舉。流程圖如下：二、 實(shí)現(xiàn)代碼#include<stdio.h># include <stdlib.h># define maxlen 10# define large 999# define true 1# define false 0# define ok 1# define error 0# define overflow -2# define null 0typedef int status;#include <ctype.h>#include &l

3、t;string.h>#include <queue>#include <stack>#include <process.h>using namespace std;#define MAX_VERTEX_NUM 20#define MAX 1000typedef structint amaxlen,bmaxlen,hmaxlen;char vexsmaxlen;int vexnum,arcnum;int kind;int arcsmaxlenmaxlen;graph;typedef struct nodeint adjvex;int info;stru

4、ct node *next;edgenode;typedef struct int id; char data; edgenode *link;vexnode; typedef struct vexnode adjsmaxlen; int vexnum,arcnum; int kind;adjlist;typedef struct qnode int data; struct qnode *next;linkqlist; typedef struct linkqlist *front; linkqlist *rear; linkqueue;typedef struct int stackmax

5、len; int top;stackstru;int cnull=-1;graph g;adjlist adjl;stackstru *t;stackstru *s;linkqueue *q;graph printf_adjmatrix(graph g)int i,j;printf("鄰接矩陣:n");printf("vertext");for (i=0;i<g.vexnum;i+) printf("%4c",g.vexsi);printf("n");for(i=0;i<g.vexnum;i+)prin

6、tf("% 4c t",g.vexsi);for(j=0;j<g.vexnum;j+) printf("%4d",g.arcsij);printf("n");return g;void create_2(graph g) /構(gòu)造有向圖int i,j,k,c=0;for (i=0;i<g.vexnum;i+)for(j=0;j<g.vexnum;j+)g.arcsij=c;for(k=0;k<g.arcnum;k+)g.arcsg.ak-1g.bk-1=1;printf_adjmatrix(g);void cre

7、ate_1(graph g) /構(gòu)造無(wú)向圖int i,j,k,c=0;for (i=0;i<g.vexnum;i+)for(j=0;j<g.vexnum;j+)g.arcsij=c;for(k=0;k<g.arcnum;k+)g.arcsg.ak-1g.bk-1=1;g.arcsg.bk-1g.ak-1=1;printf_adjmatrix(g);graph create_4(graph g) /構(gòu)造有向網(wǎng)int i,j,k,c=999;for (i=0;i<g.vexnum;i+)for(j=0;j<g.vexnum;j+)g.arcsij=c;for(k=0;

8、k<g.arcnum;k+)g.arcsg.ak-1g.bk-1=g.hk;printf_adjmatrix(g);return g;graph create_3(graph g) /構(gòu)造無(wú)向網(wǎng)int i,j,k,c=999;for (i=0;i<g.vexnum;i+)for(j=0;j<g.vexnum;j+)g.arcsij=c;for (k=0;k<g.arcnum;k+)g.arcsg.ak-1g.bk-1=g.hk;g.arcsg.bk-1g.ak-1=g.hk;printf_adjmatrix(g);return g;void creategraph(gr

9、aph g)switch(g.kind)case 1:create_1(g);break;case 2:create_2(g);break;case 3:create_3(g);break;case 4:create_4(g);break;default:printf("Errorn");adjlist createlist (graph g ,adjlist adjl) /創(chuàng)建鄰接表 int i; edgenode *p; if(g.kind=1|g.kind=3)/創(chuàng)建有向鄰接表 for(i=0;i<adjl.arcnum;i+) p=(edgenode*)mal

10、loc(sizeof(edgenode); p->adjvex=g.bi; p->info=g.hi; p->next=adjl.adjsg.ai-1.link; adjl.adjsg.ai-1.link=p; if(g.kind=2|g.kind=4)/創(chuàng)建無(wú)向鄰接表for(i=0;i<adjl.arcnum;i+)p=(edgenode*)malloc(sizeof(edgenode);p->info=g.hi;p->adjvex=g.bi;p->next=adjl.adjsg.ai-1.link;adjl.adjsg.ai-1.link=p;p=

11、(edgenode*)malloc(sizeof(edgenode);p->info=g.hi;p->adjvex=g.ai;p->next=adjl.adjsg.bi-1.link;adjl.adjsg.bi-1.link=p;printf("鄰接表為:n");for(i=0;i<g.vexnum;i+)printf("%d,%c=>",i+1,adjl.adjsi.data);p=adjl.adjsi.link;while(p!=null)printf("%c,%d->",adjl.adjs(p

12、->adjvex)-1.data,p->info);p=p->next;printf("n");return adjl;void initqueue(linkqueue *p) /構(gòu)造空隊(duì)列p->front=(linkqlist *)malloc(sizeof(linkqlist);p->rear=p->front;(p->front)->next=null;status empty(linkqueue *q) /判斷是否為空int v;if(q->front=q->rear) v=true;else v=fals

13、e;return v;int addqueue(linkqueue *q,int e)q->rear->next=(linkqlist *)malloc(sizeof(linkqlist);q->rear=q->rear->next;if(!q->rear) return -1;q->rear->data=e;q->rear->next=null;return ok;status delqueue(linkqueue *q) /linkqlist *p;int e;if (q->front=q->rear)printf(&

14、quot;the linklist is overflow");else p=(q->front)->next;(q->front)->next=p->next;e=p->data;if(q->rear=p)q->rear=q->front;free(p);return(e);bool visitmaxlen; /深度優(yōu)先搜索void DFS(adjlist adjl,int i)edgenode *p;visiti=1; printf("%c ",adjl.adjsi.data);for(p=adjl.adj

15、si.link;p;p=p->next)if(!visitp->adjvex) DFS(adjl,p->adjvex); void DFSTraverse(adjlist adjl) int i;printf("tt深度優(yōu)先搜索 :");for( i=0;i<maxlen;i+)visiti=false;for( i=0;i<=adjl.vexnum;i+)if(!visiti) DFS(adjl,i); queue <int> Q;void BFSTraverse(adjlist adjl) /廣度優(yōu)先搜索edgenode *w;

16、int i,j;printf("ntt廣度優(yōu)先搜索 :");for( i=0;i<maxlen;i+)visiti=0;for(i=0;i<=adjl.vexnum;i+)if(!visiti)visiti=1; printf("%c ",adjl.adjsi.data);Q.push(i);while(!Q.empty()j=Q.front();Q.pop();for( w=adjl.adjsi.link;w;w=w->next)if(!visitw->adjvex)visitw->adjvex=1; printf(&qu

17、ot;%c ",adjl.adjsw->adjvex-1.data);Q.push(w->adjvex);status initstack(stackstru *s) /構(gòu)造空棧s->top=0; return ok;status push(stackstru *s,int x) /進(jìn)棧if (s->top=maxlen) printf("the stack is overflow!n"); else s->top=s->top+1; s->stacks->top=x;return 1;status pop(stac

18、kstru *s) /出棧 int y; if(s->top=0)printf("the stack is empty!n"); elsey=s->stacks->top; s->top=s->top-1; return y;status stackempty(stackstru *s) /判斷棧是否為空 if (s->top=maxlen) return (true);else return (false);int TopologicalSort(adjlist adjl) /拓?fù)渑判騭tack <int> S; edgen

19、ode *p;int i,j,count=0;printf("n拓?fù)渑判颍?quot;);for(i=0;i<=adjl.vexnum;i+)if(adjl.adjsi.id=0)S.push(i);count=0;while(!S.empty() j=S.top(); S.pop(); count+; printf("(%d %c) ",j,adjl.adjsj.data);for(p=adjl.adjsi.link;p;p=p->next) int k=p->adjvex; int d=-(adjl.adjsk.id); if(!d)S.pu

20、sh(k); if(count<adjl.vexnum) printf("n網(wǎng)中有環(huán)!n");return error;else return ok; void prim(graph g)int i,j,k,min;int lowcostmaxlen;int closetmaxlen;printf("最小生成樹(shù)的邊為:n");for(i=1;i<g.vexnum;i+)lowcosti=g.arcs0i;closeti=1;closet1=0;j=1;for(i=1;i<g.vexnum;i+)min=lowcostj;k=i;for(

21、j=1;j<g.vexnum;j+)if(lowcostj<min&&closetj!=0)min=lowcostj;k=j;printf("(%c,%c),",g.vexsk-1,g.vexsclosetk-1);closetk=0;for(j=1;j<g.vexnum;j+)if(g.arcskj<lowcostj&&closetj!=0)lowcostj=g.arcskj;closetj=k;int vemaxlen;int vlmaxlen;status toporder(adjlist adjl,stacks

22、tru *t) /關(guān)鍵路徑int i,j,count,k;edgenode *p;initstack(s);initstack(t);for(i=0;i<adjl.vexnum;i+)if(adjl.adjsi.id=0) push(s,i);count=0;for(i=0;i<adjl.vexnum;i+) vei=0;while(!stackempty(s) j=pop(s);push(t,j);+count;for(p=adjl.adjsj.link;p;p=p->next) k=p->adjvex;if(-adjl.adjsk-1.id=0) push(s,k-

23、1);if(vej+(p->info)>vek-1) vek-1=vej+(p->info);if(count<adjl.vexnum) return error;else return ok;int criticalpath(adjlist adjl) int i,j,k,dut,ee,el;edgenode *p;if(!toporder(adjl,t) return error;for(i=0;i<adjl.vexnum;i+) vli=vei-1;printf("關(guān)鍵路徑為:n");while(!stackempty(t)for(j=p

24、op(t), p=adjl.adjsj.link;p;p=p->next) k=p->adjvex; dut=(p->info);if(vlk-dut<vlj) vlj=vlk-dut;for(j=0;j<adjl.vexnum;+j)for(p=adjl.adjsj.link;p;p=p->next)k=p->adjvex;dut=p->info;ee=vej;el=vlk-1-dut;if(ee=el) printf("(%c,%c)->",adjl.adjsj.data,adjl.adjsk-1.data);ret

25、urn ok;void shortpath_dijkstra(graph g) /有向網(wǎng)的最短路徑 int costmaxlenmaxlen;int distmaxlen;int pathmaxlen;int smaxlen;int i,j,v0,min,u;printf("n請(qǐng)輸入起點(diǎn)的編號(hào):");scanf("%d",&v0);v0-;for(i=0;i<g.vexnum;i+)for(j=0;j<g.vexnum;j+)costij=g.arcsij;for(i=0;i<g.vexnum;i+) disti=costv0i

26、;if(disti<large&&disti>0) pathi=v0;si=0;sv0=1;for(i=0;i<g.vexnum;i+) min=large;u=v0;for(j=0;j<g.vexnum;j+)if(sj=0&&distj<min)min=distj;u=j;su=1; for(j=0;j<g.vexnum;j+)if(sj=0&&distu+costuj<distj) distj=distu+costuj;pathj=u;printf("n頂點(diǎn)%d到各頂點(diǎn)的最短路徑長(zhǎng)度為:n

27、",v0);for(i=0;i<g.vexnum;i+)if(si=1) u=i;while(u!=v0) printf("%4c<-",g.vexsu);u=pathu;printf("%4c",g.vexsu);printf(":%dn",pathi);else printf("%4c<-%4c:無(wú)路徑n",g.vexsi,g.vexsv0);void ShowMainMenu()printf("n");printf("*圖的基本操作及應(yīng)用*n"

28、;);printf("* 1 無(wú)向圖的基本操作及應(yīng)用 *n");printf("* 2 有向圖的基本操作及應(yīng)用 *n");printf("* 3 無(wú)向網(wǎng)的基本操作及應(yīng)用 *n");printf("* 4 有向網(wǎng)的基本操作及應(yīng)用 *n");printf("* 5 退出n");printf("*n");void UDG()int n;doprintf("n");printf("*無(wú)向圖的基本操作及應(yīng)用*n");printf("*

29、1 創(chuàng)建無(wú)向圖的鄰接矩陣 *n");printf("* 2 創(chuàng)建無(wú)向圖的鄰接表 *n");printf("* 3 無(wú)向圖的深度優(yōu)先遍歷 *n");printf("* 4 無(wú)向圖的廣度優(yōu)先遍歷 *n");printf("* 5 退出n");printf("*n");printf("請(qǐng)選擇：");scanf("%d",&n);switch(n)case 1:printf("-wait-");creategraph(g);b

30、reak; /鄰接矩陣case 2:printf("-wait-");createlist (g,adjl);break; /鄰接表case 3:printf("-wait-");DFSTraverse(adjl);break; /深度優(yōu)先搜索case 4:printf("-wait-");BFSTraverse(adjl);break; /廣度優(yōu)先搜索case 5:break;default:printf("ERROR!");while(n!=5);void DG() int n;doprintf("n

31、");printf("*有向圖的基本操作及應(yīng)用*n");printf("* 1 創(chuàng)建有向圖的鄰接矩陣 *n");printf("* 2 創(chuàng)建有向圖的鄰接表 *n");printf("* 3 拓?fù)渑判?*n");printf("* 4 退出 *n");printf("*n");printf("請(qǐng)選擇：");scanf("%d",&n);switch(n)case 1:printf("-wait-");

32、creategraph(g);break; /鄰接矩陣case 2:printf("-wait-");createlist (g,adjl);break; /鄰接表case 3:printf("-wait-");createlist(g,adjl);TopologicalSort(adjl);break; /拓?fù)渑判騝ase 4:break; /退出 default:printf("ERROR!");while(n!=4);void UDN() int n;doprintf("n");printf("*無(wú)

33、向網(wǎng)的基本操作及應(yīng)用*n");printf("* 1 創(chuàng)建無(wú)向網(wǎng)的鄰接矩陣 *n");printf("* 2 創(chuàng)建無(wú)向網(wǎng)的鄰接表 *n");printf("* 3 Prim算法求最小生成樹(shù) *n");printf("* 4 kraskal算法求最小生成樹(shù) *n");printf("* 5 退出n");printf("*n");printf("請(qǐng)選擇：");scanf("%d",&n);switch(n)case 1:p

34、rintf("-wait-");creategraph(g);break; / 創(chuàng)建無(wú)向網(wǎng)的鄰接矩陣case 2:printf("- -wait-");createlist (g,adjl);break; / 創(chuàng)建無(wú)向網(wǎng)的鄰接表case 3:printf("-wait-");prim(g);break; /Prim算法求最小生成樹(shù)case 4:printf("-wait-");break;case 5:break;default:printf("ERROR!");while(n!=5);void

35、 DN() int n;doprintf("n");printf("*有向網(wǎng)的基本操作及應(yīng)用*n");printf("* 1 創(chuàng)建有向網(wǎng)的鄰接矩陣 *n");printf("* 2 創(chuàng)建有向網(wǎng)的鄰接表 *n");printf("* 3 關(guān)鍵路徑 *n");printf("* 4 單源頂點(diǎn)最短路徑問(wèn)題 *n");printf("* 5 退出n");printf("*n");printf("請(qǐng)選擇：");scanf(&q

36、uot;%d",&n);switch(n)case 1:printf("-wait-");creategraph(g);break; /創(chuàng)建有向網(wǎng)的鄰接矩陣case 2:printf("-wait-");createlist (g,adjl);break; /創(chuàng)建有向網(wǎng)的鄰接表case 3:printf("-wait-");criticalpath(adjl);break; /關(guān)鍵路徑case 4:printf("-wait-");criticalpath(adjl);break; /單源頂點(diǎn)最短

37、路徑問(wèn)題case 5:break; /退出default:printf("ERROR!");while(n!=5);void main()int i,j,k,h,n;doShowMainMenu();printf("請(qǐng)選擇：");scanf("%d",&n);if(n>5) error;elseg.kind=n;h=n;printf("請(qǐng)輸入頂點(diǎn)數(shù),邊數(shù):");scanf("%d,%d",&i,&j);g.vexnum=i;adjl.vexnum=i;g.arcnu

38、m=j;adjl.arcnum=j;for (i=0;i<g.vexnum;i+)printf("第%d個(gè)頂點(diǎn)的信息:",i+1);scanf("%s",&g.vexsi);adjl.adjsi.data=g.vexsi;adjl.adjsi.link=null;adjl.adjsi.id=0;for (k=1;k<=g.arcnum;k+)/label:if (g.kind=2|g.kind=4)printf("第%d條邊的起點(diǎn)編號(hào),終點(diǎn)編號(hào):",k);else printf("第%d條邊的兩個(gè)頂點(diǎn)的編

39、號(hào):",k);scanf("%d,%d",&i,&j);g.ak-1=i;g.bk-1=j;while (i<1|i>g.vexnum|j<1|j>g.vexnum)printf(" 編號(hào)超出范圍,重新輸入");/goto label;if (g.kind=3|g.kind=4)printf("t該邊的權(quán)值:");scanf("%d",&h);g.hk-1=h;else g.hk-1=null;adjl.adjsi.id+;switch(n)case 1:UDG();break;case 2:DG();break;case 3:UDN();break;case 4:DN();break;case 5:break;default:printf("ERROR!");break;while(n!=5);三、 測(cè)試a) 程序開(kāi)始運(yùn)行，進(jìn)入選擇界面b） 選擇無(wú)向圖，并創(chuàng)建無(wú)向圖C）基于已創(chuàng)建的的無(wú)向圖選擇各項(xiàng)具體的操作四、 難點(diǎn)與收獲這次的實(shí)習(xí)報(bào)告相對(duì)我而言算是比較難的，因?yàn)樵趯W(xué)這門課程的時(shí)