AcWing算法提高课笔记

**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;
 }
 }