曲阜师范大学：电子信息工程专业《数据结构》课程教学大纲

数据结构”课程教学大纲教研室主任：黄勇坚执笔人：狄振强一、课程基本信息开课单位：物理工程学院课程名称：数据结构课程编号：07201311英文名称：data structure课程类型：专业基础课总学时：70理论学时：54实验学时：16学分：3开设专业：电子信息工程通信工程物联网先修课程：C语言程序设计二、课程任务目标（一）课程任务数据结构是计算机及应用专业中一门重要的专业基础课程，在计算机软件的各个领域中均会使用到数据结构的有关知识。当用计算机来解决实际问题时，就要涉及到数据的表示及数据的处理而数据表示及数据处理正是数据结构课程的主要研究对象，数据结构课程在计算机应用专业中具有举足轻重的作用。本课程的任务是：在基础方面，要求学员掌握常用数据结构的基本概念及其不同的实现方法；在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。总言之，使应用者较全面的掌握各种常用的数据结构，提高运用数据结构解决实际问题的能力。（二）课程目标在学完本课程之后，学生能够：1.掌握常用数据结构的基本概念；2.掌握用C语言处理顺序表、栈、队列、单链表、双链表等等抽象数据类型的实现方法；3.掌握树型结构、图状结构等等的概念及处理方法，掌握用C语言实现的具体方法；4.在掌握数据结构基本知识的基础上，提高运用数据结构解决实际问题的能力。三、教学内容和要求（一）理论教学的内容及要求

“数据结构”课程教学大纲 教研室主任： 黄勇坚 执笔人：狄振强 一、课程基本信息 开课单位：物理工程学院 课程名称：数据结构 课程编号：07201311 英文名称：data structure 课程类型：专业基础课 总 学 时：70 理论学时：54 实验学时： 16 学 分：3 开设专业：电子信息工程 通信工程 物联网 先修课程：C 语言程序设计 二、课程任务目标 （一）课程任务 数据结构是计算机及应用专业中一门重要的专业基础课程，在计算机软件的各个领域中均会使 用到数据结构的有关知识。当用计算机来解决实际问题时，就要涉及到数据的表示及数据的处理， 而数据表示及数据处理正是数据结构课程的主要研究对象，数据结构课程在计算机应用专业中具有 举足轻重的作用。本课程的任务是：在基础方面，要求学员掌握常用数据结构的基本概念及其不同 的实现方法；在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的 方式和技巧有所体会。总言之，使应用者较全面的掌握各种常用的数据结构，提高运用数据结构解 决实际问题的能力。 （二）课程目标 在学完本课程之后，学生能够： 1. 掌握常用数据结构的基本概念； 2.掌握用 C 语言处理顺序表、栈、队列、单链表、双链表等等抽象数据类型的实现方法； 3.掌握树型结构、图状结构等等的概念及处理方法，掌握用 C 语言实现的具体方法； 4.在掌握数据结构基本知识的基础上，提高运用数据结构解决实际问题的能力。 三、教学内容和要求 （一）理论教学的内容及要求

第一章概论第一节数据结构1、了解数据结构中常用的基本概念和术语以及学习数据结构的意义，了解各种基本概念和术语，掌握算法描述和分析的方法。2、了解数据结构的逻辑结构、存储结构及数据的运算三方面的要领及相互关系。第二节抽象数据类型1、了解数据、数据元素、数据项、数据结构等基本概念。数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。数据的两大类逻辑结构和四种常用的存储表示方法。2、了解数据结构在各种软件系统中所起的作用。选择合适的数据是解决应用问题的关键步骤。第三节1、了解算法、算法的时间复杂度和空间复杂度、最坏的和平均的时间复杂度等概念2、掌握算法描述和算法复杂度的分析方法，对于一般算法能分析出时间复杂度。第二章线性表第一节线性表1、了解线性表的逻辑结构和各种存储表示方法。2、掌握定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。第二节顺序表1、了解顺序表的含义及特点，即顺序表如何反映线性表中元素之间的逻辑关系。2、掌握顺序表上的插入删除操作及其平均时间性能分析。3、掌握利用顺序表设计算法解决简单的应用问题。第三章栈和队列第一节栈1、了解栈的逻辑结构特点，栈与线性表的异同。2、掌握顺序栈的实现，及进栈、退栈等基本算法。3、掌握栈的"上溢"和"下溢"的概念及其判别条件，掌握利用栈设计算法解决简单的应用问题。第二节队列1、了解队列的逻辑结构特点，队列与线性表的异同。2、掌握顺序队列实现的入队、出队等基本算法，掌握队列的"上溢"和"下溢"的概念及其判别条件。3、掌握循环队列上实现的入队、出队等基本算法。4、掌握使用数组实现的循环队列取代普通的顺序队列的方法，掌握循环队列中对边界条件的处理方法。5、掌握利用队列设计算法解决简单的应用问题。第四章线性表的链式存储第一节链式存储1、了解链式存储的概念。2、了解顺序表、栈、队列等链式存储的形式。第二节单链表1、了解单链表的基本概念与描述。2、了解单链表表示线性表中元素之间的逻辑关系。3、掌握单链表上实现的建表、查找、插入和删除等基本算法。第三节带头结点的单链表1、了解引入带头结点单链表的原因

