将顺序表的接口进行详细的实现(干货!!!!!!!!!)详细!!!!!!!
顺序表
顺序表就是用一段连续的物理地址连续的存储单元存放的线性结构.
动态顺序表:
typedef struct seqList{SLDataType* _data; //需要进行动态开辟的一个数组size_t _size; //有效元素的个数size_t _capacity; //当前我们可以存放的最大元素个数}seqList; //别名
如果你对这个使用动态存储的结构体,只能看到12个字节,但是对于下面的静态就不一样了,大家可以试一下(很简单,利用sizeof实现)
静态顺序表:
#define N 10struct seqList2{SLDataType _data[N];size_t _size; //有效元素的个数size_t _capacity; //当前我们可以存放的最大元素个数}seqList2; //别名
接口声明
//1.初始化void initSeqList(seqList * sl);//2.检查内存是否够用void checkCapacity(seqList* sl);//3.函数打印void printSeqList(seqList* ls);//4.头插void pushFront(seqList* sl, SLDataType val);//5.头删void popFront(seqList* sl);//6.尾插void pushBack(seqList* sl, SLDataType val);//7.尾删void popBack(seqList* ls);//8.指定插入void insert(seqList* sl, int pos, SLDataType val);//9.指定删除void erase(seqList* sl, int pos);//10.查找对应的值int findIdx(seqList* sl, SLDataType val);//11.内存大小int size(seqList* sl);//12.销毁void destorySeqList(seqList* sl);
这里有12个对应头文件的声明,量比较多,但是都大体相似,希望能坚持看下去,一起加油!
接口实现
1.初始化
对于初始化这里没有什么要说的,就是将其进行0的赋值就行了.
void initSeqList(seqList * sl){sl->_data = NULL; //指针指向空间变为0sl->_size = sl->_capacity = 0; //内存大小和最大容量也变为0,相当于int i=0;操作,很好理解}
2.检查内存是否够用
void checkCapacity(seqList* sl){if (sl == NULL) //基本的判断是否为空指针,是则直接返回return;if (sl->_size == sl->_capacity){//在所存储的size和最大的容量相等时,我们就需要扩大内存空间//当需要扩大内存时,我们的最大容量也需要变化,这里的条件运算符:如果这两个相等则+1,不等开辟二倍的内存int newCapacity = sl->_capacity == 0 ? 1 : 2 * sl->_capacity;//写入一个新的指针,进行动态内存的申请SLDataType* tmp = (SLDataType*)malloc(sizeof(SLDataType)* newCapacity);//将原始的数据进行拷贝过来memcpy(tmp, sl->_data, sizeof(SLDataType)*sl->_size);//释放原有的内存,否则会造成内存泄漏free(sl->_data);//更新代码sl->_data = tmp;sl->_capacity = newCapacity;}}
在这里唯一有点疑惑的可能就是为啥要申请二倍的内存,当两个内存相等的时候,我们只用申请一个,当不等的时候,我们并不能确定要申请多少个空间才能将其覆盖,所以我们直接申请二倍的内存,绝对够用,而且不用不停地进行申请,比较方便.
3.函数打印
void printSeqList(seqList* ls){for (int i = 0; i < ls->_size; ++i){ //for将内存进行循环printf("%d ",ls->_data[i]); //然后挨个打印}printf("\n");}
4.头插
void pushFront(seqList* sl, SLDataType val){if (sl == NULL)return; //判断是否空指针checkCapacity(sl); //内存大小检查int end = sl->_size; //这里最后一个内存就应该是size的大小,直接利用while (end > 0){//在while里面从后往前循环依次将数据往后移一位sl->_data[end] = sl->_data[end - 1];--end;}sl->_data[0] = val; //将要插入的数据放在最前面sl->_size++; //更新代码}
5.头删
void popFront(seqList* sl){if (sl == NULL||sl->_size==0)return;checkCapacity(sl); //前三行基本操作,不过多解释,后面的话int start = 1; //第二个变量while (start < sl->_size){ //循环[2,size)sl->_data[start-1]=sl->_data[start]; //依次向前一位++start; //循环}--sl->_size; //更新}
6.尾插
void pushBack(seqList* sl,SLDataType val){checkCapacity(sl);sl->_data[sl->_size] = val; //直接将数据插入到最后++sl->_size; //更新}
7.尾删
void popBack(seqList* ls){if (ls == NULL)return;if (ls->_size > 0) //对于尾删这里并不是真正的删除,而是将size直接-1,从而达到了尾删的效果ls->_size--;}
8.指定插入
void insert(seqList* sl,int pos,SLDataType val){if (sl == NULL)return;if (pos >= 0 && pos <= sl->_size){ //判断输入的位置是否在有效区域checkCapacity(sl);int end = sl->_size; //定义最后一个数据while (end > pos){ //在插入数后面的数据进行循环!!!!!!sl->_data[end] = sl->_data[end - 1]; //向后移一位--end; //依次循环}sl->_data[pos] = val; //指定位置进行插入sl->_size++; //更新}}
9.指定删除
void erase(seqList* sl, int pos){if (sl == NULL || sl->_size == 0)return;if (pos >= 0 && pos < sl->_size){ //有效范围内int start = pos + 1; //定义要插入后面一位的数开始while (start < sl->_size){ //后面的范围内sl->_data[start - 1] = sl->_data[start]; //依次向前一格++start; //循环}--sl->_size; //更新}}
10.查找对应的值
int findIdx(seqList* sl, SLDataType val){int i = 0;for (; i < sl->_size; ++i){ //内存内循环if (sl->_data[i] == val) //当值相等的时候return i; //输出位置}return -1; //找不到,返回-1}
11.内存大小
int size(seqList* sl){if (sl == NULL)return 0; //如果为空,返回0elsereturn sl->_size; //不为空,返回其长度}
12.销毁
void destorySeqList(seqList* sl){if (sl){if (sl->_data){ //指向空间free(sl->_data); //空间释放sl->_data = NULL; //指针变为空}}}
对于顺序表有下面几个特点:
1.空间是连续的
2.支持随机访问
3.空间利用率高
关键:我们一般使用顺序表主要用尾插和尾删,因为他们的复杂度低,提高效率,我们还是要多多注重对于内存的理解,这里是比较重要的,对于cpp而言,希望大家能坚持看下来,确实有点长,不积跬步,无以至千里嘛.一起加油!多敲代码!!!
墨蓝
刺骨的言语ヽ痛彻心扉
爱被打了一巴掌
小灰灰
还没有评论，来说两句吧...