数据结构课程设计报告.docx
《数据结构课程设计报告.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计报告.docx(59页珍藏版)》请在冰点文库上搜索。
数据结构课程设计报告
2013年1月
控制台
1.停车场管理……………………………………………………3
2.个人电话号码查询系统………………………………………6
3.排序运用………………………………………………………12
4.“火烧连营”问题……………………………………………16
5.管道铺设施工的最佳方案选择………………………………19
MFC
1.停车场管理……………………………………………………27
2.个人电话号码查询系统………………………………………29
3.排序运用………………………………………………………34
总结
自我总结…………………………………………………38
实习题目一停车场管理
【问题描述】
设停车场是一个可停放n辆汽车的狭长通道,且只有一个大门可供汽车进出。
汽车在停车场内按车辆到达时间的先后顺序,依次由北向南排列(大门在最南端,最先到达的第一辆车停放在车场的最北端),若车场内已停满n辆汽车,则后来的汽车只能在门外的便道上等候,一旦有车开走,则排在便道上的第一辆车即可开入;当停车场内某辆车要离开时,在它之后进入的车辆必须先退出车场为它让路,待该辆车开出大门外,其他车辆再按原次序进入车场,每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。
试为停车场编制按上述要求进行管理的模拟程序。
【设计思想】
以栈模拟停车场,以队列模拟车场外的便道,按照从终端读入的输入数据序列进行模拟
管理。
每一组输入数据包括三个数据项:
汽车“到达”或“离去”信息,汽车牌照号以及到达或离去的时刻。
对每一组输入的数据进行操作后的输出信息为:
若是车辆到达,则输出汽车在停车场内或便道上的停车位置;若是车辆离去,则输出汽车在停车场内停留的时间和应交纳的费用(在便道上停留的时间不收费)。
栈以顺序结构实现,队列以链表结构实现。
需另设一个栈,临时停放为给要离去的汽车让路而从停车场推出来的汽车,也用顺序存
储结构实现。
输入数据按到达或离去的时刻有序。
栈中每个元素表示一辆汽车,包含两个数
据项:
汽车的牌照号码和进入停车场的时刻。
【设计表示】
【代码实现】
//主函数的实现
#include"stdafx.h"
#include"iostream.h"
#include"queue.h"
#include"stack.h"
intmain(intargc,char*argv[])
{
cout<<"请输入停车场的容量:
";
intn,num,time;
cin>>n;
chara;
cout<<"请输入停车场车辆的情况:
"<cin>>a>>num>>time;
SeqStacks1;
SeqStacks2;
LinkedQueueq;
s1.Push(a,num,time);
cout<<"车牌为"<"<while(a!
='E')
{
cin>>a>>num>>time;
inttime1=time;
if(a=='A')
{
if(s1.Find(num)==true)
{
cout<<"车牌为"<"<continue;;
}
else
{
if(s1.getSize(){
s1.Push(a,num,time);
cout<<"车牌为"<"<}
else
{
q.EnQueue(a,num,time);
cout<<"车牌为"<"<}
}
}
if(a=='D')
{
if(s1.Find(num)==true)//先找到此车
{
intb=s1.gettime(num);
cout<<"车牌为"<"<for(inti=s1.getnum(num)+1;i{
s1.Pop(a,num,time);//将车辆放在零时栈
s2.Push(a,num,time);
}
s1.Pop(a,num,time);//退出此车
for(i=0;i{
s2.Pop(a,num,time);
s1.Push(a,num,time);
}
if(q.getSize()>0)//如果便道中有车,则将便道的车进入停车场
{
q.DeQueue(a,num,time);
s1.Push(a,num,time1);
}
}
else
{
cout<<"车牌为"<"<}
}
}
return0;
}
【运行结果】
实习题目二个人电话号码查询系统
【问题描述】
人们在日常生活中经常需要查找某个人或某个单位的电话号码,本实验将实现一个简单
的个人电话号码查询系统,根据用户输入的信息(例如姓名等)进行快速查询。
基本要求:
(1)在外存上,用文件保存电话号码信息;
(2)在内存中,设计数据结构存储电话号码信息;
(3)提供查询功能:
根据姓名实现快速查询;
(4)提供其他维护功能:
例如插入、删除、修改等。
【设计思想】
由于需要管理的电话号码信息较多,而且要在程序运行结束后仍然保存电话号码信息,
所以电话号码信息采用文件的形式存放到外存中。
在系统运行时,需要将电话号码信息从文
件调入内存来进行查找等操作,为了接收文件中的内容,要有一个数据结构与之对应,可以
设计如下结构类型的数组来接收数据:
constintmax=10;
structTeleNumber
{
stringname;//姓名
stringphoneNumber;//固定电话号码
stringmobileNumber;//移动电话号码
stringemail;//电子邮箱
}Tele[max];
为了实现对电话号码的快速查询,可以将上述结构数组排序,以便应用折半查找,但是,
在数组中实现插入和删除操作的代价较高。
如果记录需频繁进行插入或删除操作,可以考虑
采用二叉搜索树组织电话号码信息,则查找和维护都能获得较高的时间性能。
更复杂地,需
要考虑该二叉搜索树是否平衡,如何使之达到平衡。
【设计表示】
【代码实现】
//结构体的实现
#include
#include"stdlib.h"
#include
usingnamespacestd;
structTeleNumber;
istream&operator>>(istream&is,TeleNumber&c);//使编译器识别重载的运算符
ostream&operator<<(ostream&os,TeleNumber&c);
structTeleNumber
{
stringname;
stringphoneNumber;
stringmobileNumber;
stringemail;
friendistream&operator>>(istream&is,TeleNumber&c);//重载>>
friendostream&operator<<(ostream&os,TeleNumber&c);//重载<<
}Tele[10];
istream&operator>>(istream&is,TeleNumber&c)
{
is>>c.name>>c.phoneNumber>>c.mobileNumber>>c.email;//输入结构体
returnis;
}
ostream&operator<<(ostream&os,TeleNumber&c)//输出结构体
{
os<returnos;
}
//二叉搜索树的实现
#include"stdlib.h"
structBSTNode//TeleNumber(E)
{
TeleNumberdata;
BSTNode*left,*right;
BSTNode():
left(NULL),right(NULL){}
BSTNode(constTeleNumberd,BSTNode*L=NULL,BSTNode*R=NULL)
:
data(d),left(L),right(R){}
~BSTNode(){}
voidsetData(TeleNumberd){data=d;}
TeleNumbergetData(){returndata;}
};
classBST
{
public:
BST():
root(NULL){}
~BST(){}
boolInsert(constTeleNumber&e1)
{
returnInsert(e1,root);
}
boolRemove(conststringx)
{
returnRemove(x,root);
}
boolModify(conststringx,BSTNode*&ptr);
BSTNode*getroot(){returnroot;}
BSTNode*Search(conststringx,BSTNode*ptr);
private:
BSTNode*root;
boolInsert(constTeleNumber&e1,BSTNode*&ptr);
boolRemove(conststringx,BSTNode*&ptr);
};
//插入到二叉搜索树
boolBST:
:
Insert(constTeleNumber&e1,BSTNode*&ptr)
{
inti=0;
if(ptr==NULL)
{
ptr=newBSTNode(e1);
if(ptr==NULL)
{
cerr<<"Outofspace"<(1);
returntrue;
}
}
elseif(int(e1.name.substr(i,i+1)[0])data.name.substr(i,i+1)[0]))
{
Insert(e1,ptr->left);
}
elseif(int(e1.name.substr(i,i+1)[0])>int(ptr->data.name.substr(i,i+1)[0]))
{
Insert(e1,ptr->right);
}
else
returnfalse;
};
//删除二叉搜索树中的某结点
boolBST:
:
Remove(conststringx,BSTNode*&ptr)
{
BSTNode*temp;
if(ptr!
=NULL)
{
if(int(x.substr(0,1)[0])data.name.substr(0,1)[0]))
{
Remove(x,ptr->left);
}
elseif(int(x.substr(0,1)[0])>int(ptr->data.name.substr(0,1)[0]))
{
Remove(x,ptr->right);
}
elseif(ptr->left!
=NULL&&ptr->right!
=NULL)
{
temp=ptr->right;
while(temp->left!
=NULL)
{
temp=temp->left;
}
ptr->data=temp->data;
Remove(ptr->data.name,ptr->right);
}
else
{
temp=ptr;
if(ptr->left==NULL)
{
ptr=ptr->right;
}
elseptr=ptr->left;
deletetemp;
returntrue;
}
}
returnfalse;
};
//在二叉搜索树的某个值
BSTNode*BST:
:
Search(conststringx,BSTNode*ptr)
{
if(ptr==NULL)
{
returnNULL;
}
elseif(int(x.substr(0,1)[0])data.name.substr(0,1)[0]))
{
returnSearch(x,ptr->left);
}
elseif(int(x.substr(0,1)[0])>int(ptr->data.name.substr(0,1)[0]))
{
returnSearch(x,ptr->right);
}
else
returnptr;
};
boolBST:
:
Modify(conststringx,BSTNode*&ptr)
{
ptr=Search(x,root);
cin>>ptr->data;
returntrue;
}
//主函数的实现
#include
#include
#include
#include
usingnamespacestd;
#include"tele.h"
#include"BST.H"
intmain(intargc,char*argv[])
{
inta;
stringstr;
BSTbst;
BSTNode*b;
cout<<"************************欢迎使用个人电话号码查询系统**********************"<cout<<"************************||1.查找联系人||**********************"<cout<<"************************||2.添加联系人||**********************"<cout<<"************************||3.删除联系人||**********************"<cout<<"************************||4.修改联系人||**********************"<cout<<"************************||5.退出本系统||**********************"<inti=0;
ifstreamfin("C.txt");
while(!
fin.eof())
{
fin>>Tele[i];
bst.Insert(Tele[i]);
i++;
}
fin.close();
while(a!
=5)
{
cout<<"请输入您的选择:
";cin>>a;
switch(a)
{
case1:
{
cout<<"请输入你要查找的名字:
";
cin>>str;
if(bst.Search(str,bst.getroot())==NULL)
cout<<"没有此联系人!
"<else
cout<data<case2:
{
cout<<"请输入要添加的联系人:
";
cin>>Tele[i];
bst.Insert(Tele[i]);
}break;
case3:
{
cout<<"请输入要删除的联系人:
";
cin>>str;
bst.Remove(str);
}break;
case4:
{
cout<<"请输入要修改的联系人:
";
cin>>str;
bst.Modify(str,b);
}break;
case5:
{
cout<<"谢谢使用个人电话号码查询系统!
"<}break;
}
}
return0;
}
【运行结果】
实习题目三排序应用
【问题描述】
假定文本文件A1.txt中是我校所有参加南望山庄二期挑房职工的信息,请编写程序,读
出文件中的内容,再按挑房的先后次序排队后将排序号和姓名以文本方式存放到文件A2.txt
中。
排队原则:
先按职称排,同职称按分房工龄排,同工龄按年龄排。
职称编号:
校级干部0
教授、正处级1
副教授、副处级2
讲师、科级3
其他4
【设计思想】
先将文本文档的内容读到数组中,重载输入输出号,使得文本文档中的每一行为一个元素,然后按照要用冒泡排序法。
排序后,并将有序的结果输入到文本文档中
【设计表示】
【代码实现】
#include
#include
usingnamespacestd;
structstaff;
istream&operator>>(istream&is,staff&c);
ostream&operator<<(ostream&os,staff&c);
constintmax=1000;
structstaff//结构体包括职工信息
{
stringname;//姓名
stringtitleID;//职称编号
stringworkingage;//工龄
stringage;//年龄
friendistream&operator>>(istream&is,staff&c);//重载<<,>>
friendostream&operator<<(ostream&is,staff&c);
}sta[max];
istream&operator>>(istream&is,staff&c)
{
is>>c.name>>c.titleID>>c.workingage>>c.age;
returnis;
}
ostream&operator<<(ostream&os,staff&c)
{
os<:
left)<:
left)<:
left)<:
left)<returnos;
}
//冒泡排序法进行排序
voidBubbleSort(staffv[],intn)
{
for(inti=2;i{
for(intj=n-1;j>=i;j--)
{
if(atof(v[j-1].titleID.c_str())>atoi(v[j].titleID.c_str()))
{
stafftemp=v[j-1];v[j-1]=v[j];v[j]=temp;
}
if(atof(v[j-1].titleID.c_str())==atoi(v[j].titleID.c_str()))
{
if(atof(v[j-1].workingage.c_str())>atoi(v[j].workingage.c_str()))
{
stafftemp=v[j-1];v[j-1]=v[j];v[j]=temp;
}
if(atof(v[j-1].workingage.c_str())==atoi(v[j].workingage.c_str()))
{
if(atof(v[j-1].age.c_str())>atoi(v[j].age.c_str()))
{
stafftemp=v[j-1];v[j-1]=v[j];v[j]=temp;
}
}
}
}
}
}
#include"stdafx.h"
#include"staff.h"
#include"sort.h"
#include
#include
#include
usingnamespacestd;
intmain(intargc,char*argv[])
{
inti=0;
ifstreamfin("a1.txt");//将a1.txt的内容读到结构体数组中
while(!
fin.eof())
{
fin>>sta[i];
i++;
}
fin.close();
BubbleSort(sta,i)