第三次作业
1.假设正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’ 和‘ababab’则不是回文。假设一字符序列已存入计算机，请分析用线性表、堆栈和队列等方式正确输出其回文的可能性？
2.顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？
3.设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有
① front=11，rear=19;② front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？
4.试将下列递归过程改为非递归过程。
void test(int &sum){
int x;
Sanf(x);
if(x= =0) sum=0;
else {test(sum);sum+=x;}
printf(sum);
}
1.假设正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’ 和‘ababab’则不是回文。假设一字符序列已存入计算机，请分析用线性表、堆栈和队列等方式正确输出其回文的可能性？
答：线性表是随机存储，可以实现，靠循环变量（j--）从表尾开始打印输出；
堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可；
队列是先进先出，不易实现。
哪种方式最好，要具体情况具体分析。若正文在机内已是顺序存储，则直接用线性表从后往前读取即可，或将堆栈栈顶开到数组末尾，然后直接用POP动作实现。（但堆栈是先减后压还是„„）
若正文是单链表形式存储，则等同于队列，需开辅助空间，可以从链首开始入栈，全部压入后再依次输出。
2.顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？
答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。
采用循环队列是解决假溢出的途径。
另外，解决队满队空的办法有三：
① 设置一个布尔变量以区别队满还是队空；
② 浪费一个元素的空间，用于区别队满还是队空。
③ 使用一个计数器记录队列中元素个数（即队列长度）。
我们常采用法②，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。
判断循环队列队空标志是： f=rear队满标志是：f=(r+1)%N
3.设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有
① front=11，rear=19;② front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？
答：用队列长度计算公式：(N＋r－f)% N
① L=（40＋19－11）% 40=8② L=（40＋11－19）% 40=32
4.参考程序：
void test(int &sum){
Stack S;
int x;
Sanf(x);
InitStack(S);
While(x){
Push(S,x);
Scanf(x);
}
sum=0;
printf(sum);
while(Pop(S,x)){
sum+=x;
printf(sum);
}
}
