CSAPP:ShellLab 实现原理整理

CSAPP附带实验中的ShellLab要求实现一个Unix下运行的Shell程序,并且能接受fg、bg、job、quit等指令和ctrl-c、ctrl-z的信号。这里并不从解题思路,而是从该程序的运行过程进行整理。

首先,不带参数启动时,Shell进程的main函数将编写好的handler注册到各个Signal上,然后通过一个不断循环的while来读取指令,在没有异常的情况下送到eval函数进行指令的解析。

int main(int argc, char **argv) // 未经修改的main函数
{
    char c;
    char cmdline[MAXLINE];
    int emit_prompt = 1; /* emit prompt (default) */

    /* Redirect stderr to stdout (so that driver will get all output
     * on the pipe connected to stdout) */
    dup2(1, 2);

    /* Parse the command line */
    while ((c = getopt(argc, argv, "hvp")) != EOF) {
        switch (c) {
        case 'h':             /* print help message */
            usage();
	    break;
        case 'v':             /* emit additional diagnostic info */
            verbose = 1;
	    break;
        case 'p':             /* don't print a prompt */
            emit_prompt = 0;  /* handy for automatic testing */
	    break;
	default:
            usage();
	}
    }

    /* Install the signal handlers */

    /* These are the ones you will need to implement */
    Signal(SIGINT,  sigint_handler);   /* ctrl-c */
    Signal(SIGTSTP, sigtstp_handler);  /* ctrl-z */
    Signal(SIGCHLD, sigchld_handler);  /* Terminated or stopped child */

    /* This one provides a clean way to kill the shell */
    Signal(SIGQUIT, sigquit_handler); 

    /* Initialize the job list */
    initjobs(jobs);

    /* Execute the shell's read/eval loop */
    while (1) {

	/* Read command line */
	if (emit_prompt) {
	    printf("%s", prompt);
	    fflush(stdout);
	}
	if ((fgets(cmdline, MAXLINE, stdin) == NULL) && ferror(stdin))
	    app_error("fgets error");
	if (feof(stdin)) { /* End of file (ctrl-d) */
	    fflush(stdout);
	    exit(0);
	}

	/* Evaluate the command line */
	eval(cmdline);
	fflush(stdout);
	fflush(stdout);
    } 

    exit(0); /* control never reaches here */
}

接着,在eval函数中,先判断命令是否为内建指令,若不是内建指令,则是需要创建一个新的子进程。子进程依靠fork创建,依靠execve切换进程的内容,同时利用pid来判断在父进程还是子进程中,从而分别执行不同的代码。在父进程内部,同时需要创建一个jobs表来记录子进程。

在这里,有两个情况需要加锁:一是父进程在整个从fork到等待子进程被回收的过程,此操作内需要发送SIGCHLD信号,保证前台只有一个子进程;而是在父进程修改jobs表前需要加锁,此操作是保证jobs表不发生冲突。

void eval(char *cmdline) 
{
    int bg;
    pid_t pid;
    sigset_t mask, mask_all, prev;
    char buf[MAXLINE];
    char *argv[MAXARGS];

    strcpy(buf, cmdline);  // 读指令至buffer
    bg = parseline(buf, argv); // 是否后台运行
    if (argv[0] == NULL) // 空行
    {
        return;
    }

    if (!builtin_cmd(argv)) // 不是内建指令
    {
        sigemptyset(&mask);
        sigaddset(&mask, SIGCHLD);
        sigfillset(&mask_all);
        sigprocmask(SIG_BLOCK, &mask, &prev); // 添加阻塞
        if ((pid = fork()) == 0) // 子进程
        {
            sigprocmask(SIG_SETMASK, &prev, NULL); // 子进程的阻塞解除
            if (setpgid(0, 0) < 0) // 初始化唯一的pid
            {
                printf("Setpgid Error!\n");
                exit(0);
            }
            if (execve(argv[0], argv, environ) < 0) // 转换进程
            {
                printf("%s: Command not found.\n", argv[0]);
                exit(0);
            }
        }
        else // 父进程
        {
            sigprocmask(SIG_BLOCK, &mask_all, NULL);
            if (bg) 
            {
                addjob(jobs, pid, BG, cmdline); // 添加至job表
            }
            else
            {
                addjob(jobs, pid, FG, cmdline); // 添加至job表
            }
            sigprocmask(SIG_SETMASK, &prev, NULL); // 对job操作完后即可解阻塞

            if (bg)
            {
                printf("[%d] (%d) %s", pid2jid(pid), pid, cmdline);
            }
            else
            {
                waitfg(pid);
            }
        }
    }
    return;
}

在waitfg函数中等待前台子进程结束的方式,这里简单地采用了sleep+轮询

void waitfg(pid_t pid) // 等待前台子进程
{
    while (pid == fgpid(jobs))
    {
        sleep(1);
    }
    return;
}

若指令是内建指令,则通过buildin_cmd函数来进行解析

int builtin_cmd(char **argv) 
{
    if (!strcmp(argv[0],"quit"))
    {
        exit(0);
    }
    if (!strcmp(argv[0],"jobs"))
    {
        listjobs(jobs); // 输出jobs表
        return 1;
    }
    if (!strcmp(argv[0],"bg") || !strcmp(argv[0],"fg"))
    {
        do_bgfg(argv);
        return 1;
    }
    
    return 0;
}

其中quit为结束shell,jobs为输出jobs表,而bg或fg指令为将参数(pid或%jobid)所对应的进程切换到后台/前台运行。

因此,需要编写do_bgfg函数来具体执行bg和fg指令,并且发送绑定了handler的信号给子进程。

void sigchld_handler(int sig) 
{
	int old_errno = errno;	// 保存原errno
	pid_t pid;
	sigset_t mask, prev;
	int state;	// waitpid的状态
	struct job_t *job;
	
	sigfillset(&mask);
	while ((pid = waitpid(-1, &state, WNOHANG | WUNTRACED)) > 0) // while保证回收每个子进程
    {
		sigprocmask(SIG_BLOCK, &mask, &prev); // 阻塞所有信号
		if (WIFEXITED(state)) // 正常终止
        {
			deletejob(jobs, pid);
		}
        else if (WIFSIGNALED(state)) // 信号导致终止
        {
			printf("Job [%d] (%d) terminated by signal %d\n", pid2jid(pid), pid, WTERMSIG(state));		
			deletejob(jobs, pid);
		}
        else if (WIFSTOPPED(state)) // 子进程停止
        {
			job = getjobpid(jobs, pid);
            if (job == NULL)
            {
                printf("Error: (%d): No such process\n",pid);
            }
			else
            {
                job->state = ST;
            }
			printf("Job [%d] (%d) stopped by signal %d\n", job->jid, pid, WSTOPSIG(state));
		}
		sigprocmask(SIG_SETMASK, &prev, NULL);	// 解锁
	}
	errno = old_errno; // 复原errno
}

对SIGCHLD信号,需要判断发送的原因。子进程正常终止、收到信号而终止、或者STOP时都会发送该信号。因此若正常终止或信号导致终止,则从jobs表中删除;若子进程停止,则只需要将job的状态改为STOP。

同样,需要在修改前后对信号加阻塞。

void sigint_handler(int sig) // 响应ctrl-c
{
    int old_errno = errno;
    pid_t pid = fgpid(jobs);
    if (pid != 0)
    {
        kill(-pid, sig);
    }
    errno = old_errno;
    return;
}

void sigtstp_handler(int sig) // 响应ctrl-z
{
    int old_errno = errno;
    pid_t pid = fgpid(jobs);
    if (pid != 0)
    {
        kill(-pid, sig);
    }
    errno = old_errno;
    return;
}

最后是ctrl-c和ctrl-z的相应。这里都只需要从jobs表中找到该job,并且将ctrl-c或ctrl-z的signal发送给子进程即可。

配合其他的辅助函数,这个程序便可以实现简单的shell功能,与参考文件中的示例shell输出无差。

