数据结构之线性表

发表于： 更新于： 分类于：
字数： 425 阅读：≈ 2分钟 浏览： 评论：

简介

  • 概念: 零个或多个数据元素的有限序列

抽象数据类型定义 

ADT 线性表List
Data
	线性表的数据对象集合为{a1,a2,...,an}, 每个元素的类型均为DataType, 除第一个元素a1外,每一个元素有且只有一个直接前驱元素, 除了最后一个元素an外, 每一个元素有且只有直接后驱元素。数据元素之间的关系是一对一的关系
Operation
    InitList(*L): 初始化操作, 构造一个空的线性表L
    ListEmpty(L): 若线性表L为空表，则返回TRUE，否则返回FALSE
    ClearList(*L): 将线性表置空
    GetElem(L,i,*e):
        初始条件：线性表已存在（1≤i≤ListLenght(L)）
        操作结果：用e返回线性表L中第i个数据元素的值
    locatElem(L,e): 在线性表中查找与给定值e相等的元素, 如果查找成功, 返回该元素在表中的序号表示成功; 否则, 返回0表示失败
    ListInsert(*L,i,e)
        初始条件：线性表已存在（1≤i≤ListLenght(L)+1）
        操作结果：在线性表L中第i个数据元素之前插入新元素e，L长度加1
    ListDelete(*L,i,&e)
        初始条件：线性表已存在（1≤i≤ListLenght(L)）
        操作结果：删除线性表L中第i个数据元素，用e返回其值，L长度减1
    ListLenght(L)
        初始条件：线性表已存在
        操作结果：返回线性表L数据元素个数
end ADT

存储结构

顺序存储结构

  • 定义: 用一段地址连续的存储单元依次存储线性表的数据元素
  • 存储方式: 一维数组

优缺点

  • 优点: 存储和读取数据, 时间复杂度均为O(1)
  • 缺点: 插入和删除数据, 时间复杂度均为O(n)

链式存储结构

  • 结点:
    • 为了表示每个数据元素ai与其直接后续元素ai+1之间的逻辑关系, 对于数据元素ai来说, 除了存储其本身的信息之外, 还需存储一个指示其直接后继的信息(即直接后续的存储位置)。把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素ai的存储映像, 称为结点(Node)。
    • 线性链表的最后一个结点指针为空(NULL或’^‘表示)
  • 定义:
    • n个结点(ai的存储映象)链接成一个链表, 即为线性表(a1,a2,…,an)的链式存储结构, 因为此链表的每个结点中只包含一个指针域, 所以叫做单链表
    • 头指针: 链表中第一个结点的存储位置
    • 头结点: 为了方便操作,会在单链表的第一个结点前附设一个结点称为头结点
      • 其数据域可以不存储任何信息
      • 若线性表为空表, 则头结点的指针域为"空"

头指针与头结点

  • 头指针:
    • 指向链表第一个结点的指针, 若链表有头结点,则是指向头结点的指针
    • 具有标识作用, 所以常用头指针冠以链表的名字
    • 无论链表受否为空, 头指针均不为空, 头指针是链表的必要元素
  • 头结点:
    • 为了操作的统一和方便而设立, 放在第一个元素的结点之前, 其数据域一般无意义(也可以存放链表的长度)
    • 有了头结点, 对第一个元素结点前插入结点和删除第一结点, 其操作与其他结点的操作就统一了
    • 头结点不一定是链表必须要素

单链表的创建和删除

  • 创建:
    • 头插法
    • 尾插法
  • 删除:
    • 声明一结点p和q, 将第一个结点赋值给p
    • 循环:
      • 将下一结点复制给q
      • 释放p
      • 将q赋值给p
    • 头结点指针域为空

数据操作

  • 读取: 使用while循环, 工作指针后移
  • 插入: 时间复杂度均为O(n)
//假设插入元素e的结点为s, 注意两者顺序不能颠倒
s->next = p->next;
p->next = s;
  • 删除: 时间复杂度均为O(n)
//假设将结点q删除
q = p->next;
p->next = q->next;

优缺点

  • 优点: 对于插入和删除余额频繁的操作, 单链表的效率优势就越明显
  • 缺点: 查找的时间复杂度为O(n)

两种存储结构对比

  • 存储分配方式:
    • 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
    • 单链表采用链式存储结构, 用一组任意的存储单元存放线性表的元素
  • 时间性能:
    • 查找: 顺序存储结构O(1), 单链表O(n)
    • 插入和删除:
      • 顺序存储结构要平均移动表长一半的元素, 时间为O(n)
      • 单链表在查出某位置的指针后, 插入和删除时间仅为O(1)
  • 空间性能:
    • 顺序存储结构需要预分配存储空间, 太大浪费, 太小易发生上溢
    • 单链表不需要预分配, 只要有就可以分配, 元素个数也不受限制

其他链式存储结构

  • 静态链表
    • 定义: 用数组描述的链表
  • 循环链表
    • 定义: 将单链表中终端结点的指针端由空指针改为指向头结点, 就使整个单链表形成一个环, 这种头尾相接的单链表称为单循环连链表, 简称循环链表
    • 遍历: 条件为p->next不等于头结点, 则循环未结束
    • 尾指针: 方便合并操作
  • 双向链表: 使用空间换取时间
    • 定义: 在单链表的每个结点中, 再设置一个指向其前驱结点的指针域
    • 插入
