【精选】算法设计与分析（第一章概述知识点）

命运之光

发布于 2024-03-20 13:50:32

1210

发布于 2024-03-20 13:50:32

文章被收录于专栏：我在本科期间写的文章

前言

总结算法设计与分析课程期末必记知识点。

第一章概述

1、渐进符号

紧凑上界记号：O 紧凑下界符号：Ω 渐进紧确界记号：Θ

2、求解梵塔问题的递归算法

void Hanoi(int n,char x,char y,char z){
	if(n==1)
		printf("将盘片%d从%c搬到%c\n",n,x,z);
	else
	{
		Hanoi(n-1,x,z,y);
		printf("将盘片%d从%c搬到%c\n",n,x,z);
		Hanoi(n-1,y,x,z);
	 } 
}

时间复杂度为

3、二路归并的递归算法

void mergesort(int a[],int i,int j){
	int mid;
	if(i!=j){
		mid=(i+j)/2;
		mergesort(a,i,mid);
		mergesort(a,mid+1,j);
		merge(a,i,j,mid);
	}
}

时间复杂度为

4、STL概述

STL主要由容器、算法和迭代器三大部分构成

5、STL容器

基础容器

向量
字符串
双端队列
链表

适配器容器

栈
队列
优先队列

在使用STL时必须加入

using namespace std;

5、STL算法

STL算法部分主要由头文件为 <algorithm> , <numeric> 和 <functional> 组成。

6、STL迭代器

每个容器都有自己的迭代器

7、常用的STL容器（没时间可以看一个大概）

（一）顺序容器

vector（向量容器）

begin：得到数组头的指针
end：得到数组的最后一个单元+1的指针
rbegin：将vector反转后的开始指针返回(其实就是原来的end-1)
front ：获取当前容器的第一个元素
push_back：在数组的最后添加一个数据
insert(pos,elem)：在pos位置插入一个elem拷贝
erase：删除指针指向的数据

string字符串容器（直接看例子）

void main(){
	string s1="",s2,s3="Bye";
	s1.append("Good morning");
	s2=s1;
	int i=s2.find("morning");
	s2.replace(i,s2.length()-i,s3);
	cout<<"s1: "<<s1<<endl;
	cout<<"s2: "<<s2<<endl;
}

deque（双端队列容器）

#include <iostream>
#include <deque>

