数据结构【顺序表】

🕗 发布于 2024-05-15 18:35 数据结构 c语言

1.顺序表的概念

在认识顺序表之前，让我们先认识下线性表。

线性表

线性表是由n个相同类型的数据所组成的有限序列，线性表是一种在现实里被广泛使用的，常见的线性表有：顺序表、链表、栈、队列等等。
线性表在逻辑结构一定连续，但在物理结构中并不一定是连续的。

物理结构

物理结构就是数据存储于内存的结构，就那数组来说，数组开辟的空间是连续的，第x个数据的空间的下一块空间就是第x+1个数据，这就是物理结构连续。
在这里插入图片描述
如果我在设计表的时候，专门设计一个指针用来存放下一个数据的地址。
如下图：

第x数据和第x+1数据的空间并不是连续的，而是被指针位连接的，是像一个绳子，每个数据位就相当于绳结，指针位相当于绳结后面的绳子，这就是物理结构不连续。

逻辑结构

逻辑结构是我们自己抽象出来的，对于线性表来说，它的逻辑结构我们就可以把他想象成直线的线性结构，就拿上面物理结构不连续的例子来说，尽管它第一个数据和第二个数据在空间上并不是连续，但是我们可以把它们想象是连续的。
就类似于下图：
在这里插入图片描述
顺序表是线性表的一种，顺序表的特点就是物理层面和逻辑层面都连续，数据与数据之间都是相邻的
顺序表的底层是数组!!!

2.顺序表的分类

顺序表可以分为静态和动态两种

2.1静态顺序表

在创建之前将大小固定，这样虽然很简单，但是有局限性；如果给定的数据多了，就无法完整的存储数据；如果给定的数据少了，就会造成空间的浪费

typedef int SQLDATATYPE;
typedef struct SQList
{
SQLDATATYPE a[100];//给定了100个数据，后续无法改动大小
int size;//当前数据的个数
}SQList;

哪有什么方法可以解决呢？

2.2动态顺序表

内存大小是不固定的，需要使用时再进行动态开辟，如果后面有多的数据要存储，就可以使用realloc函数来进行增容，所以就更加的灵活

typedef int SQLDATATYPE;
typedef struct SQList
{
SQLDATATYPE* a;
int size;//当前数据的个数
int capacity;//当前顺序表的容量
}SQList;

我们本章讲解的是动态顺序表

3.顺序表接口的实现

首先我们需要一个头文件和一个源文件；
头文件是用来声明顺序表函数的，源文件是用来实现顺序表函数的实现

头文件(SQList.h)如下

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//typedef int SQLDATATYPE;
//typedef struct SQList
//{
//SQLDATATYPE a[100];//给定了100个数据，后续无法改动大小
//int size;//当前数据的个数
//}SQList;

typedef int SQLDATATYPE;
typedef struct SQList
{
SQLDATATYPE* a;
int size;//当前数据的个数
int capacity;//当前顺序表的容量
}SQList;

//初始化顺序表
void SQListInit(SQList* plist);
//销毁顺序表
void SQListDestroy(SQList* plist);

//插入(尾部)
void SQListPushBack(SQList* plist, SQLDATATYPE x);
//删除(尾部)
void SQListPopBack(SQList* plist);

//插入(头部)
void SQListPushFront(SQList* plist, SQLDATATYPE x);
//删除(头部)
void SQListPopFront(SQList* plist);

//查找元素
int SQListFind(SQList* plist, SQLDATATYPE x);

//插入(指定位置前)
void SQListInsect(SQList* plist, int pst, SQLDATATYPE x);
//删除(指定位置)
void SQListDelete(SQList* plist, int pst);


//打印顺序表
void SQListPrint(SQList* plist);

源文件

记住要包含头文件

#include"SQList.h"

初始化顺序表

//初始化顺序表
void SQListInit(SQList* plist)
{
plist->a = NULL;
//其实也可以在初始化的时候就给a开辟空间(看个人喜好)
plist->size = plist->capacity = 0;
}

一定要传址调用，这样才能真正的改变到顺序表

