2024新粤教版(2019)《高中信息技术》选择性必修第一册第三章 线性数据的组织和存储 ppt课件(共29张PPT).pptx

上传人(卖家):QXX 文档编号:7635987 上传时间:2024-05-03 格式:PPTX 页数:29 大小:3.72MB
下载 相关 举报
2024新粤教版(2019)《高中信息技术》选择性必修第一册第三章 线性数据的组织和存储 ppt课件(共29张PPT).pptx_第1页
第1页 / 共29页
2024新粤教版(2019)《高中信息技术》选择性必修第一册第三章 线性数据的组织和存储 ppt课件(共29张PPT).pptx_第2页
第2页 / 共29页
2024新粤教版(2019)《高中信息技术》选择性必修第一册第三章 线性数据的组织和存储 ppt课件(共29张PPT).pptx_第3页
第3页 / 共29页
2024新粤教版(2019)《高中信息技术》选择性必修第一册第三章 线性数据的组织和存储 ppt课件(共29张PPT).pptx_第4页
第4页 / 共29页
2024新粤教版(2019)《高中信息技术》选择性必修第一册第三章 线性数据的组织和存储 ppt课件(共29张PPT).pptx_第5页
第5页 / 共29页
点击查看更多>>
资源描述

1、线性数据的组织和存储线性表(Linear List)是最简单且最常用的一种数据结构,是由若干个具有相同属性的数据元素组成的有限序列。比如,英文字母表(A,B,C,Z)就是一个长度为26的线性表,表中的每一个英文字母为一个数据元素。线性表具有如下的结构特点:1均匀性虽然不同数据表的数据元素可以是各种各样的,但同一线性表的各数据元素必定具有相同的数据类型和长度。2有序性各数据元素在线性表中的位置只取决于它们的序号,数据元素之间的相对位置是线性的,即存在唯一的“第一个”和“最后一个”数据元素,除了第一个和最后一个,其他元素前面均只有一个数据元素(直接前趋),后面也只有一个数据元素(直接后继)。对于线

2、性表,常见的基本运算有:(1)置空表setnull(L),这是一个过程,其结果是将线性表L置为空表。(2)求长度length(L),这是一个函数,返回值为线性表L的长度。(3)取得表中第i个元素get(L,i),这是一个函数,当1ilength(L)时,返回第i个数据元素。(4)取直接前趋prior(L,ai),这是一个函数,当2ilength(L)时,返回ai的直接前趋ai-1。(5)取直接后继next(L,ai),这是一个函数,当1ilength(L)-1时,返回ai的直接后继ai+1。(6)根据特定值查找线性表locate(L,x),这是一个函数,若线性表中存在值为x的数据元素ai时,则

3、返回i值,即ai在线性表中的序号;若存在多个值为x的数据元素ai时,则i为其序号最小的值;若不存在值为x的数据元素,则返回值零。(7)插入数据元素insert(L,x,i),这是一个过程,是将新数据元素x插入到数据元素ai之前,因此当1ilength(L)+1时有意义,运算的结果使长度为n的线性表变为长度为n+1的线性表。(8)删除操作delete(L,i),这是一个过程,当1ilength(L)时,将线性表L中第i个数据元素删除,使长度为n的线性表变为长度为n-1的线性表。3.2用字符串存储数据3.2.1 字符串及其存储字符串(String)一般简称为串,可以将它看作一种特殊的线性表,它的每

4、个数据元素仅由一个字符组成。与一般线性表相比,字符串有以下特点:(1)字符串的数据元素的类型限定为字符型。(2)字符串操作的对象,多数情况下是字符串整体或其中一部分,当然也可以是单个的数据元素。随着计算机技术的发展,字符串成为非数值计算问题中的主要操作对象,如信息检索、文本编辑、问答系统、音乐分析程序等。1字符串的描述 字符串是由零个或有限个字符构成的有序序列。一般记作:s=c0c1c2cn-1(n0)其中:s为串名,用双引号引起来的字符序列称为串值;ci(0in-1)可以是字母、数字或其他字符。下标i表示字符ci在串中的位置。双引号是串值的定界符,不是串的一部分。字符串中字符的个数n称为串的

5、长度。长度为0的字符串称为空串,此时串中没有任何字符。注意:空格在字符串中也算一个字符;长度为1的字符串与单个字符的意义及可执行的操作是不同的。例如,字符串“20180105”,长度为8,其中字符“8”的位置是3。为了支持字符串的处理,在高级语言中引入了串的数据类型。并且,字符串变量与其他变量(如整型、实型等)一样,可以进行各种运算,字符串运算的基本函数和过程也可以同时建立。在C+语言中,字符串被定义为结构数据类型,可以直接用string来定义字符串变量:string s;一个字符串中任意个连续的字符组成的子序列称为该串的子串,包含这个子串的字符串就称为主串。一个子串在主串中的位置是用这个子串

