《数据结构实验》教学大纲.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合并成一个按元素值递增的有序单链表Leo7 .成绩评定指导教师根据实验态度、操作技能和实验报告完成的情况综合评定成绩。成绩的评定分 为五个级别，按时进行实验，态度认真，基本知识扎实，操作技能娴熟，能在实验课时内完 成实验，实验报告正规、工整的学生评为优秀；缺席两次以上实验，态度不认真，基本知识 未掌握，无法完成实验，缺交实验报告的学生评为不及格，中间再分良好、中等、及格三个 级别。实验工程三：栈和队列实验（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张乃孝.数据结构与算法学习辅导及习题详解.（第一版）.北京：电子工业 出版社，20042严蔚敏吴伟民.数据结构题集（C语言版）.北京：清华大学出版社，1999七、课程学时分配表序号实验工程名称学时实验属性修读性质主要仪器设备实验工程1C语言基础1学时设计性实验选开计算机实验工程2线性表的抽象 数据类型的实 现3学时验证性实验必开计算机实验工程3栈和队列实验2学时验证性实验必开计算机实验工程4数组实验2学时验证性实验必开计算机实验工程5树和二叉树实 验3学时验证性实验必开计算机实验工程6图的实验2学时验证性实验必开计算机实验工程7查找表实验2学时设计性实验必开计算机实验工程8内部排序实验2学时设计性实验必开计算机