《数据结构》实验指导书(Java语言版).pdf

《《数据结构》实验指导书(Java语言版).pdf》由会员分享，可在线阅读，更多相关《《数据结构》实验指导书(Java语言版).pdf（113页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 数据结构实验指导书(Java语言版)D 1 1 1 1 算法设计分概要和详细设计。概要设计着重解决程序的类的设计问题，这包括考虑如何把被开发的问题程序分解成若干个类，并决定类与类之间的关系。详细设计则要决定每个类内部的具体算法，包括输入、处理和输出。1.测试用例设计 准备典型测试数据和测试方案。测试数据要有代表性、敏感性。测试方案包括单元测试和单元集成测试。2.上机调试 对程序进行编译，纠正程序中可能出现的语法错误。调试前，先运行一遍程序看看究竟将会发生什么。如果情况很糟，则根据事先设计的测试方案并结合现场情况进行错误跟踪，包括打印执行路径或输出中间变量值等手段。6.程序性能分析 在运行结果

2、正确的前提下再分析程序中主要算法是否具有较好的时间复杂度和空间复杂度。如果没有，则通过改变数据结构或操作方法使编写的程序性能达到最佳。7.实验总结 每个实验完成后要认真书写实验报告，对程序运行的结构，要认真分析，总结每次实验项目的体会与收获。四、报告与考核 每个实验都要求学生根据上机内容写出实验报告，报告要求包括以下七个方面的内容：1实验目的；2实验内容；3实验要求；4算法设计；5详细程序清单；6程序运行结果；7实验心得体会。考核方式：每个实验项目根据以下两个方面进行考核：2 1指导教师随堂抽查学生的实验过程（包括实验预习、实验出勤、实验结果的测试），并根据抽查结果评定学生成绩，此成绩占此实验

3、总成绩的 70%；2学生编写课程实验报告，每位学生按照实验报告的内容和要求编写详细的实验报告上交给指导老师，由指导老师根据每位学生的完成情况评定成绩，此成绩占实验总成绩的 30%。五、设备及器材材料配置 硬件：奔腾以上 PC 机 软件：Netbeans 6.5 以上或 Eclipse、MyEclipse等编程环境 六、实验指导书及主要参考书 1刘小晶.数据结构实验指导书(Java语言版)2 Robert Lafore 著,计晓云等译.Java 数据结构和算法(第二版)M.北京：中国电力出版社,2004.3 Sartaj Sahni著,孔芳,高伟译.数据结构、算法与应用(Java 语言描述)M.

4、北京：中国水利水电出版社,2007.4 叶核亚.数据结构(Java 版)M.北京：电子工业出版社，2004.5 邓俊辉.数据结构与算法(Java 语言描 3 述)M.北京：机械工业出版社，2006.6 朱战立.数据结构-Java 语言描述M.北京：清华大学出版社，2005.7 张铭.数据结构与算法.高教出版社.2008.6 8 张铭.数据结构与算法学习指导与习题解析.高教出版社.2009 9 耿国华等 数据结构-C 语言描述.高教出版社.2005.7 10 刘怀亮.数据结构(C 语言描述).冶金出版社.2005.2 11 刘怀亮.数据结构(C 语言描述)习题与实验指导导.冶金出版社.2005.

5、2 12 蔡子经，施伯乐.数据结构教程.上海:复旦大学出版社.1994 13 严蔚敏,吴伟民.数据结构(C语言版).北京：清华大学出版社.1999；14 严蔚敏,吴伟民.数据结构题集(C语言版).北京：清华大学出版社.1999；15 徐孝凯.数据结构课程实验.北京：清华大学出版社.2002；16 孟佳娜,胡潇琨.算法与数据结构实验与习题.北京：机械工业出版社.2004.七、实验项目与内容提要 序号 实验名称 目的要求、内容提要（限 20 字）每组人数 实验学时 实验类型 必做 选做 所在实验分室 1 顺序表的基本操作 熟悉并完成顺序表上基本操作的算法及其应用问题的编程实现。1个班 2 验 证

