当前位置： 首页 > news >正文

数组与链表算法-单向链表算法

news 2025/8/18 19:15:21

目录

数组与链表算法-单向链表算法

C++代码

单向链表插入节点的算法

C++代码

单向链表删除节点的算法

C++代码

对单向链表进行反转的算法

C++代码

单向链表串接的算法

C++代码

数组与链表算法-单向链表算法

在C++中，若以动态分配产生链表节点的方式，则可以先行定义一个类数据类型，接着在类中定义一个指针变量，其数据类型与此类相同，作用是指向下一个链表节点，另外类中至少要有一个数据字段。例如，声明一个学生成绩链表节点的结构，并且包含两个数据字段：姓名（name)和成绩（score），以及一个指针（next）。接着就可以动态创建链表中的每个节点。假设现在要新增一个节点至链表的末尾，且ptr指向链表的第一个节点，程序必须设计以下4个步骤：

  1. 动态分配内存空间给新节点使用。
  2. 将原链表尾部的指针（next）指向新元素所在的内存位置（内存地址）。
  3. 将ptr指针指向新节点的内存位置，表示这是新的链表尾部。
  4. 由于新节点当前为链表的最后一个元素，因此将它的指针（next）指向NULL。

遍历（Traverse）单向链表的过程，就是使用指针运算来访问链表中的每个节点。如果要遍历已建立的单向链表，就可以使用结构指针ptr来作为链表的读取游标，一开始指向链表的头。每次读完链表的一个节点，就将ptr往下一个节点移动（指向下一个节点），直到ptr指向NULL为止。

C++代码

#include<iostream>
using namespace std;class list {
public:int num;char name[10];int score;class list* next;
};void SetList(list* tempList) {cout << "请输入学号：";cin >> tempList->num;cout << "请输入姓名：";cin >> tempList->name;cout << "请输入成绩：";cin >> tempList->score;
}int main() {list* newnode;list* ptr;list* delptr;cout << "请输入5位学员的数据：" << endl;delptr = new list;SetList(delptr);ptr = delptr;for (int i = 1; i < 5; i++) {newnode = new list;SetList(newnode);newnode->next = nullptr;ptr->next = newnode;ptr = ptr->next;}cout << "学生成绩" << endl;cout << "学号\t姓名\t成绩\n========================" << endl;ptr = delptr;while (ptr != nullptr) {cout << ptr->num << "\t" << ptr->name << "\t" << ptr->score << endl;ptr = ptr->next;}return 0;
}

输出结果

单向链表插入节点的算法

  1. 将新节点加到第一个节点之前，即成为此链表的首节点。
  2. 将新节点加到最后一个节点之后。
  3. 将新节点加到链表中间的位置。

C++代码

#include<iostream>
using namespace std;class list {
public:int num;char name[10];int score;class list* next;
};void SetList(list* tempList) {cout << "请输入学号：";cin >> tempList->num;cout << "请输入姓名：";cin >> tempList->name;cout << "请输入成绩：";cin >> tempList->score;
}void PrintList(list* head) {list* ptr = head;while (ptr != nullptr) {cout << ptr->num << "\t" << ptr->name << "\t" << ptr->score << endl;ptr = ptr->next;}
}list* FindNode(list* head, int num) {list* ptr;ptr = head;while (ptr != nullptr) {if (ptr->num == num)return ptr;ptr = ptr->next;}return ptr;
}list* InsertNode(list* head, list* ptr, list* tempList) {if (ptr == nullptr) {tempList->next = head;return tempList;}else {if (ptr->next == nullptr) {ptr->next = tempList;}else {tempList->next = ptr->next;ptr->next = tempList;}}return head;
}int main() {list* newnode;list* ptr;list* head;cout << "请输入3位学员的数据：" << endl;head = new list;SetList(head);ptr = head;for (int i = 1; i < 3; i++) {newnode = new list;SetList(newnode);newnode->next = nullptr;ptr->next = newnode;ptr = ptr->next;}cout << "========================" << endl;cout << "学生成绩" << endl;cout << "学号\t姓名\t成绩\n========================" << endl;PrintList(head);int position;while (true){cout << "请输入要插入其后的学生学号，要结束请输入-1：";cin >> position;if (position == -1)break;else {ptr = FindNode(head, position);newnode = new list;SetList(newnode);head = InsertNode(head, ptr, newnode);}}cout << "========================" << endl;cout << "学生成绩" << endl;cout << "学号\t姓名\t成绩\n========================" << endl;PrintList(head);return 0;
}

