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

http://blog.csdn.net/lfeng_coding/article/details/47300563

題目描述：在已知單鏈表頭節點的情況下，設計算法逆置單鏈表并輸出

方法一：采用首先將頭節點指向空，讓其變為尾節點，然后利用中間節點 p、q 將其后的節點一個接一個改為指向前面的節點



/****************************

*作者：劉峰

* 時間：2015\8\5

* 環境：VS2013

* 功能：實現創建一個節點可控的單鏈，并逆置輸出

****************************/


[cpp]?view plain?copy
  1. #include?"stdafx.h"??
  2. ??
  3. #include?<iostream>??
  4. using?namespace?std;??
  5. ??
  6. struct?List??
  7. {??
  8. ????int?num;??
  9. ????List?*next;??
  10. };??
  11. ??
  12. List?*createList(int?n)???????//創建含有n個節點的單鏈表??
  13. {??
  14. ????List?*head,?*p,?*q;??
  15. ????q=head?=?NULL;???//初始化表頭和中間指針??
  16. ????int?i;??
  17. ????for?(i?=?n;?i?>?0;?--i)??
  18. ????{??
  19. ????????p?=?new?List;?????//申請空間，創建第一個節點??
  20. ????????cin?>>?p->num;??????//往節點中存入數據信息??
  21. ????????if?(head?==?NULL)??
  22. ????????{??
  23. ????????????head?=?p;??
  24. ????????}??
  25. ????????else??
  26. ????????{??
  27. ????????????q->next?=?p;??
  28. ????????}??
  29. ????????q?=?p;??
  30. ????}??
  31. ????q->next?=?NULL;??
  32. ????return?head;??
  33. }??
  34. ??
  35. List?*ReverseList(List?*head)??????????//逆置單鏈表??
  36. {??
  37. ????List?*p,?*r;???????//定義兩個中間節點，用于順移逆置鏈表節點??
  38. ????if?(head->next?==?NULL)??
  39. ????????return?head;??
  40. ????p?=?head;??????????//獲取頭節點地址??
  41. ????r?=?p->next;???????//獲取鏈表第二個節點地址??
  42. ????p->next?=?NULL;????//頭節點變為尾節點，原鏈表表頭指向空??
  43. ????while?(r)??
  44. ????{??
  45. ????????p?=?r;??
  46. ????????r?=?r->next;??
  47. ????????p?->next?=?head;???//使第二個節點指向原先的頭節點??
  48. ????????head?=?p;??????????//使第二個節點變為頭節點，用于循環逆置??
  49. ????}??
  50. ????return?head;??
  51. }??
  52. ??
  53. void?print(List?*head)????????//輸出逆置后的單鏈表??
  54. {??
  55. ????List?*p;??
  56. ????p?=?head;??
  57. ????while?(p)??
  58. ????{??
  59. ????????cout<<p->num;??
  60. ????????p?=?p->next;??
  61. ????????cout?<<?"?";??
  62. ????}??
  63. ????cout?<<?endl;??
  64. }??
  65. int?_tmain(int?argc,?_TCHAR*?argv[])??
  66. {??
  67. ????List?*p,?*q;??
  68. ????cout?<<?"請輸入單鏈表的節點個數：";??
  69. ????int?n;??
  70. ????cin?>>?n;??
  71. ????cout?<<?endl;??
  72. ????cout?<<?"創建一個節點為"?<<?n?<<?"的單鏈表"?<<?endl;??
  73. ????p?=?createList(n);??
  74. ????cout?<<?endl;??
  75. ????cout?<<?"這步為程序逆置單鏈表"?<<?endl;??
  76. ????q?=?ReverseList(p);??
  77. ????cout?<<?endl;??
  78. ????cout?<<?"打印逆置后的單鏈表"?<<?endl;??
  79. ????print(q);??
  80. ????cout?<<?endl;??
  81. ????return?0;??
  82. }??



方法二：用p,q指向單鏈表中相鄰的兩節點，將r指向q的下一個結點，然后同步后移。當q=NULL時，表示指向原單鏈表的尾結點，將p賦值為頭節點 head 即可。


逆置函數代碼如下（其他部分不變）：

List *ReverseList(List *head)
{
List *p, *q, *r;
p = head;
if (p->next == NULL)
return head;
q = p->next;
while (q != NULL) ? ? //q為空，說明p為最后一個節點，所以結束while后將q賦值給head,作為逆置后的表頭
{
r = q->next;
q->next = p;
p = q;
q = r;
}
head->next = NULL; ? //將原head變為逆置后鏈表的表尾
head = p; ? ? ? ? ? ?//逆置后新的表頭
return head;
}



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

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

