独立思考_潜心修行

AllenNewOK

常用链接

统计

最新评论

2010年9月17日 #

多项式的规范化_数据结构_C语言实现

多项式的规范化,采用单链表,使用C语言实现,gcc调试通过。

  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 



调试环境:Ubuntu Desktop 8.04.4    VI 7.1.138    GCC 4.2.4
QQ:81064483
E-mail:AllenNewOK@126.com

复习之用,不足之处,烦请高手们指教。< ^_^ >

posted @ 2010-09-17 10:44 AllenNewOK 阅读(1224) | 评论 (0)编辑 收藏

2010年9月12日 #

单链表的创建、计数打印、删除节点、增加节点和逆序操作

单链表的创建、计数打印、删除节点、增加节点和逆序操作,是在上一篇的基础上完善了逆序操作,gcc编译通过。

  1 #include<stdio.h>
  2 #include<stdlib.h>  /*使用到其中的malloc和exit函数*/
  3 #define times 4  /*用于循环次数的控制*/
  4 
  5 static int N=4;  /*静态全局变量,用于控制单链表长度*/
  6 
  7 typedef struct _person
  8 {
  9     char name[12];
 10     int age;
 11     struct _person *next;
 12 }stud;
 13 
 14 stud *Create(int num)  /*创建单链表的函数,num为单链表的长度*/
 15 {
 16     int i;
 17     stud *h,*p,*q;  /* h为头指针,指向单链表的第一个节点*/
 18     h=(stud*)malloc(sizeof(stud));
 19     if(h!=NULL)
 20     {
 21         p=h;
 22         for(i=0;i<num;i++)
 23         {
 24             q=(stud*)malloc(sizeof(stud));  /* q为指向新建节点的指针*/
 25             if(q!=NULL)
 26             {
 27                 printf("依次输入第%d个人的姓名和年龄:\n",i+1);
 28                 scanf("%s%d",q->name,&q->age);
 29                 q->next=NULL;  /*创建新节点完毕*/
 30                 p->next=q;
 31                 p=q;
 32             }
 33         }
 34     }
 35     printf("\n");
 36     return(h);
 37 }
 38 
 39 stud *Delete(stud *person,int post)  /*删除单链表指定位置节点的函数*/
 40 {
 41     int i;
 42     stud *cur,*pre;
 43     cur=person;
 44 
 45     if(0==post)  /*如果输入的值为0,则不删除任何节点*/
 46     {
 47         printf("\n注意:您决定不删除任何节点!!!\n\n");
 48         return(person);
 49     }
 50     else if(post>N||post<0)  /*如果输入的值大于单链表长度或者小于0,程序结束*/
 51     {
 52         printf("输入有误,程序终止。\n");
 53         exit(1);
 54     }
 55     else
 56     {
 57         if(1==post)  /*在单链表头部删除的情况*/
 58         {
 59             cur=cur->next;
 60             person->next=cur->next;
 61             free(cur);
 62         }
 63         else  /*在其它位置删除的情况*/
 64         {
 65             for(i=2;i<post+1;i++)  /*使pre成为要插入位置的上一位置的节点*/
 66             {
 67                 cur=cur->next;
 68                 pre=cur;
 69             }
 70             cur=cur->next;
 71             pre->next=cur->next;
 72             free(cur);
 73         }
 74         return(person);
 75     }
 76 }
 77 
 78 stud *Insert(stud *person,int post)  /*在单链表指定位置插入新的节点的函数*/
 79 {
 80     int i;
 81     stud *cur,*pre,*node;
 82     
 83     if(post>N+1||post<1)  /*如果输入的值大于单链表长度加1或者小于1,程序结束*/
 84     {
 85         printf("输入错误,程序终止。\n");
 86         exit(1);
 87     }
 88 
 89     if(person!=NULL)
 90     {
 91         cur=person;
 92         node=(stud*)malloc(sizeof(stud));
 93         if(node!=NULL)
 94         {
 95             printf("请输入新人的姓名和年龄:\n");
 96             scanf("%s%d",node->name,&node->age);  /*为新的节点输入数据内容*/
 97 
 98             if(1==post)
 99             {
100                 node->next=person->next;
101                 person->next=node;
102             }
103             else
104             {
105                 for(i=2;i<post+2;i++)
106                 {
107                     pre=cur;
108                     cur=cur->next;
109                 }
110                 node->next=pre->next;
111                 pre->next=node;
112                 
113             }
114         }
115     }
116     printf("\n");
117     return(person);
118 }
119 
120 stud *Reverse(stud *person)  /*对单链表进行逆序操作的函数*/
121 {
122     stud *cur,*tmp;  //cur将代表逆序后单链表的第一个节点
123                //tmp代表原单链表中cur之后紧邻的节点,起交换作用
124 
125     if(person!=NULL)
126     {
127         cur=person->next;
128         person->next=NULL;  /*将原单链表置空*/
129         
130         while(cur!=NULL)  /*如果cur不为NULL*/
131         {
132             tmp=cur->next;  /*把当前节点的下一个节点赋给tmp */
133             cur->next=person->next;  //若当前节点为原链表中的第一个节点,则使其next指向NULL
134                          //否则使其next指向原链表中当前节点的上一个节点,也就是正在逆序中的第一个节点
135             person->next=cur;  /*使头指针指向当前节点*/
136             cur=tmp;  /*把原cur的下一个节点赋给cur*/
137         }
138         
139     }
140     return(person);
141 }
142 
143 void Print(stud *person)
144 {
145     int post=1;
146     stud *cur;
147     cur=person->next;
148     printf("当前的节点信息如下所示:\n");
149     while(cur!=NULL)
150     {
151         printf("第%d个人的姓名是:%s,年龄为:%d\n",post,cur->name,cur->age);
152         cur=cur->next;
153         post++;
154     }
155     N=--post;
156     printf("当前单链表的长度是:%d\n\n",N);
157 }
158 
159 int main()
160 {
161     int number,post,i;
162     stud *head;
163     head=Create(N);
164     Print(head);
165 
166     for(i=0;i<times;i++)
167     {
168         printf("请输入要删除的节点的位置:\n");
169         scanf("%d",&number);
170         Delete(head,number);
171         Print(head);
172 
173         printf("请输入要插入节点的位置(此位置是指预期插入成功后新节点在单链表中的位置):\n");
174         scanf("%d",&post);
175         Insert(head,post);
176         Print(head);
177     
178         printf("以下展示了两次单链表的逆序!!!\n\n");
179         Print(Reverse(head));
180         Print(Reverse(head));
181     
182         printf("\n注意:剩余输入轮数为:%d  !!!!!\n\n",(times-(i+1)));
183     }
184 
185     return 0;
186 }



