C语言的一些基础知识

一些细节

linux下编译运行c++程序

g++ -W file_name.cpp -o another_name
./file_name

-W = 输入错误信息

字符数组的输入输出
scanf输入，printf输出
```
 #include <stdio.h>
 int main(){
     char str[10];
     scanf("%s", str);
     printf("%s", str);
     return 0;
 }
```
注：%s识别空格作为字符串的结尾；scanf在使用%s时，对应数组名是不需要加&运算符的。
数组初始化符号{}
ascii
A = 65; a: 97

结构体的初始化

scanf("%d %c %d", &a, &data, &b);
node[a] = {data, b, false};  // 注意时花括号，和数组初始化一样。

高位补0与高位补空

printf("%05d", i);  // 使不足５位的整数的高位补０。
printf("%5d", i);  // 使不足５位的整数的高位补为空。

scanf()使用%c可以读入空格，要注意格式！

scanf("%d %c");

使用new运算符为链表结点分配内存空间
使用方法：typename *p = new typename;
例子如下
```
int *p = new int;
node *p = new node;
int *p = new arr[10000];
```
memset对数组中每一个元素赋相同的值
格式：memset(name, value, sizeof(name))
前提条件：添加string.h
==建议赋值为0或-1==，不易出错。

c++

1. vector

使用：#include<vector>；除此之外，还需加上using namespace std;

（1）定义

vector<typename> name;

注：其长度可以根据需要进行变化，“变长数组”

（2）vector容器内元素的访问

eg.

vector<typename> vi;

通过下标访问

vi[index];  // 下标从为0~vi.size()-1

通过迭代器访问

迭代器(iterator)定义：vector<typename> =:iterator it;

// it 是一个 vector =:iterator 型的变量

// 这样得到了迭代器it，访问vector里的内容方式如下：

*it

// 测试vector
#include <cstdio>
#include <vector>
using namespace std;
int main(){
    vector<int> vi;
    for(int i = 1; i <= 5; i++){
        vi.push_back(i);
    }
    vector<int> =:iterator it = vi.begin(); // vi.begin()取vi首元素地址
    for(int i = 0; i < 5; i++){
        printf("%d\n", *(it+i));
    }
    return 0;
}

// vector_test_2
#include <cstdio>
#include <vector>
using namespace std;
int main(){
    vector<int> vi;
    for(int i = 1; i <= 5; i++){
        vi.push_back(i);
    }
    for(vector<int> =:iterator it = vi.begin(); it != vi.end(); it++){
        printf("%d ", *it);
    }
    return 0;
}

（3）vector常用函数

push_back()

push_back(x) = 在vector后添加元素x，时间复杂度O(1)

// vector_test_3
// push_back()
#include <cstdio>
#include <vector>
using namespace std;
int main(){
    vector<int> vi;
    for(int i = 1; i <=3; i++){
        vi.push_back(i);
    }
    for(int i = 0; i < 3; i++){
        printf("%d ", vi[i]);
    }
    return 0;
}

pop_back()

pop_back() = 删除vector尾元素，时间复杂度O(1)

// vector_test_4
// pop_back()
#include <cstdio>
#include <vector>
using namespace std;
int main(){
    vector<int> vi;
    for(int i = 1; i <= 5; i++){
        vi.push_back(i);
    }
    vi.pop_back();
    for(int i = 0; i < vi.size(); i++){
        printf("%d ", vi[i]);
    }
    return 0;
}
// result = 1 2 3 4

size()
用来获得vector中元素个数，时间复杂度O(1)
clear()
用来清空vector中的所有元素，时间复杂度O(n)

insert()

insert(it, x) = 向vector迭代器it处插入元素x，时间复杂度O(N)

// vector_test_7
// insert(it, x)
#include <cstdio>
#include <vector>
using namespace std;
int main(){
    vector<int> vi;
    for(int i = 1; i <= 3; i++){
        vi.push_back(i);
    }
    vi.insert(vi.begin()+2, -1);
    for(int i = 0; i < vi.size(); i++){
        printf("%d ", vi[i]);
    }
    return 0;
}
// result = 1 2 -1 3

erase()

时间复杂度均为O(N)

删除单个元素 erase(it)

// vector_test_8
// erase()
#include <cstdio>
#include <vector>
using namespace std;
int main(){
    vector<int> vi;
    for(int i = 1; i <= 5; i++){
        vi.push_back(i);
    }
    vi.erase(vi.begin()+3);
    for(int i = 0; i < vi.size(); i++){
        printf("%d\n", vi[i]);
    }
    return 0;
}
// result = 1 2 3 5

删除区间所有元素 erase(first, last) 左开右闭

2. stack

（1）定义

添加#include <stack>与using namespace std;

定义写法：

stack<typename> name;

（2）stack容器内元素访问

后进先出，只能通过top()访问栈顶元素。

（3）常用函数

push()
push(x) = 将x入栈，时间复杂度O(1)
top()
top() = 获得栈顶元素，时间复杂度O(1)
pop()
pop() = 弹出栈顶元素，时间复杂度O(1)
empty()
检测stack是否为空。返回true为空。时间复杂度O(1)
size()
返回stack内元素个数。时间复杂度O(1)

3. string

（1）定义

添加#include <string>与using namespace std

string str;

初始化：string str = "abcd";

（2）string中内容访问

通过下标访问
str[i]

通过迭代器访问

定义：string =:iterator it;

通过*it访问string中的每一位。

