线性表的顺序储存结构.doc

重庆交通大学
《算法与数据结构》课程
实验报告
班 级:计算机科学与技术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; //最大可容纳表项的项数
int last; //当前已存表项的最后位置（从0开始）
void reSize（int newSize）; //改变data数组空间大小
public:
SeqList(int sz = defaultSize）; //构造函数
SeqList（SeqList<T〉& L）； //复制构造函数
~SeqList（）｛delete[] data；} //析构函数
int Size（)const｛return maxSize;} //计算表最大可容纳表项个数
int Length（）const｛return last+1；} //计算表长度
int search(T＆ x）const; //搜索x在表中位置，函数返回表项序号
int Locate(int i）const; //定位第i个表项，函数返回表项序号
bool getData（int i,T& x）const //去第i个表项的值
｛if（i>0＆＆i<=last+1)｛x=data［i-1]；return true;}else return false;}
void setData(int i，T& x） //用x修改第i个表项的值
{if(i>0&＆i〈=last+1) data[i-1］=x；｝
bool Insert(int i，T& x)； //插入x在第i个表项之后
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；｝ //判表满否,满则返回true；否则返回false
void input（）; //输入
void output()； //输出
SeqList<T>operator=（SeqList<T>& L)； //表整体赋值
void ofile()； //存储在文件中
void ifile(); //读取文件并显示
2、 部分成员函数
//搜索函数：在表中顺序搜索与给定值x匹配的表项，找到则函数返回该表项是第几个元素
//否则函数返回0,表示搜索失败
template<class T〉
int SeqList〈T>：:search（T＆ x）const{
for(int i = 0;i 〈= last; i++)
if(data［i］ == x） return i+1； //顺序搜索
return 0； //搜索失败
}
//定位函数：
template〈class T〉
int SeqList〈T>：：Locate(int i）const｛
if(i 〉= i＆&i <= last+1) return i ；
else return 0；
}
//插入函数
//将新元素x插入到表中第i（i>=0＆&i〈=last+1）个表项之后，函数返回插入成功的信息，若
//插入成功，则返回true；否则返回false.i=0是虚拟的,实际上是插入的第1个元素位置
template<class T〉
bool SeqList〈T>::Insert(int i,T& x）{
if(last == maxSize—1) return false; //表满，不能插入
if（i〈0 ｜｜ i>last+1) return false; //参数i不合理，不能插入
for（int j = last ;j >=i；j—-) //依次后移，空出第i号位置
data[j+1］ = data［j］;
data[i] = x; //插入
last++； //最后位置+1
return true; //插入成功
｝
//删除函数
//从表中删除第i个表项，通过应用型参数x返回删除的元素值,函数
//返回删除成功的信息,如删除成功则返回true,否则返回false
template〈class T〉
bool SeqList<T>:：Remove(int i，T＆ x){
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；
｝
//输入函数
//从标准输入逐个数据输入，建立顺序表
template<class T>
void SeqList<T〉:：input（）｛
cout<<”开始建立顺序表,请输入表中的元素个数:"；
while（1）｛
cin>>last；
if(last<=maxSize-1） break;
cout〈<"表元素个数有误，范围不能超过"〈〈maxSize〈<"：”;
}
for（int i = 0;i 〈 last;i++）｛
cout〈〈”＃"<〈i+1<<”：";
cin〉〉data［i］;
}
}
//输出函数
template<class T〉
void SeqList<T〉::output(）｛
cout〈<”顺序表当前元素最后的位置为：”〈<last〈<endl；
for（int i = 0；i 〈 last；i++）
cout<〈"＃"〈<i+1<<"：”<<data[i]<<endl；
}
//存储在文件中
template〈class T〉
void SeqList〈T>：：ofile(){
ofstream f1(”Test1.txt”,ios：：out）;
if（！f1）{cout〈<”存储文件失败！”<〈endl;exit(1）;}
for（int i = 1；i < last+1;i++)
f1.write（（char＊） &data［i—1],sizeof（data［i—1］));
cout〈<"存储成功！”〈〈endl；
f1.close（）;
｝
//读取文件并打印出文件内容
template<class T〉
void SeqList<T>：：ifile(）｛
ifstream f2("Test1.txt"，ios::binary）；
if（！f2）{cout〈〈”打开文件失败!”<〈endl；exit(1);}
cout<〈”文件内容如下：”〈〈endl；
for(int i = 1;!f2.eof();i++）{
f2.read(（char＊)＆data［i—1]，sizeof(data［i-1］)）;
}
for（int j = 1；j < i-1；j++）
cout〈<”＃"<〈j<〈"：”<<data［j-1］<<endl；
f2.close(）；
｝
㈡ 测试主函数
1、插入功能，对不同位置的插入通过修改函数Insert(int i,x)第一形参实现,位置可通过成员函数search（x）确定
case 3:{//指定元素后插入
int x，y；
cout〈<”请输入指定元素:”;cin>>x；
cout<〈”请输入要插入的元素：”;cin〉>y；
Seq。Insert(Seq。search（x),y)；
break;
}
case 4：{//指定位置插入
int i,x;
cout<〈”请输入插入的位置:”；cin>>i；
cout〈〈”请输入要插入的元素:”;cin>>x;
Seq.Insert（i，x）;
break;
｝
case 5:{//按内容删除指定元素
int i，x;
cout〈<”请输入要删除的元素内容:";cin〉〉x;
i = Seq。search（x）; //指定元素位置
if（Seq.Remove（i,x）） cout〈<”删除成功！"〈〈endl；
else cout<<"删除失败！”〈〈endl；
break;
｝
2、删除功能,指定序号删除直接调用Remove(i,x）即可实现，指定表项的内容删除可通过search(x)函数返回得到该表项的序号，再通过Remove（i，x)实现
case 5：{//按内容删除指定元素
int i，x；
cout〈〈"请输入要删除的元素内容：”；cin>〉x；
i = Seq。search（x); //指定元素位置
if（Seq。Remove(i,x）） cout〈〈”删除成功！”<〈endl;
else cout<〈"删除失败!"<〈endl；
break;
}
case 6:{//按位置删除指定元素
int i，x;
cout<〈”请输入要删除的元素序号:”;cin>>i；
if（Seq.Remove（i,x）) cout〈〈”删除成功，删除的元素 是:”<<x〈<endl;
else cout<<"删除失败！”<〈endl;
break；
｝
3、显示功能，直接调用成员函数output（）即可实现。
4、查找功能,指定序号的查找通过成员函数getData（i,x)，其中的应用型形参可以返回该序号表项的值；指定表项查找通过成员函数search(x)即可实现
case 8：｛//查找指定序号的元素
int i，x；
cout〈<"请输入要查找元素的序号:”；cin〉〉i；
if（Seq.getData（i,x）) cout<〈”第"<〈i<〈"个元素的值 是:"<<x〈〈endl;
else cout〈〈"查找失败！"〈<endl;
break；
｝
case 9：｛//查找指定内容的元素
int x；
cout〈〈”请输入要查找元素的内容:”;cin〉〉x；
if（Seq。search（x)） cout〈〈x<<"在 "<〈Seq。search（x)〈〈" 位！ "〈〈endl;
else cout〈<”查找失败！"<〈endl;
break；
｝
5、修改功能，调用成员函数setData(i,x)即可实现
case 10：｛//修改指定位置元素的数据
int i，x，y；
cout<<"请输入要修改元素的序号:"；cin>〉i；
cout〈〈”请输入要替代的元素数据:”;cin〉〉x;
Seq。setData(i,x）；Seq.getData（i,y）； //用y判定修改成功与否
if（y == x) cout<<"修改成功！"<〈endl;
else cout<<”修改失败！"〈〈endl；
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、编写过程中应当注意细节部分,避免大量无效率的调试时间。