[原创]数据结构学习笔记之一:链表

wool王

大四了,忙着找工作.凭着三年的项目实践经验,本以为工作不会太难找...但是,事与愿违,我在这场找工作的战役中却屡战屡败,总结其原因,最大最根本的是我基础不足,甚至是没有基础.晕,大四找工作的时候我才来恶补基础,真后悔以前对基础的排斥和不重视.

为了找份好工,也只能好好的恶补基础了.

数据结构首当其冲,下面我就将我数据结构的学习笔记share一下.(唉,人家大二学的东西,我现在才来学,不得不说是种悲哀)...

jackvenn

让我来检查一下你的学习成果.

哈哈

wool王

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

wool王

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

1. 
   
2. /*
   
3. * 创建日期 2005-11-26
   
4. * @author Woden Wang
   
5. */
   
6. package listtest;
   
7. 
   
8. public class ListNode {
   
9.        
   
10.         Object element;
    
11.         ListNode next;
    
12.                
    
13.         ListNode(Object o,ListNode n)
    
14.         {
    
15.                 element=o;
    
16.                 next=n;
    
17.         }
    
18.        
    
19.         ListNode(Object o)
    
20.         {
    
21.                 this(o,null);
    
22.         }
    
23. }
    

复制代码

[ Last edited by wool王 on 2005-11-26 at 12:59 ]

wool王

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

1. 
   
2. /*
   
3. * 创建日期 2005-11-26
   
4. * @author Woden Wang
   
5. */
   
6. package listtest;
   
7. 
   
8. public class LinkedList {
   
9. 
   
10.         private ListNode header;
    
11.        
    
12.         LinkedList()
    
13.         {
    
14.                 header=new ListNode(null);
    
15.         }
    
16.        
    
17.         LinkedList(ListNode n)
    
18.         {
    
19.                 header=new ListNode(null,n);
    
20.         }
    
21.        
    
22.         /**
    
23.          * 判断链表是否为空
    
24.          * @return 链表是否为空的布尔值
    
25.          */
    
26.         boolean isEmpty()
    
27.         {
    
28.                 return header.next==null;
    
29.         }
    
30.        
    
31.         /**
    
32.          * 清空链表.
    
33.          * 注:此方法没有真正清除内存,清楚内存的任务交给java垃圾回收器去处理吧.^_^
    
34.          */
    
35.         void makeEmpty()
    
36.         {
    
37.                 header=null;
    
38.                 System.gc();
    
39.         }
    
40.        
    
41.         /**
    
42.          * 查找目标数据所在节点
    
43.          * @param o 目标数据
    
44.          * @return 保存目标数据节点
    
45.          */
    
46.         ListNode find(Object o)
    
47.         {
    
48.                 if(isEmpty())
    
49.                         return null;
    
50.                
    
51.                 ListNode node = header.next;
    
52.                 while(node!=null)
    
53.                 {
    
54.                         if(node.element.equals(o))
    
55.                                 return node;
    
56.                        
    
57.                         node=node.next;
    
58.                 }
    
59.                 return null;
    
60.         }
    
61.        
    
62.         /**
    
63.          * 在节点node后面新建一个节点,该节点保存数据o
    
64.          * @param o 数据
    
65.          * @param node 插入节点
    
66.          */
    
67.         void insert(Object o,ListNode node)
    
68.         {
    
69.                 node.next=new ListNode(o,node.next);
    
70.         }
    
71.        
    
72.         /**
    
73.          * 删除目标数据的节点
    
74.          * @param o 目标数据
    
75.          */
    
76.         void remove(Object o)
    
77.         {
    
78.                 if(isEmpty())
    
79.                         return;
    
80.                
    
81.                 ListNode node = header.next;
    
82.                 while(node!=null)
    
83.                 {
    
84.                         if(node.next.element.equals(o))
    
85.                         {
    
86.                                 node.next=node.next.next;
    
87.                                 return;
    
88.                         }
    
89.                         node = node.next;
    
90.                 }
    
91.         }
    
92. }
    

复制代码

[ Last edited by wool王 on 2005-11-26 at 12:59 ]

wool王

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

wool王

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

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

dy.f

