数据结构通常分为四类：
1.集合结构 线性结构 树形结构 图形结构
1.1、集合结构：就是一个集合，就是一个圆圈中有很多个元素，元素与元素之间没有任何关系 。
1.2、线性结构 ：就是一个条线上站着很多个人。 这条线不一定是直的。也可以是弯的。也可以是值的 相当于一条线被分成了好几段的样子。 线性结构是一对一的关系。
1.3、树形结构 ：做开发的肯定或多或少的知道xml 解析 树形结构跟他非常类似。也可以想象成一个金字塔。树形结构是一对多的关系
1.4、图形结构：这个就比较复杂了。 无穷、无边、 无向（没有方向）图形机构 你可以理解为多对多 类似于我们人的交集关系。
2. 数据结构的存储
数据结构的存储一般常用的有两种 顺序存储结构 和 链式存储结构。
2.1 顺序存储结构
举个列子。数组。1-2-3-4-5-6-7-8-9-10。这个就是一个顺序存储结构 ，存储是按顺序的 栈。做开发的都熟悉。栈是先进后出 ，后进先出的形式。hello world 在栈里面从栈底到栈顶的逻辑依次为 h-e-l-l-o-w-o-r-l-d 这就是顺序存储 再比如 队列 ，队列是先进先出的对吧，从头到尾 h-e-l-l-o-w-o-r-l-d 就是这样排对的。
2.2 链式存储结构
1-2-3-4-5-6-7-8-9-10 链式存储就不一样了 1(地址)-2(地址)-7(地址)-4(地址)-5(地址)-9(地址)-8(地址)-3(地址)-6(地址)-10(地址)。每个数字后面跟着一个地址 而且存储形式不再是顺序 ，也就说顺序乱了，1（地址） 1后面跟着的这个地址指向的是2，2后面的地址指向的是3，3后面的地址指向是谁你应该清楚了吧。他执行的时候是 1(地址)-2(地址)-3(地址)-4(地址)-5(地址)-6(地址)-7(地址)-8(地址)-9(地址)-10(地址)，但是存储的时候就是完全随机的。
3. 单向链表\双向链表\循环链表
3.1 单向链表
A->B->C->D->E->F->G->H. 这就是单向链表 H 是头 A 是尾 像一个只有一个头的火车一样 只能一个头拉着跑
3.2 双向链表
H<- A->B->C->D->E->F->G->H. 这就是双向链表。有头没尾。两边都可以跑 跟地铁一样 到头了 可以倒着开回来
3.3 循环链表
A->B->C->D->E->F->G->H. 绕成一个圈。就像蛇吃自己的这就是循环。
4.二叉树／平衡二叉树
4.1 什么是二叉树
树形结构下,两个节点以内 都称之为二叉树 不存在大于2 的节点 分为左子树 右子树 有顺序 不能颠倒。
二叉树有五种表现形式
1. 空的树（没有节点）可以理解为什么都没 像空气一样
2. 只有根节点。 （理解一个人只有一个头 其他的什么都没，说的有点恐怖）
3. 只有左子树 （一个头 一个左手 感觉越来越写不下去了）
4. 只有右子树
5 、左右子树都有
二叉树可以转换成森林 树也可以转换成二叉树。
5.算法，冒泡排序、选择排序、插入排序、快速排序、二分法查找、希尔排序、戴克斯特拉算法，快捷算法，动态规划，堆排序，归并排序。
5.1 冒泡排序
1. 首先将所有待排序的数字放入工作列表中。
2. 从列表的第一个数字到倒数第二个数字，逐个检查：若某一位上的数字大于他的下一位，则将它与它的下一位交换。
3. 重复2号步骤(倒数的数字加1。例如：第一次到倒数第二个数字，第二次到倒数第三个数字，依此类推...)，直至再也不能交换。
平均时间复杂度：O(n^2)
平均空间复杂度：O(1)
-(void)maoPao{//冒泡排序
NSMutableArray *arr=[NSMutableArray arrayWithArray:@[@"17",@"28",@"36",@"15",@"29",@"39"]];
for (int i=0;i<arr.count;i++) {
for (int j=0; j<arr.count-1-i; j++) {
if ([arr[j] intValue]>[arr[j+1] intValue]) {
int temp=[arr[j] intValue];
arr[j]=arr[j+1];
arr[j+1]=[NSString stringWithFormat:@"%d",temp];
}
}
}
NSLog(@"%@",arr);
}
5.2 选择排序
1. 设数组内存放了n个待排数字，数组下标从1开始，到n结束。
2. i=1
3. 从数组的第i个元素开始到第n个元素，寻找最小的元素。（具体过程为:先设arr[i]为最小，逐一比较，若遇到比之小的则交换）
4. 将上一步找到的最小元素和第i位元素交换。
5. 如果i=n－1算法结束，否则回到第3步
平均时间复杂度：O(n^2)
平均空间复杂度：O(1)
-(void)xuanZe{//选择排序
NSMutableArray *arr=[NSMutableArray arrayWithArray:@[@"17",@"28",@"36",@"15",@"29",@"39"]];
for (int i=0;i<arr.count-1;i++) {
for (int j=i+1; j<arr.count; j++) {
if ([arr[i] intValue]>[arr[j] intValue]) {
int temp=[arr[i] intValue];
arr[i]=arr[j];
arr[j]=[NSString stringWithFormat:@"%d",temp];
}
}
}
NSLog(@"%@",arr);
}
5.3 插入排序
1. 从第一个元素开始，认为该元素已经是排好序的。
2. 取下一个元素，在已经排好序的元素序列中从后向前扫描。
3. 如果已经排好序的序列中元素大于新元素，则将该元素往右移动一个位置。
4. 重复步骤3，直到已排好序的元素小于或等于新元素。
5. 在当前位置插入新元素。
6. 重复步骤2。
平均时间复杂度：O(n^2)
平均空间复杂度：O(1)
-(void)chaRu{//插入排序
NSMutableArray *arr=[NSMutableArray arrayWithArray:@[@"17",@"28",@"36",@"15",@"29",@"39"]];
for (int i=1;i<arr.count;i++) {
int j=i;
NSInteger temp=[[arr objectAtIndex:i]integerValue];
while (j>0&&temp<[[arr objectAtIndex:j-1]integerValue]) {
[arr replaceObjectAtIndex:j withObject:[arr objectAtIndex:(j-1)]];
j--;
}
[arr replaceObjectAtIndex:j withObject:[NSNumber numberWithInteger:temp]];
}
NSLog(@"%@",arr);
}
5.4 希尔排序
-(void)xiEr{//希尔排序
NSMutableArray *arr=[NSMutableArray arrayWithArray:@[@"17",@"28",@"36",@"15",@"29",@"39"]];
NSInteger gap=arr.count/2;
while (gap>=1) {
for (NSInteger i=gap; i<arr.count; i++) {
NSInteger temp=[[arr objectAtIndex:i] integerValue];
NSInteger j=i;
while (j>=gap&&temp<[[arr objectAtIndex:(j-gap)] integerValue]) {\
[arr replaceObjectAtIndex:j withObject:[arr objectAtIndex:j-gap]];
j-=gap;
}
[arr replaceObjectAtIndex:j withObject:[NSNumber numberWithInteger:temp]];
}
gap=gap/2;
}
NSLog(@"%@",arr);
}
5.5 二分法查找
当数据量很大适宜采用该方法。 采用二分法查找时，数据需是排好序的。