第12章 字符串、栈-浙江高中信息技术知识点

浙江高中技术培优算法（陶小波） 48 第十二章 字符串、栈 1. 字符串是由零个或多个字符组成的有限组合。 2. 字符集是多个字符的集合。种类较多，每个字符集包含的字符个数不同，常 见的字符集有ASCII码字符集、GB2312字符集、GBK字符集、BIG5 字符集、GB18030 字符集、Unicode 字符集 3. 字符串空串：空串是不包含任何字符的串，其长度为 0 4. 字符串空格串：空格串是由空格组成的字符串，其长度为空格字符的个数 5. 字符串特性:1.有限序列性、2.字符串的可比性 6. 字符串是一种线性结构，它的数据元素个数是有限的，由 0 个或多个字符组 成，可以用元素在字符串中的相对位置作为标号来访问每个元素。在用 Python 实现的字符串中，由正索引符号和负索引标号。字符串”Hello World” 索引如 下图 7. 字符串切片与常用函数 详见本篇第三章 8. 正则表达式：正则表达式是用一些特定的字符组成的一个“规则字符串”。 它可以实现检查一个字符串中是否包含由某种子串、将匹配的子串替换或者从字 符串中取出符合某个条件的子串等操作 9. 队列是一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端 称为队首。 10. 队列中的数据元素称为队列元素，在队列中插入一个元素称为入队，从队列 中删除一个元素称为出队。如下图 11. 队列的特性：1.先进先出、后进后出，2.有限序列性 12. 队列也是一种线性表结构，元素个数是有限的。队列可以是空的，也可以包 含多个元素。队列中所有元素呈现线性特征，队首元素只有一个后继点，队尾元 素只有一个前驱点，其他元素既有一个前驱点，又有一个后继点。 13. 常见队列的操作有：入队、出队 浙江高中技术培优算法（陶小波） 49 14. Python 中自带队列对象 Queue，本文采用列表实现和 Queue 对象实现两种方 法 队列 head=tail=0 #头尾指针 ls=[] #空队列 ls.append("A") #入队 tail+=1 ls.append("B")#入队 tail+=1 ls.append("C")#入队 tail+=1 while head<tail:#出队 print(ls[head]) head+=1 列表实现 from queue import Queue q = Queue(maxsize=5) q.put("满分") q.put("计划") q.put("陶小波") print(q.queue) # 输出队列 结果 ['满分', '计划', '陶小 波'] q.get() # 出队列 先入先出 print(q.queue) # 输出队列 结果 ['计划', '陶小波'] print(q.empty()) # 判断是否为空 结果 False print(q.qsize()) # 输出队列元素数量 结果 2 print(q.full()) # 判断是否满队列 结果 False Queue 对象实现 15. 栈也是一种操作受限的线性表，仅允许在表的一端进行插入或删除。进行插 入或删除的操作的一端称为栈顶，位于栈顶位置的元素称为栈顶元素；相应的将 表的另一端称为栈底，位于栈低位置的元素为栈底元素 16. 栈的特性：1.先进后出、后进先出、2.有限序列性 17. 栈中的元素也是有限的。栈可以是空的，也可以包含多个元素。栈中元素呈 现线性关系，栈顶元素有一个前驱点，栈底元素有一个后继点，其他元素既有一 个前驱点，也有一个后继点 如下图 浙江高中技术培优算法（陶小波） 50 18. 栈的代码如下： Python 中自带队列对象 LifoQueue 实现栈，本文采用列表实现和 LifoQueue 对象实现两 种方法实现 import queue q = queue.LifoQueue(maxsize=5) q.put("满分") q.put("计划") q.put("陶小波") print(q.queue) # 输出栈结果 ['满分', '计划', '陶 小波'] q.get() # 出栈 print(q.queue) # 输出栈 结果 ['满分', '计划'] print(q.empty()) # 判断是否为空 print(q.qsize()) # 输出栈元素数量 print(q.full()) # 判断是否满栈 LifoQueue 对象实现 栈 ls = [] # 空栈 top = -1 # 栈顶 ls.append("A") # 入栈 top += 1 ls.append("B") # 入栈 top += 1 ls.append("C") # 入栈 top += 1 while top != -1: # 出栈 print(ls[top]) top -= 1 列表实现 浙江高中技术培优算法（陶小波） 51 （一）判定 b是否为 a 某栈的出栈顺序 def isstack(a,b): stack = [] i = j = 0 while i < len(a): stack.append(a[i]) i += 1 while len(stack) > 0 and stack[-1] == b[j]: stack.pop() j += 1 if len(stack) == 0 and i == j == len(a): return True else: return False a = [1, 2, 3, 4, 5] ls=[2,1,5,3,4] if isstack(a,ls): print(ls,"是",a,"的出栈序列") else: print(ls, "不是", a, "的出栈序列")