1 / 6
实验一线性表操作
一、实验目的
1熟悉并掌握线性表的逻辑结构、物理结构。
2熟悉并掌握顺序表的存储结构、基本操作和具体的函数定义。
3熟悉VC++程序的基本结构，掌握程序中的用户头文件、实现文件和主文件之间的相互关系及各自的作用。
4熟悉VC++操作环境的使用以及多文件的输入、编辑、调试和运行的全过程。
二、实验要求
1实验之前认真准备，编写好源程序。
2实验中认真调试程序，对运行结果进行分析，注意程序的正确性和健壮性的验证。
3不断积累程序的调试方法。
三、实验内容
基本题:
1对元素类型为整型的顺序存储的线性表进行插入、删除和查找操作。
加强、提高题：
2、编写一个求解Josephus问题的函数。用整数序列1, 2, 3, ……, n表示顺序围坐在圆桌周围的人。然后使用n = 9, s = 1, m = 5，以及n = 9, s = 1, m = 0，或者n = 9, s = 1, m = 10作为输入数据，检查你的程序的正确性和健壮性。最后分析所完成算法的时间复杂度。定义JosephusCircle类，其中含完成初始化、报数出圈成员函数、输出显示等方法。（可以选做其中之一）
加强题：
2 / 6
（1）采用数组作为求解过程中使用的数据结构。
提高题：
（2）采用循环链表作为求解过程中使用的数据结构。运行时允许指定任意n、s、m数值，直至输入n = 0退出程序。
实验二栈、队列、递归应用
一、实验目的
1熟悉栈、队列这种特殊线性结构的特性
2熟练掌握栈、队列在顺序存储结构和链表存储结构下的基本操作。
二、实验要求
1实验之前认真准备，编写好源程序。
2实验中认真调试程序，对运行结果进行分析，注意程序的正确性和健壮性的验证。
3不断积累程序的调试方法。
三、实验内容
基本题（必做）：
1分别就栈的顺序存储结构和链式存储结构实现
栈的各种基本操作。
2、假设以带头结点的循环链表表示队列，并且
实验六 树与二叉树
6.1实验目的：
（1） 掌握二叉树链表的结构和二叉树的建立过程；
（2） 掌握二叉树的基本操作，加深对二叉树的理解，逐步培养解决实际问题的编程能力。
6.2实验要求：
（1） 复习课本中有关树与二叉树的知识；
（2） 用C语言完成算法和程序设计并上机调试通过；
（3） 撰写实验报告，给出算法思路或流程图和具体实现（源程序）、算法分析结果（包括时间复杂度、空间复杂度以及算法优化设想）、输入数据及程序运行结果（必要时给出多种可能的输入数据和运行结果）。
6.3基础实验
[实验1] 二叉树的构造
实验内容与要求:
按先序序列构造一棵二叉链表表示的二叉树T；
分析:
二叉树是每个结点至多只有两棵子树，并有左、右之分，顺序不能任意颠倒的一种非线性结构。二叉树常用的存储结构是二叉链表形式，二叉链表由一个数据项data（用于存放结点的值）和两个指针项lchild、rchild（分别指向该结点的左、右子树）。结点及结构如图6-1所示：
//- - - - - - 二叉树的二叉链表存储表示模型- - - - - - -
typedef struct BiTNode{
TElemType data;
Struct BiTNode * lchild, * rchild; //左右孩子指针
}BiTNode, * BiTree;
将此结构定义放在一个头文件BiTNode.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出二叉链表的初始化及常量的定义。
实现提示
按先序序列建立一棵二叉树，先构造根结点，再构造根的左、右子树；每一棵子树又都是一颗二叉树，所以构造一棵子树的过程与构造整棵二叉树的过程完全相同， 按照先序序列，先构造根，再构造左子树，然后构造右子树；采用递归形式直到叶子结点为止。以下是算法描述： lchild data
rchild
图6-1含有两个指针的二叉树的结点及结构 data
《数据结构和算法》
实验指导书
实验及学时数分配
序号 实验名称 学时数（小时）
1 实验一 线性表 4
2 实验二 树和二叉树 2
3 实验三 图 2
4 实验四 查找 2
5 实验五 内部排序 2
合计 12
几点要求：
一、 上机前：认真预习相关实验内容，提前编写算法程序，上机时检查（未提前编写程序者，扣除平时成绩中实验相关分数）。
二、 上机中：在Turbo C或VC6.0环境中，认真调试程序，记录调试过程中的问题、解决方法以及运行结果。上机时签到；下机时验收签字。
三、 下机后：按要求完成实验报告，并及时提交（实验后1周内）。
实验一 线性表
【实验目的】
1、 掌握用Turbo c上机调试线性表的基本方法；
2、 掌握线性表的基本操作，插入、删除、查找以及线性表合并等运算在顺序存储结构和链式存储结构上的运算；
3、 运用线性表解决线性结构问题。
【实验学时】
4 学时
【实验类型】
设计型
【实验内容】
1、 顺序表的插入、删除操作的实现；
2、 单链表的插入、删除操作的实现；
3、 两个线性表合并算法的实现。(选做)
【实验原理】
1、 当我们在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表中第i个元素之后的所有元素依次后移一个位置，以便腾出一个位置，再把新元素插入到该位置。若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置；
2、 当我们在线性表的链式存储结构上的第i个位置上插入一个元素时，只需先确定第i个元素前一个元素位置，然后修改相应指针将新元素插入即可。若是欲删除第i个元素时，也必须先确定第i个元素前一个元素位置，然后修改相应指针将该元素删除即可；
3、 详细原理请参考教材。
【实验步骤】
一、用C语言编程实现建立一个顺序表，并在此表中插入一个元素和删除一个元素。
1、 通过键盘读取元素建立线性表；（从键盘接受元素个数n以及n个整形数；按一定格式显示所建立的线性表）
数据结构实验指导书
（计算机科学与技术专业）
淮南师范学院
计算机与信息工程系
2015.9 2
前言
数据结构是软件开发的基础，数据结构课程是软件工程、计算机科学与技术、网络工程、信息安全、物联网工程等专业的必修技术基础课程。该课程是在学生学习高级语言程序设计课程基础上，使学生掌握各种常用数据结构的逻辑表示、存储表示、处理方法及应用算法设计，学会常用数据分类和数据查找的技术，对所设计的算法会做定量或定性的分析比较，培养学生的算法设计与分析的能力。通过该课程的学习，使学生学会分析数据对象特性，选择合适的数据结构、存贮结构及相应的基本处理算法；初步掌握算法的时间空间复杂度分析技巧。既为学生学习后继课程打好基础，也为将来软件开发提供理论指导。
数据结构具有很强的实践性，只有通过编程上机实验，才能真正领会数据结构的真正内涵，并灵活运用数据结构的基本知识提高自己的软件开发能力。
《数据结构》实验项目一览表
课程名称：数据结构 学时：16 适应专业：计算机科学与技术
序 号 实验项目名称 学时 实验要求 实验类型
0808090120301 顺序表及其应用 2 必做 验证
0808090120302 链表及其应用 2 必做 验证
0808090120303 栈、队列及其应用 2 必做 验证
0808090120304 串及其应用 2 必做 验证
0808090120305 树和二叉树 2 必做 验证
0808090120306 二叉树的应用 2 必做 验证
0808090120307 图及其应用 2 必做 验证
0808090120308 查找与排序 2 必做 验证
学时总计 16 3
实验1：顺序表及其应用
1．实验目的：
（1）熟练掌握VC或Dev C++集成环境和程序开发步骤；
（2）熟练掌握顺序表的插入、删除、查找定位等基本算法；
（3）能利用顺序表解决简单的问题。
2．实验原理：
线性表是最基本最常用的一种线性结构。其特点是除了第一个元素和最后一个元素以外，其他数据元素都只有一个前驱和一个后继。一个线性表中的数据元素应具有相同的描述性质，即属于同一个数据对象。
