数据结构【第二篇】线性表之链表的实现与讲解
如何弥补顺序表的不足之处？
第一次学习线性表一定会马上接触到一种叫做顺序表（顺序存储结构），经过上一篇的分析顺序表的优缺点是很显然的，它虽然能够很快的访问读取元素，但是在解决如插入和删除等操作的时候，却需要移动大量的元素，效率较低，那么是否有一种方法可以改善或者解决这个问题呢？
首先我们需要考虑，为什么顺序表中的插入删除操作会涉及到元素的移动呢？
好家伙，问题就是围绕着顺序表的最大的特点出现的——顺序存储，相邻放置元素，也就是说每个元素都是根据编号一个一个挨着的，这就导致了 插入或删除后，为了仍然呈顺序线性存储，被操作元素后面的元素的位置均需要发生一定的变化，你应该能想象得到，在拥挤的队伍中突然从中插入一个学生的场景，后面浩浩荡荡的人群，口吐芬芳的向后挪了一个空位，如果人群过大，重新排好队也需要一定的时间
好嘛，人与人之间别这么挤在一起，每个人与人之间都流出一点空隙来，留一定的位置出来，好了，这好像是个办法，但是负责一个一个与学生交流填表的老师可就不干了，这意味着我（找人）遍历的时候，需要多跑好多路，浪费好多时间，先不说这个，体院馆又不行了，你们这么个摆法，我这小馆可放不下，这也就意味着空间复杂度增加了很多
我们刚才所围绕的都是在 "排队" 的基本前提下的，但我们能想到的方法并不是很理想，那么我们索性就不排队了，是不是能有更好的解决方式呢？
一个有效的方法：
让同学们（元素）自己找位置随便站，不过你要知道相对于自己下一位同学的位置，这样既解决了空间上的问题，又能通过这种两两联系的方式访问（遍历）到整个队伍（数组），最重要的是，插入和离开同学，由于同学（元素）之间不存在了那种排队，相邻的特点，所以也不会说影响到过多的同学（元素）只需要和你插入位置的前后两位同学沟通好就行了，反正别人也不知道你们之间发生了什么事
好了思路是有了，我们来看一种最常见的链表——单链表
单链表的基本结构
这种链表为什么被称作单链表呢？这是因为它只含有一个地址域，这是什么意思呢？
我们在链表中摈弃了顺序表中那种一板一眼的排队方式，但是我们必须让两个应该相邻的元素之间有一定的相互关系，所以我们选择让每一个元素可以联系对应的下一个元素
而这个时候我们就需要给每个元素安排一个额外的位置，来存储它的后继元素的存储地址，这个存储元素信息的域叫做指针域或地址域，指针域中储存的信息也叫作指针或者链，
我们用一张图 看一下他的结构
结构中名词解释
- 头指针：一个指向第一个节点地址的指针变量
- 头指针具有标识单链表的作用，所以经常用头指针代表单链表的名字
- 头结点：在单链表的第一个结点之前附设一个结点，它没有直接前驱，称之为头结点
- 可不存信息，也可以作为监视哨，或用于存放线性表的长度等附加信息
- 指针域中存放首元结点的地址
- 首元结点：存储第一个元素的节点
为什么要附设一个头结点
我们来解释一下：
- 链表如果为空的情况下，如果单链表没有头结点，那么头指针就会指向NULL，如果加上头结点，无论单链表是否为空，头指针都会指向头结点，这样使得空链表与非空链表处理一致
- 使首元结点前插入或删除元素的时候，与后面操作相同，不需要产生额外的判断分支，使得算法更加简单
（以插入为例讲解）在带头结点的情况下，在首元结点前插入或者删除元素仍与在其他位置的操作相同，只需要将前一个元素（在这里是头结点）的指针域指向插入元素，同时将插入元素的指针域指向原来的第二的元素
而无头结点的情况由于，首元结点前没有元素，只能通过修改head的前后关系，所以导致了 与在别的位置插入或删除元素的操作不同，在实现这两个功能的时候就需要额外的写一个判断语句来判断插入的位置是不是首元结点之前的位置，增加了分支，代码不够简洁
总结：头结点的存在使得空链表与非空链表处理一致，也方便对链表首元结点前结点的插入或删除操作
单链表的类型定义
线性表的抽象数据类型定义
我们在给出单链表的定义之前我们还是需要先引入我们线性表的抽象数据类型定义
#ifndef _LIST_H_
#define _LIST_H_
#include<iostream>
using namespace std;
class outOfRange{};
class badSize{};
template<class T>
class List {
public:
// 清空线性表
virtual void clear()=0;
// 判空，表空返回true，非空返回false
virtual bool empty()const=0;
// 求线性表的长度
virtual int size()const=0;
// 在线性表中，位序为i[0..n]的位置插入元素value
virtual void insert(int i,const T &value)=0;
// 在线性表中，位序为i[0..n-1]的位置删除元素
virtual void remove(int i)=0;
// 在线性表中，查找值为value的元素第一次出现的位序
virtual int search(const T&value)const=0;
// 在线性表中，查找位序为i的元素并返回其值
virtual T visit(int i)const=0;
// 遍历线性表
virtual void traverse()const=0;
// 逆置线性表
virtual void inverse()=0;
virtual ~List(){};
};
/*自定义异常处理类*/
class outOfRange :public exception { //用于检查范围的有效性
public:
const char* what() const throw() {
return "ERROR! OUT OF RANGE.\n";
}
};
class badSize :public exception { //用于检查长度的有效性
public:
const char* what() const throw() {
return "ERROR! BAD SIZE.\n";
}
};
#endif单链表的类型定义
#ifndef _SEQLIST_H_
#define _SEQLIST_H_
#include "List.h"
#include<iostream>
using namespace std;
template<class elemType>
//elemType为单链表存储元素类型
class linkList:public List<elemType> {
private:
//节点类型定义
struct Node {
//节点的数据域
elemType data;
//节点的指针域
Node *next;
//两个构造函数
Node(const elemType value, Node *p = NULL) {
data = value;
next = p;
}
Node(Node *p = NULL) {
next = p;
}
};
//单链表的头指针
Node *head;
//单链表的尾指针
Node *tail;
//单链表的当前长度
int curLength;
//返回指向位序为i的节点的指针
Node *getPostion(int i)const;
public:
linkList();
~linkList();
//清空单链表，使其成为空表
void clear();
//带头结点的单链表，判空
bool empty()const {return head -> next == NULL;}
//返回单链表的当前实际长度
int size()const {return curLength;}
//在位序i处插入值为value的节点表长增1
void insert(int i, const elemType &value);
//删除位序为i处的节点，表长减1
int search(const elemType&value)const;
//查找值为value的节点的前驱的位序
int prior(const elemType&value)const;
//访问位序为i的节点的值，0定位到首元结点
elemType visit(int i)const;
//遍历单链表
void traverse()const;
//头插法创建单链表
void headCreate();
//尾插法创建单链表
void tailCreate();
//逆置单链表
void inverse();
};单链表上的基本运算实现
(一) 单链表的初始化-构造函数
单链表的初始化就是创建一个带头节点的空链表，我们不需要设置其指针域，为空即可
template<class elemType>
linkList<elemType>::linkList() {
head = tail = new Node();
curLength=0;
}注意：new 操作符代表申请堆内存空间，上述代码中应该判断是否申请成功，为简单，默认为申请成功，实际上如果系统没有足够的内存可供使用，那么在申请内存的时候会报出一个 bad_alloc exception 异常
(二) 析构函数
当单链表对象脱离其作用域时，系统自动执行析构函数来释放单链表空间，其实也就是清空单链表内容，同时释放头结点
template<class elemType>
linkList<elemType>::~linkList() {
clear();
delete head;
}(三) 清空单链表
清空单链表的主要思想就是从头结点开始逐步将后面节点释放掉，但是我们又不想轻易的修改头指针head的指向，所以我们引入一个工作指针，从头结点一直移动到表尾，逐步释放节点
template<class elemType>
void linkList<elemType>::clear() {
Node *p, *tmp;
p - head -> next;
while(p != NULL) {
tmp = p;
p = p -> next();
delete tmp;
}
head -> next = NULL;
tail = head;
curLength = 0;
}(四) 求表长
由于我们的代码中已经定义过一个叫做 curLength 的变量用来记录我们的表长
所以我们可以直接返回，我们在定义中已经实现了，也就是这句
//返回单链表的当前实际长度
int size()const {return curLength;}但是如果我们没有这样一个变量，我们想要实现这样的功能又是什么样的方法呢？
template<class elemType>
int linkList<elemType>::size()const {
Node *p = head -> next;
int count;
while(p) {count++; p = p -> next;}
return count;
}(五) 遍历单链表
我们需要从头到尾访问单链表中的每一个节点，并且输出其中数据域的信息
template<class elemType>
void linkList<elemType>::traverse()const {
Node *p = head -> next;
cout << "traverse:";
while (p != NULL) {
cout << p -> date << " ";
p = p -> next;
}
}(六) 按照位序 i 寻找其元素对应内存地址
设置一个移动工作指针，和一个计数器 count，初始时p指向头结点，每当指针p移向下一个结点的时候，计数器count + 1 ，直到 p指向位序为 i的节点为止。返回 p
template<class elemType>
typename linkList<elemType>::Node *linkList<elemType>::getPostion(int i)const {
if(i < -1 || i > curLength - 1)
return NULL;
Node *p = head;
int count = 0;
while(count <= i) {
p = p -> next;
count++;
}
return p;
}(七) 按值查询节点位序
设置一个移动工作指针，和一个计数器 count，从单链表的第一个节点开始，开始于给定的值进行比对，如果相等则查找成功，返回节点的位序，否则继续查询知道单链表结束，查询失败返回 -1
template<class elemType>
int linkList<elemType>::search(const elemType&value)const {
Node *p = head -> next;
int count = 0;
while (p != NULL && p -> data != value) {
p = p -> next;
count++;
}
if (p == NULL) {
return -1;
}else {
return count;
}
}(八) 插入节点
在位序为 i 出插入值为value 的新节点q，我们需要做的就是找到位序为i - 1 的节点p，让q指针域指向原来p的后继，然后修改p的后继为q即可，说白了也就是修改插入元素位置前后的元素指向关系就可以了
template<class elemType>
void linkList<elemType>::insert(int i,const elemType &value) {
Node *p, *q;
if(i < 0 || i > curLength)
throw outOfRange();
p = getPostion(i - 1);
q = new Node(value,p -> next);
p -> next = q;
if (p == tail) tail = q;
curLength++;
}(九) 删除节点
能看懂添加节点的方法，理解删除节点也是手到擒来
template<class elemType>
void linkList<elemType>::remove(int i) {
//p是待删节点，pre是其前驱
Node *p, *pre;
if(i < 0 || i > curLength)
throw outOfRange();
pre = getPostion(i - 1);
p = pre -> next;
if (p == tail) {
tail = pre;
pre -> next = NULL;
delete p;
} else {
pre -> next = p -> next;
delete p;
}
}单链表整表的创建
回顾我们前面认识的顺序表，它其实可以理解为一个数组，我们声明一个类型，同时给定值，初始化其大小，但是单链表就不一样了，它是一种动态组织，它不需要像顺序表一样元素集中，它可以随着实际的情况来动态生成节点，所以也不需要预先分配空间大小和位置
(一) 头插法创建单链表
头插法的意思就是说，每次新增节点全部插在头结点之后，首元结点之前，你可以这样理解，我先来排队，但是后面来了人，他就会排到我的前面去，我们来借助图看一下
我们一次插入元素 123 但实际上输出的是按照321的顺序存储的，也就是说和我们的逻辑顺序是相反的
我们来看一看怎么实现它
template<class elemType>
void linkList<elemType>::headCreate() {
Node *p;
elemType value, flag;
cout << "inputelements, ended with:";
cin >> flag;
while(cin >> value, value != flag) {
//p -> data == value, p -> next = head ->next
p = new Node(value, head -> next);
head -> next = p;
//原链表为空，新节点p成为为节点
if (head == tail)
tail = p;
curLength++;
}
}逆置单链表
我们知道单链表中元素顺序与读入的顺序是相反的，我们可以通过逆置单链表的算法，帮助我们重新恢复我们的惯有思维顺序
template<class elemType>
void linkList<elemType>::inverse() {
Node *p, *tmp;
//p为工作指针，指向首元结点
p = head -> next;
//头结点的指针域置空，构成空链表
head -> next = NULL;
//逆置后首元结点将成为尾节点
if (p)
tail = p;
while (p) {
//暂存p的后继
tmp = p -> next;
p -> next = head -> next;
//节点p插在头结点的后面
head -> next = p;
//继续处理下一个节点
p = tmp;
}
}(二) 尾插法创建单链表
看完了头插法，但是感觉这样的顺序与我们一贯的思维总是有一点别扭，而尾插法则是一种，逻辑顺序与我们一致的创建方法
还是看一下图
template<class elemType>
void linkList<elemType>::tailCreate() {
Node *p;
elemType value, flag;
cout << "inputelements, ended with:";
cin >> flag;
while(cin >> value, value != flag) {
p = new Node(value,NULL);
tail -> next = p;
tail = p;
curLength++;
}
}合并单链表
要求：假设我们给出两个仍然是递增的单链表la和lb，我们将其合并为lc 仍保证递增，利用原表空间，但是我们仍在下面将表C称作新表
因为我们的要求是递增的，所以使用尾插法是非常合适的，我们设计三个工作指针，分别指向两个表的首元结点，然后将第三个指针指向新表的头结点，比较前两个指针指向的值，小的就放到新表的表尾，然后后移动两表中较小的那一个的指针，以此类推，直到其中一个表尾空，将剩余的节点全部链接到新表的末尾
template<class elemType>
typename linkList<elemType> *linkList<elemType> ::Union(linkList<elemType> *lb) {
Node *pa, *pb, *pc;
linkList<elemType> *lc = this;
pa = head -> next;
head -> next = NULL;
pb = (lb -> head) -> next;
(lb -> head) -> next = NULL;
pc = lc -> head;
while(pa && pb) {
if(pa -> data <= pb -> data) {
pc-> next = pa;
pc = pa;
pa = pa -> next;
} else {
pc -> next = pb;
pc = pb;
pb = pb -> next;
}
}
if(pa) {
pc -> next = pa;
lc -> tail = tail;
} else {
pc -> next = pb;
lc -> tail = lb -> tail;
}
lc -> cuirLength = curLength + lb -> curLength;
delete lb;
return lc;
}总结
单链表，采取了链式存储结构，用一组任意的存储单元存放线性表的元素，尤其对于需要频繁的插入和删除数据的时候更加适用，如果需要进行频繁的查找还是推荐使用顺序表，例如对于一个学生成绩管理系统的制作，学生更多的时候是查看自己的成绩，而录入的老师，也只有在考试后录入一次，所以应该使用顺序表，而例如考勤打卡系统，更多的是打卡信息的记录，所以还是选择使用链表，当然例子可能不是很恰当，同时正常的开发中还会有更多复杂的问题需要考虑，举例子只为了利于理解