第
3
章
线性表
..3.1线性表概述
数据之间存在各种关系,其中存在一种简单的“前后相继”的关系,即A数据
是
B
数据的前驱,
B
数据是
A
数据的后继。如果每个数据都有唯一的前驱元素和
唯一的后继元素,那么就称为线性存储结构,即线性表。
其中,第一个数据元素无前驱,最后一个数据元素无后继。数据元素之间的
关系是“一对一”的,适合存储在线性表中。线性表是一种简单、基本的数据结构,
应用场景较为广泛,可以用于存储和处理一组结构相同的数据元素,如一组学生
的考试成绩,也是后续章节中堆栈和队列的实现基础。
线性表有顺序和链表两种存储方式。顺序存储方式用数组实现,定义一个指
定长度的数组,将数据元素依次存储在数组中,使用数组下标可以访问到指定位
置的数据元素。链表存储方式创建一组带指针域和数据域的结构体,数据域中存
储数据元素,指针域中存储相邻数据元素的地址。
..3.线性表的定义及基本操作
2
一个线性表是
n
个具有相同特性的数据元素的有限序列。数据元素可以是
简单数据类型,也可以是结构体、对象、指针、字符串等其他数据类型。但在同一
个线性表中,数据类型必须统一。在线性表中,出现在
A
数据前面的数据元素称
为
A
的“前驱元素”;出现在
A
的后面的元素称为
A
的“后继元素”。在线性表中,
A
的前驱元素中最接近
A
的数据元素称为“直接前驱”;
A
的后继元素中最接近
A
的数据元素称为“直接后继”。
线性表的基本操作如下。
创建空表:创建一个线性表,数据元素个数初始化为0。
插入:确定插入的位置,在线性表中插入一个元素,元素个数加1。
删除:找到要删除元素的位置,删除元素,元素个数减1。
查找:给出元素的值,返回元素在线性表中的位置,如果元素不存在则返
回空。
第3章 线性表 41
.. 3.3 线性表存储结构
线性表有两种存储结构,顺序存储结构将数据存储于连续的物理空间,通过下标确定数
据的位置;链式存储结构将数据存储于不连续的物理空间,通过指针确定后继数据的位置。
3.3.1 线性表的顺序存储结构
顺序存储结构用数组的形式实现。在C++中,定义一个数组的时候,系统为数组分配
了一个连续的物理空间。数组的名就是数组存储在内存中的首地址。线性表的数据元素的
数据类型就是数组数据类型,各个数据元素的数据类型相同。
数组的长度即为数组中可以存储的数据元素的个数。数组元素的下标可以表示数据元
素在线性表中的位置。
顺序存储结构的优点有:创建简单,访问效率高,可以通过下标从任意位置开始访问线
性表,查找前驱元素和后继元素都很方便。
3.3.2 线性表的链表存储结构
顺序结构在使用方便的同时也存在限制:数组大小确定,不能动态增长;存储的内存需
要连续的空间,随着数据元素的增加,可能无法开辟出足够的连续内存空间。而链表结构可
以解决顺序结构的这些限制。链表结构在需要存储时再动态开辟一个结点空间,结点空间
由以下部分组成。
数据域:每个结点存储的数据元素本身的信息。
指针域:元素之间逻辑关系的信息,后继指针存储后继结点的地址,前驱指针(可选)存
储前驱结点的地址。通过指针域可以找到相邻结点的地址,提高数据查找速度。
一般来说,每个结点有一个或多个指针域,若某个结点不存在前驱或者后继,对应的指
针域设为空,用常量NULL表示。
链表存储结构可以用于实现堆栈和队列,处理大规模数据,实现动态扩展和收缩的数据
结构,还可以用于Hash表解决冲突。
链表有单向链表、双向链表、循环链表等形式。
.. 3.4 线性表的实现
3.4.1 单链表
单链表
结点只包含指向后继结点的指针,适用于基本上只做单向访问的线性表。链表结点可
以用结构体来描述如下。
//定义单链表结点
struct ListNode {
int val;
42 数据结构与问题求解(C++版·微课版)
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
其中,成员val用于存放结点中的有用数据,next是指针类型的成员,指向structListNode
类型数据,构建结点时可将指针域的默认值设为空。
链表头有两种设置模式:头结点模式和头指针模式。头结点模式中,head是一个结点,
next域存储第一个结点的地址;头指针模式中,head是一个指针,存储第一个结点的地址,
如图3.1所示。
图3.1 头结点和头指针模式下的单链表
虽然直接在栈区创建结构体变量可以用于创建链表,但是不能体现链表动态改变长度
的优势,因此往往使用动态内存分配,将结点建立在堆区。下面使用动态内存分配创建一个
学生成绩链表,学生的信息包含学号和成绩,并在链表中加入4个学生的数据。
1.链表类的创建
首先创建链表结点结构体,设置一个头指针head指向链表的第一个元素。
struct Student {
int id; //学号
float score; //成绩
Student* next; //指向下一个结点的指针
};
/*学生链表类*/
class LinkedList {
private:
Student* head; //指向链表的头指针
2.构造函数与析构函数
构造函数创建一个空的链表,此时链表中无结点,head指针的值为空。析构函数需要
清空链表,将堆区所占用的空间进行释放。head指针所指的数据不能直接释放,否则链表
后继数据将无法找到,需要借助一个temp指针指向head指针所指的第一个元素,head指
针再进行后移,释放掉temp指针所指的数据元素,循环进行,直至所有数据都被释放。
public:
LinkedList() {
head =NULL;
}
~LinkedList() {
Student* temp;
第3章 线性表 43
while(head !=NULL) {
temp =head;
head =head->next;
delete temp;
}
}
3.头插法插入结点
使用头插法插入一个学生结点。首先创建一个新的学生结点,然后将学号和成绩赋给
结点数据域,结点指针域赋为head,即第一个元素的地址,最后将head指针指向新结点。
void add(int id, float score) {
Student* newNode =new Student();
newNode->id =id;
newNode->score =score;
newNode->next =head;
head =newNode;
}
4.按序插入结点
按照给出的学号,找到适合的位置插入结点,使得学号按升序排列。首先生成新结点
newNode,然后使用访问指针p 从第一个元素开始进行比较,找到插入位置后终止循环,如
图3.2所示。
图3.2 按序插入结点
void insert(int id, float score)
{
Student* newNode =new Student();
newNode->id =id;
newNode->score =score;
newNode->next =NULL;
if(head ==NULL)
{
head =newNode;
}
else
{
Student* p =head;
//使用访问指针p 找到插入元素的位置
while(p->next !=NULL && p->next->id <newNode->id)
{
p =p->next;
44 数据结构与问题求解(C++版·微课版)
}
newNode->next =p->next;
p->next =newNode;
}
}
5.删除结点
删除结点首先要查找到指定结点,使用一个访问指针p 对链表进行遍历,比对结点的
id值进行查找。对结点进行删除后,要将前后的两个结点进行连接,因此需要借助一个前
驱指针prev来保存左侧结点的地址。如果删除的结点是第一个元素,那么在查找中p 指针
没有移动,prev指针的值为空,此时只需要将head指针指向第二个元素,再释放p 指针即
可。假设要删除的是学号为103的学生,如图3.3所示。
图3.3 删除一个结点
void remove(int id)
{
Student* p =head; //设置访问指针指向第一个元素
Student* prev =NULL; //设置前驱指针指向访问指针前一个元素
while(p !=NULL && p->id !=id) //查找id 对应的结点
{
prev =p;
p =p->next;
}
if(p ==NULL) //没有找到对应的学号
{
cout <<"Student not found." <<endl;
return;
}
if(prev ==NULL) //id 找到的是第一个元素
{
head =p->next;
}
else //其余的位置
{
prev->next =p->next;
}
delete p; //释放要删除的元素
}
第3章 线性表 45
3.4.2 双向链表
双向链表在每个结点中除包含数值域外,设置有两个指针域,分别用于指向其前驱结点
和后继结点,这样构成的链表称为线性双向链表,简称双链表。
在双链表中具有两个指针,所以当访问过一个结点后,既可以依次向后访问每个结点,
也可以依次向前访问每个结点,如图3.4所示。
图3.4 双向链表
双向链表可以设计一个头指针head指向第一个元素,一个尾指针tail指向最后一个元
素,创建双向链表时将头尾指针都赋为空。双向链表中增加了一个指针域,成员函数中要增
加相应的处理。
#include <iostream>
using namespace std;
struct Node //链表结点结构体
{
int data;
Node* prev; //前驱指针
Node* next; //后继指针
Node(int d) //初始化结点
{
data =d;
prev =NULL;
next =NULL;
}
};
class DoublyLinkedList //双向链表类
{p
ublic:
Node* head; //头指针
Node* tail; //尾指针
DoublyLinkedList()
{
head =NULL;
tail =NULL;
}
void append(int data) //尾插插入元素
{
Node* newNode =new Node(data);
if(head ==NULL)
{
head =newNode;
tail =newNode;
46 数据结构与问题求解(C++版·微课版)
}
else
{
tail->next =newNode;
newNode->prev =tail;
tail =newNode;
}
}
void prepend(int data) //头插插入元素
{
Node* newNode =new Node(data);
if(head ==NULL)
{
head =newNode;
tail =newNode;
}
else
{
head->prev =newNode;
newNode->next =head;
head =newNode;
}
}
void print() //打印双向链表
{
Node* p =head;
while(p !=NULL)
{
cout <<p->data <<" ";
p =p->next;
}
cout <<endl;
}
};
3.4.3 循环链表
循环链表形成环状结构,有head、tail两个固定指针,tail结点的next指针指向第一个
结点,在双向的循环链表中,head的prev指针指向最后一个结点,这样将链表连接为环状
结构。从表中任一结点出发均可找到链表中的其他结点。循环链表的结构如图3.5所示。
双向循环链表可以由头指针找到尾指针,类中也可以不设置tail指针。
循环链表形成的环状结构可以解决环状结构的问题,如约瑟夫环问题。
第3章线性表47
图3.5循环链表
..3.5能力拓展
3.5.1判断链表中是否存在环
判断链表中
是否存在环
给定一个单链表,其中可能存在某个结点的next指针指向前面已经出现过的结点,此
时链表中出现了环,如果使用访问指针直接进行遍历则无法达到链表的尾端。给出一个链
要求返回链表开始入环的第一个结点。从链表的头结点开始沿着nt指针进
表的头指针, ex
入环的第一个结点为环的入口结点。如果链表无环,则返回NULL 。
为了表示给定链表中的环,使用整数pos来表示链表尾连接到链表中的位置(索引从0
开始)。如果pos是-1,则在该链表中没有环。注意,pos仅用于标识环的情况,并不会作
为参数传递到函数中。不允许修改给定的链表。
如表3.
1所示为判断链表是否有环的示例。
表3.判断链表是否有环的示例
1
示例
1
示例
2
示例
3
head=[1,4,2,7,5],pos=1 head=[1,4,2,7,5],pos=0 head=[1,4,2,7,5],pos=-1
返回索引为1的链表结点返回索引为0的链表结点返回NULL
链表中有一个环,其尾部连接到
第2个结点
链表中有一个环,其尾部连接到
第1个结点
链表中不存在环
解题思路:
使用一个慢指针slow 和一个快指针fast判断链表中是否存在环。两个指针都从head
指针开始对链表进行访问,ow 指针每次移动一个结点,t指针每次移动两个结点。如
slfas
果链表不存在环,那么fas如图3.
t指针将先访问到NULL, 6所示
。
当链表存在圈时,t指针和sow 指针会相遇,设sow 指针走过的结点个数为s,
fasllfast
指针走过的结点个数是2s。设链表的圈外结点个数为Nout,圈内结点个数为Nin,圈内
48 数据结构与问题求解(C++版·微课版)
图3.6 使用快慢指针判断是否有环
slow指针走过的结点个数为Sv,如图3.7所示。
图3.7 快慢指针相遇时的情况
当快慢指针相遇时,慢指针走过的结点数目:
s=Nout+Sv (1)
快指针走过的结点数目(n 为快指针走过的圈数):
2s=Nout+n ×Nin+Sv (2)
由(1)(2)式联立得Nout=n×Nin-Sv,即圈外结点的数目Nout和从相遇点出发共绕
n 圈回到入圈点的距离相等。slow 指针此时停留在相遇点,因此只需要让slow 指针走
Nout步就能刚好回到圈的入口点。可以再设置一个指针p 从head出发进行访问,当p 和
slow相遇时,p 走过了Nout步,slow回到入口点,即求得圈的入口点。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode*next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode*detectCycle(ListNode*head) {
if(head==NULL||head->next==NULL)//特殊情况
return NULL;
ListNode* fast=head;
ListNode* slow=head;
do{
if(fast==NULL||fast->next==NULL)
return NULL;
第3章 线性表 49
fast=fast->next->next;
slow=slow->next;
}while(fast!=slow);
//退出循环时快慢指针相遇了
ListNode*p=head; //设置指针从head 出发
while(p!=slow) //p 和slow 将相遇在入圈点
{
p=p->next; //两指针移动
slow=slow->next;
}
return slow; //返回入圈点的地址
}
};
3.5.2 约瑟夫环
约瑟夫环问题:有num 只猴子,按顺时针方向围成一圈选大王(编号从1到num),从
第1号开始报数,一直数到target,数到target的猴子退出圈外,剩下的猴子再接着从1开
始报数。就这样,直到圈内只剩下一只猴子时,这个猴子就是猴王,编程求输入num 和
target后,输出最后猴王的编号。
解题思路:
约瑟夫环是学习算法的一个经典问题,可以使用数组、指针、链表和数学方法解决。我
们用循环链表模拟猴子报数的结构。每只猴子都看成一个结点,从1号到num 号依次加入
链表中。链表head指针指向1号,num 号猴子的next指针指向head,使得猴子能形成环状
结构,示例如图3.8所示。
图3.8 6只猴子进行报数,报到2出圈,最后剩下5号
用指针cur从表头开始对链表进行访问模拟报数的过程,每跳一个结点进行一次报数,报
到target-1时删除cur指针所指的下一个结点,最后只剩下一个结点时输出结点的编号。
struct Node
{
int val;
Node* next;
Node(int x) : val(x), next(nullptr) {}
};
50 数据结构与问题求解(C++版·微课版)
int josephus(int num, int target)
{
//创建循环链表
Node* head =new Node(1);
Node* cur =head;
for(int i =2; i <=num; i++)
{
cur->next =new Node(i);
cur =cur->next;
}
cur->next =head; //形成循环
//当圈内个数大于1 时
while(num >1)
{
//进行报数
for(int i =1; i <target; i++)
{
cur =cur->next;
}
//删除结点
Node* tmp =cur->next;
cur->next =tmp->next;
delete tmp;
num--; //圈内数目减1
}
//返回最后剩下的结点编号
return cur->val;
}
.. 习 题
1.有带有字母A、B、C的三张卡片,按某种顺序排列在一排。最多可以进行一次操作,
选择两张牌并交换它们。是否操作后可以变成ABC? 是就输出“YES”,否就输出“NO”。
输入格式:第一行包含一个整数t(1≤t≤10),代表有t 组数据。接下来n 行,每行包
括一个长度为3的字符串,由A、B、C三个字符组成。
输出格式:“YES”或者“NO”。
2.小S有一个数组,他想检查这个数组是否是一个排列。一个长度为n 的排列指的
是,1-n 在这个排列中都出现且仅出现过一次。
输入格式:第一行输入一个整数n。第二行输入n 个整数,表示数组元素。
输出格式:“YES”或者“NO”。
3.众所周知,小S十分挑食。这天,小S又来到了食堂,但他的挑食症又犯了,他不会
选择热量为k 的食物,请问他有多少种选择?
输入格式:第一行输入一个整数t,代表有多少组数据。第二行输入两个整数n 和k,n
代表有多少个食物,不同食物的热量可能相同。第三行输入n 个整数ai,ai 表示每个食物
的热量。(1≤t≤104,1≤n≤103,1≤ai,k≤109。)
第3章线性表51
输出格式:他有多少种选择,每组数据输出一个整数占一行。
4.给定两个大小分别为m和n的数组a和b。请找出并输出这两个数组的中位数。
输入格式:第一行输入两个整数n和m。第二行输入n个整数,表示数组a。第三行
输入m个整数,表示数组b。
输出格式:请输出一个浮点数,保留一位小数。
5.森林里有n只猴子,它们都想当猴王,因为当猴王就不用自己找果子吃。但不是每
只猴子都能当猴王,能当上猴王的只能有一只,于是便有了这样的规则:n只猴子围成一个
圈,从第1只猴子开始报数1,2,3,…报出m的那只猴子出列,失去继续争夺猴王的机会,由
下一只猴子继续从1开始报数,最终只剩下一只猴子得胜成为猴王。
输入格式:输入两个整数n和m。
输出格式:输出一个整数———第几只猴子获胜成为猴王。
6. 小S最近在学习后缀表达式,他已经把后缀表达式练得炉火纯青了,这一天他又看
到了一道后缀表达式的题,他觉得太简单了,于是交给了你。后缀表达式,指的是不包含括
号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行
(不再考虑运算符的优先规则) 。将给出一个后缀表达式T,保证T的长度不超过100,且操
作数仅为0~9的整数,操作符只包含+、-、*,求该后缀表达式的计算结果。
输入格式:本题的输入为单个测试用例,输入长度不超过100,且操作数仅为0~9的整
数,操作符只包含+、-、*等算术运算符的中缀表达式。
输出格式:输出一个整数,为该后缀表达式的计算结果。
7. 斯拉夫正在为朋友的生日准备礼物,礼物是
n
个数字的乘积。斯拉夫有一次机会选
择
n
个数字中的一个数字来增加1。请问斯拉夫可以送给朋友的最大礼物数是多少?
输入格式:第一行包含一个整数t(1≤t≤104)测试用例的数量。每个测试用例的第一
行包含一个整数n(1≤n≤9 )。每个测试用例的第二行包含
n
个空格分隔的整数ai
(0≤
ai≤9 )。
输出格式:对于每个测试用例,输出一个整数。
j!
8.给你一个整数数组a, i],j],k], =i!
j]
判断是否存在三元组a[a[a[满足i! j,=
k,
k=
]
k
=
并且a[=a[a[=a[a[=a[同时还满足a[
i]! j],i]! k],j]! k], i]+a[
+a[0。请统计三元组的数量。
输入格式:第一行输入一个整数n,数组
a
的长度。第二行输入
n
个整数。
输出格式:输出一个整数,为三元组的数量。
9.给定
n
个整数a1,a求问有多少个四元组(j,l)
a2,…,
n
, i,k,满足以下条件:1≤i<
j
<k<l≤n,ai=aj
=。
ak
,al
输入格式:第一行输入一个整数t,表示数据组数。对于每组数据,下一行输入一个整
数n,表示有多少个数。对于每组数据, 表示a1,an
。
下一行输入
n
个整数, a2,…
,
输出格式:每组输出一个整数,为四元组的数量
。
10.小李在玩一个游戏,他有
n
个盒子,每个盒子有两个数字,小李自己也有两个数字。
每个盒子可以得到的分数,是排在这个盒子前面的所有盒子的第一个数的乘积,除以这个盒
52数据结构与问题求解(C++版·微课版)
子的第二个数,然后向下取整得到的结果。小李不希望某一个盒子得到特别多的分数,所以
他想请你帮他重新安排一下盒子的顺序,使得得到分数最多的盒子,所获分数尽可能的少。
注意,小李的位置始终在盒子队列的最前面。
输入格式:第一行包含一个整数n,表示盒子的数量。第二行包含两个整数a和b,之
间用一个空格隔开,分别表示小李的两个数。接下来n行,每行包含两个整数a和b,之间
用一个空格隔开,分别表示每个盒子的两个数。
输出格式:一个整数,表示重新排列后的盒子队列中获分数最多的盒子所获得的分数。