《数据结构(JAVA版)》课程教学大纲计算机专业.pdf

《数据结构》课程教学大纲 课程编号：806302024 课程名称：数据结构 英文名称：Data Structure 课程类型：专业基础课 总 学 时：72 讲课学时：56 实验学时：16 学 时：72 学 分：4.5 适用对象：计算机科学与技术专业本科生 先修课程：C/C++语言程序设计、Java 语言程序设计、离散数学 一、课程性质、目的和任务 数据结构课程是计算机科学与技术专业本科学生必修的一门专业基础课程。 数据结构是软件设计的重要理论和实践基础，数据结构设计和算法设计是软件系统设计 的核心。数据结构课程的任务是，讨论数据的各种逻辑结构、在计算机中的存储结构以及各 种操作的算法设计。数据结构课程的主要目的是，培养学生掌握处理数据和编写高效率软件 的基本方法，为学习后续专业课程以及进行软件开发打下坚实基础。 二、教学基本要求 数据结构是理论与实践并重的课程，既要掌握数据结构的基础理论知识，掌握算法设计 和分析方法，熟练运用一种程序设计语言编制具有中等难度的应用程序；也要掌握运行和调 试程序的基本技能，在实践中培养独立分析问题和解决问题的作风和能力。 本课程采用Java 语言及面向对象程序设计方法描述数据结构和算法。 本课程教学的基本要求说明如下。 1．理解线性表、串、栈、队列、数组、广义表、树、二叉树、图、散列表等数据结构 的基本概念，掌握它们的存储结构及各种操作的实现方法。 2．理解各种数据结构的查找操作要求，掌握在线性表、二叉树中采用的查找算法及查 找效率分析方法。掌握插入、交换、选择、归并等排序算法，掌握排序算法效率分析方法。 3．熟练运用Java 语言及面向对象程序设计方法描述各种抽象数据类型，表达它们的存 储结构，实现在各存储结构上的各种操作。掌握递归算法设计方法。 4．掌握在MyEclipse 集成开发环境中编辑、编译、运行和调试程序的方法，具备运行 和调试程序的基本技能，能够发现程序错误、及时找到错误所在并改正错误，重点和难点是 运用单步运行、设置断点、查看变量运行时值等程序调试技术，发现并改正程序逻辑错误。 1 三、教学内容及要求 1．绪论 ① 了解数据结构的基本概念，了解数据的逻辑结构、数据的存储结构和数据操作，了 解抽象数据类型与数据结构的关系。 ② 了解算法、算法描述、算法设计目标和算法分析方法，掌握算法的时间复杂度和空 间复杂度的分析方法。 2．线性表 ① 理解线性表的逻辑结构和基本操作，掌握线性表抽象数据类型的描述方法。 ② 掌握线性表的顺序存储结构和实现方法。 ③ 掌握线性表的链式存储结构及其特点，掌握实现单链表、循环单链表、双链表、循 环双链表基本操作的设计方法。比较两种存储结构的特点和性能。 3．串 ① 理解串的概念和串的基本操作，熟悉串的顺序存储结构和链式存储结构。 ② 掌握串的定义和基本操作的实现方法。 ③ 掌握两种串的模式匹配算法：Brute-Force 算法和KMP 算法。 4．栈和队列 ① 理解栈的概念和作用，掌握顺序栈和链式栈的设计方法，熟悉使用栈的算法设计方 法。 ② 理解队列的概念和作用，掌握顺序循环队列和链式队列的设计方法，熟悉使用队列 的算法设计方法。熟悉优先队列的概念、设计和使用方法。 ③ 理解递归定义，掌握递归算法设计方法。 5．数组和广义表 ① 理解数组的概念，理解一维数组和二维数组的存储结构。 ② 熟悉三角矩阵等特殊矩阵的压缩存储方法；熟悉稀疏矩阵的各种压缩存储方法，包 括稀疏矩阵三元组顺序表、单链表、行/列的单链表和十字链表存储结构。 ③ 理解广义表的概念，熟悉广义表双链表示的存储结构和操作实现。 6．树和二叉树 ① 理解树的定义、术语、表示方法、遍历规则和多种存储结构，掌握采用树的孩子兄 弟链表存储树并实现树的遍历、插入、删除等操作。 ② 理解二叉树的定义、性质、遍历规则和存储结构，掌握采用二叉链表或三叉链表存 储结构存储二叉树的特点，掌握二叉树的遍历、构造、插入、删除等操作算法，比较二叉树 遍历的递归算法与非递归