我们数据结构版面准备编写一部数据结构的初级教程，初步设定读者对象为数据结构初学者和数据结构自学者。
我们希望这部教程即可以单独作为一本初级教程，又可以作为一本很好的参考书。
当然最主要的是对您学习数据结构有所帮助。
对于同一个例子，我们将用C/C++两种语言格式分别进行编写，以消除程序语言方面的障碍。
我们使用统一的编译器VC++6.0，我们保证我们所列出的每一个程序都是能够正常运行的。
不过由于工作量很大，所以并不期望短期内完成。

************************************

绪论
======================



预备知识
-----------------------------------

在开始学习数据结构之前，请您先确保如下几点：

1. 至少掌握了一门编辑语言（C/C++，JAVA，VB等），当然我们推荐您在学习数据结构前先掌握好C/C++，相对来说用这两种语言学习数据结构会更容易些，我们的教程也是基于这两种语言的。

2. 如果您使用的是C/C++语言，那么请您温习一下C中的结构体或C++中的类的相关章节，确保您能熟练的使用C中的结构体或C++中的类进行编程，在以后的学习中，您会发现这是多么的重要，数据结构中几乎所有的程序实现都离不开结构体或是类的运用。

3. 我们强烈要求在您的手边至少要有一只能写字的笔和一张能用于演算的纸。您不应期望像读小说一样来读数据结构中出现的算法和相关程序，如果抱有这样的想法，就很难理解算法的进程。学习算法的最好方法就是尝试它。您应当纸笔不离手，并在遇到算法时，立即在纸上进行算法的推演，比如您可以假定一个合理的数据，并用这个算法来处理这个数据，那么这个数据会怎样变化，会依次经历算法中的哪些步骤，最后会输出一个怎样的数据，这都是您需要了解的。事实上，这非常的重要，并不限于数据结构。如果您想更深入的学习编程技术，从而摆脱菜鸟阶段，这种方法是必须掌握的。

4. 我们希望您能明白这一点，相对于程序，数据结构更加注重算法，算法才是数据结构的重点。对于初学者来说，通过编程来理解算法的思想是最好的方法，因此编程在数据结构中占了不小的比例。然而，有人因此认为编程才是重点，并在编程的问题上喋喋不休，这就舍本逐末了。数据结构不是来教您怎样编程的，那是C/C++语言老师的任务。在数据结构中程序只是让您更加理解算法的一个途径。当然，我们会在每一个重要的算法后面贴上相关的能够运行的程序范例，但我们希望您能单独完成它，这说明您已经掌握了这种算法。





数据结构及其基本概念
-----------------------------------------

什么是数据结构？在回答这个问题前，我们得先弄清楚什么是数据。

数据（Data），是对客观事物的符号表示，它是具体的，可以被量化处理的。比如说住在一栋宿舍内的所有的人（后面的例子以此为基础）。在计算机科学中指的是所有能输入到计算机中并能被计算机程序处理的符号的总称（如数字，图象，声音等等）。

数据元素（Data Element）是数据的基本单位，就像宿舍内的一间寝室，在计算机程序中通常作为一个整体进行考虑和处理。一般情况下它是由若干个数据项组成。

数据项（Data Item）是数据的不可分割的最小单位，就像住在宿舍内的一个人，再分割可就得把人大卸八块了，那可是杀人罪啊。

数据对象（Data Object）是性质相同的数据元素的集合，是数据的一个子集，比如说一栋宿舍内的第二楼的所有的人。

那什么是结构呢？

结构（Structure），是指数据元素相互之间的关系，就像整个宿舍楼的建筑构造布局一样，在任何问题中没有数据元素是孤立存在的。当然，这里的结构指的是数据结构研究范围内的结构。

那么什么是数据结构呢？数据结构就是那栋宿舍楼。
数据结构是指同一类数据元素中各个数据元素之间存在的关系。

*******************************************

小知识

对于数据结构这个概念，至今国际上并没有一个同意精确的说法。不同的人在不同的环境下在使用这个词时表达的意思有所不同。通常情况下它指的是数据的存储结构，即同一类数据元素中各个数据元素之间存在的关系。但有时候也被诠释为具有某种结构关系的数据，即相互之间存在一种或多种特定关系的数据元素的集合。我个人倾向于前一种说法，当然，你也可以将其理解为数据及其结构，这样可能更加完善，更加明白些。

*******************************************

根据元素之间的相互关系， 通常有下列4种基本结构：

