|
|
发表于 2004-4-4 17:48:42
|
显示全部楼层
最初由 top 发表
cozo 说得好 ！
从概念上来看，表是一种抽象数据类型；数组是一种具体的数据结构
从数学性质上来看，表是一个二元关系R，<x,y>∈R 当且仅当x是y的前驱；如果将该二元关系用关系图（将每一个元素用一个点来表示，若x与y有关系则从x到y连一条有向线段）来表示，则得到的是一条单链a1→a2→…→an ，因此表也可以看成是特殊的图或特殊的树（每个节点有且仅有一个子节点）；而数组是从1..n的自然数集合到数组元素集合的一一映射，其中n是数组的长度，1..n中每一个自然数唯一地对应着一个数组元素，反之亦然。所以数组可以用来实现映射。
从物理性质来看，数组中相邻的元素是连续地存储在内存中的，或者对于程序员来说可以认为它们是连续地存储在内存中的（比如动态增长的数组实际上并不存储在连续的内存中，但程序员可以认为它存储在连续的内存中），数组的存取对程序员来说是透明的；表只是一个抽象的数学结构，并不具有具体的物理形式，表需要通过其它有具体物理形式的数据结构来实现。在表的具体实现中，表中相邻的元素不一定存储在连续的内存空间中，除非表是用数组来实现的。对于数组，可以利用其下标在一个操作内随机存取任意位置上的元素；对于表，只能根据当前元素找到其前驱或后继，因此要存取第i个位置上的元素，一般不能在一个操作内实现，除非表是用数组实现的。在实现表时需要提供足够的信息以便能够通过表中元素的位置p来存取表中的元素。表中元素的位置p是指示表中元素位置的信息，通过对p进行处理（可能是从事某种函数运算计算出该元素在内存中的位置，也可能从表头开始，依次寻找当前元素的后继，重复i次找到第i个位置的元素）可以得到表中元素在内存中的物理位置，因此不能简单地将位置p理解为类似数组下标的自然数，实际上p可以是各种类型的变量，在数学上可将p定义为一个偏序集上的变量。在具体实现表及其运算时，应区分p与p所表示的位置，以及该位置上的元素三者之间的不同含义。
首先，先佩服一下你的离散数学水平，我已经望的差不多了。
但是，你不是要比较数组和链表么？这两个都是具体的数据结构的实现，表是数据抽象，和链表根本不是一个层面上的概念，是不应该混淆的。而所谓的动态增长数组，并不能说他是数组中的一种，他和传统的数组也不是一个层面上的概念，按照我的理解，他实际上代表着“基于数组实现的可变长线性表”。
至于链表和数组，只是对于线性表不同的实现罢了，他们可以实现完全相同的功能，但是算法的复杂度是不同的，我想任何一本讲数据结构的书都会对这一点有一个很详细的论述。至于抽象类型和实现的关系，我觉得看一下C++的<vector> <list> <deque>..会有一个很好的了解，它们的接口是类似的，但是对于某个特定的方法，时间复杂度不同，The C++ Programming Language,3/ed 在17.1.2小节有一张表，把这几个标准容器的接口时间复杂度比较的很清楚。
至于那个所谓“专业人士”讲得话，我觉得也没有什么好继续说的了吧。 |
|
IP卡
狗仔卡
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
楼主
)