Linux_Shell编程

发表于2022-02-15更新于2025-07-15阅读次数

内容

  1. 编译型语言
  2. 解释器
  3. 变量：本地变量、环境变量、参数变量
  4. 条件：字符串判断、算术、文件测试
  5. 控制结构：循环、case
  6. 函数
  7. 脚本调用脚本，c语言调用脚本
  8. awk，sed

环境变量

类型 语法 注意点
赋值 var=value 不能有空格
引用 $var 用双引号包裹是读var的值，用单引号包裹是$var这4个字符。
删除 unset var 不要加$符
输入 read var1 var2 ... 按顺序写入变量，类似于scanf，以回车或者空格分隔
列出所有变量 set
全局化变量 export var

特殊变量

都需要搭配$使用

特殊变量 定义 注意点
? 前一命令的退出状态 0代表成功、真；其他非0数代表失败、假的某一状态
$ 当前Shell的进程ID echo $$才能输出
! 后台运行命令的进程ID
1 ~ 9 当前脚本的第1到9个参数
_ 上一个命令的最后一个参数 比如在命令行敲入ls -a，则echo $_输出-a
PS1 Shell主提示符
PS2 Shell次提示符

字符串处理

  1. 注意双引号、单引号的功能，双引号引起主要是为了消除空格的影响，保留转义效果；而单引号是把所引的内容原封不动地保留。
1
2
3
4
5
6
a="xcg"
str="$a"	#把a的值赋给了str
echo "$str" #实际输出: xcg

str='$a'	#把"$a"这个 原本的字符串 赋给了str
echo "$str"	#实际输出: $a
  1. 如果想把某一个命令的运行结果作为字符串返回给str，则有两种方式。
    1. $( )
1
str=$(ls)	#把当前目录的文件信息字符串赋给str
2. 反引号

1
str=`ls`	##把当前目录的文件信息字符串赋给str

export

在当前shell可以再启动一个shell。如果我们在之前的shell中定义了局部变量，比如var=hello，在新启动的shell是看不到的。如果要新shell看到，需要export var。
其实新开的这个shell是在之前的shell新运行的一个程序。他俩是不同的进程。同理，如果想让其他进程也能看到之前shell的环境变量，此时就需要export。

第一行注释

第一行需要添加注释，指示使用哪个shell程序运行该脚本。

1
2
3
#! /bin/sh

# ...

C语言编程main函数的参数 - 结合环境变量

1
2
3
4
5
6
7
8
9
10
// c.c
#include <stdio.h>
int main (int ac, char * av[])
{
    if (ac > 1)
    {
        printf("%s\n", av[1]);
    }
    return 0;
}

运行结果：

1
2
mrcan@ubuntu:~$ ./c.out var
var

如上，var是命令中的参数，程序输出了var这个参数名。

1
2
3
mrcan@ubuntu:~$ VAR=ThisIsMyVar
mrcan@ubuntu:~$ ./c.out $VAR
ThisIsMyVar

如上，也可以先定义环境变量VAR。然后再通过$VAR传到main函数。

结合重定向 - 把另一个程序的结果作为参数传到main

结合《Linux_重定向》一文中的知识。
可以利用“命令代换”（形如$(./a.out)）。

1
2
3
4
mrcan@ubuntu:~$ ./a.out 
C Program!  # 这是a.out的执行结果
mrcan@ubuntu:~$ ./c.out $(./a.out)
C           # 把a.out的输出传给了c.c的main函数

如上，把a.out的输出结果通过$(a.out)传到了c.c的main函数。

系统中的小程序，也可以作为命令代换的参数。

1
2
pwd # 输出结果 /home/mrcan
ls $(pwd)

输出结果：

1
2
3
4
5
6
mrcan@ubuntu:~$ pwd
/home/mrcan
mrcan@ubuntu:~$ ls $(pwd)
a.c    b.out  c.out    Documents  Music     Public     test.cpp
a.out  build  c.sh     Downloads  packages  Templates  test_muduo.cpp
b.c    c.c    Desktop  mprpc      Pictures  test       Videos

Operator - 操作符

Equal Operator

  1. = string。注意，=前后必须有空格分隔。不然就成了环境变量赋值了。
  2. != string
  3. -eq numeral
  4. -ne numeral
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
```
## Logical Operator
1. `-a`：and
2. `-o`：or
3. `!`：not

## Relation Operator
1. `-gt`：greater than
2. `-ge`：greater equal
3. `-lt`：less than
4. `-le`：less equal
# if语句
```sh
#! /bin/sh
VAR1="COMPUTER"
if [ $VAR! = "COM" ]
then
    echo "Y"
else
    echo "N"
fi

注意点：

  1. =前后有无空格的行为是不一样的。
  2. 中括号的前后最好也留上空格，避免无法分辨。
1
2
3
4
5
6
7
8
9
#! /bin/sh
VAR1="COMPUTER"
 if [ $VAR1="COM" ]
