深圳网站建设 案例,网站外链建设书籍,网站制作价格与售后视频,石家庄室内设计公司排名专栏#xff1a;数据结构 个人主页#xff1a;HaiFan. 专栏简介#xff1a;从零开始#xff0c;数据结构#xff01;#xff01; 顺序表前言接口实现SListInit初始化和SListDestory销毁SListPrint打印表中的元素SListCheckCapacity检查表中空间SListPushBack尾插和SListP… 专栏数据结构 个人主页HaiFan. 专栏简介从零开始数据结构 顺序表前言接口实现SListInit初始化和SListDestory销毁SListPrint打印表中的元素SListCheckCapacity检查表中空间SListPushBack尾插和SListPopBack尾删SListPushFront头插和SListPopFront头删SListFind查找元素SListInset插入元素SListErase删除元素完整代码前言 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存 储。在数组上完成数据的增删查改。 顺序表一般可以分为
静态顺序表使用定长数组存储元素。动态顺序表使用动态开辟的数组存储。
接口实现
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了空间开多了浪费开少了不够用。所以现实中基本都是使用动态顺序表根据需要动态的分配空间大小所以下面我们实现动态顺序表。
typedef int SLDataType;typedef struct SeqList
{SLDataType* val;int cnt;int capacity;
}SL;void SListInit(SL* ps);//对顺序表进行初始化
void SListDestory(SL* ps);//使用动态分配函数开辟的空间需要free掉
void SListPrint(SL* ps);//打印出顺序表中的内容void SListCheckCapacity(SL* ps);//检查顺序表中的空间是否够用void SListPushBack(SL* ps,SLDataType x);//顺序表尾部插入
void SListPopBack(SL* ps);//尾部删除void SListPushFront(SL* ps, SLDataType x);//头部插入
void SListPopFront(SL* ps);//头部删除int SListFind(SL* ps,SLDataType x);//查找元素void SListInsert(SL* ps, int pos, SLDataType x);//在任意位置插入元素void SListErase(SL* ps, int pos);//删除任意位置的元素要说明的是这里为什么要把int重命名成SLDataType因为元素的类型是可以变化的想改变元素的类型只需要在typedef这里改一下即可就不需要在更改其他的数据了。 cnt是用来记录顺序表中的元素有多少个 capacity是用来检查顺序表中的空间是否够用 SListInit初始化和SListDestory销毁
顺序表初始化要把结构体中的val开辟一点空间。
void SListInit(SL* ps)
{ps-val (SLDataType*)malloc(sizeof(SLDataType) * 4);if (ps-val NULL){perror(malloc fail);exit(-1);}ps-capacity 4;ps-cnt 0;
}在程序结束的时候要把动态开辟的空间给销毁用了多少空间还给系统多少空间。
void SListDestory(SL* ps)
{free(ps-val);ps-val NULL;ps-capacity ps-cnt 0;
}SListPrint打印表中的元素
打印表中的元素要实现这个只需要一个for循环就能解决。
void SListPrint(SL* ps)
{for (int i 0; i ps-cnt; i){cout ps-val[i] ;}puts();
}cnt是用来记录表中的元素个数的
SListCheckCapacity检查表中空间
在进行增加元素的时候要先对表中的空间进行一个检查判断空间的大小是否足够在容纳一个元素。
void SListCheckCapacity(SL* ps)
{if (ps-capacity ps-cnt){SLDataType* tmp (SLDataType*)realloc(ps-val, sizeof(SLDataType) * ps-capacity * 2);if (tmp NULL){perror(realloc fail);exit(-1);}ps-val tmp;ps-capacity * 2;}
}如果val是NULL先通过malloc开辟一段空间如果val不是NULL就让cnt和capacity进行是否相等判断如果相等就使用realloc函数对val进行扩容扩容的时候用一个临时的指针接收然后在把临时的指针赋值给val。
当然空间扩容了capacity也别忘记扩大了。
SListPushBack尾插和SListPopBack尾删
尾插很简单cnt不但可以用来记录元素的个数的也可以当作要插入的元素的下标。
元素值1 2 3
下标 0 1 2
cnt的值3
此时在下标为cnt(3)的地方插入一个值即可。
void SListPushBack(SL* ps, SLDataType x)
{SListCheckCapacity(ps);ps-val[ps-cnt] x;ps-cnt;
}当然在插入元素之前要先检查表的空间。 删除元素也很简单只需要cnt–即可。
void SListPopBack(SL* ps)
{assert(ps-cnt);ps-cnt--;
}这里要添加一个断言避免没有元素了还执行删除操作。 SListPushFront头插和SListPopFront头删
头插的话需要先把每个元素都往后移动一位把第一个元素的位置给腾出来才能把x给插入。
void SListPushFront(SL* ps, SLDataType x)
{SListCheckCapacity(ps);for (int i ps-cnt; i 0; i--){ps-val[i] ps-val[i - 1];}ps-val[0] x;ps-cnt;
}
当然要先检查表中空间是否够用 头删的话只需要把第一个元素等于第二个元素就行即下一个元素把上一个元素给覆盖了。
void SListPopFront(SL* ps)
{assert(ps-cnt);for (int i 0; i ps-cnt - 1; i){ps-val[i] ps-val[i 1];}ps-cnt--;
}SListFind查找元素
查找元素的话只需要遍历一遍表中元素即可找到相同的值返回下标
int SListFind(SL* ps, SLDataType x)
{assert(ps-cnt);for (int i 0; i ps-cnt; i){if (ps-val[i] x){return i;break;}}return -1;
}SListInset插入元素
插入元素分为两种情况当要插入的位置等于cnt时就是尾插。
否则就要让pos之后的元素依次往后移动一位把pos位置空出来在进行插入操作。
void SListInsert(SL* ps, int pos, SLDataType x)
{SListCheckCapacity(ps);if (pos ps-cnt){return;}else if (pos ps-cnt){SListPushBack(ps, x);}else{for (int i ps-cnt; i pos; i--){ps-val[i] ps-val[i - 1];}ps-val[pos] x;ps-cnt;}}SListErase删除元素
删除元素也分为两种情况当pos等于cnt-1的时候就是尾删。
否则就要让pos后的元素依次往前移动一位把pos给覆盖即可。
void SListErase(SL* ps, int pos) { assert(ps);
if (pos ps-cnt - 1)
{SListPopBack(ps);
}
else if (pos ps-cnt)
{exit(-1);
}
else
{for (int i pos; i ps-cnt - 1; i){ps-val[i] ps-val[i 1];}ps-cnt--;
}完整代码
.h文件
#pragma once#include iostream
#include stdlib.h
#include assert.husing namespace std;typedef int SLDataType;typedef struct SeqList
{SLDataType* val;int cnt;int capacity;
}SL;void SListInit(SL* ps);//对顺序表进行初始化
void SListDestory(SL* ps);//使用动态分配函数开辟的空间需要free掉
void SListPrint(SL* ps);//打印出顺序表中的内容void SListCheckCapacity(SL* ps);//检查顺序表中的空间是否够用void SListPushBack(SL* ps,SLDataType x);//顺序表尾部插入
void SListPopBack(SL* ps);//尾部删除void SListPushFront(SL* ps, SLDataType x);//头部插入
void SListPopFront(SL* ps);//头部删除int SListFind(SL* ps,SLDataType x);//查找元素void SListInsert(SL* ps, int pos, SLDataType x);//在任意位置插入元素void SListErase(SL* ps, int pos);//删除任意位置的元素.cpp文件
#define _CRT_SECURE_NO_WARNINGS 1#include SeqList.hvoid SListPrint(SL* ps)
{for (int i 0; i ps-cnt; i){cout ps-val[i] ;}puts();
}void SListInit(SL* ps)
{ps-val (SLDataType*)malloc(sizeof(SLDataType) * 4);if (ps-val NULL){perror(malloc fail);exit(-1);}ps-capacity 4;ps-cnt 0;
}void SListDestory(SL* ps)
{free(ps-val);ps-val NULL;ps-capacity ps-cnt 0;
}void SListCheckCapacity(SL* ps)
{if (ps-capacity ps-cnt){SLDataType* tmp (SLDataType*)realloc(ps-val, sizeof(SLDataType) * ps-capacity * 2);if (tmp NULL){perror(realloc fail);exit(-1);}ps-val tmp;ps-capacity * 2;}
}void SListPushBack(SL* ps, SLDataType x)
{SListCheckCapacity(ps);ps-val[ps-cnt] x;ps-cnt;
}void SListPopBack(SL* ps)
{assert(ps-cnt);ps-cnt--;
}void SListPushFront(SL* ps, SLDataType x)
{SListCheckCapacity(ps);for (int i ps-cnt; i 0; i--){ps-val[i] ps-val[i - 1];}ps-val[0] x;ps-cnt;
}void SListPopFront(SL* ps)
{assert(ps-cnt);for (int i 0; i ps-cnt - 1; i){ps-val[i] ps-val[i 1];}ps-cnt--;
}int SListFind(SL* ps, SLDataType x)
{assert(ps-cnt);for (int i 0; i ps-cnt; i){if (ps-val[i] x){return i;break;}}return -1;
}void SListInsert(SL* ps, int pos, SLDataType x)
{SListCheckCapacity(ps);if (pos ps-cnt){return;}else if (pos ps-cnt){SListPushBack(ps, x);}else{for (int i ps-cnt; i pos; i--){ps-val[i] ps-val[i - 1];}ps-val[pos] x;ps-cnt;}}void SListErase(SL* ps, int pos)
{assert(ps);if (pos ps-cnt - 1){SListPopBack(ps);}else if (pos ps-cnt){exit(-1);}else{for (int i pos; i ps-cnt - 1; i){ps-val[i] ps-val[i 1];}ps-cnt--;}}
test.cpp文件
#define _CRT_SECURE_NO_WARNINGS 1#include SeqList.hvoid TestSeqList()
{SL s;SListInit(s);SListPushBack(s, 1);SListPushBack(s, 2);SListPushBack(s, 3);SListPushBack(s, 4);SListPushBack(s, 5);SListPrint(s);SListPopBack(s);SListPrint(s);SListPushFront(s, -1);SListPushFront(s, -2);SListPushFront(s, -3);SListPushFront(s, -4);SListPushFront(s, -5);SListPrint(s);SListPopFront(s);SListPrint(s);int ret SListFind(s, 4);cout ret endl;SListInsert(s, 3, 100000);SListPrint(s);SListErase(s, 3);SListPrint(s);SListDestory(s);
}int main()
{TestSeqList();return 0;
}
