最小生成树数据结构课程设计

❶ 数据结构课程设计 谁能帮下啊！！！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);
}