算法和数据结构---数据结构篇：数组，链表，栈和队列

生活

最近还是在学习flask和java，java马上也快看完了，然后就准备开始复习一下数据结构，同时也预习一下算法。都说程序=数据结构+算法，确实，面对不同问题选择好的数据结构和算法去编程往往能达到最高的效率，经常看到那些简短却又十分完美的代码都会十分佩服，所以决定开始好好复习一下大二学的数据结构（从树那里开始就有点忘了，哈哈）然后学学算法，体会一下那些精妙的思想。
对于数据结构和算法的基本概念，还有时间复杂度，空间复杂度什么的我就不多啰嗦了，看到好多人写的博客真的讲的很好，有兴趣的可以去搜索一下啦。

数据结构部分

我想先从数据结构开始，回顾一下我学过的数据结构：线性表，栈和队列，串，数组和广义表，树、二叉树、哈夫曼树、森林，图……还是有很多知识点的。之前学的时候是用c来写的，但既然自学了这么久java，那我就试着用java写写看，所以今天呢我想从简单的数组，链表开始。
数组和链表都是物理结构，分别是顺序存储结构和链式存储结构。那在内存中呢前者就是顺序存储，后者则是随机存储。数组便于人们去查找，但是不方便插入和删除，链表就刚好相反，相对简单的插入和删除，但是查找某个节点就要遍历链表了。栈和队列也是对应的兄弟，一个先进后出，一个先进先出，他们都是可以基于物理结构实现的逻辑结构。说了这么多，对于所有的数据结构，基本的操作都是增删改查，所以我们还是用代码来实践下。

1.数组

插入：对于数组来说，增又可以分为中间插入和尾插。尾插很简单，只要有空余空间，那就把新来的元素放进去即可，所以重点聊聊中间插入。想让一个新来的元素进入数组中，我们需要知道什么？元素的值和插入的位置也就是插入数组的下标。我们得到了该怎么做呢，首先要把这个位置腾出来，那就从这个位置开始把所有元素往后挪一位，数组大小加一**（注意：判断数组是否越界）**，然后用新加元素的值赋给这个空出来的位置。

删除：删除刚好和插入相反，从这个位置开始到最后每个元素往前移一位，并且数组大小减一。
查找：利用数组下标
修改：利用数组下标直接赋值修改
所以我就写写数组的实现和增删的代码

package 数组的插入;
//数组的插入
public class Myarray {
	private int[] array;
	private int size;
	
	public Myarray(int capacity) {
		this.array=new int[capacity];
		size=0;
	}
	//数组的插入
	public void insert(int element,int index) throws Exception
	{
		if(index<0||index>size)
		{
			throw new IndexOutOfBoundsException("超出数组范围");
		}
		if(size>=array.length) {resize();}
		for(int i=size-1;i>=index;i--)
		{
			array[i+1]=array[i];
		}
		array[index]=element;
		size+=1;
	} 
	
	//数组内元素的删除1:index开始从左往右元素位置依次向左挪一位
	public int delete(int index) throws Exception
	{
		if(index<0||index>=size)
		{
			throw new IndexOutOfBoundsException("超出数组范围");
		}
		int deleted_element=array[index];
		for(int i=index;i<size-1;i++)
		{
			array[i]=array[i+1];
		}
		size-=1;
		return deleted_element;
	}
	
	//数组内元素的删除2:将末尾元素换到需要删除的元素位置，并且数组长度减一
	public int delete2(int index)  throws  Exception
	{
		if(index<0||index>=size)
		{
			throw new IndexOutOfBoundsException("超出数组范围");
		}
		int deleted_element=array[index];
		array[index]=array[size-1];
		size-=1;
		return deleted_element;
	}
	
	public void resize()
	{
		int[] arraynew = new int[array.length*2];//对原数组范围扩大两倍
		System.arraycopy(array, 0, arraynew, 0, array.length);//从旧数组复制到新的数组中
		array=arraynew;
	}
	
	public void print()
	{
		for(int i=0;i<size;i++)
		{
			System.out.printf("%d\t",array[i]);
		}
		System.out.println();
	}

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		Myarray arr=new Myarray(4);
		arr.insert(3,0);
		arr.insert(7,1);
		arr.insert(9,2);
		arr.insert(5,3);
		System.out.println("原数组为:");
		arr.print();
		//插入新的元素
		arr.insert(4,2);
		System.out.println("插入元素后的数组为");
		arr.print();
		//删除元素9
		int del=arr.delete(3);
		System.out.println("删除的元素为"+del);
		arr.print();
		//删除元素7
		int del2=arr.delete2(1);
		System.out.println("删除的元素为"+del2);
		arr.print();
	}

}

我这里对数组越界做了处理，如果数组发生越界，我就将数组的大小变为原来的两倍。运行的结果

2.链表

插入：链表的插入相对于数组来说就比较方便，不用大面积的更换元素，插入新的节点只需要得到插入位置，然后找到它的前一个节点，将前一个节点的下一节点改为新添加的节点，新添加节点的下一节点变为原节点的下一节点。大概就是图里这个意思，画图丑别介意。

删除：和插入相反，得到前一个节点后再获取它的下下个节点，并且把前一个节点的下一个节点变为它的下下个节点。

查找：从头节点开始遍历数组，没找到需要的位置就找它的下一个节点，直到找到尾节点。

修改：根据查找到的节点，修改它的data

package 链表;
//实现单链表
public class Mylist {
	private static class Node
	{
		int data;
		Node next;
		Node(int data){ this.data=data;}
	}
	
