“数据结构与算法”课程设计指导书
计算机与信息学院
2013年6月
目录
第1章概述 (1)
第2章设计完成步骤 (2)
2.1系统分析与系统设计 (2)
2.2详细设计与编码 (2)
2.3上机调试和测试 (2)
2.4撰写课程设计报告 (2)
第3章课程设计报告样例 (4)
第4章选题及评分 (10)
4.1 选题 (10)
4.2 编程语言 (10)
4.3 验收和答辩 (10)
4.4 成果提交 (10)
4.5 评分 (10)
第5章设计课题 (12)
1. 字符串距离（90分） (12)
2. 后缀表达式计算器（全部完成100分，完成①和②90分） (12)
3. 两个小游戏（90分） (12)
4. 二叉树结点染色问题（95分） (13)
5. 打印机任务队列（85分） (14)
6. 输出满足条件整数（75分） (14)
7. 布尔表达式真值问题（90分） (14)
8. 谣言传播问题（95分） (15)
9. 盒子分形（95分） (15)
10. 网络布线(90分) (16)
11. 数独游戏(95分) (17)
12. 中国邮路问题(100分) (19)
13. 最大匹配问题(80分) (19)
14. 最佳匹配问题(80分) (20)
15. 构造哈夫曼树(85分) (21)
16. 哈夫曼树编码文件压缩(95分) (21)
17. 排序算法及性能对比(85分) (21)
18. 模拟电梯控制系统(85分) (22)
19. 决策树算法实现(100分) (22)
20. 关联规则求解算法Apriori的实现(100分) (23)
21. 迷宫问题(90分) (24)
22. 广义表实现(80分) (24)
23. 求无向图简单路径(90分) (25)
24. 求有向图简单路径(90分) (25)
25. 指针式屏幕时钟(90分) (25)
26. 简单工资管理系统设计(85分) (26)
27. 简单学生成绩管理系统设计(85分) (26)
28. 散列表的设计与实现(90分) (27)
29. 宿舍管理查询软件设计与实现(85分) (27)
30. 求最长公共子串(80分) (27)
31. 统计英文单词数(90分) (27)
32. 本科生导师制问题(90分) (28)
33. 求镜像二叉树(75分) (28)
34. 栈的一种应用(70分) (28)
35. 矩阵位置旋转算法(75分) (29)
36. 记事簿的设计与实现(85分) (29)
37. 集合运算(85分) (29)
38. 矩阵运算(85分) (29)
39. 保龄球计分(80分) (30)
40. 车位管理(75分) (30)
41. 学生成绩管理系统(85分) (31)
42. 英文单词填空游戏(80分) (32)
43. 城市距离问题(100分) (32)
44. 实现简单的数字图像处理(100分) (32)
45. 一字棋游戏设计实现(100分) (33)
46. 扑克牌洗牌发牌过程模拟(80分) (33)
47. 简单英文词典(75分) (34)
48. 字符串模式匹配(90分) (34)
49. N皇后问题(95分) (34)
50. K-means算法(100分) (35)
51. 简单通信录管理软件设计(80分) (35)
52. 简单汽车租赁管理软件设计(85分) (35)
53. 机器人搬箱子问题(100分) (35)
54. 猴子和香蕉问题(100分) (36)
55. 野人修道士问题(100分) (36)
56. 八数码问题(100分) (37)
57. 平衡二叉树（A VL树）(95分) (38)
58. B树(95分) (38)
59. B+树(95分) (38)
60. 二叉树相似问题(85分) (39)
第1章概述
课程设计是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的、必不可少的一个教学环节。通常，课程设计中的问题比平时的习题复杂的多，也更接近实际。课程设计着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上的知识变“活”，起到深化理解和灵活掌握教学内容的目的。平时的习题较偏重于如何编写功能单一的“小”算法，局限于一个或两个知识点，而课程设计题是软件设计的综合训练，包括问题分析，总体结构设计，用户界面设计、程序设计基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。此外，还有很重要的一点是：计算机是比任何教师更严厉的检查者。
为达到上述目的，使学生更好地掌握程序设计的基本方法和C++语言的应用，本课程安排了课程设计环节，提供了各类题目供学生选择。每个设计题采取了统一的格式，由问题描述、基本要求、测试数据、实现提示和选做内容等五个部分组成。问题描述旨在为学生建立问题提出的背景，指明问题“是什么”。基本要求则对问题进一步求精，划出问题的边界，指出具体的参量或前提条件，并规定该题的最低限度要求。测试数据部分旨在为检查学生上机作业提供方便。在实现提示部分，对实现中的难点及其解法思路等问题作了简要提示，提示的实现方法未必是最好的，学生不应拘泥与此，而应努力设计和开发更好的方法和结构。选做部分向那些尚有余力的读者提出了更高的要求，同时也能开拓其它读者的思路，在完成基本要求时就力求避免就事论事的不良思想方法，尽可能寻求具有普遍意义的解法，使得程序结构合理，容易修改、扩充和重用。
第2章设计完成步骤
2.1系统分析与系统设计
“分析就是在采取行动之前，对问题的研究”（Demarco,1978）。系统分析在软件开发过程中是非常重要的，其任务就是通过对问题本身的研究，产生一个系统需要做什么的规范的、一致的和可行的需求说明。在此基础上，确定系统中所需考虑的类（对象）、类之间的关系、本系统中各个类所涉及的属性及针对这些属性的操作。类及类之间的关系可用类图来表示，对象之间的消息传递可用箭头表示，另外一些重要的操作应给出规格说明。
2.2详细设计与编码
对类中的属性和操作从实现的角度（如可扩充、在派生类中能否直接使用或只需少量修改、访问的效率和方便性等）进一步考察；对类中的操作（即方法）进一步求精：用if、while、for和赋值语句加上自然语言写出算法框架；同时考虑能否使用已有类库（包括直接使用或通过派生）以减少编程的工作量和提高程序的可靠性。
编码，即程序设计，是对详细设计的结果的进一步求精，用面向对象语言（如C++）表达出来。在充分理解和把握语言运行机制的基础上，编写出正确的、清晰的、易读易改和高效率的程序。另外，在标识符的命名、代码的长度（一个方法长度一般不超过40行，否则应划分为两个或多个方法）、程序书写的风格（如缩进格式、空格（空行）的应用、注释等）方面也应注意，遵循统一的规范。
2.3上机调试和测试
上机时要带一本面向对象语言的教材，若有开发环境的用户指南（手册）及类库（库函数）手册则更好。应仔细阅读程序编译和连接时的错误信息（通常是英文的），弄清其确切含义，提高调试效率。要学习并掌握开发环境所提供的调试工具。
经过调试，能够运行的的程序并非就是一个正确的程序。实际上，在上机之前，就应根据系统的需求设计相应的测试数据集，特别是一些异常情况的处理（如用户输入数据未按指定格式、数据极大或极小时程序如何处理等一些极端的情况）。
2.4撰写课程设计报告
课题设计实现完成后，按规范要求撰写课程设计报告，报告一般要求阐述的内容如下：1. 需求和规格说明
描述问题，简述题目要解决的问题是什么？规定软件做什么。原题条件不足时补全
2. 设计
(1) 设计思想：程序结构（如类图），重要的数据结构。主要算法思想（文字描述，不要画框图）
(2) 设计表示：类名及其作用，类中数据成员名称及作用，类中成员函数原型及其功能，可以用表格形式表达。
(3) 实现注释：各项要求的实现程度、在完成基本要求的基础上还实现了什么功能？
(4) 详细设计表示：主要算法的框架及实现此算法的成员函数接口。
3. 用户手册
即使用说明（包括数据输入时的格式要求）。
4. 调试及测试
调试过程中遇到的主要问题是如何解决的；对设计和编码的回顾讨论和分析；程序运行的时空效率分析；测试数据集；运行实例；改进设想；经验和体会等。
5. 附录
(1) 源程序清单：打印文本和磁盘文件，磁盘文件是必须的。源程序要加注释，除原有注释外再用钢笔加一些必要的注释和断言。
(2) 测试数据：即列出测试数据集
(3) 运行结果：上面测试数据输入后程序运行的结果
可以根据设计课题的实际情况对以上内容进行增减。
第3章课程设计报告样例
以下报告样例仅供撰写设计报告时参考，学生可根据选题的实际情况进行增减。
（报告封面）
“数据结构与算法”
课程设计报告
（一）需求和规格说明
某小型公司，主要有四类人员：经理、技术人员、销售经理和推销员。要求存储这些人员的姓名、编号、级别、当月薪水，计算月薪总额并显示全部信息。
人员编号基数为1000，每输入一个人员的信息，编号顺序加1。
程序要对所有人员有提升级别的功能。为简单起见，所有人员的初始级别均为1级，然后进行升级，经理升为4级，技术人员和销售经理升为3级，推销员仍为1级。
月薪计算办法是：经理拿固定月薪8000元；技术人员按每小时100元领取月薪；推销员的月薪按该推销员当月销售额的4%提成；销售经理既拿固定月薪也领取销售提成，固定月薪为5000元，销售提成为所管辖部门当月销售总额的5?。
（二）设计
根据上述需求，设计一个基类employee,然后派生出technician（技术人员）类、manager（经理）类和salesman（推销员）类。由于销售经理（salesmanager）既是经理又是销售人员，兼具两类人员的特点，因此同时继承manager和salesman 两个类。
在基类中，除了定义构造函数和析构函数以外，还应统一定义对各类人员信息都应有的操作，这样可以规范各派生类的基本行为。但是各类人员的月薪计算方法不同，不能在基类employee中统一定义计算方法。各类人员信息的显示内容也不同，同样不能在基类中统一定义显示方法。因此，在employee类中用纯虚函数的方式定义了计算月薪函数pay()和显示信息函数displayStatus()，然后在派生类中再根据各自的同名函数实现具体的功能。
由于salesmanager的两个基类又有公共基类employee，为避免二义性，这里将employee类设计为虚基类。
系统类图
（三）用户手册
程序运行时，首先提示输入雇员姓名。
对于经理直接输出其工资及其它信息；
对于技术人员，程序提示输入其本月工作时数，然后输出其工资及其它信息；
对于推销员，程序提示输入其本月销售额，然后输出其工资及其它信息；
对于销售经理，程序提示输入其管辖部门本月销售总额，然后输出其工资及其它信息。
（四）调试及测试
由于公司每增加一个雇员，无论他（她）是哪一类人员,其编号均是顺序加1，也就是employee类的所有派生类对象创建时，都要访问同一个employeeNo，因此将employeeNo定义为静态数据成员。
（五）运行实例：
please input employee's name: zhang
please input employee's name: wang
please input employee's name: Li
please input employee's name: zhao
input zhang the workHours of this month: 56
Technician: zhang No: 1001 month salary: 5600
Technician: zhang No: 1001 grade: 3 this month salary: 5600
Manager: wang No: 1002 month salary: 8000
Manager: wang No: 1002 grade: 4 this month salary: 8000
input Li the sales of this month: 47900
Salesman: Li No: 1003 month salary: 1916
Salesman: Li No: 1003 grade: 1 this month salary: 1916
input zhao the total sales of the department of this month: 123654
salesman: zhao No: 1004 month salary: 5618.27
salesmanager: zhao No: 1004 grade: 3 this month salary: 5618.27
（六）进一步改进
（1）目前程序中，经理月薪，技术人员的小时酬金和销售人员的销售额提成比例均是固定的，这不适应不同公司的需要，可考虑用带参数的构造函数来解决。
（2）销售经理月薪计算中，要输入其管辖部门当月销售总额。实际上，这可以通过将本部门所有推销员销售额相加而得到。可以考虑在推销员类中增加所属部门等属性来完成这方面的功能。
（七）心得体会
（可描述课程设计过程中出现的主要问题、原因及解决方法，课程设计的主要收获等）
（八）对课程设计的建议
（九）附录 源程序
第4章选题及评分
4.1 选题
学生可在给出的设计题目中选择一个题目完成设计任务，每个题目都给出了难度参考分值，请同学们选题时注意。
选题时原则上一个自然班级同学的设计题目不能重复，即不能有两名以上同学完成同一个题目。
每个同学独立完成设计任务，即不能有两名以上同学合作完成同一设计任务。
同学可以自选设计题目，对自选的题目必须向指导老师书面申请，经指导老师批准后有效。
4.2 编程语言
鼓励使用C或C++完成设计任务。同学也可以选择其它自己熟悉的语言完成。同等条件下，使用C或C++完成可获适当加分。
有些设计题目鼓励实现图形用户界面，比如用MFC实现，凡使用GUI实现可获得适当加分。
4.3 验收和答辩
在课程设计执行期的最后一个工作日，由指导老师对每个学生设计的完成情况进行验收和答辩。
学生向指导老师演示设计的完成情况和效果。老师针对具体情况向学生提问。
4.4 成果提交
设计工作完成后需提交课程设计报告的纸质文档和电子文档。电子文档首先提交到班长处，班长打包后再提交给指导老师。
4.5 评分
课程设计成绩按优秀、良好、中等、及格和不及格五个等级评分，评分考察的因素如下：
1.设计题目的难度系数。
2.现场验收答辩情况。
3.设计的实现完成情况。
4.课程设计报告完成情况。
凡未经验收答辩、未按期提交纸质版和电子版设计报告的同学一律按不及格处理。
第5章设计课题
1. 字符串距离（90分）
目的：字符串是一种基础且广泛使用的数据结构，与字符串相关的题目既可以考察基本程序设计能力和技巧，也可以考查较强算法设计能力。
题目：求字符串之间距离
要求：设有字符串X，称在X的头尾及中间插入任意多个空格后构成的新字符串为X的扩展串，如字符串X为―abcbcd‖，则字符串―abcb□cd‖，―□a□bcbcd□‖和―abcb□cd□‖都是X的扩展串，这里―□‖代表空格字符。如果A1是字符串A的扩展串，B1是字符串B的扩展串，A1与B1具有相同的长度，那么定义字符串A1与B1的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定义为它们的ASCII码的差的绝对值，而空格字符与其它任意字符之间的距离为已知的定值K，空格字符与空格字符的距离为0。在字符串A、B的所有扩展串中，必定存在两个等长的扩展串A1、B1，使得A1与B1之间的距离达到最小，将这一距离定义为字符串A、B的距离。请编写程序，求出字符串A、B的距离。
2. 后缀表达式计算器（全部完成100分，完成①和②90分）
目的：后缀表达式不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则，如：2 1 + 3 *,即(2 + 1) * 3. 通过本课程设计，应使学生掌握后缀表达式的特点、栈的基本方法和基本原理，培养学生运用语言编程及调试的能力，运用数据结构解决简单的实际问题的能力，为后续计算机专业课程的学习打下坚实的基础。
要求：实现一个简单的后缀表达式计算器。假定表达式里的基本数值为实数，可用的运算符包括+,-,*,/,^，其中的^ 表示求幂运算。
①假定输入表达式里的数和运算符之间都有空格，这样可以简化输入的处理；
②输入的算术表达式以分号为结束符。计算器应该能输入并计算一系列表达式，遇到一行的第一个字符就是分号时程序结束。
③上题的计算器增加一元函数功能，允许表达式里写sin, cos, tan, log（自然对数）等函数，还可以考虑加入自定义的其他数学函数。（选做）
3. 两个小游戏（90分）
目的：很多精妙的数学理论往往都以有趣的游戏形式表现出来，正是这些有趣的小游戏使得高深的数学理论被广泛的传播和接受。通过编程实现这些“数学游戏”可以提高学生的编程技巧和算法设计能力，提高解决实际问题的能力。
要求：
猜数字（文曲星游戏）
电脑随机生成一个0~9999之间的整数，若为23，则记为0023。玩家去猜，电脑将对玩家的答案做个评价，然后玩家再按电脑的评价重新猜，一共8次机会，猜对为赢。
比如：
电脑随机生成7859，若玩家第一次输入：1234，程序返回0A0B，A代表数字和位置都猜对，B代表数字猜对，但位置不对。
若玩家第二次输入：5678，则返回0A2B，因为78都是原整数中的，但是位置不对。
若玩家第三次输入：0896，则返回1A1B……
依次，直至玩家输入7859，返回4A0B并终止程序。
记住，只有8次机会哦。
生命游戏（经典游戏，实现起来不难，正因为实现简单却变化繁复所以才成为经典）https://www.doczj.com/doc/41472558.html,/view/162057.htm
我们可以把计算机中的宇宙想象成是一堆方格子构成的封闭空间，尺寸为N的空间就有N*N个格子。而每一个格子都可以看成是一个生命体，每个生命都有生和死两种状态，如果该格子生就显示蓝色，死则显示白色。每一个格子旁边都有邻居格子存在，如果我们把3*3的9个格子构成的正方形看成一个基本单位的话，那么这个正方形中心的格子的邻居就是它旁边的8个格子。
每个格子的生死遵循下面的原则：
①如果一个细胞周围有3个细胞为生（一个细胞周围共有8个细胞），则该细胞为生（即该细胞若原先为死，则转为生，若原先为生，则保持不变）。
②如果一个细胞周围有2个细胞为生，则该细胞的生死状态保持不变；
③在其它情况下，该细胞为死（即该细胞若原先为生，则转为死，若原先为死，则保持不变设定图像中每个像素的初始状态后依据上述的游戏规则演绎生命的变化，由于初始状态和迭代次数不同，将会得到令人叹服的优美图案）。
4. 二叉树结点染色问题（95分）
目的：二叉树是常用的重要非线性数据结构，在客观世界中有着广泛的应用。通过本题可以加深对于二叉树这一数据结构的理解。掌握二叉树的存储结构及各种操作。
要求：一棵二叉树可以按照如下规则表示成一个由0、1、2组成的字符序列，我们称之为―二叉树序列S‖：
例如，下图所表示的二叉树可以用二叉树序列S=21200110来表示。
任务是要对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或蓝色。并且，一个节点与其子节点的颜色必须不同，如果该节点有两个子节点，那么这两个子节点的颜色也必须不相同。给定一棵二叉树的二叉树序列，请求出这棵树中最多和最少有多少个点能够被染成绿色。
5. 打印机任务队列（85分）
目的：通过本课程设计，应使学生掌握队列的基本方法和基本原理，培养学生运用语言编程及调试的能力，运用数据结构解决简单的实际问题的能力，为后续计算机专业课程的学习打下坚实的基础。
要求：打印机的打印队列中，每一个打印任务都有一个优先级，为1~9的一个整数（9的优先级最高，1的优先级最低），打印按如下方法进行.
（1）取出打印队列中队首的打印任务J；
（2）如果打印队列中存在优先级高于J的打印任务，则将J移动到打印队列的队尾；否则，打印J.
现在的问题是，要确定你要打印的文件何时打印完毕。给定当前打印队列（一个优先级队列）和你的打印任务在当前打印队列中的位置，确定你的打印任务完成时需要多长时间。为了简化问题，假定没有新的打印任务加入到打印队列中；并且，假定完成任何一个打印任务均需要1min时间，向打印队列中加入一个打印任务或从打印队列中移除一个打印任务不需要时间。
例如，当前打印队列为―1 1 9 1 1 1‖且你的打印任务在队首时，需要5min.
6. 输出满足条件整数（75分）
目的：通过本课程设计，培养学生算法设计的能力，运用语言编程及调试的能力，运用计算机解决实际问题的能力，为后续计算机专业课程的学习打下坚实的基础。
要求：输入一个正整数N，从小到大输出满足如下条件的整数：
是7和7的倍数
包含7的数字
且输出的数字≤ N
例如（17，27，37...70，71，72，73...）
7. 布尔表达式真值问题（90分）
目的：本课程设计是求中缀算术表达式真值问题。求中缀算术表达式值的问题是数据结构中栈的一个典型应用。通过本题，学生应掌握中缀表达式和后缀表达式的转换方法和后缀表达
式求值问题。
要求：已知某种类型的布尔表达式由―T‖、―F‖、―！‖、―&‖和―|‖组成，其中，―T‖代表真值True，―F‖代表真值False，―！‖代表逻辑非运算，―&‖代表逻辑与运算，“|”代表逻辑或运算。并且，运算符―！‖、―&‖和―|‖的优先级为：―！‖最高，―|‖最低，―&‖介于―！‖和―|‖之间。你的任务是，计算给定布尔表达式的真值。
例如，布尔表达式―(T|T)&F&(F|T)‖的真值为―F‖.
8. 谣言传播问题（95分）
目的：通过本课程设计，应使学生掌握如何用图结构解决实际问题的能力，加深对于图结构的理解和认识。掌握图的存储方法和关于图的经典算法。提高学生的程序设计能力。
要求：股票经纪人往往对谣言很敏感，你的老板希望你能找到一个好方法向他们散布谣言，从而使他在股市占有战术优势。为了达到最佳效果，需要谣言传播的尽量快。不幸的是，股票经纪人只相信从他们信任的信源传播来的消息，因此，在你散布谣言之前，需要对他们的联系网进行详细考察。对于一个股票经纪人，他需要一定时间才能将信息传送给他的联系人，给你这些信息，你的任务是，决定选谁作为第一个传送谣言的人，以使谣言传遍所有人的时间最短，当然，如果谣言不能传遍所有人的话，你也要给出说明。
例如，假设共有3个联系人，联系人1传递信息给联系人2和3所有的时间分别为4和5；联系人2传送信息给联系人1和3所有的时间分别为2和6；联系人3传送信息给联系人1和2所有的时间均为2，则选择联系人3作为第一个传送谣言的人，可以使谣言传遍所有的人时间最短，为2.
（选择有向图中的一个源点，使它到其余各顶点的最短路径中最长的一条路径最短）
9. 盒子分形（95分）
目的：递归是基本的算法思想和设计方法之一，也是数据结构重点讲授的部分，是许多算法的基础，对它们的理解和运用直接关系着其他算法的理解和应用。因此，熟练掌握递归是十分重要的。通过本题，应使学生加深对于递归方法的理解，提高运用递归解决问题的能力。
要求：分形是一种具有自相似性的现象，在分形中，每一组成部分都在特征上和整体相似，
只不过仅仅是缩小了一些而已，一种盒子分形定义如下：
（1）规模为1的盒子分形为
X
（2）规模为2的盒子分形为
X X
X
X X
（3）若用B(n - 1)表示规模为n-1的盒子分形，则规模为n的盒子分形为
B(n - 1) B(n - 1)
B(n - 1)
B(n - 1) B(n - 1)
你的任务是，输出规模为n的盒子分形。
例如，规模为3的盒子分形输出如下：
X X X X
X X
X X X X
X X
X
X X
X X X X
X X
X X X X
10. 网络布线(90分)
计算机网络要求网络中的计算机被连接起来，本问题考虑一个“线性”的网络，在这一网络中计算机被连接到一起，并且除了首尾的两台计算机只分别连接着一台计算机外，其它任意一台计算机恰连接着两台计算机。图1中用圆点表示计算机，它们的位置用直角坐标表示。网络连接的计算机之间的距离单位为英尺。
由于很多原因，我们希望使用的电缆长度应可能地短。你的问题是去决定计算机应如何被连接以使你所使用的电缆长度最短。在设计方案施工时，电缆将埋在地下，因此连接两台计算机所要用的电缆总长度等于计算机之间的距离加上额外的16英尺电缆，以从地下连接到计算机，并为施工留一些余量。
下图是计算机的最优连接方案，这样一个方案用电缆的总长度是：
(4 + 16) + (5 + 16) + (5.38 + 16) + (11.18 + 16) = 90.01英尺
基本要求：
输入网络中的计算机总数和每台计算机的坐标。
输出使电缆长度最短的连接方案。给出最优连接方案中每两台相邻计算机之间的距离，以及总的电缆长度。
提高要求：
参考图2，用图形化的方式显示结果，包括点的坐标、最优路径、相邻计算机之间的距离。
11. 数独游戏(95分)
在一个9×9的大正方形中，包含9个3×3的小正方形。如图3所示。可以看到，其每行、每列、每个小正方形，都有9个空格。
要求只用1到9这些数字，填满大正方形中所有的81个空格，同时满足：
（1）在每列的9个空格中分别填入1到9，且每个数字在此列中只能出现一次；
（2）在每行的9个空格中分别填入1到9，且每个数字在此行中只能出现一次；
（3）在每个小正方形的9个空格中分别填入1到9，且每个数字在此正方形中只能出现一次；
游戏一开始会给定了某些空格的值。参加游戏的人根据这些已知的值以及上面的约束条件，推理出剩余的空格的值。