当前位置：首页 > news >正文

11. 线性表的顺序表示和实现（3）

news 2025/6/13 16:20:40

本节主要介绍顺序表的查找、插入和删除操作。

本文部分ppt、视频截图来自：[青岛大学-王卓老师的个人空间-王卓老师个人主页-哔哩哔哩视频]

1. 顺序表上的查找操作

（1）什么是按值查找

给定一个值，顺序遍历线性表，看该值是否在线性表中，如果存在就返回元素位序，如果不存在，就返回0。

在这里插入图片描述

（2）顺序表的按值查找算法

在线性表L中查找与指定值e相同的数据元素的位置
从表的一端开始，逐个进行记录关键字和给定值的比较。找到，返回该元素的位置序号，未找到，返回0

//for语句实现：
int LocatedElem(SqList L，ElemType e){
//在线性表L中查找值为e的数据元素，返回其序号（是第几个元素）for(i = 0;i < L.length;i++)//查找成功，返回序号if(L.elem[i] == e)  return i+1;return 0; //查找失败，返回0
}//while语句实现
int LocatedElem(SqList L，ElemType e){
//在线性表L中查找值为e的数据元素，返回其序号（是第几个元素）i = 0;while (i < L.length && L.elem[i] != e)  i++;//查找成功，返回序号if(i < L.length)  return i+1;return 0; //查找失败，返回0
}

（3）顺序表的查找算法分析

因为查找算法的基本操作为：记录的关键字同给定值进行比较

平均查找长度ASL(Average Search Length)：
为确定记录在表中的位置，需要与给定值进行比较的关键字的个数的期望值叫做算法的平均查找长度。如果e = g，那么平均查找长度为：(1 + 2 + 3 + 4 + 5 + 6 + 7) / 7 = 4

假设每个记录的查找概率相等： P_i = 1 / n
则： $ASLSS = \sum_{i=1}^{n}P_{i}C_{i}$

2. 顺序表上的插入操作

（1）顺序表插入算法的思想

线性表的插入运算是指在表的第i(1≤i≤n+1)个位置上，插入一个新结点e，使长度为n的线性表(a₁,…,a_i-1,a_i,…,a_n)变成长度为n+1的线性表(a₁,…,a_i-1,e,a_i,…,a_n)

在这里插入图片描述

算法思想：

判断插入位置 i 是否合法。
判断顺序表的存储空间是否已满，若已满返回ERROR。
将第n至第ì 位的元素依次向后移动一个位置，空出第i个位置。
将要插入的新元素e放入第i个位置。
表长加1，插入成功返回OK。

（2）插入算法实现

Status ListInsert_Sq(SqList &L,int i,ElemType e){//i值不合法if(i < 1 || i > L.length+1)  return ERROR;//当前存储空间已满if(L.length == MAXSIZE) return ERROR;//插入位置及之后的元素后移for(j = L.length-1;j>=i-1;j--)L.elem[j+1] = L.elem[j];//将新元素e放入第i个位置L.elem[i-1] = e;//表长增1L.length++;return OK;
}

（3）顺序表插入算法分析

算法时间主要耗费在移动元素的操作上

若插入在尾结点之后，则根本无需移动（特别快）；
若插入在首结点之前，则表中元素全部后移（特别慢）；
若要考虑在各种位置插入（共n+1种可能）的平均移动次数，该如何计算？
顺序表插入算法的平均时间复杂度为O(n)。

2. 顺序表上的删除操作

（1）顺序表删除算法的思想

线性表的删除运算是指将表的第i(1 ≤ i ≤ n)个结点删除使长度为n 的线性表(a₁, …, a_i-1, a_i,a_i+1,…,a_n )变成长度为n-1的线性表(a₁, …, a_i-1, a_i+1,…,a_n )

算法思想：

判断删除位置 i 是否合法（合法值为1 ≤ i ≤ n）。
将欲删除的元素保留在e中。
将第i+1至第 n 位的元素依次向前移动一个位置。
表长减1，删除成功返回OK。

（2）删除算法实现

Status ListDelete_Sq(SqList &L,int i){//i值不合法if((i < 1) || (i > L.length))  return ERROR;//被删除元素之后的元素前移for (j = i;j <= L.length - 1; j++)L.elem[j-1] = L.elem[j];//表长减1L.length--;return OK;
}