跳到主要内容

程序设计复习

基本语句

表达式与运算符

&&、||需要考虑它们算完一个就不算了的可能

  • 运算符优先级::: > ()->.++(后缀)> !++(前缀)> 算术运算符 > 关系运算符(其中==!=优先级低于剩下四个)> 逻辑与 > || > 赋值运算符 > 逗号运算符
  • (a=b)<5a=b<5 的区别
  • 注意 === 的区别
  • 逻辑表达式从左到右计算
  • 逗号表达式的值是最后一个基本表达式的结果值

分支程序

区别情况,执行相应语句

if

  • if() {XXX;} if() {XXX;}else {XXX;}
  • 嵌套规则:else子句与它之前最近的一个没有else子句的if配对(或者用大括号括起来表示优先级)

条件表达式(问号冒号运算符)

  • (x>y)?x:y 可以把表达式的值直接赋给左值
  • << 的优先级比 ?: 运算符的优先级高(使用须加括号)

switch

  • 顺着执行,default可以被省略;常量表达式中必须是常量
  • 若想要执行完了就跳出,在每个语句后面加break;如果想让两个相邻的情况得出的结果一样,中间不要加break;每种情况后面允许加多个语句,最多再加一个break;但是常量表达式的值不能相同

循环程序设计

重复某一段代码

  • 注意:在循环后面直接加一个分号,编译器会认为循环结束了

for

  • for(int i=0;i<n;i++) {循环体} 循环体内的所有语句执行一次叫做一个循环周期;看到for的时候,先判断i是否符合循环条件,但不改变步长
  • for(int i:{1,9,6,8,3}) 或遍历数组 for(int x:a)
  • 定义在循环控制行中的变量在循环结束时被销毁
  • Windows:Ctrl+c终止程序
  • break语句也可用于跳出当前的循环语句,直接终止循环
  • continue语句的作用是跳出当前循环周期,继续进行下一个循环

while(基于哨兵的循环)

  • while(){;} 括号内表达式为假,循环终止,一开始为false,循环直接寄掉

do-while

  • 保证循环至少执行一次
  • do{;}while(); 注意末尾是有分号的

数组与指针

数组

解决处理大批量同类数据的问题。下标从0开始;不能直接赋值,必须用循环赋值;不能直接用cincout输入输出,字符数组除外。

静态变量

动态变量(写程序时无法确定它们的存在,在程序运行时,根据程序的需求动态产生和消亡的变量)

  • 定义指针→申请空间(从堆中申请)→地址存入指针→释放动态变量的空间
  • 创建动态变量:int *p; p=new int(10); int *p; p=new int[n]; 其中n可以为变量
  • 初始化动态变量(对象):p=new int(5);
  • 释放动态变量所处的空间:delete p; delete [] p;
  • 内存泄漏:没有delete变量造成的后果(原因有2),可能会耗尽内存
  • delete掉一个不存在的动态变量:
    • 一个动态变量删了两次
    • 申请变量,但使得指针指向了别的动态变量,这时删去指针指向的动态变量也会导致程序寄掉
  • 动态数组与函数:动态数组在函数内外都可以使用(只要没有被delete掉)
  • 查找new是否成功:
    • new不成功时返回空指针,利用这一点判断
    • 使用 assert() 发出错误消息后自动终止程序:#include <cassert>int *p; p=new int; assert(p!=0);

字符串(一系列有序数组组成的一个处理单元)

  • 看做一个数组存储与初始化:
    • 一个一个往里敲
    • char ch[]={"LOVEC++"} 或者不加括号
    • 分配一个数组,最后插入 '\0';存储时须+1
    • 用字符数组存储字符串时,可以直接输入输出(其他都不行)
  • #include <cstring> strcpy, strcat函数中dst必须是字符数组,否则会出现内存溢出;字符串比较:从左往右逐个字符比较内码
  • 用指针表示:
    • 将字符串常量赋给指向字符的指针变量(其实也相当于把首地址赋给了指针)(但由于该指针指向的是一个常量,因此不能修改字符串中的任何一个字符,也不能把它作为strcpy函数的第一个参数)
    • 字符数组名赋给一个指针(字符串在栈中)
    • 申请动态字符数组给一个指向字符的指针(字符串在堆中)
    • char *s="i love c++"; 这个指针实际指向了一个字符串常量
    • 可以改变这个指针指向的位置,但不能改变这个指针指向的内容(若把它声明为数组就可以)

