Pop(s1,ch); }
//c[j++]=; c[j++]=0; return c; }
3.24③ 试编写如下定义的递归函数的递归算法: g(m,n) = 0 当m=0,n>=0 g(m,n) = g(m-1,2n)+n 当m>0,n>=0 并根据算法画出求g(5,2)时栈的变化过程。
int G(int m, int n)/* if m<0 or n<0 then return -1. */ {
int F;
if(m<0||n<0) return -1;
else if(m==0&&n>0) F=0; else if(m==0&&n==0) F=0; else if(m>0&&n>=0) F=G(m-1,2*n)+n; return F; } 3.25
int F(int n)
/* if n<0 then return -1. */ { int f;
if(n<0) return -1; else {
if(n==0) f=n+1; else f=n*F(n/2); return f; } }
3.25④ 试写出求递归函数F(n)的递归算法，并消除递归： F(n) = n+1 当n=0 F(n) = nF(n/2) 当n>0 实现下列函数： int F(int n);
/* if n<0 then return -1. */ int F(int n)
/* if n<0 then return -1. */ { int f;
if(n<0) return -1; else {
if(n==0) f=n+1; else f=n*F(n/2);
return f; }
}
◆3.28② 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针)，试编写相应的队列初始化、入队列和出队列的算法。 实现下列函数：
Status InitCLQueue(CLQueue &rear);
Status EnCLQueue(CLQueue &rear, ElemType x); Status DeCLQueue(CLQueue &rear, ElemType &x);
带头结点循环链队列CLQueue的类型为以下LinkList类型： typedef struct LNode{ ElemType data; struct LNode *next; } LNode, *LinkList;
typedef LinkList CLQueue;
Status InitCLQueue(CLQueue &rear) {
rear=(LNode*)malloc(sizeof(LNode)); rear->next=rear; return OK; }
Status EnCLQueue(CLQueue &rear, ElemType x) {
LinkList p;
p=(LNode*)malloc(sizeof(LNode)); p->data=x;
p->next=rear->next; rear->next=p; rear=p; return OK; }
Status DeCLQueue(CLQueue &rear, ElemType &x) { LinkList p;
if(rear->next!=rear ) {
p=rear->next;
rear->next=p->next; free(p);
return OK; }
else return ERROR; }
3.29③ 如果希望循环队列中的元素都能得到利用，则需设置一个标志域tag，并以tag的值为0或1来区分，尾指针和头指针值相同时的队列状态是\空\还是\满\。试编写与此结构相应的入队列和出队列的算法，并从时间和空间角度讨论设标志和不设标志这两种方法的使用范围（比如，当循环队列容量较小而队列中每个元素占的空间较多时，那一种方法较好？）。 实现下列函数：
Status EnCQueue(CTagQueue &Q, QElemType x); Status DeCQueue(CTagQueue &Q, QElemType &x); 本题的循环队列CTagQueue的类型定义如下： typedef char QElemType; typedef struct {
QElemType elem[MAXQSIZE]; int tag; int front; int rear; } CTagQueue;
Status EnCQueue(CTagQueue &Q, QElemType x) { int tag;
if(Q.front==Q.rear&&tag==1) return ERROR; Q.elem[Q.rear]=x;
Q.rear=(Q.rear+1)%MAXQSIZE; tag=1; return OK; }
Status DeCQueue(CTagQueue &Q, QElemType &x) { int tag;
if(Q.front==Q.rear&&tag==0) return ERROR; x=Q.elem[Q.front];
Q.front=(Q.front+1)%MAXQSIZE; if(Q.front==Q.rear) tag=0;
return OK; }
◆3.30② 假设将循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回队头元素）。 实现下列函数：
Status EnCQueue(CLenQueue &Q, QElemType x); Status DeCQueue(CLenQueue &Q, QElemType &x); 本题的循环队列CLenQueue的类型定义如下： typedef char QElemType; typedef struct {
QElemType elem[MAXQSIZE]; int length; int rear; } CLenQueue;
StatusEnCQueue(CLenQueue&Q, QElemType x) {
if(Q.length==MAXQSIZE) return ERROR;
Q.rear=(Q.rear+1)%MAXQSIZE; Q.elem[Q.rear]=x; Q.length++; return OK; }
Status DeCQueue(CLenQueue &Q, QElemType &x) {
if(Q.length==0)
return ERROR;
x=Q.elem[(Q.rear-Q.length+1+MAXQSIZE)%MAXQSIZE]; Q.length--; return x; }
◆3.31③ 假设称正读和反读都相同的字符序列为\回文\，例如，'abba'和'abcba'是回文，'abcde' 和'ababab'则不是回文。试写一个算法判别读入的一个以'@'为结束符的字符序列是否是\回文\。 实现下列函数：
Status Palindrome(char *word);
/* 利用栈和队列判定字符序列word是否是回文 */ 可使用栈Stack和队列Queue及其下列操作： Status InitStack(Stack &S); Status Push(Stack &S, ElemType x); Status Pop(Stack &S, ElemType &x); Status StackEmpty(Stack S); Status InitQueue(Queue &Q);
Status EnQueue(Queue &Q, ElemType x); Status DeQueue(Queue &Q, ElemType &x); Status QueueEmpty(Queue Q); Status Palindrome(char *word)
/* 利用栈和队列判定字符序列word是否是回文 */ {
Stack Q;
SElemType e,f; Queue S; char *p; p=word;
InitStack(Q); InitQueue(S); while(*p!='@') {
Push(Q,*p);EnQueue(S,*p); p++; }
while(!StackEmpty(Q))
{ Pop(Q,e); DeQueue(S,f);
if(e!=f)
return ERROR; }
return OK; }
第四章
4.10③ 编写对串求逆的递推算法。 要求实现以下函数：
void Reverse(StringType &s);/* Reverse s by iteration. */
StringType是串的一个抽象数据类型，它包含以下6种基本操作： void InitStr(StringType &s); // 初始化s为空串。
void StrAssign(StringType &t, StringType s); // 将s的值赋给t。s的实际参数是串变量。 int StrCompare(StringType s, StringType t);
// 比较s和t。若s>t，返回值>0；若s=t，返回值=0；若s // 返回s中的元素个数，即该串的长度。 StringType Concat(StringType &s, StringType t); // 返回由s和t联接而成的新串。 StringType SubString(StringType s, int start, int len); // 当1<=start<=StrLength(s)且0<=len<=StrLength(s)- start+1时， // 返回s中第start个字符起长度为len的子串，否则返回空串。 // 注意,不要使用 \的形式为 StringType 类型的变量赋值 , // 而要使用 StrAssign 函数!!! void Reverse(StringType &s) /* Reverse s by iteration. */ { int i=0,j=StrLength(s)-1; char temp; while(i<=j) { temp=s[i]; s[i]=s[j]; s[j]=temp; i++;j--; } } 4.12③ 编写一个实现串的置换操作Replace(&S,T,V)的算法。 要求实现以下函数： void Replace(StringType &S, StringType T, StringType V); /* 以串 v 置换串 s 中出现的所有和串 t 相同的非空串 */ StringType是串的一个抽象数据类型，它包含以下6种基本操作： void InitStr(StringType &s); // 初始化s为空串。 void StrAssign(StringType &t, StringType s);