数据结构【一】:顺序表和单链表(C++)

顺序表


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
#include<iostream>
using namespace std;
int defaultSize=100;
template <class T>
class List
{
public:
List();
List(int sz ); //构造函数
List(List<T>& L); //复制构造函数
~List()
{
delete[ ] data; //析构函数
}
int getSize() const
{
return size; //求表最大容量
}
int getLength() const
{
return last+1; //计算表长度
}
int Search(T& x) const; //搜索x在表中位置
int Locate(int i) const; //定位第 i 个表项
bool getData(int i, T&x) const; //取下标为i的数据
void setData(int i,T& x); //用x修改下标为i的的值
bool Insert(int i, T& x); //在第i个表项后插入x
bool Remove(int i, T& x); //删除第i个表项 通过x返回表项
bool IsEmpty(); //判断表空
bool IsFull(); //判断表满
void input(); //按照数值输n个数据入表
void output(); //输出表的全部数据
void reSize(int newSize); //空间大小重设
List<T>&operator=(List<T>& L);
protected:
T *data;
int size;
int last;
};
template<class T>
List<T>::List()
{
size=defaultSize;
last=-1;
data=new T[size];
}
template<class T>
List<T>::List(int sz)
{
if(sz>0) //SZ>0判断
{
size=sz;
last=-1;
data=new T[sz];
if(data==NULL)
{
//储存分配错误判断
cerr<<"储存分配错误"<<endl;
exit(1);
}
}
}
template <class T>
List<T>::List(List<T>& L)
{
T value;
size=L.getSize();
last=L.getLength;
data=new T[size];
if(data==NULL)
{
//储存分配错误判断
cerr<<"储存分配错误"<<endl;
exit(1);
}
for(int i=0; i<=last;i++)
{
L.getData(i,value);
data[i]=value;
}
}
template<class T>
int List<T>::Search(T& x) const
{
for(int i=0;i<=last;i++)
if(data[i]==x)
return i+1;
return 0;
}
template<class T>
int List<T>::Locate(int i) const
{
if(i>1&&i<=last+1)
return i;
else
return 0;
}
template<class T>
bool List<T>::getData(int i, T&x) const
{
if(i>=0&&i<=last)
{
x=data[i];
return true;
}
else
return false;
}
template<class T>
void List<T>::setData(int i,T& x)
{
if(i>=0&&i<=last)
{
data[i]=x;
}
}
template<class T>
bool List<T>::IsFull()
{
if(last==size-1)
return true;
else
return false;
}
template<class T>
bool List<T>::IsEmpty()
{
if(last==-1)
return true;
else
return false;
}
template<class T>
bool List<T>::Insert(int i, T& x)
{
if(last==size-1) //表满,不能插入
return false;
if(i<0||i>last+1) //i的值不规范,插入不再原表内,不能插入
return false;
for(int j=last;i>=i;j--) //后往前移位
{
data[j+1]=data[j];
}
last++; //记得个数+1
data[i]=x;
return true;
}
template<class T>
bool List<T>::Remove(int i, T& x)
{
if(last==-1) //表空,不能删除
return false;
if(i<0||i>last+1) //i的值不规范,插入不再原表内,不能插入
return false;
for(int j=i;i<=last;j++)
data[j-1]=data[j];
last--;
return true;
}
template<class T>
void List<T>::input()
{
int num;
cout<<"请输入需要输入的数据的个数:";
while(1)
{
cin>>num;
if(num>0&&num<=size)
break;
cout<<"请输入数值在0到"<<size<<"的数值";
}
for(int i=0;i<num;i++)
cin>>data[i];
last=num-1;
}
template<class T>
void List<T>::output()
{
for(int i=0;i<=last;i++)
cout<<data[i]<<" ";
cout<<endl;
}
template <class T>
void List<T>::reSize(int newSize)
{ if(newSize <= 0 )
{ cerr<<"无效的空间大小!"<<endl; return; }
if( newSize!=size)
{ T * newarray=new T[newSize];
if (newarray == NULL)
{ cerr<<"存储分配错误!"<<endl; exit(1); }
int n=last+1;
T* srcptr=data; T* destptr=newarray;
while(n--) //将原存储空间的数据复制到新扩充的空间
{ *destptr=*srcptr; destptr++; srcptr++; }
delete []data;
data=newarray; size=newSize;
}
}
template <class T>
List<T>& List<T>::operator=(List<T>& L)
{
size=L.getSize();
last=L.getLength()-1;
for(int i=0;i<=last;i++)
{
L.getData(i,data[i]);
}
return *this;
}
int main()
{
List<int> test1,test3;
List<char> test2;
test1.input();
test1.output();
test3.output();
test3=test1;
test3.output();
}
/*
1、给i的值进行取数设数判断等操作,添加判断i是否再列表范围内。 插入删除还要判断表满表空的情况
2、 申请空间时记得判断是否申请成功
3、bool型,void型根据需要灵活转换
4、根据size的值申请空间时候判断size>0;
5、声明的函数后有const ,下面描述的时候也要有const
6、注意重载=中不需要使用this->size等。
*/

