C语言基础 - C 面向对象快速入门 - 《C语言、数据结构课件》

bool类型
引用类型
动态分配内存
面向对象思想
- 1. 手动实现一个栈stack
- 2. 技能清单
4. C++标准模版库 STL
字符串转换

#include <iostream>
using namespace std;
int main(){
    int a, b;
    cin >> a >> b;
    cout << "a + b = " << a + b << endl;
    cout << "hello world!" << endl;
    return 0;
}

bool类型

bool flag = true;
flag = false;

引用类型

值传递

void swap(int a, int b){
    int temp = a;
    a = b;
    b = temp;
}

int main(){
    int a = 1, b = 2;
    swap(a, b);        //我希望能交换a、b的值，即预期结果是a = 2, b = 1
    printf("%d %d\n", a, b);    //事实上a、b的值并未发生改变，还是a = 1, b = 2
    return 0;
}

地址传递

void swap(int* a, int* b){    //函数接受两个变量的地址
    int temp = *a;            //函数内部都是访问指针所指地址的内容
    *a = *b;
    *b = temp;
}

int main(){
    int a = 1, b = 2;
    swap(&a, &b);            //调用这函数时需要传递变量的地址
    printf("%d %d\n", a, b);
    return 0;
}

引用传递

void swap(int &a, int &b){        //只需在函数参数前添加引用&符号
    int temp = a;                //函数内部还是那个熟悉的写法
    a = b;
    b = temp;
}

int main(){
    int a = 1, b = 2;
    swap(a, b);                    //调用函数时也不需要做任何改变
    printf("%d %d\n", a, b);
    return 0;
}

可见在c中，引用一定程度上可以替代指针。由于指针使用比较繁琐，且过于灵活容易出错，在c后的很多语言里已经完全取消掉了指针，需要指针实现的功能部分由引用替代。

动态分配内存

C语言

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    Node* p;
} Node;

int main() {
    Node* temp = (Node*)malloc(sizeof(Node));
    int N = 100;
    int* A = (int*)malloc(sizeof(int) * N);
    free(temp);
    free(A);
    A = NULL;
    temp = NULL;
}

C++

#include <iostream>

struct Node {
    int data;
    Node* p;
};

int main() {
    Node* temp = new Node;
    int N = 100;
    Node* A = new Node[N];
    delete temp;
    delete[] A;
    A = NULL;
}

面向对象思想

1. 手动实现一个栈stack

1. 完全不封装

#include <stdio.h>
#define MAXN 10010

int Stack[MAXN];
int size;

void push(int x) {
    if (size >= MAXN) {
        printf("栈满");
        return;
    }
    Stack[size++] = x;
}

bool isEmpty() {
    return size == 0;
}

int pop() {
    if (isEmpty()) {
        printf("栈空");
        return -1;
    }
    return Stack[--size];
}

int top() {    //访问栈顶元素
    if (isEmpty()) {
        return -1;
    }
    return Stack[size - 1];
}

int getSize() {
    return size;
}

int main() {
    for (int i = 1; i <= 10; i++) {
        push(i);
    }
    pop();
    //..........
    return 0;
}

2. 使用结构体部分封装

#include <stdio.h>
#include <stdlib.h>
#define MAXN 1005

struct Stack {
    int* data;
    int size;
};

void initStack(Stack &S) {
    S.data = (int*)malloc(MAXN * sizeof(int));
    S.size = 0;
}

void destoryStack(Stack &S) {
    free(S.data);
    S.data = NULL;
}

void clearStack(Stack &S) {
    S.size = 0;
}

bool isEmptyStack(const Stack &S) {
    return S.size == 0;
}

void pushStack(Stack &S, int x) {
    if (S.size >= MAXN) {
        printf("栈满");
        return;
    }
    S.data[S.size++] = x;
}

int popStack(Stack &S) {
    if (isEmptyStack(S)) {
        printf("栈空");
        return -1;
    }
    return S.data[--S.size];
}

int topStack(const Stack &S) {
    if (isEmptyStack(S)) {
        return -1;
    }
    return S.data[S.size - 1];
}

int getStackSize(const Stack &S) {
    return S.size;
}

void printStack(const Stack &S) {
    for (int i = 0; i < S.size; i++) {
        printf("%d ", S.data[i]);
    }
    printf("\n");
}

int main() {
    Stack stack_1;
    initStack(stack_1);
    for (int i = 1; i <= 10; i++) {
        pushStack(stack_1, i);
    }
    printStack(stack_1);
    destoryStack(stack_1);

    Stack stack_2;
    initStack(stack_2);
    //.........
    return 0;
}

