【408数据结构与算法】—顺序表的插入、删除和查找（四）

【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
  

本章小结：