《2022年《数据结构》授课教案》由会员分享，可在线阅读，更多相关《2022年《数据结构》授课教案（13页珍藏版）》请在金锄头文库上搜索。
1、授课教案2021 2021 学年 1 学期开课单位：数学运算机科学学院课程名称：数据结构课程性质：专业基础课学分： 3总学时： 51理论学时： 51试验学时： 0机动学时： 0授课专业：运算机科学技术 / 地理信息系统授课年级： 2021 级/2021 级同学人数： 80/37多媒体授课时数比例： 100%主讲老师：左开中职称：副教授可编辑资料 - - - 欢迎下载数据结构授课教案周次第 1 周第 1 次章节名称第一章：绪论1.1 什么是数据结构1.2 基本概念和术语1.3 抽象数据类型的表示和实现1.4 算法与算法分析授课方式多媒体教室课堂讲授教具预备自制 PPT电子课件1. 明白学习把握数
2、据结构的意义及数据结构的基本内容.教 学2把握数据结构及数据，数据元素等相关概念.2. 把握抽象数据类型ADT 的定义，表示与实现目 的4懂得时间复杂度概念和基本的估算方法.教 学1数据结构的基本概念重 点2算法分析教 学1抽象数据类型 ADT 的定义，表示与实现难 点2算法时间复杂度及其运算授课要点1.1 什么是数据结构用 3 个引例：1. 图书书目自动检索2. 人机对奕3. 交通灯治理引出数据结构的争论内容1.2 基本概念和术语1. 数据2. 数据元素，数据项3. 数据对象，数据结构4. 四类基本规律结构：集合，线性结构，树形结构，图形结构或网状结构.5. 数据结构一般包括三方面的内容：规
3、律结构，储备结构 物理结构 和数据的运算可编辑资料 - - - 欢迎下载课堂争论与练习算法的设计取决于选定的数据规律结构,而算法的实现依靠于接受的储备结构.6. 数据的两种储备结构：次序储备结构和链式储备结构1.3 抽象数据类型的表示与实现ADT 的概念和类 C语言1.4 算法和算法分析1.4.1 算法算法的定义算法具有五个重要特性：有穷性，确定性，可行性，输入，输出1.4.2 算法设计的要求正确性,可读性,健壮性,高效率低储备1.4.3 算法效率的度量时间复杂度1.4.4 算法的储备空间需求空间复杂度1. 什么是数据结构？数据，数据对象，数据元素，数据项等术语的关系和区分？2. 数据类型和抽
4、象数据类型是如何定义的,二者有何相同和不同之处？抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？3. 依据阶由低到高的次序排列以下时间复杂度：可编辑资料 - - - 欢迎下载可编辑资料 - - - 欢迎下载O log 2 n,O n 2,2O n 31,On 2, On2 , O n 33可编辑资料 - - - 欢迎下载可编辑资料 - - - 欢迎下载O 2 n, O 1,O n., O n, O n n, O nlog 2 n可编辑资料 - - - 欢迎下载作业1. 分析并运算下面各程序段的最大语句频度和算法的时间复杂度.1） for i=0;in;i+for j=0;jn;
5、 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+可编辑资料 - - - 欢迎下载for k=0;kn;k+s=s+Bijk;sum=s; 4） i=s=0;while sni+;s+=i;/s=s+i5） i=1;while i=ni=i*2;2简答题1）在数据结构课程中,数据的规律结构,数据的储备结构及数据的运算之间存在着怎样的关系？2） 如规律结构相同但储备结构不同,这样的说法对吗？举例说明之.3） 当你为解决某一问题而挑选数据结构时,应从哪些方面考虑？就为不同的数据结构.4）
6、有实现同一功能的两个算法A1 和 A2,其中 A1 的时间复杂度为 Tl=O2 ,A2 的时间复杂度为nT2=On ,仅就时间复杂2度而言,请详细分析这两个算法哪一个好.课后记要可编辑资料 - - - 欢迎下载周次第 2 周第 1 次章节名称其次章：线性表2.1 线性表的类型定义2.2 线性表的次序表示与实现授课方式多媒体教室课堂讲授教具预备自制 PPT电子课件1.明白线性表的结构特点.教 学2.把握线性表的规律结构.目 的3把握线性表的次序储备结构及其基本运算的实现. 1懂得线性表的规律结构特性.教 学2娴熟把握线性表的次序储备结构的描述方法,以及在该储备重 点结构下的基本操作.1. 能够从
7、时间和空间复杂度的角度综合比较线性表两种储备结教 学构的不同特点及其应用场合.2. 使用本章所学的基本学问设计有效算法,解决与线性表相关难 点的应用问题.授课要点2.1线性表的类型定义1. 线性表的定义（a1, ,ai-1,ai,ai+1, an）2. 定义在规律结构上的运算表的初始化，求表长，取表中的结点，查找结点，插入结点和删除结点等.3. 抽象数据类型线性表的定义2.2 线性表的次序表示和实现1，线性表的次序表示：指的是用一组地址连续的储备单元依次储备线性表的数据元素.用物理位置来表示规律结构.LOCai+1=LOCai +l LOCai=LOCa1+i-1* l2，次序表的特点：随机存
8、取3，线性表的动态支配次序储备结构（用一维数组） #define LIST_INIT_SIZE 100#define LISTINCREAMENT 10typedef structElemType *elem;可编辑资料 - - - 欢迎下载int length; intlistsize;SqList;4， 次序表的运算次序表简洁实现拜望操作, 可随机存取元素. 但插入和删除操作主要是移动元素.初始化操作插入操作3删除操作 5，应用实例可编辑资料 - - - 欢迎下载课堂争论与练习1. 线性表的两种储备结构的优缺点？它们各自适用场合是什么？2. 线性表的次序储备结构具有三个弱点：1）在插入删除
9、操作时,需要大量移动元素. 2）由于难以估量,必需预先支配较大的空间,使得储备空间不能得到充分利用.3）表的容量难以扩充.线性表的链式储备结构是否确定都能克服上述三个弱点, 试争论.可编辑资料 - - - 欢迎下载作业1. 设计一个算法,从给定的次序表L 中删除元素值在 X 到 Y 之间的全部元素,要求以较高的效率来实现,要求算法的时间复杂度为 On .2. 设有一个次序表 L,其元素为整型数据,设计一个算法将L 中全部小于 0 的整数放在前半部分,大于等于0 的整数放在后半部分. 3设计一个高效算法,将次序表中的全部元素逆置,要求算法 的时间复杂度为 On课后记要可编辑资料 - - - 欢迎
10、下载周次第 3 周第 1 次章节名称其次章：线性表2.3 线性表的链式表示与实现2.4 一元多项式的表示及相加授课方式多媒体教室课堂讲授教具预备自制 PPT电子课件教 学1. 把握线性表的链式储备结构及其基本运算的实现.目 的1娴熟把握线性表链式储备结构的描述方法, 灵敏使用单链表，教 学双链表，循环链表,学会在相应储备结构下实现其各种基本算重 点法及相关的时间性能分析.1三种链表的插入删除算法教 学2使用本章所学的基本学问设计有效算法,解决与线性表相关难 点的应用问题.授课要点2.3线性表的链式表示和实现2.3.1 线性链表1，线性表链式储备结构的特点相关概念：结点，数据域，指针域，头结点，
11、头指针2，链式储备结构的优点：插入，删除操作是不再需要移动大量的元素,但失去了次序表的可随机存取特点.3，链表的分类：单链表，循环链表和双向链表.3，单链表： 1单链表概念：链表中的每一个结点中只包含一个指针域的称为单链表.2单链表的储备结构定义typedef struc LNodeElemTypedata; structLNode*next;LNode, *LinkList; 3单链表的操作：拜望：可编辑资料 - - - 欢迎下载算法思想：单链表是非随机存取结构.每个元素的位置信息 都包含在前驱结点的信息中,所以取得第i 个元素必需从头指针动身查找.设置一个指针变量指向第一个结点,然后, 让
12、该指针变量逐一向后指向,直到第i 个元素.插入操作：要在数据元素 a 和 b 之间插入元素 x.算法思想： 预备 a和 b 之间的相邻关系是由 a 的指针预备的.如要实现插入,生成 x 结点,然后让 a 的指针指向 x 且 x 的指针指向 b.实现三个元 a，x 和 b 的规律关系.设 p 为指向结点 a 的指针, s 为指向结点 x 的指针,就修改 s，a 的指针：snext=pnext.pnext=s.删除操作：在单链表数据元素a，b，c 三个相邻的元素中删除 b,算法思想：就是要让 a 的指针直接指向 c,使 b 从链表中脱离.即： pnext=p nextnext.单链表的合并：例：将
13、两个有序链表合并为一个有序链表.设立三个指针 pa，pb 和 pc 分别用来指向两个有序链表和合并表的当前元素.比较两个表的当前元素的大小,将小的元素 链接到合并表中,即,让合并表的当前指针指向该元素,然后, 修改指针.在归并两个链表为一个链表时,不需要另建新表的 结点空间,而只需将原先两个链表中结点之间的关系解除,重 新建立关系.2.3.2 循环链表1，循环链表：特点：表中最终一个结点的指针域指向头结点,整个链表形成一个环.循环链表可分为单链和多链的.2，循环链表的操作：和线性链表基本一样,差别仅在于循环条件判定是否为空改为是否为头指针.2.3.3 双向链表1，双向链表：特点：在双向链表的结点中有两个指针域,分别指向前驱和后继.双向链表也可以有循环链表.2，双向链表储备结构定义： typedef struct DuLNode 可编辑资料 - - - 欢迎下载课堂争论与练习ElemTypedata; struct DuL
