文档章节

学习《数据结构与算法》笔记01 栈和队列

太猪-YJ
 太猪-YJ
发布于 07/15 17:48
字数 4080
阅读 8
收藏 0

Day1:

java对象之间的赋值:

// 两个对象使用"="号相连,意味着它们指向同一个地址,当A对象对属性进行操作后,B对象的值也会改变;

People A = new People ();
People B = new People ();
A.setAge(20);
A.setName("test");
B.setAge(A.getAge());
B.setName(A.getName()); // 也等于20      

// 如果希望两个对象只是值相等,那么需要调用构造方法,开辟两个独立的存储空间,通过get/set方法,将字段的值分别赋予

People A = new People ();
People B = new People ();
A.setAge(20);
A.setName("test");
B.setAge(A.getAge());
B.setName(A.getName());

// "=="是对引用地址的比较,判断两个对象是否指向了同一个内存地址。

People a = new People(5);
People b;
b = a;
a.setAge(20);

if(a == b){
    System.out.println("a == b true"); // 会输出 a == b true
}

// "equals"方法,默认也是内存地址比较;如果希望equals方法比较对象的属性值,需要重写equals和hashcode方法

public boolean equals(Object obj) {
    return (this == obj);
}
@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;

    People people = (People) o;

    return age == people.age;
}

@Override
public int hashCode() {
    return age;
}

数组的增、删、改:

  • 数组在创建时,需要指定长度,且数组的长度是固定的。
  • 数组分为无序数组和有序数组,有序数组是按照数组元素中的某个或某几个属性来区分大小,进行排序。
  • 数组在做删除操作时,需要将删除元素下标之后的元素,进行向前位移,填补删除的元素留下的“洞”。
  • 无序数组在做操作时,只会使用线性方式,即顺着下标从0开始挨个查找,查找某个元素的平均操作是N/2;删除某个元素,需要移动数组的平均操作是N/2。例如10条记录的数组,线程查找平均操作次数是5次,平均移动元素次数也是5次。
  • 有序数组,在做查找操作时,可以使用二分法,二分法可以有效提高大数据量有序数组的查找效率大大降低操作次数,但是在数据量很小的情况下,与线性查找区别不明显。例如100条记录,线性查找平均需要50次,二分法需要7次;对于1000条记录,结果是500比10;100000条记录是50000比20。
  • 有序数组,在查找效率上,比无序数组要快;但是在新增操作上,比无序数组要慢,因为需要找到合适的位置插入元素,并且将其他元素向后移动。所以有序数组适合频繁查找的情况。如果新增和删除操作频繁的情况,则无法高效工作。
  • 有序数组和无序数组的删除操作一样很慢,因为需要将后面的元素向前位移。

如何获取算法的比较次数,通常我们使用对数;如何获取算法的运行时间,通常我们使用大O表示法

对分:分成两半

对数:s = log2(r) s就是对数,它表示算法的比较次数,r是范围或数组的长度,2是底数,即2的s次幂大于等于r;以10为底数求对数,其结果通常是以2为底数求对数的3.322倍,比如log10(100)=2,乘以3.322,就是6.644,四舍五入就是7,这正是log2(100)的结果。因为所有的对数,都和log10成比例,所以我们经常用logN来表示对数。

大O:大O表示法使用大写字符O,意思为"order of"大约是。我们使用大O表示法来描述线性查找使用了O(N)级时间,二分查找使用了O(logN)级时间。向一个无序数组中插入记录,使用了O(1)时间或常数级时间。

图中结果显示了一些时间与数据项个数的大O关系。N标识数组的项目个数。通过它我们可以看到不同给的大O值:O(1)是优秀,O(logN)是良好,O(N)是还可以,在冒泡排序等其他算法中,还会出现O(N的2次方)这样时间,性能要差一些。

大O表示法,实质并不是对运行时间给出实际值,而是表达了运时间是如何受到项目个数影响的。

DAY2:

冒泡排序法:

冒泡排序法代码如下:

