自考数据结构串讲笔记课件.ppt
《自考数据结构串讲笔记课件.ppt》由会员分享,可在线阅读,更多相关《自考数据结构串讲笔记课件.ppt(210页珍藏版)》请在三一办公上搜索。
1、自考数据结构 串讲笔记自考乐园版 课程代号:02331,课程说明,串讲目的参考教材:数据结构黄刘生主编经济科学出版社,更多优质自考资料尽在百度贴吧自考乐园俱乐部()欢迎加入.欢迎交流.止不住的惊喜等着你.,课程说明,知识点:线形表、栈、队列、数组、广义表、树、图、查找和排序。,第一章绪论,基本概念与术语数据结构:是一门研究非数值计算的程序设计问题中计算机的操作对象及他们之间关系和操作等的学科。,(一)数据结构概念包括三个方面(三要素)数据之间的逻辑关系(逻辑结构)数据在计算机中的存储方式(存储结构)实现数据操作的算法(数据的运算),(二)、相关术语,1、数据:能输入计算机并能计算机程序处理的符
2、号的总称。2、数据元素:数据的基本单位。可以进一步细分为若干数据项,数据项是最小单位,不能再细分。3、数据对象:具有相同性质的数据元素的集合,是数据的一个子集。,4、(1)数据的逻辑结构:数据之间的关系。A.集合(无顺序):B.线性结构(一对一):C.树形结构(一对多):D.网状、图结构(多对多):,()数据的存储结构(物理结构)数据结构在计算机中的表示。(种)A.顺序表示借助数据在连续的存储空间中的相对位置表示元素关系。B.链式表示借助数据元素的存储地址的指针表示元素关系。,2.算法和算法分析,一、算法定义:是对特定问题求解步骤的一种描述,是指令的有限序列。特点:有穷性确定性可行性零个或多个
3、输入一个或多个输出,大O表示法大O表示同级别例:f(n)=n2,f(n)=1/2(n(n-1),f(n)=(n-1)(n+2)均表示为:O(n2)加法规则:若T1(n)=O(f1(n),T2(n)=O(f2(n)则两段程序连在一起的时间代价为:T(n)=T1(n)+T2(n)=O(max(f1(n),f2(n),例:,语句段 频度f(n)时间复杂度T(n)x=x+11O(1)for(j=1;j=3n+5;j+)3n+5O(n)x=x+1;for(i=1;i=3n;i+)3n2O(n2)for(j=1;j=n;j+)x=x+1;i=0;n+1O(n)while(x!=ai,求时间复杂度的原则,当
4、重复执行次数与输入有关时,计算平均值。平均复杂度不易求时,讨论最坏情况下的T(n)。,更多优质自考资料尽在百度贴吧自考乐园俱乐部()欢迎加入.欢迎交流.止不住的惊喜等着你.,算法时间开销随时间规模变化趋势,n,T(n),随n增大,T(n)增加快,算法坏,随问题规模n增大,T(n)趋缓,算法好,T(n)的增大趋势:O(1)O(log2n)O(n)O(nlog2n)O(n2)O(nk)O(2n)O(en),算法的存储空间需求,算法空间开销与输入形式无关时,仅考虑辅加空间开销。空间量依赖特定输入,讨论最坏情况下的空间开销。,(本章结束),1.线性表的逻辑结构,一、线性结构线性表是n个数据元素的有限序
5、列当n=0时,称线性表为空表当n0时,线性表中各元素都有确定序号线性表中各元素除第一个元素没有前驱、最后一个元素没有后继外,均具有唯一的前驱、后继元素(a1,a2,ai-1,ai,ai+1,an),无前驱,直接前驱,直接后继,无后继,第二章线性表,2.线性表的顺序存储结构,一、线性表的顺序存储在计算机内开辟一片连续空间(存储单元)依次存放表中所有元素。设线性表为A(a1,a2,ai,an),表中的一个元素占用L个存储单元,第一个元素a1的起始地址是Loc(a1),则第i个元素的起始地址为:Loc(ai)=Loc(a1)+(i-1)*L,a1,a2,ai,an,连续空间,3.线性表的链式存储结构
6、一、单链表,定义:存储空间上一个结点对应线性表上一个元素,结点分为两个字段(或两个域)。一个字段存放元素的数据值;另一个字段存放指针,指向后继元素。结点:,Data,Pointer,两个概念:,头指针:指示链表中第一个结点。头结点:在第一个结点之前附设的结点,其指针域指向链表中第一个结点。,在链表中第i个结点前插入新结点b(前插)算法分析:基本操作:查找第i-1个元素当1in 频度为:i-1当in(最坏,即i不合法)频度为:nT(n)=O(n),二、循环链表,特点尾结点的next指针指向头结点,可以设头结点和尾结点指针。优点可迅速找到头、尾结点。,a1,an,Head,Head,空表,三、双向
7、链表和双向循环链表,特点:在结点中增加一个指向前趋的指针域。优点:可迅速找到结点前趋。缺点:增加存储空间。(每个结点增加了一个指针域),双向链表,a1,a2,双向循环链表,a2,a1,2、基本操作,(1)插入:在链表的x结点前插入元素e步骤:a.在链表中查找x结点b.申请结点空间s,s-data=ec.先做s-prior=p-prior;p-prior-next=s;d.后做s-next=p;p-prior=s;,a,x,p,e,s,(本章结束),(2)删除:删除双向循环链表中的结点x步骤:a.在链表中查找x结点b.删除:p-prior-next=p-next;p-next-prior=p-p
8、rior;c.free(p),a,x,c,p,第3章栈与队列,1.栈一、栈的描述1.栈的定义2.栈的特点:后进先出(LIFO)1,2,3,4顺序进栈,有多少种出栈的情况?Sn=s0sn-1+s1Sn-2+sn-2s1+sn-1s0S0=1,s1=1,更多优质自考资料尽在百度贴吧自考乐园俱乐部()欢迎加入.欢迎交流.止不住的惊喜等着你.,例:,一个栈的输入序列为1,2,3,4,下面哪一个序列不可能是这个栈的输出序列?()A.1,3,2,4B.2,3,4,1C.4,3,1,2D.3,4,2,1,二、栈的表示和实现,1、栈的顺序存储结构顺序栈顺序栈:开辟一组地址连续的存储单元,依次存放自栈底到栈顶的
9、数据元素。设top指针指示栈顶元素的当前位置。,基本操作,栈示意图:,C,B,A,base,top,新元素入栈顶时:先入栈,再移指针top=top+1删除元素时:先移指针top=top-1,后删栈顶元素 栈的长度:top-base,2、链栈,定义:采用链式存储结构的栈,并由其栈顶指针惟一确定。设ls为栈顶指针,栈=(a1,a2,an),a1为栈底元素,an为栈顶元素。,an,a2,a1,ls,最迟入栈元,最早入栈元,2.队列,一、队列描述1、队列定义2、队列特点:先进先出(FIFO),二、队列的顺序存储表示,1、顺序队列用一组地址连续的存储单元依次存放从队头到队尾的元素。设队头指针为front
10、,队尾指针为rear。约定:当front=rear=0,表示空队列;front指向队头元素;rear指向队尾元素的下一个位置。,2、循环队列,假想:将队列的头、尾相连形成一个环,构成循环队列。并引入数学中的模运算计算队头和队尾指针。,front,rear,Maxsize-1,0,基本操作:,入队操作:Q.baseQ.rear=x;Q.rear=(Q.rear+1)%MAXQSIZE;出队操作:x=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;,问题:循环队列的队空、队满条件?,举例说明:矛盾:对空:front=rear队满:front=rear解决方法:
11、少用一个存储空间,矛盾,三、链队列,定义:用链表示的队列简称为链队列。设两个指针front、rear分别指示队头和队尾。为了链队列的操作方便,增加一个头结点,front指向头结点,rear指向队尾元素。如图所示:,a1,an,front,队头元素,队尾元素,rear,头结点,3.递归算法设计,一、递归算法设计递归过程:一个直接调用自己或通过一系列的过程调用语句间接地调用自己的过程称为递归过程。直接递归调用间接递归调用,1、递归算法的设计思想,分治思想:对一个较大问题可分解成属性相同、规模较小的问题,在小问题求解之后,通过组合,求得原来较大问题的解。递归定义:基本项:描述递归过程的终结状态,即可
12、直接求解状态。归纳项:描述如何实现从当前状态到终结状态的转化,即子问题与原问题之间的转化。,例1:求n!,用分治思想分析,得到递归定义:基本项:当n=1时,f=1。(直接求解状态)归纳项:如果能求得(n-1)!,原问题n!则迎刃而解。(n-1)!与n!问题的属性特征相同,只是规模小了。所以,归纳项是设法求(n-1)!。,2、递归算法设计,在程序设计中,什么情况下使用递归算法进行程序设计呢?考虑以下三个方面的因素:当问题的定义是递归的解决问题的数据结构是递归的解决问题的过程是递归的,(本章结束),更多优质自考资料尽在百度贴吧自考乐园俱乐部()欢迎加入.欢迎交流.止不住的惊喜等着你.,第四章串,基
13、本概念与基本运算一、串1、串定义:有零个或n个字符构成的有限序列。记为S=a1a2an(n=0);其中S是串名,a1a2.an是串值,ai(i=1)可以是字母、字符、数字,n是串长度,当n=0时为空串。,2串的存储结构,一、顺序存储结构(或称静态存储结构:编译时进行空间分配)定义:用一组地址连续的存储单元存储串的字符序列。两种编址形式:字节编址:一个字节存一个字符。(如早期的pc机)字编址:一个字存一个字符。非紧缩格式:每个字存放一个字符。紧缩格式:每个字节存放一个字符。C语言仅有紧缩格式:char strmax;,概念:存储密度存储密度=,串值所占的存储位,实际分配的存储位,顺序存储结构的特
14、点预先分配串最大长度,有可能造成存储密度低。使串的某些操作受到很大限制。如置换、联接等操作。,二、动态存储结构,(在运行时进行存储空间的分配)定义:用一组任意的存储单元(可以连续,可以不连续)存放串的字符序列。,1、链式存储结构,每个结点存放一个字符。图示:存储密度=1/(1+4)=20%(设指针占用4字节)特点:密度低,存储空间利用率低,操作简单。每个结点存放多个字符块链结构。图示:存储密度=4/(4+4)=50%(设指针占用4字节)特点:存储密度大,节省空间,操作复杂。链式结构的特点:结点的选择非常重要。,a,b,c,rear,a b c d,e f g h,i#,3串的模式匹配算法,模式
15、匹配:子串的定位操作通常称为串的模式匹配,是各种串处理系统中重要的操作之一。Index(S,T,pos)其中S为主串,T被称为模式串。若T为S子串,则返回T在S中第pos个字符后首次出现的位置。若T不为S子串,则返回0。,模式匹配:子串在主串中的定位操作(mn)。t=t0 t1 t2 tn-1 目标 p=p0 p1 p2 pm-1 模式从目标t中查找与模式p完全相同子串的过程。朴素的模式匹配。,模式匹配,t,a,b,b,b,a,a,p,图3.3朴素的模式匹配过程,a b a,a b a,a b a,a b a,1、朴素的模式匹配,模式匹配的最简单的做法是:用p中的字符依次与t中的字符比较:如果
16、t0=p0,t1=p1,tm-1=pm-1,则匹配成功,调用求子串的操作subStr(t,1,m)即是找到的子串。否则必有某个i(0im-1),使得ti pi,这时可将p右移一个字符,用p中字符从头开始与t中字符依次比较;如此反复执行,直到下面两种情况之一:或者到达某步时,ti=p0,ti+1=p1,ti+m-1=pm-1,匹配成功,subStr(t,i+1,m)即是找到的(第一个)与模式p相同的子串;或者一直将p移到无法与t继续比较为止,则匹配失败。,说明:S串下次比较位置:i-j+2jT0时说明匹配成功。匹配成功的返回值:T中第一个字符在S中的位置。,(本章结束),第五章数组和广义表,1.
17、数组定义一、数组定义(n维数组)当n=1时,称为一维数组。当n2时,称为多维数组。一个n维数组是由若干个n-1维数组构成的。,更多优质自考资料尽在百度贴吧自考乐园俱乐部()欢迎加入.欢迎交流.止不住的惊喜等着你.,举例:二维数组m*n,a11 a12 a1na21 a22 a2n.am1 am2 amn可以看成由若干个一维数组组成,这些一维数组或按行或按列向量构成,Am*n=,按列向量:,a11 a12 a1na21 a22 a2n.am1 am2 amn,Am*n=,n个一维数组,按行向量:,a11 a12 a1n a21 a22 a2n.am1 am2 amnAm*n=(a11 a12a1
18、n),(a21 a22a2n),(am1 am2 amn),Am*n=,m个一维数组,2.数组的顺序存储表示,问题:存储单元是一维的结构,而数组是多维结构,如何用一组连续存储空间存放数组的数据元素呢?解决方法:存储映射策略;行优先存储;列优先存储。,数组元素满足1=i=m,1=j=n设每个数据元素占L个存储单元,第一个元素a00存储地址是Loc(a00),问aij在空间上的存储地址是什么?,1、行优先存储,Loc(aij)=Loc(a00)+(i*n+j)*L,a00,a01,a0n-1,am-10,am-1n-1,n,L,假设:行、列的下界为0,Loc(a00),2、列优先存储,Loc(ai
19、j)=Loc(a00)+(j*m+i)*L,a00,a10,am-10,a0n-1,am-1n-1,m,L,假设:行、列的下界为0,Loc(a00),3.矩阵的存储及运算,一、一般矩阵的存储通常用二维数组存储矩阵。特点:矩阵中的每个元素占用二维数组中的相应位置。,二、特殊矩阵的存储,特殊矩阵:矩阵中相当一部分元素取值相同或都为0或元素在矩阵中分布有一定规律。特殊矩阵的存储方式:通常采用压缩存储。压缩存储:为多个值相同的矩阵元只分配一个存储空间;对0元不分配空间。,更多优质自考资料尽在百度贴吧自考乐园俱乐部()欢迎加入.欢迎交流.止不住的惊喜等着你.,1、对称矩阵,定义:对于一个n*n方阵,且a
20、ij=aji(1=i=n,1=j=n),则称为对称矩阵。特点:矩阵中元素关于对角线元素对称。存储方式:采用三角存放法。即指存储对角线及对角线以下或对角线以下的元素。对于n阶对称矩阵,仅用n(n+1)/2个存储单元。,a11 a12 a1n a21 a22 a2n.an1 an2 ann存储方式:按行优先K=1/2i(i-1)+(j-1)i=j1/2j(j-1)+(i-1)ij,An*n=,a11,a21,a22,a31,aij,an1,ann,k,2、三角矩阵,特征:n阶矩阵,对角线下(或上)的元素均为零或各元素相等于某一个常数C。存储方式:采用三角存放法。即指存储对角线及对角线以下的元素。除
21、此之外,在增加一个存储常数C的存储单元。对于n阶三角矩阵,仅用n(n+1)/2+1个存储单元。,a11 a21 a22 C.an1 an2 ann存储方式:按行优先K=1/2i(i-1)+(j-1)i=j1/2n(n+1)ij,An*n=,a11,a21,a22,a31,aij,an1,ann,k,C,3、对角线阵(对角矩阵),特征:n*n方阵,若他的全部非0元都集中在以主对角线为中心的带状区域内。存储方式:压缩存储。,三、稀疏矩阵的存储及运算,稀疏矩阵:矩阵中的许多元素为0,并且0元素的个数远远大于非0元的个数。,1、三元组表,三元组表是稀疏矩阵的压缩存储方法之一,是顺序存储结构。稀疏矩阵中
22、的一个非0元用一个三元组(i,j,value)表示;其中:i表示该非0元在矩阵中的行号;j表示该非0元在矩阵中的列号;Value表示该非0元的值。整个矩阵中每个非0元的三元组共同构成该稀疏矩阵的三元组表。,3.广义表,一、广义表定义:设广义表LS=(1,2,n),n是表长。(1)当n=0时,称广义表LS是空表;(2)当n0时,1,2,n是满足线性有序关系的,且i可以是某一数据对象元素,也可以是一个表结构。前者称为原子,后者称为子表。(在表示习惯上,广义表名称用大写字母表示,原子用小写字母表示)特点:广义表的结构是递归的。,举例:,广义表表长LS1=()n=0(空表)LS2=(a)n=1(只有原
23、子)LS3=(a,(b)n=2LS4=(a,b)n=2LS5=(a,(b,(c)n=2F=(a,F)n=2(递归表),广义表的术语:,当广义表非空时:(1)广义表的表头:表中第一个元素;(2)广义表的表尾:除了表头之外,表中其余元素构成的子表。特点:表头可以是原子或子表,而表尾一定是子表。,举例:,LS=(a,b),c)Head:(a,b)Tail:(c)LS=(a)Head:aTail:()空表LS=(),(e),(a,(b,c,d)Head:()Tail:(e),(a,(b,c,d),广义表运算:设广义表LS=(1,2,n)取广义表表头Head(LS)=1取广义表表尾Tail(LS)=(2
24、,n),二、求广义表深度,1、广义表深度定义:广义表括号重数例:LS=()深度:1LS=()深度:2LS=(a)深度:1LS=(a,(b,c)深度:2,例:求E=(A,B,C)的深度,其中:A=(),B=(e),C=(a,(b,c,d)解:Depth(E)=1+maxDepth(A),Depth(B),Depth(C)Depth(A)=1Depth(B)=1+maxDepth(e)=1Depth(C)=1+max(Depth(a),Depth(b,c,d)Depth(a)=0Depth(b,c,d)=1+maxDepth(b),Depth(C),Depth(d)=1Depth(C)=1+max
25、0,1=2 Depth(E)=1+max1,1,2=3,(本章结束),第六章树,树的定义和术语一、树的定义二、树的术语结点度、树的度、结点层次、树的深度、家族树、有序树。,更多优质自考资料尽在百度贴吧自考乐园俱乐部()欢迎加入.欢迎交流.止不住的惊喜等着你.,2二叉树,一、二叉树的相关概念1、二叉树定义树中每个结点至多有两棵子树,且子树有序。(根据二叉树的定义,二叉树的结构是递归的)2、二叉树的基本形态二叉树有五种基本形态:,二叉树的基本形态:,左子树,右子树,右子树,左子树,(1)空二叉树,(2)只有一个根结点,(3)有根结点和左子树,(4)有根结点和右子树,(5)有根结点和左,右子树,二、
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 自考 数据结构 串讲 笔记 课件
链接地址:https://www.31ppt.com/p-3732942.html