2022年《数据结构》授课教案.docx

《2022年《数据结构》授课教案.docx》由会员分享，可在线阅读，更多相关《2022年《数据结构》授课教案.docx（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -名师精编 优秀教案授课教案2022 2022 学年 1 学期开课单位：数学运算机科学学院课程名称：数据结构课程性质：专业基础课 学分： 3 总学时： 51 理论学时： 51 试验学时： 0 机动学时： 0 授课专业：运算机科学技术 / 地理信息系统 同学人数： 80/37 授课年级： 2022 级/2022 级 多媒体授课时数比例： 100% 细心整理归纳 精选学习资料 主讲老师：左开中职称：副教授 第 1 页,共 12 页 - - - - - - - - - - - - - - - - - - - - -

2、- - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -名师精编 优秀教案数据结构授课教案周次第 1 周第 1 次章节名称第一章：绪论1.1 什么是数据结构1.2 基本概念和术语 1.3 抽象数据类型的表示和实现 1.4 算法与算法分析授课方式 教具预备多媒体教室课堂讲授 自制 PPT电子课件 1明白学习把握数据结构的意义及数据结构的基本内容；2把握数据结构及数据、数据元素等相关概念；教学目的2把握抽象数据类型ADT 的定义、表示与实现4懂得时间复杂度概念和基本的估算方法；1数据结构的基本概念 2算法分析教学重点教学1抽象数据类型ADT 的定义、表示与

3、实现难点2算法时间复杂度及其运算 1.1 什么是数据结构 用 3 个引例：授课要点1图书书目自动检索 2人机对奕 3交通灯治理 引出数据结构的争论内容 1.2 基本概念和术语 1. 数据 2. 数据元素、数据项 3. 数据对象、数据结构 4. 四类基本规律结构：集合、线性结构、树形结构、图形 结构或网状结构；5. 数据结构一般包括三方面的内容：规律结构、储备结构 物理结构 和数据的运算细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 2 页,共 12 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - -

4、 - - - - - -名师精编 优秀教案算法的设计取决于选定的数据规律结构,而算法的实现依靠 于采纳的储备结构；6. 数据的两种储备结构：次序储备结构和链式储备结构 1.3 抽象数据类型的表示与实现 ADT 的概念和类 C语言 1.4 算法和算法分析 1.4.1 算法 算法的定义算法具有五个重要特性：有穷性、确定性、可行性、输入、输出 1.4.2 算法设计的要求 正确性,可读性,健壮性,高效率低储备 1.4.3 算法效率的度量 时间复杂度 1.4.4 算法的储备空间需求 空间复杂度课堂争论 1什么是数据结构？数据、数据对象、数据元素、数据项等术 语的关系和区分？与练习 2数据类型和抽象数据类

5、型是如何定义的,二者有何相同和不 同之处？抽象数据类型的主要特点是什么？使用抽象数据 类型的主要好处是什么？3依据阶由低到高的次序排列以下时间复杂度：作业Olog2n, On2, On2, On1, O2n, On3323O 2n, O1, On ., On, Onn, Onlog2n1分析并运算下面各程序段的最大语句频度和算法的时间复杂 度；1） for i=0;in;i+ for j=0;jn; j+ Aij=0; 2） for i=0;in;i+ for j=0; ji; j+ Aij=0; 3）s=0; for i=0;in;i+ for j=0;jn;j+ 细心整理归纳 精选学习资料

6、 - - - - - - - - - - - - - - - 第 3 页,共 12 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -名师精编 优秀教案for k=0;kn;k+ s=s+Bijk; sum=s; 4） i=s=0; while sn i+; /s=s+i s+=i; 5） i=1; while i=n 2简答题i=i*2; 1）在数据结构课程中,数据的规律结构,数据的储备结构及数据的运算之间存在着怎样的关系？2）如规律结构相同但储备结构不同,就为不同的数据结构；这样的说法对吗？举例说明之；3）当你为解

