什么是数据结构

例1：如何在书架上摆放图书

问题：空间如何分配？类别应该分多细？

递归函数跑出来的结果，前面100000是输入，它什么都没做，直接罢工了。到底发生了什么？递归程序对空间的占用是很恐怖的。。。

为什么说第二种算法比第一种要好呢？因为第一种算法慢很多

这两个函数跑的实在是太快了，解决方法就是在循环中重复多跑几次

第一个算法比第二个算法慢了一个数量级的样子

 

 

什么是逻辑结构，比如说我们一开始把书架想象成一个一长条一层的架子，然后所有的书是一个挨着一个放的，除了一头一尾的书以外呢，每一本书它前面只有一本书，后面只有一本书，如果我给每一本书有一个编号的话，那么这一个编号对应的就是一本书，那么这种结构呢是一对一的结构，我们管它叫线性结构，另外一种组织方式，是我们的第三个方法，就是先把图书来分类，那如果我给每一类一个编号的话，那么这一个类别的编号里面对应着很多本书，那么这是一个一对多的逻辑结构，那这种结构有个名字叫作树，树(一对多)，前面讲的就是线性结构和树型结构。后面就会讲图，假设我们还会统计这些信息，这本书都会有哪些人买过？买了这本书的人他还买过其它的什么书？于是呢，其实就是一本书对应着很多人，而一个人又对应了很多本书，这是一个多对多的很复杂的关系网，那么这个关系网对应的就是一个图的结构，除了逻辑结构之外，我们还有数据对象在计算机里面的物理存储结构，我们说的这些逻辑结构在机器的内存里面到底要怎么样一个放法，是连续放呢？还是东一个，西一个隔开放呢？也就是用一个数组来存它呢？还是用一个链表来存它呢？这个就属于物理存储结构

数据对象集就是我们在说的什么东西，第二个是数据集合相关联的操作集，就像我们说不能单纯的讲怎么去处理图书，我们是要对这些图书去做操作的，这两件事情，图书的摆放跟它的操作是紧密结合在一起的，那么这两个东西在C语言里头，它们是独立处理的，但是在一些面向对象的语言里面，你就会发现它们很好的为数据类型专门设计了机制，就是一个类把数据集跟它相关的操作集封装在一个类里面

在描述数据对象集的时候，我们说a是矩阵元素的值，这个值是个什么值呢？它是一个float,还是一个double,还是int,我们在抽象数据类型描述中间是不关心的，相应的当需要对它的元素值进行操作的时候，我们返回的也是ElementType,实现的函数跟矩阵元素到底是哪种类型是没有关系的，哪种类型都是可以做运算的，就避免了你对int实现了一遍，又要对double重新写一遍，当然说可以将所有的int全部换成double, 但有些时候的int是真的int,不能换成double,所以就很有可能出错，总的来说，就是一个一个的去替换元素的类型的话，会是一件很麻烦的事情，而抽象一下就是有这个好处，这是一个地方的抽象，另外像这个矩阵，我们只是说M*N的矩阵，至于在程序里面怎么样一个存法，我们是用二维数组去存它，还是一维数组，还是十字链表，这个我们在抽象数据类型定义的时候，都是不关心的，我不管它是怎么实现的，我只是说我要实现的是一个矩阵，另外我在描述这个Add,矩阵加法这个函数的时候，我只是说如果它们可以相加的话，我要返回它们的和，那我可没说在算矩阵加法的时候，到底是先按行加，还是先按列加，我到底是用什么语言去实现？通通不管，这就是所谓的抽象。