1.学习总结
1.1 树结构学习体会
- 困难：树的构建方法多种、有各种遍历方式以及分为递归和非递归的方式，要掌握下来比较困难， 二叉树中的线索二叉树，画图时会经常出错；哈夫曼树的构造及WPL利用频率进行画图也要花时间弄懂；
- 体会：树里面对于递归的运用狠多，递归原理要知道；开始接触树只学习简单的操作，不知道树的更深用法，现在了解到的是可利用树的相关知识解决一些生活中的app功能，如：微信中的朋友圈，图书管理系统查找等，运用好树的相关知识，就会有些许收获；在学习树的时候，像学姐学长们说的那样，先看图，树方面图挺重要，看懂图再多看几遍代码，两个结合起来，比较容易理解；
1.2树结构思维导图
2.PTA实验作业
- 6-4 jmu-ds-表达式树（代码错误，出现运行超时，还没改对），写了另外一题；
2.1 题目1：7-2 根据后序和中序遍历输出先序遍历
- 根据给定的一棵二叉树的后序遍历和中序遍历结果，输出该树的先序遍历结果；
2.2 设计思路（伪代码或流程图）
结构体：
typedef struct node
{
char data;
struct node *lchild;
struct node *rchild;
}BTNode;
定义循环变量i,j,k, n表二叉树节点个数
整型数组 Post[MAX+1],in[MAX+1]分别存放后续、中序序列
分别输入后续、中序序列
调用函数输出先序序列：
if(n<=0) return;
在Post中找出根节点 r=Post[n-1]
for k=0 to k
在中序遍历序列中找根节点
in[k]==r
输出r
递归调用
end for
2.3 代码截图
2.4 PTA提交列表说明
- 在最后再次递归GetPreorder(Post,in,k)时，内部的Post,in,k三者关系出错，后思考修改成功；
2.1 题目2：7-5 修理牧场
- 计算将木头锯成N块的最少花费
2.2 设计思路（伪代码或流程图）
使用优先队列
priority_queue<int,vector<int>, greater<int> > Q;
定义循环变量i,sum表示总费用, N 指总木头段数
a,b,x 指队列中两个元素
for i=0 to N
Q.push(x) 入队列
while(队中元素个数 > 1)
{
取出队中两个最小的元素
a,b 相加
所得和入队
}
end for
2.3 代码截图
2.4 PTA提交列表说明
- 思路乱；需要先排序，再不断进行最小的两数值和排序，找到最优解输出，会出现运行超时，查资料发现用优先队列可以直接解决，简便快捷；
- DEVC上面编译好提交测试点没出错；
2.1 题目3：7-7 朋友圈
- 计算最大朋友圈中有多少人；
2.2 设计思路（伪代码或流程图）
利用并查集
typedef struct node
{
int data;//存人的编号
int rank;//存节点
}UFSTree;
定义全局数组变量 UFSTree t[max]
i,j循环变量 x,x1,x2表俱乐部集合编号
N,M 总人数和俱乐部数,Max=1
for i=1 to N
并查集初始化
while(俱乐部数)
{
输入俱乐部号 x
for j=1 to x
{
俱乐部人编号 x1,x2
若不是在一个集合, 合并
}
}
比较找最大的节点 Max
end for
2.3 代码截图
2.4 PTA提交列表说明
- 多种错误；运行超时和段错误，通过调试发现在查找X的集合时出现死循环，没法跳出，把Find(x)函数中的返回值由x改为对应的数值；
- 部分正确；段错误，数组溢出，把1000 改为 30000；
3.截图本周题目集的PTA最后排名
3.1 PTA排名
3.2 我的得分：205
4. 阅读代码
/*目录树*/
解题思路：
麻烦的地方在于建树，然后建树之后先序遍历，每次递归一层就多输出两个空格，回溯的时候减少两个输出空格数量。
对每一层的目录和文件按字典序排序，题目要求先输出目录再输出文件，所以先按目录还是文件排序然后再按字典序排序
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e4;
char a[333];
struct p
{
char str[333];
int siz;
int od;
p*next[333];
};
int top;
bool cmp(p *a , p *b)
{
if(a->od!=b->od)return a->od>b->od;
else return strcmp(a->str,b->str)<0;
}
void pre(p*root)
{
int i, j;
for(i=0; i<top; i++)printf(" ");
printf("%s
", root->str);
top++;
char t[333];
for(i=0; i<root->siz; i++)
{
sort(root->next, root->next+root->siz, cmp);
pre(root->next[i]);
}
top--;
return;
}
int main()
{
int n;
cin>>n;
int i, j;
p*root=(p*)malloc(sizeof(p));
for(i=0; i<332; i++)root->next[i]=NULL;
root->siz=0;
strcpy(root->str, "root");
int s=0, k;
char e[333];
p*q;
top=0;
for(i=0; i<n; i++)
{
q=root;
scanf("%s", a);
int siz;
for(j=0; a[j]; j++)
{
if(a[j]=='\')
{
e[s]=' ';
siz=q->siz;
for(k=0; k<q->siz; k++)
{
if(strcmp(e, q->next[k]->str)==0)
{
q=q->next[k];
break;
}
}
if(k>=siz)
{
q->next[q->siz]=(p*)malloc(sizeof(p));
q->next[q->siz]->siz=0;
strcpy(q->next[q->siz]->str, e);
q->siz++;
q=q->next[siz];
q->od=1;
s=0;
}
s=0;
}
else e[s++]=a[j];
}
if(!a[j] && a[j-1]!='\')
{
e[s]=' ';
siz=q->siz;
q->next[q->siz]=(p*)malloc(sizeof(p));
q->next[q->siz]->siz=0;
strcpy(q->next[q->siz]->str, e);
q->siz++;
q=q->next[siz];
q->od=0;
s=0;
}
}
pre(root);
return 0;
}
- 功能：程序实现目录的树状结构的重建工作
- 优点：此篇代码中出现建树、回溯法、排序、递归以及先序遍历等方法进行编程，有利于巩固多方面的知识点；
- 地址：[https://blog.csdn.net/johsnows/article/details/61208333]
- 代码Git提交记录截图
