将线性表的抽象数据类型定义在链接存储结构下用C++的类实现,由于线性表的数据元素类型不确定,所以采用模板机制。
1 头文件linklist.h
2 #pragma once
3 #include <iostream>
4 // 单链表的节点
5 template<class T>
6 struct Node
7 {
8 T data;//数据域
9 Node<T> *next;// 指针域,指向后继节点
10 };
11 // 单链表的类实现
12 template<class T>
13 class LinkList
14 {
15 public:
16 LinkList();// 无参构造函数,建立只有头节点的空链表
17 LinkList(T a[],int n);// 有参构造函数,建立有n个元素的单链表
18 ~LinkList();// 析构函数
19 int Length();// 求单链表的长度
20 T Get(int i);// 查找第i个元素
21 int Locate(T x);// 查找值为x的元素
22 void Insert(int i, T x);// 在第i个元素处插入x
23 T Delete(int i);// 删除第i个节点
24 void PrintList();// 遍历各个元素
25 private:
26 Node<T>* first;// 单链表的头节点
27 };
28
29 template<class T>
30 inline LinkList<T>::LinkList()
31 {
32 first = new Node<T>; // 生成头节点
33 first->next = NULL; // 头节点指针域为空
34 }
35
36 // 头插法建立单链表
37 template<class T>
38 LinkList<T>::LinkList(T a[], int n)
39 {
40 first = new Node<T>;
41 first->next = NULL; // 初始化一个空链表
42 for (int i = 0; i < n; i++)
43 {
44 Node<T>* S = new Node<T>;
45 S->data = a[i]; // 为每个数据元素建立一个节点
46 S->next = first->next;
47 first->next = S; // 将节点S插入头节点之后
48 }
49 }
50 // 尾插法建立单链表
51 template<class T>
52 LinkList<T>::LinkList(T a[], int n)
53 {
54 first = new Node<T>;// 建立头节点
55 first->next = NULL;
56 Node<T>* r = first;// 尾指针初始化
57 for(int i = 0; i < n; i++)
58 {
59 Node<T>* S = new Node<T>;
60 S->data = a[i]; // 为每个数据元素建立一个节点
61 r->next = S;
62 r = S; // 插入节点S,并将尾指针指向S节点
63 }
64 r->next = NULL; // 单链表建立完毕之后,将尾指针置空
65 }
66
67 template<class T>
68 LinkList<T>::~LinkList()
69 {
70 while (first != NULL)
71 {
72 Node<T>* p = first; // 暂存将被释放节点
73 first = first->next; // 指向下一个节点
74 delete p;
75 }
76 }
77
78 template<class T>
79 int LinkList<T>::Length()
80 {
81 int count = 0; // 计数
82 Node<T>* p = first->next; // 将工作指针指向第一个节点
83 while (p != NULL)
84 {
85 count++;
86 p = p->next;
87 }
88 return count;
89 }
90
91 template<class T>
92 T LinkList<T>::Get(int i)
93 {
94 int count = 0; // 计数
95 Node<T>* p = first->next; // 将工作指针指向第一个节点
96 while (p != NULL)
97 {
98 count++;
99 if (count == i)
100 return p->data;
101 p = p->next;
102 }
103 return -1; // 越界
104 }
105
106 template<class T>
107 int LinkList<T>::Locate(T x)
108 {
109 int count = 0; // 计数
110 Node<T>* p = first->next; // 将工作指针指向第一个节点
111 while (p != NULL)
112 {
113 count++;
114 if (p->data == x)
115 return count;
116 p = p->next;
117 }
118 return 0; // 查找失败
119 }
120
121 template<class T>
122 void LinkList<T>::Insert(int i, T x)
123 {
124 int count = 0; // 计数
125 Node<T>* p = first; // 将工作指针指向头节点
126 while (p != NULL)
127 {
128 if (count == i - 1) // 找第i-1个节点
129 {
130 Node<T>* S = new Node<T>;
131 S->data = x;
132 S->next = p->next;
133 p->next = S;
134 }
135 p = p->next;
136 count++;
137 }
138 if (p == NULL)
139 throw "位置越界";
140 }
141
142 template<class T>
143 T LinkList<T>::Delete(int i)
144 {
145 int count = 0; // 计数
146 Node<T>* p = first; // 将工作指针指向头节点
147 while (p != NULL)
148 {
149 if (count == i - 1)
150 {
151 Node<T>* q = p->next;// 暂存被删节点
152 T x = q->data;
153 p->next = q->next;
154 delete q;
155 return x;
156 }
157 p = p->next;
158 count++;
159 }
160 return -1;
161 }
162
163 template<class T>
164 void LinkList<T>::PrintList()
165 {
166 Node<T>* p = first->next; // 将工作指针指向第一个节点
167 while (p != NULL)
168 {
169 cout << p->data << " ";
170 p = p->next;
171 }
172 }
主函数
#include"linklist.h"
using namespace std;
int main()
{
int arry[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
LinkList<int>* linklist = new LinkList<int>(arry, 10);
cout << linklist->Length() << endl;
cout << linklist->Get(5) << endl;
cout << linklist->Locate(6) << endl;
linklist->Insert(3, 11);
linklist->Delete(10);
linklist->PrintList();
system("pause");
return 0;
}
运行结果如下:
原文链接: https://www.cnblogs.com/smile233/p/8063788.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/265994
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!