【408数据结构与算法】—顺序表的插入、删除和查找（四）
一、顺序表的插入
ListInsert（&L，i,e）：插入操作。在表L中的第i个位置上插入指定的元素e.
二、插入操作的代码实现
三、插入操作的时间复杂度
- 最好的情况：新元素插入到表尾，不需要移动元，i=n+1,循坏0次，最好的时间复杂度：o(1)
- 最坏的情况：新元素插入到表头，需要将原有的n个元素全都向后移动，i=1,循坏n次，最坏的时间复杂度：o(n)
- 平均情况：假设新元素插入到任何一个位置的概率相同，即i=1,2,3,……length+1的概率p=1/n+1
四、顺序表的基本操作—删除
五、删除操作的时间复杂度
- 最好的情况:删除表尾元素，不需要移动其他元素 i=n,循环0次，最好的时间复杂度为O（1）。
- 最坏的情况：删除表头元素，需要将后续的n-1个元素全部向前移动 i=1,循坏n-1 次，最坏的时间复杂度为O(n)。
-
平均情况：假设删除任何一个元素的概率相同，即i=1,2,3,4,……length的概率都是p=1/n
i=1，循坏n-1次，i=2，循坏n-2次，i=3,循坏n-3次，……i=n时，循坏 0 次。
本章知识点回顾
六、顺序表的查找
GetElem(L ,i):按位查找操作，获取表L中第i个位置的元素的值
由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第i个元素—随机存取的特性
按位查找的时间复杂度：O(1)📢LocateElem（L,e）：按值查找，在表L中查找具有给定关键字值的元素
🎇结构类型的比较
Tips:《数据结构》考研初试中，手写代码可以直接用
“==”
，无论ElementType是基本数据类型还是结构类型，手写代码主要考察学生是否能理解算法思想，不会严格要求代码完全可运行。有的学校考C语言程序设计，那么或许语法就会严格一些
按值查找的时间复杂度
- 最好情况：目标元素在表头 循坏1次：最好时间复杂度为O(1)
- 最坏情况：目标元素在表尾，循坏 n次最坏的时间复杂度为O(n)
- 平均情况：假设目标元素出现在任何一个位置的概率都相同，都是 1/n