销毁顺序表

//销毁顺序表
void SQListDestroy(SQList* plist)
{
assert(plist);
free(plist->a);
plist->a = NULL;//这一步是为了让a不会野指针
//也可以避免a被重复释放(free函数不会对NULL进行操作)
plist->size = plist->capacity = 0;
}

插入

插入就意味这内容的增加，就必然会导致内容空间的不足，这时候我们就需要进行扩容。

扩容

我们在插入之前要看，内部是否还有空间可以让我们插入，当size==capacity时，就代表表内已经填满数据了，我们就需要进行扩容
扩容用到的是realloc函数，我们扩容是默认是以两倍来扩容

尾插

void SQListPushBack(SQList* plist, SQLDATATYPE x)
{
assert(plist);//检查plist是否为空指针
if (plist->size == plist->capacity)//判断空间是否满了
{
int NewCapacity = plist->capacity == 0 ? 4 : 2 * plist->capacity;//此处为一个三目表达式
//如果plist->capacity==0为真，将4赋给NewCapacity;反之则赋值2*plist->capacity

SQLDATATYPE* tmp = (SQLDATATYPE*)realloc(plist->a, NewCapacity * sizeof(SQLDATATYPE));
if (tmp == NULL)
{
perror("realloc fail");
exit(1);
}
plist->a = tmp;//将调整的空间赋给顺序表
plist->capacity = NewCapacity;//调整容量
}
plist->a[plist->size] = x;
plist->size++;
}

头插

头插我们就会遇到一个问题。
我们不能直接在顺序表的头部进行插入，这样会覆盖掉顺序表原来的数据，会造成数据的丢失。在这里插入图片描述

解决方法也很简单
我们将整个顺序表往后挪动一位，让下标为x的数据等于下标为x-1的数据。
因为我们size处是一个待插入数据的空间，所以这样并不会造成数据的丢失。在这里插入图片描述

代码如下：

void SQListPushFront(SQList* plist, SQLDATATYPE x)
{
assert(plist);//检查plist是否为空指针
if (plist->size == plist->capacity)
{
int NewCapacity = plist->capacity == 0 ? 4 : 2 * plist->capacity;//此处为一个三目表达式
//如果plist->capacity==0为真，将4赋给NewCapacity;反之则赋值2*plist->capacity

SQLDATATYPE* tmp = (SQLDATATYPE*)realloc(plist->a, NewCapacity * sizeof(SQLDATATYPE));
if (tmp == NULL)
{
perror("realloc fail");
exit(1);
}
plist->a = tmp;//将调整的空间赋给顺序表
plist->capacity = NewCapacity;//调整容量
}

for (int i = plist->size; i > 0; i--)//将整个顺序表往后挪动一位
{
plist->a[i] = plist->a[i - 1];
}

plist->a[0] = x;
plist->size++;
}

封装扩容函数

这时候我们看到，尾插函数和头插函数有一段代码是一模一样的，我们接下来还有个指定位置前的插入，它也是可能会进行扩容函数的，如果这三个函数都使用一段相同的代码，就会显得代码很冗余。

我们就可以将这段代码抽离出来，封装成一个独立的函数，需要扩容的时候调用该函数就可以了。

代码如下：

//扩容函数
//因为扩容函数是在源代码运行的，所以可以不用在头文件进行声明(当然你也可以在头文件进行声明  看个人喜好)
void SQListAdd(SQList* plist)
{
int NewCapacity = plist->capacity == 0 ? 4 : 2 * plist->capacity;//此处为一个三目表达式
//如果plist->capacity==0为真，将4赋给NewCapacity;反之则赋值2*plist->capacity

SQLDATATYPE* tmp = (SQLDATATYPE*)realloc(plist->a, NewCapacity * sizeof(SQLDATATYPE));
if (tmp == NULL)
{
perror("realloc fail");
exit(1);
}
plist->a = tmp;//将调整的空间赋给顺序表
plist->capacity = NewCapacity;//调整容量
}

删除

尾删

