一、数组

数组：数组的存储是连续的

数组只能覆盖不能插入，删除

数组的创建

int arr1[10] //定义一个数组长度是10int arr3[5] = {1，2，3，4，5};//直接创建一个数组int arr2[] = {1,2,3,4};//创建一个数组，不标明长度也行

二、链表

1、单链表最后一个next指向null

2、要改变链表节点的话，一般最后设置一个虚节点，这样便于对头结点进行操作

3、要改变next指针指向，要先消除原先的指向，这样的话就无法访问到之间的一些节点要注意

4、插入节点的时候，先让新节点指向旧节点，要是先让旧节点指向新节点就会先断裂原先的链表

节点的插入

我们需要知道插入位置的前一个节点位置cur，再加上cur->next就把前后节点位置都找到了

  先是新节点指向cur->next

  然后再是cur->next指向新节点

节点的删除

需要两个指针，一个pre指向目标前一个节点，一个cur指针指向要删除的目标节点，然后利用

cur->next访问到要删除的节点的下一个节点

注意：在对next指针进行操作的时候，原先的会断裂

 节点的反转

需要三个指针，一个pre指针指向反转的前一个节点，cur指向要反转的节点，然后设置有一个temp指针指向需要反转的下一个节点，用来使得cur指针移动，因为我们反转之后，无法使用next指针访问到后一个节点 

两两交换节点

在我们修改过程中，指针一直在变。cur->next不一定可以访问到我们要的节点

cur指针两两指向交换的后一个节点

终止条件（cur的后一个或者两个为空，这斗凑不到一对，怎么换）

删除倒数第n个节点间

 快指针先跑n。然后快慢指针一起运行。等块指针指向空，慢指针指向就是倒数第n个节点

环形链表

双指针法

当fast指针一次移动两格，slow一次移动一格，当要是有换的话就会在环中遇到

环的终止条件是（快指针的下一步存在）

怎么找到入口处

从相遇点出发一个指针，从头部出发一个指针，会在入口处相遇

三、哈希表

哈希表的原理就是将key带入哈希函数中，然后就会生成一个数组的索引

哈希表的原理就是快速查找key，在map中 key存放元素，value就随意

哈希表的插入

set

m.insert(x);

unordered_set hash1(nums1.begin(),nums1.end()); //直接在初始化的时候插入整

哈希set会自动去重复元素

map

m.insert(pair(1, 10));

hash[s[i]];表示将将是是s[i]插入哈希表中，默认value就是0

哈希表的遍历

end指针指向表中最后一个元素的下一个地址

set

unordered_set count;
for(auto it=m.begin();it!=m.end();it++)
{int result = *it;   //key}

map

unordered_map count;
for(auto it=m.begin();it!=m.end();it++)
{int front = it->first;   //keyint end = it->second;   //value
}

哈希表的一般用法

判断是否有重复

unordered_set 

存放重复次数（存放其他也行）

unordered_map

哈希表中常用的哈数

find函数，查找哈希表中是否存有这个元素

if(map.find(3) != map.end()) //map中key是否有三，要是没有find函数返回的指针指指向map.end

四、字符串

字符串的创建

string str1 = "this is an example!"; //initial string srting str2； //create an empty string object;

字符串加法，就是字符串拼凑

库函数

s.erase(7,5);//从索引7开始往后删5个s.substr(5,6);//取从索引5开始6个字符reverse（begin(),end()）;//左闭右开s.find(  ) 字符串查找函数，返回一个下标s.resize(3)   //改变大小

to_string(n) //将整型数字转成字符串stoi(str) //将字符串转成整数

左旋转字符串  

1、新建一个字符串，将两个拼接在一起

2、在原地修改，使用reverse函数，颠三倒四

反转字符串

快指针是找到我们需要的元素，然后赋给慢指针

反转字符串里面的单词

1、删除空格

快慢指针，块指针获取我们需要需要的元素，然后赋值给我买的慢指针

注意我们这样需要手动添加单词之间的空格，

单词一个一个录入，等快指针遍历到空格就一个单词结束，等下轮开始找到一个元素进行开始，我们也在这里添加一个空格

 

2、大反转 使用reverse（s.begin(),s.end()）

 

3、单词反转,两个指针交换单词首尾

栈和队列

栈 ：提供push 和pop等等接口，所有元素必须符合先进后出规则，所以栈不提供走访功能，也不提供迭代

接口：

push

pop

top

队列：先进先出

que.front()//获取头部元素
que.back()
que.pop()
que.front()        // 取队首元素
que.back()        // 取队尾元素
que.push(x )    // 将元素x入队，从已有元素后面增加元素
que.pop()          // 将队首元素出队
que.size()          // 返回队列的长度（即队列中的元素个数）
que.empty()    // 判断队列是否为空，若为空则返回1，否则返回0

1、用栈实现队列

verctor

容器的创建   

vector a(10); //定义了10个整型元素的向量

a.back(); //返回a的最后一个元素a.front(); //返回a的第一个元素a.empty(); //判断a是否为空，空则返回ture,不空则返回falsea.pop_back(); //删除a向量的最后一个元素a.push_back(5); //在a的最后一个向量后插入一个元素，其值为5a.insert(a.begin()+1,5); //在a的第1个元素（从第0个算起）的位置插入数值5，如a为1,2,3,4，插入元素后为1,5,2,3,4a.erase(a.begin()+1,a.begin()+3); //删除a中第1个（从第0个算起）到第2个元素，也就是说删除的元素从a.begin()+1算起（包括它）一直到a.begin()+3（不包括它）

通过遍历器方式读取

int a[6]={1,2,3,4,5,6};
vector b(a,a+4);
for(vector::iterator it=b.begin();it!=b.end();it++)cout<<*it<<" ";