|
|
好同学们，大家好，今天呢，我们来为大家讲解一下。数据结构当中，站和对立这样一个部分。在和队列呢，我们在看到这个内容的时候呢，我们需要了解它的一些情况，比如说。它的基本概念。它的存储结构。它的应用这些呢，是我们需要了解的部分。债和队列呢，
是对线性表的某些操作加以限定，而派生出的结构。也就是说，我们的债和队列，包括今后我们要讲的串和数组了。它都属于线性表，只不过呢，它是操作受限的线性表。所以呢，我们的债和队列呢，也有我们的顺序债链债和我们的循环队列和链式队列。再和队列是仅限定插入和删除只能在表的端点。进行的线性表。那么我们看一下这样一个部分债和队列呢，是两种常用的数据类型。
首先呢，我们来看一下债的部分。这个这债呢？是只允许在一端进行插入。或删除操作的线性表，那么这里大家同学要注意债呢？它也属于线性表，只不过呢，是操作受限的线性表。也就是说，债呢，首先它是一种线性表，但限定这种线性表呢，只能在某一端进行插入或删除操作。那比如说我们这个图当中。
我们只能在一端进行一个插入。或者删除。在在中呢线性表允许。插入删除的那一端，我们称之为在顶。在底呢，是固定的。不允许进行插入和删除的那一端，也就是说在顶是top。在底了，是bottom。这就是我们的。债的部分，比如说我们这个图当中，我们允许了进行插入删除的这一端，
称为债顶。那么，不允许清除删，不允许插入删除的一端呢？称为占比。那么，还有一个空债，什么是空债呢？空战。就是不含任何元素的空表，那么我们这里呢？它就是空站。债呢，有一些基本操作，比如说以离销。
spark.初始化一个空站，还有destroy stack，销毁一个空站，销毁一个站start lens，求站的长度。struck empty.判断一个债是否为空，若空则返回true，否则呢，返回FALSE还有get top。如债顶元素，若再飞空，则返回债顶元素。clear stack.
那么就是清空一个债，还有push净债，若债s未满。则将我们的这样一个数据元素加入在顶。使之成为新的载体，还有破普。top呢是出债，它是独若债非空。则弹出在顶元素，并用这样一个数据数据类型呢？进行一个返回，以及呢？structural。便利一个债，那么这是债的基本操作。
债呢？它是一种操作受限的线性表。那么，类似于线性表呢？它也有对应的两种存储方式。一种呢，称之为顺序站。一种呢，称之为恋战。首先我们来看一下顺序在。顺序债呢，是采用顺序存储的债称为顺序债，它利用一组地址连续的存储单元。存放至在底至在顶的元素。同时呢，
复设一个指针top来表示，当前在顶元素的位置。它离它类似于呢，在线性表的顺序表示法指向表尾的指针呢，可作为载顶指针。那么我们看一下它的存储结构。井号de fin start initial site 1百一一号de fin start increment 10。还不是drug的，还不是defy drug ts element tab新tabs element tab base。int start sizes QS，这是定义一个结构体类型的这样一个部分，那么定义一个名称SQ start表示这样一个结构体。我们的在顶指针呢。再顶指针。这个时候呢。
指向链债中，指向链债指向，这是我们的顺序上这样一个顺，这样一个债的顺序的这样一个部分。那么，我们的链债是什么样子的？链债呢？就是用我们的这样一个。指针。指向第一个元素，再指向最后一个元素，再指向下一个元素，一直指向最后一个元素。采用链式存储的债呢？称为链债。
链债的优点呢，是便于多个债共享存储空间和提高其效率，且不存在呢。链在上亿的情况通常呢，采用单链表实现，并规定所有操作都是在单链表的表头进行。比如说我们的拓扑指针。列在顶指针指向了在顶元素。在底元素呢指向下，一个元素一直呢指向最后一个，第一个在底元素。采用链式存储了便于节点的插入和删除链在的操作呢，与链表类似。入债和出债的操作呢，都在链表的表头进行。
那么债呢？在算法设计中有着比较重要的这样一个应用运用的技巧呢？也比较高。那么这里呢？我们再给大家讲一下顺序债和链债，它的这样一个。特点那么也就是说。顺序在呢，它的入在操作受数组上界的约束。当对债的最大存储空间估计不足时，有可能发生债的上亿。这是顺序在的这样一个情况。念在呢，念在。它的。
优点呢，是便于多个站共享存储空间，提高效率。且不存在了载满上亿的情况，它采用链式存储，便于节点的插入和删除。链债呢？它的出债和入债操作都是在债的链表的表头进行。那么，这是债的顺序，债和链债，它的这样一个特点。接下来我们看一下债的应用，比如说。基于数字转换公式。
我们在这里转换公式了，是什么样子的呢？大家知道我们的我们的债呢？它的特点。就是。后进入债的。先出债，这是我们债的这样一个特点。债呢，最大的特点呢就是后进债的先出债。比如说我们可以将债的这样一个特点呢，运用到我们的数字转换当中。比如说我们的数字转换工具呢，是这样一个数来除以d，然后呢，
再乘以d+n来磨d，那么这是债的。数字转换的公式，比如说。我们要将十进制的1348转换成为八进制的这样一个数，那么怎么转换呢？首先呢，是用。1348来除，以八取取。得到它的商是168，然后呢？用它来磨用1348来磨一磨八。模八呢，得到的结果呢是四。
那么，我们再用1300÷48÷8的商168，再来除以八得到的商是21。这个时候呢，用它来磨八得到的余数呢，是零再用得到的商21来除以八那么商商呢二？用它来模八呢，得到的余数呢是五。再用我们除以八得到的这个商，二来再来除以八得到的商是零。用它来模八呢，得到的余数是二。那么这个时候呢，我们再用债的这样一个特点后，进债的先出债，
那么我们按照这个顺序呢得到的。最后的这样一个八进制数的这样一个情况呢，就是二五零四，那么我们得到的八进制数的这样一个情况呢，就是二五零四，我们按照这个顺序呢。得到的这样一个结果，二五零四。那么，这是我们计算的顺序，以及我们输出的顺序，它利用了我们债的后进，债的先出债这样一个特点呢？来计算我们的这样一个数字转换的部分。那么，
我们来看一下这个语句word conversion。initial starts.输入一个整输入一个整数。yn当这个整数呢？不为零的时候呢？push s。n摩巴。这个时候呢，就这里的n摩巴呢，表示n除除来摩巴得到的这样一个结果。将它呢，放入债中放将它放入债中，接下来呢再。用n来除以八。得到的商呢赋给n。
然后呢，再进行这样一个循环当n当得到的商不为零的时候呢，继续用它来除来磨八。得到的得到的这样一个数呢，放到我们的债中，接下来再用n来除以八得到的这个商呢负给n。那么，直到了得到的n呢为零，那么结束循环。接下来wire stack mps。那么如果债呢？不如果在了为空，那么取反了。那么如果债呢？不为空，
那么这个时候呢？债缺乏，那么执行实实现这样一个循环。po pse对债顶元素进行出债操作。这样呢，输出一个债比的这样一个元素e。它的这样一个含义呢，就是我们的。进将我们如果债非空，那么执行这样一个循环，将债顶元素呢进行出债。并删除掉我们的债顶元素。接下来输出这样一个在定元素，那么接下来呢？如果再还不为空的话，
那么接下来呢？就再进行循环，直到呢？再为空。这样呢，按照这个顺序先后进债的先出债，这样一个顺序呢，将债顶的元素呢依次。进行出站，然后呢？进行输出，那么这样呢？我们就实现了我们数字的转换，将余数将它的这样一个数呢？进行按这个顺序来进行排列。
得到了我们最后的这个数值的这样一个结果，那么这是我们数字转换的这样一个操作。那么，接下来我们再看一下括号匹配的检验，那么假设呢？在我们的表达式中。假设在表达式中。我们。这样的形式呢？括号这样的括号形式呢？配对的这样配匹配的这样一个形式呢？我们称之为正确的格式。而这样的格式呢？不匹配的形式呢？我们称之为不正确的格式，
那么检验括括号是否匹配的方法呢？那么，我们可以采用期待的紧迫程度这个概念的描述，比如说我们这样的括号序列。一二三四五六七八这样一个八个括号，那么分析可能出现的不匹配的情况，来到来的右括弧并非是所期待的。那么到来的呢，就是不匹不匹配的这样一个括号，那么直到结束也没有到来所期待的括弧。那么，我们来看一下这个算法的思想。凡是出现左括弧，则静在。凡是出现右括弧，
则检验债是否为空。如果为空，则表明该诱惑符多余，那么不匹配，否则呢，则与在顶元素比较。若匹配了，则左括弧。出债否则呢，表明不匹配。当表达式检验结束的时候呢，若债为空。则表明，表达式中呢，匹配正确。
也就说，我们所有的这样一个括号呢，都能够匹配。否则呢，表明左括弧有余，那么就说明了不匹配。我们来看一下这个算法，看一下这个程序。full matching下一句。exp数组int state=1 ch等于星号exp加加yo ch。不等于井号。并且state。switch of state.case左括弧push。s.
CHI加加break case。if.case右括号。右圆括号。if.start empty.并且呢，get TOPS。hopes eels estate=0 break，接下来是case右方括号，最后呢，是ch=exp。加加最后if stuck empty，并且state retire true else retire FALSE。那么这个呢，
就是用来检验括号了，是否匹配的这样一个语句？那么，我们来看一下这个部分。b marching share exexp这是一个函数，那么它的参数呢？是一个字符数组。int state=1那么定义一个整形，定义一个整形变量state=1 ch等于星号exp加加那么。ch呢等于数组字符，数组当中的这样一个值某个。字符元素的数组元素的值，并且呢，这个字这个这个这个exp呢加加。while.
ch.不等于井号，并且state，那么就是当我们的ch呢？不等于井号的时候，并且state呢？它是非。不为零的时候，那么switch och这是一个选条件判断。选择结构的这样一个条件判断case左括弧，那么当我们的这样一个。数据呢，是我们的左括号的时候，那么我们就进行push sch操作，进行我们的进入再操作，
把它放到我们的债中，然后呢I加加。break.case如果它出现的是右圆括号，那么我们就要判断它是否匹配，那么怎么判断呢？如果再飞空。并且呢，在顶元素是我们的左圆括号，那么这个时候呢，就说明是匹它的左它上一个呢，是这样一个左圆括号，那么是匹配的，那么这个时候呢，就进行初债操作。
to pse那么进行初再操作，并且呢，从在中呢删除这样一个在点元素，那么否则呢state=0那么。state=0将我们的state设置为0 break，那么这个是？跳出。那么，结束掉我们这样一个。选择题选择选择结构这样一个语句的运行，那么接下来呢？case右方括号那么也是一样的匹配操作，如果呢？在不为空，并且呢，
在顶元素呢，是左方括号，那么进行匹配，否则呢，state=0，然后break=0 break，那么这样一个匹配的操作。那么，这样一个选择结构呢？结束之后那么ch呢，等于星号exp加加那么得到进行下一个数据元素的这样一个一括号的就括号的这样一个p。数据元素的这样一个。要运用的这样一个部分，那么这个时候呢，最后如果if start mts。
并且state就说，如果再为空，并且呢，state了非零。那么这个时候呢，说明呢，括号呢，都是匹配的。最后呢，返回一个true，如果再不为空或者state了。非零为零，那么这个时候呢，返回一个FALSE，那么这就是括号匹配的这样一个算法。
那么，接下来我们再看一下行编辑程序问题，那么每接受一个字符呢？既存入寄存器。这样呢，并不恰当。用户输入一行的过程中呢允许用户输入出差错，并在发现有误时呢，可及时进行更正。那么，合理的做法呢？是设置一个输入缓冲区，用来接受用户输入的一行字符，并且逐行的输入用户数据区。假设井号为退格符，
那么at为退行符，那么我们看at为退行符，我们看一下假设从终端接收了这样两行数据。whl I井号井号il。r井号e。s井号，星号s。out CHA art.put char.星号s等于井号加加，那么得输入得得到的两行字符呢？实际上呢？有效的是这样，两行那么就是我们的while星sport char新s加加，那么就是我们有效的字符。
那么我们看一下这样一个语句。while.ch不等于eof eof呢，为全文结束符。while ch不等于uf，并且呢，ch不等于换行符。那么switch ch case井号那么假如是井号呢？to psc break。就说假如是井号对上一个输入的这样一个元素呢，进行一个初在操作，也就是说进行初在在链在在中呢，删除掉这个元素。删除掉载体元素，比如说如果是井号的话呢，
就进行初载删除操作。case art，如果是art的话呢，那么那么进行一个星空债的操作，然后设置债呢为空债。default那么其他的操作，其他的如果是其他的。其他的这样一个数据呢，那么就push sc将我们的这样一个。元素呢，放入在中，然后呢break那么最后呢ch=get char再从终端呢接收下一个字符。那么接下来。这部分呢，是将从寨底到寨顶的字符呢，
传送至调用过程的数据区。最后呢？clear starts重置s为空载，那么if ch不等于uf if。ch=get char。这个时候呢，那么传闻结束，如果呢ch不等于e of，那么ch=get char，那么再进行了这样一个循环的部分，那么这是我们的行编辑的这样一个问题。最后呢，我们再看一下表达式求值，表达式处理的过程呢，是需要两个在操作数，
在和符号，在比如说计算。二+4-36，那么我们呢？有操作符，有运算数，那么首先呢？制操作数在为空在。起始表起始表达式起始符井号呢，为运算符在的在底元素。至左至右，扫描表达式每一个字符时。啊，操作数和表达数，如果是操作数呢，
就入操作数，再如果是运算符呢，从运从在比运算符比较。那么高了就入站继续向后处理，如果是相等呢就出站，那么继续向后处理，如果是低了则从操作数。出债两个运算量从运算符债出债一个运算符进行运算，并将其运算结果呢？放入我们的对象栈。比如说计算二+4-3×6。那么，我们有我们的中缀表达式，以及呢，我们的后缀表达式，
然后我们来看一下算术运算式求值的过程。opera round.type evaluate expression这样一个函数initial star top tr。不许。OP tr.井号。initial stock OP nd.c=get char。while c不等于井号或者get top。OP tr不等于星，不等于井号。那么if。因COP虚反。那么不为零为不为零的话，非零的话，
那么pu shop nd CC=get char，那么不是运算符呢？就就进站。else switch.free set.get to pop trc case小于那么再点优先权d呢？那么push opt rcc=get char break？那么case等号如果这个时候呢，就去掉括号，并接触下一个字符OP opp opo ptr x。c0 get char break如果是大于的话，那么就进行退债，并将运算结果呢？入债拓扑OP trs it a。po po pndbpopoptaa.
pu shop nd operate as it ab break default print expression error,retire error.retail get to pop nd，那么这是我们表达式求值的这样一个部分，那么我们的。在呢，它还有函数调，可以实现递归的函数的实现。那么这里呢，大家就要注意我们的债呢。它的一个重要的用途呢，就是实现我们的递归，那么这里呢，大家要注意。对于在了。
对于债呢它的。一个重要应用呢，就是实现递归。那么债的这样一个应用呢？就是最大的，最重要的应用呢？就是实现递归，比如说我们的函数调用。那么word a May那么这个时候调用AA呢？又调用b那么b呢？这个时候调用完了？那么，回到a再回到我们的妹。
|
|
|Archiver|手机版|小黑屋|5432考试网
( 蜀ICP备2022024372号|
川公网安备51152402000101号 )|网站地图
发表于 2024-4-15 09:16:04