数据结构：顺序表（动态顺序表）

🕗 发布于 2024-11-10 05:17 c++ 学习 c语言 数据结构 算法

专栏说明：本专栏用于数据结构复习，文章中出现的代码由C语言实现，在专栏中会涉及到部分OJ题目，如对你学习有所帮助，可以点赞鼓励一下博主喔💓

博客主页：Duck Bro 博客主页
系列专栏：数据结构专栏
关注博主，后期持续更新系列文章
如果有错误感谢请大家批评指出，及时修改
感谢大家点赞👍收藏⭐评论✍

数据结构：顺序表（动态顺序表）

1. 概念与结构

1.1 概念

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存
储。在数组上完成数据的增删查改。

1.2 结构

静态顺序表：使用定长数组存储元素。
在这里插入图片描述

#define N 7
typedef int DataType;
typedef struct SeqList
{
DataType a[N];
int size;
int capacity;
}SL;

动态顺序表：使用动态开辟的数组存储。
在这里插入图片描述

typedef int DataType;
typedef struct SeqList
{
DataType* a;
int size;
int capacity;
}SL;

2. 接口实现

2.1 动态顺序表结构

//顺序表动态存储
typedef int DataType;
typedef struct SeqList
{
DataType* a;//指点动态开辟数组
int size;//有效数据个数
int capacity;//容量空间大小
}SL;

2.2 顺序表初始化

void SLInit(SL* pc)
{
//断言
assert(pc);
//pc->a = NULL;
pc->a = (DataType*)malloc(sizeof(DataType) * 4);
//判断是否为空
if (pc->a == NULL)
{
//报错提示
perror("SLInit faild");
//退出程序
exit(-1);
}
//顺序表内的数据个数
pc->size = 0;
//顺序表内的容量
pc->capacity = 4;
}

2.3 顺序表销毁

void SLDestroy(SL* pc)
{
//断言
assert(pc);
//释放内存
free(pc->a);
//将指针置为空
pc->a = NULL;
//设置数据个数和容量为0个
pc->size = 0;
pc->capacity = 0;
}

2.4 检查空间、扩容

void SLCheckCapacity(SL* pc)
{
//断言
assert(pc);
//如果size==capacity,则进行二倍扩容
if (pc->size == pc->capacity)
{
DataType* temp = (DataType*)realloc(pc->a, pc->capacity * sizeof(DataType) * 2);
//进行判断是否开辟成功
if (temp == NULL)
{
perror("SLCheckCapacity faild");
exit(-1);
}
pc->a = temp;
pc->capacity *= 2;
}
}

2.5 顺序表尾插

void SLPushBack(SL* pc, DataType x)
{
assert(pc);

/*assert(pc);
SLCheckCapacity(pc);
pc->a[pc->size] = x;
pc->size++;*/
SLInsert(pc, pc->size, x);
}

2.6 顺序表尾删

void SLPopBack(SL* pc)
{
assert(pc);
/*assert(pc);
assert(pc->size);
pc->size--;*/
SLErase(pc, pc->size - 1);
}

2.7 顺序表头插

void SLPushFront(SL* pc, DataType x)
{
assert(pc);

断言
//assert(pc);
检查空间是否足够
//SLCheckCapacity(pc);
end为顺序表中最后一个数据的下标
//int end = pc->size - 1;
将所有数据进行后移
//while (end >= 0)
//{
//pc->a[end + 1] = pc->a[end];
//--end;

//}
//pc->a[0] = x;
//pc->size++;
SLInsert(pc, 0, x);

}

2.8 顺序表头删

void SLPopFront(SL* pc)
{
assert(pc);

/*assert(pc->size > 0);
int begin = 1;
while (begin < pc->size)
{
pc->a[begin - 1] = pc->a[begin];
begin++;

}
pc->size--;*/
SLErase(pc, 0);
}

2.9 顺序表查找

