【答案】
1、输入序列为123456，不能得出435612，其理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能栈底元素1在栈顶元素2之前出栈。
得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为：13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。
2、不能得到序列2，5，3，4，6。栈可以用单链表实现，这就是链栈。由于栈只在栈顶操作，所以链栈通常不设头结点。
3. 简述顺序存储队列的“假溢出”现象的避免方法及怎样判定队列满和空的条件。 【答案】：
3、设顺序存储队列用一维数组q[m]表示，其中m为队列中元素个数，队列中元素在向量中的下标从0到m-1。设队头指针为front，队尾指针是rear，约定front指向队头元素的前一位置，rear指向队尾元素。当front等于-1时队空，rear等于m-1时为队满。由于队列的性质（“删除”在队头而“插入”在队尾），所以当队尾指针rear等于m-1时，若front不等于-1，则队列中仍有空闲单元，所以队列并不是真满。这时若再有入队操作，会造成假“溢出”。其解决办法有二，一是将队列元素向前“平移”（占用0至rear-front-1）；二是将队列看成首尾相连，即循环队列（0..m-1）。在循环队列下，仍定义front=rear时为队空，而判断队满则用两种办法，一是用“牺牲一个单元”，即rear+1=front（准确记是（rear+1）%m=front，m是队列容量）时为队满。另一种解法是“设标记”方法，如设标记tag，tag等于0情况下，若删除时导致front=rear为队空；tag=1情况下，若因插入导致front=rear则为队满。
4.假设有如下图所示的列车调度系统，约定两侧铁道均为单向行驶，入口处有N节硬席或软席车厢（程序中可分别用H和S表示）等待调度，试编写算法，输出对这N节车厢进行调度的操作序列，要求所有的软席车厢被调整到硬席车厢之前。
? 【参考答案】： ? void trains(char *elem) ? {int i,k; ? k=0;
? for(i=0;i ? if(elem[i]==‘S’) //软席车厢S ? { push(); ? pop(); ? } ? else ? {push(); ? k++} ? while(k>0){pop();k--;} ? } 5.对于一个具有N个单元（N>>2）的循环队列，若从进入第一个元素开始每隔T1个时间单位进入下一个元素，同时从进入第一个元素开始，每隔T2（T2>T1）个时间单位处理完一个元素并令其出队，试编写一个算法，求出在第几个元素进队时将发生溢出。 ? 【分析】 ? 时刻t: 0 1 2 3 4 5 6 7 8 9 ? 个数： 1 1 2 1 2 2 3-2 2 3 2 ? 放取： + + - + + - + - ? 时刻t: 10 11 12 13 ? 个数： 3 3 4-3 …… ? 放取： + + - …… ? ? N=2 ? 先放后取： 6时刻，放了4次，3个为溢出 ? 放取同时： 8时刻，放了5次，3个为溢出 如果同一时刻先放后取： int main( ) { int y=1,i=0, n, m, front=0,rear=1; cin>>n; cin>>t1;cin>>t2; m=n+2; if (t1>=t2) cout<<\ else{ while((rear+1)%m!=front) { i++; if (i%t1==0) {rear=(rear+1 )%m; y++; } if (i%t1==0&&(rear+1)%m==front) break; if (i%t2==0) {front=(front+1 )%m; } } cout< 习题3 1.假定有编号为A、B、C、D的四辆列车，自右向左顺序开进一个栈式结构的站台， 如图3.16所示。可以通过栈来编组然后开出站台。请写出列车开出站台的顺序有几种？写出每一种可能的序列。如果有n辆列车进行编组呢？如何编程？ 注：每一辆列车由站台向左开出时，均可进栈、出栈开出站台，但不允许出栈后回退。 图3.16 火车编组栈 2.已知栈采用链式存储结构，初始时为空，试画出a,b,c,d四个元素依次进栈以后栈的状态，然后再画出此时的栈顶元素出栈后的状态。 3.写出链表栈的取栈顶元素和置栈空的算法。 4.写出计算表达式3+4/25*8-6时，操作数栈和运算符栈的变化情况表。 5.对于给定的十进制正整数N，转换成对应的八进制正整数。 （1）写出递归算法。 （2）写出非递归算法。 6.已知n为大于等于零的整数，试写出计算下列递归函数f(n)的递归和非递归算法。 n?1? f(n)=??n*f(n/2)当n?0时当n?0时 7. 假设如题3.1所述火车调度站的入口处有n节硬席或软席车厢（分别以H和S表示）等待调度。试编写算法，输出对这n节车厢进行调度的操作（即入栈或出栈操作）序列，以使所有的软席车厢都被调整到硬席车厢之前。 8.课文中规定：无论是循环队列还是链表队列，队头指针总是指向队头元素的前一位置，队尾指针指向队尾元素。 （1）试画出有２个元素Ａ、B的循环队列图，及将这2个元素出队后队列的状态图。 注：假设MAXSIZE=6，front=5，完成本题要求的图示。若erar=5，情况如何？ （2）试画出有２个元素C、D的链表队列图，及将这2个元素出队后链表队列的状态图。 9.对于一个具有m个单元的循环队列，写出求队列中元素个数的公式。 10.对于一个具有n个单元(n>>2)的循环队列,若从进入第一个元素开始，每隔t1个时间单位进入下一个元素，同时从进入第一个元素开始，每隔t2(t2≥t1)个时间单位处理完一个元素并令其出队，试编写一个算法，求出在第几个元素进队时将发生溢出。 11.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写出相应的置空队列，入队列和出队列的算法。 12.二项式(a + b)i展开后，其系数构成杨辉三角形。利用队列写出打印杨辉三角形前n行的程序。即逐行打印二项展开式(a + b)i 的系数。图3.17是指数i从1到6的(a + b)i的展开式系数所构成的杨辉三角形。 讨论小课堂4 重点掌握串的匹配运算及应用，可结合实际的题目进行讨论来加深对串的一些运算的理解和掌握。 1. 输入一个字符串，内有数字和非数字字符，如：ak123x456 17960?302gef4563，将其中连续的数字作为一个整体，依次存放到一数组ａ中，例如123放入ａ［０］,456放入ａ［１］，… … 。编程统计其共有多少个整数，并输出这些数。 【参考答案】在一个字符串内，统计含多少整数的问题，核心是如何将数从字符串中分离出来。从左到右扫描字符串，初次碰到数字字符时，作为一个整数的开始。然后进行拼数，即将连续出现的数字字符拼成一个整数，直到碰到非数字字符为止，一个整数拼完，存入数组，再准备下一整数，如此下去，直至整个字符串扫描到结束。 算法如下： int CountInt（） /* 从键盘输入字符串，连续的数字字符算作一个整数，统计其中整数的个数。*/ ｛int i=0，a[]； /* 整数存储到数组a，i记整数个数*/ char ch; scanf(″%d″,&ch)；/* 从左到右读入字符串*/ while（ch!=?#‘） /*?#‘是字符串结束标记*/ if（（ch）>=48 && (ch)<=57）/* 是数字字符*/ ｛num=０； /*数初始化*/ while（（ch）>=48 && (ch)<=57 && ch!=?#‘）/* 拼数*/ ｛num=num＊10+?ch‘-?０‘； scanf(″%d″,&ch)； ｝ a[i]=num；i++； if（ch!=?#‘）scanf(″%d″,&ch)；/* 若拼数中输入了?#‘，则不再输入*/ ｝while（ch！＝?#‘） /* 结束*/ Printf(‖共有%d‖,I,‖个整数，它们是：‖)； for（j=０；j if（（j+1）％10==0）printf(―\\n‖);} /*每10个数输出在一行上*/ ｝/* 算法结束*/ 假定字符串中的数均不超过32767，否则，需用长整型数组及变量。 2. 以顺序存储结构表示串，设计算法。求串S中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。例如：若S=―abceebccadddddaaadd!‖， 则最长重复子串为―ddddd‖。位置是9。 【参考答案】设以字符数组s表示串，重复子串的含义是由一个或多个连续相等的字符组成的子串，其长度用max表示，初始长度为0，将每个局部重复子串的长度与max相比，若比max大，则需要更新max，并用index记住其开始位置。 算法如下： int LongestString(char s[],int n) /*串用一维数组s存储，长度为n，本算法求最长重复子串，返回其长度。*/ {int index=0,max=0; /*index记最长的串在s串中的开始位置，max记其长度*/ int length=1,i=0,start=0; /*length记局部重复子串长度，i为字符数组下标*/ while(i if(s[i]==s[i+1]) {i++; length++;} else /*上一个重复子串结束*/ {if(max /*初始化下一重复子串的起始位置和长度*/ } Printf(―最长重复子串的长度为:%d―;max;‖在串中的位置:%d‖;index); return(max); }/*算法结束*/ 算法中用i 算法的时间复杂度为O(n)，每个字符与其后继比较一次。 习题4 习题4 1．填空 （1）在计算机软件系统中，有两种处理字符串长度的方法：一种是采用 显式 ，第二种 是 隐式 。 （2）一个字符串相等的充要条件是 长度 和 对应字符都相等 。 （3）串是指 有限个字符组成 的序列；空串是指 长度 的串；空格串是指 一个或多个空格组成 的串。 （4）设s=―I︺AM︺A︺TEACHER‖,其长度是_14___。 （5）若n为主串长，m为子串长，则串的古典匹配算法最坏的情况下需要比较字符的总 次数为 ○（m*n） 。 2．空串和空格串有何区别？字符串中的空格符有何意义？空串在串的处理中有何作用？ 答：空串时长度为0的字符串；空格串是一个或多个字符组成的字符串。字符串中的空格符充当界符的作用。空串在串的处理中可作为任意串的子串。 3．设计一算法，将两个字符串连接起来，要求不能利用strcat（）函数。 答： Typedef struct {char *ch; /*串数组*/ int length; /*串长*/ }HString; int StrConcat(HString *S, HString T) { */ free(S->ch); S->ch=(char*)malloc(S->length+T.length); /* 为S分配新的空间*/ for(int i=0;i< S->length;i++)S->ch[i]=temp[i]; for(int j=0;j< T.length;j++)S->ch[i+j]=T.ch[j]; char *temp;temp=(char *)malloc(S->length); if(temp==NULL)return(0); for(int i=0;i /* 先把串S放入临时串temp中