數據結構學習(二)——單鏈表的操作之頭插法和尾插法創建鏈表

http://blog.csdn.net/abclixu123/article/details/8210109

鏈表也是線性表的一種，與順序表不同的是，它在內存中不是連續存放的。在C語言中，鏈表是通過指針相關實現的。而單鏈表是鏈表的其中一種，關于單鏈表就是其節點中有數據域和只有一個指向下個節點的指針域。創建單鏈表的方法有兩種，分別是頭插法和尾插法。

所謂頭插法，就是按節點的逆序方法逐漸將結點插入到鏈表的頭部。反之尾插法就是按節點的順序逐漸將節點插入到鏈表的尾部。相對來說，頭插法要比尾插法算法簡單，但是最后產生的鏈表是逆序的，即第一個輸入的節點實際是鏈表的最后一個節點。而為了習慣，通常用尾插法來創建鏈表。下面的代碼就是實現了頭插法和尾插法。代碼在Linux下調試通過。

[cpp]?view plaincopy
print?
  1. #include?<stdio.h>??
  2. #include?<stdlib.h>??
  3. ??
  4. typedef?struct?link??
  5. {??
  6. ????char?data;??
  7. ????struct?link?*next;??
  8. }linklist;??
  9. ??
  10. linklist?*CreateList_Front();???//頭插法創建單鏈表??
  11. linklist?*CreateList_End();?????//尾插法創建單鏈表??
  12. void?ShowLinklist(linklist?*h);?//輸出顯示鏈表??
  13. ??
  14. int?main(void)??
  15. {??
  16. ????int?choice;??
  17. ????linklist?*head;??
  18. ??
  19. ????//head?=?(linklist*)malloc(sizeof(linklist));??
  20. ????while(1)??
  21. ????{??
  22. ????????printf("單鏈表的創建\n");??
  23. ????????printf("1.使用頭插法創建單鏈表\n");??
  24. ????????printf("2.使用尾插法創建單鏈表\n");??
  25. ????????printf("3.鏈表輸出顯示\n");??
  26. ????????printf("4.退出\n");??
  27. ????????printf("做出選擇：\n");??
  28. ????????scanf("%d",&choice);??
  29. ????????switch(choice)??
  30. ????????{??
  31. ????????//頭插法??
  32. ????????case?1:??
  33. ????????????head?=?CreateList_Front();??
  34. ????????????break;??
  35. ????????//尾插法??
  36. ????????case?2:??
  37. ????????????head?=?CreateList_End();??
  38. ????????????break;??
  39. ????????//輸出鏈表??
  40. ????????case?3:??
  41. ????????????ShowLinklist(head);??
  42. ????????????break;??
  43. ????????//退出程序??
  44. ????????case?4:??
  45. ????????????return?0;??
  46. ????????????break;??
  47. ????????default:??
  48. ????????????break;??
  49. ????????}??
  50. ????}??
  51. ????return?1;??
  52. }??
  53. ??
  54. linklist?*CreateList_Front()??
  55. {??
  56. ????linklist?*head,?*p;??
  57. ????char?ch;??
  58. ??
  59. ????head?=?NULL;??
  60. ????printf("依次輸入字符數據(‘#’表示輸入結束):\n");??
  61. ????ch?=?getchar();??
  62. ????while(ch?!=?'#')??
  63. ????{??
  64. ????????p?=?(linklist*)malloc(sizeof(linklist));??
  65. ????????p->data?=?ch;??
  66. ????????p->next?=?head;??
  67. ????????head?=?p;??
  68. ????????ch?=?getchar();?????????????//頭插法算法簡單?核心就兩句p->next?=?head;head?=?p;??
  69. ????}??
  70. ????return?head;??
  71. }??
  72. ??
  73. linklist?*CreateList_End()??
  74. {??
  75. ????linklist?*head,?*p,?*e;??
  76. ????char?ch;??
  77. ??
  78. ????head?=?NULL;??
  79. ????e?=?NULL;??
  80. ????printf("請依次輸入字符數據('#'表示輸入結束):\n");??
  81. ????ch?=?getchar();??
  82. ????while(ch?!=?'#')??
  83. ????{??
  84. ????????p?=?(linklist*)malloc(sizeof(linklist));??
  85. ????????p->data?=?ch;??
  86. ????????if(head?==?NULL)????????//先判斷輸入的是不是第一個節點??
  87. ????????{??
  88. ????????????head?=?p;?????????????
  89. ????????}??
  90. ????????else??
  91. ????????{??
  92. ????????????e->next?=?p;?????//e始終指向輸入的最后一個節點??
  93. ????????}??
  94. ????????e?=?p;??
  95. ????????ch?=?getchar();???????????
  96. ????}??
  97. ????if(e?!=?NULL)???????????????//如果鏈表不為空，則最后節點的下一個節點為空??
  98. ????{??
  99. ????????e->next?=?NULL;??
  100. ????}??
  101. ????return?head;????????????????//尾插法比頭插法復雜一些，程序中要做兩次判斷，分別是判斷第一個節點和最后一個節點的判斷。且消耗多一個指針變量e。??
  102. }??
  103. ??
  104. void?ShowLinklist(linklist?*h)??
  105. {??
  106. ????linklist?*p;??
  107. ??
  108. ????p?=?h;??
  109. ????while(p?!=?NULL)??
  110. ????{??
  111. ????????printf("%c?",?p->data);??
  112. ????????p?=?p->next;??
  113. ????}??
  114. ????printf("\n");??
  115. }??