指针

保存另一个变量地址的变量

  • 直接访问:通过变量名访问;间接访问:通过指针变量访问
  • int *p 指向不同类型的指针占内存相等(占用4个字节);指针指向的变量的类型称为指针的基本类型;定义指针时每个变量都要有 * 标志
  • 赋值:程序某一变量的地址赋给指针变量/其他(相同类型)指针的地址赋给指针变量;*p=&x p1=p2(&取址运算符,后面不能跟右值)
  • 访问:* 返回指针指向的变量的值,对其做计算,也会改变指针指向变量的值
  • 统配指针 void *指针变量名 任何类型的指针都可以对它赋值

指针与常量限定符

  • 指向常量的指针:const int *p=&x; 对象不能修改,但指针的指向可以修改(指到谁谁就寄)
  • 指针常量:int *const p=&x; 指针自己被定住了,但是它指向的常量是可变的
  • 指向指针的指针常量,以上两者的加和;const加在哪里哪部分就是常量

数组名与指针

  • 由于数组名实际上就是一个指针常量,所以可以把数组名中的地址赋给其他的指针;但指针实际与数组无关,只有将数组名赋给指针后,指针才与数组名有了类似的功能
  • 指针和指针之间可以相互赋值,但数组之间不能相互赋值
  • 不要引用未被赋值的指针!可以向不用的指针赋空指针NULL

指针数组

  • char *ch[10]

指向函数的指针(通过指针调用某个函数)

函数

特定功能语句封装,取名为函数名,自变量称为参数,函数值称返回值

  • 无返回值的函数常常被称为过程
  • 返回布尔值的函数也称为谓词函数
  • 调用前声明原型:返回类型 函数名(形参类型 形式参数名字);(必须以分号结束)

函数调用

参数传递(输入参数一般用值传递,输出参数必须用指针传递)

  • 值传递(对形式参数的修改对实际参数无影响)
    • 避免写出与实际参数计算次序有关的调用
  • 引用传递
    • 常量的引用传递
  • 指针传递
    • 数组传递本质上是指针传递,也就是首地址传递,所以形式参数中数组的大小是无意义的;若需要,需要单独传递元素个数
    • 二维数组作为参数传递:第一维的个数可以省略,第二维必须指定
    • 由于字符串有特定的结束标志 \0,故而传递字符串时,通常使用指向字符的指针而非字符数组,也不需要指出字符串的长度

:调用函数时,系统给函数分配的内存空间

函数调用时,定义的变量创建在栈中(事实上多个函数嵌套时,确实是先进后出的)

带默认值的函数

  • 在定义/声明时赋值,相当于指定了默认值,未指定实际参数时直接用默认值
  • 有默认值的参数放在参数表的右边
  • 声明时指定,声明和定义不能同时指定默认值
  • 同一源文件中,一个参数匹配一个默认值

返回指针的函数

  • 只需在函数名前加 *
  • 也允许将函数作为左值使用

引用类型作为参数的函数

引用:给变量取一个别名(注意区分引用和取址)

  • 带来指针的效果,避免指针的问题
  • int i; int &j=i;(指定初值是必须的)
  • 引用的初值可以是另一个引用
  • 引用与变量之间的绑定是永久的
  • 引用类型可以是常量:int a; const int &b=a;,b的值只能通过a的值修改
  • 实际参数必须为左值(有地址)
  • 指针作为函数参数时必须用引用 *&i,因为若不用引用,在函数内改变指针所指的位置是无效的(考虑复制构造函数,相当于复制了一个新指针)

返回引用的函数

  • 相当于直接返回 return 之后的变量(该变量一般是全局变量或者程序内的动态变量,在执行结束后依然存在)
  • 好处是可以将函数作为左值参与运算

内联函数

  • 用于本身比较小,运行时间短的函数
  • 产生函数代码的多个副本,使得目标代码变长
  • 返回类型前加 inline
  • 定义在被调用之前

重载函数

  • 允许参数个数不同、类型不同的两个以上的函数取相同的函数名(但不考虑返回值!!!)
  • 共用一个函数名称:函数重载;一组函数称为:重载函数
  • 对编译器的考验:绑定,根据实际参数和形式参数的匹配来决定

