[原创]数据结构学习笔记之一:链表
大四了,忙着找工作.凭着三年的项目实践经验,本以为工作不会太难找...但是,事与愿违,我在这场找工作的战役中却屡战屡败,总结其原因,最大最根本的是我基础不足,甚至是没有基础.晕,大四找工作的时候我才来恶补基础,真后悔以前对基础的排斥和不重视.为了找份好工,也只能好好的恶补基础了.
数据结构首当其冲,下面我就将我数据结构的学习笔记share一下.(唉,人家大二学的东西,我现在才来学,不得不说是种悲哀)... 让我来检查一下你的学习成果.
哈哈 许多人都知道链表(C语言)都是借助指针来实现链接的,同样许多人也知道java语言是没有指针的,所以很多人可能很理所当然的认为"java没有数据结构",我想这种想法是错误的.程序=算法+数据结构,任何语言都离不开数据结构(唉,这么简单一个道理我也是最近才悟出的,惭愧啊...).下面我就谈谈java语言的数据结构. 代码一:链表结构的java实现
/*
* 创建日期 2005-11-26
* @author Woden Wang
*/
package listtest;
public class ListNode {
Object element;
ListNode next;
ListNode(Object o,ListNode n)
{
element=o;
next=n;
}
ListNode(Object o)
{
this(o,null);
}
}
[ Last edited by wool王 on 2005-11-26 at 12:59 ] 代码二:链表操作器的java实现
/*
* 创建日期 2005-11-26
* @author Woden Wang
*/
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;
}
}
}
[ Last edited by wool王 on 2005-11-26 at 12:59 ] 完成...参考了<数据结构(C语言版)>(hjack借我D书,呵呵,沾点仙气)和<数据结构与算法分析--java语言描述>,不过感觉原作者写得罗嗦了点,所以自己整理了下(原著的java实现用了3个类,我觉得有点不必要). 接下来用链表解一道题.这道题是我去北电笔试的时候遇到的,当时做得乱七八糟(因为要求用C/C++做...晕...当时就投降了...).
题目是这样的:输入一串字符,分别统计各个字符的数目.(maybe大家都觉得很简单,,,但我当时确实不会...用力鄙视我吧...) 楼主注释得很清楚.
之前没有看过JAVA的链表.
但都很容易看懂了.
下面这个函数小弟没用过
System.gc();//功能是什么?
[ Last edited by dy.f on 2005-11-26 at 21:46 ] 学得还不错，赞一下。
上述代码应该没有问题的，等你的实例出来再研究一下。 这题用了三个文件,其中两个分别是链表结构和链表操作器.
文件一: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");
}
}
[ Last edited by wool王 on 2005-11-26 at 13:34 ] 最后修饰下,把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次 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垃圾搜集器开始垃圾收集... well done， wool thx 13楼即楼主
[ Last edited by dy.f on 2005-11-26 at 23:02 ] 先定义结果体
typedef struct LNode{
char data; //字符
int count; //字符的数目
struct LNode *next;
}LNode,*LinkList;
[ Last edited by dy.f on 2005-11-27 at 01:45 ] /*函数功能:将元素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) //字符c不在链表L中,把它插到链表后面
ListInsert(L,c);
}
[ Last edited by dy.f on 2005-11-27 at 19:12 ] // 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;
} 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
页:
[1]
2