线性表的顺序储存结构

重庆交通大学

《算法与数据结构》课程 实

验报告

班 级：计算机科学与技术2014级2班

实验项目名称： 线性表的顺序储存结构

实验项目性质：

实验所属课程： 算法与数据结构

实验室(中心)： B01407

指 导 教 师 ： 鲁云平

实验完成时间： 2016 年 3 月 21 日

教师评阅意见：

实验成绩： 签名： 年 月 日

一、实验目的

1、实现线性表的顺序存储结构

2、熟悉C++程序的基本结构，掌握程序中的头文件、实现文件和主文件之间的相互关系及各自的作用

3、熟悉顺序表的基本操作方式,掌握顺序表相关操作的具体实现

二、实验内容及要求

对顺序存储的线性表进行一些基本操作。主要包括：

（1）插入：操作方式为在指定元素前插入、在指定元素之后插入、在指定位置完成插入

（2）删除：操作方式可分为删除指定元素、删除指定位置的元素等，尝试实现逻辑删除操作。 （3）显示数据

（4）查找：查询指定的元素（可根据某个数据成员完成查询操作） （5）定位操作：定位指定元素的序号 （6）更新：修改指定元素的数据 （7）数据文件的读写操作等。 其它操作可根据具体需要自行补充。

要求线性表采用类的定义,数据对象的类型自行定义。

三、实验设备及软件

VC6.0

四、设计方案

㈠ 题目

线性表的顺序存储结构

㈡ 设计的主要思路

1、新建SeqList.h头文件，定义SeqList模板类

2、设计类数据成员，包括：T *data（用于存放数组）、int maxSize（最

大可容表项的项数）、int last（当前已存表项的最后位置） 3、设计类成员函数，主要包括：

int search(T& x)const;//搜索x在表中位置，函数返回表项序号 int Locate(int i)const;//定位第i个表项，函数返回表项序号 bool getData(int i,T& x)const;//去第i个表项的值

void setData(int i,T& x)//用x修改第i个表项的值 bool Insert(int i,T& x);//插入x在第i个表项之后

bool Remove(int i,T& x); //删除第i个表项，通过x返回表项的值 bool IsEmpty();//判表空否，空则返回true；否则返回false bool IsFull();//判表满否，满则返回true；否则返回false void input(); //输入 void output();//输出 void ofile();/存储在文件中 void ifile();//读取文件并显示 ㈢ 主要功能

1、建立新表

2、对表进行插入（指定元素前、后以及指定位置插入）、删除（指定

元素删除及指定位置删除）、修改等操作

3、显示当前操作表的全部内容 4、存储在文件中 5、从文件中读取表

五、主要代码

㈠SeqList.h中的主要代码： 1、类成员声明部分： protected:

T *data;

//存放数组

//最大可容纳表项的项

int maxSize;

数 小 public: 值 后

bool Remove(int i,T& x);

//删除第i个表项，通过//判表空否，空则返回//判表满否，满则返回//输入

//输出

//表整体赋值

x返回表项的值

bool IsEmpty(){return (last == -1)?true:false;} true；否则返回false

bool IsFull(){return (last == maxSize-1)?true:false;} void input(); void output(); void ofile(); void ifile();

true；否则返回false

{if(i>0&&i<=last+1) data[i-1]=x;} bool Insert(int i,T& x);

//插入x在第i个表项之

SeqList(int sz = defaultSize); SeqList(SeqList& L); ~SeqList(){delete[] data;}

//构造函数

//复制构造函数 //析构函数

//计算表最大可容纳表//计算表长度

//搜索x在表中位

int last;

//当前已存表项的最后//改变data数组空间大

位置（从0开始）

void reSize(int newSize);

int Size()const{return maxSize;} int Length()const{return last+1;} int search(T& x)const; int Locate(int i)const;

项个数

置，函数返回表项序号

//定位第i个表项，函数//去第i个表项的值 //用x修改第i个表项的

返回表项序号

bool getData(int i,T& x)const void setData(int i,T& x)

{if(i>0&&i<=last+1){x=data[i-1];return true;}else return false;}

SeqListoperator=(SeqList& L);

//存储在文件中 //读取文件并显示

2、部分成员函数

//搜索函数：在表中顺序搜索与给定值x匹配的表项，找到则函数返回该表项是第几个元素

//否则函数返回0，表示搜索失败 template

int SeqList::search(T& x)const{ }

//定位函数： template

int SeqList::Locate(int i)const{ }

//插入函数

//将新元素x插入到表中第i（i>=0&&i<=last+1）个表项之后，函数返回插入成功的信息，若

//插入成功，则返回true；否则返回false.i=0是虚拟的，实际上是插入的第1个元素位置

template

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

//删除函数

//从表中删除第i个表项，通过应用型参数x返回删除的元素值，函数 //返回删除成功的信息，如删除成功则返回true，否则返回false

if(last == maxSize-1) return false; if(i<0 || i>last+1) return false; for(int j = last ;j >=i;j--)

data[j+1] = data[j];

//插入

//最后位置+1 //插入成功

data[i] = x; last++; return true;

//表满，不能插入 //参数i不合理，不能插入 //依次后移，空出第i号位置

if(i >= i&&i <= last+1) return i ; else return 0;

for(int i = 0;i <= last; i++)

if(data[i] == x) return i+1;

//顺序搜索 //搜索失败

return 0;

