本书是计算机领域本科教育教学改革试点工作（“101计划”）核心课程配套实践教材。本书针对“软件工程”课程实践教学的特点、难点和重点，以能力和素质培养为目标，围绕实践任务的设计、实施和考评三个方面，阐述了如何基于群智和开源的方法，依托相关的软件工具和平台，开展“软件工程”课程教学实践。

全书共8章，主要包括：概论，软件工程基础，实践任务的设计与要求，实践支撑软件工具，阅读、分析和维护开源软件（实践任务一），开发软件系统一、开发软件系统二（实践任务二），实践考评方法。

本书可作为计算机大类专业本科软件工程实践教学教材，也可作为软件工程师的参考用书。为便于教学，作者建设了软件工程教学生态，提供完整的教学资源，包括：实践教学PPT，实践任务设计，软件文档模板，实践考评样例，软件项目案例（含UML模型、软件文档、源代码、可运行程序等），线上实践，学习社区，支撑工具等。

前辅文
第1章 绪论
  1.1 背景
   1.1.1 计算机软件的变化
   1.1.2 软件工程的发展
   1.1.3 对软件人才培养提出的要求
  1.2 “软件工程”课程的特点
  1.3 “软件工程”课程实践教学的目标和要求
  1.4 现行实践教学存在的问题
  1.5 互联网和开源软件带来的启发
  1.6 “软件工程”课程实践教学的指导思想
  1.7 本书案例说明
  本章小结
  实践作业
第2章 软件工程基础
  2.1 软件工程概述
   2.1.1 软件工程的思想
   2.1.2 软件工程的目标
  2.2 经典软件过程模型
   2.2.1 瀑布模型
   2.2.2 原型模型
   2.2.3 迭代模型
  2.3 敏捷方法
   2.3.1 敏捷方法的理念和价值观
   2.3.2 敏捷方法的实施原则
  2.4 面向对象软件开发方法
   2.4.1 核心概念
   2.4.2 基本思想和方法
   2.4.3 统一建模语言
  2.5 开源软件及群体化开发方法
   2.5.1 开源软件
   2.5.2 群体化软件开发方法
   2.5.3 基于Issue的任务管理
   2.5.4 基于Git的代码版本管理
   2.5.5 基于Pull Request的分布式协同开发
  2.6 基于群智的软件开发知识分享
  2.7 开源软件的获取和利用
   2.7.1 开源软件社区
   2.7.2 开源软件项目资源
   2.7.3 开源软件的使用
  2.8 软件项目的组织方式
   2.8.1 结对模式
   2.8.2 团队模式
   2.8.3 社区模式
  本章小结
  实践作业
第3章 实践任务的设计与要求
  3.1 实践设计理念和指导思想
   3.1.1 以三类能力培养为目标
   3.1.2 循序渐进、逐层递进地开展实践
   3.1.3 基于开源软件的实践教学方法
   3.1.4 基于群智知识的实践教学方法
   3.1.5 运用群体化软件开发技术
  3.2 实践任务的整体设计
  3.3 “阅读、分析和维护开源软件”实践任务的设计
   3.3.1 实践内容
   3.3.2 实践要求
  3.4 “开发软件系统”实践任务的设计
   3.4.1 实践内容
   3.4.2 实践要求
  本章小结
  实践作业
第4章 实践支撑软件工具
  4.1 实践实施的支撑工具概述
  4.2 软件开发的支撑工具
   4.2.1 软件建模工具
   4.2.2 编码实现工具
   4.2.3 软件测试工具
   4.2.4 代码质量分析工具
   4.2.5 软件文档撰写工具
  4.3 实践实施工具
   4.3.1 软件开发实践支撑工具EduCoder
   4.3.2 软件工程学习社区LearnerHub
  本章小结
  实践作业
第5章 阅读、分析和维护开源软件
  5.1 实践实施的过程和原则
   5.1.1 实施过程和活动
   5.1.2 实施原则和要求
   5.1.3 实践输出及成果
  5.2 开源软件案例介绍：“小米便签”软件MiNotes
  5.3 实践准备工作
   5.3.1 选择和准备开源软件
   5.3.2 组织实践人员
   5.3.3 布置实践任务和创建实践项目
   5.3.4 访问和加入开源社区
  5.4 阅读和标注开源软件
   5.4.1 泛读开源软件代码
   5.4.2 理解代码语义
   5.4.3 标注代码注释
   5.4.4 输出实践成果
  5.5 分析开源软件
   5.5.1 分析软件架构
   5.5.2 分析实现类图
   5.5.3 分析软件质量
   5.5.4 输出实践成果
  5.6 维护开源软件
   5.6.1 纠正开源代码缺陷
   5.6.2 完善开源软件功能
   5.6.3 演示经维护后的开源软件
   5.6.4 输出实践成果
  5.7 借助群智知识开展实践
  5.8 实践总结
  5.9 实践任务的拓展和剪裁
  本章小结
  实践作业
