【数据结构与算法】顺序表的基本操作实现

小鱼儿 2024-04-26 02:16 67阅读 0赞

> ? 本文由 [程序喵正在路上][Link 1] 原创，CSDN首发！  
> ? 系列专栏：[数据结构与算法][Link 2]  
> ? 首发时间：2022年9月19日  
> ? 欢迎关注?点赞?收藏?留言?  
> ? 一以贯之的努力 不得懈怠的人生

#### 阅读指南 ####

*  顺序表的插入
 *   *  实现
     *  时间复杂度分析
 *  顺序表的删除
 *   *  实现
     *  时间复杂度分析
 *  顺序表的按位查找
 *  顺序表的按值查找
 *   *  实现
     *  时间复杂度分析

## 顺序表的插入 ##

`ListInsert(&L, i, e)`：插入操作。在表 **L** 中的第 **i** 个位置（位序）上插入指定元素 **e**

### 实现 ###

我们采用静态分配的方式

#include <stdio.h>
    
    #define MaxSize 10				//定义最大长度
    typedef int ElemType;
    
    typedef struct {
        
    	ElemType data[MaxSize];		//用静态的 “数组” 存放数据元素
    	int length;					//顺序表的当前长度
    } SqList;						//顺序表的类型定义（静态分配方式）
    
    //初始化顺序表
    void InitList(SqList &L);
    
    //插入
    bool ListInsert(SqList &L, int i, int e);
    
    //主函数
    int main() {
        
    	SqList L;			//声明一个顺序表
    	InitList(L);		//初始化顺序表
    
    	ListInsert(L, 3, 3);
    
    	return 0;
    }
    
    //初始化顺序表
    void InitList(SqList &L) {
        
    	L.length = 0;
    }
    
    //插入
    bool ListInsert(SqList &L, int i, int e) {
        
    	if (i < 1 || i > L.length + 1) return false;	//判断 i 的范围是否有效
    	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;
    }

在移动元素的时候要注意位序、数组下标的关系，并从后面的元素依次移动

插入操作的关键在于插入前对于异常情况的判断，好的算法，应该具有 ”健壮性“，能处理异常情况，并给使用者反馈

### 时间复杂度分析 ###

//插入
    bool ListInsert(SqList &L, int i, int e) {
        
    	if (i < 1 || i > L.length + 1) return false;	//判断 i 的范围是否有效
    	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;
    }

我们要关注最深层循环语句的执行次数与问题规模 **n** 的关系

最好情况：新元素插入到表尾，不需要移动元素，此时 **i=n+1**，循环 **0** 次，最好时间复杂度为 **O(1)**

最坏情况：新元素插入到表头，需要将原有的 **n** 个元素全都向后移动，此时 **i=1**，循环 **n** 次，最坏时间复杂度为 **O(n)**

平均情况：假设新元素插入到任何一个位置的概率相同，即 **i = 1, 2, 3, … , length+1** 的概率都是 **p = 1 / (n+1)**

**i = 1** 时，循环 **n** 次；  
**i = 2** 时，循环 **n-1** 次；  
**i = 3** 时，循环 **n-2** 次；  
…  
**i = n+1** 时，循环 **0** 次

平均循环次数 = **n\*p + (n-1)\*p + (n-2)\*p + … + 1\*p = n / 2** —> 平均时间复杂度为 **O(n)**

## 顺序表的删除 ##

### 实现 ###

//删除
    bool ListDelete(SqList &L, int i, int &e);
    
    //主函数
    int main() {
        
    	SqList L;			//声明一个顺序表
    	InitList(L);		//初始化顺序表
    
    	for (int i = 1; i < 6; i++) {
        
    		if (ListInsert(L, i, i * 10)) {
        
    			printf("数值 %d 已插入第 %d 个位置\n", i * 10, i);
    		}
    		else {
        
    			printf("插入失败");
    		}
    	}
    
    	int e = -1;		//用变量 e 把删除的元素带回来
    	if (ListDelete(L, 3, e)){
        
    		printf("已删除第 3 个元素，删除元素值为 %d\n", e);
    	}
    	else {
        
    		printf("位序i不合法，删除失败\n");
    	}
    
    	return 0;
    }
    
    //删除
    bool ListDelete(SqList &L, int i, int &e) {
        
    	if (i < 1 || i > L.length) return false;	//判断 i 的范围是否有效
    
    	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;
    }