./sdriver.pl -t trace01.txt -s ./tsh -a "-p"
#
# trace01.txt - Properly terminate on EOF.
#
./sdriver.pl -t trace01.txt -s ./tshref -a "-p"
#
# trace01.txt - Properly terminate on EOF.
#
./sdriver.pl -t trace02.txt -s ./tsh -a "-p"
#
# trace02.txt - Process builtin quit command.
#
./sdriver.pl -t trace02.txt -s ./tshref -a "-p"
#
# trace02.txt - Process builtin quit command.
#
./sdriver.pl -t trace03.txt -s ./tsh -a "-p"
#
# trace03.txt - Run a foreground job.
#
tsh> quit
./sdriver.pl -t trace03.txt -s ./tshref -a "-p"
#
# trace03.txt - Run a foreground job.
#
tsh> quit
./sdriver.pl -t trace04.txt -s ./tsh -a "-p"
#
# trace04.txt - Run a background job.
#
tsh> ./myspin 1 &
[1] (19812) ./myspin 1 &
./sdriver.pl -t trace04.txt -s ./tshref -a "-p"
#
# trace04.txt - Run a background job.
#
tsh> ./myspin 1 &
[1] (19817) ./myspin 1 &
./sdriver.pl -t trace05.txt -s ./tsh -a "-p"
#
# trace05.txt - Process jobs builtin command.
#
tsh> ./myspin 2 &
[1] (19824) ./myspin 2 &
tsh> ./myspin 3 &
[2] (19826) ./myspin 3 &
tsh> jobs
[1] (19824) Running ./myspin 2 &
[2] (19826) Running ./myspin 3 &
./sdriver.pl -t trace05.txt -s ./tshref -a "-p"
#
# trace05.txt - Process jobs builtin command.
#
tsh> ./myspin 2 &
[1] (19834) ./myspin 2 &
tsh> ./myspin 3 &
[2] (19836) ./myspin 3 &
tsh> jobs
[1] (19834) Running ./myspin 2 &
[2] (19836) Running ./myspin 3 &
./sdriver.pl -t trace06.txt -s ./tsh -a "-p"
#
# trace06.txt - Forward SIGINT to foreground job.
#
tsh> ./myspin 4
Job [1] (19846) terminated by signal 2
./sdriver.pl -t trace06.txt -s ./tshref -a "-p"
#
# trace06.txt - Forward SIGINT to foreground job.
#
tsh> ./myspin 4
Job [1] (19853) terminated by signal 2
./sdriver.pl -t trace07.txt -s ./tsh -a "-p"
#
# trace07.txt - Forward SIGINT only to foreground job.
#
tsh> ./myspin 4 &
[1] (19860) ./myspin 4 &
tsh> ./myspin 5
Job [2] (19862) terminated by signal 2
tsh> jobs
[1] (19860) Running ./myspin 4 &
./sdriver.pl -t trace07.txt -s ./tshref -a "-p"
#
# trace07.txt - Forward SIGINT only to foreground job.
#
tsh> ./myspin 4 &
[1] (19874) ./myspin 4 &
tsh> ./myspin 5
Job [2] (19876) terminated by signal 2
tsh> jobs
[1] (19874) Running ./myspin 4 &
./sdriver.pl -t trace08.txt -s ./tsh -a "-p"
#
# trace08.txt - Forward SIGTSTP only to foreground job.
#
tsh> ./myspin 4 &
[1] (19886) ./myspin 4 &
tsh> ./myspin 5
Job [2] (19888) stopped by signal 20
tsh> jobs
[1] (19886) Running ./myspin 4 &
[2] (19888) Stopped ./myspin 5 
./sdriver.pl -t trace08.txt -s ./tshref -a "-p"
#
# trace08.txt - Forward SIGTSTP only to foreground job.
#
tsh> ./myspin 4 &
[1] (19898) ./myspin 4 &
tsh> ./myspin 5
Job [2] (19900) stopped by signal 20
tsh> jobs
[1] (19898) Running ./myspin 4 &
[2] (19900) Stopped ./myspin 5 
./sdriver.pl -t trace09.txt -s ./tsh -a "-p"
#
# trace09.txt - Process bg builtin command
#
tsh> ./myspin 4 &
[1] (19912) ./myspin 4 &
tsh> ./myspin 5
Job [2] (19914) stopped by signal 20
tsh> jobs
[1] (19912) Running ./myspin 4 &
[2] (19914) Stopped ./myspin 5 
tsh> bg %2
[2] (19914) ./myspin 5 
tsh> jobs
[1] (19912) Running ./myspin 4 &
[2] (19914) Running ./myspin 5 
./sdriver.pl -t trace09.txt -s ./tshref -a "-p"
#
# trace09.txt - Process bg builtin command
#
tsh> ./myspin 4 &
[1] (19926) ./myspin 4 &
tsh> ./myspin 5
Job [2] (19928) stopped by signal 20
tsh> jobs
[1] (19926) Running ./myspin 4 &
[2] (19928) Stopped ./myspin 5 
tsh> bg %2
[2] (19928) ./myspin 5 
tsh> jobs
[1] (19926) Running ./myspin 4 &
[2] (19928) Running ./myspin 5 
./sdriver.pl -t trace10.txt -s ./tsh -a "-p"
#
# trace10.txt - Process fg builtin command. 
#
tsh> ./myspin 4 &
[1] (19942) ./myspin 4 &
tsh> fg %1
Job [1] (19942) stopped by signal 20
tsh> jobs
[1] (19942) Stopped ./myspin 4 &
tsh> fg %1
tsh> jobs
./sdriver.pl -t trace10.txt -s ./tshref -a "-p"
#
# trace10.txt - Process fg builtin command. 
#
tsh> ./myspin 4 &
[1] (19955) ./myspin 4 &
tsh> fg %1
Job [1] (19955) stopped by signal 20
tsh> jobs
[1] (19955) Stopped ./myspin 4 &
tsh> fg %1
tsh> jobs
./sdriver.pl -t trace11.txt -s ./tsh -a "-p"
#
# trace11.txt - Forward SIGINT to every process in foreground process group
#
tsh> ./mysplit 4
Job [1] (19968) terminated by signal 2
tsh> /bin/ps a
  PID TTY      STAT   TIME COMMAND
 1054 tty1     Ss+    0:00 /sbin/agetty --noclear tty1 linux
 8356 pts/2    Ss+    0:00 /bin/bash
18883 pts/0    Ss     0:00 -bash
19786 pts/0    S+     0:00 sh run.sh
19964 pts/0    S+     0:00 make test11
19965 pts/0    S+     0:00 /usr/bin/perl ./sdriver.pl -t trace11.txt -s ./tsh -a -p
19966 pts/0    S+     0:00 ./tsh -p
19973 pts/0    R      0:00 /bin/ps a
21890 pts/1    Ss+    0:00 /bin/bash
./sdriver.pl -t trace11.txt -s ./tshref -a "-p"
#
# trace11.txt - Forward SIGINT to every process in foreground process group
#
tsh> ./mysplit 4
Job [1] (19978) terminated by signal 2
tsh> /bin/ps a
  PID TTY      STAT   TIME COMMAND
 1054 tty1     Ss+    0:00 /sbin/agetty --noclear tty1 linux
 8356 pts/2    Ss+    0:00 /bin/bash
18883 pts/0    Ss     0:00 -bash
19786 pts/0    S+     0:00 sh run.sh
19974 pts/0    S+     0:00 make rtest11
19975 pts/0    S+     0:00 /usr/bin/perl ./sdriver.pl -t trace11.txt -s ./tshref -a -p
19976 pts/0    S+     0:00 ./tshref -p
19985 pts/0    R      0:00 /bin/ps a
21890 pts/1    Ss+    0:00 /bin/bash
./sdriver.pl -t trace12.txt -s ./tsh -a "-p"
#
# trace12.txt - Forward SIGTSTP to every process in foreground process group
#
tsh> ./mysplit 4
Job [1] (19992) stopped by signal 20
tsh> jobs
[1] (19992) Stopped ./mysplit 4 
tsh> /bin/ps a
  PID TTY      STAT   TIME COMMAND
 1054 tty1     Ss+    0:00 /sbin/agetty --noclear tty1 linux
 8356 pts/2    Ss+    0:00 /bin/bash
