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

欢迎爰徽峥龙火省授课教案学年1学期开课单位：数学计算机科学学院课程名称：数据结构课程性质：专业基础课学分：3总学时：51理论学时：51实验学时：0机动学时：0授课专业：计算机科学技术/地理信息系统授课年级：200级学生人数：80/37多媒体授课时数比例：100%主讲教师：左开中职称：副教授数据结构授课教案周次第1周第1次草节名称

第一章：绪论

1.1什么是数据结构

1.2基本概念和术语

1.3抽象数据类型的表示和实现

1.4算法与算法分析授课方式多媒体教室课堂讲授教具准备自制PPT电子课件教学目的1.了解学习掌握数据结构的意义及数据结构的基本内容；

2.掌握数据结构及数据、数据元素等相关概念；

3.掌握抽象数据类型ADT的定义、表示与实现

4.理解时间复杂度概念和基本的估算方法。教学重点

1.数据结构的基本概念

2.算法分析教学难点

1.抽象数据类型ADT的定义、表示与实现

2.算法时间复杂度及其计算授课要点

1.1什么是数据结构用3个引例：

1.图书书目自动检索

2.人机对奕

3.交通灯管理引出数据结构的研究内容

1.2基本概念和术语

1.数据

2.数据元素、数据项

3.数据对象、数据结构

4.四类基本逻辑结构：集合、线性结构、树形结构、图形结构或网状结构。

5.数据结构一般包括二方面的内容：逻辑结构、存储结构（物理结构）和数据的运算算法的设计取决于选定的数据逻辑结构，而算法的实现依赖于采用的存储结构。

6.数据的两种存储结构：顺序存储结构和链式存储结构

1.3抽象数据类型的表示与实现ADT的概念和类C语言

1.4算法和算法分析

1.41算法算法的定义算法具有五个重要特性：有穷性、确定性、可行性、输入、输出

1.42算法设计的要求止确性，可读性，健壮性，局效率低存储

1.43算法效率的度量时间复杂度

1.44算法的存储空间需求空间复杂度课堂讨论与练习

1.2

3.什么是数据结构数据、数据对象、数据元素、数据项等术语的关系和区别数据类型和抽象数据类型是如何定义的，二者有何相同和不同之处抽象数据类型的主要特点是什么使用抽象数据类型的主要好处是什么按照阶由低到高的顺序排列卜列时间复杂度：O（log2n）,O（n2）,O，n,O.n,oR,O（n3）V3）O（2n）,O

(1),O（n!）,O（n）,O（nn）,O（nlog2n）作业

1.分析并计算卜面各程序段的最大语句频度和算法的时间复杂度。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 ）for（k=0;kn;k ）s=s B皿k；sum=s;4）i=s=0;while（sn）i ；s =i;s=s i5）i=1;while（i=n）i=i*2;6）简答题1）在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系2）若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗举例说明之。3）当你为解决某一问题而选择数据结构时，应从哪些方面考虑4）有实现同一功能的两个算法A1和A2,其中A1的时间复杂度为Tl=O（2n）,A2的时间复杂度为T2=O（n2）,仅就时间复杂度而言，请具体分析这两个算法哪一个好。课后记要周次第2周第1次草节名称

第二章：线性表

2.1线性表的类型定义

2.2线性表的顺序表示与实现授课方式多媒体教室课堂讲授教具准备自制PPT电子课件教学目的1.了解线性表的结构特点；

2.掌握线性表的逻辑结构；

3.掌握线性表的顺序存储结构及其基本运算的实现；教学重点

1.理解线性表的逻辑结构特性；2,熟练掌握线性表的顺序存储结构的描述方法，以及在该存储结构下的基本操作；教学难点

1.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的/、同特点及其应用场合；

2.使用本章所学的基本知识设计有效算法，解决与线性表相关的应用问题。授课要点

2.1线性表的类型定义

1.线性表的定义（a1,，a1,a,a 1,.

2.定义在逻辑结构上的运算表的初始化、求表长、取表中的结点、查找结点、插入结点和删除结点等。

3.抽象数据类型线性表的定义

2.2线性表的顺序表示和实现

1、线性表的顺序表示：指的是用一组地址连续的存储单元依次存储线性表的数据元素。用物理位置来表示逻辑结构。LOC（ai 1）=LOC（ai） lLOC（ai尸LOC（a1） （inet=pfnet；XXX MAQSIZE）%MAQSIZE;算法

三、循环队列的入队列：队列满条件：（XXX 1）%MAQSIZE==XXXt算法

四、循环队列出队列：

3.5队列的应用

1.银行排队

2.找舞伴课堂讨论与练习

1.分别叙述栈和队列的特点，并指出它们的共同点。

2.循环队列的优点是什么如何判断它的空和满假设循环队列只设rear和quelen来分别指示队尾元素的位置和队中元素的个数，试给出判断此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头指针。

3.讨论限制存取点的表的各种情况，并列举其应用场合。作业

1.简述线性表和栈的区别队列和栈这两种数据结构的相同点和差异处

2.若用一个大小6的数组来实现循环队列，且当前rear和front的值分别为0和3,当从队列中先删除一个元素，再加入两个元素后，rear和front的值分别为多少

3.利用栈设计算法，从键盘上输入一批整数，然后按照相反的次序打印出来。

4.试证明，若借助栈输入1,2，n得到输出序列为P1,P2,（它是输入序列的一个排列），则在输出序列中不可能出现这样的情形：ikj,使得PjPkPi。

5.试编写如的递归函数：0m=0,n之0g（m,n）0,n至0(1)写出递归算法

(2)写出非递归算法

(3)根据非递归算法，画出g（5,2）时栈的变化过程。课后记要