7、决某一问题而挑选数据结构时,应从哪些方面考虑？4）有实现同一功能的两个算法 A1和 A2,其中 A1 的时间复杂度为 Tl=O2 n ,A2 的时间复杂度为 T2=On 2 ,仅就时间复杂度而言,请详细分析这两个算法哪一个好；课后记要细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 4 页,共 12 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -周次名师精编优秀教案第 1 次第 2 周章节名称授课方式教具预备其次章：线性表 2.1 线性表的类型定义 2.2 线性表的次序表示

8、与实现多媒体教室课堂讲授自制 PPT电子课件1. 明白线性表的结构特点；2. 把握线性表的规律结构；3把握线性表的次序储备结构及其基本运算的实现；1懂得线性表的规律结构特性；2娴熟把握线性表的次序储备结构的描述方法,以及在该储备 结构下的基本操作；1能够从时间和空间复杂度的角度综合比较线性表两种储备结 构的不同特点及其应用场合；2使用本章所学的基本学问设计有效算法,解决与线性表相关 的应用问题；2.1 线性表的类型定义教学目的教学重点教学难点授课要点1.线性表的定义（a1, ,ai-1,ai,ai+1, an）2. 定义在规律结构上的运算表的初始化、求表长、取表中的结点、查找结点、插入结点和删

9、除结点等；3. 抽象数据类型线性表的定义2.2 线性表的次序表示和实现1、线性表的次序表示：指的是用一组地址连续的储备单元 依次储备线性表的数据元素；用物理位置来表示规律结构；LOCai+1=LOCai+l LOCai=LOCa1+i-1* l 2、次序表的特点：随机存取3、线性表的动态安排次序储备结构（用一维数组）#define LIST_INIT_SIZE 100 #define LISTINCREAMENT 10 typedef struct ElemType *elem; 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 5 页,共 12 页

10、- - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -名师精编 优秀教案int length; int listsize; SqList; 4、 次序表的运算 次序表简单实现拜访操作, 可随机存取元素； 但插入和删除 操作主要是移动元素；初始化操作 插入操作 3删除操作 5、应用实例课堂争论 与练习1线性表的两种储备结构的优缺点？它们各自适用场合是什 么？2线性表的次序储备结构具有三个弱点：1）在插入删除操作时,需要大量移动元素； 2）由于难以估量,必需预先安排较大的空间,使得储备空间不能得到充分利用；3）表的容量难以扩充；线

11、性表的链式储备结构是否肯定都能克服上述三个弱点,试争论；作业1设计一个算法,从给定的次序表L 中删除元素值在 X 到 Y 之间的全部元素,要求以较高的效率来实现,要求算法的时间复杂度为 On ；2设有一个次序表 L,其元素为整型数据,设计一个算法将 L 中全部小于 0 的整数放在前半部分,大于等于 0 的整数放在后 半部分；3设计一个高效算法,将次序表中的全部元素逆置,要求算法 的时间复杂度为 On课后记要细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 6 页,共 12 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - -

12、- - - - - - - - - - - -周次名师精编优秀教案第 1 次第 3 周章节名称授课方式教具预备其次章：线性表 2.3 线性表的链式表示与实现 2.4 一元多项式的表示及相加多媒体教室课堂讲授自制 PPT电子课件1. 把握线性表的链式储备结构及其基本运算的实现；教学目的1娴熟把握线性表链式储备结构的描述方法,敏捷使用单链表、教学双链表、循环链表,学会在相应储备结构下实现其各种基本算 法及相关的时间性能分析；1三种链表的插入删除算法 2使用本章所学的基本学问设计有效算法,解决与线性表相关 的应用问题；2.3 线性表的链式表示和实现重点教学难点授课要点2.3.1 线性链表1、线性表链

