一、大体复习内容
复习思路；
二、数据结构算法-常见复杂度汇总介绍-性能对比-图表展示
数据结构:
相互之间存在一种或者多种特定关系的数据元素的集合。在逻辑上可以分为线性结构，散列结构、树形结构，图形结构等等。
数据结构说的是组织数据的一种方式，一种结构。
算法:
求解具体问题的步骤描述，代码上表现出来是解决特定问题的一组有限的指令序列。
它讲究的是有一输入，有一组有限的指令序列去做某一件事情，然后最后一个输出，数据结构是存储数据，组织数据的一种方式结构
算法复杂度:
时间和空间复杂度，衡量算法效率，算法在执行过程中，随着数据规模n的增长，算法执行所花费的时间和空间的增长速度。
复杂度分为两个，一个是时间复杂度，一个是空间复杂度，衡量算法效率的，算法在执行过程中，随着数据规模N的增长执行，算法执行所花费的时间和空间的增长速度，所以杂度并不是，准确的去计算我们这个算法所花费的时间和空间的，这个时间就是算法执行的时间，空间就是算法执行过程中所需要占用的额外的内存控件，这里边儿控件指的是内存，也就是说复杂度，并不是准确的去计算这个算法执行过程中花费的时间有多长，所需占用的内存有多大。
常见的时间复杂度:
三、线性表-数组-常用操作接口-复杂度分析
1、数组特点:
内存是连续的
优点
下标访问（随机访问) 时间复杂度是O(1)。
末尾位置增加删除元素时间复杂度是O(1)。
访问元素前后相邻位置的元素非常方便
缺点
非末尾位置增加删除元素需要进行大量的数据移动。
搜索的时间复杂度
无序数组-线性搜索O(n)·
有序数组-二分搜索O(logn)。
数组扩容消耗比较大
扩容
2、内存分布
对于我们C和C++的程序，程序运行以后叫做进程，进程在内存上的布局，它的内存可用内存主要分为三个部分：
数据段（.data ---- 存放全局变量，系统分配，系统释放，其生命周期是整个程序的生命周期
堆（heap --- C语言里边通过malloc free ，c++边儿通过new跟delete来去自己去开辟，自己去释放的，
栈（stack --- 随着函数进来分配内存，函数出一括号，内存释放
3、数组代码输出
相关接口：
class Array
{
public:
//构造
Array(int size = 10);
//析构
~Array();
public:
//末尾增加元素
void push_back(int val);
//末尾删除元素
void pop_back();
//按位置增加元素
void insert(int pos,int val);
//按元素值删除
void erase(int val);
//元素查询
int find(int val);
private:
int * mpArr; //指向可扩容的数组内存
int mCap_; //数组的容量
int mCur; //数组有效元素的个数
};
代码实现
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
//数组实现
class Array
{
public:
Array(int size = 10):mCur(0),mCap(size)
{
mpArr = new int[mCap]();
}
~Array()
{
if(mpArr != nullptr)//用处不大，不能保证指针不为空，指针指向的内存是否是有效内存，想要开发者来保证
delete []mpArr;
mpArr = nullptr;//防止野指针
}
public:
//末尾增加元素
void push_back(int val)
{
if(mCur == mCap)//数组满了,扩容 -- 在原有的基础上再定义新的内存，这个内存大小是原有内存的两倍，进行数据拷贝，释放原堆内存
{
expand(2 * mCap);
}
mpArr[mCur++] = val;
}
//末尾删除元素
void pop_back()
{
if(mCur == 0)
{
return;
}
mCur--;
}
//按位置增加元素
void insert(int pos,int val)
{
if(pos < 0 || pos > mCur)
{
return;//throw "pos invalid!"
}
if(mCur == mCap)
{
expand(2 * mCap);
}
//移动元素
for (int i= mCur;i > pos; i--)
{
mpArr[i] = mpArr[i-1];
}
mpArr[pos] = val;
mCur++;
}
//按位置删除
void erase(int pos)
{
if(pos < 0 || pos > mCur)
{
return;//throw "pos invalid!"
}
//移动元素
for (int i= pos + 1;i < mCur; i++)
{
mpArr[i-1] = mpArr[i];
}
mCur--;
}
//按照元素值查询,返回下标
int find(int val)
{
for(int i=0; i < mCur; i++)
{
if(mpArr[i] == val)
{
return i;
}
}
return -1;
}
//打印数据
void show()const
{
for(int i=0; i < mCur; i++)
{
cout << mpArr[i] << " ";
}
cout << endl;
}
private:
//内部数组扩容接口
void expand(int size)
{
int* p = new int(size);
memcpy(p,mpArr,sizeof(int) * mCap);
delete[]mpArr;
mpArr = p;
mCap = size;
}
private:
int *mpArr; //指向可扩容的数组内存
int mCap; //数组的容量
int mCur; //数组有效元素的个数
};
测试
int main()
{
Array arr;
srand(time(0));//生成随机数
for(int i = 0;i < 10;i++)
{
arr.push_back(rand() % 100);
}
//测试
arr.show();
arr.pop_back();
arr.show();
arr.insert(0,100);
arr.show();
arr.insert(10,200);
arr.show();
int pos = arr.find(100);
if(pos != -1)
{
arr.erase(pos);
arr.show;
}
}
运行结果：
四、线性表-数组-笔试面试常见问题-基于数组的双指针思想
1、元素逆序问题
#include <iostream>
#include <string.h>
using namespace std;
//逆序字符串
void Reverse(char arr[],int size)
{
char* p = arr;
char* q = arr + size - 1;
while (p < q)
{
char ch = *p;
*p = *q;
*q = ch;
p++;
q--;
}
}
int main()
{
char arr[] = "kyrie_sakura";
Reverse(arr,strlen(arr));
cout << arr << endl;
}
运行结果：
2、奇偶数调整问题：整形数组，把偶数调整到数组的左边，把奇数调整到数组的右边
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <string.h>
using namespace std;
//奇偶数调整问题：整形数组，把偶数调整到数组的左边，把奇数调整到数组的右边
void AdjustArray(int arr[],int size)
{
int* p = arr;
int* q = arr + size -1;
while(p < q)
{
//p->奇数
while(p < q)
{
if((*p & 0x1) == 0)
{
break;
}
p++;
}
//q<-偶数
while(p < q)
{
if((*q & 0x1) == 1)
{
break;
}
q--;
}
//p奇数，q偶数
if(p < q)
{
int tmp = *p;
*p = *q;
*q = tmp;
p++;
q--;
}
}
}
代码测试：
int main()
{
int arr[10] = {0};
srand(time(0));
for(int i = 0; i < 10; i++)
{
arr[i] = rand() % 100;
}
for(int v:arr)
{
cout << v << " ";
}
cout << endl;
AdjustArray(arr,10);
for(int v:arr)
{
cout << v << " ";
}
cout << endl;
}
测试结果
