用C++实现了一个链表类，附上可执行代码

爱学习520

上午发了一个Vector类，昨天做了一天，即可动态扩容的数组，今天做了一个链表，刚刚写完链表类，附上链表类的代码和main的测试案例，有什么可以优化的地方欢迎提出来，共同进步。明天接着写，争取把二叉搜索树写完

链表LinkList类

1. #include<iostream>
   
2. using namespace std;
   
3. 
   
4. #define    Index_Error     -1    //索引错误
   
5. 
   
6. template<class T_ELE>
   
7. class LinkList
   
8. {
   
9. //私有结构体、函数
   
10. private:
    
11.         typedef struct Node
    
12.         {
    
13.                 T_ELE data;
    
14.                 struct Node* pNext;
    
15.         }NODE,*PNODE;
    
16. 
    
17.         //以下的索引都是从1开始的，而非0
    
18.         PNODE GetIndexPreviousNode(int index)
    
19.         {
    
20.                 PNODE p = pHead->pNext;
    
21.                 //因为下面的for循环是考虑index从2开始的，所以这里考虑只有一个结点的情况
    
22.                 if (index == 1)
    
23.                         return pHead;
    
24.                 for (int i = 0; i < index -2; i++)
    
25.                         p = p->pNext;
    
26.                 return p;
    
27.         }
    
28.         PNODE GetIndexCurrentNode(int index)
    
29.         {
    
30.                 PNODE p = pHead->pNext;
    
31.                 for (int i = 0; i < index - 1; i++)
    
32.                         p = p->pNext;
    
33.                 return p;
    
34.         }       
    
35.         PNODE GetIndexNectNode(int index)
    
36.         {
    
37.                 PNODE p = pHead->pNext;
    
38.                 for (int i = 0; i < index ; i++)
    
39.                         p = p->pNext;
    
40.                 return p;
    
41.         }
    
42. 
    
43. //私有成员
    
44. private:
    
45.         PNODE pHead;
    
46.         PNODE pTail;
    
47.         int Length;
    
48. 
    
49. //构造、析构函数
    
50. public:
    
51.         LinkList() :pHead (nullptr),pTail(nullptr),Length(0)
    
52.         {
    
53.                 //申请一块空的节点，仅作为后续使用方便
    
54.                 pHead =pTail= new NODE;
    
55.                 pHead->pNext = nullptr;
    
56.                 pTail->pNext = nullptr;
    
57.         }
    
58. 
    
59.         ~LinkList()
    
60.         {
    
61.                 Clear();
    
62.         }
    
63. 
    
64. //链表类的函数功能
    
65. public:
    
66.         //向当前链表插入元素
    
67.         void Insert(T_ELE Element)
    
68.         {
    
69.                 //申请新空间，存放元素
    
70.                 PNODE cur = new NODE;
    
71.                 cur->data = Element;
    
72.                 //将新节点连接到之前的结点上
    
73.                 pTail->pNext = cur;
    
74.                 cur->pNext = nullptr;
    
75.                 //修改类成员其他对应的参数
    
76.                 pTail = cur;
    
77.                 Length++;       
    
78.         }
    
79. 
    
80.         //向指定索引的位置插入元素
    
81.         int Insert(int index,T_ELE Element)
    
82.         {
    
83.                 //判断是否在正确区间
    
84.                 if (index<1 || index>Length + 1)
    
85.                 {
    
86.                         cout << index << "不在该链表区域，插入失败！！！" << endl;
    
87.                         return Index_Error;
    
88.                 }
    
89.                        
    
90.                 //新申请一块空间
    
91.                 PNODE pNew=new NODE;
    
92.                 pNew->data = Element;
    
93.                 //插入操作
    
94.                 PNODE temp = GetIndexPreviousNode(index)->pNext;
    
95.                 GetIndexPreviousNode(index)->pNext=pNew;
    
96.                 pNew->pNext = temp;
    
97.                 //其他对应的成员值的修改
    
98.                 Length++;
    
99.         }
    
100.         //向指定索引位置删除元素
     
101.         int Delete(int index)
     
102.         {
     
103.                 //判断删除区间是否有误
     
104.                 if (index<1 || index>Length)
     
105.                 {
     
106.                         cout << index << "不在链表区域，删除失败！！！" << endl;
     
107.                         return -1;
     
108.                 }
     
109.                 //删除操作
     
110.                 PNODE temp = GetIndexPreviousNode(index)->pNext;
     
111.                 GetIndexPreviousNode(index)->pNext = GetIndexPreviousNode(index)->pNext->pNext;
     
112.                 delete temp;
     
113.                 //修改类成员对应的值
     
114.                 Length--;
     
115. 
     
116.                        
     
117.         }
     
118.         //判断链表是否为空
     
119.         bool IsEmpty()
     
120.         {
     
121.                 if (pHead->pNect == nullptr)
     
122.                 {
     
123.                         cout << "链表为空" << endl;
     
124.                         return false;
     
125.                 }
     
126.                 return true;
     
127.         }
     
128.         //清除链表
     
129.         void Clear()
     
130.         {
     
131.                 PNODE p= pHead->pNext;
     
132.                 for (int i = 0; i < Length; i++)
     
133.                 {
     
134.                         PNODE temp = p->pNext;
     
135.                         delete p;
     
136.                         p = temp;
     
137.                 }
     
138.                 //修改对应的成员变量值
     
139.                 Length = 0;
     
140.         }
     
141.         //遍历链表
     
142. 
     
143.         void Traverse()
     
144.         {
     
145.                 PNODE p=pHead->pNext;
     
146.                 for(int i=0;i<Length;i++,p=p->pNext)
     
147.                 cout << p->data << endl;
     
148.         }
     
149. 
     
150. };

复制代码

main测试LinkList类，测试用例

1. #include "LinkList.cpp"
   
2. 
   
3. //测试LinkList
   
4. int main()
   
5. {
   
6.     LinkList<int> p;
   
7.     p.Insert(1);
   
8.     p.Insert(2);
   
9.     p.Insert(3);
   
10.     p.Insert(4);
    
11.     p.Insert(5);
    
12.     p.Insert(6);
    
13.     p.Insert(7);
    
14. 
    
15.     //插入测试,以下每行分开测试，不然链表长度增加后失去测试效果
    
16.     cout << "插入测试开始......" << endl;
    
17.     //p.Insert(0, 520);
    
18.     //p.Insert(1, 520);
    
19.     //p.Insert(4, 520);
    
20.     //p.Insert(8, 520);
    
21.     //p.Insert(9, 520);
    
22. 
    
23.     //测试删除
    
24.     //p.Delete(0);
    
25.     //p.Delete(1);
    
26.     //p.Delete(4);
    
27.     //p.Delete(7);
    
28.     //p.Delete(8);
    
29.         
    
30.     p.Traverse();
    
31.    
    
32. }
    

复制代码