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

数据结构与算法(C语言版)P2---线性表之顺序表

news 2025/6/28 20:42:47

前景回顾
数据结构
数据的逻辑结构
数据的存储结构
数据的运算
线性结构
非线性结构
线性表
栈
队列
字符串,数组,广义表
树形结构
图形结构
索引,排序,插入,删除,修改等

1、线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表有：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但在物理结构上并不一定是连续的，线性表在物理上存储时，通常以__数组__和__链式结构__的形式存储。

顺序表本质上就是数组。

在这里插入图片描述

2、顺序表

2.1、概念及结构

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

顺序表就是数组，但是在数组的基础上，它还要求数据是从头开始存储并且是连续存储的，不能跳跃间隔。

顺序表一般可以分为：

1、静态顺序表：使用固定长数组存储元素。

在这里插入图片描述

2、动态顺序表：使用动态开辟的数组存储。

在这里插入图片描述

3、顺序表的实现

【说明】：这里使用动态数组来实现顺序表。

顺序表主要有以下几个接口功能：

  • 打印（SeqListPrint）
  • 结构体初始化（SeqListInit）
  • 释放空间（SeqListDestory）
  • 检查扩容（SeqListCheckCapacity）
  • 头插（SeqListPushBack）
  • 头删（SeqListPopBack）
  • 尾插（SeqListPushFront）
  • 尾删（SeqListPopFront）
  • 查找元素（SeqListFind）
  • 在指定pos下标位置插入元素（SeqListInsert）
  • 删除pos位置的数据（SeqListErase）

3.1、定义结构体

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

a指针变量表示需要动态开辟的数组。
size变量表示数组中有效数据个数。
capacity变量表示动态开辟数组的空间大小。

3.2、结构体初始化接口实现

//结构体初始化
void SeqListInit(SL* ps)
{ps->a = NULL;ps->size = ps->capacity = 0;
}

3.3、检查扩容接口实现

因为我们采用动态开辟数组的形式来实现顺序表，所以当我们在进行任何一个插入操作时，都需要先申请空间，以便数据的插入。
这里有几种情况需要我们处理：

  • 整个顺序表没有空间，扩容
  • 空间不够，扩容。
  • 空间足够，直接插入数即可。
void SeqListCheckCapacity(SL* ps)
{if (ps->size == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newcapacity);if (tmp == NULL){printf("realloc fail\n");exit(-1);}ps->a = tmp;ps->capacity = newcapacity;}
}

3.4、头插接口实现

void SeqListPushFront(SL* ps, SLDataType x)
{SeqListCheckCapacity(ps);int end = ps->size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];end--;}ps->a[0] = x;ps->size++;
}

头插的核心思想：将全体数据元素向后移动。比如现在有数组int b = [1,2,3,4,5]，现在想头插数据6，可以采取这样的方法：把1，2，3，4，5全部整体向后移一位。然后再把6进行头插。

3.5、打印接口实现

void SeqListPrint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");
}

3.6、销毁接口实现

void SeqListDestroy(SL* ps)
{free(ps->a);ps->a = NULL;ps->size = ps->capacity =  0;
}

3.7、头删接口实现

void SeqListPopFront(SL* ps)
{//这里需要加个判断，判断size是否>0，否则防止越界访问if (ps->size > 0){int begin = 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;}
}

头删核心思想：把数组中下标为1到下标为最后一个的所有元素全部向前移动。

3.8、尾插接口实现

void SeqListPushBack(SL* ps, SLDataType x)
{//先检查扩容SeqListCheckCapacity(ps);ps->a[ps->size] = x;ps->size++;
}

3.9、尾删接口实现

void SeqListPopBack(SL* ps)
{if (ps->size > 0){ps->size--;}
}

3.10、查询指定元素

//查询指定元素，并返回下标
int SeqListFind(SL* ps, SLDataType x)
{for (int i = 0; i < ps->size; i++){if (x == ps->a[i]){return i;}}return -1;
}

3.11、在指定pos下标位置插入

void SeqListInsert(SL* ps, int pos, SLDataType x)
{assert(pos >= 0 && ps->size >= pos);SeqListCheckCapacity(ps);int end = ps->size - 1;while (pos <= end){ps->a[end + 1] = ps->a[end];end--;}ps->a[pos] = x;ps->size++;
}

3.12、删除pos下标位置的数据

void SeqListErase(SL* ps, int pos)
{assert(pos >= 0 && ps->size > pos);int begin = pos + 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;
}

以上就是使用动态数组实现顺序表的过程。下面展示全代码。

4、全代码展示

这里使用三个文件：

  • seqlist.h：用于结构体、各种函数接口的声明。
  • seqlist.c：用于各种函数接口的定义。
  • test.c：用于创建顺序表，实现顺序表。

4.1、seqlist.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLDataType;typedef struct SeqList
{SLDataType* a;int size;int capacity;
}SL;//结构体初始化
void SeqListInit(SL* ps);//检查扩容
void SeqListCheckCapacity(SL* ps);//头插
void SeqListPushFront(SL* ps, SLDataType x);//打印
void SeqListPrint(SL* ps);//销毁
void SeqListDestroy(SL* ps);//头删
void SeqListPopFront(SL* ps);//尾插
void SeqListPushBack(SL* ps, SLDataType x);//尾删
void SeqListPopBack(SL* ps);//查询指向元素，并返回下标
int SeqListFind(SL* ps, SLDataType x);//在指定pos下标位置插入
void SeqListInsert(SL* ps, int pos, SLDataType x);//删除pos下标位置的数据
void SeqListErase(SL* ps, int pos);