通過上述代碼可以看出，尾插法確實比頭插法復雜點，多了兩個判斷。但是這是可以解決的，通過添加一個頭節點，此節點不存放數據域，只是存放指向下個節點的指針域就是了。這樣就可以免除掉兩次判斷。整體也要清晰點了。下面是增加一個頭節點后尾插法的實現代碼：

[cpp]?view plaincopy
print?
  1. #include?<stdio.h>??
  2. #include?<stdlib.h>??
  3. ??
  4. typedef?struct?list??
  5. {??
  6. ????char?data;??
  7. ????struct?list?*next;??
  8. }linklist;??
  9. ??
  10. linklist?*CreateList_End();?????//尾插法創建鏈表??
  11. void?ShowLinklist(linklist?*h);?//輸出顯示鏈表??
  12. ??
  13. int?main(void)??
  14. {??
  15. ????linklist?*head;??
  16. ??
  17. ????printf("使用尾插法創建鏈表(改進版)\n");??
  18. ????printf("請依次輸入字符數據(‘#’表示輸入結束):\n");??
  19. ????head?=?CreateList_End();????????//創建鏈表??
  20. ????ShowLinklist(head);?????????????//輸出鏈表??
  21. }??
  22. ??
  23. linklist?*CreateList_End()??
  24. {??
  25. ????linklist?*head,?*p,?*e;??
  26. ????char?ch;??
  27. ??
  28. ????head?=?(linklist*)malloc(sizeof(linklist));??
  29. ????e?=?head;???????????//讓e指向頭節點??
  30. ????ch?=?getchar();??
  31. ????while(ch?!=?'#')??
  32. ????{??
  33. ????????p?=?(linklist*)malloc(sizeof(linklist));??
  34. ????????p->data?=?ch;???
  35. ????????e->next?=?p;?????//把新節點添加到表尾??
  36. ????????e?=?p;??????????????//把指針指向新節點??
  37. ????????ch?=?getchar();??
  38. ????}?????
  39. ????e->next?=?NULL;??????????//尾節點的指針域置空??
  40. ????return?head;??
  41. }??
  42. ??
  43. void?ShowLinklist(linklist?*h)??
  44. {??
  45. ????linklist?*p;??
  46. ??
  47. ????p?=?h->next;??
  48. ????while(p?!=?NULL)??
  49. ????{??
  50. ????????printf("%c?",?p->data);??
  51. ????????p?=?p->next;??
  52. ????}??
  53. ????printf("\n");??
  54. }??

添加了一個頭節點后代碼是不是就要清晰點了呢？

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/384074.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/384074.shtml
英文地址，請注明出處：http://en.pswp.cn/news/384074.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

信號的基本概念以及信號的產生

信號的基本概念以及信號的產生