第一章 概论 第一节 数据结构 1、了解数据结构中常用的基本概念和术语以及学习数据结构的意义，了解各种基本概念和术语， 掌握算法描述和分析的方法。 2、了解数据结构的逻辑结构、存储结构及数据的运算三方面的要领及相互关系。 第二节 抽象数据类型 1、了解数据、数据元素、数据项、数据结构等基本概念。数据结构的逻辑结构、存储结构及数 据运算的含义及其相互关系。数据的两大类逻辑结构和四种常用的存储表示方法。 2、了解数据结构在各种软件系统中所起的作用。选择合适的数据是解决应用问题的关键步骤。 第三节 1、了解算法、算法的时间复杂度和空间复杂度、最坏的和平均的时间复杂度等概念。 2、掌握算法描述和算法复杂度的分析方法，对于一般算法能分析出时间复杂度。 第二章 线性表 第一节 线性表 1、了解线性表的逻辑结构和各种存储表示方法。 2、掌握定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。 第二节 顺序表 1、了解顺序表的含义及特点，即顺序表如何反映线性表中元素之间的逻辑关系。 2、掌握顺序表上的插入删除操作及其平均时间性能分析。 3、掌握利用顺序表设计算法解决简单的应用问题。 第三章 栈和队列 第一节 栈 1、了解栈的逻辑结构特点，栈与线性表的异同。 2、掌握顺序栈的实现，及进栈、退栈等基本算法。 3、掌握栈的"上溢"和"下溢"的概念及其判别条件，掌握利用栈设计算法解决简单的应用问题。 第二节 队列 1、了解队列的逻辑结构特点，队列与线性表的异同。 2、掌握顺序队列实现的入队、出队等基本算法，掌握队列的"上溢"和"下溢"的概念及其判别条 件。 3、掌握循环队列上实现的入队、出队等基本算法。 4、掌握使用数组实现的循环队列取代普通的顺序队列的方法，掌握循环队列中对边界条件的处 理方法。 5、掌握利用队列设计算法解决简单的应用问题。 第四章 线性表的链式存储 第一节 链式存储 1、了解链式存储的概念。 2、了解顺序表、栈、队列等链式存储的形式。 第二节 单链表 1、了解单链表的基本概念与描述。 2、了解单链表表示线性表中元素之间的逻辑关系。 3、掌握单链表上实现的建表、查找、插入和删除等基本算法。 第三节 带头结点的单链表 1、了解引入带头结点单链表的原因

