信息结构设计CS126

课程内容：

CS126主要介绍数据结构以及如何编程。课程内容涉及基本数据结构；如何对其进行数学分析；如何对这些数据结构进行编程等。此外，课程还对使用数据结构的常见算法有所讨论，包括搜索数据、排序数据。

课程目标：

1、让学生熟悉一些标准抽象数据类型（ADT）的规范、实现和使用，如链表、堆栈、队列、图等。

2、让学生学习一些常见任务的标准算法（如搜索和排序）以及一些衡量算法复杂度和正确性的基本方法；

3、让学生学习如何使用面向对象语言。

4、让学生学习编写非标准ADT的程序。

课程大纲：

1、类型及其属性：编程语言中的简单类型；熟悉的数学对象与给定类型的程序对象之间的关系。使用谓词逻辑来陈述类型的属性及其操作的前置条件和后置条件。

2、抽象数据类型：熟悉抽象对象（例如复数、集合、序列、矩阵）及其操作的规范，以及使用典型编程语言实现比较。一些重要标准类型的规范和实现（例如字符串、堆栈和队列）。

3、算法：数据结构和算法之间的关系；一些用于搜索、排序和模式匹配的标准算法。对复杂性的基本分析。推理简单算法实现的正确性。

学习成果：

在课程结束时，学生应能够：

1、熟悉一系列标准的ADT，以及如何使用其来完成常见的编程任务。

2、评估简单算法的复杂性和正确性，并为简单任务选择合适的算法。

3、具有为非标准应用设计用户定义的ADT和相关算法的实践经验。