public class Test {
    public static void main(String[] args) {
        int[] arr = {10, 40, 30, 20, 70, 60, 50, 90, 80, 9};
        int count_compare = 0;
        int count_for = 0;

        /* for (int j = 0; j < arr.length; j++) {
            for (int i = 0; i < arr.length - 1; i++) {
                if (arr[i] > arr[i + 1]) {
                    int temp = arr[i + 1];
                    arr[i + 1] = arr[i];
                    arr[i] = temp;
                }
                count_compare++;
            }
            count_for ++;
        } */

        for (int j = arr.length; j > 1; j-- ) {
            for (int i = 0; i < j - 1; i++) {
                if (arr[i] > arr[i + 1]) {
                    int temp = arr[i + 1];
                    arr[i + 1] = arr[i];
                    arr[i] = temp;
                }
                count_compare++;
            }
            count_for ++;
        }
        System.out.println("count_compare = " + count_compare);
        System.out.println("count_for = " + count_for);
        for(int i = 0; i < arr.length; i++){
            System.out.print(arr[i] + " ");
        }
    }

输出结果比较:

count_compare = 90
count_for = 10
9 10 20 30 40 50 60 70 80 90 

count_compare = 45
count_for = 9
9 10 20 30 40 50 60 70 80 90 

冒泡排序效率:

比较次数为:(N-1)+(N-2)+...+1=N*(N-1)/2

当N为10时,N*(N-1)/2等于45既10*(10-1)/2

这样,算法做了约为N的2次方/2次比较,忽略减1

那么冒泡排序的时间级别为O(N的2次方),因为大O表示法,会排除掉常量,只体现N(元素个数)对算法时间的影响。

 当一层循环外面套着一层循环时,就意味着大约要执行N*N或者N的2次方次某个基本操作。

选择排序:

选择排序法代码如下:

        int[] arr = {10, 40, 30, 20, 70, 60, 50, 90, 80, 9};
        int count_compare = 0;
        int count_for = 0;

        for (int i = 0; i < arr.length - 1; i++) {
            count_for++;
            for (int j = i + 1; j < arr.length; j++) {
                count_compare++;
                if (arr[j] < arr[i]) {
                    int temp = arr[j];
                    arr[j] = arr[i];
                    arr[i] = temp;
                }
            }
        }

        System.out.println("count_for = " + count_for);
        System.out.println("count_compare = " + count_compare);


输出结果:count_for = 9
        count_compare = 45
        9 10 20 30 40 50 60 70 80 90 

选择排序,是每次找出最小的元素,放在数组的最左边,然后从最小元素的下一个元素开始和右边的元素比较,找出最小的,继续放在最左边,比较元素的下标向右移动;冒泡排序是每次找出最大的元素放在数组的最右边,并且每次比较元素的下标向左移动。

选择排序效率:

比较次数与冒泡排序是一样的,N*(N-1)/2;运行时间与冒泡排序一样,都是O(N的2次方),但是选择排序元素交换次数比冒泡排序少,所以当交换时间远大于比较时间的情况时,选择排序优于冒泡排序。

插入排序:

插入排序算法,虽然运行时间同样为O(N的2次方),但是在一般情况下,它要比冒泡排序快一倍,比选择排序还要快一些,尽管它比选择排序和冒泡排序要复杂一些,但是通常它都是作为复杂地排序算法的最后阶段。

插入排序代码如下:

        int[] arr = {10, 40, 30, 20, 70, 60, 50, 90, 80, 9};
        int count_compare = 0;
        int count_for = 0;
        
        for (int out = 1; out < arr.length; out++) {
            int temp = arr[out];
            int in = out;
            while (in > 0 && arr[in - 1] >= temp) {
                arr[in] = arr[in - 1];
                --in;
                count_compare++;
            }
            arr[in] = temp;

            count_for++;
        }

