《数据结构实验》教学大纲.docx

《数据结构实验》大纲
一、课程基本信息
中文名称
数据结构实验
英文名称
Data Structure Test
适用专业
物联网工程
先修课程
C程序设计
课程类别
专业核心课
修读性质
必修
学分/学时
1学分/17学时
考核方式
考查
二、教学目标
本课程是为物联网工程专业的本科生开设的学科基础课程之一，学习本课程能使学生掌 握数据在计算机中的表示、存储和处理。为以后学习编译程序、操作系统、数据库系统打下 基础。掌握常用的数据结构及内在的逻辑关系，计算机软件设计中的算法知识。提高软件设 计和编程技能。学会初步对不同的存储结构和相应算法的比照，有一定的算法改进能力。
三、教学内容实验工程一：C语言基础(1学时)
1 .实验属性：设计实验
2,修读性质：选开
3 .教学目标(1)通过实验进一步掌握指针的概念，会定义和使用指针变量；(2)掌握结构体类型变量的定义和使用；(3)掌握malloc> calloc和free函数的使用
4 .实验方法
上机操作
5实验仪器设备
装有C语言环境的计算机
6 .实验内容
(1)用指针处理字符串。输入一行文字，找出其中大写字母、小写字母、空格、数字 及其他字符各有多少。
(2)用指针做形参。写一个函数，将此字符串中从第m个字符开始的全部字符复制成 为另一个字符串。
(3)结构体的使用。设计一个学生综合考评排序程序。设每名学生包含姓名、学号、 年级和综合考评成绩四项数据，要求键盘输入上述各项数据，按成绩的高低排序输出。
7 .成绩评定
指导教师根据实验态度、操作技能和实验报告完成的情况综合评定成绩。成绩的评定分 为五个级别，按时进行实验，态度认真，基本知识扎实，操作技能娴熟，能在实验课时内完 成实验，实验报告正规、工整的学生评为优秀；缺席两次以上实验，态度不认真，基本知识 未掌握，无法完成实验，缺交实验报告的学生评为不及格，中间再分良好、中等、及格三个 级别。
实验工程二：线性表的抽象数据类型的实现（3学时）
1 .实验属性：验证实验
2,修读性质：必开
3 .教学目标（1）掌握线性表的顺序存储结构的定义及C语言实现。
（2）掌握线性表在顺序存储结构即顺序表中的各种基本操作。
（3）掌握线性表的链式存储结构一一单链表的定义及C语言实现。
（4）掌握线性表在链式存储结构一一单链表中的各种基本操作。
4 .实验方法
上机操作
5实验仪器设备
装有C语言环境的计算机
6 .实验内容
（1）顺序表的建立：建立一个含n个数据元素的顺序表并输出该表中各元素的值及顺 序表的长度。
（2）顺序表的插入：利用前面的实验先建立一个顺序表L={21, 23, 14, 5, 56, 17, 31）,然后在第i个位置插入元素68,通过比照插入元素前后的线性表发生的变化，判断插 入操作是否正确。
（3）单链表的建立：建立一个带头结点的单链表，结点的值域为整型数据。要求将用 户输入的数据按尾插入法来建立相应单链表。
（4）单链表的合并：建立两个带头结点的有序单链表La, Lb （单调递增），利用La,Lb 的结点空间，将La和Lb合并成一个按元素值递增的有序单链表Leo
7 .成绩评定
指导教师根据实验态度、操作技能和实验报告完成的情况综合评定成绩。成绩的评定分 为五个级别，按时进行实验，态度认真，基本知识扎实，操作技能娴熟，能在实验课时内完 成实验，实验报告正规、工整的学生评为优秀；缺席两次以上实验，态度不认真，基本知识 未掌握，无法完成实验，缺交实验报告的学生评为不及格，中间再分良好、中等、及格三个 级别。
实验工程三：栈和队列实验（2学时）
1 .实验属性：验证实验
2,修读性质：必开
3 .教学目标
（1）熟悉栈的特点（先进后出）及栈的基本操作，如入栈、出栈等，掌握栈的基本操 作在栈的顺序存储结构和链式存储结构上的实现；
（2）熟悉队列的特点（先进先出）及队列的基本操作，如入队、出队等，掌握队列的 基本操作在队列的顺序存储结构和链式存储结构上的实现。
4 .实验方法
上机操作
5实验仪器设备
装有C语言环境的计算机
6 .实验内容
（1）栈的顺序表示和实现：编写一个程序实现顺序栈的各种基本运算，并在此基础上 设计一个主程序，完成如下功能：初始化顺序栈、插入元素、删除栈顶元素、取栈顶元素、遍历顺序栈、置空顺序栈
（2）队列的顺序表示和实现：编写一个程序实现顺序队列的各种基本运算，并在此基 础上设计一个主程序，完成如下功能：初始化队列、建立顺序队列、入队、出队、判断队列 是否为空、取队头元素、遍历队列
7 .成绩评定
指导教师根据实验态度、操作技能和实验报告完成的情况综合评定成绩。成绩的评定分 为五个级别，按时进行实验，态度认真，基本知识扎实，操作技能娴熟，能在实验课时内完 成实验，实验报告正规、工整的学生评为优秀；缺席两次以上实验，态度不认真，基本知识 未掌握，无法完成实验，缺交实验报告的学生评为不及格，中间再分良好、中等、及格三个 级别。
实验工程四：数组实验（2学时）
L实验属性：验证实验
2,修读性质：必开
8 .教学目标（1）熟悉和掌握数组结构的实际应用，特别是多维数组的存储；（2）熟悉和掌握稀疏矩阵的存储及其应用。
9 .实验方法
上机操作
5实验仪器设备
装有C语言环境的计算机
6,实验内容
实现稀疏矩阵（采用三元组表示）的基本运算：假设nXn的稀疏矩阵a和b采用三元组 表示，编写一个程序实现如下功能：
a）生成两个稀疏矩阵的三元组a和b.。
b）输出a转置矩阵的三元组。
c）输出a+b的三元组。
d）输出aXb的三元组。
10 成绩评定
指导教师根据实验态度、操作技能和实验报告完成的情况综合评定成绩。成绩的评定分 为五个级别，按时进行实验，态度认真，基本知识扎实，操作技能娴熟，能在实验课时内完 成实验，实验报告正规、工整的学生评为优秀；缺席两次以上实验，态度不认真，基本知识 未掌握，无法完成实验，缺交实验报告的学生评为不及格，中间再分良好、中等、及格三个 级别。
实验工程五：树与二叉树实验（3学时）
L实验属性：验证实验
2,修读性质：必开
11 教学目标（1）掌握二叉树链表的结构和二叉树的建立过程；
（2）掌握二叉树的基本操作，加深对二叉树的理解，逐步培养解决实际问题的编程能 力。
12 实验方法
上机操作
5实验仪器设备
装有C语言环境的计算机
6,实验内容（1）二叉树的构造：按先序序列构造一k棵二叉链表表示的二叉树T；
（2）二叉树的遍历：对一棵二叉链表表示的二叉树进行先序遍历、中序遍历、后序遍 历和层序遍历并分别输出遍历的结点顺序。
13 成绩评定
指导教师根据实验态度、操作技能和实验报告完成的情况综合评定成绩。成绩的评定分 为五个级别，按时进行实验，态度认真，基本知识扎实，操作技能娴熟，能在实验课时内完 成实验，实验报告正规、工整的学生评为优秀；缺席两次以上实验，态度不认真，基本知识 未掌握，无法完成实验，缺交实验报告的学生评为不及格，中间再分良好、中等、及格三个 级别。
实验工程六：图实验（2学时）
1 .实验属性：验证实验
2,修读性质：必开
3 .教学目标（1）熟悉图的邻接矩阵、邻接表的表示；（2）掌握建立图的邻接矩阵和邻接表的算法；（3）熟悉对图的邻接矩阵和邻接表表示分别进行深度和广度优先搜索遍历的算法。
4 .实验方法
上机操作
5实验仪器设备
装有C语言环境的计算机
6 .实验内容
建立以邻接矩阵结构存储的图，并对其进行深度优先搜索遍历。
7 .成绩评定
指导教师根据实验态度、操作技能和实验报告完成的情况综合评定成绩。成绩的评定分 为五个级别，按时进行实验，态度认真，基本知识扎实，操作技能娴熟，能在实验课时内完 成实验，实验报告正规、工整的学生评为优秀；缺席两次以上实验，态度不认真，基本知识 未掌握，无法完成实验，缺交实验报告的学生评为不及格，中间再分良好、中等、及格三个 级别。
实验工程七：查找表实验（2学时）
L实验属性：设计实验
8 .修读性质：必开
9 .教学目标（1）掌握静态查找表算法（重点掌握折半查找）；（2）熟悉理解动态查找表二叉排序树查找算法及哈希表查找算法；（3）学会分析各种查找算法的性能。
10 实验方法
上机操作
5实验仪器设备
装有C语言环境的计算机
11 实验内容
编写一个程序，实现对顺序表｛2, 4, 6, 8, 10, 12, 14, 16）进行折半查找关键字
14的过程。
12 成绩评定
指导教师根据实验态度、操作技能和实验报告完成的情况综合评定成绩。成绩的评定分 为五个级别，按时进行实验，态度认真，基本知识扎实，操作技能娴熟，能在实验课时内完 成实验，实验报告正规、工整的学生评为优秀；缺席两次以上实验，态度不认真，基本知识 未掌握，无法完成实验，缺交实验报告的学生评为不及格，中间再分良好、中等、及格三个 级别。
实验工程八：内部排序实验（2学时）
1 .实验属性：设计实验2,修读性质：必开.教学目标（1）熟悉掌握各种排序方法，深刻理解排序算法及其执行的过程；
（2）学会分析各种排序算法的性能；了解各种方法的优缺点，对于实际问题能够选择一种较好的排序方案。
3 .实验方法上机操作5实验仪器设备装有C语言环境的计算机
6 .实验内容
编写一个程序实现直接插入排序过程，并输出｛9, 8, 7, 6, 5, 4, 3, 2, 1, 0）的排 序过程。
7 .成绩评定
指导教师根据实验态度、操作技能和实验报告完成的情况综合评定成绩。成绩的评定分 为五个级别，按时进行实验，态度认真，基本知识扎实，操作技能娴熟，能在实验课时内完 成实验，实验报告正规、工整的学生评为优秀；缺席两次以上实验，态度不认真，基本知识 未掌握，无法完成实验，缺交实验报告的学生评为不及格，中间再分良好、中等、及格三个 级别。
四'考核形式及成绩评定（一）考核形式：
根据实验态度、操作技能和实验报告完成的情况综合考核。
（-）成绩评定：
成绩的评定分为五个级别，按时进行实验，态度认真，基本知识扎实，操作技能娴熟, 能在实验课时内完成实验，实验报告正规、工整的学生评为优秀；缺席两次以上实验，态度 不认真，基本知识未掌握，无法完成实验，缺交实验报告的学生评为不及格，中间再分良好、 中等、及格三个级别。
五' 教材与参考书教材：严蔚敏,数据结构（C语言）.（第三版）,北京：清华大学出版社，2007
参考书：［1］张乃孝.数据结构与算法学习辅导及习题详解.（第一版）.北京：电子工业 出版社，2004［2］严蔚敏吴伟民.数据结构题集（C语言版）.北京：清华大学出版社，1999七、课程学时分配表
序号
实验工程名称
学时
实验属性
修读性质
主要仪器设备
实验工程1
C语言基础
1学时
设计性实验
选开
计算机
实验工程2
线性表的抽象 数据类型的实 现
3学时
验证性实验
必开
计算机
实验工程3
栈和队列实验
2学时
验证性实验
必开
计算机
实验工程4
数组实验
2学时
验证性实验
必开
计算机
实验工程5
树和二叉树实 验
3学时
验证性实验
必开
计算机
实验工程6
图的实验
2学时
验证性实验
必开
计算机
实验工程7
查找表实验
2学时
设计性实验
必开
计算机
实验工程8
内部排序实验
2学时
设计性实验
必开
计算机