PAT预备知识C++/少量C与注意事项-必备基础初学-算法笔记

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了PAT预备知识C++/少量C与注意事项-必备基础初学-算法笔记，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含8459字，纯文字阅读大概需要13分钟。

内容图文

语法

char str[25] = "hello"; //字符数组

printf("%s", str);

#define pi 3.24 

const double pi=3.24;  //设置常量

const int INF=0x3fffffff;  //无穷大常用2^30-1

printf("%5d\n",a);//使a占5位，高位用空格补齐（超过5位则不变），%05d 高位0补齐  ，%.1f 保留一位小数

struct node{
    node n;  //错误表述，不可定义自身
    node* next;  //正确，可定义自身类型的指针
};

结构体的优先级设置

struct fruit{
    string name;
    int price;
    friend bool operator < (fruit f1, fruit f2){//对fruit类型的操作符<进行了重载
        return f1.price < f2.price;//当进行sort排序时排序方式为水果的价钱由小到大
    }
};
//若结构体内的数据较为庞大，建议使用引用提高效率
friend bool operator < (const fruit &f1, const fruit &f2){
    return f1.price < f2.price;
}

动态链表

int* p=new int[100];//申请动态空间
delete(p);//需释放，否则内存泄漏

静态链表

struct Node{
    int data;
    int next;//下一个节点的数组下标
}node[100];

isdigit(x);//是否为十进制数字

isalpha(x);//是否字母

isalnum(x);//是否十进制数字或字母

islower(x);//是否小写字母

s[i]=tolower(s[i]);//转换为小写字母

toupper();//大写

常用函数

#include<math.h>

fabs(db);//对double值取绝对值

floor(db);//...向下取整

ceil(db);//...向上取整

pow(r, p);//double r,p; 返回r^p

sqrt(db);//返回db算术平方根

log(db);//返回ln(db)

sin(db) cos(db) tan(db)//弧度制

round(db);//四舍五入，返回double

//字符数组的相关操作

#include<string.h>

strlen(str);//长度

strcmp(str1, str2); // 若str1<str2 则返回负   =（返回0） >（返回正）

strcpy(str1,str2); // str2复制给str1

strcat(str1,str2); // str2接到str1后面

sscanf(str,"%d",&n);//把str以指定格式输入到n，支持正则

sprintf(str,"%d",n);//把n输出到str

#include<iostream>

using namespace std;

cin>>n;

cin>>n>>db>>c>>str; //可连续输入多个不同类型的变量

cin.getline(str); //输入包含空格的字符串，string类型

cout<<n<<db<<c<<str; // 可连续输出多个不同类型的变量

cout<<endl;//换行+刷新缓冲区，cout<<"\n";换行   

#include<algorithm>

using namespace std;

sort(a, a+6);//将a[0]~a[5]从小到大排序

sort(a, a+6, cmp);//cmp为比较函数，确定排序的方式

