数据结构实验1(顺序表逆置以及删除)
最后更新于：2022-04-01 20:51:24
在顺序表类SeqList中增加成员函数void Reverse()，实现顺序表的逆置。
在顺序表类SeqList中增加成员函数bool DeleteX(const T &x)，删除表中所有元素值等于x的元素。若表中存在这样的元素，则删除之，且函数返回true。否则函数返回false。
直接在SeqList类增加两个成员函数完成相应功能，逆置的话用到了stl中的栈，原elements入栈后紧着着赋值覆盖原来的元素值就实现了逆置。删除所有等于x的元素则扫一遍顺序表，若找到等于x的元素就调用Delete()函数，最后比较原长度以及现长度就知道有没有删除成功。
实现代码：
~~~
#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
#include "stack"
using namespace std;
template
class LinearList
{
public:
virtual bool IsEmpty() const = 0; // 为空则返回true
virtual int Length() const = 0; // 返回长度
virtual bool Find(int i, T &x) const = 0; // 若a[i]存在则x = a[i]，返回true，不存在返回flase
virtual int Search(T x) const = 0; // 若存在等于x的元素则返回下标，否则返回-1
virtual bool Insert(int i, T x) = 0; // i == -1则x插在第一个元素之前， 否则x插在a[i]后，插入成功返回true
virtual bool Delete(int i) = 0; // 删除元素a[i]，删除成功返回true
virtual bool Update(int i, T x) = 0; // 修改元素a[i]为x，若修改成功则返回true
virtual void Output(ostream &out) const = 0;
/* data */
protected:
int n;
};
template
class SeqList:public LinearList
{
public:
SeqList(int mSize);
~SeqList() {delete []elements;}
bool IsEmpty() const;
int Length() const;
bool Find(int i, T &x) const;
int Search(T x) const;
bool Insert(int i, T x);
bool Delete(int i);
bool Update(int i, T x);
void Output(ostream &out) const;
void Reverse(); // 顺序表的逆置
bool DeleteX(const T &x); // 删除表中所有等于x的元素，成功则返回true
/* data */
private:
int maxLength, n;
T *elements;
};
template
SeqList::SeqList(int mSize)
{
maxLength = mSize;
elements = new T[maxLength];
n = 0;
}
template
bool SeqList::IsEmpty() const
{
return n == 0;
}
template
int SeqList::Length() const
{
return n;
}
template
bool SeqList::Find(int i, T &x) const
{
if(i < 0 || i > n - 1) { // i不合法
cout << "Out of Bounds" << endl << endl;
return false;
}
x = elements[i];
return true;
}
template
int SeqList::Search(T x) const
{
for(int i = 0; i < n; ++i)
if(elements[i] == x) return i;
return -1;
}
template
bool SeqList::Insert(int i, T x)
{
if(i < -1 || i > n - 1) { // i不合法
cout << "Out of Bounds" << endl << endl;
return false;
}
if(n == maxLength) { // 数组满了
cout << "OverFlow" << endl << endl;
return false;
}
for(int j = n - 1; j > i; --j)
elements[j + 1] = elements[j];
elements[i + 1] = x;
n++;
return true;
}
template
bool SeqList::Delete(int i)
{
if(!n) { // 数组已经为空
cout << "UnderFlow" << endl << endl;
return false;
}
if(i < 0 || i > n - 1) { // i不合法
cout << "Out of Bounds" << endl << endl;
return false;
}
for(int j = i + 1; j < n; ++j)
elements[j - 1] = elements[j];
n--;
return true;
}
template
bool SeqList::Update(int i, T x)
{
if(i < 0 || i > n - 1) { // i不合法
cout << "Out of Bounds" << endl << endl;
return false;
}
elements[i] = x;
return true;
}
template
void SeqList::Output(ostream &out) const
{
for(int i = 0; i < n; ++i)
out << elements[i] << " ";
out << endl << endl;
}
template
void Union(SeqList &A, SeqList &B)
{
T x;
for(int i = 0; i < B.Length(); ++i) {
B.Find(i, x);
if(A.Search(x) == -1) A.Insert(A.Length() - 1, x);
}
}
template
void SeqList::Reverse()
{
stack s;
for(int i = 0; i < n; ++i)
s.push(elements[i]);
for(int i = 0; i < n; ++i) {
elements[i] = s.top();
s.pop();
}
cout << "转置成功" << endl;
}
template
bool SeqList::DeleteX(const T &x)
{
int flag = n;
for(int i = 0; i < n; ++i)
if(elements[i] == x) {
Delete(i);
i--;
}
if(flag != n) return true;
return false;
}
int main(int argc, char const *argv[])
{
SeqList A(20), B(20);
for(int i = 0; i < 5; ++i)
A.Insert(i - 1, i); // A = {0, 1, 2, 3, 4}
cout << "顺序表A为：" << endl;
A.Output(cout);
for(int i = 5; i < 10; ++i)
B.Insert(i - 6, i); // B = {5, 6, 7, 8, 9}
cout << "顺序表B为：" << endl;
B.Output(cout);
A.Update(1, 5); // A = {0, 5, 2, 3, 4}
cout << "更新后顺序表A为：" << endl;
A.Output(cout);
int flag = A.Search(2); // 元素中是否有2
if(flag != -1) cout << "有等于2的元素" << endl;
else cout << "无等于2的元素" << endl;
int x;
A.Find(2, x); // x = a[2];
cout << "a[2] == " << x << endl;
B.Insert(-1, 0); // B = {0, 5, 6, 7, 8, 9}
cout << "插入0后顺序表B为：" << endl;
B.Output(cout);
B.Insert(3, 2); // B = {0, 5, 6, 7, 2, 8, 9}
cout << "插入2后顺序表B为：" << endl;
B.Output(cout);
B.Delete(4); // B = {0, 5, 6, 7, 8, 9}
cout << "删除4后顺序表B为：" << endl;
B.Output(cout);
Union(A, B); // 合并A, B到A A = {0, 2, 3, 4, 5, 6, 7, 8, 9}
cout << "合并A，B到A后顺序表A为：" << endl;
A.Output(cout);
B.Reverse(); // B = {9, 8, 7, 6, 5, 0};
cout << "转置后顺序表B为：" << endl;
B.Output(cout);
B.Insert(-1, 9);
cout << "插入9后顺序表B为：" << endl;
B.Output(cout);
x = 9;
if(B.DeleteX(x)) cout << "删除表中x成功" << endl;
else cout << "表中无等于x的元素" << endl;
cout << "顺序表B为：" << endl;
B.Output(cout);
return 0;
}
~~~
';