单链表范例

  1 #include <iostream>
  2 #include <stdlib.h>
  3 using namespace std;
  4 typedef    struct tagNote
  5 {
  6     int                nNumber;
  7     struct tagNote*    pNext;
  8 }Note;
  9 bool        CreateList(Note*& pListHead);
 10 bool        DisposeList(Note*& pListHead);
 11 bool        ListInsertItem(Note*& pListHead,int nValue,int nIndex=-1);
 12 bool        ListItemPushBack(Note*& pListHead,int nValue);
 13 bool        ListItemPushFront(Note*& pListHead,int nValue);
 14 bool        ListDeleteItem(Note*& pListHead,int nIndex=-1);
 15 bool        ListDeleteFirstItem(Note*& pListHead);
 16 bool        ListDeleteLastItem(Note*& pListHead);
 17 bool        ListGetFirstItem(Note*& pListHead,int& nValue);
 18 bool        ListGetLastItem(Note*& pListHead,int& nValue);
 19 bool        ListGetItemNumber(Note*& pListHead,int& nNumber);
 20 bool        ListGetItem(Note*& pListHead,int& nValue,int nIndex=-1);
 21 bool        ListPrint(Note*& pListHead);
 22 void        ShowMenu();
 23 
 24 int            main()
 25 {
 26     Note*        pListHead = NULL;
 27     int nSelect = 0;
 28     bool        isLoop = true;
 29     int        nTmpInput1,nTmpInput2,nTmpOut;
 30     while (isLoop)
 31     {
 32         ShowMenu();
 33         cin>>nSelect;
 34         switch (nSelect)
 35         {
 36         case 0:
 37             isLoop = false;
 38             break;
 39         case 1:
 40             if (!CreateList(pListHead))
 41             {
 42                 cout<<"创建链表失败"<<endl;
 43             }
 44             else
 45             {
 46                 cout<<"创建链表成功"<<endl;
 47             }
 48             break;
 49         case 2:
 50             cout<<"请输入插入项的值："<<endl;
 51             cin>>nTmpInput1;
 52             if (!ListItemPushFront(pListHead,nTmpInput1))
 53             {
 54                 cout<<"输入插入值("<<nTmpInput1<<")失败"<<endl;
 55             }
 56             else
 57             {
 58                 cout<<"插入项成功"<<endl;
 59             }
 60             break;
 61         case 3:
 62             cout<<"请输入插入项的值："<<endl;
 63             cin>>nTmpInput1;
 64             if (!ListItemPushBack(pListHead,nTmpInput1))
 65             {
 66                 cout<<"输入插入值("<<nTmpInput1<<")失败"<<endl;
 67             }
 68             else
 69             {
 70                 cout<<"插入项成功"<<endl;
 71             }
 72             break;
 73         case 4:
 74             cout<<"请输入插入项的值："<<endl;
 75             cin>>nTmpInput1;
 76             cout<<"请输入插入项的位置："<<endl;
 77             cin>>nTmpInput2;
 78             if (!ListInsertItem(pListHead,nTmpInput1,nTmpInput2))
 79             {
 80                 cout<<"输入插入值("<<nTmpInput1<<")在位置（"<<nTmpInput2<<"）失败"<<endl;
 81             }
 82             else
 83             {
 84                 cout<<"插入项成功"<<endl;
 85             }
 86             break;
 87         case 5:
 88             if (!ListGetFirstItem(pListHead,nTmpOut))
 89             {
 90                 cout<<"取第一个值失败"<<endl;
 91             }
 92             else
 93             {
 94                 cout<<"取第一个值为"<<nTmpOut<<endl;
 95             }
 96             break;
 97         case 6:
 98             if (!ListGetLastItem(pListHead,nTmpOut))
 99             {
100                 cout<<"取最后一个值失败"<<endl;
101             }
102             else
103             {
104                 cout<<"取最后一个值为"<<nTmpOut<<endl;
105             }
106             break;
107         case 7:
108             cout<<"请输入要取值的位置："<<endl;
109             cin>>nTmpInput1;
110             if (!ListGetItem(pListHead,nTmpOut,nTmpInput1))
111             {
112                 cout<<"取值在位置（"<<nTmpInput1<<"）失败"<<endl;
113             }
114             else
115             {
116                 cout<<"取值在位置（"<<nTmpInput1<<"）值为"<<nTmpOut<<endl;
117             }
118             break;
119         case 8:
120             if (!ListDeleteFirstItem(pListHead))
121             {
122                 cout<<"删除第一个项目失败"<<endl;
123             }
124             else
125             {
126                 cout<<"删除第一个项目成功"<<endl;
127             }
128             break;
129         case 9:
130             if (!ListDeleteLastItem(pListHead))
131             {
132                 cout<<"删除最后一个项目失败"<<endl;
133             }
134             else
135             {
136                 cout<<"删除最后一个项目成功"<<endl;
137             }
138             break;
139         case 10:
140             cout<<"请输入要删除项的位置："<<endl;
141             cin>>nTmpInput1;
142             if (!ListDeleteItem(pListHead,nTmpInput1))
143             {
144                 cout<<"删除第("<<nTmpInput1<<")项目失败"<<endl;
145             }
146             else
147             {
148                 cout<<"删除第("<<nTmpInput1<<")项目成功"<<endl;
149             }
150         case 11:
151             if (!ListGetItemNumber(pListHead,nTmpOut))
152             {
153                 cout<<"取项目个数失败"<<endl;
154             }
155             else
156             {
157                 cout<<"取项目个数为"<<nTmpOut<<endl;
158             }
159             break;
160         case 12:
161             if (!DisposeList(pListHead))
162             {
163                 cout<<"销毁链失败"<<endl;
164             }
165             else
166             {
167                 cout<<"销毁链成功"<<endl;
168             }
169         case 13:
170             ListPrint(pListHead);
171             break;
172         default:
173             cout<<"输入无效菜单项"<<endl;
174             break;
175         }
176         if (isLoop)
177         {
178             system("pause");
179             system("cls");
180         }
181     }
182     DisposeList(pListHead);
183     return    0;
184 }
185 void        ShowMenu()
186 {
187     cout<<"================================================================"<<endl;
188     cout<<"1.	创建一个单向链表"<<endl;
189     cout<<"2.	从头部插入一个项"<<endl;
190     cout<<"3.	从尾部插入一个项"<<endl;
191     cout<<"4.	从指定位置插入一个项"<<endl;
192     cout<<"5.	取出第一个项的值"<<endl;
193     cout<<"6.	取出最后一个项的值"<<endl;
194     cout<<"7.	取出指定项的值"<<endl;
195     cout<<"8.	删除第一个项的值"<<endl;
196     cout<<"9.	删除最后一个项的值"<<endl;
197     cout<<"10.	删除指定项的值"<<endl;
198     cout<<"11.	得到表中的项目个数"<<endl;
199     cout<<"12.	销毁当前链表"<<endl;
200     cout<<"13.	打印整个链表"<<endl;
201     cout<<"0.	退出程序"<<endl;
202     cout<<"================================================================"<<endl;
203     cout<<"请输入你的选择：";
204 }
205 bool        CreateList(Note*& pListHead)
206 {
207     if (pListHead != NULL)
208     {
209         return    false;
210     }
211     else
212     {
213         pListHead = new Note;
214         pListHead->nNumber    = 0;
215         pListHead->pNext        = NULL;
216         return    true;
217     }
218 }
219 bool        DisposeList(Note*& pListHead)
220 {
221     if (pListHead == NULL)
222     {
223         return    false;
224     }
225     else
226     {
227         while (ListDeleteLastItem(pListHead))
228         {
229             ;
230         }
231         delete    pListHead;
232         pListHead    = NULL;
233         return    true;
234     }
235 }
236 bool        ListInsertItem(Note*& pListHead,int nValue,int nIndex)
237 {
238     if (pListHead == NULL)
239     {
240         return false;
241     }
242     int nNum = 0;
243     ListGetItemNumber(pListHead,nNum);
244     if (nIndex > nNum)
245     {
246         return    false;
247     }
248     else if (nIndex == -1)
249     {
250         nIndex    = nNum;
251     }
252     Note*    pTmp = pListHead;
253     for (int i=0;i<nIndex;i++)
254     {
255         pTmp    = pTmp->pNext;
256     }
257     Note*    pNext = pTmp->pNext;
258     pTmp->pNext    = new Note;
259     pTmp->pNext->nNumber    = nValue;
260     pTmp->pNext->pNext    = pNext;
261     return    true;
262 }
263 bool        ListItemPushFront(Note*& pListHead,int nValue)
264 {
265     return    ListInsertItem(pListHead,nValue,0);
266 }
267 bool        ListItemPushBack(Note*& pListHead,int nValue)
268 {
269     return    ListInsertItem(pListHead,nValue,-1);
270 }
271 bool        ListDeleteItem(Note*& pListHead,int nIndex)
272 {
273     if (pListHead == NULL)
274     {
275         return false;
276     }
277     int nNum = 0;
278     ListGetItemNumber(pListHead,nNum);
279     if (nNum == 0)
280     {
281         return    false;
282     }
283     if (nIndex > nNum)
284     {
285         return    false;
286     }
287     else if (nIndex == -1)
288     {
289         nIndex    = nNum-1;
290     }
291     Note*    pTmp = pListHead;
292     for (int i=0;i<nIndex;i++)
293     {
294         pTmp    = pTmp->pNext;
295     }
296     Note*    pNext = pTmp->pNext->pNext;
297     delete    pTmp->pNext;
298     pTmp->pNext    = pNext;
299     return    true;
300 }
301 bool        ListDeleteFirstItem(Note*& pListHead)
302 {
303     return    ListDeleteItem(pListHead,0);
304 }
305 bool        ListDeleteLastItem(Note*& pListHead)
306 {
307     return    ListDeleteItem(pListHead,-1);
308 }
309 bool        ListGetItem(Note*& pListHead,int& nValue,int nIndex)
310 {
311     if (pListHead == NULL)
312     {
313         return false;
314     }
315     int nNum = 0;
316     ListGetItemNumber(pListHead,nNum);
317     if (nIndex >= nNum)
318     {
319         return    false;
320     }
321     else if (nIndex == -1)
322     {
323         nIndex    = nNum;
324     }
325     Note*    pTmp = pListHead;
326     for (int i=0;i<=nIndex;i++)
327     {
328         pTmp    = pTmp->pNext;
329     }
330     nValue    = pTmp->nNumber;
331     return    true;
332 }
333 bool        ListGetFirstItem(Note*& pListHead,int& nValue)
334 {
335     return    ListGetItem(pListHead,nValue,0);
336 }
337 bool        ListGetLastItem(Note*& pListHead,int& nValue)
338 {
339     return    ListGetItem(pListHead,nValue,-1);
340 }
341 bool        ListGetItemNumber(Note*& pListHead,int& nNumber)
342 {
343     if (pListHead == NULL)
344     {
345         return false;
346     }
347     Note*    pTmp = pListHead->pNext;
348     nNumber    = 0;
349     while (pTmp != NULL)
350     {
351         nNumber++;
352         pTmp    = pTmp->pNext;
353     }
354     return    true;
355 }
356 bool        ListPrint(Note*& pListHead)
357 {
358     if (pListHead == NULL)
359     {
360         return    false;
361     }
362     Note* pTmp = pListHead->pNext;
363     int nIndex = 0;
364     while (pTmp != NULL)
365     {
366         cout<<nIndex++<<":	"<<pTmp->nNumber<<endl;
367         pTmp    = pTmp->pNext;
368     }
369     return    true;
370 }