粤教版 (2019)3.1.1 线性表及其运算完美版ppt课件

这是一份粤教版 (2019)3.1.1 线性表及其运算完美版ppt课件，共30页。PPT课件主要包含了新知讲解，字符串的描述，字符串的存储结构，循环队列，汽车轮渡口等内容，欢迎下载使用。

线性表（Linear List）
是最简单且最常用的一种数据结构，是由若干个具有相同属性的数据元素组成的有限序列。比如，英文字母表（A，B，C，…，Z）就是一个长度为26的线性表，表中的每一个英文字母为一个数据元素。
线性表具有如下的结构特点：
1．均匀性虽然不同数据表的数据元素可以是各种各样的，但同一线性表的各数据元素必定具有相同的数据类型和长度。2．有序性各数据元素在线性表中的位置只取决于它们的序号，数据元素之间的相对位置是线性的，即存在唯一的“第一个”和“最后一个”数据元素，除了第一个和最后一个，其他元素前面均只有一个数据元素（直接前趋），后面也只有一个数据元素（直接后继）。
对于线性表，常见的基本运算有：
（1）置空表setnull(L)，这是一个过程，其结果是将线性表L置为空表。（2）求长度length(L)，这是一个函数，返回值为线性表L的长度。（3）取得表中第i个元素get(L,i)，这是一个函数，当1≤i≤length(L)时，返回第i个数据元素。（4）取直接前趋prir(L,ai)，这是一个函数，当2≤i≤length(L)时，返回ai的直接前趋ai-1。（5）取直接后继next(L,ai)，这是一个函数，当1≤i≤length(L)-1时，返回ai的直接后继ai+1。（6）根据特定值查找线性表lcate(L,x)，这是一个函数，若线性表中存在值为x的数据元素ai时，则返回i值，即ai在线性表中的序号；若存在多个值为x的数据元素ai时，则i为其序号最小的值；若不存在值为x的数据元素，则返回值零。（7）插入数据元素insert(L,x,i)，这是一个过程，是将新数据元素x插入到数据元素ai之前，因此当1≤i≤length(L)+1时有意义，运算的结果使长度为n的线性表变为长度为n+1的线性表。（8）删除操作delete(L,i)，这是一个过程，当1≤i≤length(L)时，将线性表L中第i个数据元素删除，使长度为n的线性表变为长度为n-1的线性表。
3.2　用字符串存储数据
3 . 2 . 1 　字符串及其存储
字符串（String）一般简称为串，可以将它看作一种特殊的线性表，它的每个数据元素仅由一个字符组成。与一般线性表相比，字符串有以下特点：（1）字符串的数据元素的类型限定为字符型。（2）字符串操作的对象，多数情况下是字符串整体或其中一部分，当然也可以是单个的数据元素。随着计算机技术的发展，字符串成为非数值计算问题中的主要操作对象，如信息检索、文本编辑、问答系统、音乐分析程序等。
字符串是由零个或有限个字符构成的有序序列。一般记作：s="c0c1c2…cn-1" (n≥0)其中：s为串名，用双引号引起来的字符序列称为串值；ci（0≤i≤n-1）可以是字母、数字或其他字符。下标i表示字符ci在串中的位置。双引号是串值的定界符，不是串的一部分。字符串中字符的个数n称为串的长度。长度为0的字符串称为空串，此时串中没有任何字符。注意：空格在字符串中也算一个字符；长度为1的字符串与单个字符的意义及可执行的操作是不同的。例如，字符串“20180105”，长度为8，其中字符“8”的位置是3。
为了支持字符串的处理，在高级语言中引入了串的数据类型。并且，字符串变量与其他变量（如整型、实型等）一样，可以进行各种运算，字符串运算的基本函数和过程也可以同时建立。在C++语言中，字符串被定义为结构数据类型，可以直接用string来定义字符串变量：string s;一个字符串中任意个连续的字符组成的子序列称为该串的子串，包含这个子串的字符串就称为主串。一个子串在主串中的位置是用这个子串的第一个字符在主串中的位置来表示的。例如，s1="20180105"，s2="01"，则称s2是s1的子串，子串s2在s1中的位置是1。
字符串是一种特殊的线性表。因此，字符串的存储结构也有两种：静态的顺序存储结构，动态的链式存储结构或堆存储结构。
（1）串的顺序存储结构。串的顺序存储结构与一维数组的类似，用一组地址连续的存储单元存储串值的符序列，如图3-6所示。字符串的字符依次存放在这些存储单元中。因此，串可以用数组表示。
此外，存储串的连续的存储单元一般要求先定义好最大长度，这也使得串的操作受限。两个字符串连接的结果，很可能超出这个最大长度。
（2）串的动态存储结构
用顺序存储结构来存储字符串，因为其规模在定义的时候就已定下，容易造成存储空间的浪费；同时，线性表的插入和删除操作效率很低。因此，有些时候也采用动态存储方式。动态存储方式包括链式存储结构和堆存储结构。
3 . 2 . 2 　字符串的基本操作
字符串的基本操作有赋值、连接、求串长、求子串、插入子串、删除子串、查找子串、判断两个串是否相等。目前，字符串在很多程序设计语言中被定义为结构数据类型，有关字符串的操作也被设计成系统函数，可以直接引用。
以C++语言为例，通常有以下几种基本操作：（1）字符串赋值：直接赋值s="20180105"。（2）字符串连接s1.append(s2)：把字符串s2接在s1的后面，返回连接后的新串。（3）求字符串长度s.length( )：返回字符串s中当前所含字符个数。（4）求子串操作s1.substr(ps1,len1)：从字符串s1中复制指定位置ps1开始、指定长度len1的子串。（5）插入操作s1.insert(ps,s2)：将一个子串s2插入到s1的指定位置ps，返回这个新的主串。（6）删除操作s.erase(ps,len)：删除位置ps开始的长度为len的一个子串。
（7）查找子串操作s1.find(s2)：找出主串s1中是否包含子串s2，包含则返回该子串位置，不包含则返回空值。（8）判断两个字符串是否相等s1.cmpare(s2)：比较s1、s2两个字符串是否相等，相等返回true，否则返回false。字符串相等，是指两个字符串长度相等且对应位置的元素一一相等。例如，字符串s1="693450213"，s2="693450213"，s3="693550213"，其中串s2与s1相等，s3与s1不等。顾客若要求查询编号为“693450213”的商品销量，则需将此字符串与销售记录中的商品编号逐一比较，找到该字符串第一次出现的记录。
3.3　用队列组织先进先出数据（先进先出）
队列（Queue）是一种特殊的线性表，它只允许在表的一端进行插入，在表的另一端进行删除。在队列中，可以插入的一端称为队尾，可以删除的一端称为队头。把一个数据元素插入队列中的操作叫作进队，从队列中删除一个数据元素的操作叫作出队。队列中没有元素时，称为空队列。
在日常生活中，售票窗外或服务台前，顾客按到达的先后次序排成一队。排在队头的首先得到服务，然后离队。所有顾客一律平等，严格遵守秩序，不允许插队现象。也就是说，队列中总是排在最前面的对象首先离队。因此，队列符合这个规律：先放入队列中的数据元素首先取出。故队列又被称为先进先出（FIFO：First In First Out）线性表。
3 . 3 . 2 　队列的基本操作
3 . 3 . 3 　队列的实现
1．顺序队列在队列的程序定义中，可以利用数组这种具有一定容量的顺序存储结构来存储队列元素，并用队头标志frnt指示即将出队的元素的位置，用队尾标志rear指示即将入队的元素的位置，它们的初始值在队列初始化时均为0。同时我们约定：当入队或出队时，队尾标志rear或队头标志frnt只能往后移动一位，且其最大值为队列的最大长度maxsize（数组的量），我们把这种队列称为顺序队列。假设已定义队列q，队头frnt，队尾rear，数组容量为6，其顺序队列存储方式如图3-12所示。
基于以上约定，在编程实现队列操作时，队头标志和队尾标志会有几种不同的变化，还可以利用队头标志和队尾标志来求得队列的当前长度：（1）初始化队列：frnt = rear = 0（2）入队操作：rear = rear+1（3）出队操作：frnt = frnt+1（4）队空判断：frnt == rear（5）队满判断：rear == maxsize（6）求队列长度：rear - frnt
当我们对顺序队列不断执行入队操作时，队列就有可能出现溢出现象。如已定义顺序队列q，队头frnt，队尾rear，数组容量为6，当有元素入队时，有下面两种情况：（1）真溢出。当队列中的实际元素个数达到队列最大长度maxsize时，队列满，这时做入队操作将产生空间溢出的现象，如图3-13所示。真溢出是一种出错状态，应设法避免。
为充分利用队列的存储空间，克服“假溢出”现象，可以将数组存储区想象为一个首尾相接的圆环，并称存储在其中的队列为循环队列。同时，为了区别队满和队空，我们约定：当数组中只剩下一个元素为空时，即若队尾标志继续后移一位将与队头标志重叠，就判为队满，此时不能再做入队操作。
不难发现，循环队列中的元素被删除后，其原来的空间仍然可以使用，因而循环队列能实现对空间更大限度的利用。
3.4　用栈组织后进先出数据（后进先出）
队列对应了生活中的排队现象，但还有另一种现象，如对一叠碗的取放：每次把洗净的碗放好时总是放在这叠碗的最上面，而每次取用的时候也总是取最上面的。在这种现象中，事物的进出顺序都有共同的特征，那就是后进先出。
栈（Stack）是限制只能在一端进行插入和删除的特殊线性表。栈中能进行插入和删除的一端称为栈顶（Tp），而另一固定端称为栈底（Bttm）。把一个数据元素放入栈中的操作叫作进栈或压栈（Push），从栈中取出一个数据元素的操作称为出栈或弹出Pp）。栈中没有元素时，称为空栈。
3 . 4 . 3 　顺序栈的实现
栈的存储也可采用顺序存储结构的方法来实现，采用顺序存储结构的栈称为顺序栈，是指利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时设置指针tp来动态地指示栈顶元素的当前位置。
3 . 4 . 2 　栈的基本操作
栈的常用基本操作有以下几种：（1）初始化栈：构造一个空栈，初始化栈顶标志。（2）元素入栈：若栈非满，栈顶标志上移一位，插入一个元素到栈顶标志指向的位置，该元素成为新的栈顶元素。（3）元素出栈：删除栈顶标志指向的栈顶元素，栈顶标志下移一位，若此时栈非空，则栈顶标志指向的元素成为新的栈顶元素。（4）栈空判断：判断栈是否为空。（5）栈满判断：判断栈是否为满。（6）栈的长度：求栈的元素个数。
由于栈是一个动态结构，而数组是一个静态结构，所以在顺序栈的操作过程中会有“溢出”情况的出现。当栈满时，如果再有元素入栈，将会产生“上溢（Overflw）”；当栈空时，如果再执行出栈操作，将会产生“下溢（Underflw）”。为了避免发生栈溢出情况，在进行入栈和出栈操作前应先检测栈是否已满或已空。顺序栈的程序定义如下： 其中，maxsize为栈中允许存放元素个数的最大值，tp是栈顶标志，指示存放数组的下标，不是真正的指针，当tp= -1时表示空栈，当tp= maxsize -1时表示满栈。
栈来存储数学运算表达式
日常生活中，我们所遇见的数学表达式都是类似于a+b-xy这样的中缀表达式。但在计算机中，是如何翻译这个表达式并对其求值呢？例如，x+y*(a-b)-d/e所对应的后缀表达式是xyab-*+de/。计算机运用该方法进行计算的原理在于，从左向右扫描时，当遇到操作数，则将操作数进栈；当遇到操作符时，弹出两个操作数，进行运算后，将新的结果压入栈中。循环如此，直到栈内不含操作符，弹出结果。该算法的特点在于，操作数与操作符使用同一个栈，但是要将算术表达式先转换为后缀表达式。实践：一个是存放操作数的data栈，一个是存放操作符p栈。利用事先定义好的运算符优先级，将操作符压栈或退栈。1.操作符站初始化，将#压入p栈内，从表达式中读取字符ch。2.若ch是操作数，则直接压入data栈内。3.若ch是操作符，则判断instack(p)与utstack(ch)的优先级。
假设数组q的最大下标为10，恰好是每次载渡的最大量。假设客车的队列是q1，货车的队列为q2。若q1充足，则每取4个q1元素后再取一个q2元素，直到q的长度为10。若q1不充足，则直接用q2补齐。