java数据结构典型题

一、 顺序表

}

public void remove(int i) throws

if(i<0||i>curLen-1)

throw new Exception(\删除位置不合法

interface IList{ }

< SqList.java>

public class SqList implements IList{

private Object[] listElem; private int curLen;

public SqList(int maxSize){ }

public void clear(){ }

public boolean isEmpty(){ }

public int lenght(){ }

public Object get(int i) throws Exception{

if(i<0||i>curLen-1)

throw new Exception(\第\+i+\个元素return curLen; return curLen==0; curLen=0; curLen=0;

listElem=new Object[maxSize]; public void clear(); public boolean isEmpty();

public Object get(int i) throws

public void insert(int i,Object x) throws public void remove(int i) throws public int indexOf(Object x); public void display();

Exception{

\);

while(j

public static void main(String[] args)

SqList L=new SqList(50); L.insert(0,'a'); L.insert(1,'b'); L.insert(2,'c'); L.insert(3,'d'); L.insert(4,'e');

int order=L.indexOf('c'); if(order!=-1)

System.out.println(\顺序表中第一次

j++; return j; return-1; } if(j

public int indexOf(Object x) {

int j=0;

Exception; Exception; Exception;

for(int j=i;j

listElem[j]=listElem[j+1]; curLen--;

public void display(){

for(int j=0;j

System.out.print(listElem[j]+\); System.out.println();

throws Exception{

不存在\); return listElem[i];

}

public void insert(int i,Object x) throws

if(curLen==listElem.length)

throw new Exception(\顺序表已满\); if(i<0||i>curLen)

throw new Exception(\插入位置不合法

出现的值为‘c’的数据元素的位置为：\+order); else

System.out.println(\此顺序表中不包

含值为‘c’的数据元素！\); L.remove(2); \);

顺序表中第一次出现的值为‘c’的数据元素的位置为：2 删除后的顺序表为： abde

System.out.println(\删除后的顺序表为：L.display(); }}

Exception{

\);

for(int j=curLen;j>i;j--)

listElem[j]=listElem[j-1]; listElem[i]=x; curLen++;

- 1 -

二、 链表 Exception { Scanner sc=new Scanner(System.in);

for(int j=0;j

insert(length(),sc.next()); }

interface IList{ public void clear(); public boolean isEmpty();

public Object get(int i) throws

public void insert(int i,Object x) throws public void create2(int n)throws {

Scanner sc=new Scanner(System.in); Exception

Exception; Exception; public void remove(int i) throws Exception;

public int indexOf(Object x); public void display(); public void nizhi();

}

< Node.java > public class Node { private Object data; private 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; } public Object getData(){

return data; } public Node getNext() { return next; }

public void setData(Object data) { this.data=data; }

public void setNext(Node next)

{ this.next=next; } } < LinkList.java> import java.util.*;

public class LinkList implements IList { private Node head; public LinkList(){ head=new Node();

}

public LinkList(int n,boolean Order)throws Exception{

this(); if(Order) create1(n); else

create2(n); }

public void create1(int n)throws

for(int j=0;j

insert(0,sc.next()); }

public void clear(){

head.setData(null); head.setNext(null); }

public boolean isEmpty(){ return head.getNext()==null; } public int length(){

Node p=head.getNext(); int length = 0; while(p!=null) {

p=p.getNext(); ++length; }

return length;

}

public Object get(int i) throws Exception { Node p=head.getNext(); int j=0;

while(p!=null&&j

p=p.getNext(); ++j; }

if(j>i||p==null)

{ throw new Exception(\第\+i+\个元素不存在\); }

return p.getData(); }

public void insert(int i,Object x)throws Exception { Node p=head; int j=-1;

while(p!=null&&j

++j; } if(j>i-1||p==null)

throw new Exception(\插入位置不合法\); Node s=new Node(x); s.setNext(p.getNext()); p.setNext(s);

}

public void remove (int i)throws Exception { Node p=head;

- 2 -

int j=-1;

while(p.getNext()!=null&&j

++j; }

if(j>i-1||p.getNext()==null)

import java.util.*; public class test {

public static void main(String[] args)

int a;

throws Exception{

System.out.println(\请输入5个结点值：\); LinkList L=new LinkList(5,true); System.out.println(\插入的字符为：\); intx=new Scanner(System.in).nextInt(); System.out.println(\插入的位置为：\); inty=newScanner(System.in).nextInt();

L.display();

System.out.println(\单链表的长度为：\); a=L.length();

System.out.println(a);

System.out.println(\所删除字符的结点值

throw new Exception(\删除位置不合法\); p.setNext(p.getNext().getNext()); } public int indexOf(Object x) { {

Node p=head.getNext(); Node q;

head.setNext(null); while(p!=null) { q=p.getNext(); }}

public static void main(String[] args) throws Exception{

int n=10;

LinkList L=new LinkList(); for(int i=0;i

p.setNext(head.getNext()); head.setNext(p); p=q;

Node p=head.getNext(); int j=0;

while(p!=null&&!p.getData().equals(x)) { p=p.getNext();

++j; } return j; return -1; } if(p!=null) else

L.insert(y,x);

public void display(){

Node node=head.getNext(); while(node!=null)

{ System.out.print(node.getData()+\); }

System.out.println();} public void nizhi()

node=node.getNext();

为：\);

Int n=new Scanner(System.in).nextInt();

L.remove(n); L.display();

System.out.println(\请输入要查询的结点

值:\); Int i=new Scanner(System.in).nextInt();

if(0

System.out.println(\位置\+i+\的元素的

值是：\+L.get(i)); }

请输入5个结点值： a b c d e 插入的字符为： 1

插入的位置为： 2

a b 1 c d e 单链表的长度为： 6

所删除字符的结点值为： 2

a b c d e

请输入要查询的结点值: 3

位置3的元素的值是：d 实现单链表逆置

else

System.out.println(\位置\+i+\的元素不System.out.println(\实现单链表逆置\); L.nizhi(); L.display(); }}

存在\);

System.out.println(\删除后的单链表表为：\); }}

- 3 -

L.display();

e d c b a

三、 栈

public interface IStack {

public class SqStack implements IStack{

private Object[] stackElem; private int top;

public SqStack(int maxSize) { top=0; }

public int length(){ }

public void push(Object x) throws { if(top==stackElem.length)

throw new Exception(\栈已满\); else

stackElem[top++]=x; } return top; } if(!isEmpty())

return stackElem[top-1]; return null; else

public Object peek(){

stackElem=new Object[maxSize]; } top=0; } return top==0; public void clear(){ public boolean isEmpty(){ public void clear(); public boolean isEmpty(); public int length(); public Object peek();

public void push(Object x) throws public Object pop(); }

public class teststack {

public static void main(String[] args)

SqStack S = new SqStack(100); //

throws Exception {

初始化一个新的容量为100的顺序栈 Scanner sc=new Scanner(System.in);

System.out.print(\请输入顺序栈的长度:\); int n=sc.nextInt();

System.out.println(\请输入顺序栈中的各个数据元素值(数字):\); for(int i=0;i

S.push(sc.nextInt()); System.out.println(\建立的顺序栈

Exception;

中各元素为(从栈顶到栈底)： \); S.display();

System.out.println();

System.out.println(\请输入待入栈

的数据值e（数字）:\); int e=sc.nextInt();

S.push(e);

System.out.println(\入栈后的顺序

栈中各元素为(从栈顶到栈底):\); S.display();

System.out.println();

System.out.println(\取栈顶元素

值为： \); System.out.println(S.peek());

System.out.println(\去除栈顶元素后，顺序栈中各元素为(从栈顶到栈底)： \); S.pop(); }

S.display();

}

Exception

public Object pop() { if(isEmpty())

return null;

return stackElem[--top]; } else

public void display()

{ for(int i=top-1;i>=0;i--)

System.out.print(stackElem[i].toString(}}

)+\);

import java.util.*;

- 4 -

请输入顺序栈的长度:5

请输入顺序栈中的各个数据元素值(数字): 1 2 3 4 5

建立的顺序栈中各元素为(从栈顶到栈底)： 54321

请输入待入栈的数据值e（数字）: 9

入栈后的顺序栈中各元素为(从栈顶到栈底): 954321

取栈顶元素值为： 9

去除栈顶元素后，顺序栈中各元素为(从栈顶到栈底)： 54321