	private Node head;
	private Node last;
	private int size;
	
	//链表插入元素
	public void insert(int data,int index) throws Exception{
		if(index<0||index>size)
		{
			throw new IndexOutOfBoundsException("超出链表范围");
		}
		Node insertnode=new Node(data);
		if(size==0)
		{
			//插入头部
			head=insertnode;
			last=insertnode;
		}else if(size==index)
		{
			//插入尾部
			last.next=insertnode;
			last=insertnode;
		}else
		{
			//插入中间
			Node prevnode=get(index-1);
			Node nextnode=prevnode.next;
			prevnode.next=insertnode;
			insertnode.next=nextnode;
		}
		size+=1;
	}
	
	//链表删除元素
	public Node remove(int index) throws Exception
	{
		if(index<0||index>size)
		{
			throw new IndexOutOfBoundsException("超出链表范围");
		}
		Node removenode=null;
		if(index==0)
		{
			//删除头节点
			removenode=head;
			head=head.next;
		}else if(index==size-1)
		{
			//删除尾节点
			Node prevnode=get(index-1);
			removenode=prevnode.next;
			prevnode.next=null;
			last=prevnode;
		}else
		{
			//删除中间节点
			Node prevnode =get(index-1);
			Node nextnode=prevnode.next.next;
			removenode=prevnode.next;
			prevnode.next=nextnode;
		}
		size-=1;
		return removenode;
	}
	
	//链表查找元素
	public Node get(int index) throws Exception
	{
		if(index<0||index>size)
		{
			throw new IndexOutOfBoundsException("超出链表范围");
		}
		Node t=head;
		for(int i=0;i<index;i++)
		{
			t=t.next;
		}
		return t;
	}
	
	//链表的输出
	public void print()
	{
		Node t=head;
		while(t!=null)
		{
			System.out.printf("%d\t",t.data);
			t=t.next;
		}
		System.out.println();
	}

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		Mylist linklist=new Mylist();
		linklist.insert(3, 0);
		linklist.insert(7, 1);
		linklist.insert(2, 2);
		linklist.insert(5, 3);
		linklist.insert(8, 4);
		System.out.println("原链表为:");
		linklist.print();
		//删除index=3
		Node deldata=linklist.remove(3);
		System.out.println("删除后的链表为");
		linklist.print();
		System.out.println("删除链表index=3元素为"+deldata.data);
		//查找index=2的元素
		Node i=linklist.get(2);
		System.out.println("找到链表index=2元素为"+i.data);
	}

}

运行结果：

3.栈和队列

前面说过，他们的区别并不大，只是一个是先进后出，一个是先进先出，如果比喻的话，可以把栈比喻成往瓶子里装糖果，最先装进去的在最底下，最后才会出来。而队列就像是车过隧道，先进去的车先出山洞。这两种数据结构可以用数组实现，也可以用链表实现，只要按照它们的定义，按规则来存或取就行，并不难。我想重点聊的是循环队列。假设我们用数组来实现队列，几次出队操作后前面的位置全部空出来了，而有可能数组已经满了，无法再入队，那么这时候前面出队的位置就浪费掉了。那我们能不能想一种方法来填满这个空出来的空间呢，肯定可以的，这就需要循环队列了。

循环队列：几次出队操作后，我们可以把队尾的指针重新回到数组的首位，那样入队就可以利用出队留下的空余空间。那什么时候队列真的满了呢，其实就是队尾指针后一个就是队头指针，那我们判断式的代码一般就是（队尾+1）%数组大小=队头。（为什么不直接加一？有可能队尾指针在最后一个，队头指针在第一个）
那我们就来实现这个循环队列

package 循环队列;
//用数组实现循环队列
public class Myqueue {
	public Myqueue(int capacity)
	{
		this.array=new int[capacity];
	}
	
	private int[] array;
	private int front;//队头
	private int rear;//队尾
	
	
	//入队enqueue
	public void enqueue(int element) throws Exception
	{
		if((rear+1)%array.length==front)
			throw new Exception("队列已经满了");
		array[rear]=element;
		rear=(rear+1)%array.length;
	}
	
	//出队dequeue
	public int dequeue() throws Exception
	{
		if(rear==front)
			throw new Exception("队列已经空了");
		int del=array[front];
		front=(front+1)%array.length;
		return del;
	}

	
	//队列的输出
	public void print()
	{
		System.out.println("队列中的元素为:");
		for(int i=front;i!=rear;i=(i+1)%array.length)
		{
			System.out.printf("%d\t",array[i]);
		}
		System.out.println();
	}
	
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		Myqueue que=new Myqueue(6);
		que.enqueue(3);
		que.enqueue(5);
		que.enqueue(2);
		que.enqueue(8);
		que.dequeue();
		que.dequeue();
		que.enqueue(12);
		que.print();
	}

}

总结

数据结构和算法其实并没有想象的那么可怕，只要你愿意动脑筋去多想想，多联系一下实际生活来体会，不懂的时候多画画图来模拟。当时学数据结构的时候链表啥的也是一直没搞清楚，但是现在回过头再来复习，感觉简单了很多。所以，千万不要有抗拒抵制心理，你愿意和它交朋友，才能更好了解它。后期呢我也会补充算法和数据结构这一块的内容，争取用c,c++,java,python全部都实现一遍。不过这段时间很忙就没时间经常更新了，争取每天学的都写点东西记录保存，最后有时间整合一下发。