（C語言版）棧和隊列（一）——實現鏈式棧和鏈式隊列的基本操作以及遇到的問題

http://blog.csdn.net/fisherwan/article/details/20055179

首先要感謝這位大牛的一篇博客，地址如下：http://blog.csdn.net/hguisu/article/details/7674195

當然還有網上一些其他的資料，今天自己寫了一下鏈式棧和鏈式隊列的程序。其中在釋放內存的時候遇到了些許問題，通過調，找出了原因，在這里我與大家分享一下。

（1）鏈式棧的相關代碼塊

Stack.h 頭文件——定義了節點結構和鏈式棧結構，以及基本操作函數的聲明部分

[cpp]?view plain?copy
  1. #ifndef?_STACK_H_H??
  2. #define?_STACK_H_H??
  3. ??
  4. typedef?struct?Node??
  5. {??
  6. ????int?data;??
  7. ????struct?Node?*pNext;??
  8. }NODE,?*pNODE;??
  9. ??
  10. typedef?struct?Stack??
  11. {??
  12. ????pNODE?top;??
  13. }STACK,?*pSTACK;??
  14. ??
  15. //棧初始化??
  16. void?InitStack(pSTACK?stack);??
  17. ??
  18. //入棧??
  19. void?PushStack(pSTACK?stack,?int?data);??
  20. ??
  21. //出棧??
  22. void?PopStack(pSTACK?stack,?int?*data);??
  23. ??
  24. //判斷棧是否為空??
  25. int?IsEmptyStack(pSTACK?stack);??
  26. ??
  27. //獲得棧頂元素??
  28. int?GetTopStack(pSTACK?stack);??
  29. ??
  30. //釋放內存??
  31. void?FreeMemory(pSTACK?stack);??
  32. ??
  33. #endif??


Stack.cpp 源文件——定義鏈式棧的基本操作函數的定義

說明：一開始對棧初始化，但是這個棧是沒有頭節點的，直接定義了一個指針（top）剛開始指向NULL。

入棧的時候就是讓top指針始終指向棧頂元素，入棧的節點的指針指向top指針，這樣不斷的進行入棧操作，節點不斷增加，但是top指針一直是指針最后插入的節點。

出棧的時候就是從top指針指向的節點還是釋放，然后讓top指針指向被釋放節點的下一個節點，這樣節點不斷釋放，top指針不斷向下移動。

所以，棧就成了一個“先進后出”的結構。

[cpp]?view plain?copy
  1. #include?"Stack.h"??
  2. #include?<stdlib.h>??
  3. #include?<stdio.h>??
  4. ??
  5. //棧初始化??
  6. void?InitStack(pSTACK?stack)??
  7. {??
  8. ????stack->top?=?NULL;??
  9. }??
  10. ??
  11. //入棧??
  12. void?PushStack(pSTACK?stack,?int?data)??
  13. {??
  14. ????pNODE?p_new?=?(pNODE)malloc(sizeof(NODE));??
  15. ??
  16. ????if?(NULL?==?p_new)??
  17. ????{??
  18. ????????printf("內存分配失敗！\n");??
  19. ????????exit(EXIT_FAILURE);??
  20. ????}??
  21. ??????
  22. ????p_new->data?=?data;??
  23. ????p_new->pNext?=?stack->top;?//這里要注意??
  24. ????stack->top?=?p_new;??
  25. }??
  26. ??
  27. //出棧??
  28. void?PopStack(pSTACK?stack,?int?*data)??
  29. {??
  30. ????pNODE?p_delete?=?stack->top;??
  31. ??
  32. ????if?(IsEmptyStack(stack))??
  33. ????????exit(EXIT_FAILURE);??
  34. ??
  35. ????*data?=?p_delete->data;??
  36. ????stack->top?=?p_delete->pNext;??
  37. ????free(p_delete);??
  38. ????p_delete?=?NULL;??
  39. }??
  40. ??
  41. //判斷棧是否為空??
  42. int?IsEmptyStack(pSTACK?stack)??
  43. {??
  44. ????if?(stack->top?==?NULL)??
  45. ????????return?1;??
  46. ????else??
  47. ????????return?0;??
  48. }??
  49. ??
  50. //獲得棧頂元素??
  51. int?GetTopStack(pSTACK?stack)??
  52. {??
  53. ????int?data;??
  54. ????if?(stack->top?==?NULL)??
  55. ????????exit(EXIT_FAILURE);??
  56. ??
  57. ????data?=?stack->top->data;??
  58. ????return?data;??
  59. }??
  60. ??
  61. //釋放內存??
  62. void?FreeMemory(pSTACK?stack)??
  63. {??
  64. ????pNODE?p_delete?=?NULL;??
  65. ??
  66. ????while?(stack->top?!=?NULL)??
  67. ????{??
  68. ????????p_delete?=?stack->top;??
  69. ????????stack->top?=?p_delete->pNext;??
  70. ????????free(p_delete);??
  71. ????????p_delete?=?NULL;??
  72. ????}??
  73. }??

