【数据结构与算法】顺序表的定义及初步实现

青旅半醒 2024-04-26 02:14 58阅读 0赞

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

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

*  顺序表的定义
 *  顺序表的实现 —— 静态分配
 *  顺序表的实现 —— 动态分配

## 顺序表的定义 ##

顺序表 —— 用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现

线性表是具有相同数据类型的 **n** (n≥0) 个数据元素的有限序列，数据类型相同说明每个数据元素所占的空间是一样大的

我们假设线性表第一个元素的存放位置（即首地址）是 **LOC(L)** ，**LOC** 是 **location** 的缩写，那么第二个元素的存放位置就是 **LOC(L)+数据元素的大小**，第三个元素的存放位置就是 **LOC(L)+2\*数据元素的大小**，依此类推…

**那么，我们又怎么知道所存放的数据元素的大小呢？**

学过 **C语言** 的小伙伴肯定知道，**C语言** 中有一个函数 **sizeof()** 可以帮上我们的忙，我们用 `sizeof(ElemType)` 这样调用的方式就能得到对应数据元素的大小，其中的 **ElemType** 就是你的顺序表中存放的数据元素类型，比如 `sizeof(int) = 4B`，一个整型一般是 **4** 个字节；此外，我们还可以传自己定义的类型进去，比如，我们定义一个 **Customer** 类型

typedef struct {
        
    	int num;	//号数
    	int people; //人数
    } Customer;

相应地，我们使用 `sizeof(Customer)` 就可以得到这个数据类型的大小为 **8B**

## 顺序表的实现 —— 静态分配 ##

#define MaxSize 10				//定义最大长度
    typedef struct {
        
    	ElemType data[MaxSize];		//用静态的 “数组” 存放数据元素
    	int length;					//顺序表的当前长度
    } SqList;						//顺序表的类型定义（静态分配方式）

`ElemType data[MaxSize];` 会给各个数据元素分配连续的存储空间，大小为 **MaxSize\*sizeof(ElemType)**

Sq：sequence —— 顺序，序列

#include <stdio.h>
    #define MaxSize 10				//定义最大长度
    typedef int ElemType;
    
    typedef struct {
        
    	ElemType data[MaxSize];		//用静态的 “数组” 存放数据元素
    	int length;					//顺序表的当前长度
    } SqList;						//顺序表的类型定义
    
    //基础操作 —— 初始化一个顺序表
    void InitList(SqList &L) {
        
    	for(int i = 0; i < MaxSize; i++) {
        
    		L.data[i] = 0;		//将所有数据元素设置为默认初始值
    	}
    	L.length = 0;
    }
    
    //主函数
    int main() {
        
    	SqList L;		//声明一个顺序表
    	InitList(L);	//初始化顺序表
    	//其他操作
    	return 0;
    }

**如果在初始化顺序表中不给 data 数组赋值为 0，会怎么样呢？**

#include <stdio.h>
    #define MaxSize 10				//定义最大长度
    typedef int ElemType;
    
    typedef struct {
        
    	ElemType data[MaxSize];		//用静态的 “数组” 存放数据元素
    	int length;					//顺序表的当前长度
    } SqList;						//顺序表的类型定义
    
    //基础操作 —— 初始化一个顺序表
    void InitList(SqList &L) {
        
    	L.length = 0;
    }
    
    //主函数
    int main() {
        
    	SqList L;		//声明一个顺序表
    	InitList(L);	//初始化顺序表
    	//尝试“违规”打印整个数组
    	for(int i = 0; i < MaxSize; i++) {
        
    		printf("data[%d]=%d\n", i, L.data[i]);
    	}
    	return 0;
    }

运行这段代码，你会看到很奇怪的数据，或许和我的运行结果不太一样，这是正常的

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

**为什么会显示这些奇怪的数据呢？**

其实啊，程序在给我们这个数组分配内存的时候，我们并不知道这块内存里面之前存储过什么，如果我们不设置数据元素的默认值，就会出现这样的结果

其实，我们这样访问也是违规的，因为初始化顺序表的时候 **length** 是为 **0** 的，我们要遍历的条件应该是 `i < L.length;` 才对，所以数据元素的初始化是可以省略的，不过 **length** 的初始化这一步骤就不能省略了

**如果我们定义的 “数组” 存满了，怎么办呢？**

建议直接放弃治疗，顺序表的表长刚开始确定后就无法更改了，因为我们是静态分配空间

有小伙伴就说，那我一开始就声明一个很长的顺序表不就行了，但这样的后果是会浪费我们的内存空间，从这里我们就可以看出来静态分配的局限性了

## 顺序表的实现 —— 动态分配 ##

#define InitSize 10			//顺序表的初始长度
    typedef struct {
        
    	ElemType *data;			//指示动态分配数组的指针
    	int MaxSize;			//顺序表的最大容量
    	int length;				//顺序表的当前长度
    } SqList;					//顺序表的类型定义

**C语言** 中提供了 **malloc** 和 **free** 这两个函数来让我们动态申请和释放内存空间

**malloc** 会申请一整片连续的存储空间，然后返回一个指向这一片存储空间开始地址的指针，同时需要我们强制转型为定义的数据元素类型指针

**malloc** 函数的参数，指明了要分配多大的连续内存空间

L.data = (ElemType *) malloc(sizeof(ElemType) * InitSize);

如果你学习过 **C++**，那你也可以使用 **new** 和 **delete** 这两个函数来实现同样的功能

#include <stdio.h>
    #include <stdlib.h>				//使用 malloc 和 free 函数所需的头文件
    
    #define InitSize 10				//默认最大长度
    typedef int ElemType;			//方便我们改变类型
    
    typedef struct {
        
    	ElemType *data;				//指示动态分配数组的指针
    	int MaxSize;				//顺序表的最大容量
    	int length;					//顺序表的当前长度
    } SqList;						//顺序表的类型定义
    
    //初始化顺序表
    void InitList(SqList &L);
    
    //增加动态数组的长度
    void IncreaseSize(SqList &L, int len);
    
    //主函数
    int main() {
        
    	SqList L;			//声明一个顺序表
    	InitList(L);		//初始化顺序表
    	IncreaseSize(L, 5);
    
    	return 0;
    }
    
    //初始化顺序表
    void InitList(SqList &L) {
        
    	//用 malloc 函数申请一片连续的存储空间
    	L.data = (ElemType *)malloc(sizeof(ElemType)* InitSize);
    	L.length = 0;
    	L.MaxSize = InitSize;
    }
    
    //增加动态数组的长度
    void IncreaseSize(SqList &L, int len) {
        
    	ElemType *p = L.data;				//将L数据存储起来
    	L.data = (ElemType *)malloc(sizeof(ElemType)* (L.MaxSize + len));
    
    	for (int i = 0; i < L.length; i++) {
        
    		L.data[i] = p[i];				//将数据复制到新区域
    	}
    
    	L.MaxSize = L.MaxSize + len;		//顺序表最大长度增加 len
    	free(p);							//释放临时的内存空间
    }

注意：**realloc** 函数也可以实现，但建议初学者使用 **malloc** 和 **free** 更能理解背后的过程

顺序表的特点：

1.  随机访问，既可以在 **O(1)** 时间内找到第 **i** 个元素，代码实现为 `data[i - 1]`
2.  存储密度高，每个节点只存储数据元素
3.  拓展容量不方便，即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高
4.  插入、删除操作不方便，需要移动大量元素

[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
[c2a835a27dcc4f4aac16bb19254282f4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/c47f284b9fbb4071886f969da5728212.png