6、与 设计 必做 2 链表的基本操作 熟悉并完成单链表和双向链表基本操作算法的编程实现。1个班 2 验 证 与 设计 必做 4 3 栈的基本操作 熟悉并完成顺序栈和链栈基本操作算法及其应用问题的编程实现 1个班 2 验 证 与 设计 必做 4 队列的基本操作 熟悉并完成循环顺序队列和循环链队列基本操作算法及其应用问题的编程实现。1个班 2 验 证 与 设计 必做 5 二叉树的操作 熟悉并完成二叉树遍历算法及其应用问题的编程实现。1个班 2 验 证 与 设计 必做 6 静态查找表的查找操作 熟悉并完成静态查找表上的顺序查找、二分查找和索引查找算法的编程实现 1个班 2 验 证 与 设计 必做 7

7、二叉排序树的查找操作 熟悉并完成在二叉排序树上进行查找、插入和删除操作的编程实现。1个班 2 验 证 与 设计 选做 8 哈希表上的查找操作 熟悉并完成哈希表的建立、查找和插入操作的编程实现 1个班 2 验 证 与 设计 选做 9 排序操作 熟悉并完成几种主要排序操作的编程实现。1个班 2 验 证 与 设计 必做 10 图的遍历 熟悉并完成图的遍历、最小生成树及其应用问题的编程实现 1个班 2 验 证 与 设计 选做 5 实验 B01:顺序表的操作实验 一、实验名称和性质 所属课程 数据结构 实验名称 顺序表的操作 实验学时 2 实验性质 验证 综合 设计 必做/选做 必做 选做 二、实验目的

8、 1掌握线性表的顺序存储结构的表示和实现方法。2掌握顺序表基本操作的算法实现。3了解顺序表的应用。三、实验内容 1建立顺序表。2在顺序表上实现插入、删除和查找操作（验证性内容）。3删除有序顺序表中的重复元素（设计性内容）。4完成一个简单学生成绩管理系统的设计（应用性设计内容）。四、实验的软硬件环境要求 硬件环境要求：PC 机（单机）使用的软件名称、版本号以及模块：Netbeans 6.5 以上或 Eclipse、MyEclipse 等编程环境下。五、知识准备 前期要求熟练掌握了 Java 语言的编程规则、方法和顺序表的基本操作算法。六、验证性实验 1实验要求 编程实现如下功能：（1）根据输入顺

9、序表的长度 n 和各个数据元素值建立一个顺序表，并输出顺序表中各元素值，观察输入的内容与输出的内容是否一致。（2）在顺序表的第 i(0in)个元素之前插入一个值为 x 的元素，并输出插入后的顺序表 6 中各元素值。（3）删除顺序表中第 i(0in-1)个元素，并输出删除后的顺序表中各元素值。（4）在顺序表中查找值为 x 的数据元素初次出现的位置。如果查找成功，则返回该数据元素在顺序表中的位序号；如果查找失败，则返回-1。2.实验相关原理 线性表的顺序存储结构称为顺序表，线性表的顺序存储结构在线性表 Java 接口的实现类中描述如下：public class SqList implements

10、IList private Object listElem;/线性表存储空间 private int curLen;/线性表的当前长度 【核心算法提示】顺序表插入操作的基本步骤：要在当前的顺序表中的第 i(0in,n 为线性表的当前长度)个数据元素之前插入一个数据元素 x，首先要判断插入位置 i 是否合法，i 的合法值范围：1in+1，若是合法位置，就再判断顺序表是否满，如果不满，则将第 i 个数据元素及其之后的所有数据元素都后移一个位置，此时第 i 个位置已经腾空，再将待插入的数据元素 x 插入到该位置上，最后将线性表的当前长度值增加 1，否则抛出异常。顺序表删除操作的基本步骤：要删除当前顺

11、序表中的第 i(0in-1)个数据元素，首先仍然要判断 i 的合法性，i 的合法范围是 0in-1，若是合法位置，则将第 i 个数据元素之后的所有数据元素都前移一个位置，最后将线性表的当前长度减 1，否则抛出异常。顺序表查找操作的基本步骤：要在当前顺序表中查找一个给定值的数据元素，则可以采用顺序查找的方法，从顺序表中第 0 个数据元素 7 开始依次将数据元素值与给定值进行比较，若相等则返回该数据元素在顺序表中的位置，如果所有数据元素都与 x 比较但都不相等，表明值为 x的数据元素在顺序表中不存在，则返回-1 值。【核心算法描述】在当前顺序表上的插入操作算法 void insert(int i,

12、Object x)throws Exception if(curLen=listElem.length)/判断顺序表是否已满 throw new Exception(顺序表已满);/抛出异常 if(i curLen)/i 不合法 throw new Exception(插入位置不合法);/抛出异常 for(int j=curLen;j i;j-)listElemj=listElemj-1;/插入位置及其之后的所有数据元素后移一位 listElemi=x;/插入 x curLen+;/表长加 1 在当前顺序表上的删除操作算法 void remove(int i)throws Exception

