Qida's Blog

纸上得来终觉浅,绝知此事要躬行。

二进制位运算 十进制运算
& 按位与(AND) $M\&(2^n-1)$ $MOD(M/2^n)$
| 按位或(OR)
~ 按位非(NOT)
^ 按位异或(XOR)
<< 左位移(LEFT SHIFT) $M<<n$ $M*2^n$
>> 右位移(RIGHT SHIFT) $M>>n$ $M/2^n$
>>> 无符号右移

https://en.wikipedia.org/wiki/Mask_(computing)

Using a mask (bitmask) can be set

  • either on or off,
  • or inverted from on to off (or vice versa)

in a single bitwise operation.

Common bitmask functions

「按位与 &」的使用场景

求子网地址

子网地址(主机地址与子网掩码做按位与运算),参考:

例子:

Calculate subnet address

Calculate subnet address

实现循环队列

编程的时候,很多时候都会要求一个数在某一个范围内进行反复循环,例如实现循环队列。如果使用 if 语句,当判断达到最大值的时候回到开始处,效率较低。是否有更简单更高效的方法?

  • & 按位与(AND)。比如说我想让一个数在 0-7 内循环,该如何做呢?temp = (temp++)&0x07,如此就简单的实现了 0-7 循环。因为要实现 0-7 的循环,其实只要提取一个变量递增的低三位即可。不管这个变量如何变化,它的低三位始终都是在 0-7 循环变化的。同理,它也可以实现 0-15、0-31 变化。但是这个方法有局限,它只能按照连续 bit 位的最大值进行循环
  • % 取余运算(Modulo),它不存在上述限制。可以在 0-任意数循环。比如 0-5 循环,只要 temp = (temp++)%6(注意是 6 而不是 5),那么 temp 就会在 0-5 之间循环了。

「按位或 |」的使用场景

单个变量保存多个值,节省存储空间

DragonPay

雪花算法的拼接

1
2
3
4
5
     timestamp << TIMESTAMP_SHIFT
| dataCenterNo << DATA_CENTER_NO_SHIFT
| workerNo << WORKER_NO_SHIFT
| seqNo << SEQ_NO_SHIFT
| ext

线程池的成员属性 ctl

线程池的成员属性 ctl,高 3 位表示 runState,低 29 位表示 workerCnt(按位或运算 bitwise OR):

1
2
3
4
5
6
7
runState workerCnt                       runState workerCnt
000 00000000000000000000000000000 SHUTDOWN empty
‭‭ 001 00000000000000000000000000000 STOP empty
010 00000000000000000000000000000 TIDYING empty
‭011 00000000000000000000000000000‬ TERMINATED empty
111 00000000000000000000000000000 RUNNING empty
‭ 111 11111111111111111111111111111 RUNNING full

操作系统 - 分页存储管理 - 逻辑地址结构

  • 若用 $m$ 位表示逻辑地址,页大小为 $2^n$ 字节,则低 $n$ 位表示「页内偏移量」,高 $m-n$ 位表示「页号」。
  • 例如 32 位的逻辑地址中,页大小为 $2^{12}$ (4KB),则低 12 位表示「页内偏移量」,高 20 位表示「页号」。即:可用内存为「页号量 $2^{20}$」×「页大小 $2^{12}$ B」=「$2^{32}$ B」=「4 GB」

paging address structure

epoll_ctl()event 参数

1
2
3
4
EPOLLIN | EPOLLOUT | EPOLLRDHUP | EPOLLPRI | EPOLLERR | EPOLLHUP | EPOLLET | EPOLLONESHOT

event.events = EPOLLIN | EPOLLET;
epoll_ctl (efd, EPOLL_CTL_ADD, sfd, &event);

TCP - Header Format - Flags

TCP - Header Format - Flags

Unix-like permissions

chmodumask

Unix-like permissions

「按位异或 ^」的使用场景

异或运算 XOR 使用场景 | 阮一峰

前向纠错(FEC))

TCP 协议实现可靠数据传输的 5 种措施中之一——差错控制,有两种纠错方案:

其中 FEC 的实质就是按位异或运算:

FEC

参考:https://www.jianshu.com/p/6157e120ef99

求 hash 值

求 hash 值使用了:

  • >>> 无符号右移
  • ^ 按位异或
  • & 按位与
1
2
3
4
5
int hash(Object key) {
int h = key.hashCode();
h = h ^ (h >>> 16);
return h & (capitity - 1); //capicity 表示散列表的大小
}

位移

逻辑右移可以处理除数为任意二的幂的除法,即:$M>>n$ 等于 $M/2^n$

更一般地,在特定底数 Base 的进位制中,除数(或分母)为任意 $Base^n$ 的除法(n 为整数)皆可以透过将数字位数向右移 n 位来完成。例如 除以十:

$M/Base^n$ Base 2 Base 8 Base 10 Base 16
230 / 2 = 115 1110 0110 / 10 = 111 0011
230 / 8 = 28 346 / 10 = 34
230 / 10 = 23 230 / 10 = 23
230 / 16 = 14 0xE6 / 10 = 0xE

参考

https://en.wikipedia.org/wiki/Bit

https://en.wikipedia.org/wiki/Bitwise_operation

https://en.wikipedia.org/wiki/Bit_array

https://dev.mysql.com/doc/refman/5.7/en/bit-functions.html

计算机中有哪些令人拍案叫绝的设计? | 良许 Linux

C 语言”位运算”有哪些奇特技巧?

注册域名、管理资源记录(RR)都是站长/运维最常见的操作。本文总结了相关知识。

DNS 是什么?

DNS 是互联网的一项基础服务,它将人类易记的域名解析为不易记的 IP 地址,使人更方便的访问互联网。

DNS 的结构?

域名系统(DNS)是一个多层级、分布式的系统,就如同一个树状结构:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
                    +---+                                 
| . | Root domain
+-+-+
|
+-------+-------+---+---+-------+-------+
| | | | | |
+-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+
|com| |net| |org| |gov| |cn | |...| Top-level domain (TLD)
+---+ +---+ +-+-+ +---+ +---+ +---+
|
+----+----+
|wikipedia| Second-level domain (SLD)
+----+----+
|
+---------------+
| | |
+-+-+ +-+-+ +-+--+
|www| |ftp| |mail| Resource record (RR)
+---+ +---+ +----+
Domain types DNS zone Name server
Root domain
根域名
DNS root zone
DNS 根区
Root name server
根域名服务器
Top-level domain (TLD)
顶级域名
DNS zone TLD name server
顶级域名服务器
Second-level domain (SLD)
二级域名
DNS zone Authoritative name server
权威域名服务器
Sub domain
子域名
Resource recerd, RR
资源记录

域名系统(DNS)的每一级只知道直接下级的位置,而无法获得跨级的位置,因此在域名解析的时候,需要自上而下、逐级查询。这种机制虽然看似低效,却能够提供分布式、高容错的服务,避免让域名系统(DNS)成为一个集中式的单点系统。

根域名(Root Domain)

早期的域名必须以英文句号“.”结尾,当用户访问 www.wikipedia.org 的 HTTP 服务时必须在地址栏中输入:http://www.wikipedia.org.,这样 DNS 才能够进行域名解析。如今 DNS 服务器已经可以自动补上结尾的句号。这个点 . 就是根域名。

. 代表的根域名服务器(Root name server),是 DNS 中最高级别的域名服务器(name server),负责返回顶级域名的权威域名服务器(Authoritative name server)的地址。

由于 ICANN 管理着所有的顶级域名,所以它是最高一级的域名节点。

根域名服务器(Root Name Server)

https://www.iana.org/domains/root/servers

由于早期的 DNS 查询结果是一个 512 字节的 UDP 数据包。这个包最多可以容纳 13 个服务器的地址,因此就规定全世界有 13 个根域名服务器,编号从 a.root-servers.net 一直到 m.root-servers.net

HOSTNAME IP ADDRESSES OPERATOR
a.root-servers.net 198.41.0.4, 2001:503:ba3e::2:30 Verisign, Inc.
b.root-servers.net 199.9.14.201, 2001:500:200::b University of Southern California, Information Sciences Institute
c.root-servers.net 192.33.4.12, 2001:500:2::c Cogent Communications
d.root-servers.net 199.7.91.13, 2001:500:2d::d University of Maryland
e.root-servers.net 192.203.230.10, 2001:500:a8::e NASA (Ames Research Center)
f.root-servers.net 192.5.5.241, 2001:500:2f::f Internet Systems Consortium, Inc.
g.root-servers.net 192.112.36.4, 2001:500:12::d0d US Department of Defense (NIC)
h.root-servers.net 198.97.190.53, 2001:500:1::53 US Army (Research Lab)
i.root-servers.net 192.36.148.17, 2001:7fe::53 Netnod
j.root-servers.net 192.58.128.30, 2001:503:c27::2:30 Verisign, Inc.
k.root-servers.net 193.0.14.129, 2001:7fd::1 RIPE NCC
l.root-servers.net 199.7.83.42, 2001:500:9f::42 ICANN
m.root-servers.net 202.12.27.33, 2001:dc3::35 WIDE Project

这 13 台根域名服务器由 12 个组织独立运营。其中,Verisign 公司管理两台根域名服务器:A 和 J。每家公司为了保证根域名服务器的可用性,会部署多个节点,比如单单 Verisign 一家公司就部署了 104 台根域名服务器(2016 年 1 月数据)。

所以,根域名服务器其实不止 13 台。据统计,截止 2016 年 1 月,全世界共有 517 台根域名服务器。你可以在 https://root-servers.org/ 这个网站查到所有根域名服务器的信息。

编号相同的根域名服务器使用同一个 IP,数百台根域名服务器总共只使用 13 个 IP(如上表所示),因此可以抵抗针对其所进行的分布式拒绝服务攻击(DDoS)。

这些根域名服务器的运行软件皆为 BINDNSD

根提示文件(Root Hints File)

https://www.internic.net/domain/named.root

根域名服务器虽然有 13 个域名,但是最少必须知道一台的 IP 地址,否则就会陷入循环查询。一般来说,本机都保存一份根域名服务器的 IP 地址的缓存,叫做 named.root 文件。这个文件同时记录了 13 台根域名服务器的 IP 地址。

1
2
3
4
5
6
7
8
9
.                        3600000      NS    A.ROOT-SERVERS.NET.
A.ROOT-SERVERS.NET. 3600000 A 198.41.0.4
A.ROOT-SERVERS.NET. 3600000 AAAA 2001:503:ba3e::2:30

. 3600000 NS B.ROOT-SERVERS.NET.
B.ROOT-SERVERS.NET. 3600000 A 199.9.14.201
B.ROOT-SERVERS.NET. 3600000 AAAA 2001:500:200::b

...

参考:4.1 Address resolution mechanism

For proper operation of its domain name resolver, a network host is configured with an initial cache (hints) of the known addresses of the root name servers. The hints are updated periodically by an administrator by retrieving a dataset from a reliable source.

域名解析的循环依赖问题及其解决方案:4.3 Circular dependencies and glue records

Name servers in delegations are identified by name, rather than by IP address. This means that a resolving name server must issue another DNS request to find out the IP address of the server to which it has been referred. If the name given in the delegation is a subdomain of the domain for which the delegation is being provided, there is a circular dependency.

