0%

多进程和多线程

现代操作系统通过多进程实现多任务宏观的并发执行

进程是资源分配的基本单元
线程是处理器调度的基本单位

进程和线程,不同操作系统的实现方式可能不同

进程通信
linux 进程通信方式:
管道:命名管道(mkfifo),父子进程间匿名管道 pipe,内核中利用文件实现
信号量:sem_init,sem_post 等,为了防止不同进程临界区资源产生问题,P 操作获取信号量,V 操作释放信号量
信号:sigaction,kill 等,Ctrl-C 产 SIGINT 信号,Ctrl-\产 SIGQUIT 信号,Ctrl-Z 产 SIGTSTP 信号
消息队列:msgget,存在与内核中,数据会从用户空间和内核空间相互复制,不适合数据量大操作频繁的场景
共享内存:shmget,地址空间映射,不需要复制数据,读写需要其他方式进行同步
套接字:socket,不同机器间的数据通信

线程同步
linux 内核没有提供线程,通过 pthread 库实现用户级多线程,c++11 后标准库开始支持多线程,实现原理是为每个创建的线程在当前进程空间生成运行栈
windows 系统提供系统线程,可通过 CreateThread,ExitThread 等系统函数操作,或 vc++运行库提供_beginthreadex 对 CreateThread 的包装函数

以下主要以 linux 下 c++学习和总结
| 功能 | pthread | std::thread(c++11) | thrd_t(c11) |
| :—– | :———- | :———- |
|线程创建 | pthread_create | thread 类 | thrd_create(C11) |
|互斥 mutex | pthread_mutex_init | mutex 类 | mtx_init |
|条件变量 | pthread_cond_init | condition_variable | cnd_init |
|读写锁 | pthread_rwlock_init | thread 类 | thrd_create(C11) |
|信号量 | sem_init | counting_semaphore(C++20) | sem_init |
|屏障 | pthread_barrier_init | barrier(C++20) | 无 |

进程通信的信号量和信号 ,线程同步也可以使用

互斥锁,只有加锁和不加锁两种状态,使用简单情况,相当于 0,1 状态的信号量
信号量,信号量的 count 代表多个可用的资源,比如多台打印机的情况
条件变量:可以以原子的方式阻塞进程,直到某个特定条件为真为止。对条件的测试是在互斥锁的保护下进行的。条件变量始终与互斥锁一起使用。

TCP/IP 协议栈

应用层:http,https,FTP,DNS 等
传输层:TCP,UDP
网络层:ICMP,ARP,RARP,IP
网络接入层:

常用端口:http:tcp:80,https:tcp:443,DNS:udp:53

TCP 与 UDP

TCP 是面向连接的全双工的可靠数据传输服务,UDP 是无连接的报文服务
为保证全双工,TCP 建立连接需要 3 次握手(SYN,SYN+ACK,ACK),4 次挥手(FIN,ACK,fin,ack)
socket,SOCK_STREAM 代表 TCP,SOCK_DGRAM 代表 UDP

http 和 https

http 数据是明文传输,https 是加密的
https 需要服务端安装证书
服务器收到客户端 https 请求后,会把证书公钥发给客户端
客户端利用公钥将密钥加密后发给服务器
服务器利用私钥解密得到密钥,然后利用密钥对数据解密后传输

服务器和客户端之间的数据需要密钥进行加密,但是协商密钥的过程有可能被窃取,所以通过证书的方式把密钥加密,保证密钥协商过程安全

IO 多路复用

五种 IO 模型

  1. 阻塞,调用 recvfrom 等,会被阻塞
  2. 非阻塞,无论数据是否准备好都立即返回,可以设置 socket 为非阻塞
  3. IO 多路复用,select(底层是数组),poll(底层是链表),epoll(底层是红黑树),可以等待多组数据
  4. 异步 IO,有 2 种,glibc 中通过创建工作线程实现异步 IO(aio_read 等函数),内核提供的(io_setup)

根据关键字比较:

基本类型

