zuoye5.cpp

图论课程设计的左右

// zuoye5.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "iostream.h"
#include "stdio.h"
#include "stdlib.h"
#define   max 999

//*************************************************
struct element
{
	int dot1;
	int dot2;
	int length;
	element * next;
};
//*************************************************
element *list(int **p,int m)
{
	int i,j;
	element *head,*q,*t;
	head = NULL;
    for(i=1;i<m+1;i++)
		for(j=i+1;j<m+1;j++)
		{
			q=head;
			if(p[i][j]<max && p[i][j]!=0)
				if(q==NULL)
				{
					t=(element *)malloc (sizeof(element));
					t->dot1=i;
					t->dot2=j;
					t->length=p[i][j];
					t->next=q;
					head=t;
				}
				else
				{
					while(q->next!=NULL && q->next->length<p[i][j])
						q=q->next;
					t=(element *)malloc (sizeof(element));
					t->next=q->next;
                   	t->dot1=i;
					t->dot2=j;
					t->length=p[i][j];
					q->next=t;
				}

		}
	return head;
}
//**************************************************
int ** creat_array(int n)
{
	int **p;
	for(int i=0;i<n;i++)
		p=new int * [n];
	for(i=0;i<n;i++)
		p[i]=new int [n];
	return p;
}
//*************************************************
void kruskal(element*head,int m)
{
	int  *a=new int [m+1];
	element *p=head;
	int s,t;
	for(int i=0;i<m+1;i++)
		a[i]=i*(-1);
    i=0;
	while(a[0]<m-1 && p!=NULL)
	{
		s=p->dot1;
		t=p->dot2;
		if(a[t]!=a[s])
		{
			a[0]++;
			cout<<s<<" and "<<t<<"insert tree,and the length is "<<p->length<<endl;
			if(a[s]<0 && a[t]>0)
				a[s]=t;
			if(a[s]>0 && a[t]<0)
                a[t]=s;
			if(a[s]<0 && a[t]<0)
				a[s] = a[t] =++i;
			if(a[s]>0 && a[t]>0)
				for(int j=1;j<m+1;j++)
					if(a[i]==a[t])
						a[i]=a[s];
		}
		p=p->next;
	}

}
//*************************************************

int main(int argc, char* argv[])
{
	int **p;
	int m;
	element *head=NULL;
	cout<<"Please input the number of dot: "<<endl;
	cin >>m;
    p=creat_array(m+1);
	cout<<"Please input the lingjie juzh:"<<endl;
    for(int i=1;i<m+1;i++)
		for(int j=1;j<m+1;j++)
			cin>>p[i][j];   
	head=list(p,m);
	kruskal(head,m);
	return 0;
}