//删除(尾部)
void SQListPopBack(SQList* plist)
{
assert(plist);
assert(plist->size > 0);//如果为0了，我还删什么呢？

plist->size--;//这里很简单，就是将他的size进行--
//size指向的是尾数据的下一块空间，也就是待插入的空间
//我们--size，就相当于把尾数据的空间变成了待插入的空间
//我们新增数据的时候，会把原来的值覆盖掉的
}

头删

这里有个问题

因为是删除头元素，我们不能直接将size–。

解决方法也很简单

将整个顺序表往前挪动一位，原理和头插的解决方法是类似的。
在这里插入图片描述
代码如下：

//删除(头部)
void SQListPopFront(SQList* plist)
{
assert(plist);
assert(plist->size > 0);//如果为0了，我还删什么呢？

for (int i = 0; i < plist->size - 1; i++)//将整个顺序表往前挪动一位
{
plist->a[i] = plist->a[i + 1];
}

plist->size--;
}

查找元素

//查找元素
int SQListFind(SQList* plist, SQLDATATYPE x)
{
assert(plist);
int i = 0;
while (i < plist->size)//size-1处就是最后一个数据
{
if (plist->a[i] == x)//找到了
return i;//返回的是下标
i++;
}
//i=size 跳出循环
//找不到
return EOF;//EOF(-1)
}

在指定位置前插入数据

情况一(指定的位置不是首元素)

我们就将指定位置及以后的数据往后挪一位;，再将数据插入到指定位置的下标。
在这里插入图片描述

情况二(指定的位置是首元素)

那么是首元素了，我们在首元素前进行插入，这是什么？
这不就是头插吗
所以我们可以直接调用我们已经写好的头插函数

//插入(指定位置前)
void SQListInsect(SQList* plist, int pst, SQLDATATYPE x)
{
assert(plist);
if (plist->size == plist->capacity)
{
SQListAdd(plist);//这里就直接调用了增容函数
}

//这里有两种情况
//第一种当pst不是首元素
if (pst != 0)
{
for (int i = plist->size; i > pst; i--)//将顺序表pst后面的数据往后挪动一位
{
plist->a[i] = plist->a[i - 1];
}
plist->a[pst] = x;
}

//第二种:当pst是首元素
//那么是首元素了，我们在首元素前进行插入，这是什么？
//这不就是头插吗
//所以我们可以直接调用我们已经写好的头插函数
else
{
SQListPushFront(plist, x);
}
}

删除指定位置

我们只要将指定位置后面的数据往前挪动一位

//删除(指定位置)
void SQListDelete(SQList* plist, int pst)
{
assert(plist);
assert(plist->size > 0);//如果为0了，我还删什么呢

for (int i = pst; i < plist->size - 1; i++)//将pst后面的数据往前挪动一位
{
plist->a[i] = plist->a[i + 1];
}
plist->size--;
}

打印顺序表

//打印顺序表
void SQListPrint(SQList* plist)
{
assert(plist);
if (plist->size == 0)
printf(NULL);
for (int i = 0; i < plist->size; i++)
{
printf("%d ", plist->a[i]);
}
printf("\n");
}

完整代码

SQList.h

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//typedef int SQLDATATYPE;
//typedef struct SQList
//{
//SQLDATATYPE a[100];//给定了100个数据，后续无法改动大小
//int size;//当前数据的个数
//}SQList;

typedef int SQLDATATYPE;
typedef struct SQList
{
SQLDATATYPE* a;
int size;//当前数据的个数
int capacity;//当前顺序表的容量
}SQList;

//初始化顺序表
void SQListInit(SQList* plist);
//销毁顺序表
void SQListDestroy(SQList* plist);

//插入(尾部)
void SQListPushBack(SQList* plist, SQLDATATYPE x);
//删除(尾部)
void SQListPopBack(SQList* plist);

//插入(头部)
void SQListPushFront(SQList* plist, SQLDATATYPE x);
//删除(头部)
void SQListPopFront(SQList* plist);

//查找元素
int SQListFind(SQList* plist, SQLDATATYPE x);