共有部分:double,char,float,int,long,short,signed,void,union,unsigned,enum,struct
c++中特有:class,bool,true,false
wchar_t
char8_t (C++20 起)
char16_t (C++11 起)
char32_t (C++11 起)

类型限定符:const,restrict (C99 起),volatile
c++中特有:mutable

强制类型转换
const_cast
dynamic_cast
reinterpret_cast
static_cast

存储类指定符

auto
extern
static
register
thread_local

面向对象

friend
private
protected
public
virtual
operator
typeid
this

模板编程

template
typename

命名空间

namespace
using

异常处理

throw
try
catch
noexcept (C++11 起)

动态内存分配

delete(1)
new

协程

co_await (C++20 起)
co_return (C++20 起)
co_yield (C++20 起)

模块

export(1)(3)
import (C++20)

代用记号

&&替代 and,&=替代 and_eq,等等

国考

基本流程

报名

时间:2019-10-15,报名网址:http://bm.scs.gov.cn/kl2020

资格审查

报名确认(上传照片、缴费)

打印准考证

笔试

时间:2019-11-24
内容:行政能力测试和申论,满分均为 100 分
官方大纲:《中央机关及其直属机构 2020 年度考试录用公务员公共科目笔试考试大纲》

面试:

时间:2020 年 2 月,笔试和面试各站 50%

体检

考察

国考专业对比:
工学=>电子信息类=>电子信息科学与技术
理学=>物理学类=>应用物理学

陕西省考专业:
电气信息类=>电子信息科学与技术
物理学类=>应用物理学

近几年国考数据统计

年份 高校毕业人数 招录人数 审查通过 参加笔试 最终比例
2020 874 万 24128 143.7 万 96.5 万 40:1
2019 834 万 14537 635113 92 万 63:1
2018 820 万 28533 165.97 万 113.4 万 40:1
2017 795 万 27061 148.63 万 98.4 万 36:1
2016 765 万 27817 139.46 万 93 万 33:1
2015 749 万 22248 129 万 90 万 41:1
2014 727 万 19538 152 万 99 万 40:1
2013 699 万 20839 138.3 万 111.7 万 54:1
2012 680 万 17941 130 万 96 万 54:1
2011 660 万 15290 141.5 万 90.2 万 59:1
2010 631 万 15526 144.3 万 92.7 万 60:1
2009 611 万 13566 105.2 万 77.5 万 57:1

高校毕业人数持续增长,经济下滑,就业压力增大
参加国考的竞争预计愈发激烈

陕西省公务员考试

报名

时间:2019-3-22,报名网址:陕西人事考试网 http://www.sxrsks.cn

事业单位

陕西省事业单位:陕西人事考试网:http://www.sxrsks.cn/website/bkwj_index.aspx
报名时间:4 月 8 号
笔试包括《职业能力倾向测验》和《综合应用能力》两科,各科满分均为 150 分

2 个我能考的,属于公益一类,全额拨款
2019 年的 陕西省荣誉军人康复医院网络管理 笔试最低分 196.5 分
2019 年的 陕西省卫生计生政策评估与信息中心机房管理与系统维护(具有电子信息科学与技术助理工程师资格证) 笔试最低分 149.5

西安市事业单位:西安人事考试网:http://xapta.xa.gov.cn/preview/channel/666.jhtml
考试时间:4 月 8 号
笔试包括《职业能力倾向测验》和《综合应用能力》两科,各科满分均为 150 分

编程范式分类

编程范式分类

语言和范式关系

语言和范式关系

相关书籍:待完成
程序设计语言实践之路
VanRoyChapter.pdf

阅读本文之前,可先参考c 语言核心

c++相对于 c 语言,主要是增加了面向对象和模板编程

c++中的实体

C++ 程序中的实体包括:值、对象、引用、 结构化绑定 (C++17 起)、函数、枚举项、类型、类成员、模板、模板特化、命名空间和形参包。预处理器宏不是 C++ 实体。

对象类型:非函数类型、非引用类型且非 void 类型的
所以,以下实体都不是对象:值,引用,函数,枚举项,类型,类的非静态成员,位域,模板,类或函数模板的特化,命名空间,形参包,和 this。

