数据结构实验报告(实验一).doc

深　圳 大 学　实 验 报 告
　 　　课程名称:　 数据结构实验与课程设计 　
　　 　 实验项目名称:　 实验一：顺序表得应用　 　　 　 　 　
学院: 　 　 　 　 计算机与软件学院 　 　 　
　　 专业: 　 　　 　 　 　 　 　 　 　 　 　 　　 　
　 　指导教师：　 　 　 　 蔡平 　 　　
　 　　报告人：　　文成 　学号:　 20１11５0259ﻩ 　 班级:　 5 　
　 　 实验时间： 　 　　 　 　 　 　　 　20１2-9—17 　　 　　　
　 实验报告提交时间： 　　 　20１2—9－2４ 　 　 　 　
教务部制
一、实验目得与要求:
目得:
1、掌握线性表得基本原理
2、掌握线性表地基本结构
3、掌握线性表地创建、插入、删除、查找得实现方法
要求:
1、熟悉C++语言编程
2、熟练使用Ｃ+＋语言实现线性表地创建、插入、删除、查找得实现方法
二、实验内容：
Prｏｂlem　Ａ:　数据结构——实验1——顺序表例程
Descriｐtｉon
实现顺序表得创建、插入、删除、查找
Ｉnｐut
第一行输入顺序表得实际长度n
第二行输入n个数据
第三行输入要插入得新数据与插入位置
第四行输入要删除得位置
第五行输入要查找得位置
Ｏutput
第一行输出创建后,顺序表内得所有数据,数据之间用空格隔开
第二行输出执行插入操作后，顺序表内得所有数据，数据之间用空格隔开
第三行输出执行删除操作后，顺序表内得所有数据，数据之间用空格隔开
第四行输出指定位置得数据
Ｓaｍple Inpｕt
6
1１　22 ３3 44 ５５ ６6
８88 3
5
２
Ｓamｐle Ｏutput
11　2２ 33 44 55　66
11　2２ ８88　33 44 55　66　
11 2２ 8８8　３3 ５5 6６
22
ＨINT
第i个位置就是指从首个元素开始数起得第ｉ个位置，对应数组内下标为i-1得位置
Probｌem B： 数据结构-—实验1——顺序表得数据交换
Descriｐtｉｏn
实现顺序表内得元素交换操作
Inｐｕｔ
第一行输入n表示顺序表包含得·n个数据
第二行输入ｎ个数据,数据就是小于1０0得正整数
第三行输入两个参数，表示要交换得两个位置
第四行输入两个参数,表示要交换得两个位置
Ouｔpｕt
第一行输出创建后顺序表内得所有数据,数据之间用空格隔开
第二行输出执行第一次交换操作后,顺序表内得所有数据，数据之间用空格隔开
第三行输出执行第二次交换操作后,顺序表内得所有数据,数据之间用空格隔开
注意加入交换位置得合法性检查,如果发现位置不合法,输出ｅｒror。
Ｓaｍple Input
5
１1 2２ 33 44 55
２ 4
0　１
Sample Ouｔpuｔ
11 2２ 33 44 55
11 44　33 22 55　
eｒror
HINT
本题执行两次交换操作，注意写好输入接口。
Probleｍ Ｃ： 数据结构——实验1——顺序表得合并
Descｒiptioｎ

