发表于 | 分类于

数据结构是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。

通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

一、数据结构的基本功能

  • 如何插入一条新的数据项
  • 如何寻找某一特定的数据项
  • 如何删除某一特定的数据项
  • 如何迭代的访问各个数据项，以便进行显示或其他操作

二、常用的数据结构

常用的数据机构有：数组Array、栈Stack、队列Queue、链表Linked List、树Tree、哈希表Hash、堆Heap、图Graph。

20200414160854

在Java中，算法通常都是由类的方法来实现的。前面的数据结构，比如链表为啥插入、删除快，而查找慢，平衡的二叉树插入、删除、查找都快，这都是实现这些数据结构的算法所造成的。后面我们讲的各种排序实现也是算法范畴的重要领域。

三、算法的五个特征

  • 有穷性：对于任意一组合法输入值，在执行又穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。
  • 确定性：在每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。
  • 可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。
  • 有输入：作为算法加工对象的量值，通常体现在算法当中的一组变量。有些输入量需要在算法执行的过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。
  • 有输出：它是一组与”输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法功能。

四、算法的设计原则

  • 正确性：首先，算法应当满足以特定的”规则说明”方式给出的需求。其次，对算法是否”正确”的理解可以有以下四个层次：

    程序语法错误。
程序对于几组输入数据能够得出满足需要的结果。
程序对于精心选择的、典型、苛刻切带有刁难性的几组输入数据能够得出满足要求的结果。
程序对于一切合法的输入数据都能得到满足要求的结果。

PS：通常以第 三 层意义的正确性作为衡量一个算法是否合格的标准。

  • 可读性：算法为了人的阅读与交流，其次才是计算机执行。因此算法应该易于人的理解；另一方面，晦涩难懂的程序易于隐藏较多的错误而难以调试。

  • 健壮性：当输入的数据非法时，算法应当恰当的做出反应或进行相应处理，而不是产生莫名其妙的输出结果。并且，处理出错的方法不应是中断程序执行，而是应当返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。

  • 高效率与低存储量需求：通常算法效率值得是算法执行时间；存储量是指算法执行过程中所需要的最大存储空间，两者都与问题的规模有关。

执行效率和存储量，我们知道比较算法的时候，可能会说A算法比B算法快两倍，但实际上这种说法没有任何意义。因为当数据项个数发生变化时，A算法和B算法的效率比例也会发生变化

复杂度(complexity)：如果排序10,000个元素花费了我1秒，那么排序1百万个元素会花多少时间？在这个例子里，复杂度就是相对其他东西的度量结果。

然后我们在说说算法的存储量，包括：

程序本身所占空间；
输入数据所占空间；
辅助变量所占空间；
一个算法的效率越高越好，而存储量是越低越好。

发表于 | 分类于

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

单项链表

单链表是链表中结构最简单的。一个单链表的节点(Node)分为两个部分，第一个部分(data)保存或者显示关于节点的信息，另一个部分存储下一个节点的地址。最后一个节点存储地址的部分指向空值。

单向链表只可向一个方向遍历，一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置。而插入一个节点，对于单向链表，我们只提供在链表头插入，只需要将当前插入的节点设置为头节点，next指向原头节点即可。删除一个节点，我们将该节点的上一个节点的next指向该节点的下一个节点。

双向链表

对于单项链表，我们如果想在尾部添加一个节点，那么必须从头部一直遍历到尾部，找到尾节点，然后在尾节点后面插入一个节点。这样操作很麻烦，如果我们在设计链表的时候多个对尾节点的引用，那么会简单很多。

发表于 | 分类于

注意：二分查找的数组一定是有序的！！！

在有序数组array[]中，不断将数组的中间值（mid）和被查找的值比较，如果被查找的值等于array[mid],就返回下标mid; 否则，就将查找范围缩小一半。如果被查找的值小于array[mid], 就继续在左半边查找;如果被查找的值大于array[mid], 就继续在右半边查找。 直到查找到该值或者查找范围为空时， 查找结束。

发表于 | 分类于

数组的声明

第一种方式：数据类型 [] 数组名称 = new 数据类型[数组长度];

这里 [] 可以放在数组名称的前面，也可以放在数组名称的后面，我们推荐放在数组名称的前面，这样看上去 数据类型 [] 表示的很明显是一个数组类型，而放在数组名称后面，则不是那么直观。

第二种方式：数据类型 [] 数组名称 = {数组元素1，数组元素2，……}

1
2
3
4
5
这种方式声明数组的同时直接给定了数组的元素，数组的大小由给定的数组元素个数决定。
//声明数组1,声明一个长度为3，只能存放int类型的数据
int [] myArray = new int[3];
//声明数组2,声明一个数组元素为 1,2,3的int类型数组
int [] myArray2 = {1,2,3};