名字查找和命名空间

作用域:文件作用域(全局作用域)、命名空间作用域、类作用域、块作用域、枚举作用域、函数作用域、函数形参作用域、模板形参作用域

内部链接和外部链接

内部链接:其他编译单元无法访问的名称,拥有内部链接,相反是外部链接

以下为内部链接:

  1. 所有声明
  2. 类型(struct/union/enum 等)
  3. 命名空间中的 static 函数和变量以及 const 常量
  4. inline 函数

以下为外部链接:

  1. 命名空间中的非 static 函数和变量
  2. 类成员函数(包含成员函数和 static 成员函数)和静态成员变量

类型比较

c++有如下类型:

  • 基本类型
    • void
    • nullptr:空指针
    • 算术类型
      • 整数类型
        • bool 类型
        • 字符类型
          • 窄字符:(char、signed char、unsigned char、char8_t)
          • 宽字符:(char16_t、char32_t、wchar_t)
        • 整数类型:各种限定的 int
      • 浮点类型:(float 、 double 、 long double)
  • 复合类型
    • 数组类型
    • 函数类型
    • 指针类型(包括对象指针,函数指针,成员函数指针,数据成员指针)
    • 引用类型
    • 枚举类型
    • 类类型
    • 联合体类型

基本类型异同

空指针字面量

为什么需要空指针字面量?
空指针用于表示一个无效的指针,它的值为 0(早期 C 语言的实现中可能有非 0 空指针,现在已经不用)。对指针置 NULL 即标记指针无效,避免“野指针”的恶果

c 语言空指针定义于<stddef.h>,它可以被定义为 ((void*)0), 0 或 0L,这取决于编译器供应商。

1
2
3
4
5
6
7
// 兼容 C++ :
#define NULL 0
// 不兼容 C++ :
#define NULL ((void*)0)
// 允许void * 与任意其他对象指针的隐式类型转换
int* p = malloc(10 * sizeof(int)); // malloc 返回 void*
void *pv = p; // int * 转换为void *

c++中空指针定义如下:

1
2
3
#define NULL 0
// C++11 起
#define NULL nullptr

问题一:为什么 c++把 NULL 定义为 0,而不是 void
因为 c++中不允许(void
)到其他类型指针的隐式类型转换

1
2
3
4
#define NULL ((void*)0) /* 如果在 C++ 语言中这么定义的话 */
int* a = NULL; /* 隐式转换,编译错误 */
int* a = (int*)NULL; /* 显示转换,正确,但很麻烦*/
int* a = 0; // 可以,字面量0可以隐式转换为指针类型

结论:c++中,NULL 只能被定义为 0

问题二:有了 NULL 表示空指针,c++11 为什么增加 nullptr_t ?
当 NULL 被定义为 0 后,在函数重载时,会发生歧义,如下

1
2
3
4
5
6
7
8
void Func(char *);
void Func(int);

int main()
{
Func(NULL); // NULL=0,所以不知道应该调用哪个
Func(nullptr); // 调用Func(char *);
}

c++11 的解决方案,定义个 std::nullptr_t 类型,该类型定义了转到任意指针类型的转换操作符,同时不允许该类型的对象转换到非指针类型

结论:用 nullptr 类型表示无效指针后,既不需要初始化时显示转换的麻烦,又避免 NULL 定义为 0 时的函数重载问题,而保留 NULL 只是为了向后兼容。所以 c 中使用 NULL,c++11 中使用 nullptr。

bool 类型
c99 开始,增加关键字_Bool 支持布尔类型

1
2
3
#define bool	_Bool
#define true 1
#define false 0

c99 后,bool,true,false 为宏定义,在<stdbool.h>中
c++中,bool,true,false 均为关键字

字符类型

c++中,目前有以下内置字符类型(关键字):
char
char8_t (C++20 起):UTF-8 字符表示的类型,char8_t utf8[] = u8”我”
char16_t (C++11 起):UTF-16 字符表示的类型,char16_t utf16[] = u”我”
char32_t (C++11 起):UTF-32 字符表示的类型,char32_t utf32[] = U”我”
wchar_t: 实现定义,windows 为 16 位 short 类型,gcc 为 32 位 int 类型,定宽字符

