中国海洋大学

数据结构

图片
课程概述

《数据结构》,是计算机程序设计的重要理论技术基础,是计算机学科的核心课程。其教学要求是:学会分析研究计算机加工的数据结构的特性,以便为应用涉及的数据选择适当的逻辑结构、存储结构以及相应的算法,并初步掌握算法的时间分析和空间分析技术。另一方面,本课程的学习过程也是复杂程序设计的训练过程,是对学生的数据抽象能力的培养过程。

课程内容:

1、综述数据、数据结构和抽象数据类型等基本概念;

2、从抽象数据类型的角度、分别讨论线性表、栈、队列、数组、广义表、树与二叉树以及图等基本类型的数据结构及应用;

3、讨论查找和排序,除了介绍各种实现方法之外,并着重从时间上进行定性或定量的分析和比较。

课程特色:

1)强调基础数据结构与算法的训练,始终以问题为研究对象,按照提出问题、分析问题、解决问题、总结问题的步骤,培养学生运用数据结构和算法基本理论来分析和解决问题得能力。

2)结合计算机科学与技术的现代前沿研究课题,按照验证实验,设计实验,综合实验三个层次设计研究启发式教学案例,扩展学生知识体系,培养主动学习、研究和创新意识。

3)注重实践能力和工程能力的培养,鼓励学生参与实际的课题实现工作,体验软件开发的规范性,并建立起数据结构与算法设计和问题求解的知识体系。





证书要求

按百分制计分,60分至84分为合格,85分至100分为优秀。

评分方案:

1. 完成课程单元测试题;(40%)

2. 期末考试占60%;

证书:

1. 评分高于 60 分颁发普通学员证书。

2. 评分高于 85 分颁发优秀学员证书。



预备知识

C程序设计语言、离散数学(或图论)

授课大纲

第一章 绪论

  1. 什么是数据结构

  2. 基本概念和术语


  3. 抽象数据结的表示与实现

  4. 算法和算法分析

第二章 线性表

  1. 线性表的类型定义

  2. 线性表的顺序表示和实现

  3. 线性表的链式表示和实现

  4. 一元多项式I的表示及相加

第三章 栈和队列

  1. 栈的应用举例

  2. 队列

第四章 

  1. 串类型的定义

  2. 串的表示和实现

  3. 串的模式匹配算法

第五章 数组和广义表

  1. 数组的定义

  2. 数组的顺序表示和实现


  3. 矩阵的压缩存储


  4. 广义表的定义

  5. 广义表的存储结构

  6. 广义表操作的递归算法

第六章 树和二叉树

  1. 树的定义和基本术语

  2. 二叉树

  3. 遍历二叉树和线索二叉树

  4. 树和森林

  5. 赫夫曼树及其应用

第七章 

  1. 图的定义和术语

  2. 图的存储结构

  3. 图的遍历

  4. 图的连通性问题

  5. 有向无环图及其应用

  6. 最短路径

第八章 查找

  1. 查找概述

  2. 静态查找表

  3. 动态查找表

  4. 哈希表

第九章 内部排序

  1. 概述

  2. 插入排序

  3. 快速排序与选择排序

  4. 归并排序

  5. 基数排序

  6. 各种内部排序方法的比较讨论