java 数据结构
[*]许多人都知道链表(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))==null)
[*] list.insert(s,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 次
页:
[1]