《数据结构》课程教学大纲 《Data Structure.》course teaching program 一、课程基本信息 课程代码：16162804 课程名称：数据结构 英文名称：Data Structure 课程类别：学科基础课 学 时：64（其中实验学时10》 学 分：4 适用对象：计算机科学与技术、软件工程、大数据与管理专业教学班 考核方式：考试 先修课程：程序设计、离散数学 二、课程简介 本课程是面向计算机科学与技术、软件工程、信息管理与信息系统本科专业的一门 学科基础课。该课程为操作系统、数据库原理、算法设计与分析等后续课程奠定基础。 通过本课程的学习，使学生熟练地掌握常用数据结构的基本概念、逻辑结构、存储结构 及相关算法的设计：学握这些数据结构在计算机科学与技术中的基本应用。本课程主要 内容包括：线性结构（含线性表、栈和队列、串）、树结构、图结构、排序算法和查找 算法等，并学习、掌握各种基本算法时间复杂性和空间复杂性的分析技术。通过这两方 面内容的学习，为后续课程，特别是软件方面的课程打下了厚实的知识基础。数据结构 课程在计算机科学与技术、软件工程等专业中具有举足轻重的作用， 本课程在讲解的过程中，结合教学内容联系我国相关软件的现状和差距，受制于人 的不甘，不失时机地激发学生沉下心来做实事，立志专业报国，树立起昂扬向上的精神 风貌：在讲解算法思想的过程中，联系《孙子兵法》、中华围棋棋理等等，注重渗透中 华文化的思想。既上学生感受到中华文化的博大清深，领悟其思想精萄，从而真正爱上 中华文化；也透过中华文化的有关思想让学生更容易理解相关算法。 (Data Structure is a elementary course for majors of Computer Science&Technology. software engineering.information management information system and E business.It's a basic foundation for the following courses such as Operating System,Database Theorem and Algorithm Design&Analysis.By the learning of this course,students will learn the basic concepts,the logical structure,the storage structure and correspondently algorithm design in order to advance the abilities of applying the learned techniques to solve the practical problems.The main contents of this course are:List Structure(including List,Stack and
1 《数据结构》课程教学大纲 《Data Structure》course teaching program 一、课程基本信息 课程代码：16162804 课程名称：数据结构 英文名称：Data Structure 课程类别：学科基础课 学 时：64（其中实验学时 10） 学 分：4 适用对象：计算机科学与技术、软件工程、大数据与管理专业教学班 考核方式：考试 先修课程：程序设计、离散数学 二、课程简介 本课程是面向计算机科学与技术、软件工程、信息管理与信息系统本科专业的一门 学科基础课。该课程为操作系统、数据库原理、算法设计与分析等后续课程奠定基础。 通过本课程的学习，使学生熟练地掌握常用数据结构的基本概念、逻辑结构、存储结构 及相关算法的设计；掌握这些数据结构在计算机科学与技术中的基本应用。本课程主要 内容包括：线性结构（含线性表、栈和队列、串）、树结构、图结构、排序算法和查找 算法等，并学习、掌握各种基本算法时间复杂性和空间复杂性的分析技术。通过这两方 面内容的学习，为后续课程，特别是软件方面的课程打下了厚实的知识基础。数据结构 课程在计算机科学与技术、软件工程等专业中具有举足轻重的作用。 本课程在讲解的过程中，结合教学内容联系我国相关软件的现状和差距，受制于人 的不甘，不失时机地激发学生沉下心来做实事，立志专业报国，树立起昂扬向上的精神 风貌；在讲解算法思想的过程中，联系《孙子兵法》、中华围棋棋理等等，注重渗透中 华文化的思想。既让学生感受到中华文化的博大精深，领悟其思想精髓，从而真正爱上 中华文化；也透过中华文化的有关思想让学生更容易理解相关算法。 《Data Structure》is a elementary course for majors of Computer Science & Technology, software engineering, information management & information system and E_business. It’s a basic foundation for the following courses such as Operating System, Database Theorem and Algorithm Design & Analysis. By the learning of this course, students will learn the basic concepts, the logical structure, the storage structure and correspondently algorithm design in order to advance the abilities of applying the learned techniques to solve the practical problems. The main contents of this course are: List Structure(including List, Stack and
Queue,String).Tree Structure,Graph Structure,Sorting and Searching Algorithms,and the analysis techniques of Time&Space complexity.After learning the course,students will have a very solid knowledge base for the following courses,especially for courses about the software development.<Data Structure is a very important course for the major of Computer Science Technology. 三、课程性质与教学目的 本课程是面向计算机科学与技术、软件工程、信息管理与信息系统、电子商务本科 专业的一门学科基础课。是计算机程序设计的重要理论技术基础。 《数据结构》课程使学生学会分析研究计算机加工的数据结构的特性，以使为应用 涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分 析和空间的技术。 本课程的学习过程也是复杂程序设计的训练过程，使学生学会编写程序结构清楚和 正确易读、符合软件工程规范的程序。《数据结构》课程培养学生的数据抽象能力。通 过本课程的学习，学生应当能够应用所学的知识，应具有分析、设计算法的能力，以解 决实际问题，为其它后续的专业课程的学习打下坚实的基础，并极大地提高软件设计的 能力。 另一方面，本课程在讲解的过程中，结合教学内容联系我国相关软件的现状和差距， 受制于人的不甘，不失时机地激发学生沉下心来做实事，立志专业报国，树立起昂扬向 上的精神风貌；在讲解算法思想的过程中，联系《孙子兵法》、中华围棋棋理等等，注 重渗透中华文化的思想。既让学生感受到中华文化的博大精深，领悟其思想精髓，从而 真正爱上中华文化；也透过中华文化的有关思想让学生更容易理解相关算法。 四、教学内容及要求 第一章绪论 (一)目的与要求 1,掌握数据结构与算法的基本概念：数据、类型、数据结构（逻辑结构和存储结 构)，理解数据、数据元素和数据项的概念及其相互间的关系。清楚数据结构的逻辑结 构、存储结构的联系与区别以及在数据结构上施加的运算及其实现。要求达到“理解” 的层次： 2.掌握算法的定义及其五个要素的确切含义、描述、算法设计的要求及初步分析， 要求达到“认识”的层次： 3.掌握数据结构与算法的类C语言描述，熟悉类C语言的书写规范，特别要注意 值调用和引用调用的区别，输入、输出的方式以及错误处理方式，要求达到“理解”的 层次。 4.初步了解计算语句频度和估算算法时间复杂度的方法
2 Queue, String), Tree Structure, Graph Structure, Sorting and Searching Algorithms, and the analysis techniques of Time & Space complexity. After learning the course, students will have a very solid knowledge base for the following courses, especially for courses about the software development.《Data Structure》is a very important course for the major of Computer Science & Technology. 三、课程性质与教学目的 本课程是面向计算机科学与技术、软件工程、信息管理与信息系统、电子商务本科 专业的一门学科基础课。是计算机程序设计的重要理论技术基础。 《数据结构》课程使学生学会分析研究计算机加工的数据结构的特性，以使为应用 涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分 析和空间的技术。 本课程的学习过程也是复杂程序设计的训练过程，使学生学会编写程序结构清楚和 正确易读、符合软件工程规范的程序。《数据结构》课程培养学生的数据抽象能力。通 过本课程的学习，学生应当能够应用所学的知识，应具有分析、设计算法的能力，以解 决实际问题，为其它后续的专业课程的学习打下坚实的基础，并极大地提高软件设计的 能力。 另一方面，本课程在讲解的过程中，结合教学内容联系我国相关软件的现状和差距， 受制于人的不甘，不失时机地激发学生沉下心来做实事，立志专业报国，树立起昂扬向 上的精神风貌；在讲解算法思想的过程中，联系《孙子兵法》、中华围棋棋理等等，注 重渗透中华文化的思想。既让学生感受到中华文化的博大精深，领悟其思想精髓，从而 真正爱上中华文化；也透过中华文化的有关思想让学生更容易理解相关算法。 四、教学内容及要求 第一章 绪论 （一）目的与要求 1．掌握数据结构与算法的基本概念：数据、类型、数据结构（逻辑结构和存储结 构），理解数据、数据元素和数据项的概念及其相互间的关系。清楚数据结构的逻辑结 构、存储结构的联系与区别以及在数据结构上施加的运算及其实现。要求达到“理解” 的层次； 2．掌握算法的定义及其五个要素的确切含义、描述、算法设计的要求及初步分析， 要求达到“认识”的层次； 3．掌握数据结构与算法的类 C 语言描述，熟悉类 C 语言的书写规范，特别要注意 值调用和引用调用的区别，输入、输出的方式以及错误处理方式，要求达到“理解”的 层次。 4．初步了解计算语句频度和估算算法时间复杂度的方法
5.强调本课程对开发系统软件的基础性地位，而我国使用的系统软件几乎都是美 国货，难免受制于人！原因是什么？从而激发学生对本课程的学习热情，树立扎实的工 作作风，提升学生的专业报国的意识。 (二)教学内容 第一节什么是数据结构 1.主要内容 通过实例介绍，使学生了解线性表、栈和队列、树和图等数据结构的具体表现形式， 明确《数据结构》课程在计算机科学与技术学科各主领域中所处的地位，了解《数据结 构》课程内容组织体系架构。 2.基本概念和知识点 A.数据结构模型： B.《数据结构》与程序设计、算法设计与分析的区别与联系； C.《数据结构》与数学、计算机硬件和计算机软件之间的区别与联系。 3.问题与应用 若要为图书馆的书目检索系统自动化问题、计算机和人对奔问题及多叉路口交通灯 的管理等问题设计软件，你该如何思考？ 第二节基本概念和术语 1.主要内容 掌握数据结构所涉及的基本概念：掌握抽象数据类型ADT三元组的定义方法。掌 握顺序存储结构和链式存储结构的特点。存储结构的描述方法。 2.基本概念和知识点 数据、数据元素、数据对象、结点、数据域、指针；数据的逻辑结构和物理结构、 顺序存储结构和链式存储结构、数据类型、抽象数据类型ADT。 3.问题与应用 思考：有一张数据表，若用每一种结构对该表加以管理、操作，则其结点是什么？ 第三节抽象数据类型的表示与实现 1.主要内容 通过类C语言的介绍和学习，使学生掌握用类C语言正确地描述抽象数据类型 元组（数据对象、数据关系、基本操作）。 2
3 5．强调本课程对开发系统软件的基础性地位，而我国使用的系统软件几乎都是美 国货，难免受制于人！原因是什么？从而激发学生对本课程的学习热情，树立扎实的工 作作风，提升学生的专业报国的意识。 （二）教学内容 第一节 什么是数据结构 1．主要内容 通过实例介绍，使学生了解线性表、栈和队列、树和图等数据结构的具体表现形式， 明确《数据结构》课程在计算机科学与技术学科各主领域中所处的地位，了解《数据结 构》课程内容组织体系架构。 2．基本概念和知识点 A. 数据结构模型； B. 《数据结构》与程序设计、算法设计与分析的区别与联系； C. 《数据结构》与数学、计算机硬件和计算机软件之间的区别与联系。 3．问题与应用 若要为图书馆的书目检索系统自动化问题、计算机和人对弈问题及多叉路口交通灯 的管理等问题设计软件，你该如何思考？ 第二节 基本概念和术语 1．主要内容 掌握数据结构所涉及的基本概念；掌握抽象数据类型 ADT 三元组的定义方法。掌 握顺序存储结构和链式存储结构的特点。存储结构的描述方法。 2．基本概念和知识点 数据、数据元素、数据对象、结点、数据域、指针；数据的逻辑结构和物理结构、 顺序存储结构和链式存储结构、数据类型、抽象数据类型 ADT。 3．问题与应用 思考：有一张数据表，若用每一种结构对该表加以管理、操作，则其结点是什么？ 第三节 抽象数据类型的表示与实现 1．主要内容 通过类 C 语言的介绍和学习，使学生掌握用类 C 语言正确地描述抽象数据类型三 元组（数据对象、数据关系、基本操作）
2.基本概念和知识点 类C语言、抽象数据类型三元组的表示和实现。 3.问题与应用 思考：我们在设计算法时，为什么要用类C语言来描述算法，而不用真实的C语 言来描述呢？ 第四节算法和算法分析 1.主要内容 讲解算法的定义和算法的五个重要特性：算法设计的四大要求：算法效率的度量方 法：时间复杂度与空间复杂度。时间复杂度的阶。 2.基本概念和知识点 算法、算法特性、何谓“好”的算法、算法时间复杂性和空间复杂性。 3.问题与应用 通过一些简易程序实例，基本学握算法时间复杂性的分析，并理解时间复杂性的阶 和算法的追求目标。 思考：己知程序源码，如何正确地分析该程序的时间复杂性？己知问题的求解算法， 如何正确地分析该算法的时间复杂性？ (三)思考与实践 思考：计算机语言很熟悉，是否就意味着会程序的设计了呢？为什么？ 实践：求连续整数阶乘的和 练习题：《数据结构(C语言版)》P17第5、6题 (四)教学方法与手段 课堂讲授、多媒体教学。 通过课堂讨论，让学生明确算法与程序的区别。 第二章线性表 (一)目的与要求 1,了解线性表的逻辑结构特性、线性表的抽象类型定义和基本运算，掌握线性结 构的四大特点，要求达到“理解”层次： 2.线性表的存储结构：顺序存储结构和链式存储结构的表示和实现（单链表，双
4 2．基本概念和知识点 类 C 语言、抽象数据类型三元组的表示和实现。 3．问题与应用 思考：我们在设计算法时，为什么要用类 C 语言来描述算法，而不用真实的 C 语 言来描述呢？ 第四节 算法和算法分析 1. 主要内容 讲解算法的定义和算法的五个重要特性；算法设计的四大要求；算法效率的度量方 法：时间复杂度与空间复杂度。时间复杂度的阶。 2. 基本概念和知识点 算法、算法特性、何谓“好”的算法、算法时间复杂性和空间复杂性。 3. 问题与应用 通过一些简易程序实例，基本掌握算法时间复杂性的分析，并理解时间复杂性的阶 和算法的追求目标。 思考：已知程序源码，如何正确地分析该程序的时间复杂性？已知问题的求解算法， 如何正确地分析该算法的时间复杂性？ （三） 思考与实践 思考：计算机语言很熟悉，是否就意味着会程序的设计了呢？为什么？ 实践：求连续整数阶乘的和 练习题：《数据结构（C 语言版）》P17 第 5、6 题 （四）教学方法与手段 课堂讲授、多媒体教学。 通过课堂讨论，让学生明确算法与程序的区别。 第二章 线性表 （一）目的与要求 1．了解线性表的逻辑结构特性、线性表的抽象类型定义和基本运算，掌握线性结 构的四大特点，要求达到“理解”层次； 2．线性表的存储结构：顺序存储结构和链式存储结构的表示和实现（单链表，双
向链表和循环链表)，要求达到“熟练”层次： 3.掌握线性表在顺序存储结构上实现基本操作：查找、插入和删除等的算法，要 求达到“熟练”层次。 4.掌握各种链表结构中实现线性表操作的基本方法，能在实际应用中选的不同特 点及其适用场合，要求达到“熟练”层次。 5.了解静态链表，能够加深对链表本质的理解，要求达到“了解”层次。 6.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其 适用场合 (二)教学内容 第一节线性表的类型定义 1.主要内容 掌握抽象数据类型线性表的定义、线性表的基本操作，通过线性表的归并算法掌握 用类C语言来描述算法的基本技巧。 2.基本概念和知识点 线性表、插入、删除、表长、文件、记录、数据项：直接前趋、直接后续、线性表 的表头和表尾元素。 通过实例了解算法的描述和时间复杂度的基本分析思路。 3.问题与应用 通过实例，使学生掌握用类C语言，正确地描述线性表的基本操作、分析算法的时 间复杂度。 第二节线性表的顺序表示和实现 1.主要内容 掌握线性表的顺序存储结构特点、动态分配的顺序存储结构定义、基本操作的特点、 顺序存储结构的插入与删除操作实现、算法的时间复杂度分析。 2.基本概念和知识点 顺序存储、动态分配、基本操作的实现。 3.问题与应用（能力要求） 通过讲解线性表的合并操作，使学生掌握线性表的应用方法，并学习算法的时间复 杂度分析。 第三节线性表的链式表示和实现
5 向链表和循环链表），要求达到“熟练”层次； 3．掌握线性表在顺序存储结构上实现基本操作：查找、插入和删除等的算法，要 求达到“熟练”层次。 4．掌握各种链表结构中实现线性表操作的基本方法，能在实际应用中选的不同特 点及其适用场合，要求达到“熟练”层次。 5．了解静态链表，能够加深对链表本质的理解，要求达到“了解”层次。 6．能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其 适用场合。 （二）教学内容 第一节 线性表的类型定义 1．主要内容 掌握抽象数据类型线性表的定义、线性表的基本操作，通过线性表的归并算法掌握 用类 C 语言来描述算法的基本技巧。 2．基本概念和知识点 线性表、插入、删除、表长、文件、记录、数据项；直接前趋、直接后续、线性表 的表头和表尾元素。 通过实例了解算法的描述和时间复杂度的基本分析思路。 3．问题与应用 通过实例，使学生掌握用类 C 语言，正确地描述线性表的基本操作、分析算法的时 间复杂度。 第二节 线性表的顺序表示和实现 1．主要内容 掌握线性表的顺序存储结构特点、动态分配的顺序存储结构定义、基本操作的特点、 顺序存储结构的插入与删除操作实现、算法的时间复杂度分析。 2．基本概念和知识点 顺序存储、动态分配、基本操作的实现。 3．问题与应用（能力要求） 通过讲解线性表的合并操作，使学生掌握线性表的应用方法，并学习算法的时间复 杂度分析。 第三节 线性表的链式表示和实现
1.主要内容 掌握线性表的链式存储结构特点、明确“结点”的含义：静态链表、单链表、循环 链表与双向链表的插入、删除等操作的实现方法和特点区别。掌握线性链表的存储地址 数据域和指针域之间的对应关系，线性表的单链表的存储结构定义，带头结点的单链表 的应用： 掌握循环链表的特点、双向链表的结构定义和结点的插入刑除操作 2.基本概念和知识点 结点、头结点、数据域、指针域：静态与动态链表、单链表、循环链表与双向链表。 单链表、循环链表和双向链表的存储结构定义和基本操作的代码实现技术。 3.问题与应用 应掌握线性链表的类型定义、基本操作的代码实现，通过链表归并算法，使学生熟 练掌握各类链表中结点的插入与别除等操作。 第四节一元多项式的表示及相加 1.主要内容 通过一元多项式的算法实现，掌握链表的应用。 2.基本概念和知识点 抽象数据类型一元多项式的定义与表示、多项式相加算法的实现。 3.问题与应用 实现两个一元多项式的相加算法，使学生进一步理解和灵活应用线性链表米解决 些实际问题。 (三)思考与实践 思考：编写一套列车票售票系统，你应当如何设计该系统的数据结构？ 实践：线性表实验(2学时)：实现单链表各种基本运算的算法 课后练习：《数据结构(C语言版)》P51,第1题、第2题的(7)、(8)(10) 练习题应涉及以下几类： 1.线性表在顺序结构上各种基本操作的实现： 2.线性链表的各种操作： 3.两个或多个线性表的各种操作： 4.对不同的存储结构作对照比较，并注重其时间复杂度的分析： 5.循环链表和双向链表： 6.稀疏多项式及其运算在线性表的两种存储结构上的实现。 6
6 1．主要内容 掌握线性表的链式存储结构特点、明确“结点”的含义；静态链表、单链表、循环 链表与双向链表的插入、删除等操作的实现方法和特点区别。掌握线性链表的存储地址、 数据域和指针域之间的对应关系，线性表的单链表的存储结构定义，带头结点的单链表 的应用； 掌握循环链表的特点、双向链表的结构定义和结点的插入删除操作。 2．基本概念和知识点 结点、头结点、数据域、指针域；静态与动态链表、单链表、循环链表与双向链表。 单链表、循环链表和双向链表的存储结构定义和基本操作的代码实现技术。 3．问题与应用 应掌握线性链表的类型定义、基本操作的代码实现，通过链表归并算法，使学生熟 练掌握各类链表中结点的插入与删除等操作。 第四节 一元多项式的表示及相加 1．主要内容 通过一元多项式的算法实现，掌握链表的应用。 2．基本概念和知识点 抽象数据类型一元多项式的定义与表示、多项式相加算法的实现。 3．问题与应用 实现两个一元多项式的相加算法，使学生进一步理解和灵活应用线性链表来解决一 些实际问题。 （三） 思考与实践 思考：编写一套列车票售票系统，你应当如何设计该系统的数据结构？ 实践：线性表实验（2 学时）：实现单链表各种基本运算的算法 课后练习：《数据结构（C 语言版）》P51，第 1 题、第 2 题的（7）、（8）（10） 练习题应涉及以下几类： 1．线性表在顺序结构上各种基本操作的实现； 2．线性链表的各种操作； 3．两个或多个线性表的各种操作； 4．对不同的存储结构作对照比较，并注重其时间复杂度的分析； 5．循环链表和双向链表； 6．稀疏多项式及其运算在线性表的两种存储结构上的实现
(四)教学方法与手段 课堂讲授、多媒体教学。 分组讨论：线性表中的循环链表和双向链表的应用实例 第三章栈和队列 (一)目的与要求 1.掌握栈的定义和基本运算、栈的存储结构与实现、栈的应用特点：掌握栈类型 的两种基本操作的实现算法，注意栈满和栈空的条件以及它们的描述方法，并能在相应 的应用问题中正确加以应用，要求达到“熟练”层次： 2.掌握队列的定义和基本运算、队的存储结构与实现、链队列和循环队列的应用 特点，注意队满和队空的描述方法：要求达到“熟练”层次： 3.要求具有熟练应用栈和队列结构解决实际问题的能力。 (二)教学内容 第一节栈 1.主要内容 介绍栈的抽象数据类型的定义、栈的顺序存储结构和链式存储结构表示及其实现、 栈操作的特点。 2.基本概念和知识点 栈、栈顶指针、栈空、栈底、L0表：栈的顺序存储结构和链式存储结构表示及 其实现。 3.问题与应用 问题：栈空/队空的判断条件意味着栈/队列的插入删除操作的特点？ 要求学生能够正确实现顺序栈和链式栈的存储结构表示，以及栈的初始化、栈的 Push和Pop等操作实现。 第二节栈的应用举例 1.主要内容 介绍栈在“数制转换”、“表达式求值”等问题求解中的应用和算法实现。 2.基本概念和知识点 数制、算符优先法。 3.问题与应用
7 （四）教学方法与手段 课堂讲授、多媒体教学。 分组讨论：线性表中的循环链表和双向链表的应用实例。 第三章 栈和队列 （一） 目的与要求 1．掌握栈的定义和基本运算、栈的存储结构与实现、栈的应用特点；掌握栈类型 的两种基本操作的实现算法，注意栈满和栈空的条件以及它们的描述方法，并能在相应 的应用问题中正确加以应用，要求达到“熟练”层次； 2．掌握队列的定义和基本运算、队的存储结构与实现、链队列和循环队列的应用 特点，注意队满和队空的描述方法；要求达到“熟练”层次； 3．要求具有熟练应用栈和队列结构解决实际问题的能力。 （二） 教学内容 第一节 栈 1．主要内容 介绍栈的抽象数据类型的定义、栈的顺序存储结构和链式存储结构表示及其实现、 栈操作的特点。 2．基本概念和知识点 栈、栈顶指针、栈空、栈底、LIFO 表；栈的顺序存储结构和链式存储结构表示及 其实现。 3．问题与应用 问题：栈空/队空的判断条件意味着栈/队列的插入/删除操作的特点？ 要求学生能够正确实现顺序栈和链式栈的存储结构表示，以及栈的初始化、栈的 Push 和 Pop 等操作实现。 第二节 栈的应用举例 1．主要内容 介绍栈在“数制转换”、“表达式求值”等问题求解中的应用和算法实现。 2．基本概念和知识点 数制、算符优先法。 3．问题与应用
通过算法实例的讲解，使学生熟练掌握栈在实际问题求解中的应用方法。 第三节队列 1.主要内容 介绍队列结构的操作特点、抽象数据类型队列的定义、链式队列结构和循环队列结 构的表示和实现。分析队列与栈的异同。 2.基本概念和知识点 队列、FI℉O表、队头指针、队尾指针：队列的插入和删除等操作在链式队列和循 环队列的表示和实现。 3.问题与应用 要求学生能够正确实现链式队列和循环队列的存储结构表示，以及队列的初始化 出队、入队等操作实现。 (三)思考与实践 思考：栈与队列两种数据结构，与基本线性表有何不同？ 实践环节：实验(2学时)：病人看病模拟程序 课后练习：《数据结构(C语言版)》P83,第1题、第2题的(10) 练习题应涉及以下三类： 1.栈的类型特点及其应用： 2.递归算法执行过程中栈的状态和递归的 3.队列的类型特点和应用以及在不同存储结构上的实现方法。 (四)教学方法与手段 课堂讲授、多媒体教学。 课堂讨论。 第四章串、数组和广义表 (一)目的与要求 1,串的数据类型定义、串的三种存储表示：定长顺序存储结构、块链存储结构和 堆分配存储结构：要求达到“熟练”层次。 2.掌握串的七种基本操作的定义，并能利用这些基本操作实现串的其他各种操作 的方法，要求达到“理解”层次。 3.掌握串的堆存储结构以及在其上实现串操作的基本方法，要求达到“理解”层 次。 4.掌握数组的类型定义，数组的顺序存储结构，特殊矩阵的压缩存储
8 通过算法实例的讲解，使学生熟练掌握栈在实际问题求解中的应用方法。 第三节 队列 1．主要内容 介绍队列结构的操作特点、抽象数据类型队列的定义、链式队列结构和循环队列结 构的表示和实现。分析队列与栈的异同。 2．基本概念和知识点 队列、FIFO 表、队头指针、队尾指针；队列的插入和删除等操作在链式队列和循 环队列的表示和实现。 3．问题与应用 要求学生能够正确实现链式队列和循环队列的存储结构表示，以及队列的初始化、 出队、入队等操作实现。 （三） 思考与实践 思考：栈与队列两种数据结构，与基本线性表有何不同？ 实践环节：实验（2 学时）：病人看病模拟程序 课后练习：《数据结构（C 语言版）》P83，第 1 题、第 2 题的（10） 练习题应涉及以下三类： 1．栈的类型特点及其应用； 2．递归算法执行过程中栈的状态和递归的 3．队列的类型特点和应用以及在不同存储结构上的实现方法。 （四） 教学方法与手段 课堂讲授、多媒体教学。 课堂讨论。 第四章 串、数组和广义表 （一） 目的与要求 1．串的数据类型定义、串的三种存储表示：定长顺序存储结构、块链存储结构和 堆分配存储结构；要求达到“熟练”层次。 2．掌握串的七种基本操作的定义，并能利用这些基本操作实现串的其他各种操作 的方法，要求达到“理解”层次。 3．掌握串的堆存储结构以及在其上实现串操作的基本方法，要求达到“理解”层 次。 4．掌握数组的类型定义，数组的顺序存储结构，特殊矩阵的压缩存储
5.掌握广义表的定义，广义表的存储结构。 6.通过讲解模式匹配算法的思想，谈及中华文化中所蕴含的相关思想。从而既让 学生感受到中华文化的博大和思想精髓，从而爱上中华文化：也透过中华文化的有关思 想让学生更容易理解本章算法。 (二)教学内容 第一节串 1.主要内容 串类型的定义：介绍抽象数据类型串的定义、串操作的最小操作子集：串赋值、串 比较、求串长、串联接、求子串。 串的存储结构：定长顺序串存储表示、堆分配存储表示、串的块链存储表示。 串的模式匹配算法：BF算法、KMP算法 2.基本概念和知识点 串、子串、串长度、空串：串的五种基本操作。 堆、块。 模式、模式匹配 3.问题与应用 使学生正确掌握串操作的定义。 对于不同的存储表示，能够正确地定义串的存储结构，以及串基本操作的算法实现， 模式匹配算法及其应用。 第二节数组 1.主要内容 数组的定义：数组的顺序存储：特殊矩阵的压缩存储。 2.基本概念和知识点 压缩存储：对称矩阵；三角矩阵；对角矩阵。 3.问题与应用 为什么要对矩阵进行压缩存储？ 对称矩阵如何压缩存储，元素的存储地址如何计算： 三角矩阵如何压缩存储，元素的存储地址如何计算？ 对角矩阵如何压缩存储，元素的存储地址如何计算？ 第三节广义表
9 5．掌握广义表的定义，广义表的存储结构。 6．通过讲解模式匹配算法的思想，谈及中华文化中所蕴含的相关思想。从而既让 学生感受到中华文化的博大和思想精髓，从而爱上中华文化；也透过中华文化的有关思 想让学生更容易理解本章算法。 （二） 教学内容 第一节 串 1．主要内容 串类型的定义：介绍抽象数据类型串的定义、串操作的最小操作子集：串赋值、串 比较、求串长、串联接、求子串。 串的存储结构：定长顺序串存储表示、堆分配存储表示、串的块链存储表示。 串的模式匹配算法：BF 算法、KMP 算法 2．基本概念和知识点 串、子串、串长度、空串;串的五种基本操作。 堆、块。 模式、模式匹配。 3．问题与应用 使学生正确掌握串操作的定义。 对于不同的存储表示，能够正确地定义串的存储结构，以及串基本操作的算法实现， 模式匹配算法及其应用。 第二节 数组 1．主要内容 数组的定义；数组的顺序存储；特殊矩阵的压缩存储。 2．基本概念和知识点 压缩存储；对称矩阵；三角矩阵；对角矩阵。 3．问题与应用 为什么要对矩阵进行压缩存储？ 对称矩阵如何压缩存储，元素的存储地址如何计算？ 三角矩阵如何压缩存储，元素的存储地址如何计算？ 对角矩阵如何压缩存储，元素的存储地址如何计算？ 第三节 广义表
1.主要内容 广义表的定义：广义表的存储结构。 2.基本概念和知识点 广义表：广义表的长度：广义表的表头：广义表的表尾：广义表的层次和深度：原 子：子表。 3.问题与应用 使学生正确掌握取表头和取表尾两种操作：掌握广义表的“头尾链表的存储结构” 和“扩展线性链表的存储结构” (三)思考与实践 思考：给定N个字符串，设计一个求公共子串的算法。 课后练习：《数据结构(C语言版)》P107,第1题、第2题的(3)、第3题的(2) 练习题应涉及以下几类： 1,利用已知串的基本操作来实现其他操作： 2.串的顺序存储结构： 3.块链存储结构： 4.堆分配存储结构 5.模式匹配算法的应用： 6.数组的顺序存储及存储地址的计算： 7.三类特殊矩阵的压缩存储及元素存储地址的计算。 (四)教学方法与手段 课堂讲授、多媒体教学。 第五章树和二叉树 (一）目的与要求 1.深刻理解二叉树的定义、性质及其存储方法。 2.熟练掌握二叉树的二叉链表存储方式、结点结构和类型定义。 3.理解并掌握二叉树的三种遍历算法。 4.掌握二叉树的线索化方法。灵活运用二叉树的遍历方法解决相关的应用问题。 5.掌握树和森林的概念、存储方式，转化为二叉树的意义与方法。掌握树和森林 的遍历。 6.任何组织，包括家族其组织结构都是树结构，由此谈到中华传统文化中有关家， 家族传承，组织观念，个人服从集体，舍小家为大家等文化特质。 (二)教学内容
10 1．主要内容 广义表的定义；广义表的存储结构。 2．基本概念和知识点 广义表；广义表的长度；广义表的表头；广义表的表尾；广义表的层次和深度；原 子；子表。 3．问题与应用 使学生正确掌握取表头和取表尾两种操作；掌握广义表的“头尾链表的存储结构” 和“扩展线性链表的存储结构” （三） 思考与实践 思考：给定 N 个字符串，设计一个求公共子串的算法。 课后练习：《数据结构（C 语言版）》P107，第 1 题、第 2 题的（3）、第 3 题的（2） 练习题应涉及以下几类： 1．利用已知串的基本操作来实现其他操作； 2．串的顺序存储结构； 3．块链存储结构； 4．堆分配存储结构； 5．模式匹配算法的应用； 6．数组的顺序存储及存储地址的计算； 7．三类特殊矩阵的压缩存储及元素存储地址的计算。 （四） 教学方法与手段 课堂讲授、多媒体教学。 第五章 树和二叉树 （一） 目的与要求 1．深刻理解二叉树的定义、性质及其存储方法。 2．熟练掌握二叉树的二叉链表存储方式、结点结构和类型定义。 3．理解并掌握二叉树的三种遍历算法。 4．掌握二叉树的线索化方法。灵活运用二叉树的遍历方法解决相关的应用问题。 5．掌握树和森林的概念、存储方式，转化为二叉树的意义与方法。掌握树和森林 的遍历。 6．任何组织，包括家族其组织结构都是树结构，由此谈到中华传统文化中有关家， 家族传承，组织观念，个人服从集体，舍小家为大家等文化特质。 （二） 教学内容
