-
第二章 受限的线性表
-
在绪论中,我们介绍了数据结构三要素, 第1章中,讲解了逻辑结构分类中线性结构的第一个部分——一般线性表,这章开始讲解逻辑结构线性结构的第二个部分——受限的线性表。这里先巩固下逻辑结构的分类,如下图所示:
受限线性表最简单直白的理解便是插入,删除,查找等操作时,不能随心所欲的进行,必须遵循一定的限制(规则)。
一.栈
1.1定义
栈(stack)是一种只允许在一端进行插入或删除操作的线性表。
一般规定,栈只能在栈顶进行插入,删除操作。因此访问元素的顺序是先进后出。
如下图所示:
这里介绍几个重要的概念:
栈顶(top):栈的操作中,仅允许插入和删除的那一端。
栈底(bottom):固定的,不允许进行插入和删除操作的那一端。
空栈:不含有任何元素的空线性表。
InitStack(&S) //初始化一个空栈S StackEmpty(S) //判断一个栈是否为空 Push(&S,x) //入栈,若栈未满,则将x加入使之称为新栈顶 Pop(&S,x) //出栈,若栈非空,则弹出栈顶元素,并用x返回 GetTop(S,&x) //读取栈顶元素,若栈S非空,则用x返回栈顶元素 ClearStack(S) //销毁栈,并释放栈S占用的存储空间
二.队列
2.1定义
队列(Queue)简称队,只允许在线性表的一端进行插入,另一端进行删除。
一般规定,只能在队尾进行插入操作,队头进行删除操作。因此访问时的顺序是先进先出。
如下图所示:
介绍几个重要的概念:
队头:允许删除的一端,又称为队首。
队尾:允许插入的一端。
空队列:不含任何元素的空表。
InitQueue(&Q) //初始化队列,构造一个空队列 QueueEmpty(&Q) //判断队列是否为空 EnQueue(&Q,x) //入队,若队列Q未满,将x加入,使之称为新的队尾 DeQueue(&Q,&x) //出队,若队列Q非空,删除队头元素,并用x返回 GetHead(Q,&x) //读取队头元素,若队列非空,则将队头元素赋值给x
三.串
3.1定义
字符串(string)简称串,是由零个或多个字符组成的有穷序列。
串长:串中所含字符的个数
子串:一个串中任意个连续字符组成的子序列(含空串,但不含串本身)
主串:包含子串的串
空串:含零个字符的串,通常用 Φ 表示。
StrAssign(&T,chars) //由字符串常量chars生成字符串T的操作。 StrCopy(&T,S) //由串S复制生成串T的操作。 StrCompare(S,T) //若S=T返回0,S>T返回正数,S<T返回负数。 StrLength(S) //返回串S的长度。 Concat(&T,S1,S2) //将串S1和S2连接起来生成串T的操作。 SubString(&Sub,S,pos,len)//以串S中pos位置开始的len个字符生成子串Sub的操作。 Index(S,T,pos) //返回子串T在S中pos个字符以后出现的位置。 Replace(&S,T,V) //将串S中所有不重叠子串T替换为串V的操作。 StrInsert(&S,pos,T) //在串S中第pos个字符前插入串T的操作。 StrDelete(&S,pos,len) //删除串S中第pos个字符开始的len个字符的操作
- 留下你的读书笔记
- 你还没登录,点击这里
-
用户笔记留言