• 固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。
• 可变空间。这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。

数组的缺点：大小(元素个数)不能改变，不能适用元素个数变化的情况。
数组可以看作无法改变大小的顺序表。

typedef int SeqType; //存储单元类型 typedef struct{ SeqType *elem; //存储空间基地址 int size; //当前长度 } List;

• 1.初始化顺序表

为什么要初始化？因为局部变量默认初始化为随机值。
怎么初始化？把结构体变量成员赋值为合法的初始值。

void list_init(List* seq);

• 2.添加元素

int sqlist_append(SqList* plist,SeqType value); int sqlist_prepend(SqList* plist,SeqType value);

• 3.获取元素

SeqType sqlist_get(SqList* plist,int index); SeqType* sqlist_at(SqList* plist,int index); //可以修改元素

• 4.获取元素个数

int sqlist_size(SqList* plist);

• 5.插入元素

void sqlist_insert(SqList* plist,int index,SeqType value);

• 6.删除元素

void sqlist_remove(SqList* plist,int index);

• 7.销毁顺序表

void sqlist_destroy(SqList* plist);

• 8.增加容量

int capacity; //当前分配的存储容量

• 9.遍历

typedef void (*SqList_Traversal)(const SeqType* value); void sqlist_traverse(SqList* plist,SqList_Traversal fp);

• 添加和删除操作需要移动元素。
• 当数据量特别大的情况，可能没有连续的内存可使用。

• 首结点：存放第一个有效数据的结点。
• 头结点：在单链表的第一个结点之前附设一个结点，它没有直接前驱，称之为头结点，头结点的数据域可以不存储任何信息，指针域指向第一个节点（首节点）的地址。头结点的作用是使所有链表（包括空表）的头指针非空。(哨兵)
• 尾结点：存放最后一个有效数据的节点。
• 头指针：指向头节点的指针
• 尾指针：指向尾结点的指针

• 链表中每个数据的存储都由以下两部分组成：
  1.数据元素本身，其所在的区域称为数据域；
  2.指向直接后继元素的指针，所在的区域称为指针域；

单链表与字符串有很多相似之处：单链表的结尾为NULL，字符串的结尾为\0。

typedef int LinkType; //定义结点 typedef struct _Node{ LinkType val; struct _Node* next; //指向下一个结点，所以指针类型是struct _Node }Node; //定义链表 typedef struct{ Node* head; //头指针 Node* tail; //尾指针 int size; }List;

Node* reverse(Node* head){ Node* p=head; Node* qhead=NULL; while(NULL !=p){ Node* n=p; p=p->next; n->next=qhead; qhead=n; } return qhead; }

• 形式1：
  让快指针先走n步，使快指针领先慢指针n步，然后再和慢指针同时移动，并且速度相等。
• 形式2：
  格式

快慢指针判断的固定格式： struct ListNode* slow=head; struct ListNode* fast=head; while(NULL !=fast && NULL !=fast->next)//条件一定要为&&

注意：
存在两种特殊情况需要处理
1.空链表删除节点
此情况使用断言或者抛出异常。
2.待删除节点的链表中只有一个节点
删除后，需要把头指针和尾指针设置为空

• 栈顶：栈的开口端称为栈顶
• 栈底：封口端称为栈底。
  
  
  文章图片
  

• 进栈：向栈中添加元素，此过程被称为"进栈"（入栈或压栈）；
• 出栈：从栈中提取出指定元素，此过程被称为"出栈"（或弹栈）
  
  文章图片
  

• 顺序栈：将顺序表的有效长度作为栈顶指针，在顺序表的末尾删除和插入节点。
• 链式栈：将链表的头结点作为栈顶指针，入栈采用头插法。

• 创建栈
• 入栈
• 出栈
• 获取栈顶元素
• 判空

• 队尾：在队列的一端只能插入元素，
• 队首：在队列的另一端只能删除元素。

• 入队：数据元素进队列的过程称为 "入队"
• 出队：出队列的过程称为 "出队"。

