下面是一个完整的攻略。
1. 单链表的实现
单链表是一种常用的链式结构,其核心是节点(Node)和指针(pointer):
- 节点:保存数据和指向下一个节点的指针
- 指针:用于连接各个节点
以下是单链表的核心代码:
// 节点结构体
struct Node {
int data;
Node* next;
Node(int d): data(d), next(nullptr) {}
};
// 单链表类
class LinkedList {
public:
LinkedList(): head(nullptr) {}
void add_front(int data); // 在链表头添加节点
void add_back(int data); // 在链表尾添加节点
void remove(int data); // 删除指定数据的节点
void print(); // 打印链表内容
private:
Node* head; // 头节点
};
其中,add_front
和add_back
方法分别是在链表头和链表尾添加节点,核心思路如下:
-
在链表头添加节点:
- 新建节点
- 将head节点作为新节点的下一个节点
- 将head更新为新节点
-
在链表尾添加节点:
- 新建节点
- 找到链表的最后一个节点
- 将最后一个节点的next指针指向新节点
remove
方法的核心是找到要删除的节点以及更新节点的next指针。
print
方法的核心是遍历链表,并输出每个节点的数据。
以下是add_front
方法的示例:
void LinkedList::add_front(int data) {
Node* new_node = new Node(data);
new_node->next = head;
head = new_node;
}
2. 双链表的实现
双链表和单链表类似,不同之处在于:
- 节点(Node)保存了指向上一个节点的指针(prev)和下一个节点的指针(next)
add_front
方法需要更新原head节点的prev指针,remove
方法需要更新相关节点的prev和next指针
以下是双链表的核心代码:
// 双链表节点结构体
struct Node {
int data;
Node* prev;
Node* next;
Node(int d): data(d), prev(nullptr), next(nullptr) {}
};
// 双链表类
class DoublyLinkedList {
public:
DoublyLinkedList(): head(nullptr), tail(nullptr) {}
void add_front(int data); // 在链表头添加节点
void add_back(int data); // 在链表尾添加节点
void remove(int data); // 删除指定数据的节点
void print(); // 打印链表内容
private:
Node* head; // 头节点
Node* tail; // 尾节点
};
以下是add_front
方法的示例:
void DoublyLinkedList::add_front(int data) {
Node* new_node = new Node(data);
if (head == nullptr) { // 空链表
head = new_node;
tail = new_node;
} else {
new_node->next = head;
head->prev = new_node;
head = new_node;
}
}
3. 栈的实现
栈(Stack)是一种基于先进后出(LIFO)的数据结构,其核心操作是压入(push)和弹出(pop)元素:
- 压入元素:将元素放在栈顶
- 弹出元素:取出栈顶元素
以下是栈的核心代码:
// 栈类
class Stack {
public:
Stack(): top(-1) {}
void push(int data); // 压入元素
int pop(); // 弹出元素
bool is_empty(); // 判断栈是否为空
void print(); // 打印栈内容
private:
static const int MAXSIZE = 100; // 栈最大容量
int data[MAXSIZE]; // 栈数据
int top; // 栈顶索引
};
其中,push
方法的实现:
void Stack::push(int data) {
if (top >= MAXSIZE - 1) { // 栈满
cout << "Stack is full!" << endl;
return;
}
data[++top] = data;
}
pop
方法的实现:
int Stack::pop() {
if (top < 0) { // 栈空
cout << "Stack is empty!" << endl;
return -1;
}
return data[top--];
}
4. 队列的实现
队列(Queue)是一种基于先进先出(FIFO)的数据结构,其核心操作是入队(enqueue)和出队(dequeue):
- 入队:将元素加入队尾
- 出队:取出队头元素
以下是队列的核心代码:
// 队列类
class Queue {
public:
Queue(): front(0), rear(0) {}
void enqueue(int data); // 入队
int dequeue(); // 出队
bool is_empty(); // 判断队列是否为空
void print(); // 打印队列内容
private:
static const int MAXSIZE = 100; // 队列最大容量
int data[MAXSIZE]; // 队列数据
int front; // 队头索引
int rear; // 队尾索引
};
其中,enqueue
方法的实现:
void Queue::enqueue(int data) {
if ((rear + 1) % MAXSIZE == front) { // 队列已满
cout << "Queue is full!" << endl;
return;
}
data[rear] = data; // 将数据放到队尾
rear = (rear + 1) % MAXSIZE; // 更新尾指针
}
dequeue
方法的实现:
int Queue::dequeue() {
if (front == rear) { // 队列为空
cout << "Queue is empty!" << endl;
return -1;
}
int res = data[front]; // 取出队头元素
front = (front + 1) % MAXSIZE; // 更新头指针
return res;
}
5. 示例说明
以下是一个示例程序,分别展示了单链表、双链表、栈和队列的基本操作:
int main() {
// 单链表示例
LinkedList ll;
ll.add_front(1);
ll.add_front(2);
ll.add_back(3);
ll.add_back(4);
ll.print();
ll.remove(2);
ll.print();
// 双链表示例
DoublyLinkedList dll;
dll.add_front(1);
dll.add_front(2);
dll.add_back(3);
dll.add_back(4);
dll.print();
dll.remove(2);
dll.print();
// 栈示例
Stack s;
s.push(1);
s.push(2);
s.push(3);
s.print();
s.pop();
s.print();
// 队列示例
Queue q;
q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
q.print();
q.dequeue();
q.print();
return 0;
}
以上程序将输出以下结果:
2 -> 1 -> 3 -> 4
1 -> 3 -> 4
2 -> 1 -> 3 -> 4
1 -> 3 -> 4
3 -> 2 -> 1
3 -> 1
3 2 1
2 1
1 -> 2 -> 3
2 -> 3
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:C++数组模拟之单链表与双链表和栈和队列的实现过程 - Python技术站