废话不多说，我们开始～
一、数据结构
1.集合结构、线性结构、树形结构、图形结构
1.集合结构：一个集合中有很多元素，元素与元素之间无任何关系
2.线性结构：一条线上有很多元素（直线、曲线），元素与元素之间是一对一的关系
3.树形结构：想象成金字塔的一种结构，其元素之间是一对多的关系
4.图形结构：无穷、无边、无向，任意图形，其元素之间是多对多的关系
2.数据结构的存储
1.顺序存储结构（栈是先进后出、队列是先进先出---栈砌墙拆墙，队列蛇进出洞）
2.链式存储结构（12345数组存储时，链式存储则可能为1(地址)2(地址)5(地址)3(地址)4(地址)，存储时每个数字后跟着一个地址，而且存储形式不再是顺序，1(地址)1后跟着的这个地址指向的是2，2后面的地址指向3，执行时顺序拿出，存储时不会顺序存储哦而是随机）
3.单向链表、双向链表、循环链表
1.单向链表：A->B->C->D->E，E是头A是尾，形如只有一个车头的火车
2.双向链表：E<-A->B->C->D->E，有头无尾，两个头，两边都可以跑，形如两个头的火车
3.循环链表：->A->B->C->D->E->，绕成一圈
4.二叉树、平衡二叉树（树形结构下的哦）
1.二叉树：树形结构+两个节点以内，分别叫做左子树和右子树，有顺序不能颠倒
五种表现形式：
（1）空的树，无节点
（2）只有根节点
（3）只有左子树
（4）只有右子树
（5）左右子树都有
二、算法
1.冒泡排序
// 1.未排序的数组
NSMutableArray *arr = [NSMutableArray arrayWithObjects:@"16", @"28", @"6", @"8", @"66", nil]
// 2.开始排序
for (int i = 0; i < arr.count - 1; i++)
{
for (int j = 0; j < arr.count - 1 - i; j++)
{
// 比较次数
if ([arr[j] intValue] > [arr[j + 1] interValue])
{
// 升序排序
int temp = [arr[j] interValue];
arr[j] = arr[j + 1];
arr[j + 1] = [NSString stringWithFormat:@"%d", temp];
}
}
}
// 3.排序完成咯
NSLog(@"排序结果：%@", arr);
2.选择排序
// 1.未排序的数组
NSMutableArray *arr = [NSMutableArray arrayWithObjects:@"16", @"28", @"6", @"8", @"66", nil]
// 2.开始排序
for (int i = 0; i < arr.count - 1; i++)
{
for (int j = i + 1; j < arr.count; j++)
{
// 比较
if ([arr[i] intValue] > [arr[j] interValue])
{
// 排序
int temp = [arr[i] interValue];
arr[i] = arr[j];
arr[j] = [NSString stringWithFormat:@"%d", temp];
}
}
}
// 3.排序完成咯
NSLog(@"排序结果：%@", arr);
3.插入排序
NSMutableArray *list = [NSMutableArray = arrayWithObjects:@"16", @"18", @"6", @"8", @"66", nil];
for (int i = 1; i < [list count]; i++)
{
int j = i;
NSInteger temp = [[list objectAtIndex:i] integerValue];
while (j > 0 && temp < [[list objectAtIndex:j-1] integerValue])
{
[list replaceObjectAtIndex:J withObject:[list objectAtIndex:(j - 1)]];
j--;
}
[list replaceObjectAtIndex:j withObject:[NSNumber numberWithInteger:temp]];
}
NSLog(@"输出结果：%@", list);
4.希尔排序
NSMutableArray *list = [NSMutableArray = arrayWithObjects:@"16", @"18", @"6", @"8", @"66", nil];
int gap = [list count] / 2.0;
while (gap >= 1)
{
for (int I = gap; i < [list count]; i++)
{
NSInteger temp = [[list objectAtIndex:i] integerValue];
int j = I;
while (j >= gap && temp < [[list objectAtIndex:(j-gap)] integerValue])
{
[list replaceObjectAtIndex:j withObject:[list objectAtIndex:j - gap]];
}
[list replaceObjectAtIndex:j withObject:[NSNumber numberWithInteger:temp]];
}
gap = gap / 2;
}
NSLog(@"输出结果：%@", list);
1.二分查找
if (low < height)
{
NSInteger mid = (low + height) / 2;
if (key == arr[mid])
{
return mid;
} else if (key < arr[mid])
{
return [self erFenChaZhaoSuanFa:arr low:low High:mid - 1 Data:key];
} else
{
return [self erFenChaZhaoSuanFa:arr low:mid + 1 High:hight Data:key];
}
} else
{
NSLog(@"参数错误");
return -1;
}
2.快排
- (void)kuaisupaixu:(NSMutableArray *)arr low:(NSInteger)left High:(NSInteger)right
{
if(left <= right) return;
NSInteger I = left;
NSInteger j = right;
NSInteger key = [arr[left] integerValue];
while (I < j) {
while (I < j && key <= [arr[j] integerValue]) {
j--;
}
arr[i] = arr[j];
while (I < j && key >= [arr[I] integerValue]) {
I++;
}
arr[j] = arr[i];
}
arr[i] = [NSNumber numberWithInteger:key];
[self kuaisupaixu:arr low:left high:i-1];
[self kuaisupaixu:arr low:i+1 high:right];
}
参考文章
iOS数据结构 和 算法 上
网友评论