13、式储备结构的特点 相关概念：结点、数据域、指针域、头结点、头指针2、链式储备结构的优点：插入、删除操作是不再需要移动大量的元素,但失去了次序 表的可随机存取特点；3、链表的分类：单链表、循环链表和双向链表；3、单链表：1单链表概念：链表中的每一个结点中只包含一个指针域的称为单链表；2单链表的储备结构定义 typedef struc LNode ElemType data; struct LNode *next; LNode, *LinkList; 3单链表的操作：拜访：细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 7 页,共 12 页 - - -

14、- - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -名师精编 优秀教案算法思想：单链表是非随机存取结构；每个元素的位置信息都包含在前驱结点的信息中,所以取得第 i 个元素必需从头指针动身查找；设置一个指针变量指向第一个结点,然后,让该指针变量逐一向后指向,直到第 i 个元素；插入操作：要在数据元素a 和 b 之间插入元素 x；算法思想： 打算 a和 b 之间的相邻关系是由 a 的指针打算的；如要实现插入,生成 x 结点,然后让 a 的指针指向 x 且 x 的指针指向 b；实现三个元 a、x 和 b 的规律关系；设 p 为指向结点 a 的

15、指针, s 为指向结点 x 的指针,就修改 s、a 的指针：snext=pnext；pnext=s；删除操作：在单链表数据元素a、b、c 三个相邻的元素中删除 b,算法思想：就是要让a 的指针直接指向c,使 b 从链表中脱离；即： pnext=pnextnext；单链表的合并：例：将两个有序链表合并为一个有序链表；设立三个指针 pa、pb 和 pc 分别用来指向两个有序链表和合 并表的当前元素；比较两个表的当前元素的大小,将小的元素 链接到合并表中,即,让合并表的当前指针指向该元素,然后,修改指针；在归并两个链表为一个链表时,不需要另建新表的 结点空间,而只需将原先两个链表中结点之间的关系解除

16、,重 新建立关系；2.3.2 循环链表 1、循环链表：特点：表中最终一个结点的指针域指向头结点,整个链表形 成一个环；循环链表可分为单链和多链的；2、循环链表的操作：和线性链表基本一样,差别仅在于循环条件判定是否为空改 为是否为头指针；2.3.3 双向链表 1、双向链表：特点：在双向链表的结点中有两个指针域,分别指向前驱和 后继；双向链表也可以有循环链表；2、双向链表储备结构定义：typedef struct DuLNode 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 8 页,共 12 页 - - - - - - - - - 名师归纳总结 精品学

17、习资料 - - - - - - - - - - - - - - -名师精编 优秀教案ElemType data; struct DuLNode *prior; struct DuLNode *next; DuLNode, *DuLinklist; 3、双向链表的操作：双指针使得链表的双向查找更为便利、快捷；NextElem 和 PriorElem 的执行时间为 O（1）；仅需涉及一个方向的指针的操作和线性链表的操作相同；插入和删除需同时修改两个方向的指针；4、双向链表的插入操作课堂争论 与练习 作业1）pnext = q 2）pprior =qprior 3）qpriornext = p 4）

18、qprior =p 1在单链表、双链表和单循环链表中,如仅知道指针p 指向某结点,不知道头指针（指向头结点的指针）,能否将结点 *p（即 p 指向的结点）从相应的链表中删除（不答应进行结点 之间数据域的复制）？如可以,时间复杂度各是多少？1设计在一个带头结点的单链表L 中删除一个最大值结点的算法；2设一个就地算法,将一个头结点指针为La 的单链表（其数据域为整数） 分解为两个单链表La 和 Lb,使得 La 链只含有原链表中数据域大于 0 的结点,而 Lb 链中只含有原链表中数据域小于等于 0 的结点；课后记要细心整理归纳 精选学习资料 - - - - - - - - - - - - - -

