关键词:
目录
20182330《程序设计与设计结构》 第十周学习总结
教材学习内容总结
周一: 树
- 树的定义:树是有n个结点组成的有限集合
n=0,为空树
n》0,有特定节点为根 - 特点:非线性结构:一个前驱多个后继 。 其他(除根)到根的路径唯一
- 结点的度:结点的子树数
树的度:结点的最大度数
叶子:度为0 - 分支点:非终端结点
- 结点的层次:根为第一层
- 树的深度:结点的最大层次
- 有序树无序树
- 树和森林
- 树的基本操作
- 查找插入删除
- traverse遍历
- 存储结构
- 双亲表示法
define M 100
class PTNode
ElemType data;
int parent
class tree
PTN items[M]
int root;
int n;
- 孩子表示法
多重链表
孩子链表(类似于链地址法) - 双亲孩子表示法
结合1 2方法 - 孩子兄弟表示法(左孩子右兄弟)
二叉树
- 结点至多为2,子树有左右之分
- 第i层最多有2^(i-1)个结点
- 深度为k最多有2^K-1个
- 叶子比子节点多一n0=n2+1
两种特殊的二叉树
满二叉树
深度为k: 2^k-1
每层:2^i-1
完全二叉树:满去掉最下层最右边
二叉树的遍历(递归性)!!
- 先序:先根后左右
- 中序:先左后根再右
- 后序:左右根
- visit函数 先后无法确定
周三:遍历
- 查询二叉树的某个结点
- 统计叶子结点个数
- 求二叉树的深度:
左右子树最大值加一。后序遍历 - 层序遍历
周五:堆
- 完全二叉树:结点小于或等于左右孩子
包含同样数据的最小堆(小顶堆)不一定一样 - 插入与重排序
作为叶子结点插入,且要保持数的完全性
插入位置:h层最右边空位置(原来不满);h+1层第一个位置 - 删除
- 删除最小值,重构堆
- 删除root,把最后一个叶子移动到根再调整
- 用顺序存储合适:更快定位索引
- 根拿出来组成有序区,筛选调整,(无序区首尾交换)
教材学习中的问题和解决过程
- 问题1:什么叫树的模拟链接策略?
- 问题1解决方案:这种方式使得元素能够连续存储在数组中而不用考虑该树的完全性。因此不会浪费空间,但是该方式增加了删除树中元素的成本。
- 该数组的每一元素都是一个结点类,每一节点存储的是每一孩子(可能还有其双亲)的数组索引,而不是作为指向其孩子(可能还有其双亲)指针的对象引用变量。
- 优点:这种方式是的元素能够连续存储在数组中,因此不会浪费空间。
- 缺点:该方式增加了删除树中元素的成本,因为它要么需要对生育元素进行移位以维持连续状态,要么需要保留一个空闲列表。
一般而言,一棵含有m各元素的平衡n元树具有的高度为lognm。
- 问题2:上课的时候没有听懂左旋和右旋?
问题2解决方案:左旋右旋指的是AVL树(高度平衡的搜索二叉树
一棵平衡树,或是空树,或是具有以下性质的二叉搜索树:左子树和右子树都是AVL树,且左右子树的高度之差的绝对值不超过1。 )的平衡化旋转。
AVL树相较于普通的二叉搜索树,自主要的就是做了平衡化处理,使得二叉树变的平衡,高度降低。
在插入一个结点后应该沿搜索路径将路径上的结点平衡因子进行修改,当平衡因子大于1时,就需要进行平衡化处理。从发生不平衡的结点起,沿刚才回溯的路径取直接下两层的结点,如果这三个结点在一条直线上,则采用单旋转进行平衡化,如果这三个结点位于一条折线上,则采用双旋转进行平衡化。
左单旋
右单旋
双旋转
代码调试中的问题和解决过程
- 问题1:明白算法,但是不知道如何输出一棵树?有哪些输出方法?
- 问题1解决方案:
- 条形输出:输出的结果是[[[1] 3 [[4] 6 [7]]] 8 [10 [[13] 14]]](没有树型)
void puttree(tree t)
if(t==NULL)return;
else
putchar(‘[‘);
puttree(t->left);
printf(“%d ”,t->data);
puttree(t->right);
putchar(‘]’);
- 躺着输出(第一次看到这种输出方法)
可以输出一个树形,但是需要歪着头看
char?bra[]="-/<";
void?puttree(tree?t,int?h)
int?i;
if(t!=NULL)
puttree(t->right,h+1);
for(i=0;i<h;i++)putchar(' ');
printf("%d",t->data);
putchar(bra[
((NULL!=(t->left))<<1)
|(NULL!=(t->right))
]);
putchar('
');
puttree(t->left,h+1);
- 缓冲区输出(没有太理解,暂且不在这里放代码)
自己定义字符缓冲区,先把树形画到缓冲区上,再把缓冲区的内容写到屏幕。对于排序二叉树,需要申请的字符缓冲区大小至少是高为logn宽为n。
- 问题2:优先级队列能不能像普通队列那样循环?
- 他们的实现不同,普通队列是用线性数据结构来实现的。优先队列使用二叉堆来实现的,是非线性结构,保证了它的插入删除时间复杂度都接近O(log2 n);实现不同,能做的功能也不同,优先级队列也无法实现循环遍历。
代码托管
上周考试错题总结
上周无考试
结对及互评
点评过的同学博客和代码
- 本周结对学习情况
- 20182314
- 点评:知识点总结的较为详细,对二叉树的理解很到位,排版简洁,值得学习。
基于评分标准,我给本博客打分:15分。得分情况如下:
感想,体会不假大空的加1分
排版精美的加一分
结对学习情况真实可信的加1分
正确使用Markdown语法
模板中的要素齐全(加1分)
错题学习深入的加1分
点评认真,能指出博客和代码中的问题的加1分
教材学习中的问题和解决过程, 加5分
代码调试中的问题和解决过程,加2分
- 上周博客互评情况
其他(感悟、思考等,可选)
堆的学习是在之前二叉树的基础上,其实优先级队列就是将堆进行一次封装,都调用了堆的函数。
学习进度条
代码行数(新增/累积) | 博客量(新增/累积) | 学习时间(新增/累积) | 重要成长 | |
---|---|---|---|---|
目标 | 5000行 | 30篇 | 400小时 | |
第一周 | 42/42 | 2/2 | 20/20 | |
第三周 | 394/471 | 2/4 | 25/45 | |
第四周 | 394/471 | 2/4 | 25/45 | |
第五周 | 1668/2139 | 2/6 | 35/80 | |
第六周 | 2388/4527 | 1/7 | 30/110 | |
第七周 | 1660 /6187 | 2/9 | 25/135 | |
第八周 | 1660/7847 | 2/11 | 20/130 | |
第九周 | 1660/9507 | 2/13 | 25/155 | |
第十周 | 1144/10651 | 2/15 | 30/185 |
计划学习时间:25小时
实际学习时间:30小时
改进情况:希望提高效率
参考资料
第十周学习知识总结(代码片段)
一、循环双向链结表插入元素intinsert(DList*L,ElemTypee)Linkcurrent=L->head;Linkprevious=L->tail;LinknewNode;intsize=getSize(*L);intposition=0;if(current==NULL)//Case1:当循环双向链结表为空时。newNode=(Link)malloc(sizeof 查看详情
20175333曹雅坤第十周学习总结###教材学习内容总结(代码片段)
20175333曹雅坤第十周学习总结教材学习内容总结第十二章Java多线程机制进程与线程线程是比进程更小的执行单位,一个进程在其执行过程中,可以产生多个线程,形成多条执行线索,每条线索,即每个线程也有它自身的产生、存... 查看详情
201771010108-韩腊梅-第十周学习总结(代码片段)
第十周总结一、知识总结1.定义简单泛型类 1.1一个泛型类Genericclass就是具有一个或多个类型变量的类 1.2Java中,使用E表示集合的元素类型,K和V表示Map的关键字和值的类型。T(需要时还可以使用临近的U和S)表示... 查看详情
李瑞红201771010111第十周学习总结(代码片段)
---恢复内容开始---实验十 泛型程序设计技术实验时间2018-11-1第一部分:理论知识总结1.泛型也称为参数化类型,就是在定义类、方法、接口时,通过类型参数指示将要处理的对象类型。.2.泛型程序设计:编写代码可以被很多... 查看详情
杨玲201771010133《面向对象程序设计(java)》第十周学习总结(代码片段)
《面向对象程序设计(java)》第十周学习总结第一部分:理论知识学习部分 第八章 泛型程序设计一、泛型程序设计的定义1、JDK5.0中增加的泛型类型,是Java语言中类型安全的一次重要改进。2、泛型:也称参数... 查看详情
第十周总结(代码片段)
总结:第十周总结第十周编程总结总结感想执行命令:holleword9序列一:1序列二:2序列三:39列表一:4列表二:5列表三:69排行一:7排行二:8排行三:9 查看详情
201771010112罗松《面向对象程序设计(java)》第十周学习总结(代码片段)
&n 查看详情
第十周java学习总结
目录第十周java学习总结学习内容代码上传截图代码链接第十周java学习总结学习内容第12章Java多线程机制主要内容Java中的线程Thread类与线程的创建线程的常用方法线程同步协调同步的线程线程联合GUI线程计时器线程重点和难点重... 查看详情
201771010134杨其菊《面向对象程序设计java》第十周学习总结(代码片段)
第8章泛型程序设计学习总结 第一部分:理论知识 主要内容: 什么是泛型程序设计 泛型类的声明及实例化的方法   查看详情
狄慧201771010104《面向对象程序设计(java)》第十周学习总结(代码片段)
实验十 泛型程序设计技术实验时间2018-11-1第一部分:理论知识学习部分(一)、泛型程序设计的定义1、JDK5.0中增加的泛型类型,是Java语言中类型安全的一次重要改进。2、泛型:也称参数化类型(parameterizedtype),就是在定义类、... 查看详情
徐思201771010132《面向对象程序设计(java)》第十周学习总结(代码片段)
一、理论知识部分泛型:也称参数化类型,就是在定义类、接口和方法时,通过类型参数指示将要处理的对象类型。(如ArrayList类)泛型程序设计(Genericprogramming):编写代码可以被很多不同类型的对象所重用。一个泛型类(gen... 查看详情
201771010128王玉兰《面向对象程序设计(java)》第十周学习总结(代码片段)
第一部分:理论知识部分总结:(1)定义简单泛型类:A:泛型:也称参数化类型(parameterizedtype),就是在定义类、接口和方法时,通过类型参数指示将要处理的对象类型。B:泛型程序设计(Genericprogramming):编写代码可以被很多不... 查看详情
20175120彭宇辰《java程序设计》第十周学习总结(代码片段)
教材内容总结十二章Java多线程机制一、进程与线程、操作系统与进程-线程不是进程,是比进程更小的执行单位。但与进程不同的是,线程的中断和恢复可以更加节省系统的开销。-线程可以共享进程中的某些内存单元。-程序是... 查看详情
王艳201771010127《面向对象程序设计(java)》第十周学习总结(代码片段)
一:理论部分。1.泛型程序设计意味着编写的代码可以被很多不同类型的对象所重用。1)泛型(参数化类型):在定义类、接口和方法时,通过类型参数指示将要处理的对象类型。如ArrayList类是一个泛型程序设计的实例,可以聚... 查看详情
刘志梅2017710101152《面向对象程序设计(java)》第十周学习总结(代码片段)
实验十 泛型程序设计技术实验时间2018-11-11、实验目的与要求(1)泛型程序设计:意味着编写的代码可以被很多不同类型的对象所重用。(ArrayList类可以聚集任何类型的对象)如果在其它地方,若将get的结果强制类型转换... 查看详情
201771010135杨蓉庆《面对对象程序设计(java)》第十周学习总结(代码片段)
1、实验目的与要求(1) 理解泛型概念;(2) 掌握泛型类的定义与使用;(3) 掌握泛型方法的声明与使用;(4) 掌握泛型接口的定义与实现;(5)了解泛型程序设计,理解其用途。一、理论知识泛型类的定义:(1)泛型:... 查看详情
第十周学习知识总结(代码片段)
一、循环双向链结表插入元素intinsert(DList*L,ElemTypee)Linkcurrent=L->head;Linkprevious=L->tail;LinknewNode;intsize=getSize(*L);intposition=0;if(current==NULL)//Case1:当循环双向链结表为空时。newNode=(Link)malloc(sizeof(Node));newNode->elem=e;newNode->prev=newNod... 查看详情
第十周编程总结(代码片段)
7-1求奇数和(15分)本题要求计算给定的一系列正整数中奇数的和。1)实验代码#include<stdio.h>intmain() intn,sum=0; scanf("%d",&n); while(n>0) if(n%2!=0) sum+=n; 查看详情