（1）集合。
该结构中的所有数据元素均独立存在，与其他数据元素之间是“鸡犬之声相闻，老死不相往来”，除了“在同一个结构里”这个关系之外就没有任何其它关系了。既然没有关系，那么就不在我们的研究范围之内了，本教程自然也不会去招惹他了。虽然刚见面，还是对它说再见吧。
//插图

（2）线形结构。
该结构中的数据元素之间存在且只存在一对一的关系。不太好理解？我也觉得有点，举个例子：就像幼儿园的小朋友玩“开火车”的游戏一样，第二个拽着第一个，第三个拽着第二个--------排成一长条，这就是一个典型的线形结构。什么？你没上过幼儿园？那就拿火车来说吧，像火车的车厢那样，一个拉一个，拉成一长条，也是一个典型的线形结构。什么？你没见过火车？！￥#￥%#……%*
//插图

（3）树形结构。
//插图

（4）图形结构和网壮结构
//插图

本部分未完待序

[此贴子已经被作者于2006-8-4 19:07:58编辑过]

算法

--------------------------------------------

算法是贯穿在所有计算机程序设计中的一个基本概念。
算法（Algorithm），顾名思义，计算方法，是从“算术”（Algorism，指用阿拉伯数字进行算术运算的过程）一词演变而来。在1950年的时候，算法一词经常和欧几里得的数学联系在一起，我们就以其著名的“求两个数的最大公因子”这个问题为例，来详细地了解下算法。

算法：给定两个正整数m和n，求它们的最大公因子（也叫最大公约数，最大公因数），即能够同时整除m和n 的最大正整数。

1.  r=m%n （r为n除m所得的余数）
2.  if r=0 . 算法结束，n即为答案
     else    m=n , n=r , 返回步骤1

当然，欧几里得肯定不是这样给出他的算法的，上面的算法也可以这样写：

1.  以n除m并令r为所得余数
2.  若 r的值为0  ，算法结束 ，n即为答案。
     否则，先将n的值赋给m，再将r的值赋给n，并返回步骤1

如果文字看着不习惯，也可以写成伪码：

int  func ( int m , int  n)
{
    //求m和n的最大公因子
    int r = m % n ;
    if ( r = 0 )
        return n ;
    else
        func ( n , r );
} 

上面给出的三种算法都是合法的， 之所以这样大费周张的列出来，是希望大家能够了解，算法并非一定要用伪码写出来，用文字或文字+伪码都可以。有时侯为了直观，我们还可以用流程图来表示算法：
//插入图片
总之，无论用哪种形式来表示一个算法，最重要的是要能让人很容易就能理解你的算法而不产生误解。

*****************************************

小技巧

有时候我们会遇到下面这样的一种格式：

int func ( int m , int  n)
{
   for ( i=0 ; i<=n ; i++ )  
    {
        y=y+1;   //  频度为 n
        for ( j=0 ; j<=2*n ; j++ )  
        {   
            x++;     
        }  // for
    }  // for
}  // func()

兰色的部分有什么用呢？对于一个比较小的程序来说，整个程序层次关系一目了然，这样的标示可能用处不大。但对于一个大型程序来说，经常会出现大量的嵌套，而且一个函数可能有几页的长度，如果只用眼睛观察的话程序的层次关系很难判断准确，这时这种标示就显得尤为重要了。每结束一个循环或嵌套就标示一次，来达到明确程序层次的目的，也方便了程序的调试，这样在很大程度上防止了程序出错，对大型程序来说尤为重要。因此养成合理使用标示的习惯是有必要的。

******************************************

关于算法的形式就讲这些，现在让我们来执行一个算法。应当立即提到，读者不应期望像读小说一样来读算法，如果抱有这样的想法，就很难理解算法的进程。算法应该是可信的，而学习算法的最好方法就是尝试它。读者应当笔纸不离手，并在课文中遇到算法时，立即运行算法的一个例子。通常我们都会给出一个有效实例的要点，要不读者也能很容易地想出一个例子。这是理解一个给定算法的简单而轻松的方法，所有其他方法一般来说都是不成功的。

因此现在让我们来考察一下“求最大公因子”的算法，就以下面这个算法为例

1.  r=m%n （r为n除m所得的余数）
2.  if r=0 . 算法结束，n即为答案
     else    m=n , n=r , 返回步骤1 

假定m=119,n=544; 我们现在已经准备好从步骤1开始。在此情况下，m除以n 十分简单，简直太简单了。因为商为0而余数为119。 因此r=116. 我们进行到步骤2。而由于 r != 0 ，因此 m =544, n=119 .显然，如果原来m<n, 步骤1中的商将总为0，因此算法在这种相当讨厌的方式下总是进行m和n的交换。 我们可以增加一个新的步骤0：

