如何使用C++顺序表
这篇文章主要讲解了如何使用C++顺序表,内容清晰明了,对此有兴趣的小伙伴可以学习一下,相信大家阅读完之后会有帮助。
为丹寨等地区用户提供了全套网页设计制作服务,及丹寨网站建设行业解决方案。主营业务为网站设计、成都网站建设、丹寨网站设计,以传统方式定制建设网站,并提供域名空间备案等一条龙服务,秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求,就会得到认可,从而选择与我们长期合作。这样,我们也可以走得更远!
一、遇到问题:
原因:类的函数定义不能放在SeqList.cpp中,必须放在Seqlist.h(类的函数声明和定义放在同一个文件下)中,否则
会出现以下问题。
二、实现程序:
1.SeqList.h
#ifndef SeqList_h #define SeqList_h #includeusing namespace std; const int defaultSize = 100; template class SeqList{ public: SeqList(int sz = defaultSize); // 构造函数 SeqList(SeqList & 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 operator=(SeqList & L); // 表整体赋值 private: T *data; // 存放数组 int maxSize; // 最大可容纳表项的项数 int last; // 当前已存表项的最后位置(从0开始) void reSize(int newSize); // 改变数组空间大小 }; template SeqList ::SeqList(int sz) { // 构造函数,通过指定参数sz定义数组的长度 if(sz > 0) { maxSize = sz; last = -1; // 置表的实际长度为空 data = new T[maxSize]; // 创建顺序表存储数组 if(data == NULL) { cerr << "动态内存分配失败!" << endl; exit(1); } } } template SeqList ::SeqList(SeqList & 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 SeqList ::~SeqList() { // 析构函数 delete []data; } template void SeqList ::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 int SeqList ::Size(){ // 计算表最大可容纳表项个数 return maxSize; } template int SeqList ::Length(){ // 计算表长度 return last+1; } template int SeqList ::Search(T x){ // 搜索x在表中位置,函数返回表项序号:在表中的第几个位置;搜索失败:返回0 for(int i = 0; i <= last; i++) // 顺序搜索 if(data[i] == x) return (i+1); return 0; } template int SeqList ::Locate(int i){ // 定位第i个表项,函数返回第i(1<= i <= last+1)个表项的位置,否则函数返回-1,表示定位失败 if(i >= 1 && i <= last+1) return i-1; // 数组下标从0开始 return -1; } template bool SeqList ::getData(int i, T& x){ // 取第i个表项的值 if(i > 0 && i <= last+1) { x = data[i-1]; return true; } return false; } template void SeqList ::setData(int i, T x){ // 用x修改第i个表项的值 if(i > 0 && i <= last+1) data[i-1] = x; } template bool SeqList ::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 bool SeqList ::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 bool SeqList ::isEmpty(){ // 判断表是否为空,空则返回true;否则,返回false return (last == -1 ? true : false); } template bool SeqList ::isFull(){ // 判断表满否,满则返回true;否则,返回false return (last == maxSize-1 ? true : false); } template void SeqList ::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 void SeqList ::Output() { // 将顺序表全部元素输出到屏幕上 for(int i = 0; i <= last; i++) cout << data[i] << " "; cout << endl; } template void SeqList ::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 SeqList SeqList ::operator=(SeqList & 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
#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; SeqListL; // 声明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; }
看完上述内容,是不是对如何使用C++顺序表有进一步的了解,如果还想学习更多内容,欢迎关注创新互联行业资讯频道。
文章名称:如何使用C++顺序表
分享地址:http://pwwzsj.com/article/joipdh.html