前言
链表是一种动态的数据结构,因为在创建链表时,不需要知道链表的长度,只需要对指针进行操作。
1. 节点的创建
链表的节点包括两部分,分别是:数据域和(指向下一个节点的)指针域。
1
2
3
4
|
struct Node { int data; struct Node* next; }; |
2. 链表的定义
1
2
3
4
5
6
|
struct Node* createList() { //创建一个指针来表示表头 struct Node* headNode = ( struct Node*) malloc ( sizeof ( struct Node)); headNode->next = NULL; return headNode; } |
3. 创建节点
1
2
3
4
5
6
7
8
|
struct Node* createNode( int data) { //创建一个新的指针节点 struct Node* newNode = ( struct Node*) malloc ( sizeof ( struct Node)); //结构体变量初始化 newNode->data = data; newNode->next = NULL; return newNode; } |
4. 节点的插入
节点的插入分为三种:头插法、尾插法、在链表中间插入节点。
4.1 头插法
头插法,顾名思义就是在链表的第一个节点插入一个节点。
解决方法:让新插入的节点的next指针指向链表的头结点即可。
1
2
3
4
5
|
void insertNodeByHead( struct Node* headNode, int data) { struct Node* newNode = createNode(data); newNode->next = headNode->next; headNode->next = newNode; } |
4.2 尾插法
尾插法,顾名思义就是在链表的末尾增加一个节点。
解决思路:首先找到链表的最后一个节点;然后让最后的节点的next指针指向要插入的这个节点,插入的节点的next指针指向NULL即可。
1
2
3
4
5
6
7
8
9
|
void insertNodeByTail( struct Node* headNode, int data) { struct Node* newNode = createNode(data); while (headNode->next != NULL) { headNode = headNode->next; //找到最后一个节点 } headNode->next = newNode; newNode->next = NULL; } |
4.3 插入中间节点
插入中间节点:即在数据为 i 的节点后面添加新的节点。
解决思路:首先判断数据为 i 的节点posNode是否在链表中存在;然后从第一个节点开始查找节点posNode。找到后就让插入的节点的next指针指向posNode的下一个节点,posNode的next指针指向新插入的节点即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
void insertNodeByCenter( struct Node* headNode, int data, int i) { struct Node* posNode = headNode; /*struct Node* posNodeFront = headNode;*/ struct Node* newNode = createNode(data); if (posNode == NULL) { printf ( "无法查找此数据,链表为空\n" ); } else { while (posNode->data != i) { posNode = posNode->next; //前面位置到达了后面节点的位置 /*posNode = posNodeFront->next;*/ //后面位置变成了原来位置的下一个 if (posNode == NULL) { printf ( "未找到此数据\n" ); break ; } } newNode->next = posNode->next; posNode->next = newNode; } } |
总结
到此这篇关于C++链表节点的添加和删除介绍的文章就介绍到这了,更多相关C++链表节点内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家!
原文链接:https://blog.csdn.net/qq_47635065/article/details/122388071