主页

教学

算法与数据结构

课程简介

  基本信息
  教学目的
  内容提要
  参考书目

课程简介—算法与数据结构

基本信息

教学目的

使学生较全面地理解算法和数据结构的概念、掌握各种数据结构与算法的实现方式，比较不同数据结构和算法的特点。通过学习，使学生不仅能学到数据结构与算法的基本知识，同时还能提高用计算机解决实际问题的能力。

本课程是一门理论与实践相结合的课程，要求学生在课堂学习的同时，完成适当的上机实习，实习与讲课的时间比不得小于1：1。本课程最后几周要求每个学生独立地完成一个较大的程序设计课题，并写出相应的课题报告，对自己的工作加以分析和总结。

内容提要

1. 概论：算法概念，算法分析；数据结构概念、数据结构分类；数据结构要讨论的基本问题
2. 线性表：线性表结构，顺序存储实现（顺序表），链接实现（链接表），应用
3. 字符串*：字符串，基本操作，模式匹配，字符串的应用
4. 堆栈与队列：堆栈的概念、和应用，队列的概念、实现和应用
5. 树与二叉树：树、二叉树的概念和实现，各种遍历算法，Huffman树的概念及应用
6. 字典与检索：字典与检索，静态字典，顺序检索，二分检索，分块检索*，最佳二叉排序树*，散列表、散列函数、碰撞处理，基于属性的检索*，倒排表与多重表*，动态字典的实现*，平衡二叉排序树*，B树与B+树*
7. 结构：基本概念及术语，存储表示法，遍历，最小生成树，最短路径，拓扑排序*，关键路径*
8. 稀疏矩阵和广义表*：多维数组和稀疏矩阵，稀疏矩阵，广义表
9. 文件：外存及文件，顺序文件，索引文件，散列文件，倒排文件*
10. 排序：排序的基本概念，选择排序、插入排序与冒泡排序，二分插入、Shell排序*、快速排序、堆排序*、归并排序*、基数排序*，排序算法的复杂性分析
11. 存储管理*：存储管理中的问题，动态分配与回收，废料搜集，存储压缩

参考书目

1. 《数据结构》，许卓群、张乃孝、杨冬青、唐世渭，高等教育出版社　1987
2. 《数据结构基础》，张乃孝等，北京大学出版社　1991
3. 《数据结构－C++与面向对象程序设计》，张乃孝、裘宗燕，高等教育出版社 1998
4. 《数据结构（C语言版）》，严蔚敏等，清华大学出版社 1997