数据结构：大纲及简介

0+1*2*(3+4)*(5-6)*7*(8-9) = 0024+0074

0*1+2345-6*7*8-sqrt(9) = 2006

0+1234+5+6!+7*8-9 = 2006

• 授课教师

  • 邓俊辉

  • deng@tsinghua.edu.cn

• 助教

  • 刘汝佳

  • liurj@mails.tsinghua.edu.cn

• 授课时间

  • 2006年02月20日 ~ 06月7日

  • 每周一、三晚7:20:-8:55

• 进度安排（根据实际情况可能调整，请经常查看本页）

  • 周次	日期 （2006）		内容	详细
    1	02/20		绪论	课程简介及要求 基本概念 计算机与算法 数据结构 抽象数据类型
    	02/22		绪论	算法复杂度 算法及其分析举例
    2	02/27		绪论	算法复杂度（续）
    			线性表	定义 ADT及接口 基于ADT完成各种操作
    	03/01		线性表	各种实现纵览 线性表的数组实现 线性表的链表实现     单链表     双向链表     循环链表     循环双向链表
    3	03/06		线性表	线性表的游标实现 表结构的应用：一元多项式 有序表     顺序查找     折半查找     Fibonacci查找     插值查找
    	03/08		习题课	作业环境及要求 基本编程技巧
    4	03/13		栈	概述     ADT     表示&实现     栈混洗 栈的应用     进制转换     括号匹配（迭代）
    	03/15		栈	表达式求值     RPN 递归     分治     括号匹配递归算法复杂度分析     Hanoi     尾递归 试探-回溯     八皇后     迷宫寻径
    5	03/20		队列	定义及ADT 链式表示与实现 顺序表示与实现 队列应用：离散事件模拟
    	03/22		串	串定义&实现 Brute-force算法 KMP算法
    6	03/27		串匹配算法	KMP改进算法 Boyer-Moore算法
    	03/29		树	树(a)概述     递归定义/拓扑定义     性质     ADT     父结点表示     孩子结点表示     父结点+孩子结点表示     孩子+兄弟表示 树(b)二叉树     定义&ADT     满、完全、一般二叉树/顺序实现     链式存储实现     生成与销毁
    7	04/03		树	树(c)二叉树的遍历     概述     前序遍历     中序遍历         递归实现         非递归实现#1、#2     后序遍历     层次遍历         非递归实现     表达式树     遍历与表达式的关系
    	04/05		树	Huffman树及编码     Binary encoding     Optimal encoding     Huffman tree     Huffman encoding
    8	04/10		查找树	BST 课堂测验#1
    	04/12		查找树	AVL树     定义 | 性质     单旋     双旋     统一算法     删除     效率分析&评价
    9	04/17		查找树	Splay树     动机 | 构思     Zig-Zig     Zig-Zag     效率分析与评价 B-树     动机 | 构思     查找     插入与分裂     删除与合并
    	04/19		查找树	kd-树     动机 | 构思     查找
    10	04/24		散列	思想 散列策略 冲突+解决冲突 课堂测验#2
    	04/26		习题课
    11	05/01		（五一）
    	05/03		（五一）
    12	05/08		优先队列	定义&性质&应用 二叉堆 基于二叉堆实现优先队列 应用实例：Huffman编码算法的改进
    	05/10		图	概述 实现     邻接矩阵     （多重）邻接表
    13	05/15		图	遍历     BFS / Queue         应用实例：最短路径     DFS / Stack         应用实例：连通分量划分 课堂测验#3
    	05/17		图	最小支撑树     定义 | 应用 | 性质     Prim算法     Kruskal算法
    14	05/22		图	最短路径     定义 | 应用 | 性质     Dijkstra算法 课堂测验#4
    	05/24		排序	问题 | 下界 bubblesort Insertionsort Quicksort Mergesort
    15	05/29		排序	Selectionsort Heapsort 课堂测验#5
    	05/31		排序	Shellsort Bucketsort Radixsort
    16	06/05		提高	Convex Hull
    	06/07		习题课

• 课程简介

  • 数据结构和算法设计是一对孪生兄弟，我们利用计算机来解决应用问题时，总可以归结并落实到这两个问题；正因为此，N. Wirth早在70年代即指出：Program = Data Structure + Algorithm。

  • 本课程属于传统数据结构，对应于经典的算法设计理论，主要讨论数据在计算机中存储、组织、传递和转换的过程及一般方法。随着现代算法理论和程序设计语言的发展，数据结构的研究也有很 多新的成果； 本课程将有选择性地做简要介绍，但不作为重点。

  • 课程内容覆盖线性表、栈、队列、串、数组、树、图，以及对这些对象施加的各种操作，如查找、排序、遍历等。

• 教学目标

  • 1. 了解各类数据结构适用的应用背景；

  • 2. 掌握各类数据结构的表示、实现方法和基本操作；

  • 3. 了解各类（基本）算法与不同数据结构之间的内在联系；

  • 4. 灵活地选取、运用各类（基本）算法及对应数据结构，解决实际问题。

• 先修要求

  • C语言程序设计

• 教材

  • 数据结构（C语言版），严蔚敏、吴伟民编著，清华大学出版社，2002年9月，ISBN: 7-900-64322-2

• 辅导材料（不属教学必需）

  • 数据结构与算法分析（C语言描述，原书第二版）, M. A. Weiss原著, 陈越改编, 人民邮电出版社, 2005年8月, ISBN: 7-115-13984-9

  • Introduction to The Design & Analysis of Algorithms, A. Levitin, 清华大学出版社（影印本）, 2003年8月, ISBN: 7-302-06796-1

  • 数据结构与算法（Java描述）, 邓俊辉, 机械工业出版社, 2006年2月, ISBN: 7-111-18204-9

  • 数据结构题集（C语言版）, 严蔚敏、吴伟民编著, 清华大学出版社, 2003年5月, ISBN: 7-302-03314-5

• 评分标准

  • 评分标准

• 作业要求

  • 相关说明及规定

  • 样题示例

  • 提交解答示例

• 学术诚信

  • 允许就作业进行讨论，但只限于宏观思路，不能涉及具体实现方法、算法流程或代码；只限于口头，不能有任何形式的记录。
  • 在各题的readme文件中，须注明共同讨论者，或者其它思路来源（如参考书籍、网站等）。
  • 严禁抄袭，违者无论情节轻重，抄袭双方除按照学校相关规定处理外，相关习题成绩按完成质量为-1计算。
  • 选修本课者有义务对自己的作业设计资料及代码保密，随意公开者也按抄袭处。

• 重要日期

  • 各次作业上交期限

TOP

Copyleft (c) 2003-3002, Junhui Deng
Last updated on 12.18.2013