template

bool SeqList::Remove(int i,T& x){ }

//输入函数

//从标准输入逐个数据输入，建立顺序表 template void SeqList::input(){ }

//输出函数 template void SeqList::output(){ }

//存储在文件中 template

cout<<\顺序表当前元素最后的位置为：\for(int i = 0;i < last;i++)

cout<<\

cout<<\开始建立顺序表，请输入表中的元素个数:\while(1){ }

for(int i = 0;i < last;i++){ }

cout<<\cin>>data[i];

cin>>last;

if(last<=maxSize-1) break;

cout<<\表元素个数有误，范围不能超过\if(last == -1 )return false; if(i<1 || i>last+1)return false; x = data[i-1];

for(int j = i;j <= last;j++)

data[j-1] = data[j]; last--; return true;

void SeqList::ofile(){ }

//读取文件并打印出文件内容 template void SeqList::ifile(){ }

㈡ 测试主函数

1、插入功能，对不同位置的插入通过修改函数Insert(int i,x)第一形参实现,位置可通过成员函数search(x)确定

case 3:{//指定元素后插入

int x,y;

cout<<\请输入指定元素:\cout<<\请输入要插入的元素:\Seq.Insert(Seq.search(x),y); break;

ifstream f2(\

if(!f2){cout<<\打开文件失败！\cout<<\文件内容如下：\for(int i = 1;!f2.eof();i++){ }

for(int j = 1;j < i-1;j++)

cout<<\f2.close();

f2.read((char*)&data[i-1],sizeof(data[i-1])); ofstream f1(\

if(!f1){cout<<\存储文件失败！\for(int i = 1;i < last+1;i++)

f1.write((char*) &data[i-1],sizeof(data[i-1])); cout<<\存储成功！\f1.close();

}

int i,x;

case 4:{//指定位置插入

cout<<\请输入插入的位置:\cout<<\请输入要插入的元素:\Seq.Insert(i,x); break;

}

int i,x;

cout<<\请输入要删除的元素内容:\i = Seq.search(x);

//指定元素位置

if(Seq.Remove(i,x)) cout<<\删除成功！\else cout<<\删除失败！\break;

case 5:{//按内容删除指定元素

}

2、删除功能，指定序号删除直接调用Remove(i,x)即可实现，指定表项的内容删除可通过search(x)函数返回得到该表项的序号，再通过Remove(i,x)实现

case 5:{//按内容删除指定元素

int i,x;

cout<<\请输入要删除的元素内容:\i = Seq.search(x);

//指定元素位置

if(Seq.Remove(i,x)) cout<<\删除成功！\else cout<<\删除失败！\break;

}

int i,x;

cout<<\请输入要删除的元素序号:\if(Seq.Remove(i,x)) cout<<\删除成功，删除的元素 是:\

else cout<<\删除失败！\break;

case 6:{//按位置删除指定元素

}

3、显示功能，直接调用成员函数output()即可实现。

4、查找功能，指定序号的查找通过成员函数getData(i,x)，其中的应用型

形参可以返回该序号表项的值；指定表项查找通过成员函数search(x)即可实现

case 8:{//查找指定序号的元素

int i,x;

cout<<\请输入要查找元素的序号:\if(Seq.getData(i,x)) cout<<\第\个元素的值 else cout<<\查找失败！\break;

是:\

}

case 9:{//查找指定内容的元素

int x;

cout<<\请输入要查找元素的内容:\

if(Seq.search(x)) cout<

else cout<<\查找失败！\break;

}

5、修改功能，调用成员函数setData(i,x)即可实现 case 10:{//修改指定位置元素的数据

}

int i,x,y;

cout<<\请输入要修改元素的序号:\cout<<\请输入要替代的元素数据:\

Seq.setData(i,x);Seq.getData(i,y); //用y判定修改成功与否 if(y == x) cout<<\修改成功！\else cout<<\修改失败！\break;

6、存储与读取文件，调用成员函数ofile()与ifile()即可 case 11:{//存储在文件中

}

Seq.ofile(); break;

case 12:{//读取存储的文件

}

Seq.ifile(); break;

六、测试结果及说明

1、新建表及显示功能

设置值：sz=5，#1=7，#2=4，#3=1，#4=5，#5=6

2、插入功能 在指定元素前插入 指定元素x=4，插入值y=3

在指定元素后插入，指定元素x=5，插入值2，结果如左图 在指定位置插入，位置i=4，插入值9，结果如右图

3、删除功能

按内容删除，指定删除x=1，结果如左图 按序号删除，指定序号i=2，结果如右图 4、查找功能

查找指定序号的元素，指定序号i=5，结果如左图 查找指定元素的序号，指定元素x=2，结果如右图 5、修改功能

指定元素x=9，修改为y=1

6、存储与读取

七、实验体会

1、写插入删除等操作的代码时注意指针的位置一定要仔细对应，否则会出现节点错位、数据丢失等错误，这要求在我们在写代码尽量细心。

2、线性表的插入、删除操作前后都要进行非法位置的剔除，如删除一个节点应该把之后的节点一一向前移位。

3、插入、删除等操作应该有返回值反馈，以防未知错误。

4、指针在方便算法的同时也可能导致大量的错误，所以使用指针时应该严谨的设计算法，以免造成后期大量的修改工作。

5、编写过程中应当注意细节部分，避免大量无效率的调试时间。

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