In this case, the name server providing the delegation must also provide one or more IP addresses for the authoritative name server mentioned in the delegation. This information is called glue. The delegating name server provides this glue in the form of records in the additional section of the DNS response, and provides the delegation in the authority section of the response. A glue record is a combination of the name server and IP address.

For example, if the authoritative name server for example.org is ns1.example.org, a computer trying to resolve www.example.org first resolves ns1.example.org. As ns1 is contained in example.org, this requires resolving example.org first, which presents a circular dependency. To break the dependency, the name server for the top level domain org includes glue along with the delegation for example.org. The glue records are address records that provide IP addresses for ns1.example.org. The resolver uses one or more of these IP addresses to query one of the domain’s authoritative servers, which allows it to complete the DNS query.

根区文件(Root Zone File)

https://www.internic.net/domain/root.zone

DNS 根域名服务器(Root name server)负责维护 DNS 根区文件(Root zone file)。该文件保存了所有顶级域名(TLD)的托管信息,所以非常大,超过 2MB。

举例来说,顶级域名 .com 可以查到 13 个域名服务器:

1
2
3
4
5
6
7
8
9
10
11
12
13
com.            172800  IN  NS  a.gtld-servers.net.
com. 172800 IN NS b.gtld-servers.net.
com. 172800 IN NS c.gtld-servers.net.
com. 172800 IN NS d.gtld-servers.net.
com. 172800 IN NS e.gtld-servers.net.
com. 172800 IN NS f.gtld-servers.net.
com. 172800 IN NS g.gtld-servers.net.
com. 172800 IN NS h.gtld-servers.net.
com. 172800 IN NS i.gtld-servers.net.
com. 172800 IN NS j.gtld-servers.net.
com. 172800 IN NS k.gtld-servers.net.
com. 172800 IN NS l.gtld-servers.net.
com. 172800 IN NS m.gtld-servers.net.

也就是说,.com 域名的解析结果,可以到这个 13 个服务器的任一台查询。细心的读者可能发现,这些服务器本身也是使用域名(比如 a.gtld-servers.net.)标识,那么还得去查询它们指向的服务器,这样很容易造成循环查询。

因此,DNS 根区文件还会同时提供这些服务器的 IP 地址(IPv4 和 IPv6):

1
2
3
4
5
6
7
a.gtld-servers.net. 172800  IN  A     192.5.6.30
a.gtld-servers.net. 172800 IN AAAA 2001:503:a83e:0:0:0:2:30
b.gtld-servers.net. 172800 IN A 192.33.14.30
b.gtld-servers.net. 172800 IN AAAA 2001:503:231d:0:0:0:2:30
c.gtld-servers.net. 172800 IN A 192.26.92.30
c.gtld-servers.net. 172800 IN AAAA 2001:503:83eb:0:0:0:0:30
...

理论上,所有域名查询都必须先查询根域名,因为只有根域名才能告诉你,某个顶级域名由哪个运营商、哪台服务器管理。事实上也确实如此,ICANN 维护着根区文件(Root zone file),里面记载着顶级域名和对应的记录。

但由于该文件很少变化,大多数 DNS 服务商都会提供它的缓存,所以根域名的查询事实上不是那么频繁。

根区数据库(Root Zone Database)

https://www.iana.org/domains/root/db

提供顶级域名的授权信息。

Much of this data is also available via the WHOIS protocol at whois.iana.org.

顶级域名(Top-Level Domain)

所有顶级域名保存在 Top-Level Domain List,可查询根区数据库(Root Zone Database)以获得更多信息(如顶级域名运营商信息、Name Servers)。

顶级域名(TLD)分为如下六种类型:

As of 2015, IANA distinguishes the following groups of top-level domains:[13]

  1. Infrastructure top-level domain (ARPA): This group consists of one domain, the Address and Routing Parameter Area. It is managed by IANA on behalf of the Internet Engineering Task Force for various purposes specified in the Request for Comments publications.

  2. Generic top-level domains (gTLD): Top-level domains with three or more characters

  3. restricted generic top-level domains (grTLD): These domains are managed under official ICANN accredited registrars.

  4. Sponsored top-level domains (sTLD): These domains are proposed and sponsored by private agencies or organizations that establish and enforce rules restricting the eligibility to use the TLD. Use is based on community theme concepts; these domains are managed under official ICANN accredited registrars.

  5. country-code top-level domains (ccTLD): Two-letter domains established for countries or territories. With some historical exceptions, the code for any territory is the same as its two-letter ISO 3166 code.

  1. Test top-level domains (tTLD): These domains were installed under .test for testing purposes in the IDN development process; these domains are not present in the root zone.

其中下面两类是最常用的:

顶级域名的数量仍在不断增长中,除了英文字母的域名,还不断新增各种语系的域名,如中文域名。

顶级域名服务器(TLD name server)

二级域名(Second-Level Domain)

组织或个人通过域名代理服务商(如 GoDaddy、万网)进行注册的域名。根据需要还可以自行在二级域名下新增三级、四级等子域名

权威域名服务器(Authoritative name server)

https://en.wikipedia.org/wiki/Name_server#Authoritative_name_server

任何一个拥有域名的主机,其域名与 IP 地址的映射关系等信息都存储在权威域名服务器上。

资源记录(Resource Record)

域名系统中,一般一个域(DNS zone)通过一个 zone 文件保存该域的相关配置信息。zone 文件包含了域名和 IP 地址等资源之间的映射,以资源记录(Resource recerd, RR)的文本形式进行组织。

这里列举了所有的资源记录类型:

DNS record types

DNS record types

以域名 example.com 为例,其 zone 文件简化如下:

name ttl record class record type record data comment
example.com. 1h IN NS ns ns.example.com is a nameserver for example.com
ns 1h IN A 192.0.2.2 IPv4 address for ns.example.com
example.com. 1h IN A 192.0.2.1 IPv4 address for example.com
www 1h IN CNAME example.com. www.example.com is an alias for example.com

CDN 服务常用到 CNAME 记录。

域名解析方式

参考 RFC 1034: Domain Names - Concepts and Facilities - IETF 规范的 2. INTRODUCTION - 2.3. Assumptions about usage 对于两种域名解析方式的描述:

In any system that has a distributed database, a particular name server may be presented with a query that can only be answered by some other server. The two general approaches to dealing with this problem are

  • “recursive”, in which the first server pursues the query for the client at another server,
  • “iterative”, in which the server refers the client to another server and lets the client pursue the query.

Both approaches have advantages and disadvantages, but the iterative approach is preferred for the datagram style of access. The domain system requires implementation of the iterative approach, but allows the recursive approach as an option.

迭代方式(Iterative Approach)

Iterative Approach

A DNS resolver that implements the iterative approach mandated by RFC 1034; in this case, the resolver consults three name servers to resolve the fully qualified domain namewww.wikipedia.org".

递归方式(Recursive Approach)

DNS resolution

公共域名服务器

https://en.wikipedia.org/wiki/Public_recursive_name_server

https://public-dns.info/

DNS 相关命令

dig

dig

安装

dig 命令安装:

1
$ apt-get install dnsutils

使用

dig 命令使用:https://downloads.isc.org/isc/bind9/cur/9.17/doc/arm/html/manpages.html#dig-dns-lookup-utility

1
$ dig @name_server name record_type

其中,record_type 参数如下:https://en.wikipedia.org/wiki/List_of_DNS_record_types

DNS record types

例子

dig 命令使用例子:

1
2
# To use a specific DNS server for the query, use the @ option.
$ dig @8.8.8.8 example.com
1
2
3
# By default, dig displays the A record for a domain. To look up a different DNS record, add it to the end of the command. 
# For example, to look up the MX (mail exchanger) record for the example.com domain, type the following command:
$ dig example.com MX
1
2
3
4
5
# query for any type of record information
$ dig +noall +answer www.google.com any

www.google.com. 107 IN A 142.250.66.132
www.google.com. 94 IN AAAA 2404:6800:4005:802::2004

+[no]trace

This option toggles tracing of the delegation path from the root name servers for the name being looked up. Tracing is disabled by default. When tracing is enabled, dig makes iterative queries to resolve the name being looked up. It follows referrals from the root servers, showing the answer from each server that was used to resolve the lookup.

下例中,使用公共域名服务器,而不是依次使用 /etc/resolv.conf 里配置的本地域名服务器进行 DNS 迭代查询,结果如下:

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
$ dig @8.8.8.8 +trace www.google.com

; <<>> DiG 9.10.6 <<>> @8.8.8.8 +trace www.google.com
; (1 server found)
;; global options: +cmd
. 24814 IN NS m.root-servers.net.
. 24814 IN NS b.root-servers.net.
. 24814 IN NS c.root-servers.net.
. 24814 IN NS d.root-servers.net.
. 24814 IN NS e.root-servers.net.
. 24814 IN NS f.root-servers.net.
. 24814 IN NS g.root-servers.net.
. 24814 IN NS h.root-servers.net.
. 24814 IN NS a.root-servers.net.
. 24814 IN NS i.root-servers.net.
. 24814 IN NS j.root-servers.net.
. 24814 IN NS k.root-servers.net.
. 24814 IN NS l.root-servers.net.
;; Received 525 bytes from 8.8.8.8#53(8.8.8.8) in 157 ms

com. 172800 IN NS b.gtld-servers.net.
com. 172800 IN NS e.gtld-servers.net.
com. 172800 IN NS i.gtld-servers.net.
com. 172800 IN NS j.gtld-servers.net.
com. 172800 IN NS a.gtld-servers.net.
com. 172800 IN NS c.gtld-servers.net.
com. 172800 IN NS d.gtld-servers.net.
com. 172800 IN NS k.gtld-servers.net.
com. 172800 IN NS m.gtld-servers.net.
com. 172800 IN NS h.gtld-servers.net.
com. 172800 IN NS f.gtld-servers.net.
com. 172800 IN NS l.gtld-servers.net.
com. 172800 IN NS g.gtld-servers.net.
;; Received 1174 bytes from 202.12.27.33#53(m.root-servers.net) in 48 ms

google.com. 172800 IN NS ns2.google.com.
google.com. 172800 IN NS ns1.google.com.
google.com. 172800 IN NS ns3.google.com.
google.com. 172800 IN NS ns4.google.com.
;; Received 840 bytes from 192.48.79.30#53(j.gtld-servers.net) in 196 ms

www.google.com. 300 IN A 142.250.66.100
;; Received 59 bytes from 216.239.38.10#53(ns4.google.com) in 84 ms

Wireshark 网卡抓包截图如下:DNS 协议 基于 UDP 协议,使用 53 端口。

DNS 协议

nslookup

nslookup 命令:https://downloads.isc.org/isc/bind9/cur/9.17/doc/arm/html/manpages.html#nslookup-query-internet-name-servers-interactively

1
2
3
4
5
6
7
8
$ nslookup www.google.com

Server: 10.0.20.101
Address: 10.0.20.101#53

Non-authoritative answer:
Name: www.google.com
Address: 142.250.66.132

参考

RFC 1034: Domain Names - Concepts and Facilities - IETF

RFC 1035 - Domain names - implementation and specification

RFC 1912 - 常见的 DNS 操作和配置错误

https://www.iana.org/domains/root

https://en.wikipedia.org/wiki/Domain_Name_System

https://en.wikipedia.org/wiki/Domain_name

