最小生成樹數據結構課程設計

❶ 數據結構課程設計 誰能幫下啊！！！1．八皇後問題 2.哈夫曼編/解碼器； 3.關鍵路徑 4.最小生成樹問題

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <ctype.h>
#include<limits.h>
int function1(char ch,char *s)
{
int i;
for(i=0; s[i]!='\0'; i++)
{
if(ch==s[i])return 0;
}
return 1;
}
typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
} HTNode,*HuffmanTree; // 動態分配數組存儲赫夫曼樹
typedef char **HuffmanCode; // 動態分配數組存儲赫夫曼編碼表
// algo6-1.cpp 求赫夫曼編碼。實現演算法6.12的程序

int min(HuffmanTree t,int i)
{
// 函數void select()調用
int j,flag;
unsigned int k=UINT_MAX; // 取k為不小於可能的值
for(j=1; j<=i; j++)
if(t[j].weight<k&&t[j].parent==0)
k=t[j].weight,flag=j;
t[flag].parent=1;
return flag;
}

void select(HuffmanTree t,int i,int &s1,int &s2)
{
// s1為最小的兩個值中序號小的那個

s1=min(t,i);
s2=min(t,i);
/* if(s1>s2)
{
j=s1;
s1=s2;
s2=j;
}*/
}

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) // 演算法6.12
{
// w存放n個字元的權值(均>0),構造赫夫曼樹HT,並求出n個字元的赫夫曼編碼HC
int m,i,s1,s2,start;
unsigned c,f;
HuffmanTree p;
char *cd;
if(n<=1)
return;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0號單元未用
for(p=HT+1,i=1; i<=n; ++i,++p,++w)
{
(*p).weight=*w;
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0;
}
for(; i<=m; ++i,++p)
(*p).parent=0;
for(i=n+1; i<=m; ++i) // 建赫夫曼樹
{
// 在HT[1~i-1]中選擇parent為0且weight最小的兩個結點,其序號分別為s1和s2
select(HT,i-1,s1,s2);
HT[s1].parent=HT[s2].parent=i;
HT[i].rchild=s1;
HT[i].lchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
// printf("HT[%d].lchild:%d HT[%d].rchild:%d\n",i,s2,i,s1);
}
// 從葉子到根逆向求每個字元的赫夫曼編碼
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
// 分配n個字元編碼的頭指針向量([0]不用)
cd=(char*)malloc(n*sizeof(char)); // 分配求編碼的工作空間
cd[n-1]='\0'; // 編碼結束符
for(i=1; i<=n; i++)
{
// 逐個字元求赫夫曼編碼
start=n-1; // 編碼結束符位置
for(c=i,f=HT[i].parent; f!=0; c=f,f=HT[f].parent)
// 從葉子到根逆向求編碼
if(HT[f].lchild==c)
cd[--start]='1';
else
cd[--start]='0';
HC[i]=(char*)malloc((n-start)*sizeof(char));
// 為第i個字元編碼分配空間
strcpy(HC[i],&cd[start]); // 從cd復制編碼(串)到HC
}
free(cd); // 釋放工作空間
}
void swap1(int *a ,int *b)
{
int t;
t=*a;
*a=*b;
*b=t;
}
void swap2(char *a,char *b)
{
char ch;
ch=*a;
*a=*b;
*b=ch;
}
int main(void)
{
HuffmanTree HT;
HuffmanCode HC;
char *s1,*s2;
int i,j=0,n,count,*m,t,flag=1;
scanf("%d",&n);
getchar();
s1=(char*)malloc((n+n)*sizeof(char));
s2=(char*)malloc(n*sizeof(char));
memset(s2,'\0',n*sizeof(char));
gets(s1);
count=strlen(s1);
for(i=0; i<count; i++)
{
if(!isspace(*(s1+i)))
{
if(function1(*(s1+i),s2))
{
*(s2+j)=*(s1+i);
j++;
}
}
else;
}
m=(int*)malloc(j*sizeof(int));
for(i=0; i<j; i++)
*(m+i)=0;
for(t=0; t<j; t++)
{
for(i=0; i<count; i++)
{
if(*(s2+t)==*(s1+i))
*(m+t)+=1;
}
}
for(i=0;i<j;i++)
while(flag)
{
flag = 0;
for (t=0; t<j-1; t++)
{
if(*(m+t)<*(m+t+1))
{
swap1(m+t,m+t+1);
swap2(s2+t,s2+t+1);
flag=1;
}
}
}
HuffmanCoding(HT,HC,m,j);
for(i=1,t=0; i<=j; i++,t++)
{
printf("%c %d %s\n",*(s2+t),*(m+t),HC[i]);

}
return 0;
}

❷ 數據結構課程設計—最短路徑

#include <stdio.h>

#define INFINITY 10000
#define TRUE 1
#define FALSE 0
#define VERTEX_NUM 6

typedef struct Graph
{
char vexs[VERTEX_NUM]; /*頂點*/
int arcs[VERTEX_NUM][VERTEX_NUM]; /*鄰接矩陣*/
int vexnum; /*頂點數專*/
int arcnum; /*弧數屬*/
}Graph;

❸ 最小生成樹課程設計

給你說說思路吧

在所有的邊中選擇權值最小的一個邊 對其進行如下操作：專
將該邊加入生成樹屬中 如果存在環 則刪除該邊
重復上面的操作 n-1 次
即可找到包含n個結點的最小生成樹

至於怎麼判斷是否存在環 可以使用並查集 當然 最簡單的方法是為每個邊建立一個bool型變數 其包含在生成樹裡面時 設置為true 否則為false 每次加邊之前判斷邊的頭結點和尾結點的bool變數是否都為true就可以