实现用类封装数组实现数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
public class MyArray {
       private Object[] objArray;
       private int elems;// 有效长度
       private int length;// 最大长度

       // 默认构造一个长度为20的数组
       public MyArray() {
               elems = 0;
               length = 20;
               objArray = new Object[length];
       }

       // 构造函数，初始化一个长度为length 的数组
       public MyArray(int length) {
               elems = 0;
               this.length = length;
               objArray = new Object[length];
       }

       // 获取数组的有效长度
       public int getSize() {
               return elems;
       }

       // 遍历显示元素
       public void display() {
               for (int i = 0; i < elems; i++) {
                       System.out.print(objArray[i] + " ");
               }
       }

       /**
        * 添加元素
        *
        * @param value
        * @return添加成功返回true,添加的元素超过范围了或者元素已存在返回false
        */
       public boolean add(Object value) {
               if (elems == length) {
                       return false;
               }
               if (find(value) >= 0) {
                       return false;
               } else {
                       objArray[elems] = value;
                       elems++;
                       return true;
               }
       }

       /**
        * 根据下标获取元素
        *
        * @param i
        * @return查找下标值在数组下标有效范围内，返回下标所表示的元素 查找下标超出数组下标有效值，提示访问下标越界
        */
       public Object get(int i) {
               if (i < 0 || i > elems) {
                       System.out.println("访问下标越界");
               }
               return objArray[i];
       }

       /**
        * 查找元素
        *
        * @param searchValue
        * @return查找的元素如果存在则返回下标值，如果不存在，返回 -1
        */
       public int find(Object searchValue) {
               int i;
               for (i = 0; i < elems; i++) {
                       if (null != searchValue && searchValue.equals(objArray[i])) {
                               break;
                       }
               }
               return i == elems ? -1 : i;
       }

       /**
        * 删除元素
        *
        * @param value
        * @return如果要删除的值不存在，直接返回 false;否则返回true，删除成功
        */
       public boolean delete(Object value) {
               int k = find(value);
               if (k == -1) {
                       return false;
               }
               if (k != elems - 1) {
                       for (int i = k; i < elems - 1; i++) {
                               objArray[i] = objArray[i + 1];// 在元素所在位置之后数据前移
                       }
               }
               objArray[elems] = null;
               elems--;
               return true;
       }

       /**
        * 修改数据
        *
        * @param oldValue原值
        * @param newValue新值
        * @return修改成功返回true，修改失败返回false
        */
       public boolean modify(Object oldValue, Object newValue) {
               int i = find(oldValue);
               if (i == -1) {
                       System.out.println("需要修改的数据不存在");
                       return false;
               } else {
                       objArray[i] = newValue;
                       return true;
               }
       }
}

发表于 | 分类于

栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。

栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 /**
* 使用数组实现的栈
*
* @param <E>
*/
public class MyStack<E> {
      private Object[] array;
      private static final int MAX_SIZE = 6;
      private int top;// 栈顶


      public MyStack() {
              this.array = new Object[MAX_SIZE];
              top = -1;
      }

      // 压入数据
      public void push(E value) {
              if (top >= MAX_SIZE - 1) {
                      // 自动扩容 old length >> 1
                      int oldLength = top + 1;
                      int newLength = oldLength + (oldLength >> 1);
                      array = Arrays.copyOf(array, newLength);
              }
              array[++top] = value;
      }

      public int count() {
              return top + 1;
      }

      // 取出数据,栈从栈顶取出数据，就代表出栈
      public E pop() {
              return top>=0?(E) array[top--]:null;
      }

      // 访问栈顶数据
      public E peek() {
              return (E) array[top];
      }

      // 判断栈是否为空
      public boolean isEmpty() {
              return top == -1;
      }

      // 判断栈是否满了
      public boolean isFull() {
              return top == MAX_SIZE - 1;
      }
}

发表于

常见的排序算法有冒泡、选择、插入排序算法。

一、冒泡排序

冒泡算法的运作规律如下：

①、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
②、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数（也就是第一波冒泡完成）。
③、针对所有的元素重复以上的步骤，除了最后一个。
④、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int[] bubbleSort(int[] array) {
        //i代表总的进行多少轮比较
        for (int i = 1; i < array.length; i++) {
                boolean flag = true;
                for (int j = 0; j < array.length - i; j++) {
                        if (array[j] > array[j + 1]) {
                                int tmp = array[j];
                                array[j] = array[j + 1];
                                array[j + 1] = tmp;
                                flag = false;
                        }
                }
                if (flag) {
                        break;
                }
        }
        return array;
}

二、选择排序

选择排序是每一次从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。分为三步：