第6章 开发软件系统（一）
  6.1 实践实施的过程和原则
   6.1.1 实施过程和活动
   6.1.2 实施原则和要求
   6.1.3 实践输出及成果
  6.2 实践准备工作
   6.2.1 实践宣传和动员
   6.2.2 组织实践人员
   6.2.3 布置实践任务和创建实践项目
   6.2.4 访问和加入开源社区
  6.3 实践案例介绍：“空巢老人看护”软件ElderCarer
  6.4 需求获取与分析
   6.4.1 任务、过程与输出
   6.4.2 实践要求与原则
   6.4.3 软件需求获取与构思
   6.4.4 软件需求建模与分析
   6.4.5 软件需求文档化与评审
   6.4.6 迭代开发过程中的软件需求变更管理
   需求获取与分析小结
  实践作业
第7章 开发软件系统（二）
  7.1 软件设计与建模
   7.1.1 任务、过程与输出
   7.1.2 软件设计的策略和原则
   7.1.3 基于开源和群智的软件设计方法
   7.1.4 软件体系结构设计
   7.1.5 用户界面设计
   7.1.6 用例设计
   7.1.7 子系统/构件设计
   7.1.8 类设计
   7.1.9 数据设计
   7.1.10 软件设计的整合、文档化及评审
   软件设计与建模小结
  7.2 代码编写与测试
   7.2.1 任务、过程与输出
   7.2.2 编写代码
   7.2.3 软件测试
   7.2.4 程序调试和修复
   7.2.5 部署和运行
   代码编写与测试小结
  7.3 借助群智知识开展实践
   7.3.1 在软件开发知识分享社区中寻找问题的解答
   7.3.2 在开源社区中与软件开发者群体进行交互
   7.3.3 搜寻和重用开源软件
  7.4 实践总结
  7.5 实践设计的剪裁
  本章小结
  实践作业
第8章 实践考评方法
  8.1 实践考评的基本原则
  8.2 实践考评的方法和手段
  8.3 “阅读、分析和维护开源软件”实践任务的考评方法
   8.3.1 考评内容
   8.3.2 考评方法
   8.3.3 持续点评
  8.4 “开发软件系统”实践任务的考评方法
   8.4.1 考评内容
   8.4.2 考评方法
   8.4.3 持续点评
  8.5 实践实施及成效
  本章小结
  实践作业
后记
参考文献

“数据结构”是计算机类专业最重要的专业基础课之一，主要教授数据的有效组织方法以及解决实际问题的各种经典算法。而经典算法的威力，往往是在处理大规模数据量时才真正体现。只有让学生动手解决规模较大的问题，才能帮助学生建立感性认识，更好地理解数据结构和算法存在的意义。

本书是计算机“101计划”核心课程“数据结构”的实践教材，与主教材《数据结构》（俞勇等主编，高等教育出版社出版）配套使用。书中给出了主教材中全部198段算法伪代码的C语言实现源代码；此外，围绕主教材中的主要知识点，本着循序渐进、由浅入深的原则，设计了47道基础练习题和71道进阶实验题，并提供详细解答，为不同层次的读者提供帮助。希望有兴趣的读者能在精读基础练习的基础上，自己动手实现一部分进阶实验，达到充分锻炼分析问题、解决问题能力的目的，使数据结构与算法成为用计算机解决实际问题的有效工具。

本书覆盖计算机及相关专业、电类各专业“数据结构”课程的教学大纲要求，可作为该课程的实验教材或参考用书。

前辅文
第1章 绪论
  1.1 算法实现
   算法0-0：求两个正整数的最大公约数GCD(x, y)
   算法1-1：求数组与整数乘积的最大值 MaxProduct1(array, m)
   算法1-2：求数组与整数乘积的最大值 MaxProduct2(array, m)
   算法1-3：将数组中元素反转存放 ReverseArray1(array)
   算法1-4：将数组中元素反转存放 ReverseArray2(array)
   算法1-5：计算1～n2的和加上1～n的和 SumUp(n)
   算法1-6：计算1～n与1～m每一项相互乘积的和SumProducts(n, m)
   算法1-7：连续子序列最大和的O(n3)算法MaxSubsequenceSum1(s)
   算法1-8：连续子序列最大和的O(n2)算法 MaxSubsequenceSum2(s)
   算法1-9：连续子序列最大和的O(n)算法 MaxSubsequenceSum3(s)
   算法1-10：输出1～n的递归算法 RecursivePrint(n)
   算法1-11：输出1～n的循环算法 IterativePrint(n)
  1.2 基础练习
   练习1-1 二分查找
   练习1-2 两枚硬币
  1.3 进阶实验
   实验1-1 有序数组的插入
   实验1-2 爆气球
