数据结构小结——简单实现链表与数组队列

 一般常用的结构类型有：

1. 数组 Array
2. 链表 Linked List
3. 队列 Queue
4. 栈 Stack
5. 堆 Heap
6. 树 Tree
7. 图 Graph

数据结构也可以根据存储的地址是不是连续的分做两大类，连续的和非连续的

连续的有：数组，栈

非连续的有：链表，堆，树

队列要看情况，要看是采用什么方式存储的。

 主要总结一下数组，链表以及由数组组成的数组队列和链表链接的链表队列

【数组】

 

 定义数组的几种方式：

     
          数据类型[ ] 数组名 = new 数据类型[长度];
          eg:int[ ] array = new int[10];

          数据类型[ ] 数组名;
          数组名 = new 数据类型[长度];
          eg: int[ ] array;

               array = new int[10];

          数据类型[ ] 数组名 = {值,...};
          数据类型[ ][ ] 数组名 = {{值,...},...};（二维数组）

          eg: int[ ] array = {1,2,3,4}
                int[ ] [ ]  array2 = { { 1,2,3 },

                                             { 4,5,6, },

                                             { 7,8,9 } };

 

          数据类型[ ] 数组名 = new 数据类型[ ]{值,...};
          eg: int[ ] array = new int[ ]{1,2,3,4 };

          
          数据类型[ ] 数组名;
          数组名 = new 数据类型[ ]{值,...};
          eg: int[ ] array;

                array = new int[ ]{ 1,2,3 };

   

     获取一维数组的大小（长度）：数组名.length

     获取二维数组有多少行数据：数组名.length
     获取二维数组某一行有多少列数据：数组名[行下标].length

     

     

     数组的特点：

          1、大小一定

          2、类型一定   

          优点：根据下标访问元素方便迅速

          缺点：因为大小一定所以添加删除等操作不方便

 

【链表】

   链表由节点，存储的数据和引用组成。

    链表的特点：

     添加、删除方便。这同时也是链表的优点。

    链表的缺点：

     不像数组那样可以通过下标直接找到存储的元素，链表必须通过遍历才能查找到存储的数据。

 

 

 

【数组队列】

用数组实现队列，依赖数组名存储的是数组对象在内存中的首地址。

添加删除节点时都需要重新建立一个数组，添加一个节点时新建数组扩大一位，删除一个节点时减少一位。

在这里采用了泛型，泛型使用某一种符号来泛指Java中所有的数据类型。

package com.hnu.wk1108数组队列;

public class ArrayQueue<E> {
	
		private int  size = 0;
		private Object[] array = new Object[0];

		// 添加新元素
		public void add(E e) {
			// 定义一个比原数组长一个单位的新数组array1
			Object array1[] = new Object[size + 1];
			// 把原数组中的元素传给新数组
			for (int i = 0; i < size; i++) {
				array1[i] = array[i];
			}
			// 把新元素添加给新数组的最后一个位置
			array1[size] = e;
			// 让原数组指向新数组
			size++;
			array = array1;
		}
		
		// 删除,根据下标
		public void delete(int n) {
			if (n >= 0 && n < size) {
				// 定义一个比原数组短一个单位的新数组array1
				Object array2[] = new Object[size - 1];
				// 把被删除元素前的元素传给新数组
				for (int i = 0; i < n; i++) {
					array2[i] = array[i];
				}
				// 把被删除元素后的元素向前移动一位传给新数组
				for (int i = n; i < size - 1; i++) {
					array2[i] = array[i + 1];
				}
				// 数组元素个数减少
				size--;
				// 让原数组指向新数组
				array = array2;
			}
		}
		//获取
		public E gete(int n){
			if( n>=0 && n<getsize() ){
				E e=(E) array[n];
				return e;
			}
			return null;
		}
		// 得到数组元素个数
		public int getsize() {
			return size;
		}

	

}

 

package com.hnu.wk1108数组队列;

public class tester {

	public static void main(String[] args) {
		ArrayQueue<String> aq = new ArrayQueue(); //String对象
		//添加节点
		for(int i= 1;i<=5;i++){
			aq.add(" "+i);
		}
		printaq(aq);
		//删除节点
		int j = 2;
		aq.delete(j);
		System.out.println("删除第"+(j+1)+"个后：");
		printaq(aq);
	}
	