0. if ( m < n ) m<->n //交换m和n的值

这在算法中不产生任何实质性的改变，只是稍微增加了算法的长度，却在大约一半的情况下减少了其运算时间。
一不小心， 我们就成功的改进了这个算法，这也是我们学习数据结构的重要的目的之一，怎样让算法或程序最优化。
怎么样，这个小小的成功是否让你对学好数据结构充满了信心呢？

回到步骤1，我们发现 544 / 119 = 4 + 68 / 119 ，因此 r = 68 , 在步骤2 ， m=119, n=68 . 下一轮置 r=51. 最终 m=68, n=51. 其次 r=17 且 m = 51 , n = 17. 最后当51为17整除时，置 r = 0 , 算法结束，119和544的最大公因子为17。

这就是一个算法。一个算法不过是一组有穷的规则，这些规则给出求解特定类型问题的运算序列。因此我们给出算法的定义：

算法是解决某一特定类型问题的有限运算序列。

同时我们可以看到算法还具有5个重要特征：

（1）有穷性。一个算法在有限步骤之后必然要终止。

（2）确定性。一个算法的每个步骤都必须精确地定义；要执行的动作每一步都必须严格地和无歧义地描述清楚。

（3）输入。 一个算法有零个或多个输入，即在算法开始之前最初赋予它的量，或当算法运行时动态地赋给它的量。这些输入是从特定的对象集合取出的。例如，在上面的“求最大公因子”的算法中，有两个输入，即m和n，两者都是从正整数集合取出来的。

（4）输出。 一个算法有一个或多个输出：和输入有特定关系的量。“求最大公因子”的算法中有一个输出。

（5）可行性。 一个算法一般可以认为是可行的（或有效的），其含义是指它的所有运算必须是充分基本的，因而原则上人们用纸和笔都可以在有限的时间内精确的完成它们。

评价一个算法的好坏一般是从4个方面进行的：正确性，可读性，稳健性和算法的效率。前3个就不用我解释了吧，而对于算法的效率则是通过算法的时间复杂度和空间复杂度来描述的。

[此贴子已经被作者于2006-8-4 19:18:57编辑过]

时间复杂度和空间复杂度

------------------------------------------

算法的时间复杂度是衡量一个算法好坏的重要指标。
所谓时间复杂度是指算法中包含简单操做次数。一般以数量级的形式给出。
如O（1），O（log ₂ n），O（n），O（n ² ）等。括号内便是它所在的数量级。
对于O（ f ( n ) ），这只是个非常模糊的概括性的表示，如果别人问你某个具体算法的时间复杂度，把这个拿出去肯定会被人笑话的。
而对于某个简单操作次数的精确数值，我们称它为这个简单操作的频度。
换句话说，语句的频度指的是该语句重复操作的次数。
一个算法中所有的语句频度之和构成了该算法的运行时间。
而对该算法的运行时间求极限，得到的结果就是算法的时间复杂度。

下面我们就举个例子来看看如何计算时间复杂度。

分析下面程序的时间复杂度

for ( i=0 ; i<=n ; i++ )  //  频度为n+1
{
    y=y+1;   //  频度为 n
    for ( j=0 ; j<=2*n ; j++ )     //  频度为 n*( 2n+1 )
        x++;     //  频度为 n*( 2n+1 )
}

所以该程序的时间复杂度为
T ( n ) = ( n+1 ) + n + n * ( 2n + 1 )+ n * (  2n + 1 )  
        = 4n 2 + 5n + 1   //  对这个表达是求极限（n 趋近无穷大时），得到 4n 2 ， 他的数量级为 n 2
        = O ( n 2 )

空间复杂度的定义和时间复杂度相近， 它作为算法所需存储空间的量度，主要考虑在算法运行过程中临时占用的存储空间的大小，一般以数量级的形式给出。

[此贴子已经被作者于2006-8-4 17:45:08编辑过]

为什么要学习数据结构？

-------------------------------------------------------

这个问题问的好。
数据结构并不是来教你怎样编程的，同样编程语言的精练也不在数据结构的管辖范围之内，那是教你学习一门语言的老师的事情，他肯定不想因为数据结构而失业。数据结构是教你如何在现有程序的基础上把它变得更优（运算更快，占用资源更少），它改变的是程序的存储运算结构而不是程序语言本身。
如果把程序看成一辆汽车，那么程序语言就构成了这辆车的车身和轮胎。而算法则是这辆车的核心——发动机。这辆车跑得是快是慢，关键就在于发动机的好坏（当然轮胎太烂了也不行），而数据结构就是用来改造发动机的。
可以这么说，数据结构并不是一门语言，它是一种思想，一种方法，一种思维方式。它并不受语言的限制，你完全可以在gave 中轻而易举地实现一个用C语言给出的算法。