6、的第一个字符在主串中的位置来表示的。例如,s1=20180105,s2=01,则称s2是s1的子串,子串s2在s1中的位置是1。2字符串的存储结构字符串是一种特殊的线性表。因此,字符串的存储结构也有两种:静态的顺序存储结构,动态的链式存储结构或堆存储结构。(1)串的顺序存储结构。串的顺序存储结构与一维数组的类似,用一组地址连续的存储单元存储串值的符序列,如图3-6所示。字符串的字符依次存放在这些存储单元中。因此,串可以用数组表示。此外,存储串的连续的存储单元一般要求先定义好最大长度,这也使得串的操作受限。两个字符串连接的结果,很可能超出这个最大长度。(2)串的动态存储结构用顺序存储结构来存储字

7、符串,因为其规模在定义的时候就已定下,容易造成存储空间的浪费;同时,线性表的插入和删除操作效率很低。因此,有些时候也采用动态存储方式。动态存储方式包括链式存储结构和堆存储结构。3.2.2 字符串的基本操作字符串的基本操作有赋值、连接、求串长、求子串、插入子串、删除子串、查找子串、判断两个串是否相等。目前,字符串在很多程序设计语言中被定义为结构数据类型,有关字符串的操作也被设计成系统函数,可以直接引用。以C+语言为例,通常有以下几种基本操作:(1)字符串赋值:直接赋值s=20180105。(2)字符串连接s1.append(s2):把字符串s2接在s1的后面,返回连接后的新串。(3)求字符串长度

8、s.length():返回字符串s中当前所含字符个数。(4)求子串操作s1.substr(pos1,len1):从字符串s1中复制指定位置pos1开始、指定长度len1的子串。(5)插入操作s1.insert(pos,s2):将一个子串s2插入到s1的指定位置pos,返回这个新的主串。(6)删除操作s.erase(pos,len):删除位置pos开始的长度为len的一个子串。3.2.2 字符串的基本操作字符串的基本操作有赋值、连接、求串长、求子串、插入子串、删除子串、查找子串、判断两个串是否相等。目前,字符串在很多程序设计语言中被定义为结构数据类型,有关字符串的操作也被设计成系统函数,可以直接

9、引用。(7)查找子串操作s1.find(s2):找出主串s1中是否包含子串s2,包含则返回该子串位置,不包含则返回空值。(8)判断两个字符串是否相等pare(s2):比较s1、s2两个字符串是否相等,相等返回true,否则返回false。字符串相等,是指两个字符串长度相等且对应位置的元素一一相等。例如,字符串s1=693450213,s2=693450213,s3=693550213,其中串s2与s1相等,s3与s1不等。顾客若要求查询编号为“693450213”的商品销量,则需将此字符串与销售记录中的商品编号逐一比较,找到该字符串第一次出现的记录。3.3用队列组织先进先出数据(先进先出)队列

10、(Queue)是一种特殊的线性表,它只允许在表的一端进行插入,在表的另一端进行删除。在队列中,可以插入的一端称为队尾,可以删除的一端称为队头。把一个数据元素插入队列中的操作叫作进队,从队列中删除一个数据元素的操作叫作出队。队列中没有元素时,称为空队列。在日常生活中,售票窗外或服务台前,顾客按到达的先后次序排成一队。排在队头的首先得到服务,然后离队。所有顾客一律平等,严格遵守秩序,不允许插队现象。也就是说,队列中总是排在最前面的对象首先离队。因此,队列符合这个规律:先放入队列中的数据元素首先取出。故队列又被称为先进先出(FIFO:First In First Out)线性表。3.3.2 队列的基

11、本操作3.3.3 队列的实现1顺序队列在队列的程序定义中,可以利用数组这种具有一定容量的顺序存储结构来存储队列元素,并用队头标志front指示即将出队的元素的位置,用队尾标志rear指示即将入队的元素的位置,它们的初始值在队列初始化时均为0。同时我们约定:当入队或出队时,队尾标志rear或队头标志front只能往后移动一位,且其最大值为队列的最大长度maxsize(数组的量),我们把这种队列称为顺序队列。假设已定义队列q,队头front,队尾rear,数组容量为6,其顺序队列存储方式如图3-12所示。基于以上约定,在编程实现队列操作时,队头标志和队尾标志会有几种不同的变化,还可以利用队头标志和

12、队尾标志来求得队列的当前长度:(1)初始化队列:front=rear=0(2)入队操作:rear=rear+1(3)出队操作:front=front+1(4)队空判断:front=rear(5)队满判断:rear=maxsize(6)求队列长度:rear-front2循环队列当我们对顺序队列不断执行入队操作时,队列就有可能出现溢出现象。如已定义顺序队列q,队头front,队尾rear,数组容量为6,当有元素入队时,有下面两种情况:(1)真溢出。当队列中的实际元素个数达到队列最大长度maxsize时,队列满,这时做入队操作将产生空间溢出的现象,如图3-13所示。真溢出是一种出错状态,应设法避免。