bool cmp(int a, int b){
    return a>b;//当a>b时，a在前面，即由大到小排序
}
bool cmp(node a, node b){
    if(a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

sort(v.begin(), v.end(), cmp);

max(x,y);//返回x,y中更大的那一个,可浮点数

min(x,y);

abs(x)；//整数的绝对值

swap(x,y);//交换x,y

reverse(it,it1);//[it,it2)之间的内容反转

fill(a, a+5, 233);//把某一区间的值都赋值为某个指定的值

lower_bound(first, last, val); //第一个大于等于val的元素的位置

upper_bound(first, last, val);//第一个值大于val的元素的位置

//不常用

#include<stdlib.h>

#include<time.h>

srand((unsigned)time(NULL));//生成随机数种子

rand();//生成随机数[0,RAND_MAX]范围内

(int)(round(1.0*rand()/RAND_MAX*(b-a)+a));//生成[a,b]范围内的数

 

 

C++ STL常用

//变长数组

#include<vector>

using namespace std;

vector<int> vi;// 通过数组下标或者迭代器访问 vi[2]  == *(vi.begin()+2) == *(it+2)   只有vector和string支持*(it+i)的访问元素的方式

vector<vector<int> > vi;//两维都变长

vector<int> vi[100];//一维变长，一维定长

vector<int>:: iterator it;//迭代器

for(auto it=vi.begin();it!=vi.end();it++)//auto自动给类型，遍历变长数组vi，vi.end()为最后一个元素的下一个位置，begin为第一个元素的位置

vi.push_back(x);//在vi的后面添加一个元素x

vi.pop_back();//删除末尾元素，无返回值

vi.clear();//清空

vi.insert(it,x);//将x插入到it处

vi.erase(it);//删除it处的元素

vi.erase(it1, it2);//删除[it1,it2)处的元素

vi.size();//获取vi的长度

//内部自动有序且不含重复元素,红黑树实现  只能通过迭代器访问*it，不支持*(it+i)

//multiset 元素不唯一

//unordered_set 不排序

#include<set>

using namespace std;

set<int> st;

st.insert(x);//将x插入

auto it=st.find(2);//在st中查找2，返回其迭代器  it==st.end() 未找到

st.erase(it);

st.erase(value);

st.erase(first,last);//删除[first,last)

st.size();

st.clear();

//字符串

#include<string>

using namespace std;

//可通过下标或迭代器访问

string str;

str.c_str();//将string型转换为字符数组

str1+=str2;//拼接

s=s+c;//拼接char类型

//比较大小根据字典序

str.substr(0,5);//返回从0位开始的5个字符

str.find(str1);//返回在str第一次出现str1的位置下标

string num=to_string(sum);//将数字转换为string 类型

//str为null 内存中没创建字符串对象

//str为空串 存在由str引用的字符串对象，这个对象的值是""，长度为0，不是空格串“ ”

//其他类似其他stl的操作

//映射，类似于python的字典. 一对一,自动实现key由小到大的排序，红黑树实现

//multimap 一对多 不常用

//unordered_map 只映射不排序 ，速度更快

#include<map>

using ...

db[0]=3.24;//数组是将int映射到数组类型，例子为float型，map将任何基本类型（包括stl容器）映射到任何基本类型（包括stl)

map<string, int> mp;//字符串到整型的映射

map<set<int>, string> mp;

it=mp.find('b');//返回key为‘b'的迭代器，未找到则返回mp.end()

mp.erase(it);//比mp.erase(key)更快

//下标访问 mp['c']=20 迭代器访问 it->first(键)   it->second（值）

mp.size();//有多少对键值对

mp.clear();

//队列，不常用

#include<queue>

using ...

queue<int> q;

q.push(x);

q.pop();//无返回值

q.empty();

q.size();

q.front();//访问队首

q.back();//访问队尾

//访问前需要判断队列是否为空

//栈 不常用

#include<stack>

us...

stack<int> st;

st.push(x);

st.pop();

st.empty();

st.size();

st.top();//访问

//pair内部有两个元素的结构体，实用

#include<utility>//map包含了pair

pair<string, int> p;

pair<string,int> p("hhh",5);

p.first;//访问第一个元素

p.second；//以结构体的方式访问

==   ！=  可比较pair类型数据的大小，先以first大小作为标准 first相等时比较second

map<string, int> mp;

mp.insert(make_pair("hhh",5));//或直接mp.insert({"hhh",5})会比make_pair更快

 

数据结构

除留余数 H(key) = key%mod 解决冲突（用map不需要自己解决冲突）

开放定址法

1）线性探查 H(key)+1

2）平方探查 H(key)+1^2 -1^2 +2^2 ...

链地址法 单链表数组

字符串hash

若A～Z，则将字符串看成二十六进制，再转换成十进制

int hashFunc(char s[], int len){
    int id=0;
    for(int I=0; I<len; i++){
        id=id*26+(s[i]-'A');
    }
    return id;
}

 

相关知识

int  32位 范围 -2*10^9 ~ 2*10^9

long long 64位 范围 -9*10^10 ~ 9*10^18  long long num=123...LL

小写字母比大写字母的ASCII码大32

\n换行

\0空字符NULL

int %d（scanf） %d(printf)

long long %lld     %lld

float %f   %f

double %lf   %f

char %c（scanf("%c", &c);//地址)   %c   等于c=getchar(); putchar(c);

字符数组 %s  %s

除了%c，其他都将空格、换行符作为结束判断标志

要输入空格，使用getline(cin,name);

%%输出%

\\ 输出\

&&  ｜｜ ！  与或非（逻辑运算符）

& | ^ ~  与 或 异或 取反 （位运算符）

int a[10] = {};//有赋初始值或者{}，未被赋值的部分默认为0

char str[15] = "hello...";//赋值只限于初始化，长度需要加上‘\0’的长度

memset(a,0,sizeof(a));// 只建议赋值0或-1

void change(int a[], int b[][5]); // 一维不需要写长度，第二维需要

void change(int &x); // 引用，与取地址不同 不产生副本 变量的别名，常量不可使用引用

const double pi=acos(-1.0);

数组长度必须用常数、cons值或常量表达式（数组必须在编译过程中就确定长度） int a[n];//若n为变量，此式子错误

if(b&1)比if(b%2==1)快

b>>=1 效果与b=b/2等价

计算最大公约数

int gcd(int a, int b){
    if(b==0) return a;
    else return gcd(b,a%b);
}

最小公倍数为ab/d等价于a/d*b

万能头文件

#include<bits/stdc++.h>

using namespace std;

typedef struct{xxx...} aaa; // 定义类，给类一个别名

struct node{xxx...} bbb;//同时定义类和对象

string cin/cout == < >速度慢  char [] scanf printf strcmp 速度快

保存下标，通过下标对字符串排序更快

//在main()里面开头加上

#ifdef ONLINE_JUDGE//如果是在测试平台则跳过
#else
    freopen("1.txt","r",stdin);//在自己的编译器则重新打开文件并将文件内容重定向到控制台输入
    //第一个位置填入文件的位置
#endif

这样就可以将测试用例粘贴到文件中，不用每次测试都手动输入测试用例

 

注意事项

int/int 注意除数为0

若数组大小较大（>10^6）需定义在主函数外

//浮点数的比较有误差（经过容易损失精度的计算之后），需要控制范围，只要差异大小在一定范围内都要算为相等。

const double eps=1e-8;// 10^-8

#define Equ(a,b) ((fabs((a)-(b))) < (eps)

数字较多位时（如id），用字符串存储，不要用整数

对一些不会的题，可先暴力计算小范围数据的结果，再找规律

当结果较大，需要取余时，应在计算过程中取余而不是输出结果时才取余

先想清楚需要定义哪些函数再动手实现

可以先列出容易出错的数据，按照自己的想法核对示例后再敲代码，以防理解错误题意，使用边界数据测试

题目用例可能给出不在链表中的节点，所以标记有效节点时需要通过给出的头节点开始遍历（若是静态链表，此时设置下标）。 

使用stl的queue,push操作只是制造了该元素的一个副本入队，因此在入队后对原元素的修改与对队列中的修改互不影响。所以队列中最好存放数组编号而不是元素值。

cin>>a;

getline(cin,line);//由于上一个cin语句没有读取换行符，所以此时line中只有一个换行符，需要在上一行加上 cin.ignore() 忽略掉那个换行符

边输入边计算时注意就算得到了最终结果也不能break，需要将该输入的数据都输入进来 ，不然会出现输入混乱。先将所有输入输入进来保存再进行模拟会更保险。

while(x);//注意x是否为负数，x--会死循环

N过大时，double精度过低，应换成long long运算

codeblocks编译器相关

watches 查看全局变量

输入  ::变量名  

tab多行缩进

shift+tab多行减少缩进

内容总结

以上是互联网集市为您收集整理的PAT预备知识C++/少量C与注意事项-必备基础初学-算法笔记全部内容，希望文章能够帮你解决PAT预备知识C++/少量C与注意事项-必备基础初学-算法笔记所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---