C--算法与数据结构--栈的应用

题目：

1.数制转换（非负数十进制整数转换为八进制数）

方法一：非递归实现

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 /* run this program using the console pauser or add your own getch, system("pause") or input loop */
 5 #define max 100
 6 typedef struct {
 7     int data[max];
 8     int top ;
 9 }SEQSTACK;
10 void initstack(SEQSTACK *s){
11     /*顺序栈初始化*/
12     s->top=0; 
13 }
14 int gettop(SEQSTACK *s){
15     /*返回栈顶元素*/
16     int x;
17     if(s->top==0){
18         printf("栈空
");
19         x=0;
20         
21     } 
22     else{
23         x=(s->data)[s->top]; 
24     } 
25     return x;
26 }
27 int push (SEQSTACK *s,int x){
28     /*元素x入栈*/
29     if(s->top==max-1){
30         printf("栈满
");
31         return 0; 
32     }
33     else{
34         s->top++;
35         (s->data)[s->top]=x;
36         return 1; 
37     }
38 }
39 int pop(SEQSTACK *s){
40     /*返回栈顶元素并删除栈顶元素*/
41     int x;
42     if(s->top ==0){
43         printf("栈空
");
44         x=0;
45     } 
46     else {
47         x=(s->data)[s->top];
48         s->top--;
49     }
50     return x;
51 }
52 main(){
53     SEQSTACK stack ,*s;
54     int n;
55     s=&stack;
56     initstack (s);
57     n=0;
58     printf("输入一个非负数（十进制）:");
59     scanf("%d",&n);
60     push (s,'#');
61     while(n!=0){
62         push (s,n%8);
63         n=n/8;
64     } 
65     printf("

对应的八进制数为：");
66     while(gettop(s)!='#'){
67         printf("%d",pop(s));
68     } 
69     printf("
");
70 }

View Code

测试结果：

2.方法二：递归实现：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 /* run this program using the console pauser or add your own getch, system("pause") or input loop */
 5 #define max 100
 6 void d_to_or(int x){
 7     /*非负十进制整数转换为八进制数的递归算法*/
 8     if(x/8!=0)
 9         d_to_or(x/8);
10     printf("%d",x%8);    
11 } 
12 main(){
13     int x;
14     printf("输入一个非负整数（十进制）");
15     scanf("%d",&x);
16     printf("

对应的八进制数为");
17     d_to_or(x);
18     printf("

");
19     
20 }

测试结果：

3.编程实现非负十进制数转换成二进制数和十六进制数

(1)转换成二进制数：

方法一：递归算法;

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 /* run this program using the console pauser or add your own getch, system("pause") or input loop */
 5 #define max 100
 6 void d_to_or(int x){
 7     /*非负十进制整数转换为八进制数的递归算法*/
 8     if(x/2!=0)
 9         d_to_or(x/2);
10     printf("%d",x%2);    
11 } 
12 main(){
13     int x;
14     printf("输入一个非负整数（十进制）");
15     scanf("%d",&x);
16     printf("

对应的二进制数为");
17     d_to_or(x);
18     printf("

");
19     
20 }

方法二;非递归算法：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 /* run this program using the console pauser or add your own getch, system("pause") or input loop */
 5 #define max 100
 6 typedef struct {
 7     int data[max];
 8     int top ;
 9 }SEQSTACK;
10 void initstack(SEQSTACK *s){
11     /*顺序栈初始化*/
12     s->top=0; 
13 }
14 int gettop(SEQSTACK *s){
15     /*返回栈顶元素*/
16     int x;
17     if(s->top==0){
18         printf("栈空
");
19         x=0;
20         
21     } 
22     else{
23         x=(s->data)[s->top]; 
24     } 
25     return x;
26 }
27 int push (SEQSTACK *s,int x){
28     /*元素x入栈*/
29     if(s->top==max-1){
30         printf("栈满
");
31         return 0; 
32     }
33     else{
34         s->top++;
35         (s->data)[s->top]=x;
36         return 1; 
37     }
38 }
39 int pop(SEQSTACK *s){
40     /*返回栈顶元素并删除栈顶元素*/
41     int x;
42     if(s->top ==0){
43         printf("栈空
");
44         x=0;
45     } 
46     else {
47         x=(s->data)[s->top];
48         s->top--;
49     }
50     return x;
51 }
52 main(){
53     SEQSTACK stack ,*s;
54     int n;
55     s=&stack;
56     initstack (s);
57     n=0;
58     printf("输入一个非负数（十进制）:");
59     scanf("%d",&n);
60     push (s,'#');
61     while(n!=0){
62         push (s,n%2);
63         n=n/2;
64     } 
65     printf("

对应的二进制数为：");
66     while(gettop(s)!='#'){
67         printf("%d",pop(s));
68     } 
69     printf("
");
70 }

View Code

(2)转换成十六进制数：

方法一：递归算法

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 /* run this program using the console pauser or add your own getch, system("pause") or input loop */
 5 #define max 100
 6 void d_to_or(int x){
 7     
 8     /*非负十进制整数转换为八进制数的递归算法*/
 9     int a;
10     a=x%16;
11     char b;
12     if(x/16!=0)
13         d_to_or(x/16);
14     if(a>=10){
15         if(a==10){
16             printf("A");
17         }
18         if(a==11){
19             printf("B");
20         }
21         if(a==12){
22             printf("C");
23         //    b='c'; 
24         }
25         if(a==13){
26             printf("D");
27         }
28         
29         if(a==14){
30             printf("E");
31         }
32         if(a==15){
33             printf("F");
34         }
35     }    
36     else{
37         printf("%d",a);
38     }
39 } 
40 main(){
41     int x;
42     printf("输入一个非负整数（十进制）");
43     scanf("%d",&x);
44     printf("

对应的二进制数为");
45     d_to_or(x);
46     printf("

");
47 }

View Code

方法二：非递归算法:

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

其他方法：不考虑算法实现：（mao主席）

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h> 
 4 void DtoOx(int x)
 5 {
 6     char str[] = "0123456789ABCDEF";
 7     char stack[100]="";
 8     int i = 0,j;
 9     int temp = x;
10     while (x)
11     {
12         stack[i] = str[x % 16];
13         x = x / 16;
14         i++;
15     }
16     printf("%d 的十六进制是:", temp);
17     for(j=i;j>=0;j--){
18         printf("%c",stack[j]);
19     } 
20 }
21 void DtoBinary(int x)
22 {
23     char str[]="01";
24     char stack[100]="";
25     int i=0,j;
26     int temp=x;
27     while(x)
28     {
29         stack[i]=str[x%2];
30         x=x/2;
31         i++;
32     } 
33     printf("%d 的二进制数是:",temp);
34     for(j=i;j>=0;j--){
35         printf("%c",stack[j]);
36     } 
37 }
38  
39 int main()
40 {
41     int x,y;
42     printf("请输入一非负整数（十进制）：");
43     scanf("%d",&x);
44     DtoOx(x);
45     printf("
");
46     printf("请输入一非负整数（十进制）：");
47     scanf("%d",&y);
48     DtoBinary(y);
49 }

View Code