C++实现顺序表的14种操作

// 顺序表.cpp: 定义控制台应用程序的入口点。
//Author:kgvito YinZongYao
//Date: 2017.12.27 #include "stdafx.h"
#include<iostream>
using namespace std; #define MAXSIZE 3
#define Node ElemType
#define ERROR 0
typedef int DataType; //创建一个节点类
class Node
{
public:
DataType data;
}; //创建一个顺序表类
class SqList
{
public:
SqList(); //初始化顺序表
~SqList(); //销毁顺序表
void CreateSqList(int n); //定义创建一个顺序表
void TraverseSqList(); //遍历顺序表
ElemType GetElemByIndex(int i); //根据下标查找顺序表中的元素
bool isEmpty(); //判断顺序表是否为空
bool isFull(); //判断顺序表是否满
int GetLength(); //获取顺序表的长度
int GetElemByElem(DataType data); //查看顺序表中是否含有查找的值
void InsertSqList(int n, DataType data); //向顺序表中插入新数据
void InsertSqListAtHead(DataType data); //在头部插入新数据
void InsertSqListAtEnd(DataType data); //向顺序表的最后插入数据
void DeleteElem(int i); //删除指定位置的值
void DeleteElemAtElem(DataType data);//按值删除元素
void DeleteAll(); //删除所有元素
void DeleteAtHead(); //在头部删除元素
private:
Node * elem; //顺序表的基地址
int length; //顺序表的长度
}; //初始化顺序表
SqList::SqList()
{
elem = new ElemType[MAXSIZE]; //开辟空间
if (!elem) { //当溢出时报异常
exit(OVERFLOW);
}
length = ; //定义顺序表的长度
} //销毁顺序表
SqList::~SqList()
{
delete[] elem; //删除基地址的指针
} //创建顺序表
void SqList::CreateSqList(int n)
{
if (n < ) { //当输入的数值有误时报异常
cout << "输入的节点个数有误!" << endl;
exit(EXIT_FAILURE);
}
else {
int i;
for (i = ; i < n;i++) { //循环向数组中插入数据
cout << "请输入第" << i + << "个节点元素: ";
cin>>elem[i].data;
}
length = n; //更改顺序表的长度
}
} //遍历顺序表
void SqList::TraverseSqList()
{
for (int i = ; i < length;i++) { //循环打印顺序表的每个节点数据
cout << "第" << i + << "个元素的值是" << elem[i].data << endl;
}
} //通过下标获取元素
ElemType SqList::GetElemByIndex(int i)
{
if (i < || i > length) { //下标输入有误时报异常
cout << "查询的下标不存在" << endl;
}
else {
return elem[i - ]; //返回下标指定的节点
}
} //判断顺序表是否为空
bool SqList::isEmpty()
{
if (length == ) //如果顺序表的长度为0，则表为空
return true;
return false; //长度不为0，表不为空
} //判断顺序表是否满
bool SqList::isFull()
{
if (length == MAXSIZE) //当长度为定义的最大长度，则顺序表满
return true;
return false; //否则不满
} //获取顺序表的长度
int SqList::GetLength()
{
return length; //返回顺序表的长度
} //判断是否存在寻找的值,如果存在将返回下标
int SqList::GetElemByElem(DataType data)
{
int i;
for (i = ; i < length;i++) { //从头遍历顺序表
if (elem && elem[i].data == data) { //若找到与之匹配的数据，则返回当前节点的下标
return i + ;
}
if (i == length - ) { //否则返回-1
return -;
} }
} //插入一个数据
void SqList::InsertSqList(int i, DataType data)
{
if (i< || i > length+) { //下标输入有误时报异常
cout << "输入的下标不合法" << endl;
}
else if (length > MAXSIZE) { //当顺序表满时无法插入新的数据
cout << "已经达到最大长度" << endl;
}
else
{
for (int j = length - ; j >= i - ; j--) { //遍历到要插入的位置
elem[j + ] = elem[j]; //从j位置后的全体数据向后移一位
}
elem[i - ].data = data; //插入数据
length++; //更改顺序表长度
}
} //在头部插入一个新数据
void SqList::InsertSqListAtHead(DataType data)
{ for (int i = length - ; i >= ; i--) //将全体元素向后移一位
{
elem[i + ] = elem[i];
}
elem[].data = data; //在第一个位置插入元素
length++; //更改长度
} //在顺序表的最后插入数据
void SqList::InsertSqListAtEnd(DataType data)
{
if (length > MAXSIZE) { //当顺序表满时无法插入新的数据
cout << "已经达到最大长度" << endl;
}
else
{
elem[length].data = data; //插入数据
length++; //更改顺序表长度
}
} //根据下标删除一个节点
void SqList::DeleteElem(int i)
{
int j;
if (i< || i>length) //输入的位置不合法报异常
cout << "输入的下标不合法" << endl;
else
{
for (j = i; j <= length - ;j++) { //循环到要删除节点的位置
elem[j - ] = elem[j]; //该位置后的元素全体向前移一个位置
}
length--; //更改顺序表长度
}
} //按值删除元素
void SqList::DeleteElemAtElem(DataType data)
{
int i = ;
while (elem[i].data == data && i < length) //按值查到要删除数据的位置
{
i++;
}
for (int index = i; index <= length - ; index++) //将该位置后的节点全体向前移一位
{
elem[index - ] = elem[index];
}
length--; //更改顺序表长度
} //删除所有元素
void SqList::DeleteAll()
{
for (int i = length;i > ;i--) //从最后一个元素开始删除，长度减一
{
elem[i] = elem[i - ]; //元素向前移位
length--; //长度减一
}
} //在头部删除元素
void SqList::DeleteAtHead()
{
for (int i = ; i <= length - ; i++) {
elem[i - ] = elem[i];
}
length--;
} //测试函数
int main()
{
SqList l;
int i;
cout << "1.创建一个顺序表 2.遍历顺序表 3.通过下标获取元素\n4.查找要查询的元素的下标 5.通过下标插入元素 6.通过下标删除一个元素\n7.获取顺序表的长度 8.删除所有元素 9.判断顺序表是否为空\n10.判断顺序表是否满 11.根据数据删除节点 12.在头部插入数据\n13.在头部删除数据 14.在顺序表最后插入数据 0.退出" << endl;
do
{
cout << "请选择一个操作: " ;
cin >> i;
switch (i)
{
case :
int n;
cout << "请输入顺序表的元素个数: ";
cin >> n;
l.CreateSqList(n);
break;
case :
l.TraverseSqList();
break;
case :
int i;
cout << "请输入将要获取元素的下标: ";
cin >> i;
ElemType getElemByIndex = l.GetElemByIndex(i);
cout << getElemByIndex.data << endl;
break;
case :
DataType data;
cout << "请输入将要查找元素的值: ";
cin >> data;
cout<<"该元素的下标为:"<<l.GetElemByElem(data)<<endl;
break;
case :
int index;
DataType insertData;
cout << "请输入要插入的数据的位置: ";
cin >> index;
cout << "请输入要插入的数据: ";
cin >> insertData;
l.InsertSqList(index, insertData);
break;
case :
int deleteIndex;
cout << "请输入要删除的数据的下标: ";
cin >> deleteIndex;
l.DeleteElem(deleteIndex);
break;
case :
cout<<l.GetLength()<<endl;
break;
case :
l.DeleteAll();
break;
case :
if (l.isEmpty() == ) {
cout << "顺序表为空" << endl;
}
else
{
cout << "顺序表不为空" << endl;
}
break;
case :
if (l.isFull() == ) {
cout << "顺序表满" << endl;
}
else
{
cout << "顺序表不满" << endl;
}
break;
case :
DataType data1;
cout << "请输入要删除的数据: ";
cin >> data1;
l.DeleteElemAtElem(data1);
break;
case :
DataType data2;
cout << "请输入要在头部插入的数据: ";
cin >> data2;
l.InsertSqListAtHead(data2);
break;
case :
l.DeleteAtHead();
break;
case :
DataType data3;
cout << "请输入要在末尾插入的数据: ";
cin >> data3;
l.InsertSqListAtEnd(data3);
break;
default:
break;
}
} while(i != );
system("pause");
return ;
}