【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

本章小结:


相关文章
|
20天前
|
存储 编译器 C语言
数据结构-顺序表详解(看这篇就足够了,哈哈哈)
数据结构-顺序表详解(看这篇就足够了,哈哈哈)
46 2
|
1天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
1天前
|
存储 C语言
【数据结构】顺序表(c语言实现)(附源码)
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列,常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构,其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别,并重点介绍了动态顺序表的实现,包括初始化、销毁、打印、增删查改等操作。最后,文章总结了顺序表的时间复杂度和局限性,并预告了后续关于链表的内容。
10 3
|
1天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
21天前
|
存储 Java
数据结构第二篇【关于java线性表(顺序表)的基本操作】
数据结构第二篇【关于java线性表(顺序表)的基本操作】
27 6
|
21天前
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
20 3
|
21天前
|
存储 C语言
探索C语言数据结构:利用顺序表完成通讯录的实现
本文介绍了如何使用C语言中的顺序表数据结构实现一个简单的通讯录,包括初始化、添加、删除、查找和保存联系人信息的操作,以及自定义结构体用于存储联系人详细信息。
18 2
|
24天前
|
存储 算法 索引
【数据结构】——顺序表
【数据结构】——顺序表
|
24天前
|
存储
【数据结构】线性表和顺序表
【数据结构】线性表和顺序表
20 1
|
26天前
|
存储
数据结构1——顺序表
数据结构1——顺序表
17 1