iOS面试题12-数据结构算法篇

2018 iOS面试题系列

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 双向链表


数组和链表区别:
数组:数组元素在内存上连续存放,可以通过下标查找元素;插入、删除需要移动大量元素,比较适用于元素很少变化的情况
链表:链表中的元素在内存中不是顺序存储的,查找慢,插入、删除只需要对元素指针重新赋值,效率高

  • 3.3 循环链表
            循环链表是与单向链表一样,是一种链式的存储结构,所不同的是,循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点,从而构成一个环形的链。发挥想象力 A->B->C->D->E->F->G->H->A. 绕成一个圈。就像蛇吃自己的这就是循环 不需要去死记硬背哪些理论知识。

4.二叉树/平衡二叉树

  • 4.1 什么是二叉树
            树形结构下,两个节点以内 都称之为二叉树 不存在大于2 的节点 分为左子树 右子树 有顺序 不能颠倒 ,懵逼了吧,你肯定会想这是什么玩意,什么左子树右子树 ,都什么跟什么鬼? 现在我以普通话再讲一遍,你把二叉树看成一个人 ,人的头呢就是树的根 ,左子树就是左手,右子树就是右手,左右手可以都没有(残疾嘛,声明一下,绝非歧视残疾朋友,勿怪,勿怪就是举个例子,i am very sorry) , 左右手呢可以有一个,就是不能颠倒。这样讲应该明白了吧

二叉树有五种表现形式

  1. 空的树(没有节点)可以理解为什么都没 像空气一样

  2. 只有根节点。 (理解一个人只有一个头 其他的什么都没,说的有点恐怖)

  3. 只有左子树 (一个头 一个左手 感觉越来越写不下去了)

  4. 只有右子树

  5. 左右子树都有

       二叉树可以转换成森林 树也可以转换成二叉树。这里就不介绍了 你做项目绝对用不到

       数据结构大致介绍这么多吧。理解为主, 别死记,死记没什么用

5.算法

从现在开始介绍算法啊

  • 5.1 冒泡排序 和选择排序
冒泡排序 和选择排序.png
  • 5.2 插入排序
插入排序.png
  • 5.3 希尔排序
希尔排序 .png
  • 5.3.1 二分查找
二分查找.png
  • 5.3.2 快排
快排.png
  • 5.4 二叉树

       二叉树这个比较麻烦 还有平衡二叉树 有点绕 如果不懂二叉树这一块 你是百分之二百看不懂的

  1. 如果左子树非空,那么左子树所有节点的值均小于它的根节点

  2. 如果右子树非空,那么右子树所有节点的值均大于它的根节点

  3. 左右子树也分别为二叉排序树

原文链接

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,723评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,485评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,998评论 0 344
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,323评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,355评论 5 374
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,079评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,389评论 3 400
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,019评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,519评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,971评论 2 325
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,100评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,738评论 4 324
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,293评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,289评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,517评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,547评论 2 354
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,834评论 2 345

推荐阅读更多精彩内容