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

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补齐。