做网站要有哪些知识,深圳软件开发定制,凡科建站怎么删除网站建设,制作报价网站#x1f493; 博客主页#xff1a;江池俊的博客⏩ 收录专栏#xff1a;数据结构探索#x1f449;专栏推荐#xff1a;✅C语言初阶之路 ✅C语言进阶之路#x1f4bb;代码仓库#xff1a;江池俊的代码仓库#x1f525;编译环境#xff1a;Visual Studio 2022#x1f38… 博客主页江池俊的博客⏩ 收录专栏数据结构探索专栏推荐✅C语言初阶之路 ✅C语言进阶之路代码仓库江池俊的代码仓库编译环境Visual Studio 2022欢迎大家点赞评论收藏⭐ 文章目录 线性表顺序表概念及结构. 静态顺序表使用定长数组存储元素。. 动态顺序表使用动态开辟的数组存储。 接口实现有哪些接口呢准备工作初始化扩容顺序表打印顺序表销毁尾插尾删头插头删指定pos下标位置插入数据删除pos位置的数据查找修改pos位置的数据 源码SeqList.h 文件SeqList.c 文件Test.c 文件 线性表 【维基百科】 线性表英语Linear List是由nn≥0个数据元素结点a[0]a[1]a[2]…a[n-1]组成的有限序列。 其中 数据元素的个数n定义为表的长度 “list”.length() “list”.length() 0表里没有一个元素时称为空表将非空的线性表n1记作a[0]a[1]a[2]…a[n-1]数据元素a[i]0≤i≤n-1只是个抽象符号其具体含义在不同情况下可以不同 一个数据元素可以由若干个数据项组成。数据元素称为记录含有大量记录的线性表又称为文件。这种结构具有下列特点存在一个唯一的没有前驱的头数据元素存在一个唯一的没有后继的尾数据元素此外每一个数据元素均有一个直接前驱和一个直接后继数据元素。 线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。 顺序表
概念及结构 【维基百科】 顺序表是在计算机内存中以数组的形式保存的线性表是指用一组地址连续的存储单元依次存储数据元素的线性结构使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。 即顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。
. 静态顺序表使用定长数组存储元素。 . 动态顺序表使用动态开辟的数组存储。 接口实现
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了空间开多了浪费开少了不够用。
所以现实中基本都是使用动态顺序表根据需要动态的分配空间大小所以下面我们实现动态顺序表。
这里的接口其实就是 接口函数 这些 接口函数 提供了顺序表的各种基本操作允许我们对顺序表进行 增、删、查、改 等操作。
有哪些接口呢
// 基本 增删查改 接口 --- 命名风格是跟着STL走的方便后续学习STL
// 顺序表初始化
void SeqListInit(SL* psl);
// 检查空间如果满了进行增容 -- 扩容
void SLCheckCapacity(SL* psl);
// 顺序表尾插
void SeqListPushBack(SL* psl, SLDataType x);
// 顺序表头插
void SeqListPushFront(SL* psl, SLDataType x);
// 顺序表尾删
void SeqListPopBack(SL* psl);
// 顺序表头删
void SeqListPopFront(SL* psl);
// 顺序表查找
int SeqListFind(SL* psl, SLDataType x);
//顺序表的修改
void SeqListModify(SL* psl,int pos, SLDataType x);
// 顺序表在pos位置插入x可以实现头插和尾插
void SeqListInsert(SL* psl, int pos, SLDataType x);
// 顺序表删除pos位置的值可以实现头删和尾删
void SeqListErase(SL* psl, int pos);
// 顺序表打印
void SeqListPrint(SL* psl);
// 顺序表销毁
void SeqListDestroy(SL* psl);接下来我将带着大家一 一实现这些接口。
准备工作
在写顺序表前我们需要创建工程这里为了让大家养成模块化的好习惯我们尽量将代码分成三个文件来写。这里我打开的编译器是 vs 2022在资源管理器的 头文件 中创建 SeqList.h 文件此文件作用主要是为了存储各种头文件和接口函数的声明以及顺序表结构体的创建在源文件中创建 SeqList.c 文件用来实现接口函数Test.c 文件用来测试顺序表的各个接口。具体如下图所示 注意
为了能够在顺序表中方便地存储各种类型的数据我们可以使用 typedef 将要存储的数据类型重命名为 SLDataType 这样在定义顺序表的数据类型时只需要使用 SLDataType 就行了修改数据类型时只需要修改 typedef 后面跟着的这个数据类型这样就大大方便了对不同类型数据的存储。类似的为了方便结构体的定义和使用我们也可以使用 typedef 将结构体定义一个简单的别名为 SL。
#pragma once#includestdio.h
#includestdlib.h // NULL、size_t
#includeassert.h// 静态的顺序表:使用定长数组存储元素。
// 特点如果满了就不让插入
// 缺点N给小了不够用给多了浪费这个很难确定
//#define N 100
//typedef int SLDataType; // 给int取别名
//struct SeqList // 创建顺序表
//{
// SLDataType a[N]; // 定长数组
// int size; // 存储的有效数据的个数
//};// 动态顺序表使用动态开辟的数组存储。
//typedef double SLDatatype;
typedef int SLDataType; //重定义类型名称方便顺序表对不同类型的数据的存储和操作
typedef struct SeqList // 创建顺序表
{SLDataType* a; //指向动态开辟的数组int size; // 存储的有效数据的个数int capacity; // 容量空间大小
}SL; //将结构体类型取别名为 SL初始化 这里我们实现动态顺序表所以刚开始时我们可以假设给定顺序表的大小为 4即能存放4个元素不够就扩容顺序表中刚开始是没有元素的。 //顺序表初始化
void SeqListInit(SL* psl)
{//防止psl为空指针即防止传错结构体地址assert(psl);psl-a (SLDataType*)malloc(sizeof(SLDataType) * 4);//判断能否成功开辟空间if (psl-a NULL){perror(malloc fail);//将系统错误信息输出到屏幕return;}psl-capacity 4;psl-size 0;
}扩容 在后续对顺序表进行操作过程中我们会插入数据如果顺序表空间不够我们就需要使用 realloc 函数进行扩容。 这里newcapacity表示扩容后能存放的元素个数即空间的容量tmp表示的是扩容后的空间的地址如果顺序表的空间为空就给定能存放4个元素的空间如果空间不够就在原来空间的基础上增加 1 倍的空间这样也依然无法避免空间的部分浪费所以就有了链表后续文章我会为大家带来。 // 扩容 --- 检查空间如果满了进行增容
void SLCheckCapacity(SL* psl)
{if (psl-size psl-capacity){//如果没有空间或者空间不足就扩容int newcapacity (psl-capacity 0 ? 4 : psl-capacity * 2);SLDataType* tmp (SLDataType*)realloc(psl-a, sizeof(SLDataType) * newcapacity);if (tmp NULL){printf(realloc fail\n);exit(-1); //退出程序}psl-a tmp;psl-capacity newcapacity;}
}顺序表打印 打印比较简单这里我们只需要依次遍历每一个节点就行。 //打印
void SeqListPrint(SL* psl)
{//防止psl为空指针即防止传错结构体地址assert(psl);//遍历for (int i 0; i psl-size; i){printf(%d , psl-a[i]);}printf(\n);
}顺序表销毁 因为是动态开辟的所以如果空间不用我们就需要销毁掉。如果不销毁会存在内存泄漏的风险所以这里我们使用free函数释放开辟的动态空间并把有效数据个数和容量空间都置为0。 //销毁
void SeqListDestroy(SL* psl)
{assert(psl);free(psl-a);psl-a NULL;psl-size 0;psl-capacity 0;
}尾插 尾插就是在最后一个元素的后面插入一个元素即在size下标位置处插入数据但要注意的是当capacity空间满了就需要扩容因此我们要调用SLCheckCapacity函数。 //尾插
void SeqListPushBack(SL* psl, SLDataType x)
{assert(psl);//psl-a[psl-size] x;//psl-size;SLCheckCapacity(psl); // 检查扩容psl-a[psl-size] x;//复用指定pos下标位置插入数据的函数//SeqListInsert(psl, psl-size, x);
}尾删 尾删其实就是将顺序表最后一个数据删去要实现这一操作其实只需要将有效数据个数减一就可以了即size--但是在尾删之前要先判断顺序表中是否有元素如果没有元素就没有必要删了。 //尾删
void SeqListPopBack(SL* psl)
{assert(psl);//温柔的处理方式//if (psl-size 0)//{// psl-size--;//}//else//{// printf(没有数据能够再删了\n);// exit(-1); //退出程序//}//暴力的处理方式assert(psl-size 0);//确保顺序表中有数据psl-size--;//复用pos下标位置删除数据的函数//SeqListErase(psl, psl-size - 1);
}头插 头插操作其实就是在顺序表下表为 0 的位置插入数据然后 size但是在此之前要判断顺序表容量空间是否已满所以要先调用 SLCheakCapacity 函数。 //头插
void SeqListPushFront(SL* psl, SLDataType x)
{assert(psl);SLCheckCapacity(psl);//挪动数据int end psl-size -1;while (end 0){psl-a[end 1] psl-a[end];end--;}psl-a[0] x;psl-size;//复用指定pos下标位置插入数据的函数//SeqListInsert(psl, 0, x);
}头删 头删的实现其实只需要将顺序表开头后面的数据依次往前挪动然后将 size-- 就可以了这里要从前往后挪如果从后往前挪数据会被覆盖。注意这里与尾删类似在头删之前要先判断顺序表中是否有元素如果没有元素就没有必要删了。 //头删
void SeqListPopFront(SL* psl)
{assert(psl);assert(psl-size 0);//有数据才能删没数据就会报错int begin 1;while (begin psl - size){psl-a[begin - 1] psl-a[begin];begin;}psl-size--;//复用pos效标位置删除数据的函数//SeqListErase(psl, 0);
}指定pos下标位置插入数据 我们只需要将顺序表中pos位置到最后的数据依次往后挪动从后往前挪然后将pos下标位置的数据改为要插入的数据最后 size 即可。但是我们依然要判断是否满容,所以在插入数据前要调用 SLCheakCapacity 函数。同时我们也要判断pos位置是否合理防止越界访问。 //指定pos下标位置插入数据
void SeqListInsert(SL* psl, int pos, SLDataType x)
{assert(psl);//if (pos psl-size || pos 0)//{// printf(pos的下标位置越界);// return;//}//暴力的方式处理pos下标不能越界assert(pos 0 pos psl-size);//如果没有空间或者空间不足就扩容SLCheckCapacity(psl);//挪动数据int end psl-size - 1;while (end pos){psl-a[end 1] psl-a[end];end--;}psl-a[pos] x;psl-size;
}删除pos位置的数据 与头删类似我们只需要将pos位置后的数据依次往前挪动将pos位置处的数据覆盖然后再 size-- 就可以了。但是要判断pos位置是否合理防止越界访问。 //删除pos位置的数据结合SeqListFind函数可以删除指定的数据
void SeqListErase(SL* psl, int pos)
{assert(psl);assert(pos 0 pos psl-size);//pos位置需要有数据//挪动数据int begin pos 1;while (begin psl-size){psl-a[begin - 1] psl-a[begin];begin;}psl-size--;
}查找 这个比较简单我们只需要遍历一遍顺序表查找相应数据若找到就返回下标若没找到就返回-1。 //查找找到了返回下标没找到返回-1
int SeqListFind(SL* psl, SLDataType x)
{assert(psl);for (int i 0; i psl-size; i){if (psl-a[i] x){return i;}}return -1;
}修改pos位置的数据 通过pos下标直接修改 //修改pos位置的数据
void SeqListModify(SL* psl, int pos, SLDataType x)
{assert(psl);assert(pos 0 pos psl-size);psl-a[pos] x;
}源码
SeqList.h 文件
#pragma once#includestdio.h
#includestdlib.h//NULL、size_t
#includeassert.h// 静态的顺序表:使用定长数组存储元素。
// 特点如果满了就不让插入
// 缺点N给小了不够用给多了浪费这个很难确定
//#define N 10000
//typedef int SLDatatype; // 给int取别名
//struct SeqList // 创建顺序表
//{
// SLDatatype a[N]; // 定长数组
// int size; // 存储的有效数据的个数
//};
//静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了空间开多了浪
//费开少了不够用。所以现实中基本都是使用动态顺序表根据需要动态的分配空间大小所以下面我们实
//现动态顺序表。// 动态顺序表使用动态开辟的数组存储。
//typedef double SLDatatype;
typedef int SLDataType; //重定义类型名称方便顺序表对不同类型的数据的存储和操作
typedef struct SeqList
{SLDataType* a; //指向动态开辟的数组int size; // 存储的有效数据的个数int capacity; // 容量空间大小
}SL;// 基本 增删查改 接口 --- 命名风格是跟着STL走的方便后续学习STL
// 顺序表初始化
void SeqListInit(SL* psl);// 检查空间如果满了进行增容
void SLCheckCapacity(SL* psl);// 顺序表尾插
void SeqListPushBack(SL* psl, SLDataType x);
// 顺序表尾删
void SeqListPopBack(SL* psl);
// 顺序表头插
void SeqListPushFront(SL* psl, SLDataType x);
// 顺序表头删
void SeqListPopFront(SL* psl);
// 顺序表查找
int SeqListFind(SL* psl, SLDataType x);
// 顺序表在pos位置插入x可以实现头插和尾插
void SeqListInsert(SL* psl, int pos, SLDataType x);
// 顺序表删除pos位置的值可以实现头删和尾删
void SeqListErase(SL* psl, int pos);// 顺序表打印
void SeqListPrint(SL* psl);
// 顺序表销毁
void SeqListDestroy(SL* psl);//顺序表的修改
void SeqListModify(SL* psl, int pos, SLDataType x);SeqList.c 文件
#includeSeqList.h//void SeqListInit(SL* psl)
//{
// psl-a NULL;
// psl-size 0;
// psl-capacity 0;
//}//顺序表初始化
void SeqListInit(SL* psl)
{//防止psl为空指针即防止传错结构体地址assert(psl);psl-a (SLDataType*)malloc(sizeof(SLDataType) * 4);//判断能否成功开辟空间if (psl-a NULL){perror(malloc fail);//将系统错误信息输出到屏幕return;}psl-capacity 4;psl-size 0;
}
//销毁
void SeqListDestroy(SL* psl)
{assert(psl);free(psl-a);psl-a NULL;psl-size 0;psl-capacity 0;
}
//打印
void SeqListPrint(SL* psl)
{assert(psl);for (int i 0; i psl-size; i){printf(%d , psl-a[i]);}printf(\n);
}
// 检查空间如果满了进行增容
void SLCheckCapacity(SL* psl)
{assert(psl);if (psl-size psl-capacity){//如果没有空间或者空间不足就扩容int newcapacity (psl-capacity 0 ? 4 : psl-capacity * 2);SLDataType* tmp (SLDataType*)realloc(psl-a, sizeof(SLDataType) * newcapacity);if (tmp NULL){printf(realloc fail\n);exit(-1);//退出程序}psl-a tmp;psl-capacity newcapacity;}
}
//尾插
void SeqListPushBack(SL* psl, SLDataType x)
{assert(psl);//psl-a[psl-size] x;//psl-size;SLCheckCapacity(psl);//检查扩容psl-a[psl-size] x;//复用指定pos下标位置插入数据的函数//SeqListInsert(psl, psl-size, x);
}
//尾删
void SeqListPopBack(SL* psl)
{assert(psl);//温柔的处理方式//if (psl-size 0)//{// psl-size--;//}//else//{// printf(没有数据能够再删了\n);// exit(-1);//}//暴力的处理方式assert(psl-size 0);//确保顺序表中有数据psl-size--;//复用pos下标位置删除数据的函数//SeqListErase(psl, psl-size - 1);
}
//头插
void SeqListPushFront(SL* psl, SLDataType x)
{assert(psl);SLCheckCapacity(psl);//挪动数据int end psl-size -1;while (end 0){psl-a[end 1] psl-a[end];end--;}psl-a[0] x;psl-size;//复用指定pos下标位置插入数据的函数//SeqListInsert(psl, 0, x);
}
//头删
void SeqListPopFront(SL* psl)
{assert(psl);assert(psl-size 0);//有数据才能删没数据就会报错int begin 1;while (begin psl - size){psl-a[begin - 1] psl-a[begin];begin;}psl-size--;//复用pos效标位置删除数据的函数//SeqListErase(psl, 0);
}
//查找找到了返回下标没找到返回-1
int SeqListFind(SL* psl, SLDataType x)
{assert(psl);for (int i 0; i psl-size; i){if (psl-a[i] x){return i;}}return -1;
}
//指定pos下标位置插入数据
void SeqListInsert(SL* psl, int pos, SLDataType x)
{assert(psl);//if (pos psl-size || pos 0)//{// printf(pos的下标位置越界);// return;//}//暴力的方式处理pos下标不能越界assert(pos 0 pos psl-size);//如果没有空间或者空间不足就扩容SLCheckCapacity(psl);//挪动数据int end psl-size - 1;while (end pos){psl-a[end 1] psl-a[end];end--;}psl-a[pos] x;psl-size;
}//删除pos位置的数据结合SeqListFind函数可以删除指定的数据
void SeqListErase(SL* psl, int pos)
{assert(psl);assert(pos 0 pos psl-size);//pos位置需要有数据//挪动数据int begin pos 1;while (begin psl-size){psl-a[begin - 1] psl-a[begin];begin;}psl-size--;
}//修改pos位置的数据
void SeqListModify(SL* psl, int pos, SLDataType x)
{assert(psl);assert(pos 0 pos psl-size);psl-a[pos] x;}Test.c 文件
#define _CRT_SECURE_NO_WARNINGS 1#include SeqList.hint main()
{SL s;SeqListInit(s);SeqListPushBack(s, 1);SeqListPushBack(s, 2);SeqListPushBack(s, 3);SeqListPushBack(s, 4);SeqListPushBack(s, 5);SeqListPushBack(s, 6);//尾插SeqListPopBack(s);//尾删SeqListPushFront(s, 0);//头插SeqListPopFront(s);//头删SeqListInsert(s, 2, 8);//指定pos下标为2的位置插入数据8SeqListPrint(s);//打印SeqListDestroy(s);//销毁return 0;
}今天的分享就到这里如果觉得博主的文章还不错的话 请三连支持一下博主哦