• 顺序队列：在index=0，入队，在index=size-1，为出队元素
• 链式队列：尾部入队，头部出队，尾插法。

• 创建队列
• 入队
• 出队
• 获取队首元素
• 判空

• stack1作为队列的入口，stack2作为队列的出口；
• 入队列的操作就是入stack1；出队列操作：若stack2为空，则将stack1里面的数据入栈到stack2中，再出栈，如果stack2不为空则直接出栈。

• 两个队列que1和que2不管是插入还是弹出或者查看栈顶元素，总是要保证有一个队列为空。
• 入栈操作：总是往有数据的列队插入，默认两个列队空时，往que1插入
• 出栈操作：从非空队列中删除元素并插入到空队列中，直到非空队列剩下一个元素，改元素就是出栈的元素。

void qsort(s,n,sizeof(s[0]),cmp);

• 参数
  s：参与排序的数组名或者也可以理解成开始排序的地址；
  n：参与排序的元素个数；
  sizeof：单个元素的大小；
  cmp：比较函数（回调函数）

int cmp(const void* a,const void* b){ int l=*(int*)a; int r=*(int*)b; if(l==r) return 0; return l>r?1:-1; }

• 1、快排是不稳定的，这个不稳定一个表现在其使用的时间是不确定的，最好情况(O(n))和最坏情况(O(n^2))差距太大，我们一般说的O(nlog(n))都是指的是其平均时间。
  
• 2、部分排序：如果要对数组进行部分排序，比如对一个s[n]的数组排列其从s[i]开始的m个元素，只需要在第一个和第二个参数上进行一些修改:
  

  void qsort(&s[i],m,sizeof(s[i]),cmp);

  
  

