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

C语言-顺序表

news 文章来源：https://blog.csdn.net/m0_73605503/article/details/140356811 2025/5/7 23:36:48

在这里插入图片描述

🎯引言

欢迎来到HanLop博客的C语言数据结构初阶系列。在这个系列中，我们将深入探讨各种基本的数据结构和算法，帮助您打下坚实的编程基础。本次我将为你讲解。顺序表（也称为数组）是一种线性表，因其简单易用而广泛应用于各类编程任务中。在本篇文章中，我们将介绍顺序表的基本概念、顺序表的创建和操作方法，以及其优缺点。通过一些实际的代码示例，您将更好地掌握顺序表在C语言中的应用，从而为后续学习其他数据结构打下坚实的基础。

👓顺序表

1.线性表

线性表的概念

线性表是数据结构中最基本、最常用的一种结构，由n个数据元素组成一个有限序列。线性表中的数据元素之间存在一对一的线性关系，即每个元素都有唯一的前驱和后继（除了第一个和最后一个元素）。常见的线性表有:顺序表、链表、栈、队列…

线性表的基本特点:

线性关系：每个元素有且仅有一个直接前驱和一个直接后继（第一个元素除外没有前驱，最后一个元素除外没有后继）。
唯一性：每个元素在表中的位置是唯一的。
相同类型：线性表中的所有元素都是相同的数据类型。

逻辑结构

线性表的逻辑结构是指线性表中元素之间的关系。线性表中的元素具有一对一的线性关系，即每个元素都有唯一的前驱和后继（第一个元素除外没有前驱，最后一个元素除外没有后继）。这种逻辑结构决定了线性表的基本操作和特点。

物理结构

线性表的物理结构是指线性表在计算机内存中的存储方式。主要有两种存储方式：

顺序存储结构（顺序表，数组）：
- 元素依次存储在一段连续的内存空间中。
- 优点：可以通过索引快速访问元素，查找效率高。
- 缺点：插入和删除操作效率较低，因为需要移动大量元素。
链式存储结构（链表）：
- 元素存储在任意的内存位置，元素之间通过指针连接。
- 优点：插入和删除操作效率较高，不需要移动元素，只需改变指针。
- 缺点：查找效率较低，因为需要从头遍历到所需位置。

2.顺序表

2.1概念

定义：顺序表是由一组连续的存储单元组成的线性表，元素之间的逻辑顺序与物理存储位置相对应。
特点：
- 元素类型相同，存储在一块连续的内存空间中。
- 支持通过索引快速访问元素。
- 插入和删除操作需要移动大量元素，效率较低。
适用场景：适合于元素数量固定且需要频繁进行查找操作的场景。

2.2结构

顺序表的物理结构如下：

存储结构：使用一段连续的内存空间存储元素，可以通过下标来访问各个元素。(底层本质上数组,对数组进行封装后成了顺序表)

基本操作：

插入操作：
- 定义：在顺序表的指定位置插入一个新的元素。
- 步骤：如果插入位置不在表尾，需要将插入位置后的元素依次后移一位，然后将新元素插入到指定位置。
- 时间复杂度：最坏情况下是O(n)，因为可能需要移动表尾的所有元素。
删除操作：
- 定义：删除顺序表中指定位置的元素。
- 步骤：将删除位置后的元素依次前移一位，覆盖被删除的元素位置。
- 时间复杂度：最坏情况下是O(n)，因为可能需要移动表尾的所有元素。
修改操作：
- 定义：修改顺序表中指定位置的元素值。
- 步骤：直接通过索引定位到指定位置，修改元素的值。
- 时间复杂度：O(1)，因为修改操作是直接定位到位置进行修改。
查找操作：
- 定义：查找顺序表中指定元素或元素位置。
- 步骤：通过顺序表的索引直接访问指定位置的元素，或者遍历整个表查找特定元素。
- 时间复杂度：最坏情况下是O(n)，因为可能需要遍历整个表来查找元素。

2.3分类

2.3.1静态顺序表：

定义：静态顺序表是在程序运行前就确定了大小，内存空间是静态分配的，不可动态改变大小。
特点：数组长度在创建时固定，不能动态增加或减少。
优点：访问速度快，不需要额外的空间管理。
缺点：浪费内存空间，不能适应动态变化的数据需求。

