数据结构与算法课后习题解答(2)

p->next=q->next; q->next->prior=p;// 将p

p->prior=q; q->next=p；

}

} // 算法结束

第三章 )

//

//

3.1 1 2 3 4 2 1 3 4 3 2 1 4 4 3 2 1

1 2 4 3 2 1 4 3 3 2 4 1

1 3 2 4 2 3 1 4 3 4 2 1

1 3 4 2 2 3 4 1

数据结构与算法课后习题解答

1 4 3 2 2 4 3 1

设入栈序列元素数为n，则可能的出栈序列数为C2nn=(1/n+1)*(2n!/(n!)2)

3.2 证明：由j<k和pj<pk 说明pj在pk之前出栈，即在k未进栈之前pj已出栈，之后k进栈，然后pk出栈；由j<k和pj>pk 说明pj在pk之后出栈，即pj被pk 压在下面，后进先出。由以上两条，不可能存在i<j<k使pj<pk<pi。也就是说，若有1，2，3顺序入栈，不可能有3，1，2的出栈序列。

3.3 void sympthy(linklist *head, stack *s)

//判断长为n的字符串是否中心对称

{ int i=1; linklist *p=head->next;

while (i<=n/2) // 前一半字符进栈

{ push(s,p->data); p=p->next; }

if (n % 2 !==0) p=p->next;// 奇数个结点时跳过中心结点

while (p && p->data==pop(s)) p=p->next;

if (p==null) printf()；

else printf()

} // 算法结束 3.4

//

（init s;//初始化栈s

scanf(“%c”,&ch);

while (ch!=’#’) //’#’是表达式输入结束符号

switch (ch)

, case ’(’: push(s,ch); break;

数据结构与算法课后习题解答

case ’)’: if (empty(s)) {printf(“括号不配对”); exit(0);}

pop(s); }

if (!empty(s)) printf(“括号不配对”);

else printf(“括号配对”);

} // 算法结束 3.5

typedef struct // 两栈共享一向量空间

{ ElemType v[m]; // 栈可用空间0—m-1

int top[2] // 栈顶指针

}twostack;

int

// ,i0或1，表示两个栈，x是进栈元素，

//

栈满

else {switch (i)

{case 0: s->v[++(s->top)]=x; break;

case 1: s->v[--(s->top)]=x; break;

default: printf(“栈编号输入错误”); return(0);

}

数据结构与算法课后习题解答

return(1); // 入栈成功

}

} // 算法结束

ElemType pop(twostack *s,int i)

// 两栈共享向量空间,i是0或1，表示两个栈，本算法是退栈操作

{ ElemType x;

if (i!=0 && i!=1) return(0);// 栈编号错误

else {switch (i)

{case 0: if(s->top[0]==-1) return(0);//栈空

else x=s->v[s->top--];break;

case 1: if(s->top[1]==m) return(0);//

else x=s->v[s->top++]; break;

default: printf();return(0);

}

// 退栈成功

ElemType top (twostack *s,int i)

// 两栈共享向量空间,i是0或1，表示两个栈，本算法是取栈顶元素操作

{ ElemType x;

switch (i)

数据结构与算法课后习题解答

{case 0: if(s->top[0]==-1) return(0);//栈空

else x=s->v[s->top]; break;

case 1: if(s->top[1]==m) return(0);//栈空

else x=s->v[s->top]; break;

default: printf(“栈编号输入错误”);return(0);

}

return(x); // 取栈顶元素成功

} // 算法结束 3．6

void Ackerman(int m,int n)

// Ackerman 函数的递归算法

{ if (m==0) return(n+1);

} //

3．7

(1) linklist *init(linklist *q)

// q是以带头结点的循环链表表示的队列的尾指针，本算法将队列置空

{ q=(linklist *)malloc(sizeof(linklist));//申请空间，不判断空间溢出

q->next=q;

数据结构与算法课后习题解答

return (q);

} // 算法结束

(2) linklist *enqueue(linklist *q，ElemType x)

// q是以带头结点的循环链表表示的队列的尾指针，本算法将元素x入队

{ s=(linklist *)malloc(sizeof(linklist));//申请空间，不判断空间溢出

s->next=q->next; // 将元素结点s入队列

q->next=s;

q=s; // 修改队尾指针

return (q);

} // 算法结束

(3) linklist *delqueue(linklist *q)

//q

指向出队元素

// 若队列中只一个元素，置空队列

修改队头元素指针

// 释放出队结点 }

return (q);

} // 算法结束。算法并未返回出队元素 3.8

数据结构与算法课后习题解答

typedef struct

{ElemType data[m];// 循环队列占m个存储单元

int front,rear; // front和rear为队头元素和队尾元素的指针

// 约定front指向队头元素的前一位置，rear指向队尾元素

}sequeue;

int queuelength(sequeue *cq)

// cq为循环队列，本算法计算其长度

{ return (cq->rear - cq->front + m) % m;

} // 算法结束 3.9

typedef struct

{ElemType sequ[m];//

int rear,quelen; ,quelen为元素个数

}sequeue;

{ return (cq->quelen==0 ? 1: 0);

} // 算法结束

(2) sequeue *enqueue(sequeue *cq，ElemType x)

// cq是如上定义的循环队列，本算法将元素x入队

{if (cq->quelen==m) return(0); // 队满

数据结构与算法课后习题解答

else { cq->rear=(cq->rear+1) % m; // 计算插入元素位置

cq->sequ[cq->rear]=x; // 将元素x入队列

cq->quelen++; // 修改队列长度

}

return (cq);

} // 算法结束

ElemType delqueue(sequeue *cq)

// cq

{if (cq->quelen==0) return(0); // 队空

else { int front=(cq->rear - cq->quelen + 1+m) % m;//

cq->quelen--; //

return (cq->sequ[front]); //

}

} // 算法结束

参考答案)

在以下习题解答中，假定使用如下类型定义：

#define MAXSIZE 1024

typedef struct

{ char data[MAXSIZE];

数据结构与算法课后习题解答

int curlen; // curlen表示终端结点在向量中的位置

}seqstring;

typedef struct node

{char data;

struct node *next ；

}linkstring;

4.2 int index(string s,t)

//s,t是字符串，本算法求子串t在主串ss串中包含t串，返回其

//第一个字符在s中的位置，否则返回0

{m=length(s); n=l …… 此处隐藏：2851字，全部文档内容请下载后查看。喜欢就下载吧 ……