数据构造教案C语言版.docx

《数据构造教案C语言版.docx》由会员分享，可在线阅读，更多相关《数据构造教案C语言版.docx（22页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据构造教案C语言版数据构造教案C语言版LastupdatedontheafternoonofJanuary3,2021课程教案课程名称：数据构造授课老师：学习对象：任课时间：一、学生情况分析数据构造是计算机专业的一门核心专业课程。学生在前期的学习中已经学习了C语言程序设计课程。通过本课程学习使学生对提高编写程序的能力以及解决实际问题的能力。二、课程教学目的（数据构造）是计算机学科中一门核心专业基础课。主要介绍怎样合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。通过本课程的学习，使学生深透地理解数据构造的逻辑构造和物理构造的基本概念以及有关算法，培养基本的、良好的程

2、序设计技能，编制高效可靠的程序，为学习操作系统、编译原理和数据库等课程奠定基础。三、课程教学内容第一章绪论教学内容：1什么是数据构造2抽象数据类型概念；数据类型；数据抽象与抽象数据类型；用于描绘数据构造的语言3数据构造的抽象层次4算法定义5性能分析与度量；算法的性能标准；算法的后期测试；算法的事前估计；空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法；教学要求：了解：数据构造基本概念及数据构造的抽象层次了解：抽象数据类型概念了解：算法的定义及算法特性把握：算法的性能分析与度量方法第二章线性表教学内容：1线性表的定义和特点2线性表的顺序存储及查找、插入和删除操作3线性表的链式存储及查找、插

3、入和删除操作4使用线性表的实例教学要求：了解：线性表的定义和特点熟练把握：线性表的顺序存储构造的查找、插入和删除等基本操作熟练把握：单链表、循环链表及双向链表的定义及实现把握：熟练把握单链表的应用方法第三章栈和队列教学内容：1栈：栈的抽象数据类型；栈的顺序存储表示；栈的链式存储表示2队列：队列的抽象数据类型；队列的顺序存储表示；队列的链式存储表示3队列的应用举例教学要求：熟练把握：栈的定义及实现熟练把握：队列的定义及实现把握：能运用栈和队列解决简单实际问题第四章串教学:内容：1)字符串的抽象数据类型2)字符串操作的实现3)字符串的形式匹配教学要求：熟练把握：字符串的定义方式熟练把握：字符串的各

4、种操作的实现了解：字符串的形式匹配算法第五章数组和广义表教学:内容：1)数组的定义和初始化2)作为抽象数据类型的数组的顺序存储方式教学要求：了解：作为抽象数据类型的数组的定义熟练把握：顺序表的数组定义方式及实现第六章树和二叉树教学内容：1)树和森林的概念：树的定义；树的术语；树的抽象数据类型；森林的概念2)二叉树：二叉树的定义；二叉树的性质；二叉树的抽象数据类型3)二叉树的表示：数组表示；链表存储表示4)二叉树的遍历：中序遍历；前序遍历；后序遍历；应用二叉树遍历的实例；二叉树的中序非递归算法5)线索化二叉树：线索；中序线索化二叉树；前序与后序的线索化6)树与森林：树的存储表示；森林与二叉树的转

5、换；树的遍历；森林的遍历7)二叉树的计数8)霍夫曼树：途径长度；霍夫曼树；霍夫曼树编码教学要求：了解：树和森林的概念把握：二叉树的概念、性质及二叉树的表示熟练把握：二叉树的遍历方法把握：线索化二叉树的特性及寻找某结点的前驱和后继的方法把握：树和森林的实现及遍历方法把握：二叉树的计数方法及从二叉树遍历结果得到二叉树的方法把握：霍夫曼树的实现方法及霍夫曼编码的概念第七章图教学内容：1图的基本概念：图的基本概念；图的抽象数据类型2图的存储表示：邻接矩阵；邻接表；邻接多重表3图的遍历与连通性；深度优先搜索；广度优先搜索；连通分量4最小生成树：克鲁斯卡尔算法；普里姆算法教学要求：把握：图的基本概念和图的

