c++实现单向链表

一、问题描述

1、题目内容：集合的并、交和差运算

编写一个能演示执行集合的并、交和差运算的程序。

2、基本要求

由用户输入两组整数分别作为两个集合的元素，由程序计算它们的交、并和差集，并将运算结果输出。

3、测试数据

测试数据为两组正整数，范围最好在0~35000之间。

S1={3，5，6，9，12，27，35}；

S2={5，8，10，12，27，31，2，51，55，63}；

运行结果：

S1ÈS2={3，5，6，8，9，10，12，27，31，35，42，51，55，63},

S1ÇS2={5，12，27}

S1-S2={3，6，9，35}。

实现提示：

以有序链表表示正整数集合。

代码：

1 //2013-3-12
  2 
  3 
  4 //list头文件
  5 
  6 //合理的设置模式（隔离变化）
  7 
  8 typedef int ElemType;
  9 
 10 //定义结点
 11 struct ListNode
 12 {
 13     ElemType data;
 14     ListNode* next;
 15 };
 16 
 17 
 18 //定义链表类
 19 //注意接口的粒度的合理性
 20 
 21 class List
 22 {
 23 private:
 24     ListNode* m_head;//头指针
 25     ListNode* m_tail;//尾指针
 26     int m_length;//链表的结点数目
 27 
 28 public:
 29     //
 30     List();
 31     //在链表的后面追加元素
 32     //重载该函数
 33     //值专递，方便输入
 34     //地址传递，提高效率
 35     void AppendNode(ListNode item);
 36     void AppendNode(ListNode* item);
 37     //清空链表
 38     void ClearList();
 39     //返回链表的长度
 40     int LengthList();
 41     //返回L中第index个元素
 42     //以0开始
 43     ListNode* GetList(int index);
 44     //遍历输出l中所有元素
 45     void TraverseList();
 46     //查找item元素，并在index中保存下标
 47     bool FindList(ListNode* item,int* index);
 48     //更新第index个元素
 49     bool UpdateList(int index,const ListNode item);
 50     //
 51     bool InsertList(ListNode* item,int index);
 52     //
 53     bool DeleteList(ListNode item);
 54 
 55     //
 56     void CopyList(List* list);
 57 };
 58 
 59 //2013-3-13
 60 
 61 //list cpp
 62 
 63 #include<iostream>
 64 
 65 #include"List.h"
 66 
 67 using namespace std;
 68 
 69 
 70 
 71 //
 72 List::List()
 73 {
 74     m_head=m_tail=NULL;
 75     m_length=0;
 76 }
 77 
 78 //ok
 79 void List::AppendNode(ListNode item)
 80 {
 81     //在堆里分配的内存 
 82     ListNode* pitem=new ListNode(item);
 83 
 84         //如果链表为空
 85     if (m_head==NULL)
 86     {
 87         m_head=pitem;
 88         m_tail=pitem;
 89         ++m_length;
 90     }else
 91     {
 92         //如果不为空
 93         m_tail->next=pitem;
 94         pitem->next=NULL;
 95         m_tail=pitem;
 96         ++m_length;
 97     }
 98 
 99 }