第2章 线性表
  2.1 算法实现
   算法2-1：在顺序表list中查找元素x Search(list, x)
   算法2-2：在顺序表list的第i个位置上插入元素x Insert(list, i, x)
   算法2-3：从顺序表list中删除第i个元素 Remove(list, i)
   算法2-4：求单链表list中的元素个数，即表长 Length(list)
   算法2-5：返回单链表list中第i个元素的值 Get(list, i)
   算法2-6：在单链表list中查找元素x所在的结点 Search(list, x)
   算法2-7：在单链表list的第i个位置上插入元素x Insert(list, i, x)
   算法2-8：从单链表list中删除第i个元素 Remove(list, i)
   算法2-9：一元多项式加法运算 PolynomialAdd(p1, p2)
   算法2-10：大整数加法运算 BigIntAdd(a, b)
   算法2-11：大整数乘法运算 BigIntMultiply(a, b)
  2.2 基础练习
   练习2-1 带空头结点的单链表操作
   练习2-2 线性表循环右移
   练习2-3 一元多项式求导
   练习2-4 最长连续递增子序列
  2.3 进阶实验
   实验2-1 求链式线性表的倒数第m项
   实验2-2 一元多项式的乘法运算
   实验2-3 线性表元素的区间删除
   实验2-4 单链表分段逆转
   *实验2-5 约瑟夫问题
   *实验2-6 判断两个广义表是否相等
   *实验2-7 稀疏矩阵的链式结构构建
第3章 栈与队列
  3.1 算法实现
   算法3-1：顺序栈的入栈操作 Push(stack, x)
   算法3-2：顺序栈的取顶操作 Top(stack)
   算法3-3：顺序栈的出栈操作 Pop(stack)
   算法3-4：链式栈的入栈操作 Push(stack, x)
   算法3-5：链式栈的取顶操作 Top(stack)
   算法3-6：链式栈的出栈操作 Pop(stack)
   算法3-7：顺序存储的循环队列的入队操作 EnQueue(queue, x)
   算法3-8：顺序存储的循环队列的查看队首操作 GetFront(queue)
   算法3-9：顺序存储的循环队列的出队操作 DeQueue(queue)
   算法3-10：链式队列的入队操作 EnQueue(queue, x)
   算法3-11：链式队列的查看队首操作 GetFront(queue)
   算法3-12：链式队列的出队操作 DeQueue(queue)
   算法3-13：后缀表达式求值 PostFixEval(expr)
   算法3-14：阶乘的递归实现 Factorial(n)
   算法3-15：火车车厢重排 TrainCarriageScheduling(in_track, out_track, n, k)
  3.2 基础练习
   练习3-1 仅有头指针的队列
   练习3-2 栈操作的合法性
   练习3-3 用两个栈实现队列
   *练习3-4 符号配对
  3.3 进阶实验
   实验3-1 在一个数组中实现两个栈
   实验3-2 出栈序列的合法性
   实验3-3 简单计算器
   实验3-4 取行李
   实验3-5 双端队列
   *实验3-6 滑动窗口的极值
第4章 字符串
  4.1 算法实现
   算法4-1：顺序存储字符串的插入操作StrInsert(s, pos, t)
   算法4-2：顺序存储字符串的删除操作StrRemove(s, pos, len)
   算法4-3：顺序存储字符串的截取子串操作 SubString(s, pos, len)
   算法4-4：顺序存储字符串的连接操作 StrConcat(s, t)
   算法4-5：顺序存储字符串的比较操作 StrCompare(s, t)
   算法4-6：链式存储字符串的插入操作StrInsert(s, pos, t)
   算法4-7：链式存储字符串的删除操作 StrRemove(s, pos, len)
   算法4-8：链式存储字符串的截取子串操作 SubString(s, pos, len)
   算法4-9：链式存储字符串的连接操作 StrConcat(s, t)
   算法4-10：链式存储字符串的比较操作 StrCompare(s, t)
   算法4-11：朴素字符串模式匹配算法 PatternMatchBF(s, t)
   算法4-12：字符串替换算法 Replace(s, sub_s, t)
   算法4-13：求解字符串t的next数组 GetNext(t, next)
   算法4-14：字符串模式匹配的KMP算法 PatternMatchKMP(s, t)
   算法4-15：字符串模式匹配的KR算法 PatternMatchKR(s, t)
   算法4-16：字符串模式匹配的Sunday算法 PatternMatchSunday(s, t)
  4.2 基础练习
   练习4-1 字符串匹配算法比较
   练习4-2 剪切粘贴
  4.3 进阶实验
   实验4-1 吃火锅
   实验4-2 猜近似数字
   实验4-3 出院
