第三章 线性数据的组织和存储 课件 2023—2024学年粤教版（2019）高中信息技术选修1

线性数据的组织和存储 线性表（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）取直接前趋prior(L,ai)，这是一个函数，当2≤i≤length(L)时，返回ai的直接前趋ai-1。 （5）取直接后继next(L,ai)，这是一个函数，当1≤i≤length(L)-1时，返回ai的直接后继ai+1。 （6）根据特定值查找线性表locate(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）字符串操作的对象，多数情况下是字符串整体或其中一部分，当然也可以是单个的数据元素。 随着计算机技术的发展，字符串成为非数值计算问题中的主要操作对象，如信息检索、文本编辑、问答系统、音乐分析程序等。 1．字符串的描述 字符串是由零个或有限个字符构成的有序序列。一般记作： 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。 2．字符串的存储结构 字符串是一种特殊的线性表。因此，字符串的存储结构也有两种：静态的顺序存储结构，动态的链式存储结构或堆存储结构。 （1）串的顺序存储结构。 串的顺序存储结构与一维数组的类似，用一组地址连续的存储单元存储串值的符序列，如图3-6所示。字符串的字符依次存放在这些存储单元中。因此，串可以用数组表示。 此外，存储串的连续的存储单元一般要求先定义好最大长度，这也使得串的操作受限。两个字符串连接的结果，很可能超出这个最大长度。 （2）串的动态存储结构 用顺序存储结构来存储字符串，因为其规模在定义的时候就已定下，容易造成存储空间的浪费；同时，线性表的插入和删除操作效率很低。因此，有些时候也采用动态存储方式。动态存储方式包括链式存储结构和堆存储结构。 3 . 2 . 2 　字符串的基本操作 字符串的基本操作有赋值、连接、求串