C++ 语言学习入门--链表、队列与栈

目录


【PS】学校里也学到了,之前在信竞中也已经学过,此博客只当作个人的知识整理和备份。如果有错误的地方,请帮忙指出,谢谢!

本文引文基本出自Starting Out with C++ From Control Structures Through Objects 8th Global Edition

1. 链表(Linked List)

1.1 什么是链表?

A linked list is a series of connected nodes, where each node is a data structure. A linked list can grow or shrink in size as the program runs.

链表是一系列连接的节点,其中每个节点都是一个数据结构。和数组的功能相似,都是存储一系列同种数据类型的数据结构。

如下图,链表的每一个元素都是由一个自身的数据内容和(至少)一个指针构成的。这个指针至关重要,它承载着下一个(或上一个)元素的地址信息。这就好比自己家里有一个同学家的地址一样,只要依据这个地址,就可以找到同学家(下一个元素)的位置。这样子,一个“链”表就形成了。
C++ 语言学习入门--链表、队列与栈
当然,总得有个头啊。因此在这个链表得第一个人而言,要有一个指针专门指向第一个元素。对于新加进链表得最后一个元素而言,它是最后一个,没有下一个元素得地址,因此一般先指向自己(自己的指针指向自己)或者是一个空指针。
C++ 语言学习入门--链表、队列与栈
当然,很明显的可以看到,如果我要找到链表中的某一个元素,必须从头开始找,就跟藏宝图一样,找到一个新的宝藏和藏宝图,继续按新的藏宝图寻找下一个…

但是对于链表来说,每一个元素在物理内存中可以动态分配位置的,而不像数组一样,在物理内存中是以相邻的地址去分配的。

1.2 链表和数组(Array)、向量(Vector)的区别

虽然链表的结构会相比于数组复杂,但是链表最大的优势在于,它是可以在程序运行时大小可以随意变化,即用户想增加链表中的元素个数和减少元素个数都是可以的。而数组虽然大小可以由用户决定,一旦在程序中定义后则不可再更改大小。因此,通常说数组是“静态”(Static)的,而链表是“动态”的(Dynamic)。

称链表为动态的还有一个原因,是他比较好“维护”,也就是说,用户在链表中的某一处添加一个元素非常的容易。这也是它和向量的最大区别。虽然说链表可能没有比向量优越(指在STL中的代码),但是在动态的修改中依然占有较大的优势。如果向量中间要加入一个新元素,则这个位置后面的元素都要相应的往后位移。但是链表只需要将“链”(前一个元素的指针)链在自己身上即可添加新元素,维护起来非常的方便。相同的删除这个元素只需要把这个“链”(前一个元素的指针)从自身上卸下来,链到后面的元素即可直接将当前这个元素“删除”。

当然,数组相比于向量,向量也可以动态修改大小。数组是存储在栈中,而向量是存储在堆中,存储的位置不一致。但是数组的执行效率相比于向量会高不少。

1.3 使用链表

1.3.1 链表结构

相对简单的,我们直接可以用struct定义一个链表的结构(当然也可以使用class,使用struct是因为其结构相对比较简单,只有成员变量):

struct ListNode
{
    double value;    //链表中的数据元素(可以不同数据类型)
    ListNode *next;  //一个同类型的指针,用于指向下一个结构体的
};

这个看起来有点套娃,这个实际上是一种自引用数据结构(self-referential data structure),这可以让每个节点都去生成跟自己相同类型的数据结构。

当然,正如刚刚所说,总得有个头啊,因此再定义一个头指针:

ListNode *head; //当然最好初始化成空指针

1.3.2 封装一个自己的链表类

我们可以将这一整个封装成一个非常简单的类(单向链表),里面包含数据元素,相应的头指针,相应的成员函数:访问器,删、改、插入、添加等操作(像是自己写了一个库文件一样):

class NumberList
{
	private:
		struct Node                 //定义链表结构体
		{
			double value;           //要存储的数据
			struct ListNode *next;  //下一个链表元素的指针
		};
		Node *head;                 //头指针
	    int length;                 //链表长度
		
	public:
		NumberList() { head = nullptr; length = 0; }  //构造函数,将头指针置为空指针,链表长度初始化为0
		~NumberList();                    //解构函数
	 	void appendNode(double);          //在链表末尾添加一个节点
		void insertNode(double);          //在链表中间添加一个节点
		void deleteNode(double);          //删除一个节点
		void displayList() const;         //访问器,展示链表
};

