复试C++

本文最后更新于：7 个月前

C++ 复试

  • 关于类的使用和方法定义
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;
class Test
{
public:
    void pointOut(int a);

private:
    int k, t, f;
};
void Test::pointOut(int a)
{
    k = a;
    t = a * 10;
    f = a / 2;
    cout << k << "  " << t << " " << f;
}
int main()
{
    Test myTest;
    myTest.pointOut(10);
    return 0;
}

条件编译指令

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
27
28
29
30
31
32
33
34
35
36
/*-------------------1-----------------------*/
//区分if-else语句
//条件编译的作用正式"选择性对代码编译"
#if 常量表达式1
    程序段1
#elif 常量表达式2
      程序段2
#else
        程序段3
#endif

/*-------------------2-----------------------*/
//ifdef语句
#ifdef 标识符
       程序段1

#else
     程序段2
#endif
/*-------------------3-----------------------*/
//ifndef语句
#ifndef 标识符
       程序段1

#else
     程序段2
#endif

//类型3常用来避免在头文件中重复引入
比如：文件1和文件2同时引入head.h
#include "head.h"
则需要在head.h写
#ifndef HEAD_H
#define HEAD_H
     ····
#endif

数组、指针、字符串

指针
  • 易混淆的点，指针指向常量与常量指针
1
2
3
4
5
6
7
8
9
10
int a = 3;
int b = 2;
const int *q = &a;//定义一个指向整形常量 a 的指针
*q = 10;//不能对该指针所指向的内容进行修改，只可以访问 read-only
/*-----------*/
int a = 3;
int b = 2;
int *const q = &a;//声明一个常量指针,不可修改其内容（即不能更换它指向的变量）
q = &b;//报错

  • 指向数组的指针
1
2
3
4
5
6
7
8
int a[10];
int *p=a;
int *q=&a[0];//两句等价,都是指向数组首地址

//通过指针访问数组
cout<<*p;//即 a[0]
cout<< *(p+i)//即 a[i]
*(p+i)=*(a+i)=a[i]

使用VSCODE+CMake 编译C++项目

  • 有点复杂，但应该是我没有理清楚思路
    • 用C++实现优先级队列
  • 但一次实践复习了不少知识
    • C++面向对象编程
    • c++工程开发的步骤
    • 大根堆小根堆的实现-优先级队列
1️⃣ 动态数组
  • 数组空间的首地址十分重要，不论是作为参数还是直接指向整个数组，首地址就相当于一个指向标，我们可以通过指针访问
1
2
3
int *p;//声明一个整型数组，为其创建首地址的空间
p = (int *)malloc(sizeof(int) * (10)); //声明了动态数组的空间大小为10个整型数据的空间
memset(p, 0, 10 * sizeof(int));//初始化数组内所有元素为0
2️⃣ 实现优先级队列
  • 需要将优先级队列封装成一个类，然后通过主程序生成对象来调用其内部的方法，也就是面向对象编程，先编写头文件
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
27
28
29
30
31
/*-----------------------myqueue.h----------------*/
//头文件声明myqueue类，这样可以被main.cpp调用，通过myqueue.cpp实现该类的具体方法，分工明确，而且独立性强
#ifndef MYQUEUE__H
#define MYQUEUE__H

//定义一个优先级队列，局限于比较整形数据
class priQueue
{
public:
    //放置方法,参数为 容量大小和堆的类型
    priQueue(bool compFunc);
    int pop(); //获取首元素，最大/小
    int size();
    int top();
    void insert(int e);
    bool isEmpty();

private:
    //cap为默认容量，comp表示建堆方式，curSize为当前已入队元素数量
    int cap = 100, comp, curSize = 0;
    int *pq;          //初始队列
    void swim(int e); //上浮
    void sink(int e); //下沉
    void exchange(int x, int y);//交换两数
    bool less(int x, int y);    //用于小根堆
    bool greater(int x, int y); //用于大根堆
    int parent(int root);//获得父节点的索引
    int lchild(int root);//获取左孩子索引
    int rchild(int root);//获取右孩子索引
};
#endif
  • 类方法的具体实现

