数据结构简明教程（第3版） 教案

数据结构课程教案 PAGE3PAGE4 数据结构简明教程（第3版）数据结构教案课堂学时：32，实验学时：32（基础实验24+综合实验12）说明：基础实验可以在相关教学内容讲授完毕时布置，综合实验在整个课程内容讲授完毕时布置。实验成绩评分：考勤（30%）+编程水平（30%）+实验报告（40%），可以选择若干综合实验题撰写实验报告，其格式可参考《数据结构简明教程（第3版）学习与实验指导》中实验报告示例。课次：1（每次2学时）（1）对应章：第1章概论。（2）教学内容：数据结构的基本概念；算法的基本概念；算法描述方法；算法分析方法。（3）教学方式：以课堂讲授为主。（4）教学重点和难点：数据结构的3个方面（逻辑结构，存储结构和运算），算法时间复杂度分析。（5）教学过程：围绕学生成绩表讲授什么是数据结构。通过示例讲授算法时间复杂度分析方法。（6）作业：概论部分的若干问答题和算法分析题。课次：2（每次2学时）（1）对应章：第2章线性表。（2）教学内容：线性表的定义和顺序表存储结构。（3）教学方式：以课堂讲授为主。（4）教学重点和难点：顺序表存储结构，线性表基本运算算法设计和顺序表应用算法设计。（5）教学过程：以顺序表基本运算算法设计为核心讲授顺序表高效算法设计方法。（6）作业：无课次：3（每次2学时）（1）对应章：第2章线性表。（2）教学内容：线性表的单链表存储结构。（3）教学方式：以课堂讲授为主。（4）教学重点和难点：单链表存储结构，单链表基本运算算法设计和单链表应用算法设计。（5）教学过程：以单链表基本运算算法设计为核心讲授单链表高效算法设计方法。（6）作业：无课次：4（每次2学时）（1）对应章：第2章线性表。（2）教学内容：线性表的双链表和循环链表存储结构，线性表两类存储结构的比较。线性表的应用。（3）教学方式：以课堂讲授为主。（4）教学重点和难点：线性表两类存储结构的比较和线性表的应用。（5）教学过程：简要介绍双链表和循环链表，以两个多项式相加讲授线性表的应用。（6）作业：线性表部分的若干问答题和算法设计题。（7）实验：根据学生层次选择若干线性表部分的基础和应用实验题（实验内容：设计顺序表各种基本运算的算法，设计单链表各种基本运算的算法（2学时））。课次：5（每次2学时）（1）对应章：第3章栈和队列。（2）教学内容：栈的定义和栈的两类存储结构，栈的基本应用。（3）教学方式：以课堂讲授为主。（4）教学重点和难点：栈的两类存储结构中基本运算算法设计，栈的基本应用。（5）教学过程：结合线性表的相关知识点讲授栈的两类存储结构及其实现。（6）作业：无课次：6（每次2学时）（1）对应章：第3章栈和队列。（2）教学内容：队列的定义和队列的两类存储结构，队列的基本应用。（3）教学方式：以课堂讲授为主。（4）教学重点和难点：队列的两类存储结构中基本运算算法设计，队列的基本应用。（5）教学过程：结合线性表的相关知识点讲授队列的两类存储结构及其实现。（6）作业：栈和队列部分的若干问答题和算法设计题。（7）实验：根据学生层次选择若干栈和队列部分的基础和应用实验题（实验内容：设计顺序栈各种基本运算的算法，设计链栈各种基本运算的算法（2学时）；设计顺序队各种基本运算的算法，设计链队各种基本运算的算法（2学时））。课次：7（每次2学时）（1）对应章：第4章串。（2）教学内容：串的定义和串的两类存储结构。（3）教学方式：以课堂讲授为主。（4）教学重点和难点：串的两类存储结构中基本运算算法设计。（5）教学过程：通过示例讲授串的基本应用方法。（6）作业：串部分的若干问答题和算法设计题。（7）实验：无。课次：8（每次2学时）（1）对应章：第5章数组和稀疏矩阵。（2）教学内容：数组的定义，数组存储结构，特殊矩阵的压缩存储，稀疏矩阵的压缩存储。（3）教学方式：以学生自学为主，以课堂讲授为辅。（4）教学重点和难点：特殊矩阵的压缩存储和稀疏矩阵的压缩存储。（5）教学过程：从空间开销讲授为什么进行压缩存储。（6）作业：数组和稀疏矩阵部分的若干问答题和算法设计题。（7）实验：无。课次：9（每次2学时）（1）对应章：第6章树和二叉树。（2）教学内容：树的概念和术语、二叉树概念和性质、二叉树存储结构、二叉树的基本运算及其实现。（3）教学方式：以课堂讲授和学生自学并重。（4）教学重点和难点：树和二叉树的性质，二叉树基本运算算法设计方法。（6）教学过程：从递归算法设计出发讲授二叉树的递归算法设计方法。（7）作业：无。课次：10（每次2学时）（1）对应章：第6章树和二叉树。（2）教学内容：二叉树的遍历。（3）教学方式：以课堂讲授为主。（4）教学重点和难点：二叉树先序、中序和后序遍历递归和非递归算法，二叉树层次遍历算法，二叉树遍历算法的应用。（5）教学过程：以示例为核心讲授二叉树遍历算法的应用。（6）作业：无。课次：11（每次2学时）（1）对应章：第6章树和二叉树。（2）教学内容：二叉树的构造、线索二叉树、哈夫曼树和并查集。（3）教学方式：以课堂讲授为主。（4）教学重点和难点：二叉树的构造、线索二叉树和哈夫曼树。（5）教学过程：以示例为核心讲授二叉树的构造、线索二叉树和哈夫曼树。（6）作业：树和二叉树部分的若干问答题和算法设计题。（7）实验：根据学生层次选择树和二叉树部分的若干基础和应用实验题（实验内容：设计二叉树先序、中序和后3种递归遍历算法（2学时）；设计二叉树层次遍历算法（2学时））。课次：12（每次2学时）（1）对应章：第7章图。（2）教学内容：图的基本概念；图的存储结构；图的遍历及其应用。（3）教学方式：以课堂讲授为主。（4）教学重点和难点：图的遍历及其应用。（5）教学过程：以示例为核心讲授图的存储结构和图的遍历及其应用。（6）作业：无。课次：13（每次2学时）（1）对应章：第7章图。（2）教学内容：生成树和最小生成树，最短路径，拓扑排序，AOE网与关键路径。（3）教学方式：以课堂讲授和学生自学并重。（4）教学重点和难点：Prim和Kruskal算法，Dijkstra算法。（5）教学过程：以示例为核心讲授最小生成树的算法和最短路径算法。（6）作业：图部分的若干问答题和算法设计题。（7）实验：根据学生层次选择图部分的若干基础和应用实验题（实验内容：设计图的DFS遍历算法（2学时）；设计图的BFS遍历算法（2学时））。课次：14（每次3学时）（1）对应章：第8章查找。（2）教学内容：查找的基本概念，线性表的查找，树表的查找，哈希表（3）教学方式：以课堂讲授和学生自学并重。（4）教学重点和难点：折半查找，二叉排序树，哈希表。（5）教学过程：以各种查找方法的特点和查找性能出发讲授各种查找算法。（6）作业：查找部分的若干问答题和算法设计题。（7）实验：根据学生层次选择查找部分的若干基础和应用实验题（实验内容：设计顺序查找和折半查找算法（2学时）；设计二叉排序树算法（2学时），设计哈希表算法（2学时））。课次：15（每次3学时）（1）对应章：第9章排序。（2）教学内容：排序的基本概念，插入排序，交换排序，选择排序，归并排序，基数排序。（3）教学方式：以课堂讲授和学生自学并重。（4）教学重点和难点：快速排序，堆排序和二路归并排序。（5）教学过程：以排序算法的特点出发讲授各种排序算法。（6）作业：排序部分的若干问答题和算法设计题。（7）实验：根据学生层次选择排序部分的若干基础和应用实验题（实验内容：设计各种排序算法（4学时））。综合实验题1.线性表应用：①求集合（用单链表表示）的并、交和差运算，②求两个多项式相加运算，③链表综合算法设计。（3学时）2.用二叉树表示家谱并实现相关算法（3学时）3.GIS中最短路径规划（3学时）4.各种内排序算法的时间比较（3学时）实验报告示例1实验目的掌握队列特点、链队存储结构和循环单链表操作方法，理解队列的基本运算并且采用高效的算法实现其基本运算。2实验内容假设在整个队列操作中所有进队的元素均为正整数，设计一个包含如下基本运算的链队qu：（1）initqu(qu)：建立一个空队qu。（2）destroyqu(qu)：释放队列qu占用的内存空间。（3）empty(qu)：判断队列qu是否为空。（4）getlength(qu)：返回队列qu中的元素个数。（5）push(qu，x)：将正整数x插入到队列qu的队尾。（6）top(qu)：返回队列qu中队头元素，当队空时返回-1。（7）pop(qu)：删除队列qu中的队头元素。尽可能设计高效的算法实现上述基本运算。要求采用相关数据进行测试。3实验设计1.数据结构设计采用带尾结点指针rear的循环单链表存储队列中的元素，rear指向队尾结点，rear->next指向队头结点，如图1所示。rearrear…队头队尾图1带尾结点指针rear的循环单链表队列中数据结点的类型说明如下：typedefstructnode{ intdata; //队列中元素 structnode*next; //后继结点的指针}DNode;链队头结点的类型说明如下：typedefstructqnode{ intlength; //队列中元素个数 DNode*rear; //队尾指针}QNode;例如，在链队qu（初始为空）中依次进队整数1，2，3后的结果如图2所示，链队头结点中包含length成员可以简化算法设计，但需要在进队出队操作中维护其正确性。11rear32队头队尾3qulength图2链队qu2.算法设计（1）initqu(qu)用于建立一个空队qu，即创建一个头结点，初始化其rear成员为NULL和length成员为0。对应的算法如下：voidinitqu(QNode*&qu){ qu=(QNode*)malloc(sizeof(QNode)); qu->rear=NULL; qu->length=0;}（2）destroyqu(qu)用于销毁队列qu，不仅需要释放队列中所有数据结点，还需要释放链队头结点。对应的算法如下：voiddestroyqu(QNode*&qu){ if(qu->length==0) free(qu); //释放链队结点 else { if(qu->length==1) free(qu->rear); else { DNode*pre=qu->rear,*p=qu->rear->next; while(p!=qu->rear) { free(pre); pre=p;p=pre->next; } free(pre); } free(qu); //释放链队结点 }}（3）empty(qu)用于判断队列qu是否为空，当队空时返回1，否则返回0。直接判断其length成员是否为0即可。对应的算法如下：intempty(QNode*&qu){ returnqu->length==0;}（4）getlength(qu)用于返回队列qu中的元素个数，直接返回其length成员即可。对应的算法如下：intgetlength(QNode*qu){ returnqu->length;}（5）push(qu，x)用于正整数x的进队操作。先创建结点s存放x，队列为空时建立仅含结点s的循环单链表，否则将结点s插入到末尾，再让qu->rear指向它，并且将qu->length增加1。对应的算法如下：voidpush(QNode*&qu,intx){ DNode*s; s=(DNode*)malloc(sizeof(DNode)); //建立新结点s存放x s->data=x; if(qu->length==0) { s->next=s; //构成循环单链表 qu->rear=s; //qu->rear指向结点s } else { s->next=qu->rear->next; //链接到末尾 qu->rear->next=s; qu->rear=s; //qu->rear指向结点s } qu->length++; //长度增加1}（6）top(qu)用于返回队列qu中队头元素，当队空时返回-1。对应的算法如下：inttop(QNode*qu){ if(qu->length==0) return-1; else returnqu->rear->next->data;}（7）pop(qu)用于删除队列qu中的队头元素。当队列只有一个结点时删除该结点并且置qu->rear为NULL，否则删除该结点，并且将qu->length减少1。对应的算法如下：voidpop(QNode*&qu){ DNode*p; if(qu->length==0) //空队时直接返回 return; if(qu->length==1) //队列只有一个结点时 { free(qu->rear); qu->rear=NULL; } else //队列有2个或以上结点时 { p=qu->rear->next; qu->rear->next=p->next; free(p); } qu->length--; //长度减少1}3.实验程序结构和主函数本实验程序的结构如图3所示，通过主函数调用各个基本运算函数。initquinitqumaindestroyquemptygetlengthpushtoppop图3实验程序结构主函数如下：intmain(){ QNode*qu; initqu(qu); intx,no=1; printf("队列操作\n"); printf("(%2d)qu空否:%s\n",no++,(empty(qu)?"是":"否")); for(inti=1;i<=5;i++) { printf("(%2d)进队元素%d\n",no++,i); push(qu,i); } printf("(%2d)qu空否:%s\n",no++,(empty(qu)?"是":"否")); printf("(%