具體怎麼實現 還是希望樓主自行CODE
畢竟這個是基本功

❹ C語言 課程設計 最小生成樹的詳細設計，還有能讓人理解的話解釋一下這個編程到底在做什麼事情

我已經發到你的郵箱

❺ 數據結構課程設計--用普里姆演算法求最小生成樹

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;

❻ 急求，數據結構課程設計用Kruskal 演算法求最小生成樹

將城市看成是點，城市之間的距離看成是點之間的權值。
下面是PRIM演算法實現的最小生成樹代碼。，利用鄰接矩陣存儲邊的信息。程序已通過編譯了，可以直接運行。
#include <stdio.h>
#include <string.h>
typedef int VRType;
typedef char InfoType;
#define MAX_NAME 3
/*頂點字元串的最大長度+1*/
#define MAX_INFO 20
/*相關信息字元串的最大長度+1*/
typedef char VertexType[MAX_NAME];
#define INFINITY 32767
/*用整型最大值代替無窮大*/
#define MAX_VERTEX_NUM 20
/*最大頂點個數*/
typedef enum GraphKind;
/**/
typedef int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef int ShortPathTable[MAX_VERTEX_NUM];
typedef struct
{
VRType adj;
/*頂點關系類型。對無權圖，用1（是）或0(否）表示相鄰否*/
/*對帶全圖，則為權值類型*/
InfoType *info;
/*該弧相關信息的指針（可無）*/
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
VertexType vexs[MAX_VERTEX_NUM];
/*頂點向量*/
AdjMatrix arcs;
/*鄰接矩陣*/
int vexnum,arcnum;
/*圖的當前頂點數和弧數*/
GraphKind kind;
/*圖的種類標志*/
}MGraph;
int LocateVex(MGraph G,VertexType u)
{ /*初始條件：圖G存在，u和G中頂點有相同特徵*/
/*操作結果：若G中存在頂點u，則返回該頂點在圖中位置；否則返回-1*/
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vexs[i])==0)
return i;
return -1;
}
int CreateAN(MGraph *G)
{/*採用數組（鄰接矩陣）表示法，構造無向網G*/
int i,j,k,w,IncInfo;
char s[MAX_INFO],*info;
VertexType va,vb;
printf("please input number of acmes and arcs in G,and there is some information in arc,if yes is 1,else is 0:");
scanf("%d,%d,%d",&(*G).vexnum,&(*G).arcnum,&IncInfo);
printf("please input the value of %d acmes(<%d character):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i)
/*構造頂點向量*/
scanf("%s",(*G).vexs[i]);
for(i=0;i<(*G).vexnum;++i)
/*初始化鄰接矩陣*/
for(j=0;j<(*G).vexnum;++j)
{(*G).arcs[i][j].adj=INFINITY;
/*網*/
(*G).arcs[i][j].info=NULL;
}
printf("please input %d the first and the second of acr and weigh:\n",(*G).arcnum);
for(k=0;k<(*G).arcnum;++k)
{
scanf("%s %s %d",va,vb,&w);
/*%*c吃掉回車符*/
i=LocateVex(*G,va);
j=LocateVex(*G,vb);
(*G).arcs[i][j].adj=(*G).arcs[j][i].adj=w;
/*無向*/
if(IncInfo)
{
printf("please input some information about the arc(<%d character): ",MAX_INFO);
gets(s);
w=strlen(s);
if(w)
{
info=(char*)malloc((w+1)*sizeof(char));
strcpy(info,s);
(*G).arcs[i][j].info=(*G).arcs[j][i].info=info;
/*無向*/
}
}
}
(*G).kind=DN;
return 1;
}
typedef struct
{/*記錄從頂點集U到V-U的代價最小的邊的輔助數組定義*/
VertexType adjvex;
VRType lowcost;
}minside[MAX_VERTEX_NUM];
int mininum(minside SZ,MGraph G)
{/*求closedege,lowcost的最小正值*/
int i=0,j,k,min;
while(!SZ[i].lowcost)
i++;
min=SZ[i].lowcost;
k=i;
for(j=i+1;j<G.vexnum;j++)
if(SZ[j].lowcost>0)
if(min>SZ[j].lowcost)
{
min=SZ[j].lowcost;
k=j;
}
return k;
}
void MiniSpanTree_PRIM(MGraph G,VertexType u)
{/*用普利姆演算法從第u個頂點出發構造網G的最小生成樹T，輸出T的各條邊*/
int i,j,k;
minside closedge;
k=LocateVex(G,u);
for(j=0;j<G.vexnum;++j)
/*輔助數組初始化*/
{
if(j!=k)
{ strcpy(closedge[j].adjvex,u);
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
closedge[k].lowcost=0;
/*初始U=*/
printf(":\n");
for(i=1;i<G.vexnum;++i)
{/*選擇其餘G.vexnum-1個頂點*/
k=mininum(closedge,G);
/*求出T的下一個結點：第K頂點*/
printf("(%s-%s)\n",closedge[k].adjvex,G.vexs[k]);
/*輸出生成樹的邊*/
closedge[k].lowcost=0;
/*第K頂點並入U集*/
for(j=0;j<G.vexnum;++j)
if(G.arcs[k][j].adj<closedge[j].lowcost)
{/*新頂點並入U集後重新選擇最小邊*/
strcpy(closedge[j].adjvex,G.vexs[k]);
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
}
void main()
{
MGraph G;
CreateAN(&G);
MiniSpanTree_PRIM(G,G.vexs[0]);
getch();
}

❼ 數據結構課程設計——構造可以使n個城市連接的最小生成樹

用Prim吧，我資料里有聯系方式

❽ 急求數據結構 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);
}