19、- 第 9 页,共 12 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -周次名师精编优秀教案第 1 次第 4 周章节名称 第三章 栈和队列 3.1 栈 3.2 栈的应用举例 3.3 队列授课方式 教具预备多媒体教室课堂讲授自制 PPT电子课件1. 懂得栈和队列的操作特点；2. 把握进栈、出栈等栈的基本操作以及入队和出队等队列的基本 操作；3. 把握编写递归程序的基本方法；教学目的4. 把握栈和队列的次序和链式储备结构；5. 把握队列的次序储备循环队列；教学1熟识栈和队列的规律结构定义和特性,并在各种问题中敏捷 使用

20、；2娴熟栈和队列在两种储备结构（次序储备结构和链式储备结 构）下的实现方法；1栈在各种问题中敏捷使用,栈满和栈空的条件以及它们的描 述方法；2队列在各种问题中敏捷使用,队满和队空的条件以及它们的 描述方法；3循环队列的队空队满条件取模运算；重点教学难点授课要点第 3 章栈和队列31 栈 311 栈的定义 限定仅在表尾进行插入或删除的线性表 栈顶：表尾栈底：表头312 栈的表示和实现 1次序栈 1 类型说明：#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct 细心整理归纳 精选学习资料 - - - - - -

21、- - - - - - - - - 第 10 页,共 12 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -SElemType 名师精编优秀教案*base,*top; int stacksize; SqStack; 2 重要算法的实现：入栈操作 取栈顶元素操作 取栈顶元素与出栈不同之处在于出栈操作转变栈顶指针 top 的位置,而取栈顶元素操作不改出栈操作 判栈空操作2 链栈一个链栈可由栈顶指针top 唯独确定,当top 为 NULL时,是一个空栈；32 栈的应用 1数据转换 2递归 34 队列 341 抽象数据类型队

22、列的定义 答应在线性表的一端插入,另一端进行删除操作的线性表称为队列；342 链队列 1、单链队列 队列的链式储备结构：typedef struct QNode QElemtype data; struct QNode * next; Qnode,*QueuePtr; typedef struct QueuePtr *front,*rear; LinkQueue; 2、链队列的算法：算法一：构造一个空队列算法二：销毁一个队列 算法三：判队列是否为空：算法四：入队列 算法五：出队列细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 11 页,共 12 页

23、- - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -名师精编 优秀教案3循环队列的重要算法：算法一：构造一个空队列算法二：队列长度 int QueueLengthSqQueue Q return Q.rear-Q.front+MAXQSIZE%MAXQSIZE; 算法三、循环队列的入队列：队列满条件： Q.rear +1%MAXQSIZE = =Q.front 算法四、循环队列出队列：35 队列的应用 1银行排队 2找舞伴课堂争论 与练习1分别表达栈和队列的特点,并指出它们的共同点；2循环队列的优点是什么？如何判定它的空和满

24、？假设循环队列只设 rear 和 quelen 来分别指示队尾元素的位置和队中元素的个数,试给出判定此循环队列的队满条件,并写出相应的入队和出队算法,要求出队时需返回队头指针；3争论限制存取点的表的各种情形,并列举其应用场合；作业 1. 简述线性表和栈的区分？队列和栈这两种数据结构的相同点 和差异处？2. 如用一个大小 6 的数组来实现循环队列, 且当前 rear 和 front 的值分别为 0 和 3,当从队列中先删除一个元素,再加入两个元 的值分别为多少？素后, rear 和 front 3. 利用栈设运算法, 从键盘上输入一批整数,然后依据相反的次 序打印出来；4. 试证明,如借助栈输入 1,2, ,n 得到输出序列为 P1,P2, ,Pn（它是输入序列的一个排列） ,就在输出序列中不行能显现这样的情形： ikj ,使得 PjPkPi ；递归函数：5.试编写如的g m n , 01,2 nm0,n0g mm0,n01写出递归算法g5,2 时栈的变化过程；2写出非递归算法3依据非递归算法,画出课后记要细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 12 页,共 12 页 - - - - - - - - -