13、循环队列为充分利用队列的存储空间,克服“假溢出”现象,可以将数组存储区想象为一个首尾相接的圆环,并称存储在其中的队列为循环队列。同时,为了区别队满和队空,我们约定:当数组中只剩下一个元素为空时,即若队尾标志继续后移一位将与队头标志重叠,就判为队满,此时不能再做入队操作。循环队列为充分利用队列的存储空间,克服“假溢出”现象,可以将数组存储区想象为一个首尾相接的圆环,并称存储在其中的队列为循环队列。同时,为了区别队满和队空,我们约定:当数组中只剩下一个元素为空时,即若队尾标志继续后移一位将与队头标志重叠,就判为队满,此时不能再做入队操作。不难发现,循环队列中的元素被删除后,其原来的空间仍然可以使用

14、,因而循环队列能实现对空间更大限度的利用。3.4用栈组织后进先出数据(后进先出)队列对应了生活中的排队现象,但还有另一种现象,如对一叠碗的取放:每次把洗净的碗放好时总是放在这叠碗的最上面,而每次取用的时候也总是取最上面的。在这种现象中,事物的进出顺序都有共同的特征,那就是后进先出。栈(Stack)是限制只能在一端进行插入和删除的特殊线性表。栈中能进行插入和删除的一端称为栈顶(Top),而另一固定端称为栈底(Bottom)。把一个数据元素放入栈中的操作叫作进栈或压栈(Push),从栈中取出一个数据元素的操作称为出栈或弹出Pop)。栈中没有元素时,称为空栈。3.4.3 顺序栈的实现栈的存储也可采用

15、顺序存储结构的方法来实现,采用顺序存储结构的栈称为顺序栈,是指利用一组连续的存储单元依次存放自栈底到栈顶的数据元素,同时设置指针top来动态地指示栈顶元素的当前位置。3.4.2 栈的基本操作栈的常用基本操作有以下几种:(1)初始化栈:构造一个空栈,初始化栈顶标志。(2)元素入栈:若栈非满,栈顶标志上移一位,插入一个元素到栈顶标志指向的位置,该元素成为新的栈顶元素。(3)元素出栈:删除栈顶标志指向的栈顶元素,栈顶标志下移一位,若此时栈非空,则栈顶标志指向的元素成为新的栈顶元素。(4)栈空判断:判断栈是否为空。(5)栈满判断:判断栈是否为满。(6)栈的长度:求栈的元素个数。由于栈是一个动态结构,而

16、数组是一个静态结构,所以在顺序栈的操作过程中会有“溢出”情况的出现。当栈满时,如果再有元素入栈,将会产生“上溢(Overflow)”;当栈空时,如果再执行出栈操作,将会产生“下溢(Underflow)”。为了避免发生栈溢出情况,在进行入栈和出栈操作前应先检测栈是否已满或已空。顺序栈的程序定义如下:其中,maxsize为栈中允许存放元素个数的最大值,top是栈顶标志,指示存放数组的下标,不是真正的指针,当top=-1时表示空栈,当top=maxsize-1时表示满栈。栈来存储数学运算表达式 日常生活中,我们所遇见的数学表达式都是类似于a+b-xy这样的中缀表达式。但在计算机中,是如何翻译这个表达

17、式并对其求值呢?例如,x+y*(a-b)-d/e所对应的后缀表达式是xyab-*+de/。计算机运用该方法进行计算的原理在于,从左向右扫描时,当遇到操作数,则将操作数进栈;当遇到操作符时,弹出两个操作数,进行运算后,将新的结果压入栈中。循环如此,直到栈内不含操作符,弹出结果。该算法的特点在于,操作数与操作符使用同一个栈,但是要将算术表达式先转换为后缀表达式。实践:一个是存放操作数的data栈,一个是存放操作符op栈。利用事先定义好的运算符优先级,将操作符压栈或退栈。1.操作符站初始化,将#压入op栈内,从表达式中读取字符ch。2.若ch是操作数,则直接压入data栈内。3.若ch是操作符,则判断instack(op)与outstack(ch)的优先级。汽车轮渡口 假设数组q的最大下标为10,恰好是每次载渡的最大量。假设客车的队列是q1,货车的队列为q2。若q1充足,则每取4个q1元素后再取一个q2元素,直到q的长度为10。若q1不充足,则直接用q2补齐。

展开阅读全文
相关资源
猜你喜欢
相关搜索
资源标签

当前位置:首页 > 高中 > 信息 > 粤教版(2019) > 选修1 数据与数据结构
版权提示 | 免责声明

1,本文(2024新粤教版(2019)《高中信息技术》选择性必修第一册第三章 线性数据的组织和存储 ppt课件(共29张PPT).pptx)为本站会员(QXX)主动上传,163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。
2,用户下载本文档,所消耗的文币(积分)将全额增加到上传者的账号。
3, 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(发送邮件至3464097650@qq.com或直接QQ联系客服),我们立即给予删除!


侵权处理QQ:3464097650--上传资料QQ:3464097650

【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。


163文库-Www.163Wenku.Com |网站地图|