测试结果如下：

![在这里插入图片描述][746843677fe74244a84cb082f9014b2a.png]

### 时间复杂度分析 ###

//删除
    bool ListDelete(SqList &L, int i, int &e) {
        
    	if (i < 1 || i > L.length) return false;		//判断 i 的范围是否有效
    
    	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;
    }

同样是关注最深层循环语句的执行次数与问题规模 **n** 的关系，问题规模 **n = L.length** （表长）

最好情况：删除表尾元素，不需要移动其他元素，此时 **i = n**，循环 **0** 次，最好时间复杂度为 **O(1)**

最坏情况：删除表头元素，需要将后续的 **n-1** 个元素全都向前移动，此时 **i = 1**，循环 **n-1** 次，最坏时间复杂度为 **O(n)**

平均情况：假设删除任何一个元素的概率相同，即 **1, 2, 3, … , length** 的概率都是 **p = 1 / n**

**i = 1** 时，循环 **n-1** 次；  
**i = 2** 时，循环 **n-2** 次；  
**i = 3** 时，循环 **n-3** 次；  
…  
**i = n** 时，循环 **0** 次

平均循环次数 = **(n-1)\*p + (n-2)\*p + … + 1\*p = (n-1) / 2** —> 平均时间复杂度为 **O(n)**

## 顺序表的按位查找 ##

`GetElem(L, i)`：按位查找操作。获取表 **L** 中第 **i** 个位置的元素的值

#define MaxSize 10				//定义最大长度
    typedef int ElemType;
    
    typedef struct {
        
    	ElemType data[MaxSize];		//用静态的 “数组” 存放数据元素
    	int length;					//顺序表的当前长度
    } SqList;						//顺序表的类型定义（静态分配方式）
    
    //按位查找
    ElemType GetElem(SqList L, int i) {
        
    	return L.data[i - 1];
    }

时间复杂度为 **O(1)**

由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第 **i** 个元素 —— ”随机存取“ 特性

## 顺序表的按值查找 ##

`LocateElem(L, e)`：按值查找操作。在表 **L** 中查找具有给定关键字值的元素

### 实现 ###

#define InitSize 10				//顺序表的初始化长度
    typedef int ElemType;
    typedef struct {
        
    	ElemType *data;				//指示动态分配数组的指针
    	int MaxSize;				//顺序表的最大容量
    	int length;					//顺序表的当前长度
    } SqList;
    
    //按值查找
    int LocateElem(SqList L, ElemType e) {
        
    	for (int i = 0; i < L.length; i++) {
        
    		if (L.data[i] == e) {
        
    			return i+1;		//数组下标为 i 的元素值等于 e，返回其位序 i+1
    		}
    	}
    	return 0;		//退出循环，说明查找失败，返回 0
    }

注意：

基本数据类型：**int、char、float、double** 等可以直接使用运算符 “==” 比较，至于结构类型的数据元素就不行了

在 **C语言** 中，结构体的比较不能直接用 ”==“，需要依次对比各个分量来判断两个结构体是否相等

### 时间复杂度分析 ###

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

关注最深层循环语句的执行次数与问题规模 **n** 的关系，问题规模 **n = L.length** （表长）

最好情况：目标元素在表头，此时循环 **1** 次，最好时间复杂度为 **O(1)**

最坏情况：目标元素在表尾，此时循环 **n** 次，最坏时间复杂度为 **O(n)**

平均情况：假设目标元素出现在任何一个位置的概率相同，都是 **1 / n**

目标元素在第 **1** 位，此时循环 **1** 次；  
目标元素在第 **2** 位，循环 **2** 次；  
…  
目标元素在第 **n** 位，循环 **n** 次

平均循环次数 = **1 \* 1/n + 2 \* 1/n + … + n \* 1/n = (n+1) / 2** \--> 平均时间复杂度为 **O(n)**

[Link 1]: https://blog.csdn.net/weixin_62511863?spm=1011.2421.3001.5343
[Link 2]: https://blog.csdn.net/weixin_62511863/category_11984530.html?spm=1001.2014.3001.5482
[746843677fe74244a84cb082f9014b2a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/6b431997eedd42e5960e6281f6f17927.png