//静态顺序表
typedef int SLDateType;
#define N 10
typedef struct SeqList
{SLDateType a[N];int size;
}SeqList;

2.3.2动态顺序表：

定义：动态顺序表是在程序运行时根据需要动态分配内存空间的顺序表。
特点：可以动态地增加或减少数组的长度。
优点：节约内存空间，适应动态变化的数据需求。
缺点：可能导致频繁的内存分配和拷贝，影响性能。

typedef int SLDateType;
typedef struct SeqList
{SLDateType* a;int size;int capacity;
}SeqList;

2.4动态顺序表的实现

2.4.1SeqList.h文件

//SeqList.h文件的代码
#include <stdio.h>//标准输入输出库，提供了标准的输入输出函数。
#include <stdlib.h>//标准库，提供了动态内存分配、随机数生成、程序控制等函数。
#include <assert.h>//断言库，用于在程序中插入检查点，确保某个条件为真，如果条件为假则终止程序执行。//动态顺序表
typedef int SLDateType;
typedef struct SeqList
{SLDateType* a;int size;int capacity;
}SeqList;//顺序表初始化
void SeqListInit(SeqList* p);
//顺表打印
void SeqListPrint(SeqList* p);
//顺序表的销毁
void SeqListDestory(SeqList* p);//顺序表尾插
void SeqListPushBack(SeqList* p, SLDateType x);
//顺序表增容
void CheckCapacity(SeqList* p);
//顺序表头插
void SeqListPushFront(SeqList* p, SLDateType x);
//顺序表尾删
void SeqListPopBack(SeqList* p);//在pos位置插入数字
void SeqListInsert(SeqList* p, int pos, SLDateType X);
//删除pos位置的数字
void SeqListErase(SeqList* p,int pos);
//找到指定的数字位置,返回下标
int SeqListFind(SeqList* p, SLDateType x);

代码解析:

动态顺序表结构体定义

typedef int SLDateType;
typedef struct SeqList
{SLDateType* a;  // 指向动态数组的指针int size;       // 当前动态顺序表中元素的个数int capacity;   // 当前动态顺序表的容量
} SeqList;

SLDateType：定义动态顺序表中存储的元素类型为 int。
struct SeqList：定义了动态顺序表的结构体，包含：
- SLDateType* a：指向动态数组的指针，用于存储顺序表中的元素。
- int size：当前动态顺序表中元素的个数。
- int capacity：当前动态顺序表的容量，即可以存储的最大元素个数。

函数声明

// 顺序表初始化
void SeqListInit(SeqList* p);
// 顺序表打印
void SeqListPrint(SeqList* p);
// 顺序表的销毁
void SeqListDestory(SeqList* p);// 顺序表尾插
void SeqListPushBack(SeqList* p, SLDateType x);
// 顺序表增容
void CheckCapacity(SeqList* p);
// 顺序表头插
void SeqListPushFront(SeqList* p, SLDateType x);
// 顺序表尾删
void SeqListPopBack(SeqList* p);// 在pos位置插入数字
void SeqListInsert(SeqList* p, int pos, SLDateType X);
// 删除pos位置的数字
void SeqListErase(SeqList* p, int pos);
// 找到指定的数字位置,返回下标
int SeqListFind(SeqList* p, SLDateType x);

这些函数声明定义了动态顺序表的基本操作：

SeqListInit：初始化动态顺序表。
SeqListPrint：打印动态顺序表中的元素。
SeqListDestory：销毁动态顺序表，释放内存。
SeqListPushBack：尾部插入元素。
CheckCapacity：检查并增加动态顺序表的容量。
SeqListPushFront：头部插入元素。
SeqListPopBack：尾部删除元素。
SeqListInsert：在指定位置插入元素。
SeqListErase：删除指定位置的元素。
SeqListFind：查找指定元素并返回其位置。

这些函数声明提供了对动态顺序表进行初始化、增删改查等基本操作的接口，具体的实现应该在对应的 SeqList.c 文件中完成。

2.4.2SeqList.c文件

