1 //该程序是为了将无序的、不规范的多项式进行规范化而写的。
  2 #include<stdio.h>
  3 #include<stdlib.h>
  4 #define N 8  //指明多项式数据项的数目
  5 
  6 int GetLength();  //获得单链表的长度
  7 void Print();  //打印出单链表的节点数据
  8 
  9 typedef struct multinomialnode  //定义存储多项式数据项的节点的结构体
 10 {
 11     int coefficient,power;  //声明系数和幂
 12     struct multinomialnode *next;
 13 }node;
 14 
 15 node *Create(int num)  //创建存储多项式的链表
 16 {
 17     int i;
 18     node *head,*pointer,*tmp;
 19     
 20     head=(node*)malloc(sizeof(node));
 21     if(head!=NULL)    pointer=head;
 22     
 23     printf("请依次输入要处理的多项式元素的系数和幂：\n");
 24     for(i=0;i<num;i++)
 25     {
 26         printf("请输入第 %d 个元素的系数和幂：\n",i+1);
 27         tmp=(node*)malloc(sizeof(node));
 28         if(tmp!=NULL)
 29         {
 30             scanf("%d%d",&tmp->coefficient,&tmp->power);
 31             tmp->next=NULL;
 32             pointer->next=tmp;
 33             pointer=tmp;            
 34         }
 35     }
 36     return(head);
 37 }
 38 
 39 node *Standard(node *head)  //对多项式进行规范化的过程
 40 {
 41     int i;
 42     node *pointer,*pre,*cur,*tmp,*q;
 43     
 44     pointer=head->next;  //代表用于比较及合并相同幂的节点，也用于条件判断，控制循环
 45     pre=pointer;  //代表被比较的节点的上一个节点的指针，用于链接节点的操作，从而构造新的链表
 46     cur=pointer->next;  //代表被比较的节点，也用于条件判断，控制循环
 47 
 48     while(pointer->next!=NULL)  //合并无序多项式中具有相同幂的节点，并将被合并后的节点删除
 49     {
 50         while(cur!=NULL)
 51         {
 52             if(pointer->power==cur->power)  //相等则合并，同时删除被合并过的节点
 53             {
 54                 pointer->coefficient+=cur->coefficient;  //合并具有相同幂的项的系数
 55                 q=cur;
 56                 cur=cur->next;
 57                 pre->next=cur;
 58                 free(q);  //释放内存
 59             }
 60             else  //不等则指向被比较的节点及其上一节点的指针均后移
 61             {
 62                 cur=cur->next;
 63                 pre=pre->next;
 64             }
 65         }
 66         pointer=pointer->next;  //后移
 67         pre=pointer;  //重新初始化
 68         cur=pointer->next;  //重新初始化
 69     }
 70     
 71     Print(head);  //打印出上面while以后构造成的多项式
 72 
 73     for(i=0;i<GetLength(head);i++)  //将上一步while完成以后得到多项式进一步规范化，使之按数据项的幂由大到小依次排列
 74     {
 75         pre=head;  //代表指向当前节点的指针的上一指针，用于交换节点的操作
 76         cur=head->next;  //代表指向当前节点的指针，用于比较
 77         tmp=cur->next;  //代表指向当前节点的下一节点的指针，用于比较和条件判断
 78     
 79         while(tmp!=NULL)
 80         {
 81             if(cur->power<tmp->power)  //如果当前数据项的幂小于其后紧邻的数据项的幂，则交换两个节点在链表中的位置，然后改变指针使重新指向
 82             {
 83                 pre->next=tmp;
 84                 cur->next=tmp->next;
 85                 tmp->next=cur;
 86                 
 87                 pre=tmp;
 88                 tmp=cur->next;
 89             }
 90             else  //如果条件相反的话，直接后移这三个指针
 91             {
 92                 pre=pre->next;
 93                 cur=cur->next;
 94                 tmp=tmp->next;
 95             }
 96         }
 97     }
 98 
 99     return(head);
100 }
101 
102 int GetLength(node *head)  //获得单链表的长度
103 {
104     int i=0;
105     node *pointer;
106     pointer=head->next;
107 
108     while(pointer!=NULL)
109     {
110         i++;
111         pointer=pointer->next;
112     }
113     return i;
114 }
115 
116 void Print(node *head)  //打印出单链表的节点数据
117 {
118     int i=0;
119     node *pointer;
120     pointer=head->next;
121     
122     printf("\n新的多项式系数和幂表示如下：\n");
123     while(pointer!=NULL)
124     {
125         i++;
126         printf("第 %d 个数据元素的系数为：%d,幂为：%d\n",i,pointer->coefficient,pointer->power);
127         pointer=pointer->next;
128     }
129 }
130 
131 int main()
132 {
133     node *multinomial;
134     multinomial=Create(N);
135     Print(multinomial);
136 
137     multinomial=Standard(multinomial);
138     Print(multinomial);
139 
140     return 0;
141 }
142 

任兆强 2010-09-17 11:50 发表评论