        System.out.println("count_for = " + count_for);
        System.out.println("count_compare = " + count_compare);

在外层的for循环中,out变量从1开始,向右移动。它标记了未排序部分的最左端的数据,而在内层的while循环中,in变量从out变量开始,向左移动,直到temp变量小于in所指的数组元素,或者它已经不能再向左移动为止,while循环每一趟都向右移动了一个已排序的数据项。

在每趟排序结束后,下标在out下标号小的数据项,都是局部有序的。

输出结果:

count_for = 9
count_compare = 16
9 10 20 30 40 50 60 70 80 90 

插入排序效率: 

比较次数:N*(N-1)/2,然后,因为在每一趟排序发现插入点之前,平均只有一半的数据项真的进行了比较,我们除以2得到N*(N-1)/4。

运行时间也是O(N的2次方)

对于已经有序,或者基本有序的数组,插入排序的while子句,基本上是不会执行的,那么算法的运行时间就是O(N)或接近于O(N),但是对于逆序列,每次都要经过while循环,比较和赋值,它的效率不会比冒泡和选择排序快。

小计:

算法的常见操作,比较,交换(赋值)和复制,其中复制复杂度或时间消耗度是交换的三倍。

算法的不变性:就是在算法中,某个被标记的对象(或下标),它的左边或右边,已经是完成排序的元素,位置不会再变化了。

算法的稳定性:在对主关键词进行排序的同时,也同样对次关键词进行排序。比如对州按照人口进行排序的同时,也对每个州的城市按照人口进行排序。

DAY3:

栈、队列和优先级队列

栈 Stack

栈只允许访问一个数据项:即最后插入的数据项。移除这个数据项后,才能访问倒数第二个数据项,并以此类推。一个入口/出口,先进后出。

栈在解析表达式方面有很大作用。

栈的实现代码:

public class Test {
    public static void main(String[] args) {
        Stack theStack = new Stack(10);
        theStack.push(10);
        theStack.push(40);
        theStack.push(80);
        theStack.push(20);
        while(!theStack.isEmpty()){
            long value = theStack.pop();
            System.out.print(value);
            System.out.print(" ");
        }
    }
}
class Stack{
    private int maxSize;
    private long[] stackArray;
    private int top;

    public Stack(int maxSize){
        this.maxSize = maxSize;
        this.stackArray = new long[maxSize];
        this.top = -1;
    }

    public void push(long value){
        int i = ++top;
        System.out.println(">>>push top=" + top);
        stackArray[i] = value;
    }

    public long pop(){
        int i = top--;
        System.out.println(">>>pop i=" + i + ", top=" + top);
        return stackArray[i];
    }

    public long peek(){
        return stackArray[top];
    }

    public boolean isEmpty(){
        return (top == -1);
    }

    public boolean isFull(){
        return (top == maxSize);
    }

输出结果:

>>>push top=0
>>>push top=1
>>>push top=2
>>>push top=3
>>>pop i=3, top=2
20 
>>>pop i=2, top=1
80 
>>>pop i=1, top=0
40 
>>>pop i=0, top=-1
10 

我们可以看到,后增加的数据,会先输出出来。注意pop()方法,++top和top--的运算关系是不一样的,运算符在前面,会先对top变量的值进行改变;运算符在后面,会先将top的值赋值出去,再进行运算!pop()和peek()方法,都是获得栈的最后一个元素,但是pop()获得元素后,会在栈中删除元素,而peek()不会删除元素。

栈在做单词逆序和匹配分隔符时有作用。

队列 Queue

队列这样的数据结构,就是有一个入口和一个出口,先进入队列的数据,先从出口离开队列;最后进入队列的数据,最后离开队列,保证数据在队列中的有序的。

循环队列:环绕式处理/缓冲环

队列中需要有三个要素:一个是指定了长度的数组;一个是指向下一个该出队数据的下标;一个是指向最后入队数据的下标;

当队列的容量满了,这时几个排在前面的数据出队了,我们看到维护队头的下标,从0指向了3,而维护队尾的下标,还停留在9上。此时我们想向队列增加新的数据,怎么办?

从上图我们可以看到,维护队尾的下标,回绕到了下标0的位置;新的数据项插入到了下标0这个位置,队尾的指针颠倒了初始的位置。当出队的数据项足够多,我们发现队头的指针也回绕了,此时如果队尾的指针大于队头的指针,队列又恢复为单一的连续的序列。

环绕队列的代码实现:

package queue;

/**
 * @author yangjian
 * @date created in 11:02 2019/07/17
 */
public class Queue {
    private int maxSize;
    private long[] queArray;
    private int front;
    private int rear;
    private int nItems; // 这个是什么作用?

    public Queue(int maxSize) {
        this.maxSize = maxSize;
        this.queArray = new long[maxSize];
        this.front = 0;
        this.rear = 0;
        this.nItems = 0;
    }

    public void insert(long value) {
        if (rear == maxSize) { // 如果队尾指针,已经超过了队列的末尾,则回绕到0,从新开始插入数据项
            rear = 0;
        }
        queArray[rear] = value;
        rear++; // 每次插入数据项,下标向右移动
        nItems++;
    }

    public long remove() {
        long temp = queArray[front]; // 获取当前该出队的数据项
        System.out.println("=== remove: front=" + front + ", temp=" + temp);
        queArray[front] = 0; // 用0占位,标识该下标的元素被删除
        front++; // 队头指针向后移
        if (front == maxSize) { // 如果向后移动的队头指针已经等于maxSize即超过了队列的下标范围,则回绕到0
            front = 0;
        }
        nItems--;
        return temp;
    }