一. 信號產生的場景 1. 用戶輸入命令, 在shell 啟動一個前臺進程 ???? 2. 當用戶按一下 Ctrl C 的時候,從鍵盤產生一個硬件中斷 ???? 3. 此時CPU 正在執行這個進程的帶代碼, 則該進程的執行代碼暫停執行, CPU 從用戶態切換到內核態處理該硬件中斷. ???? 4. 中斷…
閱讀更多...
HDU - 1028——母函數入門

HDU - 1028——母函數入門

【題目描述】 “Well, it seems the first problem is too easy. I will let you know how foolish you are later.” feng5166 says. “The second problem is, given an positive integer N, we define an equation like this: Na[1]a[2]a[3]…a[m]; a[i]>0,1<m<N;…
閱讀更多...
信號的阻塞

信號的阻塞

一. 阻塞信號 1.信號的相關概念 ????(1) 遞達: 實際執行信號的處理動作稱為信號的遞達 ????(2) 未決: 信號從產生到遞達之間的過程叫做信號的未決 ????(3) 阻塞: 進程可以選擇阻塞某個信號, 被阻塞的信號產生時將保持在未決狀態, 直到進程解除該信號的屏蔽, 才…
閱讀更多...
POJ 1511 Invitation Cards——Dijkstra優先隊列優化+反向建圖

POJ 1511 Invitation Cards——Dijkstra優先隊列優化+反向建圖

【題目描述】 In the age of television, not many people attend theater performances. Antique Comedians of Malidinesia are aware of this fact. They want to propagate theater and, most of all, Antique Comedies. They have printed invitation cards with all the…
閱讀更多...
鏈棧 尹成

鏈棧 尹成

http://blog.csdn.net/itcastcpp/article/details/39271661 今天&#xff0c;我們一起用C寫鏈棧&#xff0c;具體如下。 LinkStack.h具體內容&#xff1a; [cpp] view plaincopy #include "StackNode.h" template<typename Type> class LinkStack{ publ…
閱讀更多...
信號的捕捉以及SIGCHLD信號

信號的捕捉以及SIGCHLD信號

一. 信號的捕捉定義 用戶提供一個處理函數, 要求內核在處理信號時必須切換到用戶態,執行這個函數, 這種方式就叫做信號的捕捉 二. 圖解信號的捕捉過程 1. 由上圖可以看出,當處理信號的執行動作時用戶自定義的時候,此時就需返回該函數去調用該函數, 這就叫做信號的捕捉. 以前我…
閱讀更多...
鏈隊 尹成

鏈隊 尹成

http://blog.csdn.net/itcastcpp/article/details/39271691 今天&#xff0c;我們一起用C寫一個鏈對&#xff0c;具體如下所示。 LinkQueue.h具體內容如下&#xff1a; [cpp] view plaincopy #include "QueueNode.h" template<typename Type> class LinkQueu…
閱讀更多...
強連通分量入門——Trajan算法

強連通分量入門——Trajan算法

今天學習了強連通分量。 【參考博客】 如果覺得我講的有些地方難以理解或者存在問題&#xff08;歡迎留言&#xff09;&#xff0c;可以看一下我借鑒的一些大佬的博客&#xff1a; 傳送門1 傳送門2 【知識儲備】 首先我們需要對幾個定義有一些概念&#xff1a; 強連通&#xff…
閱讀更多...
最小棧的實現

最小棧的實現

所謂最小棧, 就是當前棧頂元素最小, 我們可以這樣做, 每次在入棧之前, 將待入棧元素與棧頂元素相比, 每次現將待入棧的元素先入棧, 再將帶入棧的元素和較小的元素入棧, 這樣就可以保證每次棧頂元素是最小元素. 在出棧的時候規定每次出棧兩個元素,這樣就可以保證在出棧之后棧頂元…
閱讀更多...
用C++實現單鏈表的創建、逆置和輸出 的兩種方法

用C++實現單鏈表的創建、逆置和輸出 的兩種方法

http://blog.csdn.net/lfeng_coding/article/details/47300563 題目描述&#xff1a;在已知單鏈表頭節點的情況下&#xff0c;設計算法逆置單鏈表并輸出 方法一&#xff1a;采用首先將頭節點指向空&#xff0c;讓其變為尾節點&#xff0c;然后利用中間節點 p、q 將其后的節點一…
閱讀更多...
兩個棧實現一個隊列