第5章 树与二叉树
  5.1 算法实现
   算法5-1：构造二叉树 CreateBinaryTree(value, left_tree, right_tree)
   算法5-2：前序遍历二叉树 PreOrder(tree)
   算法5-3：中序遍历二叉树 InOrder(tree)
   算法5-4：后序遍历二叉树 PostOrder(tree)
   算法5-5：计算二叉树高度 Height(tree)
   算法5-6：将表达式树转换成中缀表达式 PrintInfixExpression(tree)
   算法5-7：非递归前序遍历二叉树 PreOrder(tree)
   算法5-8：非递归中序遍历二叉树 InOrder(tree)
   算法5-9：非递归后序遍历二叉树 PostOrder(tree)
   算法5-10：层序遍历二叉树 LevelOrder(tree)
   算法5-11：二叉树前序序列化 PreOrderSerialize(tree)
   算法5-12：根据前序序列重构二叉树 PreOrderDeSerialize( preorder, n)
   算法5-13：二叉树层序序列化 LevelOrderSerialize(tree)
   算法5-14：根据层序序列重构二叉树 LevelOrderDeSerialize(levelorder, n)
   算法5-15：创建Huffman树 CreateHuffmanTree(w)
   算法5-16：对二进制字符串解码 Decoding(tree, binary_code)
   算法5-17：查找根结点 FindRoot(tree, x)
   算法5-18：查找树中带有指定数据的结点 Search(tree, x)
   算法5-19：前序遍历树 PreOrder(tree)
   算法5-20：后序遍历树 PostOrder(tree)
   算法5-21：创建Trie树结点 CreateTrieNode(k)
   算法5-22：Trie树中插入字符串 Insert(trie, k, s)
   算法5-23：判断给定字符串是否在Trie树中 IsIn(trie, k, s)
   算法5-24：构建后缀树BuildSuffixTree(s, k)
  5.2 基础练习
   练习5-1 顺序存储的二叉树的遍历
   练习5-2 列出叶结点
   练习5-3 还原二叉树
   *练习5-4 转换树的表示法
  5.3 进阶实验
   实验5-1 树的同构
   实验5-2 树的宽度
   实验5-3 二叉树直径
   实验5-4 根据后序和中序遍历输出前序遍历
   实验5-5 顺序存储的二叉树的最近公共祖先问题
   *实验5-6 修理牧场
   *实验5-7 家谱处理
   *实验5-8 我爱背单词
第6章 优先级队列
  6.1 算法实现
   算法6-1：二叉堆的上调操作 SiftUp(h, i)
   算法6-2：二叉堆的下调操作 SiftDown(h, i)
   算法6-3：二叉堆的插入操作 Insert(h, x)
   算法6-4：二叉堆的删顶操作 ExtractMin(h)
   算法6-5：二叉堆的朴素建堆操作 MakeHeapUp(h)
   算法6-6：二叉堆的快速建堆操作 MakeHeapDown(h)
   算法6-7：多叉堆的上调操作 SiftUpD(h, d, i)
   算法6-8：多叉堆的下调操作 SiftDownD(h, d, i)
   算法6-9：左堆的合并操作 LeftistMerge(h1, h2)
   算法6-10：斜堆的合并操作 SkewMerge(h1, h2)
  6.2 基础练习
   练习6-1 堆中的路径
   练习6-2 Huffman树的实现
  6.3 进阶实验
   实验6-1 是不是堆
   实验6-2 关于堆的判断
   实验6-3 Windows消息队列
   实验6-4 D度完全树
   *实验6-5 对顶堆维护中位数
   *实验6-6 堆的合并操作比较
第7章 图
  7.1 算法实现
   算法7-1：获取图的顶点个数 NumberOfVerts(graph)
   算法7-2：判断边是否存在 ExistEdge(graph, u, v)
   算法7-3：找顶点的第一个邻接顶点 FirstAdjVert(graph, v)
   算法7-4：向图中插入边 InsertEdge(graph, u, v, weight)
   算法7-5：从图中删除边 RemoveEdge(graph, u, v)
   算法7-6：从图中删除顶点及所有邻接于该顶点的边 RemoveVert(graph, v)
   算法7-7：返回图中顶点的第一个邻接顶点 FirstAdjVert(graph, v)
   算法7-8：判断边是否存在 ExistEdge(graph, u, v)
   算法7-9：向图中插入边 InsertEdge(graph, u, v, weight)
   算法7-10：从图中删除顶点及所有邻接于该顶点的边 RemoveVert(graph, v)
   算法7-11：深度优先遍历图中顶点 DFS(graph)
   算法7-12：从指定顶点开始深度优先遍历 DFSv(graph, v, visited)
   算法7-13：广度优先遍历图中顶点 BFS(graph)
   算法7-14：从指定顶点开始广度优先遍历 BFSv(graph, v, visited)
   算法7-15：图的连通性判断 IsConnected(graph)
   算法7-16：验证六度空间理论SixDegreesOfSeparation(graph, v)
   算法7-17：获取图的强连通分量 StronglyConnectedComponents(graph)
   算法7-18：后序深度优先遍历记录顶点 PostOrderDFS(graph, v, visited, dfs_seq, dfs_num)
   算法7-19：后序深度优先遍历输出顶点 PrintV(graph, v, visited)
   算法7-20：从给定顶点出发获得一条回路 GetCircuit(graph, start)
   算法7-21：求欧拉回路 EulerCircle(graph)
   算法7-22：利用深度优先遍历计算dfn和low的值 DfnAndLow(graph, v, parent)
   算法7-23：求割点的Tarjan算法 ArticulationPoint(graph, start)
   算法7-24：求割边的Tarjan算法 ArticulationEdge(graph, start)
  7.2 基础练习
   练习7-1 哥尼斯堡七桥问题
   练习7-2 判断两点是否连通
   练习7-3 判断广度优先遍历序列
  7.3 进阶实验
   实验7-1 Hamilton回路
   实验7-2 列出连通集
   实验7-3 诈骗电话检测
   实验7-4 是否有回路
   实验7-5 社交网络图中顶点的“重要性”计算