# if (test $VAR1="COM")
then
    echo "Y"
else
    echo "N"
fi

以上程序输出Y，即使VAR1不是"COM"。就是因为=前后无空格。

  1. if后跟的[ ... ]相当于：(test ...)

循环

要注意的是对计数变量的处理

有2种方式：

  1. let
1
2
i=1
let "i+=1"
  1. (( ))，双括号中是想要执行的命令/表达式，可以用$取表达式的值。
1
2
i=1
a=$((i++))
  1. 反引号：`expr …`
1
2
3
i=1
a=`expr $i \* 2`	#*在脚本中有其他意义，需要加\转义为'*'，在此表示乘号
i=`expr $i + 1`		#此方式i自增的方法

for

for循环的次数由in后面值的数目决定

1
2
3
4
5
6
7
8
9
10
for i in 1 2 3
do
	echo i=$i
	sleep 1
done

for name in $(ls)
do
	echo "filename: $name"
done

$@

1
2
3
4
5
#! /bin/sh
for x in $@
do
    echo $x
done
1
./test.sh 1 2 3 4

输出结果

1
2
3
4
1
2
3
4

while

判断条件，满足则循环执行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#死循环示例
while [ 1 ]
do
	echo "run"
	sleep 1
done
#死循环输出输入的内容，直到输入end
while true
do
	echo "input"
	read line
	if [ "$line" = end ]
	then
		break
	fi
	echo "line=$line"
done
#输出0-9
while [ "$i" -lt 10 ]
do
	echo "i=$i"
	#let "i+=1"
	#((++i))
	i=`expr $i + 1`
done

until

条件没满足时，循环执行；一旦条件满足则退出。

1
2
3
4
5
6
7
#本地找file.txt文件，隔一秒找一遍，直到找到，退出。
until [ -f file.txt ]
do
	echo "not find file.txt"
	sleep 1
done
echo "find file.txt"

read

read命令 -n(不换行) -p(提示语句) -n(字符个数)-t(等待时间) -s(不回显)

case

结合正则表达式的示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
while true
do
    echo "input:"
    read line
    case "$line" in
        yes | Y) 	echo "this is yes";;
        no	| N)	echo "this is no";;
        end)		break;;
        *)			echo "$line";;
    esac
done
#可以搭配正则表达式使用。
read line
case "$line" in
    [Yy][Ee][Ss] | [Yy])echo "this is yes";;
    [Nn][Oo] | [Nn])	echo "this is no";;
    end)				break;;
    *)					echo "$line";;
esac

练习：把多行IP地址转换为10进制

  1. 先生成n行（192.168.0.1开始）
  2. 对n个ip地址进行转换，转换后的数据放在IPint.txt文件内。

生成n行IP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#! /bin/sh
# $1: nums of ip address
FILE="IPs.txt"
I=1
if [ -e $FILE ]
then
    rm $FILE
fi

while [ $I -le $1 ]
do
    echo "192.168.0.$I" >> $FILE
    I=$(expr $I + 1)
done
1
2
3
4
5
6
7
8
9
10
11
12
mrcan@ubuntu:~$ ./generateIP.sh 10
mrcan@ubuntu:~$ cat IPs.txt 
192.168.0.1
192.168.0.2
192.168.0.3
192.168.0.4
192.168.0.5
192.168.0.6
192.168.0.7
192.168.0.8
192.168.0.9
192.168.0.10

什么是IP地址的10进制？

不是简单的每个分段的10进制（192/168/0/1这些）
而是要一个32位无符号整型数十进制表示的：从32个0到32个1的这之间的某一个数。
其实可以直接把IP地址看作32位2进制数，来转换、计算为其十进制值。
但是过程不太美观。

如以上过程，太复杂！

有可读性更好的方法：把IP地址看作4位256进制数。来转换、计算为其十进制值。
IPv4地址每一个分段的数的大小范围：0到255，因此现在形式下的IPv4每位数属于256进制，是用.分开了。

如上，很香！

那么我们平时说的“一百二十三”，这个3位数，就可以看作：1.2.3，每一个分段的大小范围是0到9，属于10进制。怎么计算其10进制数？power是10，

\begin{align} 1 * 10 ^ 2 &= 100 \\ 2 * 10 ^ 1 &= 20 \\ 3 * 10 ^ 0 &= 3 \\ 100 + 20 + 3 &= 123 \end{align}

那么，4位256进制，转为10进制的算法：

\begin{align} 192 * 256 ^ 3 &= a\\ 168 * 256 ^ 2 &= b\\ 0 * 256 ^ 1 &= c\\ 1 * 256 ^ 0 &= d\\ result &= a + b + c + d \end{align}

编写转换进制

需要切分IP地址的4段。
用到了cut：见《[[Linux_cut命令]]》

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#! /bin/sh
INPUT=IPs.txt
OUTPUT=IPint.txt