18883 pts/0    Ss     0:00 -bash
19786 pts/0    S+     0:00 sh run.sh
19986 pts/0    S+     0:00 make test12
19987 pts/0    S+     0:00 /usr/bin/perl ./sdriver.pl -t trace12.txt -s ./tsh -a -p
19990 pts/0    S+     0:00 ./tsh -p
19992 pts/0    T      0:00 ./mysplit 4
19993 pts/0    T      0:00 ./mysplit 4
20000 pts/0    R      0:00 /bin/ps a
21890 pts/1    Ss+    0:00 /bin/bash
./sdriver.pl -t trace12.txt -s ./tshref -a "-p"
#
# trace12.txt - Forward SIGTSTP to every process in foreground process group
#
tsh> ./mysplit 4
Job [1] (20007) stopped by signal 20
tsh> jobs
[1] (20007) Stopped ./mysplit 4 
tsh> /bin/ps a
  PID TTY      STAT   TIME COMMAND
 1054 tty1     Ss+    0:00 /sbin/agetty --noclear tty1 linux
 8356 pts/2    Ss+    0:00 /bin/bash
18883 pts/0    Ss     0:00 -bash
19786 pts/0    S+     0:00 sh run.sh
20001 pts/0    S+     0:00 make rtest12
20002 pts/0    S+     0:00 /usr/bin/perl ./sdriver.pl -t trace12.txt -s ./tshref -a -p
20005 pts/0    S+     0:00 ./tshref -p
20007 pts/0    T      0:00 ./mysplit 4
20008 pts/0    T      0:00 ./mysplit 4
20011 pts/0    R      0:00 /bin/ps a
21890 pts/1    Ss+    0:00 /bin/bash
./sdriver.pl -t trace13.txt -s ./tsh -a "-p"
#
# trace13.txt - Restart every stopped process in process group
#
tsh> ./mysplit 4
Job [1] (20020) stopped by signal 20
tsh> jobs
[1] (20020) Stopped ./mysplit 4 
tsh> /bin/ps a
  PID TTY      STAT   TIME COMMAND
 1054 tty1     Ss+    0:00 /sbin/agetty --noclear tty1 linux
 8356 pts/2    Ss+    0:00 /bin/bash
18883 pts/0    Ss     0:00 -bash
19786 pts/0    S+     0:00 sh run.sh
20012 pts/0    S+     0:00 make test13
20013 pts/0    S+     0:00 /usr/bin/perl ./sdriver.pl -t trace13.txt -s ./tsh -a -p
20018 pts/0    S+     0:00 ./tsh -p
20020 pts/0    T      0:00 ./mysplit 4
20021 pts/0    T      0:00 ./mysplit 4
20025 pts/0    R      0:00 /bin/ps a
21890 pts/1    Ss+    0:00 /bin/bash
tsh> fg %1
tsh> /bin/ps a
  PID TTY      STAT   TIME COMMAND
 1054 tty1     Ss+    0:00 /sbin/agetty --noclear tty1 linux
 8356 pts/2    Ss+    0:00 /bin/bash
18883 pts/0    Ss     0:00 -bash
19786 pts/0    S+     0:00 sh run.sh
20012 pts/0    S+     0:00 make test13
20013 pts/0    S+     0:00 /usr/bin/perl ./sdriver.pl -t trace13.txt -s ./tsh -a -p
20018 pts/0    S+     0:00 ./tsh -p
20030 pts/0    R      0:00 /bin/ps a
21890 pts/1    Ss+    0:00 /bin/bash
./sdriver.pl -t trace13.txt -s ./tshref -a "-p"
#
# trace13.txt - Restart every stopped process in process group
#
tsh> ./mysplit 4
Job [1] (20037) stopped by signal 20
tsh> jobs
[1] (20037) Stopped ./mysplit 4 
tsh> /bin/ps a
  PID TTY      STAT   TIME COMMAND
 1054 tty1     Ss+    0:00 /sbin/agetty --noclear tty1 linux
 8356 pts/2    Ss+    0:00 /bin/bash
18883 pts/0    Ss     0:00 -bash
19786 pts/0    S+     0:00 sh run.sh
20031 pts/0    S+     0:00 make rtest13
20032 pts/0    S+     0:00 /usr/bin/perl ./sdriver.pl -t trace13.txt -s ./tshref -a -p
20035 pts/0    S+     0:00 ./tshref -p
20037 pts/0    T      0:00 ./mysplit 4
20038 pts/0    T      0:00 ./mysplit 4
20041 pts/0    R      0:00 /bin/ps a
21890 pts/1    Ss+    0:00 /bin/bash
tsh> fg %1
tsh> /bin/ps a
  PID TTY      STAT   TIME COMMAND
 1054 tty1     Ss+    0:00 /sbin/agetty --noclear tty1 linux
 8356 pts/2    Ss+    0:00 /bin/bash
18883 pts/0    Ss     0:00 -bash
19786 pts/0    S+     0:00 sh run.sh
20031 pts/0    S+     0:00 make rtest13
20032 pts/0    S+     0:00 /usr/bin/perl ./sdriver.pl -t trace13.txt -s ./tshref -a -p
20035 pts/0    S+     0:00 ./tshref -p
20046 pts/0    R      0:00 /bin/ps a
21890 pts/1    Ss+    0:00 /bin/bash
./sdriver.pl -t trace14.txt -s ./tsh -a "-p"
#
# trace14.txt - Simple error handling
#
tsh> ./bogus
./bogus: Command not found.
tsh> ./myspin 4 &
[1] (20055) ./myspin 4 &
tsh> fg
fg command requires PID or %jobid argument
tsh> bg
bg command requires PID or %jobid argument
tsh> fg a
fg: argument must be a PID or %jobid
tsh> bg a
bg: argument must be a PID or %jobid
tsh> fg 9999999
(9999999): No such process
tsh> bg 9999999
(9999999): No such process
tsh> fg %2
%2: No such job
tsh> fg %1
Job [1] (20055) stopped by signal 20
tsh> bg %2
%2: No such job
tsh> bg %1
[1] (20055) ./myspin 4 &
tsh> jobs
[1] (20055) Running ./myspin 4 &
./sdriver.pl -t trace14.txt -s ./tshref -a "-p"
#
# trace14.txt - Simple error handling
#
tsh> ./bogus
./bogus: Command not found
tsh> ./myspin 4 &
[1] (20075) ./myspin 4 &
tsh> fg
fg command requires PID or %jobid argument
tsh> bg
bg command requires PID or %jobid argument
tsh> fg a
fg: argument must be a PID or %jobid
tsh> bg a
bg: argument must be a PID or %jobid
tsh> fg 9999999
(9999999): No such process
tsh> bg 9999999
(9999999): No such process
tsh> fg %2
%2: No such job
tsh> fg %1
Job [1] (20075) stopped by signal 20
tsh> bg %2
%2: No such job
tsh> bg %1
[1] (20075) ./myspin 4 &
tsh> jobs
[1] (20075) Running ./myspin 4 &
./sdriver.pl -t trace15.txt -s ./tsh -a "-p"
#
# trace15.txt - Putting it all together
#
tsh> ./bogus
./bogus: Command not found.
tsh> ./myspin 10
Job [1] (20097) terminated by signal 2
tsh> ./myspin 3 &
[1] (20101) ./myspin 3 &
tsh> ./myspin 4 &
[2] (20103) ./myspin 4 &
tsh> jobs
[1] (20101) Running ./myspin 3 &
[2] (20103) Running ./myspin 4 &
tsh> fg %1
Job [1] (20101) stopped by signal 20
tsh> jobs
[1] (20101) Stopped ./myspin 3 &
[2] (20103) Running ./myspin 4 &
tsh> bg %3
%3: No such job
tsh> bg %1
[1] (20101) ./myspin 3 &
tsh> jobs
[1] (20101) Running ./myspin 3 &
[2] (20103) Running ./myspin 4 &
tsh> fg %1
tsh> quit
./sdriver.pl -t trace15.txt -s ./tshref -a "-p"
#
# trace15.txt - Putting it all together
#
tsh> ./bogus
./bogus: Command not found
tsh> ./myspin 10
Job [1] (20122) terminated by signal 2
tsh> ./myspin 3 &
[1] (20127) ./myspin 3 &
tsh> ./myspin 4 &
[2] (20129) ./myspin 4 &
tsh> jobs
[1] (20127) Running ./myspin 3 &
[2] (20129) Running ./myspin 4 &
tsh> fg %1
Job [1] (20127) stopped by signal 20
tsh> jobs
[1] (20127) Stopped ./myspin 3 &
[2] (20129) Running ./myspin 4 &
tsh> bg %3
%3: No such job
tsh> bg %1
[1] (20127) ./myspin 3 &
tsh> jobs
[1] (20127) Running ./myspin 3 &
[2] (20129) Running ./myspin 4 &
tsh> fg %1
tsh> quit
./sdriver.pl -t trace16.txt -s ./tsh -a "-p"
#
# trace16.txt - Tests whether the shell can handle SIGTSTP and SIGINT
#     signals that come from other processes instead of the terminal.
#
tsh> ./mystop 2
Job [1] (20147) stopped by signal 20
tsh> jobs
[1] (20147) Stopped ./mystop 2
tsh> ./myint 2
Job [2] (20156) terminated by signal 2
./sdriver.pl -t trace16.txt -s ./tshref -a "-p"
#
# trace16.txt - Tests whether the shell can handle SIGTSTP and SIGINT
#     signals that come from other processes instead of the terminal.
#
tsh> ./mystop 2
Job [1] (20163) stopped by signal 20
tsh> jobs
[1] (20163) Stopped ./mystop 2
tsh> ./myint 2
Job [2] (20168) terminated by signal 2

