《数据结构-用C语言描述第三版》课后答案第三章

撰写的内容可能有错误的地方，如果有错误或者疑问，欢迎评论区或者私信指正，我会及时改正

1．简述下列术语或概念：

(1）递归进层需要做的三件事。

保留本层参数与返回地址
为被调用函数的局部变量分配存储区，给下层参数赋值
将程序转移到被调用函数的入口

(2）递归退层需要做的三件事。

保存被调用函数的计算结果
释放被调用函数的数据区，恢复上层参数
依照被调用函数保存的返回地址，将控制转移回调用函数

(3）顺序队列的"假溢出"现象。

随着进队和入队，队头指针和队尾指针加1，最后出现队头指针和队尾指针指向超出顺序表索引，但是此时队列仍有空间的现象

(4）循环队列的判空、判满条件（少用一个空间区分队空队满）。

判空条件

rear == front

判满条件

(rear + 1) mod MAXSIZE == font

2．选择题

(1）输入序列为123，若进栈、出栈操作可以交替进行，则不能得到的出栈序列是（B）

A .321

B .312

C .123

D .132

(2）以下会用到栈的应用是（D)。

A ．递归

B ．子程序调用

C ．括号匹配

D ．以上选项均是

(3）栈和队列的共同点是（C)。

A ．都是先进先出

B ．都是先进后出

C ．只允许在端点处插入和删除元素

D ．它们没有共同点

(4）循环队列存储在数组 A [0.. m -1］中，则入队时 rear 应变化为（C)

A . rear ++

B . rear =( rear +1) mod ( m -1)

C . rear = (rear+1) mod m

D . rear = (rear + 1) mod (m+1)

(5）设有一个顺序共享栈 S [0.. n -1]，其中第一个栈项指针 topl 的初值为﹣1，第二个栈顶指针top2的初值为 n ，则判断共享栈满的条件是（C)

A . topl ==top2

B .top1+top2== n

C . topl +1==top2

D . topl -1==top2

3．按照四则运算加、减、乘、除和幂运算优先关系的惯例，画出对下列算术表达式求值时,算数栈和运算符栈的变化过程：

A-B*C/D+E^F

4．已知表达式为 $ab+(c-d/e)f$ :

(1）编写算法，将原表达式转换为后缀表达式 $ab*cde/-fx+$ 。

(2）编写算法，对转换后的后缀表达式进行求值。

答：(1)

此处编写了一个完整的可运行代码，但是程序可能不太稳定，qaq

#include<stdio.h>#define MaxSize 100
char ch[MaxSize] = "a*b+(c-d/e)*f";//定义栈和队列结构
typedef struct Stack{char data[MaxSize];int top;
}Stack;//定义栈的函数
//初始化
void initStack(Stack * s){s->top = -1;
}
//判空
int isEmptyStack(Stack *s){return s->top==-1;
}
//判满
int isFullStack(Stack *s){return s->top==MaxSize;
}
//出栈
char popStack(Stack * s){if(isEmptyStack(s))return '\0';return s->data[s->top--];
}
//入栈
int pushStack(Stack * s,char elem){if(isFullStack(s))return 0;s->data[++s->top] = elem;return 1;
}
//获取栈顶元素
char getTopStack(Stack *s){if(isEmptyStack(s))return '\0';return s->data[s->top];
}//定义队列
typedef struct Queue{char data[MaxSize];int rear;int front;
}Queue;//初始化
void initQueue(Queue *q){q->rear = 0;q->front= 0;
}
//判空
int isEmptyQueue(Queue *q){return q->rear == q->front;
}
//判满
int isFullQueue(Queue *q){return (q->rear+1)%MaxSize == q->front;
}// 入队
void enQueue(Queue *q, char elem) {if (isFullQueue(q))printf("queue is full!!!");q->data[q->rear++] = elem;return ;
}// 出队
char deQueue(Queue *q) {if (isEmptyQueue(q)){printf("queue is empty!!!");return '\0';}return q->data[q->front++];
}//比较优先级
int compare(char ch1,char ch2){if(ch1 == '+' || ch1 == '-'){if(ch2 == '+' || ch2 == '-')return 0;else{return -1;}}if(ch1 == '*' || ch1 == '/'){if(ch2 == '+' || ch2=='-'){return 1;}else{return 0;}}
}void transform(){int i = 13;printf("please input your function\n");//获取表达式//while(scanf("%c",&ch[i])&&ch[i]!='\n'&&i<MaxSize)//      i++;//将中缀表达式转换为后缀表达式/* 思路：*      初始化一个操作符栈和一个输出队列，一个运算符栈S，一个输出队列Q*      1.遇到操作数：  直接添加到输出队列*      2.遇到运算符：  a:如果S1为空，或者栈顶元素为'(',直接入栈*                      b:否则比较优先级*                              当前运算符比较级小于等于栈顶元素运算法与优先级，栈元素出栈并进入到输出队列*                              否则 入栈*                      c:如果为')',S出栈并进入输出队列，直到遇到'(',左右括号出栈后不添加到输出队列* *///理论结束 实战开始//初始化栈和队列for(int j = 0;j<i;j++){printf("%c",ch[j]);}printf("\n");Stack s;Queue q;initStack(&s);initQueue(&q);printf("------------\n");for(int j=0;j<i;j++){//printf("%c",ch[j]);switch(ch[j]){case '+':case '-':case '*':case '/':if(isEmptyStack(&s) || getTopStack(&s) == '('){pushStack(&s,ch[j]);}else{int compareResult = compare(ch[j],getTopStack(&s));if(compareResult !=1){//循环比较并出栈进入到输出队列do{char dataTop = popStack(&s);enQueue(&q,dataTop);}while(compare(ch[j],getTopStack(&s))!=1 && !isEmptyStack(&s));pushStack(&s,ch[j]);}else{pushStack(&s,ch[j]);}}break;case '(':pushStack(&s,ch[j]);break;case ')':while(getTopStack(&s)!='(')enQueue(&q,popStack(&s));popStack(&s);break;default:enQueue(&q,ch[j]);}}while(!isEmptyStack(&s)){enQueue(&q,popStack(&s));}//队列元素循环出队while(!isEmptyQueue(&q)){printf("%c",deQueue(&q));}
}void test(){Stack s;Queue q;initStack(&s);initQueue(&q);char ch4[] = {'a','b','c','d'};printf("------------");for(int i=0;i<4;i++){pushStack(&s,ch4[i]);enQueue(&q,ch4[i]);}printf("------------");while(!isEmptyStack(&s)){printf("%c",popStack(&s));}printf("\n");//队列元素循环出队while(!isEmptyQueue(&q)){printf("%c",deQueue(&q));}}int main(){//test();transform();return 0;
}

(2)

求出后缀表达式后。后缀表达式的求值只需要将后缀表达式数字依次入栈，遇到运算符出栈两个元素并计算，然后继续执行上述步骤

5．假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、人队列和出队列算法。

$ cat program5.c
/** 带头节点的循环链表表示队列，只设置一个尾指针，不设置* 头指针，编写相应的队列初始化、入队、出队算法* */typedef struct QueueNode{int data;struct QueueNnode *next;
}Queue;void initStruct(Queue *q){q = NULL;
}int enQueue(Queue *q,int elem){if(isFullQueue(q))return 0;struct QueueNode *node = (struct QueueNode *)malloc(sizeof(struct QueueNode));node->data = elem;if(q==NULL){//队列为空q = node;q->next = next;}else{node->next = q->next;q->next = node;q = node;}return 1;}int deQueue(Queue *q,int elem){if(isEmptyQueue(q))return 0;struct QueueNode *node = q->next;//q是尾指针，则q->next对应头结点struct QueueNode *s = node->next;//要删除的结点if(s == node){//只有一个结点free(s);q = NULL: }else{node->next = s->next;free(s);}return 1;
}

6．要求循环队列不损失一个空间全部都能得到利用，设置一个标志域 tag ，以 tag 为0或1来区分头尾指针相同时的队列状态的空与满，试编写与此结构相应的人队与出队算法。

/*
要求循环队列不损失一个空间全部都能得到利用，设置一个标志域 tag ，
以 tag 为0或1来区分头尾指针相同时的队列状态的空与满，试编写与此结
构相应的人队与出队算法。
*/#define  MaxSize 100
typedef struct Queue{int tag;                //标志域 tag == 1 为满 tag == 0 为空int data[MaxSize];      //数据域int front,rear;         //首尾指针}Queue;void InitQueue(Queue *q){q->front = 0;q->rear = 0;q->tag = 0;
}void enQueue(Queue *q,int elem){if(tag){printf("队满！！！")return;}q->data[q->rear] = elem;q->rear++;q->rear %= MaxSize;if(q->rear == q->front){q->tag = 1;}
}int deQueue(Queue *q){if(!tag){printf("队空！！！")；return -1;}int temp = q->data[q->front];q->front++;q->front%=MaxSize;if(q->front == q->rear)tag = 0;return temp;
}

7．设有4个元素1、2、3、4依次进栈，而出栈操作可随时进行（进出栈可任意交错进行，但要保证进栈次序不破坏1、2、3、4的相对次序），试写出所有不可能的出栈次序和所有可能的出栈次序。

四个元素1、2、3、4的排序种类有4*3*2*1=24种

依次为

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

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

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

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

红色为不可能的出栈顺序，黑色为可能的出栈顺序

n个元素进栈，可能的出栈顺序有 $\frac{1}{n+1} C^n_{2n}$

则四个元素进栈可能的出栈顺序有14种

8．已知递归函数如下：

$g(m,n) = \left\{\begin{matrix} 0, & m=0,n>=0 \\ g(m-1,2n)+n,&m>0,n>=0 \end{matrix}\right.$

（1）编写递归算法

int funcG(int m,int n){if(m == 0)return 0;return funcG(m-1,2*n)+n;
}

（2）给出g(3,5)的递归执行过程图示

（3）将递归算法改写为非递归算法

int funcG(int m,int n){int sum = 0;while(m!=0){sum+=n;n*=2;m--;}return sum;
}

9．有如下函数定义：

void bin(int b[],int n){if(n==1){b[1] = 2;b[2] = 2;}else{bin(b,n-1);b[n+1] = 2;for(int i=n;i>=2;i--){b[i] = b[i]+b[i-1];}}
}

若调用 bin ( A ,5)，给出 A 数组中第1个到第6个数组元素的值。

答：

数组中的值为

2 10 20 20 10 2

每次递归将后面一个元素赋值为2，然后前面的元素分别加等其前面的元素

10．分析汉诺塔问题的时间复杂度。

假设柱子编号为 A B C

执行步骤：

（1）将上面的n-1个盘子从A经过C移动到B；

（2）将编号为n的盘子从A移到C；

（3）将B上的n-1个盘子经过A移动到C

此时需要先将B上的n-2个盘子经过C移动到A,然后将第n-1个盘子从B移动到C

设ai 为有i个盘子时需要移动的次数

则

a1 = 1

a2 = 3

a3 = $2*a_{2}+1$ = 7

a4 = $2*a_{3}+1$ = 15

.......

an = $2*a_{n-1}+1$ = $2^{n}-1$

为什么？

根据移动的三个步骤：

n个盘子时

将n-1个盘子从一个柱子经另一个柱子移动到剩余的柱子需要 $a_{n-1}$ 步

将编号为n的盘子从A移动到C 需要1步

将n-1个盘子从一个柱子经另一个柱子移动到剩余的柱子需要 $a_{n-1}$ 步

则 an = $2*a_{n-1}+1$