main.cpp? 測試程序——通過簡單的交互界面測試函數的功能

[cpp]?view plain?copy
  1. #include?<stdio.h>??
  2. #include?"Stack.h"??
  3. ??
  4. int?main(void)??
  5. {??
  6. ????int?number,?i,?data,?flag;??
  7. ????STACK?s;??
  8. ????InitStack(&s);??
  9. ??????
  10. ????printf("請輸入入棧個數：");??
  11. ????scanf("%d",?&number);??
  12. ????for?(i=1;?i<number+1;?i++)??
  13. ????{??
  14. ????????printf("請輸入第%d個棧點元素值：",?i);??
  15. ????????scanf("%d",?&data);??
  16. ????????PushStack(&s,?data);??
  17. ????}??
  18. ??????
  19. ????PopStack(&s?,&data);??
  20. ????printf("出棧的元素值為：%d\n",?data);??
  21. ??
  22. ????data?=?GetTopStack(&s);??
  23. ????printf("當前棧頂元素值為：%d\n",?data);??
  24. ??
  25. ????FreeMemory(&s);??
  26. ????flag?=?IsEmptyStack(&s);??
  27. ????if?(flag)??
  28. ????????printf("內存釋放成功！\n");??
  29. ????else??
  30. ????????printf("內存釋放失敗！\n");??
  31. ??
  32. ????return?0;??
  33. }??

（2）鏈式隊列的相關代碼

Queue.h 頭文件——定義了節點結構和隊列結構，以及鏈式隊列的基本操作函數的聲明

[cpp]?view plain?copy
  1. #ifndef?_QUEUE_H_H??
  2. #define?_QUEUE_H_H??
  3. ??
  4. typedef?struct?Node??
  5. {??
  6. ????int?data;??
  7. ????struct?Node?*pNext;??
  8. }NODE,?*pNODE;??
  9. ??
  10. typedef?struct?Queue??
  11. {??
  12. ????pNODE?front;??????
  13. ????pNODE?rear;??
  14. }QUEUE,?*pQUEUE;??
  15. ??
  16. //初始化隊列??
  17. void?InitQueue(pQUEUE?queue);??
  18. ??
  19. //入隊列??
  20. void?EnQueue(pQUEUE?queue,?int?data);??
  21. ??
  22. //出隊列??
  23. void?DeQueue(pQUEUE?queue,?int?*data);??
  24. ??
  25. //判斷隊列是否為空??
  26. int?IsEmptyQueue(pQUEUE?queue);??
  27. ??
  28. //獲得隊頭元素值??
  29. int?GetFrontQueue(pQUEUE?queue);??
  30. ??
  31. //釋放內存??
  32. void?FreeMemory(pQUEUE?queue);??
  33. ??
  34. #endif??

