本文实例为大家分享了C++顺序表的基本操作，供大家参考，具体内容如下
一、遇到问题：
原因：类的函数定义不能放在SeqList.cpp中，必须放在Seqlist.h(类的函数声明和定义放在同一个文件下)中，否则
会出现以下问题。
二、实现程序：
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
如果您对该产品感兴趣，请填写办理（客服微信：xiaoxiongyidong）
发表评论
◎欢迎参与讨论，请在这里发表您的看法、交流您的观点。