资源简介

(共44张PPT)
专题三　字符串、
队列、栈及应用
思维导图
归纳提炼
一、字符串
1.字符串的概念
(1)字符串是由零个或多个字符组成的有限序列。
(2)字符串长度:字符串中所包含字符的个数。
(3)主要形式有:'Python'、"Python"、""Python""。
正确区分空串和空格串
空串是指不包含任何字符的串,其长度为零。而空格串是指由空格组成的字符串,其长度为空格字符的个数。
重难点剖析
2.字符串的特性
(1)有限序列性
字符串的数据元素个数是有限的。
(2)字符串的可比性
若比较的字符串中的字符为ASCII字符集,则按字符的ASCII码值进行比较。
3.字符串的基本操作
(1)子串判断
子串判断用于检查字符串a是否为字符串S的子串,可用in运算实现。
(2)求子串
求子串用于从字符串中取出其子串,可用切片实现。
(3)字符串的连接
字符串的连接用于把两个字符串连接在一起,用“+”号连接符实现。
4.Python字符串常用函数和方法
Python字符串常用函数和方法
函数和方法 功能 实例
len(x) 统计字符串x中字符的个数 x="Python"
len(x)的值为6
x.find(y) 返回字符串x中子串y出现的首字符下标,若找不到,则输出-1 x="Python"
y="on"
x.find(y)
返回的值为4
x.split(str="", num=string.count(str)) 以str分隔符切片x,若num有指定值,则表示仅分隔num个子串。切片得到的值存储在列表中 x="1,2,3,4"
y=x.split(",")
y列表的内容为:
['1','2','3','4']
x.replace(old,new[,max]) 返回字符串中的old替换成new后生成的新字符串,若指定第三个参数max,则表示替换不超过max次 x="This data is new data."
x.replace("data","bag")
执行后x字符串为:
'This bag is new bag.'
x.upper( ) 把字符串x中的小写字母转换成大写字母 x="Python"
x.upper( )
执行后x字符串为:
'PYTHON'
x.lower( ) 把字符串x中的大写字母转换成小写字母 x="Python"
x.lower( )
执行后x字符串为:
'python'
5.正则表达式
(1)正则表达式是用一些特定的字符组成的一个“规则字符串”。
(2)作用:它可以实现检查一个字符串中是否含有某种子串、将匹配的子串替换或从字符串中取出符合某个条件的子串等操作。
二、队列
1.队列的概念
(1)队列是一种先进先出的线性表,允许插入的一端称为队尾,允许删除的一端称为队首。
(2)队列中的数据元素称为队列元素。
2.队列的特性
(1)先进先出、后进后出。
(2)有限序列性。
队头指针指向实际队头元素的前一个位置,而队尾指针指向实际队尾元素所在的位置。
重难点剖析
3.队列的存储
(1)顺序结构存储
队列的顺序结构存储指用一段地址连续的内存单元依次存储在队列中的数据元素。
顺序存储的队列称为顺序队列,可用数组来实现。
(2)队列的链式存储
队列的链式存储指用一组任意(不要求连续)的内存单元存储队列中的数据元素及数据元素间的关系。
队列的链式存储称为链队列,用链表来实现,一个链队列由一个头指针和一个尾指针共同确定。
4.队列的操作(建队、入队、出队)的实现
(1)顺序队列
m=100　#队列规模
head=tail=0
que=[""]*m　#建队
data=input("please input data:")
i=0
while data!="#":　#入队操作,输入#结束
if tail==m:
　print("队列已满!")
else:
　　que[tail]=data
　　tail+=1
　　data=input("please input data:")
while head　 print(que[head],end='')
　 head+=1
(2)循环队列
m=100　#队列规模
head=tail=0
que=[""]*m　　#建队
data=input("please input data:")
i=0
while data!="#":　#入队操作,输入#结束
if (tail+1)%m==head:
print("队列已满!")
else:
que[tail]=data
tail=(tail+1)%m
data=input("please input data:")
while headprint(que[head],end='')
head+=1
(3)链表队列
class Queue( ):
def_init_(self):
self.queue=[]
def queue_in(self,data):
#data插入队列
self.queue.insert(0,data)
def queue_out(self):
#取出队首元素
if len(self.queue):
return self.queue.pop( )
return "队列已空"
5.与队列有关的Python模块
Python内建有queue模块,在这个模块内可以使用Queue()建立对象,然后可以使用下列方法执行queue的操作。
from queue import Queue
q=queue( )
for i in range(3):
q.put(i)
while not q.empty( ):
print(q.get ())
Queue类中定义的方法
方法 功能描述
put( ) 在队尾插入数据
get( ) 在队首取出数据
qsize( ) 返回队列的长度,即队列中的元素个数
empty( ) 判断队列是否为空,返回值为True或False
full( ) 判断队列是否为满,返回值为True或False
三、栈
1.栈的概念
(1)栈也是一种操作受限的线性表,仅允许在表的一端进行插入或删除。
(2)进行插入或删除操作的一端称为栈顶,位于栈顶位置的元素称为栈顶元素;表的另一端称为栈底,位于栈底位置的元素为栈底元素。
2.栈的特性
(1)先进后出、后进先出。
(2)有限序列性。
栈可以是空的,也可以包含多个元素。
3.栈的基本操作
(1)建栈
当要存储n个元素的栈时,可以用列表创建一个长度为n的栈。
(2)入栈、出栈
入栈操作:入栈也叫压栈操作,把数据元素压入栈顶,每次入栈时,栈顶指针变量top值加1,再给st[top]赋值。
出栈操作:出栈时把栈顶元素取出,同时top值减1。如果栈中没有元素时,即top=-1,不能进行出栈操作。
4.使用列表模拟栈操作
a=[]　#建栈
a.append("data1")　#入栈
a.append("data2")　#入栈
a.append("data3")　#入栈
print(a.pop())　#出栈
print(a.pop())　#出栈
print(a.pop())　#出栈
5.建立stack类并进行栈操作
class Stack( ):
def_init_(self):　#建栈
　　　 self.my_stack=[]
def push(self,data):　#入栈
　　　 self.my_stack.append(data)
def pop(self):　#出栈
return self.my_stack.pop( )
def size(self):　#栈空判断
return len(self.my_stack)
def isEmpty(self):
return self.my_stack==[]
stack=Stack( )
a=["data1","data2","data3"]
for item in a:　#入栈
stack.push(item)
print("栈中元素个数为:",stack.size( ))
while not stack.isEmpty( ): #出栈
print(stack.pop( ))
典型例题
[例1] 下列关于字符串的描述,错误的是(　 　)
A.网上购物的订单号可以用字符串表示
B.不存在长度为0的字符串
C.一个字符串可以包含数字、字母和其他字符
D.字符串是不可变对象
B
解析:字符串内容可以为空,如'',它的长度为0,因此答案为B。
[例2] 某字符串内容为“date:2022-05-01”,则该字符串的长度为(　 　)
A.4 B.5 C.13 D.15
D
解析:字符串的长度为字符串中字符的个数,字符串内容为“date··2022-05-01”,共有15个字符,因此长度为15,故答案为D。
[例3] 下列有关栈的说法中,不正确的是(　 　)
A.栈仅允许在表的一端进行插入或删除操作
B.进行插入或删除操作的一端称为栈底
C.栈可以是空的,也可以包含多个元素
D.入栈也叫压栈操作,把数据元素压入栈顶
B
解析:栈是一种操作受限的线性表,仅允许在表的一端进行插入或删除操作,位于栈顶位置的元素称为栈顶元素,位于栈底位置的元素称为栈底元素。进行插入或删除操作的一端称为栈顶,因此答案为B。
[例4] 有如下Python 程序:
s1=[0]*5
s2=[0]*5
top1=-1
top2=-1
a=[9,2,5,6,1]
for i in range(len(a)):
while top1!=-1 and a[i]top2+=1
s2[top2]=s1[top1]
top1-=1
top1+=1
s1[top1]=a[i]
while top2!=-1:
top1+=1
s1[top1]=s2[top2]
top2 -=1
print(s1[top1])
执行程序后的输出结果是(　 　)
A.1 B.5 C.6 D.9
D
解析:本题考查栈的相关知识。本题通过两个栈s1,s2,若a[i]a[i] s1 s2
9 9
2 29 9入栈再出栈
5 259 9入栈再出栈
6 2569 9入栈再出栈
1 12569 9652依次入栈
可知,最后栈s1的栈顶元素为9,故答案为D。
[例5] 有后缀表达式“1 3 + 2 * 3 +2 *”,现利用栈计算该表达式:从左向右扫描,遇到数字时,数字入栈;遇到运算符时,两个元素出栈,用运算符计算,所得结果入栈,如此反复操作,直到扫描结束,栈顶元素是(　 　)
A.21 B.22 C.23 D.24
B
解析:本题主要考查栈的相关操作。依题意可得表达式为((1+3)*2+3)*2=22,因此答案为B。
[例6] 设栈S和队列Q的初始状态为空,元素A1、A2、A3、A4、A5、A6、A7、A8、A9依次通过栈S,一个元素出栈后即进入队列Q,若出队的顺序依次为A4、A8、A9、A7、A6、A5、A3、A2、A1,则栈S的容量至少应该为(　 　)
A.6 B.7 C.8 D.9
B
解析:本题主要考查的是栈和队列的特点。栈的特点是先进后出,而队列的特点是先进先出,根据出队顺序可知,出栈的顺序依次为A4、A8、A9、A7、A6、A5、A3、A2、A1,在A4出栈前,栈里的元素(从栈顶到栈底)依次为A4、A3、A2、A1,共4个元素;在A8出栈前,栈里的元素为A8、A7、A6、A5、A3、A2、A1,共7个元素; 在A9出栈前,栈里的元素为A9、A7、A6、A5、A3、A2、A1,共7个元素,此时,所有元素均入栈,因此,栈的最小容量应为7,答案为B。
[例7] (2023·浙江1月选考)有1个队列,队首到队尾的元素依次为8,3,2,9,5。约定:T操作是指队列中1个元素出队后再入队,Q操作是指队列中1个元素出队。则经过TTTQTTQ系列操作后,队列中队首到队尾的元素依次为(　 　)
A.2,9,5 B.2,5,8 C.5,8,2 D.8,3,2
B
解析:本题主要考查的是队列操作。结合题意可知,T操作表示队首元素出队后再入队,Q操作为队首元素出队,操作过程如下表所示:
队列操作 操作后队列状态
初始状态 8,3,2,9,5
T 3,2,9,5,8
T 2,9,5,8,3
T 9,5,8,3,2
Q 5,8,3,2
T 8,3,2,5
T 3,2,5,8
Q 2,5,8
操作之后的元素分别为2,5,8,故答案为B。
[例8] 火车有n节车厢,现由于超载,不得不断开车厢(断开后不能再拼接)。假设火车限重m,且至少有一节车厢质量小于m,求火车正常行驶时车厢的最多节数。
程序运行时,输入车厢节数n以及各节车厢质量,输入限重m。程序运行界面如下图所示。
请输入火车车厢节数:6
请输入火车限重:5
请输入第1节车厢质量:3
请输入第2节车厢质量:2
请输入第3节车厢质量:1
请输入第4节车厢质量:2
请输入第5节车厢质量:3
请输入第6节车厢质量:2
火车正常行驶时车厢的最多节数为:3
使用Python队列来实现上述功能的代码如下,请在程序划线处填入合适的代码。
n=int(input("请输入火车车厢节数:"))
m=int(input("请输入火车限重:"))
que=[0]*n
head=tail=0
maxlength=0
def calw(a,b):
total=0
for i in range(a,b):
total+=que[i]
return total
for j in range(n):
w=int(input("请输入第"+str(j+1)+"节车厢质量:"))
　　　　①　　　
tail+=1
if　　　　②　　　　:
　 if tail-head>maxlength:
maxlength=tail-head
else:
　while calw(head,tail)>m:
　 　　　　③　　　　
print("火车正常行驶时车厢的最多节数为:",maxlength)
程序划线①处应填入的代码为:　　　　　　　　　　　　;
程序划线②处应填入的代码为:　　　　　　　　　　　　;
程序划线③处应填入的代码为:　　　　　　　　　　　　。
que[tail]=w　
calw(head,tail)<=m
head+=1
解析:程序①处表示入队操作,先将元素入队,然后队尾指针加1,因此代码为que[tail]=w; 自定义函数calw(a,b)的功能是求开始车厢到结束车厢的载质量总和,程序②处的功能是判断队列中队首指针至队尾指针间的元素总和是否超过m,因此②处代码为calw(head,tail)<=m,如果未超过m,则为车厢节数,并记录最大值,若队首指针至队尾指针间的元素总和超过m,则将队首元素出队,即队首指针head加1,然后再判断载质量是否超过m,如此继续,因此③处代码为head+=1。
感谢观看

展开更多......

收起↑