◇◇新语丝(www.xys.org)(xys.dxiong.com)(xys.3322.org)(xys.freedns.us)◇◇

赤裸抄袭——北京工业大学曾毅的《数据结构总论》

作者：披风吹雨

《数据结构总论》由曾毅发表于微软中国网站，文章地址：
http://www.microsoft.com/china/community/Columns/Zengyi/9.mspx

不查不知道，一查吓一跳，这篇文章95%以上都是从别人文章的原话抄袭来的！
作者只组织了一下就发表到微软中国网站，并且没有声明任何参考文献、感谢等
文字，简直是戴着眼镜的强盗！

这篇文章的抄袭分三部分，分别来自“算法与数据结构”网站、某网络课堂、严
蔚敏老师的教程。【】内为原文。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~
下列内容抄袭自“算法与数据结构”网站，原文地址：
http://algorithm.myrice.com/datastructure/index.html
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~

 数据结构作为一门学科，主要研究数据的各种逻辑结构和存储结构，以及对数
据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存
储结构；对数据的操作（即算法）。通常，算法的设计取决于数据的逻辑结构，
算法的实现取决于数据的物理存储结构。数据结构的研究不仅涉及到计算机硬件
的研究，比如存储装置和存取方法，而且解决编译原理、操作系统、数据库系统
的数据元素在存储器中的分配问题的重要基础。

【数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据
的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储
结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算
法的实现取决于数据的物理存储结构。】

================================================
数据元素之间的逻辑关系被称为数据元素的逻辑结构，可以用一个二元组表示：
Data_Structure = (D, S) // Data_Structure= (Data-part, 
Logic-Structure-Part)
这里D是数据元素的集合，S是定义在D（或其他集合）上的关系的集合，
S = { R │ R : D×D×...}。 

【通常来说，一个数据结构DS 可以表示为一个二元组：
DS=(D,S), //i.e., data-structure=(data-part,logic-structure-part)
这里D是数据元素的集合（或者是“结点”，可能还含有“数据项”或“数据
域”），S是定义在D（或其他集合）上的关系的集合，S = { R | R : D×D
×...}，称之为元素的逻辑结构。】

================================================
数据结构在计算机中的表示（又称为映像）称为数据的存储结构（物理结构）
数据结构的物理结构是指逻辑结构的存储映像(image)。数据结构 DS 的物理结
构 P 对应于从 DS 的数据元素到存储区M（维护着逻辑结构S）的一个映射：
P:(D,S) --> M 

【数据结构的物理结构是指逻辑结构的存储镜像(image)。数据结构 DS 的物理
结构 P 对应于从 DS 的数据元素到存储区M（维护着逻辑结构S）的一个映射：
P:(D,S) --> M】

================================================
存储器模型：一个存储器 M 是一系列固定大小的存储单元，每个单元 U 有一个
唯一的地址 A(U)，该地址被连续地编码。每个单元 U 有一个唯一的后继单元 
U'=succ(U)。
P 的四种基本映射模型：顺序（sequential）、链接（linked）、索引
（indexed）和散列（hashing）映射。因此，我们至少可以得到4×4种可能的物
理数据结构： (图略)

【存储器模型：一个存储器 M 是一系列固定大小的存储单元，每个单元 U 有一
个唯一的地址 A(U)，该地址被连续地编码。每个单元 U 有一个唯一的后继单元 
U'=succ(U)。
P 的四种基本映射模型：顺序（sequential）、链接（linked）、索引
（indexed）和散列（hashing）映射。
因此，我们至少可以得到4×4种可能的物理数据结构：(图略)】

================================================
需要指出的是：并不是所有的可能组合都合理。
数据结构DS上的操作：所有的定义在DS上的操作在改变数据元素（节点）或节点
的域时必须保持DS的逻辑和物理结构。
DS上的基本操作：任何其他对DS的高级操作都可以用这些基本操作来实现。最好
将DS和他的所有基本操作看作一个整体——称之为模块（model）。我们可以进
一步将该模块抽象为数据类型（其中DS的存储结构被表示为私有成员，基本操作
被表示为公共方法），称之为ADT（即是抽象数据类型Abstract Data Type，指
一个数学模型以及定义在该模型上的一组操作）。 

【（并不是所有的可能组合都合理）
数据结构DS上的操作：所有的定义在DS上的操作在改变数据元素（节点）或节点
的域时必须保持DS的逻辑和物理结构。
DS上的基本操作：任何其他对DS的高级操作都可以用这些基本操作来实现。最好
将DS和他的所有基本操作看作一个整体——称之为模块。我们可以进一步将该模
块抽象为数据类型（其中DS的存储结构被表示为私有成员，基本操作被表示为公
共方法），称之为ADT。作为ADT，堆栈和队列都是一种特殊的表，他们拥有表的
操作的子集。】