相關文章

兩個棧實現一個隊列

兩個棧實現一個隊列

利用兩個棧實現一個隊列思路是這樣的. 首先這個隊列包含兩個棧, 然后一個棧用來入隊列, 一個棧用來出隊列 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> #…
閱讀更多...
BZOJ1123-BLO——強連通分量求割點+計數

BZOJ1123-BLO——強連通分量求割點+計數

【題目描述】 Byteotia城市有n個 towns m條雙向roads. 每條 road 連接 兩個不同的 towns ,沒有重復的road. 所有towns連通。Input 輸入n<100000 m<500000及m條邊Output 輸出n個數&#xff0c;代表如果把第i個點去掉&#xff0c;將有多少對點不能互通。Sample Input 5…
閱讀更多...
關于memcpy和memmove兩函數的區別

關于memcpy和memmove兩函數的區別

http://blog.csdn.net/caowei840701/article/details/8491836 [cpp] view plaincopy <p> 關于memcpy和memmove兩個c標準庫函數&#xff0c;其功能都是將一塊內存區域中的指定大小內容復制到目標內存中&#xff0c;在翻閱c標準庫實現的源代碼我們發現他們是有區別的。&…
閱讀更多...
判斷字符串出棧合法性

判斷字符串出棧合法性

先來看說一下思路 接下來就是寫代碼了 int StackOrder(SeqStack* stack, char* input, char* output, int size_input, int size_output) {if(stack NULL || input NULL || output NULL){return 0;}int i_input 0;int j_output 0;SeqStackType value;for(; j_output <…
閱讀更多...
CodeForces - 1200C——小模擬

CodeForces - 1200C——小模擬

【題目描述】 Amugae is in a very large round corridor. The corridor consists of two areas. The inner area is equally divided by n sectors, and the outer area is equally divided by m sectors. A wall exists between each pair of sectors of same area (inner o…
閱讀更多...
1 單例模式

1 單例模式

達內 閔大神 //餓漢單例模式 #include <iostream> using namespace std;class Singleton { public:static Singleton& getInstance(){return s_instance;} private:Singleton(){}Singleton(const Singleton& that){}static Singleton s_instance;//靜態成員變量 …
閱讀更多...
共享棧

共享棧

1.定義 所謂共享棧就是利用一個數組實現兩個棧. 先來看一下共享棧的數據結構 typedef struct SharedStack {int top1;int top2;SeqStackType* data; }SharedStack; 2. 初始化 void SharedStackInit(SharedStack* stack) {if(stack NULL){return;//非法輸入}stack -> top…
閱讀更多...
BZOJ1018 | SHOI2008-堵塞的交通traffic——線段樹維護區間連通性+細節

BZOJ1018 | SHOI2008-堵塞的交通traffic——線段樹維護區間連通性+細節

【題目描述】 BZOJ1018 | SHOI2008-堵塞的交通traffic 有一天&#xff0c;由于某種穿越現象作用&#xff0c;你來到了傳說中的小人國。小人國的布局非常奇特&#xff0c;整個國家的交通系統可 以被看成是一個2行C列的矩形網格&#xff0c;網格上的每個點代表一個城市&#xff0…
閱讀更多...
C++ 函數隱藏

C++ 函數隱藏

C該函數隱藏 只有基類成員函數的定義已聲明virtualkeyword&#xff0c;當在派生類中的時間&#xff0c;以支付功能實現&#xff0c;virtualkeyword可以從時間被添加以增加。它不影響多狀態。 easy混淆視聽&#xff0c;掩蓋&#xff1a; &#xff0c;規則例如以下&#xff1a; …
閱讀更多...
迷宮求解(遞歸)

迷宮求解(遞歸)

首先來看一下迷宮簡易圖 ???????????????????????????? ????我們用 0 來表示該位置是墻, 用 1 來表示該位置是路. 所以, 我們在處理迷宮問題的時候可以將其看成一個二維數組即可, 而對應的每一條路我們可以用坐標的形式將其表示, 所以還需要…
閱讀更多...
CodeForces - 786C——二分+模擬？

CodeForces - 786C——二分+模擬？

【題目描述】 Rick and Morty want to find MR. PBH and they cant do it alone. So they need of Mr. Meeseeks. They Have generated n Mr. Meeseeks, standing in a line numbered from 1 to n. Each of them has his own color. i-th Mr. Meeseeks color is ai.Rick and M…
閱讀更多...
最新文章

Copyright @ 2022~2023