int main() {
    // 创建一个双端队列对象
    std::deque<int> myDeque;

    // 在队列前面添加元素
    myDeque.push_front(10);
    myDeque.push_front(20);
    myDeque.push_front(30);

    // 在队列后面添加元素
    myDeque.push_back(40);
    myDeque.push_back(50);
    myDeque.push_back(60);

    // 使用迭代器遍历双端队列并打印元素
    std::cout << "双端队列中的元素: ";
    for(auto it = myDeque.begin(); it != myDeque.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 访问队列的第一个和最后一个元素
    std::cout << "队列的第一个元素: " << myDeque.front() << std::endl;
    std::cout << "队列的最后一个元素: " << myDeque.back() << std::endl;

    // 删除队列的第一个和最后一个元素
    myDeque.pop_front();
    myDeque.pop_back();

    // 使用范围循环遍历双端队列并打印元素
    std::cout << "删除第一个和最后一个元素后的双端队列中的元素: ";
    for(auto elem : myDeque) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // 清空队列
    myDeque.clear();

    // 检查队列是否为空
    if(myDeque.empty()) {
        std::cout << "双端队列为空" << std::endl;
    } else {
        std::cout << "双端队列不为空" << std::endl;
    }

    return 0;
}

list（链表容器）

#include <iostream>
#include <list>

int main() {
    // 创建一个链表对象
    std::list<int> myList;

    // 在链表末尾添加元素
    myList.push_back(10);
    myList.push_back(20);
    myList.push_back(30);

    // 在链表开头添加元素
    myList.push_front(5);
    myList.push_front(15);

    // 使用迭代器遍历链表并打印元素
    std::cout << "链表中的元素: ";
    for(auto it = myList.begin(); it != myList.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 访问链表的第一个和最后一个元素
    std::cout << "链表的第一个元素: " << myList.front() << std::endl;
    std::cout << "链表的最后一个元素: " << myList.back() << std::endl;

    // 删除链表的第一个和最后一个元素
    myList.pop_front();
    myList.pop_back();

    // 使用范围循环遍历链表并打印元素
    std::cout << "删除第一个和最后一个元素后的链表中的元素: ";
    for(auto elem : myList) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // 在链表中间插入元素
    auto it = std::find(myList.begin(), myList.end(), 20);
    if (it != myList.end()) {
        myList.insert(it, 25);
    }

    // 删除链表中的特定元素
    myList.remove(15);

    // 清空链表
    myList.clear();

    // 检查链表是否为空
    if(myList.empty()) {
        std::cout << "链表为空" << std::endl;
    } else {
        std::cout << "链表不为空" << std::endl;
    }

    return 0;
}

（二）关联容器

set（集合容器）/multiset（多重集合容器）

#include <iostream>
#include <set>

int main() {
    // 创建一个集合对象
    std::set<int> mySet;

    // 向集合中插入元素
    mySet.insert(10);
    mySet.insert(20);
    mySet.insert(30);
    mySet.insert(40);

    // 使用迭代器遍历集合并打印元素
    std::cout << "集合中的元素: ";
    for(auto it = mySet.begin(); it != mySet.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 检查集合中是否包含某个元素
    if(mySet.count(20) > 0) {
        std::cout << "集合中包含元素 20" << std::endl;
    } else {
        std::cout << "集合中不包含元素 20" << std::endl;
    }

    // 删除集合中的某个元素
    mySet.erase(30);

    // 使用范围循环遍历集合并打印元素
    std::cout << "删除元素 30 后的集合中的元素: ";
    for(auto elem : mySet) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // 创建一个多重集合对象
    std::multiset<int> myMultiset;

    // 向多重集合中插入元素
    myMultiset.insert(10);
    myMultiset.insert(20);
    myMultiset.insert(30);
    myMultiset.insert(30);
    myMultiset.insert(40);

    // 使用迭代器遍历多重集合并打印元素
    std::cout << "多重集合中的元素: ";
    for(auto it = myMultiset.begin(); it != myMultiset.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 获取多重集合中某个元素的个数
    int count = myMultiset.count(30);
    std::cout << "元素 30 在多重集合中出现的次数: " << count << std::endl;

    // 删除多重集合中的所有某个元素
    myMultiset.erase(30);

    // 使用范围循环遍历多重集合并打印元素
    std::cout << "删除所有元素 30 后的多重集合中的元素: ";
    for(auto elem : myMultiset) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

map（映射容器）/multimap（多重映射容器）

#include <iostream>
#include <map>

int main() {
    // 创建一个映射对象
    std::map<std::string, int> myMap;

    // 向映射中插入键值对
    myMap["Alice"] = 25;
    myMap["Bob"] = 30;
    myMap["Carol"] = 35;

    // 使用迭代器遍历映射并打印键值对
    std::cout << "映射中的键值对: " << std::endl;
    for(auto it = myMap.begin(); it != myMap.end(); ++it) {
        std::cout << it->first << " : " << it->second << std::endl;
    }

    // 检查映射中是否包含某个键
    if(myMap.count("Bob") > 0) {
        std::cout << "映射中包含键 Bob" << std::endl;
    } else {
        std::cout << "映射中不包含键 Bob" << std::endl;
    }

    // 删除映射中的某个键值对
    myMap.erase("Bob");

    // 使用范围循环遍历映射并打印键值对
    std::cout << "删除键 Bob 后的映射中的键值对: " << std::endl;
    for(const auto& pair : myMap) {
        std::cout << pair.first << " : " << pair.second << std::endl;
    }

    // 创建一个多重映射对象
    std::multimap<std::string, std::string> myMultiMap;

    // 向多重映射中插入键值对
    myMultiMap.insert(std::make_pair("fruit", "apple"));
    myMultiMap.insert(std::make_pair("fruit", "banana"));
    myMultiMap.insert(std::make_pair("vegetable", "carrot"));
    myMultiMap.insert(std::make_pair("vegetable", "potato"));

    // 使用迭代器遍历多重映射并打印键值对
    std::cout << "多重映射中的键值对: " << std::endl;
    for(auto it = myMultiMap.begin(); it != myMultiMap.end(); ++it) {
        std::cout << it->first << " : " << it->second << std::endl;
    }

    // 获取多重映射中某个键对应的所有值
    std::string key = "fruit";
    auto range = myMultiMap.equal_range(key);
    std::cout << "键为 " << key << " 的值有: ";
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << it->second << " ";
    }
    std::cout << std::endl;

    return 0;
}

（三）适配器容器

指基于其他容器实现的容器

stack（栈容器）

#include <iostream>
#include <stack>

int main() {
    // 创建一个栈对象
    std::stack<int> myStack;

    // 向栈中压入元素
    myStack.push(10);
    myStack.push(20);
    myStack.push(30);

    // 查看栈顶元素并弹出它
    int topElement = myStack.top();
    myStack.pop();

    std::cout << "栈顶元素为 " << topElement << std::endl;

    // 检查栈是否为空
    if(myStack.empty()) {
        std::cout << "栈为空" << std::endl;
    } else {
        std::cout << "栈不为空" << std::endl;
    }

    // 使用范围循环遍历栈并打印元素
    std::cout << "栈中的元素: ";
    for(auto elem : myStack) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // 获取栈中的元素个数
    int size = myStack.size();
    std::cout << "栈中的元素个数为 " << size << std::endl;

    return 0;
}

queue（队列容器）

#include <iostream>
#include <queue>

int main() {
    // 创建一个队列对象
    std::queue<int> myQueue;

    // 向队列中插入元素
    myQueue.push(10);
    myQueue.push(20);
    myQueue.push(30);

    // 访问队首元素并弹出它
    int frontElement = myQueue.front();
    myQueue.pop();

    std::cout << "队首元素为 " << frontElement << std::endl;

    // 检查队列是否为空
    if(myQueue.empty()) {
        std::cout << "队列为空" << std::endl;
    } else {
        std::cout << "队列不为空" << std::endl;
    }

    // 使用范围循环遍历队列并打印元素
    std::cout << "队列中的元素: ";
    while(!myQueue.empty()) {
        std::cout << myQueue.front() << " ";
        myQueue.pop();
    }
    std::cout << std::endl;

    // 获取队列中的元素个数
    int size = myQueue.size();
    std::cout << "队列中的元素个数为 " << size << std::endl;

    return 0;
}

priority_queue（优先队列容器）

#include <iostream>
#include <queue>

int main() {
    // 创建一个优先队列对象，默认情况下是最大堆
    std::priority_queue<int> myPriorityQueue;

    // 向优先队列中插入元素
    myPriorityQueue.push(30);
    myPriorityQueue.push(10);
    myPriorityQueue.push(20);

    // 访问队顶元素并弹出它
    int topElement = myPriorityQueue.top();
    myPriorityQueue.pop();

    std::cout << "队顶元素为 " << topElement << std::endl;

    // 使用范围循环遍历优先队列并打印元素
    std::cout << "优先队列中的元素: ";
    while(!myPriorityQueue.empty()) {
        std::cout << myPriorityQueue.top() << " ";
        myPriorityQueue.pop();
    }
    std::cout << std::endl;

    // 创建一个小顶堆的优先队列
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

    // 向小顶堆中插入元素
    minHeap.push(30);
    minHeap.push(10);
    minHeap.push(20);

    // 使用范围循环遍历小顶堆并打印元素
    std::cout << "小顶堆中的元素: ";
    while(!minHeap.empty()) {
        std::cout << minHeap.top() << " ";
        minHeap.pop();
    }
    std::cout << std::endl;

    return 0;
}