【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

本章小结:


目录
打赏
0
1
0
0
27
分享
相关文章
数据结构-顺序表详解(看这篇就足够了,哈哈哈)
数据结构-顺序表详解(看这篇就足够了,哈哈哈)
92 2
【C++数据结构——线性表】顺序表的基本运算(头歌实践教学平台习题)【合集】
本文档介绍了线性表的基本运算任务,涵盖顺序表和链表的初始化、销毁、判定是否为空、求长度、输出、查找元素、插入和删除元素等内容。通过C++代码示例详细展示了每一步骤的具体实现方法,并提供了测试说明和通关代码。 主要内容包括: - **任务描述**:实现顺序表的基本运算。 - **相关知识**:介绍线性表的基本概念及操作,如初始化、销毁、判定是否为空表等。 - **具体操作**:详述顺序表和链表的初始化、求长度、输出、查找、插入和删除元素的方法,并附有代码示例。 - **测试说明**:提供测试输入和预期输出,确保代码正确性。 - **通关代码**:给出完整的C++代码实现,帮助完成任务。 文档
96 5
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
【数据结构】顺序表(c语言实现)(附源码)
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列,常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构,其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别,并重点介绍了动态顺序表的实现,包括初始化、销毁、打印、增删查改等操作。最后,文章总结了顺序表的时间复杂度和局限性,并预告了后续关于链表的内容。
145 3
|
5月前
|
数据结构第二篇【关于java线性表(顺序表)的基本操作】
数据结构第二篇【关于java线性表(顺序表)的基本操作】
74 6
|
5月前
|
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
44 3
|
5月前
|
探索C语言数据结构:利用顺序表完成通讯录的实现
本文介绍了如何使用C语言中的顺序表数据结构实现一个简单的通讯录,包括初始化、添加、删除、查找和保存联系人信息的操作,以及自定义结构体用于存储联系人详细信息。
73 2
|
5月前
|
【数据结构】线性表和顺序表
【数据结构】线性表和顺序表
48 1

热门文章

最新文章

  • 1
    局域网屏幕监控系统中的Python数据结构与算法实现
    141
  • 2
    2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
    60
  • 3
    2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    54
  • 4
    2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    56
  • 5
    2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    77
  • 6
    2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    45
  • 7
    2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    82
  • 8
    2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    46
  • 9
    2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    56
  • 10
    2024重生之回溯数据结构与算法系列学习【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    55
  • AI助理

    你好,我是AI助理

    可以解答问题、推荐解决方案等