数据结构的存储
数据结构的存储一般常
用的有两种 顺序存储结构 和 链式存储结构
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.1 单向链表
A->B->C->D->E->F->G->H. 这就是单向链表 H 是头 A 是尾 像一个只有一个头的火车一样 只能一个头拉
着跑
3.2 双向链表
数组和链表区别:
数组:数组元素在内存上连续存放，可以通过下标查找元素;插入、删除需要移动大量元素，比较适用元
素很少变化的情况
链表:链表中的元素在内存中不是顺序存储的，查找慢，插入、删除只需要对元素指针重新赋值，效率高
3.3 循环链表
循环链表是与单向链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个结点的指针是指 向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。发挥想象力 A->B->C->D->E->F->G->H->A. 绕成一个圈。就像蛇吃自己的这就是循环 不需要去死记硬背哪些理论知识。
4.1 什么是二叉树
树形结构下,两个节点以内 都称之为二叉树 不存在大于 2 的节点 分为左子树 右子树 有顺序 不能颠 倒 ，懵逼了吧，你肯定会想这是什么玩意，什么左子树右子树 ，都什么跟什么鬼? 现在我以普通话再讲 一遍，你把二叉树看成一个人 ，人的头呢就是树的根 ，左子树就是左手，右子树就是右手，左右手可以 都没有(残疾嘛，声明一下，绝非歧视残疾朋友，勿怪，勿怪就是举个例子，i am very sorry) , 左右 手呢可以有一个，就是不能颠倒。这样讲应该明白了吧
二叉树有五种表现形式
1.空的树(没有节点)可以理解为什么都没 像空气一样
2.只有根节点。 (理解一个人只有一个头 其他的什么都没，说的有点恐怖) 3.只有左子树 (一个头 一个左手 感觉越来越写不下去了)
4.只有右子树
5.左右子树都有
二叉树可以转换成森林 树也可以转换成二叉树。这里就不介绍了 你做项目绝对用不到 数据结构大致介绍这么多吧。理解为主, 别死记，死记没什么用
1、不用中间变量,用两种方法交换 A 和 B 的值
2、求最大公约数
3、模拟栈操作
栈是一种数据结构，特点:先进后出 -
练习:使用全局变量模拟栈的操作
include <stdio.h> #include <stdbool.h> #include <assert.h>
//保护全局变量:在全局变量前加 static 后，这个全局变量就只能在本文件中使用 static int data[1024];//栈最多能保存 1024 个数据
static int count = 0;//目前已经放了多少个数(相当于栈顶位置)
4、排序算法
选择排序、冒泡排序、插入排序三种排序算法可以总结为如下:
都将数组分为已排序部分和未排序部分。
1.选择排序将已排序部分定义在左端，然后选择未排序部分的最小元素和未排序部分的第一个元素交换。 2.冒泡排序将已排序部分定义在右端，在遍历未排序部分的过程执行交换，将最大元素交换到最右端。 3.插入排序将已排序部分定义在左端，将未排序部分元的第一个元素插入到已排序部分合适的位置。 4.1、选择排序
【选择排序】:最值出现在起始端
第1趟:在n个数中找到最小(大)数与第一个数交换位置
第2趟:在剩下n-1个数中找到最小(大)数与第二个数交换位置 重复这样的操作...依次与第三个、第四个...数交换位置
第n-1趟，最终可实现数据的升序(降序)排列。
/**
选择排序
*/
void xuanzePaixu() {
NSMutableArray *arr = [NSMutableArray arrayWithObjects:@"17",@"29",@"35",@"14",@"40", nil];
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[j] intValue];
arr[j] = arr[i];
arr[i] = [NSString stringWithFormat:@"%d",temp];
}
}
}
NSLog(@"%@",arr);
}
4.2、冒泡排序
【冒泡排序】:相邻元素两两比较，比较完一趟，最值出现在末尾
第1趟:依次比较相邻的两个数，不断交换(小数放前，大数放后)逐个推进，最值最后出现在第n
个元素位置
第2趟:依次比较相邻的两个数，不断交换(小数放前，大数放后)逐个推进，最值最后出现在第n-1
个元素位置
............
第n-1趟:依次比较相邻的两个数，不断交换(小数放前，大数放后)逐个推进，最值最后出现在第
2 个元素位置
/**
冒泡排序
*/
void maoPaoPaixu(void) {
NSMutableArray *arr = [NSMutableArray arrayWithObjects:@"17",@"29",@"35",@"14",@"40", nil];
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、折半查找(二分查找)
折半查找:优化查找时间(不用遍历全部数据)
折半查找的原理:
1> 数组必须是有序的
2> 必须已知 min 和 max(知道范围)
3> 动态计算 mid 的值，取出 mid 对应的值进行比较
4> 如果 mid 对应的值大于要查找的值，那么 max 要变小为 mid-1
5> 如果 mid 对应的值小于要查找的值，那么 min 要变大为 mid+1
// 已知一个有序数组, 和一个 key, 要求从数组中找到 key 对应的索引位置
/**
二分查找
@param ary
@param findNum
@return
*/
NSInteger efChazhao(NSArray *ary,NSInteger findNum) {
NSInteger mid = (ary.count - 1) / 2.0;
if (mid == 0) {
return -1; //找不到
}
if (findNum == [ary[mid] integerValue]) {
return mid;//返回所在的序列号
}
else if(findNum > [ary[mid] integerValue]) {
return efChazhao([ary subarrayWithRange:NSMakeRange(mid + 1, ary.count - mid - 1)], findNum);
}
else {
return efChazhao([ary subarrayWithRange:NSMakeRange(0, mid + 1)], findNum);
}
}
void erfenChazhao() {
//二分查找一定是有序的数组
NSMutableArray *arr = [NSMutableArray arrayWithObjects:@"17",@"29",@"35",@"14",@"40", nil];
NSInteger mid = efChazhao(arr,15);
NSLog(@"%ld",(long)mid);
}
/**
快速排序
*/
void ksPaixu(NSMutableArray *arr,NSInteger left,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] = [NSString stringWithFormat:@"%ld",(long)key];
ksPaixu(arr, left, i-1);
ksPaixu(arr, i+1, right);
}
void kuaisuPaixu() {
NSMutableArray *arr = [NSMutableArray arrayWithObjects:@"17",@"29",@"35",@"14",@"40", nil];
ksPaixu(arr, 0, arr.count-1);
NSLog(@"%@",arr);
}
/**
插入排序
*/
void charuPaixu() {
NSMutableArray *arr = [NSMutableArray arrayWithObjects:@"17",@"29",@"35",@"14",@"40", nil];
for (int i = 1; i<arr.count; i++) {
int j = I;
NSInteger temp = [arr[i] integerValue];
while (j > 0 && temp < [arr[j-1] integerValue]) {
[arr replaceObjectAtIndex:j withObject:arr[j-1]];
j--;
}
[arr replaceObjectAtIndex:j withObject:[NSString stringWithFormat:@"%ld",(long)temp]];
}
NSLog(@"%@",arr);
}
/**
希尔排序
*/
void xierPaixu() {
NSMutableArray *arr = [NSMutableArray arrayWithObjects:@"17",@"29",@"35",@"14",@"40", nil];
int gap = arr.count / 2.0;
while (gap >= 1) {
for (int i = gap; i < arr.count; i++) {
NSInteger temp = [arr[i] integerValue];
int j = I;
while (j >= gap && temp < [arr[j- gap] integerValue]) {
[arr replaceObjectAtIndex:j withObject:arr[j-gap]];
j-=gap;
}
[arr replaceObjectAtIndex:j withObject:[NSString stringWithFormat:@"%ld",(long)temp]];
}
gap = gap / 2.0;
}
NSLog(@"%@",arr);
}
字符串反正
给定字符串 "hello,world",实现将其反转。输出结果:dlrow,olleh
- (NSString *)reversalString:(NSString *)originString{
NSString *resultStr = @"";
for (NSInteger i = originString.length -1; i >= 0; i--) {
NSString *indexStr = [originString substringWithRange:NSMakeRange(i, 1)];
resultStr = [resultStr stringByAppendingString:indexStr];
}
return resultStr;
}
void char_reverse(char *cha){
char *begin = cha;
char *end = cha + strlen(cha) - 1;
while (begin <= end) {
char temp = *end;
*(end--) = *begin;
*(begin++) = temp;
}
}
// 调用
char cha[] = "hello,world";
char_reverse(cha);
printf("%s",cha);
结果：dlrow,olleh
序数组合并
将有序数组 {1,4,6,7,9} 和 {2,3,5,6,8,9,10,11,12} 合并为 {1,2,3,4,5,6,6,7,8,9,9,10,11,12}
// 将有序数组a和b的值合并到一个数组result当中，且仍然保持有序
void mergeList(int a[], int aLen, int b[], int bLen, int result[]);
void mergeList(int a[], int aLen, int b[], int bLen, int result[])
{
int p = 0; // 遍历数组a的指针
int q = 0; // 遍历数组b的指针
int i = 0; // 记录当前存储位置
// 任一数组没有到达边界则进行遍历
while (p < aLen && q < bLen) {
// 如果a数组对应位置的值小于b数组对应位置的值
if (a[p] <= b[q]) {
// 存储a数组的值
result[i] = a[p];
// 移动a数组的遍历指针
p++;
}
else{
// 存储b数组的值
result[i] = b[q];
// 移动b数组的遍历指针
q++;
}
// 指向合并结果的下一个存储位置
i++;
}
// 如果a数组有剩余
while (p < aLen) {
// 将a数组剩余部分拼接到合并结果的后面
result[i] = a[p++];
i++;
}
// 如果b数组有剩余
while (q < bLen) {
// 将b数组剩余部分拼接到合并结果的后面
result[i] = b[q++];
i++;
}
}
HASH 算法
哈希表
例:给定值是字母 a，对应 ASCII 码值是 97，数组索引下标为 97。
这里的 ASCII 码，就算是一种哈希函数，存储和查找都通过该函数，有效地提高查找效率。
在一个字符串中找到第一个只出现一次的字符。如输入"abaccdeff"，输出'b'字符(char)是一个长度为8 的数据类型，因此总共有 256 种可能。每个字母根据其 ASCII 码值作为数组下标对应数组种的一个数 字。数组中存储的是每个字符出现的次数。
查找两个子视图的共同父视图 思路:分别记录两个子视图的所有父视图并保存到数组中，然后倒序寻找,直至找到第一个不一样的父视图。
// 查找两个视图的共同父视图
- (NSArray<UIView *> *)findCommonSuperView:(UIView *)view other:(UIView *)viewOther;
- (NSArray <UIView *> *)findCommonSuperView:(UIView *)viewOne other:(UIView *)viewOther
{
NSMutableArray *result = [NSMutableArray array];
// 查找第一个视图的所有父视图
NSArray *arrayOne = [self findSuperViews:viewOne];
// 查找第二个视图的所有父视图
NSArray *arrayOther = [self findSuperViews:viewOther];
int i = 0;
// 越界限制条件
while (i < MIN((int)arrayOne.count, (int)arrayOther.count)) {
// 倒序方式获取各个视图的父视图
UIView *superOne = [arrayOne objectAtIndex:arrayOne.count - i - 1];
UIView *superOther = [arrayOther objectAtIndex:arrayOther.count - i - 1];
// 比较如果相等 则为共同父视图
if (superOne == superOther) {
[result addObject:superOne];
i++;
}
// 如果不相等，则结束遍历
else{
break;
}
}
return result;
}
- (NSArray <UIView *> *)findSuperViews:(UIView *)view
{
// 初始化为第一父视图
UIView *temp = view.superview;
// 保存结果的数组
NSMutableArray *result = [NSMutableArray array];
while (temp) {
[result addObject:temp];
// 顺着superview指针一直向上查找
temp = temp.superview;
}
return result;
}
- (void)viewDidLoad {
[super viewDidLoad];
Class commonClass1 = [self commonClass1:[ViewA class] andClass:[ViewC
class]];
NSLog(@"%@",commonClass1);
// 2018-03-22 17:36:01.868966+0800[84288:2458900] ViewD
}
//获取所有父类
- (NSArray *)superClasses:(Class)class {
if (class == nil) {
return @[];
}
NSMutableArray *result = [NSMutableArray array];
while (class != nil) {
[result addObject:class];
class = [class superclass];
}
return [result copy];
}
- (Class)commonClass1:(Class)classA andClass:(Class)classB {
NSArray *arr1 = [self superClasses:classA];
NSArray *arr2 = [self superClasses:classB];
for (NSUInteger i = 0; i < arr1.count; ++i) {
Class targetClass = arr1[i];
for (NSUInteger j = 0; j < arr2.count; ++j) {
if (targetClass == arr2[j]) {
return targetClass;
} }
}
return nil;
}
- (Class)commonClass2:(Class)classA andClass:(Class)classB{
NSArray *arr1 = [self superClasses:classA];
NSArray *arr2 = [self superClasses:classB];
NSSet *set = [NSSet setWithArray:arr2];
for (NSUInteger i =0; i<arr1.count; ++i) {
Class targetClass = arr1[i];
if ([set containsObject:targetClass]) {
return targetClass;
}
}
return nil;
}
/**
求无序数组当中的中位数(快排思想，选中关键字，高低交替扫描)
示例:
[@"1",@"9",@"6",@"8",@"3",@"2"]
输出:
@"3"
*/
+ (void)findMedianValue {undefined
NSMutableArray *array = [NSMutableArray arrayWithObjects:@"1",@"9",@"6",@"8",@"3",@"2", nil];
NSLog(@"输入数据:%@",array);
NSInteger low = 0;
NSInteger high = array.count - 1;
NSInteger mid = high/2;
NSInteger result = [self arraySort:array IndexStart:low IndexEnd:high];
while(result != mid) {undefined
if (result < mid) {undefined
result = [self arraySort:array IndexStart:result+1 IndexEnd:high];
}else {undefined
result = [self arraySort:array IndexStart:low IndexEnd:result-1];
}
}
NSLog(@"中位数是:%@",array[mid]);
}
+ (NSInteger)arraySort:(NSMutableArray *)array IndexStart:(NSInteger)indexStart IndexEnd:(NSInteger)indexEnd {undefined
NSInteger keyValue = [array[indexEnd] integerValue];
NSInteger lastEnd = indexEnd;
while (indexStart < indexEnd) {undefined
while (indexStart < indexEnd && [array[indexStart] integerValue] <= keyValue) {undefined
indexStart++;
}
while (indexStart < indexEnd && [array[indexEnd] integerValue] >= keyValue) {undefined
indexEnd--;
}
if (indexStart < indexEnd) {undefined
NSString *temp = array[indexStart];
array[indexStart] = array[indexEnd];
array[indexEnd] = temp;
}
}
NSString *temp = array[indexEnd];
array[indexEnd] = array[lastEnd];
array[lastEnd] = temp;
return indexStart;
}
//给定一个整数数组和一个目标值，找出数组中和为目标值得的俩个数
//给定nums = [2,7,11,15] ,target = 9 -------返回【0，1】
● 第一层for循环从索引0到倒数第二个索引拿到每个数组的元素
●第二个for循环遍历上一层for循环拿到的元素的后面得所有元素
class Solution {
public int[] twoSum(int[] nums, int target) {
int len = nums.length;
int[] result = new int[2];
for(int i = 0; i < len; i++){
for(int j = i+1; j < len; j++){
if(nums[i] + nums[j] == target){
result[0] = i;
result[1] = j;
return result;
} }
}
return result;
}
}
//查找第一个只出现一次的字符（hash查找）
# define SIZE 256
char GetChar(char str[])
{
if(!str)
return 0;
char* p = NULL;
unsigned count[SIZE] = {0};
char buffer[SIZE];
char* q = buffer;
for(p=str; *p!=0; p++)
{
if(++count[(unsigned char)*p] == 1)
*q++ = *p;
}
for (p=buffer; p<q; p++)
{
if(count[(unsigned char)*p] == 1)
return *p;
}
return 0;
}
char findFirstChar(char* cha)
{
char result = '\0';
// 定义一个数组 用来存储各个字母出现次数
int array[256];
// 对数组进行初始化操作
for (int i=0; i<256; i++) {
array[i] =0;
}
// 定义一个指针 指向当前字符串头部
char* p = cha;
// 遍历每个字符
while (*p != '\0') {
// 在字母对应存储位置 进行出现次数+1操作
array[*(p++)]++;
}
// 将P指针重新指向字符串头部
p = cha;
// 遍历每个字母的出现次数
while (*p != '\0') {
// 遇到第一个出现次数为1的字符，打印结果
if (array[*p] == 1)
{
result = *p;
break;
}
// 反之继续向后遍历
p++;
}
return result;
}
// 无序数组查找中位数
int list[10] = {12,3,10,8,6,7,11,13,9};
// 3 6 7 8 9 10 11 12 13
// ^
int median = findMedian(list, 10);
printf("the median is %d \n", median);
//求一个无序数组的中位数
int findMedian(int a[], int aLen)
{
int low = 0;
int high = aLen - 1;
int mid = (aLen - 1) / 2;
int div = PartSort(a, low, high);
while (div != mid)
{
if (mid < div)
{
//左半区间找
div = PartSort(a, low, div - 1);
}
else
{
//右半区间找
div = PartSort(a, div + 1, high);
}
}
//找到了
return a[mid];
}
int PartSort(int a[], int start, int end)
{
int low = start;
int high = end;
//选取关键字
int key = a[end];
while (low < high)
{
//左边找比key大的值
while (low < high && a[low] <= key)
{
++low;
}
//右边找比key小的值
while (low < high && a[high] >= key)
{
--high;
}
if (low < high)
{
//找到之后交换左右的值
int temp = a[low];
a[low] = a[high];
a[high] = temp;
}
}
int temp = a[high];
a[high] = a[end];
a[end] = temp;
return low;
}
定义一个链表
// 定义一个链表
struct Node {
int data;
struct Node *next;
};
@interface ReverseList : NSObject
// 链表反转
struct Node* reverseList(struct Node *head);
// 构造一个链表
struct Node* constructList(void);
// 打印链表中的数据
void printList(struct Node *head);
@end
#import "ReverseList.h"
@implementation ReverseList
struct Node* reverseList(struct Node *head)
{
// 定义遍历指针，初始化为头结点
struct Node *p = head;
// 反转后的链表头部
struct Node *newH = NULL;
// 遍历链表
while (p != NULL) {
// 记录下一个结点
struct Node *temp = p->next;
// 当前结点的next指向新链表头部
p->next = newH;
// 更改新链表头部为当前结点
newH = p;
// 移动p指针
p = temp;
}
// 返回反转后的链表头结点
return newH;
}
struct Node* constructList(void)
{
// 头结点定义
struct Node *head = NULL;
// 记录当前尾结点
struct Node *cur = NULL;
for (int i = 1; i < 5; i++) {
struct Node *node = malloc(sizeof(struct Node));
node->data = i;
// 头结点为空，新结点即为头结点
if (head == NULL) {
head = node;
}
// 当前结点的next为新结点
else{
cur->next = node;
}
// 设置当前结点为新结点
cur = node;
}
return head;
}
void printList(struct Node *head)
{
struct Node* temp = head;
while (temp != NULL) {
printf("node is %d \n", temp->data);
temp = temp->next;
}
}
@end
