叶茂枝--《数据结构（C语言）》实验大纲

《数据结构》实验课程教学大纲

开课单位： 宁德师范学院计算机系 设置类别： 非独立设课 学 时： 18学时 实验项目总数： 7

实验教材：《数据结构习题集与上机指导》，严蔚敏，清华大学出版社 主要设备（环境）：微机、C语言编程环境（VC++）

一、 教学目的

《数据结构》是计算机科学与技术专业的一门重要的专业基础课，课程旨在使学生学会计算机加工的数据对象的特性，学会数据的组织方法，以便选择合适的数据的逻辑结构及存储结构，并进行相应的运算。实验是该课程实践教学的重要环节，目的是培养学生根据求解问题的性质选择合理的数据结构，提高分析、设计、编程以及控制求解算法的时间、空间复杂性的能力。

二、 基本要求

《数据结构》是计算机专业的专业核心基础课程，其先修课程有至少一门高级语言。数据结构课程将覆盖计算机软件实现中的大部分的基本算法，并具有一定的深度和广度，使学生对计算机常用基础算法有一个全盘的了解；通过此课的学习，学生应该具有针对所给的问题设计和实现高效算法的能力。通过上机实验，将使学生熟悉、掌握课堂教学中所学的大部分算法。

同时，上机实习是对学生在软件设计方面的综合训练，包括问题

分析，总体结构设计，用户界面设计，程序设计基本技能和技巧等，以培养良好的编程风格和科学作风。通过理论联系实际，以最终提高学生动手操作的能力以及分析问题的能力。

三、 实验项目设置

实验 序号 试验 学时 2 2 2 2 4 2 4 实验名称 试验要求 试验类型 每组人数 1 2 3 4 5 6 7 顺序表 单链表 栈 队列 二叉树的遍历 查找 必修 必修 必修 必修 必修 必修 必修 设计 设计 设计 验证 验证 设计 设计 1 1 1 1 1 1 1 数据的排序与检索 四、实验项目说明

实验一：顺序表 一、目的：

熟练掌握线性表的基本操作在顺序存储结构上的实现 二、要求：

掌握顺序表的建立、查找、插入、删除等基本操作。 三、示例程序：

四、实验内容

1、 分析、理解程序。

2、 完成插入操作的函数设计。 3、 调试程序：

建立12个元素的顺序表SqList={c,h,i,n,a,w,e,l,c,o,m,e}，分别实现以下操作： 1) 查找元素y在SqList中的位序，输出为O则表示“y不在SqList中”； 2) 在SqList的元素6之前插入一个新元素#，输出插入后的结果； 3) 删除SqList中第8个元素，输出删除后的结果 实验二 单链表 一、目的：

熟练掌握线性表的基本操作在链式存储结构上的实现 二、要求：

掌握单链表的建立、插入、删除等基本操作；

1

三、示例程序： 四、实验内容

1、 分析、理解程序，将void DeleteList(LinkList head,char *key)函数补充完整。 2、 调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测试程序的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。 实验三 栈 一、目的：

掌握栈的基本特点，能把递归算法运用栈转换成非递归算法 二、要求：

掌握顺序栈的建立、入栈、出栈等操作 三、示例程序： 四、实验内容

补充主函数实现：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。 实验四 队列 一、目的：

掌握队列的特点和队列的基本操作 二、要求：

熟练掌握顺序队列的建立、入队、出队等操作。 三、示例程序： 四、实验内容

1、 分析、理解程序。

2、 分析写出主函数的功能

3、 试输入不同的行数调试程序，当行数超过11产生什么问题，为什么。 实验五 二叉树的遍历 一、目的：

掌握二叉树的存储结构和遍历（递归和非递归） 二、要求：

用递归算法实现二叉树的遍历 三、示例程序： 四、实验内容

1、 分析、理解程序。

2、 设计输入一棵树，看程序运行结果与自己计算的遍历顺序是否一致。 3、 输入先序遍历为12435786 的一棵树，调试程序 实验六 查找 一、目的：

掌握基本的查找算法，能够分析比较各算法。 二、要求：

掌握静态查找中顺序查找和折半查找的思想和算法实现 三、实验内容

数组st[N]={77, 111, 213, 222, 300, 400, 555, 632, 987,1024}，编写有序线性表的折半查找算法实现给定元素的查找。

实验七 数据的排序与检索

2

一、目的：

掌握数据结构中的几种常用排序方法：插入排序、快速排序、选择排序等。

二、要求：

遇到实际问题能够选择适当的排序方法解决。

三、实验内容

给定的数组list[N]={213, 111, 222, 77, 400, 300, 987, 1024, 632, 555}，试分别用直接插入排序、冒泡排序、快速排序对上述数据进行排序。

要求：每种排序算法编写为独立的自定义函数且要求输出每趟排序后的数据排列序列情况。

五、实验考核

结合平时实验过程中的程序调试、实验报告，期末进行上机考试，实验成绩占课程总成绩的20%。

执笔人： 叶茂枝 审定人：

院（系）负责人：

3