数据结构和算法绪论 学习笔记(三)

继续学习数据结构和算法绪论,最近感觉有点乱,有点学不进去,但是算法基础这块还的继续。

  • 线性表基础
  • 算法小体验

线性表:一个线性表是 N 个数据元素组成的有限序列。

  • 它是一个序列,也就是说元素之间是有一个先来后到的, 存在唯一的第一个元素和最后一个元素。
  • 元素存在多个,第一个元素则无前驱(前件),而最后一个元素无后继(后件),其他元素都有前驱和后继。

不同表示:

  • 线性表的顺序表示
  • 线性表的链式表示

线性表的顺序表示:

指的是用一组地址连续的存储单元依次存储线性表的数据元素。

  • 特点:逻辑关系上相邻的两个元素在物理位置上也相邻,因此可以随机存取表中任一元素,它的存储位置可用一个简单、直观的公式来表示。
  • 缺点: 在作插入或删除操作是,需要移动大量元素。

线性表的链式表示:

  • 线性链表(单链表)
  • 循环链表
  • 双向链表

线性链表(单链表)
  • 特点: 一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。
  • 由来:
    为了表示每个数据元素 a(i) 与其直接后继数据元素 a(i+1) 之间的逻辑关系,对数据元素 a(i) 之外,还需要存储一个指示其直接后继的信息。 这两部分信息组成数据元素 a(i) 的存储映像,称为结点
    • 它包括两个域:
      • 其中的存储数据元素信息的域称为数据域
      • 存储直接后继存储位置的域称为指针域
        指针域中存储的信息称做指针
  • 由 N 个结点 链 (指针)结成一个链表,就是线性表中链式存储结构。

由于每一个结点中只包含一个指针域,所以又称之线性链表 或单链表。

单链表 —— 图片源自:[数据结构---->线性表](http://blog.csdn.net/ncepuzhuang/article/details/8162891)
循环链表
  • 特点 : 表中最后一个结点的指针域指向头结点,整个链表形成一个环。
  • 优点: 从表中的任意一结点出发都可以找到表中其他的结点。
循环单链表—— 图片源自:[数据结构---->线性表](http://blog.csdn.net/ncepuzhuang/article/details/8162891)
循环双链表—— 图片源自:[数据结构---->线性表](http://blog.csdn.net/ncepuzhuang/article/details/8162891)
双向链表
  • 特点: 在双向链表中的结点中有两个指针域,其一指向后继,另一个指向前趋。
  • 优点:在查找时,即可以顺指针查找,也可以反向查找,避免了单链表单向性的缺点,可减少时间复杂度。
双向链表——图片源自:[数据结构---->线性表](http://blog.csdn.net/ncepuzhuang/article/details/8162891)

总结对比

常常用链表的原因:
  • 顺序表的长度是固定的,如果超出分配的长度就会造成溢出,如果存放的数据太少则会造成空间浪费。
  • 在插入元素和删除元素时(尤其不在尾部时),会移动大量的元素,造成性能和效率低下。
综合说,使用时的选择对比:
  • 如果在线性表的使用中主要操作是查找,那么应当选用顺序存储实现的线性表。
  • 如果在线性表的使用中主要操作是插入、删除操作,那么选用链式存储的线性表比较好。
笔记来源:

数据结构---->线性表
【数据结构】——严蔚敏 版本


算法再体验

  • 一个合并的排序,当然以上都是先直接转化后Model 进行处理
@[
    @{
        @"name"     : @"y01",
        @"number"   : @"1"

    },
    @{
        @"name"     : @"y02",
        @"number"   : @"1"

    },
    @{
        @"name"     : @"y01",
        @"number"   : @"1"

    },
    @{
        @"name"     : @"y02",
        @"number"   : @"1"

    },
    @{
        @"name"     : @"y03",
        @"number"   : @"1"

    }
]
@[
    @{
        @"name"     : @"y01",
        @"number"   : @"2"

    },
    @{
        @"name"     : @"y02",
        @"number"   : @"2"

    },
    @{
        @"name"     : @"y03",
        @"number"   : @"1"
    }
]
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 本文内容取自于小甲鱼的数据结构与算法。http://www.jianshu.com/p/230e6fde9c75 ...
    阿阿阿阿毛阅读 2,946评论 0 7
  • 1、线性表、栈和队列等数据结构所表达和处理的数据以线性结构为组织形式。栈是一种特殊的线性表,这种线性表只能在固定的...
    雾熏阅读 2,477评论 0 10
  • 1.线性表的定义 线性表:零个或多个数据元素的有限序列序列:也就是说元素之间是有顺序的,若元素存在多个,则第一个元...
    e40c669177be阅读 2,110评论 6 15
  • 数据 元素又称为元素、结点、记录是数据的基本单位 数据项是具有独立含义的最小标识单位 数据的逻辑结构 数据的逻辑结...
    PPPeg阅读 13,792评论 0 15
  • 后来,再也没有悠闲地等过火车。 走进熙熙攘攘地车厢,又闻烟味、酒味、汗味、泡面味等混杂的难以名状的气味。有人在谈论...
    321小肥仔阅读 123评论 0 0