《命令式计算原理》课程大纲一、课程名称：命令式计算原理二、课程性质：选修、理论课三、学时与学分：32学时，2学分四、课程先导课：C语言程序设计，计算思维，数据结构等五、课程简介“命令式计算原理”是一门关于程序设计方法学的计算机类专业课程，具有很强的理论性、技术性和实践性，在计算机学科系列课程中与程序设计基础、计算思维、数据结构和算法基础等课程紧密相关。课程从计算思维、程序设计技巧和数据结构与算法等三个维度，讲授命令式程序设计方法以及确保程序正确性方法。介绍了利用函数前置条件、函数后置条件、循环不变量、数据结构不变性等来编写程序，对代码进行逻辑上和操作上的严格推理；讨论了在编程中有效使用一些基本的数据结构和算法，包括二分搜索，次二次排序，栈和队列，哈希表，优先队列，平衡二分查找树，特里树，二分决策图，简单图算法等。课程强调对抽象和接口的理解，对顺序计算进行渐进复杂性分析和效率分析。六、课程目标通过相关教学活动，帮助学生掌握命令式程序设计方法，以及通过推理和分析，来确保程序正确性的方法。培养学生计算思维能力，掌握程序设计技能，并掌握基本算法与数据结构的有效使用，用于编程解决实际问题课程的具体目标包括：目标1：理解诸如变量、表达式、循环、数组和函数等基本的程序设计要素，掌握命令式程序设计以及确保程序正确性的方法目标2：培养计算思维，具体包括：对抽象和接口的理解：用合适的数据结构描述事物的属性和状态，用运算模拟事物的变化和相互作用：视代码如数据；目标3：掌握程序设计技能，具体包括：将算法转化成正确的命令式代码；用不变式验证程序的正确性；算法复杂性分析，包括简单的分步分析和对一般复杂性的认识(O(n)，O(n*log(n))，O(n2)，O(2")；对程序静态语义和动态语义的理解；算法设计中分治策略的应用；代码的开发、测试、改写和优化；目标4：掌握基本算法和数据结构的有效使用。包括二分查找、排序、栈和队列，哈希表、优先队列、平衡二叉搜索树、二分决策图，简单的图算法；七、课程目标对毕业要求的支撑关系
《命令式计算原理》课程大纲 一、课程名称：命令式计算原理 二、课程性质：选修、理论课 三、学时与学分：32 学时，2 学分 四、课程先导课：C 语言程序设计，计算思维，数据结构等 五、课程简介 “命令式计算原理”是一门关于程序设计方法学的计算机类专业课程，具有 很强的理论性、技术性和实践性，在计算机学科系列课程中与程序设计基础、计 算思维、数据结构和算法基础等课程紧密相关。课程从计算思维、程序设计技巧 和数据结构与算法等三个维度，讲授命令式程序设计方法以及确保程序正确性方 法。介绍了利用函数前置条件、函数后置条件、循环不变量、数据结构不变性等 来编写程序，对代码进行逻辑上和操作上的严格推理；讨论了在编程中有效使用 一些基本的数据结构和算法，包括二分搜索，次二次排序，栈和队列，哈希表， 优先队列，平衡二分查找树，特里树，二分决策图，简单图算法等。课程强调对 抽象和接口的理解，对顺序计算进行渐进复杂性分析和效率分析。 六、课程目标 通过相关教学活动，帮助学生掌握命令式程序设计方法，以及通过推理和分 析，来确保程序正确性的方法。培养学生计算思维能力，掌握程序设计技能，并 掌握基本算法与数据结构的有效使用，用于编程解决实际问题。 课程的具体目标包括： 目标 1：理解诸如变量、表达式、循环、数组和函数等基本的程序设计要素， 掌握命令式程序设计以及确保程序正确性的方法； 目标 2：培养计算思维，具体包括：对抽象和接口的理解；用合适的数据结 构描述事物的属性和状态，用运算模拟事物的变化和相互作用；视代码如数据； 目标 3：掌握程序设计技能，具体包括：将算法转化成正确的命令式代码； 用不变式验证程序的正确性；算法复杂性分析，包括简单的分步分析和对一般复 杂性的认识(O(n)，O(n*log(n))，O(n 2)，O(2 n))；对程序静态语义和动态语义的理 解；算法设计中分治策略的应用；代码的开发、测试、改写和优化； 目标 4：掌握基本算法和数据结构的有效使用。包括二分查找、排序、栈和 队列，哈希表、优先队列、平衡二叉搜索树、二分决策图，简单的图算法； 七、课程目标对毕业要求的支撑关系
支撑的毕业要求二级指标点对应课程目标3.2掌握程序设计的基本方法、算法设计与分析的基本方法目标14.3能综合应用数学物理知识、自然科学知识、工程知识，并通过文目标2献分析和研究，对本学科的复杂工程问题提出解决问题的思路5.2了解计算机科学与技术工程问题特征，掌握解决本学科复杂工程目标3问题的基本方法5.3具备选择合适的开发工具，设计（开发）满足特定功能要求的软目标3/硬件系统、单元（部件）或工艺流程的能力6.2能正确选择工具，采用科学方法和本学科的专业知识，对本学科目标3的复杂工程问题设计研究方案6.3能正确使用和处理实验或研究数据，通过信息综合处理，对本学目标4科的复杂工程问题进行预测或提出优化方案12.1能认识到计算机技术日新月异的发展特点，认同自主学习和终目标2身学习的必要性12.2具备自主学习能力，能通过多种途径拓展自己的知识和能力，目标2包括理解能力、归纳总结能力和提出问题的能力等八、教学设计及对课程目标的支持第1讲命令式计算原理简介介绍命令式计算的概念，每讲课程教学内容及学时安排，课程学习要求和课程成绩评价方法。第2讲约定与程序推理1.教学目标1）计算思维：算法的描述与实现，程序正确性：2）算法与数据结构：高效率和低效率实现的区别；3）程序设计：约定的概念及表示。本讲教学支持课程目标1、课程目标2和课程目标3。2.教学重点1）函数前置条件、函数后置条件、循环不变量和断言这四种约定的表示和使用；2）如何寻找循环不变量，以及如何证明循环不变量，理解循环不变量如何对函数后置条件其到支撑；3）常用的循环可终止性判断方法；3.教学难点
支撑的毕业要求二级指标点 对应课程目标 3.2 掌握程序设计的基本方法、算法设计与分析的基本方法 目标 1 4.3 能综合应用数学物理知识、自然科学知识、工程知识，并通过文 献分析和研究，对本学科的复杂工程问题提出解决问题的思路 目标 2 5.2 了解计算机科学与技术工程问题特征，掌握解决本学科复杂工程 问题的基本方法 目标 3 5.3 具备选择合适的开发工具，设计（开发）满足特定功能要求的软 /硬件系统、单元（部件）或工艺流程的能力 目标 3 6.2 能正确选择工具，采用科学方法和本学科的专业知识，对本学科 的复杂工程问题设计研究方案 目标 3 6.3 能正确使用和处理实验或研究数据，通过信息综合处理，对本学 科的复杂工程问题进行预测或提出优化方案 目标 4 12.1 能认识到计算机技术日新月异的发展特点，认同自主学习和终 身学习的必要性 目标 2 12.2 具备自主学习能力，能通过多种途径拓展自己的知识和能力， 包括理解能力、归纳总结能力和提出问题的能力等 目标 2 八、教学设计及对课程目标的支持 第 1 讲 命令式计算原理简介 介绍命令式计算的概念，每讲课程教学内容及学时安排，课程学习要求和课 程成绩评价方法。 第 2 讲 约定与程序推理 1. 教学目标 1）计算思维：算法的描述与实现，程序正确性； 2）算法与数据结构：高效率和低效率实现的区别； 3）程序设计：约定的概念及表示。 本讲教学支持课程目标 1、课程目标 2 和课程目标 3。 2. 教学重点 1）函数前置条件、函数后置条件、循环不变量和断言这四种约定的表示和 使用； 2）如何寻找循环不变量，以及如何证明循环不变量，理解循环不变量如何 对函数后置条件其到支撑； 3）常用的循环可终止性判断方法； 3. 教学难点
1）约定的表示和约定的重要性2）利用约定进行推理4.教学环节设计围绕教学重点和教学难点，综合运用课堂讲授与讨论、作业、在线讨论等教学形式。1）课堂讨论围绕约定在函数测试上的重要性，循环不变量的确定、循环不变量的证明等问题展开。2）作业围绕循环不变量的使用来布置。3）在线讨论如何判断循环不变量是否足够充分，以足以支撑函数后置条件的正确性。第3讲整数类型1.教学目标1）计算思维：对资源限制的理解：2）算法与数据结构：二进制加法运算，用大小固定的数据结构表示数：3）程序设计：不同范围整数类型的使用。本讲教学支持课程目标1和课程目标2。2.教学重点1）溢出的处理，模运算的性质，向下取整和向零取整：2）二进制补码表示与模运算的内在关联；3）位运算和颜色类型数据的计算；3.教学难点1）模运算里的加法逆元2）溢出的判断4.教学环节设计围绕教学重点和教学难点，综合运用课堂讲授与讨论、作业、在线讨论等教学形式。1）课堂讨论在早期的计算机中，机器字的大小通常是8位，后来扩展到16位，现在是32或者64位。为什么对机器字的位宽进行扩展？能否无限扩展？2）作业
1）约定的表示和约定的重要性 2）利用约定进行推理 4. 教学环节设计 围绕教学重点和教学难点，综合运用课堂讲授与讨论、作业、在线讨论等教 学形式。 1）课堂讨论 围绕约定在函数测试上的重要性，循环不变量的确定、循环不变量的证明等 问题展开。 2）作业 围绕循环不变量的使用来布置。 3）在线讨论 如何判断循环不变量是否足够充分，以足以支撑函数后置条件的正确性。 第 3 讲 整数类型 1. 教学目标 1）计算思维：对资源限制的理解； 2）算法与数据结构：二进制加法运算，用大小固定的数据结构表示数； 3）程序设计：不同范围整数类型的使用。 本讲教学支持课程目标 1 和课程目标 2。 2. 教学重点 1）溢出的处理，模运算的性质，向下取整和向零取整； 2）二进制补码表示与模运算的内在关联； 3）位运算和颜色类型数据的计算； 3. 教学难点 1）模运算里的加法逆元 2）溢出的判断 4. 教学环节设计 围绕教学重点和教学难点，综合运用课堂讲授与讨论、作业、在线讨论等教 学形式。 1）课堂讨论 在早期的计算机中，机器字的大小通常是 8 位，后来扩展到 16 位，现在是 32 或者 64 位。为什么对机器字的位宽进行扩展？能否无限扩展？ 2）作业
围绕循环不变量的使用来布置。3）在线讨论在高级语言中，有人更倾向于认为int类型的整数本质上是无穷大的。能否设计机器字的长度可随着计算过程而改变？基本操作例如加法不再是直接映射到一条机器指令，而是用小程序来实现。而这种开支是否可接受？第4讲数组及其安全访问1.教学目标1）计算思维：程序的安全性定义；2）算法与数据结构：大小固定的数组：3）程序设计：利用数组和循环处理批量数据。本讲教学支持课程目标1和课程目标2。2.教学重点1）数组作为数据聚合体的基本特征：2）程序的安全性定义，及数组使用上的安全性；3）数组的复制和数组别名；3.教学难点1）数组复制和数组别名的理解；2）数组相关的循环不变量；4.教学环节设计围绕教学重点和教学难点，综合运用课堂讲授与讨论、作业、在线讨论等教学形式。1）课堂讨论如果数组的越界访问不受限制，将使缓冲区溢出攻击有机可乘，带来哪些信息安全隐患？2）作业围绕数组使用上的安全性来布置。3）在线讨论在使用C语言编程时碰到过哪些不安全的问题？第5讲线性查找1.教学目标
围绕循环不变量的使用来布置。 3）在线讨论 在高级语言中，有人更倾向于认为 int 类型的整数本质上是无穷大的。能否 设计机器字的长度可随着计算过程而改变？基本操作例如加法不再是直接映射 到一条机器指令，而是用小程序来实现。而这种开支是否可接受？ 第 4 讲 数组及其安全访问 1. 教学目标 1）计算思维：程序的安全性定义； 2）算法与数据结构：大小固定的数组； 3）程序设计：利用数组和循环处理批量数据。 本讲教学支持课程目标 1 和课程目标 2。 2. 教学重点 1）数组作为数据聚合体的基本特征； 2）程序的安全性定义，及数组使用上的安全性； 3）数组的复制和数组别名； 3. 教学难点 1）数组复制和数组别名的理解； 2）数组相关的循环不变量； 4. 教学环节设计 围绕教学重点和教学难点，综合运用课堂讲授与讨论、作业、在线讨论等教 学形式。 1）课堂讨论 如果数组的越界访问不受限制，将使缓冲区溢出攻击有机可乘，带来哪些信 息安全隐患？ 2）作业 围绕数组使用上的安全性来布置。 3）在线讨论 在使用 C 语言编程时碰到过哪些不安全的问题？ 第 5 讲 线性查找 1. 教学目标
1）计算思维：①开发约定（前提条件、后置条件、断言和循环不变性）来创建安全和正确的命令式程序；②利用有序性（已排序数据）来解决问题；③识别规范和实现之间的区别：2）算法与数据结构：线性查找的描述：3）程序设计：我们在这一讲将练习深度编程。识别、描述和有效地使用“短路”布尔运算。本讲教学支持课程目标2和课程目标3。2.教学重点1）无序数组里的线性查找；2）有序数组里的线性查找；3）分析操作次数；3.教学难点1）有序性的使用；2）利用“短路”布尔运算，避免不安全操作；4.教学环节设计围绕教学重点和教学难点，综合运用课堂讲授与讨论、作业、在线讨论等教学形式。1）课堂讨论程序正确性和程序效率的重要性。2）作业围绕线性查找算法布置作业题。3）在线讨论在以往编程中，哪些场合利用了“短路”布尔运算来避免不安全操作？第6讲二分查找1.教学目标1）计算思维：理解在不同算法问题中排序所起的作用，及循环不变量在编写正确代码上的重要性：2）算法与数据结构：大小固定数组的二分查找；3）程序设计：深思熟虑的编程，在测试、推理及确保安全与正确性中约定的重要性，利用局部推理来证明程序的正确性。本讲教学支持课程目标1、课程目标2、课程目标3和课程目标4。2.教学重点
1）计算思维：① 开发约定（前提条件、后置条件、断言和循环不变性）来 创建安全和正确的命令式程序；② 利用有序性(已排序数据) 来解决问题；③ 识 别规范和实现之间的区别； 2）算法与数据结构：线性查找的描述； 3）程序设计：我们在这一讲将练习深度编程。识别、描述和有效地使用“短 路”布尔运算。 本讲教学支持课程目标 2 和课程目标 3。 2. 教学重点 1）无序数组里的线性查找； 2）有序数组里的线性查找； 3）分析操作次数； 3. 教学难点 1）有序性的使用； 2）利用“短路”布尔运算，避免不安全操作； 4. 教学环节设计 围绕教学重点和教学难点，综合运用课堂讲授与讨论、作业、在线讨论等教 学形式。 1）课堂讨论 程序正确性和程序效率的重要性。 2）作业 围绕线性查找算法布置作业题。 3）在线讨论 在以往编程中，哪些场合利用了“短路”布尔运算来避免不安全操作？ 第 6 讲 二分查找 1. 教学目标 1）计算思维：理解在不同算法问题中排序所起的作用，及循环不变量在编 写正确代码上的重要性； 2）算法与数据结构：大小固定数组的二分查找； 3）程序设计：深思熟虑的编程，在测试、推理及确保安全与正确性中约定 的重要性，利用局部推理来证明程序的正确性。 本讲教学支持课程目标 1、课程目标 2、课程目标 3 和课程目标 4。 2. 教学重点
1）二分查找算法思想和算法实现中；2）程序可终止性分析和证明；3）编程中对潜在溢出情况的处理；3.教学难点1）迭代中循环不变量的寻找；2）潜在溢出情况的判断；4.教学环节设计围绕教学重点和教学难点，综合运用课堂讲授与讨论、作业、在线讨论等教学形式。1）课堂讨论如何分析和证明循环是可终止的？2）作业围绕循环可终止性和循环不变量的证明布置作业。3）在线讨论围绕溢出问题，寻找以前编写代码中的Bug。第7讲排序1.教学目标1）计算思维：尝试理解有序性如何能够提高计算效率，函数在最坏情况下的渐进复杂性；2）算法与数据结构：一般就地排序，特别是选择排序，大O符号的理解；3）程序设计：更多利用数组和算法不变性进行编程的例子。本讲教学支持课程目标1、课程目标3和课程目标4。2.教学重点1）用大0符号表示渐进复杂性；2）排序的分类和选择排序算法思想：3）渐进复杂度分析方法的运用；3.教学难点1）选择排序过程中寻找循环不变量：2）渐进复杂度分析方法；4.教学环节设计围绕教学重点和教学难点，综合运用课堂讲授与讨论、作业、在线讨论等教学形式
1）二分查找算法思想和算法实现中； 2）程序可终止性分析和证明； 3）编程中对潜在溢出情况的处理； 3. 教学难点 1）迭代中循环不变量的寻找； 2）潜在溢出情况的判断； 4. 教学环节设计 围绕教学重点和教学难点，综合运用课堂讲授与讨论、作业、在线讨论等教 学形式。 1）课堂讨论 如何分析和证明循环是可终止的？ 2）作业 围绕循环可终止性和循环不变量的证明布置作业。 3）在线讨论 围绕溢出问题，寻找以前编写代码中的 Bug。 第 7 讲 排序 1. 教学目标 1）计算思维：尝试理解有序性如何能够提高计算效率，函数在最坏情况下 的渐进复杂性； 2）算法与数据结构：一般就地排序，特别是选择排序，大 O 符号的理解； 3）程序设计：更多利用数组和算法不变性进行编程的例子。 本讲教学支持课程目标 1、课程目标 3 和课程目标 4。 2. 教学重点 1）用大 O 符号表示渐进复杂性； 2）排序的分类和选择排序算法思想； 3）渐进复杂度分析方法的运用； 3. 教学难点 1）选择排序过程中寻找循环不变量； 2）渐进复杂度分析方法； 4. 教学环节设计 围绕教学重点和教学难点，综合运用课堂讲授与讨论、作业、在线讨论等教 学形式
1）课堂讨论评价算法效率，为什么考虑的是在大规模数据处理下算法的行为？分析算法复杂度为什么考虑的是在给定数据规模下最坏情况时的复杂度？2）作业围绕渐进复杂度分析方法运用布置作业。3）在线讨论选择排序同冒泡排序在方法上的区别。第8讲快速排序1.教学目标1）计算思维：重温二分查找中讲到的分治技术，初次领会随机性的重要性：2）算法与数据结构：观察归并排序和快速排序，二者都采用分治策略，但总体策略不尽相同；3）程序设计：递归在归并排序和快速排序两种算法实现上的应用。本讲教学支持课程目标1、课程目标3和课程目标4。2.教学重点1）归并排序算法实现及算法渐进复杂性分析：2）快速排序算法实现及算法渐进复杂性分析；3）利用随机性提高算法性能：3.教学难点1）分治策略中如何“分”，如何“治”；2）随机性的理解；4.教学环节设计围绕教学重点和教学难点，综合运用课堂讲授与讨论、作业、在线讨论等教学形式。1）课堂讨论分治策略是计算机科学中解决问题的精妙方法。归并排序和快速排序都采用了分治策略，但这两种算法在“分”和“治”上明显不同。区别在哪里？2）作业布置快速排序和随机性编程的作业。3）在线讨论怎样理解随机性，计算机里怎样模拟随机性？
1）课堂讨论 评价算法效率，为什么考虑的是在大规模数据处理下算法的行为？分析算法 复杂度为什么考虑的是在给定数据规模下最坏情况时的复杂度？ 2）作业 围绕渐进复杂度分析方法运用布置作业。 3）在线讨论 选择排序同冒泡排序在方法上的区别。 第 8 讲 快速排序 1. 教学目标 1）计算思维：重温二分查找中讲到的分治技术，初次领会随机性的重要性； 2）算法与数据结构：观察归并排序和快速排序，二者都采用分治策略，但 总体策略不尽相同； 3）程序设计：递归在归并排序和快速排序两种算法实现上的应用。 本讲教学支持课程目标 1、课程目标 3 和课程目标 4。 2. 教学重点 1）归并排序算法实现及算法渐进复杂性分析； 2）快速排序算法实现及算法渐进复杂性分析； 3）利用随机性提高算法性能； 3. 教学难点 1）分治策略中如何“分”，如何“治”； 2）随机性的理解； 4. 教学环节设计 围绕教学重点和教学难点，综合运用课堂讲授与讨论、作业、在线讨论等教 学形式。 1）课堂讨论 分治策略是计算机科学中解决问题的精妙方法。归并排序和快速排序都采用 了分治策略，但这两种算法在“分”和“治”上明显不同。区别在哪里？ 2）作业 布置快速排序和随机性编程的作业。 3）在线讨论 怎样理解随机性，计算机里怎样模拟随机性？
第9讲栈和队列1.教学目标1）计算思维：考虑数据结构接口的用户端和库端，举例说明抽象的强大：2）算法与数据结构：把队列和栈视为重要的数据结构，通过例子来介绍抽象数据类型；3）程序设计：接口的使用和设计。本讲教学支持课程目标1、课程目标2、课程目标4。2.教学重点1）栈接口的定义和使用；2）结构与数据结构不变性：3）数据类型的抽象；4）队列接口的定义和使用；5）有界与无界栈和队列；3.教学难点1）数据结构不变性；2）数据类型的抽象；4.教学环节设计围绕教学重点和教学难点，综合运用课堂讲授与讨论、作业、在线讨论等教学形式。1）课堂讨论由于数组有容量的限制，用数组实现的栈在push时可能会因超过容量而溢出。如果仍然采用数组进行存储，能否改进栈的实现，使其避免溢出的发生？2）作业布置运用栈和队列编程的作业题。3）在线讨论本讲中，队列的实现不必要地浪费了大量空间。在入队和出队一些元素之后，back可能会到达容量上限，而如果front移动过，data数组开始的地方就会有空间被浪费。如何改变队列的实现，以将此存储空间重新用于数据入队？为此需要怎样修改函数eng和deq？第10讲指针和链表1.教学目标1）计算思维：以栈和队列的第二种实现来强调抽象的重要性；
第 9 讲 栈和队列 1. 教学目标 1）计算思维：考虑数据结构接口的用户端和库端，举例说明抽象的强大； 2）算法与数据结构：把队列和栈视为重要的数据结构，通过例子来介绍抽 象数据类型； 3）程序设计：接口的使用和设计。 本讲教学支持课程目标 1、课程目标 2、课程目标 4。 2. 教学重点 1）栈接口的定义和使用； 2）结构与数据结构不变性； 3）数据类型的抽象； 4）队列接口的定义和使用； 5）有界与无界栈和队列； 3. 教学难点 1）数据结构不变性； 2）数据类型的抽象； 4. 教学环节设计 围绕教学重点和教学难点，综合运用课堂讲授与讨论、作业、在线讨论等教 学形式。 1）课堂讨论 由于数组有容量的限制，用数组实现的栈在 push 时可能会因超过容量而溢 出。如果仍然采用数组进行存储，能否改进栈的实现，使其避免溢出的发生？ 2）作业 布置运用栈和队列编程的作业题。 3）在线讨论 本讲中，队列的实现不必要地浪费了大量空间。在入队和出队一些元素之后， back 可能会到达容量上限，而如果 front 移动过，data 数组开始的地方就会有空 间被浪费。如何改变队列的实现，以将此存储空间重新用于数据入队？为此需要 怎样修改函数 enq 和 deq？ 第 10 讲 指针和链表 1. 教学目标 1）计算思维：以栈和队列的第二种实现来强调抽象的重要性；
2）算法与数据结构：链表是一种基本的数据结构：3）程序设计：在编程中使用结构和指针，以及在结构定义中正确使用递归。本讲教学支持课程目标1、课程目标2和课程目标4。2.教学重点1）结构体和指针；2）链表及链表段：3）链表段环路检测算法（龟兔赛跑算法）：3.教学难点1）数据类型的定义和变量定义的实质区别；2）链表段环路检测算法中循环不变量的证明；4.教学环节设计围绕教学重点和教学难点，综合运用课堂讲授与讨论、作业、在线讨论等教学形式。1）课堂讨论利用指针进行数据间接访问的好处，以及指针使用上需注意的安全问题。2）作业运用指针和结构编程的作业题。3）在线讨论龟兔赛跑算法中，代表乌龟的指针在程序运行期间是否可能为空指针？如何证明？第11讲数据结构实现1.教学目标1）计算思维：给出第9讲所介绍的栈和队列的第二种实现，强调抽象的重要性；2）算法与数据结构：链表的使用，并且讨论检测环的算法：3）程序设计：利用结构和指针编程。本讲教学支持课程目标1和课程目标2。2.教学重点1）用链表实现队列；2）用链表实现栈；3）环路检查，改进的龟兔赛跑算法；4）内存印象
2）算法与数据结构：链表是一种基本的数据结构； 3）程序设计：在编程中使用结构和指针，以及在结构定义中正确使用递归。 本讲教学支持课程目标 1、课程目标 2 和课程目标 4。 2. 教学重点 1）结构体和指针； 2）链表及链表段； 3）链表段环路检测算法（龟兔赛跑算法）； 3. 教学难点 1）数据类型的定义和变量定义的实质区别； 2）链表段环路检测算法中循环不变量的证明； 4. 教学环节设计 围绕教学重点和教学难点，综合运用课堂讲授与讨论、作业、在线讨论等教 学形式。 1）课堂讨论 利用指针进行数据间接访问的好处，以及指针使用上需注意的安全问题。 2）作业 运用指针和结构编程的作业题。 3）在线讨论 龟兔赛跑算法中，代表乌龟的指针在程序运行期间是否可能为空指针？如何 证明？ 第 11 讲 数据结构实现 1. 教学目标 1）计算思维：给出第 9 讲所介绍的栈和队列的第二种实现，强调抽象的重 要性； 2）算法与数据结构：链表的使用，并且讨论检测环的算法； 3）程序设计：利用结构和指针编程。 本讲教学支持课程目标 1 和课程目标 2。 2. 教学重点 1）用链表实现队列； 2）用链表实现栈； 3）环路检查，改进的龟兔赛跑算法； 4）内存印象
3.教学难点1）通过用链表重新实现栈和队列，来理解抽象的重要性；2）龟兔赛跑算法中循环不变量的证明；4.教学环节设计围绕教学重点和教学难点，综合运用课堂讲授与讨论、作业、在线讨论等教学形式。1）课堂讨论抽象在数据结构重新实现中体现的优越性。2）作业运用指针和链表编程的作业。3）在线讨论我们编写的程序中，不同位置、不同方式定义的数据，在内存什么区域分配存储。第12讲无界数组1.教学目标1）计算思维：数据结构不变性和接口；2）算法与数据结构：无界数组及其操作，3）算法分析：对顺序操作进行平摊分析的推理方式；本章教学支持课程目标1和课程目标3。2.教学重点1）算法与数据结构：无界数组及其操作，2）算法分析：对顺序操作进行平摊分析的推理方式；3.教学难点1）算法分析：对顺序操作进行平摊分析的推理方式理解对顺序操作进行平摊分析的推理方式的内涵和利用其评价无界数组各项操作的性能。4.教学环节设计围绕教学重点和教学难点，综合应用课堂讲授与讨论、作业、课后练习与讨论、课外实践、课外阅读等教学形式。1）讨论围绕不同无界数组实现方式的各种操作的复杂度性能评价指标的内涵和局限性等问题展开
3. 教学难点 1）通过用链表重新实现栈和队列，来理解抽象的重要性； 2）龟兔赛跑算法中循环不变量的证明； 4. 教学环节设计 围绕教学重点和教学难点，综合运用课堂讲授与讨论、作业、在线讨论等教 学形式。 1）课堂讨论 抽象在数据结构重新实现中体现的优越性。 2）作业 运用指针和链表编程的作业。 3）在线讨论 我们编写的程序中，不同位置、不同方式定义的数据，在内存什么区域分配 存储。 第 12 讲 无界数组 1. 教学目标 1）计算思维：数据结构不变性和接口； 2）算法与数据结构：无界数组及其操作， 3）算法分析：对顺序操作进行平摊分析的推理方式； 本章教学支持课程目标 1 和课程目标 3。 2. 教学重点 1）算法与数据结构：无界数组及其操作， 2）算法分析：对顺序操作进行平摊分析的推理方式； 3. 教学难点 1）算法分析：对顺序操作进行平摊分析的推理方式 理解对顺序操作进行平摊分析的推理方式的内涵和利用其评价无界数组各 项操作的性能。 4. 教学环节设计 围绕教学重点和教学难点，综合应用课堂讲授与讨论、作业、课后练习与讨 论、课外实践、课外阅读等教学形式。 1）讨论 围绕不同无界数组实现方式的各种操作的复杂度性能评价指标的内涵和局 限性等问题展开