int SLFind(SL* pc, DataType x)
{

assert(pc);
for (int i = 0; i < pc->size; i++)
{
if (x == pc->a[i])
{
return i;
}
}
return -1;
}

2.10 在pos位置插入x

void SLInsert(SL* pc, int pos, DataType x)
{
assert(pos >= 0 && pos <= pc->size);
SLCheckCapacity(pc);
int end = pc->size - 1;
while (end >= pos)
{
pc->a[end + 1] = pc->a[end];
end--;
}
pc->a[pos] = x;
pc->size++;
}

2.11 删除pos位置值

void SLErase(SL* pc, int pos)
{
assert(pc);
assert(pos>=0&&pos<pc->size);

int begin = pos + 1;
while (begin < pc->size)
{
pc->a[begin-1] = pc->a[begin];
begin++;
}
pc->size--;
}

2.12 修改pos位置值

void SLModify(SL* pc, int pos, DataType x)
{
assert(pc);

assert(pos <= 0 && pos < pc->size);
pc->a[pos] = x;

}

2.13 打印顺序表

void SLPrintf(SL* pc)
{
//断言
assert(pc);
//遍历
int i = 0;
for (i = 0; i < pc->size; i++)
{
printf("%d ", pc->a[i]);
}
printf("\n");
}

3. 详细代码页

3.1 SeqList.h

#define  _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int DataType;
typedef struct SeqList
{
DataType* a;
int size;
int capacity;
}SL;

//顺序表初始化
void SLInit(SL* pc);
//顺序表销毁
void SLDestroy(SL* pc);
//容量检查,并进行扩容
void SLCheckCapacity(SL* pc);
//打印顺序表中的数据 遍历顺序表
void SLPrintf(SL* pc);

//顺序表头插
void SLPushFront(SL* pc, DataType x);
//顺序表尾删
void SLPopBack(SL* pc);
//顺序表尾插
void SLPushBack(SL* pc, DataType x);
//顺序表头删
void SLPopFront(SL* pc);

//查找位置
int SLFind(SL* pc ,DataType x);
//顺序表pos位置前插入X
void SLInsert(SL* pc, int pos,DataType x);
//顺序表删除pos位置值
void SLErase(SL* pc,int pos);
//修改pos位置值
void SLModify(SL* pc, int pos,DataType x);

3.2 SeqList.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"


void SLInit(SL* pc)
{
//断言
assert(pc);
//pc->a = NULL;
pc->a = (DataType*)malloc(sizeof(DataType) * 4);
//判断是否为空
if (pc->a == NULL)
{
//报错提示
perror("SLInit faild");
//退出程序
exit(-1);
}
//顺序表内的数据个数
pc->size = 0;
//顺序表内的容量
pc->capacity = 4;
}

void SLDestroy(SL* pc)
{
//断言
assert(pc);
//释放内存
free(pc->a);
//将指针置为空
pc->a = NULL;
//设置数据个数和容量为0个
pc->size = 0;
pc->capacity = 0;

}

void SLCheckCapacity(SL* pc)
{
//断言
assert(pc);
//如果size==capacity,则进行二倍扩容
if (pc->size == pc->capacity)
{
DataType* temp = (DataType*)realloc(pc->a, pc->capacity * sizeof(DataType) * 2);
//进行判断是否开辟成功
if (temp == NULL)
{
perror("SLCheckCapacity faild");
exit(-1);
}
pc->a = temp;
pc->capacity *= 2;

}
}

void SLPrintf(SL* pc)
{
//断言
assert(pc);
//遍历
int i = 0;
for (i = 0; i < pc->size; i++)
{
printf("%d ", pc->a[i]);
}
printf("\n");
}

void SLPushFront(SL* pc, DataType x)
{
assert(pc);

断言
//assert(pc);
检查空间是否足够
//SLCheckCapacity(pc);
end为顺序表中最后一个数据的下标
//int end = pc->size - 1;
将所有数据进行后移
//while (end >= 0)
//{
//pc->a[end + 1] = pc->a[end];
//--end;

//}
//pc->a[0] = x;
//pc->size++;
SLInsert(pc, 0, x);

}

void SLPopBack(SL* pc)
{
assert(pc);
/*assert(pc);
assert(pc->size);
pc->size--;*/
SLErase(pc, pc->size - 1);
}

void SLPushBack(SL* pc, DataType x)
{
assert(pc);

/*assert(pc);
SLCheckCapacity(pc);
pc->a[pc->size] = x;
pc->size++;*/
SLInsert(pc, pc->size, x);
}

void SLPopFront(SL* pc)
{
assert(pc);

/*assert(pc->size > 0);
int begin = 1;
while (begin < pc->size)
{
pc->a[begin - 1] = pc->a[begin];
begin++;

}
pc->size--;*/
SLErase(pc, 0);
}

void SLInsert(SL* pc, int pos, DataType x)
{
assert(pos >= 0 && pos <= pc->size);
SLCheckCapacity(pc);
int end = pc->size - 1;
while (end >= pos)
{
pc->a[end + 1] = pc->a[end];
end--;
}
pc->a[pos] = x;
pc->size++;
}

void SLErase(SL* pc, int pos)
{
assert(pc);
assert(pos>=0&&pos<pc->size);

int begin = pos + 1;
while (begin < pc->size)
{
pc->a[begin-1] = pc->a[begin];
begin++;
}
pc->size--;
}

int SLFind(SL* pc, DataType x)
{

assert(pc);
for (int i = 0; i < pc->size; i++)
{
if (x == pc->a[i])
{
return i;
}
}
return -1;
}

void SLModify(SL* pc, int pos, DataType x)
{
assert(pc);

assert(pos <= 0 && pos < pc->size);
pc->a[pos] = x;

}

3.3 main.c


#include "SeqList.h"
void test1()
{
//测试创建顺序表初始化 销毁
SL s;
SLInit(&s);
SLDestroy(&s);
}

void test2()
{
//测试顺序表尾插插
SL s1;
SLInit(&s1);

SLPushBack(&s1, 5);
SLPushBack(&s1, 5);
SLPushBack(&s1, 5);
SLPushBack(&s1, 5);
SLPushBack(&s1, 5);
SLPushBack(&s1, 5);
SLPushBack(&s1, 5);
SLPushBack(&s1, 5);
SLPushBack(&s1, 5);
SLPushBack(&s1, 5);
//SLPushFront(&s1, 4);
//SLPushFront(&s1, 4);

//SLPopBack(&s1);
//SLPopBack(&s1);
SLPopBack(&s1);
SLPopBack(&s1);


SLPushBack(&s1, 67);
SLPushBack(&s1, 67);
SLPushBack(&s1, 67);

SLPrintf(&s1);
SLDestroy(&s1);
}

void test3()
{
//测试顺序表尾插插
SL s1;
SLInit(&s1);

SLPushBack(&s1, 5);
SLPushBack(&s1, 5);
SLPushBack(&s1, 5);
SLPushBack(&s1, 5);
SLPushBack(&s1, 5);
SLPrintf(&s1);

//SLPushFront(&s1, 4);
SLPushFront(&s1, 66);



SLPrintf(&s1);
SLDestroy(&s1);
}

void test4()
{
//测试顺序表尾插插
SL s1;
SLInit(&s1);

SLPushBack(&s1, 5);
SLPushBack(&s1, 5);
SLPushBack(&s1, 5);
SLPushBack(&s1, 5);
SLPushBack(&s1, 5);
//SLInsert(&s1, 2, 7);
int x = 0;
scanf("%d", &x);
int pos = SLFind(&s1, x);
if (pos != -1)
{
SLInsert(&s1, pos, 50);
}


SLPrintf(&s1);
SLDestroy(&s1);
}
void test5()
{
//测试顺序表尾插插
SL s1;
SLInit(&s1);

SLPushBack(&s1, 1);
SLPushBack(&s1, 2);
SLPushBack(&s1, 3);
SLPushBack(&s1, 4);
SLPushBack(&s1, 5);
//SLInsert(&s1, 2, 7);
SLPopBack(&s1);
SLPopFront(&s1);


SLPrintf(&s1);
SLDestroy(&s1);
}
int main()
{
//test1();
//test2();
//test3();
//test4();
test5();

return 0;
}