实现优先级队列实际就是数据结构里的大根堆小根堆的思想，常见的大小根堆都是完全二叉树，又叫二叉堆。实现二叉堆的思想并不复杂，以实现大根堆为例子，主要步骤如下：

  1. 二叉堆其实就是一种特殊的二叉树（完全二叉树），只不过存储在数组里。一般的链表二叉树，我们操作节点的指针，而在数组里，我们把数组索引作为指针
  2. 将数组中第一使用的元素arr[1]作为二叉树的根的话，根据完全二叉树的性质，每个节点的父节点及其左右孩子的索引都可以通过简单的运算得到，而大/小根堆的性质特殊在于：（此处我们只讨论整型数据，其他数据类型类似思想）每个节点的数值都大于等于/小于等于其子节点的数值；那么arr[1]就是最值元素了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//获取右孩子索引
int rchild(int root)
{
    return root * 2 + 1;
}

//获取左孩子索引
int lchild(int root)
{
    return root * 2;
}
//获取父节点索引
int parent(int root)
{
    return root / 2;
}
  1. 由于上述的计算涉及乘除法，显然我们不能使用arr[0]作为首元素；实现二叉堆主要涉及操作如下面代码定义
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159

/*------------------myqueue.cpp-------------------------*/
#include <iostream>
#include <cstring>
#include "myqueue.h"

//实现priQueue的构造函数
priQueue::priQueue(bool compFunc)
{

    pq = (int *)malloc(sizeof(int) * (cap + 1));
    memset(pq, 0, (cap + 1) * sizeof(int));
    if (compFunc == true)
    {
        comp = 1; //建立大根堆,否则为小根堆
    }
    comp = compFunc; //设置好建堆方式
};

//获取首元素
int priQueue::top()
{
    return pq[1];
};

//返回堆大小
int priQueue::size()
{
    return curSize;
};

//判断是否为空队列
bool priQueue::isEmpty()
{
    return curSize == 0;
};

void priQueue::insert(int e)
{
    curSize++; //索引0无法参与寻找双亲与孩子节点的计算，必须从1开始
    //插入到队尾
    pq[curSize] = e;
    //上浮
    swim(curSize);
};

//删除并返回当前队列中的最值
int priQueue::pop()
{
    int max = pq[1];
    exchange(1, curSize);
    pq[curSize] = 0;
    curSize--;
    sink(1);
    return max;
}
/

bool priQueue::greater(int x, int y)
{
    return pq[x] > pq[y];
};
bool priQueue::less(int x, int y)
{
    return pq[x] < pq[y];
};
//下沉,显然只能用到队首和队尾元素进行改变
void priQueue::sink(int k)
{
    //大根堆
    if (comp == true)
    {
        while (lchild(k) <= curSize)
        {
            //假设左孩子更大
            int temp = lchild(k);
            //看右孩子是否比左孩子更大
            if (rchild(k) <= curSize && less(temp, rchild(k)))
            {
                temp = rchild(k);
            }
            //如果左右都不够
            if (less(temp, k))
            {
                break;
            }
            exchange(temp, k);
            k = temp;
        }
    }

    else
    { //小根堆
        while (lchild(k) <= curSize)
        {
            //假设左孩子更小
            int temp = lchild(k);
            //看右孩子是否比左孩子更小
            if (rchild(k) <= curSize && greater(temp, rchild(k)))
            {
                temp = rchild(k);
            }
            //如果左右都不够
            if (greater(temp, k))
            {
                break;
            }
            exchange(temp, k);
            k = temp;
        }
    }
};
//上浮
void priQueue::swim(int k)
{
    //大根堆,父节点比该节点小时上浮
    if (comp == true)
    {
        while (k > 1 && less(parent(k), k))
        {
            exchange(parent(k), k);
            k = parent(k); //k上升为父节点
        }
    }
    //小根堆反之
    else
    {
        while (k > 1 && greater(parent(k), k))
        {
            exchange(parent(k), k);
            k = parent(k); //k上升为父节点
        }
    }
};

//交换两数
void priQueue::exchange(int x, int y)
{
    int temp = pq[x];
    pq[x] = pq[y];
    pq[y] = temp;
};

//获取右孩子索引
int priQueue::rchild(int root)
{
    return root * 2 + 1;
}

//获取左孩子索引
int priQueue::lchild(int root)
{
    return root * 2;
}
//获取父节点索引
int priQueue::parent(int root)
{
    return root / 2;
}
刷题 C++算法
C++

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！