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

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

news 来源：原创 2024/9/29 17:37:04

🔥 本文由程序喵正在路上原创，CSDN首发！
💖 系列专栏：数据结构与算法
🌠 首发时间：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;
}

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

在这里插入图片描述

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

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

其实，我们这样访问也是违规的，因为初始化顺序表的时候 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);							//释放临时的内存空间
}