楼主注释得很清楚.
之前没有看过JAVA的链表.
但都很容易看懂了.
下面这个函数小弟没用过
System.gc();//功能是什么?

[ Last edited by dy.f on 2005-11-26 at 21:46 ]

jackvenn

学得还不错，赞一下。

上述代码应该没有问题的，等你的实例出来再研究一下。

wool王

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

文件一:ListNode.java

1. 
   
2. package list;
   
3. 
   
4. 
   
5. public class ListNode {
   
6.        
   
7.         char element;        //当前字符
   
8.         int count;                //字符个数
   
9. 
   
10.         ListNode next;
    
11.        
    
12.         ListNode(char c,ListNode n)
    
13.         {
    
14.                 element = c;
    
15.                 count=1;
    
16.                 next=n;
    
17.         }
    
18.        
    
19.         ListNode(char c)
    
20.         {
    
21.                 this(c,null);
    
22.         }
    
23. }
    

复制代码

文件二:LinkedList.java

1. 
   
2. package list;
   
3. 
   
4. 
   
5. public class LinkedList {
   
6. 
   
7.         ListNode header;
   
8.        
   
9.         LinkedList()
   
10.         {
    
11.                 this(null);
    
12.         }
    
13.        
    
14.         LinkedList(ListNode n)
    
15.         {
    
16.                 header=new ListNode(' ',n);
    
17.         }
    
18.        
    
19.         boolean isEmpty()
    
20.         {
    
21.                 return header.next==null;
    
22.         }
    
23.        
    
24.         void makeEmpty()
    
25.         {
    
26.                 header=null;
    
27.         }
    
28.        
    
29.         ListNode find(char c)
    
30.         {
    
31.                 if(isEmpty())
    
32.                         return null;
    
33.                
    
34.                 ListNode node = header.next;
    
35.                 while(node!=null)
    
36.                 {
    
37.                         if(node.element==c)
    
38.                                 return node;
    
39.                        
    
40.                         node=node.next;
    
41.                 }
    
42.                 return null;
    
43.         }
    
44.        
    
45.         void insert(char c,ListNode node)
    
46.         {
    
47.                 node.next=new ListNode(c,node.next);
    
48.         }
    
49.        
    
50.         void remove(char c)
    
51.         {
    
52.                 if(isEmpty())
    
53.                         return;
    
54.                
    
55.                 ListNode node = header.next;
    
56.                 while(node!=null)
    
57.                 {
    
58.                         if(node.next.element==c)
    
59.                         {
    
60.                                 node.next=node.next.next;
    
61.                                 return;
    
62.                         }
    
63.                         node = node.next;
    
64.                 }
    
65.         }
    
66. }
    

复制代码

文件三:Test.java

1. 
   
2. package list;
   
3. 
   
4. 
   
5. public class Test {
   
6.        
   
7.         public static void showCharCount(char s[])
   
8.         {
   
9.                 System.out.println("原字符串是:"+new String(s));
   
10.                 LinkedList list = new LinkedList();
    
11.                 ListNode node;
    
12.                 for(int i=0;i<s.length;i++)
    
13.                 {
    
14.                         if((node=list.find(s[i]))==null)
    
15.                                 list.insert(s[i],list.header);
    
16.                         else
    
17.                                 node.count++;                               
    
18.                 }
    
19.                
    
20.                 /*
    
21.                  * 打印链表
    
22.                  */
    
23.                 node = list.header.next;
    
24.                 while(node!=null&&!list.isEmpty())
    
25.                 {
    
26.                         System.out.println("字符:  '"
    
27.                                         +node.element+"'    出现:  "
    
28.                                         +node.count+"  次");
    
29.                         node=node.next;
    
30.                 }
    
31.         }
    
32.        
    
33.         public static void showCharCount(String s)
    
34.         {
    
35.                 showCharCount(s.toCharArray());
    
36.         }
    
37. 
    
38.         public static void main(String[] args) {
    
39. 
    
40.                 showCharCount("abcd ssd wool");
    
41. 
    
42.         }
    
43. }
    
44. 
    

复制代码

[ Last edited by wool王 on 2005-11-26 at 13:34 ]

wool王

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

1. 
   
