数据结构顺序表seqlist
数据结构——顺序表seqlist
前言：大家好😍，本文主要介绍了数据结构——顺序表部分的内容
一、线性表的定义
线性表是具有相同数据类型的n个数据元素的有限序列，n为表长，当n=0时线性表时一个空表。用l命名线性表，表示为l=（a1，a2， ，an）。
线性表除第一个元素之外，每个元素都有直接前驱，除最后一个元素之外每个元素都有直接后继。
二、线性表的基本操作
Initlist（&L）：初始化表，构造一个空的线性表L，构造一个空的线性表，分配内存空间
Destroylist（&L）：销毁。销毁线性表并释放线性表L所占用的内存空间
Insertlist（&L，i，e）：插入，在表L中第i个位置上插入指定元素e
Deletelist（&L，i，&e）：删除，删除表L中第i个位置上的元素，并用e返回删除元素的值
LocateElem（L，e）：按值查找，在表L中查找具有给定关键字e值的元素
GetElem（L，i）：按位查找，获取表L中第i个位置的元素的值
Length（L)：求表长，返回线性表L的长度，即L中数据元素的个数
Printlist（L）：输出，输出线性表所有元素值
Empty（L）：判空，若L为空，返回true，否则返回false 对参数的修改结果需要引用&
三.顺序表
1.定义
顺序表是一种线性表 的存储实现方式。线性表是具有相同数据类型的元素构成的有限序列，顺序表通过数组 的形式将这些元素存储在内存中，并通过下标索引 来访问和操作元素。
2 存储结构
顺序表通常使用数组来实现，数组的每个位置存储一个元素。例如，一个顺序表可以表示为：
数组：[a0, a1, a2, …, an-1]
其中，a0 是表头元素，an-1 是表尾元素。
3 特点
优点： 随机访问：可以通过下标索引快速访问任意位置的元素，时间复杂度为 O(1)。 存储密度高：由于没有额外的指针存储空间，顺序表的存储利用率较高。 操作简单：基于数组的实现使得顺序表的操作逻辑相对简单。 缺点： 插入和删除效率低：插入或删除元素时，需要移动大量元素以保持顺序表的连续性，时间复杂度为 O(n)。 存储空间固定：顺序表的存储空间在初始化时需要预先分配，难以动态扩展。如果分配的空间不足，需要重新分配更大的空间并复制数据；如果分配过多，则会浪费空间。 内存碎片问题：频繁的动态扩展和收缩可能导致内存碎片化。
四 顺序表操作
点h文件中定义了一个顺序表（SeqList）的结构体
#define INIT_SIZE 10 //初始化时malloc购买的格子数量
//可库容的顺序表的结构体设计
typedef int ELEM_TYPE;
typedef struct SeqList
{
ELEM_TYPE* elem;//用来接收malloc返回的数组首地址
int length;//存放有效值个数
int listsize;//存放数组的总的格子数
}SeqList, * PSeqList;
作用 ：定义了一个宏
INIT_SIZE，表示顺序表初始化时分配的内存大小（即初始容量）。值 ：
INIT_SIZE被设置为 10，表示初始化时会分配 10 个元素的空间。结构体名称 ：
SeqList，表示顺序表的结构体。指针类型别名 ：
PSeqList，表示指向SeqList的指针。
ELEM_TYPE*表示elem是一个指针，指向ELEM_TYPE类型的数据。ELEM_TYPE是一个类型别名
4.1初始化
void Init_SeqList(struct SeqList* psl)
{
//0.安全处理 每一个函数都要写的
assert(nullptr != psl);
if (nullptr == psl)
{
exit(EXIT_FAILURE);
}
//1.对我们的 elem 用来去malloc 在堆区购买一块连续的空间
psl->elem = (ELEM_TYPE*)malloc(INIT_SIZE * sizeof(ELEM_TYPE));
if (NULL == psl->elem)
{
exit(EXIT_FAILURE);
}
//2.对我们的 length 初始化为0
psl->length = 0;
//3.对我们的 listsize 初始化为 INITSIZE
psl->listsize = INIT_SIZE;
}
类型转换 ：
malloc返回的是void*类型的指针，需要强制转换为ELEM_TYPE*。安全检查 ：如果
malloc分配失败（返回NULL），程序会退出。
length：表示顺序表中当前存储的元素个数，初始值为 0。
listsize：表示顺序表当前分配的总容量，初始值为INIT_SIZE。
psl->elem存储了这块内存的首地址。通过
psl->elem[i]可以访问顺序表中的第i个元素。存储元素 ：
elem指向的内存空间被用来存储顺序表中的所有元素。例如，如果elem指向的内存空间大小为INIT_SIZE，则可以存储INIT_SIZE个ELEM_TYPE类型的元素。
4.2 插入
4.2.1头插
bool Insert_Seqlist_head(PSeqList psl, ELEM_TYPE val)
{
//0.assert
//0.5 判满
if (Is_Full(psl))
{
Increase(psl);
}
//此时，肯定有空闲格子
//1.集体向后挪(尾巴先动)
for (int i = psl->length - 1; i >= 0; i–)
{
psl->elem[i + 1] = psl->elem[i];
}
//2.将val放入0号下标
psl->elem[0] = val;
//3.有效值个数+1
psl->length++;
return true;
}
- 逻辑 ：从顺序表的尾部开始，逐个将元素向后移动一个位置。
psl->elem[i + 1] = psl->elem[i]：将第i个元素移动到第i + 1个位置。
循环条件 ：从
psl->length - 1开始，直到i = 0，确保所有元素都向后移动。更新顺序表的长度，反映新插入的元素。
函数返回
true，表示插入操作成功
psl->length表示顺序表中当前存储的有效元素的个数。例如：如果psl->length的值为 5，说明顺序表中有 5 个有效元素。
psl->length - 1是对psl->length的值减去 1，如果psl->length为 5，那么最后一个有效元素的索引为5 - 1 = 4。常用于从顺序表的最后一个有效元素开始，逐个向前遍历所有元素
4.2.2 尾插
bool Insert_Seqlist_tail(PSeqList psl, ELEM_TYPE val)
{
//0.assert
//0.5 判满
if (Is_Full(psl))
{
Increase(psl);
}
//此时，肯定有空闲格子
psl->elem[psl->length] = val;
psl->length++;
return true;
}
4.2.3 按位置插
bool Insert_Seqlist_pos(PSeqList psl, ELEM_TYPE val, int pos)
{
//默认pos==0 则认为是头插
//0.安全性处理 psl pos合法性判断
assert(nullptr != psl);
assert(pos >= 0 && pos <= psl->length);
//0.5 判满
if (Is_Full(psl))
{
Increase(psl);
}
//此时，肯定有空闲格子
//1.将插入位置之后的元素，统一向后挪动，把插入位置给空出来
for (int i = psl->length - 1; i >= pos; i–)
{
psl->elem[i + 1] = psl->elem[i];
}
//2.插入
psl->elem[pos] = val;
//3.length++
psl->length++;
return true;
}
通过
psl->elem[i]可以访问顺序表中的第i个元素。
4.3 删除
4.3.1 头删
bool Del_Seqlist_head(SeqList* psl)
{
//0.assert
//0.5 判空
if (Is_Empty(psl))
return false;
//1.除了第一个元素之外，统一向前挪动
for (int i = 1; i <= psl->length - 1; i++)
{
psl->elem[i - 1] = psl->elem[i];
}
//2.有效值个数-1
psl->length–;
return true;
}
//1.除了第一个元素之外，统一向前挪动 for (int i = 1; i <= psl->length - 1; i++) { psl->elem[i - 1] = psl->elem[i]; }
//1.集体向后挪(尾巴先动) for (int i = psl->length - 1; i >= 0; i–) { psl->elem[i + 1] = psl->elem[i]; }
4.3.2 尾删
//尾删
bool Del_Seqlist_tail(SeqList* psl)
{
//0.assert
//0.5 判空
if (Is_Empty(psl))
return false;
psl->length–;
return true;
}
4.3.3 按位置删
bool Del_Seqlist_pos(SeqList* psl, int pos)
{
//0.assert psl pos
assert(psl != NULL);
assert(pos >= 0 && pos < psl->length);
//0.5 判空isempty
if (Is_Empty(psl))
return false;
//1.将pos位置之后的有效值，统一向前覆盖(头先动)
for (int i = pos + 1; i <= psl->length - 1; i++)
{
psl->elem[i - 1] = psl->elem[i];
}
//2.有效值个数-1
psl->length–;
return true;
}
4.3.4 按值删
//按值删(只删除这个val值出现的第一次的位置)
bool Del_Seqlist_val(SeqList* psl, ELEM_TYPE val)
{
//0.assert
//0.5 isempty
//1.通过调用查找函数，查找val值在顺序表中的位置
int index = Search_SeqList(psl, val);
//2.若返回的位置下标为-1 返回假 若不等于-1，则此时怎么删
if (index == -1)
return false;
return Del_Seqlist_pos(psl, index);
}
4.4 查找
//4.查找数据是否已经存在(若存在，则只需要返回下标即可 找不到返回-1) int Search_SeqList(PSeqList psl, ELEM_TYPE val) { //0.assert for (int i = 0; i < psl->length; i++) { if (psl->elem[i] == val) return i; } return -1; }
4.5 删除值val出现的位置
//删除当前val值出现的所有位置(1)
bool Del_SeqList_All_Val1(struct SeqList* psl, ELEM_TYPE val)
{
int count = 0;
for (int i = 0; i < psl->length; i++)
{
if (psl->elem[i] == val)
{
count++;
}
}
for (int i = 0; i < count; i++)
{
int index = Search_SeqList(psl, val);
Del_Seqlist_pos(psl, index);
}
return true;
}
//删除当前val值出现的所有位置(2)
bool Del_SeqList_All_Val2(struct SeqList* psl, ELEM_TYPE val)
{
int qianfangkongxiangezishu = 0;
for (int i = 0; i < psl->length; i++)
{
if (psl->elem[i] == val)
qianfangkongxiangezishu++;
else
psl->elem[i - qianfangkongxiangezishu] = psl->elem[i];
}
psl->length = psl->length - qianfangkongxiangezishu;
return true;
}
4.6 其余操作
//5.判空 bool Is_Empty(PSeqList psl) { return psl->length == 0; } //6.判满 bool Is_Full(PSeqList psl) { return psl->length == psl->listsize; } //7.扩容函数(1.5 2) 默认用2倍扩容 void Increase(PSeqList psl) { ELEM_TYPE* tmp = (ELEM_TYPE*)realloc(psl->elem, psl->listsize * sizeof(ELEM_TYPE) * 2); if (tmp != nullptr) { psl->elem = tmp; } } //8.清空 (不释放已购买的内存) void Clear(PSeqList psl) { //malloc申请空间先不释放，而是认为所有格子里都是无效值 psl->length = 0; } //9.销毁 (需要释放malloc购买的内存的) void Destroy(PSeqList psl) { free(psl->elem); psl->length = psl->listsize = 0; } //打印 void Show(PSeqList psl) { //assert for (int i = 0; i < psl->length; i++) { printf("%d “, psl->elem[i]); } printf("\n”); }
4.7 主函数测试
int main() { struct SeqList sq; Init_SeqList(&sq); Insert_Seqlist_head(&sq, 100); Insert_Seqlist_head(&sq, 101); Insert_Seqlist_head(&sq, 102); Insert_Seqlist_tail(&sq, 200); Insert_Seqlist_tail(&sq, 201); Insert_Seqlist_tail(&sq, 202); Insert_Seqlist_tail(&sq, 2000); Insert_Seqlist_tail(&sq, 2010); Insert_Seqlist_tail(&sq, 2020); Insert_Seqlist_pos(&sq, 10000, 3); Show(&sq); Insert_Seqlist_head(&sq, 111); Insert_Seqlist_tail(&sq, 222); Show(&sq); //删除 Del_Seqlist_head(&sq); Del_Seqlist_tail(&sq); Show(&sq); Del_Seqlist_pos(&sq, 4); Show(&sq); Del_Seqlist_pos(&sq, 8); Show(&sq); Del_Seqlist_pos(&sq, 0); Show(&sq); Del_Seqlist_val(&sq, 201); Show(&sq); //Clear(&sq); //Show(&sq); //Destroy(&sq); //Show(&sq); //———————————————— Insert_Seqlist_pos(&sq, 3, 2); Insert_Seqlist_pos(&sq, 3, 4); Insert_Seqlist_pos(&sq, 3, 6); Show(&sq); Del_SeqList_All_Val2(&sq, 3); Show(&sq); return 0; }