3. 使用类

#include <iostream>
using namespace std;

class Stack {
private:
    const int DEFAULT_CAPACITY = 100;
    int _capacity;
    int _size;
    int* _elem;

public:
    Stack() {    //构造函数
        _elem = new int[DEFAULT_CAPACITY];
        _size = 0;
        _capacity = DEFAULT_CAPACITY;
    }

    Stack(int _capacity) {    //构造函数
        if (_capacity < 1) {
            _capacity = DEFAULT_CAPACITY;
        }
        _elem = new int[_capacity];
        _size = 0;
        this->_capacity = _capacity;
    }

    ~Stack() {    //析构函数
        delete[] _elem;
        cout << "已释放申请的内存空间" << endl;
    }

    void clear() {
        _size = 0;
    }

    void push(int e) {
        if (_size >= _capacity) throw exception("栈满了");
        _elem[_size++] = e;
    }

    int pop() {
        if (_size <= 0) throw exception("栈为空");
        return _elem[--_size];
    }

    int& top() {
        if (_size <= 0) throw exception("栈为空");
        return _elem[_size - 1];
    }

    int size() {
        return _size;
    }

    bool empty() {
        return _size == 0;
    }

    void print() {
        for (int i = 0; i < _size; i++) {
            printf("%d ", _elem[i]);
        }
        printf("\n");
    }
};

int main() {
    Stack S;

    try {
        S.pop();
    }
    catch (exception e) {
        printf("%s\n", e.what());
    }

    S.push(2);

    printf("%d\n", S.top());
    S.clear();
    for (int i = 0; i < 5; i++) {
        S.push(i);
    }
    S.print();

    //printf("%d", stack1._size);    //_size不能被访问

    Stack* s2 = new Stack(10);
    s2->push(2);
    s2->print();
    delete s2;

    return 0;
}

2. 技能清单

类 class、对象实例、成员变量（属性）、成员函数（方法）

在面向对象的编程中，通常把用类创建对象的过程称为实例化。（用类创建对象的过程）

在创建对象时，构造函数会自动被调用，以初始化一个对象。

构造函数

构造函数是类的一种特殊的成员函数，它会在每次创建类的新对象时执行。

构造函数的名称与类的名称是完全相同的，并且不会返回任何类型，也不会返回 void。构造函数可用于为某些成员变量设置初始值。

如果创建一个类你没有写任何构造函数，则系统会自动生成默认的无参构造函数，函数为空，什么都不做。
只要定义了一个构造函数，系统就不会再自动生成这样一个默认的构造函数，如果希望有一个这样的无参构造函数，则需要自己显示地写出来。

Constructors（构造函数）

Automatic invocation（自动调用）
Has the same name as the defining class（与类同名）
NO return value (including “void”); （无返回值）
Can be overloaded （可以重载）
May have no arguments（可以不带参数）
A class may be declared without ctors (类可以不声明构造函数)
- A no-arg constructor with an empty body is implicitly declared in the class.（编译器会提供一个带有空函数体的无参构造函数）
- This constructor, called a default constructor is provided automatically only if no constructors are explicitly declared in the class.（只有当未明确声明构造函数时，编译器才会提供这个构造函数，并称之为“默认构造函数”）

#include <iostream>
using namespace std;

struct Point {
    double x, y;

    Point() {}
    Point(double _x, double _y) { x = _x; y = _y; }
};

int main() {
    //Point temp;
    //temp.x = 1; temp.y = 2;
    Point a(1, 1), b(2, 2);

}

析构函数

析构函数是类的一种特殊的成员函数，它会在每次删除所创建的对象时执行。

析构函数的名称与类的名称是完全相同的，只是在前面加了个波浪号（~）作为前缀，它不会返回任何值，也不能带有任何参数。析构函数有助于在跳出程序（比如关闭文件、释放内存等）前释放资源。

访问控制

private：访问权限仅限于类的内部，是一种封装的体现。通常习惯在变量名前加下划线_提示该变量是私有变量，如_data。
public：具有最大的访问权限，外部可以访问public成员。
C为了兼容C语言，依然保留了struct关键字。C中的struct与class一样，可以使用面向对象的各种语法，只是struct中所有的成员变量和成员函数都是public的。

封装

封装从字面上来理解就是包装的意思，专业点就是信息隐藏，是指利用抽象数据类型将数据和基于数据的操作封装在一起，使其构成一个不可分割的独立实体，数据被保护在抽象数据类型的内部，尽可能地隐藏内部的细节，只保留一些对外接口使之与外部发生联系。系统的其他对象只能通过包裹在数据外面的已经授权的操作来与这个封装的对象进行交流和交互。也就是说用户是无需知道对象内部的细节，但可以通过该对象对外的提供的接口来访问该对象。

