一、顺序表的插入
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
本章小结: