南邮数据结构上机实验一线性表的基本运算和多项式的基本运算(4)

更全面。 经过这次的实验，我在各个方面都得到了不少的提高，我希望多几次像这样的实验让我们更好的锻炼自己。

附录：

1. 线性表的基本运算

#include using namespace std; int const LEN = 50; template class LinearList {

public:

virtual bool IsEmpty() const = 0; virtual int Length() const = 0;

virtual bool Find(int i,T& x) const = 0; virtual int Search(T x) const = 0; virtual bool Insert(int i,T x) = 0; virtual bool Delete(int i) = 0; virtual bool Update(int i,T x) = 0;

virtual void Output(ostream& out) const = 0; protected:

int n; //线性表的长度 };

template

class SeqList: public LinearList {

private:

int maxLength; //线性表的最大长度 T *elements; //动态一维数组的指针 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); };

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) {

cout << \ //对i进行越界检查 return false; }

x = elements[i]; return true; }

template

int SeqList::Search(T x) const {

for(int j = 0; j < n; j++) if(elements[j] == x) return j; return -1; }

template

bool SeqList::Insert(int i, T x) {

if(i < -1 || i > n - 1) {

cout << \ return false; }

if(n == maxLength) {

cout << \ 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 << \ return false; }

if(i < 0 || i > n - 1) {

cout << \ 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) {

cout<<\ 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;

}

template

void SeqList::Reverse() {

T temp; //临时变量存放数据

for(int i = 0; i < n / 2; i++) //前后互换逆置 {

temp = elements[i];

elements[i] = elements[n - i - 1]; elements[n - i - 1] = temp; } }

template

bool SeqList::DeleteX(const T& x) {

int tmp = n, i; //用于判断是否有删除数据 n = 0;

int *hash = new int[tmp]; for(i = 0; i < tmp; i++) {

hash[i] = 0;

if(elements[i] == x) hash[i]++; }

for(i = 0; i < tmp; i++) if(!hash[i])

elements[n++] = elements[i]; delete[]hash;

if(n == tmp) //判断是否有删除的数据 return false; else

return true; }

int main() {

int del_data, len ,num; SeqList A(LEN);

cout << \ cin >> len;

cout << \ for(int i = 0; i < len; i++) {

cin >> num;

A.Insert(i - 1, num);