南山最专业的网站建设,公司网站建设公司,展示型网站建设公司,南昌网站建设公司网站建设公司哪家好文章目录零、绪论和IDE安装int取值范围常犯的编程小错误一、枚举和模拟 (暴力求解)(一) 枚举1.Reverse函数 求 反序数2.程序出错的原因1.编译错误 (compile)#xff1a;基本语法错误2.链接错误 (link)#xff1a;函数名写错了3.运行错误 (run)#xff1a;结果与预期不符基本语法错误2.链接错误 (link)函数名写错了3.运行错误 (run)结果与预期不符断点调试 [打断点看监视]3.编程规范1.判断时固定值写左边2.不要省略大括号4.命名规范1.变量命名规范(二) 模拟Ⅰ.图案问题二维数组 找数字规律1.不确定数量的输入 while(scanf(%d,n) ! EOF){ }2.作用域3.机试对字符串的处理1.处理输入、输出C风格字符串(字符数组)char str[1000]2.处理更复杂问题C风格字符串string4.二维数组5.OJ问题Ⅱ.日期问题1.闰年问题2.用空间换时间3.打印日期用printf比cout方便4.map 映射Ⅲ.其他模拟问题二、排序与查找(一) 排序1.sort函数sort(first,last,comp)2.C语言数组3.设计排序的规则设计比较和交换的条件4.C函数重载同一个函数名有不同的参数列表5.机试考试最重要的事情能把你曾经做过的题目满分地做出来(二) 查找1.顺序查找(Liner Search)时间复杂度、空间复杂度2.二分查找(Binary Search)3.用map解决查找问题指针迭代器 iterator三、字符串C字符数组:char arr[100] —— 输入输出C字符串string —— 其他复杂操作四、线性数据结构1.向量 vector2.队列 queue3.栈 stack五、递归与分治递归与分治的关系(一)、递归函数递归(二)、分治六、非线性数据结构内存空间栈堆 (自由存储区)指针和引用指针间接访问 值传递引用引用传递1.二叉树二叉树的遍历层次遍历队列递归遍历前中后序遍历重建二叉树并遍历2.二叉排序树 BST3.优先队列 priority_queue堆 heap堆优先队列模板 STL-priority_queue优先队列的应用1.顺序问题运算符重载2.哈夫曼树4.散列表 map映射 mapunorder_map七、搜索BFS 广度优先搜索打表DFS 深度优先搜索剪枝算法零、绪论和IDE安装
1.安装IDEclion或vs 新手不要直接在clion上写代码要在强大的IDE(集成开发环境)中练习能方便的找出低级错误。 在IDE上通过后再把代码复制到OJ中。
2.OJ的运行原理OJ不会直接评判代码而是用测试用例来测试你的输出结果是否与它的答案相符。如此便能在某些情况下“作弊”。 若OJ中某个测试用例超时可以提前准备好答案以便通过用例。例如“打表”。
3.机试需要的函数输入(scanf 或 cin)、输出(printf 或 cout)、读取一行(fgets 或 cin.getline) 机试考察的数据结构数组、链表、二叉树 机试需要的算法枚举、模拟、递归、分治、搜索 会50%、会70%和会90%都是零分。要会就要100%会。要么满分要么零分 练精一道题胜于浅尝辄止10道题 int取值范围
int的取值范围为-231 -231-1 ,即-2147483648 - 2147483647 注意题目要求的n的范围判断f(n)是否会超过int的取值范围。若超过则需要换成float或double或long long int或unsigned int。 常犯的编程小错误
1.问题等价条件判断是 写成了 情况不好定位。段错误且半天没看出问题逻辑都是对的。最后找助教才帮忙看出来花了十几分钟。尴尬。 解决遵守编程规范在写等价判断时值写在左边变量写在右边。 这样即使把写成了也会是编译错误直接报语法错误好定位。 一、枚举和模拟 (暴力求解)
(一) 枚举
循环 if printf
1.Reverse函数 求 反序数
int Reverse(int n){ //求反序数的Reverse函数int remain;//每次的余数int reverse 0;while(n ! 0){remain n%10;n n/10;reverse reverse*10 remain;}return reverse;
}2.程序出错的原因
前两步统称构建(build)
1.编译错误 (compile)基本语法错误
1.定位第一个编译错误根据行号、列号、提示去解决第一个编译错误。 编译错误只看第一个错误。因为解决一个问题可能就会解决一片编译错误。 2.链接错误 (link)函数名写错了
编译通过说明基本的语法没有错误。 链接错误并不提示链接错误的位置。一般就是函数名字写错了。 3.运行错误 (run)结果与预期不符断点调试 [打断点看监视]
运行时错误构建(build)成功即编译、链接都通过但结果与预期不符。 运行错误也不会提示哪里有问题这就需要通过打断点来进行断点调试了。 3.编程规范
1.判断时固定值写左边
防止 if(n0) 漏写为 if(n0)导致死循环。而且这不是编译错误检查不出来。 要写成if(0 n)把固定值写左边。这样如果漏写为 if( 0 n)是不符合语法的将错误提前到了编译阶段。 最简单的错误就是编译错误(语法错误) 2.不要省略大括号
虽然有些if里面只有一句话可以省略花括号。但是对于企业级的项目来说if里经常可能会添加新语句而忘记花括号。对于这种经常变动的代码务必全都加上大括号(即使只有一行)以防日后又增又删的调试。 即使你自己注意到了难免后续接手的程序员不会忘记if里又加了几行时忘记使用花括号而且这里加了没有调试最终bug花了半天时间才找到是因为这里if忘记加花括号了。 同时维护别人写的代码时也要注意在向单行循环体里加语句时检查它是否有大括号。 4.命名规范
1.变量命名规范
①外层循环使用不常见的变量名减少内外层冲突的可能性
②类名的首字母大写。类包括struct、class (二) 模拟
Ⅰ.图案问题二维数组 找数字规律 1.不确定数量的输入 while(scanf(“%d”,n) ! EOF){ }
//输入n然后输入n个数
int n;
int arr[101];
while (scanf(%d,n) ! EOF){for(int i0;in;i){scanf(%d,arr[i]);}
}注意输入一串数据后要先按Enter换行再按CrtlD。不换行则这一行数据没有输入缓冲区。 输入EOF ①clion/gcc/clungcrtld ②vscrtlc 2.作用域
放在花括号内部的变量生命周期只能在花括号里。 有时候有的变量需要设在全局或者函数外部才能被调用。 3.机试对字符串的处理
1.处理输入、输出C风格字符串(字符数组)char str[1000]
C风格的字符串本质是字符数组以\0结尾。
char str[1000];//初始化
scanf(%s,str);//输入(字符串的输出不需要加)
printf(%s\n,str);//输出易错%c注意要空格 2.处理更复杂问题C风格字符串string
#include string
using namespace std;①初始化string str1 hello; ②连接str1 str1 world; ③下标访问str1[0] //为h ④求长度str1.length() ⑤判断相等str1 hello ⑥比较字典序str1 abandon ⑦从C风格字符串转到C风格字符串str1.c_str() ⑧删除最后一个字符pop_back() 4.二维数组
char pat[80][80]{0};//定义二维数组并初始化长度固定5.OJ问题 Ⅱ.日期问题
1.闰年问题
bool isLeap (year%4000) || (year%100!0 year%40);//true是闰年2.用空间换时间
辅助数组
int mday[13] {0,31,28,31,30,31,30,31,31,30,31,30,31};3.打印日期用printf比cout方便
%d打印数字 %4d打印数字至少4个位置宽不足则用空格填充 %04d打印数字至少4个位置宽不足则用0填充 cout的运行效率、格式控制不如printf 4.map 映射
#include map
using namespace std;map举例
#include cstdio
#include string
#include map
using namespace std;int main(){//键 key -- 值 value//键的类型,值的类型mapstring,string myMap {{Caixukun,ikun},{Wuyifan,meigeni}};char str[1000];scanf(%s,str);string name str;printf(%s的粉丝被称为%s,name.c_str(),myMap[name].c_str());
}Ⅲ.其他模拟问题
1.剩余的树 2.手机键盘 二、排序与查找
(一) 排序
1.sort函数sort(first,last,comp)
C引入了基于快速排序的排序函数sort() sort(first,last,comp)函数的三个参数①first为待排序序列起始地址 ②last为结束地址 ③comp为排序方式不填写默认为升序排序。
#include algorithm
using namespace std;左闭右开 [arr,arrn)尾后 例1对n个数进行排序 样例输入 4 1 4 3 2 样例输出 1 2 3 4 #include cstdio
#include algorithm
using namespace std;int main(){int n;int arr[101];scanf(%d,n);for(int i0;in;i){scanf(%d,arr[i]);//arr[i] 和 arri 等价}sort(arr,arrn);//排序for(int i0;in;i){printf(%d ,arr[i]);}printf(\n);
}2.C语言数组
1.arr[i]是元素 2.arr是0号元素的地址。arri是i号元素的地址。 即C语言数组的数组名可以当地址/指针来使用。arr[i] 和 arri 等价 3.设计排序的规则设计比较和交换的条件
不发生交换返回真 4.C函数重载同一个函数名有不同的参数列表
比较的题目重点就是设计bool comp(int lhs,int rhs)函数。//不发生交换时为真 5.机试考试最重要的事情能把你曾经做过的题目满分地做出来
最重要的不是把所有题目都写了个差不多没用差一点就是零分。要么满分要么零分。 最重要的是把你曾经做过的题目满分地做出来。 泥鳅老师你就算是天纵奇才也不可能在机试的时候把你从来没做过的题目做出来。就是一个熟练度的问题。 (二) 查找
1.顺序查找(Liner Search)
顺序查找的问题效率不够高。 n个元素顺序查找时间复杂度为O(n²)。若数据量规模n在105则会OJ超时。需要采取一些策略降低时间复杂度。 时间复杂度、空间复杂度
0.O()计数法忽略常系数、忽略低阶项 1.时间复杂度指令执行次数 2.空间复杂度额外内存空间 2.二分查找(Binary Search)
要求先排序。数组有序后才可使用二分查找。 基于比较的排序时间复杂度最好为O(nlogn) 二分查找(需要排序)适用于给定一份数据要查很多次。 若每查一次数据都改那就用顺序查找不需要排序。
mid (left right)/2;
left mid 1; /收缩区间注意 1 -1避免二分查找死循环。
right mid - 1;3.用map解决查找问题
map的底层二叉搜索树(BST)。 ①在Windows下会进一步优化为平衡二叉树(AVL树) ②在Linux下会进一步优化为红黑树 指针迭代器 iterator
findIndex.begin()第一个元素的指针 findIndex.end()最后一个元素的后面一个位置的指针尾后指针 findIndex.find()查找某个元素的指针
if(findIndex.find(findNum) findIndex.end()) /说明没有找到三、字符串
C字符数组:char arr[100] —— 输入输出
1.字符数组 以 \0 作为正文结束的标志也占一个空间
2.输入输出效率 printf和scanf的效率要优于cin和cout
3.读取一整行 fgets(字符数组名,sizeof(字符数组名),stdin) fgets最后会读入换行符\n 占一个空间字符数组转string后考虑用pop_back()干掉回车
getchar() 吃掉回车 C字符串string —— 其他复杂操作
1.头文件
#include string
using namespace std;2.获取长度/大小 string str; str.length(); str.size();
printf(length of str %u\n,str.size());3.下标访问元素 str[i]i从0开始
for(unsigned int i 0;i str.size(); i){printf(%c\n,str[i]);
}4.(字符串的)迭代器访问元素
for(string::iterator it str.beign(); it ! str.end(); it){//it 更改迭代器的指向到下一个元素printf(%c\n, *it); // 取地址, *取内容
}5.连接字符串连接/拼接 (只针对C风格字符串string类型C风格字符数组禁止相加)
string str buf;
str str world;6.删除 erase(下标)
str.erase(str.size()-1); //删除最后一个元素即\n7.清空 clear()
str.clear();8.查询字符或字符子串的下标 .find(内容) ①find(字符串) ②find(变量名)
9.取字串 .substr(起始下标长度) 若要切到尾为止则只写一个参数起始下标不用写长度。
10.删除最后一个字符pop_back() 四、线性数据结构
1.当定义的数组特别大达到1千万时不能定义在函数内部会崩溃。栈比较小但快。 要定义在全局位置数据段中。 【局部大数组会崩溃全局大数组不会崩溃】
2.标准模板库STL 1.向量 vector
vector是动态数组长度可改变。 vectorint vec;//创建空向量长度为0 普通静态数组长度是固定不变的。int arr[100];//创建长度为100的静态数组
1.头文件
#include vector
using namespace std;2.声明向量
vectorint vec;//长度为03.赋初值
vectorint vec2 {1,2,3};4.申请一定空间的向量所有元素初值默认为0
vectorint vec3(10000);※5.尾部插入尾部扩容 push_back(元素) 。效率最高插入n个为O(n)插入1个为O(1)。
vec.push_back(1);//vec[0]1
vec.push_back(3);//vec[1]3※6.尾部删除弹出尾部元素 pop_back()
vec.pop_back();※7.下标访问
vec[i] //下标n时数组越界8.长度计算
vec.size();9.两种遍历方法 ①下标遍历
for(unsigned int i 0; i vec.size(); i){printf(vec[%d] %d\n,i,vec[i]);
}②迭代器遍历
for(vectorint::iterator it vec.begin(); it ! vec.end(); it){printf(vec[] %d\n,*it);
}10.随机位置的插入insert(位置元素)
vectorint::iterator it1 vec.begin()1;//迭代器指针指向vector的第二个位置
vec.insert(it13);//在vector第二个位置插入元素311.随机位置的删除erase(位置);
vec.erase(vec.begin());//删除vector的第一个位置的元素12.vector的实现原理 (1)vector的组成、申请空间(堆上) vector是类类型包括size容量、capacity内存大小、ptr首地址 首地址存放在栈上但vector申请的内存空间在堆区上堆区比栈区大因此vector可申请空间比静态数组在栈上申请的空间可以大很多。【静态数组 - 栈 - 小空间。 vector - 堆- 大空间】
(2)vector的扩容机制 2.队列 queue
队列queue是受限制的线性表。只能在队尾加入从队头入队。
1.头文件
#include queue
using namespace std;queueint myQueue;2.队尾入队 .push(变量名)
for(int i 0;i 5;i){myQueue.push(i);
}3.队头出队 .pop() 4.判空 .empty() 5.队首元素 .front() 3.栈 stack
操作受限的线性表只能一端进出。 栈禁止操作的一端称为盲端。允许元素插入和删除的一端称为栈顶。
1.头文件
#include stack
using namespace std;stacktypename myStack//定义2.方法 .size()栈大小 .push()压栈将元素加入栈中 .top()获取栈顶内容 .pop()弹栈 .empty()判断栈是否为空
3.栈的应用 (1)逆序输出 (2)括号匹配 (3)表达式求值 五、递归与分治
递归与分治的关系
分治是一种思想分而治之递归是一种实现方法函数调用自己。 分治思想可用递归来实现也可以用其他方法来实现。递归作为一种方法不止可以用于实现递归思想也可以用来实现其他思想。 但总的来说一般都用递归方法来实现分治的思想。故两者本不是同一纬度的概念但是经常放在一起谈论。
常见的分治求斐波那契数列、快速排序 常见的递归求n的阶乘 (一)、递归
从函数到递归
①大问题→小问题等价条件 ②确定最小问题即递归出口
函数
C语言编写的代码以函数定义为单位。
call把PC移到被调函数 ret把PC移回主调函数 递归
1.在函数定义中调用本函数叫做递归。
2.递归关注的两个点 ①大问题转化为小问题规模n→规模n-1 ②最小问题递归出口 例题1n的阶乘 例题2汉诺塔 (二)、分治
①分解大问题拆成小问题 ②治理找到等价条件解决递归出口(最小问题) ③合并 例题1斐波那契数列 例题网址http://t.cn/Ai0K3tU5 题解
#include cstdioint Fabonacci(int n){if(0n || 1n){return n;}else{return Fabonacci(n-1) Fabonacci(n-2);}
}int main(){int n;while(scanf(%d,n) ! EOF){//注意输入多个数据后要先Enter换行再按crtlDif(n0){printf(%d\n,Fabonacci(n));}else{printf(error: n must 0\n);}}
}例题2二叉树 提交网址http://t.cn/Ai0Ke6I0
#include cstdioint binaryTree(int m,int n){if(mn){return 0;}else{return binaryTree(2*m,n) binaryTree(2*m1,n) 1;}
}int main(){int m,n;while(scanf(%d %d,m,n) ! EOF){if(m0 n0){break;}printf(%d\n,binaryTree(m,n));}
}六、非线性数据结构
内存空间
栈
栈帧。当被调函数执行结束栈帧上的变量也会被自动回收。
堆 (自由存储区)
new出来的不会自动销毁。需要手动回收否则会发生内存泄漏。 指针和引用
指针间接访问 值传递
1.* 取内容(间接访问) 2. 取地址
3.-运算符 若p为指针则(*p).member与p-member等价 引用引用传递
引用x,y就是给变量x,y起了个别名并没有新开辟内存存储空间。这样被调函数的参数列表(int x, int y)就可以直接引用传递给主函数中的变量x,y。因为x y与x y 享有同一个内存地址会直接修改。 C的两种传递方式值传递、引用传递
例1变量名-直接访问-值传递在被调函数中无法修改主调函数中参数的内容。尽管变量名相同但不是同一个地址
#include cstdiovoid swap1(int x,int y){int temp x;x y;y temp;
}int main(){int x 1 ,y 2;swap1(x,y);
}结果是在swap1中x与y的值互换了但main中的x与y的值不变。因为swap1中和main中的x、y的地址不同。 例2指针-间接访问-值传递 在被调函数里改变主调函数中变量的内容传指针(间接访问) 在普通函数中想要改变main函数中的值要传指针。值才能透出去。
#include cstdiovoid swap2(int *px,int *py){int temp *px;*px *py;*py temp;
}int main(){int x 1 ,y 2;int *px x;int *py y;swap2(px,py);
}例3引用-引用传递 对比例1只修改了被调函数的参数列表将int x,int y改为 int x,int y
#include cstdiovoid swap3(int x,int y){ int temp x;x y;y temp;
}int main(){int x 1 ,y 2;swap3(x,y);
}1.二叉树 二叉树的遍历
层次遍历队列 递归遍历前中后序遍历
重建二叉树并遍历 例1通过先序序列和中序序列建立二叉树再输出后序遍历序列华科复试上机真题 提交网址http://t.cn/AiKgDfLU
#include cstdio
#include string
using namespace std;struct TreeNode{char data;TreeNode * leftChild;TreeNode * rightChild;
};TreeNode *rebuild(string preOrder,string inOrder){ //返回值为子树根结点的地址if(preOrder.size() 0){return NULL;}else{//从先序遍历确定根char rootdata preOrder[0];TreeNode *pNewNode new TreeNode;//二叉树结点指针pNewNode-data rootdata;//用根位置切割中序int pos inOrder.find(rootdata);//pos是根在中序序列中出现的下标pNewNode-leftChild rebuild(preOrder.substr(1,pos),inOrder.substr(0,pos));pNewNode-rightChild rebuild(preOrder.substr(pos1),inOrder.substr(pos1));return pNewNode;}
}void PostOrder(TreeNode * root){if(root NULL){return;}PostOrder(root-leftChild);PostOrder(root-rightChild);printf(%c,root-data);return;
}int main(){char preOrder[30];char inOrder[30];while(scanf(%s%s,preOrder,inOrder) ! EOF){TreeNode * root rebuild(preOrder,inOrder);PostOrder(root);printf(\n);}
}例2根据有#的先序遍历序列构建二叉树并输出中序遍历序列 清华复试上机真题
哈哈哈2.二叉排序树 BST
二叉排序树(二叉搜索树二叉查找树 BST) 的建立
#include cstdiostruct TreeNode{ //类类型/结构体类型int data; //数据域TreeNode * leftChild; //左孩子指针TreeNode * rightChild;//右孩子指针
};void insertBST(TreeNode * root,int data){//根数据域TreeNode *pNewNode new TreeNode;//申请一个空结点 pNewNodepNewNode-data data;//主函数传进来的data赋值给结点的数据域 pNewNode-datapNewNode-leftChild NULL;//左孩子置为空pNewNode-rightChild NULL;//右孩子置为空if(NULL root){root pNewNode; //若根结点为空则让当前结点TreeNode * pNewNode 作为根结点 TreeNode * root}else{TreeNode * pPre root;TreeNode * pCur;while(true){if(data pPre-data){//新数据比根结点小作为左孩子pCur pPre-leftChild;if( NULL pCur ){//左孩子为空 //判断条件是 写成一个 了pPre-leftChild pNewNode;break;}else{//左孩子结点不为空pPre pCur;//当前结点作为新的根结点}}else{//新数据比根结点大作为右孩子pCur pPre-rightChild;if( NULL pCur ){ //判断条件是 写成一个 了pPre-rightChild pNewNode;break;}else{pPre pCur;}}}}
}int main(){TreeNode * root NULL;int array[] {2,3,5,1,4};for(int i 0;i 5; i){insertBST(root,array[i]);}}例题1华科 KY207 二叉排序树 提交网址http://t.cn/Ai9PAkkv
#include cstdiostruct TreeNode{ //类类型/结构体类型int data; //数据域TreeNode * leftChild; //左孩子指针TreeNode * rightChild;//右孩子指针
};void insertBST(TreeNode * root,int data){//根数据域TreeNode *pNewNode new TreeNode;//申请一个空结点 pNewNodepNewNode-data data;//主函数传进来的data赋值给结点的数据域 pNewNode-datapNewNode-leftChild NULL;//左孩子置为空pNewNode-rightChild NULL;//右孩子置为空if(NULL root){root pNewNode; //若根结点为空则让当前结点TreeNode * pNewNode 作为根结点 TreeNode * rootprintf(-1\n);}else{TreeNode * pPre root;TreeNode * pCur;while(true){if(data pPre-data){//新数据比根结点小作为左孩子pCur pPre-leftChild;if( NULL pCur ){//左孩子为空 //判断条件是 写成一个 了pPre-leftChild pNewNode;printf(%d\n,pPre-data);break;}else{//左孩子结点不为空pPre pCur;//当前结点作为新的根结点}}else{//新数据比根结点大作为右孩子pCur pPre-rightChild;if( NULL pCur ){ //判断条件是 写成一个 了pPre-rightChild pNewNode;printf(%d\n,pPre-data);break;}else{pPre pCur;//当前结点作为新的根结点}}}}
}int main(){TreeNode * root NULL;int n;scanf(%d,n);for(int i 0;i n; i){int num;scanf(%d,num);insertBST(root,num);}return 0;
}例题2浙大 判断是否为同一个二叉搜索树序列 提交网址http://t.cn/Ai9PUJtK
在这里插入代码片3.优先队列 priority_queue堆 heap
堆
1.堆 优先队列不是队列(queue)而是堆(heap)是二叉堆(大根堆、小根堆)结构是完全二叉树用数组保存。
2.大根堆 优先队列默认为大根堆。
priority_queuetypenamename;3.小根堆 重新定义优先队列
priority_queuetypename,vectortypename,greatertypenamename优先队列模板 STL-priority_queue
1.定义
#include queue
using namespace std;
priority_queuetypenamename;2.状态 ①队空是否为空 empty() ②队长元素个数 size()
3.增删元素 ①出队插入元素 push() ②入队删除元素 pop()
4.元素访问 队首只能访问优先级最高的元素 top() 优先队列的应用
1.顺序问题
运算符重载
重载小于运算符operator 2.哈夫曼树
1.求WPL(带权路径和) ①构建哈夫曼树再求WPL已掌握 ②迭代式求WPL 例题1哈夫曼树 (北邮复试上机真题) 提交网址http://t.cn/AiCuGMki
#include cstdio
#include queue
using namespace std;int main(){priority_queueint pqueue;int n;scanf(%d,n);for(int i 0; i n; i){int weight;scanf(%d,weight);pqueue.push(-weight);}int res 0; //存储带权路径长度和的中间结果while(pqueue.size()1){int leaf1 pqueue.top();pqueue.pop();int leaf2 pqueue.top();pqueue.pop();res leaf1 leaf2;pqueue.push(leaf1leaf2);}printf(%d\n,-res);return 0;
}4.散列表 map
映射 map
1.map底层红黑树 (RBT∈BST) 2.特点所以map会自动排好序 (BST中序遍历是升序序列)。 3.map查找时间复杂度 O(logn) 和二分查找相同的时间复杂度但比二分查找需要更多的空间 4.操作
(1)头文件
#include map
using namespace std;定义
mapstring,int myMap;初始化
mapstring,int myMap {{Caixukun,1},{Wuyifan,2},{Liyifeng,3}
};(2)插入键值对 ①insert()方法
myMap.insert(pairstring,int(Wuyifan,2));②[]下标访问运算符
myMap[Caixukun] 1;删除键值对erase()
myMap.erase(Wuyifan);读取键对应的值 (3)判空empty() 求长度(获取键值对个数)size() (4)map的遍历迭代器 iterator (迭代器是指向内部元素的指针) ①定义迭代器mapstring,int::iterator it; ②第一个成员的位置.begin() ③尾后位置.end() ④迭代器指针后移it (it使得迭代器指针指向下一对键值对unorder_map不支持此操作) ⑤键it-first ⑥值it-second
mapstring,int::iterator it;
for(it myMap.begin();it ! myMap.end();it){printf(%s %d\n,it-first.c_str(),it-second);
}(5)查找某个键是否存在find()函数 例题1查找学生信息 清华大学复试上机题 提交网址http://t.cn/AiCuVIuY
#include cstdio
#include string
#include map
using namespace std;struct Student{string name;string gender;int age;
};int main(){int n;scanf(%d,n);mapstring,Student InfoMap;for(int i 0; i n; i){char num[30];char name[30];char gender[30];int age;scanf(%s %s %s %d,num,name,gender,age);//key stringstring numstr num;//value StudentStudent student;student.name name;student.gender gender;student.age age;InfoMap[numstr] student;}int m;scanf(%d,m);for(int i 0; i m; i){char num[30];scanf(%s,num);string numstr num;if(InfoMap.find(numstr) ! InfoMap.end()){//找到了printf(%s %s %s %d\n,numstr.c_str(),InfoMap[numstr].name.c_str(),InfoMap[numstr].gender.c_str(),InfoMap[numstr].age);}else{//学号没找到printf(No Answer!\n);//这里漏加换行符\n导致格式错误了好几次。}}
}例题2魔咒词典 浙大上机复试真题 提交网址http://t.cn/AiCufczt
#include cstdio
#include string
#include map
using namespace std;//魔咒词典 (采用 增量编辑法即写一部分测试一部分)
int main(){mapstring,string dict;while(true){char line[200];fgets(line,200,stdin);//输入一行string linestr line;linestr.pop_back();//干掉回车string最后一个字符为\nif(END linestr){break;}
// printf(%s\n,linestr.c_str());int pos linestr.find(]);string word linestr.substr(0,pos1);string info linestr.substr(pos2);
// printf(word %s, info %s\n,word.c_str(),info.c_str());dict[word] info;dict[info] word;}int n;scanf(%d,n);getchar();//吃掉回车 ※for(int i 0 ; i n; i){char line[200];fgets(line,200,stdin);string linestr line;linestr.pop_back();if(dict.find(linestr) ! dict.end()){//存在魔咒或功能if([ linestr[0]){//输入魔咒查找功能printf(%s\n,dict[linestr].c_str());}else{//输入功能查找魔咒string charm dict[linestr];//[xxxxxx],想办法去掉[]string charm_sub charm.substr(1,charm.size()-2);//取子串去掉了[]printf(%s\n,charm_sub.c_str());}}else{//不存在该魔咒或功能printf(what?\n);}}
}unorder_map
1.底层HashTable 散列表 2.unorder_map查找时间复杂度O(1) 3.特点①空间特别大 ②无序不能遍历 七、搜索
搜索问题就是带有限制的枚举问题。 BFS 广度优先搜索
BFSBreadth First Search广度优先搜索(宽度优先搜索)。 为了求最优解问题 例题1Catch that Cow 例题2Find the Multiple 打表
当OJ时限很小且输入范围有限1≤n≤200 还是上文例题2Find the Multiple用打表法解决 DFS 深度优先搜索
DFSDepth First Search深度优先搜索。 为了知道问题是否有解例如找迷宫出口 例题1A Knight’s Journey 例题2Square 剪枝算法
在深度优先遍历搜索过程中可以通过放弃对某些不可能产生结果的子集的搜索达到提高效率的目的。这样的技术称为剪枝。
