数据结构实验指导书0330.docx
《数据结构实验指导书0330.docx》由会员分享，可在线阅读，更多相关《数据结构实验指导书0330.docx（8页珍藏版）》请在冰点文库上搜索。
数据结构实验指导书0330
华北电力大学科技学院
实验报告
实验名称数据结构试验
课程名称数据结构
专业班级：
学生姓名：
学号：
成绩：
指导老师：
实验日期：
2011年3月-6月
（实验报告如打印，纸张用A4，左装订；页边距：
上下2.5cm，左2.5cm，右2.0cm；字体：
字体小四号，1.25倍行距。
）
验证性、综合性实验报告应包含的主要内容：
一、实验目的及要求
1．实验目的
2．实验要求
二、所用仪器、设备
1．所需的硬件设备
2．所需的软件列表
三、实验原理
1．实验所用到的原理或理论
2．结合本实验阐述如何将理论与实验相结合
四、实验步骤（附程序流程图）
五、程序源代码
六、讨论与结论（对实验现象、实验故障及处理方法、实验中存在的问题等进行分析和讨论，对实验的进一步想法或改进意见）
七、所附实验输出的结果或数据（按照以上格式书写报告）
实验一顺序表及其应用
一、实验目的及要求
1、实验目的
（1）熟悉VC++上机环境，进一步掌握C语言的结构特点。
（2）掌握线性表的顺序存储结构的定义及C语言实现。
（3）掌握线性表在顺序存储结构即顺序表中的各种基本操作的实现。
（4）掌握栈和队列的顺序表示和实现。
2、实验要求
（1）用顺序存储结构实现栈和循环队列。
（2）编写完整程序完成下面的实验内容并上机运行。
（3）整理并上交实验报告。
二、实验内容
1.约瑟夫环的实现：
设有n个人围坐在圆桌周围，现从某个位置i上的人开始报数，数到m的人就站出来。
下一个人，即原来的第m+1个位置上的人，又从1开始报数，再是数到m的人站出来。
依次重复下去，直到全部的人都站出来，按出列的先后又可得到一个新的序列。
由于该问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus问题。
例如：
当n=8,m=4,i=1时，得到的新序列为：
4，8，5，2，1，3，7，6
编写程序选择顺序存储方式模拟整个过程，并依次输出出列的各人的编号。
2、表达式的计算：
（选做）
1）问提描述：
输入形如：
某单字母变量=中缀表达式。
其中中缀表达式可以包括整数、单字母变量、二元操作符+、-、*、/、以及括号（）。
根据输入，求得表达式的解，设计算法要求：
1将等式右边的中缀表达式转换成后缀表达式，并求值。
然后以
单字母变量后缀表达式值
的形式，存放在内存，并打印输出。
②在①的基础上，对用户提出的中缀表达式求值（若非整数，则四舍五入取整）。
2）例如：
输入A=（8*6-5）*（3+6/2）
求得的后缀表达式及值
A86*5-362/+*258
实现提示：
数据结构采用顺序存储实现线性表，在中缀表达式转化为后缀表达式时，利用顺序存储实现栈。
实验二链表及其应用
一、实验目的及要求
1、实验目的
（1）熟悉VC++上机环境，进一步掌握C语言的结构特点。
（2）掌握线性表的链式存储结构即单链表的定义及C语言实现。
（3）掌握线性表在链式存储结构即单链表中的各种基本操作。
（4）掌握栈和队列的链式存储结构的表示和实现。
2、实验要求
（1）用链式存储结构实现单链表（和单向循环链表）的建立、查找和删除等运算。
（2）编写完整程序完成下面的实验内容并上机运行。
（3）整理并上交实验报告。
二、实验内容
1.约瑟夫环的问题：
设有n个人围坐在圆桌周围，现从某个位置i上的人开始报数，数到m的人就站出来。
下一个人，即原来的第m+1个位置上的人，又从1开始报数，再是数到m的人站出来。
依次重复下去，直到全部的人都站出来，按出列的先后又可得到一个新的序列。
由于该问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus问题。
例如：
当n=8,m=4,i=1时，得到的新序列为：
4，8，5，2，1，3，7，6
用单向循环链表存储结构模拟此过程。
实现提示：
typedefstructNode
{ intdata;
structNode*next;}*nodetype;//定义指向链节点类型的指针
1）先建立单向循环链表。
构造一个结点需用到C语言的标准函数malloc（），如给指针变量p分配一个结点的地址：
p=（nodetype）malloc（sizeof（structNode））;该语句的功能是申请分配一个类型为结构体类型为Node的结点的地址空间，并将首地址存入指针变量p中。
当结点不需要时可以用标准函数free（p）释放结点存储空间，这时p为空值（NULL）。
2）注意在删除第m个节点时，需要一个辅助指针指向删除节点的前驱节点，删除节点只需要修改指针即可。
2.若已知非空线性链表第一个结点的指针为list（即非空不带头节点的单链表头指针为list），请写一个算法并实现,将该链表中数据域值最小的那个结点移到链表的最前端。
实现提示：
此算法需要四个辅助指针，扫描链表节点指针p以及其前驱节点指针r,数据域小的节点指针q以及其前驱节点指针s.
实验三二叉树
一、实验目的及要求
1、实验目的
（1）通过实验，掌握二叉树的建立与存储
（2）通过实验，掌握二叉树的遍历方法
2、实验要求
（1）二叉树需要用二叉链表作为节点类型描述。
（2）二叉树的遍历递归算法能够转换为非递归算法。
（3）编写完整程序完成下面的实验内容并上机运行。
（4）整理并上交实验报告。
二、实验内容
1、问题描述
利用先序遍历建立一棵二叉树，并分别用前序、中序、后序遍历该二叉树
2、节点形式
Lchild
data
Rchild
3、说明
（1）输入数据：
1，2，3，0，0，4，0，0，5，0，0其中“0”表示空子树。
（2）输出数据：
先序：
1，2，3，4，5
中序：
3，2，4，1，5
后序：
3，4，2，5，1
三、实验步骤
1.建立自己的头文件BT.H，内容包括二叉链表的结构描述、二叉树的建立、二叉树的先序、中序与后序遍历算法。
2.建立二叉树,并通过调用函数,输出先序遍历、中序遍历与后序遍历的结果。
实现提示：
二叉链表的类型定义如下：
typedefstructbtnode
{
intdata;
structbtnode*Lchild,*Rchild;
}*bitreptr
2、说明
（1）图的邻接表存储：
（2）输出数据：
深度优先序列：
1→2→4→8→5→3→6→7
广度优先序列：
1→2→3→4→5→6→7→8
三、实验步骤
1.建立自己的头文件TU.H，内容包括邻接表的结构描述、邻接表的建立、图的深度优先与广度优先遍历算法。
2.建立图的邻接表存储结构,并通过调用函数,输出深度优先、广度优先遍历的结果。
实现提示：
邻接表形式
弧节点
adjvex
next
顶点节点：
vertex
link
邻接表的类型定义：
#definemax_vertex_num//图的顶点数
typedefstructEdgeNode//弧节点的结构
{intadjvex;//该弧所指向的顶点位置
StructEdgeNode*next;//指向下一条弧的指针
}；
typedefstructVnode//顶点节点结构
{intvertex;//顶点信息
StructEdgeNode*link;//指向第一条依附该顶点的弧
}AdjList[max_vertex_num];
（3）
（3）每个考生建立一个纪录、格式如下
姓名
政治
语文
数学
英语
总分
类别
三、实验步骤
1、用户输入每个考生姓名、考试成绩等信息，根据题目给的纪录格式存储。
2、根据类别及每一类按总分从高到低排序，根据排序结果输出n份录取通知书。
3、根据排序结果查找并输出在第一类中英语成绩最好者的纪录信息。
升级会员 