根域名的知识 - 阮一峰

https://wizardzines.com/comics/dig/

https://wizardzines.com/comics/dns-record-types/

如果美国封了 DNS,俄罗斯将从网络消失?

美国能让中国从网络上消失?- 良许 Linux

逻辑结构

图的种类

维基百科对图(Graph)的定义:

A graph is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically.

无向图(Undirected Graph)

无向图

任何两个顶点(vertex)之间都有边(edge)的无向图称为无向完全图。一个具有 n 个顶点的无向完全图的边数为:

$$
C^2_n=n(n-1)/2
$$

有向图(Directed Graph)

有向图

任何两个顶点(vertex)之间都有弧(arc)的有向图称为有向完全图。一个具有 n 个顶点的有向完全图的弧数为:

$$
P^2_n=n(n-1)
$$

带权图(Weighted Graph)

带权图

边或弧上带有权值的图,也称为网(network)

维基百科对网(network)的定义:

In computer science and network science, network theory is a part of graph theory: a network can be defined as a graph in which nodes and/or edges have attributes (e.g. names).

图(graph)是高度抽象后的逻辑结构,而网(network)在此之上可以通过在顶点(vertex)和边(edge)上增加属性来包含更多的信息,更偏重于对实际问题的建模。

图的相关术语

https://en.wikipedia.org/wiki/Glossary_of_graph_theory

What’s the difference between Adjacency and Connectivity ?

在无向图中,邻接是点与点或者边与边之间的关系。在无向图中,如果两个点之间至少有一条边相连,则称这两个点是邻接的。同样,如果两条边有共同的顶点,则两条边也是邻接的。关联是点与边之自的关系。一个点如果是一条边的顶点之一,则称为点与该边关联。

存储结构

邻接矩阵(Adjacency Matrix)

维基百科对矩阵(Matrix)的定义:

In mathematics, a matrix (plural matrices) is a rectangular array or table of numbers, symbols, or expressions, arranged in rows and columns, which is used to represent a mathematical object or a property of such an object.

维基百科对矩阵(Matrix)的定义 2:

数学上,一个 $m×n$ 的矩阵是一个由 $m$ 行(row)$n$ 列(column)元素排列成的矩形阵列。矩阵里的元素可以是数字、符号或数学式。

矩阵(Matrix)是很多科学计算问题研究的对象,矩阵可以用二维数组来表示

图最直观的一种存储方法就是,邻接矩阵(Adjacency Matrix)

In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.

定义如下:

设 $G=(V,\ E)$ 是一个图,其中 $V={v_0,\ v_1,\ …\ ,\ v_{n-1}}$,那么 $G$ 的邻接矩阵 $A$ 定义为如下的 $n$ 阶方阵:

$$
A_{[i][j]}=
\begin{cases}
1& {若\ (v_i,\ v_j)\ 或\ <v_i,\ v_j>\ ∈\ E}\
0& {若\ (v_i,\ v_j)\ 或\ <v_i,\ v_j>\ ∉\ E}
\end{cases}
$$

邻接矩阵

可见,若无向图 $G$ 中有 $n$ 个顶点 $m$ 条边,采用邻接矩阵存储,则该矩阵中非 0 元素的个数为:
$$
2m
$$

对称矩阵(Symmetric Matrix)

用邻接矩阵来表示一个图,虽然简单、直观,但是比较浪费存储空间。为什么这么说呢?

对于无向图来说,如果 $A_{[i][j]}$ 等于 1,那 $A_{[j][i]}$ 也肯定等于 1。实际上,我们只需要存储一个就可以了。也就是说,无向图的二维数组中,如果我们将其用对角线划分为上下两部分,那我们只需要利用上面或者下面这样一半的空间就足够了,另外一半白白浪费掉了。

上面描述的是一类特殊矩阵:

若一个 $n$ 阶方阵 $A$ 中的元素满足下述条件:
$$
a_{ij}=a_{ji} \quad (0≤i,\ j≤n-1)
$$

则 $A$ 称为对称矩阵(Symmetric Matrix)

In the mathematical discipline of linear algebra, a symmetric matrix is a square matrix that is equal to its transpose.

对称矩阵可以压缩存储:对称矩阵有近一半的元素可以通过其对称元素获得,为每一对对称元素只分配一个存储单元,则可将 $n^2$ 个元素压缩存储到含有 $n(n+1)/2$ 个元素的一维数组中。

三角矩阵(Triangular Matrix)

以对称矩阵的主对角线为界,上(下)半部分是一个固定的值(如 0),这样的矩阵称为:上三角矩阵(Upper Triangular Matrix)下三角矩阵(Lower Triangular Matrix)

In the mathematical discipline of linear algebra, a triangular matrix is a special kind of square matrix. A square matrix is called lower triangular if all the entries above the main diagonal are zero. Similarly, a square matrix is called upper triangular if all the entries below the main diagonal are zero.

稀疏矩阵(Sparse Matrix)

如果我们存储的是稀疏矩阵(Sparse Matrix),也就是说,顶点很多,但每个顶点的边并不多,那邻接矩阵的存储方法就更加浪费空间了。比如微信有好几亿的用户,对应到图上就是好几亿的顶点。但是每个用户的好友并不会很多,一般也就三五百个而已。如果我们用邻接矩阵来存储,那绝大部分的存储空间都被浪费了。

这里描述的是一类「非零元素个数很少的矩阵」,即稀疏矩阵(Sparse Matrix)

In numerical analysis and scientific computing, a sparse matrix or sparse array is a matrix in which most of the elements are zero.

稀疏矩阵可以压缩存储,使用三元组表示法:$(i,\ j,\ a_{ij})$。


总结,邻接矩阵的存储方法的优点:

  • 首先,邻接矩阵的存储方式简单、直接,因为基于数组,所以在获取两个顶点的关系时,就非常高效。
  • 其次,用邻接矩阵存储图的另外一个好处是方便计算。这是因为,用邻接矩阵的方式存储图,可以将很多图的运算转换成矩阵之间的运算。比如求解最短路径问题时会提到一个 Floyd-Warshall 算法,就是利用矩阵循环相乘若干次得到结果。参考:《矩阵运算及其运算规则

此外,针对邻接矩阵比较浪费存储空间的缺点,解决方案:

  • 不带权的无向图的邻接矩阵,一定是一个对称矩阵,因此可以转为三角矩阵之后进行压缩存储。
  • 有向图、带权图的邻接矩阵,一般都不是一个对称矩阵。但如果是一个稀疏矩阵,可以使用三元组表示法进行压缩存储。

邻接表(Adjacency List)

邻接表(Adjacency List) 的定义:

In graph theory and computer science, an adjacency list is a collection of unordered lists used to represent a finite graph. Each unordered list within an adjacency list describes the set of neighbors of a particular vertex in the graph. This is one of several commonly used representations of graphs for use in computer programs.

邻接表

还记得我们之前讲过的时间、空间复杂度互换的设计思想吗?邻接矩阵存储起来比较浪费空间,但是使用起来比较节省时间。相反,邻接表存储起来比较节省空间,但是使用起来就比较耗时间。

就像图中的例子,如果我们要确定,是否存在一条从顶点 2 到顶点 4 的边,那我们就要遍历顶点 2 对应的那条链表,看链表中是否存在顶点 4。而且,我们前面也讲过,链表的存储方式对缓存不友好。所以,比起邻接矩阵的存储方式,在邻接表中查询两个顶点之间的关系就没那么高效了。

在基于链表法解决冲突的散列表中,如果链过长,为了提高查找效率,我们可以将链表换成其他更加高效的数据结构,比如平衡二叉查找树等。所以,我们也可以将邻接表同散列表一样进行 “改进升级”。

我们可以将邻接表中的链表改成平衡二叉查找树。实际开发中,我们可以选择用红黑树。这样,我们就可以更加快速地查找两个顶点之间是否存在边了。当然,这里的二叉查找树可以换成其他动态数据结构,比如跳表、散列表等。除此之外,我们还可以将链表改成有序动态数组,可以通过二分查找的方法来快速定位两个顶点之间否是存在边。

图的应用

图的搜索(遍历)

https://en.wikipedia.org/wiki/Graph_traversal

图上的搜索算法,最直接的理解就是,在图中找出从一个顶点出发,到另一个顶点的路径。具体方法有很多,比如两种最简单、最 “暴力” 的深度优先、广度优先搜索,还有 A*、IDA* 等启发式搜索算法。

连通图的两种搜索方式:

邻接矩阵 邻接表
深度优先搜索 栈(LIFO)实现($O(n+e)$)
广度优先搜索 队列(FIFO)实现

深度优先搜索(DFS)

https://en.wikipedia.org/wiki/Depth-first_search

深度优先搜索(Depth-first search, DFS)类似于树的先序遍历

想象成“走迷宫”的过程。

深度优先搜索

实际上,深度优先搜索用的是一种比较著名的算法思想——回溯思想。这种思想解决问题的过程,非常适合用递归来实现。而递归的本质就是压栈与出栈操作。

深度优先搜索的栈(LIFO)实现,过程如下图,将压栈 push 的顶点序列输出即可。

深度优先搜索的栈实现

广度优先搜索(BFS)

https://en.wikipedia.org/wiki/Breadth-first_search

广度优先搜索(Breadth-first search, BFS)类似于树的层次遍历

想象成 “地毯式搜索” 层层推进的过程。

广度优先搜索的队列(FIFO)实现,过程如下:

  1. 首先顶点入队,并输出。

  2. 然后顶点出队。

  3. 将出队顶点相连的所有顶点依次入队,并输出。

重复 2、3 两步,直到所有顶点输出为止,最终结果不唯一。

广度优先搜索的队列实现

广度优先搜索

广度优先搜索

广度优先搜索

连通分量

无向图中的极大连通子图(Maximal connected subgraph)称为原图的连通分量(Connected Components)

连通分量

连通图只有一个极大连通子图,就是它本身。

最小生成树问题(MST problem)

如果无向图中,任意两个顶点都连通,称为连通图(Connected Graph)。如下图:

无向图

如果连通图中,边上有权值,称为连通网(Connected Network)。如下图:

带权图

连通图的一次遍历所经过的点和边的集合,构成一棵生成树(Spanning Tree)

一个连通图的生成树,是含有该连通图的全部顶点的一个极小连通子图(Minimum connected subgraph)

一个具有 $n$ 个顶点的连通图,它的生成树的边数为 $n-1$。

连通图的遍历序列不是唯一的,所以能得到不同的生成树。其中权值总和最小的生成树,称为最小生成树(Minimum Spanning Tree, MST)。如下图:

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible.

最小生成树

最小生成树的准则:

  • 必须使用且仅使用连通网中的 n-1 条边来联结网络中的 n 个顶点;
  • 不能使用产生回路的边
  • 各边上的权值总和达到最小。

最小生成树的应用:规划出总长度最小的网络

Prim 算法

https://en.wikipedia.org/wiki/Prim%27s_algorithm

假设 $N=(V,\ E)$ 是连通网,$TE$ 是 $N$ 上最小生成树中边的集合:

  1. 初始态:$U={u_0},\ (u_0∈V),\ TE={}$

  2. 在所有 $u∈U,\ v∈V-U$ 的边 $(u,\ v)∈E$ 中找一条代价最小的边 $(u,\ v_0)$ 并入集合 $TE$,
    同时 $v_0$ 并入 $U$

  3. 重复 2,直到 $U=V$