c 语言中,使用宏定义实现:

1
2
3
typedef unsigned short wchar_t;  // wctype.h
typedef uint_least16_t char16_t; // 定义于<uchar.h>
typedef uint_least32_t char32_t; // 定义于<uchar.h>

字符串使用原则:
程序内部使用 char8_t(UTF-8 编码)字符串,既可以表示所有字符,又不浪费空间
求字符串长度等操作时,转换为 wchar_t 宽字符串方便操作,char16_t 和 char32_t 存在字节序问题,不建议使用
注意:宽字符和窄字符相互转换,或者输出到控制台时,需要设定正确的 locale,才能正确解析窄字符串

引用类型
c++增加引用类型,表示一个标识符的别名,故不占用存储空间
没有数组的引用,没有指针的引用,没有引用的引用

面向对象

通过 class 或者 struct 支持面向对象编程

编译器默认会定义的成员函数:

1
2
3
4
5
6
7
8
class A {
A() {} // 默认构造函数
A( const A & ) {} // 复制构造函数
//移动构造函数 (C++11 起)
//复制赋值运算符
//移动赋值运算符 (C++11 起)
//析构函数
}

c++中的多态:
函数重载:可以定义不同参数的相同名称的函数,编译期,原理是编译器会产生不同的符号
多态:基类中定义的虚函数,可以被子类覆盖,运行时调用不同的函数
多态原理:通过虚函数表和虚表指针实现,编译器为每个定义了虚函数的类分配一个虚函数表,表中存放的是这个类所有虚函数的指针,每个类对象的最前面存放的是虚函数表指针,

模板编程

通过模板编程支持范型编程,让程序员编写与类型无关的通用代码,比如通用算法

1
2
3
4
5
6
// 函数模板
template <class 形参名, class 形参名, ...> 返回类型 函数名(参数列表) { ... }

// 类模板
template <class 形参名, class 形参名, ...> class 类名{ ... };
}

模板有显式实例化,隐式实例化,特化(具体化)
隐式实例化:运行期间,根据参数动态生成模板实例
显式实例化:编译期间,生成对应的实例
特化:针对自定义参数,不能生成对应实例时,跟显示实例化一样,编写针对特定类型的模板

字符集与编码

字符集:字符集是字符与代码的映射关系,例如 ASCII 字符集的 ‘A’ = 65 = 0x41
编码:将字符集中的代码按一定规则存储于计算机中,例如 ASCII 规定用一字节存储所有 ASCII 字符

编码历史

第一阶段:ASCII 编码

计算机刚开始只支持英语,使用 ASCII 编码,一个字节存储

第二阶段:ANSI 编码,表示其他外文编码

不同国家和地区的 ANSI 编码各不相同
linux 系统查看系统默认编码
locale 的命名规则为<语言>_<地区>.<字符集编码>

1
2
3
4
5
6
7
8
9
10
11
12
[root@1-min huage]# locale  //查看当前系统的语言环境
LC_CTYPE="zh_CN.UTF-8" // 中文linux系统默认UTF-8编码
[root@1-min huage]# locale -a //查看系统支持的所有语言
en_US
en_US.iso88591
en_US.iso885915
en_US.utf8
zh_CN
zh_CN.gb18030 // 2000年3月17日发布,对 GBK 的补充
zh_CN.gb2312 // 1981年5月1日发布,双字节编码
zh_CN.gbk // 1995年12月发布,对 GB2312 补充,双字节编码
zh_CN.utf8

linux 编码转换工具:iconv

1
iconv -f GBK -t UTF-8 file1 -o file2 // 将一个UTF-8 编码的文件转换成GBK编码

windows 系统可通过控制面板更改系统编码,
控制面板” =>“时钟、语言和区域”=>“区域和语言”=>“管理”=>“更改系统区域设置”
或者通过 chcp 命令查看当前代码页,通过 systeminfo 查看 local
System Locale: zh-cn;Chinese (China)

