C++ “链链“不忘@必有回响之单链表

typedef int dataType;
//结点
struct LinkNode{
	//数据成员 
	dataType  data;
	//后驱结点的地址
	LinkNode *next;
    //构造函数
	LinkNode(dataType data) {
		this->data=data;
		this->next=NULL;
	}
}; 
1
2
3
4
5
6
7
8
9
10
11
12
13

/*
* 链表类
*/
class LinkList {
	private:
		//头指针
		LinkNode *head;
		//链表的长度
		int length;
	public:
		//构造函数
		LinkList() {}
		//返回头指针
		LinkNode * getHead() {
			return this->head;
		}
		//初始化链表
		void  initLinkList() {}
		//按位置查询结点
		LinkNode * findNodeByIndex(int index) {}
		//从头创建链表
		void createFromHead(int n) {}
		//从尾建链表
		void createFromTail(int n) {}
		//按值查询结点
		LinkNode * findNodeByVal(dataType val) {}
		//后插入
		int instertAfter(dataType val,dataType data) {}
		//前插入
		int insertBefore(dataType val,dataType data) {}
		//按位置删除结点
		int delNode(dataType data) {}
		//删除所有结点
		void delAll() {}
		//显示所有
		void showSelf() {}
		//析构函数
		~LinkList() {
			this->delAll();
		}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

//初始化链表
void  initLinkList() {
	this->head=NULL;
}
1
2
3
4

//初始化链表
void  initLinkList() {
	this->head=new LinkNode(0);
}
1
2
3
4

//头部插入创建链表
void createFromHead(int n) {
	LinkNode *newNode,*p;
	p=this->head;
	for(int i=0; i>newNode->data;
		//原头结点为新结点的后驱结点 
		newNode->next=p;
		//新结点成为新的头结点 
		p=newNode;
		}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

LinkList list;
list.createFromHead(3);
LinkNode * head= list.getHead();
cout<<"输出结点信息"<data<next->data<next->next->data<

//从尾建链表
void createFromTail(int n) {
	LinkNode *newNode,*p,*tail;
	//头结点地址
	p=this->head;
	//尾结点地址
	tail=this->head;
	for(int i=0; i>newNode->data;
		if(p==NULL) {
			//如果头结点为 NULL
			p=tail=newNode;
		} else {
			//原来的尾结点成为新结点的前驱结点
			tail->next=newNode;
			//新结点成为新的尾结点
			tail=newNode;
				}
			}
			this->head=p;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

int main(){	
	LinkList list {};
	list.createFromTail(3);
	LinkNode * head= list.getHead();
	cout<<"输出结点信息"<data<next->data<next->next->data<

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12

执行后的结果：

前文说过，初始化链表时，可以指定一个空白头结点作为链表的头结点。其意义在哪里？

可以在尾部创建插入算法中使用或不使用空白头结点了解一下代码的差异性 。上述尾部创建插入算法中，因链表是不带空白结点的，所以在创建新结点时，必须有如下一段代码：

if(p==NULL) {
	//如果头结点为 NULL
	p=tail=newNode;
} 
1
2
3
4

因为刚开始时链表是空的，head和tail都是NULL，创建第一个新结点后，它即是头结点，也是尾结点，所以head和tail都需要指向此新结点。

后续再创建新结点后，head则不需修改，通用逻辑是：原来的尾结点成为新结点的前驱结点，新创建的结点成为新的尾结点。

如果在初始化链表时，已经指定了一个空白结点，则尾部创建插入算法中只需遵循通用逻辑便可。

//初始化链表时指定一个空白结点作为头结点
void  initLinkList() {
	this->head=new LinkNode(0);
}
1
2
3
4

尾部创建插入算法可修改为：

void createFromTail_(int n) {
	LinkNode *newNode,*p,*tail;
	//头结点地址
	p=this->head;
	//尾结点地址
	tail=p;
	for(int i=0; i>newNode->data;		
		//原来的尾结点成为新结点的前驱结点
		tail->next=newNode;
		//新结点成为新的尾结点
		tail=newNode;
		}
	this->head=p;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

初始链表时如果指定了空白头结点，就不需要考虑第一个结点的位置特殊性。

本文后续的算法都是基于带空白头结点的链表的操作。

2.3 查询链表

链表中的常用查询操作有 3 种方案：

• 按结点所在位置查找。
• 按结点的值查找。
• 查询链表中的所有结点。

2.3.1 按结点位置查找

设链表的头结点为编号为 0的结点，当给定编号 i 后，从头结点一至向后报数似的进行查找，至到找到与给定i值相同的结点 。

//按位置查询结点
LinkNode * findNodeByIndex(int index) {
	int j=0;
	LinkNode *p=this->head;
	if(index==j)
		//如果 index 值为 0 ，返回头结点
		return p;
	p=p->next;
	while( p!=NULL && jnext;
			j++;
	}
	if(j==index)return p;
	else return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.3.2 按结点的值查找

扫描链表中的每一个结点，比较那一个结点的值和给定的参数值相同。

//按值查询结点
LinkNode * findNodeByVal(dataType val) {
	//如果不带空白结点，则从头结点开始查找
	LinkeNode *p=this->head;
	whil(p!=null && p->data!=val ) {
		p=p->next;
	}
	if(p!=NULL) {
		return p;
	} else {
		return NULL;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

如果链表带有空白头结点，可以从头结点的后驱结点开始查找。

LinkeNode *p=this->head->next;
1

因为是按值比较，所以，无论链表是否带有空白头结点，都可以从头结点开始进行查找，对结果没有影响。

2.3.3 查询所有

不带空白头结点遍历操作：

//显示所有
void showSelf() {
    if(this->head==NULL)return;
	LinkNode *p=this->head;
	while(p!=NULL) {
		cout<data<<"\t";
		p=p->next;
	}
}
1
2
3
4
5
6
7
8
9

带空白头结点的遍历：

//显示所有
void showSelf() {
    if(this->head==NULL)return;
	LinkNode *p=this->head->next;
	while(p!=NULL) {
		cout<data<<"\t";
		p=p->next;
	}
}
1
2
3
4
5
6
7
8
9

2.4 插入

链表创建好后，后续维护过程，难免时时需要插入新的结点。插入时可以如前文在创建链表时一样，在头部插入和尾部插入。这里的插入指在链表的某个中间位置插入新结点。

• 后插入。
• 前插入。

2.4.1 后插入

所谓后插入，指新结点插入到某个已知结点的后面。如下图所示：

如果把值为 10 的新结点插入到值为 9的结点之后，称为后插入。后插入的通用逻辑：

• 查找到值为9的结点地址，称为 p结点。

• 创建新结点。

• 指定新结点n的后驱结点为p的后驱结点。

  n->next=p->next;
  1

• 指定p的后驱结点为新结点n。

  p->next=n;
  1

代码实现：

//后插入
int instertAfter(dataType val,dataType data) {
	//按值查找到结点 
	LinkNode *p=this->findNodeByVal(val);
	if (p==NULL){
		return false;
	}
	LinkNode *n=new LinkNode(0);
	n->data=data;
	n->next=p->next;
	p->next=n;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

测试后插入操作：

int main(int argc, char** argv) {
	LinkList list {};
	//创建值为 1 ，2 ，3 的 3 个结点
	list.createFromTail(3);
	//在值为 2 的结点后面插入一个值为5 的新结点
	list.instertAfter(2,5);
	//在链表中查看是否存在值为 5 的结点
	list.showSelf();
	return 0;
}
1
2
3
4
5
6
7
8
9
10

执行后输出结果：

2.4.2 前插入

所谓前插入，指新结点插入到某个已知结点的前面。如下图所示：

如果把新结点n插入到已知结点p的前面，则称为前插入。前插入的通用逻辑：

• 除了要查找到p结点在链表中的地址，还需要知道p结点的前驱结点p1的地址。

• 创建新结点，然后指定新结点n的后驱结点为p结点。

• 指定结点p1的后驱结点为新结点n。

代码实现：

/前插入
int insertBefore(dataType val,dataType data) {
	//按值查找到结点
	LinkNode *p=this->findNodeByVal(val);
	//查找前驱结点
	LinkNode *p1=this->head;
	while(p1->next!=p){
		p1=p1->next;
	} 
	//构建新结点
	LinkNode *n=new LinkeNode(0);
	n->data=data;
	//新结的点的后驱为 p 结点
	n->next=p;
	//重设 p1 的后驱为 n
	p1->next=n; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

测试前插入操作：

int main(int argc, char** argv) {
	LinkList list {};
	//创建值为 1 ，2 ，3 的 3 个结点
	list.createFromTail(3);
	//在值为 2 的结点前面插入一个值为5 的新结点
	list.insertBefore(2,5);
	//在链表中查看是否存在值为 5 的结点
	list.showSelf();
	return 0;
}
1
2
3
4
5
6
7
8
9
10

执行后输出结果：

如果仅仅是关心数据在链表中的逻辑关系，则可以先把新结点n插入到结点p的后面，然后交换 2 个结点中的数据。

2.5 删除

删除算法包括：

• 删除某一个结点。
• 删除所有结点，也称为清空链表。

2.5.1 删除结点

删除结点的基本思路：

• 在链表中查找到要删除的结点p。

• 找到p结点的前驱结点p1。

• 指定 p1的后驱结点为 p的后驱结点。

  p1->next=p->next;
  1

编码实现：

//按值删除结点
int delNode(dataType data) {
    //按值查找到要删除的结点
    LinkNode *p= this->findNodeByVal(data);
    if (p==NULL)return false;
    //查找前驱结点
    LinkNode *p1=this->head;
    while(p1->next!=p)p1=p1->next;
    //删除操作
    p1->next=p->next;
    p->next=NULL;
    delete p;
    return true; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

测试删除操作：

int main(int argc, char** argv) {
	LinkList list {};
	//创建值为 1 ，2 ，3 的 3 个结点
	list.createFromTail(3);
	//删除值为 2 的结点 
    list.delNode(2);
	list.showSelf();
	return 0;
}
1
2
3
4
5
6
7
8
9

输出结果：

2.5.2 清空链表

清空链表指删除所有结点。从头结点开始扫描，找到一个删除一个，真到没有结点为止。

void delAll() {
	LinkNode *p=this->head;
	//临时结点
	LinkNode *p1;
	while(p!=NULL) {
		//保留删除结点的后驱结点
		q=p->next;
		delete p;
		p=q;
	}
		this->head=NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12

测试：

int main(int argc, char** argv) {
	LinkList list {};
	//创建值为 1 ，2 ，3 的 3 个结点
	list.createFromTail(3);
	//没删除之前
	cout<<"清除之前:"<