抽象数据类型

研究一个简单的数据结构，先定义为抽象数据类型，然后看可能的实现方式。

列表的 ADT 定义(只定义要存的数据和可用的操作)

list

• store a given number of elements of a given data-type(隐含了静态，数量在创建之前已经直到)

• 能写或修改任意位置的元素

• 能读特定位置的元素

数组具备以上所有特性，涉及到编程细节了

int a[10];
a[i] = 2;
printf("%d", a[2]);

数组是一个具有以上特性的列表。

现在想要一个具有更多特性的列表以应对更多的情况。重新定义一个动态长度的 ADT

• 空列表的长度为 0 (empty list has size 0)

• 可以向任意位置插入列表

• 可以移除元素

• 能计算列表中元素数量

• 读取/修改指定位置的元素

• 指定列表的数据类型

可以基于数组实现这样一种数据结构，只不过需要实现更多的操作以提供这些功能。

int array[MAX_SIZE];    /**/
int end = -1;           /* 标记末尾 */

void insert(int loc, int val);  /* 插入操作 */
void remove(int loc);           /* 插入操作 */

插入和删除伴随着元素的移动。

更多的细节考虑：数组的规模，数组满的情况下需要有应对策略，需要将其纳入设计之中。数组长度是无法扩展的，那就得创建一个更大的数组，并将上一个数组的内容完整的复制过去。

问题是新数组的大小应该是多少？一个简单的策略，上一个数组长度 * 2。而且是也是一个最佳策略。

复制的过程需要花很多时间，一个良好的实现应该考虑避免这么大的开销。

此外还要研究操作花费的时间成本。

• 读写花费恒定时间，O(1)

• 末尾花费时间 O(1)

• 任意位置插入最坏情况 O(n)

• 删除也是 O(n)

如果数组已满，插入元素的时间 O(n)，最坏情况

这种实现方式子啊内存方面效率不高。