windows 记事本另存为选择编码方式,ANSI 就是系统默认编码,简体中文是 gb2312,繁体中文是 big5 编码

第三阶段:Unicode 编码,万国码

ANSI 编码解决了非英语国家的编码显示问题,但不同国家使用不同编码,相互交流沟通就很麻烦,然后就出现 Unicode 字符集,将世界上所有字符统一编码

Unicode 字符集,规定了世界上所有字符的二进制代码,字符串中存储字符在 Unicode 中的编号

常见 Unicode 字符集的编码方式有 UTF-8,UTF-16,UTF-32 等

文件编码
汉字编码如:gb2312、gbk、gb18030、big5,编码方式决定了字节顺序,跟 cpu 字节序无关,跟大端模式的顺序一致
Unicode 相关编码:
UTF-8,UTF-8 和 gb 系列编码一样,其编码某个汉字产生的字节顺序,由其编码方案决定,不受 CPU 字节序的影响
UTF-16、UTF-32:编码规则要求可以在文件头部的 BOM(Byte Order Mark)来标记字节顺序,FFFE 表示小端,FEFF 表示大端

程序中的编码

c 语言字符串常量有如下形式:
“ s-char-sequence “ (1) 系统默认编码,gcc 为 UTF-8,vs2017 为 gbk
u8 “ s-char-sequence “ (2) (C11 起) UTF-8 字符串字面量
u “ s-char-sequence “ (3) (C11 起) 16 位宽字符串字面量,通常为 UTF-16 编码,有字节序问题
U “ s-char-sequence “ (4) (C11 起) 32 位宽字符串字面量,通常为 UTF-32 编码,有字节序问题
L “ s-char-sequence “ (5) 宽字符串字面量,通常是 Unicode 码点(即 Unicode 顺序编号)

使用 GCC 编译时可以使用如下参数:
-finput-charset 指定源文件(保存文件时选择)的编码方式(若不指定,编译器默认是 UTF-8)
-fexec-charset 指定可执行程序中的字符以什么编码方式来表示,默认是 UTF-8
-fwide-exec-charset 指定可执行程序中的宽字符以什么编码方式来表示,默认是 UTF-8

字符串字面量 (1) 和宽字符串字面量 (5) 的编码是实现定义的。例如, gcc 用命令行选项 -fexec-charset 和 -fwide-exec-charset 选择不同编码

字符串不同的编码到底有什么影响:
如果这个字符串只是程序内部使用,不管什么编码都没有关系
如果这个字符串要输出到控制台或者显示到 GUI 上,那么这个字符串的编码必须和接受方(如控制台)的编码方案一致才可显示,否则乱码

参考:
标准编码百度百科
阮一峰字符编码
c++编码
彻底弄懂 UTF-8、Unicode、宽字符、locale

c 程序由一系列文本文件组成,以文件为单位,经过预处理、编译链接生成可执行程序,由系统调用执行

c 语言中的实体

c 语言有如下实体:对象、函数、标签( struct 、 union 或枚举)、结构体或联合体成员、枚举常量、 typedef 类型别名、标号名、宏名、宏形参名。

实体是由声明所引入的,使其与名字对应起来,并定义了其属性。为一个实体定义其使用所需的所有性质的声明是一个定义。

什么是对象?
一个对象是执行环境数据存储的一个区域,其内容可以表示值(值是对象的内容转译为特定类型时的含义)。
简单说,就是程序执行时,除了代码段,其他堆栈段、bss 段、数据段里面的都是对象

所以,以下实体都不是对象:值,引用,函数,枚举项

原因是以上这些实体只是在编译阶段使用,说白了就是写给编译器看的,函数直接生成进代码段,值会以二进制嵌入到代码中

如何判断?
对象类型:所有不是函数类型的类型

标识符声明和定义

声明是向程序中引入一个名字
定义是足以使用该名字所标识的实体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 对于对象,分配存储的声明为定义
extern int a; // 声明a,未分配存储
int a; // 定义a

