东莞网站建设 手袋厂,浏览网站 需要我安装wordpress,河间市网站建设,万网可以花钱做网站吗#x1f308;个人主页#xff1a;聆风吟 #x1f525;系列专栏#xff1a;图解数据结构、算法模板 #x1f516;少年有梦不应止于心动#xff0c;更要付诸行动。 文章目录 一. ⛳️线性表1.1 #x1f514;线性表的定义1.2 #x1f514;线性表的存储结构 二. ⛳️顺序表… 个人主页聆风吟 系列专栏图解数据结构、算法模板 少年有梦不应止于心动更要付诸行动。 文章目录 一. ⛳️线性表1.1 线性表的定义1.2 线性表的存储结构 二. ⛳️顺序表2.1 顺序表定义2.2 顺序表的分类2.2.1 静态顺序表2.2.2 动态顺序表 三. ⛳️顺序表的基本操作实现3.1 动态顺序表结构体构建3.2 初始化顺序表3.3 销毁顺序表3.4 打印顺序表3.4 扩容3.5 尾插3.6 尾删3.7 头插3.8 头删3.9 在下标为pos位置插入x3.10 删除下标为pos位置的数据3.11 查找某个值的下标 四. ⛳️顺序表的完整源代码4.1 SeqList.h 顺序表的函数声明4.2 SeqList.c 顺序表的函数定义4.3 test.c 顺序表功能测试 总结 一. ⛳️线性表
1.1 线性表的定义 线性表linear list线性表是一种数据结构由n个具有相同数据类型的元素构成一个有限序列。线性表可以用数组、链表、栈等方式实现常见的线性表有数组、链表、栈、队列等也可以自定义实现。 这里需要强调一下几点 首先它是一个序列。也就是说元素之间是有顺序的。线性表中的元素称为结点相邻结点之间的关系称为邻接关系。除第一个结点无前驱和最后一个结点无后继外其他每个结点有且仅有一个前驱和一个后继。图解如下 注意 线性表元素个数n (n 0)定义为线性表的长度当n0时称为空表。 1.2 线性表的存储结构 线性表的存储结构有顺序存储结构和链式存储结构两种。前者称为顺序表后者称为链表 其中线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。 本文主要详细讲解线性表的顺序存储结构 —— 顺序表。线性表的链式存储将在下期讲解言归正传接下来让我们开始今天的 “主菜 学习。 二. ⛳️顺序表
2.1 顺序表定义 顺序表Sequential List用一段物理地址连续的存储单元依次存储数据元素的线性结构。一般情况下采用数组存储。在数组上完成数据的增删查改。 2.2 顺序表的分类
顺序表一般可以分为静态顺序表和动态顺序表。
2.2.1 静态顺序表 静态顺序表指存储空间是固定的并且在程序运行前就已经确定大小的顺序表。它通常使用数组来实现即通过定义一个固定长度的数组来存储数据元素。 静态顺序表的结构代码
//静态顺序表 —— 使用定长数组存储元素不实用
#define MAXSIZE 7//存储单元初始分配量
typedef int SLDataType;//SLDataType类型根据实际情况而定这里是inttypedef struct SeqList
{SLDataType data[MAXSIZE];//定长数组int size;//有效数据的个数
}SeqList;
我们可以发现描述静态顺序表需要三个属性
存储空间的起始位置数组data他的存储位置就是存储空间的存储位置线性表的最大存储容量数组长的MAXSIZE线性表的当前位置size。
静态顺序表的优缺点
由于静态顺序表大小是固定的因此不支持动态插入和删除但可以通过重新分配空间的方式来增加或减少容量静态顺序表的优点访问数据快速由于是连续存储所以可以直接通过下标访问元素效率高静态顺序表的缺点空间利用率低因为必须预留足够的空间以防止溢出。 2.2.2 动态顺序表 动态顺序表通过动态分配内存空间实现随着数据量的增加而不断扩容的效果。它的结构类似于一个数组数据元素的存储是连续的支持随机访问和顺序访问。 动态顺序表的结构代码
//动态顺序表 —— 使用动态开辟的数组存储
typedef int SLDataType;//SLDataType类型根据实际情况而定这里是inttypedef struct SeqList
{SLDataType* a;//指向动态开辟的数组int size;//有效数据的个数int capacity;//记录容量的空间大小
}SL;我们可以发现描述动态顺序表也需要三个属性
存储空间的起始位置指针a他里面存储的地址就是存储空间的地址线性表当前最大存储容量capacity可以通过动态分配的方式进行扩容线性表的当前位置size。
动态顺序表的优缺点
动态顺序表的优点可以使用指针动态地分配内存具有高效的存储和访问效率动态顺序表的缺点在插入和删除元素时需要移动大量的数据效率较低。 三. ⛳️顺序表的基本操作实现 通过上面的学习我们已经初步了解静态顺序表和动态顺序表有同学估计要问了在日常生活中我们应该使用哪种呢在这里作者推荐大家使用动态顺序表。因为动态顺序表可以使程序更加高效和灵活可以根据实际数据量动态地调整表的大小避免在创建静态顺序表时浪费内存空间或者当数据量超出静态顺序表容量时造成数据丢失或程序崩溃等问题。本文也将采用动态顺序表结合图文去实现顺序表的基本操作。
3.1 动态顺序表结构体构建
//动态顺序表
#define SLCAPACITY 4
typedef int SLDataType;typedef struct SeqList
{SLDataType* a;//指向动态开辟的数组int size;//有效数据的个数int capacity;//记录容量的空间大小
}SL;代码深剖
结构体中 a 指向的数组类型是我们重定义的SLDataType这样当我们想创建其它类型的顺序表时只需要对 typedef 后面的类型进行需改即可size是用来计数的统计当前顺序表一共有多少个有效元素capacity是用来表示当前顺序表的容量当sizecapacity时说明当前顺序表已经“装满了”需要扩容定义标识符SLCAPACITY方便后文对顺寻表进行初始化可以方便改变capacity的初始值。 3.2 初始化顺序表
//初始化顺序表
void SLInit(SL* ps)
{assert(ps);//使用malloc开辟空间ps-a (SLDataType*)malloc(sizeof(SLDataType)*4);//判断空间是否开辟成功if (NULL ps-a){perror(malloc failed);exit(-1);}ps-size 0;ps-capacity SLCAPACITY;
}代码深剖
在这里我们需要使用assert对ps进行一下断言以防传入空指针后文在出现就不多做叙述了。使用malloc开辟空间一定要进行判断是否开辟成功如果不进行判断直接使用可能会导致程序崩溃。
时间复杂度 该程序没有循环根据大O阶的推导方法很容易得出初始化顺序表的时间复杂度为O(1) 3.3 销毁顺序表
//销毁顺序表
void SLDestroy(SL* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-size ps-capacity 0;
}代码深剖 为什么在这里要销毁顺序表呢因为我们在这里使用的动态顺序表a是通过malloc进行动态申请的空间如果使用了malloc分配的内存空间后忘记释放会导致内存泄漏浪费系统资源甚至导致程序崩溃。
时间复杂度 该程序没有循环根据大O阶的推导方法很容易得出销毁顺序表的时间复杂度为O(1) 3.4 打印顺序表
//打印顺序表
void SLPrint(SL* ps)
{assert(ps);for (int i 0; i ps-size; i){printf(%d , ps-a[i]);}printf(\n);
}代码深剖 打印顺序表就是进行简单的遍历循环此处不多做叙述。
时间复杂度 该程序有单层循环根据大O阶的推导方法很容易得出打印顺序表的时间复杂度为O(n) 3.4 扩容 因为扩容在尾插、头插以及在pos位置插入都需要使用因此我们可以把扩容单独封装成一个函数可以降低代码的的冗余。整体思路图解
//检查容量是否够不够进行扩容
void SLCheckCapacity(SL* ps)
{assert(ps);//满了要扩容if (ps-size ps-capacity){//使用realloc进行扩容SLDataType* temp (SLDataType*)realloc(ps-a, sizeof(SLDataType) * 2 * (ps-capacity));//检查是否扩容成功if (temp NULL){perror(realloc failed);exit(-1);}ps-a temp;ps-capacity * 2;}
}代码深剖 realloc是C语言中的一个函数用于重新分配已经分配的内存空间的大小。它的原型是
//头文件
#includestdlib.h
//原型
extern void *realloc(void *mem_address unsigned int newsize)其中mem_address是指向已分配内存的指针newsize是新的内存大小。如果内存分配失败将会会返回NULL。
时间复杂度 该程序没有循环根据大O阶的推导方法很容易得出扩容的时间复杂度为O(1) 3.5 尾插 尾插时需要先判断顺序表是否满了满了要先进行扩容才能继续进行扩容。size表示有效元素个数同时也是顺序表中最后一个元素后一个位置的下标。成功插入后要对有效数据个数size进行加1操作。整体思路图解
//尾插
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);//检查是否需要扩容SLCheckCapacity(ps);ps-a[ps-size] x;ps-size;
}时间复杂度 该程序没有循环根据大O阶的推导方法很容易得出尾插的时间复杂度为O(1) 3.6 尾删
整体思路图解
//尾删
void SLPopBack(SL* ps)
{assert(ps);//温柔检查/*if (ps-size 0)return;*///暴力检查assert(ps-size 0);ps-size--;
}代码深剖 在代码中我们提供两种检查顺序表是否为空的办法。第一种是比较温柔的检查如果顺序表为空直接返回返回之后仍然可以进行其他操作。第二种是比较暴力的检查方法直接提示错误并打印出错误位置的行号。 时间复杂度 该程序没有循环根据大O阶的推导方法很容易得出尾删的时间复杂度为O(1) 3.7 头插
整体思路图解
//头插
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);//检查是否需要扩容SLCheckCapacity(ps);//挪动数据int end ps-size - 1;while (end 0){ps-a[end 1] ps-a[end];--end;}ps-a[0] x;ps-size;
}时间复杂度 该程序需要执行单层循环根据大O阶的推导方法很容易得出头插的时间复杂度为O(n) 3.8 头删
整体思路图解
//头删
void SLPopFront(SL* ps)
{assert(ps);//判断顺序表是否为空assert(ps-size 0);//挪动元素向前覆盖int begin 1;while (begin ps-size){ps-a[begin - 1] ps-a[begin];begin;}ps-size--;
}时间复杂度 该程序需要执行单层循环根据大O阶的推导方法很容易得出头插的时间复杂度为O(n) 3.9 在下标为pos位置插入x
整体思路图解
//在下标为pos的位置插入x
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);//检查pos是否在有效范围内assert(pos 0 pos ps-size);//检查是否需要扩容SLCheckCapacity(ps);//挪动数据int end ps-size - 1;while (end pos) {ps-a[end 1] ps-a[end];--end;}//插入元素ps-a[pos] x;ps-size;
}时间复杂度 该程序需要执行单层循环根据大O阶的推导方法很容易得出pos位置插入的时间复杂度为O(n) 3.10 删除下标为pos位置的数据
整体思路图解
//删除下标为pos位置的数据
void SLErase(SL* ps, int pos)
{assert(ps);//检查pos是否在有效范围内assert(pos 0 pos ps-size);//挪动元素向前覆盖int begin pos 1;while (begin ps-size){ps-a[begin - 1] ps-a[begin];begin;}ps-size--;
}时间复杂度 该程序需要执行单层循环根据大O阶的推导方法很容易得出pos位置删除的时间复杂度为O(n) 3.11 查找某个值的下标
//查找某个值的下标,没找到返回-1
int SLFind(SL* ps, SLDataType x)
{assert(ps);for (int i 0; i ps-size; i){if (ps-a[i] x)return i;}return -1;
}时间复杂度 该程序需要执行单层循环根据大O阶的推导方法很容易得出查找的时间复杂度为O(n) 四. ⛳️顺序表的完整源代码
4.1 SeqList.h 顺序表的函数声明
#include stdio.h
#include stdlib.h
#include assert.h//动态顺序表
#define SLCAPACITY 4
typedef int SLDataType;typedef struct SeqList
{SLDataType* a;//指向动态开辟的数组int size;//有效数据的个数int capacity;//记录容量的空间大小
}SL;//管理数据 —— 增删查改//初始化
void SLInit(SL* ps);
//销毁顺序表
void SLDestroy(SL* ps);
//打印顺序表
void SLPrint(SL* ps);
//检查容量是否够不够进行扩容
void SLCheckCapacity(SL* ps);//尾插尾删
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);//头插头删
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);//查找某个值的下标,没找到返回-1
int SLFind(SL* ps, SLDataType x);//在pos位置插入x
void SLInsert(SL* ps, int pos, SLDataType x);
//删除pos位置的数据
void SLErase(SL* ps, int pos);4.2 SeqList.c 顺序表的函数定义
#include SeqList.h//初始化顺序表
void SLInit(SL* ps)
{assert(ps);//使用malloc开辟空间ps-a (SLDataType*)malloc(sizeof(SLDataType)*4);//判断空间是否开辟成功if (NULL ps-a){perror(malloc failed);exit(-1);}ps-size 0;ps-capacity SLCAPACITY;
}//销毁顺序表
void SLDestroy(SL* ps)
{assert(ps);//释放动态开辟的空间free(ps-a);ps-a NULL;ps-size ps-capacity 0;
}//打印顺序表
void SLPrint(SL* ps)
{assert(ps);for (int i 0; i ps-size; i){printf(%d , ps-a[i]);}printf(\n);
}//检查容量是否够不够进行扩容
void SLCheckCapacity(SL* ps)
{assert(ps);//满了要扩容if (ps-size ps-capacity){//使用realloc进行扩容SLDataType* temp (SLDataType*)realloc(ps-a, sizeof(SLDataType) * 2 * (ps-capacity));//检查是否扩容成功if (temp NULL){perror(realloc failed);exit(-1);}ps-a temp;ps-capacity * 2;}
}//尾插
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);//检查是否需要扩容SLCheckCapacity(ps);ps-a[ps-size] x;ps-size;
}//尾删
void SLPopBack(SL* ps)
{assert(ps);//暴力检查assert(ps-size 0);ps-size--;
}//头插
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);//检查是否需要扩容SLCheckCapacity(ps);//挪动数据int end ps-size - 1;while (end 0){ps-a[end 1] ps-a[end];--end;}ps-a[0] x;ps-size;
}//头删
void SLPopFront(SL* ps)
{assert(ps);//判断顺序表是否为空assert(ps-size 0);//挪动元素向前覆盖int begin 1;while (begin ps-size){ps-a[begin - 1] ps-a[begin];begin;}ps-size--;
}//查找某个值的下标
int SLFind(SL* ps, SLDataType x)
{assert(ps);for (int i 0; i ps-size; i){if (ps-a[i] x)return i;}return -1;
}//在下标为pos的位置插入x
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);//检查pos是否在有效范围内assert(pos 0 pos ps-size);//检查是否需要扩容SLCheckCapacity(ps);//挪动数据int end ps-size - 1;while (end pos) {ps-a[end 1] ps-a[end];--end;}//插入元素ps-a[pos] x;ps-size;
}//删除下标为pos位置的数据
void SLErase(SL* ps, int pos)
{assert(ps);//检查pos是否在有效范围内assert(pos 0 pos ps-size);//挪动元素向前覆盖int begin pos 1;while (begin ps-size){ps-a[begin - 1] ps-a[begin];begin;}ps-size--;
}4.3 test.c 顺序表功能测试 在这里作者只给出头插头删这组测试样例因为只需要调用前面的函数所以就不给大家挨个测试了下来之后大家可以自行尝试多敲多练大家一块进步。
#include SeqList.h//尾插尾删检测
void TestSeqList1()
{SL s;//创建顺序表SLInit(s);//初始化//尾插SLPushBack(s, 1);SLPushBack(s, 2);SLPushBack(s, 3);SLPrint(s);//打印//尾删SLPopBack(s);SLPopBack(s);SLPrint(s);//打印//销毁顺序表SLDestroy(s);
}int main()
{TestSeqList1();return 0;
}总结
本文主要讲解
线性表的定义由n个具有相同数据类型的元素构成一个有限序列线性表的存储结构顺序存储结构、链式存储结构顺序表的定义用一段物理地址连续的存储单元依次存储数据元素的线性结构顺序表的分类静态顺序表、动态顺序表顺序表的增删查改的实现。 今天的干货分享到这里就结束啦如果觉得文章还可以的话希望能给个三连支持一下聆风吟的主页还有很多有趣的文章欢迎小伙伴们前去点评您的支持就是作者前进的最大动力
