數據結構最小生成樹課程設計
① C語言 課程設計 最小生成樹的詳細設計，還有能讓人理解的話解釋一下這個編程到底在做什麼事情
我已經發到你的郵箱
② 求數據結構最小生成樹的實驗報告，包含流程圖，
數據結構（實驗報告）
姓名： 高 申 雷
學號： 0613042024
日期： 2008年3月25日
一、實驗題目： 停 車 場 管 理
二、問題描述：
設停車場是一個可以停放n輛汽車的狹長通道，且只有一個大門可以供車輛進出。車輛按到達停車場時間的早晚依次從停車場最里向大門口處停放（最先到達的第一輛車放在停車場的最裡面）。如果停車場已放滿n輛車，則後來的車只能在停車場大門外的便道上等待，一旦停車場內有車開走，則排在便道上的第一輛車就進入停車場。停車場內如有某輛車要開走，在它之後進入停車場的車都必須先退出停車場為它讓路，待其開出停車場後，這些車輛再依原來的次序進場。每輛車在離開停車場時，都應根據它在停車場內停留的時間長短交費。如果停留在便道上的車未進停車場就要離去，允許其離去，不收停車費，並且仍然保持在便道上等待的車輛次序。編制一程序模擬該停車場的管理。
三、需求分析：
停車場採用棧式結構，停車場外的便道採用隊列結構（即便道就是等候隊列）。停車場的管理流程如下：
①當車輛要進入停車場時，檢查停車場是否已滿，如果未滿則車輛進棧（車輛進入停車場）；如果停車場已滿，則車輛進入等候隊列（車輛進入便道等候）。
②當車輛要求出棧時，該車到棧頂的那些車輛先彈出棧（在它之後進入的車輛必須先退出車場為它讓路），再讓該車出棧，其他車輛再按原次序進棧（進入車場）。當車輛出棧完畢後，檢查等候隊列（便道）中是否有車，有車則從隊列頭取出一輛車壓入棧中。
四、概要設計：
1、用棧模擬停車場，用隊列模擬車場外的便道，按照從終端讀入的輸入數據序列進行模擬管理。
2、每一組輸入數據包括三個數據項：汽車到達或離去的信息，汽車牌照號碼以及到達或離去的時刻。
3、每次輸入完進行輸出操作：若是車輛到達，輸出汽車在停車場內或便道上的停車位置；若是車輛離去，輸出停留時間和應繳納的費用（在便道上停留的時間不收費）。
4、其中棧以順序結構實現，隊列以鏈表結構實現。
五、詳細設計：
1、定義棧（停車場） struct stack
初始化棧void initstack(stack* s)
元素進棧int instack(stack* s,cinfo x)
元素出棧cinfo outstack(stack* s)
2、定義隊列（車場外的便道）struct queue
初始化隊列void initqueue(queue* q)
元素進隊列void inqueue(queue* q,int num1)
元素出隊列int outqueue(queue* q)
3、處理車輛到達的情況void carrival(stack* s,queue* q,cinfo x)
處理車輛離開void carleave(stack* s1,stack* s2,queue* q,cinfo x)
4、主程序void main()
註：詳細設計中的具體代碼見模塊代碼中。
六、模塊代碼：
#include"iostream.h"
int N;
const int M=5;//M為單元時間的收費值
struct cinfo//定義棧中元素的類型
{ int cnum; int atime;
};
struct stack//定義棧
{ cinfo cstack[3000];//這里隨便定義一個數字表示數組的長度,因為後
int top; //面會根據用戶輸入的N值作為停車場能夠停車的
int size; //數量.
};
struct node//定義隊列節點的類型
{ node* next; int nnum;
};
struct queue//定義隊列
{ node *front,*rear;
};
void initstack(stack* s)//初始化棧
{ s->top=-1;
}
int instack(stack* s,cinfo x)//元素進棧
{ //int 元素進棧n;
if(s->top==N-1)
{ cout<<"Stack is full!"<<endl; return 0;
} else
{ s->cstack[++s->top]=x;
return 1;
}
}
cinfo outstack(stack* s)//元素出棧
{ cinfo y;
if(s->top<0)
{ y.cnum=NULL;
y.atime=NULL;
return y;
} else
{ s->top--;
return s->cstack[s->top+1];
}
}
void initqueue(queue* q)//初始化隊列
{ q->front=new node;
q->rear=q->front;
q->front->next=NULL;
q->front->nnum=0;
}
void inqueue(queue* q,int num1)//元素進隊列
{ node* p;
p=new node;
p->nnum=num1;
p->next=NULL;
q->rear->next=p;
q->rear=p;
q->front->nnum++;
}
int outqueue(queue* q)//元素出隊列
{ node* p;
int n;
if(q->front==q->rear) return 0;
else {
p=q->front->next;
q->front->next=p->next;
if(p->next==NULL)
q->rear=q->front;
n=p->nnum;
delete p;
q->front->nnum--;
return n;
}
}
void carrival(stack* s,queue* q,cinfo x)//處理車輛到達的情況
{ int f;
f=instack(s,x);
if(f==0) {
inqueue(q,x.cnum);
cout<<"The Number"<<x.cnum<<" "<<"car park into the pos"<<q->front->nnum<<" "<<"of the road."<<endl;
} else
{ cout<<"The Number"<<x.cnum<<" "<<"car park into the pos"<<s->top+1<<" "<<"of the room."<<endl;
}
}
void carleave(stack* s1,stack* s2,queue* q,cinfo x)//處理車輛離開
{ node* p;
cinfo y;
int a,n=0;
while((s1->top>-1)&&(n==0))
{ y=outstack(s1);
if(y.cnum!=x.cnum) {
a=instack(s2,y);
} else
n=1;
}
if(y.cnum==x.cnum)
{ cout<<"The number"<<x.cnum<<" "<<"car want to leave,the charge is"<<" "<<(x.atime-y.atime)*M<<" "<<"yuan!"<<endl;
while(s2->top>-1)
{ y=outstack(s2);
n=instack(s1,y);
}
a=outqueue(q);
if(a!=0)
{ y.cnum=a; y.atime=x.atime;
n=instack(s1,y);
cout<<"The Number"<<y.cnum<<" "<<"car park into the pos"<<s1->top+1<<" "<<"of the room."<<endl;
}
} else
{ while(s2->top>-1)
{ y=outstack(s2);
n=instack(s1,y);
}
p=q->front;
n=0;
while(p->next!=NULL&&n==0)
{ if(p->next->nnum!=x.cnum)
p=p->next;
else {
p->next=p->next->next;
q->front->nnum--;
if(p->next=NULL)
q->rear=q->front;
cout<<"The number"<<x.cnum<<" "<<"want to leave from the road."<<endl;
n=1;
}
}
if(n==0)
{ cout<<"You have entered a wrong number!"<<endl;
}
}
}
void main()//主程序
{ //int maxsize;
cout<<"Start，Written by ZIGZ"<<endl<<endl<<endl;
cout<<"Please enter a number as the maxsize of the roomStack:"<<endl;
cin>>N;//這里N將作為棧能存放元素的數量
while(N<=0)
{ cout<<"Oh!You have enter a wrong number,'N' should above 0.Please enter another number again:"<<endl;
cin>>N;
} //stack *max;
//max->size=maxsize;
char ch1;
stack* s1,*s2;
queue* q;
cinfo x;
int flag;
s1=new stack;
s2=new stack;
q=new queue;
initstack(s1);
initstack(s2);
initqueue(q);
flag=1;
for(;;) {cout<<"Please enter the infomation: 'A'/'D'; car number; car arrival time."<<endl;
cin>>ch1>>x.cnum>>x.atime;
switch(ch1)
{ case'A':
case'a':carrival(s1,q,x);
break;
case'D':
case'd':carleave(s1,s2,q,x);
break;
case'E':
case'e':flag=0;cout<<"Ok,the system will be shut down!Written by ZIGZ!"<<endl;
break;
default:cout<<"You have enter a wrong!!"<<endl;
}
if(flag==0)
break;
}
}
七、運行結果：
八、經驗小結：
通過《停車場管理》的實驗學習使我基本上理解並學會了用棧的先進後出和隊列的先進先出的原理去解決實際問題的思想和方法。但是在編程方面還是很欠缺，還要加強學習。
③ 急求數據結構 C語言版 課程設計 最小生成樹
#include <stdio.h>
#define inf 9999
#define max 40
void prim(int g[][max],int n) // prim的函數
{
int lowcost[max],closest[max];
int i,j,k,min;
for(i=2;i<=n;i++) // n個頂點，n-1條邊
{ lowcost[i]=g[1][i]; // 初始化
closest[i]=1; // 頂點未加入到最小生成樹中
}
lowcost[1]=0; // 標志頂點1加入U集合
for(i=2;i<=n;i++) // 形成n-1條邊的生成樹
{
min=inf;
k=0;
for(j=2;j<=n;j++) // 尋找滿足邊的一個頂點在U,另一個頂點在V的最小邊
if((lowcost[j]<min)&&(lowcost[j]!=0))
{
min=lowcost[j];
k=j;
}
printf("(%d,%d)%d\t",closest[k],k,min);
lowcost[k]=0; // 頂點k加入U
for(j=2;j<=n;j++) // 修改由頂點k到其他頂點邊的權值
if(g[k][j]<lowcost[j])
{ lowcost[j]=g[k][j];
closest[j]=k;
}
printf("\n");
}
}
int adjg(int g[][max]) // 建立無向圖
{
int n,e,i,j,k,v1,v2,weight;
printf("輸入頂點個數，邊的條數：");
scanf("%d,%d",&n,&e);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
g[i][j]=inf; // 初始化矩陣，全部元素設為無窮大
for(k=1;k<=e;k++)
{
printf("輸入第%d條邊的起點，終點，權值:",k);
scanf("%d,%d,%d",&v1,&v2,&weight);
g[v1][v2]=weight;
g[v2][v1]=weight;
}
return(n);
}
void prg(int g[][max],int n) // 輸出無向圖的鄰接矩陣
{
int i,j;
for(i=0;i<=n;i++)
printf("%d\t",i);
for(i=1;i<=n;i++)
{
printf("\n%d\t",i);
for(j=1;j<=n;j++)
printf((g[i][j]==inf)?"\t":"%d\t",g[i][j]);
}
printf("\n");
}
void main()
{
int g[max][max],n;
n=adjg(g);
printf("輸入無向圖的鄰接矩陣:\n");
prg(g,n);
printf("最小生成樹的構造:\n");
prim(g,n);
}
④ 數據結構課程設計--用普里姆演算法求最小生成樹
for i:=1 to n do begin d[i]:=a[1,i]; f[i]:=false; end;
f[1]:=true; //放在生成樹中回
ans:=0;
for i:=2 to n do
begin
min:=maxint;
for j:=1 to n do
if (not f[j]) and (d[j]<min) then
begin min:=d[j]; k:=j; end;
inc(ans,d[k]);
f[k]:=true;
for j:=1 to n do
if (not f[j]) and(a[k,j]<d[j]) then d[j]:=a[k,j];//修改答d
end;
⑤ 最小生成樹的實現（避圈法）課程設計怎麼弄
#include<stdio.h>
#include<stdlib.h>
#define M 20
#define MAX 20typedef struct
{
int begin; //頭頂點
int end; //末頂點
int weight; //權值
}edge;typedef struct
{
int adj;
int weight;//權值
}AdjMatrix[MAX][MAX];typedef struct
{
AdjMatrix arc;
int vexnum, arcnum;//總邊 點 的值
}MGraph;
//函數申明
void CreatGraph(MGraph *); //圖構建
void sort(edge* ,MGraph *); //權值排序
void MiniSpanTree(MGraph *); //生成最小樹
int Find(int *, int );// 尾頂點查找
void Swapn(edge *, int, int);//權值、頭頂點、尾頂點交換
void CreatGraph(MGraph *G)//構件圖
{
int i, j,n, m;
printf("請輸入邊數和頂點數:\n");
scanf("%d %d",&G->arcnum,&G->vexnum);
for (i = 1; i <= G->vexnum; i++)//初始化圖
{
for ( j = 1; j <= G->vexnum; j++)
{
G->arc[i][j].adj = G->arc[j][i].adj = 0;
}
}
for ( i = 1; i <= G->arcnum; i++)//輸入邊和權值
{
printf("請輸入有邊的2個頂點\n");
scanf("%d %d",&n,&m);
while(n < 0 || n > G->vexnum || m < 0 || n > G->vexnum)
{
printf("輸入的數字不符合要求 請重新輸入:\n");
scanf("%d%d",&n,&m);
}
G->arc[n][m].adj = G->arc[m][n].adj = 1;
getchar();
printf("請輸入%d與%d之間的權值:\n", n, m);
scanf("%d",&G->arc[n][m].weight);
}
printf("鄰接矩陣為:\n");
for ( i = 1; i <= G->vexnum; i++)
{
for ( j = 1; j <= G->vexnum; j++)
{
printf("%d ",G->arc[i][j].adj);
}
printf("\n");
}
}void sort(edge edges[],MGraph *G)//對權值進行排序
{
int i, j;
for ( i = 1; i < G->arcnum; i++)
{
for ( j = i + 1; j <= G->arcnum; j++)
{
if (edges[i].weight > edges[j].weight)
{
Swapn(edges, i, j);//交換i和j 這兩條邊
}
}
}
printf("權排序之後的為:\n");
for (i = 1; i < G->arcnum; i++)
{
printf("<< %d, %d >> %d\n", edges[i].begin, edges[i].end, edges[i].weight);
}
}void Swapn(edge *edges,int i, int j)//交換權值 以及頭和尾
{
int temp;
temp = edges[i].begin;
edges[i].begin = edges[j].begin;
edges[j].begin = temp;//交換頭頂點 temp = edges[i].end;
edges[i].end = edges[j].end;
edges[j].end = temp;//交換尾頂點 temp = edges[i].weight;
edges[i].weight = edges[j].weight;
edges[j].weight = temp;//交換權值
}void MiniSpanTree(MGraph *G)//生成最小生成樹
{
int i, j, n, m;
int k = 1;
int parent[M];
edge edges[M];
for ( i = 1; i < G->vexnum; i++)
{
for (j = i + 1; j <= G->vexnum; j++)
{
if (G->arc[i][j].adj == 1)
{
edges[k].begin = i;
edges[k].end = j;
edges[k].weight = G->arc[i][j].weight;
k++;
}
}
}
sort(edges, G);
for (i = 1; i <= G->arcnum; i++)
{
parent[i] = 0;
}
printf("最小生成樹為:\n");
for (i = 1; i <= G->arcnum; i++)//核心部分
{
n = Find(parent, edges[i].begin);
m = Find(parent, edges[i].end);
if (n != m)//判斷是否有迴路，如果有，舍棄
{
parent[m] = n;
printf("<< %d, %d >> %d\n", edges[i].begin, edges[i].end, edges[i].weight);
}
}
}int Find(int *parent, int f)//找尾
{
while ( parent[f] > 0)
{
f = parent[f];
}
return f;
}int main(void)//主函數
{
MGraph *G;
G = (MGraph*)malloc(sizeof(MGraph));//為圖動態分配存儲空間
if (G == NULL)//如果圖沒有創建，則程序非正常結束
{
printf("memory allcation failed,goodbye");
exit(1);
}
CreatGraph(G);//創建一個圖
MiniSpanTree(G);//求最小生成樹
system("pause");//系統暫停運行
return 0;
⑥ 數據結構課程設計——構造可以使n個城市連接的最小生成樹
用Prim吧，我資料里有聯系方式
⑦ 最小生成樹——最優通信網 課程設計
你這個開發語言是什麼
平台
或資料庫都怎樣
談
我這樣才好幫你
⑧ 最小生成樹課程設計
給你說說思路吧
在所有的邊中選擇權值最小的一個邊 對其進行如下操作：專
將該邊加入生成樹屬中 如果存在環 則刪除該邊
重復上面的操作 n-1 次
即可找到包含n個結點的最小生成樹
至於怎麼判斷是否存在環 可以使用並查集 當然 最簡單的方法是為每個邊建立一個bool型變數 其包含在生成樹裡面時 設置為true 否則為false 每次加邊之前判斷邊的頭結點和尾結點的bool變數是否都為true就可以
具體怎麼實現 還是希望樓主自行CODE
畢竟這個是基本功