数据结构(Java版)-线性表的实现与应用.doc

实 验 报 告

课程名称 数据结构
实验项目 线性表的实现及应用
实验仪器 PC机一台

学 院_____
专 业
班级/学号
姓名
实验日期
成 绩
指导教师

北京信息科技大学
信息管理学院
（数据结构课程上机）实验报告
专业: 班级: 学号: 姓名: 成绩:
实验名称
线性表的实现及应用
实验地点

实验时间

1. 实验目的：
（1） 理解用顺序表实现线性表的特点；熟练掌握顺序表的基本操作；学会利用顺序表解决实际应用问题。
（2） 熟练掌握单链表的使用；理解用链表实现线性表的特点；了解链表的多种形式；学会利用单链表解决实际应用问题。
2. 实验要求：
（1） 学时为8学时；
（2） 能在机器上正确、调试运行程序；
（3） 本实验需提交实验报告；
（4） 实验报告文件命名方法：数据结构实验_信管16xx_学号_姓名.doc。

3. 实验内容和步骤：

第一部分 顺序表的实现与应用
（1）基于顺序表实现线性表的以下基本操作：
public interface LList<T>
{ //线性表接口，泛型参数T表示数据元素的数据类型
boolean isEmpty(); //判断线性表是否空
int size(); //返回线性表长度
T get(int i); //返回第i（i≥0）个元素
void set(int i, T x); //设置第i个元素值为x
void insert(int i, T x); //插入x作为第i个元素
void insert(T x); //在线性表最后插入x元素
T remove(int i); //删除第i个元素并返回被删除对象
int search(T key); //查找，返回首次出现的关键字为key的元素的位序
void removeAll(); //删除线性表所有元素
public String toString();//返回顺序表所有元素的描述字符串，形式为“（，）”
}
要求：实现后应编写代码段对每个基本操作做测试。
（2）顺序表的简单应用
a) 运用基本操作编写算法删除第i个开始的k个元素。
b) 编写高效算法删除第i个开始的k个元素。
c) 将两个顺序表合并为一个顺序表（表中元素有序）；
d) 若两个元素按值递增有序排列的顺序表A和B，且同一表中的元素值各不相同。试构造一个顺序表C，其元素为A和B中元素的交集，且表C中的元素也按值递增有序排列；
（3）利用顺序表解决约瑟夫环问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。要求：输出出列次序。

第二部分 单链表的实现与应用
（4）基于单链表实现线性表的以下基本操作（不需要建立接口，直接建立带头结点的单链表类）：
ADT List<T>
{ boolean isEmpty(); //判断线性表是否空
int size(); //返回线性表长度
T get(int i); //返回第i（i≥0）个元素
void set(int i, T x); //设置第i个元素值为x
Node<T> insert(int i, T x); //插入x作为第i个元素
Node<T> insert(T x); //在线性表最后插入x元素
T remove(int i); //删除第i个元素并返回被删除对象
void removeAll(); //删除线性表所有元素
Node<T> search(T key); //查找，返回首次出现的关键字为key元素
public String toString(); //返回顺序表所有元素的描述字符串，形式为“（，）”
}
要求：实现后应编写代码段对每个基本操作做测试。
（5）实现单链表的子类排序单链表，覆盖单链表如下方法：
void set(int i, T x); //设置第i个元素值为x
Node<T> insert(int i, T x); //插入x作为第i个元素
Node<T> insert(T x); //在线性表最后插入x元素
Node<T> search(T key); //查找，返回首次出现的关键字为key元素

（6）基于排序单链表实现线性表的以下综合应用：
e) 删除第i个开始的k个元素。
f) 删除递增有序单链表中所有值大于mink且小于maxk的元素。
g) 将两个单链表合并为一个单链表，保持有序。
h) 若两个元素按值递增有序排列的单链表A和B，且同一表中的元素值各不相同。试构造一个单链表C，其元素为A和B中元素的交集，且表C中的元素也按值递增有序排列。要求利用原有链表中的元素。
（7）一元多项式的基本运算
用排序单链表表示一元多项式，并实现以下基本运算：
l 一元多项式的建立
l 一元多项式的减法运算（要求：在运算过程中不能创建新结点 即A=A-B）

（8）备份自己程序
4. 实验准备：
复习教材第2章线性表的知识点
熟悉Java编程环境
提前熟悉实验内容，设计相关算法

5. 实验过程：
第一部分：
（1）
package ex1;
public interface LList<T>
{ //线性表接口，泛型参数T表示数据元素的数据类型
boolean isEmpty(); //判断线性表是否空
int length(); //返回线性表长度
T get(int i); //返回第i（i≥0）个元素
void set(int i, T x); //设置第i个元素值为x
int insert(int i, T x); //插入x作为第i个元素
int append(T x); //在线性表最后插入x元素
T remove(int i); //删除第i个元素并返回被删除对象
void removeAll(); //删除线性表所有元素
int search(T key); //查找，返回首次出现的关键字为key的元素的位序
}

