计算机软件基础数据结构作业题——管道铺设施工最佳方案 Prim算法

本人是南京航空航天大学的学生，我们的一个计算机软件基础大作业是编写4个程序，分别是约瑟夫斯问题、停车场管理、带权图的最小生成树提取、几种排序算法的比较。希望能够帮助到大家，尤其是南航的学弟学妹们！工程里面的注释写的很清楚，相信大家认真看能够理解。 最后我们还有一个Hololens的一个课设项目，混合现实的游戏王，最后做出来也会给大家分享的！ 希望大家别忘了给个好评吧，原创不易，这篇写的算很累了！

#include “stdio.h“
#include “stdlib.h“
#include “time.h“

#define MaxVertexNum 100 //设置小区数最多为100
#define VertexNum 9

double LeastNum;//用于记录最短边长度
double LongestNum;//用于记录最长边长度，程序过程中不改变

double adjacent[VertexNum][VertexNum];
//邻接矩阵，不用于处理数据，而是用于暂时存储从文件读来的数据 
//进而在邻接表存储数据时读取此数组数据即可 
//二维数组数据为0的元素说明之间没有通道 
//在处理完数据后，此数组会用来暂时存储处理后的数据，并写入到另一个文件中 

typedef struct node
{//边表结点
	char adjvex;
	double weight;//权值
	struct node *next;
}EdgeNode;

typedef struct vnode
{//顶点表结点
	char vertex;
	EdgeNode *firstedge;
}VertexNode;

typedef struct
{
	VertexNode adjlist[MaxVertexNum];
	int ne;
}ALGraph;

void PrintInformation1（）;//输出程序信息和个人信息
void PrintInformation2（）;//程序结束信息
void CreateALGraph（ALGraph *）;//将文件中数据导入进来构建无向图邻接表
void MinimumSpanningTree（ALGraph *）;//将无向图转化为最小生成树
void ResultOutput（double *arrayint n1int n2）;//将数据在控制台显示出来
void read_data（void）;//从输入文件读取数据到邻接矩阵 
void cout_data（void）;//将邻接矩阵中的数据输出到输出文件 
void read_array（double *arrayint n1int n2FILE *fp）;//内部函数，用户无需调用 
void cout_array（double *arrayint n1int n2FILE *fp）;//内部函数，用户无需调用 

void main（）
{
	ALGraph *G;
	PrintInformation1（）;
	G = （ALGraph*）malloc（sizeof（ALGraph））;
	G->n = VertexNum;//为G指向的图分配空间，设置点数（小区数）
	read_data（）; 
	CreateALGraph（G）;
	MinimumSpanningTree（G）;
	cout_data（）;//输出到文件 
	ResultOutput（（double *）adjacentVertexNumVertexNum）;//输出到控制台 
	PrintInformation2（）;
	system（“pause“）;
}

void PrintTime（）
{
	time_t t;
	time（&t）;
	printf（“%s“ ctime（&t））;
	printf（“\r\n“）;
}

void PrintInformation1（）
{
	printf（“实验名称:实验三.管道铺设施工的最佳方案问题\r\n“）;
	printf（“学号:xxxxxxxxx（程序中修改）\r\n“）;
	printf（“姓名:老郭（本人绰号）\r\n“）;
	printf（“====================\r\n“）;
	printf（“程序运行开始Current local time and date:“）;
	PrintTime（）;
}

void PrintInformation2（）
{
	printf（“\r\n====================\r\n“）;
	printf（“程序运行结束Current local time and date:“）;
	PrintTime（）;
}

void CreateALGraph（ALGraph *G）
{
	//建立无向图的邻接表存储
	int i=0j=0k=0;
	EdgeNode *s;
	for （i = 0; i < G->n; i++）
	{
		G->adjlist[i].vertex = 65 + i;
		printf（“\t%c“ （G->adjlist[i].vertex））;//控制台输出列表头
		G->adjlist[i].firstedge=NULL;
	}
	printf（“\n“）;
	for（k=0;kn;k++）
	{
		for（j=0;jn;j++）
		{
			if（adjacent[k][j]!=0）
			{
				s = （EdgeNode*）malloc（sizeof（EdgeNode））;
				s->adjvex = 65+j;
				s->weight=adjacent[k][j];
				s->next = G->adjlist[k].firstedge;
				G->adjlist[k].firstedge = s;
			}
		}
	}
}

