白话版java数据结构

java_suddy

浏览: 31695 次
性别:
来自: 长沙

最近访客更多访客>>

z268l830

u011997289

yw200730

Starr_

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

数据结构 Java J#IDEA

前几天学习了下JAVA数据结构，之前学过C语言的数据结构，整体的思维方式是差不多的，就是在代码设计上存在差异。

自己又重新学习了下java数据结构，我就用白话版来理解每个概念了。下面我从以下方面介绍：

一、数组：

数组就是把一些具有相同类型的数据聚在一起的一种形式。可谓有了数组为我们存储数据带来给大的方便。就好像现实我们在班级在收集材料时就会分成一班一个文件夹，二班一个文件夹……，他们里面每个元素都有一个共同的类型就是XX班的一员，这样就很好利于老师寻找。这些和我们的数组大同小异，把具有相同属性的存放在同一个数组中。（大概就是这样的吧）

代码也很简单：就是在原来int、long、char、String后面加个“[ ]”这个，在在里面定义好大小，而里面的1、2、3……就是数组中的类似于位置号的。对于数组的查找我个人喜欢用二分法查找，感觉简单容易操作，可能因为习惯吧：// 二分法查找

	public int find(long searchKey){	
//		定义序列中的尾部与手部
		int lowerBound =0;
		int upperBound =nElems-1;
//		定义查找位置
		int cutIn;
		while(true){
			cutIn = (lowerBound+upperBound)/2;
//			进行判断
			if(a[cutIn]==searchKey){
				return cutIn;
			}else if(lowerBound>upperBound){
				return nElems;
			}else{
				if(a[cutIn]<searchKey){
					lowerBound = cutIn+1;
				}else{
					upperBound = cutIn-1;
				}
			}		
		}		
	}

数组就说到这了。

二、排序

1.冒泡排序

怎么说呢？大家都知道冒气泡吧，就是从最左边开始比较，如果右侧比你高就原地不动，比右侧比你低你们俩交换位置；然后向右移一位，在进行比较直到最右端。这样最大的就跑到最右端了。然后再从头来一遍，直到全部排完。是不是很复杂呀，但是个人认为唯一优点就是代码简单，但随着数据量的增大，排起来很复杂。

//	冒泡排序
	public void bubbleSort(){
		int out ,in;
		for(out=nElems-1;out>1;out--){
			for(in=0;in<out;in++){
				if(a[in]>a[in+1]){
					swap(in,in+1);
				}
			}
		}
	}
	private void swap(int one,int two){
		long temp = a[one];
		a[one] = a[two];
		a[two] = temp;
	}

2.选择排序：

描述：排序从数组的最左边开始并记录该数的大小，然后与后面的数组进行比较，找出整体最小的数，与其进行位置交换；在依次往右逐个判断，不断交换位置即可；所以比冒泡好多了，就是如果不是顺利的话你就要从第一个一直比较到最后

	public void selectionSort(){
		int out ,in,min;
		for(out=0;out<nElems;out++){
			min = out;
			for(in=out-1;in<nElems;in++){
				if(a[in]<a[min]){
//					交换位置
					min=in;
				swap(out,min);
				}
			}
		}
	}

3.插入排序

顾名思义就是插进去一个个排序，从左边起找到几个正常顺序，遇到不按顺序的就在前面顺序先找到合适位置插进去就行了。

//	插入排序
	public void insertSort(){
		int in ,out;
		for(out=0;out<nElems;out++){
			long temp = a[out];//移除被标记的item
			in = out;      
			while(in>0&&a[in-1]>=temp){//遍历直到找到比他小的
				a[in] = a[in-1];
				--in;
			}
			a[in]=temp;
		}
	}

三者比较：

冒泡排序在数据量小的作用会大些；

选择排序虽然交换次数降低了，在数据量很小时，并且排序又相对耗时应用选择排序

