JAVA数据结构——单链表的操作.doc

单链表的操作方法一：package ch02;(1)建立结点类Node.javapublic 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;（2）建立链表及操作LinkList.javapackage ch02;import java.util.Scanner;public class LinkList implements IListpublic Node head;/单链表的头指针/构造函数初始化头结点public LinkList()head=new Node();/构造函数构造长度为n的单链表public LinkList(int n,boolean Order) throws Exceptionthis();if(Order)create1(n); /头插法顺序建立单链表elsecreate2(n); /尾插法逆序建立单链表/头插法顺序建立单链表public void create1(int n) throws ExceptionScanner sc=new Scanner(System.in);System.out.println(请输入结点的数据（头插法）：);for(int i=0;in;i+)insert(0,sc.next();/尾插法逆序建立单链表public void create2(int n) throws ExceptionScanner sc=new Scanner(System.in);System.out.println(请输入结点的数据（尾插法）：);for(int i=0;in;i+)insert(length(),sc.next();/将链表置空public void clear()head.data=null;head.next=null;/判断链表是否为空public boolean isEmpty()return head.next=null;/返回链表长度public int length()Node p=head.next;int length=0;while(p!=null)p=p.next;length+;/返回P不空长度length加1return length;/读取并返回第i个位置的数据元素public Object get(int i) throws Exception Node p=head.next;int j;/从首结点开始向后查找，直到p指向第i个结点或者p为nullfor(j=0;ji|p=null)/i不合法时抛出异常throw new Exception(第+i+个数据元素不存在);return p.data;/插入x作为第i个元素public void insert(int i, Object x) throws ExceptionNode p=head;int j=-1;/寻找第i个结点的前驱i-1while(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 ExceptionNode p=head;int j=-1;while(p!=null&ji-1|p.next=null)throw new Exception(删除位置不合法);p.next=p.next.next;/返回元素x首次出现的位序号public int indexOf(Object x) Node p=head.next;int j=0;while(p!=null&!p.data.equals(x)p=p.next;j+;if(p!=null)return j;else return -1;public void display()Node p=head.next;while(p!=null)if(p.next=null)System.out.print(p.data);else System.out.print(p.data+);p=p.next; (3)建立测试类Test.javappublic class test public static void main(String args) throws Exception / TODO Auto-generated method stubScanner sc=new Scanner(System.in);boolean or;int xz,xx;System.out.println(请选择插入的方法：0、头插法，1、尾插法);xz=sc.nextInt();if(xz!=0)or=true;elseor=false;System.out.println(请插入的结点的个数：);xx=sc.nextInt();LinkList L=new LinkList(xx,or);System.out.println(建立的链表为：);L.display();System.out.println();System.out.println(链表的长度：+L.length();System.out.println(请输入查找的结点的数据：);Object x=sc.next();int position=L.indexOf(x);System.out.println(结点的数据为：+x+的位置为：+position);System.out.println(请输入删除的结点的位置：);int sr=sc.nextInt();L.remove(sr);L.display();System.out.println();System.out.println(链表的长度：+L.length();方法二（引入get和set方法）Package sy;import java.util.Scanner;/单链表的结点类public class Node private Object data; / 存放结点值private Node next; / 后继结点的引用public Node() / 无参数时的构造函数this(null, null);public Node(Object data) / 构造值为data的结点this(data, null);public Node(Object data, Node next) /构造值为data和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 void setNext(Node next) this.next = next; /实现链表的基本操作类public 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);/ 生成新结点,插入到表头 /返回带头结点的单链表中第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或者大于表长减1throw new Exception(第 + i + 个元素不存在);/ 抛出异常return p.getData(); / 返回结点p的数据域的值 /在带头结点的单链表中的第i个数据元素之前插入一个值为x的元素 public 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); / 删除带头结点的第i个数据元素。其中i取值范围为：0ilength()- 1,如果i值不在此范围则抛出异常public void remove(int i) throws Exception Node p = head;/ 初始化p为头结点,j为计数器int j = -1;while (p.getNext() != null & j i - 1 | p.getNext() = null) / i小于0或者大于表长减1throw new Exception(删除位置不合理);/ 输出异常p.setNext(p.getNext().getNext();/ 删除结点 / 输出线性表中的数据元素public void display() Node p = head.getNext();/ 取出带头结点的单链表中的首结点元素while (p != null) System.out.print(p.getData() + );/ 输出数据元素的值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(); 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.d