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

实 验 报 告

（ 2015 / 2016学年 第二学期）

课程名称

数据结构A

实验名称 线性表的基本运算和多项式的基本运算

实验时间 指导单位 指导教师

2016 年 3 月 10 日

计算机科学与技术系

骆健

学生姓名 学院(系)

管理学院

班级学号 专 业

信息管理与信息系统

实习题名:线性表的基本运算

班级 姓名 学号 日期2016.03.10 一、 问题描述 深入理解线性表数据结构,熟练掌握顺序表的各种基本操作。在顺序表类SeqList中增加成员函数void Reverse()，实现顺序表的逆置；在顺序表类SeqList中增加成员函数bool DeleteX(const T &x),删除表中所有元素值等于x元素。若表中存在这样的元素，则删除之，且函数返回true，否则函数返回false。

二、 概要设计

文件Inverse.cpp中定义了Linearlist类, SeqList类继承Linearlist类。在顺序表类SeqList中通过函数void Reverse()实现顺序表的逆置，通过函数bool DeleteX(const T &x),删除表中所有元素值等于x元素。

三、 详细设计

1. 类和类的层次设计

程序使用了两个类, 线性表Linearlist类和顺序表SeqList类和一个主函数mian。Linearlist类里包括常见的线性表运算,在类SeqList里面新增成员函数void Reverse()和bool DeleteX(const T &x)。

T Linearlist #int n +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; T SeqList -int maxLength; -T *elements; +IsEmpty() const; +Length() const; +Find(int i,T& x) const; +Search(T x) const; +Insert(int i,T x); +Delete(int i); +Update(int i,T x); +Output(ostream& out) const; +Reverse(); +DeleteX(const T& x); 2. 核心算法

顺序表SeqList类中,私有段封装了两个私有数据成员maxLength和elements,公有段封装了构造、析构、查找、删除、逆置等函数。实现要求的主要操作通过void Reverse()和bool DeleteX(const T &x)实现，void Reverse()通过前后互换实现逆置， bool DeleteX(const T &x)使用hash数组标记需要删除的元素，然后将放在elements里面的数据删除。两个函数的流程图如下。

临时变量存放数据 int i=0 Ni<=n/2 Y前后互换逆置 i++ void Reverse()

int tmp=n,i i=0 N i

bool DeleteX(const T &x)

3. 算法分析

线性表的基本运算程序的主要算法的算法时间复杂度和空间复杂度为O（n）

四、程序代码

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; }

五、测试和调试

1. 测试用例和结果

1) 输入顺序表的长度为10

2) 输入10个元素分别为1,3,7,8,4,6,24,15,22，9

3) 输出创建好的表：1,3,7,8,4,6,24,15,22,9

以及逆置后的表：9,22,15,24,6,4,8,7,3,1

4) 输入要删除的数据22，接着输出删除该数据后的

5) 重新输入需要删除的数据4,24，如图所示只删除了4

2. 结果分析

1) 程序能够正确的实现顺序表的逆置以及删除特定值的元素 2) 由测试结果来看，数据无法实现两个数的同时删除，还有改进的空

间

六、实验小结

通过这次课程设计，使我对数据结构有了初步的清晰了解，增强了程序的编写能力，在程序的运行与调试过程中出现了很多错误，通过反复地复习课本上的相关知识，不停地修改与调试，终于完成了这段程序。在调试过程中，我认识到了数据结构的灵活性与严谨性，同一个功能可以由不同的语句来实现，但编写程序时要特别注意细节方面的问题，因为一个小小的疏忽就能导致整个程序不能运行。我也认识到了自己的薄弱之处，如对c++和链表知识不够熟悉，在以后的学习中我们要集中精力、端正态度，争取把知识学得更扎实、更全面。

实习题名:多项式的基本运算 班级 姓名 学号 日期2016.03.10 一、 问题描述 设计带表头结点的单链表表示的多项式类，在该类上定义和实现教材2.4节中程序2.7的多项式类上的各个运算，在该类上增加成员函数void

PolyMul(Polynominal & r)，并重载*运算符，实现菜单驱动的main函数，测试多项式类上各个运算：输入多项式，显示多项式，多项式加法和乘法运算。

二、 概要设计

文件polynominal.cpp中定义了两个类,分别是多项式结点类Term和多项式类polynominal。

三、 详细设计

1. 类和类的层次结构

为实现多项式的算术运算,在polynominal类之前定义了Term类。

Term -int coef; -int exp; -Term* link; +Term(int c, int e); +Term(int c, int e, Term* nxt); +Term* InsertAfter(int c, int e); Polynomina -Term* theList +void AddTerms(istream& in); +void Output(ostream& out)const; +void PolyAdd(Polynominal& r); +void PolyMul(Polynominal& r); 2. 核心算法

项结点类中定义了三个私有数据域分别为coef、指数exp和指向下一个项结点的指针域link，多项式polynominal被声明成结点类的友元类。多项式polynominal其中包括了三个公有成员函数: AddTerms,Output,PolyAdd, PolyMul,分别实现多项式的输入、输出、相加、相乘。PolyAdd(Polynominal& r)函数和PolyMul(Polynominal& r)函数的流程图如下。

