服务器之家

服务器之家 > 正文

C++顺序表的基本操作（使用模版类）

时间：2021-09-02 16:12     来源/作者：ChanJose

本文实例为大家分享了C++顺序表的基本操作，供大家参考，具体内容如下

一、遇到问题：

原因：类的函数定义不能放在SeqList.cpp中，必须放在Seqlist.h(类的函数声明和定义放在同一个文件下)中，否则

会出现以下问题。

C++顺序表的基本操作（使用模版类）

二、实现程序：

1.SeqList.h

?
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
#ifndef SeqList_h
#define SeqList_h
#include <iostream>
using namespace std;
 
const int defaultSize = 100;
 
template<class T>
class SeqList{
public:
 SeqList(int sz = defaultSize); // 构造函数
 SeqList(SeqList<T>& L); // 复制构造函数
 ~SeqList(); // 析构函数
 int Size(); // 重载虚函数：计算表最大可容纳表项个数，限制权限，类外无法直接获取maxSize
 int Length(); // 计算表长度
 int Search(T x); // 搜索x在表中位置，函数返回表项序号
 int Locate(int i); // 定位第i个表项，函数返回表项序号
 bool getData(int i, T& x); // 取第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(); // 判断表是否为空，空则返回true;否则，返回false
 bool isFull(); // 判断表满否，满则返回true;否则，返回false
 void Input(); // 输入数据建立表
 void Output(); // 打印表
 void Sort(); // 排序
 SeqList<T> operator=(SeqList<T>& L); // 表整体赋值
private:
 T *data; // 存放数组
 int maxSize; // 最大可容纳表项的项数
 int last; // 当前已存表项的最后位置（从0开始）
 void reSize(int newSize); // 改变数组空间大小
};
 
template <class T>
SeqList<T>::SeqList(int sz) {
 // 构造函数,通过指定参数sz定义数组的长度
 if(sz > 0) {
 maxSize = sz;
 last = -1; // 置表的实际长度为空
 data = new T[maxSize]; // 创建顺序表存储数组
 if(data == NULL) {
 cerr << "动态内存分配失败!" << endl;
 exit(1);
 }
 }
}
 
template <class T>
SeqList<T>::SeqList(SeqList<T>& L) {
 // 复制构造函数，用参数表中给出的已有顺序表初始化新建的顺序表
 // 如果没有定义复制构造函数，系统会自动建立一个复制构造函数
 maxSize = L.Size(); // 最大可容纳的个数
 last = L.Length() - 1; // 数组最后的位置
 T value;
 data = new T[maxSize]; // 创建顺序表存储数组
 if(data == NULL) {
 cerr << "动态内存分配失败!" << endl;
 exit(1);
 }
 for(int i = 1; i <= last+1; i++) {
 L.getData(i, value); // 取第i个位置的值
 data[i-1] = value;
 }
}
 
template <class T>
SeqList<T>::~SeqList() {
 // 析构函数
 delete []data;
}
 
template <class T>
void SeqList<T>::reSize(int newSize) {
 // 私有函数：扩充顺序表的存储数组空间大小，新数组的元素个数为newSize
 if(newSize <= 0) { // 检查参数的合理性
 cerr << "无效的数组大小" << endl;
 return;
 }
 if(newSize != maxSize) { // 修改
 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++; // 复制：只是数据
 delete []data; // 删除旧数组
 data = newArray; // 复制新数组
 maxSize = newSize; // 复制新数组：数据和内存空间
 }
}
 
template <class T>
int SeqList<T>::Size(){
 // 计算表最大可容纳表项个数
 return maxSize;
}
 
template <class T>
int SeqList<T>::Length(){
 // 计算表长度
 return last+1;
}
 
template <class T>
int SeqList<T>::Search(T x){
 // 搜索x在表中位置，函数返回表项序号:在表中的第几个位置；搜索失败：返回0
 for(int i = 0; i <= last; i++) // 顺序搜索
 if(data[i] == x)
 return (i+1);
 return 0;
}
 