2.         public static void main(String[] args) throws IOException{
   
3. 
   
4.                 String s;
   
5.                 while(true)
   
6.                 {
   
7.                         System.out.print("请输入待统计字符串:  ");
   
8.                         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   
9.                         s = br.readLine();
   
10.                        
    
11.                         if(s.length()>=40)
    
12.                         {
    
13.                                 System.out.println("请输入40个字符以内.");
    
14.                                 System.out.println("===============================\n");
    
15.                                 continue;
    
16.                         }
    
17.                         else
    
18.                                 break;                       
    
19.                 }
    
20.                 showCharCount(s);
    
21. 
    
22.         }
    

复制代码

wool王

效果如下:

请输入待统计字符串:  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  次

wool王

Originally posted by dy.f at 2005/11/26 13:25:
楼主注释得很清楚.
之前没有看过JAVA的链表.
但都很容易看懂了.
下面这个函数小弟没用过
System.gc();//功能是什么?

[ Last edited by dy.f on 2005-11-26 at 21:46 ]

那个是垃圾回收的方法...调用这个方法会建议java垃圾搜集器开始垃圾收集...

jackvenn

well done， wool

dy.f

thx 13楼即楼主

[ Last edited by dy.f on 2005-11-26 at 23:02 ]

dy.f

先定义结果体

typedef struct LNode{
        char data;                //字符
        int count;                //字符的数目
        struct LNode *next;
}LNode,*LinkList;

[ Last edited by dy.f on 2005-11-27 at 01:45 ]

dy.f

/*函数功能:将元素c插到链表L的末尾
*
*/
void ListInsert(LinkList L,char c){

        LinkList q;
        LinkList s = (LinkList)malloc(sizeof(LNode));//生成新结点
        s->data = c;
        s->count = 1;
        s->next = NULL;
        q = L;
        while(q->next)q = q->next;
        q->next = s;
        s->next = NULL;
}

dy.f

/*函数功能:判断元素是否在链表中,如在,该元素的个数加1,否则,把该元素插入到该链表的末尾
*
*/
void find(LinkList L,char c){
        LinkList p ;
        p = L;
        while(p->next){
                if(p->next->data == c){
                        p->next->count++;break;  //统计相同字符的个数
                }
                else
                        p = p->next;
        }
        if(p->next == NULL)        //字符c不在链表L中,把它插到链表后面
                ListInsert(L,c);  
}

[ Last edited by dy.f on 2005-11-27 at 19:12 ]

dy.f

// charcount.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
using namespace::std;


typedef struct LNode{
        char data;                //字符
        int count;                //字符的数目
        struct LNode *next;
}LNode,*LinkList;

/*全局变量
*/
static LinkList L;

/*函数功能:将元素c插到链表L的末尾
*
*/
void ListInsert(LinkList L,char c){

        LinkList q;
        LinkList s = (LinkList)malloc(sizeof(LNode));//生成新结点
        s->data = c;
        s->count = 1;
        s->next = NULL;
        q = L;
        while(q->next)q = q->next;
        q->next = s;
        s->next = NULL;
}
/*函数功能:判断元素是否在链表中,如在,该元素的个数加1,否则,把该元素插入到该链表的末尾
*
*/
void find(LinkList L,char c){
        LinkList p ;
        p = L;
        while(p->next){
                if(p->next->data == c){
                        p->next->count++;break;  //统计相同字符的个数
                }
                else
                        p = p->next;
        }
        if(p->next == NULL)
                ListInsert(L,c);
}


/*函数功能:输入一串字符串,分别统计个各个字符的数目
*
*/
int _tmain(int argc, _TCHAR* argv[])
{
        LinkList list;
        char string[] = "helloworld";
        L = (LinkList)malloc(sizeof(LNode));//先建立一个带头结点的单链表
        L->next = NULL;
        for(int i = 0;i<sizeof(string); i++)
                find(L,string);
        list = L->next;
        while(list){
                cout<<list->data<<" number is:";
                cout<<list->count;
                list = list->next;
                cout<<endl;
        }

        cout<<endl<<"OK";
        return 0;
       
}

dy.f

h number is:1
e number is:1
l number is:3
o number is:2
w number is:1
r number is:1
d number is:1