//插入(指定位置前)
void SQListInsect(SQList* plist, int pst, SQLDATATYPE x);
//删除(指定位置)
void SQListDelete(SQList* plist, int pst);


//打印顺序表
void SQListPrint(SQList* plist);

SQList.c

#include"SQList.h"

//初始化顺序表
void SQListInit(SQList* plist)
{
plist->a = NULL;
//其实也可以在初始化的时候就给a开辟空间(看个人喜好)
plist->size = plist->capacity = 0;
}

//销毁顺序表
void SQListDestroy(SQList* plist)
{
assert(plist);
free(plist->a);
plist->a = NULL;//这一步是为了让a不会野指针
//也可以避免a被重复释放(free函数不会对NULL进行操作)
plist->size = plist->capacity = 0;
}

//扩容函数
//因为扩容函数是在源代码运行的，所以可以不用在头文件进行声明(当然你也可以在头文件进行声明  看个人喜好)
void SQListAdd(SQList* plist)
{
int NewCapacity = plist->capacity == 0 ? 4 : 2 * plist->capacity;//此处为一个三目表达式
//如果plist->capacity==0为真，将4赋给NewCapacity;反之则赋值2*plist->capacity

SQLDATATYPE* tmp = (SQLDATATYPE*)realloc(plist->a, NewCapacity * sizeof(SQLDATATYPE));
if (tmp == NULL)
{
perror("realloc fail");
exit(1);
}
plist->a = tmp;//将调整的空间赋给顺序表
plist->capacity = NewCapacity;//调整容量
}

//插入(尾部)
void SQListPushBack(SQList* plist, SQLDATATYPE x)
{
assert(plist);//检查plist是否为空指针
if (plist->size == plist->capacity)
{
SQListAdd(plist);
}
plist->a[plist->size] = x;
plist->size++;
}

//删除(尾部)
void SQListPopBack(SQList* plist)
{
assert(plist);
assert(plist->size > 0);//如果为0了，我还删什么呢？

plist->size--;//这里很简单，就是将他的size进行--
//size指向的是尾数据的下一块空间，也就是待插入的空间
//我们--size，就相当于把尾数据的空间变成了待插入的空间
//我们新增数据的时候，会把原来的值覆盖掉的
}

//插入(头部)
void SQListPushFront(SQList* plist, SQLDATATYPE x)
{
assert(plist);//检查plist是否为空指针
if (plist->size == plist->capacity)
{
SQListAdd(plist);
}

for (int i = plist->size; i > 0; i--)//将整个顺序表往后挪动一位
{
plist->a[i] = plist->a[i - 1];
}

plist->a[0] = x;
plist->size++;
}

//删除(头部)
void SQListPopFront(SQList* plist)
{
assert(plist);
assert(plist->size > 0);//如果为0了，我还删什么呢？

for (int i = 0; i < plist->size - 1; i++)//将整个顺序表往前挪动一位
{
plist->a[i] = plist->a[i + 1];
}

plist->size--;
}

//查找元素
int SQListFind(SQList* plist, SQLDATATYPE x)
{
assert(plist);
int i = 0;
while (i < plist->size)//size-1处就是最后一个数据
{
if (plist->a[i] == x)//找到了
return i;//返回的是下标
i++;
}
//i=size 跳出循环
//找不到
return EOF;//EOF(-1)
}

//插入(指定位置前)
void SQListInsect(SQList* plist, int pst, SQLDATATYPE x)
{
assert(plist);
if (plist->size == plist->capacity)
{
SQListAdd(plist);
}

//这里有两种情况
//第一种当pst不是首元素
if (pst != 0)
{
for (int i = plist->size; i > pst; i--)//将顺序表pst后面的数据往后挪动一位
{
plist->a[i] = plist->a[i - 1];
}
plist->a[pst] = x;
}

//第二种:当pst是首元素
//那么是首元素了，我们在首元素前进行插入，这是什么？
//这不就是头插吗
//所以我们可以直接调用我们已经写好的头插函数
else
{
SQListPushFront(plist, x);
}
}