形象化理解:由点找边再找点的过程。

Prim 算法

Prim 算法


📝 习题 📝

习题

Kruskal 算法(加边法)

https://en.wikipedia.org/wiki/Kruskal%27s_algorithm

假设 $N=(V,\ E)$ 是连通网

  1. 非连通图 $T={V,\ {}}$,图中每个顶点自成一个连通分量
  2. 在 $E$ 中找一条代价最小,且其两个顶点分别依附不同的连通分量的边(即不形成回路的边),将其
    加入 $T$ 中
  3. 重复 2,直到 $T$ 中所有顶点都在同一连通分量上

形象化理解:由边找点。

Kruskal 算法

Kruskal 算法

最短路径问题(Shortest path problem)

在图论中,最短路径问题是在连通图中寻找两个顶点之间的一条路径,使得其组成边的权重(如时间、距离、费用等)之和最小化的问题。

最短路径的应用:

最短路径的计算方法:

最短路径算法还有很多,比如 Bellford 算法、Floyd 算法等等。

回溯算法

从终点开始,逐步逆向推算。(从终点到起点的逆向回溯过程。)

Dijkstra 算法

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

44 | 最短路径:地图软件是如何计算出最优出行路径的?


📝 习题 📝

习题

目的地 起点:甲 前驱 最短路径
1 ✅(2️⃣) 33 甲 - 1
2 ✅(1️⃣) 27 甲 - 2
3 ✅(4️⃣) 52 甲 - 3
4 ✅(3️⃣) 47 2 甲 - 2 - 4
5 ✅(6️⃣) 122 100 3 甲 - 2 - 4 - 乙 - 5
乙 ✅(5️⃣) 73 67 1 4 甲 - 2 - 4 - 乙

A* 算法

https://en.wikipedia.org/wiki/A*_search_algorithm

49 | 搜索:如何用 A * 搜索算法实现游戏中的寻路功能?

最大流问题(Maximum flow problem)

https://en.wikipedia.org/wiki/Maximum_flow_problem

当以物体、能量或信息等作为流量流过网络时,怎样使流过网络的流量最大,或者使流过网络的流量的费用或时间最小。通常,把设计这样的流量模型问题,叫作网络的流量问题。

最大流量问题,就是在一定条件下,要求流过网络的流量为最大的问题。


📝 习题 📝

习题

拓扑排序(Topological sorting)

拓扑排序算法:

  1. 在有向图中选一个入度为 0 的顶点并输出。
  2. 从图中删除该顶点和所有以它为尾的弧。

重复 1、2 两步,直到所有顶点输出为止,最终结果不唯一。

设某有向图中有 n 个顶点和 e 条边,进行拓扑排序时,总的计算时间为 $O(n+e)$。

拓扑排序

https://en.wikipedia.org/wiki/Topological_sorting

43 | 拓扑排序:如何确定代码源文件的编译依赖关系?

社交网络(Social network)

图的两种存储结构,在社交应用的优缺点对比如下。例如在微博(有向图)中,设我为 $v_i$,ta 为 $v_j$:

  • 邻接矩阵
    • 优点:
      • 存储方式简单、直接,因为基于数组,用户之间的关系获取($O(n)$)、建立($O(1)$)、查找($O(1)$)非常高效。
    • 缺点:
      • 比较浪费存储空间。
      • 获取的好友关系无序。
  • 邻接表:
    • 优点:
      • 节约存储空间。
      • 获取的好友关系可以按关键字排序。
    • 缺点:
      • 用户之间的关系建立、查找相对低效(取决于”关系“使用的数据结构)。
      • 关注列表(邻接表)、粉丝列表(逆邻接表)需要分别存储、同时维护,关系维护相对繁琐。
需求 邻接矩阵 邻接表 A、逆邻接表 R
我关注的人 $A_{[i][0-n]}$ $A_{[i]}$
我的粉丝(关注我的人) $A_{[0-n][i]}$ $R_{[i]}$
我关注 ta $A_{[i][j]}$ = 1 insert($A_{[i]}$, $v_j$) && insert($R_{[j]}$, $v_i$)
我取消关注 ta $A_{[i][j]}$ = 0 delete($A_{[i]}$, $v_j$) && delete($R_{[j]}$, $v_i$)
我是否关注 ta $A_{[i][j]}$ == 1 exist($A_{[i]}$, $v_j$)
ta 的粉丝是否有我 $A_{[i][j]}$ == 1 exist($R_{[j]}$, $v_i$)

基于上述存储结构,可以进一步实现如下需求(以邻接表为例):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 求共同关注
A[i] ∩ A[j]

# 我关注的人也关注 ta
foreach(member in A[i]) {
# 我每个关注的人,他们关注的人中,是否有 ta
A[member] ∩ vj
}

# 我可能认识的人
foreach(member in A[i]) {
# 我每个关注的人,他们关注的人中,有我还没关注的
A[member] - A[i]
}

图应用:微博系统中的好友关系

知识图谱(Knowledge graph)

https://en.wikipedia.org/wiki/Knowledge_graph

参考

https://en.wikipedia.org/wiki/Graph_theory

https://en.wikipedia.org/wiki/Network_theory

30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?

31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?

相关术语

维基百科 Tree (data structure) 的相关术语:

树形结构的相关术语

  • 结点(Node):包含一个数据元素及若干指向其子树的分支。

  • 结点的度(Degree of node):

    For a given node, its number of children. A leaf has necessarily degree zero.

  • 树的度(Degree of tree):

    The degree of a tree is the maximum degree of a node in the tree.

  • 高度(Height)、深度(Depth):

    The height of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree.

    The depth of a node is the length of the path to its root (i.e., its root path).

    Difference Between Tree Depth and Height

    When using zero-based counting, the root node has depth zero, leaf nodes have height zero, and a tree with only a single node (hence both a root and leaf) has depth and height zero. Conventionally, an empty tree (tree with no nodes, if such are allowed) has height −1.

参考:

https://www.baeldung.com/cs/tree-depth-height-difference

https://stackoverflow.com/questions/2603692/what-is-the-difference-between-tree-depth-and-height

一叉树

有没有想过为啥有二叉树,而没有一叉树?实际上顺序表、链式表就是特殊的树,即一叉树实现。

二叉树

二叉树的五种基本形态:

注意:一棵树(包括二叉树)的最少结点个数为 0(空树)。

二叉树的五种基本形态

二叉树的常见形态:

  1. 二叉树
  2. 满二叉树
  3. 完全二叉树

二叉树的性质

二叉树的通用性质:

  • 性质 1:二叉树第 i (i ≥ 1) 层至多有 $2^{i-1}$ 个结点。

    Level start with 1 from root node

  • 性质 2:深度为 k (k ≥ 1) 的二叉树至多有 $2^k-1$ 个结点。

    Depth start with 1 from root node

  • 性质 3:二叉树中,若度数为 0 的叶子结点个数为 $n_0$,度数为 2 的结点个数为 $n_2$,则 $n_0 = n_2 + 1$。

  • 若根节点的层数为 1,则具有 n 个结点的二叉树的最大高度为 n(即一叉树)。

参考:https://www.atnyla.com/tutorial/level-and-height-of-the-tree/3/392

逻辑结构

下面介绍几种特殊的二叉树:

满二叉树(Full Binary Tree)

满二叉树的性质:

  • 深度为 k (k ≥ 1) 的满二叉树,共有 $2^k-1$ 个结点。如下图和表格:

    满二叉树的性质

    $k=1$ $k=2$ $k=3$ $k=4$
    结点总数 $2^1-1=1$ $2^2-1=3$ $2^3-1=7$ $2^4-1=15$

完全二叉树(Complete Binary Tree)

完全二叉树

完全二叉树的性质:

  • 含有 n 个结点的完全二叉树,深度为 $⌊log_2n⌋+1$。

  • 深度为 k 的完全二叉树:

    $k=1$ $k ≥ 2$
    最少结点数 $2^{k-1}$ $2^{k-1}$
    最少叶子结点数 $k$ $2^{k-2}$

    如下图和表格:

    完全二叉树的父子结点编号计算

    $k=1$ $k=2$ $k=3$ $k=4$
    最少结点数 $2^{1-1}=1$ $2^{2-1}=2$ $2^{3-1}=4$ $2^{4-1}=8$
    最少叶子结点树 1 $2^{2-2}=1$ $2^{3-2}=2$ $2^{4-2}=4$
  • 含有 n 个结点的完全二叉树按层编号,则:

完全二叉树的父子结点编号计算

存储结构

顺序存储结构

如果将完全二叉树按层编号,并以编号作为数组下标将结点存入一维数组中,则完全二叉树的顺序存储结构如下图:

完全二叉树的顺序存储

通过观察,完全二叉树按层编号之后,编号之间的关系满足下图的编号计算公式。

完全二叉树的父子结点编号计算

公式可以准确反映出结点之间的逻辑关系,可用于求某结点的父、子结点。(这一性质是二叉树顺序存储结构的基础)

但如果将非完全二叉树按层编号进行顺序存储,则无法套用编号计算公式求父、子结点:

优点 缺点
方式一:直接对结点按层编号,然后再将各结点按编号存入数组。 节省存储空间。 无法根据结点间的下标关系确定它们之间的逻辑关系,从而难以实现二叉树求父、子结点等基本运算。
方式二:先增设虚拟节点,将其转为一棵完全二叉树,然后再按层编号存入数组。 方便实现二叉树求父、子结点等基本运算。 浪费存储空间。

非完全二叉树的顺序存储

所以,如果某棵二叉树是一棵完全二叉树,那用数组存储无疑是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储法那样,要存储额外的左右子节点的指针。这也是为什么完全二叉树会单独拎出来的原因,也是为什么完全二叉树要求最后一层的子节点都靠左的原因。

当我们讲到堆和堆排序的时候,你会发现,堆其实就是一种完全二叉树,最常用的存储方式就是数组。

链式存储结构

二叉树有不同的链式存储结构,其中最常用的是二叉链表三叉链表,其结点形式如下图:

二叉链表和三叉链表的结点形式

二叉树的两种链式存储结构如下图:

二叉树的链式存储结构

其中,判断叶子结点的条件为:(p->lchild == NULL) && (p->rchild == NULL)

基本运算

树常见的基本运算如下:

  • 初始化(Init)
  • 建树(Create)
  • 插入、删除结点
  • 求根(Root)
  • 求双亲(Parent)
  • 求孩子(Child)
    • 二叉树求左孩子(Lchild)
    • 二叉树求右孩子(Rchild)
  • 遍历(Traverse)
    • 二叉树先序遍历(PreOrderTraverse)
    • 二叉树中序遍历(InOrderTraverse)
    • 二叉树后序遍历(PostOrderTraverse)
    • 层次遍历(LevelOrder):从上往下逐层遍历,同一层中结点从左往右

遍历

https://en.wikipedia.org/wiki/Tree_traversal

已知二叉树,求遍历序列

二叉树的遍历(traversing binary tree),是指从根结点出发,按照某种次序依次访问二叉树中所有的结点,使得每个结点被访问有且仅被访问一次。

二叉树的遍历,有三种经典方式:

