编程马拉松(12)链表

freesoft

还是11题的内容，但用连表方式实现

1. 
   
2. #include <iOStream>  
   
3. using namespace std;  
   
4. struct test  
   
5. {  
   
6.     int number;  
   
7.     char name[20];
   
8.         float shuxue;
   
9.         float yuwen;
   
10.         float yingyu;
    
11.         float wule;
    
12.         float huaxue;
    
13.         float zongfen()
    
14.         {
    
15.                 return shuxue+yuwen+wule+huaxue+yingyu;
    
16.         };
    
17.     test *next;
    
18.         const struct test& operator=(const struct test &a)//这里用到了，运算符重载，以后会讲。
    
19.         {
    
20.                 number = a.number;
    
21.                 strcpy(name, a.name);
    
22.                 shuxue = a.shuxue;
    
23.                 yuwen = a.yuwen;
    
24.                 yingyu = a.yingyu;
    
25.                 wule = a.wule;
    
26.                 huaxue = a.huaxue;
    
27.                 return *this;
    
28.         }
    
29. };  
    
30. test *head;//创建一个全局的引导进入链表的指针  
    
31.   
    
32. test *create()  //输入数据
    
33. {  
    
34.     test *ls;//节点指针  
    
35.     test *le;//链尾指针  
    
36.     ls = new test;//把ls指向动态开辟的堆内存地址  
    
37.     cout<<"请输入第一个学生数据,输入所有项为0退出"<<endl;  
    
38.                                 cout<<"学号:";
    
39.                         cin>>ls->number;
    
40.                                 cout<<"姓名:";
    
41.                         cin>>ls->name;
    
42.                                 cout<<"数学:";
    
43.                         cin>>ls->shuxue;
    
44.                                 cout<<"语文:";
    
45.                         cin>>ls->yuwen;
    
46.                                 cout<<"英语:";
    
47.                         cin>>ls->yingyu;
    
48.                                 cout<<"物理:";
    
49.                         cin>>ls->wule;
    
50.                                 cout<<"化学:";
    
51.                         cin>>ls->huaxue;  
    
52.     head=NULL;//进入的时候先不设置head指针指向任何地址,因为不知道是否一上来就输入null跳出程序  
    
53.     le=ls;//把链尾指针设置成刚刚动态开辟的堆内存地址,用于等下设置le->next,也就是下一个节点的位置  
    
54.     while(ls->number!=0)//创建循环条件为ls->number的值不是null,用于循环添加节点  
    
55.     {  
    
56.         if(head==NULL)//判断是否是第一次进入循环  
    
57.         {  
    
58.             head=ls;//如果是第一次进入循环,那么把引导进入链表的指针指向第一次动态开辟的堆内存地址  
    
59.         }  
    
60.         else  
    
61.         {  
    
62.             le->next=ls;//如果不是第一次进入那么就把上一次的链尾指针的le->next指向上一次循环结束前动态创建的堆内存地址  
    
63.         }  
    
64.         le=ls;//设置链尾指针为当前循环中的节点指针,用于下一次进入循环的时候把上一次的节点的next指向上一次循环结束前动态创建的堆内存地址  
    
65.         ls=new test;//为下一个节点在堆内存中动态开辟空间  
    
66.     cout<<"请输入下一个学生数据,输入所有项为0退出"<<endl;  
    
67.                                 cout<<"学号:";
    
68.                         cin>>ls->number;
    
69.                                 cout<<"姓名:";
    
70.                         cin>>ls->name;
    
71.                                 cout<<"数学:";
    
72.                         cin>>ls->shuxue;
    
73.                                 cout<<"语文:";
    
74.                         cin>>ls->yuwen;
    
75.                                 cout<<"英语:";
    
76.                         cin>>ls->yingyu;
    
77.                                 cout<<"物理:";
    
78.                         cin>>ls->wule;
    
79.                                 cout<<"化学:";
    
80.                         cin>>ls->huaxue;  
    
81.     }  
    
82.     le->next=NULL;//把链尾指针的next设置为空,因为不管如何循环总是要结束的,设置为空才能够在循环显链表的时候不至于死循环  
    
83.     delete ls;//当结束的时候最后一个动态开辟的内存是无效的,所以必须清除掉  
    
84.     return head;//返回链首指针  
    
85. }  
    