6、存储表示熟练把握：图的两种遍历方法与求解连通性问题的方法把握：构造最小生成树的Prim和Kruskal方法第九章查找教学内容：1)静态查找表：顺序表的查找；有序表的查找；索引顺序表的查找2)二叉排序树：二叉排序树上的搜索、插入和删除教学要求：熟练把握：静态搜索表的顺序搜索和折半搜索方法熟练把握：二叉搜索树的表示、搜索、插入、删除算法及其性能分析方法第十章内部排序教学内容：1)概述2)插入排序：直接插入排序；对分插入排序；链表插入排序；希尔排序3)选择排序：直接选择排序；堆排序教学要求：把握：排序的基本概念和性能分析方法把握：插入排序、选择排序、等内排序的方法及性能分析方法单元名称：第一讲：绪论

7、一、教学目的1.了解（数据构造）课程的体系构造2.把握本章介绍的各种基本概念和术语3.了解数据构造的二元组表示4.把握逻辑构造与物理构造之间的映像关系。二、重点与难点重点：数据构造的基本概念；逻辑构造与物理构造之间的映像关系。难点：逻辑构造与物理构造之间的映像关系。三、教学内容与教学经过介绍本学期课程的内容及安排本课程是计算机专业的重要专业课之一，主要介绍常用的数据构造以及相关算法。本课程主要讲授线性表、栈和队列、串、数组、树和二叉树、图、查找、排序等内容。成绩考核方式为：期末成绩+平常成绩，其中期末成绩占70%，平常成绩占30%，平常成绩为：作业成绩+出勤率+上机成绩。讲授新课1.1什么是数

8、据构造讲解：数据构造课程的研究背景从计算机最初以数值计算为主到大量非数值计算出现引出数据构造。讲解：数据构造课程的研究对象例1-1图书馆的书目检索系统自动化问题。1-2计算机和人机对奕问题1-3多叉路口交通灯的管理问题总结：从以上三个例子能够看出，描绘这类非数值计算问题的数学模型不再是数学方程，而是诸如线性表、树和图等之类的数据构造，这些都是数据构造课程的研究对象。因而，简单地讲，数据构造是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。介绍数据构造课程的发展以及与其他课程之间的关系。基本概念和术语基本概念：数据、数据元素、数据项、数据对象、数据构造、构造

9、1常见基本构造逻辑构造：集合、线性构造、树形构造、图状构造或网状构造数据构造的形式定义：数据构造一般用一个二元组来表示：Data_Structure=(D,S)其中：D是数据元素的有限集，S是D上的关系的有限集DS表示一种数据构造，它由数据元素集合K和在K上定义的一种二元关系的集合R所组成。其中：n=nKKi0,0|i是数据元素的有限集合，n为DS中数据元素的个数。=mjRRm0,0|j是K上关系的有限集合，m为K上关系的个数，通常情况下m的取值为1。K上任何一个二元关系Rj是序偶的集合。对于Rj中的任一序偶x，yK，称x为第一个元素或y的前驱，y为第二个元素或x的后继。数据构造中的数据元素和

10、数据元素之间的关系还能够用图形直观地表示出来。图形中的每个结点对应一个数据元素，两结点之间带箭头的连线对应二元关系中的一个序偶，其中序偶的第一个元素称为弧尾，第二个元素称为弧头。举例讲解：例数据构造line=K，R，其中K=01，02，03，04，05，06，07，08，09，10，R=r，r=，,，。例数据构造tree=K，R，其中K=01，02，03，04，05，06，07，08，09，10，R=r，r=，。例数据构造graph=K，R，其中K=01，02，03，04，05，R=r，r=，。介绍常见数据构造集合、线性构造、树型构造、图型构造详细表示方式(2)逻辑构造上述数据构造的定义是对操

11、作对象的一种数学描绘，是从操作对象抽象出来的数学模型。构造定义中的“关系描绘的是数据元素之间的逻辑关系，因而又称为数据的逻辑构造。根据这种逻辑关系通常将数据构造划分为线性构造和非线性构造，其中非线性构造又分为树型构造和图型构造。(3)物理构造数据构造在计算机中的表示存储映象称为数据的物理构造或存储构造，它涉及到数据元素及其互相关系在计算机内部的表示形式。数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像。根据数据元素互相之间的关系在计算机中的表示形式将数据的物理构造划分为顺序构造和链式构造。顺序映像的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。非顺序映像