//--------------------------------------------------
以下是引用热情依然的发言：

数据结构就是编程的思维，编程的灵魂，算法的精髓所在，没有了数据结构，程序就好像一个空核，是低效率的。学习数据结构的目的就是提高自己的思想，数据结构的高低是确定于你写的程序的运行效率，想不想到奇异的方法解决问题，程序的壮健性，并不是你记得多少算法。就好像我现在排序算法已经忘记了很多，平衡二叉树的建立跟删除，图论完全忘记。难道这样我就是初学者？？肯定不是，自要有思想在，有些算法用到的时候看看书就可以了。记住，想成为高手，数据结构一定要强。

//--------------------------------------------------
以下是引用starrysky的发言：

数据结构就是教你怎样用最精简的语言，利用最少的资源（包括时间和空间）编写出最优秀最合理的程序。
换句话说数据结构存在的意义就是使程序最优化。所以学习数据结构需要有一定的基础知识。用伪码表示，是因为写原代码太长，而且有时不利于理解（光是设顶的一大堆变量就让人眼花缭乱的）。数据结构不是教你怎样才能编程，而是教你怎样才能编好程，所以很多地方只需要让读者知道该怎么编就行，用汉字表达都行，原代码就让读者自己去解决，这不仅方便读者理解，而且留给了读者一个思考的空间，对于作者来说也可以节省大量写原代码的时间。

//--------------------------------------------------




怎样学好数据结构？

------------------------------------------------------

//------------------------------------------------
以下是引用可可的眼的发言：

总觉的学习数据结构有中空空的感觉，能告诉我怎么才能学好数据结构吗？？ 而且让数据结构和其他课程联系起来吗？

//------------------------------------------------
以下是引用热情依然的发言：

或者你现在还不明白，但是只要你认真学下去，当你以后用MFC，C++来写项目的时候，你就会因为当初学好数据结构，想到好的方法解决问题而庆幸。想当初我是多么的热爱数据结构，可惜现在没有时间再去研究，做完毕业设计我到要重新复习一次。每次复习都会提升很多的。你初初学的时候建议你先不要理会什么空间复杂度，时间复杂度什么的，弄明白条程序怎样运行就好，建议你去买朱站立出的数据结构，有整条程序可以给你看的，又容易学。那些程序完全可以运行的，你可以先看书敲程序，明白了之后再自己写出来，那就可以锻炼你的基础。关于时间复杂度，空间复杂度那些如果你不是打算做游戏，研究高性能算法，我觉得没有必要要那么深入研究。只要可以完全明白书上的算法，你的编程思维已经提高很多，甚至高级程序员都可以过，顺便提醒一下，看完数据结构之后顺便学下离散数学。这样思维才会更加强劲
顺便提醒一下，初学数据结构我觉得用C++或者C语言会容易一点

//-------------------------------------------------
以下是引用可可的眼的发言：

现在对数据结构的课堂上或者书本上的东西还是能接受的，也不算难，可是就是当要用C语言原程序的实现的时候总是出错，是不是实践太少，经验不够啊！~！~！~！~！~！~

//-------------------------------------------------
以下是引用热情依然的发言：

这个肯定是拉，建议用谭浩强的《C语言程序设计>>补习一下

//-------------------------------------------------
以下是引用starrysky的发言：

这个嘛, 一是说明你C语言基础不够扎实(理论应该够了,主要指实践方面), 第2嘛, 可能没有很好的理解伪码和原代码之间的区别,把伪码当原代码用了. 有很多书上的程序, 看起来象是原代码, 实际上为了保持程序的可读性, 里面省略了些基本的却有点烦琐的代码, 结果无法运行. 如何去补齐, 就要看个人的经验了. 我同意热情的看法, 实践才是王道. 你可以从最简单的程序开始做起, 最好先温习下C语言的一些知识.

//------------------------------------------------------





数据结构有哪些好的参考书？

------------------------------------------------------


<<数据结构vc++程序集>>
<<数据结构导引>>
<<数据结构与算法>>高等教育出版社,作者是张铭
《数据结构实用教程(C/C++描述)》——徐孝凯 清华大学出版社 2003版 29元
<<程序设计实践>>
《算法导论》

[此贴子已经被作者于2006-8-4 19:09:41编辑过]