template <class T>
int SeqList<T>::Locate(int i){
 // 定位第i个表项，函数返回第i（1<= i <= last+1）个表项的位置，否则函数返回-1，表示定位失败
 if(i >= 1 && i <= last+1)
 return i-1; // 数组下标从0开始
 return -1;
}
 
template <class T>
bool SeqList<T>::getData(int i, T& x){
 // 取第i个表项的值
 if(i > 0 && i <= last+1) {
 x = data[i-1];
 return true;
 }
 return false;
}
 
template <class T>
void SeqList<T>::setData(int i, T x){
 // 用x修改第i个表项的值
 if(i > 0 && i <= last+1)
 data[i-1] = x;
}
 
template <class T>
bool SeqList<T>::Insert(int i, T x) {
 // 在第i个表项后插入元素x
 if(last == maxSize-1) // 表满，不能插入
 return false;
 if(i < 0 || i > last+2) // 参数i不合理，不能插入, last+2表示数组的最后面插入
 return false;
 for(int j = last; j >= i; j--)
 data[j+1] = data[j]; // 依次后移，空出第i号位置
 data[i] = x; // 插入
 last++; // 最后位置加1
 return true; // 插入成功
}
 
template <class T>
bool SeqList<T>::Remove(int i, T& x) {
 // 删除第i个表项，通过x返回
 if(last == -1) // 表空，不能删除
 return false;
 if(i < 0 || i > last+1) // 参数i不合理，不能插入
 return false;
 x = data[i-1];
 for(int j = i-1; j < last; j++)
 data[j] = data[j+1];
 last--; // 最后位置减1
 return true; // 删除成功
}
 
template <class T>
bool SeqList<T>::isEmpty(){
 // 判断表是否为空，空则返回true;否则，返回false
 return (last == -1 ? true : false);
}
 
template <class T>
bool SeqList<T>::isFull(){
 // 判断表满否，满则返回true;否则，返回false
 return (last == maxSize-1 ? true : false);
}
 
template <class T>
void SeqList<T>::Input() {
 // 从标准输入（键盘）逐个数据输入，建立顺序表
 int len;
 cout << "开始建立顺序表，请输入表中元素个数:";
 cin >> len;
 if(len > maxSize) {
 cout << "表元素个数输入有误,范围不超过：" << maxSize << endl;
 return;
 }
 last = len - 1; // 数组最后位置
 cout << "请输入建表的数据:" << endl;
 for(int i = 0; i <= last; i++) // 逐个输入表元素
 cin >> data[i];
}
 
template <class T>
void SeqList<T>::Output() {
 // 将顺序表全部元素输出到屏幕上
 for(int i = 0; i <= last; i++)
 cout << data[i] << " ";
 cout << endl;
}
 
template <class T>
void SeqList<T>::Sort() {
 int flag;
 T temp;
 
 // 排序:从小到大
 for(int i = 0; i < last; i++) { // 最后一个不用排了
 flag = 0; // 标志该轮是否有交换, 0表示没有交换，1表示有交换
 // 没有交换，说明已排好序，提前结束
 for(int j = 0; j < (last - i); j++) { // 向后冒泡
 if(data[j] > data[j + 1]) {
 flag = 1;
 temp = data[j+1];
 data[j+1] = data[j];
 data[j] = temp;
 }
 }
 if(flag == 0) // 没有交换，提前结束程序
 break;
 }
 
}
 
template <class T>
SeqList<T> SeqList<T>::operator=(SeqList<T>& L) {
 int size, value;
 
 // 表整体赋值：顺序表整体赋值
 size = L.Size();
 if(maxSize != size) { // 表最大可容纳数小于L的
 reSize(size); // 该变数组大小
 }
 last = L.Length() - 1; // 数组的最后位置
 for(int i = 1; i <= last+1; i++) {
 L.getData(i, value); // 取第i个位置的值
 data[i-1] = value;
 }
}
 
