0%

C++链表的基本用法

Posted on Edited on In

推荐一本书–C++入门经典

C++已经流行多年，问别人该学什么编程语言，基本没有推荐C++的；现在刚入门机器视觉，也在一开始听着网上老司机学Python，Python学得一知半解，如果说只是写个算法来达到某种目标，Python学Python，Python学得一知半解，如果说只是写个算法来达到某种目标，Python+OpenCV肯定是能行的，但是不同项目可能有这样或那样的要求，如果只会一点点Python，确实有点缺乏说服力，所以就转头开始学习C++。
学习C++的时候，找到一本大牛写的书–C++入门经典by Walter Savitch，通俗易懂，而且讲得都是重要的知识点，不会在某些晦涩深奥的地方浪费半点笔墨。而且这本在前言中有各章节的依赖关系，如果想针对某个方面学习，可以按照依赖图跳着学，这样效率非常高。
C++入门经典

C++中的基础链表

不知道其他语言是怎么样的，C++的链表是靠指针来实现的，链表是由结构或类的节点链接起来构成，在结构或类中，定义所需要的数据变量以及指向这个节点的指针变量，初始化指针后，通过指针进行访问当前节点的数据变量，或者通过指针链接到下一个节点，继而访问下一个节点的数据变量。

1
2
3
4
5
6
7
struct ListNode
{
	string item;
	int count;
	ListNode *link;
}
typedef ListNode *ListNodePtr

ListNode结构类型中定义了字符串变量item、整型变量count以及指针类型link，可以看出link指针是循环定义的，C++中支持这种循环定义。

1
2
3
ListNodePtr head;
head = new ListNode;
(*head).count = 12;

这块代码先是将head声明为ListNodePtr指针类型，然后初始化，再对head指向的节点中的count变量赋值为12。

1
head->count = 12;

*加.的赋值方式难免有些难懂，c++中支持箭头操作符”->”，这样就非常清晰了，将head指向的节点中count变量赋值为12。
接下来给ListNode中的item变量赋值：

1
head->item = "bagels"

这样第一个节点就完成了，如果用图片表示，就是下图这样：
ListNode第一个节点
link之所以指向”?”，是因为还没有给link指定下一个节点，通过以下语句：

1
head->link = anotherNode;

就可以将第一个节点head链接到第二个节点anotherNode（这里假设还有一个节点为anotherNode)
当然也可以写一个插入节点的函数：

1
2
3
4
5
6
7
8
void insert(ListNodePtr head, int theNumber, string theString)
{
	listNodePtr tmpNode = new ListNode;
	tmpNode->count = theNumber;
	tmpNode->item = theString;
	tmpNode->link = head;
	head = tmpNode;
}

insert函数需要传入的参数有：需要添加节点的链表头名称head、赋给count变量的整型值以及赋给item变量的字符串，通过调用insert函数，可以在现有的head表头前添加一个节点，并将新节点的指针赋值给head。如图所示：
两个节点
重复下去，就可以获得包含若干个节点的链表。
图中那个”?”号仍旧非常扎眼，实际上可以将链表的最末尾的link赋值为NULL或nullptr，这就是告诉c++，之后再没有节点了。

C++中其他形式的链表

除了上面介绍的链表以外，通过指针和struct或类数据类型相结合，还可以设计出更为复杂的链表，比如说双向链表或者二叉树

双向链表

1
2
3
4
5
6
struct Node
{
	int data;
	Node *forwardLink;
	Node *backLink;
}

上面一段代码定义了一个双向链表Node，其中有一个整型变量data，和两个Node型指针变量，这样就可以通过forwardLink和backLink来进行节点的前后移动，达到双向的目的。

二叉树

1
2
3
4
5
6
struct TreeNode
{
	int data;
	TreeNode *leftLink;
	TreeNode *rightLink;
}

上面的代码同样定义了二叉树链表TreeNode，仍旧有一个整型变量data和两个指针型变量，但是指针型变量leftLink和rightLink指向左右方向，这样就构建了树形链表结构。

类构成的链表

除了用结构类型来定义链表外，还可以用类类型来定义链表。

1
2
3
4
5
6
7
8
9
10
11
class Node
{
public:
	Node();//类的构造函数
	Node(int value, Node *next);//类的构造函数
	int getData();//类的成员函数，获取类的值并返回
	void setData(int value);//类的成员函数，将value赋给类的成员变量
	void setLink(Node *next);//类的成员函数，更改对下一个节点的引用
private:
	int data;//类的成员变量
	Node *link;//类的指针，指向下一个节点

上面的Node类即为链表的一个节点，多个节点相连就能组成一个链表。

总结

C++的指针优点十分明显，指针可以直接访问内存中的数据，将指针和结构或者类相结合，可以实现各种强大的数据结构，这是其他编程语言不能比拟的；但是缺点也很明显，C++中指针使用非常复杂，通过指针创建的动态数据，需要在使用过后及时销毁，此过程必须程序员手动进行，否则会出现内存溢出问题，如果两个指针指向同一个内存地址，将其中一个指针销毁后，如果再次调用另一个指针，程序同样会崩溃，因此内存管理非常复杂，正印了那句话，成也指针，败也指针！