函数模板

实现类型的参数化。仅仅是参数类型不同,逻辑完全一样(符号代替类型,代码相同)

  • 可变的参数:模板参数
  • template <class T> T max(T a, T b){函数体}(T1,T2是不同类型)
  • 调用时:模板的实例化,实例化后的函数,称为模板函数
  • 若编译器难以推断实际参数的值,可以在调用时显式指定模板实参 calc<int,char,char>(5,'a')
  • 调用指向函数模板的指针时,编译器可能无法确定类型,所以可能需要显式指定模板的实际参数

递归函数

调用自身的函数

  • 函数体
  • 递归信任:信任函数的调用可以得到正确结果
  • 包装函数:调用递归函数,传递递归函数所需的额外参数的函数

变量的储存类别与内存分配

变量的作用域(有效范围)

全局变量(定义出现在所有函数定义之外)(存在全局变量区,源文件及相关的源文件都可以使用)

  • 作用域:定义它位置之后的其余部分

局部变量(在函数内部定义的变量)

  • 作用域:定义它的函数或者程序块

全局变量与局部变量同名时,在局部变量的作用域中全局变量被屏蔽

变量的存储类别

决定生存期限,一般写在数据类型前面

自动变量(局部变量,形参,程序块中的,都是自动变量)(auto)

  • 在栈中分配一块区域(帧)
  • 函数执行结束时,回收该帧的空间

静态变量(static)(函数也可以在前面加static,来声明其为源文件私有)

  • 分为:静态的全局变量(单个源文件引用)、静态的局部变量(下次调用时仍使用该值)
  • 初始为0
  • 初值在编译时赋,重复调用不改变值
  • 其他函数不能调用
  • 先消亡静态的局部变量,再消亡全局变量

寄存器变量(register)

  • 频繁使用的变量
  • 必须是局部自动变量

外部变量(声明,而非定义)(一定是全局变量)

  • 引用其他源文件中的函数,使得各文件共享全局变量
  • 最好在比较开头的地方定义
  • 可省略类型名

内存分配

  • 静态分配:全局变量(出现在所有函数定义之外)与静态变量,在整个程序运行期间都存在
  • 自动分配:局部变量分配在栈中,函数被调用,空间被分配;函数执行结束,空间被释放
  • 动态分配:从堆中分配空间,需要显式申请

常用技巧与算法

