链表结构-----“银行自助叫号”
链表(Linked List)是一种常见的数据结构,用于存储一个序列的元素。它由一系列结点组成,每个结点包含两个部分:数据部分和指针部分。数据部分存储着当前结点的数据,而指针部分则存储着下一个结点的地址。
链表可以分为单向链表、双向链表和循环链表等几种类型。其中单向链表每个结点只有一个指针指向下一个结点,而双向链表则每个结点有两个指针,一个指向前一个结点,一个指向后一个结点。循环链表与普通链表类似,只不过最后一个结点的指针指向链表的头结点。
链表相对于数组来说,具有动态性,可以根据需要随时进行扩展或缩小,但是在访问链表中的某个元素时,需要从链表的头结点开始顺序遍历,因此访问效率较低。
一、链表的初始化
链表的初始化是指创建一个空链表的过程,其中链表中没有任何节点。链表的初始化通常需要进行以下几个步骤:
1)、定义链表的结构:首先需要定义链表节点的结构。链表节点通常包含两个部分:数据域和指针域。数据域用于存储节点的数据,而指针域用于指向下一个节点。
struct LinkNode {
int data; // 数据域
LinkNode* next; // 指针域
};
2)、创建头节点:链表的头节点是一个特殊的节点,它不存储实际的数据,只用于标识链表的起点。在初始化链表时,需要创建一个头节点。
LinkNode* head = new LinkNode(); // 创建头节点
head->next = nullptr; // 头节点的指针域为空
或使用 malloc 函数创建
// 初始化空链表
LinkNode* Init_Link() {
/*该代码段将返回一个指向已初始化的空链表的头节点的指针,
可以在其他函数中使用该指针进行链表操作。*/
LinkNode* head = (LinkNode*)malloc(sizeof(LinkNode));
head->next = nullptr;
return head;
}
执行上述代码之后,则有:
3)、设置尾节点:在初始化链表时,由于链表为空,头节点同时也是尾节点,因此需要将头节点的指针域设置为空。
head->next = nullptr;
4)、完成初始化:将链表的头节点作为链表的唯一标识,可以通过头节点找到整个链表。此时,链表的初始化就完成了。
完整的链表初始化代码示例:
#include<iostream>
struct LinkNode{
int data; // 数据域
LinkNode* next; // 指针域
};
// 初始化空链表
LinkNode* Init_Link() {
/*该代码段将返回一个指向已初始化的空链表的头节点的指针,
可以在其他函数中使用该指针进行链表操作。*/
LinkNode* head = (LinkNode*)malloc(sizeof(LinkNode));
head->next = nullptr;
return head;
}
int main() {
LinkNode* L1 = Init_Link(); // 调用Init_Link函数,获得一个指向已初始化的空链表的头节点的指针。
// 输出链表头节点的指针
std::cout << "链表L1的指针域:" << L1->next;
free(L1); // 在不再需要链表时手动释放内存,确保没有内存泄漏
return 0;
}
二、链表节点的插入
2.1 头部插入
在上图中,我们首先创建了一个单链表,单链表的元素为1、2、3、4,该单链表包含头节点。接下来, 我们要完成头部插入新节点,即在头节点之后、第一个元素节点之前插入新节点,插入的步骤为:
第一步:让新节点与第一个元素的节点相连接,代码为:
New_head->next = head->next; // 新节点接到头部节点的后一个节点
第二步:让头节点与新节点相连接,代码为:
head->next = New_head; // 头部节点连接新节点
第三步: 链表头节点与原第一个元素的节点之间的连接自动断开。
完整代码实现:
// 链表头部插入节点
void Head_Insert_node(LinkNode* head) {
/*
head:链表头指针
new_data:需要插入的元素
*/
int new_data;
int num2;
std::cout << "头插法插入元素个数:" << std::endl;
std::cin >> num2;
std::cout << "头插法插入元素:" << std::endl;
for (int i = 0; i < num2; i++) {
std::cin >> new_data;
LinkNode* New_head = (LinkNode*)malloc(sizeof(LinkNode)); // 定义一个新节点NewNode(为新节点分配地址)
if (New_head == nullptr) {
std::cout << "内存分配失败!\n";
}
New_head->data = new_data; // 为新节点分配值
// 头部插入新节点
New_head->next = head->next; // 新节点接到头部节点的后一个节点
head->next = New_head; // 头部节点连接新节点
}
}
2.2 尾部插入
完整代码实现:
// 链表尾部插入节点
void Tail_Insert_node(LinkNode* head) {
int tail_new_data; // 定义尾部插入元素
int tail_num; // 定义尾插法插入元素个数
std::cout << "尾插法插入元素个数:" << std::endl;
std::cin >> tail_num;
std::cout << "尾插法插入元素:" << std::endl;
LinkNode* each_current = head; // 定义遍历指针
for (int i = 0; i < tail_num; i++) {
std::cin >> tail_new_data;
LinkNode* New_node = (LinkNode*)malloc(sizeof(LinkNode)); // 定义一个新节点NewNode(为新节点分配地址)
if (New_node == nullptr) {
std::cout << "内存分配失败!\n";
}
if (each_current->next == nullptr) { // 链表只有头节点,没有元素节点
New_node->data = tail_new_data; // 为新节点分配值
each_current->next = New_node;
New_node->next = nullptr; // 若没有这句话 会报错 *****重要!!!
each_current = each_current->next;
}
if (each_current->next != nullptr) { // 链表除头节点之外还有其他的元素节点
New_node->data = tail_new_data; // 为新节点分配值
while (each_current->next != nullptr) {
each_current = each_current->next;
}
each_current->next = New_node;
New_node->next = nullptr; // 若没有这句话 会报错 *****重要!!!
}
}
}
2.2.1 尾部插入时两种情况
2.2.1.1 非空链表时尾插
第一步:遍历指针找出链表尾部节点 。
过程分析:
首先需要定义一个链表类型的遍历指针each_current, 该指针用于寻找链表的尾部节点,该指针初始位置指向第一个节点,随后开始遍历,若该指针指向的下一个节点内容不为空,则表明该指针指向的节点不是尾部节点,此时该指针自增,直到该指针指向的下一个节点的内容为nullptr,说明该指针指向的节点为尾部节点,此时退出while循环。
第二步:将新节点New_head接入尾部节点之后。
注意:新节点New_head的指针域要赋nullptr,即New_head->next=nullptr;否则程序报错!
过程分析:
接下来我们将新节点New_head接入到尾部节点的后面位置。
2.2.1.2 空链表时尾插
2.3 中间任意位置插入
代码实现:
// 链表任意位置插入节点
void Insert_Node(LinkNode* head) {
/*
head:链表的头指针
position:新节点插入的位置
new_data:插入的元素
*/
LinkNode* each_current = head; // 定义遍历指针
LinkNode* New_node = (LinkNode*)malloc(sizeof(LinkNode)); // 定义一个新节点NewNode(为新节点分配地址)
int new_data; // 插入元素
int position; // 插入位置
if (each_current->next == nullptr) {
std::cout << "链表中无元素,请先考虑使用头插法或尾插法创建链表!" << std::endl;
}
else {
std::cout << "插入位置:" << std::endl;
std::cin >> position;
std::cout << "插入元素:" << std::endl;
std::cin >> new_data;
if (New_node == nullptr) {
std::cout << "内存分配失败!\n";
}
New_node->data = new_data; // 为新节点分配值
New_node->next = nullptr;
int count_num = count_Linknum(head); // 获取链表元素个数,储存在变量count_num中
if (position <= 0) {
std::cout << "插入位置越下界!\n";
}
else if (position > count_num) {
std::cout << "插入位置越上界!\n";
}
else {
// 找到要插入位置的前一个节点
int count = 1;
while (each_current->next != nullptr && count != position) {
each_current = each_current->next;
count++;
}
// 在指定位置插入节点
New_node->next = each_current->next;
each_current->next = New_node;
}
}
}
分析:
三、链表元素的打印
链表元素打印函数如下(带有头节点的链表):
// 打印链表元素
void printLinkNode(LinkNode* head) {
LinkNode* each_current = head->next; // 定义遍历指针
std::cout << "链表元素为:\n";
while (each_current != nullptr){
std::cout<< each_current->data << " ";
each_current = each_current->next;
}
}
上述代码段分析:
对于链表元素的打印,我们需要定义一个链表类型的遍历指针each_current,该指针首先指向头节点的后一个节点,即装第一个元素的节点。当遍历指针所指内容不为空时,输出遍历指针指向的当前节点的元素值,随后遍历指针递增,直到遍历指针指向nullptr,此时节点遍历完成,退出while循环。
四、统计链表元素个数
函数实现:
// 统计链表元素个数
int count_Linknum(LinkNode* head) {
/*
head:表示头指针
*/
LinkNode* each_current = head->next; // 定义遍历指针
int count_num = 0;
while (each_current != nullptr) {
each_current = each_current->next;
count_num++;
}
return count_num;
}
代码分析(以带头结点的四个元素节点为例):
五、链表元素的删除
5.1 链表指定元素的删除
代码如下:
// 删除链表指定元素
void Delete_element(LinkNode* head) {
LinkNode* each_current = head->next; // 定义遍历指针
LinkNode* pre_each_current = head;
if (each_current == nullptr) {
std::cout << "链表中无元素,请先创建链表!" << std::endl;
}
else {
int delete_data;
std::cout << "删除的元素:" << std::endl;
std::cin >> delete_data;
while (each_current != nullptr) {
if ((each_current->data != delete_data) && (each_current->next == nullptr)) {
std::cout << "链表中没有您想要删除的元素!" << std::endl;
}
if (each_current->data == delete_data) {
pre_each_current->next = each_current->next;
free(each_current); // 释放要删除的节点
each_current = pre_each_current->next; // each_current指向删除节点的后一个节点
std::cout << "元素" << delete_data << "已删除!" << std::endl;
}
else {
// 当没有找到要删除的元素时,each_current和pre_each_current正常递增
each_current = each_current->next;
pre_each_current = pre_each_current->next;
}
}
}
}
5.2 链表指定位置上的元素的删除
代码如下:
// 删除链表指定位置上的元素
void Delete_position(LinkNode* head) {
LinkNode* each_current = head->next; // 定义遍历指针
LinkNode* pre_each_current = head;
if (each_current == nullptr) {
std::cout << "链表中无元素,请先创建链表!" << std::endl;
}
else {
int delete_position;
std::cout << "删除的位置:" << std::endl;
std::cin >> delete_position;
int linknum = count_Linknum(head); // 链表元素个数
if (delete_position > linknum) {
std::cout << "删除越上界!" << std::endl;
}
if (delete_position <= 0) {
std::cout << "删除越下界!" << std::endl;
}
else {
int element_position = 1; // 元素位置变量
while (element_position != delete_position) {
element_position++;
each_current = each_current->next;
pre_each_current = pre_each_current->next;
}
pre_each_current->next = pre_each_current->next->next; // 也可:pre_each_current->next = each_current->next;
std::cout << "第" << delete_position << "位置上的元素" << each_current->data << "已删除!" << std::endl;
free(each_current);
}
}
}
六、查询链表元素
6.1 查询链表指定元素
// 查询链表指定元素
void search_element(LinkNode* head) {
int element_position = 1; // 元素位置变量
LinkNode* each_current = head->next; // 定义遍历指针
if (each_current == nullptr) {
std::cout << "链表中无元素,请先创建链表!" << std::endl;
}
else {
int search_data;
std::cout << "查找元素:" << std::endl;
std::cin >> search_data;
while (each_current != nullptr) {
if (each_current->data == search_data) {
std::cout << "元素:{" << search_data << "}" << "-" << "所在位置:" << element_position << std::endl;
}
else {
std::cout << "链表中不存在此元素!" << std::endl;
break;
}
each_current = each_current->next;
element_position++;
}
}
}
6.2 查询链表指定位置上面的元素
// 查询链表指定位置上面的元素
void search_position(LinkNode* head) {
int element_position = 1; // 元素位置变量
LinkNode* each_current = head->next; // 定义遍历指针
int linknum = count_Linknum(head);; // 链表元素个数
if (each_current == nullptr) {
std::cout << "链表中无元素,请先创建链表!" << std::endl;
}
else {
int Sposition;
std::cout << "查找的位置为:" << std::endl;
std::cin >> Sposition;
if (Sposition > linknum) {
std::cout << "查询越上界!" << std::endl;
}
if (Sposition <= 0) {
std::cout << "查询越下界!" << std::endl;
}
else {
while (each_current != nullptr) {
if (element_position == Sposition) {
std::cout << "位置:" << Sposition << "所对应的元素为:" << each_current->data << std::endl;
}
each_current = each_current->next;
element_position++;
}
}
}
}
七、主函数
int main() {
LinkNode* L1 = Init_Link(); // 调用Init_Link函数,获得一个指向已初始化的空链表的头节点的指针。
int choice; // 选择变量
while (true) {
system("pause");
system("cls");
std::cout << "请选择要执行的操作:" << std::endl;
std::cout << "---------------------------------------" << std::endl;
std::cout << "1:退出" << std::endl;
std::cout << "2:链表节点头插法" << std::endl;
std::cout << "3:链表节点尾插法" << std::endl;
std::cout << "4:链表节点任意位置插法" << std::endl;
std::cout << "5:查询链表指定元素" << std::endl;
std::cout << "6:查询链表指定位置上的元素" << std::endl;
std::cout << "7:删除链表指定元素" << std::endl;
std::cout << "8:删除链表指定位置上的元素" << std::endl;
std::cout << "9:统计链表元素个数" << std::endl;
std::cout << "10:打印链表元素" << std::endl;
std::cout << "---------------------------------------" << std::endl;
std::cin >> choice;
switch (choice) {
case 1:
exit(0);
break;
case 2:
Head_Insert_node(L1);
break;
case 3:
Tail_Insert_node(L1);
break;
case 4:
Insert_Node(L1);
break;
case 5: // 查询链表指定元素
search_element(L1);
break;
case 6:
search_position(L1);
break;
case 7:
Delete_element(L1);
break;
case 8:
Delete_position(L1);
break;
case 9:
int count_num;
count_num = count_Linknum(L1);
std::cout << "链表中现存元素个数为:" << count_num << std::endl;
break;
case 10:
printLinkNode(L1);
break;
}
}
/*Head_Insert_node(L1, 4);
Head_Insert_node(L1, 3);
Head_Insert_node(L1, 2);
Head_Insert_node(L1, 1);
Tail_Insert_node(L1, 5);
Insert_Node(L1, 3, 3);
printLinkNode(L1);
search_element(L1, 3);
search_position(L1, 5);
Delete_position(L1, 2);
printLinkNode(L1);*/
// int count_num = count_Linknum(L1);
// std::cout << "链表元素个数为:\n" << count_num;
// 输出链表头节点的指针
// std::cout << "链表L1的指针域:" << L1->next;
free(L1); // 在不再需要链表时手动释放内存,确保没有内存泄漏
return 0;
}