数据结构复习指导之顺序表上基本操作的实现(插入、删除、查找)

文章目录

顺序表基本操作实现

知识总览

1.顺序表的初始化

1.1静态分配顺序表的初始化

1.2动态分配顺序表的初始化

2.插入操作

2.1插入操作流程

2.2插入操作时间复杂度

3.删除操作

3.1删除操作流程

3.2删除操作时间复杂度

4.查找操作

4.1按位查找

4.2按位查找时间复杂度

4.3按值查找(顺序查找)

4.4按值查找时间复杂度

知识回顾与重要考点


顺序表基本操作实现

知识总览

注意

在各种操作的实现中(包括严蔚敏老师撰写的教材),往往可以忽略边界条件判断、变量定义、内存分配不足等细节,即不要求代码具有可执行性,而重点在于算法的思想。

1.顺序表的初始化

静态分配和动态分配的顺序表的初始化操作是不同的

1.1静态分配顺序表的初始化

静态分配在声明一个顺序表时,就已为其分配了数组空间,因此初始化时只需将顺序表的当前长度设为0。

//SqList L;                   //声明一个顺序表
void InitList(SqList &L){
 
     L.length=0;              //顺序表初始长度为0
                            
}

1.2动态分配顺序表的初始化

动态分配的初始化为顺序表分配一个预定义大小的数组空间,并将顺序表的当前长度设为0。MaxSize指示顺序表当前分配的存储空间大小,一旦因插入元素而空间不足,就进行再分配。

void InitList(SeqList &L){
    L.data= (ElemType *)malloc (MaxSize*sizeof(ElemType));    //分配存储空间
    L.length=0;             //顺序表初始长度为0
    L. MaxSize=InitSize;    //初始存储容量
}

2.插入操作

2.1插入操作流程

在顺序表L的第i(1<=i<=L.length+1)个位置插入新元素e。

若i的输入不合法,则返回false,表示插入失败;

否则,将第i个元素及其后的所有元素依次往后移动一个位置,腾出一个空位置插入新元素e,顺序表长度增加1,插入成功,返回true。

bool ListInsert(SqList &L,int i,ElemType e){
    if(i<1|i>L.length+1)            //判断i的范围是否有效
        return false;
    if(L.length>=MaxSize)           //当前存储空间已满,不能插入
        return false;
    for(int j=L.length;j>=i;j--)    //将第i个元素及之后的元素后移
        L.data[j]=L.data[j-1];
    L.data[i-1]=e;                  //在位置i处放入e
    L.length++;                     //线性表长度加1
    return true;
}

注意

区别顺序表的位序和数组下标。为何判断插入位置是否合法时if语句中用length+1,而移动元素的for语句中只用length?

2.2插入操作时间复杂度

最好情况:在表尾插入(即i=n+1),元素后移语句将不执行,时间复杂度为O(1)。

最坏情况:在表头插入(即i= 1),元素后移语句将执行n次,时间复杂度为O(n)。

平均情况:假设pi (pi=1/(n+1))是在第i个位置上插入一个结点的概率,则在长度为n的线性表中插入一个结点时,所需移动结点的平均次数为

\sum_{i=1}^{n+1}p_{i}(n-i+1)=\sum_{i=1}^{n+1}\frac{1}{n+1}(n-i+1)=\frac{1}{n+1}\sum_{i=1}^{n+1}(n-i+1)=\frac{1}{n+1}\frac{n(n+1)}{2}=\frac{n}{2}

因此,顺序表插入算法的平均时间复杂度为O(n)

3.删除操作

3.1删除操作流程

删除顺序表L中第i(1<=i<=L.length)个位置的元素,用引用变量e返回。若i的输入不合法,则返回false;否则,将被删元素赋给引用变量e,并将第i+1个元素及其后的所有元素依次往前移动一个位置,返回true.

bool ListDelete(SqList &L,int i, ElemType &e){
    if(i<1 || i>L.length)            //判断i的范围是否有效
        return false;
    e=L.data[i-1];                   //将被删除的元素赋值给e
    for(int j=i;j<L.length;j++)      //将第i个位置后的元素前移
        L.data[j-1]=L.data[j];
    L.length--;                      //线性表长度减1
    return true;
}

3.2删除操作时间复杂度

最好情况:删除表尾元素(即i=n),无须移动元素,时间复杂度为O(1)。

最坏情况:删除表头元素(即i=1),需移动除表头元素外的所有元素,时间复杂度为O(n)

平均情况:假设pi(pi =1/n)是删除第i个位置上结点的概率,则在长度为n的线性表中删除一个结点时,所需移动结点的平均次数为
\sum_{i=1}^{n}p_{i}(n-i)=\sum_{i=1}^{n}\frac{1}{n}(n-i)=\frac{1}{n}\sum_{i=1}^{n}(n-i)=\frac{1}{n}\frac{n(n-1)}{2}=\frac{n-1}{2}