//SeqList.c文件
//这里引入了头文件 SeqList.h，其中定义了动态顺序表的结构体 SeqList 和函数声明。
#include "SeqList.h"
//顺序表的初始化
void SeqListInit(SeqList* p)
{assert(p);p->a = NULL;p->size = p->capacity = 0;
}//顺序表的销毁
void SeqListDestory(SeqList* p)
{assert(p);free(p->a);p->a = NULL;p->size = p->capacity = 0;
}//顺序表打印
void SeqListPrint(SeqList* p)
{assert(p);int i = 0;for (i = 0; i < p->size; i++){printf("%d ", p->a[i]);}printf("\n");
}//检查并增加动态顺序表的容量。
void CheckCapacity(SeqList* p)
{assert(p);int newcapacity = p->capacity == 0 ? 4 : p->capacity * 2;if (p->capacity == p->size){p->capacity = newcapacity;SLDateType* tmp = (SLDateType*)realloc(p->a, p->capacity * sizeof(SLDateType));if (tmp != NULL){p->a = tmp;}else{exit(1);}}
}//顺序表尾插
void SeqListPushBack(SeqList* p, SLDateType x)
{assert(p);CheckCapacity(p);p->a[p->size] = x;p->size++;
}//顺序表头插
void SeqListPushFront(SeqList* p, SLDateType x)
{assert(p);CheckCapacity(p);int i = 0;for (i = p->size; i > 0; i--){p->a[i] = p->a[i-1];}p->a[0] = x;p->size++;
}//顺序表尾删
void SeqListPopBack(SeqList* p)
{assert(p);assert(p->size);p->size--;}//顺序表头删
void SeqListPopFront(SeqList* p)
{assert(p);assert(p->size);int i = 0;for (i = 0; i < p->size-1; i++){p->a[i] = p->a[i + 1];}p->size--;
}//在pos位置插入数字
void SeqListInsert(SeqList* p, int pos, SLDateType x)
{assert(p != NULL);assert(pos >= 0 && pos <= p->size);//检查是否需要增容CheckCapacity(p);for (int i = p->size-1; i > pos-1 ; --i){p->a[i + 1] = p->a[i];//p->a[pos+1]=p->a[pos]}p->a[pos] = x;p->size++;
}//删除pos位置的数字
void SeqListErase(SeqList* p, int pos)
{assert(p != NULL);assert(pos >= 0 && pos < p->size);for (int i = pos; i < p->size-1; i++){p->a[i] = p->a[i + 1];//p->a[size-2]=p->a[size-1]}p->size--;
}//找到指定的数字位置,返回下标
int SeqListFind(SeqList* p, SLDateType x)
{assert(p != NULL);for (size_t i = 0; i < p->size; i++){if (p->a[i] == x){return i;}}return -1;
}

代码解析:

初始化函数 SeqListInit

void SeqListInit(SeqList* p)
{assert(p);p->a = NULL;p->size = p->capacity = 0;
}

功能：初始化动态顺序表。
说明：将动态顺序表指针 p 所指向的顺序表 a 设置为 NULL，并将 size（元素个数）和 capacity（容量）都设置为 0。使用断言 assert(p) 确保传入的指针 p 不为空。

销毁函数 SeqListDestory

void SeqListDestory(SeqList* p)
{assert(p);free(p->a);p->a = NULL;p->size = p->capacity = 0;
}

功能：销毁动态顺序表。
说明：释放动态顺序表 a 所指向的内存空间，将 a 置为 NULL，并将 size 和 capacity 置为 0。同样使用断言 assert(p) 确保传入的指针 p 不为空。

打印函数 SeqListPrint

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

功能：打印动态顺序表中的元素。
说明：遍历顺序表 a 中的每个元素，依次打印出来。使用断言 assert(p) 确保传入的指针 p 不为空。

增容函数 CheckCapacity

void CheckCapacity(SeqList* p)
{assert(p);int newcapacity = p->capacity == 0 ? 4 : p->capacity * 2;if (p->capacity == p->size){p->capacity = newcapacity;SLDateType* tmp = (SLDateType*)realloc(p->a, p->capacity * sizeof(SLDateType));if (tmp != NULL){p->a = tmp;}else{exit(1);}}
}

功能：检查并增加动态顺序表的容量。
说明：
- 如果当前顺序表 a 的容量 capacity 等于当前元素个数 size，则表示需要增加容量。
- 计算新的容量 newcapacity，如果当前容量为 0，则设置为 4，否则扩大为原来的两倍。
- 使用 realloc 函数重新分配 a 的内存空间，将新的容量分配给 a。如果分配失败，程序退出。
- 使用断言 assert(p) 确保传入的指针 p 不为空。

尾部插入函数 SeqListPushBack

void SeqListPushBack(SeqList* p, SLDateType x)
{assert(p);CheckCapacity(p);p->a[p->size] = x;p->size++;
}

功能：在动态顺序表尾部插入元素 x。
说明：首先调用 CheckCapacity 函数检查并增加容量。然后将元素 x 插入到顺序表 a 的末尾，并更新 size。

头部插入函数 SeqListPushFront

void SeqListPushFront(SeqList* p, SLDateType x)
{assert(p);CheckCapacity(p);int i = 0;//元素从后往前依次往后移动一位 注:不能从前往后 因为前面的元素往后移动会覆盖掉后面的元素for (i = p->size; i > 0; i--){p->a[i] = p->a[i-1];}p->a[0] = x;p->size++;
}

功能：在动态顺序表头部插入元素 x。
说明：首先调用 CheckCapacity 函数检查并增加容量。然后将顺序表 a 中的所有元素后移一位，为新元素腾出空间，最后将 x 插入到顺序表 a 的第一个位置，并更新 size。

尾部删除函数 SeqListPopBack

void SeqListPopBack(SeqList* p)
{assert(p);assert(p->size > 0);p->size--;
}

功能：从动态顺序表尾部删除元素。
说明：首先使用断言 assert(p) 确保顺序表不为空，然后将 size 减一，表示删除尾部的元素。

头部删除函数 SeqListPopFront

void SeqListPopFront(SeqList* p)
{assert(p);assert(p->size > 0);int i = 0;//元素从前往后依次向前移动一位 for (i = 0; i < p->size-1; i++){p->a[i] = p->a[i + 1];}p->size--;
}

功能：从动态顺序表头部删除元素。
说明：首先使用断言 assert(p) 确保顺序表不为空，然后将顺序表 a 中的所有元素前移一位，覆盖掉第一个元素，最后将 size 减一，表示删除头部的元素。

插入函数 SeqListInsert

void SeqListInsert(SeqList* p, int pos, SLDateType x)
{assert(p != NULL);assert(pos >= 0 && pos <= p->size);CheckCapacity(p);//元素从后往前依次向后移动一位 for (int i = p->size-1; i >= pos; --i){p->a[i + 1] = p->a[i];}p->a[pos] = x;p->size++;
}

功能：在指定位置 pos 插入元素 x。
说明：
- 首先使用断言确保顺序表和位置参数有效。
- 调用 CheckCapacity 函数检查并增加容量。
- 将插入位置 pos 后的所有元素依次后移一位，为新元素 x 腾出空间。
- 将元素 x 插入到指定位置 pos，并更新 size。

删除函数 SeqListErase

void SeqListErase(SeqList* p, int pos)
{assert(p != NULL);assert(pos >= 0 && pos < p->size);//元素从前往后依次向前移动一位 for (int i = pos; i < p->size-1; i++){p->a[i] = p->a[i + 1];}p->size--;
}

功能：删除指定位置 pos 的元素。
说明：
- 首先使用断言确保顺序表和位置参数有效。
- 将指定位置 pos 后的所有元素依次前移一位，覆盖掉要删除的元素。
- 最后将 size 减一，表示删除了一个元素。

查找函数 SeqListFind

int SeqListFind(SeqList* p, SLDateType x)
{assert(p != NULL);for (size_t i = 0; i < p->size; i++){if (p->a[i] == x){return i;}}return -1;
}

功能：查找顺序表中值为 x 的元素，返回其位置索引。
说明：
- 使用断言确保顺序表有效。
- 遍历顺序表 a 中的所有元素，找到第一个值等于 x 的元素，返回其位置索引。
- 如果未找到，返回 -1 表示未找到。

🥇结语

通过本篇文章，我们详细介绍了顺序表这一重要的数据结构及其在C语言中的实现与应用。我们探讨了顺序表的基本概念、操作方法以及优缺点，并通过实例代码展示了如何在实际编程中使用顺序表。掌握顺序表不仅有助于理解其他更复杂的数据结构，还能提高代码编写和优化能力。希望本文能为您的编程之旅提供有益的指导。请继续关注HanLop博客，下一篇文章我们将探讨另一种常见的数据结构——链表，敬请期待！

🎯引言