void bubble_sort(int* arr,int n){ for(int i=0; i
<3>复杂度分析 时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：稳定的，排序过程中不改变相同元素的相对位置。
（3）选择排序 <1>原理 设定索引为0的元素是最大值max，其索引为maxindex，然后让max与index等于1...n-1的元素进行比较，找到max和maxindex，最后让max和最后一个元素进行交换，这样每次选择，就会找到当前元素的最大值。
<2>代码

void select_sort(int* arr,int n){ for(int i=0; imax){ max=arr[j]; maxindex=j; } } arr[maxindex]=arr[n-i-1]; //交换最大元素和最后一个元素 arr[n-i-1]=max; } }

<3>复杂度 时间复杂度：O(n^2)
空间复杂度：O(1)
不稳定。
（4）插入排序 打扑克。
<1>原理

• 只含有1个元素的序列必定是有序的；
• 第1轮：将第2个元素插入到由第1个元素组成的序列中，将其与第1个元素进行比较，如果第2个元素小于第1个元素，进行交换，此时前两个元素组成的序列完成排序。
• 第2轮：将第3个元素插入到由前两个元素组成的有序序列中，将第3个元素与有序序列的最后一个元素进行比较，如果需要发生交换，则将第三个元素替换成有序序列的最后一个元素，并保存之前的第三个元素，再将改元素与有序序列的倒数第二个进行比较，如果不需要交换，则停止，把保存的第三个元素填到有序序列的倒数第二个元素的位置。
• 第 i 轮，将第 i+1 个元素插入由前 i 个元素组成的子序列中，依次与第 i、i-1、……、1 个元素做比较，如果小于则交换位置。由于前 i 个元素都是有序的，因此一旦出现不大于第 i+1 个元素的数即可停止比较，比较次数 ≤ i，此时前 i+1 个元素组成的子序列完成排序。

<2>代码

void insert_sort(int* arr,int n){ for(int i=1; i0 && arr[j-1]>tmp){ arr[j]=arr[j-1]; }else{ arr[j]=tmp; break; //否则后面的元素都会变成tmp } } } } }

<3>复杂度 时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：稳定的，排序过程中不改变相同元素的相对位置。
8.递归(Recursion) （1）概念 <1>定义 递归是一种直接或者间接调用自身函数。
<2>本质 把问题分解成规模缩小的同类问题的子问题。（递归就是函数的“套娃”）
<3>套路 关系+出口

• 确定递归公式
• 确定边界条件

<4>示例

• 打印1到10

法1： void printN(int n){ if(n<0) return; printN(n-1); printf("&n=%p:n=%d\n",&n,n); // } 法2： int f(int n){ if(n==1) return 1; else return f(n-1)+1; } int main(){ //printN(10); for(int i=1; i<11; ++i){ printf("%d ",f(i)); } printf("\n"); }

• 1-n求和

关系：f(n)=f(n-1)+n 出口：f(1)=1 代码： int sum(int n){ if(n==0) return 0; elsereturn sum(n-1)+n; }

• 打印数组

void printN(int* arr,int n,int i){ if(i==n) return; cout<< arr[i]<

• 数组求和

int sumN(int* arr,int n,int i){//i是下标，表示从i开始求和 if(i==n-1) return arr[i]; else return arr[i]+sumN(arr,n,i+1); } int sumN(int* arr,int n){ return sumN(arr,n,0); }

• 求数组的最大值

int maxarr(int* arr,int n,int i){ if(i==n-1) return arr[i]; else{ if(maxarr(arr,n,i+1)>arr[i]){ return maxarr(arr,n,i+1); }else{ return arr[i]; } } }

• 斐波那契数列（*）
  （1）兔子问题

//f(n)=f(n-1)+f(n-2) //f(1)=1; f(2)=1 int Fibonacci(int n){ if(n==1 || n==2) return 1; //递归 //return Fibonacci(n-1)+Fibonacci(n-2); //迭代 int prev = 1; int curr = 1; for(int i=3; i<=n; ++i){ int res = prev + curr; prev = curr; curr = res; } return curr; }

（2）爬楼梯
直接使用递归可能会超时！！需要用到动态规划。！！！


文章图片

（2）递归的缺点 <1>空间 递归可能耗内存。（因为：函数参数中的每个变量都会重新申请内存）
可能导致吐核。
<2>时间 会很耗时（尤其对于两个或者三个函数相加的运算），主要原因是会重复计算某些值，会导致运行超时，解决：使用动态规划，申请动态数组来记录已经计算过的函数值。
动态规划：解决递归性能问题的一种方法。
动态规划讲解：https://leetcode-cn.com/problems/house-robber/solution/dong-tai-gui-hua-jie-ti-si-bu-zou-xiang-jie-cjavap/


文章图片

可以使用time来统计执行时间。
time ./a.out

9.高级排序算法 （1）归并排序 <1>原理

文章图片

分到一定细度的时候，每一个部分就只有一个元素了，那么我们此时不用排序，对他们进行一次简单的归并就好了
<2>步骤

• 1.实现两个有序数组的合并（*）
  

  void merge(int* arr,int n,int mid);

  
  
• 2.拆分并合并数组（递归）
  

  void merge_sort(int* arr,int n);

  
  

<3>代码

//归并排序 void merge(int*arr,int n,int mid) { int temp[n]; int p=0; //前半部分下标 int q=mid; //后半部分下标 int k=0; //结果下标 while(p
<4>复杂度

• 时间复杂度：一共拆分log2(n)次，每次比较n个元素，一共比较nlog2(n)次。
• 空间复杂度：需要增加额外空间n+log2(n)(临时数组n和递归调用函数栈log2(n)),空间复杂度为O(n)
• 稳定

（4）快速排序 <1>理解 以第一个个元素为基准，并且设置左右两个哨兵，右哨兵先走，当遇到比基准小的后，停止，然后左边的哨兵再走，当遇到比基准大的数停止，交换左右两个哨兵，然后再从右哨兵开始，重复，直到左右哨兵相遇为止。
<2>代码

• 递归

int partition(int* arr,int n){ int priot=arr[0]; //以第一个元素为基准 int low=0; //从左往右 int height=n-1; //从右往左 while(low=priot) height--; // 如果队尾元素小于tmp了,需要将其赋值给low //arr[low]=arr[height]; // 当队首元素小于等于tmp时,向前挪动low指针 while(low

• 非递归
  递归的算法主要是在划分子区间，如果要非递归实现快排，只要使用一个栈来保存区间就可以了。
  一般将递归程序改成非递归首先想到的就是使用栈，因为递归本身就是一个压栈的过程。

void quicksortnonrecursive(int* arr,int n){ stack s; int low=0; int height=n-1; if(lowlow){ s.push(low); s.push(pos-1); } if(pos+1start){ s.push(start); s.push(mid-1); } if(mid+1

非递归的算法比递归实现还要慢。 因为递归算法使用的栈由程序自动产生，栈中包含：函数调用时的参数和函数中的局部变量。如果局部变量很多或者函数内部又调用了其他函数，则栈会很大。每次递归调用都要操作很大的栈，效率自然会下降。而对于非递归算法，每次循环使用自己预先创建的栈，因此不管程序复杂度如何，都不会影响程序效率。但是对于上面的快速排序，由于局部变量只有一个mid，栈很小，所以效率并不比非递归实现的低。
<3>复杂度

• 时间复杂度：一共拆分log2(n)次，每次比较n个元素，一共比较nlog2(n)次。
• 空间复杂度：需要增加额外空间log2(n)(递归调用函数栈log2(n)),空间复杂度为O(log2(n))
• 不稳定

（5）希尔排序（Shell排序） 希尔排序比插入排序的优势：
通过分组排序使元素逐渐靠近最终位置，从而减少了插入排序 时的移动次数。（先粗调再微调）
<1>理解 https://blog.csdn.net/qq_39207948/article/details/80006224
<2>代码

void ShellSort(int* arr,int len){ int temp,j; for(int r=len/2; r>=1; r/=2){//间隔 //内层循环间距为r,分别比较对应元素，当r=1时，就是插入排序。 for(int i=r; i=0 && arr[j]>temp){ arr[j+r]=arr[j]; j -=r; } arr[j+r]=temp; } } }

<3>复杂度
文章图片
<4>算法选择标准
文章图片

推荐阅读

• 

  对于韩国化妆品,你有什么看法呢？
• 

  在word中更正拼写和语法 word2010中更正拼写时仅根据主词典提供建议的方法教程
• 

  月饼出油是什么原因
• 

  把软件做成安装包，怎么把软件变成安装包发给别人
• 

  iphone6plus怎样分屏（iphone6plus怎么分屏）
• 

  柳花月叶子打一成语
• 

  怎样洗蚬子才能洗干净 蚬子怎么洗才干净
• 

  cad文字回车后消失 cad文字按回车不见了
• 

  东宫当年有多火 东宫好看吗评价
• 

  冬天还有蚊子怎么办
• 

  如何正确清零富士施乐DocuCentre2056打印机
• 

  黄色毛毛虫是什么品种的 黄色毛毛虫是什么品种
• 

  圣诞祝福语给孩子
• 

  为什么说“药补不如食补”
• 

  长孙和嫡孙区别 长孙和嫡孙是什么
• 

  捡到的钱隔天花可以吗
• 

  sql词义分析,成果结果后果的词义分析
• 

  血玉的价格是多少 血玉的鉴定方法
• 

  面包能放冰箱冷藏，面包买回来放冰箱里能放几天
• 

  如何正确拆卸和安装抽拉式服务器？ 抽拉式服务器怎么拆装

• 急于表达——往往欲速则不达
• 第三节|第三节 快乐和幸福（12）
• 20170612时间和注意力开销记录
• 2.6|2.6 Photoshop操作步骤的撤消和重做 [Ps教程]
• 对称加密和非对称加密的区别
• 眼光要放高远
• 樱花雨
• 前任
• 2020-04-07vue中Axios的封装和API接口的管理
• 烦恼和幸福