教学计划 - 《数据结构教程（C++语言描述）》

《数据结构教程（C++语言描述）》教学计划第3版·微课视频版（10章合订本）依据李春葆主编教材编制2026-05-13前言本教学计划合订本基于清华大学出版社《数据结构教程（C++语言描述）（第3版·微课视频版）》（李春葆主编）编制，共10章，对应64学时（理论48+实验16）。每章教学计划均包含：基本信息、教学目标、教学内容详述（按加涅九段教学法组织）、实验/实践环节、课后练习与教学日志六大板块。目录第1章绪论第2章线性表第3章栈和队列第4章串第5章数组和稀疏矩阵第6章递归第7章树和二叉树第8章图第9章查找第10章排序第1章绪论·课时教学计划1.基本信息项目内容章节第1章绪论周次第1周学时4学时（2次课，每次2学时）日期待填写授课对象计算机/软件/AI专业本科二年级教材李春葆《数据结构教程（C++语言描述）》第3版（清华大学出版社）2.教学目标教学重点数据结构三要素**：逻辑结构、存储结构、运算之间的相互关系逻辑结构的四种类型*：集合、线性、树形、图形存储结构的四种基本类型*：顺序、链式、索引、哈希抽象数据类型（ADT）的描述*算法的五大特性*：有穷性、确定性、可行性、输入性、输出性算法的时间复杂度分析**：大O记号、求和/求积定理、最好/最坏/平均情况算法的空间复杂度分析**教学难点复杂度的渐近分析：学生易把"O(1)表示常数1次"误解为"执行1次"。突破方法：用极限定义limn→∞嵌套循环T(n)推导：含有变上限循环（如j上限依赖i）的频度求和。突破方法：板书一步一步展开∑，强调"先内层后外层"。对数阶O(log2n)的来源：学生不知道为何与2的幂相关。突破方法：以"学习目标学完本章，学生应能够：理解数据结构三要素并能用二元组B=(D辨析集合、线性、树形、图形四类逻辑结构的特征与差异；辨析顺序、链式、索引、哈希四种存储结构的优缺点与适用场景；应用ADT描述方法，撰写一个简单数据类型（如Set）的ADT；应用大O记号、求和与求积定理推导算法的时间/空间复杂度；分析简单算法的最好、最坏、平均时间复杂度；评价不同算法的时空性能，判别"好"算法与"坏"算法。3.教学内容详述共4学时，建议分配：第1节（第1次课，2学时）讲1.1–1.2；第2节（第2次课，2学时）讲1.3–1.4并完成综合示例。3.1课堂引入（5分钟）📌引入案例：假设我们要做一个校园食堂排队系统。每位同学进入队伍尾部排队，前端的同学先打饭离开；又或者，我们要做一个全国铁路最短路径查询，从北京到上海，途径多个枢纽城市，求最短路径——同样是"数据+操作"，两个场景需要的"数据组织方式"完全不同：前者是一条"线"，后者是一张"网"。核心问题：同样存放学生信息，为什么有时用数组、有时用链表、有时用哈希表？同样求最短路径，为什么有Dijkstra、Floyd多种算法？哪个更好？为什么微信通讯录查找瞬间完成，而某些"暴力搜索"几秒甚至几分钟？本节课目标告知：

学完今天2节课的内容，你将能够：用数学语言（二元组）描述任何现实问题的数据组织方式；用C++编写一个简单数据类型的"接口（ADT）+实现"；用O(⋅)📌教学提示：展示DonaldE.Knuth教授和《计算机程序设计技巧》三卷本封面，简述数据结构学科诞生史，培养学科自豪感与对计算机科学奠基者的敬意。3.2知识铺垫（5分钟）回顾以下先修知识：C++数组与指针：inta[10]、int*p=newint[10]、delete[]pC++结构体与类：struct、class、构造函数、->运算符离散数学集合与关系：序偶⟨x,y数学求和：i=1📌板书一行求和公式，并提示后续频度计算会反复使用。3.3数据结构的基本概念（约45分钟）3.3.1数据结构的定义**核心术语链（板书）：数据数据对象数据结构的严谨定义：数据结构是带"结构"的数据元素集合，包括三方面：数据的逻辑结构——数据元素之间的逻辑关系（面向用户、独立于计算机）；数据的存储结构——逻辑结构在计算机内存中的"映像"（面向计算机）；数据的运算——施加在该数据上的操作。通俗解释：逻辑结构=设计图纸（"长什么样"）存储结构=实际建造（"砖怎么砌"）运算=房子能干什么（"住人/办公"）📌板书建议：

