数据结构教案.ppt
《数据结构教案.ppt》由会员分享,可在线阅读,更多相关《数据结构教案.ppt(367页珍藏版)》请在三一文库上搜索。
1、第0章 绪 论 教学目的:1.掌握数据结构的基本概念; 2.掌握抽象数据类型的概念和软件构造方法 3.了解算法的含义,掌握算法时间复杂度的计算 教学重点:1.数据结构的概念 2.抽象数据结构的软件构造方法 3.时间复杂度的计算 教学难点:算法和算法的时间复杂度 作 业:1-1 1-3 1-11(前三道小题),一. 基本概念 数据:人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所作的抽象描述 *数据元素:表示一个事物的一组数据称为一个数据元素 *数据项:构成数据元素的数据称为该数据元素的数据项 抽象数据元素:没有实际含义的数据元素 抽象数据类型:没有确切定义的数据类型叫抽象
2、数据类型,用符号DataType来表示 数据的逻辑结构:即为数据元素之间的相互联系方式可分为线性结构、树结构和图结构,1.1 数据结构的基本概念,二 本门课程的主要内容,数据的存储结构:数据元素在计算机中的存储方式它的基本形式有两种:顺序存储结构,链式存储结构 数据的操作:对一种数据类型的数据进行的某种处理 数据的操作集合:对一种数据类型的数据所有的操作 数据结构课程主要讨论表、堆栈、队列、串、数组、树、二叉树、图等典型的常用数据结构在讨论这些结构时,主要从它们的逻辑结构、存储结构和数据操作三个方面进行分析讨论,三. . 数据元素 数据项举例 假设要描述学生的信息,看表1-1学生信息表,表中除
3、第一行标题行外,其他每一行为一个数据元素,每一列为一个数据项,三举 倒,关于数据元素、数据项的描述都可以使用某种高级程序设计语言来描述,本书采用C语言描述如上表学生信息可定义为如下结构体: typedef struct student char number8; char name10; char sex3; int age; student type,用C语言描述,有了上面的定义后,studenttype 就可看做与struct student 含义相同的标识符 1线性结构 树结构 图结构,结构与标识符,由图可见,线性结构除第一个和最后一个数据元素外,每个数据元素只有一个前驱数据元素和一个后
4、继数据元素而树结构是除根结点外每个元素只有一个前驱元素,可有零个或若干个后继元素图每个元素可有零或多个前驱或后继元素,1. 把数据元素存储在一块连续地址空间的内存中,其特点是逻辑上相邻的数据元素在物理上也相邻,数据间的逻辑关系表现在数据元素的存储位置上如下图所示:,2。 顺序存储结构,0 1 2 -2 -1,使用指针把相互直接关联的结点链接起来,其特点是逻辑上相邻的数据元素在物理上不一定相邻,数据间的逻辑关系表现在结点的链接关系上如下图示,3。链式存储结构,数据类型: 指一个类型和定义在这个类型上的操作集合. 例如,当说计算机中的整数数据类型时,就不仅指计算机所能表示的整数数值的集合,而且指能
5、对这个整数类型进行的+、-、*、和求模()操作 抽象数据类型(Abstract Data Type缩写为ADT):是指一个逻辑概念上的类型和这个类型上的操作集合 数据类型和抽象数据类型的不同之处在于:数据类型指的是高级程序设计语言支持的基本数据类型,而抽象数据类型指的是在基本数据类型支持下用户新设计的数据类型像表、堆栈、队列、串、数组、树、图等就是一个个不同的抽象数据类型,12 抽象数据类型和软件构造方法,13。算法和算法的时间复杂度(1),1.3.1 算法 算法是描述求解问题方法的操作步骤的集合它主要有三种形式:文字形式伪码形式和程序设计语言形式 例1-1 设计一个把存储在数组A中的个抽象数
6、据元素0,1,-1逆置的算法,即要求逆置后的数组中数据元素序列为,1,0,并要求原数组中的数据元素值不能被改变 设计:这是一个算法设计问题该算法要求有一个表示元素个数的输入参数,一个表示原数组的输入参数和一个表示逆置后数组的输出参数, 算法设计如下: void Reverse( int n , DataType a , DataType b ) int i ; for ( i=0 ; in ; i+ ) bi= a n-1- i ; ,算法的时间复杂度(2),该算法的实现方法如图1-3所示,图1-3 例1-1算法实现方法图示,该算法的实现方法,设计一个把存储在数组A中的个抽象数据元素0,1,-
7、1就地逆置的算法,即要求逆置后数组中数据元素序列为,1,0,并要求原数组中的数据元素值被改变 设计:这是另一个算法设计问题该算法要求有一个表示元素个数的输入参数,一个表示原数组的输入参数和一个表示逆置后数组的输出参数由于要求原数组中的数据元素这被改变,所以输出参数必须与输入参数相同,因此,这两个参数应设计为同一个参数,其参数类型设计为输入输出混合型参数,例1-2,算法设计如下: void Reverse (int n , DataType a ) int i , m = n / 2; DataType temp ; for ( i = 0 ; i m ; i + + ) temp = a i
8、; a i = a n 1 i ; a n 1 i = temp ; 该算法的实现方法如图14所示p20,算法设计,(1) 正确性能 (2) 可读性 (3) 健壮性 (4) 高时间效率 (5) 高空间效率,13.2 算法设计目标,. (1) 事后统计方法 (2) 事前分析方法 事前分析方法主要分析算法的时间效率与算法所处理的数据个数的函数关系 定义1-1 T ( n )=O ( f ( n ) )当且仅当存在正常数c和n0对所有的n (n n0)满足T ( n ) c * f ( n ). 即:当算法的时间复杂度T ( n )与数据个数n无关系时,T ( n ) c 1,所以此时算法的时间复杂
9、度T ( n )= O ( 1 );当算法的时间复杂度T ( n )与数据个数n为线性关系时,所以此时算法的时间复杂度T ( n ) = O ( );依次类推 分析一个算法中基本语句执行次数与数据个数的函数关系,就可求出该算法的时间复杂度,13.3算法时间效率的度量,例1-3 设数组和在前边部分已赋值,求如下两个阶矩阵相乘运算算法的时间复杂度 for ( i = 0; i n ; i + + ) for ( j = 0 ; j n ; j + + ) c i j = 0 ; *基本语句1* for ( k = 0 ; k n ; k + + ) c i j = c i j + a i j b
10、k j ; /*基本语句2*/ ,举例说明,下面举例说明算法时间复杂度的分析方法:,解:设基本语句的执行次数为f( n ),有 f( n ) = c1 * n2 + c2 * n3 因T( n ) = f( n ) = c1 * n2 + c2 * n3= c * n3,其中c1,c2,c可为任意常数,所以该算法的时间复杂度为T( n ) = O( n3 ),例1-6,下边算法是在一个有个数据元素的数组中删除第个位置的数组元素,要求当删除成功时数组元素个数减1,求该算法的时间复杂度其中,数组下标为0-1 int Delete (int a ,int * n , int i) int j; f
11、( i= *n ) return 0; /*删除位置错误,失败返回*/ ifor ( j = i+1;j *n; j +) aj-1=aj; /*顺次移位填补*/ ( * n )- -; /*数组元素个数减1*/ return ; /*删除成功返回*/ ,解:此算法的时间复杂度随删除数据的位置不同而不同当删除最后一个位置的数组元素时有in1,ji+1n,故不需要移位填补二循环次数为0,当删除第一个位置的数组元素时有i0,ji+11,需移位填补n1次而循环次数为 n1此时算法的时间复杂度应是删除数据位置等概率取值情况下的平均次数 设为删除第个位置上数据元素的概率,则有,设E为删除数组元素的平均次
12、数,则有 E= 1/n 0n-1(n-1-i)= 1/n (n-1)+(n-2)+2+1+0=1*/n 1 n(n-1)/2 =( n 1)/2 因T( n ) = E ( n 1 ) / 2 c * n,其中c为常数,所以该算法的等概率平均时间复杂度为 T(n)=0(n),算法的时间复杂度隋删除数据的位置不同而不同,() (1) 各种符号均以英语单词命名,所有命名应见名知意 (2) 变量名字母均小写,若单词多于一个时,第二个单词首字母大写 (3) 自定义结构体名常量名和文件名均小写但所有单词的首字母大写可缩写 (4) 函数中的抽象数据类型参数用单字母大写,顺序表SeqList类型的参数L,1
13、.4 算法书写规定,教学目的:1.理解线性表抽象数据类型 2.掌握线性表的顺序表示和实现 3.掌握线性表的链式表示和实 4.掌握静态链表的概念 5.掌握顺序表和单链表的算法设计 教学重点:1.概念的理解 2.线性表的操作 3.算法设计方法 教学难点:线性表的概念,顺序表和链表的操作 作 业:2-11 2-12,第二章 线性表,2.1.1 线性表的定义 线性表是一种可以在任意位置进行插入和删除数据元素操作的由n (n0)个相同类型数据元素a0,a1,a2,an-1组成的线性结构 顺序存储结构存储数据元素具体是用数组存储,数据元素编号从0开始,2。1 。1 线性表抽象数据类别,. 线性表的抽象数据
14、类型主要包括两个方面,即数据集合和该数据集合上的操作集合 数据集合: 线线性表的数据集合可以表示为a0,a1,a2,an-1或a1,a2,an,每个数据据元素的数据类型为抽象数据元素类型DataType ,2.1.2 线性表抽象数据类型,操作集合.,(1)初始化 ListInitiate( L ):初始化线性表 L. (2)求当前数据元素个数(ListLength( L ):函数返回线性表L的当前数据元素个数 (3) 插入数据元素ListInsert( L, i, x ):在线性表L的第i个数据前插入数据元素x (4) 删除数据元素ListDelete( L, i, x ):删除线性表L的第i
15、个数据元素,所删除的数据元素x由输出参数带回 (5) 取数据元素ListGet ( L, i, x ):取线性表L的第i个数据元素,所取的数据元素x由输出参数带回,2。2线性的顺序表示和实现,线性表的抽象数据类型有两种存储结构:顺序存储结构;链式存储结构 顺序存储结构的线性表称作顺序表 2.2.1 顺序表的存储结构 数组有静态数组和动态数组两种静态数组存储空间的申请和释放由系统自动完成,动态数组存储空间的申请和释放由用户通过调用系统函数完成顺序表一般采用静态数组方法实现数据元素的存储,顺序表的存储结构示意图如下: List 0 1 2 3 4 5 6 MaxSize-1 size=5 为用C语
16、言描述上图所示的顺序表,定义结构体 SeqList如下: typedef struct DataType list MaxSize ; int size ; SeqList;,顺序表的存储结构示意图,(1) 初始化ListInitiate(SeqList * L ) void ListInitiate(SeqList * L) /*初始化顺序表L*/ L-size = 0 ; /*定义初始数据元素个数*/ (2) 求当前数据元素个数(ListLength( L ) int ListLength ( SeqList L ) /*返回顺序表L的当前数据元素个数*/ return L . size;
17、 ,2.2.2顺序表操作的实现,(3) 插入数据元素ListInsert( L, i, x ) int ListInsert( SeqList * L, int i, DataType x ) /*在顺序表L的第i(0i size)个位置前插入数据元素 x */ /*插入成功返回1,插入失败返回0*/ int j ; if ( L- size=MaxSize ) printf (“顺序表已满无法插入!n”); return 0; else if ( iL-size ) ,2。2。2顺序表操作实现(2),插入数据元素(一),printf (“参数i 不合法!n”) ; return 0; ret
18、urn 0; else /*为插入做准备*/ for ( j = L-size ; ji ; j-) L-list j =L-list j-1 ; L - list i = x ; /*插入x */,L - size +; /*元素个数加1*/ return 1; 插入步骤:首先把存储单元size-1至存储单元i中的数据元素依次后移一个存储单元,然后把数据元素x插入到存储单元i中(注意此操作是前插),最后把数据元素个数加1其过程如下图: list 0 1 2 3 4 5 6 7 MaxSIZE-1,插入数据元素(二),list 0 1 2 3 4 5 6 7 MaxSize-1,(1) (in
19、tint ListDelete ( SeqList * L , int i ,DataType *x ) / /*删除顺序表L中位置为i(0i size -1)的数据元素并存放到x中*/ /* /*删除成功返回1,删除失败返回0*/ ) int j ; if ( L- size=0 ) printf (“顺序表已空无法删除!n”); return 0; ,(4) 删除数据元素取数据元素ListDelete( L, i, x),else if ( iL-size ) printf (“参数i 不合法!n”) ; return 0; Else * x = L - list i ; /*保存删除的元
20、素到x中*/ /*依次前移*/ for ( j = i+1 ; j size-1 ; j + ) L-list j-1 = L- list j ; L - size -; /*数据元素个数减1*/ return 1; ) ),删除和取数据元素(二),(5) 取数据元素ListGet ( L, i, x ) int ListGet ( SeqList L , int i , DataType * x ) /*取顺序表L中第i个数据元素存于x中成功返回1失败返回0*/ if ( i L . size -1 ) printf (“参数i不合法n”); return 0; else x = L . l
21、ist i ; return 1 ) ) ;,(5)取数据元素,顺序表上的插入和删除是顺序表中时间复杂度最高的成员函数在顺序表中插入一个数据元素时,最坏情况是pos0,需移动size个数据元素;最好情况是possize,需移动0个数据元素设pi是在第i个存储位置上插入一个数据元素的概率,设顺序表中的数据元素个数为n,当在顺序表的任何位置上插入数据元素的概率相等时,有pi1/(n+1),则向顺序表插入一个数据元素需移动的数据元素的平均次数为: Eis = 0 npi(n-i) = 0n (n-i) = n/2 删除操作的时间复杂度计算见教材33 顺序表中其余操作都与数据元素个数n无关,在顺序表中
22、插入和删除一个数据元素的时间复杂度为 O(n),其余操作的时间复杂度为 O(1),2。2。3顺序表操作的分析,2。2。4顺序表应用举例,请同学们自己分析例题算法,2。3 线性表的链式表示和实现,指针:指向物理存储单元地址的变量 结点:由数据元素域和一个或若干个指针域组成的一个结构体 链表:链式存储结构的线性表 链表主要有单链表、单循环链表和双向循环链表三种,单链表是构成链表的结点只有一个指向直接后继结点的指针域 1. 单链表的表示方法 定义单链表结点的结构体如下: typedef struct Node DataType data; struct Node * next; SLNode;,2。
23、3。1单链表的存储结构(1),其中,data域用来存放数据元素, next域用来存放指向下一个结点的指针 单链表有带头结点结构和不结点结构两种指向单链表的指针称作头指针,头指针所指的不存放数据元素的第一个结点称为头结点存放第一个数据元素的结点称为第一个数据元素结点符号表示空指针,空指针是一个特殊标识,用来标识链的结束空指针在算法描述中用NULL表示 在链式存储结构中,数据元素的逻辑次序是通过链中的指针链接实现的,2。3。1(2),(1)带头单链表每个元素的存贮区分为两大部分: head p data next,带头和不带头结点单链表的比较,a0,a n-1 ,X ,上图是在带头结点单链表第一个
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 教案
链接地址:https://www.31doc.com/p-3185669.html