顺序表和单链表
顺序表
public interface Ilist {
public void clear();
public boolean isEmpty();
public int length();
public Object get(int i) throws Exception;
public void insert(int i,Object x) throws Exception;
public void remove(int i) throws Exception;
public int indexOf(Object x);
public void display();
public void delete(int a)throws Exception;
public void delsame()throws Exception;
}
public class Sqlist implements Ilist {
private Object[] listElem;//线性表存储空间
private int curLen;//线性表当前长度
构造一个存储空间为maxSize的顺序表:
public Sqlist(int maxSize){
curLen=0;//置顺序表当前长度为0
listElem=new Object[maxSize];//为顺序表分配maxSize个存储单元
}
将顺序表置空:
public void clear() {
curLen=0;
}
判断顺序表是否非空
public boolean isEmpty() {
return curLen==0;
}
求顺序表中的数据元素的个数:
public int length() {
return curLen;
}
读取顺序表中的第i个数据元素:
public Object get(int i) throws Exception {
if(icurLen-1)
throw new Exception("第"+i+"个元素不存在");
return listElem[i];
}
顺序表的插入操作算法:
public void insert(int i, Object x) throws Exception{
if(curLen==listElem.length)//判断顺序表是否已满
throw new Exception("顺序表已满");
if(icurLen)//i不合法
throw new Exception("插入位置不合法");
for(int j=curLen;j>i;j--)
listElem[j]=listElem[j-1];//插入位置及其之后的所有数据元素后移一位 listElem[i]=x;//插入x
curLen++;//表长加1
}
顺序表的删除操作算法:
public void remove(int i) throws Exception {
if(icurLen-1)//i不合法 throw new Exception("删除位置不合法"); for(int j=i;j
listElem[j]=listElem[j+1];//被删除元素之后的所有数据元素左移一个存储位置 curLen--;//表长减1
}
顺序表的查找操作算法:
public int indexOf(Object x) {
} int j=0;//j指示顺序表中待比较数据元素,初始值指向顺序表第0个数据元素 while(j
顺序表数据元素的输出:
public void display() {
for(int j=0;j
System.out.print(listElem[j]+" ");
System.out.println();
}
public void delete(int a)throws Exception
{
for(int i=a;i
listElem[i]=listElem[i+1];
curLen--;
}
删除顺序表中相同的数据元素:
public void delsame()throws Exception
{
for(int i=0;i
for(int j=0;j
if(listElem[i].equals(listElem[j]))
delete(j);
}
}
}
import java.util.Scanner;
public class SqlistTest {
public static void main(String[] args) throws Exception{
Sqlist L=new Sqlist(20);
L.insert(0,1 );
L.insert(1, 3);
L.insert(2, 5);
L.insert(3, 2);
L.insert(4, 4);
L.insert(5, 6);
L.insert(6, -1);
L.insert(7,-21 );
L.insert(8, 54);
L.insert(9,100 );
System.out.println("输出顺序表中各元素的值为:");
L.display();
int i,x;
System.out.println("执行插入请输入i的值:"); i=new Scanner(System.in).nextInt(); System.out.println("请输入x的值:"); x=new Scanner(System.in).nextInt(); L.insert(i,x); System.out.println("输出插入后的顺序表中各元素的值为:"); L.display(); System.out.println("执行删除操作请输入i的值:"); i=new Scanner(System.in).nextInt(); L.remove(i);
System.out.println("输出删除之后的顺序表中各元素的值为:");
L.display();
System.out.println("执行查找操作请输入x的值:");
x=new Scanner(System.in).nextInt();
int order=L.indexOf(x);
if(order!=-1)
System.out.println("顺序表中第一次出现的值为"+x+"的数据元素的位置为:"+order);
else
System.out.println("此顺序表中不包含值"+x+"的数据元素!");
System.out.println("删除相同元素操作后顺序表的各元素为:");
L.delsame();
L.display();
}
}
单链表:
public interface Ilist {
public void create1(int n)throws Exception;
public void create2(int n)throws Exception;
public void clear();
public boolean isEmpty();
public int length();
public Object get(int i)throws Exception;
public void insert(int i,Object x)throws Exception;
public void remove(int i)throws Exception;
public int indexOf(Object x);
public void display();
}
结点类:
public class Node {
public Object data;//存放结点值
public Node next;//后继结点的引用
无参数的构造函数:
public Node(){
this(null,null);
}
带一个参数的构造函数:
public Node(Object data){
this(data,null);
}
带两个参数的构造函数:
public Node(Object data,Node next){
this.data=data;
this.next=next;
}
}
import java.util.Scanner;
public class LinkList implements Ilist{
public Node head;//单链表的头指针
单链表的构造函数
public LinkList(){
head=new Node();//初始化头指针
}
构造一个长度为n的单链表:
public LinkList(int n,boolean Order)throws Exception{
this();//初始化头结点
if(Order)
} create1(n);//用尾插法顺序建立单链表 else create2(n);//用头插法逆序建立单链表
用尾插法顺序建立单链表:
public void create1(int n)throws Exception{
}
} Scanner sc=new Scanner(System.in);//构造用于输入的对象 for(int j=0;j
用头插法逆序建立单链表:
public void create2(int n)throws Exception{
Scanner sc=new Scanner(System.in); //构造用于输入的对象
for(int j=0;j
System.out.println("请输入第"+j+"个元素");
insert(0,sc.nextInt());//生成新结点,插入到表头
}
}
将一个带头结点的单链表置空:
public void clear(){
head.data=null;
head.next=null;
}
判断带头结点的单链表是否非空:
public boolean isEmpty(){
return head.next==null;
}
求带头结点的单链表的长度:
public int length(){
Node p=head.next;//初始化,p指向首结点,length为计数器
int length=0;
while(p!=null){//从首结点开始向后查找,直到p为空
p=p.next;//指向后继结点
++length;//长度增1
}
return length;
}
读取单链表第i个结点:
public Object get(int i)throws Exception{
} Node p=head.next;//初始化,p指向首结点,j为计数器 int j=0; while(p!=null&&ji||p==null){ // i小于0或者大于表长减1时,即i不合法 throw new Exception("第"+i+"个元素不存在");//抛出异常 } System.out.println("第"+i+"元素的值为"+p.data); return p.data;//返回结点p的数据域值
在带头结点的单链表的第i个结点前插入一个值为x的新结点:
public void insert(int i,Object x)throws Exception{
Node p=head; //初始化p为头结点,j为计数器
int j=-1;
} while(p!=null&&ji-1||p==null)//i不合法 throw new Exception("插入位置不合法");//抛出异常 Node s=new Node(x);//生成新结点 s.next=p.next;//修改链,使新结点插入单链表 p.next=s;
删除带头结点的单链表的第i个结点:
public void remove(int i)throws Exception{
Node p=head; //初始化p为头结点,j为计数器
int j=-1;
while(p.next!=null&&j
p=p.next;
++j;
}
if(j>i-1||p.next==null){
throw new Exception("删除位置不合法");
}
p.next=p.next.next;//修改链指针,使待删除结点从单链表中脱离
}
在带头结点的单链表查找值为x的结点:
public int indexOf(Object x){
Node p=head.next; //初始化,p指向首结点,j为计数器
int j=0;
} while(p!=null&&!p.data.equals(x)){ //从首结点起查找,直到p.data的值为x或到达表尾 p=p.next;//指向下一个结点 ++j;//计数器的值增1 } if(p!=null) return j;//返回值为x的结点在单链表的位置 else return -1;//值为x的结点不在单链表,返回-1
输出单链表的所有结点:
public void display(){
Node node=head.next;//取出带头结点的单链表的首结点
while(node!=null){
System.out.print(node.data+" ");//输出结点的值
node=node.next;//取下一个结点
}
System.out.println();
}
}
import java.util.*;
public class LinkListTest extends LinkList {
public static void main(String[] args) throws Exception {
int n;
Scanner reader=new Scanner(System.in);
System.out.print("请输入n"); n=reader.nextInt(); LinkList L=new LinkList(); L.create2(n); System.out.println("输出单链表中各元素的值为:"); L.display(); int i,y; System.out.println("执行插入请输入i的值:"); i=new Scanner(System.in).nextInt(); System.out.println("请输入y的值:"); y=new Scanner(System.in).nextInt(); L.insert(i, y); System.out.println("输出插入后的单链表中各元素的值为:"); L.display(); System.out.println("执行删除操作请输入i的值:"); i=new Scanner(System.in).nextInt(); L.remove(i); System.out.println("输出删除之后的单链表中各元素的值为:"); L.display();
System.out.println("执行指定位置查找操作请输入i的值:");
i=new Scanner(System.in).nextInt();
L.get(i);
System.out.println("执行查找操作请输入y的值:");
y=new Scanner(System.in).nextInt();
int order=L.indexOf(y);
if(order!=-1)
System.out.println("单链表中第一次出现的值为"+y+"的数据元素的位置为:"+order); else
System.out.println("此单链表中不包含值"+y+"的数据元素!");
}
}
public class BiTreeNode {
public Object data;//结点的数据域
public BiTreeNode lchild,rchild;//左右孩子域
public BiTreeNode(){//构造一个空结点
this(null);
}
public BiTreeNode(Object data){//创造一棵左右孩子域为空的二叉树
this(data,null,null);
}
public BiTreeNode(Object data,BiTreeNode lchild,BiTreeNode rchild){//创造一棵数据域,左右孩子域都不为空的二叉树
this.data=data;
this.lchild=lchild;
this.rchild=rchild;
}
}