画一个三角形，三个顶点分别为"逻辑结构""存储结构""运算"，三角形中心写"数据结构"，箭头表示"逻辑→存储""存储←算法实现←运算"。3.3.2逻辑结构的二元组表示**通用表示：B其中：D={R={每个关系rj是若干序偶⟨x,y⟩（x为y的前驱，y关键概念：若x无前驱，称x为首结点/开始元素；若x无后继，称x为尾结点/终端元素；若关系r对称（即⟨x,y⟩∈r📌互动建议：让学生分别用二元组描述：一个班5名学生按学号排序的成绩表；计算机学院组织结构（院长—系主任—教师）。3.3.3逻辑结构的四种类型*对照讲解（板书一张二维表）：类型元素关系前驱/后继典型例子集合同属一个集合，无其他关系无前驱无后继全班学生（不排序）线性结构一对一至多1个前驱、1个后继成绩表、排队树形结构一对多1个前驱、多个后继组织结构、目录图形结构多对多多个前驱、多个后继交通网、社交网📌教学提示：用PowerPoint或白板分别画4张图：5个孤立结点/5个直线相连的结点/一棵4层小树/5个互相连接的结点。直观对比。3.3.4存储结构的四种类型*┌────────────┬─────────────────────────────┬───────────────────────┐

│存储结构│核心思想│优/缺│

├────────────┼─────────────────────────────┼───────────────────────┤

│顺序│逻辑相邻⇒物理相邻│随机存取/插入删除慢│

│链式│用指针域表示关系│插入删除快/不能随机访问│

│索引│元素表+索引表│查找快/占用额外空间│

│哈希(散列)│关键字─哈希函数→存储地址│查找最快/不存关系│

└────────────┴─────────────────────────────┴───────────────────────┘📌教学提示：以"学生高等数学成绩表"为统一例子，分别给出顺序存储（结构体数组）和链式存储（单链表）两套C++代码片段，强调"同一种逻辑结构→多种存储结构"。关键理解点：同一种逻辑结构可以有多种存储结构；同一种运算在不同存储结构上的实现算法不同（速度也不同）；选择存储结构必须考虑"对运算实现的方便和高效"。3.4抽象数据类型（ADT）（约30分钟）3.4.1数据类型vs数据结构数据类型数据结构程序语言已实现的类型+操作一般问题的数据组织+运算例：C++的int、double例：栈、二叉树、图📌类比：数据类型≈乐高基础积木块；数据结构≈用积木块搭建出来的城堡。3.4.2ADT的描述*定义：抽象数据类型（AbstractDataType,ADT）=用户从问题数学模型中抽象出的逻辑数据结构+该结构上的运算，不考虑具体存储和实现。三元组表示：ADT=(D：数据对象S：D上的关系集P：基本运算集通用格式：ADT抽象数据类型名{

数据对象：...

数据关系：...

基本运算：运算名(参数表)→运算功能描述

}【例1.6】集合ADT描述：ADTSet{

数据对象：data={d_i|0≤i≤length-1}

数据关系：无

基本运算：

intgetsize()//返回长度

intget(inti)//返回第i个元素

boolIsIn(Ee)//判断e∈集合？

voidadd(Ee)//插入元素e

booldeletem(Ee)//删除元素e

Set&Copy()//复制集合

voiddisplay()//输出元素

Set&Union(Sets2)//并：s3=s1∪s2

Set&Inter(Sets2)//交：s3=s1∩s2

Set&Diff(Sets2)//差：s3=s1−s2

}📌互动建议：让学生为"栈"写一份ADT描述（不超过6个运算），随机抽点2位学生写在黑板上对比。两个核心特征：数据抽象：只关心"做什么"，不关心"怎么做"——接口与实现分离；数据封装：内部实现对外不可见。3.5算法及其描述（约30分钟）3.5.1算法的定义与五大特性*定义：算法是对特定问题求解步骤的一种描述，是指令的有限序列。五大特性（必须全部满足）：特性含义反例有穷性有限步骤内结束，且每步可在合理时间内完成死循环while(true){}确定性每条指令含义唯一，无二义性"选一个大的数"可行性每条指令可被基本运算执行有限次完成x=5/0;（除零）输入性有零个或多个输入—输出性至少一个输出一个无输出的"算法"📌教学提示：用教材【例1.7】两段反例代码引导课堂讨论，让学生判断违反了哪条特性。算法vs程序：程序：算法的某种语言实现，不一定有穷（操作系统等）；算法：必须有穷，描述的是"做什么"。3.5.2C++描述算法的要点1)算法的一般格式：返回类型算法名(形参表){

//输入验证

//算法主体

//返回结果

}输入参数：传值；输出参数：传引用&（C++引用类型）；返回值：常用bool表示算法是否成功。【例1.8】求和s=1+2+⋯+boolSum1(intn,int&s){//引用参数返回结果

if(n<1)returnfalse;

s=n*(n+1)/2;

returntrue;

}

intSum2(intn){//返回值兼做错误码

if(n<1)return-1;

returnn*(n+1)/2;

}

intSum3(intn){//用异常处理错误

if(n<1)throw"参数错误";

returnn*(n+1)/2;

}关键理解点：输出参数int&s是C++引用，与实参共享内存，可双向传值；C++程序员自己用new申请、delete[]释放的空间，系统不会自动回收——内存泄漏是大忌。3.6算法分析（核心·约60分钟）3.6.1算法设计目标正确性>可使用性>可读性>健壮性>高时空性能。📌板书：5个目标按1～5排序，强调"正确性是底线"。3.6.2时间复杂度**定义：设算法的问题规模为n，算法中所有原操作的执行次数T(n)称为算法频度。

若存在正常量c,n0，使得当T为该算法的时间复杂度（大O记号、渐近时间复杂度）。通俗解释：数量级估算：找一个"上界"f(n)，描述当n很大时抓主要矛盾：保留最高阶，舍弃系数与低阶项。极限刻画（更易判断）：lim【例1.10】矩阵加法：voidmatrixadd(intA[N][N],intB[N][N],intC[N][N],intn){

for(inti=0;i<n;i++)//①

for(intj=0;j<n;j++)//②

C[i][j]=A[i][j]+B[i][j];//③

}推导：语句①频度：n+语句②频度：n(语句③频度：n2T📌板书：完整写出求和过程，强调"最深层语句决定阶数"。简化方法：仅考虑"最深层循环内的基本操作"的执行次数。3.6.3常见时间复杂度等级*O阶名称示例O常数阶简单赋值、读单元素O对数阶折半查找O线性阶一重循环、顺序查找O线性对数阶归并、快排（平均）O平方阶两重循环、冒泡O指数阶子集枚举O阶乘阶全排列、TSP暴力📌教学提示：展示一张n=10,100,1000时各阶函数值表（如n=1003.6.4三角嵌套循环示例**【例1.11】intfun(intn){

ints=0;

for(inti=0;i<=n;i++)

for(intj=0;j<=i;j++)

for(intk=0;k<j;k++)

s++;

returns;

}推导：T关键步骤板书：最内层k=中层j=外层i=3.6.5对数阶示例*【例1.12】intfun(intn){

intx=2;

while(x<n/2)x=2*x;//基本操作

returnx;

}推导：设循环执行m次，则2m+1=📌互动建议：让学生口述："变量x每次乘2→折半思想/倍增思想→对数阶"。3.6.6求和定理与求积定理*求和定理：T1求积定理：T1示例：for(inti=0;i<n;i++)s+=2;//O(n)

for(inti=0;i<n;i++)//O(n²)

for(intj=0;j<n;j++)s++;

//整体：O(max(n,n²))=O(n²)3.6.7最好、最坏、平均时间复杂度**设输入实例集Dn，P(I)为输入I平均：【例1.13】顺序查找：intfindk(inta[],intn,intk){

inti=0;

while(i<n&&a[i]!=k)i++;

returni;

}情况输入特征比较次数复杂度最好a1O最坏anO平均（等概率）—(O📌常见误解澄清：平均复杂度≠(最好+最坏)/2；必须按概率加权求期望。3.6.8空间复杂度*算法执行过程中临时占用的辅助存储空间的量度，记作S(注意：不计算代码空间、不重复计算形参空间；S(n)=O(13.7数据结构的目标与综合示例（约30分钟）3.7.1设计好算法的三步法问题定义（ADT）→设计存储结构→设计算法

↑│

└────反复迭代、互相影响──────┘关键观点：存储结构会影响算法的好坏，因此必须以"设计好算法"为目标来选择存储结构。3.7.2综合示例：用C++类实现SetADT📌教学提示：现场演示Set类完整代码（教材【例1.15】）：私有成员：int*data;intlength;intcapacity;公有成员：构造、析构、add/IsIn/Union/Inter/Diff/display主程序：构造两个集合，演示并、交、差。代码运行演示（板书或投影）：集合s1:14268

集合s2:2536

集合s1∪s2:1426853

集合s1−s2:148

集合s1∩s2:26📌互动建议：提问—Union函数的时间复杂度是多少？为什么？

（答：O(4.实验/实践环节实验0：环境搭建与"算法计时"实验（建议自学+课堂演示，2学时内可完成）实验目的：熟悉C++开发环境与编译/调试流程；验证时间复杂度的实际意义。实验环境：编译器：g++/clang++（C++17）；IDE：VSCode/CLion/Dev-C++；计时：<chrono>库的high_resolution_clock。实验步骤：配置环境：安装编译器，创建第一个helloworld工程；实现求和算法的3种版本：分别用O(1)公式法、O(n)循环累加、O(n^2)二重循环累加；使用如下代码计时：#include<chrono>

usingnamespacestd::chrono;

autot0=high_resolution_clock::now();

//...待测算法

autot1=high_resolution_clock::now();

doublems=duration<double,std::milli>(t1-t0).count();取n=103绘制曲线：横轴logn，纵轴log思考题：为什么O(1)算法在你的电脑跑O(n2)算法在n=10参考代码框架：#include<iostream>

#include<chrono>

usingnamespacestd;

usingnamespacestd::chrono;

longlongsumO1(intn){return(longlong)n*(n+1)/2;}

longlongsumOn(intn){

longlongs=0;

for(inti=1;i<=n;++i)s+=i;

returns;

}

longlongsumOn2(intn){

longlongs=0;

for(inti=1;i<=n;++i)

for(intj=1;j<=i;++j)s++;//模拟O(n^2)

returns;

}

intmain(){

intn;

cin>>n;

autot0=high_resolution_clock::now();

longlongr=sumOn(n);

autot1=high_resolution_clock::now();

cout<<"result="<<r

<<"time="<<duration<double,milli>(t1-t0).count()<<"ms\n";

return0;

}5.课后练习与作业基础概念题（3题）简答：数据结构的三要素是什么？它们之间的关系如何？辨析：顺序存储与链式存储的优缺点对比（要求列表对比4条以上）。简答：算法的5个特性是什么？请用一个反例分别说明违反每条特性的"伪算法"。二元组与ADT题（2题）写出"学校图书馆借阅记录表"（含读者证号、图书号、借阅日期）的二元组逻辑结构表示，并指明其属于哪种逻辑结构。仿照教材【例1.6】，写出栈（Stack）的ADT（不少于6个基本运算）。复杂度推导题（3题）分析以下算法的时间复杂度：for(inti=1;i<=n;i*=2)

for(intj=0;j<n;j++)

s++;分析以下算法的时间复杂度：for(inti=0;i<n;i++)

for(intj=i;j<n;j++)

for(intk=j;k<n;k++)s++;一个算法主要由两部分组成：第一部分时间复杂度为O(nlogn编程题（1题，选做）用C++实现"判断正整数n是否为素数"两种算法，分别为O(n)和O(参考答案要点三要素=逻辑结构+存储结构+运算；逻辑结构决定存储结构与运算的方式，存储结构是逻辑结构的物理实现，运算建立在存储结构之上。顺序：随机访问、节省空间；插入删除慢、需提前定容。链式：插入删除快、动态扩容；不能随机访问、需额外指针空间。有穷/确定/可行/输入/输出；反例分别为：死循环、含"选一个大数"的指令、除以0、缺少必要输入、无输出。线性结构；D={r1,rpush,pop,top,empty,size,clear等。外层logn次、内层n次，OO(n3)按求积定理，总O(O(n)算法约999999937次判断，O(n)算法仅6.板书设计（建议）┌──第1章绪论─────────────────────────────────────────────┐

││

│数据结构=①逻辑结构（D,R）②存储结构③运算│

││

│逻辑：集合/线性/树形/图形│

│存储：顺序/链式/索引/哈希│

││

│ADT=(D,S,P)接口与实现分离│

││

│算法5特性：有穷/确定/可行/输入/输出│

││

│T(n)=O(f(n))，limT(n)/f(n)=c≠0│

││

│O(1)<O(logn)<O(√n)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)│

││

│求和定理/求积定理│

│最好/最坏/平均│

└────────────────────────────────────────────────────────────┘7.教学日志日期记录内容学生反馈：教学效果：改进建议：8.课程思政点学科奠基：DonaldE.Knuth、华罗庚等科学家的故事，激发学生学科自豪感与"打基础"的意识；大国重器：中国铁路网最短路径计算、北斗导航中的数据结构应用，强化"技术服务国家"理念；工匠精神："为什么我们要分析最坏时间复杂度？"——工程系统必须考虑极端情况，培养严谨负责的工程素养。ewpage第2章线性表·课时教学计划1.基本信息项目内容章节第2章线性表周次第2–3周学时8学时（4次课，含上机2学时）日期待填写2.教学目标教学重点线性表的逻辑结构与ADT*顺序表与链表的存储与基本运算**单链表、双链表、循环链表的指针操作**有序顺序表/链表的二路归并*STLvector与list容器*教学难点链表的指针操作：插入、删除时"先连后断"的顺序问题；头结点与首结点的区别：带头结点链表vs不带头结点链表；双链表中删除结点的4步指针修改；存储结构选择：何时该用顺序表、何时该用链表。学习目标理解线性表的逻辑结构定义与ADT描述；掌握顺序表的插入、删除、查找算法及其时间复杂度（O(掌握单链表的头插法、尾插法建表，以及任意位置插入、删除算法；掌握双链表与循环链表的基本运算；应用有序顺序表/链表的二路归并算法解决合并问题；熟练使用STLvector、list容器解决工程问题；能够分析选择存储结构的依据。3.教学内容详述3.1课堂引入（5分钟）📌引入案例：微信通讯录有1000个联系人，新加好友、删除好友、按拼音排序、按字母索引……怎样的数据组织最高效？同一个"线性"数据，如果用数组存储vs用链表存储，会产生完全不同的算法实现与性能。本节目标：能写出顺序表与单链表的C++类；能分析每种基本运算的时间复杂度；能根据场景选择存储结构。3.2线性表的定义与ADT（约30分钟）3.2.1什么是线性表定义：线性表是具有相同特性的数据元素的有限序列，记为L其中n≥0称为表长，n三大特征：数据元素类型相同；数据元素个数有限；元素与位置相关（每个元素有唯一序号i，0≤📌板书：画一条带箭头的线，结点依次标a03.2.2线性表的ADTADTList{

数据对象：data={a_i|0≤i≤n-1}

数据关系：R={<a_i,a_{i+1}>|0≤i≤n-2}

基本运算：

CreateList(a[],n)voidAdd(e)

DispList()intGetLength()

GetElem(i,&e)SetElem(i,e)

GetNo(e)Insert(i,e)

Delete(i)

}📌互动建议：让学生列出10个真实生活中的线性表（如点名册、火车车厢、播放列表、单词链表……），强化对"线性"的直觉。3.3顺序表（约45分钟）3.3.1顺序存储结构**核心思想：用一片地址连续的存储单元（C++中用动态数组）依次存放线性表元素。template<typenameT>

classSqList{

public:

T*data;//动态数组

intlength;//当前实际元素个数

intcapacity;//数组容量

SqList(intcap=100){

data=newT[cap];

length=0;

capacity=cap;

}

~SqList(){delete[]data;}

//...基本运算

};地址映射：第i个元素的地址为LOC(其中c为单个元素占用字节数。这一映射是直接计算的，因此顺序表支持随机存取——GetElem(i)的时间复杂度为O(3.3.2基本运算与复杂度分析**运算算法思想时间复杂度整体建表依次data[i]=a[i]OAdd(e)data[length++]=eOGetLength返回lengthOGetElem(i)返回data[i]OSetElem(i,e)data[i]=eOGetNo(e)顺序查找OInsert(i,e)i之后元素全部后移ODelete(i)i之后元素全部前移O📌板书Insert算法：boolInsert(inti,Te){

if(i<0||i>length||length==capacity)returnfalse;

for(intj=length;j>i;j--)

data[j]=data[j-1];//后移

data[i]=e;

length++;

returntrue;

}平均移动次数：E故平均时间复杂度O(3.3.3顺序表应用示例实战2.1（LeetCode26）：删除排序数组中的重复项—用双指针法，i指向已去重区尾，j扫描后续；O(intremoveDuplicates(vector<int>&nums){

intn=nums.size();

if(n==0)return0;

inti=0;

for(intj=1;j<n;j++)

if(nums[j]!=nums[i])

nums[++i]=nums[j];

returni+1;

}📌互动建议：现场出题——"删除顺序表中所有值为x的元素，要求O(n3.4单链表（约60分钟）3.4.1链表的引入对比讨论：顺序表插入需要"全员让位"，链表只需"改两根线"；顺序表浪费容量/链表浪费指针空间。结点结构：template<typenameT>

structLinkNode{

Tdata;

LinkNode<T>*next;

LinkNode(Td=T()):data(d),next(nullptr){}

};带头结点的单链表：在首元素前增设一个"哨兵"结点head，简化插入/删除（不必特判表头）。📌板书：分别画"不带头结点"与"带头结点"两条单链表，对比插入第0个位置时的代码差异。3.4.2单链表的两种建表**头插法（逆序）：LinkNode<T>*head=newLinkNode<T>();

for(inti=0;i<n;i++){

auto*s=newLinkNode<T>(a[i]);

s->next=head->next;

head->next=s;

}尾插法（顺序）：LinkNode<T>*head=newLinkNode<T>();

auto*r=head;

for(inti=0;i<n;i++){

auto*s=newLinkNode<T>(a[i]);

r->next=s;

r=s;

}

r->next=nullptr;关键理解点：头插法结果与输入逆序，尾插法保持顺序；尾插法需要"尾指针r"，否则要遍历整表才能找到尾结点，时间退化为O(3.4.3单链表的插入与删除**插入"先连后断"原则（板书）：//在p之后插入s

s->next=p->next;//先连

p->next=s;//后断删除"先备份后释放"：LinkNode<T>*q=p->next;

p->next=q->next;

deleteq;📌教学提示：在课堂上用3段不同颜色的粉笔/记号笔模拟"指针箭头"，演示插入时如果顺序写反会出现"断链"。3.4.4单链表基本运算复杂度运算时间复杂度GetElem(i)O(Insert(i,e)已定位O(1)Delete(i)已定位O(1)对比顺序表：插入删除快了"移动元素"的代价，慢了"随机访问"。3.5双链表与循环链表（约40分钟）3.5.1双链表template<typenameT>

structDLinkNode{

Tdata;

DLinkNode<T>*prior;

DLinkNode<T>*next;

};插入新结点s到p之后（4步）：s->next=p->next;//①

s->prior=p;//②

if(p->next)p->next->prior=s;//③

p->next=s;//④📌板书：4个步骤画4张子图，标号清楚，强调顺序——③必须在④之前，否则丢失p->next的反向指针。3.5.2循环链表单循环链表：尾结点next指回头结点；双循环链表：首尾互连。优势：从任意结点出发都可遍历整个链表（适合"约瑟夫问题"等环形问题）。3.6顺序表vs链表的对比**维度顺序表链表存储连续离散随机访问OO插入/删除（已定位）O(O(空间利用需预分配按需分配，含指针开销适用场景静态数据、频繁查询动态数据、频繁增删3.7有序表的二路归并*问题：给定两个递增有序的线性表A、B，合并为一个递增有序表C。算法：双指针i,jvoidMergeSorted(intA[],intm,intB[],intn,intC[]){

inti=0,j=0,k=0;

while(i<m&&j<n)

C[k++]=(A[i]<=B[j])?A[i++]:B[j++];

while(i<m)C[k++]=A[i++];

while(j<n)C[k++]=B[j++];

}复杂度：O(📌教学提示：链表版本的归并不需移动元素，只需"链接"；现场演示链表版本代码。3.8STLvector与list*容器底层典型操作复杂度vector动态数组[i]：O(1)；push_back：均摊list双链表任意位置插入/删除：O(1)📌互动建议：让学生用vector和list分别实现"插入10^5次随机位置"，测时间，验证理论分析。4.实验环节实验1：顺序表与链表实现及性能对比（2学时）实验目的：熟练实现顺序表与单链表的C++类；通过时间测量验证两种结构的性能差异。实验内容：实现SqList与LinkList两个类，支持Insert/Delete/GetElem/Display；分别在n=10头部插入1000次；末尾插入1000次；随机位置访问1000次；实测时间，填表对比，分析与理论是否吻合。思考题：顺序表的"末尾插入1000次"实测应该接近O(1)还是链表的"随机位置访问1000次"为什么比顺序表慢？如果改用std::vector与std::list，结果有差异吗？为什么？5.课后练习基础概念题（3题）顺序表和链表各有何优缺点？分别在什么场合使用？解释为什么带头结点的链表在编程上更"统一"。头插法与尾插法分别建表后，元素顺序与输入序列有何关系？算法设计题（3题）设计算法：将顺序表中所有值为x的元素删除，要求时间复杂度O(n)、空间复杂度设计算法：将单链表就地逆置，不分配新结点。要求时间O(n)、空间设计算法：在有序单链表中删除所有重复元素（如1→1→2→STL应用题（1题）用std::list<int>实现"约瑟夫环"问题（n人围成一圈，每数到第k人出列，输出出列顺序）。答案要点双指针i,j：i指向"保留区末尾"，j头插法逆置：依次取出原链表的结点，头插到新链表。比较p->data与p->next->data，相同则删除p->next。利用list的迭代器删除，注意"环形"模拟（迭代器越过end()时回到begin()）。6.教学日志日期学生反馈教学效果改进建议ewpage第3章栈和队列·课时教学计划1.基本信息项目内容章节第3章栈和队列周次第4周学时4学时（2次课，含上机2学时）日期待填写2.教学目标教学重点栈与队列的定义与抽象数据类型*顺序栈、链栈基本运算**顺序队、循环队列、链队基本运算**栈的典型应用：括号匹配、表达式求值、迷宫求解*队列的典型应用：层次遍历、滑动窗口*STLstack、queue、deque、priority_queue*单调栈与单调队列**教学难点循环队列的"假溢出"与判空判满方法（少用一格/计数器/标志位）；链栈、链队的指针管理：易出错点；单调栈/队列的"维持单调性"：何时弹出，何时压入。学习目标理解栈"后进先出"与队列"先进先出"的本质；掌握顺序栈、链栈、顺序队（含循环队）、链队的完整实现；应用栈解决括号匹配、表达式求值、递归消除问题；应用队列解决多层缓冲、广度优先遍历问题；熟练使用STL的4类容器适配器；掌握单调栈/队列的设计思想并求解"下一个更大元素"等问题。3.教学内容详述3.1课堂引入（5分钟）📌引入案例：栈：浏览器"前进/后退"、Word"Ctrl+Z撤销"、函数调用栈；队列：打印机任务队列、消息推送、CPU进程调度；单调栈：股票价格"下一个更高价"——朴素O(n2)vs本节目标：区分栈与队列的应用场景；熟练编写4种具体实现的代码；掌握单调栈/队列这一算法竞赛常用模板。3.2栈（共约1.5学时）3.2.1栈的定义*栈是只允许在同一端进行插入/删除的线性表，该端称为栈顶（top），另一端称为栈底（base）。

特性：后进先出（LastInFirstOut,LIFO）。基本操作：Push,Pop,GetTop,IsEmpty,Size。📌板书：画一根竖直的"桶"，元素从顶部依次入栈，再依次出栈。3.2.2顺序栈**带"栈顶指针top"约定：top指向当前栈顶元素（初始为-1template<typenameT>

classSqStack{

T*data;

inttop;

intcapacity;

public:

SqStack(intc=100):capacity(c),top(-1){data=newT[c];}

~SqStack(){delete[]data;}

boolPush(Te){

if(top==capacity-1)returnfalse;

data[++top]=e;

returntrue;

}

boolPop(T&e){

if(top==-1)returnfalse;

e=data[top--];

returntrue;

}

boolGetTop(T&e)const{

if(top==-1)returnfalse;

e=data[top];

returntrue;

}

boolIsEmpty()const{returntop==-1;}

};所有操作均为O(3.2.3链栈栈顶=链表表头；每次Push即在表头插入，Pop即删除表头结点。同样所有操作O(3.2.4栈的典型应用**应用1：括号匹配boolcheckParens(conststring&s){

stack<char>st;

for(charc:s){

if(c=='('||c=='['||c=='{')st.push(c);

else{

if(st.empty())returnfalse;

chart=st.top();st.pop();

if((c==')'&&t!='(')||

(c==']'&&t!='[')||

(c=='}'&&t!='{'))returnfalse;

}

}

returnst.empty();

}📌教学提示：现场演示输入({[]})通过，([)]失败，深入讨论"为什么栈天然适合解决这类问题"。应用2：表达式求值（中缀转后缀+后缀求值）中缀转后缀：用栈缓存运算符，遇到优先级更低时出栈；后缀求值：用栈存操作数，遇到运算符弹出两个操作数计算。应用3：迷宫求解（DFS显式栈版）将"待探索位置"压入栈，每次取栈顶探索其4邻居。3.3队列（共约1.5学时）3.3.1队列的定义*队列是只允许在一端插入（队尾rear）、在另一端删除（队首front）的线性表。

特性：先进先出（FirstInFirstOut,FIFO）。3.3.2循环队列**问题：朴素顺序队Q[0..N-1]、front,rear单调递增→"假溢出"（rear超N但前面有空）。解决：把数组"首尾相接"，rear=(rear+1)%N，front=(front+1)%N。判空判满的"少用一格"约定：空：front==rear；满：(rear+1)%N==front。template<typenameT>

classCircularQueue{

T*data;

intfront,rear,capacity;

public:

CircularQueue(intc=100):capacity(c),front(0),rear(0){data=newT[c];}

~CircularQueue(){delete[]data;}

boolEnQueue(Te){

if((rear+1)%capacity==front)returnfalse;//满

data[rear]=e;

rear=(rear+1)%capacity;

returntrue;

}

boolDeQueue(T&e){

if(front==rear)returnfalse;//空

e=data[front];

front=(front+1)%capacity;

returntrue;

}

intSize()const{return(rear-front+capacity)%capacity;}

};📌板书：画一个"圆环"图，标8个位置，演示连续入队7次再出队3次时front、rear的变化。3.3.3链队用"队首指针+队尾指针"管理一条单链表，入队在尾、出队在首，均为O(3.3.4队列典型应用广度优先遍历（详见第8章图）；层次遍历二叉树（详见第7章）；作业调度、消息缓冲。3.4STL中的栈与队列容器*容器头文件底层默认关键接口stack<T><stack>dequepush/pop/top/empty/sizequeue<T><queue>dequepush/pop/front/back/empty/sizedeque<T><deque>分段数组push_front/push_back/pop_front/pop_back/[i]priority_queue<T><queue>堆push/pop/top（默认大顶堆）📌教学提示：演示用priority_queue<int,vector<int>,greater<int>>构造小顶堆。3.5单调栈与单调队列**（约1学时）3.5.1单调栈定义：栈内元素从栈底到栈顶单调递增（或递减）。经典问题：下一个更大元素给数组a，对每个ai找右边第一个比它大的元素，没有记为-朴素：O(n2)；vector<int>nextGreater(vector<int>&a){

intn=a.size();

vector<int>res(n,-1);

stack<int>st;//存下标

for(inti=0;i<n;i++){

while(!st.empty()&&a[st.top()]<a[i]){

res[st.top()]=a[i];

st.pop();

}

st.push(i);

}

returnres;

}关键理解点：维持"栈内元素递减"——新元素来到时，把比它小的全部弹出并赋值；每个元素至多入栈一次、出栈一次→均摊O(📌教学提示：手工跟踪a=[2,1,5,3,6]的求解过程，画出栈的演化。3.5.2单调队列经典问题：滑动窗口最大值（LeetCode239）长度n的数组、窗口大小k，求每个窗口内的最大值，O(vector<int>maxSlidingWindow(vector<int>&a,intk){

deque<int>dq;//存下标，对应值单调递减

vector<int>res;

for(inti=0;i<(int)a.size();i++){

while(!dq.empty()&&dq.front()<=i-k)dq.pop_front();

while(!dq.empty()&&a[dq.back()]<a[i])dq.pop_back();

dq.push_back(i);

if(i>=k-1)res.push_back(a[dq.front()]);

}

returnres;

}4.实验环节实验2：栈与队列的应用（2学时）实验目的：实现顺序栈、链栈、循环队列、链队；用栈实现表达式求值；用队列实现迷宫最短路径（BFS）；体验单调栈/队列解决经典问题。实验题目（任选两题）：A.中缀表达式求值输入形如3+(4*2-1)/5的字符串，输出结果；提示：双栈（操作符栈+操作数栈）。B.迷宫求解（BFS）输入m×n0/1矩阵，起点(0,提示：用队列保存待访问位置+visited矩阵。C.滑动窗口最大值（LeetCode239）输入a与k，输出每个窗口最大值；提示：单调双端队列。思考题：顺序栈与链栈相比，性能与空间分别有何差异？循环队列"少用一格"和"用计数器"哪种更优？为什么？单调栈中元素被弹出后，对结果还会有贡献吗？5.课后练习写出顺序栈的Pop与链栈的Pop的完整代码并对比。已知入栈序列为1,2,3,4，下列哪个设计算法：用两个栈模拟一个队列。要求enqueue与dequeue的均摊复杂度均为O(用单调栈求柱状图最大矩形（LeetCode84）。用循环队列Q[0..7]（8个位置），依次入队6次出队2次入队3次，画出front,rear的变化。答案要点选C；理由：3出栈后栈中只剩1,2（2在上），不可能立即出1而2留在栈中。入栈用stackIn，出栈时若stackOut为空，则把stackIn全部倒入stackOut，再出stackOut.top()。6.教学日志日期学生反馈教学效果改进建议ewpage第4章串·课时教学计划1.基本信息项目内容章节第4章串周次第5周学时4学时（含上机2学时）日期待填写2.教学目标教学重点串的定义、串与线性表的异同*顺序串、链串的存储结构*STLstring容器*BF模式匹配算法*KMP模式匹配算法**教学难点KMP的next数组（失败函数）求解：教学经验表明，这是数据结构入门阶段最难点之一；next数组的"自匹配"思想——为何用串自身的前后缀公共长度做"回滚"；改进的nextval数组。学习目标理解串的定义、长度、子串、模式匹配等概念；掌握顺序串、链串的存储结构与基本运算；熟练使用STLstring；掌握并能手算BF算法的执行过程；掌握并能手算KMP算法及next数组求解；应用串匹配解决文本检索、敏感词过滤等问题。3.教学内容详述3.1课堂引入（5分钟）📌引入案例：Google搜索、Word"查找替换"、生物信息学的DNA序列比对、网络入侵检测的特征码扫描——所有这些都依赖字符串模式匹配。

一个1GB的文本搜索某个100字节的模式串，BF暴力算法在最坏情况下要做近1011次比较；KMP仅109次——速度差1003.2串的基本概念（约30分钟）3.2.1串的定义*串是由零个或多个字符组成的有限序列：$$\mathrm{str}="a_0a_1\cdotsa_{n-1}",\n\geqslant0\qquad\text{(13)}$$其中n称为串长，n=0称为关键术语：空串：长度为0；空白串：仅由空格组成，长度≥1子串：原串中任意连续的字符序列；主串：包含子串的串；串相等：长度相同+对应字符全部相同；串比较：按字典序（ASCII顺序）。📌互动建议：提问：长度为n且字符各不相同的串有多少个非空子串？答案：n(n+1)3.2.2串与线性表的关系*维度一般线性表串元素类型任意字符操作粒度单个元素整体或子串典型操作插入、删除、查找单个串赋值、串连接、求子串、模式匹配串是特殊的线性表：元素全为字符，且强调"整串"操作。3.2.3串ADTADTString{

数据对象：D={a_i|a_i∈Char,0≤i≤n-1}

基本运算：

StrLength(s)StrCompare(s,t)

Concat(s,t)SubStr(s,i,len)

Index(s,t)StrInsert(s,i,t)

StrDelete(s,i,len)StrReplace(s,t1,t2)

}3.3串的存储结构（约20分钟）3.3.1顺序串constintMAXSIZE=256;

structSqString{

chardata[MAXSIZE];

intlength;

};末尾常用'\0'终止符（C风格）或length字段（教材风格）。3.3.2链串每个结点存1个或多个字符；结点存多个字符可减少指针开销（块链）。📌教学提示：实际工程中几乎都用顺序存储+动态扩容（C++的std::string、Java的String）；链串仅在编辑器、版本控制等需要频繁插入删除时使用。3.3.3STLstd::string*strings="Hello,World!";

s.length();//13

s.substr(7,5);//"World"

s.find("World");//7(找不到返回string::npos)

s+="C++";//拼接

s[0]='h';//修改3.4BF算法（暴力法）（约20分钟）3.4.1算法思想主串S（长度n）与模式串T（长度m），从S的每个位置i开始尝试与T比对，失败则i回退到i+1，TintBF(conststring&S,conststring&T){

intn=S.size(),m=T.size();

for(inti=0;i<=n-m;i++){

intj=0;

while(j<m&&S[i+j]==T[j])j++;

if(j==m)returni;//命中

}

return-1;//未命中

}3.4.2复杂度分析最好：O(最坏：O(n⋅m)（如平均：O(📌板书：跟踪S="abcabcabd"、T="abcabd"的执行过程，体会"失败后主串指针回退3.5KMP算法（核心·约45分钟）**3.5.1KMP的核心思想当S[i+j]≠T[j]失配时，主串指针i不回退，模式串指针j跳到next[j3.5.2next数组的定义next📌教学提示：用图示展示"前缀-后缀公共部分":T:ababcab

j:0123456

next:-10012013.5.3next求解算法voidgetNext(conststring&T,vector<int>&next){

intm=T.size();

next.assign(m,0);

next[0]=-1;

intk=-1,j=0;

while(j<m-1){

if(k==-1||T[j]==T[k]){

++j;++k;

next[j]=k;

}else{

k=next[k];

}

}

}关键理解点："递推式"求next：已知next[j]求若T[j]=T否则k回退到next[k3.5.4KMP主算法intKMP(conststring&S,conststring&T){

intn=S.size(),m=T.size();

vector<int>next;

getNext(T,next);

inti=0,j=0;

while(i<n&&j<m){

if(j==-1||S[i]==T[j]){i++;j++;}

elsej=next[j];

}

return(j==m)?(i-m):-1;

}复杂度：O(📌板书演示：手工跟踪S="abababcabab"、T="ababc"的全过程，标注每一步3.5.5改进的nextval数组（选讲）当T[j]=T[next[j]]时，失配后跳到nextvoidgetNextval(conststring&T,vector<int>&nv){

intm=T.size();

nv.assign(m,0);

nv[0]=-1;

intk=-1,j=0;

while(j<m-1){

if(k==-1||T[j]==T[k]){

++j;++k;

nv[j]=(T[j]!=T[k])?k:nv[k];

}elsek=nv[k];

}

}4.实验环节实验3：KMP算法实现与文本检索（2学时）实验目的：实现BF与KMP两种算法；实测在大文本上的性能差异；用KMP实现一个简单的"敏感词过滤"工具。实验内容：编写intBF(stringS,stringT)与intKMP(stringS,stringT)；测试用例：S=100万字符的随机文本；T=长度10、20、50的模式串；各跑10次取平均；对比表格输出执行时间；挑战：从文件读入敏感词表（100个），扫描一篇文章，标出所有命中位置。思考题：KMP的next数组本质上反映了模式串的什么性质？在哪些情况下，BF与KMP的性能差异最显著？多模式匹配（同时匹配100个串）能否扩展KMP？（提示：Aho-Corasick自动机）5.课后练习求串T="abaabcac"的next数组与nextval数组（必考题型）。在S="acabaabaabcacaabc"中用BF与KMP搜索T="abaabcac"，给出每一步的设计算法：判断串T是否为串S的循环移位串（如S="abcd"，用STLstring实现：统计一段英文文本中每个单词出现的频率，按频率降序输出Top10。答案要点next=[-1,0,0,1,1,2,0,1]；nextval=[-1,0,-1,1,0,2,-1,1]（具体值请学生推导验证）。巧解：拼接S+S，判断T是否为其子串（用KMP实现map<string,int>计数后转vector<pair>排序。6.教学日志日期学生反馈教学效果改进建议ewpage第5章数组和稀疏矩阵·课时教学计划1.基本信息项目内容章节第5章数组和稀疏矩阵周次第6–7周学时4学时（含上机2学时）日期待填写2.教学目标教学重点数组的逻辑结构与存储结构：行优先vs列优先*元素地址计算公式**特殊矩阵的压缩存储（对称、三角、对角矩阵）*稀疏矩阵的三元组表示与十字链表表示**教学难点二维及多维数组的地址映射公式——含起始下标非0的情况；特殊矩阵下标转换：从(i,j)到压缩存储下标十字链表的指针管理：行链+列链交叉。学习目标理解数组与一般线性表的差异；掌握d维数组按行/列优先存储的地址映射公式并能熟练计算；掌握对称矩阵、三角矩阵、对角矩阵的压缩存储下标转换公式；掌握稀疏矩阵的三元组顺序表表示与基本运算（转置、加法）；理解十字链表表示及其优缺点。3.教学内容详述3.1课堂引入（5分钟）📌引入案例：一张1024×1024的灰度图像存为整型二维数组，占4MB；推荐系统的用户-物品矩阵可能是107×106，但99.9%若用普通二维数组，需要4×1013字节核心问题：如何"按需"存储这些大矩阵？3.2数组的基本概念（约25分钟）3.2.1数组的定义*数组是二元组(下标,A其中d为维数，nk为第k数组与线性表的关系：数组是线性表的推广。一维数组=线性表；二维数组=每个元素本身又是一维线性表（行可视为元素的元素）。3.2.2数组的存储结构**两种主流存放方式：方式行优先（C/C++/Python）列优先（Fortran/MATLAB）顺序按行依次存储按列依次存储二维数组A[m][LOC(其中c为单元素字节数。📌板书：在黑板上画一张3×4的二维数组，标出每个元素的"线性下标"d维数组（设下标从0开始）地址公式：LOC(典型考题：A[1..8,1..6,1..10转换：i1LOC=1003.3特殊矩阵的压缩存储（约30分钟）思想：相同元素只存一份；零元素不存。3.3.1对称矩阵*n×n矩阵A满足aij=aji，一维数组B下标映射：k📌板书：画4×4对称矩阵，演示如何把下三角元素依次存入B[3.3.2三角矩阵下三角矩阵：上三角全0（或常数c）；上三角矩阵：下三角全0；存法类似对称矩阵，再附加1个常数c位置。3.3.3对角矩阵*仅主对角线及其上下k条副对角线非零，称为(2k+1三对角矩阵（k=1）：只存3n-2当|i-j3.4稀疏矩阵（约30分钟）**3.4.1稀疏矩阵的判别设m×n矩阵有t个非零元素，定义稀疏因子δ=t/(3.4.2三元组顺序表**思想：只存非零元素的(行structTriple{

introw,col;

doubleval;

};

structTSMatrix{

introws,cols,nums;//总行数、列数、非零个数

Tripledata[MAXSIZE];//按行序存放

};三元组转置算法（朴素vs一次定位）：朴素法：扫描cols次，每次找col==k的元素，时间O(一次定位法：先统计每列非零个数num[]，求前缀和cpot[]（每列在转置后三元组中的起始位置），再遍历一次原表把元素直接放到正确位置；时间O(voidFastTranspose(constTSMatrix&M,TSMatrix&T){

T.rows=M.cols;T.cols=M.rows;T.nums=M.nums;

if(M.nums==0)return;

vector<int>num(M.cols,0),cpot(M.cols);

for(inti=0;i<M.nums;i++)num[M.data[i].col]++;

cpot[0]=0;

for(intcol=1;col<M.cols;col++)

cpot[col]=cpot[col-1]+num[col-1];

for(inti=0;i<M.nums;i++){

intcol=M.data[i].col;

intq=cpot[col]++;

T.data[q].row=col;

T.data[q].col=M.data[i].row;

T.data[q].val=M.data[i].val;

}

}📌教学提示：以4×5稀疏矩阵（5个非零元素）为例，手工跟踪num与cpot数组演化过程。3.4.3十字链表每个非零元素既在行链上又在列链上：structOLNode{

introw,col;

doubleval;

OLNode*right;//指向同行下一非零