网站建设前期如何规划,做板子焊接的网站的公司名字,营销策划公司是干嘛的,百度怎么推广自己的信息上一节我们认识到了什么是数据结构
这一节我们就来实现第一个数据结构的实现
思考一个问题#xff1a;
假定一个数组#xff0c;空间为10#xff0c;已经使用了5个#xff0c;向其中插入数据的步骤#xff1a; 1.插入数据#xff0c;我们先要求数组长度#xff0c;其…
上一节我们认识到了什么是数据结构
这一节我们就来实现第一个数据结构的实现
思考一个问题
假定一个数组空间为10已经使用了5个向其中插入数据的步骤 1.插入数据我们先要求数组长度其中有效数据的个数判断空余空间的大小向下标中放入有效数据这里需要判断数组是否太满了剩余空间是否还足够 2.如果数据量庞大我们就要频繁获取数组有限个数就会影响程序运行速率 这时候我们就要利用其余数据结构顺序表、链表、二叉树更甚至红黑树、B树等更为高级的数据结构
那我们就进入顺序表的学习吧
顺序表
顺序表是一种线性表 线性表List零个或多个数据元素的有限序列。线性表的数据集合为{a1,a2,…,an}假设每个元素的类型均为DataType。其中除第一个元素a1外每一个元素有且只有一个直接前驱元素除了最后一个元素an外每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。在较复杂的线性表中一个数据元素可以由若干个数据项组成。在这种情况下常把数据元素称为记录含有大量记录的线性表又称为文件 顺序表对数组的封装的分类
静态顺序表
顾名思义即是使用定长数组来储存元素
typedef int SLdataTapy;
#define N 10 //数组的大小由N决定typedef struct seqlist {SLdataTapy arr[N];//定长数组int size;//有效数组个数
}SL; 注意这就会出现空间小了不够用空间大了空间浪费。 想一想呢根据之前的学习是什么可以动态增删内存呢
没错就是利用malloc、relloc、calloc内存函数了
忘记的小朋友可以回顾一下往期的博客动态内存的管理内存储存的god-CSDN博客
动态顺序表
typedef int SLdataTapy;typedef struct seqlist {SLdataTapy* a;//用来开辟动态内存int size;//有效数组个数int capacity;//剩余容量判断是否需要新添加内存
}SL;
顺序表的实现
#define INIT_CAPACITY 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);
//指定位置之前插⼊/删除数据
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
int SLFind(SL* ps, SLDataType x);
以上则是我们需要实现顺序表的作用 顺序表的初始化
将其中的数组置为NULL其余置为0
void SLInit(SL* ps) {ps-a NULL;//置为NULL,以防野指针的出现ps-size ps-capacity 0;
}
有初始化就有销毁
销毁则是需要将数组重新置为NULL其余置为0
void SLDestroy(SL* ps) {if (ps-a) {//判断数组中是否为空free(ps-a);//因为动态顺序表需要使用malloc开辟内存所以需要注意释放内存}ps-a NULL;ps-size ps-capacity 0;
}
当我们设置好一切后就要对数组进行扩容
//扩容
void SLCheckCapacity(SL* ps) {//先要判断内存够不够if (ps-size ps-capacity) {//使用malloc relloc cellocint newcappacity ps-capacity * 2;//一般增容原来内存的二到三倍SLDataType*tmp (SLDataType*)relloc(ps-a,newcappacity * sizeof(SLDataType));//注这里没有直接使用ps-a直接申请是为了防止内存申请失败防止数据丢失if (tmp NULL) {//也可以使用assert直接终止程序需要使用aseert.h的头文件perror(relloc fail);exit(1);//直接退出程序也可使用return}//空间增容成功ps-a tmp;ps-capacity newcappacity;}
}
其中出现了一点小问题是否发现了呢
果然聪明的你一眼就发现问题了呢
int newcappacity ps-capacity * 2;//一般增容原来内存的二到三倍
SLDataType*tmp (SLDataType*)relloc(ps-a,newcappacity * sizeof(SLDataType));
在使用这句的前提是capacity为0就会导致开辟为0的空间就会出现错误
就可以利用到三目操作符使其完成扩容如以下代码
int newcappacity ps-capacity 0 ? 4 :ps-capacity*2
ps-capacity是否为0如果是则为4否则乘以2 我们已经完成了初始化销毁与扩容你可以尝试剩余代码的编写
点关注不迷路up将会在接下来揭晓如何编写