经典的三种遍历方式 遍历顺序 推导
先序遍历 DLR 首先访问父节点,因此先序序列的第一个结点必为根节点
(如下图先序遍历 A)
中序遍历 LDR 先于根结点的为左子树,后于根结点的为右子树
后序遍历 LRD 最后访问父节点,因此后序序列的最后一个结点必为根节点
(如下图后序遍历 A)

已知二叉树,求三种遍历序列:

二叉树遍历

归纳:

  • 若一棵非空二叉树的先序序列和后序序列相同,则该二叉树中只有一个根节点。
  • 若一棵具有 n (n>0) 个结点的二叉树的先序序列和后序序列正好相反,则该二叉树一定是:高度为 n 的二叉树。
  • 若一棵二叉树的先序序列和中序序列正好相反,则二叉树上每个结点的右子树都是空二叉树。

已知遍历序列,求二叉树

由二叉树的遍历可知,任意一棵二叉树结点的先序序列、中序序列和后序序列都是唯一的。已知先序或后序序列 + 中序序列,可以确定一棵二叉树:

问题:

  • 假设一棵二叉树的中序序列与后序序列分别为:BACDEFGHBCAEDGHF,建立该二叉树。

分析:

二叉树恢复

二叉树遍历的实现方式

  • 递归实现
  • 非递归实现(栈)

多叉树

B-tree

B-tree 的阶(Order),来自 Knuth (1998) 的定义:

Knuth (1998) defining the order to be maximum number of children (which is one more than the maximum number of keys).

所以按照 Knuth 定义一棵 m 阶的 B 树(国内教材所用的定义):

Every node has at most m children.

每个节点最多有 m 个孩子。

Every non-leaf node (except root) has at least ⌈m/2⌉ child nodes.

非叶非根节点至少有 [m/2] 个儿子。[m/2] 表示取大于 m/2 的最小整数。

The root has at least two children if it is not a leaf node.

根节点至少有 2 个儿子。除非它本身是叶子节点,即整棵树只有它一个节点。

A non-leaf node with k children contains k − 1 keys.

非叶节点:有 k 个儿子,就有 k-1 个 keys。

All leaves appear in the same level and carry no information.

所有叶子节点在同一层,不携带信息 data。

例如一棵 3 阶 B 树,高度相比二叉树会更低。

B+ Tree

特性:

  • 非叶子节点存储索引;
  • 叶子节点存储数据,且通过双向链表关联。

为什么用?

  • 为了减少内存开销和磁盘 IO

    B+树非叶子节点上是不存储数据的,仅存储键值,而B树节点中不仅存储键值,也会存储数据。之所以这么做是因为在数据库中页的大小是固定的,innodb中页的默认大小是16KB。如果不存储数据,那么就可以存储更多的键值,相应的树的阶数就会更大,树就会更矮更胖,如此一来我们查找数据进行磁盘的IO次数会再次减少,数据查询的效率也会更快。另外,B+树的阶数是等于键值的数量的,如果我们的B+树一个节点可以存储1000个键值,那么3层B+树可以存储1000×1000×1000=10亿个数据。一般根节点是常驻内存的,所以一般我们查找10亿数据,只需要2次磁盘IO。

  • 为了支持区间查找

    因为B+树索引的所有数据均存储在叶子节点,而且数据是按照顺序排列的,叶子节点间通过双向链表连接。那么B+树使得范围查找,排序查找,分组查找以及去重查找变得异常简单。而B树因为数据分散在各个节点,要实现这一点是很不容易的。

树和森林

https://en.wikipedia.org/wiki/Tree_structure

逻辑结构

无回路的连通图(Connected Graph)即为树。

存储结构

森林(Forest):n 棵互不相交的树的集合。

A set of n ≥ 0 disjoint trees.

LC-RS Representation

https://blog.csdn.net/chengyq116/article/details/112342319

https://slidetodoc.com/left-childright-sibling-representation-instructor-prof-jyhshing-roger/

Parent Representation

List Representation

树的应用

分类算法

哈夫曼树(最优二叉树)

https://en.wikipedia.org/wiki/Huffman_tree

哈夫曼树的性质:

  • 哈夫曼树中,不存在度数为 1 的分支结点
  • 若度数为 0 的叶子结点个数为 $n_0$,则哈夫曼树共有 $2n_0 - 1$ 个结点。
  • 若度数为 2 的结点个数为 $n_2$,则哈夫曼树共有 $2(n_2 + 1) - 1$ 个结点。

灵光一现的创造 霍夫曼编码

【霍夫曼编码原理 文本压缩、ZIP压缩文件原理 Huffman Encoding by Tom Scott-哔哩哔哩】 https://b23.tv/wFatkFc

【Huffman 编码动画演示】 https://www.bilibili.com/video/BV18V411v7px/

查找

二叉查找树(Binary Search Tree, BST)

中序遍历时从小到大的二叉树。

平衡二叉查找树(Balanced Binary Search Tree, BBST)

排序

堆排序(Heap)

28 | 堆和堆排序:为什么说堆排序没有快速排序快?

29 | 堆的应用:如何快速获取到 Top 10 最热门的搜索关键词?

参考

Tree (data structure)

23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?

24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?

48 | B+树:MySQL数据库索引是如何实现的?

AVL树,红黑树,B树,B+树,Trie树都分别应用在哪些现实场景中?

Implementing a Binary Tree in Java | Baeldung

线性结构

数组

线性表顺序存储的方法是:将表中的结点依次存放在计算机内存中一组连续的存储单元中,数据元素在线性表中的邻按关系决定它们在存储空间中的存储位置,即:逻辑结构中相邻的结点其存储位置也相邻。用顺序存储实现的线性表称为顺序表。一般使用数组来表示顺序表。因此,数组可以看成线性表的一种推广。

一维数组

存储结构

一维数组又称向量(Vector),它由一组具有相同类型的数据元素组成,并存储在一组连续的存储单元中。其存储结构如下图:

顺序表

基本运算

对于可变长数组(Resizable Array)的插入、删除操作,其元素移动情况如下:

元素移动次数
(n 为数组大小, i 为操作位置)
平均移动次数 时间复杂度
插入 $n-i+1$ 次 $n/2$ 次 O(n)
删除 $n-i$ 次 $(n-1)/2$ 次 O(n)

顺序表操作

二维数组

若一维数组中的数据元素又是一维数组结构,则称为二维数组,以此类推。一般地,一个 n 维数组可以看成元素为 n-1 维数组的线性表。

二维数组的地址计算(行优先)如下:

$$
loc[i,\ j]=loc[0,\ 0]+(n*i+j)*k
$$

其中,$i$ 为行坐标,$j$ 为列坐标,$n$ 为总列数,$k$ 为存储单元。

由公式可知,数组元素的存储位置是下标的线性函数

矩阵(Matrix)是很多科学计算问题研究的对象,矩阵可以用二维数组来表示

在数值分析中经常出现一些高阶矩阵,这些高阶矩阵中有许多值相同的元素或者零元素,如果值相同的元素或者零元素在矩阵中的分布有一定规律,称此类矩阵为特殊矩阵。矩阵的非零元素个数很少的矩阵称为稀疏矩阵

为了节省存储空间,对这类矩阵采用多个值相同的元素只分配一个存储空间,零元素不存储的策略,这一方法称为矩阵的压缩存储

链表

存储结构

四种链表对比:

四种链表 非循环 循环(Cycle)
单向(Singly) 单向链表 单向循环链表
双向(Doubly) 双向链表 双向循环链表

其中,是否循环的关键代码差异如下:

关键代码 非循环链表 循环链表
判断是否空链表 head->next == NULL head->next == head
判断是否尾结点 p->next == NULL p->next == head

四种链表对比

基本运算

单链表插入(insert p before i)、删除(delete i)结点操作如下:

1
2
3
4
5
6
7
8
9
10
11
// 单链表需要先找到 i - 1 结点以便进行插入、删除操作
q = get(i - 1);

// 插入结点(注意操作顺序:先新再旧)
p->next = q->next;
q->next = p;

// 删除结点
p = q->next;
q->next = p->next;
free(p);

注意:等号左边是指针,等号右边是结点。

单链表操作

双向循环链表插入(insert p after i)、删除(delete i)结点操作如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
// 双向循环链表直接获取 i 结点即可,因为可以通过其前驱、后继指针直接进行插入、删除操作
q = get(i);

// 插入结点(注意操作顺序)
p->prev = q;
p->next = q->next;
q->next->prev = p;
q->next = p;

// 删除结点(注意操作顺序)
q->prev->next = q->next;
q->next->prev = q->prev;
free(q);

注意:等号左边是指针,等号右边是结点

双向循环链表操作

顺序存储结构

链式存储结构

基本运算

栈

使用场景

队列

顺序存储结构

链式存储结构

基本运算

队列

使用场景

引言

计算机解决一个具体问题时,一般需要经过以下几个步骤:

  1. 从具体的问题抽象出一个适当的数学模型;什么是数学模型呢?数学模型常常是现实世界的一个简化,是抽取对象的本质特性构造出来的。尽管数学是一门精准的科学,但是我们建立数学模型却要从实际出发,要针对问题做必要简化,简化的标准有两个:够用、易解。
  2. 设计一个求解该数学模型的算法
  3. 用某种计算机编程语言编写实现该算法的程序,调试和运行程序直至最终得到问题的解。

计算机解决问题的步骤

基本概念和术语

data_structure

  • 数据:所有被计算机存储、处理的对象。
  • 数据对象:是性质相同的数据元素的集合,是数据的子集。
  • 数据元素:数据的基本单位,也是运算的基本单位。例如在数据库中,又称为记录(Record)/元组(Tuple)。
  • 数据项:数据不可分割的最小单位。例如在数据库中,又称为字段(Field)/域(Domain)。
  • 数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。它包括:
    • 数据的逻辑结构
    • 数据的存储结构
    • 数据的基本运算

逻辑结构

https://en.wikipedia.org/wiki/Abstract_data_type

集合结构

任意两个结点之间都没有邻接关系,组织形式松散:

集合结构

集合的三大特性:

  • 确定性:给定一个集合,任给一个元素,该元素或者属于或者不属于该集合,二者必居其一,不允许有模棱两可的情况出现。
  • 互异性:一个集合中,任何两个元素都认为是不相同的,即每个元素只能出现一次。有时需要对同一元素出现多次的情形进行刻画,可以使用多重集,其中的元素允许出现多次。
  • 无序性:一个集合中,每个元素的地位都是相同的,元素之间是无序的。集合上可以定义序关系,定义了序关系后,元素之间就可以按照序关系排序。但就集合本身的特性而言,元素之间没有必然的序。

集合之间可以进行运算:

数学符号 含义 英文
Intersection
Union
Difference

线性结构

顾名思义,线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组,链表、队列、栈等也是线性表结构。

而与它相对立的概念是非线性表,比如二叉树、堆、图等。之所以叫非线性,是因为,在非线性表中,数据之间并不是简单的前后关系。

线性结构

特征:

  • 排队(1:1)
  • 起始节点无直接前驱
  • 终端节点无直接后继
  • 中间节点都有直接前驱和直接后继

树形结构

父子(1:N)

树形结构的相关术语

有没有想过为啥只有二叉树,而没有一叉树?实际上链表就是特殊的树,即一叉树。

图结构

地图(N:M)

图结构