因此,顺序表删除算法的平均时间复杂度为O(n)

可见,顺序表中插入和删除操作的时间主要耗费在移动元素上,而移动元素的个数取决于插入和删除元素的位置。

4.查找操作

4.1按位查找

4.2按位查找时间复杂度

4.3按值查找(顺序查找)

在顺序表L中查找第一个元素值等于e的元素,并返回其位序。
 

int LocateE lem (SqList L,ElemType e){
    int i;
    for(i=0;i<L.length;i++)
        if(L.data [i]==e)
            return i+1;        //下标为i的元素值等于e,返回其位序i+1
    return 0;                  //退出循环,说明查找失败
}

4.4按值查找时间复杂度

最好情况:查找的元素就在表头,仅需比较一次,时间复杂度为O(1)。

最坏情况:查找的元素在表尾(或不存在)时,需要比较n次,时间复杂度为O(n)。

平均情况:假设pi (pi=1/n)是查找的元素在第i (1<=i<=L.length)个位置上的概率,则在长度为n的线性表中查找值为e的元素所需比较的平均次数为

\sum_{i=1}^{n}p_{i}\cdot i=\sum_{i=1}^{n}\frac{1}{n}\cdot i=\frac{1}{n}\frac{n(n+1)}{2}=\frac{n+1}{2}

因此,顺序表按值查找算法的平均时间复杂度为O(n)。

知识回顾与重要考点

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/537537.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

NetBox4 安装指南-为网络工程师打造的基础设施管理(全面汉化)

介绍 NetBox 是用于建模和记录现代网络的领先解决方案。由 结合 IP 地址管理 &#xff08;IPAM&#xff09; 的传统应用和 具有强大 API 和扩展的数据中心基础架构管理 &#xff08;DCIM&#xff09;&#xff0c; NetBox 为推动网络自动化提供了理想的“事实来源”。 NetBox 在…

弹性云服务器性能对比(内附测试数据),快快网络服务器崭露头角

随着计算技术的不断革新&#xff0c;云服务器已成为企业和个人部署应用与服务的首选。尤其线上业务日益盛行的今天&#xff0c;云服务商的实力更是备受瞩目。对于企业而言&#xff0c;高稳定&#xff0c;存储速度都是不可或缺的基本要求&#xff0c;这些都对公有云的云端编解码…

阿里云服务器部署网站(图文详解)

一&#xff0c;准备工作 1.1&#xff0c;点击&#xff1a;注册阿里云账号 输入&#xff1a;账户名&#xff0c;登录密码&#xff0c;手机号。 1.2&#xff0c;域名注册和备案 详细请参考&#xff1a;阿里云域名购买流程和备案流程 1.3&#xff0c;准备服务器 详细请参考&a…

【QT入门】 Qt自定义控件与样式设计之QPushButton实现鼠标悬浮按钮弹出对话框

往期回顾&#xff1a; 【QT入门】 Qt自定义控件与样式设计之qss选择器-CSDN博客 【QT入门】 Qt自定义控件与样式设计之QLineEdit的qss使用-CSDN博客 【QT入门】Qt自定义控件与样式设计之QPushButton常用qss-CSDN博客 【QT入门】 Qt自定义控件与样式设计之QPushButton实现鼠标悬…

观察者模式:实现高效事件驱动编程的策略

在软件开发中&#xff0c;观察者模式是一种关键的行为型设计模式&#xff0c;用于建立对象间的一种依赖关系&#xff0c;使得当一个对象改变状态时&#xff0c;所有依赖于它的对象都会得到通知并被自动更新。这种模式是事件监听和响应编程的基石。本文将详细介绍观察者模式的定…

【JAVA基础篇教学】第十篇:Java中Map详解说明

博主打算从0-1讲解下java基础教学&#xff0c;今天教学第十篇&#xff1a;Java中Map详解说明。 在 Java 编程中&#xff0c;Map 接口代表了一种键值对的集合&#xff0c;每个键对应一个值。Map 接口提供了一系列操作方法&#xff0c;可以方便地对键值对进行增删改查等操作。本…

【汇编】_Visual Studio2019写32位汇编

目录 第一步&#xff1a;创建新项目 1. 空项目—下一步 2. 选择位置—填写项目名—创建 第二步&#xff1a;项目生成依赖项 1. 右击项目名—生成依赖项—生成自定义 2. 选中masm—确定 第三步&#xff1a;创建源文件 1. 源文件—添加—新建项 2. 选择C文件—创建新文件…

数据库被rmallox勒索病毒加密,如何还原?

近年来&#xff0c;网络安全问题日益严峻&#xff0c;勒索病毒作为其中的一种恶意软件&#xff0c;已成为网络安全领域的一大难题。其中&#xff0c;rmallox勒索病毒以其高度的隐蔽性和破坏性&#xff0c;给不少企业和个人带来了严重损失。本文将从rmallox勒索病毒的特点、传播…

