单链表程序范例(C++)

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