C语言的一些基础知识

Posted on In

一些细节

  1. linux下编译运行c++程序

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

    -W: 输入错误信息

  2. 字符数组的输入输出

    scanf输入，printf输出

    1
    2
    3
    4
    5
    6
    7
    #include <stdio.h>
    int main(){
        char str[10];
        scanf("%s", str);
        printf("%s", str);
        return 0;
    }

    注：%s识别空格作为字符串的结尾；scanf在使用%s时，对应数组名是不需要加&运算符的。

  3. 数组初始化符号{}

  4. ascii

    A: 65; a: 97

  5. 结构体的初始化

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

  6. 高位补0与高位补空

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

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

    1
    scanf("%d %c");

  8. 使用new运算符为链表结点分配内存空间

    使用方法：typename *p = new typename;

    例子如下

    1
    2
    3
    int *p = new int;
    node *p = new node;
    int *p = new arr[10000];

  9. memset对数组中每一个元素赋相同的值

    格式：memset(name, value, sizeof(name))

    前提条件：添加string.h

    ==建议赋值为0或-1==，不易出错。

c++

1. vector

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

（1）定义
1
vector<typename> name;

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

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

eg.

1
vector<typename> vi;

  • 通过下标访问

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

  • 通过迭代器访问

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

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

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

    1
    *it
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    // 测试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;
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    // 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)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    // 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)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    // 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)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    // 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)

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      // 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;

定义写法：

1
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中的每一位。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    // 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）定义

预先条件：

1
2
#include <queue>
using namespace std;

queue<typename> name;

（2）容器内元素访问

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 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)范围内的元素进行反转。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    // 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排序

    • 使用

      1
      2
      #include <algorithm>
      using namespace std;

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

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

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      // 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:

      img_1

  • 如何实现比较函数cmp

  • 基本数据类型数组的排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    // 实现从大到小排序
    // 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

  • 结构体数组的排序

    定义如下结构体：

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

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

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

    eg.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    // 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:

    img_2

（5）fill
  • 将数组或容器中某一段区间赋为某个相同的值。==赋值可以是数组类型对应的任何值==
1
2
3
4
5
6
7
8
9
10
11
12
13
#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）定义

  • 前提条件

    1
    2
    #include <map>
    using namespace std;

  • map定义

    1
    map<typename1, typename2> mp;

    注：如果是字符串到整型的映射，必须使用string而不能用char数组

    1
    map<string, int> mp;
（2）容器内元素访问

  • 通过下标访问

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    // 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()