数据结构-信息技术学院.PDF

数据结构 DATA STRUCTURE 一、基本信息 课程代码：【 课程学分：【4 】 面向专业：【数字媒体艺术专业】 课程性质：【学科基础必修课】 开课院系：【信息技术学院计算机科学与技术系】 使用教材：主教材 【数据结构 （C 语言版）.李云清等编著.人民邮电出版社.2009 年8 月】 辅助教材【数据结构题集（C 语言版）.严蔚敏、吴伟民编著.清华大学出版社. 1999 年2 月】 参考教材 【数据结构 （C 语言版）.严蔚敏、吴伟民编著.清华大学出版社. 2007 年3 月】 先修课程：【C 语言程序设计 （4）】 后续课程：【操作系统 （4）】、【数据库概论 （4）】 二、课程简介 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象及其之间关系与 操作的学科，是介于数学、计算机硬件和计算机软件三者之间的一门核心课程，属于计算 机学科中的一门综合性专业基础课程，它不仅是一般程序设计的基础，也是设计和实现编 译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。主要介绍： 线性表、栈、队列、数组、串、树、二又树、图等基本数据结构及其应用；排序和查找的 原理与方法；数据在外存上的组织方法，通过本课程的学习，使学生较熟练地掌握数据结 构的基本概念、特性、存储结构及相关算法；熟悉它们在计算机科学中最基本的应用；培 养和训练学生能运用高级程序设计语言编写结构清晰、可读性好的算法及初步评价算法的 能力；为后续课程的学习，以及计算机软件的研制和开发打下一定的理论基础及实践基础。 三、选课建议 适合计算机各专业，建议二年级上半学期开设，要求具有计算机程序设计语言及一定 的数学基础。 四、课程基本要求 全面掌握各种典型的数据结构，学会分析研究计算机的数据对象的特性，以便选择合 适的数据结构以及设计相应的算法，并初步掌握算法的时间分析及空间分析的方法。熟练 掌握几种典型的数据结构：线性表、栈、队列、树及图，熟练掌握各类数据结构的逻辑结 构、存储结构及其基本操作。在此基础上，实现查找和排序的算法。提高程序设计和实现 的能力。 五、课程内容 1 概论 了解数据结构的发展及所处的地位，学习本课程的目的、任务及要求。 理解数据结构的基本概念和术语、算法描述。 掌握算法分析（时间复杂度和空间复杂度）的方法。 2 线性表 顺序存储线性表：理解顺序存储线性表的逻辑结构及存储结构、类型描述；熟练掌握 顺序存储线性表的插入、删除、查找操作的算法描述及实现。 链式存储线性表：理解链式存储线性表的逻辑结构及存储结构、类型描述；熟练掌握 单链表基本操作的算法描述及实现；了解循环链表、双向链表基本操作的算法描述及实现。 理解顺序存储结构线性表与链式存储结构线性表的优缺点，能灵活使用线性表这类基 本数据结构。 难点：链式存储结构及算法实现；双向循环链表。 3 栈和队列 理解栈和队列的定义及特点，注意这类数据结构与线性表的异同点。 理解顺序栈、链栈的表示；熟练掌握在两种存储结构上的进栈出栈算法描述及实现； 掌握表达式的求值；了解栈与递归过程。 理解循环队列、链队列的表示；熟练掌握循环队列的存储及运算实现；掌握链队列的 存储及运算实现。 难点：循环队列和链队列的运算实现。 4 串 了解串的概念、串的逻辑结构和存储结构。 熟练掌握在顺序存储结构上实现串的各种操作的方法。 掌握利用串的基本运算来实现串的其它各种运算（重点是BF 算法）的方法。 难点：BF 算法实现 5 数组 理解数组的定义及基本概念，二维数组的存储结构。 掌握二维数组以行/列为主序的存储结构中的地址计算方法。 掌握特殊矩阵（对称矩阵、三角矩阵等）压缩存储到一维数组的方法。 理解稀疏矩阵的压缩存储的方法，掌握以三元组顺序表存储稀疏矩阵时的常用运算实 现。 难点：稀疏矩阵的三元组表示及常用运算实现。 6 树和二叉树 了解树的基本概念，理解二叉树的定义、性质和存储结构。 熟练掌握二叉树的遍历及其应用，遍历二叉