无法插入中文字符

  • 报错内容:

    1366 - Incorrect string value: ‘\xE6\x9B\xBE\xE5\x8D\x8E’ for column ‘sname’ at row 1

  • 原因

    MySQL默认配置:

    variable_name value
    character_set_database latin1
    character_set_server latin1

    可通过SHOW VARIABLES LIKE '%char%';查看。

  • 解决方法

    1. 修改C:\ProgramData\MySQL\MySQL Server 5.7\my.ini

      • 找到[mysql]

        在下方添加default-character-set=utf8

      • 找到[mysqld]

        在下方添加character-set-server=utf8

      • 找到[client]

        在下方添加default-character-set=utf8

    2. 重启MySQL,重新登录

      • Win + R - services.msc

      • 找到MySQL57(57为版本号),右键选择重新启动

      • Win + R - cmd(或cmder)

        通过mysql -u -root -p命令并输入密码后访问数据库。

      • 通过SHOW VARIABLES LIKE '%char%';查看,字符集变为utf8即成功修改。


  • 报错内容:

    2059 - Authentication plugin ‘caching_sha2_password’ cannot be loaded

  • 原因:

    MySQL8之前的版本中加密规则为mysql_native_password,而在MySQL8以后的加密规则为caching_sha2_password

  • 解决方法:

    在命令行中登录MySQL后,使用命令行:

    ALTER USER 'root'@'localhost' IDENTIFIED WITH mysql_native_password BY 'password';

第1章 了解SQL

  • 数据库软件应称为DBMS(数据库管理系统)。
  • 数据库是通过DBMS创建和操纵的容器。
  • 在很大程度上说,数据库究竟是文件还是别的什么东西并不重要,因为你并不直接访问数据库;你使用的是DBMS,它替你访问数据库。
  • 模式(schema): 关于数据库布局及特性的信息。
  • 有时,模式用作数据库的同义词。遗憾的是,模式的含义通常在上下文中并不是很清晰。
  • 主键(primary key)
  • SQL(发音为字母S-Q-L或sequel)是**结构化查询语言(Structured Query Language)**的缩写。
阅读全文 »

Python和Java一样大小写敏感

变量和简单数据类型

字符串

在Python中,用引号(可以是单引号,也可以是双引号)括起的都是字符串。

使用方法修改字符串的大小写

  • title():

    将字符串中每个单词 首字母改为大写其余字母小写

  • upper()

    将字符串中所有字母改为

  • lower()

    将字符串中所有字母改为


合并(拼接)字符串

Python使用+来合并字符串。


使用方法删除多余的空格

  • strip()

    删除字符串首尾空格

  • lstrip():

    删除字符串开头的空格

  • rstrip()

    删除字符串末尾的空格


将字符串中的特定单词都替换为另一个单词

replace()

例子:

message = "I really like dogs."
message.replace('dog', 'cat')

Python2中的print语句

例如:print "Hello Python 2.7 world!"

无需将要打印的内容放在括号内。从技术上说,Python 3中的print是一个函数,因此括号必不可少。


数字

整数

  • Python用**表示次方运算

    3**2的结果为9。


浮点数


使用函数str()避免类型错误

str()将非字符串值表示为字符串


Python允许在数字中间以_分隔,提高可读性

JDK7的特性:赋值时,可以用下划线_分割过长的数字(整数&浮点数均可),提高可读性


注释

在Python中,用**井号#**标识注释。


列表简介

列表是什么

列表由一系列按特定顺序排列的元素组成,像一个。可以创建包含字母表中所有字母、数字、所有家庭成员姓名的列表,也可以加入任何东西,其中的元素之间可以没有任何关系

在Python中,用方括号[]表示列表,并用逗号来分隔其中的元素。如:

bicycles = ['trek', 'cannondale', 'redline', 'specialized']
print(bicycles)

Python会打印列表的内部表示包括方括号

['trek', 'cannondale', 'redline', 'specialized']

访问列表元素

bicycles[0],请求获取列表元素时,Python只返回该元素,而不包括方括号和引号,是整洁干净的输出

还可以对任何列表元素调用字符串方法。


索引从0开始

  • Python还为访问最后一个列表元素提供了一种特数语法:将索引指定为-1即可访问最后一个列表元素。这种约定也适用于其他负数索引,如**-2返回倒数第二个**列表元素,以此类推。

    列表为空时,这种访问最后一个元素的方式会导致错误


使用列表中的各个值

可以像使用其他变量一样使用列表中的各个值。


修改、添加和删除元素

修改列表元素

指定列表名和要修改的元素的索引,再指定该元素的新值即可。如:

motorcycles = ['honda', 'yamaha', 'suzuki']
motorcycles[0] = 'ducati'

在列表中添加元素

  • 在列表末尾添加元素:使用append()方法

    motorcycles.append('ducati')

    append()方法让动态地创建列表易如反掌。

  • 在列表中插入元素:使用insert()方法(需要指定新元素的索引和值)

    motorcycles.insert(0, 'ducati')

从列表中删除元素

  • 使用del语句删除元素

    知道要删除的元素在列表中的位置,可以用del语句。

    del motorcycles[0]

    删除元素后,其余元素索引会相应发生变动。

  • 使用**方法pop()**删除元素

    方法pop()可以删除列表末尾元素,并能让你接着使用它

    popped_motorcycle = motorcycle.pop()
  • 弹出列表中任何位置处的元素

    在方法pop()的括号中指定要删除元素的索引即可。

    first_owned = motorcycles.pop(0)

  • 使用方法remove()根据值删除元素

    不知道要从列表中删除的值所处的位置,只知道要删除元素的值是,可以使用方法remove()

    方法remove()只删除第一个指定的值。如果要删除的值可能在列表中出现多次,就需要使用循环来判断是否删除了所有这样的值


组织列表

使用方法sort()对列表进行永久性排序

  • 无参数:按字母顺序排序
  • 填入参数reverse=True:按字母逆序排序
cars = ['bmw', 'audi', 'toyota', 'subaru']

# 按字母顺序排序
cars.sort()
# 得到结果cars = ['audi', 'bmw', 'subaru', 'toyota']


# 按字母逆序排序
cars.sort(reverse=True)
print(cars)
# 得到结果cars = ['toyota', 'subaru', 'bmw', 'audi']

并非所有的值都是小写时,按字母顺序排列列表要复杂些。决定排列顺序时,有多种解读大写字母的方式,要指定准确的排列顺序可能比较复杂。但是大多数排序方式都基于本节介绍的知识。


使用函数sorted()对列表进行临时排序

print(sorted(cars))

反转列表元素

  • reverse()方法

    注意:与sort(reverse=True)中的reverse作用不同。

cars.reverse()

确定列表的长度

  • len()方法
len(cars)

使用列表时避免索引错误


错误示例:

motorcycles = ['honda', 'yamaha', 'suzuki']
print(motorcycles[3])

即类似其他语言的数组越界访问,会引起索引错误


操作列表

遍历整个列表