void read_data（void）
{
  int ij;
  FILE *fp;
  fp=fopen（“gyp_program3_Input.dat““r“）;  // 输入数据文件 
  read_array（（double *）adjacentVertexNumVertexNumfp）;
  fclose（fp）;
  for （i = 0; i < VertexNum; i++）
  {
	  for （j = 0; j < VertexNum; j++）
	  {
		  if （adjacent[i][j] > LongestNum）
		  {
			  LongestNum = adjacent[i][j];//即给LongestNum设置的初值为最大边边值
		  }
	  }
  }
}

void read_array（double *arrayint n1int n2FILE *fp）
{
  int ij;
  float q;
  for（i=0;i	  for（j=0;j	  { 
		  fscanf（fp“%f“&q）; 
		  *array++ 

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2018-10-20 15:22  gyp_program3\.vs\
     目录           0  2018-10-20 15:22  gyp_program3\.vs\gyp_program3\
     目录           0  2018-11-06 21:36  gyp_program3\.vs\gyp_program3\v15\
     文件       26112  2018-11-06 21:36  gyp_program3\.vs\gyp_program3\v15\.suo
     文件     1818624  2018-11-06 21:36  gyp_program3\.vs\gyp_program3\v15\Browse.VC.db
     目录           0  2018-10-20 15:22  gyp_program3\.vs\gyp_program3\v15\ipch\
     目录           0  2018-10-20 22:01  gyp_program3\.vs\gyp_program3\v15\ipch\AutoPCH\
     目录           0  2018-10-21 10:44  gyp_program3\.vs\gyp_program3\v15\ipch\AutoPCH\1a465263fa0f3cf4\
     文件     2555904  2018-11-06 21:35  gyp_program3\.vs\gyp_program3\v15\ipch\AutoPCH\1a465263fa0f3cf4\GYP_PROGRAM3.ipch
     目录           0  2018-10-20 15:22  gyp_program3\.vs\gyp_program3\v15\ipch\AutoPCH\c44db10c3fc72864\
     文件     2621440  2018-10-20 15:19  gyp_program3\.vs\gyp_program3\v15\ipch\AutoPCH\c44db10c3fc72864\GYP_PROGRAM3.ipch
     目录           0  2018-10-22 17:01  gyp_program3\Debug\
     文件       41472  2018-11-06 21:36  gyp_program3\Debug\gyp_program3.exe
     文件      368352  2018-11-06 21:36  gyp_program3\Debug\gyp_program3.ilk
     文件      561152  2018-11-06 21:36  gyp_program3\Debug\gyp_program3.pdb
     文件         255  2018-09-28 20:49  gyp_program3\Debug\gyp_program3_Input.dat
     文件         392  2018-11-06 21:36  gyp_program3\Debug\gyp_program3_Output.dat
     文件      413696  2018-10-12 17:50  gyp_program3\gyp_program3.sdf
     文件         903  2018-09-20 16:11  gyp_program3\gyp_program3.sln
     文件       11776  2018-10-12 17:50  gyp_program3\gyp_program3.suo
     目录           0  2018-11-06 21:36  gyp_program3\gyp_program3\
     目录           0  2018-10-21 10:44  gyp_program3\gyp_program3\Debug\
     文件        1185  2018-10-21 10:44  gyp_program3\gyp_program3\Debug\gyp_program3.Build.CppClean.log
     文件         128  2018-11-06 21:36  gyp_program3\gyp_program3\Debug\gyp_program3.log
     文件       25970  2018-11-06 21:36  gyp_program3\gyp_program3\Debug\gyp_program3.obj
     目录           0  2018-11-06 21:36  gyp_program3\gyp_program3\Debug\gyp_program3.tlog\
     文件         674  2018-11-06 21:36  gyp_program3\gyp_program3\Debug\gyp_program3.tlog\CL.command.1.tlog
     文件        2946  2018-11-06 21:36  gyp_program3\gyp_program3\Debug\gyp_program3.tlog\CL.read.1.tlog
     文件         504  2018-11-06 21:36  gyp_program3\gyp_program3\Debug\gyp_program3.tlog\CL.write.1.tlog
     文件         232  2018-11-06 21:36  gyp_program3\gyp_program3\Debug\gyp_program3.tlog\gyp_program3.lastbuildstate
     文件        1158  2018-11-06 21:36  gyp_program3\gyp_program3\Debug\gyp_program3.tlog\link.command.1.tlog
............此处省略17个文件信息