对于封装而言，一个对象它所封装的是自己的属性和方法，所以它是不需要依赖其他对象就可以完成自己的操作。使用封装有以下好处：

良好的封装能够减少耦合。
类内部的结构可以自由修改。
可以对成员进行更精确的控制。
隐藏信息，隐藏具体的实现细节。

函数重载、运算符重载

函数重载：

函数重载是指在同一作用域内，可以有一组具有相同函数名，不同参数列表的函数，这组函数被称为重载函数。重载函数通常用来命名一组功能相似的函数，这样做减少了函数名的数量，避免了名字空间的污染，对于程序的可读性有很大的好处。

注意：不能仅通过返回类型的不同来重载函数。

#include <iostream>
using namespace std;

int add(int a, int b) {
    return a + b;
}

double add(double a, double b) {
    return a + b;
}

int pow(int x) {
    return x * x;
}

int pow(int x, int n) {
    if (n < 0) return -1;    //暂不支持指数为负
    int result = 1;
    while (n--) {
        result *= x;
    }
    return result;
}

int main() {
    int ans1 = add(1, 2);
    double ans2 = add(2.2, 3.14);
    int ans3 = pow(3);
    int ans4 = pow(3, 3);
    cout << ans1 << endl;
    cout << ans2 << endl;
    cout << ans3 << endl;
    cout << ans4 << endl;
    return 0;
}

运算符重载：

#include <iostream>
#include <string>
using namespace std;

struct Fraction {
    int numerator;        //分子
    int denominator;    //分母

    Fraction() {}
    Fraction(int numerator, int denominator) {
        if (denominator < 0) {
            numerator = -numerator;
            denominator = -denominator;
        }
        this->numerator = numerator;
        this->denominator = denominator;
    }

    Fraction operator+ (Fraction other) {
        int num1 = this->numerator * other.denominator
            + this->denominator * other.numerator;
        int num2 = this->denominator * other.denominator;
        return Fraction(num1, num2);
    }

    friend Fraction operator - (Fraction frac1, Fraction frac2) {
        int num1 = frac1.numerator * frac2.denominator - frac1.denominator * frac2.numerator;
        int num2 = frac1.denominator * frac2.denominator;
        return Fraction(num1, num2);
    }

    friend bool operator < (Fraction frac1, Fraction frac2) {
        return (frac1 - frac2).numerator < 0;
    }

    string toString() {
        // <string>头文件中的 to_string 函数可将 数值类型 转为对应的 string类型
        return to_string(numerator) + '/' + to_string(denominator);
    }
};

int main() {
    Fraction a(1, 2), b(3, 4);
    Fraction ans = a + b;
    cout << ans.toString() << endl;
    if (a < b) cout << "a < b" << endl;
    return 0;
}

#include <iostream>
using namespace std;

struct Array {
    int data[1000];
    int size = 0;

    void push_back(int e) {
        data[size++] = e;
    }

    int& operator[](int i) {
        return data[i];
    }
};


