队列的概念及其基本操作

编程入门 行业动态 更新时间:2024-10-10 19:18:33

<a href=https://www.elefans.com/category/jswz/34/1771257.html style=队列的概念及其基本操作"/>

队列的概念及其基本操作

队列的基本操作:

队列初始化: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

更多推荐

队列的概念及其基本操作

本文发布于:2024-03-06 01:15:47,感谢您对本站的认可!
本文链接:https://www.elefans.com/category/jswz/34/1713968.html
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。
本文标签:队列   概念   操作

发布评论

评论列表 (有 0 条评论)
草根站长

>www.elefans.com

编程频道|电子爱好者 - 技术资讯及电子产品介绍!