SUM=0

if [ -e $OUTPUT ]
then
    rm $OUTPUT
fi

cat $INPUT |           # 精髓
while read IP
do
    I=1
    SUM=0
    while [ $I -le 4 ]
    do
        NUM=$(echo $IP | cut -d. -f$I)
        case $I in
            1)
            SUM=$(expr $NUM \* 256 \* 256 \* 256)
            ;;
            2)
            SUM=$(expr $SUM + $NUM \* 256 \* 256)
            ;;
            3)
            SUM=$(expr $SUM + $NUM \* 256)
            ;;
            4)
            SUM=$(expr $SUM + $NUM)
            ;;
        esac
        I=$(expr $I + 1)
    done
    echo $IP $SUM >> $OUTPUT
done

输出结果：

1
2
3
4
5
6
7
8
9
10
192.168.0.1 3232235521
192.168.0.2 3232235522
192.168.0.3 3232235523
192.168.0.4 3232235524
192.168.0.5 3232235525
192.168.0.6 3232235526
192.168.0.7 3232235527
192.168.0.8 3232235528
192.168.0.9 3232235529
192.168.0.10 3232235530

注意点

  1. 没有+=这个形式
  2. expr 的设计中没有包含幂运算符（如 ** 或 ^），因此只能用num \* 256 \* 256 \* 256这样连乘。
  3. case结束别忘记esac

知识点

程序的精髓在于，怎么循环read读取一个文件中的每一行，我们用cat $INPUT | 管道传入read，再给read加一层循环，这样，只要管道中还有内容，while循环就不会停止。

函数

三个问题：1、如何传参的问题；2、函数返回值如何获得；3、如何看待函数内定义的变量

特点

  1. shell脚本中的函数没有声明，需要直接定义在最前面。
  2. 调用函数不用加圆括号，而是只有函数名
1
2
3
4
5
fun()
{
	echo "fun run"
}
fun

参数

注意$#/$1/$2在函数中、函数外的区别：在函数中代表函数的参数；而在函数外代表此shell脚本的参数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
fun()
{
	echo "fun run"
	echo "fun: \$#=$#"	# "$#"代表参数个数
	echo "fun: \$1=$1"	# "$1"表示该函数的第一个参数
	echo "fun: \$2=$2"
}
fun hello 123
#此处就要注意与上面函数中$#/$1/$2的区别了，在函数中代表函数的参数；而在函数外代表此shell脚本的参数。
echo "my.sh: \$#=$#"
echo "my.sh: \$1=$1"
echo "my.sh: \$2=$2"

# 在外部执行脚本时：
# ./my.sh xcg test
	# 输出:
        # fun: $#=2
        # fun: $1=hello
        # fun: $2=123
        # my.sh: $#=2
        # my.sh: $1=xcg
        # my.sh: $2=test

返回值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
my_add()
{
	if [ "$#" -ne 2 ]	# -ne : not equal
	then
		echo "参数有误"
		return 0
	fi
	res=`expr $1 + $2`
	return $res
}
res=my_add
echo "$res"
# 或者写为
	# my_add
	# echo "$?"
		# "$?"代表上一行语句执行的结果(返回值)。
# 如果想保存返回值，可以：
	# my_add 123 234
	# result=$?
		# 如果连续写两行"$?"，则第二行的结果是0，因为"$?"的执行结果是0，代表执行成功。

变量生存期问题

函数中的变量可能污染到函数外

1
2
3
4
5
6
7
8
9
10
11
my_test()
{
	str=hello
	echo "my_test:str=$str"
}
my_test
echo "str=$str"
# 打印结果
	# my_test:str=hello
	# str=hello
# 由此可见，函数中的变量污染到了函数外。

此问题的原因：
脚本程序的概念并不存在作用域的概念。所以，函数中定义、赋值str语句执行后，不管是函数中，还是bash解释器，也就都存在str这个变量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
my_test()
{
	str=hello
	echo "my_test:str=$str"
}
test2()
{
	echo "test2:str=$str"
}
my_test
echo "str=$str"
test2
# 执行结果
	# my_test:str=hello
	# str=hello
	# test2:str=hello
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
my_test()
{
	str=hello
	echo "my_test:str=$str"
}
test2()
{
	echo "test2:str=$str"
}

echo "str=$str"
test2
my_test
# 执行结果
	# str=
	# test2:str=
	# my_test:str=hello
# 在执行my_test前，还没有str变量给出，所以，test2和函数外的str都打印为空

解决变量污染的方法

1、可以通过unset在用完变量后，销毁之。

1
2
3
4
5
6
7
8
9
10
11
my_test()
{
	str=hello
	echo "my_test:str=$str"
	unset str
}
my_test
echo "str=$str"
# 执行结果
	# my_test:str=hello
	# str=

2、可以在变量名前加local