2、了解带头结点单链表的组成结构。3、掌握单链表上实现建表、查找、插入和删除等基本算法。第四节循环单链表1、了解循环单链表的组成结构。2、掌握循环单链表上实现建表、查找、插入和删除等基本算法。第五节双链表1、了解双链表的基本概念与描述。2、了解双链表表示线性表中元素之间的逻辑关系。3、掌握双链表上实现的建表、查找、插入和删除等基本算法。第六节链式栈1、了解链式栈与顺序栈的异同点。2、掌握链式栈的组成结构与描述形式。3、掌握链式栈的实现算法。第七节链式队列1、了解链式队列与顺序队列的异同点。2、掌握链式队列的组成结构与描述形式。3、掌握链式队列的实现算法。第五章串、数组和广义表第一节串1、了解串的有关概念及基本运算，了解串与线性表的关系。2、掌握串的两种存储表示，掌握使用C语言提供的串操作函数构造与串相关的算法解决简单的应用问题。第二节数组和广义表1、了解多维数组的逻辑结构特征，多维数组的顺序存储结构及地址计算方式。2、了解特殊矩阵和稀疏矩阵的概念，了解特殊矩阵和压缩存储时的下标变换方法，以及稀疏矩阵的三元组表表示方法及有关算法。3、了解产义表的有关概念及其与线性表的关系，了解广义表的括号表示和图形表示之间的转换。了解求给定的非空广义表的表头和表尾运算。第六章树第一节树的概念1、了解树的概念及相关术语。2、了解树的定义形式。第二节树的存储形式1、了解与掌握双亲表示法。2、了解与掌握孩子表示法。3、了解与掌握孩子兄弟表示法。第三节树的遍历1、了解树的遍历概念。2、掌握树的遍历的实现算法。第七章二叉树第一节二叉树概念1、了解二叉树的基本概念。2、了解二叉树的基本运算

2、了解带头结点单链表的组成结构。 3、掌握单链表上实现建表、查找、插入和删除等基本算法。 第四节 循环单链表 1、了解循环单链表的组成结构。 2、掌握循环单链表上实现建表、查找、插入和删除等基本算法。 第五节 双链表 1、了解双链表的基本概念与描述。 2、了解双链表表示线性表中元素之间的逻辑关系。 3、掌握双链表上实现的建表、查找、插入和删除等基本算法。 第六节 链式栈 1、了解链式栈与顺序栈的异同点。 2、掌握链式栈的组成结构与描述形式。 3、掌握链式栈的实现算法。 第七节 链式队列 1、了解链式队列与顺序队列的异同点。 2、掌握链式队列的组成结构与描述形式。 3、掌握链式队列的实现算法。 第五章 串、数组和广义表 第一节 串 1、了解串的有关概念及基本运算，了解串与线性表的关系。 2、掌握串的两种存储表示，掌握使用 C 语言提供的串操作函数构造与串相关的算法解决简单的 应用问题。 第二节 数组和广义表 1、了解多维数组的逻辑结构特征，多维数组的顺序存储结构及地址计算方式。 2、了解特殊矩阵和稀疏矩阵的概念，了解特殊矩阵和压缩存储时的下标变换方法，以及稀疏矩 阵的三元组表表示方法及有关算法。 3、了解广义表的有关概念及其与线性表的关系，了解广义表的括号表示和图形表示之间的转换。 了解求给定的非空广义表的表头和表尾运算。 第六章 树 第一节 树的概念 1、了解树的概念及相关术语。 2、了解树的定义形式。 第二节 树的存储形式 1、了解与掌握双亲表示法。 2、了解与掌握孩子表示法。 3、了解与掌握孩子兄弟表示法。 第三节 树的遍历 1、了解树的遍历概念。 2、掌握树的遍历的实现算法。 第七章 二叉树 第一节 二叉树概念 1、了解二叉树的基本概念。 2、了解二叉树的基本运算

第二节二叉树的存储结构1、掌握二叉树的顺序存储结构。2、掌握二叉树的链式存储结构。第三节二叉树的遍历1、了解二叉树遍历的定义2、掌握二叉树遍历的递归实现算法。3、掌握二叉树遍历的非递归实现算法。第四节穿线二叉树1、了解穿线二叉树的概念。2、了解穿线二叉树的基本运算。第五节树、森林和二叉树的转换1、掌握树、森林到二叉树的转换2、掌握二叉树到树、森林的转换第八章图第一节图的基本概念与运算1、了解图的基本概念。2、了解与掌握图的基本运算第二节图的遍历1、了解图的遍历算法。2、理解图的遍历算法的实现方法。第三节生成树与最小生成树1、了解生成树、最小生成树概念。2、理解图在该方面的算法应用。第九章排序与查找第一节排序1、了解排序概念。2、了解几种排序算法。第二节查找1、了解查找、检索的基本概念2、了解几种检索算法。（二）实践教学的内容及要求1、顺序表建立与输出实验了解与掌握顺序表的定义及其建立输出等操作算法的实现方法。2、顺序表的插入删除实验了解与掌握顺序表的插入、删除等操作算法的实现方法。3、栈操作实验了解与掌握栈的建立、插入、删除、输出等算法的实现方法。4、栈的应用括号匹配实验了解与掌握栈在括号匹配中的应用算法的实现方法。5、队列定义及其操作算法的实现了解与掌握队列的建立以及队列的插入、删除、输出等算法的实现方法。6、单链表实验