int main() {
    Array arr;
    for (int i = 1; i <= 5; i++) {
        arr.push_back(i);
    }

    for (int i = 0; i < arr.size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    arr[2] = 100;

    for (int i = 0; i < arr.size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

特殊的运算符重载

重载赋值运算符

深复制

Stack& operator= (const Stack& other) {
    if (_elem != NULL) {
        delete[] _elem;
    }
    _size = other._size;
    _capacity = other._capacity;
    _elem = new int[_size];
    for(int i = 0; i < _size; i++) {
        _elem[i] = other._elem[i];
    }
    return *this;
}

模版类、模板函数（泛型）

模板类：

#include <iostream>
#include <string>
using namespace std;

template<typename T>
class Stack {
private:
    const int DEFAULT_CAPACITY = 100;
    int _size;
    T* _elem;
    int _capacity;

public:
    Stack() {
        _elem = new T[DEFAULT_CAPACITY];
        _size = 0;
        _capacity = DEFAULT_CAPACITY;
    }

    Stack(int _capacity) {
        _elem = new T[_capacity];
        _size = 0;
        this->_capacity = _capacity;
    }

    ~Stack() {
        delete[] _elem;
    }

    void clear() {
        _size = 0;
    }

    void push(const T& e) {
        if (_size >= _capacity) throw exception("stack is full");
        _elem[_size++] = e;
    }

    T& pop() {
        if (_size <= 0) throw exception("stack is empty");
        return _elem[--_size];
    }

    T& top() {
        if (_size <= 0) throw exception("stack is empty");
        return _elem[_size - 1];
    }

    int size() {
        return _size;
    }

    bool empty() {
        return _size == 0;
    }

    void print() {
        for (int i = 0; i < _size; i++) {
            cout << _elem[i] << " ";
        }
        cout << endl;
    }
};

int main() {
    Stack<int> s1;
    s1.push(2);
    s1.push(3);
    s1.print();

    Stack<double>* s3 = new Stack<double>(10);

    Stack<string> s2;
    s2.push("hello");
    s2.push("world");
    s2.print();

    return 0;
}

模板函数：

#include <iostream>
#include <string>
using namespace std;

template<typename T>
T max1(const T &a, const T &b) {
    if (a > b) return a;
    return b;
}

int main() {
    double ans1 = max1(2.2, 3.3);
    cout << ans1 << endl;

    string str1 = "a", str2 = "aa";
    string ans2 = max1(str1, str2);
    cout << ans2 << endl;

    return 0;
}

命名空间namespace

命名空间可用来区分不同库中相同名称的函数、类、变量等。

可以使用 using namespace指令，这样在使用命名空间时就可以不用在前面加上命名空间的名称。这个指令会告诉编译器，后续的代码将使用指定的命名空间中的名称

#include <iostream>
using namespace std;

// 第一个命名空间
namespace first_space{
   void func(){
      cout << "Inside first_space" << endl;
   }
}

// 第二个命名空间
namespace second_space{
   void func(){
      cout << "Inside second_space" << endl;
   }
}

int main () {
   // 调用第一个命名空间中的函数
   first_space::func();

   // 调用第二个命名空间中的函数
   second_space::func(); 

   return 0;
}

异常处理

异常是程序在执行期间产生的问题。C++ 异常是指在程序运行时发生的特殊情况，比如尝试除以零的操作。

异常提供了一种转移程序控制权的方式。C++ 异常处理涉及到三个关键字：try、catch、throw。

throw: 当问题出现时，程序会抛出一个异常。这是通过使用 throw 关键字来完成的。
catch: 在您想要处理问题的地方，通过异常处理程序捕获异常。catch 关键字用于捕获异常。
try: try 块中的代码标识将被激活的特定异常。它后面通常跟着一个或多个 catch 块。

4. C++标准模版库 STL

STL容器使用了模板语法，都是模板类。在使用时需要使用<>指定容器存放元素的类型。

1. stack

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> S;
    for (int i = 0; i < 10; i++) {
        S.push(i);
    }
    S.pop();
    printf("%d\n", S.top());
    printf("S.empty()? %s\n", S.empty() ? "YES" : "NO");

    return 0;
}

2. vector

vector字面意思是向量，这里可理解为可扩容数组

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> V;
    for (int i = 0; i < 10; i++) {
        V.push_back(i);
    }
    V.pop_back();
    printf("%d %d\n", V.front(), V.back());

    for (int i = 0; i < V.size(); i++) {
        printf("%d ", V[i]);
    }
    printf("\n");

    return 0;
}

struct BinTreeNode{    //二叉树节点
    int data;
    BinTreeNode *lchild, *rchild;
}

struct TreeNode{    //（一般）树节点
    int data;
    vector<TreeNode*> child;
}

3. string

cout与printf不能混用，cin与scanf不能混用

#include <iostream>
#include <string>
using namespace std;

string numToEnglish(int num) {
    if (num < 0 || num > 9) return "";
    static string temp[] = { "zero","one","two","three","four" };
    return temp[num];
}

int main() {
    string str1 = "hello world";
    cout << str1 << " " << str1.length() << endl;
    for (int i = 0; i < str1.length(); i++) {
        printf("%c", str1[i]);
    }
    printf("\n");

    string str2;
    cin >> str2;
    printf("%s\n", str2.c_str());

    string str3 = numToEnglish(2);
    printf("%s\n", str3.c_str());

    return 0;
}

string重载了+、+=运算符，可用于字符串拼接

string str1 = "hello";
str1 += " ";
string str2 = "world";
printf("%s\n", (str1 + str2).c_str());

string重载了>、 < 、>=、<=、 ==、 !=运算符，可以用字典序对字符串进行大小比较

str1 = "aa"; str2 = "aaa"; str3 = "ab";
str1 < str2     //true
str3 > str2        //true

STL容器只能用string，不能用char[]

vector<string> V;
map<string, int> strToIndex;
map<int, string> indexToStr;

4. queue

push(x)、pop()、front()、back()、empty()、size()

5. map

#include <iostream>
#include <map>
using namespace std;

int main(){
    map<char, int> mp;
    mp['a'] = 1;
    mp['A'] = 10;
    printf("%d", mp['A']);

    if (mp.find('B') == mp.end()) {    //map的查找指定的key
        mp['B'] = 20;
    } 
    printf("%d\n", mp['B']);
    return 0;
}

用于建立字符串与整数之间的映射
对于图论很多题，你需要用一个二维数组（邻接矩阵）将题目所给的图存储起来，但很多时候题目所给的图的顶点并非是用0~N编号的，这个时候你需要自己为其编号，即建立顶点名到编号的双向映射关系。

chengdu shanghai 10
chengdu beijing 20
beijing shanghai 30
chongqin chengdu 5

chengdu-0 shanghai-1 beijing-2 chongqin-3     //为每个城市分配一个编号
int G[maxn][maxn];
G[0][1] = 10;
G[0][2] = 20;
G[2][1] = 30;
G[3][0] = 5;

#include <iostream>
#include <map>
#include <string>
using namespace std;
const int MAXN = 105;

map<int, string> indexToStr;    //从编号到地名的映射
map<string, int> strToIndex;    //从地名到编号的映射

int cnt;
int G[MAXN][MAXN];

int assignNumber(string str) {
    if (strToIndex.find(str) == strToIndex.end()) {    //如果没有对该地名分配编号，则为其分配
        strToIndex[str] = cnt;
        indexToStr[cnt] = str;
        cnt++;
    }
    return strToIndex[str];
}

int main() {
    int N;
    cin >> N;
    for (int t = 0; t < N; t++) {
        string str1, str2;
        int dist;
        cin >> str1 >> str2 >> dist;
        int index1 = assignNumber(str1);
        int index2 = assignNumber(str2);
        G[index1][index2] = dist;
    }
    //.......
}

用于记录某个大数是否出现过，可当成bool数组来用

map<int, bool> isExist;

6. sort函数

sort(首元素地址， 尾元素下一个的地址);    //元素可以直接比较大小(<)
sort(首元素地址， 尾元素下一个的地址, 比较函数);    //元素不能直接比较

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N = 6;
    int A[] = { 2, 1, 6, 4, 3, 0 };

    vector<int> vec;
    for (int i = 0; i < N; i++) vec.push_back(A[i]);

    sort(A, A + N);
    sort(vec.begin(), vec.end());

    return 0;
}

