宁夏区建设厅网站,网页制作三剑客不包括,网站维护产品推介,做app网站的软件有哪些内容吗第三章
【3.1】
03、 假设以I和O分别表示入栈和出操作。栈的初态和终态均为空#xff0c;入栈和出栈的操作序列可表示为仅由I和O组成的序列#xff0c;可以操作的序列称为合法序列#xff0c;否则称为非法序列。 如IOIIOIOO 和IIIOOIOO是合法的#xff0c;而IOOIOIIO和II…第三章
【3.1】
03、 假设以I和O分别表示入栈和出操作。栈的初态和终态均为空入栈和出栈的操作序列可表示为仅由I和O组成的序列可以操作的序列称为合法序列否则称为非法序列。 如IOIIOIOO 和IIIOOIOO是合法的而IOOIOIIO和IIIOIOIO是不合法的。 通过分析写出一个算法判定所给的操作序列是否合法。若合法返回true否则返回 false(假定被判定的操作序列已存入一维数组中) 个人理解 就构造一个栈S然后将这个序列进行处理其中I表示入栈、O表示出栈直接对栈S进行Push和Pop操作有错误就报错没错误就表示该序列合法即可。 答案好像并没有创建栈也没有执行Push、Pop的操作。而是直接对序列进行分析只作了数学上的判定。 算法思想 扫描该序列每扫描至任意一个位置均需检查出栈次数即“O”的个数是否小于等于入栈次数“I”的个数若大于则为非法序列。扫描结束后再判断入栈和出栈次数是否相等若不相等则也不合法。
bool Judge(char A[]) {int i0;int j0; //j表示字母I的个数int k0; //k表示字母O的个数while(A[i]!\0) { //对字符串的遍历操作if(A[i]I)j;if(A[i]O)k;if(kj) {printf(序列非法\n);return false;}}if(j!k) {printf(序列非法\n);return false;}else {printf(序列合法\n);return true;}}另一种算法思想 入栈后栈内元素个数增加1个出栈后栈内元素个数减少1个。因此可将判定一组出入栈序列是否合法转化为一组由1和-1组成的序列它的任意前缀子序列的累加和不能小于0每执行一次出栈或入栈操作后立即判断则合法否则非法。此外整个序列的累加和必须等于0。 思考 这个问题是否和括号匹配问题一样——感觉好像是没啥区别。 04、 设单链表的表头指针为L结点结构由data和next两个域构成其中data域为字符型。试设计算法判断该链表的全部n个字符是否中心对称。 例如xyx、xyyx都是中心对称。 个人理解 第二章单链表部分的算法应该已经解决过这个问题了。 我大概有三种思路 1将单链表的后半段原地逆置之后使用两个间距为kk为表长的一半的指针同步遍历比较。 分析原地逆置但链表需要 O ( n ) O(n) O(n)两指针同步遍历需要 O ( n ) O(n) O(n)。因此时间复杂度为 O ( n ) O(n) O(n)空间复杂度为 O ( 1 ) O(1) O(1)。 2把单链表中的元素复制到数组里然后用数组直接判断中心对称。 分析复制需要 O ( n ) O(n) O(n)数组判断中心对称需要 O ( n ) O(n) O(n)。时间复杂度为 O ( n ) O(n) O(n)空间复杂度为 O ( n ) O(n) O(n)。 3从前往后把单链表中的各个结点元素依次入栈。之后将栈中元素一一出栈并与单链表中从前往后元素进行比较。如果知道链表的表长只入栈前半个表的元素即可一一出栈并与后半个表的元素比较 分析单链表元素一一入栈需要 O ( n ) O(n) O(n)一一出栈再进行比较需要 O ( n ) O(n) O(n)。时间复杂度为 O ( n ) O(n) O(n)空间复杂度为 O ( n ) O(n) O(n)。 05、
设有两个栈s1、s2都采用顺序栈方式并共享一个存储区[0,...,maxsize-1]为了尽量利用空间减少溢出的可能可采用栈顶相向、迎面增长的存储方式。试设计s1、s2有关入栈和出栈的操作算法。 个人理解 就是考察共享栈的入栈、出栈具体操作上的细节。不难但是比较重要各方面都要想清楚 那就是栈s1初始栈顶指针为-1栈s2初始栈顶指针为maxsize对于两个栈而言入栈操作都是先将指针移动一位s1是往大了加1s2是往小了减1的区别然后再赋值。出栈操作反之先取出当前栈顶指针的元素然后栈顶指针移动一位与入栈相反。此外还有判断栈空、栈满的问题栈空的问题好说栈满的问题就是根据s2的栈顶指针是否和s1的栈顶指针相邻即可。 分析 两个栈共享向量空间将两个栈的栈底设在向量两端。初始时s1栈顶指针为-1s2栈顶指针为maxsize。当两个栈顶指针相邻时判定为栈满。两个栈顶相向、迎面增长栈顶指针指向栈顶元素。 【注意】 1主要就是注意一下两个栈各自在入栈、出栈时栈顶指针是如何变化的。对于s1而言它是一个传统意义上的栈而对于s2而言它的操作大约是要反过来一下的。 2对于所有入栈、出栈操作都要时刻牢记**“入栈判满出栈判空”**的检查。 0如下定义共享栈的数据结构
当然不这样定义也无所谓。直接定义一个数组然后定义两个变量指向栈顶位置也一样
/* 共享栈的结构定义 */
#define maxsize 100
typedef struct {int stack[maxsize]; //栈空间int top[2]; //存放两个栈顶指针
}stk;stk s; //定义栈s为上述结构类型的变量而且为全局变量
s.top[0] -1;
s.top[1] maxsize; //初始化两个栈顶指针的值1入栈操作
int push(int i, int x) {//入栈操作i为栈号当i0时表示是s1执行入栈当i1时表示s2执行入栈//x是入栈元素//入栈成功返回1失败返回0if(i0 || i1) {printf(栈号输入不对);exit(0);}if(s.top[1]-s.top[0] 1) {printf(栈已满\n);return 0;}if(i0) {s.stack[s.top[0]] x;return 1;}if(i1) {s.stack[--s.top[1]] x;return 1;}
}2出栈操作
int pop(int i) {//出栈操作i为栈号当i0时表示是s1执行出栈当i1时表示s2执行出栈//出栈成功函数返回值为出栈的元素值失败则返回-1if(i0 || i1) {printf(栈号输入错误);exit(0);}if(i0) {if(s.top[0] -1) {printf(栈s1已为空无法出栈);return -1;} elsereturn s.stack[s.top[0]--];}if(i1) {if(s.top[1] maxsize) {printf(栈s2已为空无法出栈);return -1;} else return s.stack[s.top[1]];}
}【3.2】
01、
若希望循环队列中的元素都能得到利用则需设置一个标志域 tag并以 tag 的值为0或1来区分队头指针 front 和队尾指针 rear 相同时的队列状态是“空”还是“满”试编写与此结构相应的入队和出队算法。 个人理解 既然队空、队满的依据都是frontrear只不过队空时tag0队满时tag1。 那么首先队列为空时初始化为tag0之后不断入队、出队操作。若最后一次操作执行入队并使得队满则tag1若最后一次操作执行出队并使得队空则tag0。 咋样在队满的时候再检查一下上次操作的性质——没必要。我们每次执行入队都设tag1每次执行出队都同时设tag0这样如果发现frontrear了同时就再去看看tag是几就行了。没那么复杂。 算法思想 在循环队列的类型结构中增设一个tag的整型变量进队时置tag为1出队时置tag为0因为只有入队操作可能导致队满也只有出队操作可能导致队空。队列Q初始时置tag0, frontrear0。这样队列的4要素如下
队空条件Q.frontQ.rear Q.tag0
队满条件Q.frontQ.rear Q.tag1
进队操作Q.data[Q.rear]x; Q.rear(Q.rear1)%MaxSize; Q.tag1
出队操作xQ.data[Q.rear]; Q.front(Q.front1)%MaxSize; Q.tag0
1入队算法
int EnQueue(SqQueue Q, int x) {if(Q.frontQ.rear Q.tag1)return 0; //队满Q.data[Q.rear] x;Q.rear (Q.rear1)%MaxSize;Q.tag 1; //可能队满return 1;
}2出队算法
int DeQueue(SqQueue Q, int x) {if(Q.frontQ.rear Q.tag0)return 0; //队空x Q.data[Q.front];Q.front (Q.front1)%MaxSize;Q.tag 0; //可能队空return 1;
}02、
Q 是一个队列S 是一个空栈实现将队列中的元素逆置的算法。 个人理解 很简单了。队列元素依次出队并依次入栈。最后栈中元素依次全部出栈即可。不是光输出元素值那就再入回到队列中去。 算法思想 这个问题主要考察对于队列和栈的特性的理解。由于仅对队列进行一系列操作不可能将其中的元素逆置而栈可以将入栈的元素逆序提取出来因此我们可以让队列中的元素逐个地出队、入栈全部入栈后再逐个出栈、入队列。
void Inverser(Stack S, Queue Q) {//本算法实现将队列中的元素逆置while(!QueueEmpty(Q)) {x DeQueue(Q); //队列中全部元素依次出队Push(S, x); //元素依次入栈}while(!StackEmpty(S)) {Pop(S, x); //栈中全部元素依次出栈EnQueue(Q, x); //再入队}
}03、
利用两个栈 S1 和 S2 来模拟一个队列已知栈的 4 个运算定义如下
Push(S, x); //元素x入栈S
Pop(S, x); //S出栈并将出栈的值赋给x
StackEmpty(S); //判断栈是否为空
StackOverflow(S); //判断栈是否满如何利用栈的运算来实现该队列的 3 个运算形参由读者根据要求自己设计
Enqueue;
Dequeue;
QueueEmpty;有两个栈S1和S2。两种栈的操作入栈、出栈此外还可以判栈空、判栈满。 以此来完成入队、出队、判队空的操作。 什么叫实现队列的入队、出队就是必须得是先进先出的运算逻辑才叫队列。 栈是后进先出的逻辑怎么达到先进先出的效果——两个栈配合使用。 让序列依次入栈到S1中例如abcd进入S1[a b c d] 此时S1出栈肯定是d c b a这肯定达不到队列的要求但是可以把S1的出栈序列再次入栈到S2中进入S2[d c b a]。之后S2再出栈就能得到a b c d。从而达到队列的效果。 但是好像有个问题如果是一个元素、一个元素的这样操作的话例如把a入栈S1后立马出栈再入栈到S2中这样元素a和直接入栈没区别最后也不是队列的效果。必须一次性把所需序列全部入栈S1、再出栈S1、再入栈到S2中才有效果。但是对于单个元素、单个元素这种的就不能这样做。 看下答案怎么说。 算法思想 利用两个栈 S1 和 S2 来模拟一个队列当需要向队列中插入一个元素时用 S1 来存放已输入的元素即 S1 执行入栈操作。当需要出队时则对S2执行出栈操作注意此时需要判断S2是否为空若为空则需要将S1先出栈并入栈到S2若S2不为空则直接执行S2出栈即可。总结如下两点
主要要搞清楚到底啥叫出队啥叫入队。不是说入队就是abc进入出队就是cba出来。入队、出队都只是一个元素的事。
1对S2的出栈操作用作出队。若S2为空则先将S1中的所有元素送入S2。
2对S1的入栈操作用作入队。若S1满必须先保证S2为空才能将S1中的元素全部插入S2中。
入队算法
int EnQueue(Stack S1, Stack S2, int e) {if(!StackOverflow(S1)) {Push(S1, e);return 1;}if(StackOverflow(S1) !StackEmpty(S2)) {printf(队列满);return 0;}if(StackOverflow(S1) StackEmpty(S2)) {while(!StackEmpty(S1)) {Pop(S1, x);Push(S2, x);}}Push(S1, e);return 1;
}出队算法
void DeQueue(Stack S1, Stack S2, int x) {if(!StackEmpty(S2))Pop(S2, x);else if(StackEmpty(S1))printf(队列为空); //S2为空此时去S1找发现S1也为空else {while(!StackEmpty(S1)) { //S2为空如果S1里有就先运过来Pop(S1, x);Push(S2, x);}Pop(S2, x); //都运过来之后S2出栈一下}
}判断队列为空的算法
int QueueEmpty(Stack S1, Stack S2) {if(StackEmpty(S1) StackEmpty(S2))return 1;elsereturn 0;
}04、
[2019 统考真题] 请设计一个队列要求满足①初始时队列为空②入队时允许增加队列占用空间③出队后出队元素所占用的空间可重复使用即整个队列所占用的空间只增不减④入队操作和出队操作的时间复杂度始终保持为 0(1)。请回答下列问题 1该队列是应选择链式存储结构还是应选择顺序存储结构 2画出队列的初始状态并给出判断队空和队满的条件。 3画出第一个元素入队后的队列状态。 4给出入队操作和出队操作的基本过程。 根据题意应该是要使用链式队列。主要是因为入队时允许增加队列占用空间这一点。如果是顺序存储空间会比较难实现。链表若想增加空间则插入一个新结点即可。 此外由于出队元素所占空间可以重复使用因此应该还是个循环队列。 对于单链表存放队列而言通常单链表表头对应的是队头单链表表尾对应的是队尾。可知出队操作在队头完成入队操作在队尾完成。 综上大概使用一个循环单链表可以带上一个头结点效果更好了作为该循环队列的链式存储结构即可实现题目要求。 个人理解 1应选择链式存储结构。而且选用带头、尾指针的循环单链表比较合适。 2初始状态为仅有一个头结点L此时Q-frontQ-rearNULL。队空判断条件为Q-front Q-rear队满判断条件为Q-rear-next Q-front。 3含有一个头结点、一个成员结点的循环单链表。 4入队操作若队列未满则尾指针后移一位、元素赋值到尾指针所指结点上若队列已满则建立一个新结点将新结点插入到尾指针后面。 出队操作若队列非空则输出头指针所指元素并将头指针后移一位。若队列已经为空则无法出队。 下面看下答案。 答案
1采用链式存储结构循环单链表即可满足四点要求。而顺序存储结构无法满足要求②。
2可以参考循环队列的思维。不过此处由于是链式存储因此入队时空间不够还可以动态增加。同样地循环链式队列也要区分队满、队空的情况这里参考循环队列牺牲一个存储单元的思想来做分析。初始时创建只有一个空闲结点的循环单链表头指针front和尾指针rear均指向空闲节点如下图所示。 队空的判定条件front rear
队满的判定条件front rear-next 不要用死板的眼光看待问题。看这里可能会觉得现在不是“队空”吗什么也没有而此时front rear-next啊这队空和队满怎么判定条件一样 人家这就是队满。现在队列的实际空间为0若想要入队一个元素那就是队满的情形。同时若想要出队一个元素那就是队空的情形。 这个地方链式队列要和顺序循环队列区分清楚不要混为一谈。 3插入第一个元素后的状态如下图所示 个人认为就在头结点的后面做头插即可。 4操作的基本过程
他这个操作是根据他第3问画的图那样来弄的如果画的图不一样操作相应也有区别
1.入队操作
若(front rear-next) //队满则 在rear后面插入一个新的空闲结点;
入队元素保存到rear所指结点中;
rear rear-next;
return;2.出队操作
若(front rear) //队空则 出队失败返回;
取 front所指结点中的元素e;
front front-next;
return e;