86. void showl(test *head)  //显示表
    
87. {  
    
88.         test * p = head;
    
89.     //cout<<"链首指针:"<<head<<endl;  
    
90.     while(p)//以内存指向为null为条件循环显示先前输入的内容  
    
91.     {  
    
92.         cout<<p->number<<"   "
    
93.                         <<p->name<<"   "
    
94.                         <<p->shuxue<<"   "
    
95.                         <<p->yuwen<<"   "
    
96.                         <<p->yingyu<<"   "
    
97.                         <<p->wule<<"   "
    
98.                         <<p->huaxue
    
99.                         <<endl;  
    
100.         p=p->next;  
     
101.     }  
     
102. }  
     
103. void deletel(test *&head,int number)//(删除)这里如果参数换成test *head,意义就完全不同了,head变成了复制而不是原有链上操作了,特别注意,很多书上都不对这里  
     
104. {  
     
105.     test *point;//判断链表是否为空  
     
106.     if(head==NULL)  
     
107.     {  
     
108.         cout<<"链表为空,不能进行删除工作!";  
     
109.         return;  
     
110.     }  
     
111.   
     
112.     int derror=1;//设置找不到的情况的条件,预先设置为真  
     
113.     test *check=head;  
     
114.     while(check)//利用循环进行查找  
     
115.     {  
     
116.         if (check->number==number)  
     
117.         {  
     
118.             derror=0;//条件转为假  
     
119.         }  
     
120.         check=check->next;  
     
121.     }  
     
122.     if(derror)//如果为假就跳出函数  
     
123.     {  
     
124.         return;  
     
125.     }  
     
126.   
     
127.     if(head->number==number)//判删除的节点是否为首节点  
     
128.     {  
     
129.         point=head;  
     
130.         cout<<"删除点是链表第一个节点位置!";  
     
131.         head=head->next;//重新设置引导指针  
     
132.         delete point;  
     
133.         return;  
     
134.     }  
     
135.     for(test *mp=head;mp->next;mp=mp->next)  
     
136.     {  
     
137.         if(mp->next->number==number)  
     
138.         {  
     
139.             point=mp->next;  
     
140.             mp->next=point->next;  
     
141.             delete point;  
     
142.             return;  
     
143.         }  
     
144.     }  
     
145. }  
     
146.   
     
147. void insterl(int number)  //插入
     
148. {  
     
149.     test *indata=new test;  
     
150.     cout<<"插入学生成绩"<<endl;  
     
151.         cout<<"学号:";
     
152.                 cin>>indata->number;
     
153.         cout<<"姓名:";
     
154.                 cin>>indata->name;
     
155.         cout<<"数学:";
     
156.                 cin>>indata->shuxue;
     
157.         cout<<"语文:";
     
158.                 cin>>indata->yuwen;
     
159.         cout<<"英语:";
     
160.                 cin>>indata->yingyu;
     
161.         cout<<"物理:";
     
162.                 cin>>indata->wule;
     
163.         cout<<"化学:";
     
164.                 cin>>indata->huaxue;
     
165.   
     
166.     if(head==NULL)//链表为空的情况下插入  
     
167.     {  
     
168.         head=indata;  
     
169.         indata->next=NULL;  
     
170.         return;  
     
171.     }  
     
172.   
     
173.     int ierror=1;//设置找不到的情况的条件,预先设置为真  
     
174.     test *le;  
     
175.     test *check=head;  
     
176.     while(check)//利用循环进行查找  
     
177.     {  
     
178.         if (check->number==number)  
     
179.         {  
     
180.             ierror=0;//条件转为假  
     
181.         }  
     
182.         le=check;  
     
183.         check=check->next;  
     
184.     }  
     
185.     if(ierror)  
     
186.     {  
     
187.         //cout<<le->number;  
     
188.         le->next=indata;  
     
189.         indata->next=NULL;  
     
190.         return;  
     
191.     }  
     
192.   
     
193.    if(head->number==number)//检测是否是在第一个节点处插入  
     
194.     {  
     
195.         indata->next=head;  
     
196.         head=indata;  
     
197.         return;  
     
198.     }  
     
199.   
     
200.     for(test *mp=head;mp->next;mp=mp->next)//在链表中间插入  
     
201.     {  
     
202.         if(mp->next->number==number)  
     
203.         {  
     
204.             indata->next=mp->next;  
     
205.             mp->next=indata;  
     
206.             return;  
     
207.         }  
     
208.     }  
     
209.   
     
210. }  
     
