队列的概念及其基本操作"/>
队列的概念及其基本操作
队列的基本操作:
队列初始化:InitQueue(q)
入队操作:InQueue(q,x) :对已经存在的的队列q,插入一个元素x到队尾。操作成功返回true,失败返回false
出队操作:OutQueuue(q,x):删除队首元素,并返回其值。操作成功返回true。
读取队首元素:FrontQueue(q,x):返回其值。
判断空队列:EmptyQueue(q):若队列为空返回1,负责返回0
队列的顺序结构:
一、队头指针指示队列中队头元素的前面一个位,队尾指针指示队列中队尾元素位置
二、队满和队空
队空条件:rear=front
假队满:rear= maxsize
队满:rear—front = maxsize
循环队列:
需要事先定义一个相应的空间存储数据,若事先不清楚所需存储空间大小,存在弊端。故引入链队列解决这一问题。
链队列:链式存储结构克服了顺序队列存在的需要预先确定存储空间的问题。
队列的基本操作:
表达式的求值问题
算法思想:01.设立操作数栈与运算符栈
02、设表达式的结束符为“#”,预设运算符的栈底为“#”
03、若当前字符是操作数,则直接压入操作数栈
04、若当前字符是运算符,且运算符的优先级高于栈顶运算符则进栈;否则,从操作数栈中弹出两个操作数并弹出运算符栈的栈顶运算符,经计算后压入操作数栈。
算法总结——递归与分治算法
分治法的算法思想:排序算法中的快速排序算法、归并排序算法、查找算法中的折半查找算法、大整数相乘算法、棋牌覆盖、汉诺塔问题。
串的定义:是由零个或者多个字符组成的有限序列。
基本操作:
一、串插入操作StrInsert(S,pos,T)
初始条件:串s和T存在,1<=pos<=strlength(s)+1
操作结果:在串s的下标为pos的字符前插入字符T。
二、串删除操作StrDelete(s,pos,len)
初始条件:串s存在,pos的长度大于等于1并且小于等于s的长度。len的大小要大于等于0并且小于等于s的长度减去pos再加1。
操作结果:从串s中删除下标为pos,长度为len的子串。
三、串连接操作StrCat(s,t)
初始条件:串s和t存在。
操作结果:返回由s和t联结而成的新串。
四、求子串操作SubString(Sub,S,pos,len)
初始条件:串s存在,pos的长度大于等于1并且小于等于s的长度。len的大小要大于等于0并且小于等于s的长度减去pos再加1。
操作结果:同sub返回串s的第pos个字符起长度为len的子串。
五、求位置操作StrIndex(s,pos,t)
初始条件:主串s和t存在,t是非空串。
操作结果:若主串s中存在和串t值相同的子串,则返回它在主串s中从第pos个字符起第一次出现的位置,否则返回0。
六、串替换操作StrReplace(s,t,v)
初始条件:串s、t、v均存在,且t是非空串。
操作结果:用v替换主串s中所有与t相等的不重叠的子串。
串的模式匹配
串的存储结构:定长顺序串
堆串
块链串
串的模式匹配:简单匹配算法 时间复杂度:O(m*n)
KMP算法
一、基于定长顺序串的BF简单匹配算法(暴力匹配算法)
失配后的比较位置有回溯,因而造成了比较次数过多。
时间复杂度:O(m*n)
二、基于KMP算法
(1)特点:在匹配的过程中,不需要回溯主串的指针i,且时间复杂度可以达到O(m+n)
(2) 模式串的next值计算思想
树结构
一、线性表、栈、队列、数组、广义表、串都属于线性结构。
1、线性结构特点:第一个数据元素无前驱,最后一个元素无后继,其他元素一个前驱,一个后继。
2、树型结构:根节点(无前驱),多个叶子节点(无后继),其他数据元素(一个前驱,一个后继)
3、结点的度:结点的子树个数
4、树的度:树的所有节点中最大的度数。
5、叶结点:度为0的结点。
6、父结点:有子树的结点是其子树结点的根结点的父结点。
二、树的表示方法
(一)、儿子—兄弟表示法
三、二叉树的性质:
1、二叉树是n(n>=0)个节点的有限集合。
2、当n=0时,称为空二叉树。
3、当n>0时,该集合由一个根节点及两颗互不相交的左子树和右子树,的二叉树组成。
注意:一、每个结点的度都大于2.
二、每个结点的孩子节点,次序不能任意颠倒。即孩子有左右之分。
三、除了根结点以外,每个结点有且仅有一个父结点。
重要性质:一、在二叉树的第i层至多有2的(i-1)个结点。
二、深度为k的二叉树至多含2的(k次方)-1个结点。
三、对任何一颗二叉树,若它含有n0个叶子结点、n2个度为2的结点,则必然存在n0=n2+1。
(二)、特殊的二叉树
关系:1、满二叉树必为完全二叉树
2、完全二叉树不一定是满二叉树。
1、满二叉树:深度为k且含有2的(k次方)-1个结点的二叉树。
2、完全二叉树:书中所含的n个结点和满二叉树中编号为1至n的结点一一对应。
具有n个结点的完全二叉树的深度为 :/log2 n/+1
更多推荐
队列的概念及其基本操作
发布评论