插入排序是三种简单排序中最好的选择，对于数据量大的来说，插入排序通常是最快的。

三、栈与队列

1、栈

提到栈大家首先都知道“先进后出”，就比如一个很细井（只能容下一个身体宽度，但很深），人一个跳进去，再出来。一定是先下去后上来。可以理解吧。

public class Stack {

	private int maxSize;
	private char[] stackArray;
	private int top;
//	构造器
	public Stack(int s){
		maxSize = s;
		stackArray = new char[maxSize];
		top = -1;
	}
//	向栈加数据
	public void push(char j){
		stackArray[++top] = j;
	}
//	从栈顶移除顶部数据
	public char pop(){
		return stackArray[top--];
	}
	public char peek(){
		return stackArray[top];
	}
//	判断栈是否为空
	public boolean isEmpty(){
		return (top==-1);
	}
//	判断栈是否满
	public boolean isFull(){
		return (top==maxSize-1);
	}
}
public class Reverse {

	private String input;
	private String output;
//	建立构造器
	public Reverse(String in){
		input = in;
	}
	public String doRev(){
//		获得栈的最大值
		int stackSize = input.length();
		Stack stack = new Stack(stackSize);
		
		for(int j=0;j<input.length();j++){
//			从input中得到一个char
			char ch = input.charAt(j);
			stack.push(ch);
		}
		output = "";
		while(!stack.isEmpty()){
			char ch = stack.pop();
			output = output +ch;
		}
		return output; 
	}	
}

2、队列

先进先出：类似快餐厅排队，你先排队点完餐拿着快餐就可以走了。

public class Queue {

	private int maxSize;
	private long[] queArray;
	private int front;
	private int rear;
	private int nElems;
//	含参构造器
	public Queue(int s){
		maxSize = s;
		queArray = new long[maxSize];
		front = 0;
		rear =-1;
		nElems = 0;
	}
//	在队列中插入数据
	public void insert(long j){
		if(rear == maxSize-1)
			rear =-1;
		queArray[++rear] = j;
		nElems++;
	}
//	移除队列中的数据
	public long remove(){
		long temp = queArray[front++];
		if(front==maxSize)
			front =0;
		nElems--;
		return temp;
	}
//	查看头部
	public long peekFront(){
		return queArray[front];
	}
//	判断是否为空
	public boolean isEmpty(){
		return (nElems ==0);
	}
//	判断是否为满
	public boolean idFull(){
		return (nElems==maxSize);
	}
//	求大小
	public int size(){
		return nElems;
	}	
}

3、优先级队列

顾名思义就是具有优先级功能的队列，传统的队列可能只是单纯的满足先进先出。但是有了优先级队列就是根据情况选择优先的先出来在实际应用很大，因为毕竟数据不能总是一味按照顺序。要有自己偏爱的和自己的喜爱的就优先些。

最小生成树也是优先级队列

//	优先插入
	/**方法
	 * 如果没有，直接插入到该位置就行
	 * 否则就从上部开始上衣存在的数据项，直到找到新的数据项应当插入的位置
	 */
	public void insert(long item){
		int j;
		if(nElems==0){
			queArray[nElems++] = item;
		}else{
			for(j=nElems-1;j>=0;j--){
				if(item>queArray[j])
					queArray[j+1] = queArray[j];
				else
					break;
			}
			queArray[j+1] = item;
			nElems++;
		}
	}

四、链表

链表就是把每个数据看成一个节点，用“链子”把他们连接起来的线性表，也是用来存储数据的，链表在表头的删除与插入那是相当快。所以在link中有next的功能，以为链子就要一个个往下找，那块断了两边就要连接起来。这个意为删除。就好比你在全球找我们的学校地址时，首先你先确定下找到中国——>湖南省——>长沙市——>岳麓区——>具体是几号。整个过程是一环一环一级级的。在链表中找数据也是一环一环的。

public class LinkList {