q1指向表头结点 p指向第一个要处理的结点 N p!=NULL&&p->exp>Y N p->expexp Y q1=q N p->exp==q->exY q->coef=q->coef+p->coeN q->coef==0 Y q1=q 重置q指针 以p的系数和指数生成新结点插入q1后 p=p->link PolyAdd(Polynominal& r)

定义相乘后的数据 N p->exp>=0 Y 存储某段相乘后的数据 N q->exp=0 Y 生成新节点插入n后 将temp加到result上 q指向表头结点的后继结点 N q!=NULL Y 删除原对象的所有数据 将result加到当前对象上 PolyMul(Polynominal& r)

3. 算法分析

多项式的加法和乘法算术运算程序的主要算法的时间复杂程度和和空间复杂程度为O（n）。

四、 程序代码

void Polynominal::PolyAdd(Polynominal& r) {

Term *q, *q1 = theList, *p; //q1指向表头结点

p = r.theList->link; //p指向第一个要处理的结点 q = q1->link; //q1是q的前驱，p和q就指向两个当前进行比较的项

while (p != NULL && p->exp >= 0)//对r的单循环链表遍历，知道全部结点都处理完 {

while (p->exp < q->exp) //跳过q->exp大的项 {

q1 = q; q = q->link; }

if (p->exp == q->exp) //当指数相等时，系数相加 {

q->coef = q->coef + p->coef;

if (q->coef == 0) //若相加后系数为0，则删除q {

q1->link = q->link; delete(q);

q = q1->link; //重置q指针 } else {

q1 = q; //若相加后系数不为0，则移动q1和q q = q->link; } }

else //p>exp>q->exp的情况

q1 = q1->InsertAfter(p->coef, p->exp); //以p的系数和指数生成新结点，插入q1后

p = p->link; } }

void Polynominal::PolyMul(Polynominal& r) {

Polynominal result; //定义相乘后的数据 Term *n = result.theList; //n指向result的头结点

n = n->InsertAfter(0, 0); //在result的头结点后插入新结点，系数指数均为0

Term *p = r.theList->link; //p指向第一个要处理的结点 while(p->exp >= 0) //对r的单循环链表遍历

{

Polynominal tmp; //存储某段相乘后的数据 Term *m = tmp.theList; //m指向tmp的头结点

Term *q = theList->link; //q指向表头结点的后继结点

while(q->exp >= 0) //对当前对象的单循环环链表遍历 {

m = m->InsertAfter((p->coef)*(q->coef), (p->exp) + (q->exp)); //生成新结点插入n后

q = q->link; }

result.PolyAdd(tmp); //将temp加到result上 p = p->link; }

Term *q = theList->link; //q指向表头结点的后继结点 while(q != NULL) //删除原对象的所有数据 {

theList->link = q->link; delete q;

q = theList->link; }

q = theList;

q = q->InsertAfter(0, 0);

PolyAdd(result); //将result加到当前对象上 }

五、 测试和调试

1. 测试用例和结果

1) 选择1,计算多项式相加

2) 分别输入系数和项数3 2,4 6,9 7,如图所示

3) 得到相加的多项式如图

4) 选择2,计算多项式相乘

5) 输入系数和项数4 2,6 3,,得到多项式一,如图

6) 再次输入系数和项数7 3,得到多项式二以及多项一和多项式二的乘

积

2. 结果分析

1) 程序能够正确实现多项式的相加以及相乘

2) 但是程序无法实现不能加法乘法混用，下一步改进方向是实现加法

乘法混用，是计算更加简便

六、 实习小结

这个实验的重难点都在于正确灵活使用，大部分代码在书上都有提供，真正的操作重点在于理解这些代码的意义和使用方法。通过这次课程设计，使我对数据结构有了初步的清晰了解，增强了程序的编写能力，巩固了专业知识，对程序的模块化观念也又模糊逐渐变的清晰了。在程序的运行与调试过程中出现了很多错误，通过反复地复习课本上的相关知识，不停地修改与调试，终于完成了这段程序。在调试过程中，我认识到了数据结构的灵活性与严谨性，同一个功能可以由不同的语句来实现，但编写程序时要特别注意细节方面的问题，因为一个小小的疏忽就能导致整个程序不能运行。我也认识到了自己的薄弱之处，如对c++和链表知识不够熟悉，在以后的学习中我们要集中精力、端正态度，争取把知识学得更扎实、

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

附录：

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

}

cout << \ A.Output(cout); A.Reverse();

cout << \ A.Output(cout);

cout << \ cin >> del_data;

if(A.DeleteX(del_data) == true) {

cout << \ A.Output(cout); } else

cout << \ return 0; }

2. 多项式的基本运算

#include

class Term {

public:

Term(int c, int e);

Term(int c, int e, Term* nxt); Term* InsertAfter(int c, int e); private:

int coef; int exp; Term* link;

friend ostream& operator<<(ostream &, const Term &); friend class Polynominal; };

