数据结构教案教案.ppt
《数据结构教案教案.ppt》由会员分享,可在线阅读,更多相关《数据结构教案教案.ppt(367页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、 第0章 绪 论 教学目的:1.掌握数据结构的基本概念;2.掌握抽象数据类型的概念和软件构造方法3.了解算法的含义,掌握算法时间复杂度的计算教学重点:1.数据结构的概念2.抽象数据结构的软件构造方法3.时间复杂度的计算教学难点:算法和算法的时间复杂度作业:1-11-31-11(前三道小题)一.基本概念数据:人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所作的抽象描述*数据元素:表示一个事物的一组数据称为一个数据元素*数据项:构成数据元素的数据称为该数据元素的数据项抽象数据元素:没有实际含义的数据元素抽象数据类型:没有确切定义的数据类型叫抽象数据类型,用符号DataType
2、来表示数据的逻辑结构:即为数据元素之间的相互联系方式可分为线性结构、树结构和图结构1.1数据结构的基本概念二本门课程的主要内容数据的存储结构:数据元素在计算机中的存储方式它的基本形式有两种:顺序存储结构,链式存储结构数据的操作:对一种数据类型的数据进行的某种处理数据的操作集合:对一种数据类型的数据所有的操作数据结构课程主要讨论表、堆栈、队列、串、数组、树、二叉树、图等典型的常用数据结构在讨论这些结构时,主要从它们的逻辑结构、存储结构和数据操作三个方面进行分析讨论三.数据元素数据项举例 假设要描述学生的信息,看表1-1学生信息表学号姓名性别年令200001张三男20200002李四男212000
3、03王五女22表中除第一行标题行外,其他每一行为一个数据元素,每一列为一个数据项三举倒关于数据元素、数据项的描述都可以使用某种高级程序设计语言来描述,本书采用C语言描述如上表学生信息可定义为如下结构体:typedefstructstudentcharnumber8;charname10;charsex3;intage;studenttype用C语言描述n 有 了 上 面 的 定 义 后,studenttype 就 可 看 做 与 struct student 含义相同的标识符1线性结构树结构图结构ABCDABDFCEGABCDFEG结构与标识符由图可见,线性结构除第一个和最后一个数据元素外,每
4、个数据元素只有一个前驱数据元素和一个后继数据元素而树结构是除根结点外每个元素只有一个前驱元素,可有零个或若干个后继元素图每个元素可有零或多个前驱或后继元素1.把数据元素存储在一块连续地址空间的内存中,其特点是逻辑上相邻的数据元素在物理上也相邻,数据间的逻辑关系表现在数据元素的存储位置上如下图所示:a0a1a2an-2an-12。顺序存储结构0 1 2 -2 -1使用指针把相互直接关联的结点链接起来,其特点是逻辑上相邻的数据元素在物理上不一定相邻,数据间的逻辑关系表现在结点的链接关系上如下图示3。链式存储结构 数据类型:指一个类型和定义在这个类型上的操作集合.例如,当说计算机中的整数数据类型时,
5、就不仅指计算机所能表示的整数数值的集合,而且指能对这个整数类型进行的+、-、*、和求模()操作抽象数据类型(Abstract Data Type缩写为ADT):是指一个逻辑概念上的类型和这个类型上的操作集合数据类型和抽象数据类型的不同之处在于:数据类型指的是高级程序设计语言支持的基本数据类型,而抽象数据类型指的是在基本数据类型支持下用户新设计的数据类型像表、堆栈、队列、串、数组、树、图等就是一个个不同的抽象数据类型12抽象数据类型和软件构造方法13。算法和算法的时间复杂度(1)1.3.1算法算法是描述求解问题方法的操作步骤的集合它主要有三种形式:文字形式伪码形式和程序设计语言形式例1-1设计一
6、个把存储在数组A中的个抽象数据元素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所示b0+3a0b1+3.a1.bn-2an-2bn-1An-1 图1-3例1-1算法实现方法图示该算法的实现方法设计一个把存储在数组A
7、中的个抽象数据元素0,1,-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 ;a i =a n 1 i ;a n
8、1 i =temp;该算法的实现方法如图14所示p20算法设计 (1)正确性能 (2)可读性 (3)健壮性 (4)高时间效率 (5)高空间效率13.2算法设计目标.(1)事后统计方法 (2)事前分析方法 事前分析方法主要分析算法的时间效率与算法所处理的数据个数的函数关系定义1-1T(n)=O(f(n)当且仅当存在正常数c和n0对所有的n(n n0)满足T(n)c*f(n).即:当算法的时间复杂度T(n)与数据个数n无关系时,T(n)c 1,所以此时算法的时间复杂度T(n)=O(1);当算法的时间复杂度T(n)与数据个数n为线性关系时,所以此时算法的时间复杂度T(n)=O();依次类推分析一个算
9、法中基本语句执行次数与数据个数的函数关系,就可求出该算法的时间复杂度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 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)
10、=O(n3)例1-6下边算法是在一个有个数据元素的数组中删除第个位置的数组元素,要求当删除成功时数组元素个数减1,求该算法的时间复杂度其中,数组下标为0-1intDelete(inta,int*n,inti)intj;f(i=*n)return 0;/*删除位置错误,失败返回*/ifor(j=i+1;jsize=0;/*定义初始数据元素个数*/(2)求当前数据元素个数(ListLength(L)int ListLength(SeqList L)/*返回顺序表L的当前数据元素个数*/return L.size;2.2.2顺序表操作的实现 (3)插入数据元素ListInsert(L,i,x)int
11、ListInsert(SeqList*L,inti,DataTypex)/*在顺序表L的第i(0isize)个位置前插入数据元素 x*/*插入成功返回1,插入失败返回0*/intj;if(L-size=MaxSize)printf(“顺序表已满无法插入!n”);return0;else if(iL-size)2。2。2顺序表操作实现(2)插入数据元素(一)printf(“参数i 不合法!n”);return 0;return 0;else /*为插入做准备*/for(j=L-size;ji;j-)L-list j=L-list j-1;L-list i =x;/*插入x*/L-size+;/*
12、元素个数加1*/return 1;插入步骤:首先把存储单元size-1至存储单元i中的数据元素依次后移一个存储单元,然后把数据元素x插入到存储单元i中(注意此操作是前插),最后把数据元素个数加1其过程如下图:list01234567MaxSIZE-1插入数据元素(二)1011121314151610111214151613 list0123456 7 MaxSize-1(1)(intint ListDelete(SeqList*L,int i,DataType*x)/*删除顺序表L中位置为i(0isize-1)的数据元素并存放到x中*/*/*删除成功返回1,删除失败返回0*/)int j;if
13、(L-size=0)printf(“顺序表已空无法删除!n”);return 0;(4)删除数据元素取数据元素ListDelete(L,i,x)elseif(iL-size)printf(“参数i不合法!n”);return0;Else*x=L-listi;/*保存删除的元素到x中*/*依次前移*/for(j=i+1;jsize-1;j+)L-listj-1=L-listj;L-size-;/*数据元素个数减1*/return1;)删除和取数据元素(二)(5)取数据元素ListGet(L,i,x)int ListGet(SeqList L,int i,DataType*x)/*取顺序表L中第i
14、个数据元素存于x中成功返回1失败返回0*/if(i L.size-1)printf(“参数i不合法n”);return 0;else x=L.list i ;return 1);(5)取数据元素顺序表上的插入和删除是顺序表中时间复杂度最高的成员函数在顺序表中插入一个数据元素时,最坏情况是pos0,需移动size个数据元素;最好情况是possize,需移动0个数据元素设pi是在第i个存储位置上插入一个数据元素的概率,设顺序表中的数据元素个数为n,当在顺序表的任何位置上插入数据元素的概率相等时,有pi1/(n+1),则向顺序表插入一个数据元素需移动的数据元素的平均次数为:Eis=0 npi(n-i
15、)=0n(n-i)=n/2删除操作的时间复杂度计算见教材33顺序表中其余操作都与数据元素个数n无关,在顺序表中插入和删除一个数据元素的时间复杂度为 O(n),其余操作的时间复杂度为 O(1)2。2。3顺序表操作的分析2。2。4顺序表应用举例n请同学们自己分析例题算法2。3线性表的链式表示和实现n指针:指向物理存储单元地址的变量n结点:由数据元素域和一个或若干个指针域组成的一个结构体n链表:链式存储结构的线性表n链表主要有单链表、单循环链表和双向循环链表三种单链表是构成链表的结点只有一个指向直接后继结点的指针域1.单链表的表示方法定义单链表结点的结构体如下:typedef struct Node
16、 DataType data;struct Node*next;SLNode;数据域指针域datanext2。3。1单链表的存储结构(1)其中,data域用来存放数据元素,next域用来存放指向下一个结点的指针单链表有带头结点结构和不结点结构两种指向单链表的指针称作头指针,头指针所指的不存放数据元素的第一个结点称为头结点存放第一个数据元素的结点称为第一个数据元素结点符号表示空指针,空指针是一个特殊标识,用来标识链的结束空指针在算法描述中用NULL表示在链式存储结构中,数据元素的逻辑次序是通过链中的指针链接实现的2。3。1(2)(1)带头单链表每个元素的存贮区分为两大部分:head p data
17、 next带头和不带头结点单链表的比较a0 a n-1 X 上图是在带头结点单链表第一个数据元素前插入结点前的图示a0a1an-1x上图是在带头结点单链表第一个数据元素前插入结点后的图示也可参考下图:head p s带头和不带头结点单链表的比较(2)plena1ana2headq单链表插入结点P-next=q;q-next=p-next;Head p next a0a1an-1上图是删除带头结点单链表第一个数据元素结点的示意图22)不带头结点的单链表插入删除数据元素结点的示意图如下:在第一个数据元素前插入结点时,头指针head的值将改变为新插入结点的指针s,其插入过程如下:heada0a1an
18、-1x插入删除数据元素结点的示意图在第一个数据元素前插入结点时,头指针head的值将改变为新插入结点的指针s,其插入过程如下:head插入前的示意图 s head s a0上图是在不带头结点的单链表第一个数据元素前插入结点后的示意图a0a1an-1xa0a1an-1x不带头结点的单链表插入删除数据元素示意图在不带头结点的单链表其它数据元素前插入结点的示意图如下:head data next pa0ai-1aian-1Xs插入结点的示意图类似地,删除不带头结点的单链表第一个数据元素结点时,头指针head的值将改变为head-next,即指针head等于原head-next的值head data
19、next a0a1an-1删除不带头结点示意删除不带头结点的单链表其它数据元素结点时的示意图如下:head data next pa0ai-1aiai+1an-1单链表是由一个个结点链接构成的,单链表中每个结点的结构体定义如下:typedef struct Node DataType data;struct Node*next;SLNode;在带头结点的单链存储结构下,线性表抽象数据类型的操作集合中各个操作的具体实现方法如下:(1)初始化ListInitiate(SLNode*head)void ListInitiate(SLNode*head)/*初始化*/*如果有内存空间,申请头结点空间并
20、使头指针head指向头结点*/if(*head=(SLNode*)malloc(sizeof(SLNode)=NULL)exit(1)(*head)-next=NULL;int ListLength(SLNode *head)SLNode*p=head;/*指向头结点*/int size=0;/*size初始为0*/while(p-next!=NULL)/*循环计数*/p=p-next;size+;return size;(2)求当前数据元素个数ListLength(SLNode *head)求当前数据元数个数head p size=0a0a1an-1headpsize=na0a1an-1接上
21、面(1)(3)插入ListInsert(SLNode *head,int i,DataType x)int ListInsert(SLNode *head,int i,DataType x)/*在带头结点的单链表head 的第i(0isize)个结点前*/*插入一个存放数据元素x的结点插入成功时返回1,失败返回0*/SLNode *p,*q;int j;while(p-next!=NULL&j next;j+;插入存放数据元素的结点(1)if(j!=i-1)printf(“插入位置参数错!”);return 0;/*生成新结点由指针q指示*/if(q=(SLNode*)malloc(sizeo
22、f(SLNode)=NULL)exit(1)q-data=x;q-next=p-next;/*插入步骤1*/p-next=q;/*插入步骤2*/return 1;插入存放数据元素的结点(2)(4)删除取数据元素 ListDelete(SLNode *head,int i,DataType x)int ListDelete(SLNode *head,int i,DataType x)/*删除带头结点的单链表head的第i(0isize-1)个结点*/*被删除结点的数据元素域值由x带回删除成功时返回1,失败返回0*/SLNode*p,*s;int j;p=head;j=-1;删除取数据元素(1)w
23、hile(p-next!=NULL&p-next-next!=NULL&j next;j+;if(j!=i-1)printf(“删除位置参数错!”);return 0;s=p-next;/*指针指向ai结点*/*x=s-data;/*把指针所指向结点的数据元素域值赋予x*/p-next=p-next-next;/*删除*/free(s);/*释放指针所指向结点的内存空间*/return 1;删除取数据元素(2)(5)取数据元素ListGet(SLNode *head,int i,DataType x)int ListGet(SLNode *head,int i,DataType x)SLNod
24、e*p;int j;p=head;j=-1;while(p-next!=NULL&j next;j+;if(j!=i)printf(“取元素位置参数错!”);return 0;x=p-data;return 1;取数据元素(6)撤销单链表Destroy(SLNode*head)void Destroy(SLNode*head)SLNode*p,*p1;p=*head;while(p!=NULL)p1=p;p=p-next;free(p1);head=NULL;撤销单链表当在单链表的任何位置上插入数据元素的概率相等时,在单链表中插入一个数据元素时比较数据元素的平均次数为:Eis=0n pi(n-
25、i)=1/(n+1)0n(n-i)=n/2删除单链表的一个数据元素时比较数据元素的平均次数为:Edl=0n-1 qi(n-i)=1/n0n-1(n-i)=(n-1)/2单链表数据元素个数操作的时间复杂度为T(n)=O(n)单链表的主要优点是不需要预先确定数据元素的最大个数,插入和删除操作时不需要移动数据元素;主要缺点是每个结点中要有一个指针域,因此,空间单元利用效率不高此外,单链表操作的算法较复杂2。3。3单链表操作的效率分析本章结束时,再行分析2。3。4单链表应用举例循环单链表是单链表的另一种形式,其结构特点是链表中最后一个结点的指针域不再是结束标记,而是指向整个链表的第一个结点,从而使链表
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 教案
限制150内