1.3.3 在尾部添加节点(Append)

对于在链表尾部添加一个节点,原理不难理解,例如下图12.6要放到7.9后面。先设置一个nodePtr,指针从head给出,一个个向下索引至末尾节点(即所引到空指针),这时候nodePtr便指向7.9了,这时候只需要将7.9的指针指向12.6,即可完成添加节点
C++ 语言学习入门--链表、队列与栈

代码实现:

void NumberList::appendNode(double num)
{
	Node *newNode;        //新建一个指针->当前新要添加进来的节点
	Node *nodePtr;        //新建一个指针->用于搜寻末尾节点
	
	newNode = new Node;   //申请空间,将一个结构体实例化
	newNode->value = num;     //新节点的值是传入进来的值
	newNode->next = nullptr;  
	//新节点由于是当前链表尾部的节点,没有它指向的下一个点了,因此它自己的这个指针置为空指针
	
	if (!head)                //如果当前此链表还没有节点,将新加入节点置为头节点
	    head = newNode;
	else                      //如果已经有节点了,就要去寻找还未更新时的最后一个节点
	{
		nodePtr = head;       //先获得头节点的地址 
		
		while (nodePtr->next) //根据地址一个接一个的往下找,直到遇到空指针(说明到末尾了)
	        nodePtr = nodePtr->next;
	        
	    nodePtr->next = newNode; //把最后一个节点的指针指向现在新加入的节点
	}
	length++; //更新链表长度
}

1.3.4 在中间插入一个元素

插入的方法很容易理解,例如10.5要插入到7.9和12.6中间,只需要将7.9的指针指向10.5,然后将10.5的指针指向12.6即可完成插入。
C++ 语言学习入门--链表、队列与栈
这是链表的优势所在,代码实现可以这么写:

