河南省台前县建设局网站,摄影网站网络促销方式,山西网站建设开发团队,静态网页制作期末试卷及答案知识导图： 一、数据结构 包含：线性表（数组、队列、链表、栈）、散列表、树（二叉树、多路查找树）、图
1.线性表 数据之间就是“一对一“的逻辑关系。 线性表存储数据的实现方案有两种，分别是顺序存储结构和链式存储结构。 包含：数组、队列、链表、栈。
1.1 数组…知识导图： 一、数据结构
包含：线性表（数组、队列、链表、栈）、散列表、树（二叉树、多路查找树）、图
1.线性表
数据之间就是“一对一“的逻辑关系。 线性表存储数据的实现方案有两种，分别是顺序存储结构和链式存储结构。 包含：数组、队列、链表、栈。
1.1 数组：
连续内存存储。简单，此处不多介绍。
1.2 队列：
可以通过数组+前后索引实现，也可以通过链表+前后指针实现。
queue： 1）通过数组+前后索引实现
#include iostream
#include stdexcepttemplate typename T, int capacity
class Queue {
private:T arr[capacity];int front; // 队头索引int rear; // 队尾索引int size; // 当前队列中的元素数量public:Queue() : front(0), rear(0), size(0) {}// 判断队列是否为空bool isEmpty() const {return size == 0;}// 判断队列是否已满bool isFull() const {return size == capacity;}// 入队操作void enqueue(const T value) {if (isFull()) {throw std::overflow_error("Queue is full");}arr[rear] = value;rear = (rear + 1) % capacity; // 循环更新队尾索引++size;}// 出队操作T dequeue() {if (isEmpty()) {throw std::underflow_error("Queue is empty");}T value = arr[front];front = (front + 1) % capacity; // 循环更新队头索引--size;return value;}// 获取队头元素T getFront() const {if (isEmpty()) {throw std::underflow_error("Queue is empty");}return arr[front];}// 获取队列中的元素数量int getSize() const {return size;}
};int main() {Queueint, 5 queue;try {// 入队操作queue.enqueue(1);queue.enqueue(2);queue.enqueue(3);// 输出队头元素std::cout "Front element: " queue.getFront() std::endl;// 出队操作std::cout "Dequeued element: " queue.dequeue() std::endl;// 再次输出队头元素std::cout "Front element after dequeue: " queue.getFront() std::endl;// 输出队列中的元素数量std::cout "Queue size: " queue.getSize() std::endl;} catch (const std::exception e) {std::cerr "Exception: " e.what() std::endl;}return 0;
}2）通过链表+前后指针实现
#include iostream
#include stdexcept// 定义链表节点结构体
template typename T
struct Node {T data;NodeT* next;Node(const T value) : data(value), next(nullptr) {}
};// 定义队列类
template typename T
class Queue {
private:NodeT* front; // 队头指针NodeT* rear; // 队尾指针int size; // 当前队列中的元素数量public:// 构造函数Queue() : front(nullptr), rear(nullptr), size(0) {}// 析构函数~Queue() {while (!isEmpty()) {dequeue();}}// 判断队列是否为空bool isEmpty() const {return size == 0;}// 获取队列中的元素数量int getSize() const {return size;}// 入队操作void enqueue(const T value) {NodeT* newNode = new NodeT(value);if (isEmpty()) {front = rear = newNode;} else {rear-next = newNode;rear = newNode;}++size;}// 出队操作T dequeue() {if (isEmpty()) {throw std::underflow_error("Queue is empty");}T value = front-data;NodeT* temp = front;front = front-next;if (front == nullptr) {rear = nullptr;}delete temp;--size;return value;}// 获取队头元素T getFront() const {if (isEmpty()) {throw std::underflow_error("Queue is empty");}return front-data;}
};int main() {Queueint queue;try {// 入队操作queue.enqueue(1);queue.enqueue(2);queue.enqueue(3);// 输出队头元素std::cout "Front element: " queue.getFront() std::endl;// 出队操作std::cout "Dequeued element: " queue.dequeue() std::endl;// 再次输出队头元素std::cout "Front element after dequeue: " queue.getFront() std::endl;// 输出队列中的元素数量std::cout "Queue size: " queue.getSize() std::endl;} catch (const std::exception e) {std::cerr "Exception: " e.what() std::endl;}return 0;
}双端队列Deque： 允许你从队列的两端进行元素的插入和删除操作，既可以在头部进行操作，也可以在尾部进行操作。
1）通过数组+前后索引实现
#include iostream
#include stdexcepttemplate typename T, int capacity
class ArrayDeque {
private:T arr[capacity];int front;int rear;int size;public:ArrayDeque() : front(0), rear(0), size(0) {}// 判断队列是否为空bool isEmpty() const {return size == 0;}// 判断队列是否已满bool isFull() const {return size == capacity;}// 在队头插入元素void insertFront(const T value) {if (isFull()) {throw std::overflow_error("Deque is full");}front = (front - 1 + capacity) % capacity;arr[front] = value;++size;}// 在队尾插入元素void insertRear(const T value) {if (isFull()) {throw std::overflow_error("Deque is full");}arr[rear] = value;rear = (rear + 1) % capacity;++size;}// 从队头删除元素T deleteFront() {if (isEmpty()) {throw std::underflow_error("Deque is empty");}T value = arr[front];front = (front + 1) % capacity;--size;return value;}// 从队尾删除元素T deleteRear() {if (isEmpty()) {throw std::underflow_error("Deque is empty");}rear = (rear - 1 + capacity) % capacity;T value = arr[rear];--size;return value;}// 获取队头元素T getFront() const {if (isEmpty()) {throw std::underflow_error("Deque is empty");}return arr[front];}// 获取队尾元素T getRear() const {if (isEmpty()) {throw std::underflow_error("Deque is empty");}return arr[(rear - 1 + capacity) % capacity];}// 获取队列中的元素数量int getSize() const {return size;}
};int main() {ArrayDequeint, 5 deque;try {deque.insertFront(1);deque.insertRear(2);std::cout "Front element: " deque.getFront() std::endl;std::cout "Rear element: " deque.getRear() std::endl;deque.deleteFront();std::cout "Front element after deleteFront: " deque.getFront() std::endl;deque.deleteRear();std::cout "Is deque empty after deletions? " (deque.isEmpty() ? "Yes" : "No") std::endl;} catch (const std::exception e) {std::cerr "Exception: " e.what() std::endl;}return 0;
}2）通过链表+前后指针实现
#include iostream
#include stdexcept// 定义链表节点结构体
template typename T
struct Node {T data;NodeT* prev;NodeT* next;Node(const T value) : data(value), prev(nullptr), next(nullptr) {}
};template typename T
class LinkedDeque {
private:NodeT* front;NodeT* rear;int size;public:LinkedDeque() : front(nullptr), rear(nullptr), size(0) {}~LinkedDeque() {while (!isEmpty()) {deleteFront();}}// 判断队列是否为空bool isEmpty() const {return size == 0;}// 在队头插入元素void insertFront(const T value) {NodeT* newNode = new NodeT(value);if (isEmpty()) {front = rear = newNode;} else {newNode-next = front;front-prev = newNode;front = newNode;}++size;}// 在队尾插入元素void insertRear(const T value) {NodeT* newNode = new NodeT(value);if (isEmpty()) {front = rear = newNode;} else {newNode-prev = rear;rear-next = newNode;rear = newNode;}++size;}// 从队头删除元素T deleteFront() {if (isEmpty()) {throw std::underflow_error("Deque is empty");}T value = front-data;NodeT* temp = front;front = front-next;if (front == nullptr) {rear = nullptr;} else {front-prev = nullptr;}delete temp;--size;return value;}// 从队尾删除元素T deleteRear() {if (isEmpty()) {throw std::underflow_error("Deque is empty");}T value = rear-data;NodeT* temp = rear;rear = rear-prev;if (rear == nullptr) {front = nullptr;} else {rear-next = nullptr;}delete temp;--size;return value;}// 获取队头元素T getFront() const {if (isEmpty()) {throw std::underflow_error("Deque is empty");}return front-data;}// 获取队尾元素T getRear() const {if (isEmpty()) {throw std::underflow_error("Deque is empty");}return rear-data;}// 获取队列中的元素数量int getSize() const {return size;}
};int main() {LinkedDequeint deque;try {deque.insertFront(1);deque.insertRear(2);std::cout "Front element: " deque.getFront() std::endl;std::cout "Rear element: " deque.getRear() std::endl;deque.deleteFront();std::cout "Front element after deleteFront: " deque.getFront() std::endl;deque.deleteRear();std::cout "Is deque empty after deletions? " (deque.isEmpty() ? "Yes" : "No") std::endl;} catch (const std::exception e) {std::cerr "Exception: " e.what() std::endl;}return 0;
}1.3 链表：
和顺序表不同，使用链表存储数据，不强制要求数据在内存中集中存储，各个元素可以分散存储在内存中。链表存储数据间逻辑关系的实现方案是：为每一个元素配置一个指针，每个元素的指针都指向自己的直接后继元素。
单向链表：
#include iostreamstruct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}
};class LinkedList {
private:ListNode* head;public:LinkedList() : head(nullptr) {}void insertAtHead(int val) {ListNode* newNode = new ListNode(val);newNode-next = head;head = newNode;}void insertAtTail(int val) {ListNode* newNode = new ListNode(val);if (head == nullptr) {head = newNode;return;}ListNode* curr = head;while (curr-next!= nullptr) {curr = curr-next;}curr-next = newNode;}void deleteAtHead() {if (head == nullptr) {std::cout "链表为空，无法删除" std::endl;return;}ListNode* temp = head;head = head-next;delete temp;}void deleteAtTail() {if (head == nullptr) {std::cout "链表为空，无法删除" std::endl;return;}if (head-next == nullptr) {delete head;head = nullptr;return;}ListNode* curr = head;while (curr-next-next!= nullptr) {curr = curr-next;}delete curr-next;curr-next = nullptr;}void printList() {ListNode* curr = head;while (curr!= nullptr) {std::cout curr-val " ";curr = curr-next;}std::cout std::endl;}// 查找元素是否存在bool search(int val) {ListNode* curr = head;while (curr!= nullptr) {if (curr-val == val) {return true;}curr = curr-next;}return false;}
};int main() {LinkedList list;list.insertAtHead(3);list.insertAtHead(2);list.insertAtHead(1);std::cout "插入头部后的链表: ";list.printList();list.insertAtTail(4);list.insertAtTail(5);std::cout "插入尾部后的链表: ";list.printList();list.deleteAtHead();std::cout "删除头部节点后的链表: ";list.printList();list.deleteAtTail();std::cout "删除尾部节点后的链表: ";list.printList();if (list.search(3)) {std::cout "元素 3 存在于链表中" std::endl;} else {std::cout "元素 3 不存在于链表中" std::endl;}return 0;
}双向链表：
“双向”指的是各节点之间的逻辑关系是双向的，头指针通常只设置一个。
#include iostream// 定义双向链表节点结构体
struct ListNode {int val;ListNode* prev;ListNode* next;ListNode(int x) : val(x), prev(nullptr), next(nullptr) {}
};// 双向链表类
class DoublyLinkedList {
private:ListNode* head;ListNode* tail;public:DoublyLinkedList() : head(nullptr), tail(nullptr) {}// 插入节点到链表头部void insertAtHead(int val) {ListNode* newNode = new ListNode(val);if (head == nullptr) {head = newNode;tail = newNode;} else {newNode-next = head;head-prev = newNode;head = newNode;}}// 插入节点到链表尾部void insertAtTail(int val) {ListNode* newNode = new ListNode(val);if (tail == nullptr) {head = newNode;tail = newNode;} else {newNode-prev = tail;tail-next = newNode;tail = newNode;}}// 删除头部节点void deleteAtHead() {if (head == nullptr) {std::cout "链表为空，无法删除" std::endl;return;}ListNode* temp = head;if (head == tail) {head = nullptr;tail = nullptr;} else {head = head-next;head-prev = nullptr;}delete temp;}// 删除尾部节点void deleteAtTail() {if (tail == nullptr) {std::cout "链表为空，无法删除" std::endl;return;}ListNode* temp = tail;if (head == tail) {head = nullptr;tail = nullptr;} else {tail = tail-prev;tail-next = nullptr;}delete temp;}// 打印链表元素（从头到尾）void printList() {ListNode* curr = head;while (curr!= nullptr) {std::cout curr-val " ";curr = curr-next;}std::cout std::endl;}// 打印链表元素（从尾到头）void printListReverse() {ListNode* curr = tail;while (curr!= nullptr) {std::cout curr-val " ";curr = curr-prev;}std::cout std::endl;}
};int main() {DoublyLinkedList list;list.insertAtHead(3);list.insertAtHead(2);list.insertAtHead(1);std::cout "插入头部后的链表: ";list.printList();list.insertAtTail(4);list.insertAtTail(5);std::cout "插入尾部后的链表: ";list.printList();list.deleteAtHead();std::cout "删除头部节点后的链表: ";list.printList();list.deleteAtTail();std::cout "删除尾部节点后的链表: ";list.printList();std::cout "从尾到头打印链表: ";list.printListReverse();return 0;
}单向循环链表与双向循环链表： 单链表通过首尾连接可以构成单向循环链表： 双向链表也可以进行首尾连接，构成双向循环链表：
静态链表： 用静态链表存储数据，数据全部存储在数组中（和顺序表一样），但存储位置是随机的，数据之间"一对一"的逻辑关系通过一个整形变量（称为"游标"，和指针功能类似）维持（和链表类似）。 在静态链表中，数组的每个元素代表一个链表节点，每个节点通常包含两部分：
数据域：存储节点的数据。游标域（或指针域）：存储下一个节点在数组中的索引，而不是像动态链表那样存储一个物理地址。1.4 栈
栈是一种后进先出的数据结构。
#include iostream
#include vectorclass ArrayStack {
private:std::vectorint data; // 存储元素的数组
public:// 入栈操作void push(int value) {
//使用 data.push_back(value) 将元素添加到 data 的末尾，实现入栈操作。data.push_back(value);}// 出栈操作int pop() {if (isEmpty()) {throw s