Queue.cpp 源文件——定義了基本操作函數的定義

說明：一開始對鏈式隊列進行初始化，這里就創建了一個節點（但是記得后面釋放內存的時候這里也要釋放），創建了這個節點是為了方便后面的操作，這樣一開始隊列的頭指針和尾指針都指向了這個節點，但是此時的隊列是空的，就像循環鏈表里頭節點不參與運行是一樣的道理。

入隊列的時候就是進入的節點排在初始化時創建的節點后面，然后尾指針指針指著新進入的節點，但是頭指針不動，節點不斷進入隊列，尾指針不斷向后移動，保持尾指針一直指著剛進入的節點。

出隊列的時候就是讓頭指針指向的節點的指針指向要釋放節點的下一個節點，節點不斷出隊列，這里頭指針實質上并沒有移動，但是它指向的節點的指針一直在變化，一直保持者指向要釋放節點的下一個節點，但是這里要注意，就是當隊列中只剩下一個節點的時候（這里不包含初始化創建的那個節點），釋放了這個節點以后尾指針成了野指針，那么這個時候就要讓尾指針和頭指針指向同一位置，那么這樣判斷隊列是否為空的時候就是空了。

[cpp]?view plain?copy
  1. //鏈式隊列代碼??
  2. #include?<stdlib.h>??
  3. #include?<stdio.h>??
  4. #include?"Queue.h"??
  5. ??
  6. //初始化隊列??
  7. void?InitQueue(pQUEUE?queue)??
  8. {??
  9. ????queue->front?=?(pNODE)malloc(sizeof(NODE));??
  10. ????queue->front->data?=?0;??
  11. ????queue->front->pNext?=?NULL;??
  12. ??
  13. ????if?(NULL?==?queue->front)??
  14. ????{??
  15. ????????printf("內存分配失敗！\n");??
  16. ????????exit(EXIT_FAILURE);??
  17. ????}??
  18. ??
  19. ????queue->rear?=?queue->front;??
  20. }??
  21. ??
  22. //入隊列??
  23. void?EnQueue(pQUEUE?queue,?int?data)??
  24. {??
  25. ????pNODE?p_new?=?(pNODE)malloc(sizeof(QUEUE));??
  26. ??
  27. ????if?(NULL?==?p_new)??
  28. ????{??
  29. ????????printf("內存分配失敗！\n");??
  30. ????????exit(EXIT_FAILURE);??
  31. ????}??
  32. ??
  33. ????p_new->data?=?data;??
  34. ????p_new->pNext?=?NULL;??
  35. ????queue->rear->pNext?=?p_new;??
  36. ????queue->rear?=?p_new;??
  37. }??
  38. ??
  39. //出隊列??
  40. void?DeQueue(pQUEUE?queue,?int?*data)??
  41. {??
  42. ????if?(IsEmptyQueue(queue))??
  43. ????????exit(EXIT_FAILURE);??
  44. ????pNODE?p_delete?=?queue->front->pNext;??
  45. ????*data?=?p_delete->data;??
  46. ????queue->front->pNext?=?p_delete->pNext;??
  47. ????if?(p_delete->pNext?==?NULL)??
  48. ????????queue->rear?=?queue->front;??
  49. ????free(p_delete);??
  50. ????p_delete?=?NULL;??
  51. }??
  52. ??
  53. //判斷隊列是否為空??
  54. int?IsEmptyQueue(pQUEUE?queue)??
  55. {??
  56. ????if?(queue->front?==?queue->rear)??
  57. ????????return?1;??
  58. ????else??
  59. ????????return?0;??
  60. }??
  61. ??
  62. //獲得隊頭元素值??
  63. int?GetFrontQueue(pQUEUE?queue)??
  64. {??
  65. ????int?data;??
  66. ????if?(IsEmptyQueue(queue))??
  67. ????????exit(EXIT_FAILURE);??
  68. ????data?=?queue->front->data;??
  69. ????return?data;??
  70. }??
  71. ??
  72. //釋放內存??
  73. void?FreeMemory(pQUEUE?queue)??
  74. {??
  75. ????pNODE?p_delete?=?NULL;??
  76. ????while?(queue->front?!=?NULL)??
  77. ????{??
  78. ????????p_delete?=?queue->front;??
  79. ????????queue->front?=?p_delete->pNext;??
  80. ????????if?(p_delete->pNext?==?NULL)?//如果到達最后一個節點時，隊尾指針為NULL??
  81. ????????????queue->rear?=?NULL;??
  82. ????????free(p_delete);??
  83. ????????p_delete?=?NULL;??
  84. ????}??
  85. }??


