二、数据结构-线性表

一、线性表概述

1.1 线性表的基本概念

线性表中结点具有一对一的关系，如果结点数不为零，则除起始结点没有直接前驱外，其他每个结点有且仅有一个直接前驱；除终端结点没有直接后继外，其他每个结点有且仅有一个直接后继。

• 线性表基本运算有：初始化、求表长、读表元素、定位、插入、删除。

1.2 线性表的顺序存储

线性表的顺序存储：逻辑结构相邻的结点其存储位置也相邻。用顺序存储实现的线性表称为顺序表，一般用数组来表示顺序表，如图1-1 所示

图1-1　顺序表示意图

1.2.1 线性表的基本运算在顺序表上的实现

1. 插入
   　　
   

图1-2 顺序表插入元素前、后状况示意图

• a）插入前
• b）插入前，移出空位之后
• c）插入x后

具体算法描述如下：

2. 删除

图2-5 顺序表删除元素前、后的状况示意图

• a）删除前
• b）删除后

具体算法描述如下：

3. 定位

定位运算的功能是查找出线性表L中值等于x的结点序号的最小值，当找不到值为x的结点时，返回结果0。

描述算法如下：

1.2.2 顺序表实现算法的分析

• 插入：O（n）
• 删除：O（n）
• 定位：O（n）
  2.3 线性表的链接存储

1.2.3 单链表类型的定义

线性表的链接存储是指它的存储结构是链式的。线性表常见的链式存储结构有单链表、循环链表和双向循环链表，其中最简单的是单链表。

单链表的一个结点由两部分组成：数据元素和指针。各个结点在内存中的存储位置并不一定连续。链表的结点可以重新链接。

图2-7 结点结构

非空的单链表和空单链表，如图所示：

图2-8 单链表示例

• a）非空的单链表
• b）空单链表

我们通常用结构体类型来定义单链表的结点数据类型。
单链表的类型定义如下：

Typedef　struct node
{DataType data; //数据域struct node * next; //指针域
}Node, *LinkList;

【例2-4】学生档案信息链表的类型完整描述如下：

则学生档案信息链式存储实现，如图2-9所示.

图2-9 　学生档案信息表链式存储实现示意图

为了便于运算的实现，在单链表的第一个结点之前增设一个类型相同的结点，称之为头结点，其他结点称为表结点。

图2-10 　带头结点的单链表

• a）带头结点的非空单链表
• b）带头结点的空单链表

1.2.4 线性表的基本运算在单链表上的实现

我们首先来讨论单链表的一些基本运算，这是使用单链表的开始。

1. 初始化
   　　初始化的工作是建立一个空表，空表由一个头指针和一个头结点组成。
2. 求表长
   　　在单链表存储结构中，线性表的表长等于单链表中数据元素的结点个数，即除了头结点以外的结点的个数，即除了头结点以外的结点的个数。图2-9所示为数据为整数的单链表，其长度为4.

3. 读表元素
   　　通常给定一个序号i，查找线性表的第i个元素。从头指针出发，一直往后移动，直到第i个结点。

4. 定位
   　　线性表的定位运算，就是对给定表元素的值，找出这个元素的位置。从头至尾访问链表，直至找到需要的结点，返回其序号。若未找到，返回0。
5. 插入（重点掌握）
   　　单链表的插入运算是将给定值为x的元素插入到链表head的第i个结点之前。 插入结点的指针变化

如图2-12所示。
　　图2-12 单链表上插入结点的指针变化

插入算法描述如下：

注意：p->next=q->next和q->next=p两条语句的执行顺序不能颠倒。

6. 删除（重点掌握）

删除运算是给定一个值i，将链表中第i个结点从链表中移出，并修改相关结点的指针域，以维持剩余结点的链接关系。删除结点的指针变化如图2-13所示。

图2-13 单链表上删除结点时的指针变化
　　单链表的删除运算算法描述如下：

7. 注意：free（p）是必不可少的，无用结点需要释放它的空间。

1.3 其他运算在单链表上的实现

1.3.1 建表

我们讨论建立含头结点的单链表。