void NumberList::insertNode(double pos, double num)
{
	Node *newNode;                //新建一个指针->需要插入的节点
	Node *nodePtr;                //新建一个指针->用于遍历链表
	Node *previousNode = nullptr; //新建一个指针->用于存储上一个节点

	newNode = new Node;  //申请空间,将结构体实例化
	newNode->value = num;    //将值写入新节点中
	
	if (!head)  //如果没有节点,则默认这个为第一个节点,并说明
	{
		cout<<"No node in the list, considering as the first node"<<endl;
		head = newNode;
		head->next = nullptr;
	}
	else
	{
		if (pos == 0)  //如果直接在头部插入新节点
		{
			newNode->next = head; //将新节点的指针指向原来的头
			head = newNode;       //更新头指针为此新节点
		} 
		else
		{
			nodePtr = head;  //先给予头部指针

			while (nodePtr->next && cnt < pos)  //寻找到输入位置的节点
			{
				previousNode = nodePtr;   //持续更新前一个节点
				nodePtr = nodePtr->next;  //持续寻找下一个节点
				cnt++;                    //计数,链表的第几个
			}
		
			if (cnt < pos)  //如果没到设定位置,即说明链表长度太短,默认将节点设为链表的末尾
			{
				cout<<"Warning: Insert "<<pos<<": Number would be inserted to the end of the list."<<endl;
			newNode->next = nullptr;
			nodePtr->next = newNode;
			}
			else  //如果找到了,直接将节点插入previousNode和NodePtr之间
			{
				previousNode->next = newNode;
				newNode->next = nodePtr;
			}
		}
	length++; //更新链表长度
}

1.3.5 在中间删除一个元素

删除一个元素的方法也很简单,只需要将前一个节点的指针指向当前指针指向的节点,即可删除当前的节点。例如要将7.9从中间删除,只需要把2.5的指针指向12.6即可,这样7.9的地址就被丢失了,因此索引不到它,像是被“删除”了。
C++ 语言学习入门--链表、队列与栈
代码实现:

void NumberList::deleteNode(int pos) //给定链表中的位置进行删除
{
	int cnt = 0;   //计数,数链表的第几个节点
	Node *nodePtr; //设置新指针->用于遍历  
	Node *previousNode = nullptr; //设置新指针->用于实时更新遍历指针的前一个

	if (!head)  //如果链表还是空的,不能进行删除操作
	{
		cout<<"The list is empty!"<<endl;
		return;
	} 
	else
	{
		if (pos == 0)  //如果想将链表头部删除
		{
			nodePtr = head->next;
			delete head;
			head = nodePtr;
		}
		else
		{
			while(nodePtr != nullptr && cnt < pos)  //向下索引到相应位置
			{
				previousNode = nodePtr;
				nodePtr = nodePtr->next;
				cnt++;
			}
			
			if(cnt < pos) //如果索引到的小于输入的位置,则说明链表过短,默认删除链表最后一个节点
			{
				cout<<"Warning: Delete "<<pos<<": "<<"The end of the list would be deleted."<<endl;
				previousNode->next = nullptr;
				delete nodePtr;
			}
			else
			{
				previousNode->next = nodePtr->next;
			}
		}
	}
	length--; //更新链表长度
}

1.3.6 展示链表

之前的文章提到,类需要Accessor去访问链表里的值,因此,展示链表的成员函数是必须的。当然,这里只是把每个节点的值和链表的长度展示出来。

代码实现:

void NumberList::displayList() const
{
	Node *nodePtr;
	nodePtr = head; //从头部开始索引
	while (nodePtr)
	{
		cout<<nodePtr->value<<endl;  //每个节点都将值输出
		nodePtr = nodePtr->next;     //继续索引下一个节点
	}
	cout<<"Total number in the list: "<<length<<endl; //将链表长度展示
}

1.3.7 测试

将此类进行测试,测试代码:

int main()
{
	NumberList list;          //实例化一个链表类
	list.appendNode(5.6);     //末尾添加节点
	list.appendNode(7.2);
	list.insertNode(0,3.3);   //头部插入节点
	list.insertNode(0,5.6);
	list.insertNode(2,9.9);
	list.insertNode(6,12.38); //测试默认在尾部添加节点
	list.displayList();
	cout<<endl;
	list.deleteNode(0);       //删除头部节点
	list.deleteNode(2);       //删除中间节点
	list.deleteNode(8);       //测试默认在尾部删除节点
	list.displayList();
}

结果:

Warning: Insert 6: Number would be inserted to the end of the list.
5.6
3.3
9.9
5.6
7.2
12.38
Total number in the list: 6

Warning: Delete 8: The end of the list would be deleted.
3.3
5.6
7.2
Total number in the list: 3

链表这种类可以写成模板(Template),供以后嵌套和使用

1.4 链表的类型

链表有很多种类型,依据不同的功能而设计。

1.4.1 单向链表(singly linked lists)

刚刚上面定义的即是单向链表,即每个节点只含有下一个节点地址的信息。当然,单项链表可以反过来,即最后的一个节点一个个向前一个指。

1.4.2 双向链表(doubly linked list)

双向链表,顾名思义,是一个节点同时包含前一个节点和后一个节点的地址信息。这样索引的时候既可以往前索引,也可以往后索引。
C++ 语言学习入门--链表、队列与栈

1.4.3 循环链表(circularly linked list)

循环链表是节点之间形成闭环,每个节点指向下一个,形成一个闭环。
C++ 语言学习入门--链表、队列与栈

1.5 STL List库

对于链表而言,C++标准库中有现成的成熟库,可以直接调用。list是一种双向链表。

库声明:
#include <list>

转自C++ list用法。对应成员函数:

实例化一个链表:
list<int> myList; //生成一个int的链表

相关成员函数
assign()            //给list赋值 
back()              //返回最后一个元素 
begin()             //返回指向第一个元素的迭代器 
clear()             //删除所有元素 
empty()             //如果list是空的则返回true,否则返回false
end()               //返回末尾的迭代器 
erase(x)/erase(x,y) //删除第 
front()             //返回第一个元素 
get_allocator()     //返回list的配置器 
insert()            //插入一个元素到list中 
max_size()          //返回list能容纳的最大元素数量 
merge()             //合并两个list 
pop_back()          //删除最后一个元素 
pop_front()         //删除第一个元素 
push_back()         //在list的末尾添加一个元素 
push_front()        //在list的头部添加一个元素 
remove()            //从list删除元素 
remove_if()         //按指定条件删除元素 
resize()            //改变list的大小 
reverse()           //把list的元素倒转 
size()              //返回list中的元素个数 
sort()              //给list排序 
swap()              //交换两个list 
unique()            //删除list中的重复元素

2. 队列(Queue)

2.1 什么是队列?

2.2 STL Queue库

3. 栈(Stack)

3.1 什么是栈?

3.2 STL Stack库

上一篇:增强for循环 集合嵌套


下一篇:java 中的泛型