java数据结构典型题.doc

一、 顺序表interface IListpublic void clear();public boolean isEmpty();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 SqList implements IListprivate Object listElem;private int curLen;public SqList(int maxSize)curLen=0;listElem=new ObjectmaxSize;public void clear()curLen=0;public boolean isEmpty()return curLen=0;public int lenght()return curLen;public Object get(int i) throws Exceptionif(icurLen-1)throw new Exception(第+i+个元素不存在);return listElemi;public void insert(int i,Object x) throws Exceptionif(curLen=listElem.length)throw new Exception(顺序表已满);if(icurLen)throw new Exception(插入位置不合法);for(int j=curLen;ji;j-)listElemj=listElemj-1;listElemi=x;curLen+;public void remove(int i) throws Exceptionif(icurLen-1)throw new Exception(删除位置不合法);for(int j=i;jcurLen-1;j+)listElemj=listElemj+1;curLen-;public int indexOf(Object x)int j=0;while(jcurLen&!listElemj.equals(x)j+;if(jcurLen)return j;elsereturn-1; public void display()for(int j=0;jcurLen;j+)System.out.print(listElemj+); System.out.println();public static void main(String args) throws ExceptionSqList 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(顺序表中第一次出现的值为c的数据元素的位置为：+order);else System.out.println(此顺序表中不包含值为c的数据元素！);L.remove(2);System.out.println(删除后的顺序表为：);L.display();顺序表中第一次出现的值为c的数据元素的位置为：2删除后的顺序表为：abde二、 链表interface IListpublic void clear();public boolean isEmpty();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 nizhi();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; import java.util.*;public class LinkList implements IList private Node head;public LinkList()head=new Node();public LinkList(int n,boolean Order)throws Exceptionthis();if(Order)create1(n);elsecreate2(n); public void create1(int n)throws Exception Scanner sc=new Scanner(System.in);for(int j=0;jn;j+)insert(length(),sc.next(); public void create2(int n)throws Exception Scanner sc=new Scanner(System.in);for(int j=0;jn;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&ji|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&ji-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;int j=-1;while(p.getNext()!=null&ji-1|p.getNext()=null) throw new Exception(删除位置不合法);p.setNext(p.getNext().getNext(); public int indexOf(Object x)Node p=head.getNext();int j=0;while(p!=null&!p.getData().equals(x) p=p.getNext();+j; if(p!=null)return j;elsereturn -1; public void display()Node node=head.getNext();while(node!=null) System.out.print(node.getData()+ );node=node.getNext(); System.out.println();public void nizhi()Node p=head.getNext();Node q;head.setNext(null);while(p!=null) q=p.getNext();p.setNext(head.getNext();head.setNext(p);p=q;public static void main(String args) throws Exceptionint n=10;LinkList L=new LinkList();for(int i=0;in;i+) L.insert(i, i); L.insert(11, 22); L.remove(2); System.out.println(删除后的单链表表为：); L.display();import java.util.*;public class test public static void main(String args) throws Exceptionint a;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.insert(y,x);L.display();System.out.println(单链表的长度为：);a=L.length();System.out.println(a);System.out.println(所删除字符的结点值为：);Int n=new Scanner(System.in).nextInt();L.remove(n);L.display();System.out.println(请输入要查询的结点值:);Int i=new Scanner(System.in).nextInt();if(0i&i=a)System.out.println(位置+i+的元素的值是：+L.get(i);elseSystem.out.println(位置+i+的元素不存在);System.out.println(实现单链表逆置);L.nizhi();L.display(); 请输入5个结点值：a b c d e插入的字符为：1插入的位置为：2a b 1 c d e 单链表的长度为：6所删除字符的结点值为：2a b c d e 请输入要查询的结点值:3位置3的元素的值是：d实现单链表逆置e d c b a三、 栈public interface IStack public void clear();public boolean isEmpty();public int length();public Object peek();public void push(Object x) throws Exception;public Object pop(); public class SqStack implements IStackprivate Object stackElem;private int top;public SqStack(int maxSize) top=0;stackElem=new ObjectmaxSize; public void clear()top=0; public boolean isEmpty()return top=0;public int length()return top; public Object peek()if(!isEmpty()return stackElemtop-1;else return null;public void push(Object x) throws Exception if(top=stackElem.length)throw new Exception(栈已满);elsestackElemtop+=x; public Object pop() if(isEmpty()return null;elsereturn stackElem-top; public void display() for(int i=top-1;i=0;i-)System.out.print(stackElemi.toString()+);import java.util.*;public class teststack public static void main(String args) throws Exception SqStack S = new SqStack(100); / 初始化一个新的容量为100的顺序栈 Scanner sc=new Scanner(System.in); System.out.print(请输入顺序栈的长度:); int n=sc.nextInt(); System.out.println(请输入顺序栈中的各个数据元素值(数字):); for(int i=0;in;i+) S.push(sc.nextInt(); System.out.println(建立的顺序栈中各元素为(从栈顶到栈底)： ); 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(); 请输入顺序栈的长度:5请输入顺序栈中的各个数据元素值(数字):1 2 3 4 5建立的顺序栈中各元素为(从栈顶到栈底)： 54321请输入待入栈的数据值e（数字）:9入栈后的顺序栈中各元素为(从栈顶到栈底):954321取栈顶元素值为： 9去除栈顶元素后，顺序栈中各元素为(从栈顶到栈底)： 54321四、 (1) 队列（循环）public interface IQueue public void clear();public boolean isEmpty();public int length();public Object peek();public void offer(Object x) throws Exception;public Object poll(); public class CircleSqQueue private Object queueElem;private int front;private int rear;public CircleSqQueue(int maxSize)front=rear=0;queueElem=new ObjectmaxSize;public void clear()front=rear=0;public boolean isEmpty()return front=rear;public int length()return(rear-front+queueElem.length)%queueElem.length;public Object peek()if(front=rear)return null;elsereturn queueElemfront;public void offer(Object x) throws Exceptionif(rear+1)%queueElem.length=front)throw new Exception(队列已满);elsequeueElemrear=x;rear=(rear+1)%queueElem.length;public Object poll()if(front=rear)return null;elseObject t=queueElemfront;front=(front+1)%queueElem.length;return t;public void display()if(!isEmpty()for(int i=front;i!=rear;i=(i+1)%queueElem.length)System.out.print(queueElemi.toString()+); elseSystem.out.println(此队列为空);import java.util.*;public class test public static void main(String args) throws Exception CircleSqQueue S = new CircleSqQueue(100); / 初始化一个新的容量为100的顺序栈 Scanner sc=new Scanner(System.in); System.out.print(请输入循环队列的长度:); int n=sc.nextInt(); System.out.println(请输入循环队列中的各个数据元素值(数字):); for(int i=0;in;i+) S.offer(sc.nextInt(); System.out.println(建立的循环队列中各元素为： ); S.display(); System.out.println(); System.out.println( 取队首元素值为： ); System.out.println(S.peek(); System.out.println(去除队首元素后，循环队列中各元素为： ); S.poll(); S.display(); 请输入循环队列的长度:5请输入循环队列中的各个数据元素值(数字):1 2 3 4 5建立的循环队列中各元素为： 12345 取队首元素值为： 1去除队首元素后，循环队列中各元素为： 2345（2）队列（链式）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; public interface IQueue public void clear();public boolean isEmpty();public int length();public Object peek();public void offer(Object x) throws Exception;public Object poll(); import java.util.Scanner;public class LinkQueue implements IQueueprivate Node front;private Node rear;public LinkQueue()front=rear=null; public void clear()front=rear=null; public boolean isEmpty() return front=null; public int length() if(!isEmpty() Node p=front;int length = 0;while(p!=null) p=p.getNext(); +length; return length(); public Object peek()if(front!=null)return front.getData();elsereturn null;public void offer(Object x) Node p=new Node(x);if(front!=null)rear.setNext(p);rear=p; elsefront=rear=p; public Object poll()if(front!=null)Node p=front;front=front.getNext();if(p=rear)rear=null;return p.getData(); elsereturn null; public void display()Node p=front;while(p!=null)System.out.print(p.getData().toString()+ );p=p.getNext(); System.out.println(); public static void main(String args) throws ExceptionScanner sc=new Scanner(System.in);LinkQueue L=new LinkQueue(); System.out.print(请输入链队列的长度:); int n=sc.nextInt(); System.out.println(请输入链队列中的各个数据元素值:);for(int i=0;in;i+) L.offer(sc.nextInt(); System.out.println(建立的链队列中各元素为： ); L.display(); System.out.println(); System.out. println( 取队首元素值为： ); System.out.println(L.peek(); System.out.println(去除队首元素后，链队列中各元素为： ); L.poll(); L.display(); 答案与循环队列相同五、二叉树class BiTreeNode private Object data;private 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; public Object getData() return data; public void setData(Object data) this.data = data; public BiTreeNode getLchild() return lchild; public void setLchild(BiTreeNode lchild) this.lchild = lchild; public BiTreeNode getRchild() return rchild; public void setRchild(BiTreeNode rchild) this.rchild = rchild; public class BiTree protected BiTreeNode root; public BiTree() root = null; public BiTree(BiTreeNode root) this.root = root; public BiTree (String preOrder,String inOrder,int preIndex,int inIndex,int count) if(count0) char r=preOrder.charAt(preIndex); int i=0; for(;irDepth?lDepth:rDepth);return 0; public BiTreeNode getRoot() return root; public void setRoot(BiTreeNode root) this.root = root; public int leaf(BiTreeNode T) if (T = null)return 0;else int left = leaf(T.getLchild();int right = leaf(T.getRchild();if (T.getLchild() = null & T.getRchild() = null)return left + right + 1;elsereturn left + right;public class TestTree public static void main(String arg)String preStr=AB#CD#;BiTree T= new BiTree(preStr);BiTreeNode root=T.getRoot();System.out.println(先根遍历：);T.preRootTraverse(root);System.out.println();System.out.println(中根遍历：);T.inRootTraverse(root);System.out.println();System.out.println(后根遍历：);T.postRootTraverse(root);System.out.println();System.out.println(结点个数为：+T.countNode(root);System.out.println(叶子节点总数为：+T.leaf(root);System.out.println(深度为：+T.getDepth(root);先根遍历：ABCD中根遍历：BADC后根遍历：BDCA结点个数为：4叶子节点总数为：2深度为：3六、 图的遍历（邻接矩阵）调用队列 输出矩阵：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; public interface IQueue public void clear();public boolean isEmpty();public int length();public Object peek();public void offer(Object x) throws Exception;public Object poll(); import java.util.Scanner;public class LinkQueue implements IQueueprivate Node front;private Node rear;public LinkQueue()front=rear=null; public void clear()front=rear=null; public boolean isEmpty() return front=null; public int length() if(!isEmpty() Node p=front;int length = 0;while(p!=null) p=p.getNext(); +length; return length(); public Object peek()if(front!=null)return front.getData();elsereturn null;public void offer(Object x) Node p=new Node(x);if(front!=null)rear.setNext(p);rear=p; elsefront=rear=p; public Object poll()if(front!=null)Node p=front;front=front.getNext();if(p=rear)rear=null;return p.getData(); elsereturn null; public void display()Node p=front;while(p!=null)System.out.print(p.getData().toString()+ );p=p.getNext(); System.out.println(); public interface IGraph int getVexNum();int getArcNum();Object getVex(int v) throws Except