语句为for xxx in xxx:(注意不要遗漏冒号

例子:

magicians = ['alice', 'david', 'carolina']
for magician in magicians:
    print(magician)
  • 编写for循环时,对于用于存储列表中每个值的临时变量,可指定任何名称
  • Python根据缩进来判断代码行与前一个代码行的关系。在for循环后面,没有缩进的代码就不是循环的一部分

避免缩进错误

  • 两行独立的代码语句,如果不小心缩进,Python将会报错。

创建数字列表

使用函数range()

for value in range(1, 5):
    print(value)

打印结果为:

1
2
3
4

即输出范围左闭右开

习题:使用一个for循环打印数字1~20()

for value in range(1, 21):
    print(value)

使用range()创建数字列表

  • 要创建数字列表,可使用函数list()range()的结果直接转换成列表。
numbers = list(range(1,6))
# 得到numbers = [1, 2, 3, 4, 5]
  • 使用range()函数还可以指定步长
even_numbers = list(range(2, 11, 2))
# 得到numbers = [2, 4, 6, 8, 10]
  • 创建包含(1-10)的平方的数字列表
squares = []
for value in range(1,11):
    squares.append(value**2)
  • 对数字列表执行简单的统计计算

    • min()
    • max()
    • sum()
    digits = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
    min(digits)
    max(digits)
    sum(digits)

列表解析

列表解析将for循环和创建新元素的代码合并成一行,并自动附加新元素。

如创建平方数列表可以写成:

squares = [value**2 for value in range(1, 11)]

要使用这种语法,首先指定一个描述性的列表名,如squares;然后定义一个表达式,用于生成要存储到列表中的值

在上述例子中,表达式为value**2


使用列表的一部分

Python称列表的部分元素切片


切片

创建切片可指定要使用的第一个元素的索引最后一个元素的索引+1(创建范围左闭右开)。

如:

players = ['charles', 'martina', 'michael', 'florence', 'eli']
print(players[0:3])
  • 如果没有指定第一个索引,Python将自动从列表开头开始

    player[:4]

  • 让切片终止于列表末尾,也可通过省略终止索引实现。

    player[2:]

  • 如果想输出最后三名队员,可通过切片player[-3:]实现


遍历切片

for player in players[:3]:
    print(player);

复制列表

要复制列表,可以通过同时省略起始索引和终止索引创建一个包含整个列表的切片

例如,假设有一个列表,其中包含你最喜欢的三种食品,而你还想创建另外一个列表,其中包含一位朋友喜欢的所有食物。不过你喜欢的视频,这位朋友都喜欢,因此可以通过复制来创建这个列表:

my_foods = ['pizza', 'falafel', 'carrot cake']
friend_foods = my_foods[:]

# 如下直接赋值,无法得到两个独立的列表
friend_foods = my_foods

元组

列表可以修改的,非常适合用于存储在程序运行期间可能变化的数据集。但有时候需要创建一系列不可修改的元素,元组可以满足这种需求。

Python将不可变的列表称为元组


定义元组

元组看起来犹如列表,但使用圆括号来标识。

例如有一个大小不应改变的矩形,可将其长宽存储在一个元组中:

dimensions = (200, 50)

遍历元组中的所有值

同遍历列表相同


修改元组变量

虽然不能修改元组中的元素,但可以给存储元组的变量赋值。因此如果要修改前述矩形的尺寸,可重新定义整个元组

dimensions = (200, 50)

# 重新定义元组
dimensions = (400, 100)

设置代码格式

PEP(Python Enhancement Proposal):Python改进提案

PEP 8是最古老的PEP之一,提供了代码格式设置指南。


缩进

PEP 8建议每级缩进都使用四个空格,既提高可读性,又留下了足够的多级缩进空间。

字处理文档中,大家常常使用 制表符 而不是 空格 来缩进。对于字处理文档来说,这样做的效果很好,但混合使用制表符和空格会让Python解释器感到迷惑。每款文本编辑器都提供了将输入的制表符转换为指定数量的空格的设置。在编写代码时应该使用制表符键,但一定要对编辑器进行设置,使其在文档中插入空格而不是制表符


行长

建议每行不超过80字符,PEP 8还建议注释的行长不超过72字符,因为有些工具为大型项目自动生成文档时,会在每行注释开头添加格式化字符。在大多数编辑器中,都可以设置一个视觉标志——通常是一条垂直参考线,让我们知道不能越过的界限在什么地方。


if 语句

条件测试

值为True或False的表达式被称为条件测试

检查是否相等时,大小写的影响

  • 在Python中检查是否相等时区分大小写,两个大小写不同的值会被视为不相等

  • 如果大小写无关紧要,可将变量的值转换为小写,再进行比较:

    car = 'Audi'
    car.lower() == 'audi'
    # 结果为True

检查多个条件

  • 使用and检查多个条件(Java/C/C++ 中为 &&)
  • 使用or检查多个条件(Java/C/C++ 中为 ||)

检查特定值是否包含在列表中

有时候,执行操作前必须检查列表是否包含特定的值。例如,结束用户的注册过程前,可能需要检查用户名是否已包含在用户名列表中。在地图程序中,可能需要检查用户提交的位置是否包含在已知位置列表中。

要判断特定的值是否已包含在列表中,可使用关键字in

requested_toppings = ['mushrooms', 'onions', 'pineapple']
print('mushrooms' in requested_toppings)

检查特定值是否不包含在列表中

使用关键字not in。例如,如果有一个列表,其中包含被禁止在论坛上发表评论的用户,就可在允许用户提交评论前检查他是否被禁言:

banned_users = ['andrew', 'carolina', 'david']
user = 'marie'

if user not in banned_users:
    print(user.title() + ", you can post a response if you wish.")

布尔表达式

布尔表达式不过是条件测试的别名

布尔值通常用于记录条件,如游戏是否正在运行,或用户是否可以编辑网站的特定内容:

game_active = True
can_edit = False

if语句

简单的 if 语句

if conditional_test:
    do something

假设有一个表示某人年龄的变量,而你想知道这个人是否够投票的年龄,可使用如下代码:

age = 19
if age >= 18:
	print("You are old enough to vote!")

if - else 语句

age = 19
if age >= 18:
	print("You are old enough to vote!")
else:
	print("Sorry, you are too young to vote.")

if - elif - else 结构

在现实世界中,很多情况下需要考虑的情形都超过两个。

age = 12

if age < 4:
    price = 0
elif age < 18:
    price = 5
else:
    price = 10
    
print("Your admission cost is $" + str(price) + ".")

使用if语句处理列表

检查特殊元素

requested_toppings = ['mushrooms'. 'green peppers', 'extra cheese']

for requested_topping in requested_toppings:
    if requested_topping == 'green peppers':
        print("Sorry, we are out of green peppers right now.")
    else:
        print("Adding " + requested_topping + '.')
        
print("\nFinished making your pizza!")

确定列表不是空的

requested_toppings = []

if requested_toppings:
    for requested_topping in requested_toppings:
        print("Adding " + requested_topping + '.')    
    print("\nFinished making your pizza!")
else:
    print("Are you sure you want a plain pizza?")
  • if语句将 列表名 用在条件表达式中时,Python将在列表至少包含一个元素时返回True,并在列表为空时返回False

使用多个列表

下列示例定义两个列表,其中第一个列表包含披萨店供应的配料,第二个列表包含顾客点的配料。这次对于顾客要求的每个配料,都检查是否时披萨店供应的配料:

avaliable_toppings = ['mushrooms', 'olives', 'green peppers',
                     'pepperoni', 'pineapple', 'extra cheese']
requested_toppings = ['mushrooms'. 'green peppers', 'extra cheese']

for requested_topping in requested_toppings:
    if requested_topping in avaliable_toppings:
        print("Adding " + requested_topping + ".")
    else:
        print("Sorry, we don't have " + requested_topping + ".")
print("\nFinished making your pizza!")

字典

  • 列表:用括号[]标识

  • 元组:用括号()标识(不可修改)

  • 字典:用括号{}标识


使用字典

在Python中,字典是一系列 键-值 对。每个键都与一个值相关联,可以使用键来访问与之相关联的值可以将任何Python对象用作字典中的值

键和值之间冒号:分隔,键-值对之间逗号分隔。如:alien_0 = {'color': 'green', 'points': 5}


访问字典中的值

要获取与键相关联的,可依次指定字典名放在方括号内的键

如:

alien_0 = {'color': 'green', 'points': 5}
new_points = alien_0['points']

添加 键-值 对

字典是一种动态结构可随时添加 键-值 对。要添加 键-值 对,可依次指定字典名、用方括号括起的键相关联的值

如:

alien_0['x_position'] = 0
alien_0['y_position'] = 25
  • 键-值 对的排列顺序添加顺序不同。Python只关心 键-值 对之间的关联关系

先创建一个空字典

可先使用一对空的花括号定义一个字典,再分行添加各个 键-值 对。

使用字典存储用户提供的数据或在编写能自动生成大量 键-值 对的代码时,通常都需要先定义一个空字典


修改字典中的值

修改字典中的值,可依次指定字典名、用方括号括起的以及与该键相关联的新值


删除 键-值 对

对于字典中不再需要的信息,可使用del语句将相应的 键-值 对彻底删除。使用del语句时,必须指定字典名要删除的键

如:

del alien_0['points']
  • 删除的 键-值 对永远消失

由类似对象组成的字典

字典可以存储一个对象的多种信息,也可以存储众多对象的同一种信息

favorite_languages = {
    'jen': 'python',
    'sarah': 'c',
    'edward': 'ruby',
    'phil': 'python',
}

遍历字典

遍历所有的 键-值 对

user_0 = {
    'username': 'efermi'.
    'first': 'enrico',
    'last': 'fermi',
	}
for key, value in user_0.items():
    print("\nKey: " + key)
    print("Value: " + value)

如例子所示,要编写用于遍历字典的for循环。可声明两个变量用于存储键和值,这两个变量可以使用任何名称。

  • 方法items()返回一个 键-值 对列表
  • 即使遍历字典时,键-值 对的返回顺序与存储顺序不同

遍历字典中的所有键

  • 方法keys()返回一个键列表

    for name in favorite_languages.keys():
        print(name.title())
  • 遍历字典时,会默认遍历所有的。因此for name in favorite_languages.keys():for name in favorite_languages:效果相同

下面遍历一下字典中的名字,但在名字为指定朋友的名字时,打印一条消息,指出其喜欢的语言:

friends = ['phil', 'sarah']
for name in favorite_languages.keys():
    print(name.title())
    if name in friends:
        print(" Hi " + name.title() +
             ", I see your favorite language is " +
             favorite_languages[name].title() + "!")
  • 还可以使用keys()确定某个人是否接受了调查:

    if 'erin' not in favorite_languages.keys():
        print("Erin, please take our poll!")
  • 方法keys()并非只能用于遍历,实际上,它返回一个包含字典中所有键的列表。


按顺序遍历字典中的所有键

要以特定的顺序返回元素,一种办法是在for循环中对返回的键进行排序。为此,可以使用函数sorted()(临时排序)来获得按特定顺序排列的键列表的副本

for name in sorted(favorite_languages.keys()):
    print(name.title() + ", thank you for taking the poll.")

遍历字典中的所有值

  • 方法values()返回一个值列表

    这种做法提取字典中所有的值,没有考虑是否重复。为剔除重复项,可使用集合(set)。(在C/C++中,set是一个内部自动递增排序不含重复元素的容器)

    for language in set(favorite_languages.values()):
        print(language.title())

嵌套

在列表中存储字典

字典alien_0包含一个外星人的各种信息,但无法存储第二个外星人的信息。如何管理成群结队的外星人呢?一种办法是创建一个外星人列表,其中每个外星人都是一个字典,包含有关该外星人的各种信息(即字典列表)。

# 创建一个用于存储外星人的空列表
aliens = []

# 创建30个绿色的外星人
for alien_number in range(0, 30):
    new_alien = {'color': 'green', 'points': 5, 'speed': 'slow'}
    aliens.append(new_alien)
    
# 显示前五个外星人
for alien in aliens[:5]:
    print(alien)
print("...")

# 显示创建了多少个外星人
print("Total number of aliens: " + str(len(aliens)))
  • 获取列表长度:函数len(列表名)

在字典中存储列表

有时候,需要将列表存储在字典中。例如,你要如何描述顾客点的披萨呢?如果使用列表,只能存储要添加的披萨配料;但使用字典,还可以包含其他有关披萨的描述。

pizza = {
    'crust': 'thick',
    'toppings': ['mushrooms', 'extra cheese'],
}

for topping in pizza['topping']:
    print("\t" + topping)
  • 每当需要在字典中将一个键关联到多个值时,都可以在字典中嵌套一个列表

在本章前面有关喜欢的编程语言的示例中,如果将每个人的回答都存储在一个列表中,被调查者就可以选择多种喜欢的语言。因此,在遍历该字典的for循环中,我们需要再使用一个for循环来遍历与被调查者相关联的语言列表:

favorite_languages = {
    'jen': ['python', 'ruby'],
    'sarah': ['c'],
    'edward': ['ruby', 'go'],
    'phil': ['python', 'haskell'],
	}

for name, languages in favorite_languages.items():
    print("\n" + name.title() + " 's favorite languages are:")
    for language in languages:
        print("\t" + language.title())

在字典中存储字典

可以在字典中嵌套字典,但这样做时,代码可能很快复杂起来。


将列表转换为字典


用户输入和while循环

函数input()的工作原理

函数input()让程序暂停运行,等待用户输入一些文本获取用户输入后,Python将其存储在一个变量中,Python将用户输入解读为字符串

例如,下面的程序让用户输入一些文本,再将这些文本呈现给用户:

message = input("Tell me something, and I will repeat it back to you: ")
print(message)
  • 函数input()接受一个参数,即要向用户显示的提示或说明
  • 程序等待用户输入,并在用户按回车键后继续运行

编写清晰的程序

有时候,提示可能超过一行,例如,你可能需要指出获取特定输入的原因。这种情况下,可将提示存储再一个变量中,再将该变量传递给函数input()。

prompt = "If you tell us who you are, we can personalize the messages you see."
prompt += "\nwhat is your first name? "

name = input(prompt)

使用int()来获取数值输入

函数int()让Python将输入视为数值

height = input("How tall are you, in inches? ")
height = int(height)

在Python 2.7 中获取输入

Python 2.7应使用函数raw_input()来提示用户输入,这个函数与Python 3 中的nput()一样,将输入解读为字符串。

Python 2.7 也包含函数input(),但它将用户输入解读为Python代码,并尝试运行它们。因此最好的结果是出现错误,指出Python不明白输入的代码;最糟糕的结果是,将运行原本无意运行的代码。


while循环简介

使用标志

在要求很多条件都满足才继续运行的程序中,可定义一个变量,用于判断真个程序是否处于活动状态,这个变量被称为标志。这样,在while语句中,只需检查一个条件——while的当前值是否为True

active = True
while active:
    message = input()
    if message == 'quit':
        active = false
    else:
        print(message)

使用 break 退出循环

while True:
    city = input()
    if city == 'quit':
        break;
    else:
        print("xxxxx")

在循环中使用 continue


避免无限循环

如果程序陷入无限循环,可按Ctrl + C,也可关闭显示程序输出的终端窗口。

有些编辑器(如 Sublime Text)内嵌了输出窗口,这可能导致难以结束无限循环,因此不得不关闭编辑器来结束无限循环。


使用 While 循环来处理列表和字典

for循环是一种遍历列表的有效方式,但在for循环中不应修改列表,否则将导致Python难以跟踪其中的元素。要在遍历列表的同时对其进行修改,可使用while循环。将while循环同列表和字典结合起来使用,可收集、存储并组织大量输入,供以后查看和显示。


在列表之间移动元素

假设一个列表,其中包含新注册但还未验证的网站用户;验证这些用户后,如何将他们移到另一个已验证用户列表中呢?一种办法是使用一个while循环,在验证用户的同时将其从未验证用户列表中提取出来,再将其加入到另一个已验证用户列表中

unconfirmed_users = ['alice', 'brian', 'candace']
confirmed_users = []

# 验证每个用户,直到没有未验证用户为止
# 将每个经过验证的用户都移到已验证用户列表中
while unconfirmed_users:
    current_user = unconfirmed_users.pop()
    confirmed_user.append(current_user)
  • 方法pop()删除列表末尾用户

删除包含特定值的所有列表元素

在第3章中,我们使用方法remove()删除列表中的特定值(只删除第一个指定的值)。如果要删除列表中所有包含特定值的元素,该怎么办?

pets = ['dog', 'cat', 'dog', 'goldfish', 'cat', 'rabbit', 'cat']

while 'cat' in pets:
    pets.remove('cat')

函数

现有函数

  • round(number, ndigits=None)
    • number:需要进行四舍五入的数字
    • ndigits: 指定的位数,按此位数进行四舍五入

定义函数

下面是一个打印问候语的简单函数:

def greet_user():
    """显示简单的问候语"""
    print("Hello!")

greet_user()
  • 使用关键字def告诉Python要定义一个函数,定义以冒号结尾
  • 第二行的文本"""显示简单的问候语"""是被称为文档字符串(docstring)注释文档字符串三引号括起,Python用它们来生成有关程序中函数的文档

向函数传递信息

def greet_user(username):
    """显示简单的问候语"""
    print("Hello, " + username.title() + "!")

greet_user('jesse')

传递实参

向函数传递实参的方式很多,可使用位置实参,这要求实参的顺序与形参的顺序相同;也可使用关键字实参,其中每个实参都由形参名和值组成;还可使用列表和字典

  • 关键字实参(顺序无关紧要)

    def describe_pet(animal_type, pet_name):
        """显示宠物的信息"""
        print("\nI have a " + animal_type + ".")
        print("My " + animal_type + "'s name is " + pet_name.title() + ".")
        
    describe_pet(animal_type='hamster', pet_name = 'harry')

默认值

编写函数时,可为每个形参指定默认值,那么在函数调用中就可以省略相应的实参。

def describe_pet(pet_name, animal_type='dog'):
    """显示宠物的信息"""
    print("\nI have a " + animal_type + ".")
    print("My " + animal_type + "'s name is " + pet_name.title() + ".")
    
describe_pet(pet_name='willie')
  • 由于给animal_type 指定了默认值,因此在函数调用中只包含一个实参——宠物的名字。然而,Python依然将这个实参视为位置实参,因此如果函数调用中只包含宠物的名字,这个实参将关联到函数定义中的第一个形参,因此需要将pet_name放在形参列表开头。这样,就能在函数调用中只提供小狗的名字了:

    describe_pet('willie')
  • 被指定默认值的形参,可以通过显式地提供实参忽略默认值


返回值

返回简单值

def get_formatted_name(first_name, last_name):
    """返回整洁的姓名"""
    full_name = first_name + ' ' + last_name
    return full_name.title()

musician = get_formatted_name('jimi', 'hendrix')

让实参变成可选的

def get_formatted_name(first_name, last_name, middle_name=''):
    """返回整洁的姓名"""
    if middle_name:
        full_name = first_name + ' ' + middle_name + ' ' + last_name
    else:
        full_name = first_name + ' ' + last_name
    return full_name.title()
  • Python将非空字符串解读为True

返回字典

def build_person(first_name, last_name, age=''):
    """返回一个字典,其中包含有关一个人的信息"""
    person = {'first': first_name, 'last': last_name}
    if age:
        person['age'] = age
    return person

musician = build_person('jimi', 'hendrix')

传递列表

假设有一个用户列表,我们要问候其中的每位用户。下面的示例将一个名字列表传递给一个名为greet_users()的函数,这个函数问候列表中的每个人:

def greet_users(names):
    """向列表中的每位用户都发出简单的问候"""
    for name in names:
        msg = "Hello, " + name.title() + "!"
        print(msg)
        
usernames = ['hannah', 'ty', 'margot']
greet_users(usernames)

禁止函数修改列表

为了防止函数修改列表,可向函数传递列表的副本而不是原件

将列表的副本传递给函数,可以像下面这样做:

function_name(list_name[:])
  • 切片表示法[:]创建列表的副本

虽然像函数传递列表的副本可保留原始列表的内容,但除非有充分的理由需要传递副本否则还是应该将原始列表传递给函数。因为让函数使用现成列表避免花时间和内存创建副本,从而提高效率,在处理大型列表时尤其如此。


传递任意数量的实参

有时候,你预先不知道函数需要接受多少个实参,好在Python允许函数从调用语句中收集任意数量的实参

def make_pizza(*toppings):
    """打印顾客点的所有配料"""
    print(toppings)
    
make_pizza('pepperoni')
make_pizza('mushrooms', 'green peppers', 'extra cheese')
  • 形参名*toppings中的星号*让Python创建一个名为toppings的空元组(用圆括号()标识,不可修改),并将收到的所有值都封装到这个元组中。

结合使用位置实参和任意数量实参

如果要让函数接受不同类型的实参,必须在函数定义中将接纳任意数量实参的形参放在最后。Python先匹配位置实参关键字实参,再将余下的实参都收集到最后一个形参中

例如,如果前面的函数还需要一个表示披萨尺寸的实参必须将该形参放在形参*toppings前面

def make_pizza(size, *toppings):
    """概述要制作的披萨"""
    print("\nMaking a " + str(size) +
         "-inch pizza with the following toppings:")
    for topping in toppings:
        print("- " + topping)
    
make_pizza(16, 'pepperoni')
make_pizza(12, 'mushrooms', 'green peppers', 'extra cheese')

使用任意数量的关键字实参

有时候,需要接受任意数量的实参,但预先不知道传递给函数的会是什么样的信息。可将函数编写成能够接受任意数量的 键-值 对——调用语句提供了多少就接受多少。

一个示例是创建用户简介:你知道将受到有关用户的信息,但不确定是什么样的信息。

def build_profile(first, last, **user_info):
    """创建一个字典,其中包含我们知道的有关用户的一切"""
    profile = {}
    profile['first_name'] = first
    profile['last_name'] = last
    for key, vaule in user_info.items():
        profile[key] = value
    return profile

user_profile = build_profile('albert', 'einstein',
                            location='princeton',
                            field='physics')
  • 形参名**user_info中的两个星号**让Python创建一个名为user_info的空字典(用花括号{}标识),并将收到的所有 名称-值 对都封装到这个字典中。

将函数存储在模块中

使用函数的优点之一是,使用它们可将代码块与主程序分离。通过给函数指定描述性名称,可让主程序容易理解得多。还可以更进一步,将函数存储在被称为模块的独立文件中再将模块导入到主程序中import语句允许在当前运行的程序文件中使用模块中的代码

导入整个模块

要让函数是可导入的,得先创建模块。模块是扩展名为.py的文件包含要导入到程序中的代码

下面来创建一个包含函数make_pizza()的模块。为此,我们将文件pizza.py中除函数make_pizza()之外的其他代码都删除:

def make_pizza(size, *toppings):
    """概述要制作的披萨"""
    print("\nMaking a " + str(size) +
         "-inch pizza with the following toppings:")
    for topping in toppings:
        print("- " + topping)

接下来,我们在pizza.py所在的目录中创建另一个名为making_pizzas.py的文件,这个文件导入到刚创建的模块,再调用make_pizza()两次:

import pizza

pizza.make_pizza(16, 'pepperoni')
pizza.make_pizza(12, 'mushrooms', 'green peppers', 'extra cheese')
  • Python读取这个文件时,代码行import pizza让Python打开pizza.py,并将其中的所有函数都复制到这个程序中

  • 要调用被导入的模块中的函数,可指定导入的模块的名称pizza和函数名make_pizza(),并用句点分隔它们。如果你使用这种import语句导入了名为module_name.py的整个模块,就可使用下面的语法来使用其中任何一个函数:

    module_name.function_name()

导入特定的函数

from module_name import function_0, function_1, function_2
  • 通过逗号分隔函数名,可根据需要从模块中导入任意数量的函数
  • 使用这种语法,调用函数时就无需使用句点

使用 as 给函数指定别名

要给函数指定别名,需要在导入时这样做。

from module_name import function_name as fn
  • 上面的语句将函数function_name()重命名为fn()

使用 as 给模块指定别名

import module_name as mn

导入模块中的所有函数

使用星号*运算符可让Python导入模块中的所有函数

from pizza import *

make_pizza(16 'pepperoni')

import语句中的星号让Python将模块pizza中的每个函数都复制到这个文件中。由于导入了每个函数,可通过名称来调用每个函数,而无需使用句点表示法。然而,使用并非自己编写的大型模块时,最好不要采用这种导入方法:Python可能遇到多个名称相同的函数或变量,进而覆盖函数,而不是分别导入所有的函数。

最佳的做法是,要么只导入需要使用的函数,要么导入整个模块并使用句点表示法,这能让代码更清晰,更容易阅读和理解。


函数编写指南

  1. 给函数指定描述性名称,且只使用小写字母下划线

  2. 每个函数都应包含简要地阐述其功能的注释,该注释应紧跟在函数定义后面,并采用文档字符串格式

  3. 给形参指定认值时,等号两边不要有空格

    def function_name(parameter_0, parameter_1='default value')
  4. 对于函数调用中的关键字实参等号两边不要有空格

    function_name(value_0, parameter_1='value')
  5. 如果形参很多,导致函数定义的长度超过了79字符,可在函数定义中输入左括号后按回车键,并在下一行按两次Tab键,从而将形参列表和只缩进一层的函数体区分开来

    def function_name(
    		parameter_0, parameter_1, parameter_2,
    		parameter_3, parameter_4, parameter_5):
        function body...
  6. 如果程序或模块包含多个函数,可使用两个空行将相邻的函数分开,这样更容易知道前一个函数在什么地方结束,下一个函数从什么地方开始。


高阶函数

  • range() 还可指定步长

  • map()

    def func(x):
        return x*x
    
    list(map(func, [1, 2, 3, 4, 5]))
    # 效果等价于 [i**2 for i in range(1, 6)]
    
    
    a = [1, 2, 3, 4, 5]
    list(map(str, map(func, a)))
    # 结果为 ['1', '4', '9', '16', '25']

匿名函数

使用lambda

lambda x:x*x

输入为x,输出x*x

# 避免显式构造函数func,简约
list(map(lambda x:x*x, [1, 2, 3, 4, 5]))

list(map(lambda x:'char is:'+str(x), [1, 2, 3, 4, 5]))
# 结果为 ['char is:1', 'char is:2', 'char is:3' ...]

第三方包

  • collections
import collections
a = [1, 2, 3, 1, 2, 31, 2, 1]
print(collections.Counter(a))

# 输出:Counter({1: 3, 2: 3, 3: 1, 31: 1})
  • csv
  • datetime
  • math
  • pandas
  • numpy

创建和使用类

创建 Dog 类

class Dog():
    """一次模拟小狗的简单尝试"""
    def __init__(self, name, age):
        """初始化属性name和age"""
        self.name = name
        self.age = age
        
    def sit(self):
        """模拟小狗被命令蹲下"""
        print(self.name.title() + " is now sitting.")
        
    def roll_over(self):
        """模拟小狗被命令时打滚"""
        print(self.name.title() + " rolled over!")
  • 根据约定,Python中首字母大写的名称指的是。这个类定义中的括号是空的,因为我们要从空白创建这个类
  1. 方法__init__()

    • 类中的函数称为方法。就目前而言,函数和方法唯一重要的差别是调用方法的方式

    • 上例中的方法__init__()是一个特殊的方法,每当根据Dog类创建新实例时,Python都会自动运行它

    • 在这个方法名称中,开头和末尾各有两个下划线这是一种约定,旨在避免Python默认方法与普通方法发生名称冲突

    • 这个方法的定义中,形参self必不可少,还必须位于其他形参的前面

      为何必须在方法定义中包含形参self呢?因为Python调用这个__init__()方法将自动传入实参self每个与类相关联的方法调用都自动传递实参self,它是一个指向实例本身的引用让实例能够访问类中的属性和方法

      我们创建Dog实例时,Python将调用Dog类的方法__init__()。我们将通过实参向Dog()传递name和age,self会自动传递

    • self为前缀的变量都可供类中的所有方法使用,我们还可以通过类的任何实例来访问这些变量

      self.name = name获取存储在形参name中的值,并将其存储到变量name中,然后该变量被关联到当前创建的实例

      像这样可以通过实例访问的变量称为属性

    • sit()roll_over()方法不需要额外的信息,因此它们只有一个形参self

  2. 在 Python 2.7 中创建类

    在 Python 2.7 中创建类时,需要做细微的修改——在括号内包含单词object:

    class ClassName(object):

根据类创建实例

my_dog = Dog('willie', 6)

遇到上述代码时,Python使用实参willie和6调用Dog类中的方法__init__()。方法__init__()并未显式地包含return语句,但Python自动返回一个表示这条小狗的实例。在这里,命名约定很有用:我们通常可以认为首字母大写的名称指的是小写的名称指的是根据类创建的实例

  1. 访问属性

    my_dog.name,在Dog类中引用这个属性使用的是self.name

  2. 调用方法

    my_dog.sit()
    my_dog.roll_over()

使用类和实例

Car 类

class Car():
    """一次模拟汽车的简单尝试"""
    
    def __init__(self, make, model, year):
        """初始化描述汽车的属性"""
        self.make = make
        self.model = model
        self.year = year
        
    def get_descriptive_name(self):
        """返回整洁的描述性信息"""
        long_name = str(self.year) + ' ' + self.make + ' ' + self.model
        return long_name.title()
    
my_new_car = Car('audi', 'a4', 2016)
print(my_new_car.get_descriptive_name())

运行结果:

2016 Audi A4

给属性指定默认值

class Car():
    
    def __init__(self, make, model, year):
        """初始化描述汽车的属性"""
        self.make = make
        self.model = model
        self.year = year
        self.odometer_reading = 0
        
    def get_descriptive_name(self):
        --snip--
        
    def read_odometer(self):
        """打印一条指出汽车里程的消息"""
        print("This car has " + str(self.odometer_reading) + " miles on it.")
    
my_new_car = Car('audi', 'a4', 2016)
print(my_new_car.get_descriptive_name())
my_new_car.read_odometer()

修改属性的值

  1. 直接修改属性的值

    my_new_car.odometer_reading = 23
  2. 通过方法修改属性的值

    class Car():
        --snip--
        
        def update_odometer(self, mileage):
            """将里程表读数设置为指定的值"""
            self.odometer_reading = mileage
        
    my_new_car = Car('audi', 'a4', 2016)
    print(my_new_car.get_descriptive_name())
    
    my_new_car.update_odometer(23)
    my_new_car.read_odometer()

    可对方法update_odometer()进行扩展,禁止任何人将里程表读数往回调

    class Car():
        --snip--
        
        def update_odometer(self, mileage):
            """
            将里程表读数设置为指定的值
            禁止将里程表读数往回调
            """
            if mileage >= self.odometer_reading:
                self.odometer_reading = mileage
            else:
            	print("You can't roll back an odometer!")
  3. 通过方法对属性的值进行递增

    class Car():
        --snip--
        
        def update_odometer(self, mileage):
            --snip--
        
        def increment_odometer(self, miles):
            """将里程表读数增加指定的量"""
            self.odometer_reading+= miles

继承

一个类继承另一个类时,它将自动获得另一个类的所有属性和方法。原有的类称为父类,新类称为子类。子类同时还可以定义自己的属性和方法

子类的方法__init__()

创建子类的实例时,Python首先需要给父类的所有属性赋值,为此,子类的方法__init__()需要父类施以援手

下面来创建一个简单的ElectricCar类版本,它具备Car类的所有功能

class ElectricCar(Car):
    """电动汽车的独特之处"""
    
    def __init__(self, make, model, year):
        """初始化父类的属性"""
        super().__init__(make, model, year)
        
my_tesla = ElectricCar('tesla', 'model s', 2016)
print(my_tesla.get_descriptive_name())
  • 创建子类时,父类必须包含在当前文件中,且位于子类前面
  • 定义子类时,必须在括号内指定父类的名称
  • super()是一个特殊函数,帮助Python将父类和子类关联起来父类也称为超类(superclass),名称super因此而得名。

Python 2.7 中的继承

在Python 2.7 中,继承语法稍有不同。

# 在 Python 2.7 中创建类时,需要在括号内包含单词object
class Car(object):
    def __init__(self, make, model, year):
        --snip--
        
class ElectricCar(Car):
    def __init__(self, make, model, year):
        super(ElectricCar, self).__init__(make, model, year)
  • 函数super()需要两个实参:子类名和对象self。

给子类定义属性和方法

class ElectricCar(Car):
    """电动汽车的独特之处"""
    
    def __init__(self, make, model, year):
        """
        电动汽车的独特之处
        初始化父类的属性,再初始化电动汽车特有的属性
        """
        super().__init__(make, model, year)
        self.battery_size = 70
        
    def describe_battery(self):
        """打印一条描述电瓶容量的消息"""
        print("This car has a " + str(self.battery_size) + "-kwh battery.")
        
my_tesla = ElectricCar('tesla', 'model s', 2016)
my_tesla.describe_battery()

重写父类的方法

对于父类的方法,只要它不符合子类模拟的实物的行为都可对其进行重写。为此,可在子类中定义一个与要重写的父类方法同名的方法

假设Car类有一个名为fill_gas_tank()的方法,它对全电动汽车来说毫无意义。下面演示一种重写方式:

class ElectricCar(Car):
    --snip--
    
    def fill_gas_tank(self):
        """电动汽车没有油箱"""
        print("This car doesn't need a gas tank!")

使用继承时,可让子类保留从父类继承而来的精华,并剔除不需要的糟粕。


将实例用作属性

使用代码模拟实物时,可能会发现给类添加的细节越来越多:属性方法清单以及文件越来越长。这种情况下,可能需要将类的一部分作为一个独立的类提取出来,将大型类拆分称多个协同工作的小类。

例如,不断给ElectricCar类添加细节时,我们可能会发现其中包含很多专门针对汽车电瓶的属性和方法。可以将这些属性和方法提取出来,放到另一个名为Battery的类中,并将一个Battery实例用作ElectricCar类的一个属性

class Car():
    --snip--
    
class Battery():
    """一次模拟电动汽车电瓶的简单尝试"""
    
    def __init__(self, battery_size=70):
        """初始化电瓶的属性"""
        self.battery_size = battery_size
        
    def describe_battery(self):
        """打印一条描述电瓶容量的消息"""
        print("This car has a " + str(self.battery_size) + "-kwh battery.")
        
class ElectricCar(Car):
    """电动汽车的独特之处"""
    
    def __init__(self, make, model, year):
        """
        初始化父类的属性,再初始化电动汽车特有的属性
        """
        super().__init__(make, model, year)
        self.battery = Battery()
        
my_tesla = ElectricCar('tesla', 'model s', 2016)
my_tesla.battery.describe_battery()

这看似做了很多额外的工作,但现在我们想多详细地描述电瓶都可以,且不会导致ElectricCar类混乱不堪


导入类

Python允许将类存储在模块中,然后在主程序中导入所需的模块(模块是扩展名为.py的文件包含要导入到程序中的代码)。

导入单个类

下面是模块car.py,其中只包含Car类的代码:

"""一个可用于表示汽车的类"""

class Car():
    """一次模仿汽车的简单尝试"""
    
    def __init__(self, make, model, year):
        """初始化描述汽车的属性"""
        self.make = make
        self.model = model
        self.year = year
        self.odometer_reading = 0
        
    def get_descriptive_name(self):
        """返回整洁的描述性名称"""
        long_name = str(self.year) + ' ' + self.make + ' ' + self.model
        return long_name.title()
    
    def read_odometer(self):
        """打印一条消息,指出汽车的里程"""
        print("This car has " + str(self.odometer_reading) + " miles on it.")
        
    def update_odometer(self. mileage):
        """
        将里程表读数设置为指定的值
        拒绝将历程表往回拨
        """
        if mileage >= self.odometer_reading:
            self.odometer_reading = mileage
        else:
            print("You can't roll back an odometer!")
            
    def increment_odometer(self, miles):
        """将里程表读数增加指定的量"""
        self.odometer_reading += miles

下面创建另一个文件——my_car.py,在其中导入Car类并创建其实例

from car import Car

my_new_car = Car('audi', 'a4', 2016)
print(my_new_car.get_descriptive_name())

my_new_car.odometer_reading = 23
my_new_car.reading_odometer()

导入类是一种有效的编程方式,让大部分逻辑存储在独立的文件中使主程序文件变得整洁而易于阅读


在一个模块中存储多个类

虽然同一个模块中的类之间应存在某种相关性,但可根据需要在一个模块中存储任意数量的类。

类Battery和ElectricCar都可以帮助模拟汽车,因此可以将其加入模块car.py中。


从一个模块中导入多个类

from car import Car, ElectricCar
  • 从一个模块中导入多个类时,用逗号分隔各个类

导入整个模块

可以导入整个模块,再使用句点表示法访问需要的类。这中导入方法很简单,代码也易于阅读。由于创建类实例的代码都包含模块名,因此不会与当前文件使用的任何名称发生冲突

import car

my_beetle = car.Car('volkswagen', 'beetle', 2016)

my_tesla = car.ElectricCar('tesla', 'roadster', 2016)

导入模块中的所有类

要导入模块中的每个类,可使用下面的语法:

from module_name import *

但是不推荐这种导入方式(同导入模块中的所有元素),原因有二:

  1. 这种导入方式没有明确地指出你使用了模块中的哪些类
  2. 还可能引发名称方面的困惑。如果不小心导入了一个与程序文件中其他东西同名的类,将引发难以诊断的错误

需要从一个模块中导入很多类时,最好导入整个模块,并module_name.class_name语法来访问类


在一个模块中导入另一个模块

有时候,需要将类分散到多个模块中,以免模块太大,或在同一个模块中存储不相关的类。将类存储在多个模块中时,你可能会发现一个模块中的类依赖于另一个模块中的类。这种情况下,可在前一个模块中导入必要的类。

例如,下面将Car类存储在一个模块中,并将ElectricCar和Battery类存储再另一个模块中。我们将第二个模块命名为electric_car.py:

"""一组可用于表示电动汽车的类"""

from car import Car

class Battery():
    --snip--
    
class ElectricCar(Car):
    --snip--

现在可以分别从每个模块中导入类,以根据需要创建任何类型的汽车了:

from car import Car
from electric_car import ElectricCar

my_beetle = Car('volkswagen', 'beetle', 2016)
print(my_beetle.get_descriptive_name())

my_tesla = ElectricCar('tesla', 'roadster', 2016)
print(my_tesla.get_descriptive_name())

Python 标准库

Python标准库是一组模块,安装好的Python都包含它。可使用标准库中的任何函数和类,为此只需在程序开头包含一条简单的import语句

下面来看模块collection中的一个类——OrderedDict。要创建字典并记录其中的键-值对的添加顺序,即可使用模块collections中的OrderedDict类。再来看一看第6章的favorite_languages.py示例:

from collections import OrderedDict

favorite_languages = OrderedDict()

favorite_languages['jen'] = 'python'
favorite_languages['sarah'] = 'c'
favorite_languages['edward'] = 'ruby'
favorite_languages['phil'] = 'python'

for name, language in favorite_languages.items():
    print(name.title() + "'s favorite language is " +
         language.title() + ".")

这是一个很不错的类,它兼具列表和字典的主要优点(在将信息关联起来的同时保留原来的顺序)。

模块random

模块random包含以各种方式生成随机数的函数,其中的randint()返回一个位于指定范围内的整数

例如,下面的代码返回一个1~6内的整数:

from random import randint
x = randint(1, 6)

类编码风格

  • 类名:应采用驼峰命名法
  • 实例名模块名:应采用小写格式,并在单词之间加上下划线。
  • 中,可使用一个空行分隔方法;在模块中,可使用两个空行分隔类
  • 需要同时导入标准库中的模块和自己编写的模块时,先编写导入标准库模块的import语句,再添加一个空行,然后编写导入自己编写的模块的import语句。这种做法让人更容易明白程序使用的各个模块来自何方

文件和异常

从文件中读取数据

文本文件可存储的数据量多的难以置信,每当需要分析或修改存储在文件中的信息时,读取文件都很有用,对数据分析应用程序来说尤其如此。例如可以编写一个这样的程序:读取一个文本文件的内容,重新设置这些数据的格式并将其写入文件,让浏览器能够显示这些内容

要使用文本文件中的信息,首先需要将信息读取到内存中。为此,可以一次性读取文件的全部内容,也可以每次一行逐步读取

读取整个文件

首先创建一个文件,它包含精确到小数点后30位的圆周率值,且在小数点后每10位处都换行

3.1415926535
  8979323846
  2643383279

将上述文件保存为pi_digits.txt保存到本章程序所在的目录中

下面的程序打开并读取这个文件,再将其内容显示到屏幕上

with open('pi_digits.txt') as file_object:
    contents = file_object.read()
    print(contents)

再这个程序中,第一行代码做了大量的工作

  • 函数open()

    • 接受一个参数——要打开的文件的名称
    • Python在当前执行的文件所在的目录中查找指定的文件
    • 返回一个表示文件的对象,Python将这个对象存储在我们将在后面使用的变量中。
  • 关键字with不需要访问文件后将其关闭

    • 也可以调用open()close()来打开和关闭文件,但这样做时,如果程序存在bug导致close()语句未执行,文件将不会关闭

      如果在程序中过早调用close(),你会发现需要使用文件时它已关闭(无法访问),这会导致更多的错误

    • 并非在任何情况下都能轻松确定关闭文件的恰当时机,但通过关键字with,可以让Python确定合适的时机自动关闭文件

  • 有了表示文件的对象后,使用方法read()读取这个文件的全部内容作为一个字符串

    • read()到达文件末尾时返回一个空字符串,这个空字符串显示出来就是一个空行
    • 删除末尾的空行,可在print语句中使用rstrip()print(contents.rstrip())

文件路径

Python默认在当前执行的文件所在的目录中查找指定的文件,但有时可能要打开不在程序文件所属目录中的文件。要让Python打开不与程序文件位于同一个目录中的文件,需要提供文件路径

  • 相对文件路径:

    相对于当前运行的程序所在目录的路径。

    • 在 Linux 和 OS X 中,可以这样编写代码:

      with open('text_files/filename.txt') as file_object:

      这行代码让Python到当前文件夹下的text_files文件夹中寻找指定的.txt文件。

    • 在 Windows 系统中,在文件路径中使用反斜杠(\):

      with open('text_files\filename.txt') as file_object:

  • 绝对文件路径:

    将文件在计算机中的准确位置告诉Python。

    绝对路径通常比相对路径更长,因此将其存储在一个变量中,再将该变量传递给open()会有所帮助。

    • 在 Linux 和 OS X 中,可以这样编写代码:

      file_path = '/home/ehmatthes/other_files/text_files/filename.txt'
      with open(file_path) as file_object:
    • 在 Windows 系统中,它们类似于下面这样:

      file_path = 'C:\Ysers\ehmatthes\other_files\text_files\filename.txt'
      with open(file_path) as file_object:

    注意:

    • Windows系统有时能够正确解读文件路径中的斜杠。如果使用Windows系统,且结果不符合预期,请确保在文件路径中使用的是反斜杠
    • 反斜杠在Python中被视为转义标记,为在Windows中确保万无一失,应以原始字符串的方式指定路径,即在开头的单引号前加上r(以r开头,那么说明后面的字符,都是普通的字符了,即如果是\n将表示一个反斜杠字符,一个字母n,而不是表示换行了)。

逐行读取

读取文件时,常常需要检查其中的每一行:你可能要在文件中查找特定的信息,或者要以某种方式修改文件中的文本。例如,你可能要遍历一个包含天气数据的文件,并使用天气描述中包含字样sunny的行;在新闻报道中,你可能会查找包含标签<headline>的行,并按特定的格式设置它。

要以每次一行的方式检查文件,可对文件对象使用for循环

filename = 'pi_digits.txt'

with open(filename) as file_object:
    for line in file_object:
        print(line)

我们打印每一行时,发现空白行更多了:

3.1415926535

  8979323846
  
  2643383279

为什么会出现这些空白行呢?因为在这个文件中每行的末尾都有一个看不见的换行符,而print语句也会加上一个换行符。要消除这些多余的空白行,可在print语句中使用rstrip()print(line.rstrip())


创建一个包含文件各行内容的列表

使用关键字with时,open()返回的文件对象只在with代码块内可用。如果要在with代码块外访问文件的内容,可在with代码块内将文件的各行存储在一个列表中,并在with代码块外使用该列表:

filename = 'pi_digits.txt'

with open(filename) as file_object:
    lines = file_object.readlines()
    
for line in lines:
    print(line.rstrip())
  • 方法readlines()从文件中读取每一行,并将其存储在一个列表中

使用文件的内容

首先创建一个字符串,它包含文件中存储的所有数字,且没有任何空格

filename = 'pi_digits.txt'

with open(filename) as file_object:
    lines = file_object.readlines()
    
pi_string = ''
for line in lines:
    pi_string += line.rstrip()
    
print(pi_string)
print(len(pi_string))

打印结果:

3.1415926535  8979323846  2643383279
36

在变量pi_string存储的字符串中,包含原来位于左边的空格,为删除这些空格,**可使用strip()**而不是rstrip()

注意:

读取文本文件时,Python将其中的文本都解读为字符串。如果读取的是数字,并要将其作为数值使用,就必须使用函数int()float()转换为数字。


包含小数点后一百万位的大型文件

只要系统内存足够多,想处理多少数据都可以。


圆周率值中包含你的生日吗

为确认某个人的生日是否包含在圆周率值得前1 000 000位中,可将生日表示为一个由数字组成得字符串,再检查这个字符串是否包含在pi_string中:

filename = 'pi_digits.txt'

with open(filename) as file_object:
    lines = file_object.readlines()
    
pi_string = ''
for line in lines:
    pi_string += line.strip()
    
birthday = input("Enter your birthday, in thje form mmddyy: ")
if birthday in pi_string:
    print("Your birthday appears in the first million digits of pi!")
else:
    print("Your birthday does not appear in the first million digits of pi.")

写入文件

保存数据最简单的方式之一是将其写入到文件中

写入空文件

要将文本写入文件,在调用open()时需要提供另一个实参,告诉Python要写入打开的文件

filename = 'programming.txt'

with open(filename, 'w') as file_object:
    file_object.write("I love programming.")
  • 实参'w'告诉Python,我们要以写入模式打开这个文件。

  • 打开文件时,可指定模式

    • 读取模式(‘r’
    • 写入模式(‘w’
    • 附加模式(‘a’)
    • 读写模式(‘r+’

    如果省略了模式实参,默认以只读模式打开文件。

  • 如果要写入的文件不存在,函数open()自动创建它。然而,以写入(‘w’)模式打开文件时千万要小心,因为如果指定的文件已经存在,Python将在返回文件对象前清空该文件

  • 文件对象的方法write()将一个字符串写入文件

  • Python只能将字符串写入文本文件,要将数值数据存储到文本文件中,必须先使用函数str()将其转换为字符串格式。


写入多行

函数write()不会在写入的文本末尾添加换行符,要让每个字符串都单独占一行,需要在write()语句中包含换行符。


附加到文件

如果要给文件添加内容,而不是覆盖原有内容,可以**附加模式(‘a’)**打开文件。如果指定的文件不存在,Python会创建一个空文件。

filename = 'programming.txt'

with open(filename, 'a') as file_object:
    file_object.write("I also love finding meaning in large datasets.\n")
    file_object.write("I love creating apps that can run in a browser.\n")

异常

Python使用被称为异常的特殊对象管理程序执行期间发生的错误。每当发生让Python不知所措的错误时,它都会创建一个异常对象。如果编写了处理该异常的代码,程序将继续运行;如果未对异常进行处理,程序将停止,并显示一个traceback,其中包含有关异常的报告

异常是使用try-except代码块处理的。try-except代码块让Python执行指定的操作同时告诉Python发生异常时怎么办。使用了try-except代码块时,即便出现异常,程序也将继续运行:显示编写的友好的错误消息,而不是令用户迷惑的traceback

  • ZeroDivisionError 异常

    ZeroDivisionError就是一个异常对象

  • ValueError 异常

    尝试将非数字文本转换为数字时,将引发ValueError

  • FileNotFoundError 异常


使用 try-except 代码块

当你认为可能发生了错误时,可编写一个try-except代码块来处理可能引发的异常。

处理ZeroDivisionError异常的try-except代码块类似于下面这样:

try:
    print(5/0)
except ZeroDivisionError:
    print("You can't divide by zero!")

使用异常避免崩溃

发生错误时,如果程序还有工作没有完成妥善地处理错误就尤其重要。这种情况经常会出现在要求用户提供输入的程序中;如果程序能够妥善地处理无效输入就能再提示用户提供有效输入,而不至于崩溃


else 代码块

将可能引发错误地代码放在try-except代码块中,可提高这个程序抵御错误的能力。依赖于try代码块成功执行的代码都应放到else代码块中:

try:
    answer = int(first_number) / int(second_number)
except ZeroDivisionError:
    print("You can't divide by 0!")
else:
    print(answer)

处理 FileNotFoundError 异常

filename = 'alice.txt'

try:
    with open(filename) as f_obj:
        contents = f_obj.read()
except FileNotFoundError:
    msg = "Sorry, the file " + filename + " does not exist."
    print(msg)

如果文件不存在,这个程序什么都不做,因此错误处理代码的意义不大。


分析文本

下面来提取童话Alice in Wonderland的文本,并尝试计算它包含多少个单词

我们将使用方法split(),它根据一个字符串创建一个单词列表。方法split()以空格为分隔符将字符串分拆成多个部分,并将这些部分都存储在一个列表中

filename = 'alice.txt'

try:
    with open(filename) as f_obj:
        contents = f_obj.read()
except FileNotFoundError:
    msg = "Sorry, the file " + filename + " does not exist."
    print(msg)
else:
    # 计算文件大致包含多少个单词
    words = contents.split()
    num_words = len(words)
    print("The file " + filename + " has about " + str(num_words) + " words.")

使用多个文件

下面多分析几本书。我们先将这个程序的大部分代码移到一个名为count_words()的函数中,这样对多本书进行分析时将更容易:

def count_words(filename):
    """计算一个文件大致包含多少个单词"""
    try:
    	with open(filename) as f_obj:
        	contents = f_obj.read()
	except FileNotFoundError:
        msg = "Sorry, the file " + filename + " does not exist."
        print(msg)
    else:
        # 计算文件大致包含多少个单词
        words = contents.split()
        num_words = len(words)
        print("The file " + filename + " has about " + str(num_words) + " words.")
filename = 'alice.txt'
count_words(filename)

失败时一声不吭

要让程序在失败时一声不吭,可通过pass语句,在except代码块中明确表明什么都不做

def count_words(filename):
    """计算一个文件大致包含多少个单词"""
    try:
        --snip--

	except FileNotFoundError:
        pass
    else:
        --snip--

pass语句还充当了占位符。它提醒你在程序的某个地方什么都没有做,并且以后也许要在这里做些什么。在这个程序中,我们可能决定将找不到的文件的名称写入到文件missing_files.txt中。


使用 模块json 存储数据

很多程序要求用户输入某种信息,如让用户存储游戏首选项提供可视化的数据。不管专注的是什么,程序都把用户提供的信息存储在列表和字典等数据结构中。用户关闭程序时,几乎总是要保存他们提供的信息,一种简单的方式是使用模块json来存储数据

  • 模块json能将简单的Python数据结构转储到文件中并在程序再次运行时加载该文件中的数据
  • 还可以使用json在Python程序之间分享数据
  • JSON数据格式不是Python专用,因此能够将以JSON格式储的数据与使用其他编程语言的人分享
  • JSON是一种轻便格式,很有用,也易于学习
  • **JSON(JavaScript Object Notation)**格式最初是为JavaScript开发的,但随后成了一种常见格式,被众多语言采用

我们来编写程序,使用json.dump()存储一组数字,使用json.load()将这些数字读取到内存中

使用 json.dump()

  • 函数json.dump()接受两个实参:
    1. 要存储的数据
    2. 可用于存储数据的文件对象
import json

numbers = [2, 3, 5, 7, 11, 13]

filename = 'numbers.json'
with open(filename, 'w') as f_obj:
    json.dump(numbers, f_obj)
  • 先导入模块json,再创建一个数字列表
  • 通常使用文件扩展名.json指出文件存储的数据为JSON格式
  • 使用函数json.dump()将数字列表存储到文件numbers.json中

使用 json.load()

import json

filename = 'numbers.json'
with open(filename) as f_obj:
    numbers = json.load(f_obj)
    
print(numbers)

保存和读取用户生成的数据

来看这样一个例子:用户首次运行程序时被提示输入自己的名字,这样再次运行程序时就记住他了

  • 先存储用户的名字:

    import json
    
    username = input("What is your name? ")
    
    filename = 'username.json'
    with open(filename, 'w') as f_obj:
        json.dump(username, f_obj)
        print("We'll remember you when you come back, " + username + "!")
  • 再编写一个程序,向其名字被存储的用户发出问候:

    import json
    
    filename = 'username.json'
    
    with open(filename) as f_obj:
        username = json.load(f_obj)
        print("Welcome back, " + username + "!")

我们需要将这两个程序合并到一个程序中。这个程序运行时,我们将尝试从文件username.json中获取用户名。因此首先编写一个尝试恢复用户名的try代码块。如果这个文件不存在,我们就在except代码块中提示用户输入用户名,并将其存储在username.json中,以便程序再次运行时能够获取它:

import json

# 如果以前存储了用户名,就加载它
# 否则,就提示用户输入用户名并存储它
filename = 'username.json'
try:
    with open(filename) as f_obj"
    username = json.load(f_obj)
except FileNotFoundError:
    username = input("What is your name? ")
    with open(filename, 'w') as f_obj:
        json.dump(username, f_obj)
        print("We'll remember you when you come back, " + username + "!")
else:
    print("Welcome back, " + username + "!")

重构

你经常会遇到这样的情况:代码能够正确地运行,但可做进一步的改进——将代码划分为一系列完成具体工作的函数。这样的过程被称为重构重构让代码更清晰、更易于理解、更容易扩展

要重构上述程序,可将大部分逻辑放到一个或多个函数中。

import json

def greet_user():
    """问候用户,并指出其名字"""
    filename = 'username.json'
    try:
        with open(filename) as f_obj:
            username = json.load(f_obj)
    except FileNotFoundError:
        username = input("What is your name? ")
        with open(filename, 'w') as f_obj:
            json.dump(username, f_obj)
            print("We'll remember you when you come back" + username + "!")
    else:
        print("Welcome back, " + username + "!")
        
greet_user()

下面来重构greet_user(),让它不执行这么多任务:

import json

def get_stored_username():
    """如果存储了用户名,就获取它"""
    filename = 'username.json'
    try:
        with open(filename) as f_obj:
            username = json.load(f_obj)
    except FileNotFoundError:
        return None
    else:
        return username
    
def get_new_username():
    """提示用户输入用户名"""
    username = input("What is your name? ")
    filename = 'username.json'
    with open(filename. 'w') as f_obj:
        json.dump(username, f_obj)
    
def greet_user():
    """问候用户,并指出其名字"""
    username = get_stored_username()
    if username:
        print("Welcom back, " + username + "!")
    else:
        username = get_new_username()
        print("We'll remember you when you come back" + username + "!")

greet_user()

在这个版本中,每个函数都执行单一而清晰的任务


测试代码

测试函数

下面是一个简单的函数,它接受名和姓并返回整洁的姓名:

def get_formatted_name(first, last):
    """生成整洁的姓名"""
    full_name = first + ' ' + last
    return full_name.title()

为核实函数像期望的那样工作,来编写一个使用这个函数的程序:

from name_function import get_formatted_name

print("Enter 'q' at any time to quit.")
while True:
    first = input("\nPlease give me a forst name: ")
    if first == 'q':
	    break
    last = input("Please give me a last time: ")
    if last == 'q':
        break
        
    formatted_name = get_formatted_name(first, last)
    print("\tNeatly formatted name: " + formatted_name + '.')

现在假设我们要修改get_formatted_name(),使其还能处理中间名。这样做时,我们要确保不破坏这个函数处理只有名和姓的姓名的方式。为此,我们可以在每次修改get_formatted_name()后都进行测试:运行程序names.py,并输入像Janis Joplin这样的姓名,但这太繁琐了。所幸Python提供了一种自动测试函数输出的高效方式。

单元测试和测试用例

Python标准库中的模块unittest提供了代码测试工具

  • 单元测试:用于核实函数的某个方面没有问题
  • 测试用例:是一组单元测试,这些单元测试一起核实函数在各种情形下的行为都符合要求。

良好的测试用例考虑到了函数可能收到的各种输入,包含针对所有这些情形的测试。全覆盖式测试用例包含一整套单元测试,涵盖了各种可能的函数使用方式。对于大型项目,要实现全覆盖很难。通常,最初只要针对代码的重要行为编写测试即可,等项目被广泛使用时再考虑全覆盖


可通过的测试

创建测试用例的语法需要一段时间才能习惯,但测试用例创建后,再添加针对函数的单元测试就很简单了。要为函数编写测试用例,可先导入模块unittest以及要测试的函数,再创建一个继承unittest.TestCase的类,并编写一系列方法对函数行为的不同方面进行测试。

下面是一个只包含一个方法的测试用例,它检查函数get_formatted_name()在给定名和姓时能否正确地工作:

import unittest
from name_function import get_formatted_name

class NamesTestCase(unittest.TestCase):
    """测试name_function.py"""
    
    def test_first_last_name(self):
        """能够正确地处理像Janis Joplin 这样的姓名吗? """
        formatted_name = get_formatted_name('janis', 'joplin')
        self.assertEqual(formatted_name, 'Janis Joplin')
        
unittest.main()
  • 代码行unittest.main()让Python运行这个文件中的测试

    .
    ---------------------------------------------------------
    Ran 1 test in 0.000s
    
    OK
    • 第一行的句点.表明有一个测试通过了
    • 最后的OK表明该测试用例中的所有单元测试都通过了
  • 测试类的命名最好让它看起来与要测试的函数相关,并包含字样Test。这个类必须继承unittest.TestCase类这样Python才知道如何运行你编写的测试

  • 我们运行上述程序时,所有以test_打头的方法都会自动运行

  • unittest最有用的功能之一:一个断言方法。

    断言方法用来核实得到的结果是否与期望的结果一致(应该满足的条件是否确实满足)。上述代码通过调用unittest的方法assertEqual(),并向它传递formatted_name'Janis Joplin'


不能通过的测试

测试未通过时结果是什么样的呢?我们来修改get_formatted_name(),使其能够处理中间名,但这样做时,故意让这个函数无法正确地处理像Janis Joplin这样只有名和姓的姓名。

下面是函数get_formatted_name()的新版本,它要求通过一个实参指定中间名

def get_formatted_name(first, middle, last):
    """生成整洁的姓名"""
    full_name = first + ' ' + middle + ' ' + last
    return full_name.title()

这次运行测试代码,将会得到如下输出:

E
=======================================================
ERROR: test_first_last_name (__main__.NamesTestCase)
------------------------------------------------------
...
...
...
------------------------------------------------------
Ran 1 test in 0.000s

FAILED (errors=1)
  • 第一行字母E指出测试用例中有一个单元测试导致了错误
  • 最后一行指出整个测试用例都未通过,因为运行该测试用例时发生了一个错误

添加新测试

我们再编写一个测试,用于测试包含中间名的姓名。为此,在NamesTestCase类中再添加一个方法:

import unittest
from name_function import get_formatted_name

class NamesTestCase(unittest.TestCase):
    """测试name_function.py"""
    
    def test_first_last_name(self):
        """能够正确地处理像Janis Joplin 这样的姓名吗? """
        formatted_name = get_formatted_name('janis', 'joplin')
        self.assertEqual(formatted_name, 'Janis Joplin')
        
    def test_first_last_middle_name(self):
        """能够正确地处理像Wolfgang Amadeus Mozart这样的姓名吗? """
        formatted_name = get_formatted_name(
        	'wolfgang', 'mozart', 'amadeus')
        self.assertEqual(formatted_name, 'Wolfgang Amadeus Mozart')
        
unittest.main()
  • 测试方法名必须以test_打头,这样它才会在我们运行test_name_function.py时自动运行。
  • 可以在TestCase类中使用很长的方法名,这些方法名必须是描述性的,这样才能让你明白测试未通过时的输出。

两个测试都通过的输出:

..
-------------------------------------------------
Ran 2 tests in 0.000s

OK

测试类

各种断言方法

Python在unittest.TestCase类中提供了很多断言方法

6个常用的断言方法:

方法 用途
assertEqual(a, b) 核实a == b
assertNotEqual(a, b) 核实a != b
assertTrue(x) 核实x为True
assertFalse(x) 核实x为False
assertIn(item, list) 核实item在list中
assertNotIn(item, list) 核实item不在list中

一个要测试的类

类的测试与函数的测试相似——所做的大部分工作都是测试类中方法的行为,但存在一些不同之处,下面来编写一个类进行测试。

来看一个帮助管理匿名调查的类:

class AnonymousSurvey():
    """收集匿名调查问卷的答案"""
    
    def __init__(self, question):
        """存储一个问题,并为存储答案做准备"""
        self.question = question
        self.responses = []
        
    def show_questinon(self):
        """显示调查问卷"""
        print(self.question)
        
    def store_response(self, new_response):
        """存储单份调查答卷"""
        self.responses.append(new_response)
        
    def show_results(self):
        """显示收集到的所有答卷"""
        print("Survey results:")
        for response in self.responses:
            print('- ' + response)

为证明AnonymousSurvey类能够正确地工作,我们来编写一个使用它地程序:

from survey import AnonymousSurvey

# 定义一个问题,并创建一个表示调查地AnonymousSurvey对象
question = "What language did you first learn to speak?"
my_survey = AnonymousSurvey(question)

# 显示问题并存储答案
my_survey。show_question()
print("Enter 'q' at any time to quit.\n")
while True:
    response = input("Language: ")
    if response == 'q':
        break
    my_survey.store_response(response)
    
# 显示调查结果
print("\nThank you to everyone who participated in the survey!")
my_survey.show_results()

AnonymousSurvey类可用于进行简单的匿名调查。假设我们将它放在了模块survey中,并想进行改进让每位用户都可输入多个答案;编写一个方法,它只列出不同的答案,并指出每个答案出现了多少次再编写一个类,用于管理非匿名调查

进行上述修改存在风险,可能会影响AnonymousSurvey类的当前行为。要确认在开发这个模块时没有破坏既有行为,可以编写针对这个类的测试。


测试 AnonymousSurvey 类

下面来编写一个测试,对AnonymouSurvey类的行为进行验证:如果用户面对调查问题时只提供了一个答案,这个答案也能被妥善地存储;用户提供三个答案时,也将被妥善地存储:

import unittest
from survey import AnonymousSurvey

class TestAnonymousSurvey(unittest.TestCase):
    """针对AnonymousSurvey类的测试"""
    
    def test_store_single_response(self):
        """测试单个答案会被妥善地存储"""
        question = "What language did you first learn to speak?"
        my_survey = AnonymousSurvey(question)
        my_survey.store_response('English')
        
        self.assertIn('English', my_survey.responses)
        
    def test_store_three_responses(self):
        """测试三个答案会被妥善地存储"""
        question = "What language did you first learn to speak?"
        my_survey = AnonymousSurvey(question)
        responses = ['English', 'Spanish', 'Mandarin']
        for response in responses:
            my_survey.store_response(response)
            
        for response in responses:
            self.assertIn(response, my_survey.responses)
        
unittest.main()

上述做法的效果很好,但这些测试有些重复的地方。下面使用unittest的另一项功能来提高它们的效率。


方法 setUp()

unittest.TestCase类中包含了方法setUp()让我们只需创建这些对象一次,并在每个测试方法中使用它们。如果在TestCase类章包含了方法setUp(),Python将先运行它,再运行各个以test_打头的方法。这样,在每个测试方法中都可使用在方法setUp()中创建的对象了

下面使用setUp()来创建一个调查对象和一组答案,供方法test_store_single_response()test_store_three_responses()使用:

import unittest
from survey import AnonymousSurvey

class TestAnonymousSurvey(unittest.TestCase):
    """针对AnonymousSurvey类的测试"""
    
    def setUp(self):
        """
        创建一个调查对象和一组答案,供使用的测试方法使用
        """
        question = "What language did you first learn to speak?"
        self.my_survey = AnonymousSurvey(question)
        self.responses = ['English', 'Spanish', 'Mandarin']
        
    def test_store_single_response(self):
        """测试单个答案会被妥善地存储"""
        self.my_survey.store_response(self.responses[0])
        self.assertIn(self.responses[0], self.my_survey.responses)
        
    def test_store_three_responses(self):
        """测试三个答案会被妥善地存储"""
        for response in self.responses:
            self.my_survey.store_response(response)
        for response in self.responses:
            self.assertIn(response, self.my_survey.responses)
        
unittest.main()

方法setUp()做了两件事:

  1. 创建一个调查对象
  2. 创建一个答案列表

存储这两样东西的变量名包含前缀self(即存储在属性中),因此可在这个类的任何地方使用

测试自己编写的类时,方法SetUp()让测试方法编写起来更容易:可setUp()方法中创建一系列实例并设置它们的属性,再在测试方法中直接使用这些实例

注意:

运行测试用例时,每完成一个单元测试,Python都打印一个字符测试通过时打印一个句点;测试引发错误时打印一个E;测试导致断言失败时打印一个F


Python项目

数据可视化

Numpy

Numpy是Python的一种开源的数值计算扩展。可以用来存储和处理大型矩阵,比Python自身的嵌套列表结构(nested list structure)高效得多。在实际工作中直接使用情况较少

阅读全文 »

快捷键

功能 快捷键
编辑单元格内容 【F2】
单元格内换行 Alt】+【Enter】
设置单元格格式 【Ctrl】+【1
Ctrl+E的众多效用
(拼接单元格内容、拆分提取单元格内容、
替换字符、去除空格和符号、自动换行…)
【Ctrl】+【 E】
筛选 【Ctrl】+【Shift】+【L】
输入当前日期 【Ctrl】+【;】
输入当前时间(不含日期) 【Ctrl】+【Shift】+【;】
切换sheet表 【Ctrl】+【PgUp/PgDn】
快速求和 【Alt】+【=】
数据透视表向导 【Alt+D】+【P】
隐藏
取消隐藏
选定目标区域
【Ctrl】 + 【9】
【Ctrl】 + 【Shift】 + 【(
隐藏
取消隐藏
选定目标区域,
【Ctrl】 + 【0】
【Ctrl】 + 【Shift】 +【)
展开或折叠单元格编辑栏 【Ctrl】+【Shift】+【U】
插入
删除
【Ctrl】+【Shift】+【+
【Ctrl】+【-】
设置千位分隔符,并四舍五入为整数 【Ctrl】+【Shift】+【!】
设置百分数形式 【Ctrl】+【Shift】+【%】
设置外边框 【Ctrl】+【Shift】+【&】

绝对引用行/列

使用$符号即可绝对引用


复制粘贴单元格

筛选的情况下

未被筛选的行不会被复制

隐藏的情况下

隐藏的行/列依然会被复制,想要不复制被隐藏的行/列,需要在选中指定区域后,使用【Alt】+【;】快捷键,再进行复制,即可顺利粘贴。


多个单元格中输入相同的数据

  1. 选中所有目标单元格
  2. 输入所需数据,按下【Ctrl】+【Enter】组合键即可。

多个单元格中有部分内容需要重复输入

如:邮箱后缀、电话区号、订单号前缀

希望达到效果:只需向单元格中输入不一样的内容部分,重复部分自动填充

操作:

  1. 选定需要设置的单元格范围,设置单元格格式(Ctrl + 1)

  2. 数字 - 分类 - 自定义 - 类型

  3. 输入框中填写需要的格式

    1. 添加邮箱共同后缀

      输入@"@163.com"

    2. 添加电话区号

      输入"0755-"@

    @用于在数字格式中包含文本,否则文本将不会显示出来


条件格式的设置


批量从身份证号中提取生日

编辑单元格:=TEXT(MID(身份证号所在单元格, 起始位数, 提取长度), "生日格式"(如0000-00-00))


筛选出重复值(唯一值)

  1. 选中需要筛选出重复值(唯一值)的范围
  2. 开始 - 样式 - 条件格式 - 突出显示单元格规则 - 重复值

去除重复值

  1. 选择需要去重的单元格区域
  2. 数据 - 数据工具 - 删除重复值

长数字输入

  • Excel单元格常规型数字的特殊机制
    1. 输入的数字**>11位时,自动采用科学计数法**
    2. 数字的精度15

最佳解决方式:

设置单元格格式(Ctrl + 1) - 数字 - 分类 - 文本


冻结窗口

  • 冻结指定的某行/列:选中需要冻结的行或列,选择视图 - 窗口 - 冻结窗格即可
  • 冻结指定的多行以及多列
    1. 视图 - 窗口 - 拆分,会显示一个十字型的拆分参考线
    2. 移动拆分参考线至所需的行、列
    3. 视图 - 窗口 - 冻结窗口

粘贴

粘贴值

文件 - 选项 - 快速访问工具栏 - 从下列位置选择命令 - 所有命令 - 粘贴值 - 添加至右侧,之后就可通过【Alt】+ 【提示的另一个键】即可实现快捷键操作。


选中整行/整列 数据

  • 选中整行数据:选定起始单元格Ctrl + Shift + →
  • 选中整列数据:选定起始单元格Ctrl + Shift + ↓

数据透视表

数据透视表(Pivot Table) 是一种交互式的表,可以进行某些计算,如求和与计数等,所进行的计算与数据跟数据透视表中的排列有关。

之所以称为数据透视表,是因为可以动态地改变它们的版面布置以便按照不同方式分析数据,也可以重新安排行号、列标和页字段。每一次改变版面布置时,数据透视表会立即按照新的布置重新计算数据。另外,如果原始数据发生更改,则可以更新数据透视表

  1. 选择需要透视的表格区域
  2. 插入 - 表格 - 数据透视表

函数

VLOOKUP函数

查找,最终返回查询序列中所对应的值。

与之对应的HLOOKUP是按行查找的。

  • 使用场景:
    1. 两张表格
    2. 两张表格中存在相同列
    3. 表2中存在表1不具备的字段,想把表2中的字段关联到表1中
  • 单元格中输入:=VLOOKUP(lookup_value,table_array,col_index_num,range_lookup)
    1. lookup_value:查找的值
    2. table_array:要查找的区域
    3. col_index_num:需要返回的元素在区域中的第几
    4. range_lookup:精确匹配/近似匹配
      • 1/TRUE近似匹配
      • 0/FALSE精确匹配

INDEX + MATCH 函数

  • 使用场景:

    功能与VLOOKUP函数基本相同,但是能弥补VLOOKUP函数的局限性(想要关联的列在相同列的左侧时,无法匹配)。

  • MATCH(lookup_value, lookup_array, [match_type])

    1. lookup_value:查找的值
    2. lookup_array:查找区域(只能1列宽)
    3. [match_type]:
      • 1:小于
      • 0:精确匹配
      • -1:大于

    结果返回查找区域中的所在行数

  • INDEX(array, row_num, [column_num])

    1. array:查找区域
    2. row_num:所在行数(通过MATCH函数获取)
    3. [column_num]:所在列数

AND 函数 / OR 函数

  • AND(logical1,[logical2],...)
  • OR(logical1,[logical2],...)

用于条件判断


IF 函数

IF(logical_test, [value_if_true], [value_if_false])

  1. logical_test:逻辑判断
  2. [value_if_true]:结果为true时的值(字符串使用双引号标注)
  3. [value_if_false]:结果为false时的值

例子:使用IF函数,判断业绩完成情况

单元格中输入:=IF(N4-M4>=0,"已完成", M4-N4)

IF 函数嵌套 示例

=IF(AND(O4="已完成",R4="已完成"),"已完成",IF(AND(O4="已完成",R4<>"已完成"),"仅业绩完成",IF(AND(O4<>"已完成",R4="已完成"),"仅入会完成","均未完成")))


COUNTIFS 函数

COUNTIFS(criteria_range1, criteria1,...)

  • 使用场景:

    对区域中符合条件的单元格进行筛选计数

  • 参数:

    • criteria_range1: 筛选区域

    • criteria1:筛选条件

    • criteria_range2


SUMIFS 函数

SUMIFS(sum_range, criteria_range1, criteria1,...)

  • 使用场景:

    对区域中符合条件的单元格进行筛选求和

  • 参数:

    • sum_range:求和区域

    • criteria_range1:筛选区域

    • criteria1:筛选条件

    • criteria_range2

    求和区域和筛选区域,类似VLOOKUP函数中两张表的感觉


LEFT、MID、RIGHT 函数

  • LEFT(text, [num_chars])
  • MID(text, start_num, num_chars)
  • RIGHT(text, [num_chars])
    • text:文本所在单元格
    • start_num:起始位置是第几个字符
    • num_chars:截取的字符长度

参考

数据分析中常用的9个Excel函数 - 简书

根据《算法笔记》一书,对PAT甲级、乙级真题和codeup部分试题进行分类。

1. C/C++快速入门

1.1 数组


1.2 指针


1.3 结构体的使用


2. 入门模拟

2.1 简单模拟

不涉及算法,只是根据题目描述来编写代码,考察代码能力。

题目 解题关键
codeup 问题 B: A+B \
B1001 害死人不偿命的(3n+1)猜想 \
B1010 一元多项式求导 \
B1011 A+B和C \
B1012 数字分类 有条不紊地整理
B1016 部分A+B \
B1018 锤子剪刀布 注意scanf留在缓冲区的换行符\n的处理
B1026 程序运行时间 \
B1032 挖掘机技术哪家强 统计各学校总分的方式
B1046 划拳 \
A1002 A+B for Polynomials 非零系数项个数的统计
A1009 Product of Polynomials 第二个多项式可边读边处理
A1042 Shuffling Machine 将扑克顺序号转为实际牌号的方式
A1046 Shortest Distance 便于计算距离的方式
A1065 A+B and C (64bit) B1011 A+B 和 C 进阶版
负数相加若溢出,可能得到0

2.2 查找元素

查找是学习写代码的一项基本功。

  • 一般来说,如果需要在一个比较小范围的数据集内内进行查找,直接遍历即可。
  • 如果需要查找的范围较大,可以用二分查找等算法进行更快速的查找
题目 解题关键
B1004 成绩排名 \
B1028 人口普查 1. 不合理年龄的判断方式
2. 需要考虑全不合理的情况
B1032 挖掘机技术哪家强 统计各学校总分的方式
B1041 考试座位号 \
A1011 World Cup Betting \
A1006 Sign In and Sign Out 方法类似 B1028 人口普查
A1036 Boys vs Girls \

2.3 图形输出

做法一般有两种:

  • 通过规律,直接进行输出
  • 定义一个二维字符数组,通过规律填充,然后输出整个二维数组
题目 解题关键
B1027 打印沙漏 沙漏高度和符号数量的关系
B1036 跟奥巴马一起编程 \
A1031 Hello World for U 根据 n1和n3为 $\leq$ n2,且满足 n1+n2+n3 = N+2 的最大值,求出n1,n2,n3

2.4 日期处理

需要处理好平年和闰年、大月和小月的问题,需要细心处理。

闰年的判断方法:

  1. 非整百年:能被4整除为闰年

  2. 整百年:能被400整除的是闰年(1900年不是闰年


2.5 进制转换

对一个P进制的数,如果要转换为Q进制,需要分两步:

  1. 将 P进制数x 转换为 十进制数y

    int y = 0, pro = 1;
    while(x != 0) {
        y += (x % 10) * pro;
        x /= 10;
        pro *= p;
    }
  2. 将 十进制数y 转换为 Q进制数z

    采用除基取余法

    int z[40], num = 0; //数组z 存放 Q进制数y 的每一位,num为位数
    do {
        z[num++] = y % Q; //除基取余
        y /= Q;
    } while(y != 0);

    使用do···while语句而不是while的原因是:如果十进制数y = 0,使用while语句将使循环直接跳出,导致结果出错

题目 解题关键
B1022 D进制的A+B 除基取余法
B1037 在霍格沃茨找零钱 \
A1019 General Palindromic Number \
A1027 Colors in Mars \
A1058 A+B in Hogwarts 题型同 乙级1037 在霍格沃茨找零钱
单位转换过程可能会超过int范围

2.6 字符串处理

考察代码能力的题型。一般需要仔细分析清楚题目中的输入和输出格式才能顺利AC。

有些题目中,可能实现逻辑非常麻烦,有很多细节边界情况,此类题目需要多做多想,积累经验

题目 解题关键
B1002 写出这个数 数字转为字符串
C语言:sprintf(str, "%d", num)
C++:to_string(num)
B1006 换个格式输出整数 \
B1009 说反话 句子颠倒,单词本身不颠倒
C++ 待更新
B1014 福尔摩斯的约会
A1061 Dating
正确归纳解码方式
B1021 个位数统计 \
B1024 科学计数法
A1073 Scientific Notation
1. 利用正则表达式,分开读取 数字部分 和 指数部分
2. 指数 < 0:整数部分必然为 0
3. 指数 >= 0:
- 仍有小数点,何时输出小数点
- 没有小数点,后续输出0
B1031 查验身份证 \
B1048 数字加密 1. 对齐两个整数
- 若加密正整数A 比 B 长,B高位补0后进行加密
- 若加密正整数A 比 B 短,B多余的部分正常输出,等同于A高位补0后进行加密
2. 结果从数字高位(字符串低位)开始输出
A1001 A+B Format 数字高位(字符串低位)开始,需要添加,的位置满足**(i + 1) % 3 == len % 3 且 不是最后一位**
A1005 Spell It Right \
A1035 Password (待优化)
A1077 Kuchiguse 1. 通过reverse()反转字符串,将后缀转换为前缀,便于比较
2. getline()之前注意读取换行符
A1082 Read Number in Chinese 1. 四位数字分为一节,单位为个、万、亿
2. 一节中数字全为0,则不输出节的单位
3. 节中第一个非零数之前有0,则输出1个0

3. 算法初步

3.1 排序

3.1.1 简单选择排序($O(n^2)$)

简单选择排序是指,对一个序列A中的元素A[0] ~ A[n-1],令i从 0 到 n-1 枚举,进行 n 趟操作,每一趟从待排部分$[i, n-1]$中选择最小元素(记录下标),令其与待排部分的**第一个元素A[i]**进行交换,使得$[0, i]$区间有序

void selectSort(int A[]) { //降序 简单选择排序
    for(int i = 0; i < n; i++) {
        int k = i;
        for(int j = i; j < n; j++) { //选出最小的元素
            if(A[j] < A[i])
                k = j; //记录更小元素的下标
        }
        int tmp = A[i]; //交换A[k]与A[i]
        A[i] = A[j];
        A[j] = tmp;
    }
}

3.1.2 直接插入排序($O(n^2)$)

直接插入排序是指,对序列A的n个元素A[0]~A[n-1],令 i **从 1 **到 n-1 枚举,进行 n - 1 趟操作。

某一趟时,序列A的前 i 个元素 A[0]~A[i-1]已经有序,则该趟在范围$[0, i - 1]$中,从后往前寻找某个位置j,使得A[i]插入后,范围$[0, i]$有序(A[j]~A[i]后移一位)。

void insertSort(int A[]) { //升序 直接插入排序
    for(int i = 1; i < n; i++) {
        int tmp = A[i], j = i;
        //从后往前遍历,便于编写代码
        while(j > 0 && tmp < A[j - 1]) {
            A[j] = A[j - 1];
            j--;
        }
        A[j] = tmp;
    }
}

3.1.3 冒泡排序($O(n^2)$)

冒泡排序的本质在于交换,即每次通过交换的方式把当前剩余元素的最大值(升序)移动到一端,当剩余元素减少到0时,排序结束。整个过程执行 n-1 趟,每一趟从左到右依次比较相邻的元素,如果大的数在左边,则交换,该趟结束时,最大数被移动到当前剩余数的最右边

void bubbleSort(int A[]) { //升序 冒泡排序
    for(int i = 1; i < n; i++) {//进行 n - 1 趟排序
        for(int j = 0; j < n - i; j++) {
            if(a[j] > a[j + 1]) {
                int tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
            }
        }
    }
}

3.1.4 排序题与sort函数的应用

PAT中的排序题,大部分只需要得到排序的最终结果,而不需要去写排序的完整过程(例如冒泡排序、快速排序等),因此推荐直接使用C语言的库函数qsort或是C++的sort函数进行排序。qsort函数的使用需要运用指针,且写法上没有sort函数简洁。sort函数根据具体情形使用不同的排序方法,效率较高,在实现中规避了经典快速排序中可能出现的会导致实际复杂度退化到$O(n^2)$的极端情况

因此更推荐使用C++的sort函数进行代码编写。

  • 结构体数组的排序

    struct node {
        int x;
        int y;
    } ssd[10];

    如果想先按x从大到小排序,在x相等的情况下按y从小到大排序(即二级排序),cmp的写法是:

    bool cmp(node a, node b) { //返回值为true时,a排在b之前
        if(a.x != b.x) {
            return a.x > b.x; //降序
        } else {
            return a.y < b.y; //升序
        }
    }
  • 排名的实现

    很多排序题要求在排序之后计算每个个体的排名,规则一般是:分数相同的排名相同,占用一个排位。例如有5个学生的分数分别为90、88、88、88、86,其排名分别为1、2、2、2、5。

    方法:

    将第一个个体排名记为1,遍历剩余个体,如果当前分数等于上一个个体的分数,则当前个体排名等于上一个个体的排名,否则当前个体的排名等于数组下标+1

题目 解题关键
B1015 德才论
A1062 Talent and Virtue
设置flag作为考生的分类,便于所有考生统一排序
A1012 The Best Rank 1. 利用全局变量设计cmp函数
2. 通过记录所有科目的排名,最后选出最好的排名以及对应科目
3. 相同分数者排名相同,下一不同分数者排名为数组下标+1
A1016 Phone Bills (待优化)
1. 通话记录统一先排序后处理
2. 连续的两个通话记录,判断是否为 同一用户 且 为先通话后挂断的状态
3. 通话时长的统计方法
4. 单位美分cents 要转换为 美元$
A1025 PAT Ranking \
A1028 List Sorting \
A1055 The World’s Richest 超时问题。要求输出的人数$\leq$100,通过筛去每个年龄多余的人解决
A1075 PAT Judge (待优化)
1. 不能编译的提交得分为0
2. 没有提交过的答案需要输出为-,利用<cstring>中的memset函数,为 得分数组 赋值 -1,表示没有提交过答案
3. 没有任何一题通过编译 或 没有提交过答案的人不记录排名,设置 是否有通过编译的标识,进行筛选
4. 读取数据时,将用户数组下标看作id,便于统计
5. 排序以 是否有通过编译 为 第一排序条件
A1080
A1083
A1095

3.2 散列

3.2.1 散列(hash)的定义与整数散列

例题:

给出$N$个正整数,再给出$M$个正整数,问这$M$个数中的每个数分别是否在$N$个数中出现过,其中 $N, M \leq10^5$,且所有正整数均不超过$10^5$。例如 $N = 5,M = 3$, $N$个正整数为 ${8, 3, 7, 6, 2}$,欲查询的$M$个正整数为 ${7, 4, 2}$。

对这个问题,最直观的思路是:对每个欲查询的正整数$x$,遍历所有$N$个数,看是否有一个数与$x$相等。这种做法的时间复杂度为$O(NM)$,显然不是好方法。可以采取用空间换时间的方式,用数组下标作为对应整数的标识,即设定一个bool型数组hashTable[100001],其中hashTable[x] == true表示正整数$x$在$N$个整数中出现过。这样就可以在一开始读入$N$个正整数时进行预处理。于是,对$M$个欲查询的数,就能直接通过hashTable数组判断出每个数是否出现过,这种做法的时间复杂度为$O(N+M)$。直接把输入的数作为数组的下标来对这个数的性质进行统计的方法非常实用,务必掌握

但是这个方法有一个问题:如果输入的整数可能是$10^9$大小,甚至是字符串,就不能将其直接作为数组下标了。因此我们寻找一种做法,将元素通过一个函数转换为一个在能接受范围内的整数,使得该整数尽可能唯一地代表这个元素。这样的方法称为散列(hash),用于转换的函数称为散列函数H,也就是说,如果元素在转换前为key,那么转换后就是一个整数H(key)

散列函数

key整数的情况来说,常用的散列函数有:

  1. 直接定址法

    • 恒等变换,即 H(key) = key

    • 线性变换,即 H(key) = a * key + b

  2. 除留余数法

    key除以一个数mod得到的余数作为 hash值 的方法,即 H(key) = key % mod

    通过这个散列函数,可以把很大的数转换为不超过 mod 的整数,这样就可以将它作为可用的数组下标。显然,当mod是一个素数时,H(key)能尽可能覆盖[0,mod]范围内的每一个数

  3. 平方取中法(很少用)

    key平方的中间若干位作为hash值


冲突

当两个不同的数key1key2他们的hash值相同时,这样的情况称为冲突解决冲突的常用方法:

  1. 开放定址法(获取新的hash值)

    • 线性探查法 (Linear Probing)

      当表中下标为H(key)的位置已经被其他元素占用,则检查下一个位置H(key)+1,以此类推。如果检查过程中超过了表长m,那么就回到表的首位继续循环,直到找到一个可用的位置,或是所有位置都已经被使用。

      H = (H(key) + i) % m(i = 0, 1, 2, …, m-1)

      缺点:容易导致大量元素在相邻的散列地址上“聚集”(堆积),大大降低查找效率

    • 平方探查法 (Quadratic Probing)

      当表中下标为H(key)的位置已经被其他元素占用,则按如下顺序检查表中位置

      H = (H(key) + i) % m;i = $0, 1^2, -1^2, 2^2, -2^2, …, k^2, -k^2;(k \leq m/2)$

      避免聚集问题。

      缺点:不能探测到散列表上所有单元(但至少能探测到一半单元)。

    • 再散列法(双散列法)

      H = (H1(key) + i * H2(key)) % mi 是冲突次数

  2. 链地址法 (拉链法)

    不计算新的hash值,而是把 所有H(key)相同的key(称为同义词) 存储在一个线性链表中,由散列地址唯一标识。


一般来说,可以使用**标准库模板库中的map**来直接使用hash的功能(C++11以后可以用 unordered_map速度更快),因此除非必须模拟这些方法或是对算法的效率要求比较高,一般不需要自己实现上面解决冲突的方法。


3.2.2 字符串hash初步

如果**key不是整数**,应该如何设计散列函数?

例题:

如何将一个二维整点$P$的坐标映射为一个整数,使得整点$P$可以由该整数唯一标识?

假设一个整点$P$的坐标是$(x,y)$,其中$0\leq x,y\leq Range$,那么可以令hash函数为H(P) = x * Range + y,这样对数据范围内的任意两个整点$P1$与$P2$,H(P1)都不会等于H(P2),就可以用H(P)来唯一地标识该整点P,接着便可以通过整数hash的方法进一步映射到较小的范围

字符串hash是指将一个字符串S映射为一个整数,使得该整数可以尽可能唯一地代表字符串S。

为了讨论问题方便,假设字符串均由大写字母A~Z构成,不妨把 AZ 视为 025。接着按照26进制转换为10进制的思路,实现将字符串映射为整数的需求(转换成的整数最大为$26^{len}-1$,len为字符串长度)。

int hashFunc(char S[], int len) { //将字符串S转换为整数
    int id = 0;
    for(int i = 0; i < len; i++)
		id = id * 26 + (S[i] - 'A'); //将26进制转换为10进制
    return id;
}

为了避免转换成的整数过大,需要注意 字符串长度len 不能太长。如果字符串中还有小写字母,可以把 AZ 作为 025,把 az 作为 2651,这样就变成了52进制转换为10进制的问题。

int hashFunc(char S[], int len) {
    int id = 0;
    for(int i = 0l i < len; i++) {
        if(isupper(S[i])) {
            id = id * 52 + (S[i] - 'A');
        } else if(islower(S[i])) {
            id = id * 52 + (S[i] - 'a');
        }
    }
    return id;
}

如果字符中还有数字,一般有两种处理方法:

  1. 按照小写字母的处理方法,增大进制数至62

  2. 如果保证在字符串的末尾是个确定的数字,就可以把前面英文字母的部分按上面的思路转换成整数,再将末尾的数字直接拼接上去

    int hashFunc(char S[], int len) {
        int id = 0;
        for(int i = 0; i < len - 1; i++)
            id = id * 26 + (S[i] - 'A');
       	id = id * 10 + (S[len - 1] - '0');
        return id;
    }

例题:

给出N个字符串(由三位大写字母组成),再给出M个查询字符串,问每个查询字符串在N个字符串中出现的次数。

#include <iostream>
using namespace std;

int hashFunc(char S[], int len) { //将字符串S转换为整数
    int id = 0;
    for(int i = 0; i < len; i++)
		id = id * 26 + (S[i] - 'A'); //将26进制转换为10进制
    return id;
}

int main() {
    int N, M;
    int hashTable[26 * 26 * 26] = {0};
    cin >> N >> M;
    string S[N];
    for(int i = 0; i < N; i++) {
        cin >> S[i];
        int id = hashFunc(S[i], 3);
        hashTable[id]++; //字符串出现的次数+1
    }
    string tmp;
    for(int i = 0; i < M; i++) {
        cin >> tmp;
        int id = hashFunc(tmp, 3);
        cout << hashTable[id] << endl; //输出字符串出现的次数
    }
    return 0;
}

3.2.3 相关习题

题目 解题关键
B1005 继续(3n+1)猜想 奇数在判断过程中,可能大小会超过100
B1029 旧键盘
A1084 Broken Keyboard
待优化
B1033 旧键盘打字 不能用scanfcin读取字符串,应采用gets(str)getline(cin, str),因为题目只保证第 2 行输入的文字串非空
B1038 统计同成绩学生 \
B1039 到底买不买
A1092 To Buy or Not to Buy
\
B1042 字符统计 \
B1043 输出PATest \
B1047 编程团体赛 \
A1041
A1050
A1048

3.3 递归

3.3.1 分治

分治(divide and conquer)的全称为“分而治之”。分治法将原问题划分成若干个规模较小而结构与原问题相同或类似的子问题,然后分别解决这些子问题,最后合并子问题的解,即可得到原问题的解。分治法的三个步骤:

  1. 分解:将原问题分解为若干和原问题拥有相同或相似结构的子问题。
  2. 解决:递归求解所有子问题。如果存在子问题的规模小到可以直接解决,就直接解决它。
  3. 合并:将子问题的解合并为原问题的解。

分治法分解出的子问题应当是相互独立、没有交叉的。如果存在两个子问题有相交部分,就不应该使用分治法解决。分治法作为一种算法思想,既可以使用递归的手段实现,也可以通过非递归的手段实现。一般来说,使用 递归 实现较为容易


3.3.2 递归

递归很适合用来实现分治思想

递归的逻辑中一般有两个重要概念:

  1. 递归边界
  2. 递归调用

其中递归调用是将原问题分解为若干个子问题的手段,而递归边界则是分解的尽头。递归的代码结构中一定存在这两个该概念,它们支撑起了整个递归最关键的逻辑

经典例子1:使用递归求解n的阶乘

#include <iostream>
using namespace std;

int F(int n) {
    if(n == 0) {
        return 1;
    } else {
        return n * F(n-1);
    }
}

int main() {
    int n;
    cin >> n;
    cout << F(n) << endl;
    return 0;
}

经典例子2:求 Fibonacci 数列的第n项

Fibonacci 数列(即斐波那契数列) 是满足 F(0) = 1, F(1) = 1, F(n) = F(n-1) + F(n-2) (n $\geq$ 2) 的数列,数列的前几项为 1, 1, 2, 3, 5, 8, 13, 21, … 。

从定义中可以获知递归边界为 F(0) = 1 和 F(1) = 1,且递归调用为 F(n) = F(n-1) + F(n-2) (n $\geq$ 2) ,因此可以仿照求解n的阶乘的写法。

#include <iostream>
using namespace std;

int F(int n) {
    if(n == 0 || n == 1) { //递归边界
        return 1;
    } else {
        return F(n-1) + F(n-2);
    }
}

int main() {
    int n;
    cin >> n;
    cout << F(n) << endl;
    return 0;
}

最后来看全排列(Full Permutation)。全排列指n个整数能形成的 所有排列

现在需要按字典序从小到大的顺序输出$1\sim n$的全排列,其中$(a_1, a_2, …, a_n)$的字典序小于$(b_1, b_2, …, b_n)$是指存在一个$i$,使得$a_1=b_1$、$a_2 = b_2$、…、$a_{i-1} = b_{i-1}$、$a_i < b_i$成立。

从递归的角度考虑,就可以分为若干个子问题:“输出以1开头的全排列”、“输出以2开头的全排列” … “输出以n开头的全排列”。不妨设定一个数组P,用来存放当前的排列;再设定一个散列数组hashTable,其中hashTable[x],当整数x已经在数组P中时,为1

按顺序往P的第1位到第n位中填入数字。不妨假设当前已经填好了P[1] ~ P[index-1],正准备填P[index]。显然需要枚举 1 ~ n,如果当前枚举的数字x还没有在P[1] ~ P[index-1]中(即hashTable[x] == 0),那么就把它填入P[index],同时将hashTable[x]置为1,然后去处理P的第index + 1位(即进行递归);当递归完成时,再将hashTable[x]还原为0,以便让P[index]填下一个数字

那么递归边界是什么呢?显然,当index达到n + 1时,说明P的的第1 ~ n位都已经填好了,此时可以把数组P输出,表示生成了一个排列,然后直接return即可。下面给出n = 3时的代码:

#include <iostream>
using namespace std;

void generateP(int index, int n) {
    if(index == n + 1) { //递归边界,已经处理完排列的 1~n 位
		for(int i = 1; i <= n; i++)
            cout << P[i];
        cout << endl;
        return;
    }
    for(int x = 1; x <= n; x++) { //枚举 1~n,试图将 x 填入 P[index]
        if(hashTable[x] == 0) { //如果 x 不在 P[1] ~ P[index - 1] 中
            P[index] = x; //令 P 的第 index 位为 x,即把x加如当前排列
            hashTable[x] = 1; //记 x 已在 P 中
            generateP(index + 1, n); //处理排列的第 index + 1 号位
            hashTable[x] = 0; //已处理完 P[index] 为 x 的子问题,还原状态
        }
    }
}


int main() {
    int n = 3, P[11], hashTable[11] = {0};
	generateP(1); //从P[1]开始填
    return 0;
}

最后的最后来看**$n$皇后问题**。$n$皇后问题是指在一个$nn$的国际象棋棋盘上放置$n$个皇后,使得这$n$个皇后*两两均不在同一行、同一列、同一条对角线上,求合法的方案数。

对于这个问题,如果采用组合数的方式来枚举每一种情况(即从$n^2$个位置中选择$n$个位置),那么需要$C_{n\times n}^n$的枚举量。但是换个思路,考虑到每行只能放置一个皇后、每列也只能放置一个皇后,如果把n列皇后所在的行号依次写出,那么就会是$1 \sim n$的一个排列。于是只需要枚举$1 \sim n$的所有排列,查看每个排列对应的放置方案是否合法,统计其中合法的方案即可。

于是可以在全排列的代码基础上进行求解。由于当达到递归边界时表示生成了一个排列,所以需要在起内部判断是否为合法方案,即遍历每两个皇后,判断它们是否在同一条对角线上(显然不在同一行和同一列),若不是,则累计计数变量cnt即可。主要代码如下:

int cnt = 0;

void generateP(int index) {
    if(index == n + 1) { //递归边界,生成一个排列
        int flag = 1; //flag为true表示当前排列为一个合法方案
        for(int i = 1; i <= n; i++) { //遍历任意两个皇后
            for(int j = i + 1; j <= n; j++) {
                if(abs(i - j) == abs(P[i] - P[j])) //如果在一条对角线上
                    flag = 0;
            }
        }
        if(flag) //当前方案合法
            cnt++;
    	return;
    }
    for(int x = 1; x <= n; x++) {
        if(hashTable[x] == 0) {
            P[index] = x;
            hashTable[x] = 1;
            generateP(index + 1);
            hashTable[x] = 0;
        }
	}
}

这种枚举所有情况,然后判断每一种情况是否合法的朴素做法称为暴力法

通过思考可以发现,当已经放置了一部分皇后时,可能剩余的皇后无论怎样放置都不可能合法,就不需要继续递归,直接返回上层即可。这种做法称为回溯法

void generateP(int index) {
    if(index == n + 1) { //递归边界,生成一个 合法方案
        cnt++;
        return;
    }
    for(int x = 1; x <= n; x++) { //第 x 行
        if(hashTable[x] == 0) { //第 x 行还没有皇后
            int flag = 1; //flag 为 1 表示当前皇后不会和之前的皇后冲突
            for(int pre = 1; pre < index; pre++) { //遍历之前的皇后
				if(abs(index - pre) == abs(x - P[pre])) {
                    flag = 0; //与之前的皇后在一条对角线冲突
                    break;
                }
            }
            if(flag) { //如果可以把皇后放在第 x 行
                P[index] = x; //令第 index 列皇后的行号为 x
                hashTable[x] = 1; //第 x 行已被占用
                generateP(index + 1); //递归处理第 index + 1 行皇后
                hashTable[x] = 0; //递归完毕,还原第 x 行 为 为占用
            }
        }
	}
}

3.4 贪心

3.4.1 简单贪心

贪心法是求解一类最优化问题的方法,它总是考虑在当前状态下局部最优(或较优)的策略,来使全局的结果达到最优(或较优)。要获得最优结果,要求中间的每步策略都是最优的,因此严谨使用贪心法来求解最优化问题需要对采取的策略进行证明。证明的一般思路是使用反证法及数学归纳法,即假设策略不能导致最优解,然后通过一系列推导来得到矛盾,以此证明策略是最优的,最后用数学归纳法保证全局最优。不过对平常使用来说,也许没有时间或不太容易对想到的策略进行严谨的证明(贪心的证明往往比贪心本身更难),因此一般来说,如果在想到某个似乎可行的策略,并且自己无法举出反例,那么就勇敢的实现它


3.4.2 区间贪心

区间不相交问题:给出$N$个开区间$(x, y)$,从中选择尽可能多的开区间,使得这些开区间两两没有交集。例如对开区间$(1, 3)$、$(2,4)$、$(3, 5)$、$(6, 7)$来说,可以选出最多三个区间$(1, 3)$、$(3, 5)$、$(6, 7)$,它们互相没有交集。

首先考虑最简单的情况,如果开区间$I_1$被开区间$I_2$包含(如图4-5a所示),则选择$I_1$是最好的选择,因为这样就有更大的空间去容纳其他开区间

接下来把所有开区间按左端点$x$从大到小排序,如果去掉区间包含的情况,那么一定有$y_1 > y_2 > … > y_n$成立(如图4-5b所示)。观察发现,$I_1$右边有一段一定不会和其他区间重叠,如果把它去掉,那么$I_1$的左边剩余部分就会被$I_2$包含,由图4-5a的情况可知,应当选择$I_1$。因此对这种情况,总是先选择 左端点最大 的区间。值得注意的是,总是先选择右端点最小的区间的策略也是可行的。

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

const int maxn = 110;

struct Inteval {
    int x, y; //开区间左右端点
} I[maxn];

bool cmp(Inteval a, Inteval b) {
    if(a.x != b.x) { //先按左端点从大到小排序
        return a.x > b.x; 
    else { //左端点相同的 按右端点从小到大排序
        return a.y > b.y;
    }
}
    
int main() {
    int n;
    while(cin >> n, n != 0) {
        for(int i = 0; i < n; i++)
            cin >> I[i].x >> I[i].y;
    sort(I, I + n, cmp);
    int cnt = 1, lastX = I[0].x; //记录不相交区间的个数,上一个被选中区间的左端点
    for(int i = 1; i < n; i++) {
        if(I[i].y <= lastX) { //如果该区间右端点在 lastX 左边
            lastX = I[i].x; //以 I[i] 作为新选中的区间
            cnt++; //不相交区间个数加1
        }
        cout << cnt << endl;
    }
    return 0
}

与这个问题类似的是区间选点问题:给出$N$个闭区间$[x, y]$,求最少需要确定多少个点,才能使每个闭区间中都至少存在一个点。例如对闭区间$[1,4]$、$[2, 6]$、$[5, 7]$来说,需要两个点(例如3、5)才能保证每个闭区间内都有至少一个点。

事实上,这个问题和区间不相交问题的策略是一致的。首先,回到图4-5a,如果闭区间$I_1$被闭区间$I_2$包含,那么在$I_1$中取点可以保证这个点一定在$I_2$内。接着把所有区间按左端点从大到小排序,去除掉区间包含的情况,就可以得到图4-5b。由于每个闭区间中都需要存在一个点,因此对左端点最大的区间$I_1$来说,取左端点就能让它尽可能多地覆盖其他区间。区间选点问题的代码只需要把区间不想交问题代码中的I[i].y <= lastX改为I[i].y < lastX即可。

总的来说,不是所有问题都适合使用贪心法,但是这并不妨碍贪心算法称为一个简洁、实用、高效的算法。


3.4.3 相关习题

题目 解题关键
B1020 月饼
A1070 Mooncake
库存量和售价都应该定义为double类型
B1023 组个最小数 \
A1033 To Fill or Not to Fill 能到达的距离内,由近到远遍历,有三种情况:

1. 最近距离的加油站都到不了
2. 出现油价比目前低的加油站,就直接去
2.1 油不够,只加能刚好到达的油量
2.2 不用加油
3. 没有更低价的加油站,就加满油(能尽量少加更贵的油),去价格相对 最低的加油站
A1037
A1038
A1067

3.5 二分

3.5.1 二分查找

二分查找的高效之处在于,每一步都可以去除当前区间中的一半元素,因此其时间复杂度是$O(\log n)$,这是十分优秀的。

在严格递增序列中查找给定的数$x$的做法:

#include <iostream>
using namespace std;

int binarySearch(int A[], int left, int right, int x) {
    int mid;
    while(left <= right) {
        mid = (left + right) / 2;
        if(A[mid] == x) {
            return mid;
        } else if(A[mid] > x) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1; //查找失败
}

int main() {
    int A[n] = {1, 3, 4, 6, 7, 8, 10, 11, 12, 15};
    printf("%d %d\n", binarySearch(A, 0, n - 1, 6), binarySearch(A, 0, n - 1, 9));
    return 0;
}

需要注意的是,如果过二分上界超过int型数据范围的一半,当欲查询元素在序列较靠后位置时,语句mid = (left + right) / 2中的left + right有可能超过int而导致溢出,通常使用等价语句mid = left + (right - left) / 2作为代替,以避免溢出。另外,二分法可以使用递归进行实现,但在程序设计时,更多采用非递归的写法

接下来探讨更进一步的问题:如果递增序列$A$中的元素可能重复,那么如何对给定的欲查询元素$x$,求出序列中第一个$\geq x$的元素位置$L$以及第一个$>x$的元素的位置$R$,这样元素$x$在序列中的存在区间就是$[L, R)$。

例如对下标从0开始、有5个元素的序列${1,3,3,3,6}$来说,如果要查询3,则应当得到$L = 1$、$R = 4$;如果查询 5,则应当得到$L = R = 4$。如果序列中没有$x$,$L$和$R$也可以理解为 假设序列中存在$x$,则$x$应当在的位置

先来考虑第一个小问:求序列中的第一个$\geq x$的元素位置。

  1. A[mid] >= x,说明第一个$\geq x$的元素的位置一定在**mid处或mid的左侧,应往左子区间[left, mid]继续查询,即令right = mid**
  2. A[mid] < x,说明第一个$\geq x$的元素的位置一定在**mid右侧,应往右子区间[mid+1, right]继续查询,即令left = mid + 1**
int lower_bound(int A[], int left, int right, int x) {
    int mid;
    while(left < right) {
        mid = (left + right) / 2;
        if(A[mid] >= x) { //中间值 >= x
            right = mid;
        } else { //中间值 < x
            left = mid + 1;
        }
    }
    return left; //返回夹出来的位置
}

上述代码有两个需要注意的地方:

  1. 循环条件为left < right,而不是之前的left <= right,这是由问题本身决定的。因为如果想要返回第一个>= x的元素的位置,就不需要判断元素x本身是否存在
  2. 二分的初始区间应当能覆盖到所有可能返回的结果,考虑到欲查询元素可能比序列中所有元素都大,此时应当返回n,因此二分上界是n,故二分的初始区间为[left, right] = [0, n]

接下来解决第二小问:求序列中第一个大于x的元素的位置。

int upper_bound(int A[], int left, itn right, int x) {
    int mid;
    while(left < right) {
        mid = (left + right) / 2;
        if(A[mid] > x) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left; //返回夹出来的位置
}

lower_boundupper_bound函数都在解决这样一个问题:寻找有序序列中第一个满足某条件的元素的位置。这是一个非常重要且经典的问题,平时能碰到的大部分二分法问题都可以归结于这个问题。


3.5.2 二分法拓展

首先介绍如何计算$\sqrt2$的近似值

对$f(x) = x^2$来说,在$x \in [1, 2]$范围内,$f(x)$随着$x$的增大而增大,这就给使用二分法创造了条件

以精确到$10^{-5}$为例,令浮点型leftright初值分别是 1 和 2,然后根据中点mid处$f(x)$的值与 2 的大小来选择子区间进行逼近:

  1. f(mid) > 2,说明mid > $\sqrt2$,令right = mid
  2. f(mid) < 2,说明mid < $\sqrt2$,令left = mid

上面两个步骤当right - left < $10^{-5}$时结束,显然leftright的距离 < $10^{-5}$ 时已满足精度要求mid即为所求的近似值。

const double eps = 1e-5; //精度为 10^{-5},科学计数法

double f(double x) {
    return x * x;
}

double calSqrt() {
	double left = 1, right = 2, mid;
    while(right - left > eps) {
        mid = (left + right) / 2;
        if(f(mid) > 2) { //即 mid > sqrt(2)
            right = mid;
        } else {
            left = mid;
        }
    }
    return mid;
}

事实上,计算$\sqrt2$的近似值的问题是这样一个问题的特例:给定一个定义在$[L, R]$上的单调函数$f(x)$,求方程f(x) = 0的根

同样假设精度要求为eps = $10^{-5}$,函数$f(x)$在$[L,R]$上递增,leftright的初值分别为$L$、$R$。根据中点mid的函数值f(mid) 与 0 的大小关系来判断往哪个子区间继续逼近f(x) = 0的根:

  1. f(mid) > 0,说明f(x) = 0的根在mid左侧,应往左子区间继续逼近,即令right = mid
  2. f(mid) < 0,说明f(x) = 0的根在mid右侧,应往右子区间继续逼近,即令left = mid
const double eps = 1e-5; //精度为 10^{-5},科学计数法

double f(double x) {
    return ...;
}

double solve() {
	double left = L, right = R, mid;
    while(right - left > eps) {
        mid = (left + right) / 2;
        if(f(mid) > 0) {
            right = mid;
        } else {
            left = mid;
        }
    }
    return mid; //f(x) = 0 的根
}

3.5.3 快速幂

3.5.4 相关习题

题目 解题关键
A1010 Radix 1. 基数上界为 已确认数字的十进制大小 + 1 与 下界中的较大值(确保不会出现多个解(而且基数不确定的数,只有一位数的时候才可能多个解) )
2. 基数过大时,数值转换为十进制会发生上溢,存储结果为负数
A1044
A1048

3.6 tow pointers

3.6.1 什么是two pointers

3.6.2 归并排序

3.6.3 快速排序

3.6.4 相关习题

题目 解题关键
B1030 完美数列
A1085 Perfect Sequence
\
B1035 插入与归并
A1089 Insert or Merge
1. 插入排序:未排序部分和初始序列一定相同
2. 归并排序:末尾不足数量的子序列同样需要排序
3. 插入排序 更容易判断,将其作为判断排序类型的切入点
4. 插入和归并排序的**实际操作由排序函数sort/qsort**代替
A1029
A1048

3.7 其他高效技巧与算法

3.7.1 打表

3.7.2 活用递推

3.7.3 随机选择法

3.7.4 相关习题

题目 解题关键
B1040 有几个PAT
A1093 Count PAT’s
1. A前有P,后有T才能形成PAT;
2. 当前A能构成的PAT数量 = 之前P的数量 * 之后T的数量
3. 突破口:先遍历一遍,获取T的数量
B1045 快速排序
A1101 Quick Sort
1. 可能的主元:左侧的最大值比自身小;右侧的最小值比自身大
2. 输出即使没有主元,也得换行

4. 数学问题

4.1 简单数学

题目 解题关键
B1003
B1019
A1069
B1049
A1104
A1008
A1049

4.2 最大公约数与最小公倍数

题目 解题关键
B1008

4.3 分数的四则运算

题目 解题关键
B1034
A1088
A1081

4.4 素数

题目 解题关键
B1007
B1013
A1015
A1078

4.5 质因子分解

题目 解题关键
A1059
A1096

4.6 大整数运算

题目 解题关键
A1023
A1024

4.7 扩展欧几里得算法

4.8 组合数


5. C++标准模板库介绍

5.1 vector

题目 解题关键
A1039
A1047

5.2 set

题目 解题关键
A1063

5.3 string

题目 解题关键
A1060

5.4 map

题目 解题关键
B1044
A1100
A1022
A1054
A1071

5.5 queue

5.6 priority_queue

5.7 stack

5.8 pair

5.9 algorithm


6. 数据结构专题1

6.1 栈的应用

题目 解题关键
A1051 Pop Sequence 1. 可能会发生堆栈溢出
2. 栈顶元素和当前需要出栈的元素相同时,出栈。该判断之前必须先判断栈是否不为空(否则会报错)
3. 标记出栈序列中待出栈元素下标,最终标记只有超出序列下标,才可能是出栈序列

6.2 队列的应用

题目 解题关键
A1056 Mice and Rice 1. 输入的第二行是按老鼠的序号给出的重量。第三行给出的是老鼠的序号,而不是按序号给出的比赛序号
2. 用队列记录老鼠的序号(而不是记录老鼠的结构体,有利于减少内存的占用),晋级的老鼠重新入队
3. 最后的分组中,老鼠数量可能不足(利用<cmath>中的ceil函数向上取整)

6.3 链表处理

题目 解题关键
B1025 反转链表
A1074 Reversing Linked List
1. 通过数组下标来表示地址,便于链接各个节点
2. 可能存在无效结点
3. 只根据 链表顺序的地址 进行反转,有利于节约开销
A1032 Sharing \
A1052 Linked List Sorting 存在无有效结点的情况
A1097

7. 搜索专题

7.1 深度优先搜索DFS

题目 解题关键
A1103 Integer Factorization 1. 利用vector(可根据size函数确认符合要求的元素个数),预先存储所有 ≤ N的 元素(整数的P次幂值)
2. 为了保证底数最大的序列被选中,从大到小遍历
3. DFS函数的参数:当前元素下标,已选元素数量,已选元素之和,已选元素的底数之和
4. DFS函数的递归边界:已选元素数量为K且和为N
5. DFS函数的递归调用选择当前元素和不选择当前元素
6. 剪枝和超过N 或 已选元素数量超过K 或 遍历完底数序列时,不必再递归

7.2 广度优先搜索BFS

题目 解题关键
A1091 Acute Stroke 1. 设定相对当前位置的前后左右上下6个方向的增量,便于枚举
2. 设置数组inq记录当前位置是否入过队
3. 越界、当前位置为0、已入过队的位置无需再判断。
4. 在BFS函数中,利用队列进行BFS,使用STL的queuepush函数只将所选元素的副本入队,后续对原元素的操作不改变队列中的副本

8. 数据结构专题2

8.1 树与交叉树

8.2 二叉树的遍历

题目 解题关键
A1020 Tree Traversals \
A1086 Tree Traversals Again 先序序列相当于入栈次序;中序序列相当于出栈次序
A1102 Invert a Binary Tree 1. 题目给的是结点编号的关系,故采用静态链表存储二叉树
2. 反转二叉树即每个结点的左右子树对换,选择后序遍历

8.3 树的遍历

题目 解题关键
A1004 Counting Leaves 1. 利用数组存储每层的叶结点个数
2. 根据出队结点的层数,获取最大层数,遍历输出每层叶结点个数
A1053 Path of Equal Weight 1. 输出的路径序列要求降序,因此在读入结点时就将孩子节点按权重降序排序,这样,之后遍历时得到的路径即为降序

2. 利用vectorbeginend函数获得vector首元素地址尾后地址,用于sort函数排序
3. 利用vector存储路径,在递归子结点之前,用push_back函数将子结点加入路径,递归回溯后,用pop_back将先前加入的子结点移出路径
A1079 Total Sales of Supply Chain 1. 静态写法表示树,即用数组下标指代结点
2. 结点的结构体中设有货物量变量,用来判断是否为零售商(本题采用了BFS;也可DFS)
A1090 Highest Price in Supply Chain 由于不涉及结点的数据域,可以直接vector<int> child[maxn]存放树
A1094
A1106

8.4 二叉查找树BST

题目 解题关键
A1043 Is It a Binary Search Tree 1. 静态写法(变长数组)表示二叉树
2. 根据BST左子树所有结点的数据域 < 根结点的数据域,右子树所有结点的数据域 根结点的数据域(由输入样例得出大小关系,镜像则相反),获取左右子树的边界,判断是否符合先序序列,若符合,则按照左右根的顺序递归,将符合的根结点存入vector(获取后序序列)
3. 若vecotr中元素数量 = 输入序列的元素数量(能顺利转换为BST的后序序列),说明输入序列为先序序列
A1064 Complete Binary Search Tree 1. 输入的元素升序排序,即为二叉树的中序遍历序列
2. 静态写法(变长数组)按照层序存储完全二叉排序树
3. 对二叉树进行中序遍历,依次填入中序遍历序列的元素即可得到层序存储的二叉树。注意:中序遍历时,二叉树数组根结点的下标
若设为1,则左右孩子结点下标为root * 2root * 2 + 1
若设为0,则左右孩子结点下标为root * 2 + 1root * 2 + 2
4. 顺序输出二叉树数组元素即为层序遍历序列
A1099 Build A Binary Search Tree 静态写法表示树,解题方法和 A1064 基本一致

8.5 平衡二叉树

题目 解题关键
A1066 Root of AVL Tree 即写出平衡二叉树的代码模板
1. 新建结点的初始高度为1
2. 获取树高时,注意递归到空结点时,返回0
3. 插入结点,递归过程中从系统栈出栈后
1) 平衡因子为2时,树型可能为LR型或LL型,LR型需要先对当前结点的左子树进行右旋;之后,LR型和LL型都需要对当前结点进行右旋
2) 平衡因子为-2时,树型可能为RL型或RR型,RL型需要先对当前结点的右子树进行左旋;之后,RL型和RR型都需要对当前结点进行左旋
4. 左旋和右旋过程中要及时更新树高

8.6 并查集

题目 解题关键
A1107 Social Clusters 1. 根据共同(包括潜在的→有共同爱好的人另外的爱好)爱好来确定潜在朋友的集合,利用hobby[1001]记录 任意一个 拥有对应爱好的结点便于合并操作
2. 遍历各用户,根据根结点统计各集合的人数
3. 将集合按包含人数降序排序,再遍历即可筛选统计出集合个数
4. 路径压缩可选

8.7 堆

题目 解题关键
A1098 Insertion or Heap Sort 1. 用于表示树的数组,注意下标从 0或1 开始,孩子结点表示的区别
2. 插入排序:未排序部分和初始序列一定相同
3. 堆排序:后面的元素有序,前面无规律
4. 插入排序 更容易判断,将其作为判断排序类型的切入点
4. 插入排序实际操作可由排序函数sort实现

5. 要用堆排序得到
递增序列
,则需要建立大根堆
6. 堆排序从后往前找到第一个 $<$ 堆顶的元素,与堆顶元素交换,再对整个堆向下调整

8.8 哈夫曼树


9. 图算法专题

9.1 图的定义和相关术语

9.2 图的存储

9.3 图的遍历

题目 解题关键
A1013 Battle Over Cities 1. 问题等价于求 一个无向图去掉一个结点后,连通分量的数量,这种问题一般有两种方法:图的遍历并查集
2. cin会超时,需要改为scanf,邻接矩阵和邻接表都可存储图
3. 每次输入被占领的城市之前,要重置城市的访问状态为未访问
4. 将失去的城市标记为已访问,即可达到失去的效果(没有公路可以到达)
A1021
A1034 Head of a Gang 1. 相同人员之间可能多次通话
2. map<type1, type2>自动按type1从小到大输出,使用map<string, int>建立头目姓名与成员数量的关系,便于输出结果
3. 图中可能有环,为了边权不被漏加,需要先累加边权再递归;同时为了防止边权被重复计算,累加后删除这条边,以免走回头路、重复计算边权
A1076 Forwards on Weibo 1. 转发是粉丝转发博主的信息,因此要根据用户的关注情况建立从博主到粉丝(即反向)有向图
2. DFS记录访问过的结点数量比较麻烦,BFS比较方便
3. 可能形成环 ,必须控制每个用户只能转发一次(遍历时只能访问一次)

9.4 最短路径

题目 解题关键
A1003 Emergency
A1018
A1030 Travel Plan
A1072
A1087

9.5 最小生成树

9.6 拓扑排序

9.7 关键路径


10. 动态规划专题

对黑盒测试来说,所有输入数据都放在一个文件里


单点测试

PAT试题基本为单点测试(即一次运行一组数据,一组数据通过测试则获得这组数据的分值)。


多点测试

多点测试要求程序一次运行所有数据,并要求输出结果都正确,只要存在错误,即不得分
大部分 在线判题系统(Online Judge) 都采用了多点测试
由于要求程序能运行所有数据,因此必须保证程序能反复执行代码的核心部分,这就要用到循环

输入类型

题目一般有3中输入的格式,需要采用不同输入方式。

  1. while··· EOF

题目没有给定输入的结束条件,则默认读取到文件末尾

EOF(End Of File)

可以通过printf("%d", EOF);读取EOF的数值,一般的设备上值是-1。
EOF操作:

  • windows:Ctrl + Z
  • unix:Ctrl + D

scanf 若成功读入一个值,返回1;若成功读入2个值,返回2;若读入失败,返回 -1,C/C++中,EOF即为 -1。

正常情况下,控制台中的输入不会失败,只有读取文件时到达文件末尾,导致无法读取时,才会产生读入失败

//读取数字、字符、字符串
while (scanf("%d", &n) != EOF) {
    ···
}

//读取字符串
while (gets(str) != NULL) {
    ···
}

  1. while··· break

题目要求,当输入的数据满足某个条件时,停止输入

while (scanf("%d%d", &a, &b) != EOF) {
    if (a == 0 && b == 0) {
        break;
    }
    printf("%d\n", a + b);
}

//更简洁的写法
while (scanf("%d%d", &a, &b), a || b) {// scanf()恒不为0
    printf("%d\n", a + b);
}

  1. while (T--)

题目给出测试数据的组数,然后才给出相应数量数组的输入数据。

int T;
scanf("%d", &T);
while (T--) {
    ···
}

输出

  1. 正常输出

  2. 每组数据输出之后,额外加一个空行

  3. 两组输出数据之间有一个空行,最后一组数据后面没有空行

    一般在第三种输入类型while (T--)情况下出现,只需通过判断T是否为0选择是否输出额外的换行。


重置变量

在多点测试中,每一次循环都要重置变量和数组,否则在下一组数据来临时,变量和数组不是初始状态,将出错。重置数组一般使用memset函数或fill函数

数据类型选择

  1. 整型int取值范围:$-2^{31} \sim +(2^{31}-1)$,题目要求绝对值在$10^9$以内 或 32位整数,则用int型表示

  2. 长整型long long取值范围:$-2^{63} \sim +(2^{63}-1)$,题目要求绝对值在$10^{18}$以内 或 64位整数,则用long long型表示

    注:如果 long long 型赋 $> 2^{31}-1$的初值,需要在初值后加上LL,否则编译错误。如long long num = 123456789012345LL;

  3. 浮点型数据一律用double存储,而不用float(精度低,6~7位)

  4. 字符常量使用**ASCII码(范围0~127)**统一编码。

    • 0~9 的ASCII码值:48~57
    • AZ 的ASCII码值:6590
    • az 的ASCII码值:97122 (比大写字母的ASCII码值大32)
  5. 强制类型转换

    #include <cstdio>
    
    int main() {
        double r = 12.56;
        int a = 3, b = 5;
        printf("%d\n", (int)r); //输出12
        printf("%.1f", (double)a / (double)b);//输出0.6
        return 0;
    }

输入输出

C语言 C++ 比较
#include <cstdio>
scanf函数
printf函数
#include <iostream>
using std::cin;
using std::cout;
cin
cout
cin 和 cout 无需指定输入输出格式
消耗的时间比 scanf 和 printf 多得多
推荐使用C语言的 scanf 和 printf
只有在十分必要的时候使用 cin 和 cout

输入和输出格式

类型 输入 输出
long long scanf("%lld", &n); printf("%lld", n);
double scanf("%lf", &db); printf("%f", db);
字符串 scanf("%s", str);
(无需 取地址符&)
printf("%s", str);
char c1 = getchar();
能读入换行符\n
putchar(c1);

实用的输出格式

  1. %md

    使不足m位的int型变量以m位进行右对齐输出,高位用空格补齐;若变量本身超过m位,则保持原样。

  2. %0md

    使不足m位的int型变量以m位进行右对齐输出,高位用0补齐;若变量本身超过m位,则保持原样。

  3. %.mf

    让浮点数保留m位小数(四舍六入五成双)输出。如果要四舍五入,需要用到round函数

    四舍六入五成双:

    • 5后有数时:舍5入1
    • 5后无数时:
      • 5前为奇数,舍5入1
      • 5前为偶数,舍5不进(0是偶数)

C++标准库头文件

C++标准库 包含内容
<iostream> C++标准输入和输出函数 的函数原型
<cstdio> C风格标准输入和输出函数 的函数原型
<iomanip> 格式化数据流的流操纵符 的函数原型
<cmath> 数学库函数 的函数原型
<ctime> 处理时间和日期的函数 的函数原型
<cstdlib> 数与文本的转换、内存分配、随机数及其他各种工具函数 的函数原型
<random> 产生非确定性的随机数 的功能库
<cctype> 测试 字符特定属性(如是否为数字、标点符号等)函数 的函数原型
转换 大小写字母的函数 的函数原型
<iterator> 访问 C++标准库容器中数据 的类
<algorithm> 操作 C++标准库容器中数据 的函数
<string> C++标准库的 string类 的定义
<cstring> C风格字符串处理函数 的函数原型

<cmath>

  1. double fabs(double x)

    浮点型取绝对值

  2. double floor(double x)ceil(double x)

    向下取整向上取整

  3. double round(double x)
    针对小数点后一位四舍五入

    另,不使用函数进行四舍五入的方法

    num = num + 0.5

  4. double pow(double r, double p)

    求 r 的 p次方

    $10^n$还有另外的表示方法,如

    • $10^3$ 可写成 1e3
    • $2\times10^6$可写成2e6
    • $3\times10^{-6}$可写成3e-6
  5. double sqrt(double x)

    求 x 的算术平方根

  6. double log(double x)double log10(double x)

    求 x 以 $e$ 为底的对数 和 以10为底的对数

    针对任意底数求对数的函数,必须用换底公式,即$\log_ab = \ln b/\ln a$

  7. double exp(double x)

    指数函数$e^x$

  8. 三角函数

    x为弧度

    • sin(double x)
    • cos(double x)
    • tan(double x)

<ctime>

  1. time_t time(time_t *seconds)

    返回自 格林尼治标准时间的1970年1月1日0时 起 到现在秒数。如果seconds不为空,返回值也存储在seconds


<cstdlib>

  1. int rand()

    rand函数生成 [0, RAND_MAX] 之间的一个整数

    直接由rand函数生成的数的范围常常不能满足具体需要,可以通过比例缩放(scaling)方法得到所需的随机数。例如模拟投掷六面骰子,结果可以用rand() % 6 + 1表示。其中数字6称为比例缩放因子

  2. void srand(unsigned int seed)

    rand函数实际上生成的是 伪随机数。程序每次执行时产生的序列都是重复的,将其调整为每次执行时都产生不同的随机数序列的过程称为随机化,可以通过srand函数实现srand函数接收一个unsigned int值, rand函数使用的随机数发生器 “播种”,从而产生不同的随机数序列。为了在随机化时不用每次都输入“种子”,可以使用如下语句:

    srand(static_cast<unsigned int>(time(NULL) ) );


<cctype>

  1. int isalnum(int c)

    字符是否为数字或字母

  2. int isalpha(int c)

    字符是否是字母

  3. int isdigit(int c)

    字符是否是十进制数字

  4. int islower(int c)

    是否是小写字母

  5. int isupper(int c)

    是否是大写字母

  6. int tolower(int c)

    把大写字母 转换为 小写字母

    不会改变非字母字符的值

  7. int toupper(int c)

    把小写字母 转换为 大写字母

    不会改变非字母字符的值


<algorithm>

  1. max(x, y)min(x, y)

  2. abs(x)x必须是整数,因此更推荐使用<cmath>下的fabs(x)

  3. swap(x, y)

  4. reverse(it1, it2)

    可以将 数组指针在[it1, it2)之间的元素 或 容器的迭代器在[it1, it2)之间的元素 进行反转

    int a[10] = {10, 11, 12, 13, 14, 15};
    reverse(a, a + 4); //将 a[0] ~ a[3]反转
    for(int i = 0; i < 6; i++)
        cout << a[i] << " ";
    //输出结果:13 12 11 10 14 15
    
    string str = "abcdefghi";
    reverse(str.begin() + 2, str.begin() + 6); //对str[2] ~ str[5]反转
    for(int i = 0; i < str.size(); i++) {
        cout << str[i];
    }
    //输出结果:abfedcghi
  5. next_permutation函数

    给出一个序列在全排列中的下一个序列

    int a[10] = {1, 2, 3};
    do{
        cout << a[0] << a[1] << a[2] << endl;
    } while(next_permutation(a, a + 3)); //a[0]~a[2]之间的序列求解下一个序列
  6. fill函数

    对数组或容器中某一段区间元素赋相同的值。和<cstring>memset不同(基本只用于赋0或-1),可以赋数组类型对应范围中的任意值

    int a[5] = {1, 2, 3, 4, 5}
    fill(a, a + 5, 233); //a[0] ~ a[4] 均赋值为 233
    for(int i = 0; i < 5; i++)
        cout << a[i] << " ";
    //输出结果:233 233 233 233 233
  7. sort函数

    C语言的qsort函数的使用需要运用指针,且写法上没有C++的sort函数简洁。sort函数根据具体情形使用不同的排序方法,效率较高,在实现中规避了经典快速排序中可能出现的会导致实际复杂度退化到$O(n^2)$的极端情况

    因此更推荐使用C++的sort函数进行代码编写。

    sort(首元素地址, 尾元素地址的下一个地址, 比较函数cmp(非必填))

    如果不写比较函数cmp,则默认升序排序。如果想要降序排序,需要编写比较函数cmp:

    bool cmp(int a, int b) { //返回值为true时,a被排在b之前
        return a > b; //降序
    }

    在STL标准容器中,只有vectorstringdeque可以使用sort,因为像setmap这种容器是用红黑树实现的,元素本身有序,故不允许使用sort排序

  8. lower_boundupper_bound

    lower_bound(first, last, val)用来寻找在数组或容器中的[first, last)范围内第一个值$\geq$val的元素的位置

    upper_bound(first, last, val)用来寻找在数组或容器中的[first, last)范围内第一个值>val的元素的位置

    如果是数组,则返回该位置的指针;如果是容器,则返回该位置的迭代器。如果没有找到相应元素,则返回可以插入该元素的位置的指针或迭代器

  9. max_elementmin_element

    max_element(first, last)用来寻找在数组或容器中的[first, last)范围内最大元素的位置

    min_element(first, last, val)用来寻找在数组或容器中的[first, last)范围内最小元素的位置

    如果是数组,则返回该位置的指针;如果是容器,则返回该位置的迭代器


常用容器

<vector>

向量(“变长数组”的叫法更容易理解),长度可以根据需要进行变化,比较节省空间。试题中,有时会碰到只用普通数组会超内存的情况,使用vector会让问题的解决便捷许多;另外,vector还可以用来以邻接表的方式存储图

  1. vector的定义

    vector<typename> name

    如果typename也是一个STL(Standard Template Library)容器,在C++11之前,定义的时候,在符号>>之间要加上空格。如:vector<vector<int> > name;,可以理解为两个维都可变长的二维数组

    而vector数组的定义,如:vector<typename> Arrayname[arraySize];一维长度已固定,注意两者的区别

  2. vector常用函数

    1. push_back(typename x):在 vector 末尾添加一个元素 x

    2. pop_back()删除 vector 的末尾元素

    3. begin():取 vector 的首元素地址

    4. end():取 vector 的 尾后(尾元素地址的下一个)地址(美国人思维比较习惯左闭右开

    5. size():获取 vector 中的元素个数

    6. clear()清空 vector 中所有元素

    7. insert(vector<typename>::iterator it, typename x):向vector的 任意迭代器 it 处 插入一个元素 x

      vi.insert(vi.begin() + 2, -1); //将 -1 插入vi[2]

    8. erase()

      • 删除迭代器为 it 处的元素:erase(it);
      • 删除 [firstIt, lastIt) 内所有元素:erase(firstIt, lastIt);
  3. vector容器内元素的访问

    1. 通过下标访问

    2. 通过迭代器iterator访问

      vector<typename>::iterator it;,这样就得到了迭代器it,可以通过***it来访问vector里的元素**。

      例如:

      #include <iostream>
      #include <vector>
      using namespace std;
      
      int main() {
      	vector<int> vi;
          for(int i = 1; i <= 5; i++)
              vi.push_back(i); //在 vi 的 末尾 添加元素 i
          vector<int>::iterator it = vi.begin(); //vi.begin() 为取 vi 的首元素地址
          for(int i = 0; i < 5; i++)
              cout << *(it + i);
      	return 0;
      }

      可以看出vi[i]vi.begin() + i等价。在常用的STL容器中,只有vectorstring中,才允许使用vi.begin() + 1这种 迭代器加上整数 的写法

      迭代器还实现了自增和自减的操作,于是还有一种遍历vector中元素的写法:

      //vector 的迭代器不支持 it < vi.end() 写法
      for(vector<int>::iterator it = vi.begin(); it != vi.end(); it++)
          cout << *it;

<set>

集合,是一个内部自动递增排序 且 不含重复元素的容器。试题中,可能出现需要去掉重复元素的情况,而且有可能因为这些元素 比较大 或者 类型不是int型 而不能直接开散列表,这种情况下就可以用set来保留元素本身而不考虑个数。虽然上述情况也可以通过再开一个数组进行下标和元素对应来解决,但set提供了更为直观的接口,并且可以实现自动排序,可以在做某些题时减少思维量

  1. set的定义

    set<typename> name;

    vector相同,如果typename也是一个STL容器,在C++11之前,定义的时候,在符号>>之间要加上空格。如:set<vector<int> > name;,可以理解为两个维都可变长的二维数组

  2. set常用函数

    1. begin():取 set 的首元素地址

    2. end():取 set 的 尾后(尾元素地址的下一个)地址(美国人思维比较习惯左闭右开

    3. size():获取 set 中的元素个数

    4. clear()清空 set 中所有元素

    5. insert(typename x):将 x 插入 set 容器中,并自动递增排序和去重,时间复杂度为$O(logN)$

    6. find(typename value):返回 set 中对应值为 value 的迭代器

      如:set<int>::iterator it = st.find(2); //在 set 中查找2,返回其迭代器

    7. erase()

      • 删除单个元素

        • 删除迭代器为 it 处的元素:erase(it);

          可以结合find函数使用,如:st.erase(st.find(100))

        • 删除值为 value 的元素:erase(value);

      • 删除 [firstIt, lastIt) 内所有元素:erase(firstIt, lastIt)

  3. set容器内元素的访问

    set只能通过 迭代器iterator 访问,因为只有vectorstring中,才允许使用vi.begin() + 1这种 迭代器加上整数 的写法,因此只能按如下方式枚举:

    #include <iostream>
    #include <set>
    using namespace std;
    
    int main() {
    	set<int> st;
    	st.insert(3);
        st.insert(5);
        st.insert(2);
        st.insert(3);
        //set 的迭代器不支持 it < vi.end() 写法
    	for(set<int>::iterator it = st.begin(); it != st.end(); it++)
    		cout << *it;
    	return 0;
    }

    输出为:2 3 5,可以发现,set内的元素自动递增排序,且自动去除了重复元素。

  4. 延伸

    set中元素是唯一的,如果处理元素不唯一的情况,需要使用multiset。C++11 标准中还增加了unordered_set以散列代替set内部的红黑树(一种自平衡二叉查找树)实现,使其可以用来去重但不排序的需求,速度比set快得多。


<string>

  1. string中内容的访问

    1. 通过下标访问

      一般来说,可以直接像字符数组那样去 访问string,如果要读入和输出整个字符串,则只能用cincout。那么有办法用printf输出string吗?

      string的函数c_str()可以将string类型转换为字符数组进行输出。示例:

      string str = "abcd";
      printf("%s\n", str.c_str());
    2. 通过迭代器访问

      有些函数比如insert()erase()要求以迭代器为参数进行访问。由于string不像其他STL容器那样需要参数,因此可以直接如下定义:

      string::iterator it;
      for(it = str.begin(); it != str.end(); i++)
          cout << *it;

      stringvector一样,允许使用vi.begin() + 1这种 迭代器加上整数 的写法

  2. string常用函数

    1. operator+=

      string的加法,可以将两个string直接拼接

    2. compare operator

      两个string类型可以直接使用 比较符 比较大小,比较规则是按字典序

    3. begin():取 string 的首元素地址

    4. end():取 string 的 尾后(尾元素地址的下一个)地址(美国人思维比较习惯左闭右开

    5. size()/length():返回 string 的长度

    6. clear():清空 string 中的数据

    7. insert

      • 在 pos 位置插入字符串:insert(int pos, string str)原来位置的字符串顺延

      • 在 迭代器it 位置插入字符串:

        insert(it, firstIt, lastIt)firstItlastIt待插字符串的首尾迭代器,用来表示串 [firstIt, lastIt) 将被插在 it 位置上

    8. string::npos:是一个常数,本身值为**-1**,但由于是unsigned_int类型,因此实际上可以认为是最大值。用于作为find函数失配时的返回值。

    9. find()

      • str.find(string str1):当 str1 是子串时,返回在 str 中第一次出现的位置;如果不是字串,则返回string::npos
      • str.find(string str1, int pos):从 pos 位置开始匹配 str1
    10. erase()

      • 删除单个元素:erase(it),目标字符之后的字符字串 前移
      • 删除一个区间内的所有元素,目标区间之后的字符字串 前移
        • erase(firstIt, lastIt),删除 [firstIt, lastIt) 间的所有字符
        • erase(int pos, int length),pos 是删除的起始位置
    11. substr(int pos, int length)返回从 pos 位置开始,长度为 length 的字串

    12. replace()

      • str.replace(int pos, int lenth, str1):把 str 从 pos 位置开始,长度为 length 的字串替换为 str1,替换位置之后的字符串不变
      • str.replace(it1, it2, str1):把 str 的迭代器 [it1, it2) 范围的字串替换为 str1,替换位置之后的字符串不变

<map>

映射map可以将 任何基本类型(包括STL容器) 映射到 任何基本类型(包括STL容器)

来看一个情况:判定给的一些数字在某个文件中是否出现过。如果数字很大,那么就不便建立散列的数组。这时,可以通过map,将这些数字当成字符串,建立stringint的映射

  1. map的定义

    map<typename1, typename2> mp;< >内第一个是 键(key) 的类型,第二个是 值(value) 的类型。map 会以 键 从小到大的顺序自动排序(因为 map 内部是使用红黑树实现的,set也是如此)map 的一个键只能对应一个值。如果是 int 型映射到 int 型,就相当于普通的 int 型数组。

    如果是字符串到整型的映射,必须使用 string 而不能使用 char数组map<string, int> mp;,因为数组不能作为键值

  2. map常用函数

    1. begin():取 map 的首元素地址

    2. end():取 map 的 尾后(尾元素地址的下一个)地址(美国人思维比较习惯左闭右开

    3. find(key):返回 键key的对应映射值 的迭代器

      map<char int>::iterator it = mp.find('b');

    4. erase()

      • 删除单个元素:
        • erase(it):it 为待删除映射的迭代器
        • erase(key):key 为待删除映射的键
      • 删除一个区间内的所有映射:erase(firstIt, lastIt)
    5. size():获取映射的对数

    6. clear():清空 map 中的所有映射

  3. map容器内元素的访问

    1. 通过下标访问

      例如定义为map<char, int> mp的map来说,可以直接使用mp['c']的方式来访问对应的整数。

    2. 通过迭代器访问

      map<typename1, typename2>::iterator it;,因为 map 的每一对映射都有两个 typename,这决定了必须能通过一个 it 来同时访问键和值。事实上,map可以使用it->first来访问键,it->second来访问值。

  4. 延伸

    map 的 键和值是唯一的(一对一),而如果需要一个键对应多个值(一对多),就只能用multimap。C++11 标准中还增加了unordered_map,以散列代替 map 内部的红黑树实现,使其可以只处理映射而不按key值排序,速度比 map 快得多。


<queue>

队列,先进先出。

  1. queue的定义

    queue<typename> name;

  2. queue常用函数

    1. push(x):将 x 进行入 队尾
    2. front()back():分别获得队首和队尾元素
    3. pop():令队首元素出队
    4. empty()检测 queue 是否为空
    5. size():返回队列内元素个数
  3. queue容器内元素的访问

    由于队列是一种先进先出的限制性数据结构,因此只能通过front()来访问队首元素,back()访问队尾元素

  4. queue的常见用途

    当需要实现**广度优先搜索(BFS)**时,可以不用手动实现一个队列,以提高程序的准确性。需要注意的时是,使用front()pop()函数之前,必须用empty()判断队列是否为空,否则可能因为队空而出现错误。

    延伸:STL的容器中还有两种跟队列有关:

    • 双端队列deque首尾皆可插入和删除的队列。

    • 优先队列priority_queue:使用实现的默认当前队列 最大元素置于队首的容器。

priority_queue
  1. priority_queue的定义

    priority_queue<typename> name;

  2. priority_queue常用函数

    1. push(x):将 x入队,时间复杂度为O(logN)
    2. top():获得队首(即堆顶)元素
    3. pop():令队首元素(即堆顶)元素出队,时间复杂度为O(logN)
    4. empty():检测优先队列是否为空
    5. size():返回优先队列内元素个数
  3. priority_queue容器内元素的访问

    只能通过top()函数访问队首元素(优先级最高的元素)

  4. priority_queue元素优先级的设置

    1. 基本数据类型的优先级设置

      下列两种优先队列的定义是等价的(以int型为例)

      priority_queue<int> q;
      priority_queue<int, vector<int>, less<int> > q;
      • vector<int>:用来承载底层数据结构—堆的容器
      • less<int>:表示数字大的优先级越大(默认优先级);greater<int>即为数字小的优先级越大

      因此,如果想让最小的元素放在队首,需要如下定义:

      priority_queue<int, vector<int>, greater<int> > q;

    2. 结构体的优先级设置

      比如定义水果的结构体:

      struct fruit {
      	string name;
          int price;
      }

      现在希望按水果价格高的为优先级高,就需要重载小于号<

      • 方式一:

        struct fruit {
            string name;
            int price;
            friend bool operator < (fruit f1, fruit f2) {
                return f1.price < f2.price; //水果价格高的为优先级高
                // return f1.price > f2.price; //水果价格低的为优先级高
            }
        };

        其中,friend友元bool operator < (fruit f1, fruit f2)<进行了重载。此时就可以直接定义fruit类型的优先队列,其内部就是以水果价格高的为优先级高priority_queue<fruit> q;

      • 方式二:将重载的函数写在结构体外

        struct cmp {
            bool operator () (fruit f1, fruit f2) {
                return f1.price > f2.price;
            }
        }
        
        priority_queue<fruit, vector<fruit>, cmp> q;

      即便是基本数据类型或者其他STL容器(如 set)也可以通过同样的方式来定义优先级。如果结构体内的数据较为庞大,建议使用引用来提高效率

      friend bool operate < (const fruit &f1, const fruit &f2) {
          reutrn f1.price > f2.price;
      }
      //或如下
      bool operator () (const fruit &f1, const fruit &f2) {
          return f1.price > f2.price;
      }
  5. priority_queue的常见用途

    可以解决一些贪心问题,也可以对 Dijkstra 算法进行优化(因为优先队列的本质是堆)。需要注意的时是,使用top()函数之前,必须用empty()判断队列是否为空,否则可能因为队空而出现错误。


<stack>

  1. stack的定义

    stack<typename> name;

  2. stack常用函数

    1. push(x):将 x 压入栈
    2. top():获得栈顶元素
    3. pop():弹出栈顶元素
    4. empty():检测 stack 是否为空
    5. size():返回 stack 内元素的个数
  3. stack容器内元素的访问

    只能通过top()函数访问栈顶元素

  4. stack的常见用途

    stack 用来模拟实现一些 递归,防止程序对栈内存的限制而导致程序运行出错。对有些题目来说,如果用普通的函数进行递归,一旦递归层数过深,则会导致程序运行崩溃。如果用栈来模拟递归算法的实现,则可以避免这一方面的问题


<utility>

pair

当想要将两个元素绑在一起作为一个合成元素,又不想因此定义结构体时,使用pair可以很方便地作为一个替代品,即 pair 可以看作 内部有两个元素 的结构体

  1. pair的定义

    注意:因为 映射map 的内部实现中涉及 pair,因此添加 map头文件 时会自动添加 utility头文件,因此,记不住 utility头文件,则可以用 map头文件 来代替

    pair 有两个参数:pair<typeName1, typeName2> name;

    • 如果想在定义 pair 时进行初始化,只需要跟上一个小括号,填写两个初始化元素即可:

      pair <string, int> p("haha", 5);

    • 如果想临时构建一个 pair

      • pair<string, int>("haha", 5)
      • 使用自带的make_pair函数:make_pair("haha", 5)
  2. pair中元素的访问

    pair 中只有两个元素,分别是firstsecond,只需要按 正常结构体的方式 访问即可。

  3. pair常用函数

    比较操作数

    两个 pair 类型数据可以直接使用比较符比较大小,比较规则是先以first的大小作为标准,first相等时去比较second的大小

  4. pair的常见用途

    • 代替二元结构体及其构造函数,节省编码时间

    • 作为map键值对来进行插入:

      map<string, int> mp;
      mp.insert(make_pair("heihei", 5));
      mp.insert(pair<string, int>("haha", 10));

数组

  1. 一维数组初始化

    如果数组没有初始化,数组中每个元素为随机数。一维数组的初始化,未被赋初始值的元素将默认初始化为0,因此,如果想要给整个数组初始化为0,只需第一个元素初始化为0即可。int a[10] = {0};(不适用C语言)

  2. 二维数组初始化

    二维数组初始化需要按第一维的顺序,依次用大括号给出第二维初始化的情况,未被赋初始值的元素将默认初始化为0

    int a[4][2] = {{3}, {}, {8, 4}}; //第二行使用大括号跳过
    /**
    数组初始化为:
    3 0
    0 0
    8 4
    0 0
    */
  3. 如果数组大小较大(大概$10^6$级别),需要定义在主函数外(即全局变量)

    否则程序会异常退出(局部变量来自系统栈,允许申请空间较小;全局变量来自静态存储区,允许申请的空间较大)

  4. 对数组中每一个元素赋相同的值

    需要#include <cstring>

    void* memset(数组名, 值, sizeof(数组名));

    memset 按字节赋值,即对每个字节赋同样的值,组成int型的4个字节就会被赋成相同的值。故建议只用于赋 0或 -1(0的二进制补码为全0,-1的二进制补码为全1),不易出错。

    如果要对数组赋其他数字(如 1),则使用 fill函数(执行速度比 memset 慢)


字符串

字符数组

  • 输入

    • #include <cstdio>
      
      
        - `scanf("%s", str);` 识别**空格或换行**作为输入结束,且**空格或回车符会留在缓冲区**
      
        - `char c = getchar();` 能够读入**空格和换行符**
      
        - `gets(char* str);` 识别**换行**作为输入结束,且**回车符会被舍弃,不在缓冲区**
      
          因此,**scanf一个输入后,如果要使用gets,需要先用 getchar 接收scanf后的空格或换行符**。
        
          另外,**PAT使用C++提交时**,使用`gets()`函数会出现**编译错误**,建议使用C++函数。
        
      - ```c++
        #include <iostream>
        using std::cin;
      - `cin >>` - `cin.getline(数组名称, 数组大小)`
      char str[100];
      /*
      指定最多读入 9 个字符,超出即报错
      (实际数组最多能存放99个字符,空字符\0 占用一个字符位)
      */
      cin.getline(str, 10);
  • 输出

    • #include <cstdio>
      
      
        - `printf(str);` 
        - `putchar(char c);`
        - `puts(char* str);` 输出数组内容后,**紧跟一个换行**
      
      - ```c++
        #include <iostream>
        using std::cout;
      - `cout <<`
  • 字符数组的存放方式

    字符数组的末尾都有一个 空字符\0(即NULL),表示存放的字符串的结尾。空字符\0getsscanf输入字符串时,会自动添加在输入的字符串后面,并占用一个字符位putsprintf就是通过识别\0作为字符串的结尾进行输出

    • 空字符\0占用一个字符位,因此字符数组的长度一定要比实际存储字符串的长度 至少多1
    • 如果使用getchar()输入字符串,一定要在每个字符串后加入\0,否则printf和puts输出字符串会因无法识别字符串末尾而输出一大堆乱码

C++ 的标准库类 string

#include <string>
using std::string;

若引用了<iostream>头文件,创建string对象时,无须引用<string>,因为<iostream>有对std::string的间接引用。但时要对string对象运用相关的函数操作,仍须引用<string>

  • 输入一整行

    getline(cin, str)

  • 比较字符串大小

    • str1.compare(str2)

      按字典顺序(顺序越靠后,越大),返回两个字符串大小的比较


<cstring>

  1. strlen(str)

    得到字符数组中第一个\0前 的字符个数

  2. strcmp(str1, str2)

    按字典顺序(顺序越靠后,越大),返回两个字符串大小的比较结果:

    • str1 < str2,返回一个负整数(不同编译器处理不同,不一定是 -1)
    • str1 == str2,返回一个0
    • str1 > str2,返回一个正整数(不同编译器处理不同,不一定是 +1)
  3. strcpy(str1, str2)

    把 str2 复制给 str1,包括结束符\0

  4. strcat(str1, str2)

    把 str2 拼接到 str1 后面


字符串与数字的相互转换

C语言

方法一:
#include <cstdlib>

字符串 转为 数字

  • atoi(str):将字符串转为 int型
  • atol(str):将字符串转为 long long型
  • atof(str):将字符串转为 double型

方法二: sscanf 与 sprintf

如果想从屏幕输入 int型变量n 并将 n 输出到屏幕:

scanf("%d", &n);
printf("%d", n);
//其实可以表示成如下
scanf(screen, "%d", &n);
printf(screen, "%d", n);

sscanfsprintf的格式如出一辙,只是把screen换成了字符数组

sscanf(str, "%d", &n); //将字符数组str中的内容以"%d"格式写到n中
sprintf(str, "%d", n); //把n以"%d"的格式写到str数组中

例:

#include <cstdio>

int main() {
    int n;
    double db;
    char str[100] = "2048:3.14,hello", str2[100];
    /*
    从字符串读取格式化输入
    使得 n = 2048, db = 3.14, str2 = hello
    */
    sscanf(str, "%d:%lf,%s", &n, &db, str2);
    n = 12;
    db = 3.1415;
    str2[100] = "good";
    /*
    发送格式化输出到字符串
    使得 str = "12:3.14,good"
    */
    sprintf(str, "%d:%.2f,%s", n, db, str2);
    return 0;
}

C++:

数字 转为 字符串

#include <string>
using namespace std;

string str = to_string(num);
len = str.length();

数组作为函数参数

  • 参数中数组的第一维不需要填写长度(如果是二维数组,第二维需要填写长度)
  • 在函数中对数组元素的修改 等同于 对原数组元素的修改(与普通局部变量不同)

例:

#include <cstdio>

void change(int a[], int b[][5]) {//参数数组 第一维不需要填写长度,第二维需要填写长度
    a[0] = 1;
    a[1] = 3;
    a[2] = 5;
    b[0][0] = 1;
}

int main() {
    int a[3] = {0}; //不适用C语言
    int b[5][5] = {0}; //不适用C语言
    change(a, b);
    for (int i = 0; i < 3; i++) {
        printf("%d\n", a[i]);
    }
    /*
    输出结果为:
    1
    3
    5
    */
    return 0;
}
  • 数组不允许作为返回类型出现,想要返回数组,只能通过参数返回

指针

  • C语言习惯于把*放在变量名之前:int *p;(声明多个指针时,易统一)

  • C++习惯把*放在数据类型之后:int* p;

  • 地址赋给p而不是*p

    int a;
    int* p;
    p = &a; //等价于 int* p = &a;
  • 指针的加减法

    • 两个指针相减,得到两个地址的距离
    • p + 1指 p所指的int型变量 的下一个int型变量地址
    • 指针支持自增和自减操作

指针变量作为函数参数

例子:交换两个数

只有在获取地址的情况下对元素进行操作,才能真正修改变量

#include <cstdio>

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

int main() {
    int a = 1, b = 2;
    int *p1 = &a, *p2 = &b;
    swap(p1, p2);
    return 0;
}

错误写法:

void swap1(int* a, int* b) {
    int* tmp;
    *tmp = *a;
    *a = *b;
    *b = *tmp;   
}
/*
tmp未初始化,存放的地址很大概率指向系统工作区间,不能修改,故后续报错
初始化tmp即可
*/
void swap2(int* a, int* b) {
    int x;
    int* tmp = &x;
    *a = *b;
    *b = *tmp;
}

引用

引用的含义

引用是C++的语法,在编程时极为实用。如果要修改传入函数的参数,且不使用指针,可以通过C++的引用。引用不产生副本,只是给原变量起个别名

引用的方法:在函数的参数变量名前加个&即可。要将**引用&取地址运算符&**区分开来,引用并不是取地址的意思

#include <cstdio>

void change(int &x) {
    x = 1;
}

int main() {
    int x = 10;
    change(x);
    printf("%d\n", x); //输出1
    return 0;
}

指针的引用

例子:交换两个数

//错误写法
void swap(int* a, int* b) {
    int* tmp = a;
    a = b; //交换的地址 是 值传递,不会修改原指针的地址
    b = tmp;
}

通过引用实现交换

#include <cstdio>

void  swap(int* &a, int* &b) { //通过引用实现交换
    int* tmp = a;
    a = b;
    b = tmp;
}

int main() {
    int a = 1, b = 2;
    int *p1 = &a, *p2 = &b;
    swap(p1, p2); //不能写成 swap(&a, &b);
    return 0;
}

引用是产生变量的别名,常量不可使用引用。故上述

swap(p1, p2); //不能写成 swap(&a, &b);


结构体(struct)的使用

访问结构体内的元素

假设p是一个指向结构的指针,可以用**p->结构成员的形式(等价于(*p).结构成员)**,引用相应的结构成员。


申请动态内存空间

如需要定义链表的结点时。

C语言有mallocfree函数用于内存的申请和释放,C++有newdelete运算符用于内存的申请和释放。推荐使用C++进行内存的申请和释放(用法更简洁)

  • 申请内存空间 — new运算符:

    使用new + 类型名即可分配一块该类型的内存空间,返回申请的同变量类型的指针typename* p = new typename;

    示例:

    int* p = new int;
    node* p = new node;

    通常情况下,内存空间的申请不会失败。失败一般发生在使用new申请了较大的动态数组,如:int* p = new int[1000000];申请失败会发生异常

  • 释放内存 — delete运算符:

    需要释放的内存空间的指针变量为参数:delete(p);,执行之后,指针变量p没有消失,只是指向了空地址NULL

输入输出

C语言 C++ 比较
scanf函数
printf函数
cin
cout
cin 和 cout 无需指定输入输出格式
消耗的时间比 scanf 和 printf 多得多

头文件

内容 C语言 C++
输入输出库 #include <stdio.h> #include <cstdio>
#include <iostream>
数学函数 #include <math.h> #include <cmath>
字符串有关函数 #include <string.h> #include <cstring>

变量类型

布尔型变量

C语言 C++ 比较
#include <stdbool.h> 可直接使用 true(存储时为1)
false(存储时为0)

字符串

内容 C语言 C++
表示方法 通过 字符数组 表示 通过 string类 表示
字符串长度的表示 #include <string.h>
strlen(str)
#include <string>
str.length()
字符串拼接 #include <string.h>
strcat(str1, str2); //把str2拼接到str1之后
str1 += str2;

排序函数

  • C语言 — qsort
#include <stdlib.h>

int cmp(const void *a, const void *b) {
    return *(int *)a - *(int *)b; //升序
}

qsort(排序数组, 元素数量, 每个元素的大小(可用sizeof获得), 比较函数cmp);
  • C++ — sort
#include <algorithm>

bool cmp(int a, int b) {
    return a > b; //降序
}

sort(首元素地址, 尾元素地址的下一个地址, 比较函数cmp(非必填));
cmp函数的区别 C语言 C++
返回值类型 int bool
排序的判断 返回值 > 0, a 将被排在b后面;
返回值 < 0, a 将被排在b前面;
默认升序
返回值为true时,a将被排在b前面
比较方式 元素相减
不能用$>$、$<$比较符(返回无负值
$>$、$<$比较符

qsort函数的使用需要运用指针,且写法上没有sort函数简洁。sort函数根据具体情形使用不同的排序方法,效率较高,在实现中规避了经典快速排序中可能出现的会导致实际复杂度退化到$O(n^2)$的极端情况

因此更推荐使用C++的sort函数进行代码编写。


申请动态内存空间

内存泄露是指申请到的内存空间在使用过后没有释放,导致一些程序内存消耗过快,最后无内存可分配的情况。一般考试中,分配的内存空间在程序结束时即被释放,因此即便不是放空间,也不会产生什么影响,并且内存大小一般也足够一道题的使用。但是从编程习惯上,需要养成即时释放空间的习惯

  • C语言

    <stdlib.h>

    • 申请内存空间 — malloc函数:

      需要申请的内存空间为参数,返回指向这块空间的指针,因为返回的指针是void*型,因此需要强制转换为对应类型typename* p = (typename*)malloc(sizeof(typename));

      示例:

      int* p = (int*)malloc(sizeof(int));
      node* p = (node*)malloc(sizeof(node));

      通常情况下,内存空间的申请不会失败。失败一般发生在使用malloc申请了较大的动态数组,如:int* p = (int*)malloc(1000000 * sizeof(int));申请失败会返回空指针NULL

    • 释放内存 — free函数:

      需要释放的内存空间的指针变量为参数:free(p);,执行之后,指针变量p没有消失,只是指向了空地址NULL

  • C++

    • 申请内存空间 — new运算符:

      使用new + 类型名即可分配一块该类型的内存空间,返回申请的同变量类型的指针typename* p = new typename;

      示例:

      int* p = new int;
      node* p = new node;

      通常情况下,内存空间的申请不会失败。失败一般发生在使用new申请了较大的动态数组,如:int* p = new int[1000000];申请失败会发生异常

    • 释放内存 — delete运算符:

      需要释放的内存空间的指针变量为参数:delete(p);,执行之后,指针变量p没有消失,只是指向了空地址NULL

准备

由于PE方式只适用于安装windows,因此选择常规的制作启动U盘进行Ubuntu的安装。

操作系统镜像下载(桌面版,文件名后缀 .iso.torrent)

3G及以上空间的U盘/移动硬盘(用于装载系统镜像)

制作启动U盘

  • 方式一:Windows 10 可以直接打开 iso镜像文件,不用下载任何工具

    1. 格式化U盘

    2. 双击ISO文件,然后选中打开的所有文件,复制到U盘即可

  • 方式二:下载U盘制作制作工具Rufus(无需安装,可直接运行)

    1. 选择设备(需要被制作的U盘/移动硬盘)

      • 只有一个外接设备时会自动读取
      • 如果外接设备是移动硬盘,需要显示高级设备选项 — 显示USB外置硬盘
    2. 选择操作系统镜像

    3. 分区类型理论上(联想Y480不知道为什么无法通过UEFI成功安装))

      硬盘格式与引导方式、MBR与GPT、UEFI 与LEGACY bios的区别

      • 若选择GPT,之后系统安装时选择UEFI启动推荐

      • 若选择MBR,之后系统安装时选择BIOS启动,否则报错(该模式一定能够安装成功)

    4. 其余选项默认,点击开始,即可制作启动U盘

    Rufus制作启动U盘

安装系统

  1. 重启电脑,进入选择启动方式界面(联想笔记本:F12;惠普笔记本:F9)

  2. 选择启动U盘

    • 想要安装系统的硬盘的格式为GPT,选择UEFI启动,即 EFI USB Device
    • 启动U盘分区类型为MBR,选择BIOS启动,即 选择对应的U盘
  3. 欢迎 — 中文 — 安装Ubuntu

  4. 键盘布局 — 汉语

  5. 无线 — 不连接

  6. 更新和其他软件 — 最小安装

  7. 安装类型 — 其他选项 — 进行分区

    硬盘大小110GB

    • UEFI启动:

      空间大小 主分区/逻辑分区 类型
      200MB 逻辑分区 EFI
      8GB
      (和内存大小一致)
      主分区 swap(交换)
      40GB 逻辑分区 ext4
      挂载至 “/”
      剩余空间 逻辑分区 ext4
      挂载至 “/home”
    • BIOS启动:

      空间大小 主分区/逻辑分区 类型
      200MB 主分区 biosxx
      8GB (和内存大小一致) 主分区 swap(交换)
      40GB 逻辑分区 ext4 挂载至 “/”
      剩余空间 逻辑分区 ext4 挂载至 “/home”
  8. 完成安装,根据提示重启即可(可拔去启动U盘/硬盘,避免再次从启动U盘启动)


将 从主服务器下载 更换为 国内镜像站点下载

​ 显示应用程序 - 软件和更新 - Ubuntu软件 - 下载自 - 其他站点 - 选择最佳服务器(自动选择最合适的站点)


更新系统文件

打开终端的快捷键:Ctrl+Alt+T

sudo apt update
sudo apt upgrade

获得各种开发工具

sudo apt-get install build-essential

  • 安装文字编辑器vim浏览器chromium

    sudo apt-get install vim
    sudo apt-get install chromium-browser
  • 树视图

    sudo apt-get install tree

0%