线性数据的组织和存储
一、线性表
1.线性表的结构特点
线性表的结构特点：均匀性和有序性。
2.线性表常见的基本运算
线性表常见的基本运算包括置空（setnull（L））、求长度（length（L））、取值（get（L，i））、取前驱（prior（L，ai））、取后继（next（L，ai））、查找（Locate（L，x））、插入（insert（L，x，i））、删除（delete（L，i））。
3.线性表的应用
存储不确定个数的数据项就用线性表。
二、字符串及其存储
1.字符串
字符串的数据元素的类型限定为字符型。字符串既可以整体操作也可按单个元素操作。
2.字符串的存储结构
字符串的存储可使用顺序存储和链式存储。顺序存储通常使用字符数组来存储，链式存储就是使用一个带字符类型的数据域和一个指针域的链表来存储。
3.Python中字符串的基本操作
Python中字符串的基本操作如下：
● 字符串赋值：s1=" 20230305" ，s2=" 分类考试"
● 字符串连接：s1+s2
● 求长度：leng（s1）
● 求子串：s1［0：4］#取字符串s1的前四个字符
在Python中，字符串的插入、删除、更改等操作都不可直接在源串上进行，只能通过方法生成新串。
三、用队列组织先进先出数据
1.队列的定义
队列是一种特殊的线性表，它只允许在表的一端进行插入，在表的另一端进行删除。队列符合先进先出规律（FIFO）。
2.队列的基本操作
①初始化：rear=front=0
②元素入队：rear=rear+1
③元素出队：front=front+1
④求队列长度：rear-front
⑤判断队列：空，front=rear；满，rear=M
3.循环队列
● 初始队列：条件front=rear=0
● 入队：条件rear=（rear+1）%maxsize
● 出队：条件front=（front+1）%maxsize
● 空：条件front==rear
● 满：（rear+1）%maxsize==front
四、用栈组织后进先出数据
1.栈
栈是只能在一端进行插入和删除的特殊线性表。栈中能进行插入、删除的一端称为栈顶，而另一固定端称为栈底。把一个数据放入栈中的操作称为入栈，从栈中取出一个数据称为出栈。
2.栈的基本操作
初始化、入栈、出栈、判断是否为空、判断是否满、求长度。
随堂练习
一、单项选择题
1.线性表是（ ）。
A.一个有限序列，可以为空 B.一个有限序列，不可以为空
C.一个无限序列，可以为空 D.一个无限序列，不可以为空
2.顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ ）。
A.110 B.108 C.100 D.120
3.两个字符串相等的条件是（ ）。
A.串的长度相等
B.含有相同的字符集
C.都是非空串
D.两个串的长度相等且对应位置的字符相同
4.定义了一个字符串s="hello world！"，执行print（s［2：-2］）命令后，结果是（ ）。
A.ello worl B.llo worl C.llo world D.ello world
5.下列描述不准确的是（ ）。
A.队列中没有元素时，称为零队列
B.队列只允许在表的一端进行插入，在表的另一端进行删除
C.在队列中，可以插入的一端称为队尾，可以删除的一端称为队头
D.把一个数据元素插入队列中的操作叫作进队，从队列中删除一个数据元素的操作叫作出队
6.已知队列（6，5，4，1，2，3），第一个进入队列的元素是6，请问第3个出队列的元素是（ ）。
A.2 B.3 C.4 D.5
7.已知循环队列的存储空间为数组A［11］，且头指针和尾指针分别为8和3，则该队列的当前长度为（ ）。
A.8 B.6 C.7 D.5
8.在一个长度为n的线性表中，在第i个元素（1≤i≤n+1）之前插入一个新的数据元素，需要向后移动元素的个数是（ ）。
A.n-i B.n-i+1 C.n-i-1 D.i
9.下列不是线性结构的是（ ）。
A.树 B.数组 C.队列 D.栈
10.幼儿园小朋友们排队玩滑滑梯，轮流爬上去，再轮流滑下来，此过程用哪种数据结构描述最合适？（ ）
A.链表 B.字典 C.栈 D.队列
11.下列选项中，采取“后进先出”的线性数据组织和存储的是（ ）。
A.队列 B.数组 C.字符串 D.栈
12.依次在初始为空的队列中插入元素a、b、c、d以后，紧接着做了两次删除操作，此时的队首元素是（ ）。
A.a B.b C.c D.d
13.一个栈的入栈序列是1、2、3、4、5，其出栈序列为s1、s2、s3、s4、s5。若s2是3，则s1不可能是（ ）。
A.1 B.2 C.4 D.5
14.设某个栈的输入序列为A、B、C、D，则借助这个栈所得到的输出序列不可能是（ ）。
A.A、B、C、D B.D、C、B、A C.A、C、D、B D.D、A、B、C
15.设有编号为1、2、3、4的四辆列车，顺序进入一个栈结构的站台，下列不可能的出站顺序为（ ）。
A.1、2、3、4 B.1、2、4、3 C.1、3、2、4 D.1、4、2、3
16.四个元素按A、B、C、D顺序进入S栈，执行两次Pop（S，x）运算后，栈顶元素的值是（ ）。
A.A B.B C.C D.D
17.由于十进制数转为二进制数是将该十进制数对2进行整除，直到商为0，再将每一次整除得到的余数按从下到上的顺序排列组合起来，因此十进制数转二进制数的过程中，适合用（ ）的数据结构来存储余数。
A.队列 B.栈 C.二叉树 D.图
18.在单链表中，要将s所指节点插入到p所指节点之后，其语句应为（ ）。
A.s->next=p+1； p->next=s； B.（*p）.next=s； （*s）.next=（*p）.next；
C.s->next=p->next； p->next=s->next； D.s->next=p->next； p->next=s；
二、判断题
19.同一线性表的各数据元素必定具有相同的数据类型和长度。（ ）
20.长度为1的字符串与单个字符的意义及可执行的操作是相同的。（ ）
21.字符串的数据元素可以是由一个字符组成，也可以是由多个字符组成。（ ）
22.字符串在存储时，既可以用顺序存储结构，也可以用链式存储结构。（ ）
23.某一个队列长度是8，依次进队8个元素，依次出队6个元素，此时至少还能在队列中插入6个元素。（ ）
24.栈是运算受限制的线性表。（ ）
25.在栈空的情况下，不能做出栈操作，否则产生下溢。（ ）
26.空栈就是所有元素都为0的栈。（ ）
27.一个栈的输入序列为A、B、C、D ，可以得到输出序列为C、A、B、D。（ ）
28.循环队列能实现对空间的更大限度的利用。（ ）
三、填空题
29.在数据结构中，具有“先进先出”特征的线性表是 。
30.在栈中，只能在 进行数据元素的插入和删除。
31.在一个顺序队列中，队头的标志是front，队尾的标志是rear，队列的长度为 。
32.循环队列的引入，目的是克服列队的 现象。
四、应用题
33.数据元素A、B、C依次入栈，入栈过程中允许栈顶元素出栈。出栈的序列可能有哪些？
34.用I表示进栈操作，用O表示出栈操作，如A、B、C三个元素，依次进栈写成“III”，依次再出栈写成“OOO”，经过这样的“IIIOOO”操作序列之后，出栈的序列是CBA。现有一个栈，元素进栈的次序为a、b、c、d、e，写出下列出栈的操作序列。
（1）c、b、a、d、e
（2）a、c、b、e、d