Term::Term(int c, int e) :coef(c), exp(e) {

link = 0; }

Term::Term(int c, int e, Term *nxt) : coef(c), exp(e) {

link = nxt; }

Term* Term::InsertAfter(int c, int e) {

link = new Term(c, e, link); return link; }

ostream& operator<<(ostream& out, const Term& val) {

if (val.coef==0) return out;

out << val.coef; switch (val.exp) {

case 0:break;

case 1:out << \

default:out << \ }

return out; }

class Polynominal {

public:

Polynominal(); ~Polynominal();

void AddTerms(istream& in); void Output(ostream& out)const; void PolyAdd(Polynominal& r); void PolyMul(Polynominal& r); private:

Term* theList;

friend ostream& operator<<(ostream &, const Polynominal &); friend istream& operator>>(istream&, Polynominal &);

friend Polynominal& operator+(Polynominal &, Polynominal &); friend Polynominal& operator*(Polynominal &, Polynominal &); };

Polynominal::Polynominal() {

theList = new Term(0, -1); //头结点

theList->link = NULL; //单链表尾结点指针域为空 }

Polynominal::~Polynominal() {

Term* p = theList->link; while (p != NULL) {

theList->link = p->link; delete p;

p = theList->link; }

delete theList; }

void Polynominal::AddTerms(istream & in) {

Term* q = theList; int c, e; for (;;) {

cout << \ cin >> c >> e;

q = q->InsertAfter(c, e); if (0 > e) break; } }

void Polynominal::Output(ostream& out)const {

int first = 1;

Term *p = theList->link;

for (; p != NULL && p->exp >= 0; p = p->link) {

if (!first && (p->coef>0)) out << \ first = 0; out << *p; }

cout << endl; }

void Polynominal::PolyAdd(Polynominal& r) {

Term *q, *q1 = theList, *p; //q1指向表头结点

p = r.theList->link; //p指向第一个要处理的结点 q = q1->link; //q1是q的前驱，p和q就指向两个当前进行比较的项

while (p != NULL && p->exp >= 0)//对r的单循环链表遍历，知道全部结点都处理完 {

while (p->exp < q->exp) //跳过q->exp大的项 {

q1 = q; q = q->link; }

if (p->exp == q->exp) //当指数相等时，系数相加 {

q->coef = q->coef + p->coef;

if (q->coef == 0) //若相加后系数为0，则删除q {

q1->link = q->link; delete(q);

q = q1->link; //重置q指针 } else {

q1 = q; //若相加后系数不为0，则移动q1和q q = q->link; } }

else //p>exp>q->exp的情况

q1 = q1->InsertAfter(p->coef, p->exp); //以p的系数和指数生成新结点，插入q1后

p = p->link; } }

void Polynominal::PolyMul(Polynominal& r) {

Polynominal result; //定义相乘后的数据 Term *n = result.theList; //n指向result的头结点

n = n->InsertAfter(0, 0); //在result的头结点后插入新结点，系数指数均为0

Term *p = r.theList->link; //p指向第一个要处理的结点 while(p->exp >= 0) //对r的单循环链表遍历 {

Polynominal tmp; //存储某段相乘后的数据 Term *m = tmp.theList; //m指向tmp的头结点

Term *q = theList->link; //q指向表头结点的后继结点

while(q->exp >= 0) //对当前对象的单循环环链表遍历 {

m = m->InsertAfter((p->coef)*(q->coef), (p->exp) + (q->exp)); //生成新结点插入n后

q = q->link; }

result.PolyAdd(tmp); //将temp加到result上 p = p->link; }

Term *q = theList->link; //q指向表头结点的后继结点 while(q != NULL) //删除原对象的所有数据 {

theList->link = q->link; delete q;

q = theList->link; }

q = theList;

q = q->InsertAfter(0, 0);

PolyAdd(result); //将result加到当前对象上 }

ostream &operator<<(ostream& out, const Polynominal& x) {

x.Output(out); return out; }

istream &operator>>(istream& in, Polynominal &x) {

x.AddTerms(in); return in; }

Polynominal & operator + (Polynominal &a, Polynominal &b) {

a.PolyAdd(b); return a; }

Polynominal & operator * (Polynominal &a, Polynominal &b) {

a.PolyMul(b); return a; }

int main() {

int choose;

cout << \ 1.add 2.mul\ cin >> choose; Polynominal p, q; switch (choose) {

case 1:

cin >> p; cout << p; cin >> q; cout << q; q = q + p; break; case 2:

cin >> p; cout << p; cin >> q; cout << q; q = q * p; break; }

cout << q; return 0; }

int main() {

int choose;

cout << \ 1.add 2.mul\ cin >> choose; Polynominal p, q; switch (choose) {

case 1:

cin >> p; cout << p; cin >> q; cout << q; q = q + p; break; case 2:

cin >> p; cout << p; cin >> q; cout << q; q = q * p; break; }

cout << q; return 0; }

本文来源：https://www.bwwdw.com/article/0jr6.html