AcWing算法提高课笔记
发布人:shili8
发布时间:2025-02-17 06:48
阅读次数:0
**AcWing算法提高课笔记**
### 一、前言本课程旨在帮助学生掌握算法设计和实现的基本技能,涵盖了常见的算法思想和数据结构。通过学习本课程,学生将能够解决各种类型的问题,并且能够编写高效的代码。
### 二、数组和链表####2.1 数组数组是最基本的线性数据结构,它由一系列相同类型的元素组成。每个元素都有一个唯一的索引或下标。
**例题:**
* **查找最大值**: 给定一个整数数组,找到其中最大值。
cpp#include <iostream> using namespace std; int findMax(int arr[], int n) { int max = arr[0]; for (int i =1; i < n; i++) { if (arr[i] > max) { max = arr[i]; } } return max; } int main() { int arr[] = {3,5,2,7,9}; int n = sizeof(arr) / sizeof(arr[0]); cout << "最大值为:" << findMax(arr, n); return0; }
* **查找最小值**: 给定一个整数数组,找到其中最小值。
cpp#include <iostream> using namespace std; int findMin(int arr[], int n) { int min = arr[0]; for (int i =1; i < n; i++) { if (arr[i] < min) { min = arr[i]; } } return min; } int main() { int arr[] = {3,5,2,7,9}; int n = sizeof(arr) / sizeof(arr[0]); cout << "最小值为:" << findMin(arr, n); return0; }
####2.2 链表链表是线性数据结构的一种,它由一系列的结点组成,每个结点包含一个元素和一个指向下一个结点的引用。
**例题:**
* **创建链表**: 创建一个链表,插入元素。
cpp#include <iostream> using namespace std; struct Node { int data; Node* next; }; class LinkedList { public: Node* head; void insert(int data) { Node* newNode = new Node(); newNode->data = data; newNode->next = nullptr; if (head == nullptr) { head = newNode; } else { Node* current = head; while (current->next != nullptr) { current = current->next; } current->next = newNode; } } void printList() { Node* current = head; while (current != nullptr) { cout << current->data << " "; current = current->next; } cout << endl; } }; int main() { LinkedList list; list.insert(1); list.insert(2); list.insert(3); list.printList(); return0; }
### 三、栈和队列####3.1 栈栈是一种后进先出的数据结构,它遵循 LIFO(Last In First Out)原则。
**例题:**
* **实现栈**: 实现一个栈,支持 push 和 pop 操作。
cpp#include <iostream> using namespace std; class Stack { private: int* arr; int top; int capacity; public: Stack(int capacity) { this->capacity = capacity; arr = new int[capacity]; top = -1; } void push(int data) { if (top < capacity -1) { arr[++top] = data; } else { cout << "Stack is full." << endl; } } int pop() { if (top >=0) { return arr[top--]; } else { cout << "Stack is empty." << endl; return -1; // Return a sentinel value to indicate an error } } void printStack() { for (int i = top; i >=0; i--) { cout << arr[i] << " "; } cout << endl; } }; int main() { Stack stack(5); stack.push(1); stack.push(2); stack.push(3); stack.printStack(); cout << "Popped element: " << stack.pop() << endl; return0; }
####3.2 队列队列是一种先进先出的数据结构,它遵循 FIFO(First In First Out)原则。
**例题:**
* **实现队列**: 实现一个队列,支持 enqueue 和 dequeue 操作。
cpp#include <iostream> using namespace std; class Queue { private: int* arr; int front; int rear; int capacity; public: Queue(int capacity) { this->capacity = capacity; arr = new int[capacity]; front =0; rear = -1; } void enqueue(int data) { if (rear < capacity -1) { arr[++rear] = data; } else { cout << "Queue is full." << endl; } } int dequeue() { if (front <= rear) { return arr[front++]; } else { cout << "Queue is empty." << endl; return -1; // Return a sentinel value to indicate an error } } void printQueue() { for (int i = front; i <= rear; i++) { cout << arr[i] << " "; } cout << endl; } }; int main() { Queue queue(5); queue.enqueue(1); queue.enqueue(2); queue.enqueue(3); queue.printQueue(); cout << "Dequeued element: " << queue.dequeue() << endl; return0; }
### 四、树和图####4.1 树树是一种非线性数据结构,它由一系列的结点组成,每个结点包含一个元素和零到多个子结点。
**例题:**
* **创建二叉树**: 创建一个二叉树,插入元素。
cpp#include <iostream> using namespace std; struct Node { int data; Node* left; Node* right; }; class BinaryTree { public: Node* root; void insert(int data) { Node* newNode = new Node(); newNode->data = data; newNode->left = nullptr; newNode->right = nullptr; if (root == nullptr) { root = newNode; } else { Node* current = root; while (true) { if (data < current->data) { if (current->left == nullptr) { current->left = newNode; break; } current = current->left; } else { if (current->right == nullptr) { current->right = newNode; break; } current = current->right; } } } } void printTree() { if (root != nullptr) { printTree(root); } } void printTree(Node* node) { if (node == nullptr) return; cout << node->data << " "; printTree(node->left); printTree(node->right); } }; int main() { BinaryTree tree; tree.insert(5); tree.insert(3); tree.insert(7); tree.printTree(); return0; }
####4.2 图图是一种非线性数据结构,它由一系列的结点组成,每个结点包含一个元素和零到多个邻接结点。
**例题:**
* **创建有向图**: 创建一个有向图,插入边。
cpp#include <iostream> using namespace std; struct Node { int data; vector<Node*> neighbors; }; class Graph { public: Node* nodes[10]; void addEdge(int u, int v) { if (u >=0 && u < 10 && v >=0 && v < 10) { nodes[u]->neighbors.push_back(nodes[v]); nodes[v]->neighbors.push_back(nodes[u]); // For undirected graph } } void printGraph() { for (int i =0; i < 10; i++) { cout << "Node " << i << ": "; for (auto neighbor : nodes[i]->neighbors) { cout << neighbor->data << " "; } cout << endl; } } void initGraph() { for (int i =0; i < 10; i++) { Node* node = new Node(); node->data = i; nodes[i] = node; } }