第8章 图应用
  8.1 算法实现
   算法8-1：求单源最短路径的Dijkstra算法 Dijkstra(graph, s, path, dist)
   算法8-2：求单源最短路径的Bellman-Ford算法 BellmanFord(graph, s, dist)
   算法8-3：求所有点对间最短路径的Floyd-Warshall算法 Floyd Warshall(graph, path, dist)
   算法8-4：求最小生成树的Prim算法 Prim(graph)
   算法8-5：拓扑排序 TopSort(graph, top_s)
   算法8-6：求图中关键活动 CriticalAnalysis(graph)
   算法8-7：求解二部图最大匹配的匈牙利算法 MaximumMatch(bigraph, match)
   算法8-8：找二部图匹配的增广路径 FindAugmentingPath(bigraph, match, u, visited)
  8.2 基础练习
   练习8-1 旅游规划
   练习8-2 哈利·波特的考试
   练习8-3 公路村村通
   练习8-4 任务调度的合理性
  8.3 进阶实验
   实验8-1 城市间紧急救援
   实验8-2 最短路径的交点
   实验8-3 打怪升级
   实验8-4 最小生成树的唯一性
   *实验8-5 拆积木
   *实验8-6 爱之匹配
第9章 不相交集
  9.1 算法实现
   算法9-1：初始化不相交集 InitSet(set, n)
   算法9-2：查找元素所在的集合 Find(set, x)
   算法9-3：合并两个元素所在的集合 Union(set, x, y)
   算法9-4：初始化采用按秩合并策略的不相交集 InitSet(set, n)
   算法9-5：利用按秩合并策略合并两个元素所在的集合 Union(set, x, y)
   算法9-6：以路径压缩策略查找元素所在的集合Find(set, x)
   算法9-7：Tarjan算法求解最近公共祖先 LCA(P, u, set, ancestor, visited)
  9.2 基础练习
   练习9-1 文件传输
   *练习9-2 团结就是力量
  9.3 进阶实验
   实验9-1 部落
   *实验9-2 两个序列的故事
第10章 内排序
  10.1 算法实现
   算法10-1：插入排序 InsertionSort(a, l, r)
   算法10-2：Shell排序 ShellSort(a, l, r)
   算法10-3：简单选择排序 SelectionSort(a, l, r)
   算法10-4：堆排序 HeapSort(a, l, r)
   算法10-5：冒泡排序 BubbleSort(a, l, r)
   算法10-6：序列拆分 Partition(a, l, r)
   算法10-7：快速排序 QuickSort(a, l, r)
   算法10-8：二路归并 TwoWayMerge(a, l_x, r_x, l_y, r_y)
   算法10-9：归并排序 MergeSort(a, l, r)
   算法10-10：自底向上的归并排序 MergeSortBottomUp(a, l, r)
   算法10-11：改进的二路归并 TwoWayMergeImproved(a, t, l, m, r)
   算法10-12：改进的自底向上归并排序 MergeSortBottomUpImproved(a, l, r)
   算法10-13：二路归并求逆序对减量 TwoWayInversionCount(a, l, m, r)
   算法10-14：归并排序兼求逆序对数量 InversionCount(a, l, r)
   算法10-15：计数排序 CountingSort(a, l, r, k)
   算法10-16：基数排序中使用的计数排序 CountingSort2(a, l, r, radix, k, d)
   算法10-17：MSD基数排序 MSDRadixSort(a, l, r, radix, k, d)
   算法10-18：LSD基数排序 LSDRadixSort(a, l, r, radix, d)
   算法10-19：基于插入排序的索引排序 IndexedInsertionSort(a, idx, l, r)
   算法10-20：元素顺序调整 ElementAdjust(a, idx, l, r)
   算法10-21：内省排序 IntroSort(a, l, r, d)
   算法10-22：Tim排序 TimSort(a, l, r)
  10.2 基础练习
   练习10-1 排序
   练习10-2 正负数分类
   练习10-3 模拟Excel排序
   练习10-4 插入排序还是归并排序
   练习10-5 与零交换
  10.3 进阶实验
   实验10-1 分类排序
   实验10-2 德才论
   实验10-3 插入排序还是堆排序
   实验10-4 统计工龄
   实验10-5 清点代码库
