多项式的表示和计算

　　　设计一种用单链表存储多项式的结构，每个结点存储一项的系数和指数（类型都是int），并编写一个产生多项式链表的函数和一个实现两个多项式相加的函数。
　　实例解析：
　　用单链表存储每一项的数据，则链表结点的结构应含有三个成员：系数、指数和后继的指针。定义结构如下：
1
2
3
4
5
6
struct  Node
{
　　   int  coef;
　　   int  power;
　　   struct  Node *link;
};
　　用链表存储多项式时，若系数不为0，则结点存在，若系数为0，则不保留该结点。要注意的是：做加法运算时，因有些结点不存在，所以要比较两个结点所存的次数是否一致。
　　主要程序代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <stdio.h>
　　#include < malloc .h>
　　#define MAX_CHARS_PER_LINE 10
　　 typedef  struct  Node *PNode;
　　 typedef  struct  Node *LinkList;
　　 //创建单链表（带头结点），若创建失败，返回NULL
　　LinkList createList( void )
　　{ LinkList llist;
   char  buffer[MAX_CHARS_PER_LINE];
   int  coef,power;
   llist = createNullList();
   if (llist == NULL)
     return  NULL;
   fgets (buffer,MAX_CHARS_PER_LINE,stdin); //输入数据，空格隔开
   sscanf (buffer, "%d %d" ,&coef,&power);  //从buffer中取得数据
   while (coef != 0 || power != 0){
     if (coef != 0)
　　　　　 if (append(llist,coef,power)){   //若向链表加结点失败
         freelist(llist);     //释放整个链表
         return  NULL;
       }
     fgets (buffer,MAX_CHARS_PER_LINE,stdin);
     sscanf (buffer, "%d %d" ,&coef,&power);
   }
   return  llist;
　　}
　　 //以下是其他几个函数的定义
　　LinkList createNullList( void )
　　{LinkList llist;
  llist = (PNode) malloc ( sizeof ( struct  Node));
  if (llist != NULL)
　　　　llist->link = NULL;
  return  llist;
　　}
　　 //追加结点的函数，成功返回0
　　 int  append(LinkList llist, int  coef, int  power)
　　{ PNode pnode;
   pnode = llist;
   while (pnode->link != NULL)
     pnode = pnode->link;
   pnode->link = (PNode) malloc ( sizeof ( struct  Node));
   pnode = pnode->link;
   if (pnode != NULL){
     pnode->coef = coef;
     pnode->power = power;
     pnode->link = NULL;
   }
   return  pnode == NULL;
　　}
　　LinkList add(LinkList a, LinkList b) //建立链表存储表达式的和
　　{LinkList c;
  PNode cur_a,cur_b;
  c = createNullList();
  if (c == NULL)
    return  NULL;
  cur_a = a->link;
  cur_b = b->link;
  while (cur_a != NULL && cur_b != NULL){
    if (cur_a->power > cur_b->power){
      if (append(c,cur_a->coef, cur_a->power)){
        freelist(c);
        return  NULL;
      }
      cur_a = cur_a->link;
    }
    else  {
　　　　　 if (cur_a->power < cur_b->power){
        if (append(c, cur_b->coef, cur_b->power)){
          freelist(c);
          return  NULL;
        }
        cur_b = cur_b->link;
      }
      else {
        if (append(c,cur_a->coef+cur_b->coef,cur_a->power)){
             freelist(c);
             return  NULL;
        }
        cur_a = cur_a->link;
        cur_b = cur_b->link;
      }
    }
　　 }
  if (cur_a != NULL){        //若a表达式还有未处理完的项
    while (cur_a != NULL){
      if (append(c, cur_a->coef, cur_a->power)){
        freelist(c);
        return  NULL;
      }
      cur_a = cur_a->link;
    }
  }
  if (cur_b != NULL){      //若b表达式还有未处理完的项
    while (cur_b != NULL){
      if (append(c, cur_b->coef, cur_b->power)){
        freelist(c);
        return  NULL;
      }
      cur_b = cur_b->link;
    }
  }
  return  c;
　　}
　　 int  main()
　　{ LinkList a,b,c;
   printf ( "Please input a:" );           //输入0 0表示结束
   if ((a = createList()) == NULL){
　　　　　 printf (“Create List a fail\n”);
　　　　　 return  0;
　　  }
   printf ( "Please input b:" );
   if ((b = createList()) == NULL){
　　　　　 printf (“Create List b fail\n”);
　　     freelist(a);
　　　　　 return  0;
　　  }
　　   if ((c = add(a,b)) == NULL)
　　　　　 printf (“Create List c fail\n”);
　　   else  {
　　     print(c);       //输出链表c
　　     freelist(c);
　　  }
　　  freelist(a);
　　  freelist(b);
   return  0;
　　}

十进制数化为二进制
　　　编程，将一个十进制非负整数，化为二进制（使用栈操作）。
　　实例解析：
　　十进制数化为二进制的方法，是将十进制数反复除以2，直到商为0。每次相除的余数倒排，便是所求的二进制数。
　　显然，利用栈操作最方便：将每次相除得到的余数入栈，然后将余数依次出栈输出。
　　程序代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <stdio.h>
　　#include < malloc .h>
　　#define DataType  int
　　#define MAX_SEQSTACK 100
　　 struct   SeqStack{    // 顺序栈类型定义
　　   int  MAXNUM;        //栈最多容纳的元素个数
   int  t;            // t<MAXNUM，表示已经有了第t个数据，自0计数
   DataType  *s;    //用来指向栈底元素
　　};
　　 typedef   struct  SeqStack  *PSeqStack;   //顺序栈类型的指针类型
　　PSeqStack CreateEmptyStack_seq()
　　{ PSeqStack  p;
   p = (PSeqStack) malloc ( sizeof ( struct  SeqStack));
   if (p == NULL)
　　　　 return  NULL;
　　  p->MAXNUM = MAX_SEQSTACK;
   p->t = -1;          //不能等于0，若等于0，意味着有了第0个数据
   p->s = (DataType*) malloc ( sizeof (DataType)*(p->MAXNUM));
   if (p->s == NULL){
　　     free (p);
　　     return  NULL;
　　  }
　　　 return  p;
　　}
　　 void  push_seq(PSeqStack pastack,DataType x)  //在栈中压入x
　　{ if (pastack->t >= pastack->MAXNUM - 1)
　　    printf (  "Overflow! \n"  );
　　  else {
    pastack->t = pastack->t + 1;
    pastack->s[pastack->t] = x;
  }
　　}
　　 void  pop_seq(PSeqStack pastack)     //删除栈顶元素
　　{ if (pastack->t == -1)
    printf ( "Underflow!\n" );
　　  else
    pastack->t = pastack->t - 1;
　　}
　　 int  isEmptyStack_seq(PSeqStack pastack)
　　{  return  pastack->t == -1;
　　}
　　DataType top_seq(PSeqStack pastack)   //栈不空时，求栈顶元素
　　{  return  (pastack->s[pastack->t]);
　　}
　　 void  print_bin( int  dec_number)
　　{ PSeqStack pastack;
   int  temp = dec_number;
   if (temp < 0){
      printf ( "Error!\n" );
      return  ;
   }
   pastack = CreateEmptyStack_seq();
   if (pastack == NULL)
　　　　 return ;
   while (temp > 0){      //若商大于0，继续循环
     push_seq(pastack, temp%2);   //余数入栈
     temp /= 2;                      //继续除以2
   }
   while (!isEmptyStack_seq(pastack)){
     printf ( "%d" , top_seq(pastack));  //输出栈顶值
     pop_seq(pastack);                   //删除栈顶元素
   }
   free (pastack->s);                //释放栈
　　　 free (pastack);                   //释放结构体变量
　　}
　　 int  main()
　　{  int  a;
   printf ( "Please input a number:\n" );
   scanf ( "%d" , &a);
   print_bin(a);
   return  0;
　　}

检查括号配对
　　　假设表达式中包含圆括号、方括号和花括号三种括号。试编写一个函数，判断表达式中的括号是否正确配对。
　　实例解析：
　　依次读入数学表达式的各个字符，遇到左括号，入栈；遇到右括号，查看栈顶元素是否与其配对。若配对，出栈；若不配对，返回0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <stdio.h>
　　#include < malloc .h>
　　#define DataType  char
　　 //数据定义及以下5个函数的定义与本章实例13相同
　　PSeqStack CreateEmptyStack_seq();
　　 void   push_seq(PSeqStack pastack, DataType x);
　　 void   pop_seq(PSeqStack pastack);
　　 int  isEmptyStack_seq(PSeqStack pastack);
　　DataType  top_seq(PSeqStack pastack);
　　 int  correct( char  * exp )
　　{ int  i = 0;
  DataType x;
  PSeqStack st;
  if ((st = CreateEmptyStack_seq()) == NULL)
　　　　 return  0;
  do {
     x = *( exp +i);
     switch (x){
       case  '{'  :
　　　　　 case  '['  :
　　　　　 case  '('  :      　　
                    push_seq(st, x);   //左括号入栈
                    break ;
       case  ')' :   //遇到有括号
                   if (isEmptyStack_seq(st)){   //若此时栈为空
                      free (st->s);     //释放栈
　　　　　　　　　　　　　 free (st);     //释放结构体变量
                      return  0;     //返回0
　　                  }
　　　　　　　　　　　x = top_seq(st);   //取栈顶值
                   if (x !=  '(' ){      //若不匹配
　　　　　　　　　　　　　 free (st->s);
　　　　　　　　　　　　　 free (st); 
                      return  0;
　　                  }
                   pop_seq(st);     //删除栈顶元素
                   break ;
       case  ']' :
                   if (isEmptyStack_seq(st)){
                      free (st->s); 
　　　　　　　　　　　　　 free (st); 
                      return  0;
　　                  }
　　　　　　　　　　　x = top_seq(st);
                   if (x !=  '[' ){
　　                      free (st->s);
　　　　　　　　　　　　　 free (st); 
                      return  0;
　　                  }
                   pop_seq(st);
                   break ;
       case  '}' :
                   if (isEmptyStack_seq(st)){
                      free (st->s); 
　　　　　　　　　　　　　 free (st); 
                      return  0;
　　                  }
　　　　　　　　　　　x = top_seq(st);
                   if (x !=  '{' ) {
　　　　　　　　　　　　　 free (st->s); 
　　　　　　　　　　　　　 free (st); 
                      return  0;
　　                  }
                   pop_seq(st);
                   break ;
       default :
                   break ;
     }
     i++;
  } while (x !=  '\0' );
　　  if (!isEmptyStack_seq(st)){  //若检查结束栈不为空，则左括号多
    free (st->s);
　　　　 free (st); 
    return  0;
　　 }
　　  free (st->s); 
　　　 free (st); 
  return  1;
　　}
　　 int  main()
　　{  char  exp [80];
　　   gets ( exp );
   if (correct( exp ) == 0)
     printf ( "Error\n" );
   else
     printf ( "Ok\n" );
   return  0;
　　}