C++编程实例与数据结构基础\t\r ?
我们已经学完了C++语言中的重要的语法结构。通过练习和作业我们也掌握了具体的编程方法和技巧。本章，我们将使用一个实际例子来看看如何使用以对象为基础的程序设计方法。本章中的例子也可以是对所介绍的C++的内容的复习和拓展学习。\t\r ?
本章中的例子同时是一个过渡到数据结构课程的例子。简单地说数据结构指的主要是一些常用容器类，数据结构这门课程是介绍各种数据结构的使用、特性、和实现的课程。正确了解和熟练使用各种数据结构大大简化绝大多数的程序的编写。数据结构与面向对象程序课程有基础与应用的关系。本章还将通过例子简单地介绍两种常用的数据结构：集合和关联表。作为这个学期的最后一章，本章起着承前启后和的融汇贯通作用。\t\r ?
1. 面向对象的程序设计方法\t\r ?
我门在最开始就讲过，面向对象的程序设计方法能帮助我们更好地设计程序，尤其是具有一定规模的程序。面向对象的程序设计方法并不是能写出所有程序来解决所有问题的方法：实际上有很多的问题是当前无解的，另外很多问题是很难的，它们由研究人员通过长时间的探索才找到答案的。这
里我们介绍的程序设计方法指的是在知道程序的算法的情况下，编写出结构清晰，不容易包含错误的程序。\t\r ?
下面我们回忆一下所讨论过的各个C++的语法成分的在程序设计中的作用：\t\r ?
1. 对象object：类（或复合数据类型）的变量，它使的
我们可以把每个现实世界中的物体表现为程序里面的一个复合的数据。\t\r ?
2. 封装encapsulation：使每个功能模块的使用方法简单
明了，并且消除由用户的错误操作而引起程序的错误。\t\r ?3. 模版类template\t\r ?class：使得容器可以存放不同类型的
元素，避免为不同类型的元素重写相同的容器类而造成程序的冗余。\t\r ?
4. 多态性polymorphism：具有同一个程序接口的多种数
据类型可以通过这个接口做相同的处理。避免程序的冗余。\t\r ?
5. 异常处理exception\t\r ?handling：让错误处理更加简单。
把错误的报告和错误的处理分离，使得每个错误都可以在任何（最适合处理的）地方处理。\t\r ?
6. 名字空间namespace，静态变量/函数static\t\r ?
variable/function：避免命名冲突，封装非对象变量/函数。\t\r ?
我们曾经通过简单的例子来讨论这些语法结构的用法和技巧。这章中我们使用一个比较长的例子来包含以上内容。这个例子中我们写一个程序，程序的输入使多个事件和它们的先行事件，程序的输出给出一个这些事件的可行发生顺序。输入由文件给出，文件中的每一行描述一个事件。每行中的第一个单词是一个事件，后面各个是这个事件的先行事件。\t\r ?
例子1：排列课程。\t\r ?
Algorithm\t\r ?
OperatingSystem\t\r ?Programming\t\r ?
ComputerNetwork\t\r ?DiscreteMaths\t\r ?DataStructure\t\r ?DataBase\t\r ?
Programming\t\r ?Programming\t\r ?#\t\r ?
Programming\t\r ?#\t\r ?
Programming\t\r ?Programming\t\r ?
DiscreteMaths\t\r ?DataStructure\t\r ?\t\r ?
OperatingSystem\t\r ?\t\r ?
DiscreteMaths\t\r ?OperatingSystem\t\r ?
#\t\r ?
Algorithm\t\r ?\t\r ?#\t\r ?\t\r ?#\t\r ?##\t\r ?
\t\r ?#\t\r ?\t\r ?\t\r ?\t\r ?\t\r ?\t\r ?
每行描述一个课程和它的先修课程。如第一行表示Algorithm的先修课程是Programming和DiscreteMaths。每行的#表示本行结束，最后一行中的##表示整个文件的结束。第3行中的Programming和第5行中的DiscreteMaths不需要任何先修课程。程序的输出应该是一个课程的排序列表，每个课程的先修课程必须出现在列表的前面。为了简化例子，我们只要求输出其中的一种可行的排序。例如，Programming和DicreteMaths都没有先修课程，输出的时候那个在前面都可以。\t\r ?
例子2：学生的生活安排。\t\r ?
basket--‐ball\t\r ?prepare--‐C++\t\r ?prepare--‐maths\t\r ?submit--‐maths--‐hw\t\r ?submit--‐C++--‐hw\t\r ?review--‐C++\t\r ?review--‐maths\t\r ?complete--‐C++--‐hw\t\r ?complete--‐maths--‐hw\t\r ?register--‐email\t\r ?submit--‐maths--‐hw\t\r ?review--‐C++\t\r ?review--‐maths\t\r ?register--‐email\t\r ?complete--‐C++--‐hw\t\r ?#\t\r ?#\t\r ?
review--‐C++\t\r ?review--‐maths\t\r ?#\t\r ?submit--‐C++--‐hw\t\r ?complete--‐C++--‐hw\t\r ?complete--‐maths--‐hw\t\r ?complete--‐maths--‐hw\t\r ?#\t\r ?\t\r ?\t\r ?#\t\r ?#\t\r ?\t\r ?#\t\r ?#\t\r ?#\t\r ?#\t\r ?\t\r ?\t\r ?\t\r ?\t\r ?\t\r ?\t\r ?
例子2：学生的生活安排。学生给出自己一天当中需要做的事情的优先顺序，程序给出一个可能的先后安排顺序。\t\r ?
在使用面向对象程序(OOP)的方式设计程序之前，我们看看这个程序的算法。我们以排列课程为例。首先，我们把所有课程排成一个队伍。开始的时候，课程在队伍中的顺序可以是随意的，我们就按照文件中的顺序把课程添加到队伍中。另外我们还需要一个记录已经修过了的课程的容器。\t\r ?
Queue\t\r ?
OS DiscreteMaths Database DataStructure Network \t\r ?
Programming Set
\t\r ?
计算机擅长执行简单的重复性任务，我们的算法描述如下：\t\r ?
1 把所有课程添加到队伍中 2 当队伍中有课程的时候
3 取出队伍中的第?一个课程
4 如果这个课程的先修科都以修完 5 修这?门课 6 否则
7 把这?门课添加到伍中最后
以上的算法模拟一个实际修课的过程：不断尝试每一门课程，如果一门课的先修课都修完那么我们就修这们课，否则把这们课放到队伍最后。要让程序记住那些课已经修过：我们在修没门课的时候，出了把这们课输出到控制台，还把它加入到已经修课程的容器里；以后便可以通过查看这个容器中是否有一门课程来知道该课程是否已修过。下面是更具体的算法：\t\r ?
1 把所有课程添加到队伍中
2 把已修课程的容器初始化为空 3 当队伍中有课程的时候
4 取出队伍中的第?一个课程
5 如果已修课程的容器包含这?门课程
6 把这?门课程添加到已修课程的容器 7 在控制台输出这?门课程 8 否则
9 把这?门课添加到伍中最后
有了算法，我们开始使用OOP的方式设计程序。设计的任务的看看程序需要中使用那些对象，然后看看这些对象之
C++程序设计 lectureNote12
