20172323 2018-2019-1 《程序设计与数据结构》第三周学习总结
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了20172323 2018-2019-1 《程序设计与数据结构》第三周学习总结，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6298字，纯文字阅读大概需要9分钟。
内容图文
20172323 2018-2019-1 《程序设计与数据结构》第三周学习总结
教材学习内容总结
本周学习第五章队列，主要了解了队列的模型（处理过程），并学习了通过几种方式来实现队列，运用队列解决问题以及几种实现队列方式的比较。
5.1 概述
队列是一种线性结构，队列元素按FIFO方式处理，从队列删除元素的次序，与往队列放置元素的次序是一样的。
在栈中，其处理过程只在栈的某一端进行，而在队列中，其处理过程可在队列的两端进行
关于队列的操作
| 操作 | 说明 |
|---|---|
| enqueue | 向队列末端添加一个元素 |
| dequeue | 从队列前端删除一个元素 |
| first | 考察队列前端的那个元素 |
| isEmpty | 判定队列是否为空 |
| size | 判定队列中元素的个数 |
| toString | 返回队列的字符串表示 |
5.2 JavaAPI中的队列
- API没有提供队列类，只提供了一个Queue接口，提供了两个方法add和offer用于添加和插入，element方法可用于检索队列首部的元素，poll和remove用于从队列中删除元素。
5.3 使用队列：代码密钥
import java.util.*;
/**
* Codes demonstrates the use of queues to encrypt and decrypt messages.
*
* @ author 20172323
* @version 4.0
*/
public class Codes {
/**
* Encode and decode a message using a key of values stored in
* a queue.
*/
public static void main (String[] args){
int[] key = {5, 12, -3, 8, -9, 4, 10};
Integer keyValue;
String encoded = "", decoded = "";
String message = "All programmers are playwrights and all " + "computers are lousy actors.";
Queue<Integer> encodingQueue = new LinkedList<>(Integer);
Queue<Integer> decodingQueue = new LinkedList<>(Integer);
/** load key queue */
for (int scan = 0; scan < key.length; scan++){
keyValue = encodingQueue.remove();
encoded += (char) message.charAt(scan) + keyValue;
((LinkedList<Integer>) encodingQueue).add(keyValue);
}
System.out.println("Encoded Message:\n" + encoded + "\n");
/** decode message */
for (int scan = 0; scan < encoded.length(); scan++){
keyValue = decodingQueue.remove();
encoded += (char) message.charAt(scan) - keyValue;
((LinkedList<Integer>) decodingQueue).add(keyValue);
}
System.out.println("Decoded Message:\n" + decoded);
}
}队列的性质使得密钥值能保持正确的顺序，不用担心何时抵达密钥末尾。
5.4 使用队列：售票口模拟
Customer
public class Customer {
private int arrivalTime, departureTime;
public Customer(int arrives) {
this.arrivalTime = arrives;
this.departureTime = 0;
}
public int getArrivalTime() {
return arrivalTime;
}
public void setArrivalTime(int arrivalTime) {
this.arrivalTime = arrivalTime;
}
public int getDepartureTime() {
return departureTime;
}
public void setDepartureTime(int departureTime) {
this.departureTime = departureTime;
}
public int totalTime(){
return departureTime-arrivalTime;
}
}TicketCounter
import java.util.LinkedList;
import java.util.Queue;
public class TicketCounter {
final static int PROCESS = 120;
final static int MAX_CASHIERS = 10;
final static int NUM_CUSTOMERS = 100;
public static void main(String[] args) {
Customer customer;
Queue<Customer> customerQueue = new LinkedList<Customer>();
int[] cashierTime = new int[MAX_CASHIERS];
int totalTime, averageTime, departs;
/** process the simulation for various number of cashiers */
for (int cashiers = 0; cashiers < MAX_CASHIERS; cashiers++) {
/** set each cashiers time to zero initially */
for (int count = 0; count < cashiers; count++)
cashierTime[count] = 0;
/** load customer queue */
for (int count = 1; count <= NUM_CUSTOMERS; count++)
customerQueue.offer(new Customer(count * 15));
totalTime = 0;
/** process all customers in the queue */
while (!(customerQueue.isEmpty())) {
for (int count = 0; count <= cashiers; count++) {
if (!(customerQueue.isEmpty())) {
customer = customerQueue.poll();
if (customer.getArrivalTime() > cashierTime[count])
departs = customer.getArrivalTime() + PROCESS;
else
departs = cashierTime[count] + PROCESS;
customer.setDepartureTime(departs);
cashierTime[count] = departs;
totalTime += customer.totalTime();
}
}
}
/** output results for this simulation */
averageTime = totalTime / NUM_CUSTOMERS;
System.out.println("Number of cashiers: " + (cashiers + 1));
System.out.println("Average time: " + averageTime + "\n");
}
}
}5.5 队列ADT
public interface QueueADT<T> {
public void enqueue (T element);
public T dequeue();
public T first();
public boolean isEmpty();
public int size();
public String toString();
}5.6 用链表实现队列
- head是指向链表首元素的引用，tail指向链表末元素的引用，整型变量count跟踪队列中的元素数目
5.7 用数组实现队列
- 由于队列操作会修改集合的两端，因此将一端固定于索引0处要求移动元素，而非环形数组实现元素移位会产生O（n）的复杂度，所以数组实现的队列操作效率低。
- 把数组看作是环形的，可以除去在队列的数组实现中把元素移位的需要。
- 用环形数组来实现队列，它定义在名为CircleArrayQueue的类中。环形数组并不是一种新结构，它只是一种把数组用来存储队列的方法。从概念上说，如果数组的最后一个索引后面跟的是第一个索引，那么该数组就可用作环形数组。
5.8 双端队列
- 双端队列是队列的扩展，它允许从队列的两端添加、删除和查看元素。
教材学习中的问题和解决过程
- 问题1：关于dequeue操作复杂度的理解问题
- 问题1解决方案：由于队列的特殊性，enqueue操作与dequeue操作必须作用于队列的对立端。在链表的前端进行dequeue操作，在链表的末端进行enqueue操作时，设置一个临时变量指向头结点的next，处理的复杂度为O(1)。在链表的前端进行enqueue操作，在链表的末端进行dequeue操作时，由于需要遍历链表找到倒数第二个结点，其操作复杂度为O(n)。
代码调试中的问题和解决过程
- 问题1：教材上的代码就有很多的问题
- 问题1解决方案：
1.P74代码的Integer应在<>里
Queue<Integer> encodingQueue = new LinkedList<>(Integer);-->Queue<Integer> encodingQueue = new LinkedList<Integer>();
2.P74for循环中的圆括号）多了
encoded += (char) message.charAt(scan) - keyValue;）-->encoded += (char) message.charAt(scan) - keyValue;
3.P83代码中front应该改成head
代码托管
上周考试错题总结
上周没有进行测试，错题 = null。
结对及互评
博客中值得学习的或问题：
- 教材学习内容详实，有自己的理解感悟
- 排版简洁明了
基于评分标准，我给谭鑫的博客打分：5分。得分情况如下：
正确使用Markdown语法（加1分）：
模板中的要素齐全（加1分）
教材学习中的问题和解决过程, 一个问题加1分
代码调试中的问题和解决过程, 一个问题加1分基于评分标准，我给方艺雯的博客打分：5分。得分情况如下：、
正确使用Markdown语法（加1分）：
模板中的要素齐全（加1分）
教材学习中的问题和解决过程, 一个问题加1分
代码调试中的问题和解决过程, 一个问题加1分
点评过的同学博客和代码
其他
最近其他事务很多，所以比较忙，时间也很紧张，但丝毫不能浇灭我敲代码的热情
学习进度条
| 代码行数（新增/累积） | 博客量（新增/累积） | 学习时间（新增/累积） | 重要成长 | |
|---|---|---|---|---|
| 目标 | 5000行 | 30篇 | 400小时 | |
| 第一周 | 0/0 | 1/1 | 8/8 | |
| 第二周 | 470/470 | 1/2 | 12/20 | |
| 第三周 | 685/1155 | 2/4 | 10/30 |
参考资料
内容总结
以上是互联网集市为您收集整理的20172323 2018-2019-1 《程序设计与数据结构》第三周学习总结全部内容，希望文章能够帮你解决20172323 2018-2019-1 《程序设计与数据结构》第三周学习总结所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】