12、的特点是借助指示元素存储地址的指针表示数据元素之间的逻辑关系。注意：数据的逻辑构造和物理构造是密切相关的两个方面，任何一个算法的设计取决于选定的数据的逻辑构造，而算法的实现依靠于采用的存储构造。4数据构造一般包括三方面内容：数据的逻辑构造、数据的存储构造、数据的运算举例讲解小结：总结本讲的主要内容四、作业布置见习题集单元名称：第二讲：线性表的类型定义，线性表的顺序存储一、教学目的把握线性表的顺序表示和实现二、重点与难点线性表的顺序表示和实现。三、教学经过的详细安排讲授新课线性表的类型定义线性表的定义：一个线性表是n个数据元素的有限序列。其中每个数据元素的详细含义，在不同的情况下各不一样，但是同

13、一线性表中的元素必定具有一样特性，即属于同一数据对象。例如：26个英文字母表；学生健康情况登记表图等。例如线性表a1,ai-1,ai,ai+1,an，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继。引导学生本人总结线性构造的特点。线性表的长度：线性表中元素的个数n0，n=0为空表。线性表中数据元素的位序如数据元素ai在线性表中的位序为i。抽象数据类型线性表的定义：讲解定义中的数据对象，数据关系以及基本操作教材P19，重点讲解常用的基本操作含义。通过示例2-1，2-2讲解更复杂的基本操作，并分析时间复杂度。线性表的顺序表示和实现1线性表的顺序表示：用一组地址连续的存储单元依次存储线性表

14、的数据元素。2顺序储存的地址关系：假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间知足下列关系：LOC(ai+1)=LOC(ai)+l线性表的第i个数据元素ai的存储位置为：LOC(ai)=LOC(a1)+(i-1)*l，其中LOC(a1)为线性表的基地址。3顺序表及其特点,顺序储存构造是一种随机存取的存储构造。4线性表的动态分配顺序存储构造。#defineLIST_INIT_SIZE100#defineLISTINCREMENT10Typedefs

15、tructElemType*elem;intlength;intlistsize;SqList;(1)基于顺序存储构造的基本操作的实现主要介绍下面的基本操作并且分析时间复杂度。InitList_Sq(SqListListInsert_Sq(SqList&L,inti,ElemTypee);ListDelete_Sq(SqList&L,inti,ElemTypeLocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType);MergeList_Sq(SqListLa,SqListLb,SqList重点讲解：顺序存储构造上实现

16、线性表的插入操作设线性表()niiiaaaaaaA,1121+-=，为了保证线性表的有序性，当在位置i()11+ni之前插入一个新的数据元素x时，需要将第i个到第n个数据元素均向后移动一个位置，然后将数据元素x存储到第i个位置上并改变线性表的长度。StatusListInsert_Sq(SqList&L,inti,ElemTypee)(2/)1/()210()(nOnnnnf=+=()niiiaaaaaaA,1121+-=)1(nii()(2/1/)1(210()(nOnnnnf=-=-+=2.3.1线性表的单链表存储构造的C语言描绘：typedefstrucLNode()nPxiP()mQx

17、()()()nnmRxPxQx=+nm3.1.1.,n,n0数据关系：R1|ai-1,aiD,i=2,.,n约定an端为栈顶，a1端为栈底。基本操作：InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(S)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)ADTStack3.1.2栈的表示和实现顺序栈类似于线性表的顺序映象实现，指向表尾的指针能够作为栈顶指针。栈的顺序存储表示：#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;typedefstructSElemType*base;SElemType*top;intstacksize;SqStack;顺序栈的基本操作的算法描绘：初始化，返回栈顶元素，入栈，出栈。(a)栈空栈满条件栈空条件：top=base栈满条件：base-top=stacksize(b)入栈操作StatusPush(SqStack&S,SElemTypee)if)exit(OVERFLOW);=+;+=STACKINCREMENT;*+=e;returnOK;(c)出栈操作StatusPop(SqStack&S,SElemType&e)if=returnERROR;e=*;