C数据结构最小生成树的构造

C数据结构课的一个实验,用Prim算法和Kruskal算法实现最小生成树,

#include 
#include “pro.h“
using namespace std;

/*
**建立一个顶点的存储数组。数组类型就是顶点的类型，
**n是顶点的个数，返回建立好的数组地址。
*/
elementtype* HeadArray1（int n）        //用完后要free。
{
    int i;
    elementtype* q=（elementtype*）malloc（n*sizeof（elementtype））;
    cout<<“输入各个结点\n“;
    for （i=0; i    {
        cin>>q[i];
    }
    return q;
}

/*
**建立一个邻居矩阵。参数是：n为顶点个数，m为边的个数
**q是定点的存储数组，即是上个函数的建立结果
*/
int* build_juzheng（int n int m elementtype* q）   //注意要free
{
    int* p=（int*）malloc（n*n*sizeof（int））;
    int ijflag k c;
    elementtype x y;

    for （i=0; i<=n; i++）
        for （j=0; j<=n; j++）
            p[i*n+j]=MAX;

    cout<<“输入各个边及其权值:\n“;
    for （k=0; k    {
        cin>>x>>y>>c;
        flag=0;
        for （i=1; i        for （j=1; j        if （i>=n || j>=n）flag=1;
        if （!flag）
        {
            p[i*n+j]=c;
            p[j*n+i]=c;
        }
        else
        {
            cout<<“不存在该边，重输：\n“;
            k--;
        }
    }
    return p;
}

/*
**建立邻接表的顶点数组，输入时顶点个数n和顶点数组head1
**返回建立的邻接表的顶点的结构数组。
*/
cell* HeadArray2（int n elementtype* head1）    // 注意要free
{
    cell* head=（cell*）malloc（n*sizeof（cell））;
    int i;
    for （i=0; i    {
        head[i].data=head1[i];
        head[i].next=NULL;
    }
    return head;
}

/*
**建立邻接表。参数是顶点个数n，边的个数m，顶点的结构数组head。
**即上个函数建立的数组
*/
void build_biao（int nint m cell* head） //n为顶点的个数m为边的个数，head为顶点结点数组首地址
{
    int iflag j k c;
    elementtype x y;
    edgecell* p;
    cout<<“输入边及其权值：\n“;
    for （j=0; j    {
        cin>>x>>y>>c;
        flag=0;
        for （i=0; i        for （k=0; k        if （i>=n || k>=n）flag=1;
        if （!flag）
        {
            p=new edgecell;
            p->cost=c;
            p->num=k;
            p->next=head[i].next;
            head[i].next=p;

            p=new edgecell;
            p->cost=c;
            p->num=i;
            p->next=head[k].next;
            head[k].next=p;
        }
        else
        {
            cout<<“不存在该边，重输：\n“;
            j--;
        }
    }
}

/*
**为了实现一种搜索算法对两个存储方式都好用，自己写了一个从
**邻接矩阵到邻接表的转换函数。自己只写了邻接表的访问我建立最
**小生成树。所以需要转换 。参数是head1顶点的数组，head2顶点的
**存储矩阵，n是顶点的个数
*/
cell* juzhengTObiao（elementtype* head1 int* head2 int n）//head1是存储顶点的字符数组，head2是邻接矩阵的首地址，n是顶点个数
{
    cell* head=HeadArray2（n head1）;
    edgecell* p;
    int i j;

    for （i=0; i    {
        for （j=0; j        {
            if （head2[i*n+j]）
            {
                p=new edgecell;
                p->num=j;
                p->next=head[i].next;
                head[i].next=p;
            }
        }
    }
    return head;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       3304  2009-05-27 07:06  shengchengshu\G_func.cpp

     文件       1328  2009-05-26 20:40  shengchengshu\pro.h

     文件       1180  2009-05-25 21:27  shengchengshu\shengchengshu.cbp

     文件        904  2009-05-27 06:46  shengchengshu\main.cpp

     文件        106  2009-05-26 10:05  shengchengshu\1.txt

     文件        760  2009-06-02 21:18  shengchengshu\shengchengshu.layout

     文件         65  2009-05-26 10:15  shengchengshu\2.txt

     文件       1788  2009-05-27 07:06  shengchengshu\G_view.cpp

     文件     118934  2009-05-27 06:46  shengchengshu\obj\Debug\main.o

     文件     120980  2009-05-27 07:06  shengchengshu\obj\Debug\G_func.o

     文件     119322  2009-05-27 07:06  shengchengshu\obj\Debug\G_view.o

     文件     118000  2009-05-27 07:06  shengchengshu\obj\Debug\queue_func.o

     文件     120529  2009-05-27 07:06  shengchengshu\obj\Debug\G_build.o

     文件       3218  2009-05-27 07:06  shengchengshu\G_build.cpp

     文件     602312  2009-05-27 07:06  shengchengshu\shengchengshu.exe

     文件      77312  2009-05-28 14:36  shengchengshu\最小生成树的构造算法.doc

     文件        528  2009-05-27 07:06  shengchengshu\shengchengshu.depend

     文件        926  2009-05-27 07:06  shengchengshu\queue_func.cpp

     目录          0  2009-05-25 19:02  shengchengshu\obj\Debug

     目录          0  2009-05-25 19:02  shengchengshu\obj

     目录          0  2009-05-25 19:00  shengchengshu

----------- ---------  ---------- -----  ----

              1291496                    21