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; }
閱讀更多 墨眉無鋒似劍非攻 的文章
