数据结构课程设计文档格式.docx
《数据结构课程设计文档格式.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计文档格式.docx（46页珍藏版）》请在冰点文库上搜索。
2若p->
data<
data,说明B中无此值，处理表A中的下一个结点。
3若p->
data==q->
data,说明找到了公共元素。
同理，求并运算时，只需对单链表B中的每一个元素x,在单链表A中进行查找，若存在和x不相同的元素，则将该结点插入单链表A中。
求差运算时，只需对单链表B中的每个元素x，在单链表A中查找，若存在与x相同的结点，则将该结点从单链表A中删除。
（四）详细设计
#ifndefLinkList_H
#defineLinkList_H
template<
classDataType>
structNode
{DataTypedata;
Node<
*next;
};
classLinkList
{
public:
LinkList（）;
~LinkList（）;
*first;
};
#endif
#include<
iostream>
usingnamespacestd;
#include"
LinkList.h"
LinkList<
:
LinkList（）
{first=newNode<
;
first->
next=NULL;
}
LinkList（DataTypea[],intn）
*r,*s;
first=newNode<
r=first;
for（inti=0;
i<
n;
i++）
{s=newNode<
s->
data=a[i];
r->
next=s;
r=s;
}
~LinkList（）
*q=NULL;
while（first!
=NULL）
{q=first;
first=first->
next;
deleteq;
}
template<
voidLinkList<
PrintList（）
*p=first->
while（p!
{cout<
<
p->
"
"
p=p->
cout<
endl;
//要查找单链表A和单链表B中相同的元素并保留在单链表A中。
voidjiaoji（Node<
*B）//交运算
*pre,*p,*q;
pre=A;
p=A->
q=B->
=NULL&
&
q!
{
if（p->
data）
{pre->
next=p->
deletep;
p=pre->
elseif（p->
data）q=q->
else{p=p->
q=q->
pre=pre->
}
//对单链表B中的每个元素x，在单链表A中查找，若存在与x相同的结点，则将该结点从单链表A中删除。
voidchaji（Node<
*B）//A-B
*pre,*p,*q;
q=B->
=NULL&
q!
if（p->
{p=p->
pre=pre->
}//始终保证p=pre->
}
//对单链表B中的每一个元素x,在单链表A中进行查找，若存在和x不相同的元素，则将该结点插入单链表A中
voidbingji（Node<
*B）
*s=NULL;
data=q->
data;
next=pre->
//p=pre->
pre->
pre=s;
}
data）//p=pre->
p=p->
pre=pre->
if（p==NULL&
=NULL）{pre->
next=q;
p=q;
if（p==NULL&
}
voidInsertSort（charr[],intn）
for（inti=1;
r[n]=r[i];
//设置哨兵
for（intj=i-1;
r[n]<
r[j]&
j>
=0;
j--）
{r[j+1]=r[j];
r[j+1]=r[n];
#include<
cstring>
cmath>
#include"
LinkList.cpp"
voidmain（）
注意，输入的字符串必须为小写字母，且不出现重复字母！
charr1[100],r2[100];
请输入字符串:
cin.getline（r1,100）;
cin.getline（r2,100）
intk1=strlen（r1）;
intk2=strlen（r2）;
InsertSort（r1,k1+1）;
InsertSort（r2,k2+1）;
LinkList<
char>
L1（r1,k1+1）;
//尾插法LinkList<
L2（r2,k2+1）;
cout<
输出:
建立有序链表:
L1.PrintList（）;
L2.PrintList（）;
1.交集."
2.并集."
3.差集."
请选择:
intchoice;
cin>
>
choice;
if（choice>
0&
choice<
4）
switch（choice）
case1:
交运算:
jiaoji（L1.first,L2.first）;
L1.PrintList（）;
break;
case2:
并运算"
bingji（L1.first,L2.first）;
case3:
差运算"
chaji（L1.first,L2.first）;
2、病人就医管理
【问题描述】病人到医院看病，排队看医生的情况，在病人排队过程中，主要发生两件事：
（1）病人到达诊室，将病历本交给护士，排到等待队列中候诊。
（2）护士从等待队列中取出一位病人的病历，该病人进入诊室就诊。
试为医院编制按上述要求进行管理的模拟程序。
【基本要求】程序采用菜单方式，其选项及功能说明如下：
（1）排队------输入病人的病历号，加入到病人排队队列中
（2）就诊-------病人排队队列中最前面的病人就诊，并将其从队列中删除。
（3）查看排队------从队首到队尾列出所有的排队病人的病历号。
（4）
下班---------退出运行。
patient（）;
//无参构造函数
patient（char*num）;
//带参构造函数
patient（constpatient&
per）;
//拷贝构造函数
~patient（）;
//折构函数
voiddisplay（）;
//显示病人病历
voidinput（）;
//输入病人病历
注意点:
在做第二题病人就医管理时，我采用的数据结构是队列，利用其先进先出的特性，病人取病历号时进队，就诊时出队。
判断对空的条件是front==rear.
string>
classpatient//定义病人这一个类
{//病历号
public:
char*number;
//带参构造函数patient（constpatient&
//拷贝构造函数
//折构函数voiddisplay（）;
//显示病人病历
//输入病人病
patient:
patient（）
{number=NULL;
}
patient（char*num）
if（num）
number=newchar[strlen（num）+1];
//避免浅拷贝,将病历号拷贝
strcpy（number,num）;
per）//拷贝构造函数
if（per.number）
number=newchar[strlen（per.number）+1];
strcpy（number,per.number）;
~patient（）//折构函数
{if（number）delete[]number;
}
voidpatient:
display（）//输出病人病历号
{cout<
病历号:
number<
input（）//输入病人病历号
charnum[10];
输入病历号:
num;
if（number）delete[]number;
number=newchar[strlen（num）+1];
strcpy（number,num）;
constintN=10;
voidOutput（patient*a）;
//出队voidInput（patient*a）;
//入队
intjiuzhen（patient*a）;
intchakanpaidui（patient*a）;
voidend（patient*a）;
intfront=0,rear=1,z=10;
voidInput（patient*a）
a[front].input（）;
front++;
z--;
cout<
还有"
（z）<
名排队等待名额"
intjiuzhen（patient*a）
if（rear<
=front）
请"
a[rear-1].number<
号病人现在就诊。
rear++;
z++;
//有人就诊，增加一排队名额
排队等待名额"
Elsecout<
现在没有病人救诊!
return0;
intchakanpaidui（patient*a）
if（rear==front+1）
现在没有病人排队!
else
正在排队中的病人:
for（inti=rear-1;
front;
a[i].display（）;
intend（）
if（rear==front+1）//队空
可以下班了!
return0;
还有病人，不可以下班!
return1;
intmain（）
patienta[N];
//定义病人数组
//读入选项
病人就医管理"
你好，欢迎登陆病人管理系统!
1.排队--输入病人的病历号，加入到病人的排队队列中。
2.就诊--病人排队队列中最前面的病人就诊，并将其从队列中删除。
3.参看排队--从队首到队尾列出所有的排队病人的病历号。
4.下班?
5.结束调试。
医院排队区仅限10人"
do
cin>
if（choice>
=5）
switch（choice）
{
case1:
Input（a）;
break;
case2:
jiuzhen（a）;
case3:
chakanpaidui（a）;
case4:
end（）;
}
else
cout<
输入错误，请重新输入!
endl<
}while（choice!
=5）;
3、校园导游咨询
【问题描述】设计一个校园导游程序，为来访的客人提供各种信息查询服务。
【基本要求】
（1）设计学校的校园平面图，所含景点不少于10个，以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；
以边表示路径，存放路径长度等相关信息。
（2）为来访客人提供图中任意景点相关信息的查询。
（3）为来访客人提供景点的问路查询，即已知一个景点，查询到某景点之间的一条最短路径及长度。
Grahp（inte[vertexNum][vertexNum],intv[vertexNum]）;
//初始化图的邻接矩阵
intshortest_way（ints,intd）;
//求最短路径
intBFS（ints,intd）;
//广度优先算法
第三题校园导游咨询用到了图结构，这一题蛮有难度的，这一题我采用了邻接矩阵存储各顶点，在查找最小路径时，我使用了Dijkstra算法，辅助数组dist[n];
元素dist[n]表示当前所找到的从源点v到终点vi的最短路径长度。
辅助数组path[n]:
元素path[i]是一个串，表示当前所找到的从源点v到终点vi的最短路径。
数组s[n]：
存放源点和已生成的终点，初始态只有一个源点v.我采用的基本思路是：
1.初始化数组dist,path和s;
2.While（s中元素个数<
n）
2.1在dist[n]中求最小值，其编号为k;
2.2输出dist[k]和path[k];
2.3修改数组dist和path;
2.4将顶点k添加到数组s中；
constintvertexNum=10;
constintMAX=10000;
//表示大于所有边上权值的数
intdefault_e[vertexNum][vertexNum]={0,100,150,MAX,100,400,MAX,MAX,MAX,MAX,
100,0,MAX,MAX,MAX,MAX,MAX,MAX,MAX,400,
150,MAX,0,100,MAX,MAX,50,MAX,MAX,MAX,
MAX,MAX,100,0,MAX,MAX,MAX,200,100,200,
100,MAX,MAX,MAX,0,250,MAX,MAX,MAX,MAX,
400,MAX,MAX,MAX,250,0,100,300,MAX,MAX,
MAX,MAX,50,MAX,MAX,100,0,MAX,MAX,MAX,
MAX,MAX,MAX,200,MAX,300,MAX,0,150,MAX,
MAX,MAX,MAX,100,MAX,MAX,MAX,150,0,150,
MAX,400,MAX,200,MAX,MAX,MAX,MAX,150,0};
//初始化邻接矩阵10*10
intdefault_v[vertexNum]={0,1,2,3,4,5,6,7,8,9};
/************定义景点结构体**********/
structview_spot_node
charname[vertexNum];
intcodename;
//代号
view_spot_nodeoperator=（view_spot_node&
v）//重载等号运算符,形参是一个view_spot_node结构体类型的引用
codename=v.codename;
vertexNum;
name[i]=v.name[i];
returnv;
/********输入代号及景点名字*********/
view_spot_nodedefault_vsn[vertexNum]={"
景点A"
1,"
景点B"
2,"
景点C"
3,"
景点D"
4,"
景点E"
5,"
景点F"
6,"
景点G"
7,"
景点H"
8,"
景点I"
9,"
景点J"
10};
/*************图结构***********/
classGrahp
Grahp（inte[vertexNum][vertexNum],intv[vertexNum]=default_v）;
//定义边和结点（首地址）
intshortest_way（ints,intd）;
//求最短路径intstore_v[vertexNum];
//存储结点
intdistance[vertexNum];
//声明距离的数组
private:
intBFS（ints,intd）;
//广度优先算法voidstore（intd）;
intedge[vertexNum][vertexNum];
//存储边intvertex[vertexNum];
//顶点数组
intvisited[vertexNum];
//将为访问的顶点的值设置为0，已访问的顶点的
升级会员 