JLU数据结构荣誉课——第三次上机实验
7-1 二叉树最长路径 (100 分)
给定一棵二叉树T，求T中的最长路径的长度，并输出此路径上各结点的值。若有多条最长路径，输出最右侧的那条。
输入格式:
第1行，1个整数n，表示二叉树有n个结点， 1≤n≤100000.
第2行，2n+1个整数，用空格分隔，表示T的扩展先根序列， -1表示空指针，结点用编号1到n表示。
输出格式:
第1行，1个整数length，length表示T中的最长路径的长度。
第2行，length+1个整数，用空格分隔，表示最右侧的最长路径。
输入样例:
在这里给出一组输入。例如：
5
1 2 -1 -1 3 4 -1 -1 5 -1 -1
输出样例:
在这里给出相应的输出。例如：
2
1 3 5
考察方法： 本题考查树的基本运算，包括： 建立一棵二叉树``遍历树``求树的深度 思路：题中所给按照先根遍历建树，然后按照递归遍历求出高度，这里是可以用递归的，只要先求出每个结点的高度 再存入数组下标为树节点data所对应的值，即可保存在之后输出路径的时候可以直接查找比较。
下面就是代码：
建树：
struct TNode {
ElementType Data;
BinTree Left;
BinTree Right;
};//树节点
BinTree CreatBinTree()
{
int num;
BinTree t = NULL;
scanf("%d", &num);
if (num == -1)
{
return NULL;
}//递归出口
t = (BinTree)malloc(sizeof(struct TNode));
t->Data = num;
t->Left = CreatBinTree();//创建左子树
t->Right = CreatBinTree();//创建右子树
return t;
}
求深度：
int height(BinTree T)
{
if (T == NULL)
{
return -1;
}
int hl = height(T->Left);//求取左子树
int hr = height(T->Right);//求取右子树
if (hl > hr)
{
d[T->Data] = hl + 1;
return hl + 1;
}
else
{
d[T->Data] = hr + 1;
return hr + 1;
}
}
求路径：
void path(BinTree T)
{
while (T != NULL)
{
int hl=0, hr=0;
if (T->Left != NULL)
hl = d[(T->Left)->Data];
else
hl = -1;
if (T->Right != NULL)
hr = d[(T->Right)->Data];
else
hr = -1;
if (count1 == -1 && hl > hr) { count1 = hl; printf("%d\n", count1 + 1); }
else if (count1 == -1 && hl <= hr) { count1 = hr; printf("%d\n", count1 + 1); }
printf("%d", T->Data);
if (T->Left != NULL || T->Right != NULL)
printf(" ");
if (hl > hr) T = T->Left;
else T = T->Right;
}
}
原程序：
#include<cstdio>
#include<cstdlib>
using namespace std;
typedef int ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
int d[100001];//存路径长度数组
int count1 = -1;
struct TNode {
ElementType Data;
BinTree Left;
BinTree Right;
};
BinTree CreatBinTree()
{
int num;
BinTree t = NULL;
scanf("%d", &num);
if (num == -1)
{
return NULL;
}
t = (BinTree)malloc(sizeof(struct TNode));
t->Data = num;
t->Left = CreatBinTree();
t->Right = CreatBinTree();
return t;
}
int height(BinTree T)
{
if (T == NULL)
{
return -1;
}
int hl = height(T->Left);
int hr = height(T->Right);
if (hl > hr)
{
d[T->Data] = hl + 1;
return hl + 1;
}
else
{
d[T->Data] = hr + 1;
return hr + 1;
}
//return 1+max(height(T->Left),height(T->Right));
}
void path(BinTree T)
{
while (T != NULL)
{
int hl=0, hr=0;
if (T->Left != NULL)
hl = d[(T->Left)->Data];
else
hl = -1;
if (T->Right != NULL)
hr = d[(T->Right)->Data];
else
hr = -1;
if (count1 == -1 && hl > hr) { count1 = hl; printf("%d\n", count1 + 1); }
else if (count1 == -1 && hl <= hr) { count1 = hr; printf("%d\n", count1 + 1); }
printf("%d", T->Data);
if (T->Left != NULL || T->Right != NULL)
printf(" ");
if (hl > hr) T = T->Left;
else T = T->Right;
}
}
int main()
{
int num;
scanf("%d", &num);
BinTree T = CreatBinTree();
height(T);
path(T);
printf("\n");
return 0;
}
反思：上机考试的时候被卡空间了，但是没想那么多，但其实节省空间的方法有很多。
7-2 森林的层次遍历 (100 分)
给定一个森林F，求F的层次遍历序列。森林由其先根序列及序列中每个结点的度给出。
输入格式:
第1行，1个整数n，表示森林的结点个数， 1≤n≤100000.
第2行，n个字符，用空格分隔，表示森林F的先根序列。字符为大小写字母及数字。
第3行，n个整数，用空格分隔，表示森林F的先根序列中每个结点对应的度。
输出格式:
1行，n个字符，用空格分隔，表示森林F的层次遍历序列。
输入样例:
在这里给出一组输入。例如：
14
A B C D E F G H I J K L M N
4 0 3 0 0 0 0 2 2 0 0 0 1 0
输出样例:
在这里给出相应的输出。例如：
A M B C G H N D E F I L J K
解法一：
思路：本题使用原始方法，包括: 分为森林的建立``森林的层次遍历 解法：运用递归来建立树(树用三个数组来模拟，未建立结构体)，其中引入虚根来使整个森林变成一棵树，然后通过队列结构进行遍历输出， 在虚根处引入特判。
建树：
void Createforest()//是原森林中的每一棵树的创建
{
int j = num2;
for (int i = 1; i <= data1[j]; i++)
{
child[j].push_back(++num2);
if (data1[num2] != 0)
{
Createforest();
}
}
}
inline void Createforest1()//调用Createforest,将每次生成的树连到虚根(这里记为全局数组统一标号为[0]的结点)
{
while (num2 <= num1)
{
child[0].push_back(num2);
Createforest();
num2++;
}
}
遍历树：
inline void printforest()
{
while (!Q.empty())
{
int n = Q.front();
Q.pop();
int size = child[n].size();
for (int i = 0; i < size; i++)//该结点的子结点全部入队
{
Q.push(child[n][i]);//这里把字符数组标号压入
}//进队操作
if (n != 0)//特判：不能把虚根的数据输出来
{
printf("%c", ch[n]);
if (!Q.empty())
printf(" ");
}
}
}
代码：
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
int data1[100002];//存放每个字符对应的子结点数
char ch[100002];//存放每个字符
vector<int>child[100002];//存放每个结点的子结点标号，child[x].size()为子结点数
int num2 = 1;
int num1;
queue<int>Q;
inline void printforest()
{
while (!Q.empty())
{
int n = Q.front();
Q.pop();
int size = child[n].size();
for (int i = 0; i < size; i++)
{
Q.push(child[n][i]);
}
if (n != 0)
{
printf("%c", ch[n]);
if (!Q.empty())
printf(" ");
}
}
}
void Createforest()
{
int j = num2;
for (int i = 1; i <= data1[j]; i++)
{
child[j].push_back(++num2);
if (data1[num2] != 0)
{
Createforest();
}
}
}
inline void Createforest1()
{
while (num2 <= num1)
{
child[0].push_back(num2);
Createforest();
num2++;
}
}
int main()
{
scanf("%d\n", &num1);
for (int i = 1; i <= num1; i++)
{
scanf("%c", &ch[i]);
getchar();
}
int i = 1;
for (; i <= num1; i++)
{
scanf("%d", &data1[i]);
}
Createforest1();
Q.push(0);
printforest();
//printf("\n");
return 0;
}
反思：效率还行，空间复杂度可以达到O(n)，但是要是直接开成直观的结点结构体，会显示内存超限，因此不是最优解。
方法二：
思路：通过栈来存储，在压栈的过程中，可以通过栈的深度来确定树的层数(深度)，然后将每个结点压入所在层的容器中 然后在层次遍历中及直接遍历各层的容器就可以得到层次遍历效果。
比较：与方法一比较，时间复杂度未变，空间复杂度降为O(1)值得使用。
代码如下：
#include<vector>
#include<stack>
#include<list>
#include<algorithm>
#include<map>
#include<iostream>
using namespace std;
map <int,list<char> >p;
char m[100005];int a[100005];
int top=0;
int main() {
int n, i, j, k, l;
scanf("%d", &n);
char c;
for (i = 0;i < n;++i) {
scanf("%c", &c);
while (1) {
if((c >= '0' && c<='9') || (c >= 'a' && c<='z') || (c >= 'A' && c<='Z'))
break; //读取字符的时候可能有换行或者空格
scanf("%c", &c);
}
m[i] = c;
}
for (i = 0;i < n;++i) {
scanf("%d", &a[i]);
}
stack<int>q;//存储其下标
top = 0;
while (top < n) {//使每一个元素都入栈一次
q.push(top);
if (!q.empty()) {//由于是多棵树所以我们要判栈空
i = q.top();//取出第一个元素
while (!a[i]) {//度为0则出栈然后使其父结点度-1如果仍为0则继续出栈直到不为0或栈空。
q.pop();
j = q.size();
p[j].push_back(m[i]);//在第j层加入对应的元素
if (!q.empty()) {
i = q.top(); a[i]--;
}
else//栈空就跳出循环
break;
}
}
top++;//加入新元素
}
printf("%c", p[0].front());//按照规定输出
p[0].pop_front();
j = 0;
for (i = 1;i < n;++i) {
if (p[j].empty())
j++;
printf(" %c", p[j].front());p[j].pop_front();
}
}
7-3 纸带切割 (100 分)
有一条细长的纸带,长度为 L 个单位，宽度为一个单位。现在要将纸带切割成 n 段。每次切割把当前纸带分成两段，切割位置都在整数单位上，切割代价是当前切割纸带的总长度。每次切割都选择未达最终要求的最长纸带切割，若这样的纸带有多条，则任选一条切割。如何切割，才能完成任务，并且总代价最小。
输入格式:
第1行，1个整数n，表示切割成的段数，1≤n≤100000.
第2行，n个整数Li，用空格分隔，表示要切割成的各段的长度，1≤Li≤200000000，1≤i≤n.
输出格式:
第1行，1个整数，表示最小的总代价。
第2行，若干个整数，用空格分隔，表示总代价最小时每次切割的代价。
输入样例:
在这里给出一组输入。例如：
5
5 6 7 2 4
输出样例:
在这里给出相应的输出。例如：
54
24 13 11 6
思路：通过题目得知为哈夫曼树。所以直接使用哈夫曼树进行处理，题目隐性要求就是输出每次创建的 结点。 方法：采用堆优化，使用优先队列。 代码如下：
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
int num = 0;
vector<long long>ans;
typedef long long ll;
priority_queue<ll, vector<ll> ,greater<ll> >Q;
void CreateTree()
{
int k = 0;
ll sum = 0;
while (Q.size()!=1)
{
int num1 = Q.top();
Q.pop();
int num2 = Q.top();
Q.pop();
sum += (num1 + num2);
Q.push(num1 + num2);
ans.push_back(num1+num2);
}//创立结点后，将结点送入ans中，便于下面的遍历输出
printf("%lld\n", sum);
for (auto i = ans.rbegin(); i != ans.rend(); i++)
{
printf("%lld", *i);
printf("%c", i == ans.rend() - 1 ? '\n' : ' ');
}
}
int main()
{
scanf("%d", &num);
int size1;
for (int i = 0; i < num; i++)
{
scanf("%d", &size1);
Q.push(size1);
}
CreateTree();
return 0;
}
反思：如果用的数组模拟，注意1的特判，输出应该统一为”0\n”
7-4 序列乘积 (100 分)
两个递增序列A和B,长度都是n。令 Ai 和 Bj 做乘积，1≤i,j≤n.请输出n*n个乘积中从小到大的前n个。
输入格式:
第1行，1个整数n，表示序列的长度， 1≤n≤100000.
第2行，n个整数Ai，用空格分隔，表示序列A，1≤Ai≤40000，1≤i≤n.
第3行，n个整数Bi，用空格分隔，表示序列B，1≤Bi≤40000，1≤i≤n.
输出格式:
1行，n个整数，用空格分隔，表示序列乘积中的从小到大前n个。
输入样例:
在这里给出一组输入。例如：
5
1 3 5 7 9
2 4 6 8 10
输出样例:
在这里给出相应的输出。例如：
2 4 6 6 8
作者` `谷方明` `单位` `吉林大学` `代码长度限制` `16 KB` `时间限制` `100 ms` `内存限制` `5 MB
思路:n*n的数据经过排列形成特殊矩阵，该矩阵的特点是：最左列对于每一行来说最小 所以先将最左列压入优先队列中，然后弹出第一小的数输出，取该数在矩阵中的位置，将该数 的坐标加一送到优先队列中，保持优先队列始终有且只有100个元素。 方法：涉及堆优化和对坐标的存储。
代码如下：
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int a[100001];//A序列
int b[100001];//B序列
typedef long long ll;
struct point
{
int x1, y1;
ll val;
bool operator<(const point&r)const
{
return r.val < val;
}
point(int x, int y, ll v) :x1(x), y1(y), val(v) {};
};
priority_queue<point>Q;
int main()
{
int num;
scanf("%d", &num);
for (int i = 1; i <= num; i++)
scanf("%d", &a[i]);
for (int i= 1; i <= num; i++)
{
scanf("%d",&b[i]);
if (i == 1)
{
for (int j = 1; j <= num; j++)
Q.push(point(j, 1, a[j] * b[1]));//先将第一列放入堆中
}
}
for (int i = 1; i <= num; i++)
{
point p = Q.top();
printf("%lld",p.val);
Q.pop();
if (p.y1 < num)Q.push(point(p.x1, p.y1 + 1, a[p.x1] * b[p.y1 + 1]));//行元素右移操作
printf("%c", i == num ? '\n' :' ');
}
return 0;
}
反思：大佬给的经验，用结构体来当结点，定位方便。注意移位的时候，可能超出范围列的界限。