实验报告
实验名称数据结构试验
课程名称数据结构
专业班级：学生姓名：
学号：成绩：
指导老师：实验日期：2011年3月-6月（实验报告如打印，纸张用A4，左装订；页边距：上下2.5cm，左2.5cm，右2.0cm；字体：字体小四号，1.25倍行距。）
验证性、综合性实验报告应包含的主要内容：
一、实验目的及要求
1．实验目的
2．实验要求
二、所用仪器、设备
1．所需的硬件设备
2．所需的软件列表
三、实验原理
1．实验所用到的原理或理论
2．结合本实验阐述如何将理论与实验相结合
四、实验步骤（附程序流程图）
五、程序源代码
六、讨论与结论（对实验现象、实验故障及处理方法、实验中存在
的问题等进行分析和讨论，对实验的进一步想法或改进意见）
七、所附实验输出的结果或数据（按照以上格式书写报告）
②在①的基础上，对用户提出的中缀表达式求值（若非整数，则四舍五入取整）。
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
用单向循环链表存储结构模拟此过程。
实现提示：typedef struct Node
{int data;
struct Node*next;}*nodetype;//定义指向链节点类型的指针
1）先建立单向循环链表。
构造一个结点需用到C语言的标准函数malloc()，如给指针变量p分配一个结点的地址：p=(nodetype)malloc(sizeof(struct Node));该语句的功能是申请分配一个类型为结构体类型为Node的结点的地址空间，并将首地址存入指针变量p中。当结点不需要时可以用标准函数free(p)释放结点存储空间，这时p为空值（NULL）。
2）注意在删除第m个节点时，需要一个辅助指针指向删除节点的前驱节点，删除节点只需要修改指针即可。
2.若已知非空线性链表第一个结点的指针为list（即非空不带头节点的单链表头指针为list），请写一个算法并实现,将该链表中数据域值最小的那个结点移到链表的最前端。
实现提示：此算法需要四个辅助指针，扫描链表节点指针p以及其前驱节点指针r,数据域小的节点指针q以及其前驱节点指针s.
实验二线性表及其应用—
模拟飞机场订票和退票系统
一、实验目的及要求
1、实验目的
(1)熟悉VC++上机环境，进一步掌握C语言的结构特点。
(2)掌握线性表的链式存储结构即单链表的定义及C语言实现。
(3)掌握线性表在链式存储结构即单链表中的各种基本操作。
(4)掌握栈和队列的链式存储结构的表示和实现。
2、实验要求
(1)用顺序存储结构实现飞机场航次信息，用链式存储结构实现乘客信息。
(2)编写完整程序完成下面的实验内容并上机运行。
(3)整理并上交实验报告。
二、实验内容
1、问题描述
假定某民航机场有m个航次的班机，每个航次都只到达一个目的地。试为该机场售票处设计一个自动订票和退票系统。要求系统具有下列功能：
（1）订票：若该航次余票数大于等于乘客订票数，则在该航次的乘客表（按乘客姓氏字母顺序连接）中，插入订票乘客的信息项，并修改该航次有关数据；否则，给出相应的提示信息。
（2）退票：若该航次当前退票数小于等于乘客原订票数，则在相应的乘客表中找到该乘客项，修改该航次及乘客表中有关数据。当由于退票，使得该乘客的订票
数为0时，要从乘客表中撤销该乘客项；否则，给出相应的提示信息。
（3）将某航次的余票数恢复初值---该航次的最大客票数
2、说明
（1）输入数据。T为功能标志，不同的功能要求不同的输入数据。
1)T=0设置或恢复余票数初值。输入a,需要设置或恢复初值的航次。
2)T=1订票。输入a，订票的航次；输入n，乘客姓名；输入c，订票数。
3）T=2退票。输入a，退票的航次；输入n，乘客姓名；输入c，退票数。
实验四图
一、实验目的及要求
1、实验目的
(1)掌握图的基本存储方法。
(2)掌握有关图的操作算法并用c语言实现。
(3)熟练掌握图的两种搜索路径的遍历方法。
2、实验要求
(1)图的存储结构采用邻接表结构。
(2)分别用深度优先和广度优先搜索对图进行遍历。
(3)编写完整程序完成下面的实验内容并上机运行。
(4)整理并上交实验报告。
二、实验内容
1、问题描述
对给定的下图采用邻接表结构存储，并分别用深度优先和广度优先搜索对图进行遍历。
2、说明
(1)图的邻接表存储：
实验五查找与排序
一、实验目的及要求
1、实验目的
(1)掌握查找的不同方法，并能用c语言实现查找算法。
(2)掌握常用的排序方法，并掌握用c语言实现排序算法的方法。
(3)深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用。
(4)了解各种方法的排序过程及其时间复杂度的分析方法。
2、实验要求
(1)根据题目要求选择合适的查找算法和排序算法。
(2)按照题目要求将结果输出。
(3)编写完整程序完成下面的实验内容并上机运行。
(4)整理并上交实验报告。
二、实验内容
1、问题描述
假设某公司招工n名，报考者的政审、体检已通过，现在要根据报考者的考试成绩择优录取。考试课程有：政治、语文、数学、英语四门。考试成绩分为四类：第一类为四门都及格；第二类为一门成绩不及格；第三类为两门成绩不及格；其余为第四类。录取方法是按类次并在每一类中按总分从高到低录取。
试设计一个成绩处理程序，要求打印输出n份录取通知书，列出录取者四门课程的成绩及总分，最后查找并输出在第一类中英语成绩最好者的纪录。（假设第i名和第i+1名一定不会同类且总分相等。）
2、说明
(1)输入数据：输入每个考生的姓名及各门课程的考试成绩。
(2)输出数据：按照择优录取的次序打印出n份录取通知书如下图：
华北电力大学科技学院实验报告
第11页下载本文
