实验一线性表的顺序存储结构.docx
- 文档编号:14247053
- 上传时间:2023-06-21
- 格式:DOCX
- 页数:18
- 大小:19.16KB
实验一线性表的顺序存储结构.docx
《实验一线性表的顺序存储结构.docx》由会员分享,可在线阅读,更多相关《实验一线性表的顺序存储结构.docx(18页珍藏版)》请在冰点文库上搜索。
实验一线性表的顺序存储结构
实验一线性表的顺序存储结构
一.实验的目的要求:
1.掌握顺序存储结构的特点。
2.掌握顺序存储结构的常见算法。
二.实验内容
1.建立一个接口,定义一些常用的基本方法;
2.用类实现该接口的基本方法:
◆依次插入数据元素,建立顺序表;
◆按指定位置查找在该顺序表中查找某一元素;
◆按指定位置删除该顺序表中的某一元素;
◆实现该顺序表的遍历;
3.定义客户类来调用接口中的方法;
三.程序分析
顺序表:
顺序存储结构,可以实现随机的存取,核心的方法有插入删除和查找。
优点在于:
数据之间,逻辑相邻,物理相邻,可随机存取任一元素,存储空间使用很紧凑。
缺点:
在插入删除操作时,需要移动大量元素,而且预先分配最大的存储空间,造成内存空间的利用不充分。
四.源程序
1.线性表接口
publicinterfaceListInterface
/**
*任务:
往线性表的末尾插入新元素
*输入:
newEntry作为新元素插入的对象
*返回:
如果插入成功则返回true,否则返回false
*/
publicbooleanadd(TnewEntry);
/**
*任务:
将newEntry插入到线性表中位置newPosition
*输入:
newPosition是一个整数,newPosition>=1并且
*newPosition<=getLength()+1,newEntry作为新元素插入的对象
*返回:
如果插入成功则返回true,否则返回false
*/
publicbooleanadd(intnewPosition,TnewEntry);
/**
*任务:
从线性表中删除指定位置的元素。
*原本位于比指定位置更高位置的元素移动到线性表中下一个更低的位置。
*线性表的大小减1。
*输入:
givenPosition>=1并且givenPosition<=getLength()
*返回:
如果删除成功,则返回givenPosition位置的元素,否则返回null
*/
publicTremove(intgivenPosition);
/**
*任务:
删除表中所有元素
*/
publicvoidclear();
/**
*任务:
替换表中指定位置的元素
*输入:
givenPosition指定替换元素位置的一个整数;
*givenPosition>=1并且givenPosition<=getLength();
*givenPosition非法,则返回false;
*newEntry用以替换givenPosition位置的元素的对象
*/
publicbooleanreplace(intgivenPosition,TnewEntry);
/**
*任务:
检索线性表中指定位置的元素
*输入:
givenPosition指定被检索元素位置的一个整数;
*givenPosition>=1并且givenPosition<=getLength()
*返回:
如果找到指定的线性表元素,返回对它的引用,否则返回null
*/
publicTgetEntry(intgivenPosition);
/**
*任务:
确定线性表是否含有一个给定的元素
*输入:
anEntry表示待查元素的对象
*返回:
如果线性表含有anEntry,返回true,否则返回false
*/
publicbooleancontains(TanEntry);
/**
*任务:
获得线性表的长度
*返回:
返回线性表中当前所含元素个数的整数
*/
publicintgetLength();
/**
*任务:
确定线性表是否为空
*返回:
如果线性表为空,返回true,否则返回false
*/
publicbooleanisEmpty();
/**
*任务:
确定线性表是否为满
*返回:
如果线性表为满,返回true,否则返回false
*/
publicbooleanisFull();
/**
*任务:
按照元素在线性表中的顺序显示线性表中的所有元素
*/
publicvoiddisplay();
/**
*任务:
完成指定位置之间元素的逆置
*输入:
head和tail分别指示起始位置和结束位置
*/
publicvoidinvert(inthead,inttail);
/**
*任务:
将表中前m个元素和后n元素,位置进行互换
*输入:
m和n分别指示互换的前后互换元素的长度
*/
publicvoidexchage(intm,intn);
/**
*任务:
删除表中相同元素
*/
publicvoidpurge();
/**
*任务:
将两个线性表进行合并,相同元素不并入
*输入:
willBeUnion表示合并的线性表
*输出:
合并成功返回true,否则返回false
*/
publicbooleanunion(ListInterface
}
2.publicclassAList
/**
*
*/
privateT[]entry;
privateintlength;//线性表中元素的当前个数
privatestaticfinalintMAX_SIZE=50;
publicAList(){
//TODOAuto-generatedconstructorstub
this(MAX_SIZE);
}
publicAList(intmaxsize){
//TODOAuto-generatedconstructorstub
length=0;
entry=(T[])newObject[maxsize];
}
/**
*@paramnewEntry
*/
publicbooleanadd(TnewEntry){
booleanisSuccessful=true;
if(!
isFull()){
entry[length+1]=newEntry;
length++;
}else
isSuccessful=false;
returnisSuccessful;
}
publicbooleanadd(intnewPosition,TnewEntry){
//TODOAuto-generatedmethodstub
booleanresult=false;
if(!
isFull()){
//从newPosition开始到length-1之间的元素后移一位
for(inti=length;i>=newPosition;i--)
entry[i+1]=entry[i];
entry[newPosition]=newEntry;
length++;
result=true;
}
returnresult;
}
publicvoidclear(){
//TODOAuto-generatedmethodstub
length=0;
}
publicbooleancontains(TanEntry){
//TODOAuto-generatedmethodstub
booleanresult=false;
inti=1;
for(;(i<=length)&&!
anEntry.equals(entry[i]);i++)
;
if(i<=length)
result=true;
returnresult;
}
publicvoiddisplay(){
for(inti=1;i<=length;i++){
System.out.println(entry[i]);
}
}
publicTgetEntry(intgivenPosition){
//TODOAuto-generatedmethodstub
TgotEntry=null;
if(givenPosition>=1&&givenPosition<=length){
gotEntry=entry[givenPosition];
}
returngotEntry;
}
publicintgetLength(){
returnlength;
}
publicbooleanisEmpty(){
//TODOAuto-generatedmethodstub
booleanresult=false;
if(length==0)
result=true;
returnresult;
}
publicbooleanisFull(){
//TODOAuto-generatedmethodstub
booleanreturnVal=false;
if(length>=MAX_SIZE)
returnVal=true;
returnreturnVal;
}
publicTremove(intgivenPosition){
TremovedEntry=null;
if((givenPosition>=1)||(givenPosition<=length)){//删除位置合法
removedEntry=entry[givenPosition];//被删除元素的值赋给e
for(inti=givenPosition+1;i<=length;i++){
entry[i-1]=entry[i];
}
length--;
}
returnremovedEntry;
}
publicbooleanreplace(intgivenPosition,TnewEntry){
booleanresult=false;
if((givenPosition>=1)||(givenPosition<=length)){//替换的位置合法
entry[givenPosition]=newEntry;
result=true;
}
returnresult;
}
publicvoidexchage(intm,intn){
if(m>=1&&n>=1&&m+n<=length){
invert(1,length);
//System.out.println("第一次互换:
");
//display();
invert(1,n);
//System.out.println("第二次互换:
");
//display();
invert(n+1,length-m);
//System.out.println("第三次互换:
");
//display();
this.invert(length+1-m,length);
//System.out.println("第四次互换:
");
//list.display();
}
}
publicvoidexchage2(intm,intn){
intlistLen=getLength();
if(m>=1&&n>=1&&m+n<=listLen){
intfirsEntryLoc=1;
for(inti=listLen-n+1;i<=listLen;i++){
Ttemp=remove(i);
add(firsEntryLoc,temp);
firsEntryLoc++;
}
for(intj=m+n+1;j<=listLen;j++){
Ttemp=remove(j);
add(firsEntryLoc,temp);
firsEntryLoc++;
}
}
}
@Override
publicvoidinvert(inthead,inttail){
if(!
isEmpty()&&(head>=1&&head while(head Ttemp=getEntry(head); replace(head,getEntry(tail)); replace(tail,temp); head++; tail--; } } } @Override publicvoidpurge(){ for(inti=1;i<=getLength();i++){ for(intj=i+1;j<=getLength();){ if(getEntry(i).equals(getEntry(j))){ remove(j); }else{ j++; } } } } //删除顺序表L中的冗余元素,即使操作之后的顺序表中只保留 //操作之前表中所有值都不相同的元素 publicvoidpurge2(){ intk=0;//k指示新表的表尾 for(inti=1;i<=length;++i){//顺序考察表中每个元素 intj=1; while(j<=k&&(! getEntry(j).equals(getEntry(i)))){ //在新表中查询是否存在和第i位置相同的元素 ++j; } if(k==0||j>k){//k=0表明当前考察的是第一个元素 k++; replace(k,getEntry(i)); } }//for length=k;//修改表长 } @Override publicbooleanunion(ListInterface intlb_len=willBeUnion.getLength();//求线性表的长度 for(inti=1;i<=lb_len;i++){ Te=willBeUnion.getEntry(i);//取Lb中第i个数据元素赋给e if(! contains(e)) add(e); } returntrue; } } 3测试类 importjava.util.Scanner; publicclassTestAList{ privateListInterface TestAList(){ alist=newAList } publicListInterface returnalist; } publicvoidsetAList(ListInterface this.alist=alist; } publicvoidtestGetLength(){ System.out.println("初始化后,线性表的长度为: "+alist.getLength()); } publicvoidtestInvert(){ alist.add("B"); alist.add("C"); alist.add("D"); alist.add("E"); alist.add("F"); alist.add("G"); System.out.println("逆置之前: "); alist.display(); alist.invert(2,6); System.out.println("逆置之后: "); alist.display(); } publicvoidtestExchage(){ alist.add("A"); alist.add("B"); alist.add("C"); alist.add("D"); alist.add("E"); alist.add("F"); alist.add("G"); System.out.println("互换之前: "); alist.display(); alist.exchage(2,3); System.out.println("互换之后: "); alist.display(); } publicvoidtestExchage2(){ AList alist2.add("1"); alist2.add("2"); alist2.add("3"); alist2.add("4"); alist2.add("5"); alist2.add("6"); alist2.add("7"); System.out.println("互换之前: "); alist2.display(); alist2.exchage2(2,3); System.out.println("互换之后: "); alist2.display(); } publicvoidtestPurge(){ alist.add("A"); alist.add("B"); alist.add("B"); alist.add("C"); alist.add("B"); alist.add("A"); alist.add("D"); System.out.println("删除重复元素之前: "); alist.display(); alist.purge(); System.out.println("删除重复元素之后: "); alist.display(); } publicvoidtestPurge2(){ AList alist3.add("1"); alist3.add("2"); alist3.add("2"); alist3.add("2"); alist3.add("1"); //alist3.add("2"); //alist3.add("1"); System.out.println("删除重复元素之前: "); alist3.display(); alist3.purge2(); System.out.println("删除重复元素之后: "); alist3.display(); } publicvoidtestUnion(){ alist.add("A"); alist.add("B"); alist.add("C"); alist.add("D"); AList willBeUnioned.add("D"); willBeUnioned.add("E"); willBeUnioned.add("A"); willBeUnioned.add("F"); System.out.println("合并前: "); alist.display(); alist.union(willBeUnioned); System.out.println("合并后: "); alist.display(); } /** *@paramargs */ publicstaticvoidmain(String[]args){ TestAListtestAList=newTestAList(); //测试获取线性表的长度 //testAList.testGetLength(); //测试线性表逆置 //testAList.testInvert(); //测试互换实现一 //testAList.testExchage(); //测试互换实现二 //testAList.testExchage2(); //测试删除重复元素实现一 testAList.testPurge(); //测试删除重复元素实现二 //testAList.testPurge2(); //测试线性表合并 //testAList.testUnion(); //Scannerkeyboard=newScanner(System.in); //Stringmessage=keyboard.next(); //AList //alist2.add(message); //message=keyboard.next(); //alist2.add(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验一 线性表的顺序存储结构 实验 线性 顺序 存储 结构