main.cpp 測試程序——簡單的交互界面測試函數功能

[cpp]?view plain?copy
  1. #include?<stdio.h>??
  2. #include?"Queue.h"??
  3. ??
  4. int?main(void)??
  5. {??
  6. ????int?number,?i,?data,?flag;??
  7. ????QUEUE?q;??
  8. ????InitQueue(&q);??
  9. ??????
  10. ????flag?=?IsEmptyQueue(&q);??
  11. ????if?(flag)??
  12. ????????printf("初始化成功！\n");??
  13. ??
  14. ????printf("請輸入入隊列個數：");??
  15. ????scanf("%d",?&number);??
  16. ????for?(i=1;?i<number+1;?i++)??
  17. ????{??
  18. ????????printf("請輸入第%d個隊點元素值：",?i);??
  19. ????????scanf("%d",?&data);??
  20. ????????EnQueue(&q,?data);??
  21. ????}??
  22. ??
  23. ????DeQueue(&q?,&data);??
  24. ????printf("出隊列的元素值為：%d\n",?data);??
  25. ??
  26. ????data?=?GetFrontQueue(&q);??
  27. ????printf("當前棧頂元素值為：%d\n",?data);??
  28. ??
  29. ????FreeMemory(&q);??
  30. ????if?(q.front?==?NULL?&&?q.rear?==?NULL)??
  31. ????????printf("內存釋放成功！\n");??
  32. ????else??
  33. ????????printf("內存釋放失敗！\n");??
  34. ??
  35. ????return?0;??
  36. }??

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

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

相關文章

Cookie的使用

Cookie的使用

ookie簡介 1. 定義 cookie是由服務器發送給客戶端&#xff08;瀏覽器&#xff09;的小量信息。 2. 作用 cookie是鍵值對形式存儲的少量信息&#xff0c;那它有什么作用呢&#xff1f; 我們知道&#xff0c;平時上網時都是使用無狀態的HTTP協議傳輸出數據&#xff0c;這意味著客…
閱讀更多...
循環鏈表解決約瑟夫問題（簡化版）

循環鏈表解決約瑟夫問題（簡化版）

http://blog.csdn.net/jw903/article/details/38965477 約瑟夫環是一個經典的數學的應用問題&#xff1a;已知N個人&#xff08;以編號1&#xff0c;2&#xff0c;3...N分別表示&#xff09;圍坐在一張圓桌周圍。從編號為1的人開始報數&#xff0c;數到M的那個人出列&#xff1…
閱讀更多...
Linux平臺上SQLite數據庫教程（一）——終端使用篇

Linux平臺上SQLite數據庫教程（一）——終端使用篇

http://blog.csdn.net/u011192270/article/details/48031763 SQLite是一款輕型的數據庫&#xff0c;它的設計目標是嵌入式的&#xff0c;而且目前已經在很多嵌入式產品中使用了它&#xff0c;它占用資源非常的低&#xff0c;可能只需要幾百K的內存就夠了。能夠支持Windows/Lin…
閱讀更多...
多路IO轉接服務器 epoll

多路IO轉接服務器 epoll

