線性表的鍊式實作(C++)

結點以及連結清單類的定義：

1 #define ElemType int
 2 
 3 class LNode {
 4 public:
 5     LNode(ElemType ele, LNode *pointer) :data(ele), next(pointer) {
 6 
 7     }
 8 
 9     LNode(ElemType ele) {
10         data = ele;
11         next = nullptr;
12     }
13 
14     LNode() {
15         data = 0;
16         next = nullptr;
17     }
18 
19     ElemType data;
20     LNode *next;
21 };
22 
23 class LinkList {
24 public:
25     LinkList() {
26         head = nullptr;
27     }
28 
29     // 初始化時，建立一個長度為len的連結清單
30     LinkList(int len) {
31         head = nullptr;
32         this->LListAddNodes(len);
33     }
34 
35     ~LinkList() {
36         this->LListDestory();
37     }
38 
39     LNode *LListHead() {
40         return head;
41     }
42 
43     // 設定連結清單頭結點
44     void LListSetHead(LNode *node) {
45         head = node;
46     }
47     
48     // 擷取連結清單長度
49     int LListLength();
50 
51     // 判斷連結清單是否為空
52     bool LListEmpty() {
53         return(head == nullptr) ? true : false;
54     }
55 
56     // 傳回連結清單中第pos個結點
57     bool GetNode(int pos, LNode **node);
58 
59     // 傳回指定data在連結清單中第一次出現的位置
60     bool LocateNode(ElemType ele, LNode **node);
61 
62     // 在指定位置插入後一個結點，但若pos為0是表示在連結清單頭插入一個結點
63     bool LListInsert(int pos, LNode *node);
64 
65     // 删除指定位置結點
66     bool LListDelete(int pos);
67 
68     // 删除指定位置結點并傳回被删除結點的資訊
69     bool LListDelete(int pos, LNode *node);
70 
71     // 周遊線性表
72     void LListTraverse();
73 
74     // 在連結清單尾添加cnt個結點
75     bool LListAddNodes(int cnt);
76 
77     // 銷毀連結清單，釋放所有結點資源
78     void LListDestory();
79 
80 private:
81     LNode *head;
82

具體實作：

1 int LinkList::LListLength()
  2 {
  3     int cnt = 0;
  4     LNode *node = head;
  5 
  6     while (node != nullptr) {
  7         cnt++;
  8         node = node->next;
  9     }
 10     return cnt;
 11 }
 12 
 13 bool LinkList::GetNode(int pos, LNode **node)
 14 {
 15     if (pos > this->LListLength() || pos < 1)
 16         return false;
 17 
 18     LNode *cur = head;
 19 
 20     for (int i = 2; i <= pos; i++) {
 21         cur = cur->next;
 22     }
 23 
 24     *node = cur;
 25 
 26     return true;
 27 }
 28 
 29 bool LinkList::LocateNode(ElemType ele, LNode **node)
 30 {
 31     LNode *curNode = head;
 32     while (curNode != nullptr) {
 33          34
 35         if (curNode->data == ele) {
 36             *node = curNode;
 37             return true;
 38         }
            curNode = curNode->next;
 39     }
 40 
 41     return false;
 42 }
 43 
 44 bool LinkList::LListInsert(int pos, LNode *node)
 45 {
 46     // 插入位置錯誤
 47     if (pos < 0 || pos > this->LListLength())
 48         return false;
 49     
 50     if (pos == 0) {
 51         node->next = head;
 52         head = node;
 53     }
 54     else {
 55         LNode *temp = nullptr;
 56         this->GetNode(pos, &temp);
 57         node->next = temp->next;
 58         temp->next = node;
 59     }
 60 
 61     return true;
 62 }
 63 
 64 bool LinkList::LListDelete(int pos)
 65 {
 66     if (pos <1 || pos > this->LListLength())
 67         return false;
 68 
 69     if (pos == 1) {     // 删除頭結點
 70         LNode *temp = head;
 71         head = temp->next;
 72         delete(temp);
 73     }
 74     else {
 75         LNode *temp_1 = nullptr; 
 76         LNode *temp_2 = nullptr;
 77         this->GetNode(pos - 1, &temp_1);  // 擷取被删除結點的前一個結點
 78         temp_2 = temp_1->next;
 79         temp_1->next = temp_2->next;
 80         delete(temp_2);
 81     }
 82 
 83     return true;
 84 }
 85 
 86 // 删除結點立即釋放結點所占用的空間，被傳回的僅僅是被删除結點的資訊
 87 bool LinkList::LListDelete(int pos, LNode *node)
 88 {
 89     if (pos <1 || pos > this->LListLength())
 90         return false;
 91 
 92     if (pos == 1) {     
 93         LNode *temp = head;
 94         head = temp->next;
 95         node->data = temp->data;
 96         node->next = temp->next;
 97         delete(temp);
 98     }
 99     else {
100         LNode *temp_1 = nullptr;
101         LNode *temp_2 = nullptr;
102         this->GetNode(pos - 1, &temp_1);
103         temp_2 = temp_1->next;
104         temp_1->next = temp_2->next;
105         node->data = temp_2->data;
106         node->next = temp_2->next;
107         delete(temp_2);
108     }
109 
110     return true;
111 }
112 
113 void LinkList::LListTraverse()
114 {
115     LNode *curNode = head;
116 
117     while (curNode != nullptr) {
118         std::cout << curNode->data << std::endl;
119         curNode = curNode->next;        
120     }
121 }
122 
123 bool LinkList::LListAddNodes(int cnt)
124 {
125     //std::cout << cnt << std::endl;
126 
127     if (cnt < 0)
128         return false;
129     else if (cnt == 0)
130         return true;
131 
132     LNode *curNode = head;
133 
134     if (curNode != nullptr) {
135         // 找到連結清單尾結點
136         while (curNode->next != nullptr) {
137             curNode = curNode->next;
138         }
139 
140         for (int i = 0; i < cnt; i++) {
141             int temp;
142             std::cin >> temp;
143             LNode *node = new LNode(temp);
144 
145             if (!node) {
146                 return false;
147             }
148 
149             //node->next = nullptr;
150             //node->data = i;
151 
152             curNode->next = node;
153             curNode = node;
154         }
155     }
156     else {
157         int temp;
158         std::cin >> temp;
159         LNode *node = new LNode(temp);
160         head = node;
161         curNode = node;
162 
163         for (int i = 0; i < cnt - 1; i++) {
164             std::cin >> temp;
165             node = new LNode(temp);
166 
167             if (!node) {
168                 //std::cout << "new Error!" << std::endl;
169                 return false;
170             }
171 
172             curNode->next = node;
173             curNode = node;
174         }
175     }
176 
177     return true;
178 }
179 
180 void LinkList::LListDestory()
181 {
182     //std::cout << "Destory!" << endl;
183     LNode *cur = head;
184 
185     if (!cur)
186         return;
187 
188     LNode *next = cur->next;
189 
190     while (cur) {
191         delete cur;
192         
193         if (next) {
194             cur = next;
195             next = next->next;
196         }
197         else
198             break;
199     }
200

用于測試的代碼及測試結果：

#include "link_list.h"

int main()
{
    //LNode node(5);
    //if (node.next == nullptr)
        //std::cout << "next = nullptr, data = " << node.data << std::endl;

    LinkList list(5);
    //LinkList list;

    int len = list.LListLength();
    std::cout << "InitLen = " << len << std::endl;

    if (list.LListEmpty())
        std::cout << "Empty List!" << std::endl;

    std::cout << std::endl << "First Traverse: " << std::endl;

    list.LListTraverse();

    std::cout << std::endl << "Insert two Node!" << std::endl;

    LNode *node = new LNode(0);

    if (!node)
        std::cout << "new Error!" << std::endl;

    LNode *node_2 = new LNode(6);

    if (!node_2)
        std::cout << "new Error!" << std::endl;

    list.LListInsert(0, node);
    list.LListInsert(6, node_2);

    len = list.LListLength();
    std::cout << "CurLen = " << len << std::endl;

    std::cout << std::endl << "Second Traverse: " << std::endl;
    list.LListTraverse();

    std::cout << "Get Node's Data!" << std::endl;
    LNode *node_pos_3 = nullptr;
    list.GetNode(3, &node_pos_3);

    std::cout << "node_pos_3: " << "data = " << node_pos_3->data << std::endl;
    
    LNode node_del;
    if (list.LListDelete(3, &node_del)) {
        std::cout << "Delete Node: " << "data = " << node_del.data << std::endl;
    }

    len = list.LListLength();
    std::cout << "CurLen = " << len << std::endl;

    std::cout << std::endl << "Third Traverse: " << std::endl;
    list.LListTraverse();

    std::cout << "End..." << std::endl;
    int temp;
    std::cin >> temp;

    return 0;
}

/*
輸出資訊：
1
2
3
4
5
InitLen = 5

First Traverse:
1
2
3
4
5

Insert two Node!
CurLen = 7

Second Traverse:
0
1
2
3
4
5
6
Get Node's Data!
node_pos_3: data = 2
Delete Node: data = 2
CurLen = 6

Third Traverse:
0
1
3
4
5
6
End...
*/

線性表的鍊式實作(C++)

相關内容：

結點以及連結清單類的定義：

具體實作：

用于測試的代碼及測試結果：

繼續閱讀

遇到的坑-對象之間的關系(1)啊啊啊，關于這篇文章，有很多問題，我自己又去調試了一下，發現不是那麼回事。這裡是最新的關于這個問題的分析

Java實作雙向連結清單詳細代碼

合并k個排序連結清單（Python實作）

HashMap、HashSet、ArrayList實作機制

2017年團體程式設計天梯賽-決賽小結

PAT (Advanced Level) Practise 1097 Deduplication on a Linked List (25)

圖解

求連結清單的第一個公共節點問題（好未來筆試題）

反轉連結清單，基礎棧練習，貪心

B - No Name UVALive - 6319 思維or連結清單

python連結清單逆轉(代碼附效果)

資料結構-連結清單的基本操作實作

嚴蔚敏資料結構C語言版線性表的增删改查功能（中職學習記錄篇）（純敲代碼：完全自己敲的）

LeetCode No.21 Merge Two Sorted Lists

連結清單-Java-力扣61. 旋轉連結清單1. 題目2. 思路3. 代碼

linux下自創網絡程式設計聊天室（4）改進兩點