土语版java数据结构

白话版java数据结构

?

?? ? ?前几天学习了下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];//移除被标记的itemin = 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中得到一个charchar 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];elsebreak;}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;elsecurrent = current.next;}return current;}//  插入数据public void insertFirst(int id,double dd){Link newLink = new Link(id,dd);newLink.next = first;first = newLink;}//删除第一个linkpublic 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;elseprevious.next = temp.next;return temp;}//显示出所有listpublic 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;}}}

?

?

?

?