发布时间 : 星期六 文章数据结构(C语言版)例题(第三章：栈和队列)更新完毕开始阅读
return s; }
◆3.25④ 试写出求递归函数F(n)的递归算法， 并消除递归：
F(n) = n+1 当n=0 F(n) = nF(n/2) 当n>0
实现下列函数： int F(int n);
int F(int n) {int s;
if(n<0) return -1; if(n==0) s=n+1; else {
s=n*F(n/2); }
return s; }
◆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=(CLQueue)malloc(sizeof(LNode)); rear->next=rear; return (OK);
}
Status EnCLQueue(CLQueue &rear, ElemType x) {LinkList p;
p=(CLQueue)malloc(sizeof(LNode)); p->data=x;
p->next=rear->next; rear->next=p; rear=p; return OK;
}
Status DeCLQueue(CLQueue &rear, ElemType &x) {LinkList q;
if(rear==rear->next) return ERROR ; q=rear->next->next; x=q->data;
rear->next->next=q->next; free(q); return OK;
} ◆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) {if(Q.rear==Q.front&&Q.tag==1) return ERROR; else
{
Q.elem[Q.rear]=x; Q.rear++;
if(Q.rear==Q.front) Q.tag=1; return OK; }
}
Status DeCQueue(CTagQueue &Q, QElemType &x) { if(Q.rear==Q.front&&Q.tag==0) return ERROR; else {
x=Q.elem[Q.front]; Q.front++;
if(Q.rear==Q.front) Q.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;
Status EnCQueue(CLenQueue &Q, QElemType x) {if(Q.length==MAXQSIZE) return ERROR; else {
Q.rear=Q.rear+1; Q.elem[Q.rear]=x; Q.length++; return OK; }
}
Status DeCQueue(CLenQueue &Q, QElemType &x) { if(Q.length==0) return ERROR; else {
int front; //？
front=front+1; //？
//另一作者的； ——dlgcy
head=(Q.rear-Q.length+1)%MAXSIZE; //详见书后注释 x=Q.base[head]; //
Q.length--; return OK; }
}
◆3.31③ 假设称正读和反读都相同的字符序列为 \回文\，例如，'abba'和'abcba'是回文，'abcde' 和'ababab'则不是回文。试写一个算法判别读入的 一个以'@'为结束符的字符序列是否是\回文\。
实现下列函数：
Status Palindrome(char *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) { char a,b; Stack S; Queue Q; InitStack(S); InitQueue(Q); while(*word!='@') {
Push(S,*word);
EnQueue(Q,*word); word++;