C++實現單鏈表的12種基本操作

来源:https://www.cnblogs.com/KGvito/archive/2017/12/25/8111047.html
-Advertisement-
Play Games

單鏈表的12種基本操作 ...


C++單鏈表的操作
2017-12-25


  1 // 單鏈表.cpp: 定義控制台應用程式的入口點。
  2 //Author:kgvito 
  3 //Date: 2017.12.25
  4 
  5 
  6 #include "stdafx.h"
  7 #include<iostream>
  8 using namespace std;
  9 
 10 typedef int DataType;
 11 #define Node ElemType
 12 #define ERROR NULL
 13 
 14 //構建一個節點類
 15 class Node                          
 16 {
 17 public:
 18     int data;     //數據域
 19     Node * next;  //指針域
 20 };
 21 
 22 //構建一個單鏈表類
 23 class LinkList                      
 24 {
 25 public:
 26     LinkList();                      //構建一個單鏈表;
 27     ~LinkList();                  //銷毀一個單鏈表;
 28     void CreateLinkList(int n);   //創建一個單鏈表
 29     void TravalLinkList();        //遍歷線性表
 30     int GetLength();              //獲取線性表長度
 31     bool IsEmpty();               //判斷單鏈表是否為空
 32     ElemType * Find(DataType data); //查找節點
 33     void InsertElemAtEnd(DataType data);            //在尾部插入指定的元素
 34     void InsertElemAtIndex(DataType data,int n);    //在指定位置插入指定元素
 35     void InsertElemAtHead(DataType data);           //在頭部插入指定元素
 36     void DeleteElemAtEnd();       //在尾部刪除元素
 37     void DeleteAll();             //刪除所有數據
 38     void DeleteElemAtPoint(DataType data);     //刪除指定的數據
 39     void DeleteElemAtHead();      //在頭部刪除節點
 40 private:
 41     ElemType * head;              //頭結點
 42 };
 43 
 44 //初始化單鏈表
 45 LinkList::LinkList()                  
 46 {
 47     head = new ElemType;            
 48     head->data = 0;               //將頭結點的數據域定義為0
 49     head->next = NULL;            //頭結點的下一個定義為NULL
 50 }     
 51 
 52 //銷毀單鏈表
 53 LinkList::~LinkList()
 54 {
 55     delete head;                 //刪除頭結點
 56 } 
 57 
 58 //創建一個單鏈表
 59 void LinkList::CreateLinkList(int n)
 60 {
 61     ElemType *pnew, *ptemp;
 62     ptemp = head;
 63     if (n < 0) {       //當輸入的值有誤時，處理異常
 64         cout << "輸入的節點個數有誤" << endl;
 65         exit(EXIT_FAILURE);
 66     }
 67     for (int i = 0; i < n;i++) {        //將值一個一個插入單鏈表中
 68         pnew = new ElemType;
 69         cout << "請輸入第" << i + 1 << "個值: " ;
 70         cin >> pnew->data;
 71         pnew->next = NULL;          //新節點的下一個地址為NULL
 72         ptemp->next = pnew;         //當前結點的下一個地址設為新節點
 73         ptemp = pnew;               //將當前結點設為新節點
 74     }
 75 }
 76 
 77 //遍歷單鏈表
 78 void LinkList::TravalLinkList()
 79 {
 80     if (head == NULL || head->next ==NULL) {
 81         cout << "鏈表為空表" << endl;
 82     }
 83     ElemType *p = head;                 //另指針指向頭結點
 84     while (p->next != NULL)        //當指針的下一個地址不為空時，迴圈輸出p的數據域
 85     {
 86         p = p->next;               //p指向p的下一個地址
 87         cout << p->data << " ";
 88     }
 89 }
 90 
 91 //獲取單鏈表的長度
 92 int LinkList::GetLength()
 93 {
 94     int count = 0;                  //定義count計數
 95     ElemType *p = head->next;           //定義p指向頭結點
 96     while (p != NULL)                //當指針的下一個地址不為空時，count+1
 97     {
 98         count++;                  
 99         p = p->next;                //p指向p的下一個地址
100     }
101     return count;                   //返回count的數據
102 }
103 
104 //判斷單鏈表是否為空
105 bool LinkList::IsEmpty()
106 {
107     if (head->next == NULL) {                 
108         return true;
109     }
110     return false;
111 }
112 
113 //查找節點
114 ElemType * LinkList::Find(DataType data)
115 {
116     ElemType * p = head;
117     if (p == NULL) {                           //當為空表時，報異常
118         cout << "此鏈表為空鏈表" << endl;
119         return ERROR;
120     }
121     else
122     {
123         while (p->next != NULL)               //迴圈每一個節點
124         {
125             if (p->data == data) {
126                 return p;                     //返回指針域
127             }
128             p = p->next;
129         }
130         return NULL;                           //未查詢到結果
131     }
132 }
133 
134 //在尾部插入指定的元素
135 void LinkList::InsertElemAtEnd(DataType data)
136 {
137     ElemType * newNode = new ElemType;    //定義一個Node結點指針newNode
138     newNode->next = NULL;         //定義newNode的數據域和指針域
139     newNode->data = data;
140     ElemType * p = head;              //定義指針p指向頭結點
141     if (head == NULL) {           //當頭結點為空時，設置newNode為頭結點
142         head = newNode;
143     }
144     else                          //迴圈知道最後一個節點，將newNode放置在最後
145     {
146         while (p->next != NULL)
147         {
148             p = p->next;
149         }
150         p->next = newNode;
151     }
152 }
153 
154 //在指定位置插入指定元素
155 void LinkList::InsertElemAtIndex(DataType data,int n)
156 {
157     if (n<1 || n>GetLength())                   //輸入有誤報異常
158         cout << "輸入的值錯誤" << endl;
159     else
160     {
161         ElemType * ptemp = new ElemType;        //創建一個新的節點
162         ptemp->data = data;                     //定義數據域
163         ElemType * p = head;                    //創建一個指針指向頭結點
164         int i = 1;
165         while (n > i)                           //遍歷到指定的位置
166         {
167             p = p->next;
168             i++;
169         }
170         ptemp->next = p->next;                 //將新節點插入到指定位置
171         p->next = ptemp;
172     }
173 }
174 
175 //在頭部插入指定元素
176 void LinkList::InsertElemAtHead(DataType data)
177 {
178     ElemType * newNode = new ElemType;    //定義一個Node結點指針newNode
179     newNode->data = data;
180     ElemType * p = head;              //定義指針p指向頭結點
181     if (head == NULL) {           //當頭結點為空時，設置newNode為頭結點
182         head = newNode;
183     }
184     newNode->next = p->next;          //將新節點插入到指定位置
185     p->next = newNode;
186 }
187 
188 //在尾部刪除元素
189 void LinkList::DeleteElemAtEnd()
190 {
191     ElemType * p = head;          //創建一個指針指向頭結點
192     ElemType * ptemp = NULL;      //創建一個占位節點
193     if (p->next == NULL) {        //判斷鏈表是否為空
194         cout << "單鏈表空" << endl;
195     }
196     else
197     {
198         while (p->next != NULL)   //迴圈到尾部的前一個
199         {
200             ptemp = p;            //將ptemp指向尾部的前一個節點
201             p = p->next;          //p指向最後一個節點
202         }
203         delete p;                //刪除尾部節點
204         p = NULL;
205         ptemp->next = NULL;
206     }
207 }
208 
209 //刪除所有數據
210 void LinkList::DeleteAll()
211 {
212     ElemType * p = head->next;
213     ElemType * ptemp = new ElemType;
214     while (p != NULL)                    //在頭結點的下一個節點逐個刪除節點
215     {
216         ptemp = p;
217         p = p->next;
218         head->next = p;
219         ptemp->next = NULL;
220         delete ptemp;
221     }
222     head->next = NULL;                 //頭結點的下一個節點指向NULL
223 }
224 
225 //刪除指定的數據
226 void LinkList::DeleteElemAtPoint(DataType data)
227 {
228     ElemType * ptemp = Find(data);    //查找到指定數據的節點位置
229     if (ptemp == head->next) {        //判斷是不是頭結點的下一個節點，如果是就從頭部刪了它
230         DeleteElemAtHead();
231     }
232     else
233     {
234         ElemType * p = head;          //p指向頭結點
235         while (p->next != ptemp)      //p迴圈到指定位置的前一個節點
236         {
237             p = p->next;
238         }
239         p->next = ptemp->next;         //刪除指定位置的節點
240         delete ptemp;
241         ptemp = NULL;               
242     }
243 
244 }
245 
246 //在頭部刪除節點
247 void LinkList::DeleteElemAtHead()
248 {
249     ElemType * p = head;
250     if (p == NULL || p->next == NULL) {   //判斷是否為空表，報異常
251         cout << "該鏈表為空表" << endl;
252     }
253     else
254     {
255         ElemType * ptemp = NULL;      //創建一個占位節點
256         p = p->next;
257         ptemp = p->next;              //將頭結點的下下個節點指向占位節點
258         delete p;                     //刪除頭結點的下一個節點
259         p = NULL;
260         head->next = ptemp;           //頭結點的指針更換
261     }
262 }
263 
264 //測試函數
265 int main()
266 {
267     LinkList l;
268     int i;
269     cout << "1.創建單鏈表   2.遍歷單鏈表   3.獲取單鏈表的長度   4.判斷單鏈表是否為空   5.獲取節點\n";
270     cout << "6.在尾部插入指定元素   7.在指定位置插入指定元素   8.在頭部插入指定元素\n";
271     cout<<"9.在尾部刪除元素   10.刪除所有元素   11.刪除指定元素   12.在頭部刪除元素   0.退出" << endl;
272     do
273     {
274         cout << "請輸入要執行的操作: ";
275         cin >> i;
276         switch (i)
277         {
278         case 1:
279             int n;
280             cout << "請輸入單鏈表的長度: ";
281             cin >> n;
282             l.CreateLinkList(n);
283             break;
284         case 2:
285             l.TravalLinkList();
286             break;
287         case 3:
288             cout << "該單鏈表的長度為" << l.GetLength() << endl;
289             break;
290         case 4:
291             if (l.IsEmpty() == 1)
292                 cout << "該單鏈表是空表" << endl;
293             else
294             {
295                 cout << "該單鏈表不是空表" << endl;
296             }
297             break;
298         case 5:
299             DataType data;
300             cout << "請輸入要獲取節點的值: ";
301             cin >> data;
302             cout << "該節點的值為" << l.Find(data)->data << endl;
303             break;
304         case 6:
305             DataType endData;
306             cout << "請輸入要在尾部插入的值: ";
307             cin >> endData;
308             l.InsertElemAtEnd(endData);
309             break;
310         case 7:
311             DataType pointData;
312             int index;
313             cout << "請輸入要插入的數據: ";
314             cin >> pointData;
315             cout << "請輸入要插入數據的位置: ";
316             cin >> index;
317             l.InsertElemAtIndex(pointData, index);
318             break;
319         case 8:
320             DataType headData;
321             cout << "請輸入要在頭部插入的值: ";
322             cin >> headData;
323             l.InsertElemAtHead(headData);
324             break;
325         case 9:
326             l.DeleteElemAtEnd();
327             break;
328         case 10:
329             l.DeleteAll();
330             break;
331         case 11:
332             DataType pointDeleteData;
333             cout << "請輸入要刪除的數據: ";
334             cin >> pointDeleteData;
335             l.DeleteElemAtPoint(pointDeleteData);
336             break;
337         case 12:
338             l.DeleteElemAtHead();
339             break;
340         default:
341             break;
342         }
343     }while (i != 0);
344 
345     system("pause");
346     return 0;
347 }

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • Python之web模板
    Python的web模板，其實就是在HTML文檔中使用控制語句和表達語句替換HTML文檔中的變數來控制HTML的顯示格式，Python的web模板可以更加靈活和方便的控制HTML的顯示，而且大大地減少了編程人員的工作量。 模板語法： 1、控制語句{% ... %}：控制語句需要用{% end %}來 ...
  • java學習筆記之面向對象多態
    面向對象三大特性之多態 一.多態的概念 多態是繼封裝，繼承之後，面向對象的三大特性。 現實事物經常會體現出多種形態，如學生，學生是人的一種，則一個具體的張三同學既是學生也是人，即出現兩種形態。 java作為面向對象的語言，同樣可以描述一個事物的多種形態，java中多態的代碼體現在一個子類對象（實現類 ...
  • 加密文件之Java改進版
    對應Python版：加密文件之Python版Java版比Python版要快得多，兩個版本不在一個量級上。在加密解密1G大文件時，Java版花費的時間是秒級，而Python版花費的時間是10分鐘級。 ...
  • Thymeleaf的學習
    1.引入依賴 maven中直接引入 可以查看依賴關係,發現spring-boot-starter-thymeleaf下麵已經包括了spring-boot-starter-web,所以可以把spring-boot-starter-web的依賴去掉. 2.配置視圖解析器 spring-boot很多配置都 ...
  • Akka Cluster簡介與基本環境搭建
      akka集群是高容錯、去中心化、不存在單點故障以及不存在單點瓶頸的集群。它使用gossip協議通信以及具備故障自動檢測功能。 Gossip收斂   集群中每一個節點被其他節點監督(預設的最大數量為5)。集群中的節點互相監督著，某節點所監督的狀態也正在被其他 ...
  • Akka Serialization
    Akka本身使用了 來序列化內部消息(比如gossip message)。Akka系統還可以配置自定義序列化機制。 配置conf 預設的，在local actor之間(the same JVM)的消息是不會序列化的。可以通過 配置，來序列化所有消息(local和remote)。序列化所有的消息不回給 ...
  • 鎖的實現原理
    本文將從happens-before關係出發，結合ReentranLock源碼，如何用記憶體屏障、CAS操作、LOCK指令實現鎖的功能。 ...
  • （python走過的坑）OpenCV中錯誤opencv-3.3.1\modules\highgui\src\window.cpp:339: error: (-215) size.width>0 && size.height>0 in function cv::imshow
    第一次在python中使用OpenCV（cv2），運行時報錯opencv-3.3.1\modules\highgui\src\window.cpp:339: error: (-215) size.width>0 && size.height>0 in function cv::imshow 源碼如下 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類