2010年9月17日
#
多项式的规范化，采用单链表，使用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
复习之用，不足之处，烦请高手们指教。< ^_^ >
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
复习之用，不足之处，敬请指正。< ^_^ >
单链表的创建、计数打印、删除与插入操作，提供四轮删除与插入操作，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.4QQ：81064483E-mail：AllenNewOK@126.com不足之处，敬请指正。< ^_^ >