龙华建站公司,游戏制作软件有哪些,android源码下载,南里商濮阳网站建设文章目录 前言线性表顺序表静态顺序表动态顺序表 接口实现 前言
我们先补一下上篇博客落下的知识点#xff1a; 首先说一下斐波那契的时间复杂度和空间复杂度#xff1a;
long long Fac(size_t N)
{if(0 N)return 1;return Fac(N-1)*N;
}还是说一下size_t代表的类型是unsi… 文章目录 前言线性表顺序表静态顺序表动态顺序表 接口实现 前言
我们先补一下上篇博客落下的知识点 首先说一下斐波那契的时间复杂度和空间复杂度
long long Fac(size_t N)
{if(0 N)return 1;return Fac(N-1)*N;
}还是说一下size_t代表的类型是unsigned int这里我们画个图来计算其时间复杂度 如上图为斐波那契数列每一层递归的时间复杂度我们需要把他们加在一起求出最后的时间复杂度。所以最终答案用大O法表达为为O(2^N)。 而其空间复杂度是O(N)。 这里要说一下时间是累积的一去不复返而空间是可以重复利用的通过上图我们可以看到Fib(N-1)之后创造的Fib(N-2)所用的空间其实是Fib(N)创造的如下图所示 而时间算完之后就流失了不可重复利用所以其时间复杂度为O(2^N),空间复杂度为 ON。
线性表
线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构常见的线性表顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的 线性表在物理上存储时通常以数组和链式结构的形式存储。 以上了解就好 下图为顺序表和链表的模型。
顺序表
这里我们先说顺序表其实顺序表大家了解就好博主觉得数据结构最重要的地方是链表顺序表当做对链表的铺垫就好学好链表对后面学习栈和队列的帮助很大但顺序表学好了貌似没多大作用仅代表个人观点。
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存 储。在数组上完成数据的增删查改。 而顺序表又分为静态顺序表和动态顺序表。
静态顺序表
#define N 10000
typedef int SLDataType;
typedef struct SeqList
{SLDataType a[N];int size; // 记录存储多少个有效数据
}SL;这里再说一下在学习数据结构的阶段我们一般会对各种类型使用typedef来声明新的类型名。如上代码所示我们对int重命名为SLDataType将struct SeqList重命名为SL。还有就是我们在构建各个函数接口时尽量用英文这样显得比较正式例如SeqList表示顺序表不要写成struct shunxubiao顺序表这样在面试时会给面试官一个很不好的印象。
动态顺序表
本章我们主要说动态顺序表代码案例也会以动态顺序表为主。
typedef int SLDataType;
typedef struct SeqList
{SLDataType* a;int size; // 记录存储多少个有效数据int capacity; // 空间容量大小
}SL;上述代码为动态顺序表的结构。 其与静态表的区别在于静态表的空间由数组确定而动态表的空间需要编写函数接口来动态分配。
接口实现
首先我们要构建一个动态顺序表
typedef int SLDataType;
typedef struct SeqList
{SLDataType* a;int size; // 记录存储多少个有效数据int capacity; // 空间容量大小
}SL;之后对其初始化将其的容量有效数据个数置为0指针指向空。 这里还要注意传参一定要传地址否则函数函数内部对其操作无效。
void SLInit(SL* ps)
{assert(ps);//assert断言ps-a NULL;ps-size 0;ps-capacity 0;
}这里在回忆一个知识点assert断言其作用是如果它的条件返回错误则终止程序。 之后我们若要将数据放入表内则需要构建一个插入数据的接口函数。
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);if (ps-size ps-capacity)//检查容量为0或顺序表是否是满数据{int newCapacity (ps-capacity 0 ? 4 : ps-capacity * 2);//这里首先判断其容量是否为0若为0则先对其容量赋值不为0则扩容SLDataType* tmp (SLDataType*)realloc(ps-a, newCapacity * sizeof(SLDataType));//扩容if (tmp NULL){perror(realloc fail);exit(-1);}ps-a tmp;//将扩容空间赋值给动态顺序表ps-capacity newCapacity;//表内容量更新}ps-a[ps-size] x;//将值赋给顺序表ps-size;//表内有效数据加1
}上述代码为将数据放入顺序表的函数在本章函数和接口是一个意思。这种方法其实又叫尾插法。 假如顺序表中某个数据无用我们将其删除也需要构建函数。
void SLPopBack(SL* ps)
{assert(ps);// 温柔的检查/*if (ps-size 0){return;}*/// 暴力的检查assert(ps-size 0);//ps-a[ps-size - 1] 0;ps-size--;
}这里在对数据删减前要先判断表是否为空判断其是否为空也有两种检查方法一种是比较温柔的即顺序表若为空则会结束函数不会报错而另一种则是稍微暴力的用assert来判断若表为空表则会报错并终止程序这个判断方式根据个人喜好来设置还有就是删减数据后不必使其变为0也许要删减的数据本身就是0也说不准。 而我们也有可能想删除整个顺序表那么就要销毁其空间
void SLDestroy(SL* ps)
{assert(ps);if (ps-a){free(ps-a);ps-a NULL;ps-size ps-capacity 0;}
}若其空间不为空那么则free掉并使其指向NULL其容量与有效数据个数归0。 我们可以看到上述代码的命名都是以英文命名如销毁顺序表SLDestroy初始化顺序表SLInit。 下面说一下头插法代码如下
void SLPushFront(SL* psSLDataType 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;
}
这里SLCheckCapacity函数为检查顺序表是否还有容量在本章博客未作实现因为不是什么太难函数在一个顺序表这里稍作了解就好。end首先赋值为顺序表最后的元素下标然后将顺序表元素一直后移最后将要插入数据赋值给首元素。 再说一下中间插入
void SLInsert(SL* ps, int posSLDataType x) {assert(ps);assert(pos 0);assert(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;
}
其原理与头插法相似。都是先让end为末尾元素下标之后不断后移将数据插入中间这里的pos表示要将元素x插入的那个位置。 最后为从中间删除
void SLErase(SL* ps, int pos) {assert(ps);assert(pos 0);assert(pos ps-size);//assert(ps-size 0);//挪动数据覆盖int begin pos 1;while (begin ps-size) {ps-a[begin - 1] ps-a[begin];begin;}ps-size--;
}
还是先判断顺序表是否为空pos的值是不是有效值。 之后将begin赋值为要删除元素后一个元素的下标之后不断的前移达到覆盖要删除元素的目的。 最后期待你的三连若有错误欢迎私信指正。
