3、 if(i>=n)
return (sum/n);
else
{
sum += a[i];
return (cal_average(a, i+1, n));
}
}
/***************************************
輸入數(shù)據(jù)的個(gè)數(shù)
5
輸入數(shù)據(jù)
1 2 3 4 5
平均數(shù)數(shù)3.000000
Press any key to continue
**********************************************/
6.2
/*****************************
4、**
題目;有一個(gè)不帶表頭結(jié)點(diǎn)的單鏈表，設(shè)計(jì)如下的遞歸算法：（下面的代碼實(shí)現(xiàn)的順序?yàn)榱朔奖憧赡芘c問題的順序不一致）
1.求以h為頭指針的單鏈表的節(jié)點(diǎn)的個(gè)數(shù)
2.正向顯示以h為頭指針的單鏈表的所有節(jié)點(diǎn)值
3.反向顯示以h為頭指針的單鏈表的所有節(jié)點(diǎn)值
4.刪除以h為頭指針的單鏈表中值為x的第一個(gè)節(jié)點(diǎn)
5.刪除以h為頭指針的單鏈表中值為x的所有節(jié)點(diǎn)
6.輸出以h為頭指針的單鏈表中最大節(jié)點(diǎn)值
7.輸出以h為頭指針的單鏈表中最小節(jié)點(diǎn)值
設(shè)計(jì);狼影
時(shí)間：2012.10.1
**********************************************
5、**/
# include
# include
//節(jié)點(diǎn)類型按課本上的來寫
typedef int ElemType;
typedef struct node
{
ElemType data;
struct node *next;
}NODE;
int number = 0;
//函數(shù)聲明
NODE *creat_list(void);
void front_output(NODE *pHead);
void back_output(NODE *pHead);
int node_number(NODE *pHe
6、ad);
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;
//首先先創(chuàng)建一個(gè)鏈表
printf("輸入數(shù)據(jù)按0結(jié)束\n");
pHead = creat_list();
if(pHead!=NULL)
{
/
7、/下面正向輸出內(nèi)容
printf("正向輸出的結(jié)果是\n");
front_output(pHead);
printf("\n");
//反向輸出鏈表內(nèi)容
printf("反向輸出的結(jié)果是\n");
back_output(pHead);
printf("\n");
//求節(jié)點(diǎn)的個(gè)數(shù)
number = node_number(pHead);
printf("節(jié)點(diǎn)的個(gè)數(shù)是%d\n", number);
//輸出最大值
max = cal_max(pHead);
printf("最大值是%d\n", m
8、ax);
//求最小值
min = cal_min(pHead);
printf("最小值是%d\n", min);
//刪除鏈表中值為x的第一個(gè)元素
printf("輸入刪除的元素值\n");
scanf("%d", &x);
do
{
printf("刪除所有的x按1， 首個(gè)x按0\n");
scanf("%d", &sert);
}while(sert<0||sert>1);
switch(sert)
{
case 0:
pHead = delete_x(pHead, x);
9、 printf("剩余的節(jié)點(diǎn)是\n");
front_output(pHead);
printf("\n");
break;
case 1:
pHead = delete_all_x(pHead, x);
printf("剩余的節(jié)點(diǎn)是\n");
front_output(pHead);
printf("\n");
break;
}
}
else
printf("鏈表為空\n");
}
//遞歸創(chuàng)建鏈表
NODE *creat_list(void)
{
ElemTy
10、pe n;
NODE *pNow;
scanf("%d", &n);
if(0==n)
return NULL;
else
{
pNow = (NODE *)malloc(sizeof(NODE));
if(NULL==pNow)
{
printf("內(nèi)存分配失敗\n");
exit(-1);
}
pNow->data = n;
pNow->next = creat_list();
}
return pNow;
}
//正向輸出鏈表內(nèi)容
void front_output(NODE *pHead
11、)
{
if(NULL==pHead)
return;
else
{
printf("%d ", pHead->data);
front_output(pHead->next);
}
}
//反向輸出鏈表的內(nèi)容
void back_output(NODE *pHead)
{
if(NULL == pHead)
return;
else
{
back_output(pHead->next);
printf("%d ", pHead->data);
}
}
//求節(jié)點(diǎn)的個(gè)數(shù)
int node_number(
12、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;
13、
}
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
14、 NODE *pNow;
//下面是把等于x節(jié)點(diǎn)之前的鏈斷開，重新連接，把等于x節(jié)點(diǎn)之后的一部分鏈直接接到新形成的鏈的后面
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
15、節(jié)點(diǎn)
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);
}
}
16、else
return NULL;
}
/*****************************************
輸入數(shù)據(jù)按0結(jié)束
1 2 3 4 2 7 2
0
正向輸出的結(jié)果是
1 2 3 4 2 7 2
反向輸出的結(jié)果是
2 7 2 4 3 2 1
節(jié)點(diǎn)的個(gè)數(shù)是7
最大值是7
最小值是1
輸入刪除的元素值
2
刪除所有的x按1， 首個(gè)x按0
1
剩余的節(jié)點(diǎn)是
1 3 4 7
Press any key to continue
***************************************************
17、******/
//另加皇后的問題（僅供參考）
/******************************************
題目：采用遞歸求解皇后的問題(n*n)
實(shí)踐：狼影
時(shí)間：2012.10.1
*******************************************/
# include
# include
# define size 20
//函數(shù)的聲明
void place(int row,int n);
bool is_set(int row, int i);
void print(
18、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 =
19、0; i
20、 i, j;
int a[size][size];
for(i = 0; i
21、放的方式有2種
Press any key to continue
***************************************/
//迷宮的問題
/****************************
題目：用棧輸出所有可能的迷宮路徑，并求最短路徑長度與最短的路徑
實(shí)踐：狼影
時(shí)間：2012.9.18
**************************************/
/************************************\
此題可以用遞歸很簡單的就輸出所有的路徑，不過下面用自己建棧的方式
********
22、***************************************/
# include
# include
# define size 256
char map[10][10] = { {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
{'#', '0', '0', '0', '0', '0', '0', '0', '0', '#'},
{'#', '#', '0', '#', '#', '#', '0', '#', '0', '#
23、'},
{'#', '#', '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', '#'},
24、 {'#', '0', '0', '0', '0', '0', '#', '#', '0', '#'},
{'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'}
};
//定義節(jié)點(diǎn)
typedef struct
{
int x;
int y;
int di;
}STATE;
typedef struct
{
STATE state[size];
int top;
}STACK;
int sin = 0; //標(biāo)記是不是有路徑
int number =
25、0;
int max = 65535;
int clea;
STATE arry[size];//存放最短路徑
STATE cl[size];//存放最后的一條路徑
//函數(shù)的聲明
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 p
26、op_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("地圖的入點(diǎn)是（1,1）出口點(diǎn)是(8,8)\n");
find_path(stack);
if(0 == sin)
printf("沒有路徑\n");
else
{
printf("一共有%
27、d條路徑\n", number);
printf("最短路徑是\n");
re_paint();
print_map();
printf("\n");
}
}
//尋找路徑
void find_path(STACK *stack)
{
//將入口點(diǎn)入棧
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(stac
28、k, &st);
if(8==st.x && 8==st.y)
{
sin = 1;//有路徑的話sin標(biāo)記為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))//當(dāng) 當(dāng)
29、前點(diǎn)的四個(gè)方向沒有瀏覽完并且瀏覽的方向不通時(shí)，循環(huán)
{
st.di++;
switch(st.di) //改變方向（有上下左右四個(gè)方向）
{
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;
30、 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 = s
31、t.di; //記錄當(dāng)前點(diǎn)走向哪個(gè)方向的相鄰點(diǎn)
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);
}
}
}
}
//初始化隊(duì)列
STACK *init_sta
32、ck(void)
{
STACK *stack = (STACK *)malloc(sizeof(STACK));
if(NULL == stack)
{
printf("內(nèi)存分配失敗\n");
exit(-1);
}
stack->top = -1;
return stack;
}
//入隊(duì)列
void push_stack(STACK *stack, STATE st)
{
stack->top++;
stack->state[stack->top].di = st.di;
stack->state[stack->top].x
33、= 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-
34、>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");
35、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;
//記錄最后的路徑，為了清除重繪
fo
36、r(i = 0; i<=stack->top; i++)
{
cl[i] = stack->state[i];
}
clea = stack->top;
//記下最短的路徑坐標(biāo)
if(stack->top 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';
}
}
數(shù)據(jù)結(jié)構(gòu)教程習(xí)題答案 李蓉蓉 安楊等編著第三版 第六章答案