// 对于函数,包含函数体的声明为定义
void b(); // 声明函数b
void b(){;}; // 定义函数b

// 对于结构体,包含结构体成员列表的为定义
struct c; // 声明结构体c
struct c {int c;}; // 定义结构体c

// 所有的typedef 都是定义,定义的名称属于通常命名空间
typedef int A[]; // A 是 int[]
A a = {1, 2}; // a 的类型是 int[2]
typedef struct { double hi, lo; } range;
range z, *zp;

include 预处理指令,会将包含的头文件插入到当前行
所以,头文件如果定义了全局变量,如果重复包含此头文件,会出现重定义,可使用#pragma once 或者宏定义避免一个头文件被多次包含
但,即使每个编译单元编译通过,链接时也会出现重复定义,原因是全局变量有外部链接
所以头文件可以放所有声明和内部链接的定义

标识符查找和命名空间

c 语言有 4 个独立的命名空间:
标号命名空间:跟在 goto 后的标识符,在标号命名空间查找
标签命名空间:跟在 struct、union、enum 后的标识符,在标签命名空间查找
类型成员命名空间:跟在成员访问运算符后的标识符,在类型成员命名空间查找
通常命名空间:函数名称,对象名,以 typedef 声明的标识符,枚举常量,所有其他标识符

4 个作用域:
文件作用域:任何在代码块之外声明的标识符都具有文件作用域
块作用域:任何位于一对花括号声明的标识符具有块作用域
函数作用域:只适用于函数内部的标号
函数原型作用域:只适用于在函数原型中声明的参数

1
2
3
4
5
6
7
8
9
10
struct A {
int a; // 类型成员命名空间/文件作用域
enum { INT, FLOAT, STRING} B; // B属于标签命名空间文件作用域,INT属于通常命名空间,文件作用域
struct C {
char c;
};
}
// ABCD 都属于标签命名空间,文件作用域
union D d; // ok
void INT(); // false 通常命名空间文件作用域已经有INT标识符

当 c 程序遇到标识符时,会在当前作用域查找定位引入该标识符,

对象类型

每个对象有如下属性:
标识符属性

作用域:标识符在某一范围内可见
命名空间:同一作用域同名标识符可属于不同命名空间,指代不同对象
链接:跨作用域指代同一对象的能力
存储期:用于限定对象的生存期

链接分为:
无链接:只能在其所在的作用域使用,函数形参和所有非 extern 的块作用域对象
内部链接:当前翻译单元的任何作用域都可使用,所有 static 的函数和对象
外部链接:在其他翻译单元可以使用的标识符,文件作用域下的非 static 函数和对象、extern 对象

存储类指定符:指定对象和函数的存储期和链接
auto - 自动存储期与无链接
register - 自动存储期与无链接;不能取这种对象的地址
static - 静态存储期与内部链接(除非在块作用域)
extern - 静态存储期与外部链接(除非已声明带内部链接)
_Thread_local - 线程存储期

若不提供存储类指定符,则默认为:
对所有函数为 extern
对在文件作用域的对象为 extern
对在块作用域的对象为 auto

结论:默认情况下
文件作用域定义得对象和函数:都是外部链接

类型

对象、函数和表达式拥有称为类型的属性,它确定存储于对象或表达式求值所得的二进制值的转译方式。
c 语言类型分为:

  1. void 类型
  2. 基本类型:char、int、long、double、float 等
  3. 派生类型:数组、结构体、联合体、函数、指针、原子类型
  4. 枚举类型

表达式

表达式是运算符及其运算数的序列,它指定一个运算
表达式求值可得到一个结果,分为:左值、右值和函数指代器

某些类型的常量值可常量或字面量,直接嵌入程序中

  1. 整数常量
  2. 浮点常量
  3. 字符常量
  4. 字符串字面量:
  5. 复合字面量:结构体、联合体或数组的无名对象,( type ) { initializer-list }
1
2
3
int *p = (int[]){2, 4}; // 创建一个无名的 int[2] 类型静态存储数组
// 初始数组为值 {2, 4}
// 创建指向数组首元素的指针 p

