假期周进度报告1(6.18-6.24)

发布时间 2023-06-25 21:40:37作者: 王者归来蔡徐
6.18我已经分配了算法与数据结构的一阶段小组,和德民,垚基,旭彤我们分工明确,

1. 7-2 关键路径 

2.7-5 哈夫曼编码译码

3.7-10 寻找大富翁

4. 7-11 二路归并排序

我分到了这四个题目在今天完成了关键路径的问题

6.19今天尽力完成最终关键路径的问题,开始了哈夫曼编码译码的题目。创建哈夫曼树根生成的树,前序遍历输出每个字符的哈夫曼编码。根据哈夫曼编码解码

6.20完成了哈夫曼编码译码的问题,写了当日的个人进程。上交学习通,pta报错原因是我把哈夫曼的顺序搞混了,后来改过来,但是思路简单,时间复杂度太大了,资源浪费太多。

6.21今天完成了寻找大富翁的问题这题看上去不难,只是排序,找出前几名大富翁就可以了。但是它难在数据庞大,最大是输入N的数量可以达到10^6,但是要找的大富翁最多却只有10个人。这题如果是用数组或者链表把所有数据储存进去,再排序,这样显然很浪费内存和时间。也很可能超出题目要求的内存限制和时间限制。所有在这里,我的代码解题方式是先定义一个long类型的数组。数组长度为10。判断n和m的大小关系,虽然要找到前m个大富翁,但是题目有一个测试点是输入的人数小于m的。所有要先判断n和m的大小。然后取小的先输入完,填满数组,然后运用快排函数qsort()对数组排序,顺序从大到小。这样数组最后一个元素就是m个大富翁中最小的那个了。然后再继续输入,每次输入都和最后一个元素(即数值最小的元素)比较,如果比最小的这个元素的数值大,那么就把这个数插入到数值合适的位置(这里合适的位置是指不改变数组的非升序排序),排完之后自然把最后一个元素踢出去了。重复以上步骤,便可以找出前m位大富翁了。完成了这个学习通作业。

6.22休息一天出去大洗浴了,很爽

6.23今天完成二路归并排序,归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。

6.24我选择的二阶段题目,车库管理系统,构思了这个过程,用

栈以顺序结构实现,队列以链表结构实现。