类名：
public class SeqList<T> implements LList<T> {

protected Object[] element;
protected int n;

public SeqList(int length) //构造容量为length的空表
{
this.element = new Object[length]; //申请数组的存储空间，元素为null。
//若length<0，Java抛出负数组长度异常 java.lang.NegativeArraySizeException
this.n = 0;
}
public SeqList() //创建默认容量的空表，构造方法重载
{
this(64); //调用本类已声明的指定参数列表的构造方法
}

public SeqList(T [] values) //构造顺序表，由values数组提供元素，忽略其中空对象
{

this(values.length*2); //创建2倍values数组容量的空表
//若values==null，用空对象调用方法，Java抛出空对象异常NullPointerException
for (int i=0; i<values.length; i++) //复制非空的数组元素。O(n)
if (values[i]!=null)
this.element[this.n++] = values[i]; //对象引用赋值
}

public boolean isEmpty() //判断线性表是否空
{
return this.n==0;
}
public int length(){ //返回线性表长度
return this.n;

}
public T get(int i){ //返回第i（i≥0）个元素

if (i>=0 && i<this.n)
return (T)this.element[i]; //返回数组元素引用的对象，传递对象引用
// return this.element[i]; //编译错，Object对象不能返回T对象
return null;
}
public void set(int i, T x){ //设置第i个元素值为x

if (x==null)
throw new NullPointerException("x==null"); //抛出空对象异常
if (i>=0 && i<this.n)
this.element[i] = x;
else throw new java.lang.IndexOutOfBoundsException(i+"");//抛出序号越界异常
}
public int insert(int i, T x){ //插入x作为第i个元素

if (x==null)
throw new NullPointerException("x==null"); //抛出空对象异常
if (i<0) i=0; //插入位置i容错，插入在最前
if (i>this.n) i=this.n; //插入在最后
Object[] source = this.element; //数组变量引用赋值，source也引用element数组
if (this.n==element.length) //若数组满，则扩充顺序表的数组容量
{
this.element = new Object[source.length*2]; //重新申请一个容量更大的数组
for (int j=0; j<i; j++) //复制当前数组前i-1个元素
this.element[j] = source[j];
}
for (int j=this.n-1; j>=i; j--) //从i开始至表尾的元素向后移动，次序从后向前
this.element[j+1] = source[j];
this.element[i] = x;
this.n++;
return i; //返回x序号
}
public int append(T x){ //在线性表最后插入x元素

return this.insert(this.n, x);
}
public T remove(int i){
//删除第i个元素并返回被删除对象
if (this.n>0 && i>=0 && i<this.n)
{
T old = (T)this.element[i]; //old中存储被删除元素
for (int j=i; j<this.n-1; j++)
this.element[j] = this.element[j+1]; //元素前移一个位置
this.element[this.n-1]=null; //设置数组元素对象为空，释放原引用实例
this.n--;
return old; //返回old局部变量引用的对象，传递对象引用
}
return null;

}
public void removeAll(){
//删除线性表所有元素
this.n=0;
}
public int search(T key){ //查找，返回首次出现的关键字为key的元素的位

System.out.print(this.getClass().getName()+".indexOf("+key+")，");
for (int i=0; i<this.n; i++)
{
if (key.equals(this.element[i])) //执行T类的equals(Object)方法，运行时多态
return i;
}
return -1;
}
public String toString(){

String str=this.getClass().getName()+"("; //返回类名
if (this.n>0)
str += this.element[0].toString(); //执行T类的toString()方法，运行时多态
for (int i=1; i<this.n; i++)
str += ", "+this.element[i].toString(); //执行T类的toString()方法，运行时多态
return str+") ";
}

public static void main (String args[])
{

SeqList<Integer> list=new SeqList<Integer>(20);
Integer values[]={10,1,2,3,4,5,6,7,8,9};
SeqList<Integer> list1=new SeqList<Integer>(values);
System.out.print("输出顺序表:");
System.out.println(list1.toString());
System.out.println("顺序表List是否为空"+list.isEmpty()+",List1是否为空"+list1.isEmpty());
System.out.println("list的长度"+list.length()+",list1的长度"+list1.length());
System.out.println("返回list1的第7个元素是:"+list1.get(6));

System.out.println("重新设置第5个元素为19:");
list1.set(4, 19);
list1.insert(2, 100);
list1.append(20);
System.out.println("删除8:"+list1.remove(8));
System.out.print("修改后的顺序表:");
System.out.println(list1.toString());
list1.removeAll();
System.out.println("删除后的顺序表："+list1.toString()); //为空
System.out.println("寻找元素50:"+list1.search(50));

}
}

（2）
a)

package ex1;

public class Del {
public Del(int i,int k)
{
String values[]={"A","b","C","d","e","f","g","h"};
int n =values.length;
for(int j=0;j<n;j++){
System.out.print(values[j]+" ");}
System.out.println();

for(int j=i+k;j<n;j++){
values[j-k]=values[j];}
n=n-k;

for(int j=0;j<n;j++){
System.out.print(values[j]+ " " );}
System.out.println();

}
public static void main(String args[]){
new Del(2,3);
}
}