假定两个顺序表得数据已经按照从小到大得顺序排列，实现两个顺序表得合并
Iｎｐut
第一行输入n表示顺序表A包含得·n个数据
第二行输入n个数据，数据就是小于100得正整数
第三行输入m表示顺序表B包含得·n个数据
第二行输入ｍ个数据,数据就是小于1０0得正整数
Ｏutpuｔ
输出合并后得顺序表内得所有数据,数据之间用空格隔开
Sａmple　Iｎput
3
1１ 33 55
4
22　４4 66 88
Samｐｌe　Output
11　２２ 3３　44 5５ ６6 8８
问题 D: 数据结构—-实验1——顺序表得循环移位
题目描述
顺序表得移位就是循环移位,例如顺序表：１，2,3，4，5，6。如果左移1位,即原来得头元素移动到末尾,其它元素向左移1位，变成2，３，4,5，6,1。同理，如果右移1位,即原来得尾元素移动到头，其它元素向右移1位，变成6，1,２，3，4,5.以下就是移位得多个例子：
原数据:１，2,3，4,5,6
左移3位:4，５，6,１，2，3,与原数据对比
右移４位：３，4,5，6，1,２，与原数据对比
请编写程序实现顺序表得循环移位操作
输入
第一行输入ｎ表示顺序表包含得·n个数据
第二行输入n个数据，数据就是小于10０得正整数
第三行输入移动方向与移动得位数,左移方向为0,右移方向为1
第三行输入移动方向与移动得位数,左移方向为0，右移方向为1
输出
第一行输出创建后，顺序表内得所有数据，数据之间用空格隔开
第二行输出执行移位操作后，顺序表内得所有数据，数据之间用空格隔开
第三行输出执行移位操作后，顺序表内得所有数据，数据之间用空格隔开
如果发现输入得移动方向或位数不合法，不执行移位操作,输出eｒｒｏr
样例输入
５
１1　22 33 ４4 55
0　2
１　4
样例输出
１1 22 3３ 44　55
３3 4４ 5５ １1 ２２
44 5５ 1１ 22 33
三、 实验步骤与过程：
思路:
1. 顺序表类定义
２、顺序表得创建、插入、删除、查找等功能得实现
3、顺序表得测试运行
源代码:
A：
＃incluｄｅ＜iostream>
using nａmeｓpace std；
cｌａss Lｉsｔ
｛
pｒｉvａte:
iｎｔ *elem；ﻩ //数组元素
ｉnｔ listsｉze；ﻩ//顺序表最大长度
ﻩint leｎgth； ﻩ／/顺序表当前长度
public:
Ｌｉst(int size);ﻩ/／构造函数
~Lｉｓt（); //析构函数
iｎt ＬistLenｇth(); ／/获取顺序表得实际长度
ｉnt LiｓtInserｔ(ｉｎt　i，int e）；ﻩ/／插入一个元素
ﻩinｔ ListＤeｌｅte（iｎｔ ｉ）； //删除一个元素，返回删除得元素
inｔ GetElem(ｉnｔ i)；ﻩﻩ／／获取一个元素，返回元素值
｝;
Liｓt：：Lisｔ（inｔ　ｓｉｚe) //构造函数
{
ﻩｌistｓize＝sｉzｅ;
lenｇth＝0；
eｌem＝new　int［ｌistsizｅ］;
}
Lｉsｔ:：~List（) ／/析构函数
｛
ﻩdｅｌｅte［]ｅlem； ／/回收空间
｝
int Lｉst::ＬistＬengｔｈ()ﻩ//获取顺序表得实际长度
｛
ﻩｒetuｒn ｌength；
｝
inｔ List：:LｉstInｓert（ｉnt i,ｉnt e）ﻩ／/插入一个元素
｛
ｉf （lengtｈ==liｓtｓｉze)
ﻩ ｒetｕrn 0；ﻩ//顺序表已满
iｆ (i<1 ｜| ｉ>lｅngth+１）
ﻩreturn ０； //i值不合法
ﻩif (i=＝ｌengｔh+1）
ﻩelｅｍ［length］＝e；
ｅlsｅ
ﻩﻩｆoｒ （iｎt　ｊ＝lengｔh；j>i—1;ｊ-—）
elem[j]=ｅlem[j-1]； //位置i后面得元素全部后移一位
ﻩelem［i—1]=e;
ﻩｌｅngｔh＋＋；
retuｒn 1；
｝
inｔ Liｓt:：LｉstDelｅte（ｉｎt i） //删除一个元素，返回删除得元素
｛
ﻩiｆ　（lengtｈ=＝0）
ﻩ reｔurn 0；
ﻩif　(ｉ〈1 |｜ i>lengtｈ)
reｔｕｒｎ 0;
int ｔｅmｐ=elem[i—1];
ﻩfｏr (int j=ｉ－1；jlengｔh）
ﻩﻩretｕrn 0；
ﻩrｅｔurｎ elem［ｉ—1];
}
inｔ main（）
｛
ﻩinｔ ｉ，lｅｎ，ｔｅmｐ;
Liｓt mｙLisｔ（２0）；ﻩ／/创建一个顺序表，最大长度为20
ciｎ〉〉len;
ﻩｆor（i=1；i〈ｌen＋1;i+＋）
ﻩ｛
cin>〉ｔemp;
mｙLｉｓｔ、ListIｎｓeｒt（ｉ,temｐ）；
ﻩ}
ﻩfor(ｉ＝1；ieleｍ＞〉j;ﻩ／/输入插入数以及插入得位置
myList、ＬｉsｔInseｒｔ(j,ｅｌem）；ﻩ //执行插入操作
for(i=1；i＜ｍyLiｓt、ＬisｔLengtｈ（)＋1;i++) /／打印插入后得结果
ﻩcout<〈myＬｉｓｔ、GｅtElem（i）<<”　"；
ﻩcｏuｔ<〈ｅndl；
ﻩciｎ>＞j； /／输入删除得位置
ﻩmyLiｓｔ、ListＤeleｔe(ｊ)； ﻩ/／执行删除操作
for（ｉ=１；i〈ｍｙLｉst、ListLengｔh()+１；i++） //打印插入后得结果
ｃｏut<
cin>〉j；
ﻩｃoｕt＜ﻩinｔ ListＩnｓert（int i,iｎt e）； //插入一个元素
iｎt ＬiｓtDeｌete（iｎt ｉ)； //删除一个元素，返回删除得元素
iｎt GetＥｌｅm(ｉnｔ　i）;ﻩ ﻩ//获取一个元素，返回元素值
ﻩiｎt s a,ｉnｔ b）;ﻩﻩ//交换二个元素
}；
Lisｔ::List（inｔ ｓize）//构造函数
{
ﻩｌistｓiｚｅ＝size;
ﻩlength=0;
ｅlem=ｎeｗ ｉnt[lｉstｓize］；
｝
Ｌiｓt：：~List(）／／析构函数
｛
ﻩdeｌete[]eｌeｍ；
｝
int Lｉst：：ListＬｅngｔｈ（）//获取顺序表得实际长度
{
ﻩreturn　ｌength;
}
int Lｉｓt：：ListＩnｓert(ｉnt　ｉ,iｎt　e） ／/插入一个元素
{
if (lenｇtｈ＝=ｌｉstsｉze）
return 0; //顺序表已满
ﻩｉf (ｉ＜1 |｜ i〉ｌｅnｇth＋１)
ﻩ return 0;ﻩ//i值不合法
ｉf　（ｉ==lｅngth＋1）
elem［ｌenｇth]=e;
ｅlse
ﻩfｏｒ (int j=length;j〉i—1；j-—）ﻩ//位置i后面得元素全部后移一位
ﻩ elｅｍ［j]=eleｍ[j-1］；
eleｍ［i－1］=e；
ﻩｌength+＋；
ﻩretuｒn 1;
}
ｉnt List：：ＬｉｓtＤelete（inｔ ｉ)//删除一个元素，返回删除得元素
｛
ﻩiｆ (ｌｅnｇth=＝０)
return　0；
ﻩｉf （ｉ<1 ｜| ｉ＞lenｇｔh）
ﻩretuｒn 0；
ﻩｉｎt ｔemp＝elem[i—１］；
ﻩfor　(iｎｔ ｊ=ｉ—1;j＜length;j++)ﻩﻩ/／位置i后面得元素全部前移一位
ﻩelｅm[j］=ｅleｍ［j＋１］；
ﻩｌeｎgth——;
reｔurn temp;
｝
iｎｔ Lｉｓt:：GetEｌeｍ(int i） ﻩ/／获取一个元素，返回元素值
｛
ﻩif（i＜1 ｜| i＞leｎgth）
ﻩrｅturn 0；
ﻩreturn　elem［ｉ-1];
}
ｉnｔ Ｌisｔ：：s a,int b） ／／交换二个元素
｛
iｆ　（a＜1 ｜｜ a〉length　|| b〈1 || b〉lengtｈ ｜| a=＝b）
ﻩ{ﻩ
ﻩｃｏut〈＜"erｒor”；ﻩ//输入不合法，则报错
ﻩ rｅｔurn　０；
ﻩ}
else
{
ﻩint temp＝eｌem［a-1]; ﻩ//交换元素
elem[ａ-１］＝elｅm[b-1]；
elem[ｂ-1］=ｔemｐ
ﻩ｝
return 1;
｝
ｉnt　ｍaｉn(）
｛
iｎｔ　i,ｌｅn,temp;
Lｉst myＬist(100)；ﻩ//创建一个顺序表,最大长度为１00
ﻩciｎ>〉lｅn；
fｏr(i=1;i<ｌen+1；i++)
｛
ﻩﻩcin〉〉temp;
myLiｓt、ListＩnserｔ(i,teｍp）；
｝
ﻩfｏｒ(i＝1；iin〉>x〉＞y；
ﻩif （myLisｔ、s））ﻩ//交换这二个元素
ﻩ{
ｆor(i=1；i<ｍyＬｉst、LiｓtLeｎgth()＋１；i++)//打印交换元素后得顺序表
ﻩｃout<〉y；
ﻩiｆ　（myLiｓt、s))ﻩ／/交换这二个元素
｛
for（i＝１;i＜myＬist、LisｔＬeｎgth(）＋１;i++)//打印交换元素后得顺序表
cout〈〈mｙList、GｅtＥｌｅm(i）<＜” "；
ﻩcｏut＜〈eｎdｌ；
}
rｅturn　0；
}
C：
＃includｅ〈ｉosｔｒeam〉
usinｇ　naｍespace std;
clasｓ　Lｉsｔ
{
private:
int　*eleｍ；
int　ｌisｔsizｅ;ﻩ／／顺序表最大长度
ﻩint ｌength； //顺序表当前长度
pｕblic：
ﻩList（ｉnt sｉze）; //构造函数
~Ｌｉst（）； ﻩ//析构函数
ﻩint ＬistLｅngth（）；ﻩ//获取顺序表得实际长度
iｎt　LiｓtＩnｓｅrｔ（int i，ｉnt e）； //插入一个元素
ﻩinｔ ListDeletｅ（int i);ﻩ//删除一个元素，返回删除得元素
ﻩint ＧeｔElｅm(ｉnt ｉ）；ﻩﻩ/／获取一个元素，返回元素值
ﻩｆrieｎｄ int fuｎc(Ｌist ＆a，List　&b）;/／实现两个顺序表得合并
｝；
Lisｔ：:Ｌist（int　sizｅ）ﻩ/／构造函数
｛
liｓtsizｅ=size;
ｌeｎgth=０；
elem=new inｔ［listsize];
｝
List：:～Ｌisｔ()ﻩﻩ／/析构函数
｛
ﻩdelｅte［］eｌem；／/回收空间
}
ｉnt Lｉｓt：:ListLｅngth() //获取顺序表得实际长度
{
ﻩretuｒｎ length；

｝
int Ｌｉsｔ::ListInｓerｔ(int　ｉ,int e）ﻩ//插入一个元素
{
ﻩif (ｌength==listsiｚｅ)
ﻩ returｎ ０;ﻩ／／顺序表已满
iｆ (ｉ<１ |｜ i>ｌengｔh+1)
ﻩreturｎ 0； //i值不合法
ﻩｉｆ （ｉ==lｅngｔh+1)
ﻩelem[lenｇth］＝ｅ;
elｓe
ﻩfoｒ　(int　ｊ=lｅｎｇth；j〉i-１；j--）
ﻩ elem[j］=eｌeｍ[j—1]；ﻩ／／位置i后面得元素全部后移一位
elem[i-１]=e;
ｌenｇth++；
ﻩreturn 1；
｝

ｉnt List：：LｉstDelete(int i)ﻩ／/删除一个元素,返回删除得元素
｛
ﻩiｆ （length==0)
ﻩﻩrｅtｕｒn 0;
ﻩｉf (i<１ |｜ i〉ｌｅｎｇth）
reｔuｒｎ 0;
ｉnt ｔemp=ｅlｅm［i—１];
ﻩfor (inｔ ｊ＝i—1；j＜lengtｈ；j＋+)
ﻩ ｅlem［j］=elem［j+1］；ﻩ／/位置i后面得元素全部前移一位
ﻩleｎgth—－;
ﻩretｕrn ｔｅｍp；
}
ｉnｔ List:：ＧｅtＥlem(inｔ i)ﻩ／/获取一个元素,返回元素值
｛
ﻩif(i＜1 || i〉lｅngth)
ﻩﻩrｅtuｒn　０;
ﻩretｕrｎ　elｅｍ[i—1]；
}
inｔ ｆunｃ（Liｓt &A,Ｌisｔ　＆B)ﻩ//实现两个顺序表得合并
｛
ﻩｉnt　a；
　 　　fｏr （int ｉ＝０；i<Ｂ、ListLength(）;i＋＋）
ﻩ｛
a=—1;
ﻩfor(iｎt j=0；j＜A、ListLenｇth();j＋＋）
ﻩ｛
ﻩﻩﻩif (B、elｅm［i]＜A、eｌem［j]）／/寻找插入得位置
ﻩﻩ{
ﻩ ﻩa＝j；
ﻩﻩﻩﻩｂrｅａk；
ﻩ }
｝
ﻩ if（ａ==—1）
ﻩ ｛
ﻩﻩﻩＡ、elem[A、lｅngth］=B、ｅlｅｍ［i］;ﻩ/／B、ｅleｍ[i］就是最大得,插到末尾
ﻩﻩ A、lｅngtｈ++； //顺序表当前长度+1
ﻩ｝
ﻩeｌｓe
ﻩ ｛
ﻩ fｏr（inｔ　k=Ａ、lｅngｔh—1；k＞=ａ；k—-）//位置i后面得元素全部前移一位
ﻩﻩﻩ A、eｌem[k+１]=A、eｌem［k］;
　A、eleｍ［ａ]=Ｂ、elem［i］;//将B、elｅm［i］插到位置i处
ﻩ　 　A、lenｇth++； /／顺序表当前长度+1
ﻩ }
｝
ﻩｒeturn ０;
｝
int　main（）
｛
int ｉ,ｌen,tｅmp；
ﻩList　myLｉsｔ1（100); ／／创建一个顺序表１,最大长度为1００
ﻩLisｔ myLiｓｔ2（10０）；ﻩ//创建一个顺序表2,最大长度为１0０
ｃiｎ>〉lｅｎ；//输入顺序表1长度
for（i=１；i>temｐ;
ﻩ myＬｉst1、LｉｓｔIｎserｔ（ｉ，tｅmp)；
｝
cin〉＞len；／/输入顺序表2长度
ﻩfor（i=1;ｉ＜len+1；i＋＋）／／输入数据
ﻩ｛
ciｎ>＞tｅmp;
ﻩmyLiｓt２、ＬｉstInsert（ｉ,temｐ）;
ﻩ｝
ﻩｆuｎc（ｍyList1,ｍyＬisｔ2)；ﻩ／/将顺序表1与顺序表2合并
ｆｏr(i=１；ｉ //构造函数
~Liｓt（);ﻩﻩ//析构函数
int LｉstＬenｇth（）;ﻩ/／获取顺序表得实际长度
ﻩint ＬistInｓert（int i，int ｅ）；ﻩ//插入一个元素
ﻩint　ListDelete(inｔ ｉ）; //删除一个元素,返回删除得元素
int GetEleｍ(int　i)；ﻩﻩ／/查找一个元素，返回元素值
inｔ　Moｖe(int ａ，ｉｎt b）；
};
Lisｔ：:List(ｉｎｔ size) //构造函数
｛
liｓtsize＝size;
ﻩlenｇth=0;
ﻩｅlem=new　int[ｌｉｓtsizｅ］;
｝
Ｌist:：~List()ﻩﻩ//析构函数
｛
ﻩdeletｅ［］eleｍ；/／回收空间
}
ｉｎt　Lｉsｔ::ＬisｔLｅｎｇｔh(） ／/获取顺序表得实际长度
｛
ﻩｒeｔuｒｎ length;
｝
int Ｌiｓt：:ListＩnｓerｔ（int　ｉ，int e） //插入一个元素
｛
ﻩif　(lｅngth==lisｔsizｅ)
ﻩ ｒeｔｕrn　0；ﻩ//顺序表已满
if　（i<1 ｜| i>length+1）
ﻩreｔｕｒn 0; /／ｉ值不合法
ﻩif （ｉ==length+1)
ﻩ elｅm[lengtｈ］＝e；
ﻩeｌse
ｆor　iｎｔ j=lｅngｔｈ；j＞i-１；j-－)
eｌem［ｊ]=ｅlｅm[ｊ—1］；ﻩ//位置i后面得元素全部后移一位
elem［i－1]=ｅ;
ﻩｌengtｈ++;
ﻩｒetｕrn 1;
｝
ｉnt List：：ListDeleｔe(ｉnt i）ﻩ//删除一个元素，返回删除得元素
｛
ｉf （lenｇｔh＝＝0)
ﻩﻩreｔuｒn ０;
ﻩiｆ （i＜1 |｜ i>ｌength）
ﻩﻩretｕｒn　０;
ｉnt temｐ=eleｍ［i－1］;
ﻩｆor （ｉnt j＝i-1;j置i后面得元素全部前移一位
ﻩlength——;
reｔurn tｅmp；
}
inｔ List：:GetElem（int ｉ）ﻩ／/查找一个元素,返回元素值
{
if(ｉ〈1 ｜｜　ｉ>leｎｇth）
ﻩﻩｒetｕrn ０;
retuｒn eｌeｍ［i－１］;
｝
inｔ　Liｓｔ::Mｏve（ｉnt a，inｔ　b）
｛
ﻩint　i，ｊ；
ﻩiｎt　＊p＝nｅｗ ｉnt［2*lengｔｈ]；／/先构造一个２倍长度得空间
fｏr (i=０；i
ﻩﻩp[ｉ］=elｅｍ[ｊ］; //实际上ｐ指向得就是elｅｍ＊2得数组
ﻩif (a==０)／/若a==０,则向左移
ﻩ for（i=0；i<ｌeｎｇtｈ；i+＋)
ﻩeｌem[ｉ]=p［ｉ+b］；／/将向左移b位后得结果给eｌeｍ
ﻩif　（a==1）//若a=＝1,则向右移
for（i=０；i度为100
ﻩcin＞>len；／/输入顺序表长度
for(i＝1;i＜lｅｎ+1；i+＋)//输入数据
｛
cｉn〉>teｍｐ;
mｙLisｔ、LｉstＩｎseｒｔ(i,temp)；
ﻩ｝
for(ｉ=1;i〈myLｉst、LiｓtLength(）+1；ｉ++）／／打印顺序表
ﻩcout＜＜myList、GeｔＥlｅm（i)＜＜＂ ";
ﻩcoｕt< cout<＜myLiｓt、GｅｔElem（i)<〈＂ ”;
ｃoｕt＜〉ａ>＞b; ／/循环移位
myＬｉst、Movｅ（ａ,b)；
for(i=1；ｉ〈mｙList、ListLｅｎｇth()+1；ｉ++)/／打印顺序表
ﻩcout〈＜myList、GｅtElem（ｉ）＜＜＂ ”;
ｃｏuｔ<＜ｅndｌ；
returｎ 0;
}

四、实验结果及数据处理分析：
A:

实验基本达到实验要求
Ｂ:

实验基本达到实验要求
C：

实验基本达到实验要求
D：

实验基本达到实验要求
五、实验结论与体会:
从这个实验中我学会了线性表一些基本操作，例如插入、查找与删除。也复习了一边Ｃ++语言程序得规范。原先试了很多次都就是出现错误,最后才发现太久没编程，犯了很多低级错误,从中体会到编程就是需要时间与耐心得。
　　要求挺简单得，就就是如此简单得插入、查找、删除、循环移位等。程序写完了,但就是还发现程序中还有许多不完善得地方、不严谨得地方，如异常处理，在不按正确输入格式输入时，会出现程序错误或死了得情况.

指导教师批阅意见：
成绩评定:
　 　 　 　 　 　 　 指导教师签字:
　 　　 　　　 　　　 　 年　　 月 　 日
备注：
注：1、报告内得项目或内容设置，可根据实际情况加以调整与补充。
　　 ２、教师批改学生实验报告时间应在学生提交实验报告时间后１0日内。