🎯引言
欢迎来到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博客,下一篇文章我们将探讨另一种常见的数据结构——链表,敬请期待!