数据结构教程习题答案-李蓉蓉-安杨等编著第三版-第六章答案.doc

6.1
/*********************************************
题目：已知A[n]为整数数组，编写一个递归算法求n个元素的平均值
设计：狼影
时间;2012.10.1
*****************************************************/
# include <stdio.h>
# define size 100

float sum = 0;
//函数声明
float cal_average(int *a,int i,int n);

main()
{
int n;
int i;
float average;
int a[size];

//输入数据的个数
printf("输入数据的个数\n");
scanf("%d", &n);

//输入n个数据
printf("输入数据\n");
for(i = 0; i<n; i++)
scanf("%d", &a[i]);

//求平均数
average = cal_average(a,0,n);
printf("平均数数%f\n", average);
}

//递归求平均数
float cal_average(int *a,int i,int n)
{
if(i>=n)
return (sum/n);
else
{
sum += a[i];
return (cal_average(a, i+1, n));
}
}

/***************************************
输入数据的个数
5
输入数据
1 2 3 4 5
平均数数3.000000
Press any key to continue
**********************************************/

6.2
/*******************************
题目;有一个不带表头结点的单链表，设计如下的递归算法：（下面的代码实现的顺序为了方便可能与问题的顺序不一致）
1.求以h为头指针的单链表的节点的个数
2.正向显示以h为头指针的单链表的所有节点值
3.反向显示以h为头指针的单链表的所有节点值
4.删除以h为头指针的单链表中值为x的第一个节点
5.删除以h为头指针的单链表中值为x的所有节点
6.输出以h为头指针的单链表中最大节点值
7.输出以h为头指针的单链表中最小节点值

设计;狼影
时间：2012.10.1
************************************************/

# include <stdio.h>
# include <stdlib.h>
//节点类型按课本上的来写
typedef int ElemType;
typedef struct node
{
ElemType data;
struct node *next;
}NODE;

int number = 0;
//函数声明
NODE *creat_list(void);
void front_output(NODE *pHead);
void back_output(NODE *pHead);
int node_number(NODE *pHead);
int cal_max(NODE *pHead);
int cal_min(NODE *pHead);
NODE *delete_x(NODE *pHead, int x);
NODE *delete_all_x(NODE *pHead, int x);

main()
{
NODE *pHead;
int max, min;
int number, x;
int sert;
//首先先创建一个链表
printf("输入数据按0结束\n");
pHead = creat_list();

if(pHead!=NULL)
{
//下面正向输出内容
printf("正向输出的结果是\n");
front_output(pHead);
printf("\n");

//反向输出链表内容
printf("反向输出的结果是\n");
back_output(pHead);
printf("\n");

//求节点的个数
number = node_number(pHead);
printf("节点的个数是%d\n", number);

//输出最大值
max = cal_max(pHead);
printf("最大值是%d\n", max);

//求最小值
min = cal_min(pHead);
printf("最小值是%d\n", min);

//删除链表中值为x的第一个元素
printf("输入删除的元素值\n");
scanf("%d", &x);
do
{
printf("删除所有的x按1， 首个x按0\n");
scanf("%d", &sert);
}while(sert<0||sert>1);

switch(sert)
{
case 0:
pHead = delete_x(pHead, x);
printf("剩余的节点是\n");
front_output(pHead);
printf("\n");
break;
case 1:
pHead = delete_all_x(pHead, x);
printf("剩余的节点是\n");
front_output(pHead);
printf("\n");
break;
}
}
else
printf("链表为空\n");

}

//递归创建链表
NODE *creat_list(void)
{
ElemType n;
NODE *pNow;

scanf("%d", &n);
if(0==n)
return NULL;
else
{
pNow = (NODE *)malloc(sizeof(NODE));
if(NULL==pNow)
{
printf("内存分配失败\n");
exit(-1);
}
pNow->data = n;
pNow->next = creat_list();
}
return pNow;
}

//正向输出链表内容
void front_output(NODE *pHead)
{
if(NULL==pHead)
return;
else
{
printf("%d ", pHead->data);
front_output(pHead->next);
}
}

//反向输出链表的内容
void back_output(NODE *pHead)
{
if(NULL == pHead)
return;
else
{
back_output(pHead->next);
printf("%d ", pHead->data);
}
}

//求节点的个数
int node_number(NODE *pHead)
{
if(NULL==pHead)
return 0;
else
return (node_number(pHead->next)+1);
}