	public static void printaq(ArrayQueue<String> aq ){
		for(int i=0;i<aq.getsize();i++){
			System.out.println(aq.gete(i));
		}
	}

}

 

【链表队列】

 用链表实现队列，依赖链表的引用可以方便地找到下一个节点。

节点类

package com.hnu.wk1113链表队列;


public class LinkNode {
	
	public Object data;//链表节点内的数据
	public LinkNode next;//下一个节点的指向
	
}

 方法类

package com.hnu.wk1113链表队列;



public class LinkList {
	
	private LinkNode root = null;//首节点
	private LinkNode last = null;//尾节点
	private int size = 0;
	
	
	

	/**
	 * 给链表添加节点的方法
	 * @param data 添加的数据对象
	 */
	public void add(Object data){
		if(root==null){
			root = new LinkNode();	
			root.data = data;//数据存入首节点
			last=root;
			size++;
		}else{
			LinkNode node = new LinkNode();//新建节点
			node.data = data;//存入数据
			last.next = node;//上个节点指向新建的节点
			last = node;//last指向新建节点
			size++;
		}
	}
	
	/**
	 * 获取指定位置节点的数据
	 * @param index 节点位置
	 * @return 指定节点数据
	 */
	public Object getIndex(int index){
		if(index<0||index>size){
			 return null;	 
			 
		 }
		LinkNode node = root;
		for(int i=0;i<index;i++){
			node = node.next;
		}
		return node.data;
	}
	
	/**
	 * 在指定位置插入节点
	 * @param index 指定位置
	 * @param o 插入节点数据   
	 * 
	 */
	public void insert(int index,Object data){
		if ( index < 0 || index > size){
			 throw new RuntimeException("下标越界");
		}else{
			if(root==null){
				root = new LinkNode();	
				root.data = data;//数据存入首节点
				last=root;
				size++;
			}else{
			//新建要插入的节点
			LinkNode newNode = new LinkNode();
			newNode.data = data;
			//得到当前索引位置的节点
			
			LinkNode node = root;
			//遍历至索引位置
			for(int i = 0;i<index-1;i++){
				node = node.next;
			}
			newNode.next = node.next;
			node.next = newNode;
			size++;

			}
		}
	}
	
	
	/**
	 * 删除指定位置节点的方法
	 * @param index 指定位置
	 */
	public void delete(int index){
//		String str ;
		if ( index < 0 || index > size){
			 throw new RuntimeException("下标越界");
		}else{
			//得到当前索引位置的节点
			LinkNode node1 = new LinkNode();
			node1.data = this.getIndex(index);//获取索引位置的节点
			LinkNode node = root;
			//遍历至索引位置前一个
			for(int i = 0;i<index-1;i++){
				node = node.next;
			}
			node.next = node.next.next;
			size--;
//			System.out.println("   "+node1.data);
		}
	}
	
	
	/**
	 * 获取链表长度的方法
	 * @return 链表长度
	 */
	public int getSize(){
		return size;
	}

}

 测试类

package com.hnu.wk1113链表队列;


public class Tester {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		LinkList list = new LinkList();
		String s1 = "a";
		list.add(s1);
		String s2 = "b";
		list.add(s2);
		String s3 = "c";
		list.add(s3);
		
		int count=list.getSize();
		
		
		for(int t=0;t<count;t++){
			Object obj=list.getIndex(t);
			String s=(String)obj;
			System.out.println(t+" 号位取出的是: "+s);
		}
		
		list.insert(1, "d");
     	count=list.getSize();
		System.out.println("插入一个节点：");
		for(int t=0;t<count;t++){
			Object obj=list.getIndex(t);
			String s=(String)obj;
			System.out.println(t+" 号位取出的是: "+s);
		}
		
		list.delete(2);
		count=list.getSize();
		System.out.println(list.getSize());
		System.out.println("删除后：");
		for(int t=0;t<count;t++){
			Object obj=list.getIndex(t);
			String s=(String)obj;
			System.out.println(t+" 号位取出的是: "+s);
		}
	}

}

 

链表和数组都是基本的，常常会用到的数据类型，要好好练习_(:з」∠)_

最后再让我吐槽一下这个博客的编辑器真难用啊（╯‵□′）╯ノ┻━┻☆ 

格式经常会不统一啊强迫症患者的世界有人懂吗吗吗！இ௰இ