网站建设中中文模板下载,广东省高水平建设专业网站,wordpress 企业站,制作网页用什么进行页面布局最近更新的少#xff0c;主要是因为参加了ACM竞赛空间复杂度空间复杂度也是一个数学表达式#xff0c;是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes的空间#xff0c;因为这个也没太大意义#xff0c;所以空间复杂度算的是变量…最近更新的少主要是因为参加了ACM竞赛空间复杂度空间复杂度也是一个数学表达式是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes的空间因为这个也没太大意义所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似也使用大O渐进表示法。注意函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。也就是说数据源的空间不能计算在内。时间一去不复返也就是说不能够重复利用但是空间用了之后就能够归还因此空间可以重复利用比如下面这个例子上面这个的空间复杂度就是O(N)因为我要运行这个算法在这个过程当中我需要去额外开辟空间这是跟我的数据源无关的我额外开辟的空间。当前函数在调用的时候为开辟对应的函数栈帧如果函数里面又会调用函数那么当前函数的函数栈帧并不会被销毁上面这个的空间复杂度也是O(N)那么重头戏来了这个的空间复杂度是多少首先的话必须要了解到底函数的调用顺序是怎么样的就看我的这张图这种函数执行的顺序有点类似于深度优先搜索到底了之后那个函数执行结束之后就会销毁函数栈帧接下来再去调用函数对于总的空间来说已经不会再增加因此空间复杂度就是O(N)。虽然说空间复杂度统计的是变量的个数如果说函数里面并没有创建变量那么我们认为在这个函数栈帧里面的空间大小为一个常数也就是O(1)。对于数组而言有几个元素就表示所谓的变量个数。线性表数据结构的作用在内存当中存储与管理数据。线性表是n个具有相同特性的数据元素的有限序列线性表是一种常用的数据结构。比较常见的线性表有顺序表链表栈队列字符串.......。我们说线性表在逻辑上是线性结构也就是说好比一条连续的直线。但是在物理结构上并不一定是连续的。在物理上存储时通常以数组和链式结构的形式存储顺序表SeqList顺序表就是写一个结构体然后通过这个结构对数组进行管理存储数据就是用数组存储1.创建一个顺序表//创建一个结构体
typedef int SLDataType;
typedef struct SeqList
{SLDataType* p;size_t size;size_t capacity;
}SeqList;2.顺序表的初始化#define INIT_CAPACITY 5
void SeqListInit(SeqList* ps)
{ps-p (SeqList*)malloc(sizeof(SLDataType) * INIT_CAPACITY);if (ps-p NULL){perror(SeqListInit::Malloc:);return;}ps-size 0;ps-capacity INIT_CAPACITY;
}3.顺序表使用结束后的销毁void SeqListDestroy(SeqList* ps)
{free(ps-p);ps-p NULL;ps-capacity 0;ps-size 0;
}4.打印顺序表void SeqlistPrint(SeqList* ps)
{for (int i 0; i ps-size; i){printf(%d , *(ps-p i));}printf(\n);
}5.顺序表的尾插void SeqListPushBack(SeqList* ps, SLDataType x)
{if (ps-size ps-capacity){SLDataType* pp (SLDataType*)realloc(ps-p, sizeof(SLDataType) * ps-capacity * 2);if (pp NULL){perror(SeqListPushBack::Realloc);return;}ps-p pp;}*(ps-p ps-size) x;ps-capacity * 2;ps-size;
}6.顺序表的尾删void SeqListPopBack(SeqList* ps)
{assert(ps-size 0);ps-size--;
}未完待续........