//求最大值
int cal_max(NODE *pHead)
{
int max, max1;

if(pHead->next==NULL)
max = pHead->data;
else
{
max = pHead->data;
max1 = (cal_max(pHead->next));
max = (max>max1)? max:max1;
}
return max;
}

//求最小值
int cal_min(NODE *pHead)
{
int min, min1;

if(pHead->next == NULL)
min = pHead->data;
else
{
min = pHead->data;
min1 = cal_min(pHead->next);
min = (min<min1)? min:min1;
}
return min;
}

//删除值为x的第一个值
NODE *delete_x(NODE *pHead, int x)
{
NODE *pNow;

//下面是把等于x节点之前的链断开，重新连接，把等于x节点之后的一部分链直接接到新形成的链的后面
if(pHead != NULL)
{
if(pHead->data != x)
{
pHead->next = delete_x(pHead->next, x);
return pHead;
}
else
{
pNow = pHead;
pHead = pHead->next;
free(pNow);
return pHead;
}
}
}

//删除所有的x节点
NODE *delete_all_x(NODE *pHead, int x)
{
NODE *pNow;

if(pHead!=NULL)
{
if(pHead->data!=x)
{
pHead->next = delete_all_x(pHead->next, x);
return pHead;
}
else
{
pNow = pHead;
pHead = pHead->next;
free(pNow);
return delete_all_x(pHead, x);
}
}
else
return NULL;
}

/*****************************************
输入数据按0结束
1 2 3 4 2 7 2
0
正向输出的结果是
1 2 3 4 2 7 2
反向输出的结果是
2 7 2 4 3 2 1
节点的个数是7
最大值是7
最小值是1
输入删除的元素值
2
删除所有的x按1， 首个x按0
1
剩余的节点是
1 3 4 7
Press any key to continue
*********************************************************/

//另加皇后的问题（仅供参考）
/******************************************
题目：采用递归求解皇后的问题(n*n)
实践：狼影
时间：2012.10.1
*******************************************/
# include <stdio.h>
# include <math.h>
# define size 20

//函数的声明
void place(int row,int n);
bool is_set(int row, int i);
void print(int n);

int set[size];
int number = 0;
main()
{
int n;
printf("输入n的大小\n");
scanf("%d", &n);
place(0,n);
printf("八皇后安放的方式有%d种\n", number);
}

//安放皇后
void place(int row,int n)
{
int i;

if(row>=n)
{
print(n);
number++;
fflush(stdin);
getchar();

}
for(i = 0; i<n; i++)
{
if(is_set(row, i))
{
set[row] = i;
place(row+1, n);
}
}
}

//判断是不是能安放皇后
bool is_set(int row, int i)
{
int j;

for(j = 0; j<row; j++)
{
if(set[j]==i || abs(row-j)==abs(i-set[j]))
return 0;
}
return true;
}

//输出
void print(int n)
{
int i, j;
int a[size][size];

for(i = 0; i<n; i++)
{
for(j = 0; j<n; j++)
{
if(set[i]==j)
printf("9 ");
else
printf("0 ");
}
printf("\n");
}
}
/************************
输入n的大小
4
0 9 0 0
0 0 0 9
9 0 0 0
0 0 9 0

0 0 9 0
9 0 0 0
0 0 0 9
0 9 0 0

八皇后安放的方式有2种
Press any key to continue
***************************************/

//迷宫的问题
/****************************
题目：用栈输出所有可能的迷宫路径，并求最短路径长度与最短的路径
实践：狼影
时间：2012.9.18
**************************************/

/************************************\
此题可以用递归很简单的就输出所有的路径，不过下面用自己建栈的方式
***********************************************/

# include <stdio.h>
# include <stdlib.h>
# define size 256

