建行门户网站,厦门建设局网站首页6,传媒广告公司简介,资源网站怎么做#x1f3af;引言
欢迎来到HanLop博客的C语言数据结构初阶系列。在这个系列中#xff0c;我们将深入探讨各种基本的数据结构和算法#xff0c;帮助您打下坚实的编程基础。本次我将为你讲解。顺序表#xff08;也称为数组#xff09;是一种线性表#xff0c;因其简单易用…
引言
欢迎来到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[pos1]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博客下一篇文章我们将探讨另一种常见的数据结构——链表敬请期待