①、从待排序序列中，找到关键字最小的元素
②、如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换
③、从余下的 N - 1 个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int[] selectionSort(int[] array) {
        // 总共要经过N-1轮比较，每次拿当前i位置的值去后面查到最小的值比较,找出最小值的位置，再交换。
        for (int i = 0; i < array.length - 1; i++) {
                int min = i;
                // 找到后面的最小元素，如遇到比i对应还小的，记录下标，直到找完为止。
                for (int j = i + 1; j < array.length; j++) {
                        if (array[min]>array[j]) {
                                min = j;// 记录目前能找到的最小值元素的下标
                        }
                }
                // 最小值和当前i位置所在的值进行交换
                if (i != min) {
                        int temp = array[i];
                        array[i] = array[min];
                        array[min] = temp;
                }
        }
        return array;
}

三、插入排序

直接插入排序基本思想是每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。插入排序还分为直接插入排序、二分插入排序、链表插入排序、希尔排序等等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int[] insertSort(int[] array) {
    //从第一个元素开始，把当前值与依次前面的值对此，前面的值只要比他大就往后移动，直到合适位置，直接插入
    for(int i = 1;i < array.length;i++){
    int temp = array[i];
    int j = i;
    //判断前面的值是否与需要插入的值比较，只要不小于插入的值，都往后移动位置。
    while(j > 0 && array[j-1] >= temp){
            array[j] = array[j-1];//移动值
        j--;
    }
    array[j] = temp;
}
        return array;
}

发表于 | 分类于

队列（queue）是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO-first in first out）线性表。

队列分为：

①、单向队列（Queue）：只能在一端插入数据，另一端删除数据。
②、双向队列（Deque）：每一端都可以进行插入数据和删除数据操作。

双端队列

双端队列就是一个两端都是结尾或者开头的队列， 队列的每一端都可以进行插入数据项和移除数据项，这些方法可以叫做：insertRight()、insertLeft()、removeLeft()、removeRight()

如果严格禁止调用insertLeft()和removeLeft()（或禁用右端操作），那么双端队列的功能就和前面讲的栈功能一样。

如果严格禁止调用insertLeft()和removeRight(或相反的另一对方法)，那么双端队列的功能就和单向队列一样了。

优先级队列

优先级队列（priority queue）是比栈和队列更专用的数据结构，在优先级队列中，数据项按照关键字进行排序，关键字最小（或者最大）的数据项往往在队列的最前面，而数据项在插入的时候都会插入到合适的位置以确保队列的有序。

优先级队列 是0个或多个元素的集合，每个元素都有一个优先权，对优先级队列执行的操作有：

（1）查找
（2）插入一个新元素
（3）删除

一般情况下，查找操作用来搜索优先权最大的元素，删除操作用来删除该元素 。对于优先权相同的元素，可按先进先出次序处理或按任意优先权进行。

发表于 | 分类于
  • 下载Oracle客户端
  • 配置Oracle客户端

下载之后将其解压，然后在instantclient_11_2目录下新建两层文件夹\NETWORK\ADMIN，再在ADMIN文件夹下面建一个tnsnames.ora文件,然后向文件中添加如下内容：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ORACLE =
 (DESCRIPTION =
   (ADDRESS = (PROTOCOL = TCP)(HOST = localhost)(PORT = 1521))
   (CONNECT_DATA =
     (SERVER = DEDICATED)
     (SERVICE_NAME = ORACLE)
   )
 )

LISTENER_ORACLE =
 (ADDRESS = (PROTOCOL = TCP)(HOST = localhost)(PORT = 1521))

ORACLR_CONNECTION_DATA =
 (DESCRIPTION =
   (ADDRESS_LIST =
     (ADDRESS = (PROTOCOL = IPC)(KEY = EXTPROC1521))
   )
   (CONNECT_DATA =
     (SID = CLRExtProc)
     (PRESENTATION = RO)
   )
 )

以上的内容可进行拷贝：dbhome_1\network\admin\tnsnames.ora。

  • 安装PL/SQL Developer
  • PL/SQL Developer的配置

安装完成之后，运行PL/SQL Developer，此时出现的登录窗体不能进行登录，点击Calcel按钮，这时会在无登录状态下进入。
配置相应信息，把之前的解压包信息配置上

  • 重新启动PL/SQL Developer进行登录。

发表于 | 分类于
1、定义
  • ServletConfig：Servlet的配置对象，容器在初始化Servlet时通过它传递信息给Servlet。
  • ServletContext：上下文对象，提供了一系列方法供Servlet与Web容器交互。
    2、创建时机
  • ServletConfig：在容器初始化Servlet的时候，并为其提供上下文初始化参数的名/值对的引用。
  • ServletContext：容器启动的时候，并为其提供Servlet初始化参数的名/值对的引用。
    3、作用范围（可见性）
  • ServletContext：每个JVM中每个Web应用一个ServletContext。
  • ServletConfig：每个JVM中每个Web应用的每个Servlet一个ServletConfig。所以ServletConfig=Servlet初始化参数，ServletContext=上下文初始化参数。