调试环境:Ubuntu Desktop 8.04.4    VI 7.1.138    GCC 4.2.4
QQ:81064483
E-mail:AllenNewOK@126.com

复习之用,不足之处,敬请指正。< ^_^ >



posted @ 2010-09-12 18:03 AllenNewOK 阅读(1969) | 评论 (0)编辑 收藏

单链表的创建、计数打印、删除与插入操作


单链表的创建、计数打印、删除与插入操作,提供四轮删除与插入操作,gcc编译通过。

 

  1 #include<stdio.h>
  2 #include<stdlib.h>  /*使用到其中的malloc和exit函数*/
  3 #define times 4  /*用于循环次数的控制*/
  4 
  5 static int N=4;  /*静态全局变量,用于控制单链表长度*/
  6 
  7 typedef struct _person
  8 {
  9     char name[12];
 10     int age;
 11     struct _person *next;
 12 }stud;
 13 
 14 stud *Create(int num)  /*创建单链表的函数,num为单链表的长度*/
 15 {
 16     int i;
 17     stud *h,*p,*q;  /* h为头指针,指向单链表的第一个节点*/
 18     h=(stud*)malloc(sizeof(stud));
 19     if(h!=NULL)
 20     {
 21         p=h;
 22         for(i=0;i<num;i++)
 23         {
 24             q=(stud*)malloc(sizeof(stud));  /* q为指向新建节点的指针*/
 25             if(q!=NULL)
 26             {
 27                 printf("依次输入第%d个人的姓名和年龄:\n",i+1);
 28                 scanf("%s%d",q->name,&q->age);
 29                 q->next=NULL;  /*创建新节点完毕*/
 30                 p->next=q;
 31                 p=q;
 32             }
 33         }
 34     }
 35     printf("\n");
 36     return(h);
 37 }
 38 
 39 stud *Delete(stud *person,int post)  /*删除单链表指定位置节点的函数*/
 40 {
 41     int i;
 42     stud *cur,*pre;
 43     cur=person;
 44 
 45     if(0==post)  /*如果输入的值为0,则不删除任何节点*/
 46     {
 47         printf("\n注意:您决定不删除任何节点!!!\n\n");
 48         return(person);
 49     }
 50     else if(post>N||post<0)  /*如果输入的值大于单链表长度或者小于0,程序结束*/
 51     {
 52         printf("输入有误,程序终止。\n");
 53         exit(1);
 54     }
 55     else
 56     {
 57         if(1==post)  /*在单链表头部删除的情况*/
 58         {
 59             cur=cur->next;
 60             person->next=cur->next;
 61             free(cur);
 62         }
 63         else  /*在其它位置删除的情况*/
 64         {
 65             for(i=2;i<post+1;i++)  /*使pre成为要插入位置的上一位置的节点*/
 66             {
 67                 cur=cur->next;
 68                 pre=cur;
 69             }
 70             cur=cur->next;
 71             pre->next=cur->next;
 72             free(cur);
 73         }
 74         return(person);
 75     }
 76 }
 77 
 78 stud *Insert(stud *person,int post)  /*在单链表指定位置插入新的节点的函数*/
 79 {
 80     int i;
 81     stud *cur,*pre,*node;
 82     
 83     if(post>N+1||post<1)  /*如果输入的值大于单链表长度加1或者小于1,程序结束*/
 84     {
 85         printf("输入错误,程序终止。\n");
 86         exit(1);
 87     }
 88 
 89     if(person!=NULL)
 90     {
 91         cur=person;
 92         node=(stud*)malloc(sizeof(stud));
 93         if(node!=NULL)
 94         {
 95             printf("请输入新人的姓名和年龄:\n");
 96             scanf("%s%d",node->name,&node->age);  /*为新的节点输入数据内容*/
 97 
 98             if(1==post)
 99             {
100                 node->next=person->next;
101                 person->next=node;
102             }
103             else
104             {
105                 for(i=2;i<post+2;i++)
106                 {
107                     pre=cur;
108                     cur=cur->next;
109                 }
110                 node->next=pre->next;
111                 pre->next=node;
112             }
113         }
114     }
115     printf("\n");
116     return(person);
117 }
118 
119 void Print(stud *person)
120 {
121     int post=1;
122     stud *cur;
123     cur=person->next;
124     printf("当前的节点信息如下所示:\n");
125     while(cur!=NULL)
126     {
127         printf("第%d个人的姓名是:%s,年龄为:%d\n",post,cur->name,cur->age);
128         cur=cur->next;
129         post++;
130     }
131     N=--post;
132     printf("当前单链表的长度是:%d\n\n",N);
133 }
134 
135 int main()
136 {
137     int number,post,i;
138     stud *head;
139     head=Create(N);
140     Print(head);
141 
142     for(i=0;i<times;i++)
143     {
144         printf("请输入要删除的节点的位置:\n");
145         scanf("%d",&number);
146         Delete(head,number);
147         Print(head);
148 
149         printf("请输入要插入节点的位置(此位置是指预期插入成功后新节点在单链表中的位置):\n");
150         scanf("%d",&post);
151         Insert(head,post);
152         Print(head);
153     
154         printf("\n注意:剩余输入轮数为:%d  !!!!!\n\n",(times-(i+1)));
155     }
156 
157     return 0;
158 }

 


调试环境:Ubuntu Desktop 8.04.4   VIM 7.1.138 GCC 4.2.4
QQ:81064483
E-mail:AllenNewOK@126.com

不足之处,敬请指正。< ^_^ >

posted @ 2010-09-12 13:00 AllenNewOK 阅读(1732) | 评论 (2)编辑 收藏

仅列出标题