数据结构之顺序表实现2.1

1.大纲：抽象数据类型表的基本概念及其逻辑特征。实现抽象数据类型表的一般步骤及常用实现表的方法。

2.定义：线性表是具有相同特性数据元素的一个有限序列。

【注】：相同特性是把同一类事物归类，方便批量处理。

3.逻辑特征：只有一个表头，只有一个表尾，表头没有前驱，表尾没有后继。

4.存储结构对比：

⑴顺序表：随机访问特性，会占用连续的存储空间。

⑵链表：不支持随机访问，结点存储空间利用率较顺序表稍低一些。

5.链表5种形式：单链表，双链表，循环单链表，循环双链表，静态链表。

6.对顺序表插入的时间复杂度分析：

数列｛1，2，3…n-2,n-1,n｝的一个顺序表中进行操作，插入一个元素的平均移动个数？

①求概率：插入位置的随机性，n个可插入位置，p=1/n.

②求插入需要移动元素：第i个元素插入之后，所有元素将往后移动一个位置，因此，移动元素个数为n-i.

总的移动数：n-1+n-2+n-3+……+n-(n-1)+n-n=n*n-(1+n)n/2

数学期望E=p*[ n*n-(1+n)n/2]=(n-1)/2

要移动近一半的元素，时间复杂度O（n）。

7.顺序表的五大必备操作：

①初始化顺序表的算法

②求指定位置元素的算法（返回L p位置上的元素）

③按元素查找（查出第一个e的元素）

④插入（在第p个元素后插入元素e）

⑤删除（删除第p个元素）

综合代码示例（可以左右滑动）

ps：代码总结自网络及严版数据结构。时间太紧，就不在意文章排版了，内容虽少，但一篇文章耗时也是不少，可能有点得不偿失了，我一直希望能用c来将数据结构部分的代码实现一遍，可惜能力有限，bug多多，下次更的时间从来未定，但是我肯定会尽量压缩时间，加快复习进度，下次见，我是潇雷，晚安。