13、if(i curLen-1)/i 不合法 throw new Exception(删除位置不合法);/抛出异常 for(int j=i;j curLen-1;j+)listElemj=listElemj+1;/被删除元素及其之后的数据元素左移一个存储位置 curLen-;/表长减 1 在当前顺序表是的查找操作算法 int indexOf(Object x)int j=0;/j 指示顺序表中待比较的数据元素，其初始值指示顺序表中第 0 个数据元素 while(j curLen&!listElemj.equals(x)/依次比较 j+;if(j curLen)/判断 j 的位置是否位于顺序表中 r

14、eturn j;/返回值为 x 的数据元素在顺序表中的位置 else return-1;/值为 x 的数据元素在顺序表中不存在 3源程序代码参考 package sy;import java.util.Scanner;class SqList private Object listElem;/线性表存储空间 private int curLen;/当前长度 8 public int getCurLen()return curLen;public void setCurLen(int curLen)this.curLen=curLen;public Object getListElem()ret

15、urn listElem;public void setListElem(Object listElem)this.listElem=listElem;/顺序表的构造函数，构造一个存储空间容量为 maxSize 的空线性表 public SqList(int maxSize)curLen=0;/置顺序表的当前长度为 0 listElem=new ObjectmaxSize;/为顺序表分配 maxSize 个存储单元 /在线性表的第i个数据元素之前插入一个值为x的数据元素。其中i取值范围为：0icurLen。public void insert(int i,Object x)throws Exc

16、eption if(curLen=listElem.length)/判断顺序表是否已满 throw new Exception(顺序表已满);/输出异常 if(i curLen)/i小于 0 或者大于表长 throw new Exception(插入位置不合理);/输出异常 for(int j=curLen;j i;j-)listElemj=listElemj-1;/插入位置及之后的元素后移 listElemi=x;/插入 x curLen+;/表长度增 1 /将线性表中第 i 个数据元素删除。其中 i 取值范围为：0icurLen-1,如果 i 值不在此范围则抛出异常 public void

17、 remove(int i)throws Exception if(i curlew-1)/i小于 1 或者大于表长减 1 throw new Exception(删除位置不合理);/输出异常 for(int j=i;j curLen-1;j+)listElemj=listElemj+1;/被删除元素之后的元素左移 curLen-;/表长度减 1 9 /查找顺序表中值的 x 元素,若查找成功则返回元素在表中的位序(0curLen-1),否则返回-1 public int indexOf(Object x)int j=0;/j 指示顺序表中待比较的数据元素，其初始值指示顺序表中第 0 个数据元素

18、 while(j curLen&!listElemj.equals(x)/依次比较 j+;if(j curLen)/判断 j 的位置是否位于顺序表中 return j;/返回值为 x 的数据元素在顺序表中的位置 else return-1;/值为 x 的数据元素在顺序表中不存在 /输出顺序表中的数据元素 public void display()for(int j=0;j curLen;j+)System.out.print(listElemj+);System.out.println();/换行 /测试类 public class SY1_SqList public static void

19、main(String args)throws Exception SqList L=new SqList(20);/构造一个存储容量为 0 的空顺序表 Scanner sc=new Scanner(System.in);System.out.println(请输入顺序表的长度:);int n=sc.nextInt();System.out.println(请输入顺序表中的各个数据元素:);for(int i=0;in;i+)L.insert(i,sc.nextInt();System.out.println(请输入待插入的位置 i(0curLen):);int i=sc.nextInt();

20、System.out.println(请输入待插入的数据值 x:);int x=sc.nextInt();L.insert(i,x);System.out.println(插入后的顺序表为:);L.display();System.out.println(请输入待删除元素的位置(0curLen-1):);i=sc.nextInt();L.remove(i);System.out.println(删除后的顺序表为:);10 L.display();System.out.println(请输入待查找的数据元素:);x=sc.nextInt();int order=L.indexOf(x);if(o

21、rder=-1)System.out.println(此顺序表中不包含值为+x+的数据元素!);else System.out.println(值为+x+元素在顺序表中的第+order+个位置上);4运行结果参考如图 1-1 所示：图 1-1:验证性实验运行结果 备注:以下设计性和应用性实验内容学生可根据自己的掌握程度或兴趣自行选择其一或其二完成。七、设计性实验 编程实现删除有序顺序表中的所有重复元素，即使有序顺序表中相同的元素只保留一个。1.实验要求 根据输入的 n 个非递减的有序数据建立一个有序顺序表，并输出有序顺序表中各元素 11 值。删除有序顺序表中所有的重复元素，并显示删除后的有序顺

22、序表中各元素值。2.核心算法提示 要在有序顺序表中删除重复的元素，首先就要抓住有序顺序表的特性：重复的元素总是在相邻的位置上，如：12，15，15，15，35，56，56，78。则删除重复元素后所得的有序表为：12，15，35，56，78。下面给出大致的操作步骤：从第 0个元素开始，依次将它与后面相邻的元素进行比较，如果相等则将前面那个相等的元素从顺序表中删除；如果不相等，则继续往下比较，如此重复，直到最后一个元素为止。3.核心算法描述/删除有序顺序表 L 中的所有重复元素，即使得有序顺序表中相同的元素只保留一个 public static void remove_repeat(SqList

23、L)int i=0;while(iL.getCurLen()-1)if(L.getListElem()i.equals(L.getListElem()i+1)/如果第i个及第i+1个相邻元素值相等 for(int j=i+1;jL.getCurLen();j+)/将第i+1个元素及其之后的所有元素前移一个位地置 L.getListElem()j-1=L.getListElem()j;L.setCurLen(L.getCurLen()-1);/有序顺序表的表长减1 else i+;八、应用性设计实验 编程实现一个简单学生成绩管理系统的设计。实验要求 此系统的功能包括：查询：按特定的条件查找学生

24、修改：按学号对某个学生的某门课程成绩进行修改 12 插入：增加新学生的信息 删除：按学号删除已退学的学生的信息。学生成绩表的数据如下：学号 姓名 性别 大学英语 高等数学 2008001 Alan F 93 88 2008002 Danie M 75 69 2008003 Helen M 56 77 2008004 Bill F 87 90 2008006 Peter M 79 86 2008006 Amy F 68 75 要求采用顺序存储结构来实现对上述成绩表的相关操作。13 实验 B02:链表的操作实验 一、实验名称和性质 所属课程 数据结构 实验名称 链表的操作 实验学时 2 实验性质

25、验证 综合 设计 必做/选做 必做 选做 二、实验目的 1掌握线性表的链式存储结构的表示和实现方法。2掌握链表基本操作的算法实现。三、实验内容 1建立单链表，并在单链表上实现插入、删除和查找操作（验证性内容）。2建立双向链表，并在双向链表上实现插入、删除和查找操作（设计性内容）。3计算已知一个单链表中数据域值为一个指定值 x 的结点个数（应用性设计内容）。四、实验的软硬件环境要求 硬件环境要求：PC 机（单机）使用的软件名称、版本号以及模块：Netbeans 6.5 以上或 Eclipse、MyEclipse 等编程环境下。五、知识准备 前期要求熟练掌握了 Java 语言的编程规则、方法和单链

26、表和双向链表的基本操作算法。六、验证性实验 1实验要求 编程实现如下功能：（1）根据输入的一系列整数，以 0 标志结束，用头插法建立单链表，并输出单链表中各元素值，观察输入的内容与输出的内容是否一致。（2）在单链表的第 i 个元素之前插入一个值为 x 的元素，并输出插入后的单链表中各元素值。（3）删除单链表中第 i 个元素，并输出删 14 除后的单链表中各元素值。（4）在单链表中查找第 i 个元素，如果查找成功，则显示该元素的值，否则显示该元素不存在。2.实验相关原理：线性表的链式储结构是用一组任意的存储单元依次存放线性表中的元素，这组存储单元可以是连续的，也可以是不连续的。为反映出各元素在线

27、性表中的前后逻辑关系，对每个数据元素来说，除了存储其本身数据值之外，还需增加一个或多个指针域，每个指针域的值称为指针，又称作链，它用来指示它在线性表中的前驱或后继的存储地址。这两个部分的的一起组成一个数据元素的存储映像，称为结点，若干个结点链接成链表。如果一个结点中只含一个指针的链表，则称单链表。单链表中结点类描述如下：class Node private Object data;/存放结点值 private Node next;/后继结点的引用 /无参数时的构造函数 public Node()this(null,null);/带一个参数时的构造函数 public Node(Object da

28、ta)this(data,null);/带两个参数时的构造函数 public Node(Object data,Node next)this.data=data;this.next=next;【核心算法提示】链表建立操作的基本步骤：链表是一个动态的结构，它不需要予分配空间，因此建立链表的过程是一个结点“逐个插入”的过程。先建立一个只含头结点的空单链表，然后依次生成新结点，再不断地将其插入到 15 链表的头部或尾部，分别称其为“头插法”和“尾插法”。链表查找操作的基本步骤：因链表是一种顺序存取的结构，则要在带头结点的链表中查找到第 i 个 元素，必须从头结点开始沿着后继指针依次点数，直到点到第

29、i 个结点为止,如果查找成功，则用 e 返回第 i个元素值。头结点可看成是第 0 个结点。链表插入操作的基本步骤：先确定要插入的位置，如果插入位置合法，则再生成新的结点，最后通过修改链将新结点插入到指定的位置上。链表删除操作的基本步骤：先确定要删除的结点位置，如果位置合法，则再通过修改链使被删结点从链表中“卸下”，最后释放被删结点的空间。【核心算法描述】用头插法创建带头结点的单链表操作算法 void creat()throws Exception/*输入一系列整数，以 0 标志结束，将这些整数作为/data域并用头插法建立一个带头结点的单链表 Scanner sc=new Scanner(Sy

30、stem.in);/构造用于输入的对象 for(int x=sc.nextInt();x!=0;x=sc.nextInt()/输入 n 个元素的值 insert(0,x);/生成新结点,插入到表头 在当前带头结点的单链表上的查找操作算法 Object get(int i)throws Exception Node p=head.getNext();/初始化，p 指向首结点，j 为计数器 int j=0;while(p!=null&j i|p=null)/i 小于 0 或者大于表长减 1 throw new Exception(第+i+个元素不存在);/抛出异常 return p.getData

31、();/返回结点 p 的数据域的值 16 在当前带头结点的单链表上的插入操作算法 void insert(int i,Object x)throws Exception Node p=head;/初始化 p 为头结点,j 为计数器 int j=-1;while(p!=null&j i-1|p=null)/i 不合法 throw new Exception(插入位置不合理);/输出异常 Node s=new Node(x);/生成新结点 s.setNext(p.getNext();/插入单链表中 p.setNext(s);在当前带头结点的单链表上的删除操作算法 void remove(int i

32、)throws Exception Node p=head;/初始化 p 为头结点,j 为计数器 int j=-1;while(p.getNext()!=null&j i-1|p.getNext()=null)/i 小于 0 或者大于表长减 1 throw new Exception(删除位置不合理);/输出异常 p.setNext(p.getNext().getNext();/删除结点 3源程序代码参考 package sy;import java.util.Scanner;/单链表的结点类 class Node private Object data;/存放结点值 private Node

33、 next;/后继结点的引用 public Node()/无参数时的构造函数 17 this(null,null);public Node(Object data)/构造值为 data 的结点 this(data,null);public Node(Object data,Node next)this.data=data;this.next=next;public Object getData()return data;public void setData(Object data)this.data=data;public Node getNext()return next;public v

34、oid setNext(Node next)this.next=next;/实现链表的基本操作类 class LinkList Node head=new Node();/生成一个带头结点的空链表 /根据输入的一系列整数，以 0 标志结束，用头插法建立单链表 public void creat()throws Exception Scanner sc=new Scanner(System.in);/构造用于输入的对象 for(int x=sc.nextInt();x!=0;x=sc.nextInt()/输入若干个数据元素的值(以 0 结束)insert(0,x);/生成新结点,插入到表头 /返

35、回带头结点的单链表中第 i 个结点的数据域的值。其中：0icurLen-1 public Object get(int i)throws Exception Node p=head.getNext();/初始化，p 指向首结点，j 为计数器 int j=0;while(p!=null&j i|p=null)/i小于 0 或者大于表长减 1 throw new Exception(第+i+个元素不存在);/抛出异常 return p.getData();/返回结点 p 的数据域的值 /在带头结点的单链表中的第 i 个数据元素之前插入一个值为 x 的元素 public void insert(in

36、t i,Object x)throws Exception Node p=head;/初始化 p 为头结点,j 为计数器 int j=-1;while(p!=null&j i-1|p=null)/i不合法 throw new Exception(插入位置不合理);/输出异常 Node s=new Node(x);/生成新结点 s.setNext(p.getNext();/插入单链表中 p.setNext(s);/删除带头结点的第 i 个数据元素。其中 i 取值范围为：0ilength()-1,如果 i 值不在此范围则抛出异常 public void remove(int i)throws Ex

37、ception Node p=head;/初始化 p 为头结点,j 为计数器 int j=-1;while(p.getNext()!=null&j i-1|p.getNext()=null)/i小于 0 或者大于表长减 1 throw new Exception(删除位置不合理);/输出异常 p.setNext(p.getNext().getNext();/删除结点 /输出线性表中的数据元素 public void display()Node p=head.getNext();/取出带头结点的单链表中的首结点元素 19 while(p!=null)System.out.print(p.getD

38、ata()+);/输出数据元素的值 p=p.getNext();/取下一个结点 System.out.println();/换行 /测试类 public class SY2_LinkList public static void main(String args)throws Exception Scanner sc=new Scanner(System.in);LinkList L=new LinkList();System.out.println(请输入链表中的各个数据元素(0 为结束):);L.creat();System.out.println(建立的单链表为:);L.display(

39、);System.out.println(请输入待插入的位置 i(0curLen):);int i=sc.nextInt();System.out.println(请输入待插入的数据值 x:);int x=sc.nextInt();L.insert(i,x);System.out.println(插入后的链表为:);L.display();System.out.println(请输入待删除元素的位置(0curLen-1):);i=sc.nextInt();L.remove(i);System.out.println(删除后的链表为:);L.display();System.out.printl

40、n(请输入待查找的数据元素的位序号(0curLen-1):);i=sc.nextInt();Object o=L.get(i);System.out.println(此单链表中第+i+个结点的数据元素值为+o);20 4运行结果参考如图 2-1 所示：图 2-1:验证性实验运行结果 备注:以下设计性和应用性实验内容学生可根据自己的掌握程度或兴趣自行选择其一或其二完成。七、设计性实验 编程实现在双向循环链表上的插入和删除操作 1 实验要求（1）输入链表的长度和各元素的值，用尾插法建立双向循环链表，并输出链表中各元素值，观察输入的内容与输出的内容是否一致。（2）在双向循环链表的第 i 个元素之前插

41、入一个值为 x 的元素，并输出插入后的链表中各元素值。（3）删除双向循环链表中第 i 个元素，并输出删除后的链表中各元素值。（4）在双向循环链表中查找值为 x 元素，如果查找成功，则显示该元素在链表中的位序号，否则显示该元素不存在。2核心算法提示 双向循环链表中的结点类描述如下：21 class DuLNode private Object data;/存放结点值 private DuLNode prior;/前驱结点的引用 private DuLNode next;/后继结点的引用 双向循环链表类描述如下：class DuCircleLinkList private DuLNode head

42、;/双向循环链表的头结点 /构造函数:构造一个只含头结点的空双向循环链表 public DuCircleLinkList()head=new DuLNode();/初始化头结点 head.setPrior(head);/初始化头结点的前驱和后继 head.setNext(head);不论是建立双向循环链表还是在双向循环链表中进行插入、删除和查找操作，其操作方法和步骤都跟单链表类似。只不过要注意两点：（1）凡是在操作中遇到有修改链的地方，都要进行前驱和后继两个指针的修改。（2）单链表操作算法中的判断条件：p=null 或 p!=null,在循环链表的操作算法中则需改为：p=head 或 p!=h

43、ead,其中 head 为链表的头指针。3核心算法描述 在当前带头结点的双向循环链表上的插入操作的算法 void insert(int i,Object x)throws Exception DuLNode p=head.getNext();/初始化,p 指向首结点,j 为计数器 int j=0;while(!p.equals(head)&j i)/确定插入位置 i p=p.getNext();/指向后继结点 +j;/计数器的值增 1 if(j!=i)/i 小于 0 或者大于表长 throw new Exception(插入位置不合理);/输出异常 22 DuLNode s=new DuLNo

44、de(x);/生成新结点 s p.getPrior().setNext(s);/将结点 s 插入到 p 结点的前面 s.setPrior(p.getPrior();s.setNext(p);p.setPrior(s);在当前带头结点的双向循环链表上的删除操作算法 void remove(int i)throws Exception DuLNode p=head.getNext();/初始化,p 指向首节点结点,j 为计数器 int j=0;while(!p.equals(head)&j=0;i-)System.out.print(stackElemi.toString()+);/打印 Syst

45、em.out.println();/测试类 public class SY3_SqStack public static void main(String args)throws Exception SqStack S=new SqStack(100);/初始化一个新的容量为 100 的顺序栈 27 Scanner sc=new Scanner(System.in);System.out.print(请输入顺序栈的长度:);int n=sc.nextInt();System.out.println(请输入顺序栈中的各个数据元素值:);for(int i=0;i1时，若能将压在编号为 n 的圆盘

46、上的 n-1 个圆盘从塔座 X 借助于塔座 Z 移至塔座 Y 上，则可先将编号为 n 的圆盘从塔座 X 移至塔座 Z 上，再将塔座Y上的n-1个圆盘借助于塔座X移至塔座Z上。而将 n-1 个圆盘从一个塔座借助于另一个塔座而移至到第三个塔座上是一个与原问题具有相同特征属性的问题，只是问题规模小 1,因此可以用解决原问题的方法来解决。30 实验 B04:队列的操作实验 一、实验名称和性质 所属课程 数据结构 实验名称 队列的操作 实验学时 2 实验性质 验证 综合 设计 必做/选做 必做 选做 二、实验目的 1掌握队列存储结构的表示和实现方法。2掌握队列的入队和出队等基本操作的算法实现。3 了解队

47、列在解决实际问题中的简单应用。三、实验内容 1建立循环顺序队列，并在循环顺序队列上实现入队、出队基本操作（验证性内容）。2建立循环链队列，并在循环链队列上实现入队、出队基本操作（设计性内容）。3设计一个程序模仿操作系统的进程管理问题（应用性设计内容）。四、实验的软硬件环境要求 硬件环境要求：PC 机（单机）使用的软件名称、版本号以及模块：Netbeans 6.5 以上或 Eclipse、MyEclipse 等编程环境下。五、知识准备 前期要求熟练掌握了 Java 语言的编程规则、方法和顺序循环队列、循环链队列的基本操作算法。六、验证性实验 1实验要求 编程实现如下功能：（1）根据输入的队列长度

48、 n 和各元素值建立一个循环顺序表表示的队列（循环队列），并输出队列中各元素值。（2）将数据元素 x 入队，并输出入队后的队列中各元素值。31（3）将循环队列的队首元素出队，并输出出队元素的值和出队后队列中各元素值。2.实验相关原理：队列是一种插入操作限制在表尾，而删除操作限制在表头进行的特殊线性表，它的操作具有“先进先出”的特性。采用顺序存储结构的队列称为顺序队列，顺序队列的类描述如下：class CircleSqQueue implements IQueue private Object queueElem;/队列存储空间 private int front;/队首的引用，若队列不空，指向

49、队首元素 private int rear;/队尾的引用，若队列不空，指向队尾元素的下一个位置 【核心算法提示】循环顺序队列入队操作的基本步骤：首先判断队列是否为满，如果队列满，则函数返回ERROR，否则将待入队的数据元素 x 存放在尾指针 rear 所指示的存储单元中，再使尾指针沿着顺序循环存储空间后移一个位置。循环顺序队列出队操作的基本步骤：首先判断队列是否为空，如果队列空，则函数返回null，否则将头指针所指示的队首元素用 t 返回其值，再使头指针沿着顺序循环存储空间后移一个位置。【核心算法描述】假设以少用一个存储单元的方法来解决区分队列判空和判满的条件，则入队和出队操作算法可描述如下：

50、在当前循环顺序队列上的入队操作算法 void offer(Object x)throws Exception /将指定的元素 x 插入队列 if(rear+1)%queueElem.length=front)/队列满 throw new Exception(队列已满);/输出异常 else/队列未满 queueElemrear=x;/x 赋给队尾元素 rear=(rear+1)%queueElem.length;/修改队尾指针 在当前循环顺序队列上的出队操作算法 32 Object poll()/移除队首元素并返回其值，如果此队列为空，则返回 null if(front=rear)/队列为空