如何实现一个简单的链表或栈结构
实现一个简单的链表或栈结构是面向对象编程中的基础任务。下面我将分别给出链表和栈的简单实现。
链表（单链表）的实现
链表是由一系列节点组成的集合，每个节点都包含数据部分和指向列表中下一个节点的链接（指针或引用）。
cpp复制代码
#include <iostream> | |
using namespace std; | |
// 定义链表的节点 | |
struct ListNode { | |
int val; // 节点存储的数据 | |
ListNode* next; // 指向下一个节点的指针 | |
// 构造函数 | |
ListNode(int x) : val(x), next(nullptr) {} | |
}; | |
// 定义链表类 | |
class LinkedList { | |
private: | |
ListNode* head; // 链表的头节点 | |
public: | |
// 构造函数 | |
LinkedList() : head(nullptr) {} | |
// 析构函数（用于释放链表内存，这里为了简化省略） | |
// 向链表末尾添加元素 | |
void append(int val) { | |
ListNode* newNode = new ListNode(val); | |
if (head == nullptr) { | |
head = newNode; | |
} else { | |
ListNode* temp = head; | |
while (temp->next != nullptr) { | |
temp = temp->next; | |
} | |
temp->next = newNode; | |
} | |
} | |
// 打印链表（为了演示） | |
void print() { | |
ListNode* temp = head; | |
while (temp != nullptr) { | |
cout << temp->val << " "; | |
temp = temp->next; | |
} | |
cout << endl; | |
} | |
// 其他链表操作（如删除、查找等）可以按需添加 | |
}; | |
int main() { | |
LinkedList list; | |
list.append(1); | |
list.append(2); | |
list.append(3); | |
list.print(); // 输出: 1 2 3 | |
return 0; | |
} |
栈的实现
栈是一种后进先出（LIFO）的数据结构，只能在一端（栈顶）进行添加（push）或删除（pop）元素的操作。
cpp复制代码
#include <iostream> | |
#include <stdexcept> // 用于抛出异常 | |
using namespace std; | |
// 使用链表实现栈 | |
class Stack { | |
private: | |
ListNode* top; // 栈顶元素 | |
public: | |
Stack() : top(nullptr) {} | |
// 向栈中添加元素 | |
void push(int val) { | |
ListNode* newNode = new ListNode(val); | |
newNode->next = top; | |
top = newNode; | |
} | |
// 从栈中删除元素 | |
int pop() { | |
if (top == nullptr) { | |
throw runtime_error("Stack is empty"); | |
} | |
ListNode* temp = top; | |
int val = top->val; | |
top = top->next; | |
delete temp; | |
return val; | |
} | |
// 检查栈是否为空 | |
bool isEmpty() { | |
return top == nullptr; | |
} | |
// 栈的其他操作（如查看栈顶元素但不删除等）可以按需添加 | |
}; | |
// 注意：ListNode 类已经在链表实现中定义，这里不再重复 | |
int main() { | |
Stack stack; | |
stack.push(1); | |
stack.push(2); | |
stack.push(3); | |
while (!stack.isEmpty()) { | |
cout << stack.pop() << " "; | |
} | |
// 输出: 3 2 1 | |
return 0; | |
} |
以上代码展示了如何使用C++中的类和结构来实现简单的链表和栈结构。链表通过节点间的链接来存储数据，而栈则通过限制只能在一端进行操作来实现后进先出的特性。