1
2
3
4
5
6
7
8
9
10
11
str="abcdef"
my_test()
{
	local str=hello
	echo "my_test:str=$str"
}
my_test
echo "str=$str"
# 执行结果
	# my_test:str=hello
	# str=abcdef

注意事项：unset对于local变量，只会局部地销毁这个变量，不影响全局的同名变量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#################### 程序1
str="abcdef"
my_test()
{
	local str=hello
	echo "my_test:str=$str"
	unset str
}
my_test
echo "str=$str"
# 执行结果
	# my_test:str=hello
	# str=abcdef

#################### 程序2
str="abcdef"
my_test()
{
	str=hello
	echo "my_test:str=$str"
	unset str
}
my_test
echo "str=$str"
# 执行结果
	# my_test:str=hello
	# str=

脚本间的调用

1
2
3
4
5
6
7
8
9
10
11
12
13
###################### b.sh
#!/usr/bin/bash
echo "b.sh run pid=$$"	# "$$"代表本bash脚本的pid
./d.sh
exit 0
###################### d.sh
#!/usr/bin/bash
echo "d.sh run pid=$$"	# "$$"代表本bash脚本的pid
exit 0
###################### 外部执行: ./b.sh
###################### 执行结果:
        # b.sh run pid=5346
        # d.sh run pid=5347

脚本间变量的传递问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
###################### b.sh
#!/usr/bin/bash
echo "b.sh run pid=$$"	# "$$"代表本bash脚本的pid
mystr=hello
echo "b.sh mystr=$mystr"
./d.sh
exit 0
###################### d.sh
#!/usr/bin/bash
echo "d.sh run pid=$$"	# "$$"代表本bash脚本的pid
echo "d.sh mystr=$mystr"
exit 0
###################### 外部执行: ./b.sh
###################### 执行结果:
        # b.sh run pid=5368
        # b.sh mystr=hello
        # d.sh run pid=5369
        # d.sh mystr=
# 注意，此时d.sh没有打印出来b.sh中的mystr，说明两个脚本程序各自运行在不同的进程空间内，变量互不污染。

为了在脚本间可以传递变量，可有以下方式

1、在一个sh中调用另一个sh时，后面加参数。但是只是能拿到值，变量名字不能通用，需要用“$1”来取出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
###################### b.sh
#!/usr/bin/bash
echo "b.sh run pid=$$"
mystr=hello
echo "b.sh mystr=$mystr"
./d.sh $mystr			#!!! 后面加参数
exit 0
###################### d.sh
#!/usr/bin/bash
echo "d.sh run pid=$$"
echo "d.sh mystr=$1"	#!!! 需要用“$1”来取出
exit 0
###################### 外部执行: ./b.sh
###################### 执行结果:
        # b.sh run pid=5380
        # b.sh mystr=hello
        # d.sh run pid=5381
        # d.sh mystr=hello

2、如果想要变量名字通用，可以export改变mystr为环境变量，因为环境变量可以被继承，所以让变量名字通用了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
##################### b.sh
#!/usr/bin/bash
echo "b.sh run pid=$$"
mystr=hello
export mystr			#export改变mystr为环境变量
echo "b.sh mystr=$mystr"
./d.sh
exit 0
###################### d.sh
#!/usr/bin/bash
echo "d.sh run pid=$$"
echo "d.sh mystr=$mystr"
exit 0
###################### 外部执行: ./b.sh
###################### 执行结果:
        # b.sh run pid=5380
        # b.sh mystr=hello
        # d.sh run pid=5381
        # d.sh mystr=hello

3、通过source。source的作用是在调用另一个脚本时，不启动另外的sh，而是在自身的解释器中去运行另一个脚本的命令。相当于内联展开于此，所以原来的变量可以复用。但是问题的隐患很多，因为调用的脚本会对原来的脚本造就的环境造成影响。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
##################### b.sh
#!/usr/bin/bash
echo "b.sh run pid=$$"
mystr=hello
echo "b.sh mystr=$mystr"
. ./d.sh	# 前面的“.+空格”中的“.”即代表source
# source ./d.sh
exit 0
###################### d.sh
#!/usr/bin/bash
echo "d.sh run pid=$$"
echo "d.sh mystr=$mystr"
exit 0
###################### 外部执行: ./b.sh
###################### 执行结果: !!!发现pid一样！
        # b.sh run pid=5448
        # b.sh mystr=hello
        # d.sh run pid=5448
        # d.sh mystr=hello

source的作用：有时需要对当前的bash进行环境变量的初始化，可以用source(. ./xx.sh)来在本sh直接运行提前写好的配置脚本。

C程序和脚本间的调用

脚本调用C程序显而易见。

我们讨论C程序调用脚本。