存储结构

数据的逻辑结构在计算机中的实现,称为数据的存储结构(或物理结构)。

一般情况下,一个存储结构包括以下两个部分:

  • 存储数据元素本身
  • 数据元素之间的关联方式

逻辑结构常见的存储结构实现如下:

顺序存储方式 链式存储方式 散列存储方式 索引存储方式
集合结构 散列表(Hash Table)
线性结构 数组(一维、二维)
顺序栈
循环队列(取余运算)
链表(单向/双向、是否循环)
链栈
链队列
树形结构
(二叉树)
一维数组
  • 满二叉树
  • 完全二叉树
  • 非完全二叉树(需增设虚拟结点转为完全二叉树)
  • 链表
  • 二叉链表
  • 三叉链表
  • 树形结构
    (树)
    双亲表示法(一维数组) 孩子链表表示法(一维数组 + 单链表)
    孩子兄弟表示法(二叉链表,LC-RS)
    图结构 邻接矩阵(二维数组) 邻接表(一维数组 + 单链表)

    顺序存储方式

    所有存储结点存放在一个连续的存储区中。利用结点在存储区中的相对位置来表示数据元素之间的逻辑关系。

    链式存储方式

    每个存储结点除了含有一个数据元素之外,还包含指针,每个指针指向一个与本结点有逻辑关系的结点。利用指针表示数据元素之间的逻辑关系。

    散列存储方式

    散列表(Hash Table)。

    索引存储方式

    基本运算

    基本运算,是指在某种逻辑结构上施加的操作,即对逻辑结构的加工。这种加工以数据的逻辑结构为对象。一般而言,在每个逻辑结构上,都定义了一组基本运算,这些运算包括:等。

    • 建立(Init)
    • 读取(Access)
    • 查找(Search)
    • 插入(Insert)
    • 删除(Delete)

    算法

    定义:一个算法规定了求解给定问题所需的处理步骤及其执行顺序,使得给定问题能在有限时间内被求解。

    算法分析:

    • 正确性
    • 易读性
    • 健壮性
    • 时空性

    时间复杂度

    空间复杂度

    常用数据结构

    data_structure

    参考

    https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

    https://www.bigocheatsheet.com

    https://the-algorithms.com/

    数据结构与算法教程 C 语言版教程

    Techie Delight

    C 语言

    C++ integrates the operators new and delete for allocating dynamic memory. But these were not available in the C language; instead, it used a library solution, with the functions malloc, calloc, realloc and free, defined in the header <cstdlib> (known as <stdlib.h> in C). The functions are also available in C++ and can also be used to allocate and deallocate dynamic memory.

    Note, though, that the memory blocks allocated by these functions are not necessarily compatible with those returned by new, so they should not be mixed; each one should be handled with its own set of functions or operators.

    动态内存分配 malloc, calloc, realloc

    https://www.runoob.com/cprogramming/c-memory-management.html

    动态内存回收 free

    https://www.runoob.com/cprogramming/c-memory-management.html

    C++ 语言

    动态内存分配 new

    在 C++ 中,您可以使用特殊的运算符为给定类型的变量在运行时分配堆内存(memory heap),这会返回所分配的空间地址

    动态内存分配使用 new 运算符,后面跟上一个数据类型,语法如下:

    1
    2
    3
    4
    5
    6
    // allocate memory to contain one single element of specified type
    pointer = new type

    // allocate a block (an array) of elements of specified type, where `number_of_elements` is an integer value representing the amount of these.
    // it returns a pointer to the beginning of the new block of memory allocated.
    pointer = new type [number_of_elements]

    例如:

    1
    2
    int * bar = new int(5); // int bar = 5
    int * foo = new int[5]; // int foo[5]

    In this case, the system dynamically allocates space for five elements of type int and returns a pointer to the first element of the sequence, which is assigned to foo (a pointer). Therefore, foo now points to a valid block of memory with space for five elements of type int.

    Here, foo is a pointer, and thus, the first element pointed to by foo can be accessed either with the expression foo[0] or the expression *foo (both are equivalent). The second element can be accessed either with foo[1] or *(foo+1), and so on…

    由于使用动态内存分配机制,因此 number_of_elements 可以是一个变量,变量值在运行时才决定,例如:p = new int[i];


    声明普通数组与使用 new 分配动态内存的区别:

    There is a substantial difference between declaring a normal array and allocating dynamic memory for a block of memory using new. The most important difference is that the size of a regular array needs to be a constant expression, and thus its size has to be determined at the moment of designing the program, before it is run, whereas the dynamic memory allocation performed by new allows to assign memory during runtime using any variable value as size.


    C++ 提供了两种标准机制来检查堆内存分配是否成功:

    The dynamic memory requested by our program is allocated by the system from the memory heap. However, computer memory is a limited resource, and it can be exhausted. Therefore, there are no guarantees that all requests to allocate memory using operator new are going to be granted by the system.

    C++ provides two standard mechanisms to check if the allocation was successful:

    机制一:异常机制

    One is by handling exceptions. Using this method, an exception of type bad_alloc is thrown when the allocation fails. If this exception is thrown and it is not handled by a specific handler, the program execution is terminated.

    1
    foo = new int [5];  // if allocation fails, an exception is thrown

    机制二:返回空指针

    The other method is known as nothrow, and what happens when it is used is that when a memory allocation fails, instead of throwing a bad_alloc exception or terminating the program, the pointer returned by new is a null pointer, and the program continues its execution normally.

    This method can be specified by using a special object called nothrow, declared in header <new>, as argument for new:

    1
    foo = new (nothrow) int [5];

    In this case, if the allocation of this block of memory fails, the failure can be detected by checking if foo is a null pointer:

    1
    2
    3
    4
    5
    int * foo;
    foo = new (nothrow) int [5];
    if (foo == nullptr) {
    // error assigning memory. Take measures.
    }

    This nothrow method is likely to produce less efficient code than exceptions, since it implies explicitly checking the pointer value returned after each and every allocation. Therefore, the exception mechanism is generally preferred, at least for critical allocations. But nothrow mechanism is more simplicity.

    It is considered good practice for programs to always be able to handle failures to allocate memory, either by checking the pointer value (if nothrow) or by catching the proper exception.

    动态内存回收 delete

    如果您不再需要动态分配的内存空间,可以使用 delete 运算符,删除之前由 new 运算符分配的堆内存(memory heap),以便该内存可再次用于其它动态内存分配。语法如下:

    1
    2
    3
    4
    5
    // releases the memory of a single element allocated using new
    delete bar;

    // releases the memory allocated for arrays of elements using new and a size in brackets ([])
    delete [] foo; // 不管所删除数组的维数多少,指针名前只用一对方括号 []

    参考

    http://www.cplusplus.com/doc/tutorial/dynamic/

    Input/Output library

    下图是 C++ 提供的输入/输出库,其中:

    • <xxx> 表示:头文件
    • 白框表示:类(Classes)
    • 黑框表示:对象(Objects)

    Input/Output library

    The iostream library is an object-oriented library that provides input and output functionality using streams.

    A stream is an abstraction that represents a device on which input and ouput operations are performed. A stream can basically be represented as a source or destination of characters of indefinite length.

    Streams are generally associated to a physical source or destination of characters, like a disk file, the keyboard, or the console, so the characters gotten or written to/from our abstraction called stream are physically input/output to the physical device. For example, file streams are C++ objects to manipulate and interact with files; Once a file stream is used to open a file, any input or output operation performed on that stream is physically reflected in the file.

    To operate with streams, C++ provides the standard iostream library, which contains the following elements:

    Elements of the iostream library

    Basic class templates

    The base of the iostream library is the hierarchy of class templates. The class templates provide most of the functionality of the library in a type-independent fashion.

    Class template instantiations

    The library incorporates two standard sets of instantiations of the entire iostream class template hierarchy:

    • The narrow-oriented (char type) instantiation is probably the better known part of the iostream library. Classes like ios, istream and ofstream are narrow-oriented. The diagram on top of this page shows the names and relationships of narrow-oriented classes.

    • The classes of the wide-oriented (wchar_t) instatiation follow the same naming conventions as the narrow-oriented instantiation but with the name of each class and object prefixed with a w character, forming wios, wistream and wofstream, as an example.

    Objects

    As part of the iostream library, the header file <iostream> declares certain objects that are used to perform input and output operations on the standard input and output.

    They are divided in two sets:

    • narrow-oriented objects: cin, cout, cerr and clog
    • wide-oriented objects: wcin, wcout, wcerr and wclog

    Manipulators

    Manipulators are global functions designed to be used together with insertion (<<) and extraction (>>) operators performed on iostream stream objects. They generally modify properties and formatting settings of the streams.

    常用头文件

    下列这些头文件在 C++ 编程中很常用,下面分别介绍:

    头文件 函数和描述
    <iostream> 该文件定义了 cincoutcerrclog 对象,用于输入输出。
    <iomanip> 该文件通过所谓的参数化的流操纵器(比如 setwsetfillsetprecision),来声明对执行标准化 I/O 有用的服务。
    <fstream> 该文件定义了 ifstreamofstreamfstream 对象,用于文件读写。

    <iostream>

    下图摘录了 iostream 类的继承关系及成员函数,如下:

    iostream classes

    http://www.cplusplus.com/doc/tutorial/basic_io/

    http://www.cplusplus.com/reference/iolibrary/

    output stream

    输出流与流插入运算符 << 配合使用。<iostream> 提供了下列三种输出流对象:

    • cout 标准输出流(默认设备是显示器屏幕)
    • cerr 无缓冲标准错误输出流(默认设备是显示器屏幕)
    • clog 有缓冲标准错误输出流(默认设备是打印机)

    此外,<iostream> 还提供了一个常用的操纵符:

    • endl Insert newline and flush

    例子:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    // 定义一些头文件,这些头文件包含了程序中必需的或有用的信息。
    #include <iostream>
    // 告诉编译器使用 std 命名空间。命名空间是 C++ 中一个相对新的概念。使用该命名空间之后,std::cout 可以简写为:cout
    using namespace std;

    // 主函数,程序从这里开始执行。
    int main()
    {
    // 在屏幕上输出 "Hello World"
    cout << "hello world" << std::endl;

    // 终止 main() 函数,并向调用进程返回值 0。
    return 0;
    }

    // 使用 g++ 编译器,编译 cpp 源文件为可执行文件,并执行之
    // cd "/Users/wuqd/Documents/workspace/cpp/" && g++ HelloWorld.cpp -o HelloWorld && "/Users/wuqd/Documents/workspace/cpp/"HelloWorld

    运行结果:hello world

    input stream

    输入流与流提取运算符 >> 配合使用。<iostream> 提供了下列一种输入流对象:

    • cin 标准输入流(默认设备是键盘)

    例子:

    1
    2
    3
    4
    5
    cin >> name;
    cin >> age;

    // 流提取运算符 >> 在一个语句中可以多次使用,如果要求输入多个数据,可以使用如下语句:
    cin >> name >> age;

    <iomanip> 流操纵器

    常用流操纵器函数如下:

    函数 作用
    setw Set field width
    setfill Set fill character
    setprecision Set decimal precision

    setw 函数用于设置字段的宽度,只对紧接着的输出产生作用。当后面紧跟着的输出字段长度小于 n 的时候,在该字段前面默认用空格补齐,当输出字段长度大于 n 时,全部整体输出。如下:

    setw

    例子:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    #include <iostream>
    #include <iomanip>
    using namespace std;

    /*
    * 测试 I/O
    */
    int main()
    {
    double pi = 3.1415926;

    // 默认右补位,可以使用 setf() 进行左补位
    cout.setf(ios::left);

    // setprecision() 包含小数点
    cout << setfill('*') << setw(5) << setprecision(3) << pi << endl;

    return 0;
    }

    运行结果:3.14*

    参考:

    https://www.runoob.com/w3cnote/cpp-func-setw.html

    <fstream> 文件读写

    <fstream> 定义了下面三个对象,用于文件读写:

    数据类型 描述
    ofstream 该数据类型表示输出文件流,用于创建文件并向文件写入信息。
    ifstream 该数据类型表示输入文件流,用于从文件读取信息。
    fstream 该数据类型通常表示文件流,且同时具有 ofstream 和 ifstream 两种功能,这意味着它可以创建文件,向文件写入信息,从文件读取信息。

    例子:

    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
    #include <iostream>
    #include <fstream>
    using namespace std;

    void output() {
    ofstream myfile;
    // 打开文件
    myfile.open("/Users/wuqd/Desktop/test", ios::app); // ios::app 表示追加模式。所有写入都追加到文件末尾。
    // 写入文件
    myfile << "helloworld" << endl;
    // 关闭文件
    myfile.close();
    }

    void input() {
    ifstream in;
    // 打开文件
    in.open("/Users/wuqd/Desktop/test");
    char data[100];
    // 读取文件
    while (in >> data) {
    // 输出到屏幕
    cout << data << endl;
    }
    // 关闭文件
    in.close();
    }

    int main() {
    output();
    input();
    return 0;
    }

    参考:

    https://www.cplusplus.com/doc/oldtutorial/files/

    https://www.runoob.com/cplusplus/cpp-files-streams.html

    继承

    C++ 继承的语法如下,支持单继承和多继承:

    1
    2
    3
    4
    5
    // Single inheritance 单继承
    class derived_class: access_specifier base_class

    // Multiple inheritance 多重继承,各个基类之间用逗号分隔
    class derived_class: access_specifier base_class_1, access_specifier base_class_2, ...

    继承类型

    继承类型通过访问修饰符 access_specifier 来指定:

    继承类型 基类的 public 成员 基类的 protected 成员 基类的 private 成员
    公有继承(public 派生类的 public 成员 派生类的 protected 成员 无法继承
    保护继承(protected 派生类的 protected 成员 派生类的 protected 成员 无法继承
    私有继承(private 派生类的 private 成员 派生类的 private 成员 无法继承

    通常使用 public 继承,几乎不使用 protectedprivate 继承。

    In principle, a publicly derived class inherits access to every member of a base class except:

    • its constructors and its destructor
    • its assignment operator members (operator=)
    • its friends
    • its private members

    继承的访问控制属性

    Access public protected private
    members of the same class yes yes yes
    members of derived class yes yes no
    not members yes no no

    构造、析构函数执行顺序

    Even though access to the constructors and destructor of the base class is not inherited, they are automatically called by the constructors and destructor of the derived class.

    Unless otherwise specified, the constructors of a derived class calls the default constructor of its base classes (i.e., the constructor taking no arguments).

    继承后,执行顺序如下:

    • 构造函数:先父后子
    • 析构函数:先子后父

    子类调用父类方法

    BaseClass::Function()

    多态

    One of the key features of class inheritance is that a pointer to a derived class is type-compatible with a pointer to its base class. Polymorphism is the art of taking advantage of this simple but powerful and versatile feature.

    类继承的关键特性之一,就是指向派生类的指针与指向其基类的指针在类型上兼容。 多态是利用这一简单但强大而通用的功能的艺术。

    下面使用指针来演示多态这一特性。

    UML 类图如下:

    UML 类图

    类声明如下:

    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
    // pointers to base class
    #include <iostream>
    using namespace std;

    class Shape {
    protected:
    int width, height;
    public:
    Shape(int width, int height) {
    this->width = width;
    this->height = height;
    }
    virtual int area() { return 0; }
    };

    class Rectangle : public Shape {
    public:
    Rectangle(int x, int y) : Shape(x, y) {};
    int area() { return width * height; }
    };

    class Triangle : public Shape {
    public:
    Triangle(int x, int y) : Shape(x, y) {};
    int area() { return width * height / 2; }
    };

    使用方式一:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    int main() {
    Rectangle rect(2, 3);
    Triangle trgl(2, 3);

    Shape * p1 = &rect;
    Shape * p2 = &trgl;

    cout << "rectangle area is " << p1->area() << endl; // rectangle area is 6
    cout << "triangle area is " << p2->area() << endl; // triangle area is 3

    return 0;
    }

    使用方式二,参考:Dynamic memory

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    int main() {

    Shape * p1 = new Rectangle(2, 3);
    Shape * p2 = new Triangle(2, 3);

    cout << "rectangle area is " << p1->area() << endl; // rectangle area is 6
    cout << "triangle area is " << p2->area() << endl; // triangle area is 3

    delete p3;
    delete p4;

    return 0;
    }

    描述如下:

    Function main declares two pointers to Shape (named p1 and p2). These are assigned the addresses of rect and trgl, respectively, which are objects of type Rectangle and Triangle. Such assignments are valid, since both Rectangle and Triangle are classes derived from Shape.

    Dereferencing p1 and p2 (with p1-> and p2->) is valid and allows us to access the members of their pointed objects. For example, the following two statements would be equivalent in the previous example:

    1
    2
    rect.area();
    p1->area();

    虚函数(virtual)

    虚函数是在基类中使用 virtual 关键字声明的函数,是可以在派生类中重定义的成员函数。虚函数用于实现运行时多态

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    +--------------------+
    | Base Class |
    | virtual function |
    +---------^----------+
    |
    |class inheritance
    |
    +---------+----------+
    | Derived class |
    | redefined function|
    +--------------------+

    运行时多态的实现手段:虚函数 + 继承 + 函数重定义

    派生类也可以重定义基类的非虚函数,但无法通过基类的引用来访问派生类的该函数。即:如果移除上述基类中 area 函数声明的 virtual 关键字,下面的函数调用将返回 0,因为实际调用的是基类的版本:

    1
    2
    cout << "rectangle area is " << p1->area() << endl;  // rectangle area is 0
    cout << "triangle area is " << p2->area() << endl; // triangle area is 0

    Therefore, essentially, what the virtual keyword does is to allow a member of a derived class with the same name as one in the base class to be appropriately called from a pointer, and more precisely when the type of the pointer is a pointer to the base class that is pointing to an object of the derived class, as in the above example.

    A class that declares or inherits a virtual function is called a polymorphic class.

    注意,尽管成员之一是 virtual 的,但 Sharp 仍然是一个常规类,可以实例化对象。

    纯虚函数(抽象类)

    Classes that contain at least one pure virtual function are known as abstract base classes. The syntax of pure virtual function is to replace their definition by =0 (an equal sign and a zero):

    1
    2
    3
    4
    5
    6
    7
    // abstract class CPolygon
    class Shape {
    protected:
    int width, height;
    public:
    virtual int area () = 0;
    };

    Abstract base classes cannot be used to instantiate objects:

    1
    2
    3
    // 不允许使用抽象类类型 "Shape" 的对象: -- 函数 "Shape::area" 是纯虚函数
    // variable type 'Shape' is an abstract class
    Shape shape;

    But an abstract base class is not totally useless. It can be used to create pointers to it, and take advantage of all its polymorphic abilities.

    1
    2
    3
    // the following pointer declarations would be valid
    Shape * p1 = &rect;
    Shape * p2 = &trgl;

    Virtual members and abstract classes grant C++ polymorphic characteristics, most useful for object-oriented projects.

    C++ 接口是使用抽象类来实现的。

    参考

    http://www.cplusplus.com/doc/tutorial/inheritance/

    http://www.cplusplus.com/doc/tutorial/polymorphism/

    类的声明:

    1
    2
    3
    4
    5
    6
    7
    class class_name {
    access_specifier_1:
    member1;
    access_specifier_2:
    member2;
    ...
    } object_names;

    访问修饰符

    • private members of a class are accessible only from within other members of the same class (or from their friend). By default, all members of a class have private access for all its members.
    • protected members are accessible from other members of the same class (or from their friend), but also from members of their derived classes.
    • Finally, public members are accessible from anywhere where the object is visible.

    this 指针

    在 C++ 中,每一个对象都能通过 this 指针来访问自己的地址。this 指针是所有成员函数的隐含参数。因此,在成员函数内部,它可以用来指向调用对象。

    友元函数没有 this 指针,因为友元不是类的成员。只有成员函数才有 this 指针。

    静态成员(static)

    static 关键字用于修饰静态成员变量或函数。限制如下:

    • 无法访问类的非静态成员变量或函数;
    • 无法使用 this 指针。

    静态成员的引用方式:Runoob:runoob_age

    成员函数

    有两种方式定义类的成员函数:

    • 内联成员函数(inline member function)
    • 普通成员函数(not-inline member function)

    两种方式并不会导致行为上的差异,而只会导致可能的编译器优化。

    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
    // classes example
    #include <iostream>
    using namespace std;

    class Rectangle {
    int width, height;
    public:
    // declaration of a member function within the class
    void set_values (int, int);
    // defining a member function completely within the class definition
    int area() {return width*height;}
    };

    // definition of a member function of a class outside the class itself.
    // The scope operator (::) specifies the class to which the member being defined belongs, granting exactly the same scope properties as if this function definition was directly included within the class definition.
    void Rectangle::set_values (int x, int y) {
    width = x;
    height = y;
    };

    int main () {
    Rectangle rect;

    // public members of object can be accessed by dot operator (.)
    rect.set_values (3,4);
    cout << "area: " << rect.area() << endl;
    return 0;
    }

    常成员函数

    To specify that a member is a const member, the const keyword shall follow the function prototype, after the closing parenthesis for its parameters:

    1
    int get() const {return x;}        // const member function

    构造函数

    类的构造函数是类的一种特殊的成员函数,构造函数的名称与类的名称是完全相同的,并且不会返回任何类型,也不会返回 void。它会在每次创建类的新对象时执行:

    1
    2
    3
    4
    // 调用有参构造函数
    Rectangle rect(1, 2); // Object is being created, width=1, height=2
    // 调用默认构造函数
    Rectangle rectb; // Object is being created

    构造函数重载

    Overloading constructors

    Like any other function, a constructor can also be overloaded with different versions taking different parameters: with a different number of parameters and/or parameters of different types. The compiler will automatically call the one whose parameters match the arguments:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class Rectangle {
    int width, height;
    public:
    // 声明一个无参构造函数
    Rectangle();
    // 声明一个有参构造函数
    Rectangle(int, int);
    };

    // 定义一个无参构造函数
    Rectangle::Rectangle() {
    cout << "Object is being created" << endl;
    }

    // 定义一个有参构造函数
    Rectangle::Rectangle(int width, int height) {
    this->width = width;
    this->height = height;
    cout << "Object is being created, width=" << this->width << ", height=" << this->height << endl;
    };

    This example introduces a special kind constructor: the default constructor. The default constructor is the constructor that takes no parameters, and it is special because it is called when an object is declared but is not initialized with any arguments. In the example above, the default constructor is called for rectb. Note how rectb is not even constructed with an empty set of parentheses - in fact, empty parentheses cannot be used to call the default constructor:

    1
    2
    Rectangle rectb;   // ok, default constructor called
    Rectangle rectc(); // oops, default constructor NOT called, empty parentheses interpreted as a function declaration

    This is because the empty set of parentheses would make of rectc a function declaration instead of an object declaration: It would be a function that takes no arguments and returns a value of type Rectangle.

    在构造函数中初始化成员变量

    使用构造函数初始化其他成员变量时,有下面两种方式:

    Member initialization in constructors

    When a constructor is used to initialize other members, these other members can be initialized directly, without resorting to statements in its body. This is done by inserting, before the constructor’s body, a colon (:) and a list of initializations for class members. For example, consider a class with the following declaration:

    1
    2
    3
    4
    5
    6
    class Rectangle {
    int width, height;
    public:
    Rectangle(int, int);
    int area() {return width*height;}
    };

    The constructor for this class could be defined, as usual, as:

    1
    Rectangle::Rectangle(int x, int y) { width=x; height=y; }

    But it could also be defined using member initialization as:

    1
    Rectangle::Rectangle(int x, int y) : width(x), height(y) { }

    Or even:

    1
    Rectangle::Rectangle(int x, int y) : Shape(x, y) { }

    Note how in this last case, the constructor does nothing else than initialize its members, hence it has an empty function body.

    析构函数(~)

    类的析构函数是类的一种特殊的成员函数,它会在每次删除对象时执行,有助于在跳出程序前释放资源(比如关闭文件、释放内存等)。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Rectangle {
    int width, height;
    public:
    // 构造函数
    Rectangle();
    // 析构函数
    ~Rectangle();
    };

    Rectangle::Rectangle(){
    cout << "Object is being created" << endl;
    };

    Rectangle::~Rectangle(){
    cout << "Object is being deleted" << endl;
    };

    析构函数要点:

    • 析构函数名称与类的名称完全相同,前缀使用关键字 ~
    • 一个类中只能声明一个析构函数(destructor cannot be redeclared);
    • 析构函数无参数(destructor cannot have any parameters);
    • 析构函数无返回值(destructor cannot have a return type);
    • 不可重载。

    友元函数(friend)

    类的友元函数(friend 关键字),有权访问类的所有私有(private)和保护(protected)成员变量。尽管友元函数在类中声明,但是友元函数并不是类的成员函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Rectangle {
    int width, height;
    public:
    friend int getWidth(Rectangle);
    friend int getHeight(Rectangle rect) {
    return rect.height;
    }
    };

    int getWidth(Rectangle rect) {
    return rect.width;
    }

    int main () {
    Rectangle rect1(1, 2);

    cout << "width: " << getWidth(rect1) << " height: " << getHeight(rect1) << endl; // width: 1 height: 2
    return 0;
    }

    友元函数破坏了类的封装性,实践中不建议使用。

    重载(overload)

    函数重载

    可以声明几个功能类似的同名函数,但是这些同名函数的形式参数(指参数的个数、类型或者顺序)必须不同。

    运算符重载

    一、支持重载的运算符:

    C++ allows most operators to be overloaded so that their behavior can be defined for just about any type, including classes. Here is a list of all the operators that can be overloaded:

    1
    2
    3
    4
    +    -    *    /    =    <    >    +=   -=   *=   /=   <<   >>
    <<= >>= == != <= >= ++ -- % & ^ ! |
    ~ &= ^= |= && || %= [] () , ->* -> new
    delete new[] delete[]

    Operators are overloaded by means of operator functions, which are regular functions with special names: their name begins by the operator keyword followed by the operator sign that is overloaded. The syntax is:

    1
    type operator sign (parameters) { /*... body ...*/ }

    二、重载运算符的不同形式:

    There is a table with a summary of the parameters needed for each of the different operators than can be overloaded (please, replace @ by the operator in each case):

    Expression Operator Member function Non-member function
    @a + - * & ! ~ ++ -- A::operator@() operator@(A)
    a@ ++ -- A::operator@(int) operator@(A,int)
    a@b + - * / % ^ & | < > == != <= >= << >> && || , A::operator@(B) operator@(A,B)
    a@b = += -= *= /= %= ^= &= |= <<= >>= [] A::operator@(B) -
    a(b,c...) () A::operator()(B,C...) -
    a->b -> A::operator->() -
    (TYPE) a TYPE A::operator TYPE() -

    Where a is an object of class A, b is an object of class B and c is an object of class C. TYPE is just any type (that operators overloads the conversion to type TYPE).

    Notice that some operators may be overloaded in two forms: either as a member function or as a non-member function.

    三、例子:

    For example, cartesian vectors are sets of two coordinates: x and y. The addition operation of two cartesian vectors is defined as the addition both x coordinates together, and both y coordinates together. For example, adding the cartesian vectors (3,1) and (1,2) together would result in (3+1,1+2) = (4,3). This could be implemented in C++ with the following code:

    Overloading operators

    The function operator+ of class CVector overloads the addition operator (+) for that type. Once declared, this function can be called either implicitly using the operator, or explicitly using its functional name:

    1
    2
    3
    4
    5
    // called either implicitly using the operator
    c = a + b;

    // or explicitly using its functional name
    c = a.operator+ (b);

    Both expressions are equivalent.

    四、注意点:

    Attention

    The operator overloads are just regular functions which can have any behavior; there is actually no requirement that the operation performed by that overload bears a relation to the mathematical or usual meaning of the operator, although it is strongly recommended. For example, a class that overloads operator+ to actually subtract or that overloads operator== to fill the object with zeros, is perfectly valid, although using such a class could be challenging.

    函数重定义(redefine)

    即 Java 语言中的方法重写(rewrite)。

    类指针

    Objects can also be pointed to by pointers: Once declared, a class becomes a valid type, so it can be used as the type pointed to by a pointer. For example:

    1
    2
    // a pointer to an object of class Rectangle.
    Rectangle * prect;

    Similarly as with plain data structures, the members of an object can be accessed directly from a pointer by using the arrow operator (->). Here is an example with some possible combinations:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    // pointer to classes example
    #include <iostream>
    using namespace std;

    class Rectangle {
    int width, height;
    public:
    Rectangle(int x, int y) : width(x), height(y) {}
    int area(void) { return width * height; }
    };

    int main() {
    Rectangle obj(3, 4);
    Rectangle * foo, * bar; // 类指针(Pointers to classes)
    foo = &obj;
    bar = new Rectangle (5, 6); // 参考:http://www.cplusplus.com/doc/tutorial/dynamic/
    cout << "obj's area: " << obj.area() << '\n';
    cout << "*foo's area: " << foo->area() << '\n';
    cout << "*foo's area: " << (*foo).area() << '\n';
    cout << "*bar's area: " << bar->area() << '\n';
    cout << "*bar's area: " << (*bar).area() << '\n';
    delete bar;
    return 0;
    }

    This example makes use of several operators to operate on objects and pointers (operators *, &, ., ->). They can be interpreted as:

    expression can be read as
    *x pointed to by x
    &x address of x
    x.y member y of object x
    x->y member y of object pointed to by x
    (*x).y member y of object pointed to by x (equivalent to the previous one)

    模板

    模板是泛型编程的基础,泛型编程即以一种独立于任何特定类型的方式编写代码。

    函数模板

    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
    // function templates
    #include <iostream>
    using namespace std;

    template <typename T>
    T getmax (T a, T b)
    {
    T retval;
    retval = a > b ? a : b;
    return retval;
    }

    int main () {
    int maxInt = getmax(100, 75);
    cout << maxInt << endl; // 100

    double maxDouble = getmax(3.3, 2.18);
    cout << maxDouble << endl; // 3.3

    // no matching function for call to 'getmax'
    // char maxChar = getmax('a', 1.99);
    // cout << maxChar << endl;

    return 0;
    }

    类模板

    Just like we can create function templates, we can also create class templates, allowing classes to have members that use template parameters as types. For example:

    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
    // class templates
    #include <iostream>
    using namespace std;

    template <class T>
    class MyPair {
    T a, b;
    public:
    MyPair (T first, T second)
    {a=first; b=second;}
    T getmax ();
    };

    // In case that a member function is defined outside the defintion of the class template, it shall be preceded with the template <...> prefix
    template <class T>
    T MyPair<T>::getmax ()
    {
    T retval;
    retval = a > b ? a : b;
    return retval;
    }

    int main () {
    MyPair<int> myobject(100, 75);
    cout << myobject.getmax() << endl; // 100

    MyPair<double> myfloats(3.3, 2.18);
    cout << myfloats.getmax() << endl; // 3.3

    // implicit conversion from 'double' to 'char' changes value from 1.99 to 1
    // MyPair<char> mychars('a', 1.99);
    // cout << mychars.getmax() << endl;

    return 0;
    }

    Notice the syntax of the definition of member function getmax:

    1
    2
    template <class T>
    T mypair<T>::getmax ()

    There are three T‘s in this declaration: The first one is the template parameter. The second T refers to the type returned by the function. And the third T (the one between angle brackets) is also a requirement: It specifies that this function’s template parameter is also the class template parameter.

    模板类

    模板类是类模板实例化后的一个产物。

    It is possible to define a different implementation for a template when a specific type is passed as template argument. This is called a template specialization.

    For example:

    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
    // template specialization
    #include <iostream>
    using namespace std;

    // class template:
    template <class T>
    class mycontainer {
    T element;
    public:
    mycontainer (T arg) {element=arg;}
    T increase () {return ++element;}
    };

    // class template specialization:
    template <>
    class mycontainer <char> {
    char element;
    public:
    mycontainer (char arg) {element=arg;}
    char uppercase ()
    {
    if ((element>='a')&&(element<='z'))
    element+='A'-'a';
    return element;
    }
    };

    int main () {
    mycontainer<int> myint (7);
    mycontainer<char> mychar ('j');
    cout << myint.increase() << endl; // 8
    cout << mychar.uppercase() << endl; // J
    return 0;
    }

    This is the syntax used for the class template specialization:

    1
    2
    template <>
    class mycontainer <char> { ... };

    First of all, notice that we precede the class name with template<> , including an empty parameter list. This is because all types are known and no template arguments are required for this specialization, but still, it is the specialization of a class template, and thus it requires to be noted as such.

    But more important than this prefix, is the <char> specialization parameter after the class template name. This specialization parameter itself identifies the type for which the template class is being specialized (char). Notice the differences between the generic class template and the specialization:

    1
    2
    template <class T> class mycontainer { ... };
    template <> class mycontainer <char> { ... };

    The first line is the generic template, and the second one is the specialization.

    When we declare specializations for a template class, we must also define all its members, even those identical to the generic template class, because there is no “inheritance” of members from the generic template to the specialization.

    参考

    http://www.cplusplus.com/doc/tutorial/classes/

    http://www.cplusplus.com/doc/tutorial/templates/

    http://www.cplusplus.com/doc/tutorial/classes2/

    https://www.cplusplus.com/doc/oldtutorial/templates/

    https://www.runoob.com/cplusplus/cpp-classes-objects.html

    https://www.runoob.com/cplusplus/cpp-templates.html