数据结构上机作业1-5章(6)

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 …… 此处隐藏：1847字，全部文档内容请下载后查看。喜欢就下载吧 ……