第二节 二叉树的存储结构 1、掌握二叉树的顺序存储结构。 2、掌握二叉树的链式存储结构。 第三节 二叉树的遍历 1、了解二叉树遍历的定义 2、掌握二叉树遍历的递归实现算法。 3、掌握二叉树遍历的非递归实现算法。 第四节 穿线二叉树 1、了解穿线二叉树的概念。 2、了解穿线二叉树的基本运算。 第五节 树、森林和二叉树的转换 1、掌握树、森林到二叉树的转换 2、掌握二叉树到树、森林的转换 第八章 图 第一节 图的基本概念与运算 1、了解图的基本概念。 2、了解与掌握图的基本运算 第二节 图的遍历 1、了解图的遍历算法。 2、理解图的遍历算法的实现方法。 第三节 生成树与最小生成树 1、了解生成树、最小生成树概念。 2、理解图在该方面的算法应用。 第九章 排序与查找 第一节 排序 1、了解排序概念。 2、了解几种排序算法。 第二节 查找 1、了解查找、检索的基本概念 2、了解几种检索算法。 （二）实践教学的内容及要求 1、顺序表建立与输出实验 了解与掌握顺序表的定义及其建立输出等操作算法的实现方法。 2、顺序表的插入删除实验 了解与掌握顺序表的插入、删除等操作算法的实现方法。 3、栈操作实验 了解与掌握栈的建立、插入、删除、输出等算法的实现方法。 4、栈的应用括号匹配实验 了解与掌握栈在括号匹配中的应用算法的实现方法。 5、队列定义及其操作算法的实现 了解与掌握队列的建立以及队列的插入、删除、输出等算法的实现方法。 6、单链表实验

了解与掌握单链表的定义及其插入、输出等相关算法的实现方法。7、循环单链表实验了解与掌握循环单链表的定义及其查找、删除等相关算法的实现方法。8、双链表实验了解与掌握双链表的定义及其插入、删除等相关算法的实现：四、学时分配各教学环节学时分配小上习讨课章次讲实备注计外授验机题论第一章概论（概念、抽象数据类型、66算法）6第二章线性表14881828第三章栈和队列1010第四章线性表的链式存储44第五章串、数组和广义表66第六章树682第七章二叉树22第八章：图22第九章：排序与查找合计705016五、考核说明本课程为考试课程。其中，期中成绩占10%，期末成绩50%，实验成绩30%，作业等平时成绩10%六、主要教材及教学参考书目（一）主要教材1.《数据结构（C语言版）》李云清杨庆红揭安全编著人民邮电出版社2013（二）主要参考书目1.《数据结构---用C语言描述》唐策善、李龙澍、黄刘生高等教育出版社1995

了解与掌握单链表的定义及其插入、输出等相关算法的实现方法。 7、循环单链表实验 了解与掌握循环单链表的定义及其查找、删除等相关算法的实现方法。 8、双链表实验 了解与掌握双链表的定义及其插入、删除等相关算法的实现； 四、学时分配 章 次 各教学环节学时分配 小 计 讲 授 实 验 上 机 习 题 讨 论 课 外 备 注 第一章 概论（概念、抽象数据类型、 算法） 6 6 第二章 线性表 14 6 8 第三章 栈和队列 18 8 8 2 第四章 线性表的链式存储 10 10 第五章 串、数组和广义表 4 4 第六章 树 6 6 第七章 二叉树 8 6 2 第八章：图 2 2 第九章：排序与查找 2 2 合 计 70 50 16 4 五、考核说明 本课程为考试课程。其中，期中成绩占 10%，期末成绩 50%，实验成绩 30%，作业等 平时成绩 10% 六、主要教材及教学参考书目 （一）主要教材 1.《数据结构（C 语言版）》 李云清 杨庆红 揭安全编著 人民邮电出版社 2013 （二）主要参考书目 1.《数据结构-用 C 语言描述》 唐策善、李龙澍、黄刘生 高等教育出版社 1995

严蔚敏、吴伟民清华大学出版社19972.《数据结构（C语言版）》

2.《数据结构（C 语言版）》 严蔚敏、吴伟民 清华大学出版社 1997