第11章 查找
  11.1 算法实现
   算法11-1：顺序表的顺序查找 SequentialSearch(record, n, key)
   算法11-2：二分查找 BinarySearch(record, low, high, key)
   算法11-3：索引表的顺序查找 IndexSequentialSearch(record, idx, m, l, key)
   算法11-4：二叉查找树的查找 SearchBST(bstree, key)
   算法11-5：二叉查找树的插入 InsertBST(bstree, x)
   算法11-6：二叉查找树的删除 DeleteBST(bstree, key)
   算法11-7：AVL树的插入 InsertAVL(tree, x)
   算法11-8：AVL树的左单旋转（RR型） RRSingleRotation(root)
   算法11-9：AVL树的先左后右双向旋转(LR型） LRDoubleRotation(root)
   算法11-10：英文字典的散列 StringHash(string, table_size)
   算法11-11：开放定址法散列查找 SearchHash(htable, key)
   算法11-12：开放定址法散列插入 InsertHash(htable, x)
  11.2 基础练习
   练习11-1 垃圾分类
   练习11-2 是否二叉查找树
   练习11-3 AVL树的根
   练习11-4 整型关键字的散列映射
  11.3 进阶实验
   实验11-1 集合相似度
   实验11-2 查找树判断
   实验11-3 树种统计
   *实验11-4 笛卡儿树
   *实验11-5 新浪微博热门话题
第12章 高级查找
  12.1 算法实现
   算法12-1：构建最小值线段树BuildSegTree(seg_tree, array, l, r, p)
   算法12-2：求最小值线段树的单点更新 Update(seg_tree, l, r, p, idx, value)
   算法12-3：求最小值线段树的区间查询 Query(seg_tree, l, r, p, ql, qr)
   算法12-4：求最小值线段树的区间增值更新 RangeUpdate(seg_tree, lazy, l, r, p, ql, qr, c)
   算法12-5：树状数组区间求前缀和 GetPrefixSum(c, k)
   算法12-6：树状数组单点更新 Update(c, n, k, d)
   算法12-7：红黑树中的右旋 RRotate(rbtree, x)
   算法12-8：红黑树中插入结点后的调整 InsertAdjust(rbtree, x)
   算法12-9：删除黑结点及颜色调整 DeleteAdjust(rbtree, x)
   算法12-10：树堆的插入 InsertTreap(treap, x)
  12.2 基础练习
   练习12-1 是否红黑树
   *练习12-2 三逆序组
  12.3 进阶实验
   实验12-1 树种统计
   *实验12-2 染成红黑树
   *实验12-3 逆序对
第13章 外排序
  13.1 算法实现
   算法13-1：初始化败者树 InitLoserTree(tree, array, size)
   算法13-2：从内部结点到根结点的路径上进行比赛 Play(tree, p, left, right)
   算法13-3：重构时从外部结点到根结点的路径上重新进行比赛 RePlay(tree, i)
   算法13-4：利用败者树进行多路归并排序MultiMerge(tree, racer, buffer_ pool, f, size)
   算法13-5：置换选择算法 ReplacementSelection(ram_array, m, file_ in, file_out)
  13.2 基础练习
   *练习13-1 数据去重
  13.3 进阶实验
   *实验13-1 文件排序
第14章 索引
  14.1 基础练习
   *练习14-1 B+树的查找
   *练习14-2 基于词频的文件相似度
  14.2 进阶实验
   *实验14-1 3 阶B+树
   *实验14-2 迷你搜索引擎
第15章 算法设计基础
  15.1 算法实现
   算法15-1：小规模分书问题的嵌套循环算法 BookAssignment(T)
   算法15-2：枚举法的嵌套循环实现 IterBruteForce(T)
   算法15-3：枚举法的递归实现 RecBruteForce(T, s, i, n)
   算法15-4：分书问题的递归枚举算法 BookAssignmentBF(table, s, i, n, m)
   算法15-5：回溯法的通用伪代码 Backtracking(i, n)
   算法15-6：点集重构问题回溯算法的伪代码 PointSetReconstruction(x, D, n, left, right)
   算法15-7：分治法的伪代码描述 DivideAndConquer(n)
   算法15-8：第n项斐波那契数的递归计算 RecFib(n)
   算法15-9：第n项斐波那契数的循环计算 Fib(n)
   算法15-10：计算m1, n的动态规划算法 OptimalMatrixOrdering(m, p, r, n)
   算法15-11：活动安排问题的贪心算法 ActivitySelection(a, k, n)
   算法15-12：连续背包问题的贪心算法 Knapsack(W, s, x, n)
   算法15-13：离散背包（0-1 背包）问题的递归分治解法 Knapsack01(W, s, x, f, n, i)
   算法15-14：整数重量限制下离散背包问题的动态规划解法 Knapsack01(W, s, opt, n)
  15.2 基础练习
   练习15-1 分书问题
   练习15-2 n皇后问题
   *练习15-3 旅行商问题
   练习15-4 最长公共子序列
   练习15-5 带权的活动安排问题
   练习15-6 教室安排问题
  15.3 进阶实验
   实验15-1 0-1 背包问题的回溯剪枝解
   实验15-2 0-1 背包问题的分支限界解
   实验15-3 拼题A打卡奖励
   实验15-4 有多少红黑树
   *实验15-5 代金券
第16章 高级算法设计
  16.1 算法实现
   算法16-1：顶点覆盖问题的近似算法 VertexCoverApproximation(E)
   算法16-2：基于贪心策略的离散背包问题近似算法 KnapsackGreedyApproximation(W, s, x, n)
   算法16-3：基于动态规划的离散背包问题近似算法 KnapsackDPApproximation(W, s, x, n, eps)
   算法16-4：A算法 A(h, init_state, goal_state)
   算法16-5：爬山算法 HillClimbing(f, init_solution, E)
   算法16-6：模拟退火算法 SimulatedAnnealing(init_solution, E, T, alpha, k, iter_num, eps)
   算法16-7：计算 ai mod n的幂取模算法 PowMod(a, i, n)
   算法16-8：Miller-Rabin素数测试算法 MillerRabin_IsPrime(n, k)
  16.2 进阶实验
   实验16-1 0-1 背包问题的近似解
   *实验16-2 旅行商问题
   *实验16-3 九宫数独
   *实验16-4 五子棋
   *实验16-5 最小生成树
  参考文献

本书是计算机领域本科教育教学改革试点工作（“101”计划）核心课程“计算机组成与系统结构”的实践教材。“101计划”着力以课程建设带动本科教育改革，提高本科人才培养质量。本书面向培养学生计算机系统设计和实现能力的教学目标，紧密结合课程教学内容，基于清华大学计算机科学与技术系自研的课程教学实验平台，设计了不同难度、不同层次的系列实验，构成了为计算机系统能力培养服务的实验体系。

全书共8章。第1—4章分别介绍实验系统硬件平台的组成，实验系统的软件开发工具，SystemVerilog HDL硬件描述语言和Vivado开发环境。第5章介绍计算机部件实验。第6章介绍单周期处理器实验。第7章的实验要求实现一个简单的多周期或指令流水处理器，可以运行一个应用程序。第8章实验的目标是设计一个带指令流水功能的CPU，可以运行支持虚拟地址及中断功能的监控程序。

本书可作为高等学校本科计算机类专业计算机组成与结构等课程配套的实践教材，也可供有关技术人员参考。

前辅文
第1章 ThinPAD-Cloud教学计算机实验平台
  1.1 总体介绍
  1.2 实验平台结构
  1.3 可编程逻辑芯片
   1.3.1 可配置逻辑块
   1.3.2 块存储器
   1.3.3 时钟管理单元
   1.3.4 数字信号处理单元
   1.3.5 可配置I/O单元
  1.4 板载存储芯片
   1.4.1 SRAM
   1.4.2 Flash
  1.5 外部接口
   1.5.1 串行接口
   1.5.2 DVI图像输出接口
   1.5.3 100M以太网接口
   1.5.4 USB接口
  1.6 实验平台使用方法——本地模式
   1.6.1 硬件连接
   1.6.2 驱动安装
   1.6.3 通过ThinPAD-Cloud控制面板进行实验
  1.7 实验平台使用方法——远程模式
   1.7.1 设计文件上传
   1.7.2 实验平台基本操作
  1.8 处理器设计硬件实验概览
第2章 计算机系统综合设计软件工具
  2.1 指令系统
   2.1.1 RISC-V指令集概述
   2.1.2 ThinPAD教学计算机中所使用的指令和指令功能
  2.2 编译工具链
   2.2.1 GCC
   2.2.2 GNU Binutils
  2.3 模拟器qemu
  2.4 调试器gdb
  2.5 RISC-V汇编语言编程
  2.6 监控程序
   2.6.1 监控程序简介
   2.6.2 基础版本监控程序分析
   2.6.3 支持中断异常的监控程序分析
   2.6.4 支持虚拟地址的监控程序分析
   2.6.5 终端程序与使用方法
   2.6.6 在qemu里调试监控程序
第3章 SystemVerilog HDL硬件描述语言
  3.1 概述
  3.2 SystemVerilog语言入门
   3.2.1 加法器
   3.2.2 按钮开关
   3.2.3 秒表
   3.2.4 计数器
   3.2.5 无状态仲裁器
   3.2.6 循环优先级仲裁器
  3.3 SystemVerilog语言代码规范
   3.3.1 通过命名区分寄存器和信号
   3.3.2 信号或寄存器的赋值
   3.3.3 时序逻辑和组合逻辑的代码组织
   3.3.4 寄存器在上升沿触发
   3.3.5 寄存器复位到常量
   3.3.6 组合逻辑中的信号赋值
   3.3.7 对寄存器设置FPGA启动初始值
   3.3.8 组合逻辑块中的赋值顺序
   3.3.9 阻塞赋值与非阻塞赋值
   3.3.10 信号极性一致
   3.3.11 case语句
第4章 Vivado开发环境
  4.1 概述
  4.2 Vivado使用入门
   4.2.1 创建项目
   4.2.2 编写代码
   4.2.3 代码综合
   4.2.4 系统仿真
   4.2.5 添加约束
   4.2.6 生成比特流文件
   4.2.7 装载FPGA比特流文件
第5章 计算机部件实验
  5.1 实验平台的顶层项目
   5.1.1 顶层项目文件的位置
   5.1.2 顶层项目
   5.1.3 顶层项目中的仿真
  5.2 计数器实验
   5.2.1 实验目的
   5.2.2 实验环境
   5.2.3 实验内容
   5.2.4 实验原理
   5.2.5 实验思考
  5.3 ALU与寄存器堆实验
   5.3.1 实验目的
   5.3.2 实验内容
   5.3.3 实验原理
   5.3.4 实验思考
  5.4 SRAM控制器实验
   5.4.1 SRAM存储器件的读写
   5.4.2 Wishbone总线协议
   5.4.3 Wishbone SRAM控制器
   5.4.4 三态门
   5.4.5 实验目的
   5.4.6 实验内容
   5.4.7 评测流程
   5.4.8 实验步骤
   5.4.9 实验思考
  5.5 串行接口控制器实验
   5.5.1 串口概述
   5.5.2 UART协议
   5.5.3 串口收发逻辑
   5.5.4 串口控制器总线接口
   5.5.5 Wishbone Master的实现
   5.5.6 实验目的
   5.5.7 实验环境
   5.5.8 实验内容
   5.5.9 实验步骤
   5.5.10 实验思考
  5.6 DVI接口实验
   5.6.1 实验目的
   5.6.2 实验环境
   5.6.3 实验内容
   5.6.4 实验原理
   5.6.5 实验步骤
   5.6.6 实验思考
  5.7 Flash实验
   5.7.1 实验目的
   5.7.2 实验环境
   5.7.3 实验内容
   5.7.4 实验原理
   5.7.5 实验步骤
   5.7.6 实验思考
第6章 单周期处理器实验
  6.1 指令系统实验
   6.1.1 实验目的
   6.1.2 实验环境
   6.1.3 实验内容
   6.1.4 实验原理
   6.1.5 实验步骤
   6.1.6 实验思考
  6.2 单周期处理器设计与实现
   6.2.1 实验目的
   6.2.2 实验环境
   6.2.3 实验内容
   6.2.4 实验原理
   6.2.5 实验步骤
   6.2.6 实验思考
第7章 简化处理器实验
  7.1 实验概述
  7.2 程序与二进制文件
  7.3 多周期处理器的设计
   7.3.1 多周期处理器设计
   7.3.2 Wishbone总线多路选择器
  7.4 流水线处理器的设计
   7.4.1 流水线处理器设计概述
   7.4.2 总线仲裁器
   7.4.3 流水线处理器的总体结构
   7.4.4 流水线处理器的气泡与暂停
  7.5 简化处理器实验
   7.5.1 实验目的
   7.5.2 实验环境
   7.5.3 实验内容
   7.5.4 实验原理
   7.5.5 实验步骤
   7.5.6 实验思考
第8章 处理器综合实验
  8.1 基本版本流水线CPU计算机系统实验
   8.1.1 实验目的
   8.1.2 实验环境
   8.1.3 实验内容
   8.1.4 实验原理
   8.1.5 实验步骤
   8.1.6 实验思考
  8.2 支持中断异常的流水线CPU计算机系统实验
   8.2.1 理解中断和异常的处理
   8.2.2 实现CSR寄存器及读写指令
   8.2.3 基本的异常处理
   8.2.4 mtime和mtimecmp寄存器
   8.2.5 中断处理
  8.3 支持虚拟地址的流水线CPU计算机系统实验
   8.3.1 理解监控程序中的页表机制
   8.3.2 查询页表
  8.4 处理器扩展实验
   8.4.1 提高运行速度类的扩展
   8.4.2 支持不同外设类型的扩展
   8.4.3 支持更多指令功能的扩展
附录A SystemVerilog简明手册
  A.1 概述
  A.2 程序结构
  A.3 语言元素
   A.3.1 SystemVerilog语言元素
   A.3.2 SystemVerilog中的数据
   A.3.3 SystemVerilog中的运算
  A.4 SystemVerilog的行为语句
   A.4.1 综述
   A.4.2 always过程语句
   A.4.3 begin/end块语句
   A.4.4 赋值语句
   A.4.5 条件语句
   A.4.6 循环语句
  A.5 SystemVerilog的设计层次与风格
附录B FPGA引脚分配表