《数据结构》实验报告
实验序号：6 实验项目名称：树和二叉树的操作学号姓名专业、班
实验地点指导教师实验时间
一、实验目的及要求
1、进一步掌握指针变量、动态变量的含义。
2、掌握二叉树的结构特征，以及各种存储结构的特点及适用范围。
3、掌握用指针类型描述、访问和处理二叉树的运算。
4、掌握用二叉树前序、中序、后序、层次遍历的方法。
二、实验设备（环境）及要求
微型计算机；
windows 操作系统；
Microsoft Visual Studio 6.0集成开发环境。
三、实验内容与步骤
1.根据下图中的树回答问题①-⑨。
①列出所有的叶子结点；K L M
②列出G结点的双亲； B
③列出E结点的孩子；K L
④列出I结点所有的堂兄弟； E F G H
⑤列出B结点所有的子孙； E F G M K L
⑥结点E的度是多少；2
⑦树的度是多少；3
⑧结点E的层次是多少；2
树的深度是多少；4
2．根据P129的方法，将a*b-((c+d*e/f)+g)转化为表达式二叉树（绘图），并写出表达式二叉树的前序、中序和后序遍历顺序。
前序-*ab++\*defdg 中序-*ab++\*defdg
后序ab*de*+\d+g+-
3.根据左孩子-右兄弟的规则画出下列二叉树相应的森林：
A C F I
B E M
D H K
G J
4. 链式表表示和实现二叉排序树如下：
#include
#include
typedef int TElemType;
typedef struct BiTNode
root=NULL; /*千万别忘了赋初值给root!*/
printf("请输入数据,-9999表示输入结束\n");
do
{
printf("please input data %d:",i);
i++;
scanf("%d",&x); /*从键盘采集数据，以-9999表示输入结束*/
if(x==-9999){
printf("\nNow output data value:\n");
}
else
insert_data(x); /*调用插入数据元素的函数*/
}while(x!=-9999);
}
改写以上程序，实现功能如下(任选三题)：
1). 编写函数实现前序、中序和后序遍历。
2). 编写函数实现计算叶节点个数。
3). 编写函数实现层序遍历。
4). 编写函数实现查询二叉树中的某个结点(分查到和查不到两种情况)。
5)．编写函数实现求二叉树的深度
6). 编写函数实现中序非递归遍历(利用栈)
5. 如果通讯字符a，b，c，d出现频度分别为7，5，2，4
①某同学设计了如下程序，请根据程序画出对应的二叉树，计算所画出的二叉树的带权路径长度；
if(input==’c’)
printf("%c",’c’);
else if(input==’d’)
printf("%c",’d’);
else if(input==’a’)
printf("%c",’a’);
else
printf("%c",’b’);
2*1+4*2+7*3+5*3=46
②请画出对应的赫夫曼（哈弗曼）树；
③计算赫夫曼树的带权路径长度；2*1+2*4+3*7+3*5=46
④根据赫夫曼树，用if-else语句修改①中的程序，写出最佳判定算法。
if(input=='a')
{
printf("%c",'a');
}
Else if(input=='b')
{
printf("%c",'b');
}else if(input=='c')
printf("%c",'c');
else
printf("%c",'d');
四、实验结果与数据处理
详细记录程序在调试过程中出现的问题及解决方法。记录程序执行的结果（贴图）。
五、分析与讨论
对上机实践结果进行分析，上机的心得体会。
六、教师评语
成绩
签名：
附源程序清单：
4(1)
前序排列
int bianli(Bitree root)
{
if(root!=NULL)
{
printf("%d",root->data);
bianli(root->lchild);
bianli(root->rchild);
if(root->lchild==NULL&&root->rchild==NULL) t++;
}
return t;
}
中序排列
int bianli(Bitree root)
{
if(root!=NULL)
{
bianli(root->lchild);
printf("%d",root->data);
bianli(root->rchild);
if(root->lchild==NULL&&root->rchild==NULL) t++;
}
return t;
}
后序排列
int bianli(Bitree root)
{
if(root!=NULL)
{
bianli(root->lchild);
bianli(root->rchild);
printf("%d",root->data);
if(root->lchild==NULL&&root->rchild==NULL) t++;
}
return t;
}
(2)
#include
#include
typedef int TElemType;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiNode, *Bitree;
Bitree root;//定义根结点
int t=0;
int visit(int e)
{
printf("%d",e);
return 0;
}
int bianli(Bitree root)
{
if(root!=NULL)
{
bianli(root->lchild);5
bianli(root->rchild);
printf("%d",root->data);
if(root->lchild==NULL&&root->rchild==NULL) t++;
}
return t;
}
void insert_data(int x) /*生成二叉排序树*/
{
Bitree p,q,s;
s=(Bitree)malloc(sizeof(BiNode)); //创建结点
s->data=x; //结点赋值
s->lchild=NULL;
s->rchild=NULL;
if(!root)
{
root=s;
}
else
{
p=root;
while(p) /*如何接入二叉排序树的适当位置*/
{
q=p;
if(p->data==x) //相同结点不能重复插入
{
printf("data already exist! \n");
return;
}
else if(x
p=p->lchild;
else
p=p->rchild;
}
if(x
q->lchild=s;
else
q->rchild=s;
}
}
void main() /*先生成二叉排序树*/
{
int i=1,x,m; //i记录结点个数，x存放结点值
root=NULL; /*千万别忘了赋初值给root!*/
printf("请输入数据,-9999表示输入结束\n");
do
{
printf("please input data %d:",i);
i++;
scanf("%d",&x); /*从键盘采集数据，以-9999表示输入结束*/
if(x==-9999){
printf("\nNow output data value:\n");
m=bianli(root);
printf("\n叶子节点数%d\n",m);
}
else
insert_data(x); /*调用插入数据元素的函数*/ }while(x!=-9999);
}
(3)
(4)
#include
#include
typedef int TElemType;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiNode, *Bitree;
Bitree root;
int t=0,l=0;
int visit(int e)
{
printf("%d",e);
return 0;
}
int bianli(Bitree root)
{
if(root!=NULL)
{
bianli(root->lchild);
bianli(root->rchild);
if(root->lchild==NULL&&root->rchild==NULL)
t++;
}
return t;
}
int jiancha(int &x,Bitree root)
{
if(root!=NULL)
{
bianli(root->lchild);
bianli(root->rchild);
if(root->data==x)
l++;
}
}
void insert_data(int x)
{
Bitree p,q,s;
s=(Bitree)malloc(sizeof(BiNode));
s->data=x;
s->lchild=NULL;
s->rchild=NULL;
if(!root)
{
root=s;
}
else
{
p=root;
while(p)
{
q=p;
if(p->data==x)
{
printf("data already exist! \n");
return;
}
else if(x
p=p->lchild;
else
p=p->rchild;
}
if(x
q->lchild=s;
else
q->rchild=s;
}
}
void main()
{
int i=1,x,m,u;
root=NULL;
printf("??ê?è?êy?Y,-9999±íê?ê?è??áê?\n");
do
{
printf("please input data %d:",i);
scanf("%d",&x);
insert_data(x);
}while(x!=-9999);
printf("ê?è?2é?ò?úμ?");
scanf("%d",&u);
m=jiancha(u,root);
if(m!=0)
{
printf("\ndata exist\n");
}
else
{
printf("\nno found\n");
}
}
(5)
(6)
#include
#include
#include
#include
#include
#define OK 0;
#define ERROR 1;
typedef int Elemtype;
typedef int status;
typedef struct treende{
Elemtype data;
struct treende *lchild,*rchild,*father; }treende,*treeptr;
using namespace std;
treeptr zone;
void insert(int e)
{
treeptr p,q,s;
s=(treeptr)malloc(sizeof(treende));
s->data=e;
s->lchild=NULL;
s->rchild=NULL;
s->father=NULL;
if(!zone)
{
zone=s;
}
else
{
p=zone;
while(p)
{
q=p;
if(e
{
p=p->lchild;
}
else if(e>p->data)
{
p=p->rchild;
}
else
return;
}
if(e
q->lchild=s;
else
q->rchild=s;
}
}
status zhongxubianli(treeptr zone)
{
stack
treeptr p=zone;
while(p!=NULL||!s.empty())//新建二叉树类型的栈形式，储存树的指针
{
while(p!=NULL)
{
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
printf("%d ",p->data);
s.pop();
p=p->rchild;
}
}
return OK;
}
void main()
{
int e,i=0;
zone=NULL;
printf("ê?è?-9999?áê?");
do
{
scanf("%d",&e);
if(e==-9999)
{
printf("\nnaaaaaaaa\n");
}
else
{
insert(e);
}
}while(e!=-9999);
zhongxubianli(zone);
}
实验2 查找算法的实现和应用?实验目的 1. 熟练掌握静态查找表的查找方法； 2. 熟练掌握动态查找表的查找方法; 3. 掌握hash表的技术. ?实验内容 1.用二分查找法对查找表进行查找； 2.建立二叉排序树并对该树进行查找； 3.确定hash函数及冲突处理方法，建立一个hash表并实现查找。 程序代码 #include cout<<"Not present!"; } return 0; } 结果 二叉排序树 #include 数据结构实验指导书 实验一线性表的顺序存储结构 一、实验学时 4学时 二、背景知识:顺序表的插入、删除及应用。 三、目的要求： 1．掌握顺序存储结构的特点。 2．掌握顺序存储结构的常见算法。 四、实验内容 1．从键盘随机输入一组整型元素序列，建立顺序表。（注意：不可将元素个数和元素值写死在程序中） 2．实现该顺序表的遍历（也即依次打印出每个数据元素的值）。 3．在该顺序表中顺序查找某一元素,如果查找成功返回1,否则返回0。 4．实现把该表中某个数据元素删除。 5．实现在该表中插入某个数据元素。 6．实现两个线性表的归并（仿照课本上P26 算法2.7）。 7. 编写一个主函数,调试上述6个算法。 五、实现提示 1.存储定义 #include typedef int ElemType；//元素类型 typedef struct list{ ElemType *elem;//静态线性表 int length; //表的实际长度 int listsize; //表的存储容量 }SqList;//顺序表的类型名 2.建立顺序表时可利用随机函数自动产生数据。 3.为每个算法功能建立相应的函数分别调试，最后在主函数中调用它们。 六、注意问题 插入、删除元素时对于元素合法位置的判断。 七、测试过程 1.先从键盘输入元素个数，假设为6。 2.从键盘依次输入6个元素的值（注意：最好给出输入每个元素的提示，否则除了你自己知道之外，别人只见光标在闪却不知道要干什么），假设是：10,3,8,39,48，2。 3．遍历该顺序表。 4.输入待查元素的值例如39（而不是待查元素的位置）进行查找，因为它在表中所以返回1。假如要查找15,因为它不存在，所以返回0。 5.输入待删元素的位置将其从表中删掉。此处需要注意判断删位置是否合法，若表中有n个元素，则合法的删除位 厦门理工学院专业介绍 厦门理工学院专业介绍 本科专业介绍 材料成型及控制工程专业（本科四年） 【培养目标】 本专业以研究开发各种材料的加工成型工艺和模具设计制造技术为主攻方向，培养具备材料成型及模具设计制造基础知识与应用能力，掌握金属塑性成形、压铸成形和塑料成型工艺及设备控制，具有创新能力，能从事产品开发、材料成型工艺设计、模具设计与制造，企业生产经营管理等工作的高素质工程技术人才。 【主要课程】 工程制图及CAD、工程力学、电工电子技术、机械原理、机械设计、计算机辅助三维设计、机械制造技术基础、检测及控制工程、材料科学基础、材料成型原理、材料成型工艺、材料成型设备、塑料成型工艺与模具设计、冲压工艺及模具课程设计、金属压力铸造工艺与模具设计等。 【就业方向】 在机械、汽车、电子电器、仪器仪表、轻工、日常用品等企业，从事材料成型与控制工程领域的产品开发、技术创新、材料成型工艺设计、 模具设计与制造、企业生产运行管理等工作，还可以进一步攻读本专业及相关专业的硕士学位。 车辆工程专业（本科四年） 【培养目标】 本专业培养具备汽车设计、制造、试验等专业知识与应用能力，掌握汽车电器与电子技术，汽车保养维修、检测与诊断技术，能在汽车及其相关行业中从事汽车设计制造、科技开发、应用研究、经营管理和车辆保险与公估等方面工作的高素质工程技术人才。 【主要课程】 工程制图及CAD、理论力学、材料力学、机械设计、工程材料及材料成形技术基础、液压与气压传动、控制工程基础、机械制造工程基础、汽车构造、汽车设计、汽车理论、汽车试验学、汽车车身设计、汽车制造工艺学、汽车发动机原理、有限元分析、汽车电器与电子技术、汽车检测与诊断技术等课程以及汽车维修理论、汽车保险公估、汽车营销与技术服务等。 【就业方向】 可以在机械、汽车、车辆保险与公估以及汽车相关行业的科研院所、企事业单位、技术开发中心从事车辆设计、制造、商贸和管理等工作，还可以进一步攻读本专业及相关专业的硕士学位。 重庆文理学院软件工程学院实验报告册 专业：_____软件工程__ _ 班级：_____软件工程2班__ _ 学号：_____201258014054 ___ 姓名：_____周贵宇___________ 课程名称：___ 数据结构 _ 指导教师：_____胡章平__________ 2013年 06 月 25 日 实验序号 1 实验名称实验一线性表基本操作实验地点S-C1303 实验日期2013年04月22日 实验内容1.编程实现在顺序存储的有序表中插入一个元素（数据类型为整型）。 2.编程实现把顺序表中从i个元素开始的k个元素删除（数据类型为整型）。 3.编程序实现将单链表的数据逆置，即将原表的数据（a1,a2….an）变成 (an,…..a2,a1)。（单链表的数据域数据类型为一结构体，包括学生的部分信息：学号，姓名，年龄） 实验过程及步骤1. #include { ElemType elem[MAXSIZE]; /*线性表占用的数组空间*/ int last; /*记录线性表中最后一个元素在数组elem[ ]中的位置（下标值），空表置为-1*/ }SeqList; #include "common.h" #include "seqlist.h" void px(SeqList *A,int j); void main() { SeqList *l; int p,q,r; int i; l=(SeqList*)malloc(sizeof(SeqList)); printf("请输入线性表的长度:"); scanf("%d",&r); l->last = r-1; printf("请输入线性表的各元素值:\n"); for(i=0; i<=l->last; i++) { scanf("%d",&l->elem[i]); } px(l,i); printf("请输入要插入的值:\n"); 实验报告 实验六图的应用及其实现 一、实验目的 1．进一步功固图常用的存储结构。 2．熟练掌握在图的邻接表实现图的基本操作。 3．理解掌握AOV网、AOE网在邻接表上的实现以及解决简单的应用问题。 二、实验内容 一>.基础题目：(本类题目属于验证性的，要求学生独立完成) [题目一]：从键盘上输入AOV网的顶点和有向边的信息,建立其邻接表存储结构,然后对该图拓扑排序,并输出拓扑序列. 试设计程序实现上述AOV网 的类型定义和基本操作,完成上述功能。 [题目二]：从键盘上输入AOE网的顶点和有向边的信息,建立其邻接表存储结构,输出其关键路径和关键路径长度。试设计程序实现上述AOE网类型定义和基本操作,完成上述功能。 测试数据：教材图7.29 【题目五】连通OR 不连通 描述：给定一个无向图，一共n个点，请编写一个程序实现两种操作： D x y 从原图中删除连接x，y节点的边。 Q x y 询问x，y节点是否连通 输入 第一行两个数n,m（5<=n<=40000,1<=m<=100000） 接下来m行，每行一对整数 x y （x,y<=n）,表示x,y之间有边相连。保证没有重复的边。 接下来一行一个整数 q（q<=100000） 以下q行每行一种操作，保证不会有非法删除。 输出 按询问次序输出所有Q操作的回答，连通的回答C，不连通的回答D 样例输入 3 3 1 2 1 3 2 3 5 Q 1 2 D 1 2 Q 1 2 D 3 2 Q 1 2 样例输出 C C D 【题目六】 Sort Problem An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not. 【Input】 Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n<= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. 1 <= m <= 100. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character "<" and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input. 【Output】 For each problem instance, output consists of one line. This line should be one of the following three: Sorted sequence determined: y y y… y. Sorted sequence cannot be determined. Inconsistency found. 附件3 厦门理工学院毕业设计（论文）撰写规范 第一条本科生毕业论文字数不少于10000字，毕业设计的篇幅根据专业特点由各系自行界定。 第二条毕业设计（论文）要求文字通畅、条理清楚、结构严谨；观点明确、论证充分、论据详实；版面整洁、数据可靠、图表规范清晰；能反映出学生掌握本学科知识的深广度、驾驭资料和仪器设备的能力、发现分析解决实际问题的能力。 第三条毕业设计（论文）的撰写要求如下： 1.文稿要求：语言流畅，版面整洁，便于装订； 2.图纸要求：图面整洁，布局合理，线条粗细均匀，圆弧连接光滑，尺寸标准规范，文字注释必须使用工程字书写； 3.曲线图表要求：所有曲线、图表、线路图、流程图、程序框图、示意图等不得简单徒手画，须按国家规范标准或工程要求绘制； 4.公式要求：所有公式不得徒手书写，利用Microsoft公式编辑器或Mathtype编辑。 第四条打印及装订顺序要求： 毕业设计（论文）的内容及其装订顺序为：封面、诚信声明书、题目、中外文摘要和关键词、目录、正文、致谢、参考文献。使用A4复印纸输出，上边距为2.5cm，左边距为2.5cm，右边距为2cm，下边距2cm，正文页码居中。（边距问题大家要调整，要在“页面设置”里进行设置，很多同学漏掉了这一条） 1.封面。教务处统一印制，学生填写或打印。填写时应注意：学号及专业名称应填写完整，例如“2003401008”，不能填写成“8号”或“08”；“电子商务”专业，不能填写成“电商”等。 2.诚信声明书。教务处统一印制，学生在完成毕业设计（论文）的同时，需签署一份诚信声明书，声明所撰写的毕业设计（论文）无剽窃他人学术成果，各种数据及参考资料等真实可靠，如有不实之处，则按照学院有关规定接受处罚。（诚信申明书的签字要用手写，所以大家在诚信申明书上签字那一栏要空着，不要打字上去，等输出时才手签上去） 数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 《数据库系统工程师》认证近年试题实例 By jhsun 厦门理工学院计算机科学与技术系 目录 2012年软考数据库系统工程师试题 (3) 2011年软考数据库系统工程师试题 (6) 【参考答案】 (8) 2010年软考数据库系统工程师试题 (9) 【参考答案】 (11) 2009年软考数据库系统工程师试题 (12) 【参考答案】 (13) 2008年软考数据库系统工程师试题 (15) 试题二（共15分） (15) 【参考答案】 (17) 2012年软考数据库系统工程师试题 阅读下列说明，回答问题1至问题5，将解答填入答题纸的对应栏内。[说明] 某企业网上销售管理系统的数据库部分关系模式如下所示： 客户(客户号，姓名，性别，地址，邮编) 产品(产品号，名称，库存，单价) 订单(订单号，时间，金额，客户号) 订单明细(订单号，产品号，数量) 关系模式的主要属性及约束如表2-1所示。 表2-1关系模式的主要属性及约束关系名约束 客户客户号唯一标识一位客户，客户性别取值为“男”或者“女’产品产品号唯一标识一个产品 订单订单号唯一标识一份订单。一份订单必须且仅对应一位客户，一份订单可由一到多条订单明细组成。一位客户可以有多份订单。 订单明细一条订单明细对应一份订单中的一个产品 客户、产品、订单和订单明细关系及部分数据分别如表2-2、2-3、2-4、2-5所示。 表2-2客户关系 客户号姓名性别地址邮编 Ol 王晓丽女南京路2号200005 02 林俊杰男北京路18号200010 表2-3产品关系 产品号名称库存单价 01 产品A 20 298.00 02 产品B 50 168.00 表2-4订单关系 订单号时间金额 客户 号 1001 2006.02.03 1268.00 01 1002 2006.02.03 298.00 02 表2-5订单明细关系订单号产品号数量1001 01 2 1001 02 4 1002 01 1 [问题1](3分) 以下是创建部分关系表的SQL语句，请将空缺部分补充完整。 姓名： 学号： 班级： 2010年12月15日 实验一线性表的应用 【实验目的】 1、熟练掌握线性表的基本操作在顺序存储和链式存储上的实现。、； 2、以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点； 3、掌握线性表的动态分配顺序存储结构的定义和基本操作的实现； 4、通过本章实验帮助学生加深对C语言的使用（特别是函数的参数调用、指针类型的 应用和链表的建立等各种基本操作）。 【实验内容】 约瑟夫问题的实现：n只猴子要选猴王，所有的猴子按1,2，…，n编号围坐一圈，从第一号开始按1,2…，m报数，凡报到m号的猴子退出圈外，如此次循环报数，知道圈内剩下一只猴子时，这个猴子就是猴王。编写一个程序实现上述过程，n和m由键盘输入。【实验要求】 1、要求用顺序表和链表分别实现约瑟夫问题。 2、独立完成，严禁抄袭。 3、上的实验报告有如下部分组成： ①实验名称 ②实验目的 ③实验内容：问题描述：数据描述：算法描述：程序清单：测试数据 算法： #include #include 厦门理工学院uml考试试卷a卷厦门理工学院uml考试试卷A卷 总分42分，1-18题每小题1分，19-30题每小题2分。 1(下列描述中，哪个不是建模的基本原则( d ) A.要仔细的选择模型 B.每一种模型可以在不同的精度级别上表示所要开发的系统 C.模型要与现实相联系 D.对一个重要的系统用一个模型就可以充分描述 2(下列关于软件特点的描述中，哪个是错误的( c ) 软件是被开发或设计的，而不是被制造的; A. B.软件不会“磨损”，但会“退化”; C.软件的开发已经摆脱了手工艺作坊的开发方式; D. 软件是复杂的 3(在UML中，有3种基本构造块，分别是(a ) A. 事物、关系和图 B. 注释、关系和图 C. 事物、关系和结构 D. 注释、关系和结构 4(在UML中，有四种关系，下面哪个不是(b) A.依赖关系 B.继承关系 C.泛化关系 D.实现关系 5(下面哪个不是UML中的静态视图(a) 状态图 A. B.用例图 C.对象图 D.类图 6(用户在银行员工的指导下，使用ATM机，查阅银行帐务系统的个人帐务数 据，并打印其个人用户帐单。在上述 过程中，对ATM机管理系统而言，哪个不是系统的参与者( b) A.用户 B.银行员工 C.打印系统 D.帐务系统 7(在用例之间，会有三种不同的关系，下列哪个不是他们之间可能的关系( d ) A.包含(include) B.扩展(extend) C.泛化(generalization) D.关联(connect) 8(下列关于活动图的说法错误的是( d ) A. 一张活动图从本质上说是一个流程图，显示从活动到活动的控制流 B. 活动图用于对业务过程中顺序和并发的工作流程进行建模。 C. 活动图中的基本要素包括状态、转移、分支、分叉和汇合、泳道、对象 流。 D. 活动图是UML中用于对系统的静态方面建模的五种图中的一种 9(在下面的图例中，哪个用来描述活动(activity)(a) 长春大学计算机学院网络工程专业 数据结构实验报告 实验名称：实验二栈和队列的操作与应用 班级：网络14406 姓名：李奎学号：041440624 实验地点：日期： 一、实验目的： 1．熟练掌握栈和队列的特点。 2．掌握栈的定义和基本操作，熟练掌握顺序栈的操作及应用。 3．掌握链队的入队和出队等基本操作。 4．加深对栈结构和队列结构的理解，逐步培养解决实际问题的编程能力。 二、实验内容、要求和环境： 注：将完成的实验报告重命名为：班级+学号+姓名+（实验二），（如：041340538张三（实验二）），发邮件到：ccujsjzl@https://www.doczj.com/doc/9a5526787.html,。提交时限：本次实验后24小时之内。 阅读程序，完成填空，并上机运行调试。 1、顺序栈，对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数 (1)文件SqStackDef. h 中实现了栈的顺序存储表示 #define STACK_INIT_SIZE 10 /* 存储空间初始分配量*/ #define STACKINCREMENT 2 /* 存储空间分配增量*/ typedef struct SqStack { SElemType *base; /* 在栈构造之前和销毁之后，base 的值为NULL */ SElemType *top; /* 栈顶指针*/ int stacksize; /* 当前已分配的存储空间，以元素为单位*/ }SqStack; /* 顺序栈*/ (2)文件SqStackAlgo.h 中实现顺序栈的基本操作（存储结构由SqStackDef.h 定义） Status InitStack(SqStack &S) { /* 构造一个空栈S */ S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); /* 存储分配失败*/ S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; } int StackLength(SqStack S) { // 返回S 的元素个数，即栈的长度, 编写此函数 洛阳理工学院实验报告 附：源程序： #include { InsertBST(&((*bst)->lchild),key); return OK; } else if(key>(*bst)->key) { InsertBST(&((*bst)->rchild),key); return OK; } } void CreateBST(BSTree *bst) { int key; *bst=NULL; scanf("%d", &key); while (key!=ENDKEY) { InsertBST(bst, key); scanf("%d", &key); } } BSTree SearchBST(BSTree bst, int key) { if(!bst) return NULL; else if(bst->key==key) return bst; //查找成功 else if(bst->key>key) return SearchBST(bst->lchild,key); else return SearchBST(bst->rchild,key); 实验六图的应用及其实现 一、实验目的 1．进一步功固图常用的存储结构。 2．熟练掌握在图的邻接表实现图的基本操作。 3．理解掌握AOE网在邻接表上的实现及解决简单的应用问题。 二、实验内容 [题目]：从键盘上输入AOE网的顶点和有向边的信息,建立其邻接表存储结构,输出其关键路径和关键路径长度。试设计程序实现上述AOE网类型定义和基本操作,完成上述功能。 三、实验步骤 （一）、数据结构与核心算法的设计描述 本实验题目是基于图的基本操作以及邻接表的存储结构之上，着重拓扑排序算法的应用，做好本实验的关键在于理解拓扑排序算法的实质及其代码的实现。 （二）、函数调用及主函数设计 以下是头文件中数据结构的设计和相关函数的声明： typedef struct ArcNode // 弧结点 { int adjvex; struct ArcNode *nextarc; InfoType info; }ArcNode; typedef struct VNode //表头结点 { VertexType vexdata; ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct //图的定义 { AdjList vertices; int vexnum,arcnum; int kind; }MGraph; typedef struct SqStack //栈的定义 { SElemType *base; SElemType *top; int stacksize; }SqStack; int CreateGraph(MGraph &G);//AOE网的创建 int CriticalPath(MGraph &G);//输出关键路径 （三）、程序调试及运行结果分析 （四）、实验总结 在做本实验的过程中，拓扑排具体代码的实现起着很重要的作用，反复的调试和测试占据着实验大量的时间，每次对错误的修改都加深了对实验和具体算法的理解，自己的查错能力以及其他各方面的能力也都得到了很好的提高。最终实验结果也符合实验的预期效果。 四、主要算法流程图及程序清单 1、主要算法流程图： 2、程序清单： 创建AOE网模块： int CreateGraph(MGraph &G) //创建有向网 { int i,j,k,Vi,Vj; ArcNode *p; cout<<"\n请输入顶点的数目、边的数目"< 厦门理工学院毕业设计（论文）撰写规范第一条本科生毕业论文字数不少于8000字，英语专业学生的毕业论文字数不少于5000英文单词。毕业设计的篇幅根据专业特点由各系自行界定。 第二条毕业设计（论文）要求文字通畅、条理清楚、结构严谨；观点明确、论证充分、论据详实；版面整洁、数据可靠、图表规范清晰；能反映出学生掌握本学科知识的深广度、驾驭资料和仪器设备的能力、发现分析解决实际问题的能力。 第三条毕业设计（论文）的撰写要求如下： 1.文稿要求：语言流畅，版面整洁，便于装订； 2.图纸要求：图面整洁，布局合理，线条粗细均匀，圆弧连接光滑，尺寸标准规范，文字注释必须使用工程字书写； 3.曲线图表要求：所有曲线、图表、线路图、流程图、程序框图、示意图等不得简单徒手画，须按国家规范标准或工程要求绘制； 4.公式要求：所有公式不得徒手书写，利用Microsoft公式编辑器或Mathtype编辑。 第四条打印及装订顺序要求： 毕业设计（论文）的内容及其装订顺序为：封面、诚信声明书、题目、中外文摘要和关键词、目录、正文、致谢、参考文献。使用A4复印纸输出，上边距为2.5cm，左边距为2.5cm，右边距为2cm，下边距2cm，正文页码居中。 1.封面。教务处统一印制，学生填写或打印。填写时应注意：学号及专业名称应填写完整，例如“2003401008”，不能填写成“8号”或“08”；“电子商务”专业，不能填写成“电商”等。 2.诚信声明书。教务处统一印制，学生在完成毕业设计（论文）的同时，需签署一份诚信声明书，声明所撰写的毕业设计（论文）无剽窃他人学术成果，各种数据及参考资料等真实可靠，如有不实之处，则按照学院有关规定接受处罚。 3.题目、中外文摘要和关键词 [1]设计（论文）题目应该简短、明确、有概括性；字数要适当，一般不宜超过20个汉字，用三号黑体字，可以分为1或2行居中打印。题目下空１行打印摘要。 [2]中外文摘要。摘要是以简要文字介绍研究课题的目的、方法、内容及主要结果， 邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template int vertexNum, arcNum; }; #endif MGraph.cpp #include 招标投标企业报告 厦门理工学院建筑设计院有限公司 本报告于 2019年9月19日 生成 您所看到的报告内容为截至该时间点该公司的数据快照 目录 1. 基本信息：工商信息 2. 招投标情况：中标/投标数量、中标/投标情况、中标/投标行业分布、参与投标 的甲方排名、合作甲方排名 3. 股东及出资信息 4. 风险信息：经营异常、股权出资、动产抵押、税务信息、行政处罚 5. 企业信息：工程人员、企业资质 * 敬启者：本报告内容是中国比地招标网接收您的委托，查询公开信息所得结果。中国比地招标网不对该查询结果的全面、准确、真实性负责。本报告应仅为您的决策提供参考。 一、基本信息 1. 工商信息 企业名称：厦门理工学院建筑设计院有限公司统一社会信用代码：91350203155010510U 工商注册号：350203100000354组织机构代码：155010510 法定代表人：/成立日期：2004-06-04 企业类型：/经营状态：存续 注册资本：300万人民币 注册地址：厦门市集美区银亭路28号之七 营业期限：2004-06-04 至 2054-06-04 营业范围：承担建筑设计乙级范围内工程设计；建筑装修、相关市政道路设计、相关研究及技术咨询；举办土木、建筑专业培训班。 联系电话：*********** 二、招投标分析 2.1 中标/投标数量 企业中标/投标数： 个 （数据统计时间：2017年至报告生成时间） 7 2.2 中标/投标情况（近一年） 截止2019年9月19日，根据国内相关网站检索以及中国比地招标网数据库分析，未查询到相关信息。不排除因信息公开来源尚未公开、公开形式存在差异等情况导致的信息与客观事实不完全一致的情形。仅供客户参考。 2.3 中标/投标行业分布（近一年） 截止2019年9月19日，根据国内相关网站检索以及中国比地招标网数据库分析，未查询到相关信息。不排除因信息公开来源尚未公开、公开形式存在差异等情况导致的信息与客观事实不完全一致的情形。仅供客户参考。 2.4 参与投标的甲方前五名（近一年） 2 厦门象屿港湾开发建设有限公司 （） 序号地区日期标题中标情况1厦门2017-04-28同安新城小学扩建工程(设计)中标2厦门2017-04-26同安新城小学扩建工程(设计)工程建设项目中标1 厦门理工学院 （） 序号地区日期标题中标情况1厦门2015-05-04厦门务实-竞争性谈判-2015-SH152厦门理工学院南大门改造工程中标厦门市集美城市发展有限公司 （） 1 序号地区日期标题中标情况 数据结构实验 实验四、图遍历的演示。 【实验学时】5学时 【实验目的】 （1）掌握图的基本存储方法。 （2）熟练掌握图的两种搜索路径的遍历方法。 【问题描述】 很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示连通的无向图上，遍历全部结点的操作。 【基本要求】 以邻接多重表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。 【测试数据】 教科书图7.33。暂时忽略里程，起点为北京。 【实现提示】 设图的结点不超过30个，每个结点用一个编号表示（如果一个图有n个结点，则它们的编号分别为1，2，…，n）。通过输入图的全部边输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制。注意，生成树的边是有向边，端点顺序不能颠倒。 【选作内容】 （1）借助于栈类型（自己定义和实现），用非递归算法实现深度优先遍历。（2）以邻接表为存储结构，建立深度优先生成树和广度优先生成树，再按凹入表或树形打印生成树。 （3）正如习题7。8提示中分析的那样，图的路径遍历要比结点遍历具有更为广泛的应用。再写一个路径遍历算法，求出从北京到广州中途不过郑州的所有简单路径及其里程。 【源程序】 #include 厦门理工学院uml考试试卷A卷 总分42分，1-18题每小题1分，19-30题每小题2分。 1．下列描述中，哪个不是建模的基本原则（ d ） A.要仔细的选择模型 B.每一种模型可以在不同的精度级别上表示所要开发的系统 C.模型要与现实相联系 D.对一个重要的系统用一个模型就可以充分描述 2．下列关于软件特点的描述中，哪个是错误的（ c ） A.软件是被开发或设计的，而不是被制造的； B.软件不会“磨损”，但会“退化”； C.软件的开发已经摆脱了手工艺作坊的开发方式； D. 软件是复杂的 3．在UML中，有3种基本构造块，分别是（a ） A. 事物、关系和图 B. 注释、关系和图 C. 事物、关系和结构 D. 注释、关系和结构 4．在UML中，有四种关系，下面哪个不是（b） A.依赖关系 B.继承关系 C.泛化关系 D.实现关系 5．下面哪个不是UML中的静态视图（a） A.状态图 B.用例图 C.对象图 D.类图 6．用户在银行员工的指导下，使用ATM机，查阅银行帐务系统的个人帐务数据，并打印其个人用户帐单。在上述过程中，对ATM机管理系统而言，哪个不是系统的参与者( b) A.用户 B.银行员工 C.打印系统 D.帐务系统 7．在用例之间，会有三种不同的关系，下列哪个不是他们之间可能的关系（ d ） A.包含（include） B.扩展（extend） C.泛化（generalization） D.关联（connect） 8．下列关于活动图的说法错误的是（ d ） A. 一张活动图从本质上说是一个流程图，显示从活动到活动的控制流 B. 活动图用于对业务过程中顺序和并发的工作流程进行建模。 C. 活动图中的基本要素包括状态、转移、分支、分叉和汇合、泳道、对象流。 D. 活动图是UML中用于对系统的静态方面建模的五种图中的一种 9．在下面的图例中，哪个用来描述活动（activity）（a） A B C D 10．事件（event）表示对一个在时间和空间上占据一定位置的有意义的事情的规格说明，下面哪个不是事件的类型（ c ） A.信号 B.调用事件 C.空间事件 D.时间事件 11．下列关于状态图的说法中，正确的是（ c ） A. 状态图是UML中对系统的静态方面进行建模的五种图之一。 B. 状态图是活动图的一个特例，状态图中的多数状态是活动状态 C. 活动图和状态图是对一个对象的生命周期进行建模，描述对象随时间变化的行为。 D. 状态图强调对有几个对象参与的活动过程建模，而活动图更强调对单个反应型对象建模 12．下面（a）不属于UML中的静态视图 A.状态图 B.用例图 C.对象图 D.类图 13．通常对象有很多属性，但对于外部对象来说某些属性应该不能被直接访问，下面哪个不是UML中的类成员访问限定性（ c） A.公有的（public） B.受保护的（protected） C.友员（friendly） D.私有的（private） 14．UML中类的有三种，下面哪个不是其中之一（b ） A.实体类 B.抽象类数据结构实验
厦门理工学院专业介绍
数据结构实验答案1
数据结构_实验六_报告
厦门理工学院本科毕业设计(论文)撰写规范
数据结构实验报告
数据库系统工程师认证之二_SQL应用与数据库操作_试题实例
数据结构实验报告
数据结构第六章实验
厦门理工学院uml考试试卷a卷
数据结构实验
数据结构实验六
数据结构实验六 图的应用及其实现
厦门理工学院毕业设计(论文)撰写规范
数据结构实验报告图实验
厦门理工学院建筑设计院有限公司_中标190920
数据结构实验四五六
厦门理工学院uml考试试卷A卷
相关主题
文本预览