1
2
3
4
5
6
#!/usr/bin/bash
echo "my.sh pid=$$"
mystr="hello^_^"
echo "mystr=$mystr"
exit 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
#include<string.h>
int main()
{
    printf("main pid=%d\n",getpid());
    execl("./my.sh","my.sh",(char*)0);
    printf("execl err\n");
    exit(0);
}
// 执行结果
	// main pid=5607
	// my.sh pid=5607
	// mystr=hello^_^
// 为什么pid一样呢？因为在main函数中exec了自身。

表面上启动的是my.sh，实际上启动的是/usr/bin/bash。

练习

  • 从键盘读取一个成绩，0~100之外的不可以。把整数值转为等级A、B、C、D。
成绩 等级
>= 90 A
>= 80 B
>= 70 C
>= 60 D
< 60 E 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#!/usr/bin/bash

while [ 1 ]; do
  printf 'please input your score:'
  read score
  if [ $score -ge 0 ] && [ $score -le 100 ]
  then
    grade=$(($score/10))
    #echo $grade
    printf 'your grade is:'
    case $grade in
      9 | 10 ) echo "A";;
      8 ) echo "B";;
      7 ) echo "C";;
      6 ) echo "D";;
      * ) echo "E";;
    esac
  else
    echo "error in your input!"
  fi
done

exit 0

测试结果：

image-20220215130731237

  • 第一题的优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#!/usr/bin/bash
printf '输入你的成绩：'
read score
case $score in
    [0-9] | [1-9][0-9] | 100)
        grade=$(($score/10))
        #echo $grade
        printf "你的成绩是$score，等级："
        case $grade in
            9 | 10 ) echo "优";;
            8 ) echo "良";;
            7 ) echo "中";;
            6 ) echo "及格";;
            * ) echo "不及格";;
        esac;;
    *) echo "error in your input!";;
esac
exit 0
  • 循环接收用户输入的学生成绩（百分制），若成绩小于60，输出“不及格”；若成绩大于等于60，输出“及格”，按Q(q)键退出。
1
2
3
4
5
6
7
8
9
10
11
#!/bin/bash
while true
do
    read -p "输入成绩：" score
    case $score in
        [Qq]) exit;;
        [0-9] | [1-5][0-9]) echo "不及格";;
        100 | [6-9][0-9])   echo "及格";;
        *)  echo "不合法，请输入0~100";;
    esac
done
  • 循环接收某门课程的成绩，计算用户已输入的最高分、最低分、平均分，按P(p)键输出计算结果，按Q(q)键退出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#!/bin/bash
min=100
max=0
sum=0
count=0
while true
do
    read -p "输入分数：" score
    case $score in
        [0-9] | [1-9][0-9] | 100)
            echo "$score 已录入"
            sum=$(($sum+$score))
            count=$(($count+1))
            if [ $score -gt $max ]
            then max=$score
            fi
            if [ $score -lt $min ]
            then min=$score
            fi;;
        [Pp])
            echo "max = $max"
            echo "min = $min"
            echo "avg = $(($sum/$count))"
            continue;;
        [Qq])   exit;;
        *)      echo "$score 不合法，请重新输入。"
    esac
done

注意

例：输入一个正整数，判断其是否为质数。正确的程序如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#!/bin/bash

read -p "请输入一个正整数：" number
[ $number -eq 1 ] && echo "$number 不是质数" && exit
for i in `seq 2 $(($number-1))`
do
    [ $[$number % $i] -eq 0 ] && echo "$number不是质数" $$ exit
done
echo "$number是质数" && exit
# 正确的测试结果：
# 	输入 1
# 	输出 1不是质数
# 正确的测试结果：
# 	输入 7
# 	输出 7是质数

其中，判断语句如[ $number -eq 1 ]必须在首尾中括号之间有空格，不然找不到命令。如下是错误的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
read -p "请输入一个正整数：" number
[$number -eq 1] && echo "$number 不是质数" && exit	#错误
for i in `seq 2 $(($number-1))`
do
    [$[$number % $i] -eq 0] && echo "$number不是质数" $$ exit #错误
done
echo "$number是质数" && exit
# 测试：
# 	输入 1
# 	输出 ./zhishu.sh: line 4: [1: command not found
# 		 1是质数
# 测试：
# 	输入 7
# 	输出 ./zhishu.sh: line 7: [1: command not found
#		./zhishu.sh: line 7: [1: command not found
#		./zhishu.sh: line 7: [3: command not found
#		./zhishu.sh: line 7: [2: command not found
#		./zhishu.sh: line 7: [1: command not found
#		7是质数

算法_递归_分治

发表于2022-02-13更新于2025-11-04阅读次数

内容

阶乘(factorial)

1
2
3
4
阶乘可递归地定义为:
fac(n) = 
	1;                 当n=1时
	fac(n-1)*n;        当n>1时

此处, fac(n-1)代表什么意思呢? 是: 1 * 2 * ... * (n-1)

代码

非递归版

