《数据结构》课程教学大纲 《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．问题与应用（能力要求） 通过讲解线性表的合并操作，使学生掌握线性表的应用方法，并学习算法的时间复 杂度分析。 第三节 线性表的链式表示和实现