211. void paixu(test *head)//排序
     
212. {
     
213.         test *tmp0=new test;
     
214.        
     
215. 
     
216.         test *tmp1=head;
     
217.         while(tmp1)
     
218.         {
     
219.                 test *tmp2=tmp1->next;
     
220.                 while(tmp2)
     
221.                 {
     
222.                         if(tmp1->zongfen()>tmp2->zongfen())
     
223.                         {
     
224.                                 *tmp0=*tmp1;
     
225.                                 *tmp1=*tmp2;
     
226.                                 *tmp2=*tmp0;
     
227.                         }
     
228. 
     
229.                         tmp2=tmp2->next;
     
230.                 }
     
231.                 tmp1=tmp1->next;
     
232.         }
     
233.         delete tmp0;
     
234.         tmp0 = head;
     
235.         while(tmp0)  
     
236.     {  
     
237.         cout<<tmp0->number<<"   "
     
238.                         <<tmp0->name<<"   "
     
239.                         <<tmp0->shuxue<<"   "
     
240.                         <<tmp0->yuwen<<"   "
     
241.                         <<tmp0->yingyu<<"   "
     
242.                         <<tmp0->wule<<"   "
     
243.                         <<tmp0->huaxue<<"  "
     
244.                         <<tmp0->zongfen()<<"  "
     
245.                         <<tmp0->zongfen()/5.0<<"  "
     
246.                         <<endl;  
     
247.         tmp0=tmp0->next;  
     
248.     }
     
249.        
     
250. }
     
251. 
     
252.        
     
253. 
     
254. void main()  
     
255. {  
     
256.        
     
257.         int mu=1;
     
258.         int err=1;
     
259.        
     
260.         while (err!=0)
     
261.         {
     
262.         cout<<"\n1--输入学生成绩(学号，姓名，数学，语文，英语，物理，化学)\n"
     
263.                 <<"2--插入学生成绩(学号，姓名，数学，语文，英语，物理，化学)\n"
     
264.                 <<"3--输入学号删除学生成绩\n"
     
265.                 <<"4--按总分排序输出(学号，姓名，数学，语文，英语，物理，化学，总分，平均分)\n"
     
266.                 <<"0--退出\n"
     
267.                 <<"请选择你的操作：";
     
268.         cin>>mu;
     
269.         switch(mu)
     
270.         {
     
271.         case 1://第一次输入
     
272.                         if(head==NULL)//用来判断是不是第一次输入数据。
     
273.                         {
     
274.                         head=create();//调用创建        
     
275.                         showl(head);
     
276.                         err=1;
     
277.                         break;
     
278.                         }
     
279.                         cout<<"您不是第一次输入数据,请选择插入\n\n\n";
     
280.                         break;
     
281.         case 2://插入数据
     
282.                         showl(head);
     
283.                         int ip;  
     
284.                         cout<<"请输入在那个学号前面，如果没有这个学号将在最后插入"<<endl;  
     
285.                         cin>>ip;  
     
286.                         insterl(ip);
     
287.                         err=1;
     
288.                         break;
     
289.         case 3://删除数据
     
290.                         showl(head);
     
291.                     int dp;  
     
292.                         cout<<"请输入删除点如果找不到就跳出函数"<<endl;  
     
293.                         cin>>dp;  
     
294.                         deletel(head,dp);//调用删除
     
295.                         err=1;
     
296.                         break;
     
297.         case 4://排序
     
298.                 if(head!=NULL)
     
299.                 {
     
300.                         paixu(head);
     
301.                         showl(head);
     
302.                         err=1;
     
303.                         break;
     
304.                 }
     
305.                 cout<<"学生成绩数据为空,请输入数据在排序。";
     
306.                 break;
     
307.         case 0: //退出
     
308.                         err=0;
     
309.                         break;
     
310.         default://错误
     
311.                         cout<<"输入错误,请重新输入\n";
     
312.                         err=-1;
     
313.                         break;
     
314.                        
     
315.         }
     
316.     }
     
317. }
     
318. 
     

复制代码