首页 > 其他 > 详细

2018-2019-1 20172316 《程序设计与数据结构》第三周学习总结

时间:2018-09-26 23:23:31      阅读:168      评论:0      收藏:0      [点我收藏+]

20172316 2017-2018-2《程序设计与数据结构》第三周学习总结

教材学习内容总结

第五章 队列

队列是一种线性结构,队列元素按照FIFO方式处理。

队列和栈十分相似,所以只需要学习好前面两个章节就可以有效地理解“队列”的基本概念了。

其方法的功能上可以大概地一一对应起来
push-->enqueue
pop-->dequeue
peek-->first

所以在最后通过链表、数组来实现队列的问题和实现栈也非常类似,实现起来非常轻松。

值得注意的是实现队列时,要注意两端(front, rear)而非一端(栈中的peek),所以利用固定数组来实现队列的效率不高,而动态的链表会好得多,为了有效利用数组的空闲空间,书上采用了环形数组的方式。


教材学习中的问题和解决过程

  • 环形数组(circular array)相关问题

环形数组的大致概念和原理,可以借助之前介绍过的循环链表进行理解。从概念上来说,如果数组的最后一个索引后面跟的是第一个索引,那么该数组就可用作环形数组。

当front和rear指向同一个位置时,这代表的是队空还是队满呢?
(图)技术分享图片

为区分两种情况,可以空出一个元素空间,当rear的下一个位置是front时为满,当rear和front位置重合时为空。
(图)技术分享图片

何以达到循环的目的呢(最后一个索引后面跟着第一个索引)?可以参照书中的例子:

public void enqueue(T element)
    {
        if (size() == queue.length) 
            expandCapacity();
    
        queue[rear] = element;
        rear = (rear+1) % queue.length;
    
        count++;
    }
    
private void expandCapacity()
    {
        T[] larger = (T[]) (new Object[queue.length *2]);
    
        for (int scan = 0; scan < count; scan++)
        {
            larger[scan] = queue[front];
            front = (front + 1) % queue.length;
        }
    
        front = 0;
        rear = count;
        queue = larger;
    }

这两个方法就很好的解释了环形的实现——通过更新frontrear的值。


代码调试中的问题和解决过程

  • 好像实现了双向链表,并打算应用至LinkedQueue中,发现插队(插在第一个元素之前)的方法思路出现短路。
public void chadui(T element)
    {
        LinearNode<T> node = new LinearNode<>(element);
        if (isEmpty())
            head = node;
        else {
            head.setPrevious(node);
            head = head.getPrevious();
        }
        count++;
    }

(图)技术分享图片
排在后面的人都跑了,看来是队伍断了

public void chadui(T element)
    {
        LinearNode<T> node = new LinearNode<>(element);
        if (isEmpty())
            head = node;
        else {
            node.setNext(head);
            head.setPrevious(node);
            head = head.getPrevious();

        }
        count++;
    }

(图)技术分享图片
加上node.setNext(head);链接起来,队伍重连起来。


代码托管

(statistics.sh脚本的运行结果截图)技术分享图片技术分享图片


上周考试错题总结


学习进度条

代码行数(新增/累积) 博客量(新增/累积) 学习时间(新增/累积) 重要成长
目标 5000行 30篇 400小时
第一周 0/0 1/1 6/6
第二周 771/771 1/2 16/22
第三周 562/1233 1/3 15/37

结对互评

唐才铭19
王文彬29

参考资料

2018-2019-1 20172316 《程序设计与数据结构》第三周学习总结

原文:https://www.cnblogs.com/zhaoqianchen/p/9710594.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!