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不足之處，敬請指正。< ^_^ >