#include <iostream>
using namespace std; // 使用标准命名空间
// 定义模板类节点
template <typename T>
class Node
{
public:
T data; // 存储节点数据
Node* next; // 指向下一个节点的指针
// 构造函数初始化节点
Node(T value)
{
data = value; // 初始化节点数据
next = nullptr; // 初始化指向下一个节点的指针为空
}
};
// 定义模板类单链表
template <typename T>
class LinkedList {
private:
Node<T>* head; // 指向链表头节点的指针
public:
LinkedList() : head(nullptr)
{
} // 构造函数初始化头节点为空
//LinkedList()
//{
// head = nullptr; // 在构造函数体内初始化头节点为空
//}
// 头插法插入新节点
void insertAtHead(T value)
{
Node<T>* newNode = new Node<T>(value); // 创建新节点 Node* newNode = new Node(value);
newNode->next = head; // 新节点指向当前头节点
head = newNode; // 头节点更新为新节点
}
// 在任意位置插入新节点
void insertAtPosition(T value, int position)
{
if (position <= 0)
{ // 如果位置小于等于0,直接头插法插入
insertAtHead(value); // 插入新节点到头部
return; // 结束函数
}
Node<T>* newNode = new Node<T>(value); // 创建新节点
Node<T>* current = head; // 当前节点从头节点开始
// 遍历到指定位置的前一个节点
for (int i = 1; i < position-1 && current != nullptr; ++i)
{
current = current->next; // 当前节点向后移动
}
if (current == nullptr)
{ // 如果当前位置超出链表长度
cout << "位置超出链表长度,将在链表末尾插入。\n"; // 输出提示信息
Node<T>* last = head; // 从头节点开始找最后一个节点
while (last->next != nullptr) { // 找到链表的最后一个节点
last = last->next; // 移动到下一个节点
}
last->next = newNode; // 在最后一个节点后插入新节点
}
else
{
newNode->next = current->next; // 新节点指向当前位置的下一个节点
current->next = newNode; // 前一个节点指向新节点
}
}
// 打印链表
void printList() const
{
Node<T>* current = head; // 从头节点开始遍历
while (current != nullptr)
{ // 遍历到链表末尾
cout << current->data << " -> "; // 打印当前节点数据
current = current->next; // 移动到下一个节点
}
cout << "nullptr\n"; // 打印链表结束标志
}
// 析构函数,释放链表内存
~LinkedList()
{
Node<T>* current = head; // 从头节点开始遍历
while (current != nullptr)
{ // 遍历到链表末尾
Node<T>* nextNode = current->next; // 保存下一个节点指针
delete current; // 删除当前节点
current = nextNode; // 移动到下一个节点
}
}
};
int main()
{
LinkedList<int> list; // 创建一个整型单链表
list.insertAtHead(10); // 插入数据10到头部
list.insertAtHead(20); // 插入数据20到头部
list.insertAtHead(30); // 插入数据30到头部
cout << "初始链表:\n"; // 输出提示信息
list.printList(); // 打印链表
list.insertAtPosition(25, 2); // 在位置2插入数据25
cout << "在位置2插入25后:\n"; // 输出提示信息
list.printList(); // 打印链表
list.insertAtPosition(5, 0); // 在位置0插入数据5
cout << "在位置0插入5后:\n"; // 输出提示信息
list.printList(); // 打印链表
list.insertAtPosition(50, 10); // 在位置10插入数据50,超出范围
cout << "在位置10插入50后 (超出范围):\n"; // 输出提示信息
list.printList(); // 打印链表
system("pause");
return 0; // 返回0,结束程序
}
//
//#include <iostream>
//using namespace std; // 使用标准命名空间
// 定义具体的节点类(处理 int 类型)
//class Node
//{
//public:
// int data; // 存储节点数据
// Node* next; // 指向下一个节点的指针
//
// // 构造函数初始化节点
// Node(int value)
// {
// data = value; // 初始化节点数据
// next = nullptr; // 初始化指向下一个节点的指针为空
// }
//};
//
定义具体的单链表类(处理 int 类型)
//class LinkedList {
//private:
// Node* head; // 指向链表头节点的指针
//
//public:
// LinkedList() : head(nullptr)
// {
// } // 构造函数初始化头节点为空
//
// // 头插法插入新节点
// void insertAtHead(int value)
// {
// Node* newNode = new Node(value); // 创建新节点
// newNode->next = head; // 新节点指向当前头节点
// head = newNode; // 头节点更新为新节点
// }
//
// // 在任意位置插入新节点
// void insertAtPosition(int value, int position) {
// if (position <= 0)
// { // 如果位置小于等于0,直接头插法插入
// insertAtHead(value); // 插入新节点到头部
// return; // 结束函数
// }
//
// Node* newNode = new Node(value); // 创建新节点
// Node* current = head; // 当前节点从头节点开始
//
// // 遍历到指定位置的前一个节点
// for (int i = 1; i < position-1 && current != nullptr; ++i)
// {
// current = current->next; // 当前节点向后移动
// }
//
// if (current == nullptr)
// { // 如果当前位置超出链表长度
// cout << "位置超出链表长度,将在链表末尾插入。\n"; // 输出提示信息
// Node* last = head; // 从头节点开始找最后一个节点
// while (last != nullptr && last->next != nullptr)
// { // 找到链表的最后一个节点
// last = last->next; // 移动到下一个节点
// }
// if (last != nullptr)
// {
// last->next = newNode; // 在最后一个节点后插入新节点
// }
// else {
// // 链表为空,直接插入新节点
// head = newNode;
// }
// }
// else
// {
// newNode->next = current->next; // 新节点指向当前位置的下一个节点
// current->next = newNode; // 前一个节点指向新节点
// }
// }
//
// // 打印链表
// void printList() const
// {
// Node* current = head; // 从头节点开始遍历
// while (current != nullptr)
// { // 遍历到链表末尾
// cout << current->data << " -> "; // 打印当前节点数据
// current = current->next; // 移动到下一个节点
// }
// cout << "nullptr\n"; // 打印链表结束标志
// }
//
// // 析构函数,释放链表内存
// ~LinkedList() {
// Node* current = head; // 从头节点开始遍历
// while (current != nullptr) { // 遍历到链表末尾
// Node* nextNode = current->next; // 保存下一个节点指针
// delete current; // 删除当前节点
// current = nextNode; // 移动到下一个节点
// }
// }
//};
//
//int main() {
// LinkedList list; // 创建一个整型单链表
// list.insertAtHead(10); // 插入数据10到头部
// list.insertAtHead(20); // 插入数据20到头部
// list.insertAtHead(30); // 插入数据30到头部
//
// cout << "初始链表:\n"; // 输出提示信息
// list.printList(); // 打印链表
//
// list.insertAtPosition(25, 2); // 在位置2插入数据25
// cout << "在位置2插入25后:\n"; // 输出提示信息
// list.printList(); // 打印链表
//
// list.insertAtPosition(5, 0); // 在位置0插入数据5
// cout << "在位置0插入5后:\n"; // 输出提示信息
// list.printList(); // 打印链表
//
// list.insertAtPosition(50, 10); // 在位置10插入数据50,超出范围
// cout << "在位置10插入50后 (超出范围):\n"; // 输出提示信息
// list.printList(); // 打印链表
// system("pause");
// return 0; // 返回0,结束程序
//}
C++实现单链表(头加法)(在任意位置添加)
最新推荐文章于 2024-09-08 17:41:31 发布