// string_test_3
#include <cstdio>
#include <string>
using namespace std;
int main(){
    string str = "abcd";
    for(string =:iterator it = str.begin(); it != str.end(); it++){
        printf("%c", *it);
    } 
    return 0;
}

（3）常用函数

4. queue

（1）定义

预先条件：

#include <queue>
using namespace std;

queue<typename> name;

（2）容器内元素访问

通过front()访问队首元素，通过back()访问队尾元素。

// queue_test_1
#include <cstdio>
#include <queue>
using namespace std;
int main(){
    queue<int> q;
    for(int i = 0; i < 5; i++) {
        q.push(i);
    }
    printf("%d %d\n", q.front(), q.back());
    return 0;
}
result =
0 4

（3）常用函数

push()
push(x)：将x入队。
时间复杂度：O(1)
front()/back()
时间复杂度：O(1)
pop()
pop()：出队
时间复杂度：O(1)
empty()
检测q是否为空，为空返回true.
时间复杂度：O(1)
size()
返回元素个数。
时间复杂度：O(1)

（4）用途

广度优先搜索

5. algorithm头文件下常用函数

须添加using namespace std;

（1）max()/min()/abs()

max(x, y) = 返回x, y中最大值
min(x, y) = 返回x, y中最小值
参数必须是两个，可以是浮点数
max(x, max(y, z)) = 返回三者中最大值
abx(x) = 返回x绝对值 // x必须是整数
fabs(x) = 浮点数绝对值，使用math头文件

（2）swap()

swap(x, y) = 交换x和y的值

（3）reverse()

reverse(it, it2) = 将数组指针在[it, it2)之间的元素或容器的迭代器在[it, it2)范围内的元素进行反转。

// algorithm_test_3
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
    int a[10] = {10, 11, 12, 13, 14, 15};
    reverse(a, a+4);
    for(int i = 0; i < 6; i++){
        printf("%d ", a[i]);
    }
    return 0;
}
result = 13 12 11 10 14 15

（4）sort()

如何使用sort排序

使用

#include <algorithm>
using namespace std;

sort(首元素地址(必填), 尾元素地址(必填), 比较函数(非必填))

注：不写比较函数，默认递增排序

// algorithm_test_4
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
    int a[6] = {9, 4, 2, 5, 6, -1};
    sort(a, a+4); // [0, 4)
    for(int i = 0; i < 6; i++)
        printf("%d ", a[i]);
    printf("\n");
    sort(a, a+6); // [0, 6)
    for(int i = 0; i < 6; i++)
        printf("%d ", a[i]);
    return 0;
}
result =

如何实现比较函数cmp

基本数据类型数组的排序

// 实现从大到小排序
// algorithm_test_5
#include <cstdio>
#include <algorithm>
using namespace std;

bool cmp(int a, int b){
    return a > b;  // 当a>b时，a放在b前边
}
int main(){
    int a[] = {1, 2, 3, 4};
    sort(a, a+4, cmp);
    for(int i = 0; i < 4; i++){
        printf("%d ", a[i]);
    }
    return 0;
}
result =
4 3 2 1

结构体数组的排序

定义如下结构体：

struct node{
    int x, y;
}ssd[10];

将ssd数组按x从大到小排序：

bool cmp(node a, node b){
    return a.x > b.x;
}

eg.

// algorithm_test_6
// 结构体数组的排序
#include <cstdio>
#include <algorithm>
using namespace std;

struct node{
    int x, y;
}ssd[10];
bool cmp(node a, node b){
    return a.x > b.x;
}

int main(){
    ssd[0].x = 2;
    ssd[0].y = 2;
    ssd[1].x = 1;
    ssd[1].y = 3;
    ssd[2].x = 3;
    ssd[2].y = 1;
    sort(ssd, ssd+3, cmp);
    for(int i = 0; i < 3; i++){
        printf("%d %d\n", ssd[i].x, ssd[i].y);
    }
    return 0;
}

result =

（5）fill

将数组或容器中某一段区间赋为某个相同的值。==赋值可以是数组类型对应的任何值==

#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
    int a[5] = {1, 2, 3, 4, 5};
    fill(a, a+5, 23);
    for(int i = 0; i < 5; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}
result =
23 23 23 23 23

6. map

翻译为映射。
例如在定义数组时，是定义了一个从int到int的映射，如arr[0] = 5是将0映射到5.
map可以将任何基本类型映射到任何基本类型。

（1）定义

前提条件
```
#include <map>
using namespace std;
```
map定义
```
map<typename1, typename2> mp;
```
注：如果是字符串到整型的映射，必须使用string而不能用char数组
```
map<string, int> mp;
```

（2）容器内元素访问

通过下标访问

// map_test_1
#include <cstdio>
#include <map>
using namespace std;
int main() {
    map<char, int> mp;
    mp['c'] = 20;
    mp['c'] = 30;
    printf("%d\n", mp['c']);
    return 0;
}

通过迭代器访问(跳过)

（3）常用函数

find()
size()
clear()

C语言的一些基础知识

2020/04/04

一些细节

c++

1. vector

（1）定义

（2）vector容器内元素的访问

（3）vector常用函数

2. stack

（1）定义

（2）stack容器内元素访问

（3）常用函数

3. string

（1）定义

（2）string中内容访问

（3）常用函数

4. queue

（1）定义

（2）容器内元素访问

（3）常用函数

（4）用途

5. algorithm头文件下常用函数

（1）max()/min()/abs()

（2）swap()

（3）reverse()

（4）sort()

（5）fill

6. map

（1）定义

（2）容器内元素访问

（3）常用函数