函数调用关系观察:深度优先搜索解决八皇后问题

代码:

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

void dfs(int x, const int size, int* a, int* row, int* col, int* ld, int* rd, int& total);
int main()
{
	const int size = 10000;
	int row[size] = { 0 };
	int col[size] = { 0 };
	int ld[2 * size] = { 0 };
	int rd[2 * size] = { 0 };
	int a[size] = { 0 };
	int total = 0;
	dfs(0, size, a, row, col, ld, rd, total);
	cout << "总方案数: " << total;
	return 0;
}

void dfs(int x, const int size, int* a, int* row, int* col, int* ld, int* rd, int & total)
{
	//cout << x;
	if (x == size)
	{
		/*
		cout << "正确解法:";
		for (int i = 0; i < size; i++)
		{
			cout << a[i] << " ";
		}
		cout << endl;
	*/
		total++;
		return;
	}
	cout << "正在测试第 " << x + 1 << " 行的情况\n";
	for (int y = 0; y < size; y++)
	{
		//cout << "正在测试第 " << x + 1 << " 行第 " << y + 1 << " 列的情况:";
		if (!row[x] && !col[y] && !ld[x - y + size] && !rd[x + y])
		{
			//cout << "第 " << x + 1 << " 行第 " << y + 1 << " 列的情况是成功的,此时为:";
			//cout << "成功\n";
			a[x] = y + 1;

			row[x] = 1;//封闭行
			col[y] = 1;//封闭列
			ld[x - y + size] = 1;//封闭左对角线
			rd[x + y] = 1;//封闭右对角线
			/*
			for (int i = 0; i < size; i++)
			{
				cout << a[i] << " ";
			}
			cout << endl;
			*/
			dfs(x + 1, size, a, row, col, ld, rd, total);//进行下一层回溯

			row[x] = 0;//还原行
			col[y] = 0;//还原列
			ld[x - y + size] = 0;//还原左对角线
			rd[x + y] = 0;//还原右对角线
		}
		else
		{
			//cout << "  但是在第 " << x + 1 << " 行第 " << y + 1 << " 列的情况是失败的\n";
			//cout << "失败\n";
		}
	}
}
  1. 观察函数栈的调用:方法一:设置断点,在每个断点处检查变量的值;方法二:设置断点,并且在函数调用时和返回后都进行输出
  2. 程序以八皇后问题为例,这里使用的方法二,运行之后可以看出进行深度优先搜索时函数调用栈满足后进先出的原则,
  3. 将八皇后的棋盘大小设置为10000,在测试第2869~2875行的情况时发生了溢出,每次发生溢出时深度不完全相同

如何在宝塔上搭建express后端

问题

按照网络上的关于在宝塔上搭建express后端的方法,在我的环境下是有问题的。先简单叙述网上其他博文中的办法:先新建站点,然后上传express后端到站点目录下,然后再pm2管理器中启动,最后在站点的配置文件加上几行:

location / {
	    proxy_pass http://127.0.0.1:3000; // 监听的本地端口
}

然而这样会导致一个情况:只有根目录下的网页可以访问到,于是会导致如图情况:

连页面请求的css、js等文件都请求不到。

解决方案

研究了宝塔端pm2后,终于发现了正确的搭建方式:先在pm2中启动express后端,再在pm2中添加映射。具体的方式如下:

1. 上传写好的express后端

上传到一个方便管理的目录下

2. 在pm2中启动express

填写好文件夹地址、启动文件和项目名,点击添加,pm2可以自动在正确的端口启动express。这里使用了express-generator,所以启动文件是bin/www

3. 添加映射

点击上图中需要添加映射的项目右边的“映射”

填入需要添加映射的站点即可,宝塔会自动创建一个网站,在左侧“网站”面板中可以管理。

这时候所有的资源都请求得到了。

原因猜测

原方法访问不到的原因必然是仅仅加上那几行,Nginx无法正确映射所有的express框架中访问的资源的url。而直接使用pm2的自动配置映射的功能,可以自动完成对Nginx的配置,比较省时。

C++STL之unordered_map用法简析,从造轮子到用轮子

unordered_map是C++11中加入的,以哈希表为索引方式的STL结构。与map不同,unordered_map寻找索引的值的理论时间复杂度仅为O(1),而依靠红黑树的map是O(logn)。

要理解unordered_map的运作原理,首先来造个轮子,写个自己的哈希表寻址结构。

Hash值是每个数据某个数据(比如是key)通过运算得到的某个数值,将该数据放进整个结构(比如数组)中以这个Hash值为索引的地址中,就类似于把数据倒入桶中。当需要找到某个key值对应的数据时,也同样算出Hash值,然后直接在结构中寻找就可以。由于数组的地址连贯性,Hash值作为索引可以直接计算出数据所在的地址,因此时间复杂度仅为O(1)。

造个Hash Table试试

首先是用到的数据的结构Record:

class Record
{
private:
	int key;
	int value;
public:
	int the_key() { return key; }
	int the_value() { return value; }
	Record() { key = value = -1; }
	Record(int k, int v) : key(k), value(v) {}
	bool operator==(Record r) { return the_value() == r.the_value(); } //相等
	Record operator=(Record r); //赋值构造函数
	//...以及更多需要的函数
};

定义好了key和value,写好构造函数并且重载部分需要的操作符(具体略)。然后是利用Hash值寻址的结构hash_table。