Unity-超级方便的Excel 读写插件

超级无敌棒棒糖&#x1f58c; &#x1f32d;功能介绍&#x1f355; Demo&#x1f333;准备一个数据类&#x1f333;准备一个Excel&#x1f333;导入Excel&#x1f333;行数据自动转换&#x1f333;导出到Excel &#x1f371;新增映射字段类型 &#x1f32d;功能介绍 &#x1f…

监控系统泛滥:CTO 面临的隐形成本危机

在信息技术飞速发展的今天&#xff0c;构建和维护现代化的数字系统变得日益复杂和关键&#xff1b;在这样的背景下&#xff0c;监控系统的作用变得尤为突出。正如业界广泛流传的一句经验之谈“无监控&#xff0c;不运维”所揭示的道理一样&#xff0c;对于任何具有一定复杂性的…

进程程序替换

文章目录 程序替换原理替换函数函数解释调用举例 程序替换原理 用新进程的代码和数据覆盖旧进程的代码和数据&#xff0c;没有创建新进程&#xff0c;用旧进程的壳执行了新进程。 站在被替换进程的角度&#xff1a;本质就是程序从磁盘加载到了内存。 怎么加载呢&#xff1f;…

【电控笔记6】电流回路+延迟效应

问题提出 数字控制系统的delay: 5.4节有介绍T0=0.5TS 低通滤波器的时间常数? 可用示例程序 m2 2 1b 如下图画出开环系统的伯德图进行比较,如图 2-2-4 所示,由于延迟组件会侵蚀系统的相位,因此从图可以看出,加入延迟效应后,q轴电流回路的相位裕度(Phase Margin) 从…

【数据结构】单链表(二)

目录 1.查找数据 2.指定位置插入和删除节点 2.1 指定位置之前插入节点 2.2 指定位置之后插入节点 2.3 删除指定位置节点 2.4 删除指定位置之后的节点 3.销毁链表 我们接着上一篇【数据结构】单链表&#xff08;一&#xff09;-CSDN博客 来继续实现单链表 1.查找数据 在…

c# wpf datagrid 简单试验

1.概要 datagrid 一个列表类的控件 2.代码 <Window x:Class"WpfApp2.Window3"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d"http://schemas.mic…

关于 STM32WL LSE 添加反馈电阻后无法起振问题

1. 问题描述 客户调试 STM32WLE5JB 样机的时候遇到这样一个问题&#xff1a;在调试 LPUART&#xff0c;不打开外部时钟的时候&#xff0c;能够正常打印&#xff0c;若开启外部的 HSE 和 LSE 后就没有打印。 2. 问题确认 发现上述问题时&#xff0c;客户使用 STM32CubeMX 生成…

数字图像处理项目——模糊图像边缘检测算法设计及实现(论文/代码)

完整的论文代码见文章末尾 以下为部分内容 摘要 本研究旨在针对大脑核磁图像中的黑色腔体进行有效分割&#xff0c;以提供可靠的腔体定位和分析。为此&#xff0c;采用了三种常用的图像分割方法&#xff1a;8邻域区域生长法、Canny算子边缘检测和8邻域边界跟踪法。 首先&…

ES13:类的新增特性、最外层的await、at...

1-类的新增特性 类私有属性和方法&#xff1a;# class Person{// 不需要传参、一开始就需要初始化的&#xff0c;就可以在类的最外面直接声明这个成员state{a:1,b:2}constructor(name,age){this.namename;this.ageage;}}在属性和方法前加#表示私有 #obj{} #prest(){}静态成员…

数据结构--链式栈

一.链式栈的栈顶在哪里? 二.链栈的结构: typedef struct LSNode{ int data; struct LSNode* next; }LSNode ,*PLStack; //链栈的节点.由于栈顶在第一个数据节点,所以不需要top指针 三.链式栈的实现: //初始化LSNode* p (LSNode*)malloc(sizeof(LSNode));assert(p ! NULL)…

C语言调用Python

目录 1.直接调用python语句 头文件引用 2.调用无参有参函数 1、调用无参函数 1.建立nopara.py文件 2.使用c语言根据上面流程进行调用 2、调用有参函数 1.建立nopara.py文件 2.使用c语言根据上面流程进行调用 C语言调用python需要我们已经安装好了libpython3的 dev依赖…

【Shell语言学堂】数组练习题

数组练习 1、使用数组和循环实现冒泡排序2、将冒泡排序的代码重构为2个函数&#xff0c;2个关系是a函数调用b函数自定义数组参数&#xff1a; 3、声明一个存储的全整数数组&#xff0c;对其中的每一个值进行10处理4、对硬盘使用空间占比的排序5、对当前目录的文件大小进行排序 …