比较函数

a在b的前面，返回true，否则返回false；

bool cmp1(int a, int b) {    //从小到大
    return a < b;
}

bool cmp2(int a, int b) {    //从大到小 cmp(1,5)
    return a > b;
}

sort(A, A + N, cmp1);
sort(A, A + N, cmp2);

结构体数组

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Stu {
    int chinese;
    int math;
    Stu() {}
    Stu(int a, int b) { chinese = a; math = b; }

    friend bool operator < (Stu &a, Stu &b) {
        int total1 = a.chinese + a.math;
        int total2 = b.chinese + b.math;
        if (total1 != total2) {
            return total1 > total2;
        }
        return a.math > b.math;
    }
};

Stu student[100];

bool cmp(Stu &a, Stu &b) {
    int total1 = a.chinese + a.math;
    int total2 = b.chinese + b.math;
    if (total1 != total2) {
        return total1 > total2;
    }
    return a.math > b.math;
}

int main() {
    freopen("input.txt", "r", stdin);
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d %d", &student[i].chinese, &student[i].math);
    }

    //sort(student, student + N, cmp);
    sort(student, student + N);
    for (int i = 0; i < N; i++) {
        printf("%d %d\n", student[i].chinese, student[i].math);
    }
    return 0;
}

7. fill函数

fill(首元素地址， 尾元素下一个的地址, 填充的值);

字符串转换

程序读入一行字符串（可能含空白字符），将其中的大写字母转成小写，小写的转换成大写。

Sample Input:

abc 12@DeFg

Sample Output:

ABC 12@dEfG

参考代码：

#include <iostream>
#include <string>
using namespace std;

void convertStr(string &str) {
    int len = str.length();
    for (int i = 0; i < len; i++) {
        char ch = str[i];
        if (ch >= 'a' && ch <= 'z') {
            str[i] = ch + 'A' - 'a';
        } else if (ch >= 'A' && ch <= 'Z') {
            str[i] = ch + 'a' - 'A';
        }
    }
}

int main() {
    string str;
    getline(cin, str);    //读入一行
    convertStr(str);
    printf("%s\n", str.c_str());
    return 0;
}