//删除(指定位置)
void SQListDelete(SQList* plist, int pst)
{
assert(plist);
assert(plist->size > 0);//如果为0了，我还删什么呢

for (int i = pst; i < plist->size - 1; i++)//将pst后面的数据往前挪动一位
{
plist->a[i] = plist->a[i + 1];
}
plist->size--;
}

//打印顺序表
void SQListPrint(SQList* plist)
{
assert(plist);
if (plist->size == 0)
printf(NULL);
for (int i = 0; i < plist->size; i++)
{
printf("%d ", plist->a[i]);
}
printf("\n");
}

test.c (测试部分)

#include"SQList.h"

void TestSQL()
{
SQList sq;
SQListInit(&sq);

SQListPushBack(&sq, 1);
SQListPushBack(&sq, 2);
SQListPushBack(&sq, 3);
SQListPushBack(&sq, 4);
SQListPushBack(&sq, 5);
SQListPushBack(&sq, 6);

SQListPushFront(&sq, 0);

SQListPopBack(&sq);
SQListPushBack(&sq, 128);
//SQListPrint(&sq);
//SQListPopFront(&sq);
//SQListPrint(&sq);

int flag = SQListFind(&sq, 3);
//if (flag != EOF)
//{
//printf("找到了 下标为%d\n", flag);
//}
//else
//{
//printf("找不到\n");
//}

SQListInsect(&sq, flag, 255);

//SQListDelete(&sq, flag);

SQListPrint(&sq);

SQListDestroy(&sq);
}

int main()
{
TestSQL();
return 0;
}

结语

最后感谢您能阅读完此片文章，如果有任何建议或纠正欢迎在评论区留言。

如果您认为这篇文章对您有所收获，点一个小小的赞就是我创作的巨大动力，谢谢！！！

原文地址：https://blog.csdn.net/2301_80216111/article/details/138896804

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

上一篇：Win10安装mamba个人总结的2种实现方式
下一篇：在Python中，f代表着格式化字符串

大数据治理：构建数据驱动的智能决策体系
随着大数据时代的到来，企业和组织面临着海量数据的挑战和机遇。大数据治理作为一种核心思想，旨在通过规范化、整合和优化数据资源，构建一个可信、高效、安全的数据环境，为智能决策提供支持。本文将介绍大数据治理
阅读更多2024-10-19
【Mysql/xtrabackup】主从恢复（高端操作）
xtrabackup恢复主从，用于mysql数据量大情况
阅读更多2024-10-19
大数据-178 Elasticsearch Query - Java API 索引操作 & 文档操作
通过 Java API，可以向特定索引插入单个文档，并指定文档的 ID（如果不指定，Elasticsearch 会自动生成一个 ID）。获取文档：Java API 可以根据文档 ID 从索引中获取单个
阅读更多2024-10-19
Laravel|Lumen项目配置信息config原理
laravel config 配置原理
阅读更多2024-10-19
玄机平台-应急响应-webshell查杀
玄机靶场，适合应急响应的学习
阅读更多2024-10-19
从Apple Intelligence到远程机器人手术：更快、更安全的网络成企业业务关键
：以苹果公司的Apple Intelligence以及医疗界革命性的远程机器人手术为例，探讨更快、更安全网络对企业的重要性。
阅读更多2024-10-19
【RV1126】板子adb 调试流程
I 0 选择的摄像头序号，可以选择0或1。1. 连接电源线，网线。
阅读更多2024-10-19
【网络】HTTPS协议
本文主要介绍了HTTPS的加密过程，以及其如何保证数据的安全
阅读更多2024-10-19
LeetCode 145.二叉树的后序遍历
给你一棵二叉树的根节点root，返回其节点值的。[0, 100]递归算法很简单，你可以通过迭代算法完成吗？
阅读更多2024-10-19
vue3中使用element-plus的组件，编辑器检查警告爆红找不到名称相关的element组件
在tsconfig.json中，增加标红框文件配置，目的就是将根目录下包含.d.ts的文件中的匹配项，应用于整个项目的匹配项检查，去除代码检查爆红警告。按照以上配置完之后，当在代码中使用element
阅读更多2024-10-19