数据结构与算法笔记

线性表的顺序存储结构

顺序存储结构的三个属性：

• 存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置
• 线性表的最大存储容量：数组长度MaxSize
• 线性表的当前长度：Length

数据长度和线性表的长度区别：

• 数据长度是存放线性表的存储空间的长度，存储分配后一般是不可变的
• 线性表的长度是线性表中数据元素的个数，随着线性表插入和删除会发生变化
• 线性表的长度应该小于等于数组的长度

线性表顺序存储结构的优缺点：

• 优点
  • 无须为表示表中元素之间的逻辑关系二增加额外的存储空间
  • 可以快速的存取表中任一位置的元素
• 缺点
  • 插入和删除操作需要移动大量元素
  • 当线性表长度变化较大时，难以确定存储空间的容量
  • 造成存储空间的“碎片”

线性表的顺序存储结构

头指针和头结点的异同

• 头指针
  • 头指针是指链表指向第一个结点的指针，若链表有头结点，则指向头结点的指针
  • 头指针具有标识作用，所以常用头指针冠以链表的名字
  • 无论链表是否为空，头指针均不为空。头指针是链表的必要元素
• 头结点
  • 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度）
  • 有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其他结点的操作就统一了
  • 头结点不一定是链表必须要素
• 注意：对于插入和删除数据越频繁的操作，单链表的效率优势就越明显

• 单链表的创建主要分为（头插法和尾插法）

  
  单链表结构和顺序结构的区别