《数据结构与算法》
课程设计报告
学 号：班级序号：姓 名： 陶 剑 浩
指导教师： 吴 亮
成 绩：
中国地质大学（武汉）信息工程学院
20xx年1月
中国地质大学 数据结构实习报告 陶剑浩
目录
一、软件压缩/解压缩软件 Szip（Huffman 算法及应用） ................................................. 2
1．需求规格说明 .............................................................................................................. 2
2．总体分析与设计 .......................................................................................................... 2
3．编码 .............................................................................................................................. 5
4．程序及算法分析 .......................................................................................................... 5
5．小结 .............................................................................................................................. 7
6．附录 .............................................................................................................................. 7
二、电话簿软件的实现（动态查找表算法的应用） .......................................................... 17
1．需求规格说明 ............................................................................................................ 17
2．总体分析与设计 ........................................................................................................ 18
3．编码 ............................................................................................................................ 19
4．程序及算法分析 ........................................................................................................ 19
5．小结 ............................................................................................................................ 20
6．附录 ............................................................................................................................ 20
三、管道铺设施工的最佳方案选择（选做，加分题） ...................................................... 39
1．需求规格说明 ............................................................................................................ 39
2．总体分析与设计 ........................................................................................................ 39
3．编码 ............................................................................................................................ 41
4．程序及算法分析 ........................................................................................................ 41
5．小结 ............................................................................................................................ 43
6．附录 ............................................................................................................................ 43
四、总结 .................................................................................................................................. 51
五、参考资料 .......................................................................................................................... 51
- 1 -
中国地质大学 数据结构实习报告 陶剑浩
一、软件压缩/解压缩软件 Szip
（Huffman 算法及应用）
1．需求规格说明
利用哈夫曼编码进行对已有文件进行重新编码可以大大提高减小文件大小，减少存储空 间。但是，这要求在首先对一个现有文件进行编码行成新的文件，也就是压缩。在文件使用 时，再对压缩文件进行解压缩，也就是译码，复原原有文件。试为完成此功能，写一个压缩 /解压缩软件。
2．总体分析与设计
（1）设计思想：
哈夫曼树又称最优二叉树，是带权路径长度最小的二叉树。在文本文件中多采用二进制编码。为了使文件尽可能的缩短，可以对文件中每个字符出现的次数进行统计。设法让出现次数多的字符二进制码短些，而让那些很少出现的字符二进制码长一些。若对字符集进行不等长编码，则要求字符集中任一字符的编码都不是其它字符编码的前缀。为了确保哈夫曼编码的唯一性，我们可以对它的左右子树的大小给予比较限定，如：左子树的权值小于右子树的权值。哈夫曼树中的左右分支各代表‘0’和‘1’,则从根节点到叶子节点所经历的路径分支的‘0’和‘1’组成的字符串，为该节点对应字符的哈夫曼编码。
统计字符中每个字符在文件中出现的平均概率（概率越大，要求编码越短）。利用哈夫曼树的特点：权越大的叶子离根越近，将每个字符的概率值作为权值，构造哈夫曼树。则概率越大的节点，路径越短。哈夫曼译码是从二进制序列的头部开始，顺序匹配成功的部分替换成相应的字符，直至二进制转换为字符序列。
哈夫曼用于文件解压缩的基础是在压缩二进制代码的同时还必须存储相应的编码，这样就可以根据存储的哈夫曼编码对压缩代码进行压缩。首先要打开要压缩的文本文件并读出其字符出现的频率，以其为权值构建哈夫曼树。其次要找到构建压缩功能的方法，在构建哈夫曼树的基础上进行编码，改变字符原先的存储结构，以达到压缩文件的目的，以外还有存储相应的哈夫曼编码，为解压缩做准备。
（2）设计表示：
- 2 -
中国地质大学 数据结构实习报告 陶剑浩
//huffman树的结点结构体
typedef struct HTnode
{
long weight; //记录结点的权值
int parent; //记录结点的双亲结点位置
int lchild; /结点的左孩子
int rchild; //结点的右孩子
int *code; //记录该结点的huffman编码
int codelen; //记录该结点huffman编码的长度
//初始化结点，令其权值为无穷大，无双亲及左右孩子
HTnode()
{
weight = MAX;
parent = -1;
lchild = -1;
rchild = -1;
codelen = 0;
}
}HTnode;
//huffman树类及其函数
class huffmanTree
{
public:
huffmanTree();
virtual ~huffmanTree();
bool count(char *input); //压缩时统计各字符出现的次数，将其写入对应结点的权值 void create(); //压缩时根据各结点的权值构造huffman树
void code(); //压缩时利用huffman树计算每个字符的huffman编码
void printcode(); //列出每个字符的huffman编码
void addbit(int bit); //压缩时对一个未满8个bit的byte中加入一个bit
void resetbyte(); //将byte清空
bool compress(char *input, char *output);//压缩函数,成功返回 true 失败 false bool decompress(char *input, char *output); //恢复函数,成功返回 true 失败false void compare(char *input, char *output); //将原文件与压缩后的文件比较
void compare2(char *input, char *output); //将原文件与恢复后的文件比较
private:
int root; //记录根结点的位置
int leafnum; //记录不同字符的个数
HTnode HT[leaf*2-1]; //HTnode结构的数组，用来表示huffman树，树的最大结点个数不会超过leaf*2-1
char byte; //压缩文件时用来缓冲bit的变量
int bitsnum; //byte中bit的个数
int lacknum; //压缩到最后byte中的bit不满8个时填充的0的个数
};
主程序的流程及模块间关系：
主函数实例化huffmanTree类，并实现菜单工具栏，通过用户的选择输入，用switch语
- 3 -
中国地质大学 数据结构实习报告 陶剑浩
句进行分支执行huffmanTree类中功能函数：
1:压缩函数 bool compress(char *input, char *output) 2:恢复函数 bool decompress(char *input, char *output)
3:恢复文件与原文件的对比函数 void compare2(char *input, char *output) 并可在完成相应功能后安全退出，压缩或恢复的文件在同文件夹下生成。 （3）详细设计表示：
核心算法----huffman算法：根据给定的n个权值｛w1,w2,??,wn｝构成n棵二叉树的集合F=｛T1,T2,??,Tn｝,其中每棵二叉树T1中只有一个带权的 w1的根据点，其左右子树均空。在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右树上根结点的权值之和。在F中删除这两棵树，同时将所得到的二叉树加入F中。重复,直到F中只含一棵树为止。这棵树便是Huffman树。HuffmanHuffman
Huffman
中国地质大学 数据结构实习报告 陶剑浩
图 解码流程
3．编码
问题：huffman编码是采用等长编码还是采用不等长问题，采用不等长编码要避免译码的二义性或多义性。假设用0表示字符D,用01表示字符C则当接受到编码串“?01?”，并译到字符0时，是立即译出对应的字符D，还是接着与下一个字符1一起译为对应的字符C，这就产生了二义性。因此，若对某一个字符集进行不等长编码，则要求字符集合中任何一个字符的编码都不能是其他字符编码的前缀。符合此要求的编码叫做前缀编码。显然等长编码是前缀编码，这从等长编码所对应的编码二叉树也可以直接看出，任何一个叶子结点都不可能是其它叶子结点的双亲，也就是说，只有当一个结点是另一个结点的双亲时，该结点的字符编码才会是另一个结点的字符编码的前缀。
解决方法：可用该字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得文件的最短长度，特将每个字符的出现频率作为字符结点的权值赋予该结点上，求出此树的最小带权路径长度就等于文件的最短长度。因此，对文件进行压缩，就可以转化字符集中的所有字符作为叶子结点，字符出现的频率作为权值所产生的 huffman树的问题。
4．程序及算法分析
程序运行结果：
- 5 -
中国地质大学 数据结构实习报告 陶剑浩
- 6 -
中国地质大学 数据结构实习报告 陶剑浩
时间复杂度：大部分函数应在O(?2) 。
5．小结
第一题的实习让我了解了对Huffman的理解运用，对压缩软件有了更深的认识。同时对于存储数据的结构优化重要性有了深刻的认识。
6．附录
//huffmanTree.cpp
#include "stdafx.h"
#include "huffmanTree.h"
huffmanTree::huffmanTree()
{
//初始化成员变量
root = 0;
leafnum = 0;
byte = 0;
bitsnum = 0;
lacknum = 0;
}
huffmanTree::~huffmanTree()
{
for (int i = 0; i<leaf; i++)
{
if (HT[i].codelen != 0)
delete[]HT[i].code;
}
}
//统计各字符出现的次数
- 7 -
中国地质大学 数据结构实习报告 陶剑浩 bool huffmanTree::count(char *input)
{
ifstream ifs;
char c;
ifs.open(input, ios::binary);
if (!ifs){
cout << "无法打开文件 " << input << '!' << endl;
return false;
}
while (ifs.get(c)){
if (HT[c + 128].weight == MAX){ //若该字符是第一次出现，先初始化权值 HT[c + 128].weight = 0;
leafnum++;
}
HT[c + 128].weight++; //权值+1
}
ifs.close();
return true;
}
//选权值最小的两棵树组成新的数
void huffmanTree::create()
{
for (int i = leaf; i<2 * leaf - 1; i++)
{
int loc1 = -1, loc2 = -1;
for (int j = 0; j<i; j++){
if (HT[j].parent != -1)
continue;
if (loc1 == -1 || HT[j].weight < HT[loc1].weight)
{
loc2 = loc1;
loc1 = j;
}
else if (loc2 == -1 || HT[j].weight < HT[loc2].weight)
loc2 = j;
}
if (HT[loc1].weight == MAX || HT[loc2].weight == MAX || loc2 == -1) //只剩一棵树，结束
break;
HT[i].weight = HT[loc1].weight + HT[loc2].weight;
//为了减少压缩文件中需要写入的huffman树的信息，约定小标小的结点做为双亲结点的左孩子
HT[i].lchild = loc1>loc2 ? loc2 : loc1;
- 8 -
中国地质大学 数据结构实习报告
HT[i].rchild = loc1>loc2 ? loc1 : loc2;
HT[loc1].parent = i; HT[loc2].parent = i;
root = i;
}
}
//列出每个字符的huffman编码
void huffmanTree::printcode()
{
for (int i = 0; i<leaf; i++)
{
if (HT[i].codelen != 0){
cout << "值为" << i - 128 << "的字符的huffman编码："; for (int j = 0; j<HT[i].codelen; j++)
{
cout << HT[i].code[j];
}
cout << endl;
}
}
}
//压缩时，利用建好的huffman树计算每个字符的huffman编码
void huffmanTree::code()
{
for (int i = 0; i<leaf; i++)
{
int len = 0;
int loc = i;
while (HT[loc].parent != -1)
{ huffman编码长度
len++;
loc = HT[loc].parent;
}
HT[i].codelen = len;
HT[i].code = new int[len];
loc = i;
for (int j = len - 1; j >= 0; j--)
{ 找，记录结点的huffman编码
if (loc == HT[HT[loc].parent].lchild)
HT[i].code[j] = 0;
else
陶剑浩 //计算//从后往前- 9 -
中国地质大学 数据结构实习报告 陶剑浩 HT[i].code[j] = 1;
loc = HT[loc].parent;
}
}
}
//压缩时对一个未满8个bit的byte中加入一个bit
void huffmanTree::addbit(int bit)
{
if (bit == 0) byte = byte << 1; //若新增的bit为0，则直接将byte按位左移
else
byte = ((byte << 1) | 1); //若新增的bit为1，先将byte按位左移，再与1按位或运算
bitsnum++;
}
//将byte清空
void huffmanTree::resetbyte()
{
byte = 0;
bitsnum = 0;
}
//压缩函数 成功执行返回 true 失败 false
bool huffmanTree::compress(char *input, char *output)
{
if (!count(input))
return false;
create();
code();
ifstream ifs;
ofstream ofs;
ifs.open(input, ios::binary);
ofs.open(output, ios::binary);
char c;
if (!ifs)
{
cout << "无法打开文件 " << input << '!' << endl;
return false;
}
if (!ofs)
- 10 -
中国地质大学 数据结构实习报告 陶剑浩 {
cout << "无法打开文件 " << output << '!' << endl;
return false;
}
ofs.put(0); //预留一个字符，等压缩完后在该位置写入不足一个byte的bit个数
ofs.put(root - 384); //将根节点的位置-384写入（为使该值不超过char的最大表示范围）
for (int i = 0; i<leaf * 2 - 1; i++)
{ //写入每个结点的双亲结点位置
if (HT[i].parent == -1) //若该节点没有双亲结点，则写入127(一个字节所能表示的最大值)
ofs.put(127);
else //否则将双亲结点的位置-384再写入（为使该值不超过char的最大表示范围）
ofs.put(HT[i].parent - 384);
}
while (ifs.get(c))
{ //将字符的huffman编码并加入byte中 int tmp = c + 128;
for (int i = 0; i<HT[tmp].codelen; i++)
{
addbit(HT[tmp].code[i]);
if (bitsnum == 8)
{ //若byte已满8位，则输出该byte并将byte清空
ofs.put(byte);
resetbyte();
}
}
}
if (bitsnum != 0){ //处理最后未满8个字符的byte，用0填充并记录填充的个数
for (int i = bitsnum; i<8; i++)
{
addbit(0);
lacknum++;
}
ofs.put(byte);
resetbyte();
}
ofs.seekp(0, ios::beg); //将写指针移动到文件开头
- 11 -
中国地质大学 数据结构实习报告 陶剑浩 ofs.put(lacknum); //写入最后一个字节缺失的bit个数 ifs.close();
ofs.close();
return true;
}
//恢复函数 成功执行返回 true 失败 false
bool huffmanTree::decompress(char *input, char *output)
{
queue<char> q;
char c;
ifstream ifs;
ofstream ofs;
ifs.open(input, ios::binary);
ofs.open(output, ios::binary);
if (!ifs)
{
cout << "无法打开文件 " << input << '!' << endl;
return true;
}
if (!ofs)
{
cout << "无法打开文件 " << output << '!' << endl;
return false;
}
ifs.get(c);
lacknum = c; //读出最后一个字节缺失的bit个数
ifs.get(c);
root = c + 384; //读出根结点的位置
for (int i = 0; i<leaf * 2 - 1; i++)
{ //建立各结点之间的双亲孩子关系 ifs.get(c);
if (c == 127)
continue;
else
{
HT[i].parent = c + 384;
if (HT[c + 384].lchild == -1)
HT[c + 384].lchild = i;
else
HT[c + 384].rchild = i;
}
}
- 12 -
中国地质大学 数据结构实习报告
int point = root;
//为了方便处理最后一个可能有缺失bit的字节，先将读出的数据放入队列 while (ifs.get(c))
q.push(c);
//还原文件过程
while (q.size()>1)
{ //还未到最后一个字节
c = q.front();
for (int i = 0; i<8; i++)
{
if (int(c & 128) == 0)
{
point = HT[point].lchild;
if (HT[point].lchild == -1 && HT[point].rchild == -1) {
ofs.put(char(point - 128));
point = root;
}
c = c << 1;
}
else
{
point = HT[point].rchild;
if (HT[point].lchild == -1 && HT[point].rchild == -1) {
ofs.put(char(point - 128));
point = root;
}
c = c << 1;
}
}
q.pop();
}
c = q.front(); //最后一个字节 for (int i = 0; i<8 - lacknum; i++)
{
if (int(c & 128) == 0)
{
point = HT[point].lchild;
if (HT[point].lchild == -1 && HT[point].rchild == -1) {
ofs.put(char(point - 128));
陶剑浩 - 13 -
中国地质大学 数据结构实习报告
point = root;
}
c = c << 1;
}
else{
point = HT[point].rchild;
if (HT[point].lchild == -1 && HT[point].rchild == -1) {
ofs.put(char(point - 128));
point = root;
}
c = c << 1;
}
}
q.pop();
ifs.close();
ofs.close();
return true;
}
//将原文件与压缩后的文件比较
void huffmanTree::compare(char *input, char *output)
{
ifstream origin, compress;
origin.open(input, ios::binary);
compress.open(output, ios::binary);
if (!origin)
{
cout << "无法打开文件 " << input << '!' << endl;
return;
}
if (!compress)
{
cout << "无法打开文件 " << output << '!' << endl; return;
}
double total1 = 0, total2 = 0;
char c;
while (origin.get(c))
total1++;
while (compress.get(c))
total2++;
cout << "原文件大小：" << total1 << " Byte" << endl;
陶剑浩 - 14 -
中国地质大学 数据结构实习报告
cout << "压缩后大小：" << total2 << " Byte" << endl;
cout << "压缩率：" << total2 / total1 * 100 << '%' << endl; origin.close();
compress.close();
}
//将原文件与恢复后的文件比较 void huffmanTree::compare2(char *input, char *output)
{
ifstream origin, decompress;
origin.open(input, ios::binary);
decompress.open(output, ios::binary);
double total1 = 0, total2 = 0;
char c1, c2;
bool dif = false;
while (origin.get(c1) && decompress.get(c2))
{
if (c1 != c2) //依次比较每个字节，不同则将dif标志设为true dif = true;
total1++;
total2++;
}
while (origin.get(c1))
{ //若原文件还有剩余的数据，将dif设为true
dif = true;
total1++;
}
while (decompress.get(c2))
{ //若恢复文件还有剩余的数据，将dif设为true
dif = true;
total2++;
}
cout << "原文件大小：" << total1 << " Byte" << endl;
cout << "恢复文件大小：" << total2 << " Byte" << endl; if (dif == true)
cout << "原文件与恢复文件不同!" << endl;
else
cout << "原文件与恢复文件相同!" << endl;
origin.close();
decompress.close();
}
//main.cpp
陶剑浩 - 15 -
中国地质大学 数据结构实习报告 陶剑浩 #include "stdafx.h"
#include "huffmanTree.h"
void main()
{
int choice = 1;
char input[255], output[255];
huffmanTree h;
while (choice)
{
cout << " ***************************************************" << endl;
cout << " * 软件压缩/解压缩软件 Szip *" << endl;
cout << " * *" << endl;
cout << " * *" << endl;
cout << " * 输入字符选择功能： *" << endl;
cout << " * 1:压缩 2:解压 3:压缩比 4:初始化 5:退出 *" << endl;
cin >> choice;
switch (choice)
{
case 1:
{
cout << "请输入要压缩的文件绝对路径：";
cin >> input;
cout << "请输入压缩后的文件绝对路径：";
cin >> output;
if (h.compress(input, output))
{
h.printcode();
h.compare(input, output);
cout << endl << "文件压缩成功!" << endl;
}
else
{
cout << endl << "文件压缩失败!" << endl;
}
}
break;
case 2:
- 16 -
中国地质大学 数据结构实习报告 陶剑浩
} } { cout << "请输入解压缩的文件名："; cin >> input; cout << "请输入解压后的文件名："; cin >> output; if (h.decompress(input, output)) cout << endl << "文件解压成功!" << endl; else cout << endl << "文件解压失败!" << endl; } break; case 3: { cout << "请输入源文件的文件名："; cin >> input; cout << "请输入解压后的文件名："; cin >> output; h.compare2(input, output); } break; case 4: { //执行清屏命令 system("cls"); } break; case 5: break; default: cout << "参数错误！请重新输入" << endl; } cout << endl;
二、电话簿软件的实现（动态查找表算
法的应用）
1．需求规格说明
- 17 -
中国地质大学 数据结构实习报告 陶剑浩
在很多实际应用中，动态索引结构在文件创建或初始装入记录时生成，在系统运行过程 中插入或删除记录时，为了保持较好的检索性能，索引结构本身将随之发生改变。教材上已 经介绍的动态查找数据结构包括：二叉搜索树（BST）、平衡二叉树（AVL）、红黑树（RBT）、 B-树。本题要求选取一种已经学过的动态搜索树结构，设计并实现一个手机电话薄软件。
2．总体分析与设计
（1） 设计思想：
使用二叉搜索树来实现这个问题，而搜索树中进行比较大小的数据是成员的名字。类中有一些成员函数和成员变量。主要的设计思路是这样的：在类生成的时候，记录中就有一条记录，这个记录是：姓名，电话号码，手机号码，邮箱。这是初始值，现在用户可以进行添加、删除、修改、等一系列操作，还有一个操作是能够将txt中的数据读入之后将这些数据 利用修改过的插入函数初始化到对象中去。这是一个多个数据的循环录入。
（2） 设计表示：
在插入函数中，调用c++的string类的compare函数， 这个函数可以比较任意两个字符串的大小关系。 删除函数 。这个函数的情况比较多，处理方式也比较复杂。 当要删除一个节点并且这个节点是唯一的结点时，要将删除后的对象标记为空的对象。如果没有节点时，当然是不能删除的；修改函数，这个函数要进行寻找结点之后再进行修改操作；查询函数，就是用户输入号码，用这个号码来寻找树中与这个名字相同的人，如果找到就将电话本中这个人的信息输出给用户看，如果没找到就输出没找到的信息。
（3） 详细设计表示：树中的每一个节点包含特定人员的数据。人名是查找关键字，是可
在图中看到的数据项： //存储的结构体
struct myItem
{
string Name;
string Telphonenumber;
string Homenumber;
string Officenumber;
string Email;
string Group;
string Note;
};
因为二叉查找树的本质上是递归的，所以很自然为树的操作设计递归算法。假设要在图1的二叉树中查找Ellen的记录。Jane在树的根节点中，所以若树中存在Ellen的记录，则必然在Jane的左子树中，因为按字母顺序，查找关键字Ellen在查找关键字Jane之前。有递归的定义知，Jane的左子树也是二叉树，因此可用完全相同的策略，在子树中查找ELlen。Bob是这个二叉查找树的根，因为关键字Ellen大于关键字Bob，所以Ellen的记录必然在Bob的右子树中。Bob的右子树也是二叉查找树，而Ellen正好在该树的叶节点中。这样就找到了Ellen的记录。
- 18 -
中国地质大学 数据结构实习报告 陶剑浩
图1：二叉查找树
search算法是二叉查找树的插入、删除和检索操作的基础。
时间复杂度：本程序二叉搜索树函数应在O(n)，无法达到最优二叉树的O(log2?)。
3．编码
在增加文件输入输出的部分，使用静态成员可以使这个流对象仅被初始化一次；在利用文件初始化时，改变了文件的格式，就是在文件头加上一个个数的整型，使整个初始化函数得到简化。
4．程序及算法分析
导入：
查找：
- 19 -
中国地质大学 数据结构实习报告 陶剑浩
其余演示略去
使用说明：一个文本文档txt，在里面按照这个格式写东西： 总记录条数；记录一名字 记录一电话号码 记录一手机号码??记录一邮箱 记录二名字 记录二电话号码?? 记录二手机号码 记录二邮箱 记录N名字 记录N电话号码?? 记录N手机号码 记录N邮箱。 再使用初始化函数将这个电话本导入；还可以自己选择一个一个添加记录，还可以删除、修改、查询等等操作。 然后调用浏览函数就可以将电话本按照中序遍历输出，而且此时可以输出到下面的txt中去，将这个文本中的数据拷贝到txt中去，就可以作为下一次的初始化电话薄.。
5．小结
主要利用二叉搜索树结构理论来设计手机电话薄软件，有一些优点如简洁，迅速等；但是需要改进的地方就是代码冗余较大，基本上功能相似的代码有许多段，导致代码长度较大，这个可以用包装的思想进行减少。
6．附录
//PhoneBook.h #ifndef PhoneBook_
#define PhoneBook_
#include "bbinary.h"
#include "xcept.h"
#include "Item.h"
class PhoneBook:
public BinaryTree<myItem>
{
public:
- 20 -
中国地质大学 数据结构实习报告
bool SearchName(const string& name, myItem& item) const; static void SearchGroup(BinaryTreeNode<myItem> * i);
bool SearchName(const string& name) const;
bool SearchNumber(const string& number, myItem& item) const; PhoneBook& Insert(const myItem& item);
PhoneBook& Delete(const string& name, myItem& item);
static void Write(BinaryTreeNode<myItem> * i);
void FindGroup();
void PreWrite();
friend class Item;
private:
};
#endif
//PhoneBook.cpp bool PhoneBook::SearchName(const string& name, myItem& item) const{
BinaryTreeNode<myItem> *p = root;
while (p) // examine p->data
if (name< (p->data).Name) p = p->LeftChild;
else if (name> (p->data).Name) p = p->RightChild; else {// found element
item= p->data;
return true;}
return false;
}
void PhoneBook::PreWrite()
{
PreOrder(Write,root);
}
void PhoneBook::Write(BinaryTreeNode<myItem> * i)
{
ofstream file("PhoneBook.txt", ios::app);
陶剑浩 - 21 -
中国地质大学 数据结构实习报告 if (i->data.Name!="")
{
file<<"姓名：";
file<<i->data.Name;
file<<" ";
}
if (i->data.Telphonenumber!="")
{
file<<"手机号码：";
file<<i->data.Telphonenumber;
file<<" ";
}
if (i->data.Homenumber != "")
{
file << "手机号码：";
file << i->data.Homenumber;
file << " ";
}
if (i->data.Officenumber!="")
{
file<<"办公号码:";
file<<i->data.Officenumber;
file<<" ";
}
if (i->data.Email!="")
{
file<<"电子邮件:";
file<<i->data.Email;
file<<" ";
}
if (i->data.Group!="")
{
file<<"所属群组:";
file<<i->data.Group;
file<<" ";
}
陶剑浩 - 22 -
中国地质大学 数据结构实习报告 陶剑浩
if (i->data.Note!="")
{
file<<"备忘:";
file<<i->data.Note;
}
file<<"\n";
}
bool PhoneBook::SearchName(const string& name) const
{
BinaryTreeNode<myItem> *p = root;
while (p) // examine p->data
if (name< (p->data).Name) p = p->LeftChild;
else if (name> (p->data).Name) p = p->RightChild;
else {// found element
//item= p->data;
return true;}
return false;
}
bool PhoneBook::SearchNumber(const string& number, myItem& item) const
{
//关键字是按字符排列的
BinaryTreeNode<myItem> *p = root;
LinkedStack<BinaryTreeNode<myItem>*> S;
while(p!=NULL||!S.IsEmpty()) //用非递归的中序遍历找寻p节点 {
if(p!=NULL)
{
//pp=p;
S.Add(p);//如果p不为空，则将p压入栈中。在遍历p的左孩子
p=p->LeftChild;
}
else//如果p为空则在栈中取出T，并遍历其右孩子
{
S.Delete(p);
if(p->data.Telphonenumber==number||p->data.Officenumber==number||p->data.Ho
- 23 -
中国地质大学 数据结构实习报告
menumber==number)//如果找到了，则return ；
{
item=p->data;
return true;
}
p=p->RightChild;
}
}
return false;
}
PhoneBook& PhoneBook::Insert(const myItem &item)
{
// Insert e if not duplicate.
BinaryTreeNode<myItem> *p = root, // search pointer
*pp = 0; // parent of p
// find place to insert
while (p) {// examine p->data
pp = p;
// move p to a child
if (item.Name <= (p->data).Name) p = p->LeftChild;//允许重复插入 else if (item .Name> (p->data).Name) p = p->RightChild; else throw BadInput(); // duplicate
}
// get a node for e and attach to pp
BinaryTreeNode<myItem> *r = new BinaryTreeNode<myItem> (item); if (root) {// tree not empty
if (item.Name < (pp->data).Name) pp->LeftChild = r;
else pp->RightChild = r;}
else // insertion into empty tree
root = r;
return *this;
}
PhoneBook & PhoneBook::Delete(const std::string &name, myItem &item) {
// Delete element with key k and put it in e.
// set p to point to node with key k
BinaryTreeNode<myItem> *p = root, // search pointer
*pp = 0; // parent of p
陶剑浩 - 24 -
中国地质大学 数据结构实习报告
while (p && (p->data).Name != name){// move to a child of p pp = p;
if (name < (p->data).Name) p = p->LeftChild;
else p = p->RightChild;
}
if (!p) throw BadInput(); // no element with key k
//e = p->data; // save element to delete
item =p->data; // save element to delete
// restructure tree
// handle case when p has two children
if (p->LeftChild && p->RightChild) {// two children // convert to zero or one child case
// find largest element in left subtree of p
BinaryTreeNode<myItem> *s = p->LeftChild,
*ps = p; // parent of s
while (s->RightChild) {// move to larger element ps = s;
s = s->RightChild;}
// move largest from s to p
// p->data = s->data;
// p = s;
p = s;
pp = ps;}
// p has at most one child
// save child pointer in c
BinaryTreeNode<myItem> *c;
if (p->LeftChild) c = p->LeftChild;
else c = p->RightChild;
// delete p
if (p == root) root = c;
else {// is p left or right child of pp?
if (p == pp->LeftChild)
pp->LeftChild = c;
else pp->RightChild = c;}
delete p;
return *this;
}
陶剑浩 - 25 -
中国地质大学 数据结构实习报告
void PhoneBook::SearchGroup(BinaryTreeNode<myItem> * i)
{
string p1=i->data.Group;
string p2(st.GetBuffer());
if(p1==p2)
{
CString temp;
temp.Format("%s", i->data.Name.c_str());
names+=temp;
names+=";";
}
}
void PhoneBook::FindGroup()
{
names.Empty();
PreOrder(SearchGroup,root);
}
//MFC的窗体内部代码
//======================从内存卡复制至手机=================== void CKesheerDlg::OnBnClickedButton1()
{
// TODO: 在此添加控件通知处理程序代码
this->UpdateData(1);
CStdioFile InFile;
CString Text=_T("");
CString p=_T("");
CString t=_T("");
if(InFile.Open("text.txt",CFile::modeReadWrite|CFile::typeText)) {
InFile.ReadString(Text);
int num=atoi(Text);
myItem i;
陶剑浩 - 26 -
中国地质大学 数据结构实习报告
while(num--)
{
InFile.ReadString(Text);
int length=Text.GetLength();
if(Text=="")
break;
int n1=0,n2=0,n3=0;//存放一个字段的开头索引和结尾索引 //============找姓名的内容==========
n2=n1;
char a=Text.GetAt(++n2);
while(a-32&&n2<=length)
{
a=Text.GetAt(n2++);
}
p=Text.Mid(n1-1,n2-n1-1);
int m=p.Compare("姓名");
if(m==0&&n3<=length)
{
n3=n2;
a=Text.GetAt(++n3);
while(a-32&&n2<=length)
{
a=Text.GetAt(n3++);
}
//m_name=Text.Mid(n2,n3-n2-1);
p=Text.Mid(n2,n3-n2-1);
}
else//如果没有这一段，则跳过
{
n2=n3=n1;
//m_name="";
p="";
}
i.Name=p.GetBuffer();
//=================找手机号码===========
n1=n2=n3;
陶剑浩 - 27 -
中国地质大学 数据结构实习报告
a=Text.GetAt(++n2);
while(a-32&&n2<=length)
{
a=Text.GetAt(n2++);
}
p=Text.Mid(n1,n2-n1-1);
if(p.Compare("手机号码")==0&&n2<=length) { n3=n2;
a=Text.GetAt(++n3);
while(a-32&&n3<=length)
{
a=Text.GetAt(n3++);
}
p=Text.Mid(n2,n3-n2-1);
}
else//如果没有这一段，则跳过
{
n2=n3=n1;
p="";
}
i.Telphonenumber=p.GetBuffer();
//=================找住宅号码的内容=========== n1=n2=n3;
a=Text.GetAt(++n2);
while(a-32&&n2<=length)
{
a=Text.GetAt(n2++);
}
p=Text.Mid(n1,n2-n1-1);
if(p.Compare("住宅号码")==0&&n2<=length) {
陶剑浩 - 28 -
中国地质大学 数据结构实习报告 n3=n2;
a=Text.GetAt(++n3);
while(a-32&&n3<=length)
{
a=Text.GetAt(n3++);
}
p=Text.Mid(n2,n3-n2-1);
}
else//如果没有这一段，则跳过
{
n2=n3=n1;
p="";
}
i.Homenumber=p.GetBuffer();
//=============找办公号码的内容=========== n1=n2=n3;
a=Text.GetAt(++n2);
while(a-32&&n2<=length)
{
a=Text.GetAt(n2++);
}
p=Text.Mid(n1,n2-n1-1);
if(p.Compare("办公号码")==0&&n2<=length) {
n3=n2;
a=Text.GetAt(++n3);
while(a-32&&n3<=length)
{
a=Text.GetAt(n3++);
}
p=Text.Mid(n2,n3-n2-1);
}
else//如果没有这一段，则跳过
{
n2=n3=n1;
p="";
}
陶剑浩 - 29 -
中国地质大学 数据结构实习报告
i.Officenumber=p.GetBuffer();
//================找电子邮件的内容=============== n1=n2=n3;
a=Text.GetAt(++n2);
while(a-32&&n2<=length)
{
a=Text.GetAt(n2++);
}
p=Text.Mid(n1,n2-n1-1);
if(p.Compare("电子邮件")==0&&n2<=length)
{
n3=n2;
a=Text.GetAt(++n3);
while(a-32&&n3<=length)
{
a=Text.GetAt(n3++);
}
p=Text.Mid(n2,n3-n2-1);
}
else
{
n2=n3=n1;
p="";
}
i.Email=p.GetBuffer();
//==============找所属群组的内容=============== n1=n2=n3;
a=Text.GetAt(++n2);
while(a-32&&n2<=length)
{
a=Text.GetAt(n2++);
}
p=Text.Mid(n1,n2-n1-1);
if(p.Compare("所属群组")==0&&n2<=length)
陶剑浩 - 30 -
中国地质大学 数据结构实习报告 {
n3=n2;
a=Text.GetAt(++n3);
while(a-32&&n3<=length)
{
a=Text.GetAt(n3++);
}
p=Text.Mid(n2,n3-n2-1); }
else//如果没有这一段，则跳过
{
n2=n3=n1;
p="";
}
i.Group=p.GetBuffer();
//==============找备忘的内容=============== n1=n2=n3;
a=Text.GetAt(++n2);
while(a-32&&n2<=length)
{
a=Text.GetAt(n2++);
}
p=Text.Mid(n1,n2-n1-1);
if(p.Compare("备忘")==0&&n2<=length) {
n3=n2;
a=Text.GetAt(++n3);
while(a-32&&n3<=length)
{
a=Text.GetAt(n3++);
}
p=Text.Mid(n2,n3-n2-1);
}
else//如果没有这一段，则跳过
陶剑浩 - 31 -
中国地质大学 数据结构实习报告 陶剑浩
{ n2=n3=n1; p=""; } i.Note=p.GetBuffer(); if(!PB.SearchName(i.Name))//电话簿里不允许重复存取，如果允许则屏蔽这
{
PB.Insert(i);//将联系人信息添加至PB树中
p.Format("%s",i.Name.c_str());
m_ListBox1.AddString(p);//
if(m_name)
{
p.Format("%s",i.Group.c_str());
if(i.Group=="")
continue;
m_ListBox2.AddString(p);
//删除m_ListBox2里面重复的字符串。
int num=m_ListBox2.GetCount();
int iBrowline = 0;
while(1)
{
// 获得List表的总行数
int ilines = m_ListBox2.GetCount();
// 判断是否最后一行
if(iBrowline == ilines)
{
break;
}
// 获得iBrowline行的值
CString strBuffer = "";
m_ListBox2.GetText(iBrowline, strBuffer);
for(int i = ilines-1 ; i >iBrowline; i--)
{
- 32 - 句话
中国地质大学 数据结构实习报告
//获得第i行的值
CString strTemp = "";
m_ListBox2.GetText(i, strTemp);
//是否与第iBrowline行的值相等
if(strBuffer == strTemp)
{
m_ListBox2.DeleteString(i);
}
}
// 换下一行
iBrowline++;
}
}
m_ListBox1.SetCurSel(0);//自动将listBox指向其第一个item m_ListBox2.SetCurSel(0);//自动将listBox指向其第一个item this->UpdateData(0);
}
}
}
}
//=============查找联系人===================
void CKesheerDlg::OnBnClickedButton2()
{
// TODO: 在此添加控件通知处理程序代码
this->UpdateData(1);
if (m_ListBox1.GetCount()==0)
{
return;
}
int nIndex = m_ListBox1.GetCurSel();
m_ListBox1.GetText(nIndex ,st);
if(nIndex<0)
{
this->UpdateData(0);
return ;
陶剑浩 - 33 -
中国地质大学 数据结构实习报告
}
m_name.Empty();
m_telphonenumber.Empty();
m_homenumber.Empty();
m_officenumber.Empty();
m_group.Empty();
m_note.Empty();
m_email.Empty();
myItem item;
PB.SearchName(st.GetBuffer(),item);
st.Format("%s",(item.Name).c_str());
m_name+=st;
st.Format("%s",item.Telphonenumber.c_str());
m_telphonenumber+=st;
st.Format("%s",item.Homenumber.c_str());
m_homenumber+=st;
st.Format("%s",item.Officenumber.c_str()); m_officenumber+=st;
st.Format("%s",item.Email.c_str());
m_email+=st;
st.Format("%s",item.Group.c_str());
m_group+=st;
st.Format("%s",item.Note.c_str());
m_note+=st;
m_ListBox1.SetCurSel(0);//自动将listBox指向其第一个item m_ListBox2.SetCurSel(0);//自动将listBox指向其第一个item this->UpdateData(0);
}
//===================新建联系人===============
void CKesheerDlg::OnBnClickedButton3()
{
// TODO: 在此添加控件通知处理程序代码
this->UpdateData(1);
myItem a;
a.Name=m_name.GetBuffer();
a.Telphonenumber=m_telphonenumber.GetBuffer();
a.Officenumber=m_officenumber.GetBuffer();
a.Email=m_email.GetBuffer();
a.Note=m_note.GetBuffer();
陶剑浩 - 34 -
中国地质大学 数据结构实习报告 陶剑浩 a.Group=m_group.GetBuffer();
a.Homenumber=m_homenumber.GetBuffer();
if
(m_name==""&&m_telphonenumber==""&&m_officenumber==""&&m_email==""&&m_note==""&&m_group==""&&m_homenumber=="")
{
return;
}
if
(m_name==""&&m_telphonenumber!=""||m_officenumber!=""||m_email!=""||m_note!=""||m_group!=""||m_homenumber!="")
{
m_name=="未知联系人";
a.Name=m_name.GetBuffer();
}
PB.Insert(a);//将联系人添加至PB树中
this->UpdateData(0);
AfxMessageBox("完成！");
m_ListBox1.AddString(m_name); m_ListBox2.AddString(m_group);
//删除m_ListBox2里面重复的字符串。
int num=m_ListBox2.GetCount();
int iBrowline = 0;
while(1)
{
// 获得List表的总行数
int ilines = m_ListBox2.GetCount();
// 判断是否最后一行
if(iBrowline == ilines)
{
break;
}
// 获得iBrowline行的值
CString strBuffer = "";
m_ListBox2.GetText(iBrowline, strBuffer);
for(int i = ilines-1 ; i >iBrowline; i--)
{
//获得第i行的值
- 35 -
中国地质大学 数据结构实习报告
CString strTemp = "";
m_ListBox2.GetText(i, strTemp);
//是否与第iBrowline行的值相等
if(strBuffer == strTemp)
{
m_ListBox2.DeleteString(i);
}
}
// 换下一行
iBrowline++;
}
m_ListBox1.SetCurSel(0);//自动将listBox指向其第一个item m_ListBox2.SetCurSel(0);//自动将listBox指向其第一个item this->UpdateData(0);
}
//=====================删除联系人====================
void Czhh2010explab2newnewnewNEWMFCDlg::OnBnClickedButton4() {
// TODO: 在此添加控件通知处理程序代码
this->UpdateData(1);
if (m_ListBox1.GetCount()==0)
{
return;
}
CString st;
int nIndex = m_ListBox1.GetCurSel();
m_ListBox1.GetText( nIndex, st);//strCBText2用来存放终点的字符串 myItem i;
PB.SearchName(st.GetBuffer(),i);
PB.Delete(st.GetBuffer(),i);
int n = m_ListBox1.FindStringExact(0,st.GetBuffer());
m_ListBox1.DeleteString(n);
m_name.Empty();
m_telphonenumber.Empty();
m_homenumber.Empty();
m_officenumber.Empty();
陶剑浩 - 36 -
中国地质大学 数据结构实习报告
m_group.Empty();
m_note.Empty();
m_email.Empty();
m_ListBox1.SetCurSel(0);//自动将listBox指向其第一个item m_ListBox2.SetCurSel(0);//自动将listBox指向其第一个item this->UpdateData(0);
AfxMessageBox("删除完毕！");
}
//=======================查找电话号码==================== void CKesheerDlg::OnBnClickedButton5()
{
// TODO: 在此添加控件通知处理程序代码
this->UpdateData(1);
m_name.Empty(); m_telphonenumber.Empty();
m_homenumber.Empty();
m_officenumber.Empty();
m_group.Empty();
m_note.Empty();
m_email.Empty();
CString p;
myItem i;
PB.SearchNumber(m_number.GetBuffer(),i);
p.Format("%s",i.Name.c_str());
m_name=p;
p.Format("%s",i.Telphonenumber.c_str());
m_telphonenumber=p;
p.Format("%s",i.Homenumber.c_str());
m_homenumber=p;
p.Format("%s",i.Officenumber.c_str());
m_officenumber=p;
p.Format("%s",i.Email.c_str());
m_email=p;
p.Format("%s",i.Group.c_str());
m_group=p;
陶剑浩 - 37 -
中国地质大学 数据结构实习报告
p.Format("%s",i.Note.c_str());
m_note=p;
m_ListBox1.SetCurSel(0);//自动将listBox指向其第一个item m_ListBox2.SetCurSel(0);
this->UpdateData(0);
}
//=====================将电话簿复制至内存卡中=================void CKesheerDlg::OnBnClickedButton6()
{
// TODO: 在此添加控件通知处理程序代码
PB.PreWrite();
AfxMessageBox("复制完成！");
}
//====================组群查找======================== void CKesheerDlg::OnBnClickedButton7()
{
// TODO: 在此添加控件通知处理程序代码
this->UpdateData(1);
m_ListBox3.ResetContent( );
if (m_ListBox2.GetCount()==0)
{
return;
}
int nIndex = m_ListBox2.GetCurSel();
m_ListBox2.GetText(nIndex ,st);
if(nIndex<0)
{
this->UpdateData(0);
return ;
}
PB.FindGroup();
int n1=0;
陶剑浩 - 38 -
中国地质大学 数据结构实习报告 陶剑浩
} int n2=0; int length=names.GetLength(); while(n1<length) { n2=names.Find(";",n1); CString p=names.Mid(n1,n2-n1); m_ListBox3.AddString(p); n1=n2+1; } this->UpdateData(0);
三、管道铺设施工的最佳方案选择
（选做，加分题）
1．需求规格说明
需要在某个城市的 n 个居民区之间铺设煤气管道，则在这 n 个居民区之间只要铺设 n-1条管道即可。假设任意两个居民区之间都可以架设管道，但由于地理环境的不同，所需
经费 不同。选择最有的施工方案能使总投资尽可能少，这个问题即为求网的“最小生成树”。
2．总体分析与设计
（1）设计思想：
? 利用克鲁斯卡尔算法求出网的最小生成树；
? 实现抽象数据类型。以此表示构造生成树过程中的连通分量；
? 以顶点对形式输出生成树中各条边以及他们的权值。
（2）设计表示：
1. 无向带权图的抽象数据类型定义为：
ADT Graph {数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。
数据关系R：
R??VR? VR???v,w?|v,w?V,?v,w?表示v和w之间存在路径?
基本操作：
Graph()：对数据成员进行初始化。
- 39 -
中国地质大学 数据结构实习报告 陶剑浩 Status CreatGraph()：根据用户输入的城市个数、可能的通信链路数创建城市之间的通信网。 Status KruskalTree()：输出最低代价的通信链路，即网络的最小生成树。
2. MFSet抽象数据类型的定义如下：
ADT MFSet{
数据对象：若设S是MFSet型的集合，则它由n?n?0?个子集Si?i?1,2,
个子集的成员都是子界[-maxnumber..maxnumber]内的整数；
数据关系：S1
基本操作：
MFSet()：对数据成员进行初始化。
Status Initial(int n)：初始化操作。构造一个由n个子集（每个子集只含单个成员xi）构成的集合S。
Status Find_MFSet(int x)：查找函数。确定S中x所属子集Si。
Status Merge_MFSet(int i,int j,int wt)：归并操作。将Si和Sj中的一个并入另一个中。 }ADT MFSet
（3）详细设计表示：
主程序模块：
void main(){
初始化；
while (“命令” != “退出”)
{
接受命令；
处理命令；
}
无向带权图表示及操作模块——对图进行各种操作的函数；
MFSet模块——表示构造生成树过程中的连通分量。 ,n?构成，每S2Sn?S????Si?S?i?1,2,,n?
- 40 -
中国地质大学 数据结构实习报告 陶剑浩
图 各模块之间的调用关系
3．编码
1. 本程序采用类实现，使得各种操作方便快捷。其中，实现的类有图、带权的边、MFSet和树的节点PTNode等。图类被声明为边类的友元类，这样，图类中的成员函数可以直接对边类的相关数据成员进行各种操作。在实现边类时重载了“<”运算符，使边可以按权重的大小进行比较，方便之后Sort()函数的使用。
2. 本程序使用了STL中的容器Vector和Map来存储带权的边和顶点，这样，省去了数组的定义，一方面省去了大量的代码编写；另一方面又可以方便高效地对这些数组进行各种操作。
3. 在调试KruskalTree()函数时花了一定的时间。一开始程序总是运行至某一步不再运行，陷入死循环，经过仔细的检查才发现条件语句中少写了一句i++，使得程序一旦满足条件进入这里就无法退出循环。
4．程序及算法分析
程序运行结果：
- 41 -
中国地质大学 数据结构实习报告 陶剑浩
- 42 -
中国地质大学 数据结构实习报告 陶剑浩
时间复杂度：基于克鲁斯卡尔算法的最小生成树程序中各种运算和操作的时间复杂度分析如下：克鲁斯卡尔算法的时间复杂度为O?eloge?，其中，Find_MFSet()e为网络的边数；
d为树的深度；函数的时间复杂度为O?d?，其中，Merge_MFSet()函数的时间复杂度为O?1?；
CreatGraph()函数的时间复杂度为Omax?arcnum,vexnum?
ma?xarcnu,mvexnum?取边数和顶点数中的较大值。
??，其中，
5．小结
主要内容为最小生成树的实现，使用到的数据存储结构为图和树。相比前面的二叉树,图的实现更为复杂。通过这次实验，对无向带权图有了更深的理解，也了解了实际问题如何转化为具体程序的实现。此外，本程序中还是用了标准模板库（Standard Template Library, STL）中的vector和map等，这对于程序的快速实现起了很大作用。
6．附录
- 43 -
中国地质大学 数据结构实习报告 //Edge.h 边类的声明 //边类声明
class Edge
{
public:
//构造函数
Edge(int st = 0,int nd = 0,int wt = 0); //< 运算符重载
bool operator < (const Edge &temp)const;
public:
//边的起点
int start;
//边的终点
int end;
//边的权重
int weight;
};
//MFSet.h MFSet类的声明 //PTNode类声明
class PTNode
{
public:
PTNode();
friend class MFSet;
private:
int order;
int parent;
};
//MFSet类声明
class MFSet
{
public:
//构造函数
MFSet();
//创建集合
void Initial(int n);
//确定集合中x所属的子集
int Find_MFSet(int x);
//合并两个集合
bool Merge_MFSet(int i,int j,int wt); 陶剑浩 - 44 -
中国地质大学 数据结构实习报告
//记录总路径
int Total_Cost;
private:
PTNode Nodes[max_vexnum];
int num;
};
//Graph.h 图类的声明 //图类声明
class Graph
{
public:
//构造函数
Graph();
//创建空图
bool CreatGraph();
//计算最小生成树
void KruskalTree();
private:
//以边（带权）的数组来存储图
vector<Edge> AdjMatrix;
//图的顶点，每个节点均有唯一的标号
map<int,string> Vertex;
//节点数
int vexnum;
//边数
int arcnum;
};
//Edge.cpp 边类的成员函数定义，包括运算符“<”重载//构造函数
Edge::Edge(int st, int nd, int wt)
{
start = st;
end = nd;
weight = wt;
}
//操作符重载
bool Edge::operator < (const Edge &temp)const
{
return weight < temp.weight;
}
陶剑浩 - 45 -
中国地质大学 数据结构实习报告
//MFSet.cpp 对MFSet的各种操作函数 //PTNode构造函数定义
PTNode::PTNode()
{
order = 0;
parent = 0;
}
//MFSet类定义
//构造函数
MFSet::MFSet()
{
num = 0;
Total_Cost = 0;
}
//创建集合
void MFSet::Initial(int n)
{
num = n;
for(int i = 0;i < n;i++)
{
Nodes[i].order = i;
Nodes[i].parent = 0;
}
}
//查找
int MFSet::Find_MFSet(int i)
{
int j;
for (j = i;Nodes[j].parent > 0;j = Nodes[j].parent); return j;
}
//合并
bool MFSet::Merge_MFSet(int i, int j, int wt)
{
i = Find_MFSet(i);
j = Find_MFSet(j);
陶剑浩 - 46 -
中国地质大学 数据结构实习报告 陶剑浩 if (i == j)
return OK;
if (Nodes[i].order > Nodes[j].order)
{
Nodes[j].parent = i;
}
else
{
Nodes[i].parent = j;
}
Total_Cost += wt;
return OK;
}
//Graph.cpp 对图各种操作，Kruskal算法的实现
/*********************Graph()**************************/
//初始化空图
Graph::Graph()
{
AdjMatrix.clear();
//清空所有边
Vertex.clear();
//清楚所有节点
vexnum = 0;
//初始化节点数
arcnum = 0;
//初始化边数
}
/******************CreatGraph()**********************/
//根据用户的输入创建新图
bool Graph::CreatGraph()
{
//清屏
system("cls");
cout<<"\n\t\t----------请输入居民点数及可能的管道铺设数----------\n"; //输入城市个数
cout<<"\n请输入居民点的个数：";
cin>>vexnum;
while (vexnum > max_vexnum)
{
- 47 -
中国地质大学 数据结构实习报告 陶剑浩 cout<<"\n城市数不应超过30！";
cout<<"\n请输入城市的个数：";
cin>>vexnum;
}
//输入可能的线路数
cout<<"\n请输入可能的管道数：";
cin>>arcnum;
while (arcnum > max_arcnum)
{
cout<<"\n线路数不应超过100！";
cout<<"\n请输入可能的线路数：";
cin>>arcnum;
}
string city;
cout<<"\n********************************************************************************\n";
//存储输入的居民点名称
for (int i = 0;i < vexnum;i++)
{
cout<<"请输入居民点名：";
cin>>city;
//将居民点名存于Vertex数组中
Vertex[i] = city;
}
//输出居民点名称及相应编号
cout<<"\n输入的居民点名及编号为：\n";
for (int j = 0;j < vexnum;j++)
{
cout<<"["<<j + 1<<","<<Vertex[j]<<"]";
cout<<" ";
if ((j + 1)%4 == 0)
cout<<endl;
}
//输入居民点之间的费用
cout<<"\n\n请输入居民点的编号及相应的费用（如1 2 12）：\n";
Edge temp_edge;
int city1_no,city2_no;
int cost;
- 48 -
中国地质大学 数据结构实习报告
for (int k = 0;k < arcnum;k++)
{
cin>>city1_no;
cin>>city2_no;
cin>>cost;
//将输入的节点信息及权重信息赋予边
temp_edge.start = city1_no;
temp_edge.end = city2_no;
temp_edge.weight = cost;
//将带权的边存于数组中
AdjMatrix.push_back(temp_edge); }
return OK;
}
/******************KruskalTree()**********************/
//计算最小生成树
void Graph::KruskalTree()
{
//清屏
system("cls");
MFSet NewMFSet;
NewMFSet.Initial(arcnum);
//对带权的边按权重大小进行排序
sort(AdjMatrix.begin(),AdjMatrix.end());
cout<<"\n\t\t---------利用Kruskal算法计算出的最小生成树---------\n"; cout<<"\n各边及相应的权重值为：\n"
<<"\t\t\t起点\t终点\t路径\t总路径\n";
int i = 0;
while(i < arcnum - 1)
{
if (NewMFSet.Find_MFSet(AdjMatrix[i].start - 1) ==
NewMFSet.Find_MFSet(AdjMatrix[i].end - 1))
{
i++;
陶剑浩 - 49 -
中国地质大学 数据结构实习报告 陶剑浩 continue;
}
else
{
NewMFSet.Merge_MFSet(AdjMatrix[i].start - 1,AdjMatrix[i].end - 1,AdjMatrix[i].weight);
cout<<"\t\t\t "<<Vertex[AdjMatrix[i].start - 1]<<"\t
"<<Vertex[AdjMatrix[i].end - 1]<<"\t "
<<AdjMatrix[i].weight<<"\t "<<NewMFSet.Total_Cost<<endl;
}
i++;
}
cout<<"\n您要花的最短路径为："<<NewMFSet.Total_Cost<<endl;
}
//Main.cpp 主函数
#include <iostream>
#include <string>
#include <fstream>
#include <conio.h>
#include "Graph.h"
void Display()
{
system("cls");
//欢迎界面
cout<<"\n\t\t\t\t最小生成树问题\n"
<<"\t\t************************************************\n" <<"\t\t* 1.创建城市通信网络 *\n" <<"\t\t* *\n" <<"\t\t* 2.生成最低代价链路 *\n" <<"\t\t* *\n" <<"\t\t* 3.退出系统 *\n" <<"\t\t************************************************\n"; }
int main()
{
Graph NewGraph;
- 50 -
中国地质大学 数据结构实习报告 陶剑浩
} while (true) { Display(); int Flag; cout<<"\n请输入操作选项："; cin>>Flag; switch(Flag) { case 1: NewGraph.CreatGraph(); cout<<"城市通信网已建成！请返回继续..."; getch(); break; case 2: NewGraph.KruskalTree(); cout<<"按任意键继续..."; getch(); break; case 3: exit(0); default: break; } } return 0;
四、总结
用抽象数据类型以及面向对象的方法组织、存储各种类型的数据是数据结构课程的重点。面向对象方法以及结构化技术都是建立高质量软件的技术，通过《数据结构》课程的实习，可以加深对这些先进软件开发方法的理解和体会。因此，实习的任务是按照软件工程思想，用面向过程和面向对象方法进行数据设计和程序设计的基本思想，在实践中逐步熟练掌握。
通过这几天的学习，也复习巩固了课程的基本数据结构(包括数组、顺序表、多项式、字符串、链表、栈与队列、优先级队列、广义表、树与森林、二叉树、堆、集合、图、搜索结构、索引结构、散列结构等)及其不同的实现。
在实习中最令我们感到吃力的是设计和编写算法。算法设计水平是软件设计的基础。要提高算法的设计水平，首先需要掌握问题要求的基本内容，通过反复体会和练习来实现。通
- 51 -
中国地质大学 数据结构实习报告 陶剑浩 常需要根据具体问题的要求，选择合适的数据结构，设计有效的算法，这是我在实习中获得最深的体会。
【参考资料】
1、 Sartaj Sahni 著，《数据结构、算法与应用》，机械工业出版社
2、 殷人昆 等编著，数据结构(用面向对象方法与 C++语言描述)》，清华大学出版社
3、 严蔚敏，吴伟民 编著，《数据结构题集》，清华大学出版社
4、 严蔚敏，陈文博 编著，《数据结构及应用算法》，清华大学出版社
- 52 -