数据结构-线性表

线性表的定义

零个或多个数据元素的有限序列

线性表的顺序存储结构

顺序存储定义

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

顺序存储方式

一维数组来实现顺序存储结构。

数据长度与线性表长度的区别

线性表的长度应该小于等于数组的长度。

地址计算方法

存储器中的每个存储单元都有自己的编号，这个编号称为地址。

顺序存储结构的插入与删除

获得元素操作

返回数组下标对应的值即可。

插入操作

插入算法的思路：

  1. 如果插入位置不合适，抛出异常

  2. 如果线性表长度大于等于数组长度，则抛出异常或动态增加容量。

  3. 从最后一个元素开始向前遍历到第i个位置，分别将它们都往后移动一个位置。

  4. 将要插入元素填入第i个位置

  5. 表长加1

删除操作

删除算法的思路：

  1. 如果删除位置不合理，抛出异常。

  2. 取出删除元素。

  3. 从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置。

  4. 表长减1

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

  • 优点

  1. 无需为表示表中元素之间的逻辑关系而增加额外的存储空间

  2. 可以快速地存取表中任意位置的元素

  • 缺点

  1. 插入和删除操作需要移动大量元素

  2. 当线性表长度变化较大时，难以确定存储空间的容量

  3. 造成存储空间的"碎片"

线性表的链式存储结构

顺序存储结构不足的解决办法

主要解决插入和删除时需要移动大量元素。

不考虑顺序存储

线性表链式存储结构定义

n个结点(访问指针和数据元素组成的结点)链接成一个链表，即为线性表的链式存储结构。

链表中第一个结点的存储位置叫做头指针

在单链表的第一个结点前附设一个结点，称为头结点

头指针和头结点的异同

头指针

  • 指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针

  • 头指针具有标志作用，所以常用头指针冠以链表的名字

  • 无论链表是否为空，头指针均不为空，头指针是链表的必要元素

头结点

  • 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义(也可以存放链表的长度)

  • 有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其他结点的操作就统一了

  • 头结点不一定是链表必需要素

线性表链式存储结构代码描述

结点由存放数据元素的数据域和存放后继结点地址的指针域组成

单链表的读取

获得链表第i个数据的算法思路：

  1. 声明一个指针p指向链表第一个结点，初始化j从1开始

  2. 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1

  3. 若到链表末尾p为空，则说明第i个结点不存在

  4. 否则查找成功，返回结点p的数据

单链表的插入与删除

插入

第i 个数据插入结点的算法思路：

  1. 声明一个指针p指向链表头结点，初始化j从1开始

  2. 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1

  3. 若到链表末尾p为空，则说明第i个结点不存在

  4. 否则查找成功，在系统中生成一个空节点s

  5. 将数据元素e赋值给s的数据域

  6. 单链表的插入标准语句：将s的指针指向p的下一个结点，p的指针指向s

  7. 返回成功

删除

第i 个数据删除结点的算法思路：

  1. 声明一个指针p指向链表头结点，初始化j从1开始

  2. 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1

  3. 若到链表末尾p为空，则说明第i个结点不存在

  4. 否则查找成功，将欲删除的结点p.next 赋值给q

  5. 单链表的删除标准语句：p.next = q.next

  6. 将q结点中的数据赋值给e，作为返回

  7. 释放q结点

  8. 返回e结点

对于插入或者删除数据越频繁的操作，单链表的效率优势就越明显

单链表的整表创建

头插法

思路：

  1. 声明一指针p

  2. 初始化一空链表L

  3. 让L的头结点的指针指向NULL，即建立一个带头结点的单链表

  4. 循环：

  • 生成一新结点赋值给p

  • 将数据内容赋值给p的数据域p.data

  • 将p插入到头结点L与前一新结点之间

尾插法

思路：

  1. 声明一指针p 和r

  2. 初始化一空链表L

  3. 让L的头结点的指针指向NULL，即建立一个带头结点的单链表，r指向尾结点，此时为L的头结点

  4. 循环：

  • 生成一新结点赋值给p

  • 将数据内容赋值给p的数据域p.data

  • 将p插入到r结点之后

  • 更新r结点为p结点(更新尾结点操作)

单链表的整表删除

头插入对应删除思路：

  1. 声明一指针p 和q

  2. 将第一个结点赋值给p

  3. 循环：

  • 将下一结点赋值给q

  • 释放p

  • 将q赋值给p

单链表结构与顺序存储结构的优缺点

查询数据多且很少进行数据数量变化的操作则使用顺序结构

数据数量变化大或者不知道数量情况下，则使用单链表结构

静态链表

用数组描述的链表叫静态链表

数组元素的结构体可以理解为由数据域和下标域组成

实现了在不移动元素的情况下进行插入和删除操作

数组第一位的下标记录备用链表开始位置

数组最后一位下标记录链表第一节点的位置

主要为了解决给没有指针的高级语言设计的一种实现链表能力的方法

循环链表

首尾相连即可，一般使用尾指针

双向链表*

在单链表中的每一个结点中添加一个前指针域即可。

双向链表插入操作的顺序很重要：

  1. 插入结点s的前指针指向前结点pre

  2. 插入结点s的后指针指向后结点next

  3. 后结点next的前指针指向插入结点s

  4. 前结点pre的后指针指向插入结点s

第1、2步顺序容易理解，不影响原有链表查询

第3、4步顺序考虑到链表正向查询操作可能会更多，这样的顺序会更小地影响原链表的查询操作

双向链表删除操作的顺序可以参考上条结论：

  1. 前结点pre的后指针指向后结点next

  2. 后结点next的前指针指向前结点pre