enum Error_code { not_present, overflow, deplicate_error, success };
const int hash_size = 100;
class hash_table
{
private:
	Record table[hash_size];
	int hash(Record r); //获得某个Record的Hash值
	bool is_empty(int index) { return table[index].the_key() == -1; } //查询table数组中index位上是否已经有数据
public:
	hash_table();
	hash_table(const hash_table& ht);
	//...以及更多构造函数
	Error_code insert(const Record& r); //插入某个Record的函数
	Error_code retrive(const int& key, Record& r); //查询表中是否存在某个key值,并且存在r中
	Error_code remove(const int& key); //删去该key值对应的Record
	Error_code find_key(int value, int& result); //寻找第一个value匹配key
	Error_code find_value(int key, int& result); //寻找key对应的value
	//...以及更多增删查改的操作
	hash_table operator=(const hash_table& ht); //赋值构造函数
	//...以及更多重载运算符 
};

其中,灵魂部分便是hash(Record r),这个函数对r的key计算得到其Hash值,后面的函数中,增删查改等所有需要从key来寻找到地址的操作,都需要用到这个函数。

例:用取余运算作为Hash函数

//简单的采用取余得到的结果作为Hash值
int hash_table::hash(Record r) 
{ 
	return r.the_key() % hash_size; 
}
//每次insert一个Record,便先算出其hash值,然后根据索引存储数据
Error_code hash_table::insert(const Record& r)
{
	for (int index = hash(r), k = 0; k < hash_size; (index = (index == hash_size - 1) ? 0 : index + 1), k++)
	{
		if (is_empty(index))
		{
			table[index] = r;
			return success;
		}
	}
	return overflow;
}
//通过key寻找value也同样先算出Hash值,载根据索引查询数据
Error_code hash_table::find_value(int key, int& result)
{
	for (int index = hash(Record(key, 0)); index < hash_size; index++)
	{
		if (is_empty(index))
		{
			return not_present;
		}
		if (table[index].the_key() == key)
		{
			result = table[index].the_value();
			return success;
		}
	}
}
//...以及更多函数

这里需要注意的一点是,当数据发生冲突,即Hash值相等时,这里采用的办法是从这个地址开始不断向后寻找下一个可以存储数据的地址,然后存下,如果全满则返回overflow;取值的时候也类似。这种处理冲突的办法称为开放寻址法。

Unordered_map之用法

声明

像其他STL一样,unordered_map已经内置了很多方法;不过,它还可以传入更多的参数,先看看其定义

template < class Key,                  // unordered_map::key_type
           class T,                    // unordered_map::mapped_type
           class Hash = hash<Key>,     // unordered_map::hasher
           class Pred = equal_to<Key>, // unordered_map::key_equal
           class Alloc = allocator< pair<const Key,T> >  // unordered_map::allocator_type
           > class unordered_map;

第三到第五个参数都可以省略。第一个参数是Key值,第二个参数是存储的数据,第五个参数是空间配置器,没必要修改。这里聊聊第三第四两个参数。
其中,第三个参数需要一个包含取Hash值的函数,取的对象是第一个参数,即为数据的key值。这里依然以取余运算为Hash函数为例。

struct my_hash
{
	int operator()(const int& value) const
	{
		return value % hash_len;
	}
};

struct就是默认为public的class。为了简便,直接重载()运算符,这样,每个my_hash的对象都可以相当于一个函数名,用()传入参数,调用取Hash值的函数。
接下来是第四个参数,它需要包含一个判断key值是否相等的函数。

struct my_compare
{
	bool operator()(const int& x, const int& y) const
	{
		return x == y;
	}
};

也同样的道理,重载()运算符即可。
有了这样自定义好的两个类,便可以创建unordered_map了。

unordered_map<int, int, my_hash, my_compare> umap;
//声明了一个key值为int,数据也是int,取Hash值的方法的类为my_hash,判断key值是否相等的方法的类为my_compare的unordered_map

当然,这个例子中的my_hash和my_compare也是可以省略的,因为int型是可以直接比较的,默认的比较函数可以工作;unordered_map也内置了计算Hash值的方法。

方法

首先,键值对在unordered_map中的每个元素是pair<const Key, T>的模板类的实例化的对象,每一个pair中first属性是其key,second属性是其value。

另外,后一个insert或emplace入的的同key元素将被忽略,不会覆盖原有的value

  1. unordered_map::begin, end, cbegin, cend 头迭代器,超尾迭代器,const头迭代器,const超尾迭代器
  2. unordered_map::operator= 赋值构造函数,可以传入另一个unordered_map;移动构造函数,传入一个unordered_map右值;初始化列表,用直接量的列表赋值
  3. unordered_map::operator[] 其行为类似数组,以key为索引,可以读写值
    um3[“z”] = 5;
    um3[“y”] = um3[“z”];
  4. unordered_map::insert 插入一个或多个键值对
    um.insert(pair<string, int>{ “a”, 5 }); //使用直接量
    um.insert({ “a”, 5 }); //省略类型
    um2.insert(um.begin(), um.end()); //使用迭代器
  5. unordered_map::emplace 传入参数列表,自动创建一个键值对
    um.emplace( “c”, 10 ); //添加键值对pair<string, int>{ “c”, 10 }
  6. unordered_map::emplace_hint 传入一个迭代器和参数列表,自动(优先从该迭代器的位置)创建一个键值对,并且当成功插入时,返回指向插入元素的迭代器;因为key已存在而插入失败时,返回指向该key所在元素的迭代器(值不会覆盖)
    um.emplace_hint(um.begin(), “a”, 10); //返回指向{ “a”, 5 }的迭代器
  7. unordered_map::at 获得传入key对应的值
    um.at(“a”); //返回5
  8. unordered_map::find 寻找传入key对应的迭代器
    um.find(“a”); //返回指向pair<string, int>{ “a”, 5 }的迭代器
    um.find(“b”); //key不存在,返回um.end()
  9. unordered_map::erase 删去容器中的部分元素,可以传入key的值、某个迭代器、或者两个迭代器组成的范围
    um2.erase(um2.begin(), um2.end()); //这个例子相当于clear
  10. unordered_map::clear 清空容器
  11. unordered_map::swap 传入另一个unordered_map,交换两个容器的值
  12. unordered_map::empty 返回容器是否为空的布尔值
  13. unordered_map::count 计算传入的key在容器中存在的个数;事实上因为key是唯一的,只能得到0或1
    um.count(“a”); //返回1
    um.count(“b”); //返回0
  14. unordered_map :: hash_function 返回该容器使用的Hash函数的对象(可以当做函数指针使用)
    auto fn = um.hash_function();
    fn(“d”); //返回3775669363
  15. unordered_map :: key_eq 无参数,返回一个需要传入两个参数的函数,给该函数传入两个key,返回两个key是否Hash值相等的布尔值
    um.key_eq()(“a”, “A”); //返回false
  16. unordered_map::bucket 获得传入的key所在的桶的编号,传入的key不一定要在容器中已存在
    um.bucket(“a”); //返回4
    um.bucket(“b”); //返回5
  17. unordered_map::bucket_count 返回容器的桶的个数
    um.bucket_count(); //返回8
  18. unordered_map::bucket_size 传入一个unsigned int,获得这个编号的桶内的元素数
    um.bucket_size(4); //返回1
    um.bucket_size(5); //返回0
  19. unordered_map::size, max_size, load_factor, max_load_factor 该容器的元素个数,最大元素个数,已加载的桶的比例,最大加载的桶的比例,其中,load_factor = size / bucket_count
  20. unordered_map::reserve 传入一个unsigned int,将容器中的bucket_count设置为最适合的包含至少n个元素的大小
  21. unordered_map :: rehash 传入一个unsigned int,将容器中的bucket_count设置为n(或更多)
  22. unordered_map::equal_range 传入一个key,返回寻找到含有这个key的键值对所组成一个范围。返回值的first属性是头键值对,second属性是尾键值对。因为key是唯一的,返回的范围自然也只有一个元素,该方法在unordered_multimap中更常用。
    auto range = um.equal_range(“a”);
    for_each( range.first, range,second, [](auto x) {cout << x.first << x.second; } //输出a5
    这里使用了for_each语句,给定头尾和执行的函数,并且用Lambda表达式作为匿名函数,简单实现将range中所有元素(只有一个)进行输出
    其中x的类型是unordered_map::value_type
  23. unordered_map::get_allocator 返回allocator_type

参考了 http://www.cplusplus.com/reference/unordered_map/

链表解题笔记

刷完了Leetcode所有的链表简单—中等题,归纳一下用过的技巧。

一、快慢指针

相位差快慢

例题:实现一种算法,找出单向链表中倒数第 k 个节点。返回该节点的值。

class Solution {
public:
    int kthToLast(ListNode* head, int k) {
        ListNode* fast = head, *slow = head;
        for(int i = 0; i < k - 1; i++)
        {
            fast = fast->next;
        }
        while(fast->next != NULL)
        {
            fast = fast->next;
            slow = slow->next;
        }
        return slow->val;
    }
};

先让快指针走k-1步,再让快慢指针同速度前进。当快指针走到尾部,慢指针自然在倒数第k个节点。

步长快慢

例题:给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        if(head == NULL)
        {
            return NULL;
        }
        ListNode* fast = head;
        ListNode* low = head;
        while(fast->next != NULL)
        {
            low = low->next;
            fast = fast->next->next;
            if(fast == NULL)
            {
                break;
            }
        }
        return low;
    }
};

