java

19941021

浏览: 6009 次
性别:
来自: 长沙

最近访客更多访客>>

wy150150

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

java数据结构之单链表

java 数据结构单链表

[b][/b][color=green][/color][size=large][/size]     首先和大家分享一下为何要引入链表，其和我们所熟知的数组有何异同。
      如果大家再能补充一下，我将不胜感激。
                         数组与链表的联系与区别
      数据结构：线性结构，树状结构，网状结构，集合。
      数据的存储结构：顺序存储，链接存储

      联系：两者都是用来存储数据，而且体现出数据之间的联系。
      区别：
               数组中的数据都是顺序存储，只适合处理线性结构，而链表为链接存储，可以处理四种结构的数据

               顺序存储结构(数组)的优缺点：
                      优点：逻辑上相邻的元素，物理位置也是连续的(静态存储)，因此表示方法简单直观，利用下标可随机访问结构
                              中的任何元素
                      缺点：(1)要求存储空间连续，这样对于分散的空间难于利用
                (2)数组的长度是固定的，分配空间按最大数据长度，这样容易导致空间浪费，有时也会出现长度小数据溢出
                (3)对数组中的元素进行插入或删除时，需要把插入或删除后的点的数据进行移动，很麻烦
                链接存储结构(链表)的优缺点：
                     优点：(1)逻辑上相邻的元素，物理位置不需要连续(动态存储)，利用指针属性来表示数据之间的逻辑关系
                              提高空间的利用率
               (2)不是一次性为所有数据元素分配空间，而是以结点为单位，动态的为每一个结点分配空间
               (3)对链表存储的元素进行插入或删除时不需要把它后面的点都移动，变动小
                    缺点：(1)链表是由结点组成的非连续的数据结构，结点通过指针相连，访问时需要从链表头开始访问
                                  因此不能随机访问每一个结点，不适合进行大量的数据查找
               (2)数据属性较简单时，每个指针属性的存储占用空间大

    链表以结点为单位构成（数据和指针）；
    链表有单链表，双链表，循环链表之分：

    下面是三者的图示有助于大家理解：
    单链表：[img][/img]

双向链表：[img][/img]

循环链表：[img][/img]

    这里我先说一下单链表：

     //单链表结点类：

    public class Node { //定义结点类
Object num,name,score; //结点中的数据属性
Node next;    //结点中指针的属性，指向下一个Node对象的引用
public Node(Object obj1,Object obj2,Object obj3){
num=obj1; name=obj2;score=obj3;next=null;
}
    }

    //单链表队列的创建

    public class List {
Node head,tail; //定义表头结点与表尾结点对象的引用名
String Lname; //定义链表名
    //构造方法，创建一个空链表时对头，尾结点及链表名赋值
public List(String str){
Lname=str;head=null;tail=null;
}
//若用户没给链表对象名，List作为默认名
public List(){
Lname="List";head=null;tail=null;
}
/**
* @param 添加结点n到链表头部
*
*/
public void appendToFront(Node n){
if(head==null){
head=n;tail=n; //链表为空，添加第一个结点到链表中
}else{
n.next=head; head=n;
}
}
/**
* @param 添加节点n到链表尾部
*
*/
public void appendToTail(Node n){
if(head==null){
head=n;tail=n; //链表为空，添加第一个结点到链表中
}else{
tail.next=n; tail=n;
}
}

/**
* @param 遍历整个链表
*
*/
public void visitAllNode(){
Node p=head; //设p为head结点的引用
System.out.println(this.Lname);
if(p==null) System.out.println("该链表为空链表");
else
while(true)
{
System.out.println(p.num.toString()+"\t"+p.name.toString()+"\t"+p.score.toString()
+"->");
if(p.next==null) break; //再没有需要访问的结点
p=p.next; //设p为下一个结点的引用
}
}
/**
* @param i:得到的结点索引
*
*/
public Node getNode(int i){
//查找链表中第i个结点
Node p=head; int j=1; //设p为head结点的引用
while(j<i){
if(p.next==null) break;
p=p.next;// 扫描下一个结点
j++;
}
if(j==i) return p;
else{
System.out.println("链表中不存在第+“i"+"个结点");
return null;
}

}

/**
* @param 查找链表中第j个数据属性的值为obj的结点
*
*/
public Node getNode(Object obj,int j){
Node p=head; j=1; //设p为head结点的引用
if(j==1||j==2||j==3)
while(p!=null){
if(j==1){
if(p.num.equals(obj)) break;
}
if(j==2){
if(p.num.equals(obj)) break;
}
if(j==3){
if(p.num.equals(obj)) break;
}
}
else p=null;
if(p==null) System.out.println("查找无第"+j+"个数据属性值为"+obj+"的结点");
return p;
}
/**
* @param k:查找其前趋借点
*
*/
public Node getPreNode(Node k){
//查找链表中k结点的前趋结点
Node p=head,pre=head; //查找开始时，设p与pre都是head的引用
if(k==p||p==null){    //空链表或只有一个结点的链表均无前趋结点
System.out.println("链表中无此结点");
return null;
}else{
while(k!=p){
if(p.next==null) break;
pre=p;p=p.next;
}
if(k==p) return pre;
else{
System.out.println("链表中"+k+"结点前无结点");
return null;
}
}

}
/**
* @param i:在指定索引下插入对象
*
*/
public void insert(Node n,int i){
//添加结点n到链表中第i个结点之后
Node p=getNode(i);
if(p!=null)
if(p.next==null){ //插入的结点n为链表尾结点
p.next=n;tail=n;
}else{
n.next=p.next;p.next=n; //插入结点n到链表p结点之后
}
}
public void insert(Node n,Object obj,int j){
//添加结点n到链表中第j个数据属性的值为obj的结点之后
Node p=getNode(obj,j);
if(p!=null)
if(p.next==null){
p.next=n;tail=n;
}else{
n.next=p.next;p.next=n; //插入结点n到链表p结点之后
}
}
/**
* @param i:在指定索引下删除对象
*
*/
public void delete(int i){
Node p=getNode(i),pre=null;   //得到i结点
if(p!=null){
if(i==1)
if(p.next!=null)
head=p.next;    //删除第一个结点
else head=tail=null; //设此链为空链
else{
pre=getPreNode(p); //得到i结点的前趋结点
if(p.next==null){
pre.next=null;tail=pre;
}else
pre.next=p.next; //结点为中间结点，被删除
}
}

}
public void delete(Object obj,int j){
//删除链表中第j个数据属性的值我为obj的结点
Node p=getNode(obj,j),pre=null; //得到第j个数据属性的值为obj的结点p
if(p!=null){
if(p==head)
if(p.next!=null)
head=p.next;
else head=tail=null;
else{
pre=getPreNode(p);
if(p.next==null){
pre.next=null;tail=pre;
}
else pre.next=p.next;
}
}
}
public void deleteAll(){
//删除链表中的所有结点，使链表为空
head=null;tail=null;
}
/**
* @param i:在指定索引下修改对象
*
*/
public void updateNode(int i,Object obj,int j){
Node p=getNode(i);    //得到第i个结点
if(p==null) System.out.println("无第"+j+"个结点");
else
switch(j){ //根据j值修改数据属性值为obj
case 1: p.num=obj;break;
case 2: p.name=obj;break;
case 3: p.score=obj;break;
default: System.out.println("无第"+j+"个数据属性，不修改");
}
}
public List listSort(int j){
/**
* 对链表中的结点从小到大进行排序
* 使用插入法对链表中的结点按第j个数据属性值从小到大排序
*/
List f2=new List("f2list");
if(head==null)   return f2;
if(j==1||j==2||j==3){
System.out.println("需要排序的链表是："+Lname);
//得到链表f1的第一个结点
Node pp=new Node(head.num,head.name,head.score);
if(head.next==null)
System.out.println("该链表是空链表或只有一个结点，不排序");
else{
Node f1p=head.next,f2p=null; //f1p为链表f1结点的引用
f2.appendToFront(pp); //插入到f2链表中的f1链表的第一个pp结点
String str1="",str2="";int i;
//排序操作
while(true){
//得到链表f1的结点
Node p=new Node(f1p.num,f1p.name,f1p.score);
f2p=f2.head;i=1; //设为链表f2的第i个结点
if(j==1){
str1=String.valueOf(p.num);
str2=String.valueOf(f2p.num);
}
if(j==2){
str1=String.valueOf(p.name);
str2=String.valueOf(f2p.name);
}
if(j==3){
str1=String.valueOf(p.score);
str2=String.valueOf(f2p.score);
}
//遍历链表f2，判断结点p插入到链表f2的位置
while(str1.compareTo(str2)>=0&&f2p.next!=null){
i++;f2p=f2p.next;
if(j==1) str2=String.valueOf(f2p.num);
if(j==2) str2=String.valueOf(f2p.name);
if(j==3) str2=String.valueOf(f2p.score);
}
if(str1.compareTo(str2)<=0){
if(f2.head.equals(f2p))
f2.appendToFront(p);
else f2.insert(p, i-1);
}
else f2.insert(p,i);
if(f1p.next==null) break;
f1p=f1p.next;
}
}
}
else
{
System.out.println("无第j个数据属性，不能排序");
}
return f2;
}
}

   //链表程序测试类

public class Try {
public static void main(String args[]){
Integer n1=new Integer(1001), n2=new Integer(1008);
Integer n3=new Integer(1003), n4=new Integer(1002);
Integer n5=new Integer(1009), n6=new Integer(1005);

//创建浮点型对象
Double s1=new Double(89.0),s2=new Double(64.5),s3=new Double(90.0);
Double s4=new Double(79.0),s5=new Double(96.5),s6=new Double(80.0);
//创建结点对象
Node node1=new Node(n1,"Li1",s1),node2=new Node(n2,"Li2",s2);
Node node3=new Node(n1,"Li3",s1),node4=new Node(n2,"Li4",s2);
Node node5=new Node(n1,"Li5",s1),node6=new Node(n2,"Li6",s2);
//创建f1链表对象
List f1=new List("f1List");
//结点插入到f1链表头部
f1.appendToFront(node1);f1.appendToFront(node2);f1.appendToFront(node3);
//结点插入到f2链表尾部
List f2=new List("f2List");
f2.appendToFront(node4);f2.appendToFront(node5);f2.appendToFront(node6);

//打印f1链表中的所有结点
f1.visitAllNode(); System.out.println();
//打印f2链表中的所有结点
f2.visitAllNode(); System.out.println();

}

}

下一篇是双链表队列的创建