    public long peekFront(){
        return queArray[front];
    }

    public boolean isEmpty(){
        return (nItems == 0);
    }

    public boolean isFull(){
        return (nItems == maxSize);
    }

    public int size(){
        return nItems;
    }

    public long[] getQueArray(){
        return queArray;
    }

    public int getFront(){
        return front;
    }

    public int getRear(){
        return rear;
    }

 }
class QueueApp{
    public static void main(String [] args){
        Queue theQueue = new Queue(5);
        theQueue.insert(10);
        theQueue.insert(20);
        theQueue.insert(30);
        theQueue.insert(40);
        theQueue.insert(50);

        theQueue.insert(60);
        theQueue.insert(70);
        theQueue.insert(80);

        System.out.println("rear = " + theQueue.getRear());

        for(int i = 0; i < theQueue.getQueArray().length; i++){
            System.out.print(theQueue.getQueArray()[i] + " ");
        }
        System.out.println("");

        theQueue.remove();
        theQueue.remove();
        theQueue.remove();

        theQueue.insert(50);
        theQueue.insert(60);
        theQueue.insert(70);
        theQueue.insert(80);

        System.out.println("");
        System.out.println("rear = " + theQueue.getRear());

        for(int i = 0; i < theQueue.getQueArray().length; i++){
            System.out.print(theQueue.getQueArray()[i] + " ");
        }
        System.out.println("");
        while (!theQueue.isEmpty()){
            theQueue.remove();
        }
    }
}

输出结果:

rear = 3
60 70 80 40 50 
=== remove: front=0, temp=60
=== remove: front=1, temp=70
=== remove: front=2, temp=80

rear = 2
70 80 0 50 60 
=== remove: front=3, temp=50
=== remove: front=4, temp=60
=== remove: front=0, temp=70
=== remove: front=1, temp=80
=== remove: front=2, temp=0
=== remove: front=3, temp=0
=== remove: front=4, temp=0
=== remove: front=0, temp=0
=== remove: front=1, temp=0

双端队列:

双端队列是一个两端都是结尾的队列。队列的每一端都可以插入数据项和移除数据项。这些方法叫做insertLeft(),rmoveLeft(),insertRight(),removeRight()。

如果双端队列,禁止调用insertLeft()和removeLeft(),那它就是一个栈;如果禁止调用它的insertLeft()和removeRight(),那它就是一个普通队列。

优先级队列:

优先级队列,是在插入新对象时,对队列内的数据项,按照一定规则进行排序。使队头和队尾的数据项始终为最大或最小的项。它的主要特点,集中在insert方法中。优先级队列不像Queue那样,有front和rear指针,它的front总是nItems-1,rear总是0。

下面是我们以数组对象为例子,演示优先级队列:

优先级队列的java代码:

package queue;

/**
 * @author yangjian
 * @date created in 09:19 2019/07/19
 */
public class PriorityQue {
    private int maxSize;
    private long[] queArray;
    private int nItems;

    public PriorityQue(int maxSize) {
        this.maxSize = maxSize;
        this.queArray = new long[maxSize];
        this.nItems = 0;
    }

    /**
     * 重中之重
     *
     * @param value 需要插入的值
     */
    public void insert(long value) {
        int i;
        if (nItems == 0) {
            queArray[nItems++] = value;
        } else {
            for (i = nItems - 1; i >= 0; i--) {
                /*
                 *  从数组最后一个元素开始比较,此时i=nItems-1,queArray[i]就是数组最后位的数据项,
                 *  当最后位数据项大于value时,说明value要插在queArray[i]上,
                 *  queArray[i + 1] = queArray[i]就意味着数组最后位的数据项,向右移动了一位,
                 *  但是queArray[i]已经是数组最后位了,queArray[i + 1]就意味着数组扩容了一位。
                 *  i是越来越小的,直到queArray[i] > value条件不成立,说明value已经找到了合适的位置,终止循环,
                 *  此时我们能拿到i的值,那么就把value插入到queArray[i]的右边,也就是queArray[i + 1]的位置上,
                 *  原来的queArray[i + 1]位置的数据项,已经向右移动过了。
                 *  完成所有操作后,数组容量已经+1了,所以nItems++
                 */
                if (queArray[i] > value) {
                    queArray[i + 1] = queArray[i];
                } else {
                    break;
                }
            }
            queArray[i + 1] = value;
            nItems++;
        }
    }