随机数生成

  • #include<cstdlib>
  • rand() 函数生成一个0~RAND_MAX之间的整数(32767 in Visual C++)
  • rand()%10 rand()*(max-min+1)/(RAND_MAX+1)+min
  • 生成的随机数相同?——因为随机数的种子相同!(计算机不能产生随机数,只能产生伪随机数)
  • 将系统时间设为种子(#include <ctime>),开头写一行代码 srand(time(NULL));

小技巧

  • 魔阵中的回绕:寻找下一行:(row+1)%N;寻找上一行:(row-1+N)%N
  • 数组的逆序:for(i=0;i<size/2;i++){int tmp=array[i]; array[i]=array[size-i-1]; array[size-i-1]=tmp;}
  • 字符串数/非负整数转换为整数并输出:采用循环 / 采用递归

枚举法

注意取一个比较简单的条件作为约束条件以简化程序的步骤

贪婪法

得到局部最优解,而非全局最优解

查找

顺序查找(复杂度为 O(n)O(n)

二分查找

int low, high;
while (low <= high) {
mid = (low + high) / 2;
if (x == array[mid]) break;
if (x < array[mid]) high = mid - 1;
else low = mid + 1;
}

最后如果low的值大于high,则没有找到。复杂度:O(log2n)O(\log_2 n)

排序

直接选择排序法

for (lh = 0; lh < n; ++lh) {
rh = lh;
for (k = lh; k < n; ++k) {
if (array[k] < array[rh]) {
int tmp = array[rh];
array[rh] = array[k];
array[k] = tmp;
}
}
}

时间复杂度 O(n2)O(n^2)

冒泡排序法

for (i = 0; i < n; i++) {
flag = false;
for (j = 0; j < n - i - 1; j++) {
if (a[j+1] < a[j]) {
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = true;
}
}
if (!flag) break;
}

在数字原本就有一定顺序的情况下,冒泡排序的复杂度低于选择排序,但逆序时:时间复杂度 O(n2)O(n^2)

回溯法

试试就试试,不行就退回去

分治法

将大问题分解成多个小问题

  • 快速排序(核心代码)
  • 寻找最长连续子序列(注意分类讨论)

动态规划

由小问题开始,构建规模稍大的问题的解

  • 找零问题
  • 求斐波那契数列(由于数列的特性,只需要用两个数就可以,不需要用数组)

结构体

记录

程序设计语言中,一组无序的异质的数据看作一个整体。C++称其为结构体。

  • 每个组成部分称为字段(成员)

使用记录

定义一个新的结构体类型

  • struct studentT{;;};
  • 字段名可以与程序的变量名相同,不同的结构体也可以有相同的字段名
  • 结构体成员可以是其他的结构体,但不能自我引用(造成无穷嵌套循环)
  • 可以在定义之后直接定义结构体类型的变量

使用结构体

  • 结构体只能相互赋值,不能整体操作;输入结构体相当于挨个输入它的每个成员(与数组的区别:数组不是左值,结构体是左值)
  • student1.chinese 这样访问结构体类型变量中的某个字段,相当于一个普通变量
  • 利用指向结构体的指针访问结构体中的成员:
    • (*sp).chinese(括号的使用:. 运算符的优先级更高)
    • sp->chinese
    • 若指针 p 指向的是相关结构体的数组,则 p->,当指针单独使用时;p[1]. 当指针与数组有相同的功能时

结构体作为参数

  • 值传递(浪费空间和时间)
  • 使用const的引用传递 const student &s1

链表

数据结构,储存一组同类数据,可以动态地进行内存分配

  • 单链表的定义:struct linkNode{int data; linkNode *next;};(自引用结构)
  • 创建单链表:linkNode *head, *p, *rear; head=rear=new linkNode;
  • 插入单链表:linkNode *p; p=new linkNode; p->data=x; rear->next=p; rear=p; /*循环结束*/ rear->next=NULL;
  • 删除单链表:linkNode *tmp; tmp=p->next; p->next=tmp->next; delete tmp;(这种删除方法要求每个被删除的数据前面都要有另一个数据,所以要在链表的开头加入头结点)
  • 读链表:p=head->next; while(p!=NULL){cout<<p->data<<endl; p=p->next;}
  • 约瑟夫环问题:单循环链表,用两个头尾纠缠的指针实现报数
  • 数组不便于插入和删除,难以变换顺序;链表便于插入和删除以及改变顺序,但是难以查找第i个元素

模块化开发

结构化程序设计

自顶向下,逐步求精

模块

由整个程序的一部分组成的较小的源文件

  • 模块划分的原则:同一模块功能类似,不同模块联系少
  • 符号常量定义、类型定义、函数原型声明写入头文件,之后让每个模块include之。但这样会使相关声明在程序中反复出现多次,编译器认为这些符号被重复定义,报错。须写入代码(头文件保护符)#ifndef mycpph #define mycpph ... #endif 作为编译预处理命令。最好每个头文件都要有(含义:若已被定义,直接跳过;没有定义,就执行之)
  • 在头文件中定义的变量并不是真正的变量定义,而是变量声明。变量定义是将变量分配到内存中的过程,而变量声明只是告诉编译器变量的类型和名称。
  • 在头文件中定义并初始化变量,那么每次包含头文件时,都会创建该变量的一个新实例,这可能导致多个源文件中变量不同步的问题。

设计和实现库(实现隐藏)

头文件与实现文件一般取相同的名字

  • 设计库的接口(头文件):包括库中函数原型,相关注释,函数用到的符号常量和自定义类型
  • 设计库中函数的实现(源文件):注释介绍功能,include相关头文件

特点

  • 代码重用
  • 实现隐藏(类的实现方法)
  • 多态性(对一个基类发出指令,派生类会相应地发生变化)(程序扩展比较容易)

类的继承或派生

原类叫做基类或父类,新建的类叫做派生类或子类

相比结构体的优势

  • 函数就在类中,省去调用结构体花费的空间和时间
  • 不会引起函数名的冲突

与结构体之间的区别

  • 结构体不指明——成员公有
  • 类不指明——成员私有

类的组成

  • 数据成员:定义类的一组属性
  • 成员函数:类中的函数(工具函数:解决类内部的工作的函数,通常设为私有成员)
    • 写在实现文件中
    • 定义在类中(为内联函数)

定义方法

class 类名{private: ;; public: ;;};

  • 私有成员只能被自己类中的成员函数访问,不能被全局函数访问
  • 公有成员可以通过 变量名.成员函数名 来访问

this指针

成员函数访问对象整体的时候需要显式地使用this指针 *this

构造函数与析构函数

均为系统自动调用

构造函数

  • 定义:类名 对象名(实际参数表);
  • 可以重载
  • 没有返回值也不需要返回值,不能指定返回类型
  • 不带参数的叫默认构造函数
  • 在声明构造函数时可以指定默认值,在函数头和函数体之间可以包含一个构造函数初始化列表
  • Fun::Fun(int a, b):a1(a),b1(b){...;}
  • 采用初始化列表,可以使数据成员的初始化和赋初值同时进行,提高函数的效率
  • 必须使用初始化列表的情况:
    • 数据成员不是内置类型,而是某一个类的对象,无法使用赋值语句赋初值
    • 包含常量的数据成员,只能在定义时对它初始化

复制构造函数(用同类的对象对其初始化)

  • Fun(const Fun &something);(注意是参数传递捏,值传递会造成递归捏)
  • 调用复制构造函数的场景:
    • 对象定义(使用一个已经存在的对象来定义另一个对象)
    • 函数调用(特指值传递函数,会复制实际参数给形式参数)
    • 函数返回(return后面的值是自定义类,也会调用复制构造函数)

析构函数(在对象生命周期结束时自动回收空间)

  • 默认析构函数为空
  • 无返回值
  • 不能重载
  • ~Fun(){;}

const与类

常量数据成员

  • 每个数据成员都有
  • 只能初始化,不能赋值
  • 只能使用构造函数的初始化列表初始化

常量对象

常量成员函数

  • 告知编译器该成员函数不会改变对象的数据成员值
  • 常量对象只能调用常量成员函数
  • 定义时,类定义和成员函数定义都要定义
  • void display() const {;}

静态成员

静态数据成员

  • 属于类,名字只在类的范围内有效,公有私有函数都可以调用
  • static int a;(在类的定义中)
  • int Fun::a=0.05;(在类的实现文件中)
  • 调用:Fun::a

静态成员函数

  • 操作静态数据成员,对类而非类的对象服务
  • 定义:static void a(){;} 可以在类中,也可以在类外;在类外时前面不用加static
  • 调用:Fun::a()(也可以通过对象调用,但只能访问静态成员变量)
  • 没有隐含的this指针

静态常量成员

  • 类的所有对象共享的常量成员
  • 必须在类定义时初始化
  • 实现:static const int a=42;enum{a=42};

友元

不放弃私有成员安全性的前提下,使得全局函数或者其他类的成员能够访问类的私有成员

  • 友元函数:在类中声明 friend void f();
  • 友元类:在类中声明 friend class B;
  • 友元成员函数:在类中声明 friend void B::f();
  • 关系:不对称,也不传递

组合(包含)和继承(衍生)

组合:已有类的对象作为新定义类的数据成员

  • 一个类的对象作为另一个类的对象,则该对象为"对象成员"
  • 对象成员难以直接赋值,且不能用默认构造函数进行初始化,则必须用构造函数的初始化列表来初始化

继承:已有类的基础上扩展形成新类(运行多态性的基础)

  • 基类、父类 → 派生类、子类(添加数据成员与成员函数,更具体)
  • 作用:支持软件重用、分类、增量开发
  • 定义:class a2:public a1{...};
    • 继承方式:public、private与protected,说明访问特性,默认private
    • protected是特殊的私有成员,不能被全局函数和其他类的成员函数访问,但可以被派生类的成员函数和友元函数访问
    • 默认public继承;protected访问特性的成员破坏了类的封装,因为它变了之后,所有派生类都被修改
  • 构造函数、析构函数
  • 重定义基类的函数:
    • 功能扩展:写一个与基类完全相同的函数吧!派生类对象只能看到新定义的函数!
    • 所以要调用基类的公有成员函数
  • 派生类作为基类:直接调用基类的构造函数即可,不用管其他,这个递归只有一层

派生类可以转换为基类对象(反之则不行,除非有类型转换函数)

  • 赋值:仅把基类部分赋给基类对象
  • 基类指针指向派生类对象:只访问基类部分,不能访问派生类,调用的函数也都是基类中的函数(硬要引用派生类会出错的)
  • 基类对象引用派生类对象
  • 注意:派生类指针可以给基类指针赋值。但反之不行。若确信基类指针指向派生类并且想要赋值,可以使用强制类型转换 a=reinterpret_cast<Derived*>(b);

多态性

编译时:静态绑定(运算符重载,重载函数)

运行时:动态绑定(根据指针指向的对象,决定调用的函数)

  • 实现:虚函数、基类指针指向不同的派生类的对象
  • 虚函数:函数原型前面加关键字 virtual,在派生类中定义时,函数原型必须与基类中的虚函数完全相同(virtual 可写可不写)
  • 虚析构函数:将基类的析构函数定义为虚函数,这样就可以把派生类的对象完全析构了
  • 纯虚函数:在基类中声明的虚函数
    • 基类中没有定义,在派生类中定义
    • virtual void fun() const = 0;
  • 抽象类:一个类中至少含有一个纯虚函数
    • 无法定义抽象类的对象,但可以定义指向抽象类的指针,指向派生类的对象
    • 派生类若不重新定义,派生类仍为抽象类
    • 保证进入继承层次的每个类都有纯虚函数要求的行为

输入与输出

几种类型

  • 层次:低层次(对字节操作)、高层次(对整型数之类操作)
  • 格式:无格式(传输速度快)、有格式(按照不同类型、格式处理数据)

输入输出类

基于控制台 (iostream)

  • cerr类,ostream类的对象,与标准的错误设备相关联,没有缓冲
  • clog类,同上,但有缓冲

基于文件 (fstream)

  • 相关概念:
    • 数据项:数据的基本单位
    • 相关的数据项组成一个记录(也被看做一个对象)
    • 文件:驻留在外存储器上、具有一个标识名的一组信息集合,永久保留数据;记录的一组集合
    • 一组相关的文件构成了数据库
  • 流式文件:没有记录的概念,文件是字节序列,以EOF结束(看作字符串)
  • 分类:
    • ASCII文件:文本文件,每字节看做ASCII值,可以直接显示
    • 二进制文件:每字节看做二进制比特串,由程序解释,一般不能显示

访问文件

  • 定义文件流对象:
    • ifstream读,ofstream
    • ifstream infile; infile是一个输入文件流对象,需要将它与一个具体的文件相关联
    • 定义对象后,这个对象可以理解为就是这个文件本身(输入输出时)
  • 打开、关闭文件:
    • 关联具体文件:infile.open("file1") / infile.open("file1",ifstream::in); / ifstream infile("file1") / ifstream infile("file1",ifstream::in)
    • 使用out会清空(在不指定in的情况下),所有文件都可以用ate与binary模式打开
    • 检查是否打开成功:if(!infile){cerr<<"create file error\n"; return 1;}
    • 断开关联:file1.close();最好显式地关闭文件!
  • 顺序读写:用流提取运算符(<< >>)读数据时,以空白字符作为分隔符;想读取空白运算符就用getline
  • 随机访问:
    • 文件定位指针(long型,表示读写的是文件的第几个字节)
    • tellg 读文件定位指针 / tellp 写文件定位指针
    • 看看读文件定位指针:location = in.tellg();
    • seekg / seekp
    • in.seekg(10, ios::beg/cur/end)
  • 流式文件处理:
    • 要求:立即访问相关记录;插入数据时不破坏其他文件;不重写文件的情况下更新以前存储的数据
    • 写入语句:outFile.write(reinterpret_cast<const char*>(&number), sizeof(number));

基于字符串 (sstream)

输入输出过程(基于对象)

  • 程序与输入输出缓冲区的信息交互 → 输入输出缓冲区与外围设备的信息交互
  • >> 从缓冲区中存入变量,<< 将数据放入输出缓冲区
  • 缓冲区刷新:
    • 程序结束
    • 缓冲区已满
    • endl
    • 输入流输出流关联,一者的变化将改变另一者