实验二 线性表的顺序存储

实验报告二 线性表的顺序存储

班级： 2010251 姓名： 李鑫 学号： 20103277 专业： 信息安全

一、 实验目的：

（1） 掌握顺序表的基本操作的实现方法。

（2） 应用顺序表的基本算法实现集合A=AUB算法。

（3） 应用顺序表的基本算法实现两有序顺序表的归并算法。 二、 实验内容：

1、线性表顺序存储结构的基本操作算法实现（要求采用类模板实现）

[实现提示] （同时可参见教材p5822-p60页算法、ppt）函数、类名称等可自定义，部分变量请加上学号后3位。 库函数载和常量定义：（代码） #include #include

（1）顺序表存储结构的定义(类的声明)：（代码） const int MaxSize=100;

template //定义模板类SeqList class SeqList {

public:

SeqList( ); //无参构造函数

SeqList(datatype a[ ], int n); //有参构造函数 ~SeqList(){}; //析构函数为空 int Length(); //求线性表的长度

datatype Get(int i); //按位查找，取线性表的第i个元素 int Locate(datatype item); //查找元素item

void Insert(int i, datatype item); //在第i个位置插入元素item datatype Delete(int i); //删除线性表的第i个元素 void display(); //遍历线性表，按序号依次输出各元素 int isEmpty();

int qianqu(int i,datatype item); int houji(int i,datatype item); private:

datatype data[MaxSize]; //存放数据元素的数组 int length; //线性表的长度 };

（2）初始化顺序表算法实现（不带参数的构造函数） /*

*输 入：无

*前置条件：顺序表不存在 *功 能：构建一个顺序表 *输 出：无

*后置条件：表长为0 */

实现代码：

template

SeqList:: SeqList( ) {

length=0; }

（3）顺序表的建立算法（带参数的构造函数） /*

*输 入：顺序表信息的数组形式a[],顺序表长度n *前置条件：顺序表不存在

*功 能：将数组a[]中元素建为长度为n的顺序表 *输 出：无

*后置条件：构建一个顺序表 */

实现代码：

template

SeqList:: SeqList(datatype a[], int n) {

if (n>MaxSize) throw 数组元素个数不合法 for (int i=0; i

（4）在顺序表的第i个位置前插入元素e算法 /*

*输 入：插入元素e,插入位置i *前置条件：顺序表存在，i要合法

*功 能：将元素e插入到顺序表中位置i处 *输 出：无

*后置条件：顺序表插入新元素，表长加1 */

实现代码：

template

void SeqList::Insert(int i, datatype item) {

int j;

if (length>=MaxSize) throw “溢出

if (i<1 || i>length+1) throw “i不合法！ for (j=length; j>=i; j--) data[j]=data[j-1]; data[i-1]=item; length++; }

（5）删除线性表中第i个元素算法 /*

*输 入：要删除元素位置i *前置条件：顺序表存在,i要合法

*功 能：删除顺序表中位置为i的元素 *输 出：无

*后置条件： 顺序表册除了一个元素，表长减1 */

实现代码：

template

datatype SeqList::Delete(int i) {

int item,j;

if (length==0) throw “表为空,无法删除元素! if (i<1 || i>length) throw “i不合法! item=data[i-1];//获得要删除的元素值 for (j=i; j

data[j-1]=data[j]; //注意数组下标从0记 length--; return item; }

（6）遍历线性表元素算法 /*

*输 入：无

*前置条件：顺序表存在

*功 能：顺序表遍历 *输 出：输出所有元素 *后置条件：无 */

实现代码：

template

void SeqList::display() {

for(int i=0;i

（7）获得线性表长度算法 /*

*输 入：无

*前置条件：顺序表存在 *功 能：输出顺序表长度 *输 出：顺序表长度 *后置条件：无 */

实现代码：

template

int SeqList::Length() {

return length; }

（8）在顺序线性表中查找e值，返回该元素的位序算法 /*

*输 入：查询元素值e *前置条件：顺序表存在

*功 能：按值查找值的元素并输出位置 *输 出：查询元素的位置 *后置条件：无 */

实现代码：

template

int SeqList::Locate(datatype item) {

for (int i=0; i

//下标为i的元素等于item，返回其序号i+1 return 0; //查找失败 }

（9）获得顺序线性表第i个元素的值 /*

*输 入：查询元素位置i

*前置条件：顺序表存在，i要合法

*功 能：按位查找位置为i的元素并输出值 *输 出：查询元素的值 *后置条件：无 */

实现代码：

template

datatype SeqList::Get(int i) {

if (i<1 || i>length) throw 不合法! else return data[i-1]; }

（10）判表空算法 /*

*输 入：无 *前置条件：无

*功 能：判表是否为空

*输 出：为空返回1，不为空返回0 *后置条件：无 */

实现代码：

template

int SeqList::isEmpty() {

if(length==0) return 1; return 0; }

(11)求直接前驱结点算法 /*

*输 入：要查找的元素e，待存放前驱结点值e1 *前置条件：无