100 
101 //ok
102 void List::AppendNode(ListNode* item)
103 {
104     //如果链表为空
105     if (m_head==NULL)
106     {
107         m_head=item;
108         m_tail=item;
109         ++m_length;
110     }else
111     {
112         //如果不为空
113         m_tail->next=item;
114         item->next=NULL;
115         m_tail=item;//指针往后移
116         ++m_length;
117     }
118 
119 
120 }
121 
122 void List::ClearList()
123 {
124 
125     ListNode* cp;
126     ListNode* np;
127     cp=m_head;
128     while (cp!=NULL)
129     {
130         np=cp->next;
131         delete cp;
132         cp=np;
133     }
134     m_tail=m_head=NULL;
135     m_length=0;
136 
137 }
138 
139 //ok
140 int List::LengthList()
141 {
142     return m_length;
143 }
144 
145 
146 //0下标开始
147 ListNode* List::GetList(int index)
148 {
149     int readindex=index-1;
150     ListNode* finder;
151 
152     if (readindex>m_length)
153     {
154         cout<<"查找失败."<<endl;
155         return NULL;
156     }
157 
158     //first node
159     if (readindex==0)
160     {
161         return m_head;
162     }
163 
164     //last node
165     if (readindex==(m_length-1))
166     {
167         return m_tail;
168     }
169 
170     //else
171     finder=m_head;
172     for (int i = 1; i <= readindex; i++)
173     {
174         finder=finder->next;
175     }
176     return finder;
177 }
178 
179 //ok
180 void List::TraverseList()
181 {
182     ListNode* out=m_head;
183 
184     if (m_length!=0)
185     {
186         while (out!=NULL)
187         {
188             cout<<out->data<<" ";
189             out=out->next;
190         }
191     }
192 }
193 
194 
195 bool List::FindList(ListNode* item,int* index)
196 {
197     ListNode* currnode=m_head;
198     int item_index=0;
199 
200     while ((currnode->data!=item->data)&&item_index++<m_length-1)
201     {
202         currnode=currnode->next;
203     }
204 
205     if (item_index>=m_length)
206     {
207         *index=-1;
208         return false;
209     }else
210     {
211         *index=item_index+1;
212         return true;
213     }
214 }
215 
216 //ok
217 bool List::UpdateList(int index,const ListNode item)
218 {
219     ListNode* updatenode=GetList(index);
220     if (updatenode!=NULL)
221     {
222         updatenode->data=item.data;
223         return true;
224     }
225     return false;
226 }
227 
228 //2013-3-14
229 //
230 // 在链表不为空的前提下
231 //ok
232 bool List::InsertList(ListNode* item,int index)
233 {
234     //找到将要插入的前一项 
235     ListNode* previtem=GetList(index);
236 
237     if (previtem==NULL)
238     {
239         cout<<"插入失败。"<<endl;
240         return false;
241     }
242 
243     //item指向previtem的下一个元素
244     item->next=previtem->next;
245 
246     //previtem指向item
247     previtem->next=item;
248 
249     previtem=item=NULL;
250     //长度+1
251     ++m_length;
252 
253     return true;
254 }
255 
256 //
257 //ok
258 bool List::DeleteList(ListNode item)
259 {
260     //将要删除的元素的前驱变量
261     ListNode* prevdelenode=m_head;
262 
263     //要删除的元素的指针
264     ListNode* delenode=m_head;
265 
266     //
267     while ((delenode->data!=item.data)&&delenode!=NULL)
268     {
269         prevdelenode=delenode;
270         delenode=delenode->next;
271     }
272 
273     if (delenode==NULL)
274     {
275         cout<<"不存在该元素。"<<endl;
276         return false;
277     }
278 
279     //如果是删除第一个
280     if (delenode==m_head)
281     {
282         prevdelenode=NULL;
283         m_head=m_head->next;
284         delete delenode;
285         --m_length;
286         return true;
287     }
288 
289     //如果是删除最后一个
290     if (delenode==m_tail)
291     {
292         m_tail=prevdelenode;
293         m_tail->next=NULL;
294 
295         prevdelenode=NULL;
296 
297         delete delenode;
298         --m_length;
299         return true;
300     }
301 
302     //prevdelenode指向delenode的下个元素
303     prevdelenode->next=delenode->next;
304     //
305     delenode->next=NULL;
306     //
307     delete delenode;
308     //
309     --m_length;
310 
311     return true;
312 
313 
314 }
315 
316 
317 void List::CopyList(List* list)
318 {
319     ListNode node={NULL,NULL};
320     ListNode* datanode=list->m_head;
321     while (datanode!=NULL)
322     {
323         node.data=datanode->data;
324         AppendNode(node);
325         datanode=datanode->next;
326     }
327 
328 }
329 
330 //2013-3-14
331 
332 #include<iostream>
333 
334 #include"List.h"
335 
336 using namespace std;
337 
338 
339 int main()
340 {
341     List set1;
342     List set2;
343 
344     List add_set;//并集
345     List same_set;//交集
346     List cut_set;//差集
347 
348     ListNode node={NULL,NULL};
349     cout<<"请输入set1的数值，以-1结束。"<<endl;
350     while (cin>>(node.data),(node.data)!=-1)
351     {
352         set1.AppendNode(node);
353     }
354 
355 
356     cout<<"请输入set2的数值，以-1结束。"<<endl;
357     while (cin>>(node.data),(node.data)!=-1)
358     {
359         set2.AppendNode(node);
360     }
361 
362     //将set1复制到三个集合
363     add_set.CopyList(&set1);
364     same_set.CopyList(&set1);
365     cut_set.CopyList(&set1);
366 
367     ListNode set2_node={NULL,NULL},set1_node={NULL,NULL};
368     int nothing=0;//作为函数参数引用
369     //遍历set2集合
370     for (int i = 1; i <= set2.LengthList(); i++)
371     {
372 
373         set2_node.data=set2.GetList(i)->data;
374 
375         //add_set
376         if (!add_set.FindList(&set2_node,¬hing))//NULL=worng
377         {
378             add_set.AppendNode(set2_node);
379         }
380 
381         //cut_set
382         if (cut_set.FindList(&set2_node,¬hing))
383         {
384             cut_set.DeleteList(set2_node);
385         }
386 
387     }
388 
389     //遍历set1集合
390     for (int i = 1; i <=set1.LengthList(); i++)
391     {
392         //same_set
393         set1_node.data=set1.GetList(i)->data;
394 
395         if (!set2.FindList(&set1_node,¬hing))
396         {
397             same_set.DeleteList(set1_node);
398         }
399     }
400 
401     cout<<endl<<"并集:";
402     add_set.TraverseList();
403     cout<<endl<<"交集:";
404     same_set.TraverseList();
405     cout<<endl<<"差集:";
406     cut_set.TraverseList();
407     cout<<endl;
408 
409     char ch=getchar();
410     return 0;
411 }

原文链接: https://www.cnblogs.com/pandang/p/4849184.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