【数据结构】顺序表的定义及实现方式

颜颜yan_

发布于 2023-10-16 16:43:37

2420

发布于 2023-10-16 16:43:37

文章被收录于专栏：颜颜yan_的学习笔记

顺序表的定义

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

顺序表的实现

静态分配

在静态分配时，由于数组的大小和空间事先已经固定，一旦空间占满，再加入新的数据就会产生溢出，进而导致程序崩溃。在使用静态存储时，首先定义一个最大长度，然后声明顺序表，在声明的顺序表中使用数组存放数据元素，定义当前长度length，代码如下。 Sq：sequence（顺序，序列）

#include <stdio.h>
 // 静态存储
// 定义最大长度,最大为10个,所以只能存放10个
#define MaxSize 10
// 声明顺序表
typedef struct {
	// 用静态的数组存放数据元素
	int data[MaxSize];
	// 顺序表的当前长度
	int length;
}SqList; // 顺序表的类型定义

初始化顺序表 声明顺序表后，需要初始化顺序表，将所有数据元素设置为默认初始值，顺序表的初试长度设置为0（这一步必须做！！！） 如果没有初始化顺序表，则内存中会有遗留的脏数据，所以将length的值设置为0这一步必须做！！！ 初始化代码如下：

#include <stdio.h>
 // 静态存储
// 定义最大长度,最大为10个,所以只能存放10个
#define MaxSize 10
// 声明顺序表
typedef struct {
	// 用静态的数组存放数据元素
	int data[MaxSize];
	// 顺序表的当前长度
	int length;
}SqList; // 顺序表的类型定义

// 初始化顺序表
void InitList(SqList& L){
	for (int i = 0; i < MaxSize; i++) {
		// 将所有数据元素设置为默认初始值
		L.data[i] = 0;
		// 设置顺序表初试长度为0
		L.length = 0;
	}
}

int main() {
	// 声明顺序表
	SqList L;
	// 初始化顺序表
	InitList(L);
	return 0;
}

注意：

使用静态分配时，如果数组存满了，就“放弃治疗”，因为顺序表的表长刚开始确定后就无法更改（存储空间是静态的）。
如果刚开始就声明一个很大的内存空间是没有必要的，这样会浪费存储资源。

动态分配

使用动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数组空间占满，就另外开辟一块更大的存储空间，替换原来的存储空间，而不需要为线性表一次性地划分所有空间。动态分配使用“动态数组”实现，先定义一个初始长度，然后定义顺序表，在顺序表中用指针来动态分配数组，定义顺序表的最大容量和当前长度。

#include <stdio.h>
// 初始长度
#define InitSize 10
typedef struct {
	// 动态分配数组的指针
	ElemType *data;
	// 顺序表的最大容量
	int MaxSize;
	// 顺序表的当前长度
	int length;
}SeqList;

动态申请内存空间，动态释放内存空间（malloc，free）

初始动态分配内存语句： L.data = (ElemType *)malloc(sizeof(ElemType) * InitSize)

L.data：指向一整片连续的存储空间的起始地址。
(ElemType *)：malloc 函数返回一个指针，需要强制转型为你定义的数据元素类型指针。
malloc：动态申请内存空间。
InitSize：malloc 函数的参数，指明要分配多大的连续内存空间。

注意：使用malloc和free函数需要引入头文件 #include <stdlib.h>

#include <stdio.h>
#include <stdlib.h>
// 初始长度
#define InitSize 10
typedef struct {
	// 动态分配数组的指针
	int *data;
	// 顺序表的最大容量
	int MaxSize;
	// 顺序表的当前长度
	int length;
}SqList;
// 初始化顺序表
void InitList(SqList& L) {
	//申请一片连续的存储空间
	L.data = (int *)malloc(sizeof(int) * InitSize);
		// 设置顺序表初试长度为0
		L.length = 0;
		L.MaxSize = InitSize;
}
//动态插入数据，增加长度
void IncreaseSize(SqList& L, int len) {
	int* p = L.data;
	L.data = (int*)malloc((L.MaxSize + len) * sizeof(int));
	for (int i = 0; i < L.length;i++) {
		// 将数据复制到新区域，但是这样使用时间开销大
		L.data[i] = p[i];
	}
	// 顺序表的最大长度增加len
	L.MaxSize = L.MaxSize + len;
	// 释放原来的内存空间
	free(p);
}
int main() {
	// 声明顺序表
	SqList L;
	// 初始化顺序表
	InitList(L);
	//插入数据
	IncreaseSize(L, 6);
	return 0;
}