char map[10][10] = { {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
{'#', '0', '0', '0', '0', '0', '0', '0', '0', '#'},
{'#', '#', '0', '#', '#', '#', '0', '#', '0', '#'},
{'#', '#', '0', '#', '0', '0', '0', '#', '0', '#'},
{'#', '0', '0', '0', '0', '0', '0', '#', '0', '#'},
{'#', '0', '#', '#', '0', '#', '0', '0', '0', '#'},
{'#', '0', '#', '#', '0', '0', '0', '#', '#', '#'},
{'#', '0', '#', '#', '#', '0', '0', '0', '0', '#'},
{'#', '0', '0', '0', '0', '0', '#', '#', '0', '#'},
{'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'}
};

//定义节点
typedef struct
{

int x;
int y;
int di;
}STATE;

typedef struct
{
STATE state[size];
int top;
}STACK;

int sin = 0; //标记是不是有路径
int number = 0;
int max = 65535;
int clea;
STATE arry[size];//存放最短路径
STATE cl[size];//存放最后的一条路径
//函数的声明
STACK *init_stack(void);
void find_path(STACK *stack);
void push_stack(STACK *stack, STATE st);
bool is_empty(STACK *stack);
void get_top(STACK *stack, STATE *st);
bool is_through(STATE st);
void pop_stack(STACK *stack);
void print_map(void);
void shortest_path(STACK *stack);
void clear_map(void);
void re_paint(void);

main()
{
STACK *stack;

stack = init_stack();
printf("地图的入点是（1,1）出口点是(8,8)\n");
find_path(stack);
if(0 == sin)
printf("没有路径\n");
else
{
printf("一共有%d条路径\n", number);
printf("最短路径是\n");
re_paint();
print_map();
printf("\n");
}
}

//寻找路径
void find_path(STACK *stack)
{

//将入口点入栈
STATE st;
st.x = 1;
st.y = 1;
st.di = -1;
push_stack(stack, st);
map[st.x][st.y] = '\1';

while(!is_empty(stack))
{
get_top(stack, &st);
if(8==st.x && 8==st.y)
{
sin = 1;//有路径的话sin标记为1
print_map();
printf("\n");
number++;
shortest_path(stack);
map[stack->state[stack->top].x][stack->state[stack->top].y] = '0';
pop_stack(stack);

}
else
{
while(st.di<4 && !is_through(st))//当 当前点的四个方向没有浏览完并且浏览的方向不通时，循环
{
st.di++;
switch(st.di) //改变方向（有上下左右四个方向）
{
case 0: st.x = stack->state[stack->top].x-1;
st.y = stack->state[stack->top].y;
break;
case 1: st.x = stack->state[stack->top].x;
st.y = stack->state[stack->top].y+1;
break;
case 2: st.x = stack->state[stack->top].x+1;
st.y = stack->state[stack->top].y;
break;
case 3: st.x = stack->state[stack->top].x;
st.y = stack->state[stack->top].y-1;
break;
default: break;

}
}

stack->state[stack->top].di = st.di; //记录当前点走向哪个方向的相邻点
if(is_through(st))
{

st.di = -1;
push_stack(stack, st);
map[st.x][st.y] = '\1';
}
else
{
map[stack->state[stack->top].x][stack->state[stack->top].y] = '0';
pop_stack(stack);

}
}
}
}

//初始化队列
STACK *init_stack(void)
{
STACK *stack = (STACK *)malloc(sizeof(STACK));
if(NULL == stack)
{
printf("内存分配失败\n");
exit(-1);
}
stack->top = -1;
return stack;
}
//入队列
void push_stack(STACK *stack, STATE st)
{
stack->top++;

stack->state[stack->top].di = st.di;
stack->state[stack->top].x = st.x;
stack->state[stack->top].y = st.y;

}

//判断空
bool is_empty(STACK *stack)
{
if(-1 == stack->top)
return true;
else
return false;
}

//获得栈顶元素
void get_top(STACK *stack, STATE *st)
{
if(is_empty(stack))
{
printf("栈空\n");
return;
}
st->x = stack->state[stack->top].x;
st->y = stack->state[stack->top].y;
st->di = stack->state[stack->top].di;
}

//判断是不是可以通过
bool is_through(STATE st)
{
if('0' == map[st.x][st.y])
return true;
else
return false;
}

//出栈操作
void pop_stack(STACK *stack)
{
if(is_empty(stack))
{
printf("栈空\n");
return;
}
else
{
stack->top--;
}
}

//打印地图
void print_map(void)
{
int i, j;

for(i = 0; i<10; i++)
{
for(j = 0; j<10; j++)
{
printf("%c ", map[i][j]);
}
printf("\n");
}
}

//寻找最短路径
void shortest_path(STACK *stack)
{

int i;

//记录最后的路径，为了清除重绘
for(i = 0; i<=stack->top; i++)
{
cl[i] = stack->state[i];
}
clea = stack->top;

//记下最短的路径坐标
if(stack->top <max)
{
max = stack->top;
for(i = 0; i<=stack->top; i++)
{
arry[i] = stack->state[i];
}

}
}

//绘制最短路径地图
void re_paint(void)
{
int i;

clear_map();
for(i = 0; i<=max;i++)
{
map[arry[i].x][arry[i].y] = '\1';
}
}

//将地图还原
void clear_map(void)
{
int i;

for(i = 0; i<=clea; i++)
{
map[cl[i].x][cl[i].y] = '0';
}
}