数据结构（顺序表、单链表）

这是一篇关于数据结构（顺序表、单链表）的脑图，讲述了线性表（存储方式的定位、存储方式的链表），收藏下图了解吧！

数据结构

• 线性表
  • 除了第一个元素外，其他元素有唯一的直接前驱。
  • 除了最后一个元素外，其他元素有唯一的直接后继。
  • 存储方式
    • 定位：顺序表（连续，不允许有空）
      • 静态分配（ElemType data[MaxSize];）
      • 动态分配（int *elem)定义基地址
      • 方法(随机存取)
        • 初始化o(1)
          • 1、分配一段连续空间
          • 2、长度为0
          • L.elem=new int[MaxSize];
        • 取值o(1)
          • 1、判断位置的合法性
          • 2、根据pos-1取值
        • 查找o(n)
          • 1、遍历顺序表
          • 2、找到返回位置，找不到返回-1
        • 插入o(n)
          • 1、判断pos的合法性
          • 2、腾出pos-1的空间（从后往前移动）
          • 3、将e放到pos-1上
          • 4、长度加一
          • n(n+1)/2，移动次数为n/2，时间复杂度o(n)
        • 删除o(n)
          • 1、判断pos的合法性
          • 2、将pos元素往前移
          • 3、长度减一
          • 移动次数（n-1）/2
      • 总结
        • 1、多练习
        • 2、主函数中方法的使用
    • 链表（头指针）
      • 单链表(头结点，操作比较方便）
        • data域（头结点不存数据，第一个元素（首元结点）int data
        • 指针域（最后一个为NULL)struct Lnode *next
        • 方法
          • 创建
            • 头插法（逆序建表），先建立一个带头空链表
              • 1、生成新结点s并放入数据
              • 2、将s结点的指针域指向前一个结点的next域（s->next=L->next)；
              • 3、将L的指针域指向s(L->next=s)
            • 尾插法（顺序建表，必须有尾指针，直接在尾部插入），先建立一个带头空链表
              • 1、尾指针的指针域指向s
              • 2、尾指针的指针域后移
          • 取值（顺序存取）o(n)
            • 注意位置的合法性。指针后移，直到=pos(头指针不可以移动，需要新定义一个指针指向首元结点）
          • 查找o(1)
            • 同取值（要判断p是否为空）
          • 删除o(1)
            • 跳过需删除的结点
            • 释放需删除的结点
            • 注意：判断p->next（如果合法，p->next一定存在）
          • 逆置（头插法）
            • 1、记录结点，置空
            • 2、q记录p的下一个结点
            • 3、移动p、q结点
            • p指针指向要操作的结点，q指针指向断点
          • 初始化
            • 1、新建结点
            • 2、指针域置空
          • 插入（先修改没有指针标记的那一端）o(n)
            • 找位置
            • 插入