单链表


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
#include<iostream>
using namespace std;
template <class T>
struct LinkNode
{
T data;
LinkNode<T> *next=NULL;
};
template <class T>
class List
{
public:
List();//构造函数
List(const T& x);//构造函数
List( List<T>& L);//复制构造函数
~List(){makeEmpty();};
void makeEmpty();//置空表
int getLength()const;//获取表长
LinkNode<T> *getHead()const{return head;};//获取头节点地址
LinkNode<T> *Search(T x);// 查询含有数据x节点的地址 失败返回NULL
LinkNode<T> *Locate(int i);// 查询第i个 数据的地址 失败返回NULL
bool getData(int i,T&x);//用x获取第i个数据
bool setData(int i,T &x);//用x替换第i个位替上的数据
bool Insert(int i,T &x);//在第i个元素后插入数据x
bool Remove(int i,T &x);//删除第i个数据并用x返回
bool isEmpyty()const; //判断表空
bool isFull()const ;//判断表满
void inputQianCha();//清空链表,输入结束标志,根据标志判断来输入数据
void inputHouCha();//清空链表,输入结束标志,根据标志判断来输入数据
void output();//输出
List<T>&operator=(List<T> &L);
protected:
LinkNode<T> *head;
};
template <class T>
List<T>::List()
{
head=new LinkNode<T>;
}
template <class T>
List<T>::List(const T& x)
{
head=new LinkNode<T>(x);
}
template <class T>
List<T>::List(List<T>& L)
{

LinkNode<T> *p1,*p2,*newNode;
p1=L.getHead()->next;
p2=head=new LinkNode<T>; //p2=head=new LinkNode<T>;必须要有 new LinkNode<T>,因为此时head还没有构造出来。
while(p1!=NULL)
{

newNode=new LinkNode<T>;
newNode->data=p1->data;
p2->next=newNode;
p2=newNode;
p1=p1->next;
}
}
template <class T>
void List<T>::makeEmpty()
{
LinkNode<T> *p=head->next;
while(head->next!=NULL)
{
head->next=p->next;
delete p;
p=head->next;
}
}
template <class T>
int List<T>::getLength()const
{
LinkNode<T> *p=head->next;
int num=0;
while(p!=NULL)
{
num++;
p=p->next;
}
return num;
}
template <class T>
LinkNode<T>* List<T>::Search(T x)
{
LinkNode<T> *p=head->next;
while(p!=NULL)
{
if(p->data==x)
return p;
p=p->next;
}
return p;
}
template <class T>
LinkNode<T>* List<T>::Locate(int i)
{
if(i<=0) return NULL;
int num=1;
LinkNode<T> *p=head->next;
while(i!=num&&p!=NULL)
{
num++;
p=p->next;
}
return p;
}
template <class T>
bool List<T>::getData(int i,T&x)
{
LinkNode<T> *p=Locate(i);
if(p==NULL)
return false;
else
{
x=p->data;
return true;
}
}
template <class T>
bool List<T>::setData(int i,T &x)
{
LinkNode<T> *p=Locate(i);
if(p==NULL)
return false;
else
{
p->data=x;
return true;
}
}
template <class T>
bool List<T>::Insert(int i,T &x)
{
LinkNode<T> *p1=Locate(i),*p2;
if(p1==NULL)
return false;
else
{
p2=new LinkNode<T>(x);
if(p2==NULL)
{
cerr<<"储存分配错误"<<endl;
exit(1);
}
p2->next=p1->next;
p1->next=p2;
return true;
}
}
template <class T>
bool List<T>::Remove(int i,T &x)
{
LinkNode<T> *p1=Locate(i-1),*p2;
if(p1==NULL||p1->next==NULL)
return false;
else
{
p2=p1->next;
p1->next=p2->next;
x=p2->data;
delete p2;
return true;
}
}
template <class T>
bool List<T>::isEmpyty()const
{
if(head->next==NULL)
return true;
else
return
false;
}
template <class T>
bool List<T>::isFull()const
{
return false;
}
template <class T>
void List<T>::inputQianCha()
{
makeEmpty();
T endTag,val;
LinkNode<T> *newNode;
cout<<"请输入结束标志";
cin>>endTag;
while(1)
{
cin>>val;
if(val==endTag)
break;
newNode=new LinkNode<T>(val);
if(newNode==NULL)
{
cerr<<"储存分配错误"<<endl;
exit(1);
}
newNode->next=head->next;
head->next=newNode;
}
}
template <class T>
void List<T>::inputHouCha()
{
makeEmpty();
T endTag,val;
LinkNode<T> *newNode,*p=head;
cout<<"请输入结束标志";
cin>>endTag;
while(1)
{
cin>>val;
if(val==endTag)
break;
newNode=new LinkNode<T>;
newNode->data=val;
if(newNode==NULL)
{
cerr<<"储存分配错误"<<endl;
exit(1);
}
p->next=newNode;
p=p->next;
}
}
template <class T>
void List<T>::output()
{
LinkNode<T> *p=head->next;
while(p!=NULL)
{
cout<<p->data<<",";
p=p->next;
}
cout<<endl;
}
template <class T>
List<T>& List<T>::operator=(List<T> &L)
{
makeEmpty(); //先清空原有的数据
LinkNode<T> *p1,*p2,*newNode;
p1=L.getHead()->next;
p2=head;
while(p1!=NULL)
{
newNode=new LinkNode<T>;
newNode->data=p1->data;
p2->next=newNode;
p2=newNode;
p1=p1->next;
}
return *this;
}
int main()
{
List<int> test1,test2;
test1.inputHouCha();
test1.output();
test2=test1;
test2.output();
List<int> test3(test2);
test3.output();
test3.inputHouCha();
test3.output();
}
/*
1、置空表
2、 Locate查询第i个数据的地址,注意i的合理性判断,注意判断在查找第i个数据前是否链表就结束了
3、 getData获取第i个数据,可以利用 Locate函数,节省代码; 同理,setData、Insert、Remove也一样;
4、 凡是使用new 后面都要考虑申请失败退出程序;
5、删除第i个元素,注意是找到第i-1个元素。 且要判断下一个元素地址也不为空
6、new LinkNode<T>(val)直接将值输入
7、顺序表中为T *data,链表为T data;
8、复制构造函数中p2=head=new LinkNode<T>必须要有 new LinkNode<T>,因为此时head还没有构造出来。而重载=号中head已经是构造出来的了。
*/
-----------------------本文结束 感谢阅读-----------------------
坚持原创技术分享,您的支持将鼓励我继续创作!恰饭^.^~