兩個棧實現一個隊列

利用兩個棧實現一個隊列思路是這樣的. 首先這個隊列包含兩個棧, 然后一個棧用來入隊列, 一個棧用來出隊列 typedef struct QueBy2Stack {SeqStack input;SeqStack output; }QueBy2Stack; 1. 初始化 void QueBy2StackInit(QueBy2Stack* stack) {if(stack NULL){return;//非法…
閱讀更多...
HDU 5934：Boom——強連通分量+縮點

HDU 5934：Boom——強連通分量+縮點

【題目描述】 There are N bombs needing exploding.Each bomb has three attributes: exploding radius ri, position (xi,yi) and lighting-cost ci which means you need to pay ci cost making it explode.If a un-lighting bomb is in or on the border the exploding ar…
閱讀更多...
Linux--線程死鎖

Linux--線程死鎖

http://blog.csdn.net/gebushuaidanhenhuai/article/details/73799824 線程為什會死鎖&#xff1f;&#xff1f;“鎖”又是什么東西&#xff1f;我們這篇博客主要講一下為什么要給線程加鎖&#xff0c;為什么會出現線程死鎖&#xff0c;線程死鎖怎么解決。 互斥鎖 在我的上篇博…
閱讀更多...
兩個隊列實現一個棧

兩個隊列實現一個棧

用兩個隊列實現一個棧的原理是這樣的. 規定兩個隊列, 必須有一個隊列是非空, 一個隊列是空.每次入棧時必須往非空隊列中入, 而每次出棧時, 必須將非空隊列里的元素裝到空隊列中, 直到非空隊列中只有一個元素時, 此時就將剩下的這個元素出棧即可. 而取棧頂元素時, 和出棧一樣, 先…
閱讀更多...
POJ-1144 Network——Trajan+割點

POJ-1144 Network——Trajan+割點

【題目描述】 A Telephone Line Company (TLC) is establishing a new telephone cable network. They are connecting several places numbered by integers from 1 to N . No two places have the same number. The lines are bidirectional and always connect together tw…
閱讀更多...
Linux--生產者與消費者

Linux--生產者與消費者

http://blog.csdn.net/gebushuaidanhenhuai/article/details/74011636 基本概念 提到生產者和消費者&#xff0c;我們最有可能想到的是商店賣東西&#xff0c;顧客在貨架上(緩沖區&#xff09;買東西。 生產者消費者問題&#xff0c;其實是一個多線程同步問題的經典案例。該問…
閱讀更多...
進程的掛起以及可重入函數

進程的掛起以及可重入函數

相關接口 ????pause 函數用于將進程掛起. 如果信號的處理動作是終止進程, 則進程終止, pause 函數沒有返回值; 如果信號的處理動作是忽略, 則進程被掛起, pause函數不返回, 如果信號的處理動作是捕捉, 則調用信號處理動作之后pause 返回 -1.來看一段代碼 #include<s…
閱讀更多...
POJ1236Network of Schools——強連通分量縮點建圖

POJ1236Network of Schools——強連通分量縮點建圖

【題目描述】 A number of schools are connected to a computer network. Agreements have been developed among those schools: each school maintains a list of schools to which it distributes software (the “receiving schools”). Note that if B is in the distri…
閱讀更多...
C——通過調用函數分配內存

C——通過調用函數分配內存

http://blog.csdn.net/u012627502/article/details/3579724 1&#xff09;以返回值方式返回&#xff1a;把動態分配的存儲位置地址&#xff0c;賦值給指針類型返回值&#xff08;不同于被調用函數的自動變量地址&#xff09; 2&#xff09;以形參形式返回&#xff1a;二級指針類…
閱讀更多...
gdb調試多進程程序

gdb調試多進程程序

1.gdb下調試多進程程序只需要以下幾條命令即可 ???????? ????除此之外還可以查看正在調試的進程 info inferiors, 同時也可以將當前正在調試的進程切換到另外一個進程中讓其取運行 ????2.代碼調試演示 #include<stdio.h> #include<stdlib.h> #…
閱讀更多...
最新文章

Copyright @ 2022~2023