1
2
3
4
5
6
7
8
9
int factorial(int n)
{
    int res = 1;
    for(int i = 1; i <= n; ++i)
    {
        res = res * i;
    }
    return res;
}

递归版

1
2
3
4
5
6
7
int factorial(int n)
{
    if(n <= 1)
        return 1;
    else
        return factorial(n - 1) * n;
}

死递归和死循环的区别

死循环

若把上面阶乘的代码, 稍做改动:

for循环中间的条件去掉 - 变为死循环

1
2
3
4
5
6
7
8
9
int factorial(int n)
{
    int res = 1;
    for(int i = 1;  ; ++i)
    {
        res = res * i;
    }
    return res;
}

但是, 死循环除了会耗费单核的CPU, 不会对内存空间产生伤害;

1
2
3
4
int main()
{
    int sum = fun(4);
}

死递归

若把上面递归版本阶乘的代码, 稍做改动, 把if判断条件改为永假:

1
2
3
4
5
6
7
int factorial(int n)
{
    if(false)
        return 1;
    else
        return factorial(n - 1) * n;
}

则递归将没有一个出口;

而且更严重的是, 由于每一次的递归调用都需要开辟栈帧, 所以不久之后栈将会溢出, 程序崩溃;

思考

就这个现象, 其实说明了背后的一些更重要的意义, 一般, 非递归算法的空间复杂度最低可为O(1), 而递归算法的空间复杂度最低为O(n), 递归的特性势必造成额外的空间;

遍历打印数组

假如有一int数组为{12,23,34}, 要求打印出来

非递归 - 能不能把它改成递归?

1
2
3
4
5
6
7
8
9
void Print_Ar(const int * ar, int n)
{
    assert(ar != NULL);
    for(int i = 0; i < n; ++i)
    {
        cout << ar[i] << " ";
    }
    cout << endl;
}//12 23 34

递归初版 - 逆序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void Print(const int * ar, int n)
{
    if(n > 0)
    {
        cout << ar[n-1] << " ";
        Print(ar, n-1);
    }
}
void Print_Ar_recur(const int * ar, int n)
{
    assert(ar != NULL);
    if(n < 1) return;//the length must > 0
    Print(ar, n);
    cout << endl;
}
int main()
{
    int ar[] = {12, 23, 34};
    int n = sizeof(ar) / sizeof(ar[0]);
    Print_Ar_recur(ar, n);
    return 0;
}//34 23 12

递归2版 - 正序-✔

看到没? 只是把5行和6行的代码调了个序, 效果就截然不同, 这就是递归的神奇之处;

当n > 0时, 将一直递归下去, 直到n等于0, 之后, 随着递归栈帧的回退, 将从0到n-1逐一打印出来;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void Print(const int * ar, int n)
{
    if(n > 0)
    {
        Print(ar, n - 1);
        cout << ar[n-1] << " ";
    }
}
void Print_Ar_recur(const int * ar, int n)
{
    assert(ar != NULL);
    if(n < 1) return;//the length must > 0
    Print(ar, n);
    cout << endl;
}
int main()
{
    int ar[] = {12, 23, 34};
    int n = sizeof(ar) / sizeof(ar[0]);
    Print_Ar_recur(ar, n);
    return 0;
}//12 23 34

总结 - 递归的范式

递归的题解有两部分组成, 将会把代码划分的清清楚楚;

  1. 第一个函数过滤掉不合法的参数, 同时作为开始调用递归的调用者;
  2. 第二个函数才是真正的递归函数;

总结 - 递归的分析

递归函数的执行分为“递推”和“回归”两个过程，这两个过程由递归终止条件控制，即逐层递推，直至递归终止条件满足，终止递归，然后逐层回归。

递归调用同普通的函数调用一样，每当调用发生时，就要分配新的栈帧（形参数据，现场保护，局部变量）, 所以, 每个栈帧中的数据都是本层独有的!；

而与普通的函数调用不同的是，由于递推的过程是一个逐层调用的过程，因此存在一个逐层连续的分配栈帧过程，直至遇到递归终止条件时，才开始回归，这时才逐层释放栈帧空间，返回到上一层，直至最后返回到主调函数。

错误版本1-不要使用后置自减

这个浅看看不出来, 实际上是一个必死的结局;

这个会导致栈溢出;

因为, n--会导致每次前一个栈帧给下一个函数传递的是n原本的值, 才去--, 这是后置自减的语义, 然后, 就相当于n原地不变, 所以一直到不了栈帧回退的出口;

1
2
3
4
5
6
7
8
void Print(const int * br, int n)
{
    if(n > 0)
    {
        Print(br, n--);
        cout << br[n - 1] << " ";
    }
}

错误版本2-不要使用前置自减

会导致越界, 并且前面多打了一个(br[-1]), 后面少打了一个(br[n-1]);