声明和定义

声明是引入一个标识符到程序中,并指定其属性
格式:specifiers-and-qualifiers declarators-and-initializers ;
specifiers-and-qualifiers:空白符分割,类型指定符,类型限定符,存储类指定符,对齐指定符,函数指定符
declarators-and-initializers:逗号分割,声明器和初始化器
声明器格式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1. 标识符:identifier
int i; // i是标识符

2. 指针声明器格式:* qualifiers(可选) declarator
int *p; // p是指向int类型的指针
int (*p)(int); // 函数指针
int (*p)[5]; //数组指针

3. 数组声明器格式:
noptr-declarator [ static(可选) qualifiers(可选) expression ]
noptr-declarator [ qualifiers(可选) * ]
int n = 1;
int a[5]; // 常量大小的数组
int b[n]; // 变长度数组(VLA)
int c[]; // 位置大小数组

4. noptr-declarator ( parameters-or-identifiers ):函数声明器
int max(int a, int b);

5. ( declarator ):任何可放入括号中的声明器,引入指向数组或指向函数指针时要求这么做

初始化器格式

1
2
1. = expression
2. = { initializer-list }

三种显示初始化器:
标量类型初始化:包括整型类型,浮点类型,指针类型等
数组初始化:2 种形式

1
2
3
4
5
6
7
8
9
1. = string_literal 字符串字面量,初始化字符数组
int c[] = "abc";
2. = { expression , ... } 被初始化数组成员列表
int y[5] = {1,2,3}; // y 拥有类型 int[5] 并保有 1,2,3,0,0
int y[4][3] = { // 4 个 3 个 int 的数组的数组( 4*3 矩阵)
{ 1 }, // 0 行初始化到 {1, 0, 0}
{ 0, 1 }, // 1 行初始化到 {0, 1, 0}
{ [2]=1 }, // 2 行初始化到 {0, 0, 1}
}; // 3 行初始化到 {0, 0, 0}

结构体及联合体类型初始化:

1
2
3
4
5
6
7
8
9
// . member 形式的单独成员指代器,和 [ index ] 形式的数组指代器。

// 初始化 w (二个结构体的数组)为
// { { {1,0,0}, 0}, { {2,0,0}, 0} }
struct {int a[3], b;} w[] = {[0].a = {1}, [1].a[0] = 2};

union { int x; char c[4]; }
u = {1}, // 令 u.x 活跃,拥有值 1
u2 = { .c={'\1'} }; // 令 u2.c 活跃,拥有值 {'\1','\0','\0','\0'}

算法是为解决某个具体问题设计的解题步骤,根据问题分类有:

  1. 排序
  2. 查找
  3. 字符串:字符串匹配等
  4. 图问题:对复杂关系的建模
  5. 组合问题:排列组合,选取满足目标的对象,比如成本最小等
  6. 几何问题:处理点、线、面等几何对象,应用于计算机图形学
  7. 数值问题:数学问题,比较解方程,计算定积分等

因算法依赖具体问题,局限性较强,但很多算法设计思想有相通之处,根据设计思想分类有:

  1. 蛮力法:比如 BFS,DFS,顺序遍历等,遍历所有解空间,找满足条件的解
  2. 分治法:
  3. 动态规划:主要是多阶段决策问题
  4. 贪心:图相关算法,最小生成树(Prim 算法和 Kruskal 算法),最短路径(dijkstra 算法)都属于贪心算法

一些个人总结:
不论什么问题,第一步都可以将问题规模降到最低,然后求解,然后问题规模再变大一点,再去求解
根据这个过程,就可以利用不同的设计技巧

  1. 如果增大问题规模,求解需要使用原来已求解的结果,这就是动态规划,保存每个阶段的结果,递推下去,就可以找到最终解
  2. 如果增大问题规模,求解过程不依赖原来已求解的结果,这就是分治,分成独立的子问题,分别求解,然后合并解就是最终解
  3. 如果增大问题规模,

一些个人文章:
动态规划的解释
labuladong 个人文章
程序员小吴