![](/skins/sea/images/title_post.gif)
2014年4月14日
在C/C++中动态分配二维数组可以先申请一维的指针数组,然后该数组中的每个指针再申请数组,这样就相当于二维数组了,但是这种方法会导致每行可能不相邻,从而访问效率比较低。如何申请连续的二维数组了?本文将分别三个方面讲解:
一.动态申请列大小固定的二维数组
二.C语言中动态申请连续的二维数组
三.C++语言中动态申请连续的二维数组
一.动态申请列大小固定的二维数组
首先如果二维数组的列大小固定,那么很简单,可以用申请一维数数组再其指针强制转化成为二维数组指针即可。详见代码:
- //列大小固定的二维数组可以申请一维数据并将指针强转成二维数组
- #include <stdio.h>
- int main()
- {
- printf(" 列大小固定的二维数组可以申请一维数据并将指针强转成二维数组\n");
- printf(" -- by MoreWindows( http://blog.csdn.net/MoreWindows ) --\n\n");
-
- //列值固定
- const int MAXCOL = 3;
-
- int nRow;
- printf("请输入二维数组的行数(列值固定为%d): ", MAXCOL);
- scanf("%d", &nRow);
-
- //申请一维数据并将其转成二维数组指针
- int *pp_arr = new int[nRow * MAXCOL];
- int (*p)[MAXCOL] = (int(*)[MAXCOL])pp_arr;
-
- //为二维数组赋值
- int i, j;
- for (i = 0; i < nRow; i++)
- for (j = 0; j < MAXCOL; j++)
- p[i][j] = i + j;
-
- //输出二维数组
- for (i = 0; i < nRow; i++)
- {
- for (j = 0; j < MAXCOL; j++)
- printf("%5d", p[i][j]);
- putchar('\n');
- }
-
- //释放资源
- delete[] pp_arr;
- return 0;
- }
运行结果如下所示:
![](http://my.csdn.net/uploads/201206/13/1339577619_1663.PNG)
二.C语言中动态申请连续的二维数组
上面的方法虽然方便,但必须要求列的大小固定。下面先来试下在C语言中如何动态申请连续的二维数组。可以采用多申请一些指针,然后这一些指针分别指向后面数据区中对应的位置,如一个3*4的int类型数组,我们先申请大小为sizeof(int*) * 3 + 3 * 4 * sizeof(int)的一维数组设为arr。然后arr[0]存放指向arr + sizeof(int*) * 3这个位置的指针,arr[1]存放指向arr + sizeof(int*) * 3 + 4 * sizeof(int)这个位置的指针, arr[2]存放指向arr + sizeof(int*) * 3 + 2 * 4 * sizeof(int)这个位置的指针。下面用图展示指向的示意:
![](http://my.csdn.net/uploads/201206/13/1339577657_5620.PNG)
详细代码如下,由于指针操作有点小复杂,请读者耐心看:
- //C语言中动态的申请二维数组 malloc free
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- //动态申请二维数组
- template <typename T>
- T** malloc_Array2D(int row, int col)
- {
- int size = sizeof(T);
- int point_size = sizeof(T*);
- //先申请内存,其中point_size * row表示存放row个行指针
- T **arr = (T **) malloc(point_size * row + size * row * col);
- if (arr != NULL)
- {
- memset(arr, 0, point_size * row + size * row * col);
- T *head = (T*)((int)arr + point_size * row);
- while (row--)
- arr[row] = (T*)((int)head + row * col * size);
- }
- return (T**)arr;
- }
- //释放二维数组
- void free_Aarray2D(void **arr)
- {
- if (arr != NULL)
- free(arr);
- }
- int main()
- {
- printf(" C语言中动态的申请二维数组 malloc free\n");
- printf(" -- by MoreWindows( http://blog.csdn.net/MoreWindows ) --\n\n");
-
- printf("请输入行列(以空格分开): ");
- int nRow, nCol;
- scanf("%d %d", &nRow, &nCol);
-
- //动态申请连续的二维数组
- int **p = malloc_Array2D<int>(nRow, nCol);
-
- //为二维数组赋值
- int i, j;
- for (i = 0; i < nRow; i++)
- for (j = 0; j < nCol; j++)
- p[i][j] = i + j;
-
- //输出二维数组
- for (i = 0; i < nRow; i++)
- {
- for (j = 0; j < nCol; j++)
- printf("%4d ", p[i][j]);
- putchar('\n');
- }
-
- free_Aarray2D((void**)p);
- return 0;
- }
运行结果如下:
三.C++语言中动态申请连续的二维数组
可 以看出我们已经成功实现了在C语言中动态申请连续的二维数组,如果上面的程序不使用int类型而使用string类这种类型,那会有什么后果了?肯定的 说,由于没有调用构造函数和析构函数,程序绝对会造成内存泄露。因此要做下改进,下面给出在C++语言中动态申请连续的二维数组的代码,有些C++语法可 能平时见得少,但其实这些语法在STL里面运用还是比较多的,有兴趣的童鞋应该掌握下。
- //C++语言中动态的申请二维数组 new delete
- #include <new>
- #include <cstdio>
- #include <cstdlib>
- #include <string>
- using namespace std;
- //动态申请二维数组
- template <typename T>
- T** new_Array2D(int row, int col)
- {
- int size = sizeof(T);
- int point_size = sizeof(T*);
- //先申请内存,其中sizeof(T*) * row表示存放row个行指针
- T **arr = (T **) malloc(point_size * row + size * row * col);
- if (arr != NULL)
- {
- T *head = (T*)((int)arr + point_size * row);
- for (int i = 0; i < row; ++i)
- {
- arr[i] = (T*)((int)head + i * col * size);
- for (int j = 0; j < col; ++j)
- new (&arr[i][j]) T;
- }
- }
- return (T**)arr;
- }
- //释放二维数组
- template <typename T>
- void delete_Array2D(T **arr, int row, int col)
- {
- for (int i = 0; i < row; ++i)
- for (int j = 0; j < col; ++j)
- arr[i][j].~T();
- if (arr != NULL)
- free((void**)arr);
- }
- int main()
- {
- printf(" C++语言中动态的申请二维数组 new delete\n");
- printf(" -- by MoreWindows( http://blog.csdn.net/MoreWindows ) --\n\n");
-
- printf("请输入行列(以空格分开): ");
- int nRow, nCol;
- scanf("%d %d", &nRow, &nCol);
-
- //动态申请连续的二维数组
- string **p = new_Array2D<string>(nRow, nCol);
-
- //为二维数组赋值
- int i, j;
- for (i = 0; i < nRow; i++)
- for (j = 0; j < nCol; j++)
- {
- char szTemp[30];
- sprintf(szTemp, "(第%d行,第%d列)", i, j);
- p[i][j] = szTemp;
- }
-
- //输出二维数组
- for (i = 0; i < nRow; i++)
- {
- for (j = 0; j < nCol; j++)
- printf("%s ", p[i][j].c_str());
- putchar('\n');
- }
-
- delete_Array2D<string>(p, nRow, nCol);
- return 0;
- }
运行结果如下:
![](http://my.csdn.net/uploads/201206/13/1339577831_2249.PNG)
posted @
2014-04-14 21:37 wuxu 阅读(283) |
评论 (0) |
编辑 收藏
![](/skins/sea/images/title_post.gif)
2013年10月25日
Ubuntu 12.04 安装 VMware Tools,运行vmware-config-tools.pl 时,总是提示
The path "" is not valid.
What is the location of the directory of C header files that match your running
kernel?
输入 /usr/src/linux-headers-3.8.0-29-generic/include
或 /lib/modules/3.8.0-26-generic/build/include 都提示“The path ... is not valid.”。
用了半天时间才找到解决方案 555....分享一下。
1. 更新或安装linux headers
sudo apt-get update
sudo apt-get install build-essential
sudo apt-get install linux-headers-$(uname -r)
2. 关联文件,就是因为找不到这个几个文件,vmware tools才认为路径无效的。
cd /lib/modules/$(uname -r)/build/include/linux
sudo ln -s ../generated/utsrelease.h
sudo ln -s ../generated/autoconf.h
sudo ln -s ../generated/uapi/linux/version.h
就是因为没有最后这个链接,一直失败,郁闷啊。
3. 再次执行安装就ok啦,运行vmware-config-tools.pl 也没问题了。
sudo ./vmware-install.pl
posted @
2013-10-25 15:58 wuxu 阅读(2687) |
评论 (0) |
编辑 收藏
![](/skins/sea/images/title_post.gif)
2013年6月15日
题目链接:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2176RMQ问题,《算法竞赛入门经典——训练指南》上的例题。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 100005;
![](/Images/OutliningIndicators/None.gif)
int n, q;
int a[maxn];
int len;
int val[maxn], cnt[maxn];
int num[maxn], lef[maxn], rig[maxn];
int d[maxn][20];
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
void RLE_proc()
{
len = 0;
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i = 0; i < n; )
{
int j = i + 1;
while(a[j] == a[i] && j < n) j++;
val[len] = a[i];
cnt[len] = j - i;
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int k = i; k < j; k++)
{
num[k] = len;
lef[k] = i;
rig[k] = j - 1;
}
len++;
i = j;
}
}
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
void RMQ_init()
{
for(int i = 0; i < len; i++) d[i][0] = cnt[i];
for(int j = 1; (1<<j) <= len; j++)
for(int i = 0; i + (1<<j) - 1 < len; i++)
d[i][j] = max(d[i][j-1], d[i + (1<<(j-1))][j-1]);
}
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
int RMQ_query(int a, int b)
{
int k = int(log(b-a+1) / log(2.0));
return max(d[a][k], d[b- (1<<k) + 1][k]);
}
![](/Images/OutliningIndicators/None.gif)
int main()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(scanf("%d", &n) != EOF && n)
{
scanf("%d", &q);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
RLE_proc();
RMQ_init();
int a, b;
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i = 0; i < q; i++)
{
scanf("%d%d", &a, &b);
a--;
b--;
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(num[a] == num[b])
{
printf("%d\n", b-a+1);
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
} else
{
int ans = max(rig[a]-a+1, b-lef[b]+1);
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(num[a]+1 <= num[b]-1)
{
ans = max(ans, RMQ_query(num[a]+1, num[b]-1));
}
printf("%d\n", ans);
}
}
}
return 0;
}
![](/Images/OutliningIndicators/None.gif)
posted @
2013-06-15 17:34 wuxu 阅读(239) |
评论 (0) |
编辑 收藏
![](/skins/sea/images/title_post.gif)
2012年1月3日
题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=646
先将每个格子划分为3*3的小格,斜杠占据的小格标记为1,其它的为0。然后遍历即可。
#include <cstdio>
#include <cstring>
![](/Images/OutliningIndicators/None.gif)
int row, col;
int map[230][230];
bool vis[230][230];
![](/Images/OutliningIndicators/None.gif)
int cnt, curLen, maxLen;
bool iscyc;
![](/Images/OutliningIndicators/None.gif)
void dfs(int r, int c)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
if(r < 0 || r >= row || c < 0 || c >= col)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
iscyc = false; // 由于没有分枝,所以能走出图就一定不会构成环。
return;
}
if(map[r][c] || vis[r][c])
return;
vis[r][c] = true;
++curLen;
dfs(r -1, c);
dfs(r, c + 1);
dfs(r + 1, c);
dfs(r, c - 1);
}
![](/Images/OutliningIndicators/None.gif)
int main()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
char ch;
int ca = 0;
while(EOF != scanf("%d%d", &col, &row) && (col || row))
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
row *= 3;
col *= 3;
memset(map, 0, sizeof(map));
memset(vis, 0, sizeof(vis));
for(int i = 0; i < row; i += 3)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
getchar();
for(int j = 0; j < col; j += 3)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf("%c", &ch);
if(ch == '/')
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
map[i][j + 2] = 1;
map[i + 1][j + 1] = 1;
map[i + 2][j] = 1;
}
else if(ch == '\\')
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
map[i][j] = 1;
map[i + 1][j + 1] = 1;
map[i + 2][j + 2] = 1;
}
}
}
cnt = 0;
maxLen = 0;
for(int i = 0; i < row; ++i)
for(int j = 0; j < col; ++j)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(!map[i][j] && !vis[i][j])
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
iscyc = true;
curLen = 0;
dfs(i, j);
if(iscyc)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
++cnt;
if(curLen > maxLen)
maxLen = curLen;
}
}
}
printf("Maze #%d:\n", ++ca);
if(cnt)
printf("%d Cycles; the longest has length %d.\n\n", cnt, maxLen / 3);
else
printf("There are no cycles.\n\n");
}
return 0;
}
![](/Images/OutliningIndicators/None.gif)
posted @
2012-01-03 14:46 wuxu 阅读(350) |
评论 (0) |
编辑 收藏
![](/skins/sea/images/title_post.gif)
2011年12月22日
首先,确定已经使用Tools > Configure tools...配置好了两个工具:qmake –pro, qmake。
qmake –pro 配置如下:
![](/images/cppblog_com/wuxu/g.jpg)
注意:“-project”前有个空格。
qmake 配置如下:
![](/images/cppblog_com/wuxu/v.jpg)
其次,在创建工程时,把输出文件目录中的bin(和obj)都去掉,直接用Debug和Release作为输出目录,如下图。(该步骤为可选) [★]
1. 依次运行qmake –pro, qmake。
2. 在Project > Properties > Project settings中选中”This is a custom Makefile”。![](/images/cppblog_com/wuxu/k.jpg)
3. 如果编译的文件是GUI类型,在Project > Properties > Build targets中将Type设置为”GUI application”。
4. 在Project > Properties > Build targets中将Output filename由原本的 ”bin\debug\projectname.exe” 改成 ”debug\projectname.exe”。(如果在创建工程时执行了带[★]的那步,则该步不需要执行,否则必须执行。)
![](/images/cppblog_com/wuxu/a.jpg)
5. 在Project > Build Options中,分别选择Debug - ”Make” commands和Release - ”Make” commands,做如下修改:
Clean project/target: $make -f $makefile $target-clean
![](/images/cppblog_com/wuxu/c.jpg)
6. 运行Build,即可生成可执行文件。
注意:在Code::Blocks中调试Qt程序时,最好使用Qt官网提供的那个mingw,否则可能由于版本的原因出现不能调试的情况。
posted @
2011-12-22 14:54 wuxu 阅读(1505) |
评论 (0) |
编辑 收藏
![](/skins/sea/images/title_post.gif)
2011年12月2日
题目链接:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=104&page=show_problem&problem=1503
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
using namespace std;
![](/Images/OutliningIndicators/None.gif)
char disk[205][205];
char ourTree[200000];
int line[205];
int r;
![](/Images/OutliningIndicators/None.gif)
inline bool IsNode(char c)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
return isprint(c) && c != '|' && c != '-' && c != ' ' && c != '#';
}
![](/Images/OutliningIndicators/None.gif)
void ConvertTree(int row, int col, int &idx)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
ourTree[idx++] = disk[row][col];
ourTree[idx++] = '(';
if(row + 1 < r && col < line[row + 1] && disk[row + 1][col] == '|')
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int rr = row + 2;
int left = col, right = col;
for( ; left > 0 && disk[rr][left - 1] == '-'; --left);
for( ; right < line[rr] - 1 && disk[rr][right + 1] == '-'; ++right);
for(int i = left; i <= right; ++i)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(i < line[rr + 1] && IsNode(disk[rr + 1][i]))
ConvertTree(rr + 1, i, idx);
}
}
ourTree[idx++] = ')';
}
![](/Images/OutliningIndicators/None.gif)
int main()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
int ca;
scanf("%d", &ca);
getchar();
while(ca--)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
r = 0;
memset(disk, 0, sizeof(disk)); //注意每轮开始时清空数组。如果去掉该句,会wa.
while(gets(disk[r]) && disk[r][0] != '#')
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
line[r] = strlen(disk[r]);
++r;
}
int idx = 0;
ourTree[idx++] = '(';
for(int i = 0; i < line[0]; ++i)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(IsNode(disk[0][i]))
ConvertTree(0, i, idx);
}
ourTree[idx++] = ')';
ourTree[idx++] = '\0';
printf("%s\n", ourTree);
}
return 0;
}
![](/Images/OutliningIndicators/None.gif)
posted @
2011-12-02 18:32 wuxu 阅读(305) |
评论 (0) |
编辑 收藏
![](/skins/sea/images/title_post.gif)
2011年11月29日
摘要: 题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=104&page=show_problem&problem=263
Code highlighting produced by Actipro CodeHighlighter (freeware)ht...
阅读全文
posted @
2011-11-29 21:19 wuxu 阅读(353) |
评论 (0) |
编辑 收藏
posted @
2011-11-29 16:42 wuxu 阅读(398) |
评论 (0) |
编辑 收藏
![](/skins/sea/images/title_post.gif)
2011年11月25日
题目链接:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=104&page=show_problem&problem=233
首先建树,建树的同时算出每个节点的pixels,然后分3种情况递归求解:1、两个都为叶节点;2、有且只有一个为叶节点;3、都不是叶节点。由于每个节点记录了pixels,所以对于情况1、2可以直接返回结果。
#include <iostream>
#include <string>
using namespace std;
![](/Images/OutliningIndicators/None.gif)
struct quadtree
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
int val;
quadtree *t[4];
quadtree()
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
val = 0;
for(int i = 0; i < 4; ++i) t[i] = 0;
}
quadtree(int v)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
val = v;
for(int i = 0; i < 4; ++i) t[i] = 0;
}
bool isLeaf()
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
return !(t[0] || t[1] || t[2] || t[3]);
}
~quadtree()
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for(int i = 0; i < 4; ++i)
if(t[i]) delete t[i];
}
};
![](/Images/OutliningIndicators/None.gif)
quadtree* build(const string &s, int &idx, int pixel)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
if(s[idx] == 'e')
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
++idx;
return new quadtree;
}
else if(s[idx] == 'f')
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
++idx;
return new quadtree(pixel);
}
else// if(s[idx] == 'p')
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
++idx;
quadtree *tree = new quadtree;
for(int i = 0; i < 4; ++i)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
tree->t[i] = build(s, idx, pixel / 4);
tree->val += tree->t[i]->val;
}
return tree;
}
}
![](/Images/OutliningIndicators/None.gif)
int merge_tree(quadtree *t1, quadtree *t2)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
if(t1->isLeaf() && t2->isLeaf())
return t1->val ? t1->val : t2->val;
else if(t1->isLeaf() && !t2->isLeaf())
return t1->val ? t1->val : t2->val;
else if(!t1->isLeaf() && t2->isLeaf())
return t2->val ? t2->val : t1->val;
else
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int ans = 0;
for(int i = 0; i < 4; ++i)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
ans += merge_tree(t1->t[i], t2->t[i]);
}
return ans;
}
}
![](/Images/OutliningIndicators/None.gif)
int main()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
int T;
string s1, s2;
quadtree *tree_head1, *tree_head2;
cin >> T;
while(T--)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
cin >> s1 >> s2;
int idx = 0;
tree_head1 = build(s1, idx, 1024);
idx = 0;
tree_head2 = build(s2, idx, 1024);
int ans = merge_tree(tree_head1, tree_head2);
cout << "There are " << ans << " black pixels." << endl;
if(tree_head1) delete tree_head1;
if(tree_head2) delete tree_head2;
}
return 0;
}
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/None.gif)
posted @
2011-11-25 21:22 wuxu 阅读(411) |
评论 (0) |
编辑 收藏
题目链接:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=104&page=show_problem&problem=489
递归求解,可以不用建树。
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
using namespace std;
const int minn = 100000005;
![](/Images/OutliningIndicators/None.gif)
int inorder[10002];
int postorder[10002];
int leaf, minval;
![](/Images/OutliningIndicators/None.gif)
void proc_tree(int num, int in, int post, int sum)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
if(num == 0) return;
sum += postorder[post];
if(num == 1)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(sum < minval)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
minval = sum;
leaf = postorder[post];
}
else if(sum == minval && leaf < postorder[post])
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
leaf = postorder[post];
}
return;
}
int pos = find(inorder + in, inorder + in + num, postorder[post]) - inorder;
proc_tree(num - (pos - in + 1), pos + 1, post -1, sum);
proc_tree(pos - in, in, post - num + pos - in, sum);
}
![](/Images/OutliningIndicators/None.gif)
int main()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
int n;
string si, sp;
while(getline(cin, si))
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
getline(cin, sp);
n = 0;
stringstream strmi(si);
while(strmi >> inorder[n]) ++n;
n = 0;
stringstream strmp(sp);
while(strmp >> postorder[n]) ++n;
leaf = -1;
minval = minn;
proc_tree(n, 0, n - 1, 0);
cout << leaf << endl;
}
return 0;
}
![](/Images/OutliningIndicators/None.gif)
posted @
2011-11-25 14:50 wuxu 阅读(344) |
评论 (0) |
编辑 收藏