創建一個epoll句柄&#xff0c;參數size用來告訴內核監聽的文件描述符的個數&#xff0c;跟內存大小有關。 #include <sys/epoll.h> int epoll_create(int size)　　 size&#xff1a;監聽數目 通過創建一個size大小的紅黑數來實現epoll句柄&#xff0c;返回epfd是該…
閱讀更多...
Linux平臺上SQLite數據庫教程（二）——C語言API介紹

Linux平臺上SQLite數據庫教程（二）——C語言API介紹

http://blog.csdn.net/u011192270/article/details/48086961 前言&#xff1a;本文將介紹幾個基本的SQLite3數據庫的C語言API接口&#xff0c;主要用到兩個文件&#xff1a;sqlite3.c、sqlite3.h。源碼地址&#xff1a;https://github.com/AnSwErYWJ/SQLite。 打開數據庫 1.原型…
閱讀更多...
epoll非阻塞IO

epoll非阻塞IO

設置connfd套接字為非阻塞 flag fcntl(connfd, F_GETFL); flag | O_NONBLOCK; fcntl(connfd, F_SETFL, flag); 轉載于:https://www.cnblogs.com/lr1402585172/p/10758740.html
閱讀更多...
小白創建網站的曲折之路

小白創建網站的曲折之路

小白創建網站的曲折之路 在虛擬機上創建網站 顧名思義&#xff0c;首先要有一個虛擬機。在網上百度一下后&#xff0c;我發現大家都在說使用一種叫做VMware Workstation的軟件進行虛擬機的構建 在這位好心人的幫助下我找到了Vmware Workstation的下載資源&#xff0c;并成功下…
閱讀更多...
Ubuntu 14.04數據庫服務器--mysql的安裝和配置

Ubuntu 14.04數據庫服務器--mysql的安裝和配置

https://jingyan.baidu.com/article/425e69e6bbc6c7be14fc1640.html mysql是Oracle公司的一種開放源代碼的關系型數據庫管理系統&#xff0c;被廣泛應用于各中小網站&#xff0c;是一種跨平臺的數據庫管理系統&#xff0c;現在介紹一下如何在Ubuntu 14.04上安裝和配置mysql 工具…
閱讀更多...
javavbean

javavbean

一、什么是javabeanJavaBean是一個遵循特定寫法的Java類&#xff0c;它通常具有如下特點&#xff1a;這個Java類必須具有一個無參的構造函數屬性必須私有化。私有化的屬性必須通過public類型的方法暴露給其它程序&#xff0c;并且方法的命名也必須遵守一定的命名規范。JavaBean…
閱讀更多...
Centos7下搭建LAMP環境，安裝wordpress（不會生產博客，只是一名博客搬運工）(菜鳥)

Centos7下搭建LAMP環境，安裝wordpress（不會生產博客，只是一名博客搬運工）(菜鳥)

1.搭建MySQL數據庫 安裝MariaDB yum install mariadb-server -y 啟動MySQL服務 emctl start mariadb #啟動服務 emtcl enable marriadb#設置開機服務 設置MySQL賬戶和root密碼 mysqladmin -u root password ******* 2.安裝Apache服務 安裝Apache yum install httpd -y 啟動A…
閱讀更多...
（C語言版）棧和隊列（二）——實現順序存儲棧和順序存儲隊列的相關操作

（C語言版）棧和隊列（二）——實現順序存儲棧和順序存儲隊列的相關操作

http://blog.csdn.net/fisherwan/article/details/21479649 棧和隊列都有兩種實現方式&#xff0c;一種在之前已經寫過了&#xff0c;是鏈式存儲形式&#xff0c;另一種是順序存儲形式。也就是這里所寫的用數組的形式實現&#xff0c;和鏈式存儲形式相比&#xff0c;有幾個不同…
閱讀更多...
算法學習——貪心篇

算法學習——貪心篇

貪心選擇是指應用同一規則&#xff0c;將原問題變為一個相似但是規模更小的問題&#xff0c;而后的每一步都是當前看起來最佳的選擇&#xff0c;且這種選擇只依賴于已做出的選擇&#xff0c;不依賴于未作出的選擇。 貪心算法說起來容易&#xff0c;操作起來卻經常有點玄學。&am…
閱讀更多...
使用基本MVC2模式創建新聞網站

使用基本MVC2模式創建新聞網站

轉載于:https://www.cnblogs.com/lr1402585172/p/10885084.html
閱讀更多...
棧（Stack），輕松解決數制轉換和括號匹配問題！

棧（Stack），輕松解決數制轉換和括號匹配問題！

http://data.biancheng.net/view/9.html 棧&#xff0c;線性表的一種特殊的存儲結構。與學習過的線性表的不同之處在于棧只能從表的固定一端對數據進行插入和刪除操作&#xff0c;另一端是封死的。 圖1 棧結構示意圖由于棧只有一邊開口存取數據&#xff0c;稱開口的那一端為“…
閱讀更多...
第一章 TCP/IP協議族

第一章 TCP/IP協議族

一、協議族體系結構 TCP/IP協議族分為四層協議系統&#xff0c;自底向下分別為數據鏈路層、網絡層、傳輸層、應用層。 數據鏈路層常用ARP&#xff08;地址解析協議&#xff09;和RARP&#xff08;逆地址解析協議&#xff09;。在網絡層使用IP尋址&#xff0c;而在數據鏈路層使用…
閱讀更多...
二分（三分）+快速冪

二分（三分）+快速冪

之前學習的二分&#xff0c;現在感覺突然理解許多&#xff0c;補一下總結 首先&#xff0c;二分能夠解決什么樣的問題呢&#xff0c;個人認為&#xff0c;二分能夠快速解決已經知道答案范圍&#xff08;線性&#xff09;但是不知道確切答案的問題&#xff0c;例如在一個有序序列…
閱讀更多...
pthread_cleanup_push與pthread_cleanup_pop的目的 作用

pthread_cleanup_push與pthread_cleanup_pop的目的 作用

http://blog.csdn.net/slj_win/article/details/7267483 首先你必須知道pthread_cleanup_push與pthread_cleanup_pop的目的(作用)是什么。 比如thread1: 執行 pthread_mutex_lock(&mutex); //一些會阻塞程序運行的調用&#xff0c;比如套接字的accept&#xff0c;等待客…
閱讀更多...
動態規劃淺談

動態規劃淺談

接觸動態規劃這么久了&#xff0c;簡單談一下自己對動態規劃的理解。 動態規劃名字聽起來好像比比較高大上&#xff0c;可是事實上&#xff0c;人家就是比較高大上。&#xff08;抖個機靈&#xff09; 剛開始接觸動態規劃的時候覺得好可怕&#xff0c;這么復雜的問題我怎么能想…
閱讀更多...
Linux多線程——使用信號量同步線程

Linux多線程——使用信號量同步線程

http://blog.csdn.net/ljianhui/article/details/10813469/ 信號量、同步這些名詞在進程間通信時就已經說過&#xff0c;在這里它們的意思是相同的&#xff0c;只不過是同步的對象不同而已。但是下面介紹的信號量的接口是用于線程的信號量&#xff0c;注意不要跟用于進程間通信…
閱讀更多...
linux下安裝erlang

linux下安裝erlang

1.安裝Erlang編譯依賴: yum -y install gcc glibc-devel make ncurses-devel openssl-devel xmlto perl wget 2.下載Erlang&#xff1a; wget http://www.erlang.org/download/otp_src_19.3.tar.gz 3.解壓并安裝 tar -xzvf otp_src_19.3.tar.gz cd otp_src_19.3 ./configure --…
閱讀更多...
最新文章

Copyright @ 2022~2023