//假设存储元素e的结点为s
s->prior = p;
s->next = p->next;
p->next->prior = s;
p->next = s;

* 删除

//假设要删除结点p
p->prior->next = p->next;
p->next->prior = p->prior;

特殊的线性表: 栈和队列

  • 限定了线性表的插入和删除位置

栈

  • 定义: 限定仅在表尾进行插入和删除操作的线性表, 允许插入和删除的称为栈顶(即表尾), 另一端为栈底
  • 特点: 后进先出(LIFO)

抽象数据结构 

ADT 栈(stack)
Data
	同线性表, 元素具有相同的类型, 相邻元素具有前驱和后驱关系
Operation
	InitStack(*S): 初始化操作, 建立一个空栈S
	DestroyStack(*S): 若栈存在, 则销毁它
	ClearStack(*S): 将栈清空
	StackEmpty(S): 若栈为空, 则返回true, 否则返回false
	GetTop(S,*e): 若栈存在且非空, 用e返回S的栈顶元素
	Push(*S,e): 若栈S存在, 插入新元素e到栈S中并成为栈顶元素
	Pop(*S,e): 删除栈S中栈顶的元素, 并用e返回其值
	StackLength(S): 返回栈S的元素个数
end ADT

顺序存储结构(顺序栈)及实现

  • 数组实现: 下标为0作为栈底
    • 定义top变量指示栈顶元素在数组中的位置, 存在一个元素时为0, 空栈为-1

进栈和出栈操作

  • 进栈(push)
//todo判断是否栈满
S->top ++;
S->data[S->top] = e;
  • 出栈(pop)
//todo判断是否空栈
*e = S->data[S->top];
S->top --;

两栈共享空间

  • 数组实现: 一个栈的栈底为数组的始端, 另一个栈为栈的末端
  • 栈满: top1 + 1 = top2
  • 说明: 通常这样的数据结构是两个栈的控件需求有相反关系

链式存储结构(链栈)及实现

  • 结构: 将栈顶放在单链表的头部, 通常对于链栈来说, 是不需要头结点的
    • 对于链栈来说, 基本不存在栈满的情况(除非系统的内存不够)
  • 实现:
    • 空栈, top=NULL

进栈和出栈操作

  • 进栈
//假设元素值为e的新结点为s, top为栈顶指针
s->data = e;
s->next = S->top;
S->top = s;
S->count ++;
  • 出栈
//假设p存储要删除的栈顶结点
//todo判断是否为空栈
*e = S->top->data;
p = S->top;
S->top = S->top->next;
free(p);
S->count --;

使用场景

  • 如果栈的使用过程中元素变化不可预测, 有时很小, 有时非常大, 最好使用链栈;
  • 反之, 如果他的变化在可控范围内, 建议使用顺序栈

递归: 编译器使用栈实现递归

  • 定义: 直接或间接的调用自己的函数
  • 条件: 至少有一个条件, 满足时递归不再进行, 即不再引用自身而是返回值退出
  • 与迭代的区别:
    • 迭代使用的是循环结构, 递归使用的是选择结构
    • 大量的递归调调用会建立函数副本, 会耗费大量的世间和内存
  • 应用:
    • 斐波拉契数列(Fibonacci)

四则表达式求值

  • 括号: 遇左括号进栈, 遇到右括号, 让栈顶的左括号出栈
  • 步骤:
    • 将中缀表达式转化为后缀表达式(栈用来进出运算的符号)
    • 将后缀表达式进行运算得出结果(栈用来进出运算的数字)

队列

  • 定义: 只允许在一端进行插入操作(队尾), 而在另一端进行删除操作(队头)的线性表;
  • 特点: 先进先出(FIFO)

抽象数据结构 

ADT 队列(Queue)
Data
	同线性表, 元素具有相同的类型, 相邻元素具有前驱和后继关系
Operation
	InitQueue(*Q): 初始化操作, 建立一个空队列Q
	DestroyQueue(*Q): 若队列存在, 则销毁它
	ClearStack(*Q): 将队列清空
	QueueEmpty(Q): 若队列为空, 则返回true, 否则返回false
	GetHead(Q,*e): 若队列存在且非空, 用e返回队列Q的队头元素
	EnQueue(*Q,e): 若队列存在, 插入新元素e到队列Q中并成为队尾元素
	DeQueue(*Q,e): 删除队列中队头的元素, 并用e返回其值
	QueueLength(Q): 返回队列Q的元素个数
end ADT

队列顺序存储: P113

  • 引入两个指针: front指向队头, rear指向队尾的下一个位置, 两者相等为空队列
  • 缺陷: 产生’假溢出’, 为了避免数组的插入和删除需要移动数据, 引入循环队列

循环队列: P114

  • 定义: 头尾相接的顺序存储结构
  • 队列满的条件: 设队列的最大尺寸为QueueSize, 队列满时保留一个空位
    • (rear + 1) % QueueSize = front
  • 队列长度计算: (rear - front + QueueSize) % QueueSize

队列链式存储(链队列): P117

  • 线性表中的单链表, 只能尾进头出
  • 头指针指向链队列的头结点, 队尾指向终端结点
    • 空队列front和rear都指向头结点

使用场景

  • 确定队列长度最大值的情况下, 使用循环队列
  • 无法预估队列的长度时, 使用链队列