让快慢指针同时从头指针出发,快指针一次走两步,慢指针一次走一步,当快指针到达尾部,慢指针自然在正中间。

二、缓冲区

也就是另外建立存储数据的区域,例题:编写代码,移除未排序链表中的重复节点。保留最开始出现的节点。

class Solution {
public:
    ListNode* removeDuplicateNodes(ListNode* head) {
        ListNode* cur = head, *prev;
        int data[20001] = {0};
        while(cur != NULL)
        {
            if(data[cur->val] == 0)
            {
                data[cur->val]++;
                prev = cur;
                cur = cur->next;
            }
            else if(data[cur->val] == 1)
            {
                prev->next = cur->next;
                delete cur;
                cur = prev->next;
            }
        }
        return head;
    }
};

这里将每个数据放入对应的桶中,如果桶中已经有数据,自然判断出重复。

三、使用STL

同样也是使用了缓冲区,不过stl的一些方法可以大大简便操作

使用vector

例题:给定一个单链表 L:L0→L1→…→Ln-1→Ln ,
将其重新排列后变为: L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

class Solution {
public:
        void reorderList(ListNode* head) {
            if (!head) return;
            vector<ListNode*> vec;
            ListNode* cur = head;

            while (cur) {
                vec.push_back(cur);
                cur = cur->next;
            }

            int left = 0;
            int right = vec.size() - 1;
            while (left < right) {
                vec[left]->next = vec[right];
                vec[right--]->next = vec[++left];
            }
            vec[left]->next = nullptr;
        }
};

vector简便了取未操作过的首、尾节点的方法

使用stack

例题:多级双向链表中,除了指向下一个节点和前一个节点指针之外,它还有一个子链表指针,可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项,依此类推,生成多级数据结构。给你位于列表第一级的头节点,请你扁平化列表,使所有结点出现在单级双链表中。

class Solution {
public:
    Node* flatten(Node* head) {
        if (!head) return head;
        stack<Node*> n;
        Node* p = head, *temp;
        while (true)
        {
            while(true)
            {
                if (p->child)
                {
                    if (p->next)
                        n.push(p->next);
                    p->next = p->child;
                    p->next->prev = p;
                    p->child = NULL;
                }
                if(!(p->next))
                    break;
                p = p->next;
            }
            if (n.empty())
                break;
            temp = p;
            p = n.top();
            n.pop();
            temp->next = p;
            p->prev = temp;
        }
        return head;
    }
};

使用了stack保证了后进先出,使得扁平化从最分支到主枝进行。

使用map

map确保了键值对的唯一性,可以快速解决重复值问题。例题:给你一个链表的头节点 head,请你编写代码,反复删去链表中由 总和 值为 0 的连续节点组成的序列,直到不存在这样的序列为止。删除完毕后,请你返回最终结果链表的头节点。

class Solution {
public:
    ListNode* removeZeroSumSublists(ListNode* head) {
        map<int, ListNode*> map;
        int sum = 0;
        ListNode* dummy = new ListNode(0), *cur = dummy;
        dummy->next = head;
        while (cur)
        {
            sum += cur->val;
            map[sum] = cur;
            cur = cur->next;
        }
        for(cur = dummy, sum = 0; cur; cur = cur->next)
        {
            sum += cur->val;
            if (map.find(sum) != map.end())
                cur->next = map[sum]->next;
        }
        return dummy->next;
    }
};

从头开始计算每到达一个节点时,前面所有节点值的总和,并且存在map中,如果有一个序列和为0,那么必有两个总和相等。再一次遍历时,如果某个总和在map中但不是当前节点,那么map中对应的节点和当前节点之间的和必定是0.

四、递归

链表的节点是相似的,可以使用递归解决。例题:给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。返回删除后的链表的头节点。

class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        if(!head) return NULL;
        if(head->val == val) return head->next;
        head->next = deleteNode(head->next,val);
        return head;
    }
};

通过递归,从头结点开始,下一个节点等于删除的只便跳过,重新连接链表。

五、补齐链表

当操作的两个链表长度不等时,可以先补齐至相同长度再操作。

例题:给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。你可以假设除了数字 0 之外,这两个数字都不会以零开头。

void addLinkList(struct ListNode* l1, struct ListNode* l2,int *cout)
{       
        if(l1==NULL||l2==NULL)
            return;
        if(l1->next!=NULL&&l2->next!=NULL)
            addLinkList(l1->next,l2->next,cout);
        int Sum=l1->val+l2->val+*cout;
        if(Sum>=10)
        {
            *cout=1;
            l1->val=Sum%10;
        }
        else
        {
            *cout=0;
            l1->val=Sum;
        }
        return;
}

六、原地修改

当复制的链表具有其他信息,不便于直接复制时,可以先原地复制,再间隔地挑出来。

例题:请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head) return NULL;
        Node* cur = head, *prev, *newhead;
        while(cur)
        {
            Node* newNode = new Node(cur->val);
            newNode->random = cur->random;
            newNode->next = cur->next;
            cur->next = newNode;
            cur = cur->next->next;
        }
        prev = head;
        newhead = head->next;
        while(prev)
        {
            cur = prev->next;
            if(cur->random)
                cur->random = cur->random->next;
            prev = prev->next->next;
        }
        prev = head;
        while(prev)
        {
            cur = prev->next;
            prev->next = prev->next->next;
            prev = prev->next;
            cur->next = prev ? prev->next : NULL;
        }
        return newhead;
    }
};

七、结合其他算法

例如结合BFS、DFS等搜索办法,DP、DC等优化算法等等

排序之基数排序:LSD & MSD

LSD原理:从最低位到最高位,将每个数字放入这一位数对应的桶中,再依次按顺序倒出,即优先度越高的元素(更高位的数),越在后面排序。

LSD代码:(使用了STL,提高输入数据大小、长度的灵活性)

#include <iostream>
#include <vector>
using namespace std;
const int DIGITS = 10;
int max(vector<int>);
int count_digit(int);
int get_digit(int num, int cnt);

int main()
{
	vector<int> datas = { 36,5,16,98,1123,1523,1698,5,98,95,47,32,36,48,10,423,455,127,432,123,834,678,176 };

	for (int digit = 0; digit < count_digit(max(datas)); digit++)
	{
		vector<int> t[DIGITS] = {};
		for (auto num : datas)
			(t + get_digit(num, digit))->push_back(num);
		datas.clear();
		for (int i = 0; i < DIGITS; i++)
			for (auto num : t[i])
				datas.push_back(num);
	}

	for (auto num : datas)
		cout << num << ' ';

	return 0;
}

