2017年11月26日,这样的日子不好受。

2017年11月26日22:43:42 3 1,144 views

整日这样与电脑交朋友,都快忘记了生活,整天都无意学习。

2017年11月26日22:42:36

今由于看到以下内容中的数据结构,花了一天的时时间去看数据结构。

2017年11月26日,这样的日子不好受。

学java这么久来,都还没了解过数据结构,然后在网上看到一篇博客,让我燃起了学数据结构的斗志。

http://blog.csdn.net/iaiti/article/details/39268173

他里面引用了一句知乎的话,我这里也引用一下。

如果说 Java 是自动档轿车,C 就是手动档吉普。数据结构呢?是变速箱的工作原理。你完全可以不知道变速箱怎样工作,就把自动档的车子从 A 开到 B,而且未必就比懂得的人慢。写程序这件事,和开车一样,经验可以起到很大作用,但如果你不知道底层是怎么工作的,就永远只能开车,既不会修车,也不能造车。如果你对这两件事都不感兴趣也就罢了,数据结构懂得用就好。但若你此生在编程领域还有点更高的追求,数据结构是绕不开的课题。

Java 替你做了太多事情,那么多动不动还支持范型的容器类,加上垃圾收集,会让你觉得编程很容易。但你有没有想过,那些容器类是怎么来的,以及它存在的意义是什么?最粗浅的,比如 ArrayList 这个类,你想过它的存在是多么大的福利吗——一个可以随机访问、自动增加容量的数组,这种东西 C 是没有的,要自己实现。但是,具体怎么实现呢?如果你对这种问题感兴趣,那数据结构是一定要看的。甚至,面向对象编程范式本身,就是个数据结构问题:怎么才能把数据和操作数据的方法封装到一起,来造出 class / prototype 这种东西?

此外,很重要的一点是,数据结构也是通向各种实用算法的基石,所以学习数据结构都是提升内力的事情。

内存分配

1) 寄存器 。 最快的存储区,处理器内部,根据需求分配,不能自己控制,但是C/C++可以用register。

2)栈:位于RAM中,速度仅次于寄存器。存放的是基本变量和引用,在栈中的数据可以共享,在栈中的数据大小和生存周期必须确定。
栈存的一个是基本的数据类型,int i = 1; 其实i是一个指向int类型的引用。1存在栈中,i指向1的地址(作用和指针一个样),如果此时有int j = 1; 由于共享性,就不会再开辟
一个新的1的地址。直接让i和j指向同一个地址。
栈也存储对象的引用。

3)堆。存放所有的java对象。

4)常量存储。常量(注意常量和变量,int i =1是变量),字符串,静态区的东西存储在此。

5)非RAM存储。

空间计算:

之前看到过空间和时间的关系,但是没理解,今天再次看到,仔细去研究了下,明白了一个究竟。还是某个博客讲排序时同时讲的时间问题才明白了。

大O表示法

设N为数据总数,加入插入一个数据时间为K。

那么线性查找总时间T=K*N/2,因为查找的话大概为比较数目的一半。

二分查找的话T=k*log2(N)。

大O表示法,O可以看成是order of,大约是的意思,k/2也是常数,所以可以看成是O(N)。

数组

Java中有两种数据类型,基本类型和对象类型,java中把数组当成对象,创建数组需要用new操作符。

在引用数组时,会在栈中开辟空间,空间存储着保存数据的地址,new操作符在堆中开辟了所需的空间,然后数组指向头地址。

然后分析看到了别人写得数组封装

好奇起研究了下,看完就了解了arrayList了

下面是封装代码:

  1. public class UseArray {
  2.     private int[] array;
  3.     private int number = 0;
  4.     public UseArray(int max){
  5.         array = new int[max];
  6.     }
  7.     public void insert(int value){
  8.         array[number] = value;
  9.         number++;
  10.     }
  11.     public int find(int value){
  12.         for (int i= 0; i < number; i++) {
  13.             if(array[i]==value)
  14.                 return i;
  15.         }
  16.         return number;
  17.     }
  18.     public boolean delete(int value){
  19.         int index = find(value);
  20.         if(index != number){
  21.             for (int i = index; i < number-1; i++) {
  22.                 array[i] = array[i+1];
  23.             }
  24.             number--;
  25.             return true;
  26.         }
  27.         return false;
  28.     }
  29.     public void display(){
  30.         for (int i = 0; i < number; i++) {
  31.             System.out.printf(array[i]+" ");
  32.         }
  33.     }
  34.     public static void main(String[] args) {
  35.         UseArray ua  = new UseArray(5);
  36.         ua.insert(1);
  37.         ua.insert(2);
  38.         ua.insert(6);
  39.         ua.insert(7);
  40.         ua.insert(3);
  41.         ua.display();
  42.         if(ua.find(5) != ua.number){
  43.             System.out.println("find,the number index is "+ua.find(5));
  44.         }else{
  45.             System.out.println("not found!");
  46.         }
  47.         if(ua.delete(5)!=true){
  48.             System.out.println("can not delete!");
  49.         }
  50.         ua.display();
  51.     }
  52. }

排序

冒泡排序

最后看了排序,以前觉得排序简单,然而自己写的时候还是有点棘手。要是在我不了解排序的情况下写个排序可能也就像冒泡排序一样吧,以前C语言考试就瞎写了一个排序,最后才知道那是冒泡。

下面是我复习的冒泡排序java代码:

2017年11月26日,这样的日子不好受。

运行结果:

2017年11月26日,这样的日子不好受。

冒泡排序就是大的数像后放,在排序的时候给一个中间变量,让大的数和小的数做交换。

选择排序:

首先默认一个最小值,然后再循环一次去找到比默认还小的最小值。如果找到了,就存入此值得下标,继续向数组后面查找。这次循环结束后,把小的值和前面的值进行交换。后面的循环依旧如此。

2017年11月26日,这样的日子不好受。

运行结果:

2017年11月26日,这样的日子不好受。

插入排序

这个排序相对于前面两个排序花了点时间去了解,还去http://zh.visualgo.net/可视化数据结构网上去看了它的运行原理,分析了几次和参考网上的代码,写出如下内容:

2017年11月26日,这样的日子不好受。

运行结果:

2017年11月26日,这样的日子不好受。

今天就这样了,可能是深度不够,吐不出什么东西来,但是这几天来,一天一个算法,然后练习题目,哪里不懂学哪里。感觉到慢慢在开始学入java底层了。


欢迎来到菜鸟头头的个人博客
本文章百度已收录,若发现本站有任何侵犯您利益的内容,请及时邮件或留言联系,我会第一时间删除所有相关内容。

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:3   其中:访客  2   博主  1

    • avatar 威客系统 1

      不出一个月,要疯

      • avatar 微型隔膜泵 1

        java真的是太强大了。