武汉纺织大学《数据结构》实验报告1

武汉纺织大学《数据结构》实验报告班级：级管工类专业2班姓名：序号：1实验时间：2014年4月4日指导教师：实验一：线性结构的基本操作一、实验目的：1、熟悉Java上机环境，掌握Java语言编程方法，熟练运用Java语言实现数据结构设计和算法设计。2、掌握线性表的顺序存储结构和链式存储结构的定义与基本操作，并能用Java语言实现线性表基本功能。3、掌握栈、队列的存储结构与基本操作，并能利用该结构编写算法解决实际问题。二、实验内容：1、编写一个Java语言程序，利用线性表实现约瑟夫环问题，参考书本程序示例【例2.1】，完善该程序并运行。实验步骤：①、在Java编辑环境中新建程序，根据【例2.1】输入完整程序内容，并保存和编译；②、运行程序，输入约瑟夫环长度number、起始位置start、计数值distance；③、依次输入约瑟夫环中number个数据元素；④、输出约瑟夫环执行过程。2、编写一个程序，利用栈解决递归问题，实现n阶Hanoi塔问题。实验步骤：①、在Java编辑环境中新建程序，输入n阶Hanoi塔程序内容，并保存和编译；②、运行程序，输入盘子数目n。③、输出n阶Hanoi塔问题解决过程。参考程序如下：importjava.util.Scanner;publicclassMethodOfHanoi{publicstaticvoidmain(String[]args){System.out.println(“请输入盘子数目：”);Scannerscan=newScanner(System.in);//输入盘子数目intnumber=scan.nextInt();hanoi(number,‘A’,‘B’,‘C’);//调用hanoi方法}publicstaticvoidhanoi(intnum,chara,charb,charc){if(num==1)//只有一个盘子，直接移动{move(a,c);}else{hanoi(num-1,a,c,b);//递归调用move(a,c);hanoi(num-1,b,a,c);//递归调用}}publicstaticvoidmove(chara,charc)//移动过程方法{System.out.println(从+a+移到+c);}}3、编写一个程序，利用Java语言建立一个空队列，如果输入奇数，则奇数入队列；如果输入偶数，则队列中的第一个元素出队列；如果输入0，则退出程序。实验步骤：①、在Java编辑环境中新建程序，输入程序内容，并保存和编译；②、运行程序，输入数据并进行相应队列操作。③、输出每次输入数据后的队列结果。三、操作步骤：1．代码：importjava.util.ArrayList;importjava.util.List;publicclassYSfh{publicYSfh(intnumber,intstart,intdistance){ListStringlist=newArrayListString(number);for(inti=0;inumber;i++)list.add((char)('A'+i)+);System.out.print(约瑟夫环(+number+,+start+,+distance+),);System.out.print(list.toString());inti=start;while(list.size()1){i=(i+distance-1)%list.size();System.out.print(删除+list.remove(i).toString()+,);System.out.print(list.toString());}System.out.print(被赦免者是+list.get(0).toString());}publicstaticvoidmain(Stringargs[]){newYSfh(5,0,2);}}运行结果：2.代码：importjava.util.Scanner;publicclassMethodOfHanoi{publicstaticvoidmain(String[]args){System.out.println(请输入盘子数目:);Scannerscan=newScanner(System.in);//输入盘子数目intnumber=scan.nextInt();hanoi(number,'A','B','C');}publicstaticvoidhanoi(intnum,chara,charb,charc){if(num==1)//只有一个盘子，直接移动{move(a,c);}else{hanoi(num-1,a,c,b);//递归调用move(a,c);hanoi(num-1,b,a,c);//递归调用}}publicstaticvoidmove(chara,charc)//移动过程方法{System.out.println(从+a+移到+c);}}运行结果：3.代码QQueue.javapublicinterfaceQQueueT{booleanisEmpty();booleanenqueue(Tx);Tdequeue();}SeqQueue.javapublicclassSeqQueueTimplementsQQueueT{privateObjectelement[];privateintfront,rear;publicSeqQueue(intlength){if(length64)length=64;this.element=newObject[Math.abs(length)];this.front=this.rear=0;}publicSeqQueue(){this(64);}publicbooleanisEmpty(){returnthis.front==this.rear;}publicbooleanenqueue(Tx){if(x==null)returnfalse;if(this.front==(this.rear+1)%this.element.length){Object[]temp=this.element;this.element=newObject[temp.length*2];inti=this.front,j=0;while(i!=this.rear){this.element[j]=temp[i];i=(i+1)%temp.length;j++;}this.front=0;this.rear=j;returntrue;}this.element[this.rear]=x;this.rear=(this.rear+1)%this.element.length;returntrue;}publicTdequeue(){if(isEmpty())returnnull;Ttemp=(T)this.element[this.front];this.front=(this.front+1)%this.element.length;returntemp;}publicStringtoString(){Stringstr=(;if(!isEmpty()){str+=this.element[this.front].toString();inti=(this.front+1)%this.element.length;while(i!=this.rear){str+=,+this.element[i].toString();i=(i+1)%this.element.length;}}returnstr+);}}ts3.javaimportjava.util.Scanner;publicclassts3{publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);SeqQueueIntegerqueue=newSeqQueue(64);intnum=-1;while(num!=0){num=in.nextInt();if(num%2==0){if(queue.dequeue()==null){System.out.println(当前队列为空！);}}else{if(!queue.enqueue(num)){System.out.println(当前队列满！);}}System.out.println(当前队列:+queue.toString())}}}四、实验收获和建议：通过这次实验，完成了三个具体的操作任务，对课堂上学到的知识有了进一步的了解，虽然有些地方还不是很懂，通过与其他同学的交流，更深入的理解了线性表，串，栈，队列的相关学习内容