首页 > 代码库 > 天方夜谈_数据结构
天方夜谈_数据结构
之前，在选修的课程选了我的第一门程序设计语言《Java程序设计语言》，现在并没有学的很透彻，大致了解！而后到了大二，开设的《数据结构》的课程，只不过是用C/C++语言来实现的，THE IMPORTANT QUESTION IS我一直没有明白数据结构是一门什么样的课程，只是跌跌撞撞的进了这个门，然后发现其中还是有很多有趣的事情，比如各种各样的算法。
[参考]
1.《Data Structures Outside In with Java》@ author by Sech Venugopal
2.《An Introduction to the Analysis of Algorithms》@author by [美]Robert Sedgewick [法] Philippe Flajolet
该书的首先回顾了Java的很多基础知识，细致的回顾了面向对象编程的特点。关于java的基础知识可以 http://www.runoob.com/java/java-tutorial.html 了解。
我就直接从Venugopal的数据结构部分开始学习。
1.数据结构概观
百度百科：http://baike.baidu.com/link?url=D5sKgDLIBKaVubTILMCrHS0LpTYJwg-VTg6FeZnOIBIPtydXzTNADAUoyXnImndtbxP4nPV0jj_zoOjc5ryEx_4uRQRug3lU40_6qG1y0oUkYQHiMxdNcWU3rlaIJlyb
2.算法的效率
这个部分我打算从图书馆新借来的《算法分析导论》着重小结。
此处暂代更新
3.线性数据结构
3.1无序列表list
在战场上杀不死的敌人，永远也别想打败他，他就像幽灵横亘在你失败的田地上。
大一下学期，接触到Java程序设计语言，时至今日，才越发觉得知识与技术的海洋是多么多么的浩瀚.......如果说编程语言的一个宏大愿望，没有别的，除了改变世界。
谈到Java，就一定会想到它的那个大家族——类（累）族！我认识Class有一段时间了，我一直认为Class是独处幽灵世界的魔，有着变换莫测的成员函数（方法），随意声明的成员。List是其中一个类，List很想爱德华**世，无序也自然，认识它从一个实例开始：日常收支。
3.2有序列表list
3.3队列Queue
"我在想Y的时候不能想X....."
什么叫做Queue(队列)？”队列是项的集合，对于每一项x和y，如果x在y之前离开对头，那么x一定在y之前进入队列——Sesh·Venugopal“。生活中最形象的一个例子是：排队服务。先来的人先排队先接受服务，这种方式也叫做FIFO（first-in，first-out）。也叫做变态版的”先下手为强“。
我们希望这个Queue类具有一些操作，能够更好的为我们服务嘛：
Class structures.linear.Queue
//构造器:创建一个新的空队列
Queue(){}
void enqueue(T item){} //把指定项添加到这个队列的队尾
T dequeue(){} /*删除并返回这个队列的对头的项，如果队列为空的话，那就抛出NoSuchElementException */
int size(){} //返回这个队列的项数
boolean isEmpty(){} //判断这个队列是否为空队列
int pisitionOf(T item){} //返回指定项在队列中的位置，若不存在则返回null
void clear(){} //删除这个队列的所有项，清空项
void remove(T item){} //移除项中的item指定项
void removeAll(T item){} /*移除队列中所有的指定项，如果不存在，则抛出NoSucnElementException*/
T first(){} //返回队列的第一项，即队头。空队列则返回null
T next(){} //返回队列的下一项，到达队尾则返回null
方法的运行时间，队列的基本操作就是在队列的头尾执行，因此一个高效实现将维护对队头队尾的直接引用，使这些位置可以一次执行，则时间复杂度为O(1)，对于返回搜索项的位置，移除项其都要遍历整个队列，则为O(n)。
现在我们来模拟一下打印机的工作原理：
打印第一个文件——>打印完毕——>打印第二个文件········打印第n个文件——>打印结束
package printQueue;
public class fileJob {
String file;
int id;
String owner;
fileJob(String owner,int id,String file){
this.file=file;
this.owner=owner;
this.id=id;
}
public String toString(){
return new String(owner+" "+id+" "+file);
}
public boolean equals(Object other){
if(other!=null&&other instanceof fileJob){
fileJob another=(fileJob)other;
return id==another.id;
}
return false;
}
}
//将打印的文件做成一个类，然后用这个类的实例化对象进行操作
package printQueue;
/*
这几个类继承fileJob类，主要是重写了比较方法，按照不用的比较参数，进行匹配
*/
public class ownerJob extends fileJob {
ownerJob(String owner, int id, String file) {
super(owner, id, file);
}
public boolean equals(Object other){
if(other!=null&&other instanceof fileJob){
fileJob another=(fileJob)other;
return (owner.equals(another.owner));
}
return false;
}
}
class idowner extends fileJob{
idowner(String owner, int id, String file) {
super(owner, id, file);
}
public boolean equals(Object other){
if(other!=null&&other instanceof fileJob){
fileJob another=(fileJob)other;
return (id==another.id)&&(owner.equals(another.owner));
}
return false;
}
}
package printQueue;
import java.util.*;
import java.io.*;
import structrues.linear.Queue; //导入后面建立的类Queue类
public class printQueue{
Queue<fileJob> printQ;
public printQueue(){
printQ=new Queue<fileJob>();
} //实例化对象
public void lqr(String owner,int id,String file){
printQ.enqueue(new fileJob(owner,id,file));
}
//添加入队列
public void lpq(){
fileJob job=printQ.first();
while(job!=null){
System.out.println(job);
job=printQ.next();
}
} //遍历输入队列中所有的项
//下面几个就是对队列进行出队列和删除队列中的项的操作
public void lprm(String owner,int idjob){
if(printQ.isEmpty()){
throw new NoSuchElementException();
}
//删除所有与id相同的项
printQ.remove(new idowner(owner,idjob,null));
}
public void lprm(String owner){
if(printQ.isEmpty()){
throw new NoSuchElementException();
}
fileJob job = printQ.first();
if(owner.equals(job.owner)){
printQ.dequeue();
}
else{
throw new NoSuchElementException();
}
}
public void lprmAll(String owner){
if(printQ.isEmpty()){
throw new NoSuchElementException();
}
printQ.removeAll(new ownerJob(owner,0,null));
}
}
package structrues.linear;
import java.util.Collection;
import java.util.LinkedList;
import java.util.NoSuchElementException;
import printQueue.fileJob;
/*类Queue的实现，主要是用了一个LinkedList类，ListedList类的具体实现设计到底层的算法
*/
public class Queue<T> {
LinkedList<T> list;
int cursor;
public Queue(){
list=new LinkedList<T>();
cursor=-1;
}
public void enqueue(T item){
list.add(item);
} //把指定项添加到这个队列的队尾
public T dequeue(){
if(list.isEmpty()){
throw new NoSuchElementException();
}
return list.remove(0);
} /*删除并返回这个队列的对头的项，如果队列为空的话，那就抛出NoSuchElementException */
public int size(){
return list.size();
} //返回这个队列的项数
public boolean isEmpty(){
return list.isEmpty();
} //判断这个队列是否为空队列
public int pisitionOf(T item){
return list.indexOf(item);
} //返回指定项在队列中的位置，若不存在则返回null
public void clear(){
list.clear();
} //删除这个队列的所有项，清空项
public void remove(T item){
list.remove(item);
} //移除项中的item指定项
public void removeAll(T item){
list.removeAll((Collection<?>) item);
} /*移除队列中所有的指定项，如果不存在，则抛出NoSucnElementException*/
public T first(){
if(list.size() == 0){return null;}
cursor = 0;
return list.get(cursor);
} //返回队列的第一项，即队头。空队列则返回null
public T next(){
if(list.size() == 0 || cursor == (list.size()-1)){
return null;
}
cursor++;
return list.get(cursor);
} //返回队列的下一项，到达队尾则返回null
}
到了最后，完成测试类：
package printQueue;
public class mainText {
public static void main(String[] args) {
printQueue pq=new printQueue();
pq.lqr("小二",001,"第一个文件");
pq.lqr("张三",002,"第二个文件");
pq.lqr("李四",003,"第三个文件");
pq.lqr("王二麻子",004,"第四个文件");
pq.lqr("老王",005,"第五个文件");
System.out.println("运行出来的结果还是蛮不错的嘛");
System.out.println("需要打印的文件已经按照好顺序准备打印");
System.out.println();
pq.lpq();
}
}
真的，对于才开始解除java,一开始理解这样的编程过程肯定是有点难的。实际上对类成员的操作一直是java这类面向对象编程的特点。真正理解类才发现写代码“累” 。关于Queue我们还可以做的更多.......
3.4 栈Stack
3.5 二叉树和普通书 binaryTree and normalTree
3.6 堆Heap
3.7 散列表Hashmap
3.8 图Graph
3.9 递归算法
4.0 排序算法
天方夜谈_数据结构