方法一：尾插法，这个过程分为三部，首先建立带头结点的空表；其次建立一个新结点，然后将新结点链接到头结点之后；重复后面两个步骤，直到线性表中所有元素链接到单链表中。

代码描述如下：

方法中的链接操作如图2-14所示，它的时间与元素个数成正比，故其时间复杂度为O（n）。

图2-14 建表算法中的表尾链入操作

方法二：头插法，始终将新增加的结点插入到头结点之后，第一个数据结点之前。它的时间复杂度也是O（n）。如图2-15所示。

图 2-15 建表算法中的在表头链入操作

代码描述如下：

1.3.2 删除重复结点

1.4 其他链表

1.4.1 循环链表

在单链表中，如果让最后一个结点的指针域指向第一个结点可以构成循环链表。在循环链表中，从任一结点出发能够扫描整个链表。

图 2-15 循环链表示意图

• a）带头结点的非空循环链表
• b）带头结点的空循环链表
• c）设立尾指针的非空循环链表
• d）设立尾指针的空循环链表

1.4.2 双向循环链表

双向循环链表的结点结构 如图2-18所示：

图2-18　双向循环链表结点结构

双向循环链表示意图，如图2-19所示，prior与next类型相同，它指向直接前驱结点。头结点的prior指向最后一个结点，最后一个结点的next指向头结点。

图2-19 双向循环链表示意图

• a）空表
• b）非空表

1. 删除

在单链表中删除结点时，需要用一个指针指向待删除结点的前驱结点，在双循环链表中，设p指向待删除结点，删除*p可通过下述语句完成，执行效果如图2-18所示。

• （1）p->prior->next=p->next;
  　　//p前驱结点的后链指向p的后继结点
• （2）p->next->prior=p->prior;
  　　//p后继结点的前链指向p的前驱结点
• （3）free（p）; //释放*p的空间
  　　
  　　（1）、（2）这两个语句的执行顺序可以颠倒。

图 2-20 双向循环链表上结点的删除

• a）删除结点*p之前
• b）删除结点*p后

2. 插入
   　　在p所指结点的后面插入一个新结点*t，需要修改四个指针：

• （1）t->prior=p;
• （2）t->next=p->next;
• （3）p->next->prior=t;
• （4）p->next=t;

插入操作过程如图2-21所示，注意这些语句之间的顺序。

图 2-21 双向循环链表上结点的插入

• a）插入前
• b）插入后

1.5 顺序实现与链接实现的比较

二、典例练习

【例题：单选题】在表长为n的顺序表上做删除运算，其平均时间复杂度为（　）。
　　A.O（1）
　　B.O（n）
　　C.O（nlog2n）
　　D.O（n2）
『正确答案』B
『答案解析』在顺序表上做删除运算，需要后续结点向前移动一个位置以保证顺序表的连续。

【例题：单选题】在表长为n的顺序表上做插入运算，平均要移动的点数为（　）。
　　A.n/4
　　B.n/3
　　C.n/2
　　D.n
『正确答案』C
『答案解析』如果在顺序表的尾部插入，则移动0个结点，如果在顺序表的头部插入，则移动n个结点。

【例题：单选题】从一个长度为n的顺序表中删除第i个元素（1<=i<=n）时，需向前移动的元素个数为（　）。
　　A.n-i
　　B.n-i+1
　　C.n-i-1
　　D.i
『正确答案』A
『答案解析』删除第i个元素，则后面n-i个元素都要前移。

【例题：单选题】设单链表中指针p指向结点A，要删除A之后的结点（若存在），则修改指针的操作为（　）。
　　A.p->next=p->next->next
　　B.p=p->next
　　C.p=p->next->next
　　D.p->next=p
『正确答案』A
『答案解析』要删除A之后的结点，即将A的指针域指向A之后的结点的下一个结点。参见教材P47。

【例题：填空题】设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的语句序列是________; r=s; r->next=NULL。
『正确答案』r->next=s
『答案解析』在单链表中用尾插法插入一个结点，将尾结点的指针域指向待插结点，带插结点的指针域指向NULL。