因为他把n减1并传过去了, 就缺少了n的情况, 并且, 由于前面做了n值的判断, 而又在if里面改值, 这是不妥的; 即, 最好不要在判断n的合法性后对n进行改动, 这是递归程序的忌讳;

1
2
3
4
5
6
7
8
void Print(const int * br, int n)
{
    if(n > 0)
    {
        Print(br, --n);
        cout << br[n - 1] << " ";
    }
}// [?随机值] 12 23 [缺34]

但是这种情况, 也可以把程序改正确, 即: 把打印br[n-1]改为br[n]

1
2
3
4
5
6
7
8
void Print(const int * br, int n)
{
    if(n > 0)
    {
        Print(br, --n);
        cout << br[n] << " ";
    }
}// 12 23 34

但还是不建议在递归程序的变量上进行前置自减;

错误版本3-引用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Print(const int * br, int & n)
{
    if(n > 0)
    {
        Print(br, --n);
        cout << br[n] << " ";
    }
}
void Print_Ar_recur(const int * br, int n)
{
    assert(br != NULL);
    if(n < 1)return;//the length must > 0
    Print(br, n);
    cout << endl;
}
//12 12 12

因为栈帧递进时, 所有栈帧中的n都一直在动态改变, 最终所有栈帧的n值都变为0了, 即所有的n都保持一致了, 因此, 打印的都是br[0], 这是引用的影响;

尽量在递归中少用引用，只有在线索二叉树才会用到

FindPos

传入数据指针, 长度, 和要找到val值, 返回下标

非递归版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int FindPos(const int * br, int n, int val)
{
    if(br == NULL || n < 1)return -1;
    int pos = n - 1;
    while(pos >= 0 && br[pos]!=val)
    {
        --pos;
    }
    return pos;
}
int main()
{
    int ar[] = {12,56,34,78};
    int n = sizeof(ar)/sizeof(ar[0]);
    int val = 78;
    int pos = FindPos(ar,n,val);
    cout << pos << endl;
}

递归版本-自己写的初版

1
2
3
4
5
6
7
8
9
10
11
12
13
int Find(const int * br, int n, int val)
{
    if(n > 0)
    {
        if(br[n - 1] == val) return n - 1;
        return Find(br, n - 1, val);
    }
}
int FindPos(const int * br, int n, int val)
{
    if(br == NULL || n < 1) return -1;
    return Find(br, n, val);
}

错误点：如果没有找到val，没有返回值。即, 如果走到n==-1, 则没有return的值, 可视为获取到了一个随机值

递归版本-正确版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//杨版
int Find(const int * br, int n, int val)
{
    if(n <= 0 || br[n-1] == val)
    {
        return n - 1;
    }
    else
    {
        return Find(br, n - 1, val);
    }
}
int FindPos(const int * br, int n, int val)
{
    if(br==NULL || n<1)return -1;
    return Find(br,n,val);
}

递归版本-标准版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//初版和杨版结合、改进
//杨版
int Find(const int * br, int n, int val)
{
    if(n > 0)
    {
        if(br[n-1] == val) return n - 1;
        else return Find(br, n - 1, val);
    }
    return -1;
}
int FindPos(const int * br, int n, int val)
{
    if(br==NULL || n < 1)return -1;
    return Find(br, n, val);
}

排序

快排、归并、堆排

问题

  1. 时间复杂度是多少？
  2. 空间复杂度是多少？
  3. 是否稳定？怎样可以稳定？什么时候需要稳定，什么时候不需要稳定？
  4. 什么情况下性能会退化？
  5. 三个排序的适用场景？
  6. 如果你的排序的递归的，怎么改为非递归？

快排

  1. 为什么数据有序的时候, 快排时间复杂度为O(n2)O(n^2)?
    1. 这个仅限于每次只从最边缘数据作为划分, 才出现这种情况
    2. 每次划分时, 相当于只划分出了一个数据和剩余的数据, 规模并没有有效的减小, 仍需要划分nn次; 而不是像最好的情况 - 每次正好把数据划分在中间, 规模减小, 此时只需划分log⁡2n\log_2n次;
    3. 放在二叉树上的形象图示就是: 最差情况下的快排就是一个极端不平衡的二叉树, 最好情况下的快排就是一个很平衡的二叉树;

快排

划分函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int Partition(int *ar, int left, int right)
{
    int tmp = ar[left];
    while(left < right)
    {
        while(left < right && ar[right] > tmp)
        {
            --right;
        }
        if(left < right) ar[left] = ar[right];
        while(left < right && ar[right] <= tmp)
        {
            ++left;
        }
        if(left < right) ar[right] = ar[left];
    }
    ar[left] = tmp;	//最后, left成为中间位置
    return left;
}

思考 - 为什么一直要强调left < right?

因为, 如果不加这种条件的话, left或right可能就会一直贪婪地, 不着边际地走下去, 最终left和right有可能错位!

如果产生了错位, left的right下标的值相互赋值将没有意义;

