个人介绍
数据结构
提供学校: 大连海事大学
专业大类: 管理科学与工程
学分: 4
课时: 72
       《数据结构》是计算机科学课程体系中核心课程之首,作为学科的专业基础课,具有承上启下的重要作用。对应于学科中问题求解的理论、抽象和设计的方法论,本课程内容体系结构分为概念表述、构建数据模型、设计算法三个层面,突出数据组织方法与处理技术,贯穿程序设计和软件工程新思想和新观点。采用面向对象和抽象数据类型(ADT)观点介绍数据结构技术,集中体现了分解、抽象和信息隐蔽基本原则,抽象数据类型是中枢,展示了信息结构转换的三个重要阶段:数学模型→抽象数据类型→数据结构与算法。以构造性思维训练为重点,培养数据抽象能力、算法设计能力和软件开发能力。
教师团队







《数据结构》课程负责人陈燕教授是享受国务院政府特殊津贴的专家,辽宁省优秀科技工作者,辽宁省教学名师,辽宁省优秀教师,大连市有突出贡献专家。本课程教学团队主要由四名教师组成,其中教授2名,副教授2名,4人均获得博士学位。教学团队年龄结构合理,是新老结合的、有着丰富教学经验和教学激情的队伍。

教学目的




这门课程的目的是通过学习使学生全面掌握各种常用的数据结构、存储结构及相关算法,为今后学习专业课及继续深造奠定基础,为提高利用计算机解决实际问题的能力创造条件。在学习过程中,让学生学会利用STL(Standard Template Library)提供的数据结构及算法进行编程,把学习的重点放在利用学习的数据结构理论解决实际问题上。

教学要求




要求掌握线性表、栈和队列、字符串、数组、树、图等常用的一些数据结构的逻辑形式、存储形式以及实现各种操作的算法。掌握在上述各种数据结构上实现的查找和排序的基本方法。能对工作中遇到的一些算法的时间复杂性和空间复杂性进行分析。能根据用户的要求及系统提供的数据,设计或选择合适的数据结构并能编写正确的算法。学会利用C++及STL编程,能够正确评价、选择和使用库函数(STL)提供的数据结构及算法解决应用问题。

本课程地位和任务




数据结构是信息管理与信息系统的重要基础课。通过对课程的学习,学生可以掌握从问题入手,分析研究计算机加工的数据结构的特性,为应用所涉及的数据,选择适当的逻辑结构、存储结构及相应操作的算法,使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法,要求学生掌握各种数据结构的特点、存储表示、运算方法以及在计算机科学中最基本的应用。培养、训练学生选用合适的数据结构和编写质量高、风格好的应用程序的能力,培养学生分析问题、解决问题的能力。通过本课程的学习,为学习操作系统和数据库等课程奠定基础。

教学内容及基本要求





第一章 绪论(4学时) 

(1)数据结构及其解决问题的范畴 

(2)基本概念 

(3)算法和算法的量度 

要求:掌握数据结构的基本概念;算法的概念,以及算法的执行效率及其度量。

第二章 线性表(4学时) 

(1)线性表的概念、数据类型定义及线性结构的特点 

(2)线性表的顺序表示与实现 

(3)线性表的链式表示与实现

要求:掌握线性表的逻辑结构特性;顺序存储结构和链式存储结构的描述方法;线性表在顺序和链式存储上实现查找、插入、删除等基本操作的算法;循环链表和双向链表的操作实现。

第三章 栈和队列(8学时) 

1)顺序栈 

(2)链栈

(3)循环队列

(4)链队列

要求:掌握栈和队列这两种抽象数据类型、名词和术语;栈与队列的实现方法、基本操作及其算法,循环队列和链队列的基本操作实现。

第四章 串(4学时) 

(1)串的定义 

(2)串的表示与实现 

(3)串的模式匹配 

要求:掌握串的定义和基本操作的含义;在串的定长顺序存储结构上实现串的基本操作方法;串的三种模式匹配

第五章 数组与广义表(4学时) 

(1)数组的定义、顺序表示与实现 

(2)矩阵的压缩存储与应用 

(3)广义表的存储表示与应用

要求:要求:掌握数组的两种存储表示方法;稀疏矩阵的两种压缩存储方法的特点和适用范围;以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法;广义表的概念。

第六章 树(8学时) 

(1)树的定义、基本术语和二叉树定义、性质和存储结构 

(2)遍历二叉树与线索二叉树 

(3)森林与二叉树的转换和树和森林的遍历 

要求:掌握本章中的名词、术语;二叉树的定义、性质及及相应的证明方法;二叉树线索化的实质;二叉树的各种存储结构的特点及适用范围;二叉树的各种遍历算法;树和森林与二叉树的转换方法;建立赫夫曼树和赫夫曼编码的方法。

第七章 图(8学时) 

(1)图的定义和术语 

(2)图的存储结构 

(3)图的遍历 

(4)连通网的最小生成树 

(5)两点之间的最短路径问题 

(6)拓扑排序 

(7)关键路径 

要求:掌握本章各名词、术语;图的多重邻接表、十字链表的存储方法;图的邻接矩阵、邻接表的存储结构及其构造方法;图的两种搜索路径的遍历方法:深度优先搜索和广度优先搜索;应用图的遍历算法求解连通分量;求解最小生成树算法;求解拓扑排序算法;求解最短路径算法;求解关键路径算法。


第八章 查找(6学时) 

(1)静态查找表 

(2)动态查找表 

(3)哈希表 

要求:掌握顺序表和有序表的查找方法;平衡二叉树的旋转技术;二叉排序树的构造方法和查找方法;哈希表的构造方法及哈希查找中解决“冲突”的相关方法;按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。

第九章 内部排序(6学时) 

(1)插入排序 

(2)快速排序与选择排序 

(3)归并排序与基数排序 

要求:掌握直接插入排序、折半插入排序、希尔排序、快速排序、堆排序、归并排序、基数排序等排序方法。方法;各种排序方法的算法及时间复杂度的分析和比较;排序方法"稳定"和"不稳定"的含义;排序的定义和各种排序方法的特点。


随身课堂

参考教材

主要教学参考书

《数据结构》,科学出版社,陈燕,曹妍等编著,2014.3

《Data Structures& Program Design In C》Robert Kruse/C.L. Tondo Bruce Leung,清华大学出版社, Prentice-Hall International ,Inc. 

《C程序设计教程(C how to program Second Edition)》 H.M.Deitel P.J.Deitel(美)著,薛万鹏等译.机械工业出版社.

《The C Programming Language Second Edition》Brian W.Kernighan Dennis M.ritchie(美)著,徐宝文等译,机械工业出版社.


扩展阅读


课程评价

提示框
提示框
确定要报名此课程吗?
确定取消