实例
我们来计算冒泡排序的空间复杂度。
许多人计算的结果是O(N),原因是认为数组a有i个元素，我们创建了数组，所以空间复杂度为O(N)
但是注意：空间复杂度是算法临时占用存储空间大小的度量。我们临时开辟的有哪些呢？我们临时开辟的变量为exchange，所以我们的空间复杂度为O(1)
那我们举一个空间复杂度为O(N)的例子，例如我们上节课讲的数组旋转
我们提供的思路是在函数中额外创建一个数组tmp，然后nums数组的后k位拷贝到数组tmp的前k位中，把nums数组的前N-K位拷贝到tmp数组的后N-K位
这种方法的空间复杂度是O(N),因为我们额外创建了N个参数。
而我们冒泡排序的空间复杂度呢？
有人会说，冒泡排序的空间复杂度为O(N),原因是我们是在第一个循环中创建参数exchange和参数i的，循环执行N次，所以我们的空间复杂度是O(N)
这种说法对吗？
答：错误，原因是我们在第一次执行for循环时，我们创建了变量exchange和变量i和变量end，执行完毕的时候，变量exchange和变量i以及变量end都被销毁了，然后我们再一次执行for循环，再次创建变量exchange和变量i和变量end，这三个变量还是占据从前的空间，所以空间是可以循环利用的，所以这里的空间复杂度为O(1)
实例
这串代码的空间复杂度为什么？
函数的调用会开辟栈帧，我们从Fac(n)，开始一直到Fac(1)，一共开辟了n+1个栈帧，每个栈帧中有常数个参数，所以对应的复杂度为O(1)，因为我们有n+1个栈帧，所以对应的空间复杂度为O(N)
实例
我们额外开辟了一个数组fibArray，数组元素大致为N个，所以空间复杂度为O(N)
我们再介绍一个斐波那契数列的空间复杂度
这里我们要讲两点：空间可以重复利用，不累计。时间是一去不复返的，要累计
申请空间，和租房一样
释放空间，和退房一样
总的来说：释放空间就相当于把空间返还给操作系统了，并不意味着空间已经被销毁
举例
#include#include void f1(int n) { int a = 0; int*p = (int*)malloc(4 * n); if (p == NULL) { perror("malloc failed"); return; } } int main() { f1(10); f1(10); return 0; }
这串代码的空间复杂度是多少？
答：我们首先分析调用一次函数会产生多少空间，我们在f1函数的内部，创建了两个参数一个是a，一个是p，还创建了一部分空间，所以我们调用一次函数会产生n+2个空间。
那是不是我们这串代码就会产生2n+4个空间呢？
不，我们分析内部的栈帧图像。
main函数调用f1，形成栈帧，栈帧中形成参数a和参数p，p指向的是动态内存开辟的空间n
f1调用结束，对应的动态内存开辟的空间n被释放，f1的栈帧也被销毁，栈帧中的参数也被释放
接下来，我们再次调用f1函数
我们会在原来开辟的属于f1栈帧的空间上再开辟一个新的f1的栈帧，其中，参数a和参数p的地址都没有发生改变。
所以空间是可以重复利用的，我们调用了这两次函数，只创建了了n+2个空间，所以我们的空间复杂度是O(N)
我们来详解一下为什么新的f1的空间和旧的f1的空间重合并进行证明。
我们在调用函数时，会产生两个寄存器，ebp和esp
ebp在函数的顶部，esp在函数的尾部，我们会首先把ebp压到底部，ebp是一个地址，相当于把地址压到底部
然后我们调用函数f1，我们在调用f1之前，编译器会预估我们内部参数所占空间的大小，然后esp减去对应空间的大小，就到f1的底部，esp在对应空间的顶部
当我们调用完成时，对应的栈帧销毁，把esp赋给edp，再把esp的地址弹回main函数的顶部。
第二次调用f1就和第一次调用f1的过程相同了。
我们进行证明
#include#include void f1(int n) { int a = 0; int*p = (int*)malloc(4 * n); printf("%p %pn", &a, &p); if (p == NULL) { perror("malloc failed"); return; } } int main() { f1(10); f1(10); return 0; }
我们进行编译
第一次的a和p和第二次的a和p的地址是相同的。
接下来我们来计算斐波那契数列的空间复杂度
我们是这样调用的：先调用n-1，顺着n-1这条线一直调用到1，然后我们再退回去，退回去的同时执行分支，但这时候我们执行的分支所开辟的空间我们已经开辟过了，所以相当于我们只开辟了一条线的空间，所以我们的空间复杂度为O(N)
顺序表和链表非线性结构
顺序表
顺序表就是数组
不同点是数组的内部的元素可以不是连续的，但是顺序表内部的存储单元必须是连续的，不能跳跃。
静态的顺序表
我们首先在头文件中定义顺序表，a则表示顺序表内部的元素，size表示顺序表内部的元素个数。
但是我们发现，数据表不够灵活，我们可以把a[10]改成宏的形式
假如我们不想用int了，我们想用double类型，或者我们想用函数，这时候再进行修改就会非常的麻烦
我们可以这样写：
把int类型重定义为SLDataType
当然，静态的顺序表也是有很多缺点的：静态的顺序表并不知道要存放多少数据
所以我们静态的顺序表并不是i我们的重点
动态的顺序表
我们的动态的顺序表首先要想的就是扩容，如何进行扩容，我们可以使用realloc函数进行扩容，但我们要扩容多少呢？例如我们原来是10个空间，那我们要扩容到11个还是扩容到20个呢？
并且频繁的扩容也会导致出现问题，原因是：扩容分为两种情况，一种是原地扩，一种是异地扩
原地扩还好，要是异地扩的话，我们首先要找一块足够的空间，把原数据拷贝到空间中去，再释放旧空间，代价太大。
所以，我们不能够频繁扩容
我们添加一个参数capacity表示我们的结构体存储空间的大小 ，我们随时改变capacity来控制空间的大小。
空间满了以后一定是扩容二倍吗？
答：因为二倍比较合适，扩容扩太多，会导致空间浪费
扩容扩太少会导致频繁扩容，导致效率的损失。
注意：我们要对顺序表进行增删查改时，一定要用函数进行处理。
我们新增加的两个函数SLInit，SLDestory分别表示顺序表的初始化，动态开辟内存的销毁。
我们先定义初始化函数
我们在test.c中调用一个函数TestSeqlist1，通过这个函数来实现初始化和销毁。
我们设置断点，进行调试
我们按F11，进不到断点处
原因是编译器的BUG，编译器在对应的位置没有打印出调试信息
我们可以这样写：
我们把断点设置到函数的定义处
按F11，进入函数
我们成功吧结构体sl的成员变量全部初始化为0.
但是，当我们退出函数的时候：
初始化又不起作用了。
原因是什么呢？
答：我们知道，形参是实参的临时拷贝，我们对形参进行初始化，形参的改变并不会影响实参
所以我们可以使用传址调用：
我们进行编译，我们可以发现，当进入函数后，函数的初始化值就没有再发生改变了。
为什么传址调用就可以实现呢？
答：因为我们是把参数的地址传递到函数中了，我们在函数中通过解引用改变参数的值，退出函数后，值并不会发生改变。
接下来，我们来实现destory函数：
我们来补充一点：当我们调用函数时，传递的参数不对会发生什么？
答：
我们可以使用断言，防止传递的指针为空指针。
接下来，我们来实现增删查改：
头插头删，尾插尾删。
18 19 20 21行分别对应尾插头插，尾删头删。
我们先写尾插
psl->size对应的数字就是最后一位的后一位，我们直接在他这里放上我们要插入的数字，然后让size++表示跳到下一个位置
但是注意我们要检查容量，防止越界访问。
如何解析：当size对应的取值等于capacity，相当于就已经到达最后一位了，我们创建变量newCapcity用来接收，当capacity等于0时，表示第一次的容量为0，那我们就把新的容量置为4，如果不为0，我们就把对应的容量*2.
我们的realloc表示扩容到newCapcity*sizeof(SLDataType)的字节数赋给psl->a。
realloc扩容又分为三个情况，原地扩和异地扩和扩容失败，原地扩返回的是旧地址，异地扩返回的是新地址，扩容失败返回的是空指针，所以
SLDataType*tmp=(SLDataType*)realloc(psl->a, newCapcity*sizeof(SLDataType));
为什么要这样写？有可能扩容失败，扩容失败后会返回空指针，假如我们用psl->a来接受空指针，那么接下来我们解引用时，就会导致对空指针解引用，造成错误。
我们调用该函数进行尝试
我们写出打印函数
全文为
首先，
对应的代码为
#include"SeqList.h"
void SLPrint(SL*psl)
{
assert(psl);
for (int i = 0; i < psl->size; ++i)
{
printf("%d ", psl->a[i]);
}
printf("n");
}
void SLInit(SL* psl)
{
assert(psl);
psl->a = NULL;
psl->capacity = psl->size = 0;
}
void SLDestory(SL* psl)
{
assert(psl);
if (psl->a)
{
free(psl->a);
psl->a = NULL;
psl->capacity = psl->size = 0;
}
}
void SLCheckCapacity(SL*psl)
{
if (psl->capacity = psl->size)
{
int newCapcity = psl->capacity == 0 ? 4 : psl->capacity * 2;
SLDataType*tmp = (SLDataType*)realloc(psl->a, newCapcity*sizeof(SLDataType));
if (tmp == NULL)
{
perror("realloc fail");
return;
}
psl->a = tmp;
psl->capacity = newCapcity;
}
}
void SLPushBack(SL* psl, SLDataType x)
{
assert(psl);
SLCheckCapacity(psl);
psl->a[psl->size] = x;
psl->size++;
}
void SLPushFront(SL* psl, SLDataType x)
{
assert(psl);
SLCheckCapacity(psl);
int end = psl->size - 1;
while (end >= 0)
{
psl->a[end + 1] = psl->[end];
--end;
}
psl->a[0] = x;
psl->size++;
}
void SLPopBack(SL* psl)
{
assert(psl);
if (psl->size == 0)
{
return;
}
assert(psl->size > 0);
psl->size--;
}
void SLPopFront(SL* psl);
对应的代码为
#pragma once #include#include #include typedef int SLDataType; typedef struct SeqList { SLDataType*a; int size; int capacity; }SL; void SLInit(SL* psl); void SLDestory(SL* psl);
test.c对应的代码为
#include"SeqList.h"
void TestSeqList1()
{
SL s;
SLInit(&s);
SLDestory(&s);
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPrint(&s);
SLPushFront(&s, 10);
SLPushFront(&s, 20);
SLPushFront(&s, 30);
SLPrint(&s);
SLPopBack(&s);
SLPopBack(&s);
SLPopBack(&s);
SLPopBack(&s);
SLDestory(&s);
}
int main()
{
TestSeqList1();
return 0;
}