反之, 如果很好地控制了left和right的位置, 最终退出整个while循环后, left和right的位置一定指向的是同一个位置; 即, 最后两句的ar[left] = tmp和return left同样可以换为ar[right] = tmp和return left!

递归函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void PassQuick(int *ar, int left, int right)
{
    if(left < right)	//如果left == right 相当于只有一个元素, 不需排序
    {
        int pos = Partition(ar, left, right);//上一个划分出来的下标
        
        PassQuick(ar, left, pos - 1);       //对left ~ pos-1再划分
        PassQuick(ar, pos + 1, right);      //对pos+1 ~ right再划分
    }
}
void QuickSort(int * ar, int n)
{
    if(ar == NULL || n < 2)return;
    PassQuick(ar, 0, n-1);
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void Print_Ar(const int * ar, int n)
{
    if(ar == NULL || n < 1)return;
    for(int i = 0; i < n; ++i)
    {
        cout << ar[i] << " ";
    }
    cout << endl;
}
int main()
{
    int ar[] = {56, 12, 78, 90, 34, 23, 100, 56, 45, 67, 89};
    int n = sizeof(ar) / sizeof(ar[0]);
    Print_Ar(ar, n);
    QuickSort(ar, n);
    Print_Ar(ar, n);
}

同时, 也可以在PassQuick函数中Partition语句的下一行加个Print_Ar(ar, 11); 这样就能在每次划分完毕之后, 清楚地看到数组的状态;

image-20220616101832798

非递归 - 使用STL的queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void QuickSort(int * ar, int n)
{
    if(ar == NULL || n < 2) return;
    queue<int> qu;
    qu.push(0);
    qu.push(n - 1);
    while(!qu.empty())
    {
        int left = qu.front(); qu.pop();
        int right = qu.front(); qu.pop();
        
        int pos = Partition(ar, left, right);
        if(left < pos - 1)
        {
            qu.push(left);
            qu.push(pos - 1);
        }
        if(pos + 1 < right)
        {
            qu.push(pos + 1);
            qu.push(right);
        }
    }
}

使用对儿 - pair

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void QuickSort(int * ar, int n)
{
    if(ar == NULL || n < 2) return;
    queue<std::pair<int, int>> qu;
    qu.push(std::pair<int, int>(0, n-1));
    while(!qu.empty())
    {
        std::pair<int, int> record = qu.front(); qu.pop();
        int pos = Partition(ar, record.first, record.second);
        if(record.first < pos - 1)
        {
            qu.push(std::pair<int, int>(record.first, pos-1));
        }
        if(pos + 1 < record.second)
        {
            qu.push(std::pair<int, int>(pos+1, record.second));
        }
    }
}

可以使用别名使程序简化 - using idxPair = std::pair<int, int>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void QuickSort(int * ar, int n)
{
    if(ar == NULL || n < 2) return;
    using idxPair = std::pair<int, int>;
    
    queue<idxPair> qu;
    qu.push(idxPair(0, n-1));
    while(!qu.empty())
    {
        idxPair record = qu.front(); qu.pop();
        int pos = Partition(ar, record.first, record.second);
        if(record.first < pos - 1)
        {
            qu.push(idxPair(record.first, pos-1));
        }
        if(pos + 1 < record.second)
        {
            qu.push(idxPair(pos+1, record.second));
        }
    }
}

划分函数 - 单向划分 - 特别适于单链表

详见 “快速排序” 一文;

全排列、子集树

全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void Perm(int * ar, int i, int m)
{
    if(i == m)
    {
        for(int j = 0;j <= m;++j)
        {
            cout << ar[j] << " ";
        }
        cout << endl;
    }
    else
    {
        for(int j = i;j <= m;++j)
        {
            std::swap(ar[i],ar[j]);
            Perm(ar,i+1,m);
            std::swap(ar[i],ar[j]);
        }
    }
}
int main()
{
    int ar[] = {1,2,3};
    int n = sizeof(ar)/sizeof(ar[0]);
    Perm(ar, 0, n-1);
}
/*
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2
*/

全排列

子集树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
void fun(int i, int n)
{
    if(i >= n)return;
    else
    {
        fun(i+1, n);
        fun(i+1, n);
    }
}


void Print(int *ar, int * br, int i, int n)
{
    if(i >= n)
    {
        for(int j = 0;j < n;++j)
        {
            if(br[j] == 1)
            {
                cout << ar[j] << " ";
            }
            cout << endl;
        }
    }
    else
    {
        br[i] = 1;
        Print(ar, br, i+1, n);
        br[i] = 0;
        Print(ar, br, i+1, n);
    }
}
int main()
{
    int ar[] = {1,2,3};
    int br[] = {0,0,0};
    Print(ar, br, 0, 3);
    return 0;
}
/*
1 2 3
1 2
1 3
1
2 3
2
3
*/