输出结果

单向链表删除节点的算法

  1. 删除链表的第一个节点
  2. 删除链表的最后一个节点
  3. 删除链表的中间节点

C++代码

#include<iostream>
using namespace std;class list {
public:int num;char name[10];int score;class list* next;
};void SetList(list* tempList) {cout << "请输入学号：";cin >> tempList->num;cout << "请输入姓名：";cin >> tempList->name;cout << "请输入成绩：";cin >> tempList->score;
}void PrintList(list* head) {list* ptr = head;while (ptr != nullptr) {cout << ptr->num << "\t" << ptr->name << "\t" << ptr->score << endl;ptr = ptr->next;}
}list* FindNode(list* head, int num) {list* ptr;ptr = head;while (ptr != nullptr) {if (ptr->num == num)return ptr;ptr = ptr->next;}return ptr;
}list* DeleteNode(list* head, list* ptr) {list* top;top = head;if (ptr == head) {head = head->next;}else {while (top->next != ptr)top = top->next;if (ptr->next == nullptr)top->next = nullptr;elsetop->next = ptr->next;}cout << "已删除第 " << ptr->num << " 号学生的信息" << endl;delete ptr;return head;
}int main() {list* newnode;list* ptr;list* head;cout << "请输入3位学员的数据：" << endl;head = new list;SetList(head);ptr = head;for (int i = 1; i < 3; i++) {newnode = new list;SetList(newnode);newnode->next = nullptr;ptr->next = newnode;ptr = ptr->next;}cout << "========================" << endl;cout << "学生成绩" << endl;cout << "学号\t姓名\t成绩\n========================" << endl;PrintList(head);int position;while (true) {cout << "请输入要插入其后的学生学号，要结束请输入-1：";cin >> position;if (position == -1)break;else {ptr = FindNode(head, position);head = DeleteNode(head, ptr);}}cout << "========================" << endl;cout << "学生成绩" << endl;cout << "学号\t姓名\t成绩\n========================" << endl;PrintList(head);return 0;
}

输出结果

对单向链表进行反转的算法

了解单向链表节点的插入和删除之后，大家会发现在这种具有方向性的链表结构中增删节点是相当容易的一件事。而要从头到尾输出整个单向链表也不难，但若要反转过来输出单向链表，则需要某些技巧。我们知道单向链表中的节点特性是知道下一个节点的位置，是无从得知它的上一个节点的位置。如果要将单向链表反转，就必须使用3个指针变量，如下面程序代码中的before、ptr、last。

C++代码

#include<iostream>
using namespace std;class list {
public:int num;char name[10];int score;class list* next;
};void SetList(list* tempList) {cout << "请输入学号：";cin >> tempList->num;cout << "请输入姓名：";cin >> tempList->name;cout << "请输入成绩：";cin >> tempList->score;
}void PrintList(list* head) {list* ptr = head;while (ptr != nullptr) {cout << ptr->num << "\t" << ptr->name << "\t" << ptr->score << endl;ptr = ptr->next;}
}list* TransposeNode(list* head) {list* ptr = head;list* before = nullptr;list* last = nullptr;while (ptr != nullptr) {last = before; before = ptr;ptr = ptr->next;before->next = last;}head = before;return head;
}int main() {list* newnode;list* ptr;list* head;cout << "请输入3位学员的数据：" << endl;head = new list;SetList(head);ptr = head;for (int i = 1; i < 3; i++) {newnode = new list;SetList(newnode);newnode->next = nullptr;ptr->next = newnode;ptr = ptr->next;}cout << "========================" << endl;cout << "学生成绩" << endl;cout << "学号\t姓名\t成绩\n========================" << endl;PrintList(head);head = TransposeNode(head);cout << "========================" << endl;cout << "反转算法" << endl;cout << "学号\t姓名\t成绩\n========================" << endl;PrintList(head);return 0;
}