b)

package ex1;

public class Del2 {
public Del2(int i,int k){
String values[]={"A","x","y","y","b","c","h"};
SeqList<String> list=new SeqList<String>(values);
System.out.println(list.toString());

for(int j=1;j<=k;j++)
{ list.remove(i);}
System.out.println(list.toString());

}
public static void main(String args[])
{
new Del2(2,3);
}
}

c)
package ex1;

public class Merge {
public Merge(){

Integer values1[]={1,3,5,11};
SeqList<Integer> list1=new SeqList<Integer>(values1);
Integer values2[]={2,4,5,22,23};
SeqList<Integer> list2=new SeqList<Integer>(values2);

SeqList<Integer> list3=new SeqList<Integer>();

int i=0,j=0;

while(i<list1.length()&&j<list2.length())
{
if(list1.get(i)<list2.get(j)){
list3.append(list1.get(i));
i++;
}
else{
list3.append(list2.get(j));
j++;
}
}

while(i<list1.length()){
list3.append(list1.get(i));
i++;
}

while(j<list2.length())
{
list3.append(list2.get(j)) ;
j++;
}

System.out.println(list1.toString());
System.out.println(list2.toString());
System.out.println(list3.toString());
}

public static void main(String args[]){
new Merge();

}
}

d)
package test;
import ex1.SeqList;
public class Intersection {

public Intersection(){

Integer values1[]={1,3,5,11,12,13,22,23,50};
SeqList<Integer> list1=new SeqList<Integer>(values1);
Integer values2[]={2,4,5,12,19,20,22,23,};
SeqList<Integer> list2=new SeqList<Integer>(values2);

SeqList<Integer> list3=new SeqList<Integer>();

int i=0,j=0;

while(i<list1.length()&&j<list2.length())
{
if(list1.get(i)<list2.get(j)){

i++;
}
else if(list1.get(i)>list2.get(j)){
j++;
}

else
{ list3.append(list1.get(i));
i++;
j++;

}

}

System.out.println(list1.toString());
System.out.println(list2.toString());
System.out.println(list3.toString());

}

public static void main(String args[])
{
new Intersection();
}
}

3.
（1）
package ex1;

public class Josephus {

public Josephus(int n, int k, int m)
{
System.out.println("Josephus("+n+","+k+","+m+")，");
SeqList<String> list = new SeqList<String>(n);
//创建顺序表实例，元素类型是数字字符，只能排到n=9,否则达不到效果
for (int i=0; i<n; i++)
list.append((char)('1'+i)+""); //顺序表尾插入，O(1)
// System.out.println(list.toString()); //输出顺序表的描述字符串，O(n)

int i = k; //计数起始位置
while (list.length()>1) //多于一个元素时循环，计数O(1)
{
i = (i+m-1) % list.length(); //按循环方式对顺序表进行遍历,圆桌循环
System.out.print("出列"+list.remove(i).toString()+"，"); //删除i位置对象，O(n)

// System.out.println(list.toString());

}
System.out.println("出列"+list.get(0).toString());//get(0)获得元素，O(1)
}

public static void main(String args[])
{
new Josephus(9,1,3);
}

}

（2）
package test;

import ex1.SeqList;

public class JosephusA {

public JosephusA(int n, int k, int m)
{
System.out.println("Josephus("+n+","+k+","+m+")，");
SeqList<Integer> list = new SeqList<Integer>(n);
//创建顺序表实例，元素类型是数字字符，只能排到n=9,否则达不到效果
for (int i=0; i<n; i++)
list.append(i); //顺序表尾插入，O(1)
// System.out.println(list.toString()); //输出顺序表的描述字符串，O(n)

int i = k; //计数起始位置
while (list.length()>1) //多于一个元素时循环，计数O(1)
{
i = (i+m-1) % list.length(); //按循环方式对顺序表进行遍历,圆桌循环
System.out.print("出列"+list.remove(i).toString()+"，"); //删除i位置对象，O(n)

// System.out.println(list.toString());

}
System.out.println("出列"+list.get(0).toString());//get(0)获得元素，O(1)
}

public static void main(String args[])
{
new JosephusA(15,2,9);
}

}

第二部分：
（4）、
package ex2;

public class Node<T> {

public T data; //数据域
public Node<T> next; //地址域，后继结点

//构造结点
public Node(T data,Node<T> next){

this.data =data;
this.next=next;
}

//构造空结点
public Node(){

this(null,null);
}

//描述字符串
public String toString(){

return this.data.toString();
}
}

package ex2;

public class SinglyList<T> {

public Node<T>head;

//构造空单链表
public SinglyList()
{
head=new Node<T>();
}

//构造单链表，由values数组数组提供元素
public SinglyList(T[] values)
{
this();
Node<T>rear=this.head;
for(int i=0;i<values.length ;i++)
{
rear.next=new Node<T>(values[i],null);
rear=rear.next;
}
}

public boolean isEmpty() //判断线性表是否空
{
return this.head.next ==null;
}