===================================================
好的和坏的DS：如果一个DS可以通过某种“线性规则”被转化为线性的DS（例如
线性表），则称它为好的DS。好的DS通常对应于好的（高效的）算法。这是由计
算机的计算能力决定的，因为计算机本质上只能存取逻辑连续的内存单元，因此
如何没有线性化的结构逻辑上是不可计算的。比如对一个图进行操作，要访问图
的所有结点，则必须按照某种顺序来依次访问所有节点（要形成一个偏序），必
须通过某种方式将图固有的非线性结构转化为线性结构才能对图进行操作。 

【好的和坏的DS：如果一个DS可以通过某种“线性规则”被转化为线性的DS（例
如线性表），则称它为好的DS。好的DS通常对应于好的（高效的）算法。这是由
计算机的计算能力决定的，因为计算机本质上只能存取逻辑连续的内存单元，因
此如何没有线性化的结构逻辑上是不可计算的。比如对一个图进行操作，要访问
图的所有结点，则必须按照某种顺序来依次访问所有节点（要形成一个偏序），
必须通过某种方式将图固有的非线性结构转化为线性结构才能对图进行操作。】

==================================================
树是好的DS——它有非常简单而高效的线性化规则，因此可以利用树设计出许多
非常高效的算法。树的实现和使用都很简单，但可以解决大量特殊的复杂问题，
因此树是实际编程中最重要和最有用的一种数据结构。树的结构本质上有递归的
性质——每一个叶节点可以被一棵子树所替代，反之亦然。实际上，每一种递归
的结构都可以被转化为（或等价于）树形结构。说到递归在北京大学的数据结构
课程里面有个老师经常说“不懂递归就不算北大计算机系的学生”，这样看来足
以从侧面说明书的结构的重要性。 

【树是好的DS——它有非常简单而高效的线性化规则，因此可以利用树设计出许
多非常高效的算法。树的实现和使用都很简单，但可以解决大量特殊的复杂问题，
因此树是实际编程中最重要和最有用的一种数据结构。树的结构本质上有递归的
性质——每一个叶节点可以被一棵子树所替代，反之亦然。实际上，每一种递归
的结构都可以被转化为（或等价于）树形结构。】


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~
下列内容抄袭自某网络课堂，原文地址：
http://202.116.65.197/wlkc/shujujiegou/teaching/chapter1/chapter1-2-3.
html
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~
ADT按照其值的不同特性分为下列三种类型：
原子类型（Atomic Data Type）：变量是不带结构的，不可分解的。
固定聚合类型（Fixed-aggregate Data Type）：其值由确定数目的成分按照某
种结构组成
可变聚合类型（Variable-Aggregate Data Type）：值的成分的数目不确定
抽象数据类型的描述方法
抽象数据类型可用（D，S，P）三元组表示
其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。
ADT 抽象数据类型名 {
数据对象：〈数据对象的定义〉
数据关系：〈数据关系的定义〉
基本操作：〈基本操作的定义〉
} ADT 抽象数据类型名
其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为
基本操作名（参数表）
初始条件：〈初始条件描述〉
操作结果：〈操作结果描述〉

【若按其值的不同特性，可细分为下列三种类型： 
    1)原子类型(Atomic Data Type) 属原子类型的变量的值是不可分解的。这
类抽象数据类型较少，因为一般情况下，已有的固有数据类型足以满足需求。但
有时也有必要定义新的原子数据类型，例如，数位为100的整数。 
    2)固定聚合类型(Fixed-aggregate Data Type) 属该类型的变量，其值由确
定数目的成分按某种结构组成。例如，复数是由两个实数依确定的次序关系构成。 
    3)可变聚合类型(Variable-Aggregate Data Type) 和固定聚合类型相比较，
构成可变聚合类型“值”的成分的数目不确定。例如，可定义一个“有序整数序
列”的抽象数据类型，其中序列的长度是可变的。
抽象数据类型定义格式：
ADT抽象数据类型名{
数据对象：<数据对象的定义>
数据关系：<数据关系的定义>
基本操作：<基本操作的定义>
} ADT 抽象数据类型名
    其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为：
 基本操作名(参数表)
 初始条件：<初始条件描述>
 操作结果：<操作结果描述> 】

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~
下列内容抄袭自清华大学严蔚敏老师的教程，如此规模的抄袭令人惊叹不已！
http://www.mscenter.edu.cn/mybbs/viewpassage.aspx?bid=7&fid=45&id=2388
&pn=1&elite=0
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~

一个算法必须满足以下五个重要特性：
1．有穷性 对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算
法中的每个步骤都能在有限时间内完成；
2．确定性 对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法
的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有
一条执行路径；
3．可行性 算法中描述的操作都可以通过已经实现的基本操作运算有限次实现之；
4．有输入 作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入
量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌
入算法之中；
5．有输出 它是一组与输入有确定关系的量值，是算法进行信息加工后得到的结
果。