	private Link first;
	public LinkList(){
		first = null;
	}
	
//	判断是否为空
	public boolean isEmpty(){
		return (first == null);
	}
//	找到数据
	public Link find(int key){
		Link current = first;
		while(current.iData!=key){
			if(current.next == null)
				return null;
			else
				current = current.next;
		}
		return current;
	}
//  插入数据
	public void insertFirst(int id,double dd){
	Link newLink = new Link(id,dd);
	newLink.next = first;
	first = newLink;
	}
//	删除第一个link
	public Link deleteFirst(int key){
		Link temp = first;
		Link previous = first;
		while(temp.iData !=key){
			if(temp.next == null)
				return null;
			else{
				previous = temp;
				temp = temp.next;
			}
			
		}
		if(temp==first)
			first= first.next;
		else
			previous.next = temp.next;
		return temp;
	}
//	显示出所有list
	public void displaayList(){
		System.out.println("List(first--last)");
		Link current = first;
		while(current!=null){
			current.displayLink();
			current = current.next;
		}
		System.out.println("");
	}
}

五、哈希表

大家都知道哈希表是数组的一种推广，在普通数组中我们习惯了用直接寻址（给每个关键字分配一个位置，每个元素的存储地址就是关键字对应的数组下标）方法查找。但是有可能两个关键字可能就哈希到同一个位置，就发生了冲突。大多数我们是运用哈希函数解决冲突。提到哈希函数我们想到最多的就是除留余数法（通过取k除以m的余数来将关键字k映射到哈希表的m个不同地址的某个中去）。这样便可以很好的使用查找、删除、插入。

这个是哈希表的样子，竖排像数组，横着像链表。所以它就集合他们俩的优势了，太聪明了。

public class hashTable {
    
	private StoreList[] hashArray; 
	private int arraySize;
//	建立构造器
	public hashTable(int size){
		arraySize = size;
		hashArray = new StoreList[arraySize];
		for(int j=0;j<arraySize;j++){
			hashArray[j] = new StoreList();
		}
	}
//	显示hash表的情况
	public void displayHash(){
		for(int j=0;j<arraySize;j++){
			System.out.print(j+"、");
			hashArray[j].dispaly();
		}
		System.out.println("");
	}
//	设定去留余数法
	public int hashFunc(int key){
		return key%arraySize;
	}
//	插入数据
	public void insert(Link theLink){
		int key = theLink.getKey();
		int hashVal = hashFunc(key);
		hashArray[hashVal].insert(theLink);
	}
//	删除数据
	public void delete(int key){
		int hashVal = hashFunc(key);
		hashArray[hashVal].delete(key);
	}
//	查找数据
	public Link find(int key){
		int hashVal = hashFunc(key);
		return hashArray[hashVal].find(key);
	}
}

package hash;

public class StoreList {

	private Link first;
//	构造器
	public StoreList(){
		first = null;
	}
//	插入链表的数据
	public void insert(Link link){
		int key = link.getKey();
		Link previous = null;
		Link current =first;
//		判断链表是空和数据比第一个大
		while(current!=null&&key>current.getKey()){
			previous = current;
			current = current.next;
		}
		if(current ==null){
			first = link;
			
		}else{
			
			previous.next = link;
			
			link.next = current;		
		}	
	}	
//	删除
	public void delete(int key){
		Link previous=null;
		Link current = first;
		while(current!=null&&key!=current.getKey()){
			previous = current;
			current = current.next;
		}
		if(previous==null){
			first = first.next;
		}else{
			previous.next = current.next;
		}
	}
//	查找链表里面的数据
	public Link find(int key){
		Link current = first;
		if(current.getKey()==key){
			return current;
		}else{
			current = current.next;
		}
		return null;
	}
//	显示链表的信息
	public void dispaly(){
		System.out.println("链表的信息");
		Link current = first;
		while(current!=null){
			current.displayLink();
			current = current.next;
		}
	}
	
}