46自考数据结构 串讲笔记

自考数据结构串讲笔记自考乐园版课程代号：02331课程说明串讲目的参考教材：《数据结构》黄刘生主编经济科学出版社更多优质自考资料尽在百度贴吧自考乐园俱乐部（）欢迎❤加入...欢迎❤交流...止不住的惊喜等着你.........课程说明知识点：线形表、栈、队列、数组、广义表、树、图、查找和排序。第一章绪论§１．基本概念与术语数据结构：是一门研究非数值计算的程序设计问题中计算机的操作对象及他们之间关系和操作等的学科。（一）数据结构概念包括三个方面（三要素）数据之间的逻辑关系（逻辑结构）数据在计算机中的存储方式（存储结构）实现数据操作的算法（数据的运算）（二）、相关术语1、数据：能输入计算机并能计算机程序处理的符号的总称。2、数据元素：数据的基本单位。可以进一步细分为若干数据项，数据项是最小单位，不能再细分。3、数据对象：具有相同性质的数据元素的集合，是数据的一个子集。4、（1）数据的逻辑结构：数据之间的关系。A.集合（无顺序）：B.线性结构（一对一）：C.树形结构（一对多）：D.网状、图结构（多对多）：（２）数据的存储结构（物理结构）数据结构在计算机中的表示。（２种）A.顺序表示借助数据在连续的存储空间中的相对位置表示元素关系。B.链式表示借助数据元素的存储地址的指针表示元素关系。§2.算法和算法分析一、算法定义：是对特定问题求解步骤的一种描述，是指令的有限序列。特点：有穷性确定性可行性零个或多个输入一个或多个输出大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!=a[i]&&i=n)i=i+1;求时间复杂度的原则当重复执行次数与输入有关时,计算平均值。平均复杂度不易求时,讨论最坏情况下的T(n)。更多优质自考资料尽在百度贴吧自考乐园俱乐部（）欢迎❤加入...欢迎❤交流...止不住的惊喜等着你.........算法时间开销随时间规模变化趋势nT(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个数据元素的有限序列当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)*La1a2…ai…an……连续空间§3.线性表的链式存储结构一、单链表定义：存储空间上一个结点对应线性表上一个元素，结点分为两个字段（或两个域）。一个字段存放元素的数据值；另一个字段存放指针，指向后继元素。结点：DataPointer两个概念：头指针：指示链表中第一个结点。头结点：在第一个结点之前附设的结点，其指针域指向链表中第一个结点。在链表中第i个结点前插入新结点b（前插）算法分析：基本操作：查找第i-1个元素当1≤i≤n频度为：i-1当in(最坏，即i不合法)频度为：nT(n)=O(n)二、循环链表特点尾结点的next指针指向头结点，可以设头结点和尾结点指针。优点可迅速找到头、尾结点。a1an…HeadHead空表三、双向链表和双向循环链表特点：在结点中增加一个指向前趋的指针域。优点：可迅速找到结点前趋。缺点：增加存储空间。（每个结点增加了一个指针域）双向链表a1a2双向循环链表a2a12、基本操作（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;axpes（本章结束）（2）删除：删除双向循环链表中的结点x步骤：a.在链表中查找x结点b.删除：p-prior-next=p-next;p-next-prior=p-prior;c.free(p)axcp第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、栈的顺序存储结构——顺序栈顺序栈：开辟一组地址连续的存储单元，依次存放自栈底到栈顶的数据元素。设top指针指示栈顶元素的当前位置。基本操作栈示意图：CBAbasetop新元素入栈顶时：先入栈,再移指针top=top+1删除元素时：先移指针top=top-1,后删栈顶元素栈的长度：top-base2、链栈定义：采用链式存储结构的栈，并由其栈顶指针惟一确定。设ls为栈顶指针，栈=(a1,a2,…,an)，a1为栈底元素，an为栈顶元素。ana2a1……ls最迟入栈元最早入栈元§2.队列一、队列描述1、队列定义2、队列特点：先进先出（FIFO）二、队列的顺序存储表示1、顺序队列用一组地址连续的存储单元依次存放从队头到队尾的元素。设队头指针为front，队尾指针为rear。约定：当front=rear=0，表示空队列；front指向队头元素；rear指向队尾元素的下一个位置。2、循环队列假想：将队列的头、尾相连形成一个环，构成循环队列。并引入数学中的模运算计算队头和队尾指针。frontrearMaxsize-10基本操作：入队操作：Q.base[Q.rear]=x;Q.rear=(Q.rear+1)%MAXQSIZE;出队操作：x=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;问题：循环队列的队空、队满条件？举例说明：矛盾：对空：front=rear队满：front=rear解决方法：少用一个存储空间矛盾三、链队列定义：用链表示的队列简称为链队列。设两个指针front、rear分别指示队头和队尾。为了链队列的操作方便，增加一个头结点，front指向头结点，rear指向队尾元素。如图所示：a1an……front队头元素队尾元素rear头结点§3.递归算法设计一、递归算法设计递归过程：一个直接调用自己或通过一系列的过程调用语句间接地调用自己的过程称为递归过程。直接递归调用间接递归调用1、递归算法的设计思想分治思想：对一个较大问题可分解成属性相同、规模较小的问题，在小问题求解之后，通过组合，求得原来较大问题的解。递归定义：基本项：描述递归过程的终结状态，即可直接求解状态。归纳项：描述如何实现从当前状态到终结状态的转化，即子问题与原问题之间的转化。例1：求n!用分治思想分析,得到递归定义:基本项：当n=1时，f=1。（直接求解状态）归纳项：如果能求得(n-1)!，原问题n!则迎刃而解。(n-1)!与n!问题的属性特征相同，只是规模小了。所以，归纳项是设法求(n-1)！。2、递归算法设计在程序设计中，什么情况下使用递归算法进行程序设计呢？考虑以下三个方面的因素：当问题的定义是递归的解决问题的数据结构是递归的解决问题的过程是递归的（本章结束）更多优质自考资料尽在百度贴吧自考乐园俱乐部（）欢迎❤加入...欢迎❤交流...止不住的惊喜等着你.........第四章串§１．基本概念与基本运算一、串1、串定义：有零个或n个字符构成的有限序列。记为S=‘a1a2…an’(n=0);其中S是串名,a1a2..an是串值，ai(i=n且i=1)可以是字母、字符、数字，n是串长度，当n=0时为空串。§2．串的存储结构一、顺序存储结构（或称静态存储结构：编译时进行空间分配）定义：用一组地址连续的存储单元存储串的字符序列。两种编址形式：字节编址：一个字节存一个字符。(如早期的pc机)字编址：一个字存一个字符。非紧缩格式：每个字存放一个字符。紧缩格式：每个字节存放一个字符。C语言仅有紧缩格式：charstr[max];概念：存储密度存储密度=串值所占的存储位实际分配的存储位顺序存储结构的特点预先分配串最大长度，有可能造成存储密度低。使串的某些操作受到很大限制。如置换、联接等操作。二、动态存储结构（在运行时进行存储空间的分配）定义：用一组任意的存储单元（可以连续，可以不连续）存放串的字符序列。1、链式存储结构每个结点存放一个字符。图示：存储密度=1/(1+4)=20%(设指针占用4字节)特点：密度低，存储空间利用率低，操作简单。每个结点存放多个字符——块链结构。图示：存储密度=4/(4+4)=50%(设指针占用4字节)特点：存储密度大，节省空间，操作复杂。链式结构的特点：结点的选择非常重要。abcrearabcdefghi###^§3．串的模式匹配算法模式匹配：子串的定位操作通常称为串的模式匹配，是各种串处理系统中重要的操作之一。Index(S,T,pos)其中S为主串，T被称为模式串。若T为S子串，则返回T在S中第pos个字符后首次出现的位置。若T不为S子串，则返回0。模式匹配：子串在主串中的定位操作(mn)。t=t0t1t2…tn-1目标p=p0p1p2…pm-1模式从目标t中查找与模式p完全相同子串的过程。朴素的模式匹配。模式匹配tabbbaap图3.3朴素的模式匹配过程abaabaabaaba1、朴素的模式匹配模式匹配的最简单的做法是：用p中的字符依次与t中的字符比较：如果t0=p0，t1=p1，…，tm-1=pm-1，则匹配成功，调用求子串的操作subStr(t,1,m)即是找到的子串。否则必有某个i（0≤i≤m-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+2jT[0]时说明匹配成功。匹配成功的返回值：T中第一个字符在S中的位置。（本章结束）第五章数组和广义表§1.数组定义一、数组定义（n维数组）当n=1时，称为一维数组。当n2时，称为多维数组。一个n维数组是由若干个n-1维数组构成的。更多优质自考资料尽在