北 京 林 业 大 学

实 验 任 务 书

课程名称： 数据结构 实验学时： 16 适用专业：计算机科学与技术 数字媒体艺术 开设学院： 信息学院

备注：实验共分4次，其中实验1――实验3为设计性实验，实验4为综合性实验，具体安排下面一一列出。

北 京 林 业 大 学

09学年—10学年第 2学期 数据结构实验任务书

专业名称： 实验学时： 4 课程名称：数据结构 任课教师： 李冬梅 实验题目：线性表的基本操作 实验环境： Visual C++ 实验目的：

1、掌握线性表的定义；

2、掌握线性表的基本操作，如建立、查找、插入和删除等。

实验内容：

定义一个包含学生信息（学号，姓名，成绩）的的顺序表和链表，使其具有如下功能： (1) 根据指定学生个数，逐个输入学生信息； (2) 逐个显示学生表中所有学生的相关信息；

(3) 根据姓名进行查找，返回此学生的学号和成绩；

(4) 根据指定的位置可返回相应的学生信息（学号，姓名，成绩）； (5) 给定一个学生信息，插入到表中指定的位置； (6) 删除指定位置的学生记录； (7) 统计表中学生个数。

实验提示：

学生信息的定义： typedef struct {

char no[8]; //8位学号 char name[20]; //姓名 int price; //成绩 }Student;

顺序表的定义

typedef struct {

Student *elem; //指向数据元素的基地址

int length; //线性表的当前长度 }SqList；

链表的定义：

typedef struct LNode{

Student data; //数据域 struct LNode *next; //指针域 }LNode,*LinkList;

实验要求：

(1) 程序要添加适当的注释，程序的书写要采用缩进格式。

(2) 程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应，如插入删除时指定的位置不对等等。

(3) 程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。 (4) 根据实验报告模板详细书写实验报告,在实验报告中给出链表根据姓名进行查找的算法和插入算法的流程图。

(5) 上传源程序和实验报告到ftp的相应班级所在文件夹。顺序表的源程序保存为SqList.cpp，链表的源程序保存为LinkList.cpp，实验报告命名为：实验报告1.doc。源程序和实验报告压缩为一个文件（如果定义了头文件则一起压缩），按以下方式命名：学号姓名.rar，如070814101薛力.rar。

北 京 林 业 大 学

09学年—10学年第 2 学期 数据结构实验任务书

专业名称： 实验学时： 4 课程名称：数据结构 任课教师： 李冬梅 实验题目：二叉树的基本操作 实验环境： Visual C++ 实验目的：

1．掌握二叉树的定义；

2．掌握二叉树的基本操作，如二叉树的建立、遍历、结点个数统计、树的深度计算等。

实验内容：

用递归的方法实现以下算法：

1．以二叉链表表示二叉树，建立一棵二叉树（算法5.3）； 2．输出二叉树的中序遍历结果（算法5.1）； 3．输出二叉树的前序遍历结果（见讲稿）； 4．输出二叉树的后序遍历结果（见讲稿）； 5．计算二叉树的深度（算法5.5）； 6．统计二叉树的结点个数（算法5.6）； 7．统计二叉树的叶结点个数；

8．统计二叉树的度为1的结点个数；

9．输出二叉树中从每个叶子结点到根结点的路径。

选做内容

1．交换二叉树每个结点的左孩子和右孩子；

2．设计二叉树的双序遍历(DblOrderTraverse)算法（双序遍历是指对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树）。

实验提示：

7．统计二叉树的叶结点个数 int LeafNodeCount(BiTree T ){ 如果是空树，则叶子个数为0;

如果是叶子结点，则叶子结点个数为1（如何表示叶子结点？？？） 否则叶结点个数为左子树的叶结点个数+右子树的叶结点个数 }

实验要求：

(1) 程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应。 (2) 程序要添加适当的注释，程序的书写要采用缩进格式。

(3) 根据实验报告模板详细书写实验报告,上交一份实验报告打印稿。

(4) 源程序保存为“sy2.cpp”，实验报告命名为“实验报告2.doc”。将这两个文件压缩为一个文件，按以下方式命名：学号姓名.rar，上传到ftp的相应班级所在文件夹。