数据结构学习笔记之一:链表

许多人都知道链表(C语言)都是借助指针来实现链接的,同样许多人也知道java语言是没有指针的,所以很多人可能很理所当然的认为"java没有数据结构",我想这种想法是错误的.程序=算法+数据结构,任何语言都离不开数据结构(唉,这么简单一个道理我也是最近才悟出的,惭愧啊...).下面我就谈谈java语言的数据结构.

代码一:链表结构的java实现

    package listtest;

    public class ListNode {
           
            Object element;
            ListNode next;
                   
            ListNode(Object o,ListNode n)
            {
                    element=o;
                    next=n;
            }
           
            ListNode(Object o)
            {
                    this(o,null);
            }
    }

代码二:链表操作器的java实现


    package listtest;

    public class LinkedList {

            private ListNode header;
           
            LinkedList()
            {
                    header=new ListNode(null);
            }
           
            LinkedList(ListNode n)
            {
                    header=new ListNode(null,n);
            }
           
            /**
             * 判断链表是否为空
             * @return 链表是否为空的布尔值
             */
            boolean isEmpty()
            {
                    return header.next==null;
            }
           
            /**
             * 清空链表.
             * 注:此方法没有真正清除内存,清楚内存的任务交给java垃圾回收器去处理吧.^_^
             */
            void makeEmpty()
            {
                    header=null;
                    System.gc();
            }
           
            /**
             * 查找目标数据所在节点
             * @param o 目标数据
             * @return 保存目标数据节点
             */
            ListNode find(Object o)
            {
                    if(isEmpty())
                            return null;
                   
                    ListNode node = header.next;
                    while(node!=null)
                    {
                            if(node.element.equals(o))
                                    return node;
                           
                            node=node.next;
                    }
                    return null;
            }
           
            /**
             * 在节点node后面新建一个节点,该节点保存数据o
             * @param o 数据
             * @param node 插入节点
             */
            void insert(Object o,ListNode node)
            {
                    node.next=new ListNode(o,node.next);
            }
           
            /**
             * 删除目标数据的节点
             * @param o 目标数据
             */
            void remove(Object o)
            {
                    if(isEmpty())
                            return;
                   
                    ListNode node = header.next;
                    while(node!=null)
                    {
                            if(node.next.element.equals(o))
                            {
                                    node.next=node.next.next;
                                    return;
                            }
                            node = node.next;
                    }
            }
    }

完成...参考了<数据结构(C语言版)>(hjack借我D书,呵呵,沾点仙气)和<数据结构与算法分析--java语言描述>,不过感觉原作者写得罗嗦了点,所以自己整理了下(原著的java实现用了3个类,我觉得有点不必要).

接下来用链表解一道题.这道题是我去北电笔试的时候遇到的,当时做得乱七八糟(因为要求用C/C++做...晕...当时就投降了...).

题目是这样的:输入一串字符,分别统计各个字符的数目.(maybe大家都觉得很简单,,,但我当时确实不会...用力鄙视我吧...)

这题用了三个文件,其中两个分别是链表结构和链表操作器.

文件一:ListNode.java

    package list;


    public class ListNode {
           
            char element;        //当前字符
            int count;                //字符个数

            ListNode next;
           
            ListNode(char c,ListNode n)
            {
                    element = c;
                    count=1;
                    next=n;
            }
           
            ListNode(char c)
            {
                    this(c,null);
            }
    }

文件二:LinkedList.java

    package list;

    public class LinkedList {

            ListNode header;
           
            LinkedList()
            {
                    this(null);
            }
           
            LinkedList(ListNode n)
            {
                    header=new ListNode(' ',n);
            }
           
            boolean isEmpty()
            {
                    return header.next==null;
            }
           
            void makeEmpty()
            {
                    header=null;
            }
           
            ListNode find(char c)
            {
                    if(isEmpty())
                            return null;
                   
                    ListNode node = header.next;
                    while(node!=null)
                    {
                            if(node.element==c)
                                    return node;
                           
                            node=node.next;
                    }
                    return null;
            }
           
            void insert(char c,ListNode node)
            {
                    node.next=new ListNode(c,node.next);
            }
           
            void remove(char c)
            {
                    if(isEmpty())
                            return;
                   
                    ListNode node = header.next;
                    while(node!=null)
                    {
                            if(node.next.element==c)
                            {
                                    node.next=node.next.next;
                                    return;
                            }
                            node = node.next;
                    }
            }
    }

文件三:Test.java

    package list;

    public class Test {
           
            public static void showCharCount(char s[])
            {
                    System.out.println("原字符串是:"+new String(s));
                    LinkedList list = new LinkedList();
                    ListNode node;
                    for(int i=0;i<s.length;i++)
                    {
                            if((node=list.find(s[i]))==null)
                                    list.insert(s[i],list.header);
                            else
                                    node.count++;                               
                    }
                   
                    /*
                     * 打印链表
                     */
                    node = list.header.next;
                    while(node!=null&&!list.isEmpty())
                    {
                            System.out.println("字符:  '"
                                            +node.element+"'    出现:  "
                                            +node.count+"  次");
                            node=node.next;
                    }
            }
           
            public static void showCharCount(String s)
            {
                    showCharCount(s.toCharArray());
            }

            public static void main(String[] args) {

                    showCharCount("abcd ssd wool");

            }
    }

最后修饰下,把main方法写漂亮点:

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

                    String s;
                    while(true)
                    {
                            System.out.print("请输入待统计字符串:  ");
                            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                            s = br.readLine();
                           
                            if(s.length()>=40)
                            {
                                    System.out.println("请输入40个字符以内.");
                                    System.out.println("===============================\n");
                                    continue;
                            }
                            else
                                    break;                       
                    }
                    showCharCount(s);

            }


效果如下:

请输入待统计字符串:  Woden!Never give up!!!I'll do my best!!!
请输入40个字符以内.
===============================

请输入待统计字符串:  Woden!Never give up!!!
原字符串是:Woden!Never give up!!!
字符:  'p'    出现:  1  次
字符:  'u'    出现:  1  次
字符:  'i'    出现:  1  次
字符:  'g'    出现:  1  次
字符:  ' '    出现:  2  次
字符:  'r'    出现:  1  次
字符:  'v'    出现:  2  次
字符:  'N'    出现:  1  次
字符:  '!'    出现:  4  次
字符:  'n'    出现:  1  次
字符:  'e'    出现:  4  次
字符:  'd'    出现:  1  次
字符:  'o'    出现:  1  次
字符:  'W'    出现:  1  次