东北大学秦皇岛分校电子信息系。
最小生成树问题。
1需求分析。
1)在n个城市间建设通信网络，只需要架设n-1条线路即可。以最低的代价建设这个通信网，即求图的最小生成树。
2)利用克鲁斯卡尔算法求网的最小生成树。
3)利用自定义的队列结构存放连通分量。
4)以文本形式输出最小生成树中的各条边及它们的权值。输出格式为(int a,int b,int n),其中a，b为顶点序号，n为ab边的权；
5)程序运行流程：
1)提示输入顶点数目；
2)接受输入，按照项目要求产生边权值的随机矩阵；然后求解最小生成树；
3)输出最小生成树并且退出；
6)测试数据：9
2概要设计。
1表示边的类定义和接口。
class myarc
public:
int m_beginvex;
int m_endvex;
int m_weight;
myarc(int beginvex,int endvex,int weight);
myarc(){
//重载运算符。
inline bool operator < const myarc& arc)
2用邻接矩阵表示的图类的定义和接口。
class graph
private:
int m_vexnum;
int m_arcnum;
int *m_pmatrix;
public:
~graph();
graph(int vexnum);
graph(int vexnum,int *pmatrix);
void insert(myarc arc);/连通arc 边。
bool bound(int x); 判断顶点x是否已与其它顶点连通。
3自定义队列，用于存放连通图，或按权排列后的边。
class myqueues
public:
list m_list;
myqueues(){
void insert(const myarc& arc); 按权值大小排序插入。
void insertgraph(const graph &graph); 将图的连通分量插入队列。
myarc pop();出队列。
4本程序的结构。
1)主程序模块：
void main()
申明边权值矩阵数组并用随机函数初始化；
创建图；调用克鲁斯卡尔算法函数；
输出边的权值矩阵，最小生成树中的各条边及它们的权值；
退出；2)带权的边类模块---实现带权边的存储和运算。
邻接矩阵类模块---实现图的状态记录和相关操作。
自定义队列类模块---实现边的按权存贮和相关操作。
3)核心kruskal算法模块---用克鲁斯卡尔算法求出最小生成树
各模块调用关系。
3详细设计。
#include
#include<>/产生随机数组用。
#include<> 同上。
#include ""所用到的自定义数据结构定义和实现文件。
using namespace std;
#include
*mystack 堆栈类的结构 [ 0 1 ..curlen ..size] [栈底(bottomprt
#define basesize 64 //默认堆栈数组空间大小（8*8）,可以自扩充。
template
class mystack
private:
type *bottom; /元素存放的动态数组
int size,ptr; /堆栈大小和当前栈顶元素索引。
public:
//构造函数。
mystack()
析构函数。~mystack();
//清栈还原。
inline void clear()
//判栈空。
inline bool isempty()
//入栈。int push(type e);
//出栈。int pop(type &e);
//获得栈顶元素。
int top(type &e);
int settop(type e);
// 用callback函数对栈从低向上遍历。
void tr**erse(void callback(type *)type *)
private:
inline int extent()
*mystack的实现 */
*压栈*/template
int mystack::push(type e) /
if(++ptr==size) extent();
bottom[ptr]=e;
return ptr;
*出栈*/template
int mystack::pop(type &e) /
if(ptr==-1)
return -2;//栈空，返回 -2 ！
else e=bottom[ptr--]
return ptr;
*获取栈顶元素*/
template
int mystack::top(type &e) /
if(ptr==-1)
return -1;//栈空，返回 -1 ！
elsee=bottom[ptr];
return ptr;
*设置栈定元素*/
template
int mystack::settop(type e) /
if(ptr==-1)
return -1;//栈空，返回 -1 ！
elsebottom[ptr]=e;
return ptr;
*用callback函数对栈从低向上遍历*/
template
void mystack::tr**erse(void callback(type *)type *e)
if(callback!=null)
*mypoint 坐标结构 */
typedef struct mypoint
int x, y;
*pmypoint;
*表示边的类*/
class myarc
public:
int m_beginvex;
int m_endvex;
int m_weight;
myarc(int beginvex,int endvex,int weight);
myarc(){
bool operator < const myarc& arc)
bool operator ==const myarc& arc)
bool operator > const myarc& arc)
数据结构课程设计
课程设计说明书 题目哈夫曼编码问题的设计和实现。课程名称数据结构课程设计。院 系 部 中心。专业。班级。学生姓名。学号。设计地点。指导教师。设计起止时间 2008 年6月 2日至 2008 年 6月 6 日。目录。1 问题描述 2 1.1 题目内容 2 1.2 基本要求 2 1.3 测试数据 2 2...
数据结构课程设计
数据结构 课程设计。实验报告。学院 信息工程学院。班级 姓名 学号 指导老师 题目2 一元多项式的计算。1 实验目的。1 掌握链表的灵活运用 2 学习链表初始化和建立一个新的链表 3 知道怎样去实现链表删除结点操作与插入结点 4 理解链表的基本操作 包括数据域数据的相加 并能灵活运用。2 实验内容。...
数据结构课程设计
班级 信计 1102 姓名 李娜娜。学号 1108060209 设计日期 2013.07.15 西安科技大学计算机学院 1.实验题目 编制一个演绎扫雷游戏的程序。2.问题描述。做一个n x m的扫雷游戏，每个方格包含两种状态 关闭 closed 和打开 opened 初始化时每个方格都是关闭的，一个...