    public long remove() {
        return queArray[--nItems];
    }

    public long peek() {
        return queArray[nItems - 1];
    }

    public boolean isEmpty(){
        return (nItems == 0);
    }

    public boolean isFull(){
        return (nItems == maxSize);
    }

    public long[] getQueArray(){
        return queArray;
    }
}

class PriorityApp{
    public static void main(String [] args){
        PriorityQue theQue = new PriorityQue(5);
        theQue.insert(10);
        theQue.insert(40);
        theQue.insert(30);
        theQue.insert(20);
        theQue.insert(50);

        long[] que = theQue.getQueArray();
        for(int i = 0; i < que.length; i++){
            System.out.println(que[i]);
        }
        System.out.println("*******************");

        while(!theQue.isEmpty()){
            long item = theQue.remove();
            System.out.println(item);
        }
    }
}


//输出结果:
10
20
30
40
50
*******************
50
40
30
20
10

优先级队列的效率

插叙效率需要O(N),删除操作需要O(1)。可以通过堆来改进插入时间。

© 著作权归作者所有

太猪-YJ
粉丝 12
博文 92
码字总数 97999
作品 0
海淀
私信 提问
数据结构和算法(What Why How)

数据结构和算法是什么? 从广义上讲,数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法。 从狭义上讲,是指某些著名的数据结构和算法,比如队列、堆、栈、二分查找、动态规划等...

hardyyao
2018/10/05
0
0
用js来实现那些数据结构及算法—目录

  首先,有一点要声明,下面所有文章的所有内容的代码,都不是我一个人独立完成的,它们来自于一本叫做《学习JavaScript数据结构和算法》(第二版),人民邮电出版社出版的这本书。github代...

zaking
2018/05/10
0
0
【数据结构与算法】--学习方法

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/YYZZHC999/article/details/89173026 思考: 为什么要学? 最大的感受是学习的过程可以锻炼自己的性能意识,写...

杨晓慧_Hepburn
04/10
0
0
《大话数据结构》读书笔记(1)

其实去年的时候就看过这本书了。只是,基本上是走马观花, 了解了一些基本概念。这次,为了看懂里面的代码,又特地去复习了一下c语言。还记得上次看的时候,感觉算法果然名不虚传,真的难!现...

幽灵君
2018/12/16
0
0
数据结构课程主页-2016级

  新学期,再度起程!   翻转的数据结构课程再度迎来新的一批同学。   前两年,资源建设基本完备,课堂方案逐渐完善,同学们对新型的学习方式设计给予了肯定(参见2014级问卷调查和201...

sxhelijian
2017/08/30
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OpenStack 简介和几种安装方式总结

OpenStack :是一个由NASA和Rackspace合作研发并发起的,以Apache许可证授权的自由软件和开放源代码项目。项目目标是提供实施简单、可大规模扩展、丰富、标准统一的云计算管理平台。OpenSta...

小海bug
昨天
6
0
DDD(五)

1、引言 之前学习了解了DDD中实体这一概念,那么接下来需要了解的就是值对象、唯一标识。值对象,值就是数字1、2、3,字符串“1”,“2”,“3”,值时对象的特征,对象是一个事物的具体描述...

MrYuZixian
昨天
6
0
数据库中间件MyCat

什么是MyCat? 查看官网的介绍是这样说的 一个彻底开源的,面向企业应用开发的大数据库集群 支持事务、ACID、可以替代MySQL的加强版数据库 一个可以视为MySQL集群的企业级数据库,用来替代昂贵...

沉浮_
昨天
6
0
解决Mac下VSCode打开zsh乱码

1.乱码问题 iTerm2终端使用Zsh,并且配置Zsh主题,该主题主题需要安装字体来支持箭头效果,在iTerm2中设置这个字体,但是VSCode里这个箭头还是显示乱码。 iTerm2展示如下: VSCode展示如下: 2...

HelloDeveloper
昨天
7
0
常用物流快递单号查询接口种类及对接方法

目前快递查询接口有两种方式可以对接,一是和顺丰、圆通、中通、天天、韵达、德邦这些快递公司一一对接接口,二是和快递鸟这样第三方集成接口一次性对接多家常用快递。第一种耗费时间长,但是...

程序的小猿
昨天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部