【一个算法必须满足以下五个重要特性：
  1．有穷性  对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：
算法中的每个步骤都能在有限时间内完成；
  2．确定性  对于每种情况下所应执行的操作，在算法中都有确切的规定，使
算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都
只有一条执行路径；
  3．可行性  算法中的所有操作都必须足够基本，都可以通过已经实现的基本
操作运算有限次实现之；
  4．有输入  作为算法加工对象的量值，通常体现为算法中的一组变量。有些
输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已
被嵌入算法之中；
  5．有输出 它是一组与“输入”与确定关系的量值，是算法进行信息加工后得
到的结果，这种确定关系即为算法的功能。 】

=================================================
1.3.2算法设计的原则
设计算法时我们应当严格考虑：
1．正确性（Correctness）
首先，算法应当满足以特定的“规格说明”方式给出的需求。对算法是否“正确”
的理解可以有以下四个层次：
a．程序中不含语法错误；
b．程序对于几组输入数据能够得出满足要求的输出结果；
c．程序对于精心选择的、典型、苛刻的几组输入数据能够得出满足要求的结果；
d．程序对于一切合法的输入数据都能得出满足要求的结果；
通常以第c层意义的正确性作为衡量一个算法是否合格的标准。因为作为输入，
我们有时候不可能提前做出所有的预期。
2. 可读性(Readability)
算法主要是为了人的阅读与交流，其次才是为计算机执行。因此算法应该易于人
的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试；有些程序设
计者总是把自己设计的算法写的只有自己才能看懂，这样的算法反而没有太大的
价值。
3．健壮性（Rubustness）
当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫
名奇妙的输出结果。这就需要我们一定要充分的考虑异常情况（Unexpected 
Exceptions）并且，处理出错的方法不应是中断程序的执行，而应是返回一个表
示错误或错误性质的值，以便在更高的抽象层次上进行处理。
4．高效率与低存储量需求
通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储
空间。两者都与问题的规模有关。 


【二、算法设计的原则
  设计算法时，通常应考虑达到以下目标： 
    1．正确性
首先，算法应当满足以特定的“规格说明”方式给出的需求。
其次，对算法是否“正确”的理解可以有以下四个层次：
a．程序中不含语法错误；
b．程序对于几组输入数据能够得出满足要求的结果；
c．程序对于精心选择的、典型、苛刻切带有刁难性的几组输入数据能够得出满 
   足要求的结果；
d．程序对于一切合法的输入数据都能得出满足要求的结果；
通常以第c层意义的正确性作为衡量一个算法是否合格的标准。 
    2. 可读性
算法主要是为了人的阅读与交流，其次才是为计算机执行。因此算法应该易于人
的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试； 
    3．健壮性
当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫
名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回
一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。
4．高效率与低存储量需求
通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储
空间。两者都与问题的规模有关。 】

=================================================
1.3.3算法效率的衡量方法与准则
通常有两种衡量算法效率的方法: 
1．事后统计法
缺点：
(1)必须执行程序才能进行判断
(2)其它因素（如硬件、软件环境）掩盖算法本质
2.事前分析估算法
主要是看消耗的时间。和算法执行时间相关的因素：
1．算法选用的策略
2．问题的规模
3．编写程序的语言
4．编译程序产生的机器代码的质量
5．计算机执行指令的速度
一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n
表示），或者说，它是问题规模的函数。假如，随着问题规模n的增长，算法执
行时间的增长率和f(n)的增长率相同，则可记作：
T (n) = O(f(n))
称T (n) 为算法的渐近时间复杂度（Asymptotic Time Complexity）,简称时间
复杂度。O是数量级的符号。
下面我们探讨一下如何估算算法的时间复杂度
算法 = 控制结构 + 原操作（固有数据类型的操作）
算法的执行时间=原操作(i)的执行次数×原操作(i)的执行时间
算法的执行时间与原操作执行次数之和成正比
我们先介绍一个概念： 

【三、算法效率的衡量方法和准则 
    通常有两种衡量算法效率的方法: 
事后统计法
缺点：1。必须执行程序 
      2．其它因素掩盖算法本质
事前分析估算法 
    和算法执行时间相关的因素：
1．算法选用的策略
2．问题的规模
3．编写程序的语言
4．编译程序产生的机器代码的质量
5．计算机执行指令的速度
一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n
表示），或者说，它是问题规模的函数。
假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则
可记作： 
       T (n) = O(f(n))
称T (n) 为算法的(渐近)时间复杂度
算法 = 控制结构 + 原操作 
               （固有数据类型的操作）
从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在
算法中重复执行的次数作为算法运行时间的衡量准则 】

(XYS20041221)

◇◇新语丝(www.xys.org)(xys.dxiong.com)(xys.3322.org)(xys.freedns.us)◇◇