美文网首页
数据结构

数据结构

作者: 雪茸川 | 来源:发表于2019-08-02 14:11 被阅读0次
    • 存储对象的集合
    • 集合不同的类型有不同的查找方法

    抽象数据类型(ADT)

    把数据类型和数据类型上的运算捆在一起,进行封装
    常用的数据运算:
    插入、删除、修改、查找、排序

    • 组织基本数据类型
      int, float, chart
    • 内存
      连续的存储单元,一个字节会有一个地址标识
      int:4个字节,char:1个字节

    顺序表

    • 一种数据,相同类型
      Loc[k] = Loc[0]+k*c
    • 不同类型
      顺序表存储的是元素地址

    顺序表的结构与实现

    • 元素存储区的容量
    • 当前表中已有的元素个数
      表头+ 数据

    一体式结构和分离式结构

    顺序表的扩展,分离式比较方便
    扩充的两种策略

    • 每次增加固定数目,线性增长
    • 每次翻倍

    顺序表的操作

    • 插入
    1. 尾端增加元素,时间复杂度O(1)
    2. 保证顺序的元素插入O(n)
      3.非保序的元素插入O(1)
      *删除

    python中的顺序表

    List 特征

    • 按下标位置索引 O(1)
    • 任意加元素,分离式存储,表头不变
    • 空列表,8个元素存储区
    • 4倍增长达到一定阈值后2倍增长

    链表

    将元素存放在通过链接构造起来的一系列存储块里
    特点:可以充分利用计算机空间,实现灵活的内存动态管理

    链表的实现

    元素 = 数据区+链接区

    单向链表

    单链表的操作
    python中地址表示

    python中声明的变量,保存的是地址

    特点:

    • 只能在一端(top)输入(push)和输出(pop)
    • 先进后出

    栈结构的实现

    栈的操作:

    • Stack() 创建一个新的栈
    • push(item) 添加一个新的元素item到栈顶
    • pop() 弹出栈顶元素
    • peek() 返回栈顶元素
    • is_empty() 判断栈是否为空
    • size() 返回栈元素个数

    队列

    特点:

    • 一端添加,另一端取
    • 先进先出

    相关文章

      网友评论

          本文标题:数据结构

          本文链接:https://www.haomeiwen.com/subject/ghwkdctx.html