int max(vector<int> datas)
{
	int max = 0;
	for(auto num : datas)
		max = num > max ? num : max;
	return max;
}

int count_digit(int n)
{
	if (n < 10)
		return 1;
	else
		return count_digit(n / 10) + 1;
}

int get_digit(int num, int cnt)
{
	if (cnt == 0)
		return num % 10;
	else
		return get_digit(num / 10, cnt - 1);
}

利用同样的办法,可以对所有输入的字符串以ASCII码顺序来排序:

#include <iostream>
#include <vector>
using namespace std;
const int DIGITS = 128; //ASCII码最大值为127
int max_digit(vector<string>); //获得所有字符串中最长的长度
char get_digit(string num, int cnt); //获得从右起第cnt位字符
int main()
{
    vector<string> datas = {};
    int count;
    string str;
    cin >> count;
    for (int i = 0; i < count; i++)
    {
        cin >> str;
        datas.push_back(str);
    }
    //对每一位字符倒入、倒出桶
    for (int digit = 0; digit < max_digit(datas) + 1; digit++)
    {
        vector<string> t[DIGITS] = {};
        for (auto num : datas)
            (t + (int)get_digit(num, digit))->push_back(num);
        datas.clear();
        for (int i = 0; i < DIGITS; i++)
            for (auto num : t[i])
                datas.push_back(num);
    }

    for (auto num : datas)
        cout << num << ' ';
    return 0;
}
int max_digit(vector<string> datas)
{
    int max = 0;
    for (auto num : datas)
        max = num.length() > max ? num.length() : max;
    return max;
}

char get_digit(string num, int cnt)
{
    if (cnt > num.length()) //如果访问的位不存在,用ASCII码最小的NULL填补
        return NULL;
    return num[num.length() - cnt];
}

MSD原理:(待更新)

聊聊动态规划之BFS/DFS+剪枝——以滑雪问题为例(下)

下篇接着上篇的思路,对DFS同样进行剪枝

DFS是以深度为优先的搜索方式,先沿着一枝探索到底,然后逐枝从探索过的节点回溯,再探索下一枝。这种情况下,后进先出的栈更适合存储节点信息。同样地,在选取了某个曾经到达过的节点时,判断这枝是否优先度更高,从而保留或者更新枝,达到剪枝的效果。

接着上一段同样滑雪问题的DFS解法代码:

#include <iostream>
#include <stack>
using std::stack;
using std::cout;

const int Length = 5;
const int Height[Length][Length] =
{
	{1, 2, 3, 4, 5},
	{16, 17, 18, 19, 6},
	{15, 24, 25, 20, 7},
	{14, 23, 22, 21, 8},
	{13, 12, 11, 10, 9}
};
int maxsteps[Length][Length] = { 0 };

const int direction[4][2] = { {1,0},{0,1},{-1,0},{0,-1} }; //右、下、左、上
//记录每一个点的坐标和从起点到这个点所用的步数
struct point
{
	int x;
	int y;
	int step;
	point(int i, int j, int k) :x(i), y(j), step(k) {} //使用初始化列表的构造函数
};
stack<point> pts;
int steps = 0;

void clear(stack<point>& q); //定义一个清空队列的函数
void clear(int arr[Length][Length]); //定义一个清空步数缓存的函数

void dfs(point pt)
{
	cout << "  正在点(" << pt.x << ',' << pt.y << ")\n";
	for (int dir = 0; dir < 4; dir++)
	{
		int next_x = pt.x + direction[dir][0];
		int next_y = pt.y + direction[dir][1];
		if (0 <= next_x && next_x < Length && 0 <= next_y && next_y < Length) //判断方向是否有效
		{
			cout << "    正在测试有效点(" << next_x << ',' << next_y << ")高度\n";
			if (Height[next_x][next_y] < Height[pt.x][pt.y]) //判断下一个方向是否高度更低,能够前进
			{
				if (maxsteps[next_x][next_y] < pt.step + 1) //判断如果向该方向再走一步,是否步数比其他已经尝试的方式都大(也就是砍掉不可能是最大的路径)
				{
					pts.push(point(next_x, next_y, pt.step + 1)); //将下一个可行的点存入队列中
					maxsteps[next_x][next_y] = pt.step + 1; //更新步数表格
				}
			}
		}
	}
	steps = pt.step + 1 > steps ? pt.step + 1 : steps;
	return;
}

int main()
{
	int max_steps = 0;
	for (int start_x = 0; start_x < Length; start_x++)
	{
		for (int start_y = 0; start_y < Length; start_y++)
		{
			cout << "正在以(" << start_x << ',' << start_y << ")为起点\n";
			steps = 0;
			clear(maxsteps);
			clear(pts);
			dfs(point(start_x, start_y, 1));
			while (!pts.empty())
			{
				point next_point = pts.top();
				pts.pop();
				dfs(next_point);
			}
			steps--; //因为最后一次无法前进的点还记了一次步数,所以要减掉
			cout << "步数: " << steps << '\n';
			max_steps = steps > max_steps ? steps : max_steps; //计入最大步数
		}
	}
	cout << max_steps;
	return 0;
}

void clear(stack<point>& s)
{
	stack<point> empty;
	swap(empty, s);
}

void clear(int arr[Length][Length])
{
	for (int i = 0; i < Length; i++)
	{
		for (int j = 0; j < Length; j++)
		{
			arr[i][j] = 0;
		}
	}
}

几乎没有做改变,仅仅是用栈替换了队列,来存储将要读取的信息。同样,输出的结果依然是25,不过,从中间的步骤可以看出二者的区别。

我们同样以(2,2)为起点,比较一下二者所探索的点的不同之处:

BFS
正在以(2,2)为起点
正在点(2,2)
正在测试有效点(3,2)高度
正在测试有效点(2,3)高度
正在测试有效点(1,2)高度
正在测试有效点(2,1)高度
正在点(3,2)
正在测试有效点(4,2)高度
正在测试有效点(3,3)高度
正在测试有效点(2,2)高度
正在测试有效点(3,1)高度
正在点(2,3)
正在测试有效点(3,3)高度
正在测试有效点(2,4)高度
正在测试有效点(1,3)高度
正在测试有效点(2,2)高度
正在点(1,2)
正在测试有效点(2,2)高度
正在测试有效点(1,3)高度
正在测试有效点(0,2)高度
正在测试有效点(1,1)高度
正在点(2,1)
正在测试有效点(3,1)高度
正在测试有效点(2,2)高度
正在测试有效点(1,1)高度
正在测试有效点(2,0)高度
正在点(4,2)
正在测试有效点(4,3)高度
正在测试有效点(3,2)高度
正在测试有效点(4,1)高度
正在点(3,3)
正在测试有效点(4,3)高度
正在测试有效点(3,4)高度
正在测试有效点(2,3)高度
正在测试有效点(3,2)高度
正在点(2,4)
正在测试有效点(3,4)高度
正在测试有效点(1,4)高度
正在测试有效点(2,3)高度
正在点(1,3)
正在测试有效点(2,3)高度
正在测试有效点(1,4)高度
正在测试有效点(0,3)高度
正在测试有效点(1,2)高度
……

正如图中,程序先按下、右、上、左的顺序发现四个红箭头都可以前往;然后先按下的红箭头到达队列中的第一个点,判断两个蓝箭头均可前往;接着按右的红箭头到达队列中的第二个点,本来绿箭头应该先到达黄色高亮的点,然而已经判断到了蓝箭头已曾到达过这个点了,并且绿箭头到达黄点也并不更优,于是剪断了这根枝,绿箭头只到达了右边和上面的点。