输出结果

单向链表串接的算法

对于两个或两个以上的链表的串接（Concatenation，也称为级联），实现起来很容易；只要将链表的首尾相连即可。

C++代码

#include<iostream>
using namespace std;class list {
public:int num;char name[10];int score;class list* next;
};void SetList(list* tempList) {cout << "请输入学号：";cin >> tempList->num;cout << "请输入姓名：";cin >> tempList->name;cout << "请输入成绩：";cin >> tempList->score;
}void PrintList(list* head) {list* ptr = head;while (ptr != nullptr) {cout << ptr->num << "\t" << ptr->name << "\t" << ptr->score << endl;ptr = ptr->next;}
}list* ConcatNode(list* head1, list* head2) {list* ptr;ptr = head1;while (ptr->next != nullptr)ptr = ptr->next;ptr->next = head2;return head1;
}int main() {list* newnode;list* ptr;list* head1;list* head2;cout << "请输入第一组3位学员的数据：" << endl;head1 = new list;SetList(head1);ptr = head1;for (int i = 1; i < 3; i++) {newnode = new list;SetList(newnode);newnode->next = nullptr;ptr->next = newnode;ptr = ptr->next;}cout << "========================" << endl;cout << "第一组学生成绩" << endl;cout << "学号\t姓名\t成绩\n========================" << endl;PrintList(head1);cout << "请输入第二组3位学员的数据：" << endl;head2 = new list;SetList(head2);ptr = head2;for (int i = 1; i < 3; i++) {newnode = new list;SetList(newnode);newnode->next = nullptr;ptr->next = newnode;ptr = ptr->next;}cout << "========================" << endl;cout << "第二组学生成绩" << endl;cout << "学号\t姓名\t成绩\n========================" << endl;PrintList(head2);head1 = ConcatNode(head1, head2);cout << "========================" << endl;cout << "串接算法" << endl;cout << "学号\t姓名\t成绩\n========================" << endl;PrintList(head1);return 0;
}

输出结果

http://www.lryc.cn/news/210486.html

相关文章：

  • Oracle（6） Control File
  • 吴恩达《机器学习》2-5-＞2-7:梯度下降算法与理解
  • Pytorch detach()方法
  • CTF-php特性绕过
  • 人脸识别测试数据分析
  • MySQL 5.7限制general_log日志大小
  • tomcat9~10猫闪退个人经验
  • Linux之J2EE的项目部署及发布
  • 基于闪电搜索算法的无人机航迹规划-附代码
  • 【网络安全 --- 文件上传靶场练习】文件上传靶场安装以及1-5关闯关思路及技巧，源码分析
  • BUUCTF刷题记录
  • 黑客技术（网络安全）—小白自学
  • 免登陆 同步脚本 zookeeper kafka集群详细安装步骤
  • 深入理解NLP
  • Python-自动化绘制股票价格通道线
  • CTF-Crypto学习记录-第四天 “ “ --- SHA1安全散列算法，实现原理。
  • 海南海口大型钢结构件3D扫描全尺寸三维测量平面度平行度检测-CASAIM中科广电
  • 【PyQt学习篇 · ④】：QWidget - 尺寸操作
  • APC学习记录
  • 前端将图片储存table表格中，页面回显
  • [论文阅读]Ghost-free High Dynamic Range Imaging with Context-aware Transformer
  • react高阶成分（HOC）例子效果
  • 【24种设计模式】工厂模式（Factory Pattern）
  • 树——对称二叉树
  • 拉扎维模拟CMOS集成电路设计西交张鸿老师课程P10~13视频学习记录
  • 3.线性神经网络
  • python常用内置函数的介绍和使用
  • 2023辽宁省赛E
  • visual studio 启用C++11
  • 获取某个抖音用户的视频列表信息