在C++中实现一个简单的链表或栈结构,我们可以分别来看。首先,链表是一种线性数据结构,其中每个元素都包含数据本身以及指向列表中下一个元素的指针(对于双向链表,还会有指向前一个元素的指针)。而栈是一种后进先出(LIFO, Last In First Out)的数据结构,它只允许在栈顶进行添加(push)或删除(pop)元素的操作。
链表(单向链表)
下面是一个简单的单向链表的实现:
cpp复制代码
#include <iostream> | |
struct ListNode { | |
int val; | |
ListNode *next; | |
ListNode(int x) : val(x), next(nullptr) {} | |
}; | |
class LinkedList { | |
public: | |
ListNode *head; | |
LinkedList() : head(nullptr) {} | |
// 在链表末尾添加元素 | |
void append(int val) { | |
ListNode* newNode = new ListNode(val); | |
if (!head) { | |
head = newNode; | |
return; | |
} | |
ListNode* temp = head; | |
while (temp->next) { | |
temp = temp->next; | |
} | |
temp->next = newNode; | |
} | |
// 遍历链表并打印元素 | |
void print() { | |
ListNode* temp = head; | |
while (temp) { | |
std::cout << temp->val << " "; | |
temp = temp->next; | |
} | |
std::cout << std::endl; | |
} | |
// 析构函数,释放链表占用的内存 | |
~LinkedList() { | |
while (head) { | |
ListNode* temp = head; | |
head = head->next; | |
delete temp; | |
} | |
} | |
}; | |
int main() { | |
LinkedList list; | |
list.append(1); | |
list.append(2); | |
list.append(3); | |
list.print(); // 输出: 1 2 3 | |
return 0; | |
} |
栈
栈的实现可以使用数组或链表。这里我们使用链表来实现栈,因为链表在动态扩展方面更加灵活:
cpp复制代码
#include <iostream> | |
struct StackNode { | |
int val; | |
StackNode *next; | |
StackNode(int x) : val(x), next(nullptr) {} | |
}; | |
class Stack { | |
private: | |
StackNode *top; | |
public: | |
Stack() : top(nullptr) {} | |
// 判断栈是否为空 | |
bool isEmpty() { | |
return top == nullptr; | |
} | |
// 向栈顶添加元素 | |
void push(int val) { | |
StackNode* newNode = new StackNode(val); | |
newNode->next = top; | |
top = newNode; | |
} | |
// 从栈顶删除元素 | |
int pop() { | |
if (isEmpty()) { | |
throw std::runtime_error("pop from empty stack"); | |
} | |
StackNode* temp = top; | |
int val = temp->val; | |
top = top->next; | |
delete temp; | |
return val; | |
} | |
// 获取栈顶元素(不移除) | |
int peek() { | |
if (isEmpty()) { | |
throw std::runtime_error("peek from empty stack"); | |
} | |
return top->val; | |
} | |
// 析构函数 | |
~Stack() { | |
while (!isEmpty()) { | |
pop(); | |
} | |
} | |
}; | |
int main() { | |
Stack s; | |
s.push(1); | |
s.push(2); | |
std::cout << "Top element is " << s.peek() << std::endl; // 输出: Top element is 2 | |
s.pop(); | |
std::cout << "After pop, top element is " << s.peek() << std::endl; // 输出: After pop, top element is 1 | |
return 0; | |
} |
在这两个示例中,我们定义了数据结构和基本操作,包括链表的添加、打印和析构,以及栈的push、pop、peek和析构。这些操作是这些数据结构的核心功能。