CSeqList.h
#include<iostream>
#include<cstdlib>
#include<iomanip>
using namespace std;
template<class>
class SeqList
{
private:
DataType *list;//数组
int maxSize;//数组可存放的最大元素个数
int size;//数组当前的元素个数
void reSize(int newSize);//改变list数组的空间大小
public:
SeqList(int max = 0);//构造函数
~SeqList();//析构函数
int Size(void) const;//读取数组当前的元素个数
void Insert(const DataType & item, int i);//插入,在指定位置 i 插入一个数据元素item
void EndInsert(const DataType & x);//在线性表末尾插入元素x
DataType Delete(const int i);//删除指定位置 i 的数据元素
DataType GetData(int i) const;//读取数据元素
int MoreDataDelete(DataType & x);//可删除值相同的数据元素
void Input();//元素输入
void Output();//元素输出
int Search(DataType & x) const;//顺序查找
int DataLocation(DataType & x) const;//定位操作（返回与x相等的第1个数据元素的位置序号）
void Inversion();//顺序表的就地逆置,即将顺序表 A=(a0,a1,a2,...,an-1) 变为 A=(an-1,...,a2,a1,a0)
void Union(SeqList<datatype> & la, SeqList<datatype> & lb);//合并顺序表la和lb,结果存放到la,重复元素只留一个/<datatype>/<datatype>
void Intersection(SeqList<datatype> & la, SeqList<datatype> & lb);//求顺序表la和lb中的共有元素,结果存放到la/<datatype>/<datatype>
};
template<class>
SeqList<datatype>::SeqList(int max) //构造函数/<datatype>
{
maxSize = max;
size = 0;
list = new DataType[maxSize];
}
template<class>
SeqList<datatype>::~SeqList() //析构函数/<datatype>
{
delete[]list;
}
template<class>
void SeqList<datatype>::reSize(int newSize) //扩充顺序表的存储数组的空间大小/<datatype>
{
if (newSize <= 0)
{
cout << "无效的数组大小" << endl;
return;
}
if (newSize != maxSize)
{
DataType *newlist = new DataType[newSize];//构造新的数组
int n = size;
DataType *sl = list;//原数组list的首地址
DataType *sn = newlist;//新建数组newlist的首地址
while (n--)
*sn = *sl;//将原数组list中的数据元素拷贝到新建数组newlist中
delete[]list;//删除原数组
//复制新数组
list = newlist;
maxSize = newSize;
}
}
template<class>
int SeqList<datatype>::Size(void) const //读取数组当前的元素个数/<datatype>
{
return size;
}
template<class>
void SeqList<datatype>::Insert(const DataType & item, int i) //插入/<datatype>
{ //在指定位置 i 插入一个数据元素item
if (size == maxSize)
{
cout << "顺序表已满,无法插入" << endl;
exit(0);
}
if (i<0 || i>size)
{
cout << "参数i越界出错" << endl;
exit(0);
}
for (int j = size - 1; j >= i; j--) // j >= i - 1
list[j + 1] = list[j];//从size - 1到i逐个元素向后移
list[i] = item;//在i位置插入item // list[i - 1] = item
size++;//数组当前的元素个数必须加1
}
template<class>
void SeqList<datatype>::EndInsert(const DataType & x) //在线性表末尾插入元素x/<datatype>
{
if (size == MaxSize)
{
cout << "顺序表已满,插入错误" << endl;
exit(0);
}
list[size] = x;
size++;
}
template<class>
DataType SeqList<datatype>::Delete(const int i) //删除指定位置 i 的数据元素/<datatype>
{
if (size == 0)
{
cout << "顺序表已空,无元素可删" << endl;
exit(0);
}
if (i<0 || i>size - 1) //i从0开始
{
cout << "参数i越界出错" << endl;
exit(0);
}
DataType x = list[i];//取到要删除的元素
for (int j = i; j < size - 1; j++)
list[j] = list[j + 1];//从i+1到size-1逐个元素向前移
size--;//数组当前的元素个数减1 //超出size-1部分不能访问,但是数值还存在。
return x;
}
template<class>
DataType SeqList<datatype>::GetData(int i) const //读取数据元素/<datatype>
{ //取位置 i 的数据元素,取到的数据元素由函数返回
if (i<0 || i>size - 1)
{
cout << "参数i越界出错" << endl;
exit(0);
}
return list[i];//返回取到的元素
}
template<class>
int SeqList<datatype>::MoreDataDelete(DataType & x) //可删除相同元素/<datatype>
{
int i, j;
int tag = 0;//初始删除标记置为0
for (i = 0; i<size>
{
if (x == list[i])
{
for (j = i; j<size>
list[j] = list[j + 1];
size--;
i--;//保证两个相邻的元素相同时正确删除
tag = 1;//设置删除成功标志
}
}
return tag;
}
template<class>
void SeqList<datatype>::Input() //输入数据/<datatype>
{
cout << "请输入顺序表存放的最大元素个数:" << endl;
cin >> maxSize;
cout << "开始建立顺序表,请输入表中的元素个数:" << endl;
cin >> size;
if (size > maxSize)
{
cout << "输入表中的元素个数有误" << endl;
exit(0);
}
for (int i = 0; i<size>
cin >> list[i];
}
template<class>
void SeqList<datatype>::Output() //输出数据/<datatype>
{
int i;
// int count = 0;//计数
for (i = 0; i<size>
{
cout << list[i] << " ";
// cout << list[i] << setw(6);
// count++;
// if (count % 5 == 0) //每行输出5个数据
// cout << endl;
}
cout << endl;
}
template<class>
int SeqList<datatype>::Search(DataType & x) const //顺序查找/<datatype>
{
int i = 0;
while (i <= size - 1 && list[i] != x)
i++;
if (i>size - 1)
return -1;
else
return list[i];//如果是 return i; 呢？
}
template<class>
int SeqList<datatype>::DataLocation(DataType & x) const //定位操作（返回与x相等的第1个数据元素的位置序号）/<datatype>
{
int i = 0;
while (i <= size - 1 && list[i] != x) //找到要定位的数据元素
i++;
if (i>size - 1)
return -1;
else
{
cout << i << endl;
return i;//返回数据元素的位置序号
}
}
template<class>
void SeqList<datatype>::Inversion() //顺序表的就地逆置,即将顺序表 A=(a0,a1,a2,...,an-1) 变为 A=(an-1,...,a2,a1,a0)/<datatype>
{
int i;
DataType temp;
for (i = 1; i <= size / 2; i++)
{
temp = list[i - 1];
list[i - 1] = list[size - i];
list[size - i] = temp;
}
}
template<class>
void SeqList<datatype>::Union(SeqList<datatype> & la, SeqList<datatype> & lb)/<datatype>/<datatype>/<datatype>
{
int n = la.Size();
int m = lb.Size();
int i, j, k;
for (i = 0; i { j = lb.GetData(i); k = la.Search(j); if (k == -1) { la.Insert(j, n); n++;
}
}
}
template<class>
void SeqList<datatype>::Intersection(SeqList<datatype> & la, SeqList<datatype> & lb)/<datatype>/<datatype>/<datatype>
{
int n = la.Size();
int m = lb.Size();
int i, j, k;
for (i = 0; i { j = la.GetData(i); k = lb.Search(j); if (k == -1) { la.Delete(i); n--; i--; } } } main.cpp #include "CSeqList.h" int main(void) { SeqList SeqList int s[10] = { 3, 2, 4, 6, 12, 22, 15, 18, 13, 8 }; int t[10] = { 3, 2, 5, 6, 11, 22, 16, 17, 10, 7 }; /* int s[3]={3,4,2}; int t[3]={3,2,5}; for(int i=0;i<3;i++) myList.Insert(s[i],i); for(i=0;i<3;i++) myList1.Insert(t[i],i); */ for (int i = 0; i<10; i++) myList.Insert(s[i], i); for (int i = 0; i<10; i++) myList1.Insert(t[i], i); myList.Output(); myList1.Output(); myList.Union(myList, myList1); myList.Output(); myList.Intersection(myList, myList1); /* myList.Input(); myList.Output(); int i; int j; cin>>i; myList.DataLocation(i); cin>>j; myList.Search(j); myList.Insert(12,j); myList.Delete(j); myList.Inversion(); myList.Delete(j); */ myList.Output(); system("pause"); return 0; }
閱讀更多 墨眉無鋒似劍非攻 的文章