4.2、seqlist.c

#include "list.h"//结构体初始化
void SeqListInit(SL* ps)
{ps->a = NULL;ps->size = ps->capacity = 0;
}//检查扩容
void SeqListCheckCapacity(SL* ps)
{if (ps->size == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newcapacity);if (tmp == NULL){printf("realloc fail\n");exit(-1);}ps->a = tmp;ps->capacity = newcapacity;}
}//头插
void SeqListPushFront(SL* ps, SLDataType x)
{SeqListCheckCapacity(ps);int end = ps->size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];end--;}ps->a[0] = x;ps->size++;
}//打印
void SeqListPrint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");
}//销毁
void SeqListDestroy(SL* ps)
{free(ps->a);ps->a = NULL;ps->size = ps->capacity =  0;
}//头删
void SeqListPopFront(SL* ps)
{//这里需要加个判断，判断size是否>0，否则防止越界访问if (ps->size > 0){int begin = 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;}
}//尾插
void SeqListPushBack(SL* ps, SLDataType x)
{//先检查扩容SeqListCheckCapacity(ps);ps->a[ps->size] = x;ps->size++;
}//尾删
void SeqListPopBack(SL* ps)
{if (ps->size > 0){ps->size--;}
}//扩展接口
//查询指定元素，并返回下标
int SeqListFind(SL* ps, SLDataType x)
{for (int i = 0; i < ps->size; i++){if (x == ps->a[i]){return i;}}return -1;
}//在指定pos下标位置插入
void SeqListInsert(SL* ps, int pos, SLDataType x)
{assert(pos >= 0 && ps->size >= pos);SeqListCheckCapacity(ps);int end = ps->size - 1;while (pos <= end){ps->a[end + 1] = ps->a[end];end--;}ps->a[pos] = x;ps->size++;
}//删除pos下标位置的数据
void SeqListErase(SL* ps, int pos)
{assert(pos >= 0 && ps->size > pos);int begin = pos + 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;
}

4.3、test.c

#include "list.h"int main()
{SL sl;SeqListInit(&sl);SeqListPushFront(&sl, 1);SeqListPushFront(&sl, 2);SeqListPushFront(&sl, 3);int pos = SeqListFind(&sl, 2);SeqListErase(&sl, pos);SeqListPrint(&sl);SeqListDestroy(&sl);return 0;
}

5、顺序表的优缺点

顺序表的缺陷：

  • 空间不够了需要扩容，扩容是需要付出代价的。
  • 避免频繁的扩容，我们满了基本都是扩2倍。这可能就会导致一定空间的浪费。
  • 顺序表要求数据从开始位置连续存储，那么我们在头部或者中间位置插入、删除数据就需要挪动数据，有性能消耗，效率不高。

顺序表的优点：

  • 支持随机访问。
  • 存储密度大
http://www.lryc.cn/news/173402.html

相关文章：

  • AI写文章软件-怎么选择不同的AI写文章软件
  • VSCode远程连接服务器报错:Could not establish connection to
  • openssl 用法整理 —— 筑梦之路
  • Mac安装SPSS 26(含安装包)
  • uniapp存值和取值方法
  • Apache Beam 2.50.0发布,该版本包括改进功能和新功能
  • 华为云云耀云服务器 L 实例评测｜配置教程 + 用 Python 简单绘图
  • 栈的简单应用（利用Stack进行四则混合运算）（JAVA）
  • Python---异常
  • 视频编解码器H.264和H265有什么区别？
  • 网络安全进阶学习第十六课——业务逻辑漏洞介绍
  • 华为OD：跳房子I
  • C语言自定义类型详解（1）结构体知识汇总
  • 小程序中如何查看会员的访问记录
  • SpringCloud Alibaba - Sentinel
  • 内存泄漏，内存溢出，抽象类和接口，netstat、ping、ifconfig的区别
  • TensorFlow安装 ，在原本的虚拟环境下配置Tensorflow.
  • 如何使用HTML, CSS和JavaScript开发一个浏览器打字游戏：从零到一的详细步骤与完整代码教程
  • 安卓玩机搞机----不用刷第三方官改固件即可享受“高级设置”的操作 ChiMi安装使用步骤
  • 代码随想录|392.判断子序列，115.不同的子序列（需要二刷）
  • Linux——文件系统
  • 《动手学深度学习 Pytorch版》 7.3 网络中的网络(NiN)
  • 古代有没有电子元器件？
  • log4j2或者logback配置模版实现灵活输出服务名
  • 使用HTTP爬虫ip中的常见误区与解决方法
  • MySQL学习笔记3
  • 快速掌握ES6
  • 电池厂提供excel电池曲线zcv到mtk电池曲线zcv转换
  • 重写和重载、抽象类和接口
  • Untiy UDP局域网 异步发送图片