#endif /* SeqList_h */

2.main.cpp

?
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
#include "SeqList.h"
using namespace std;
 
int main(int argc, const char * argv[]) {
 int choose, len, i, x, maxSize, loc; // val存储值，choose存储用户的选择
 bool finished = false;
 
 SeqList<int> L; // 声明SeqList对象
 while(!finished) {
 cout << "1:输入数据建立顺序表：" << endl;
 cout << "2:顺序表的最大可容纳表项个数：" << endl;
 cout << "3:顺序表的长度：" << endl;
 cout << "4:搜索x在表中的位置：" << endl;
 cout << "5:定位第i个表项：" << endl;
 cout << "6:取第i个表项的值：" << endl;
 cout << "7:用x修改第i个表项的值：" << endl;
 cout << "8:在第i个表项后插入元素x：" << endl;
 cout << "9:删除第i个表项：" << endl;
 cout << "10:判断表是否为空：" << endl;
 cout << "11:判断表满否：" << endl;
 cout << "12:打印顺序表中的数据：" << endl;
 cout << "13:将顺序表排序：" << endl;
 cout << "14:退出：" << endl;
 cout << "请输入你的选择[1-14]：" << endl;
 cin >> choose;
 switch(choose) {
 case 1:
 L.Input(); // 建立顺序表
 break;
 case 2:
 maxSize = L.Size();
 cout << "顺序表的最大可容纳表项个数为：" << maxSize << endl;
 break;
 case 3:
 len = L.Length();
 cout << "顺序表的长度为：" << len << endl;
 break;
 case 4:
 cout << "请输入要搜索的值x:";
 cin >> x;
 i = L.Search(x);
 if(i == 0)
  cout << "没找到" << x << endl;
 else
  cout << x << "在表中的第" << i << "个位置" << endl;
 break;
 case 5:
 cout << "请输入要定位的位置i：";
 cin >> i;
 loc = L.Locate(i);
 if(loc != -1)
  cout << "定位成功！在顺序表中下标为：" << loc << endl;
 else
  cout << "定位失败!" << endl;
 break;
 case 6:
 cout << "请输入要取表中元素的位置i:";
 cin >> i;
 if(L.getData(i, x))
  cout << "表中第" << i << "个表项的值为:" << x << endl;
 else
  cout << "取值失败！检查是否超范围取值" << endl;
 break;
 case 7:
 cout << "请输入要修改的位置i和值x:";
 cin >> i >> x;
 L.setData(i, x);
 break;
 case 8:
 cout << "请输入要插入的位置i和值x:";
 cin >> i >> x;
 if(L.Insert(i, x))
  cout << "插入成功！" << endl;
 else
  cout << "插入失败！" << endl;
 break;
 case 9:
 cout << "请输入要删除的表项的位置i:";
 cin >> i;
 if(L.Remove(i, x))
  cout << "删除成功！删除的值为:" << x << endl;
 else
  cout << "删除失败!" << endl;
 break;
 case 10:
 if(L.isEmpty())
  cout << "表为空！" << endl;
 else
  cout << "表不为空！" << endl;
 break;
 case 11:
 if(L.isFull())
  cout << "表满！" << endl;
 else
  cout << "表未满！" << endl;
 break;
 case 12:
 cout << "表中的数据为：" << endl;
 L.Output();
 break;
 case 13:
 cout << "表中的数据排序前：" << endl;
 L.Output();
 L.Sort();
 cout << "表中的数据排序后：" << endl;
 L.Output();
 break;
 case 14:
 finished = true;
 break;
 default:
 cout << "输入选择错误，请重新输入!" << endl;
 }
 }
 return 0;
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。

原文链接：https://blog.csdn.net/chuanzhouxiao/article/details/85777381

标签：
C++ 顺序表 

相关文章

热门资讯

yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
2021年耽改剧名单 2021要播出的59部耽改剧列表
2021年耽改剧名单 2021要播出的59部耽改剧列表 2021-03-05
返回顶部