南邮数据结构实验一资料
- 格式：doc
- 大小：276.50 KB
- 文档页数：14
实 验 报 告
（2014 / 2015 学年 第 二 学期）
课程名称 数据结构
实验名称 线性表的基本运算及多项式的算术运算
实验时间 2015 年 9 月 28 日
指导单位 计算机科学与技术系
指导教师 黄海平
学生姓名 陈明阳 班级学号 Q14010119
学院(系) 贝尔英才 专 业 信息科技强化班
实 验 报 告
实验名称 线性表的基本运算及多项式的算术运算 指导教师 黄海平
实验类型 验证 实验学时 4 实验时间 9.28
一、 实验目的和要求
内容：实现顺序表和单链表的基本运算，多项式的加法和乘法算术运算。
要求：能够正确演示线性表的查找、插入、删除运算。实现多项式的加法和乘法运算操作。
二、实验环境(实验设备)
VSUAL STUDIO2015 三、实验原理及内容
LinearlistseqlistLA,LB
函数调用数据类型如下图
源码：
Linearlist.h:
#include
using namespace std;
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;
};
Seqlist.h:
#include"linearlist.h"
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;
private:
int maxLength;
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)
{
cout << "out of bounds" << endl; 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 << "out of bounds" << endl;
return false;
}
if (n == maxLength)
{
cout << "over flow" << 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 (i<0 || i>n - 1)
{
cout << "out of bounds" << endl;
return false;
}
if (!n)
{
cout << "over flow" << endl;
return false;
}
for (int j = i+1; j
n--;
return true;
}
template bool SeqList::Update(int i, T x)
{
if (i<0 || i>n - 1)
{
cout << "out of bounds" << 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;
}
源.cpp:
#include"seqlist.h"
const int SIZE = 20;
void main()
{
SeqList LA(SIZE);
int i = 0;
for (i = 0; i<5; i++) LA.Insert(i - 1, i);
LA.Insert(-1, 10);
LA.Output(cout);
}
实现在线性表LA中插入0-4然后在一开始插入10
运行截图如下： 6
多项式实验：
定义类如下
重构函数如下：
源码：
#include
using namespace std;
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 (0 == val.coef)