在这里插入图片描述

原文地址：https://blog.csdn.net/m0_74014525/article/details/143651320

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Linux系统性能调优技巧
下一篇：《JavaEE进阶》----21.＜基于Spring图书管理系统②（图书列表+删除图书+更改图书）＞

DataGrip 连接 Redis、TongRDS
有些旧版本没有 redis 驱动用不了。
阅读更多2024-11-25
【PHP】基础语法，自学笔记（二）
基本的加、减、乘、除、取余、以及幂运算。框中的的参数并计算，处理后返回给页面。字符变量，数，布尔，以及。
阅读更多2024-11-25
wordpress中Gravatar用户头像不显示，免插件实现添加自定义设置上传头像功能
虽热这个功能使用场景和频率都非常低，但在有时候还是需要WordPress来显示头像的，但是zuanmang.net并不是每个人都有注册设置Gravatar头像。将下面的代码加入到你主题的Functio
阅读更多2024-11-25
自然语言处理: RAG优化之Embedding模型选型重要依据：mteb/leaderboard榜
近期RAG 应用不断涌现，它们的性能表现各具特色。尽管我们可以通过多个方面（例如查询改写、图像数据处理、分块策略、元数据管理、密集检索、稀疏检索、结果重排、排序融合、提示词优化以及上下文压缩等）逐步优
阅读更多2024-11-25
【Verilog】第三章作业
9. (单选题)下面两段代码中信号in、q1、q2、q3的值分别是0、1、2、3，那么经过1个时钟周期后，左边程序q3的值和右边程序q3的值分别变为（）。写出表达式以实现图1对应电路的逻辑功能
阅读更多2024-11-25
【docker 保存】将Docker镜像保存为一个离线的tar归档文件
将Docker镜像保存为一个离线的tar归档文件，这样就可以在没有网络连接的情况下，或者在不同的机器上使用这个镜像。这个过程通常包括两个步骤：首先是将镜像保存为tar文件，然后是将这个tar文件传输到
阅读更多2024-11-25
Claude Opus MetaPrompt 系统详解
Claude Opus MetaPrompt 系统详解
阅读更多2024-11-25
docker搭建私有仓库，实现镜像的推送和拉取
这么做的目的是【docker默认不允许htp方式推送镜像，通过配置选项来取消这个限制】新增配置【insecure-registries】，将私服仓库的地址加入。192.168.111.162 部署do
阅读更多2024-11-25
手机文件可以打印出来吗
大多数打印店都具备手机文件上传的能力，可以通过无线传输或数据线连接的方式将手机上的文件传输到打印设备上。然而，打印店的价格通常较高，特别是对于大量文件的打印，成本会显著增加。琢贝云打印提供了一种经济实
阅读更多2024-11-25
【基础算法】链表
【代码】【基础算法】链表。
阅读更多2024-11-25

数据结构：顺序表（动态顺序表）

数据结构：顺序表（动态顺序表）

目录

1. 概念与结构

1.1 概念

1.2 结构

2. 接口实现

2.1 动态顺序表结构

2.2 顺序表初始化

2.3 顺序表销毁

2.4 检查空间、扩容

2.5 顺序表尾插

2.6 顺序表尾删

2.7 顺序表头插

2.8 顺序表头删

2.9 顺序表查找

2.10 在pos位置插入x

2.11 删除pos位置值

2.12 修改pos位置值

2.13 打印顺序表

3. 详细代码页

3.1 SeqList.h

3.2 SeqList.c

3.3 main.c

相关文章