DFS
正在点(2,2)
正在测试有效点(3,2)高度
正在测试有效点(2,3)高度
正在测试有效点(1,2)高度
正在测试有效点(2,1)高度
正在点(2,1)
正在测试有效点(3,1)高度
正在测试有效点(2,2)高度
正在测试有效点(1,1)高度
正在测试有效点(2,0)高度
正在点(2,0)
正在测试有效点(3,0)高度
正在测试有效点(2,1)高度
正在测试有效点(1,0)高度
正在点(3,0)
正在测试有效点(4,0)高度
正在测试有效点(3,1)高度
正在测试有效点(2,0)高度
正在点(4,0)
正在测试有效点(4,1)高度
正在测试有效点(3,0)高度
正在点(4,1)
正在测试有效点(4,2)高度
正在测试有效点(3,1)高度
正在测试有效点(4,0)高度
正在点(4,2)
正在测试有效点(4,3)高度
正在测试有效点(3,2)高度
正在测试有效点(4,1)高度
正在点(4,3)
正在测试有效点(4,4)高度
正在测试有效点(3,3)高度
正在测试有效点(4,2)高度
正在点(4,4)
正在测试有效点(3,4)高度
正在测试有效点(4,3)高度
……

对于DFS,因为栈后进先出,所以按相反的顺序测试点,即左、上、右、下。判断时,点先按第一条路走到底,也就是红箭头一直走到(0,0)处后,再沿着树回溯。跳过一些步骤举例,例如回溯到黄色高亮点往蓝箭头方向搜索时,蓝箭头本来优先探索左方向,然而已经判断到了红箭头已曾到达过这个点了,并且蓝箭头到达这个点也并不更优,于是同样地剪断了这根枝,蓝箭头只能跳过向左,先向右进行搜索。

结论

动态规划利用存储已经运算过的内容,避免了对某些运算内容的重复运算,从而达到了减少运算量的目的。这是一种优化力度大,通用性强的计算机算法、以至数学方法。

聊聊动态规划之BFS/DFS+剪枝——以滑雪问题为例(上)

首先让我们看看BFS是个什么样的运作原理:

BFS是以广度为优先,也就是先把同级的每一个节点(例如2)先进行运算,同时将和它相邻的需要运算的节点入队,稍后再算(例如2对应的5、6),当同级的所有节点都运算完了的时候(2、3、4),由于队列先进先出的特点,自然轮到了下一级节点(5、6、7、8、9)

然后再看看在BFS中,树是如何剪枝的:

在很多问题中(尤其是棋盘移动之类的),会出现多个节点连上同一个节点的情况(如图中的2、3、4都连着下一级的6),这时候根据条件判断哪一条更优。例如图中红色数值越大越优,当判断到2连6的数字是20时,6的红色值被赋予20,与2相连;当判断到3连6的数字是30时,30比20大,6的红色值被赋予30,与3相连;当判断到4连6的数字是10时,10比30小,6的红色值不变,仍然与3相连;这样,就剪断了2和6,4和6的枝。

那么,没有剪枝的话,会是怎样的呢?

不多解释了,来看一个例子,题目粘下来是这样:

Michael喜欢滑雪,这并不奇怪, 因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子 

 1   2   3  4  5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度减小。在上面的例子中,一条可滑行的滑坡为24-17-16-1。当然25-24-23-…-3-2-1更长。事实上,这是最长的一条。

输出最长区域的长度,本例中是 25。

先上代码吧:

#include <iostream>
#include <queue>
using std::queue;
using std::cout;

const int Length = 5;
const int Height[Length][Length] =
{
	{1, 2, 3, 4, 5},
	{16, 17, 18, 19, 6},
	{15, 24, 25, 20, 7},
	{14, 23, 22, 21, 8},
	{13, 12, 11, 10, 9}
};
int maxsteps[Length][Length] = { 0 };

const int direction[4][2] = { {1,0},{0,1},{-1,0},{0,-1} }; //右、下、左、上
//记录每一个点的坐标和从起点到这个点所用的步数
struct point
{
	int x;
	int y;
	int step;
	point(int i, int j, int k):x(i),y(j),step(k) {} //使用初始化列表的构造函数
};
queue<point> pts;
int steps = 0;

void clear(queue<point>& q); //定义一个清空队列的函数
void clear(int arr[Length][Length]); //定义一个清空步数缓存的函数

void bfs(point pt)
{
	cout << "  正在点(" << pt.x << ',' << pt.y << ")\n";
	for (int dir = 0; dir < 4; dir++)
	{
		int next_x = pt.x + direction[dir][0];
		int next_y = pt.y + direction[dir][1];
		if (0 <= next_x && next_x < Length && 0 <= next_y && next_y < Length) //判断方向是否有效
		{
			cout << "    正在测试有效点(" << next_x << ',' << next_y << ")高度\n";
			if (Height[next_x][next_y] < Height[pt.x][pt.y]) //判断下一个方向是否高度更低,能够前进
			{
				if (maxsteps[next_x][next_y] < pt.step + 1) //判断如果向该方向再走一步,是否步数比其他已经尝试的方式都大(也就是砍掉不可能是最大的路径)
				{
					pts.push(point(next_x, next_y, pt.step + 1)); //将下一个可行的点存入队列中
					maxsteps[next_x][next_y] = pt.step + 1; //更新步数表格
				}
			}
		}
	}
	steps = pt.step + 1 > steps ? pt.step + 1 : steps;
	return;
}

int main()
{
	int max_steps = 0;
	for (int start_x = 0; start_x < Length; start_x++)
	{
		for (int start_y = 0; start_y < Length; start_y++)
		{
			cout << "正在以(" << start_x << ',' << start_y << ")为起点\n";
			steps = 0;
			clear(maxsteps);
			clear(pts);
			bfs(point(start_x, start_y, 1));
			while (!pts.empty())
			{
				point next_point = pts.front();
				pts.pop();
				bfs(next_point);
			}
			steps--; //因为最后一次无法前进的点还记了一次步数,所以要减掉
			cout << "步数: " << steps << '\n';
			max_steps = steps > max_steps ? steps : max_steps; //计入最大步数
		}
	}
	cout << max_steps;
	return 0;
}

void clear(queue<point>& q) 
{
	queue<point> empty;
	swap(empty, q);
}

void clear(int arr[Length][Length])
{
	for (int i = 0; i < Length; i++)
	{
		for (int j = 0; j < Length; j++)
		{
			arr[i][j] = 0;
		}
	}
}

首先定义好高度的二维数组,以及用来存到某一点所需步数的临时二维数组;为了代码简洁,同时定义好含四个方向的数组,以及包含着x、y坐标和已经移动的步数的point结构(并且写好构造函数)

主要思路是这样的:

遍历所有的起点
–清空临时数据
–检测起点的可移动信息,并将可以去的下一个点入队(函数bfs())
–队列非空时,对每个元素再检测可移动信息,并将下一个点入队(函数bfs())
–计入每个起点最终的最大移动步数

函数bfs的思路:

遍历四个方向的下一个点进行测试
–判断该方向下一个点是否还在二维数组中
—-判断下一个点的高度是否比当前点更小
——判断下一个点是否没有别的路径到达过,或者有但是路径比正在测试的路径短(注意:这里正是树剪枝的办法,直接剪掉不可能是最长的路径)
——–如果均为是,将下一个可以到达的点入队,并且更新步数的表格
遍历完之后,总步数+1(因为最后一次无路可走也会导致步数+1,最终结果要-1)

样例输出:

首先,最终结果输出的是25,也就是从(2,2)点的“25”开始出发的最长路径。

然后以图上的(4,4),既“9”为原点为例,可以看出探索的路径:
最初在起点(4,4),判断到下一个存在的点有(3,4)和(4,3),挑选出没有经过过、并且高度更低的点(3,4),再判断存在的点(4,4),(2,4)和(3,3)。因为高度只能下降,可以没有必要去把曾经经过的点标记为已经过。通过多次测试,最终按照9、8、7、6、5、4、3、2、1的顺序找到了步数为9的最大路径。

以下是完整的输出结果: