我的漫漫程序之旅

专注于JavaWeb开发
随笔 - 39, 文章 - 310, 评论 - 411, 引用 - 0
数据加载中……

单向链表的简单实现

要求:写一个示例程序,显示一个单链表.这个链表的功能:
1.在链表头插入一个数据项
2.在链表头删除一个数据项
3.遍历链表显示它的内容
实现代码如下:
package com;
/**
 * 结点类
 * 
@author zdw
 *
 
*/

class Link
{
    
//数据区域
    public int data;
    
//指针区域
    public Link next;
    
//构造一个数据为data的结点,默认指针为空
    public Link(int data)
    
{
        
this.data = data;
        next 
= null;
    }

    
//显示结点的数据
    public void displayLink()
    
{
        System.out.println(
"Data:" + data);
    }

}

/**
 * 链表类
 * 
@author zdw
 *
 
*/

class LinkList
{
    
//头结点
    private Link first;
    
//构造一个空的链表
    public LinkList()
    
{
        first 
= null;
    }

    
    
public void insertLink(int data)
    
{
        
//构造一个内容为data的结点
        Link newLink = new Link(data);
        
//将first中的地址赋予新建的结点指针区域中
        newLink.next = first;
        
//让first结点的指针指向newLink
        first = newLink;
    }

    
//判断LinkList是否为空
    public boolean isEmpty()
    
{
        
return first == null;
    }

    
    
public Link deleteLink()
    
{
        
//将first中保存到临时变量temp中
        Link temp = first;
        
//将下一个结点的指针地址转移到first中
        first = first.next;
        
return temp;
    }

    
    
public void displayLinkList()
    
{
        Link current 
= first;
        
while(current != null)
        
{
            current.displayLink();
            current 
= current.next;
        }

        System.out.println();
    }

}

/**
 * 测试类
 * 
@author zdw
 *
 
*/

public class LinkListApp
{
    
public static void main(String[] args)
    
{
        LinkList ll 
= new LinkList();
        ll.insertLink(
1);
        ll.insertLink(
2);
        ll.insertLink(
3);
        ll.insertLink(
4);
        System.out.println(
"linkList中的内容是:");
        ll.displayLinkList();
        
//LinkList不为空
        while(!ll.isEmpty())
        
{
            
//删除
            ll.deleteLink();
        }

        System.out.println(
"删除后的内容是:");
        ll.displayLinkList();
    }


}

现在要求为该程序加入按指定键查找和删除的方法.并加以测试.
代码如下:
package com;

/**
 * 结点类
 * 
 * 
@author zdw
 * 
 
*/

class Link
{
    
// 数据区域
    public int data;
    
// 指针区域
    public Link next;

    
// 构造一个数据为data的结点,默认指针为空
    public Link(int data)
    
{
        
this.data = data;
        next 
= null;
    }


    
// 显示结点的数据
    public void displayLink()
    
{
        System.out.println(
"Data:" + data);
    }

}


/**
 * 链表类
 * 
 * 
@author zdw
 * 
 
*/

class LinkList
{
    
// 头结点
    private Link first;

    
// 构造一个空的链表
    public LinkList()
    
{
        first 
= null;
    }


    
public void insertLink(int data)
    
{
        
// 构造一个内容为data的结点
        Link newLink = new Link(data);
        
// 将first中的地址赋予新建的结点指针区域中
        newLink.next = first;
        
// 让first结点的指针指向newLink
        first = newLink;
    }


    
// 判断LinkList是否为空
    public boolean isEmpty()
    
{
        
return first == null;
    }

    
//查找
    public Link find(int key)
    
{
        
//从第一个开始查找
        Link current = first;
        
while(current.data != key)
        
{
            
if(current.next == null)
                
return null;
            
else
                
return current.next;    
        }

        
return current;
    }

    
//用指定key删除
    public Link delete(int key)
    
{
        Link current 
= first;
        Link previous 
= first;
        
while(current.data != key)
        
{
            
if(current.next == null)
                
return null;
            
else
            
{
                previous 
= current;
                current 
= current.next;
            }

        }

        
if(current == first)
        
{
            first 
= first.next;
        }

        
else
        
{
            previous.next 
= current.next;
        }

        
return current;
    }

    
    
public Link deleteLink()
    
{
        
// 将first中保存到临时变量temp中
        Link temp = first;
        
// 将下一个结点的指针地址转移到first中
        first = first.next;
        
return temp;
    }


    
public void displayLinkList()
    
{
        Link current 
= first;
        
while (current != null)
        
{
            current.displayLink();
            current 
= current.next;
        }

        System.out.println();
    }

}


/**
 * 测试类
 * 
 * 
@author zdw
 * 
 
*/

public class LinkListApp
{
    
public static void main(String[] args)
    
{
        LinkList ll 
= new LinkList();
        ll.insertLink(
1);
        ll.insertLink(
2);
        ll.insertLink(
3);
        ll.insertLink(
4);
        System.out.println(
"linkList中的内容是:");
        ll.displayLinkList();
        
// LinkList不为空
        Link f = ll.find(3);
        
if(f != null)
        
{
            System.out.println(
"已经找到:" + f.data);
        }

        
else
        
{
            System.out.println(
"没有该项");
        }

        Link d 
= ll.delete(3);
        
if(d != null)
        
{
            System.out.println(
"成功删除:" + d.data);
        }

        
else
        
{
            System.out.println(
"没有该项");
        }

        System.out.println(
"删除后的内容是:");
        ll.displayLinkList();
    }


}



posted on 2007-12-29 12:08 々上善若水々 阅读(1749) 评论(0)  编辑  收藏 所属分类: 数据结构与算法


只有注册用户登录后才能发表评论。


网站导航: