62,614
社区成员
发帖
与我相关
我的任务
分享算法题1道 急求
急求！谢谢大侠们！
使用控制语句将2维字符型数组s[row][2]变成几个1维数组：
如将{{a,b},{b,c},{b,d},{c,d},{d,e},{g,h}}转化为{a,b,c,d,e} {a,b,d,e} {g,h}
又如{{"001","002"},{"001","003"},{"002","003"},{"004","005"}} 转化为 {"001","002","003"} {"001","003"} {"004","005"}
使用控制语句将2维字符型数组s[row][2]变成几个1维数组：
如将{{a,b},{b,c},{b,d},{c,d},{d,e},{g,h}}转化为{a,b,c,d,e} {a,b,d,e} {g,h}
又如{{"001","002"},{"001","003"},{"002","003"},{"004","005"}} 转化为 {"001","002","003"} {"001","003"} {"004","005"}
...全文
请发表友善的回复…
发表回复
chixx123 2008-04-12
- 打赏
- 举报
nothing 看的对啊 呵呵猛
WuBill 2008-04-12
- 打赏
- 举报
怎么在那个帖子下都有这个深圳起点的广告回复
Lt_smile 2008-04-11
- 打赏
- 举报
关注一下，学习
jayflee 2008-04-11
- 打赏
- 举报
楼上似乎理解错了楼主的意思了。warshall算法复杂度是n的立方，不知有没有高效点的算法。
hmsuccess 2008-04-11
- 打赏
- 举报
这要用到递归
ttlxzzccc 2008-04-11
- 打赏
- 举报
这个写得非常好 可是您看啊
我要的结果不是把所有的灾害为起点的链取出来 而是将一个一个单独的不包含的链取出
比如您的结果中{a b c d e}就包含{b c d e} {c d e } {d e} { e }这5个链其实就是{a b c d e}这一个链
而您的结果中不包含我要的另一条链{a b d e}
还是非常感谢您 但是这个逻辑确实不好弄 您做的我都弄不好 呵呵
希望您再帮我个忙
也希望大家帮忙 谢谢了
我要的结果不是把所有的灾害为起点的链取出来 而是将一个一个单独的不包含的链取出
比如您的结果中{a b c d e}就包含{b c d e} {c d e } {d e} { e }这5个链其实就是{a b c d e}这一个链
而您的结果中不包含我要的另一条链{a b d e}
还是非常感谢您 但是这个逻辑确实不好弄 您做的我都弄不好 呵呵
希望您再帮我个忙
也希望大家帮忙 谢谢了
云上飞翔 2008-04-11
- 打赏
- 举报
答：对不起。上边程序有个小BUG，更新如下：
程序运行结果如下：
灾害：a 所引发的灾害链是：{a b c d e }
灾害：b 所引发的灾害链是：{b c d e }
灾害：c 所引发的灾害链是：{c d e }
灾害：d 所引发的灾害链是：{d e }
灾害：e 所引发的灾害链是：{e }
灾害：g 所引发的灾害链是：{g h }
灾害：h 所引发的灾害链是：{h }
public class Warshall {
// s数组表示灾害之间引发关系
static char[][] s={{'a','b'},{'b','c'},{'b','d'},{'c','d'},{'d','e'},{'g','h'}};
//pos数组表示一共有多少个不同的灾害：下标0-第一个灾害，下标1-第二个灾害
static int[] pos={'a','b','c','d','e','g','h'};
//数组b是求最终的灾害关系的传递闭包。即：所有的灾害链。此时全为false
//数组b也就是最终结果
static boolean[][] b=new boolean[pos.length][pos.length];
//对数组b初始化。按照数组s来进行。
private static void init()
{
for(int i=0; i<s.length;i++)
{
b[index(s[i][0])][index(s[i][1])]=true;
//含义：两维数组b中，若'a'与'b'有灾害关系，则b['a']['b']填true。无关是false.
}//for(i)
for(int i=0;i<b.length;i++)
{
b[i][i]=true;//关系的自反性
}
}
// 求关系a的传递闭包
public static void warshall(boolean[][] a)
{
for(int i=0;i<=a.length-1;i++)
{
for(int j=0;j<=a.length-1;j++)
{
if(a[j][i]==true)
{
for(int k=0;k<=a.length-1;k++)
{
a[j][k]=a[j][k] | a[i][k];
}//for(k)
}//if
}//for(j)
}//for(i)
}//warshall
//打印出最终结果
public static void print(boolean[][] a)
{
for(int i=0;i<a.length;i++)
{
System.out.print("灾害："+(char)pos[i]+" 所引发的灾害链是：{");
for(int j=0;j<a.length;j++)
{
if(a[i][j]==true){
System.out.print((char)pos[j]+" ");
}
}//for(j)
System.out.print("} \n");
}//for(i)
}
//返回字符ch在数组pos中的下标
private static int index(char ch)
{
for(int i=0;i<pos.length;i++)
{
if(pos[i]==ch)
{ return i; }
}
return -1;
}
public static void main(String[] args) {
init(); //对数组b初始化。
warshall(b);//求出所有的灾害链
print(b);//打印出所求的结果
}
}
程序运行结果如下：
灾害：a 所引发的灾害链是：{a b c d e }
灾害：b 所引发的灾害链是：{b c d e }
灾害：c 所引发的灾害链是：{c d e }
灾害：d 所引发的灾害链是：{d e }
灾害：e 所引发的灾害链是：{e }
灾害：g 所引发的灾害链是：{g h }
灾害：h 所引发的灾害链是：{h }
云上飞翔 2008-04-11
- 打赏
- 举报
答：其实就是求关系的传递闭包而已。
可用warshall算法。程序如下：
程序运行的结果如下：
灾害：a 所引发的灾害链是：{a b c d e }
灾害：b 所引发的灾害链是：{b c d e }
灾害：c 所引发的灾害链是：{c d e }
灾害：d 所引发的灾害链是：{d e }
灾害：e 所引发的灾害链是：{e }
灾害：g 所引发的灾害链是：{g h }
灾害：h 所引发的灾害链是：{}
可用warshall算法。程序如下：
public class Warshall {
// s数组表示灾害之间引发关系
static char[][] s={{'a','b'},{'b','c'},{'b','d'},{'c','d'},{'d','e'},{'g','h'}};
//pos数组表示一共有多少个不同的灾害：下标0-第一个灾害，下标1-第二个灾害
static int[] pos={'a','b','c','d','e','g','h'};
//数组b是求最终的灾害关系的传递闭包。即：所有的灾害链。此时全为false
//数组b也就是最终结果
static boolean[][] b=new boolean[pos.length][pos.length];
//对数组b初始化。按照数组s来进行。
private static void init()
{
for(int i=0; i<s.length;i++)
{
b[index(s[i][0])][index(s[i][1])]=true;
//含义：两维数组b中，若'a'与'b'有灾害关系，则b['a']['b']填true。无关是false.
b[i][i]=true;//关系的自己性
}//for(i)
}
// 求关系a的传递闭包
public static void warshall(boolean[][] a)
{
for(int i=0;i<=a.length-1;i++)
{
for(int j=0;j<=a.length-1;j++)
{
if(a[j][i]==true)
{
for(int k=0;k<=a.length-1;k++)
{
a[j][k]=a[j][k] | a[i][k];
}//for(k)
}//if
}//for(j)
}//for(i)
}//warshall
//打印出最终结果
public static void print(boolean[][] a)
{
for(int i=0;i<a.length;i++)
{
System.out.print("灾害："+(char)pos[i]+" 所引发的灾害链是：{");
for(int j=0;j<a.length;j++)
{
if(a[i][j]==true){
System.out.print((char)pos[j]+" ");
}
}//for(j)
System.out.print("} \n");
}//for(i)
}
//返回字符ch在数组pos中的下标
private static int index(char ch)
{
for(int i=0;i<pos.length;i++)
{
if(pos[i]==ch)
{ return i; }
}
return -1;
}
public static void main(String[] args) {
init(); //对数组b初始化。
warshall(b);//求出所有的灾害链
print(b);//打印出所求的结果
}
}
程序运行的结果如下：
灾害：a 所引发的灾害链是：{a b c d e }
灾害：b 所引发的灾害链是：{b c d e }
灾害：c 所引发的灾害链是：{c d e }
灾害：d 所引发的灾害链是：{d e }
灾害：e 所引发的灾害链是：{e }
灾害：g 所引发的灾害链是：{g h }
灾害：h 所引发的灾害链是：{}
ttlxzzccc 2008-04-11
- 打赏
- 举报
jayflee正解 非常感谢大家的帮助，结帖了，呵呵。
hyzhx 2008-04-11
- 打赏
- 举报
好像不怎么好写，关注
guxiangzhang 2008-04-11
- 打赏
- 举报
难理解
不懂编程 2008-04-11
- 打赏
- 举报
发了两个贴呀，lz的意思是把首尾相同的二维数组转成一维数组
jayflee 2008-04-11
- 打赏
- 举报
楼主早这样说不就行了 现在很具体了 也很容易明白
ttlxzzccc 2008-04-11
- 打赏
- 举报
不好意思啊 描述起来确实很费劲，呵呵 而且本人描述能力也比较差 呵呵
我再说具体点吧
这是我毕业设计中遇到的一道问题，我的毕业设计有关于灾害的链式管理。
这个具体意义是这样的这个2维数组中的每一个字符代表一个灾害的编号，如a。
而每一个子数组代表一个灾害之间的引发关系，如{a,b}代表着灾害a引发了灾害b。
这样在这个2维数组中就有很多灾害引发关系，如{a,b}代表灾害a引发了灾害b，{b,c}代表灾害b引发了灾害c，{c,d}代表灾害c引发了灾害d。这里明显就有着这样一个链式关系，即a引发b引发c引发d，于是将它们放入一个1维数组中（或一个其它数据结构中，如VECTOR）,形成了一个灾害链式{a,b,c,d}.
谢谢各位大侠了，小弟等。。。
我再说具体点吧
这是我毕业设计中遇到的一道问题，我的毕业设计有关于灾害的链式管理。
这个具体意义是这样的这个2维数组中的每一个字符代表一个灾害的编号，如a。
而每一个子数组代表一个灾害之间的引发关系，如{a,b}代表着灾害a引发了灾害b。
这样在这个2维数组中就有很多灾害引发关系，如{a,b}代表灾害a引发了灾害b，{b,c}代表灾害b引发了灾害c，{c,d}代表灾害c引发了灾害d。这里明显就有着这样一个链式关系，即a引发b引发c引发d，于是将它们放入一个1维数组中（或一个其它数据结构中，如VECTOR）,形成了一个灾害链式{a,b,c,d}.
谢谢各位大侠了，小弟等。。。
ttlxzzccc 2008-04-11
- 打赏
- 举报
哦 是这样的
比较2位数组中每两个子数组的前一个字符和后一个字符，如果相等就将这个链放入令一个数据结构中比如{a,b}和{b,c}比较后放入{a,b,c}， {b,c}和{c,d}比较后发现{c,d}是这个链式接着的发展趋势，于是把d再放入形成{a,b,c,d}，{c,d}和{d,e}将e放入{a,b,c,d,e}
谢谢达人求解
比较2位数组中每两个子数组的前一个字符和后一个字符，如果相等就将这个链放入令一个数据结构中比如{a,b}和{b,c}比较后放入{a,b,c}， {b,c}和{c,d}比较后发现{c,d}是这个链式接着的发展趋势，于是把d再放入形成{a,b,c,d}，{c,d}和{d,e}将e放入{a,b,c,d,e}
谢谢达人求解
fyi1106 2008-04-11
- 打赏
- 举报
是呀，我也看不懂题。
不明白它如何转换。
楼主说详细一些吧。
不明白它如何转换。
楼主说详细一些吧。
云上飞翔 2008-04-11
- 打赏
- 举报
答：提问的艺术。--你究竟想做什么呢？
a,b},{b,c},{b,d},{c,d},{d,e},{g,h}}转化为{a,b,c,d,e} {a,b,d,e} {g,h}
我比较笨，没有看出“转化”的规则是什么。
请以后提问题时，描述你究竟想做什么，说得越详细越好。否则你的问题大家没有办法解决。
a,b},{b,c},{b,d},{c,d},{d,e},{g,h}}转化为{a,b,c,d,e} {a,b,d,e} {g,h}
我比较笨，没有看出“转化”的规则是什么。
请以后提问题时，描述你究竟想做什么，说得越详细越好。否则你的问题大家没有办法解决。
Ice0River 2008-04-11
- 打赏
- 举报
补充一下
1， 此二叉树实际属于多叉树
2， 建树过程 按照广度遍历的顺序进行
1， 此二叉树实际属于多叉树
2， 建树过程 按照广度遍历的顺序进行
Ice0River 2008-04-11
- 打赏
- 举报
感觉符合 二叉树 的定义
解决步骤分析如下：
1 ，根据关联关系可以将所给集合划分为若干个子集合，这些子集合之间没有关联关系。
2 ，在每个集合中找到可以做为根节点的元素（也就是第一个元素按照字母表最靠前的，可能有不止一个），以此元素做为
根节点建立二叉树（如 jayflee 所说，可能存在循环）。
3 ，结果就是所有二叉树的所有分支的集合。
个人观点，仅供参考
解决步骤分析如下：
1 ，根据关联关系可以将所给集合划分为若干个子集合，这些子集合之间没有关联关系。
2 ，在每个集合中找到可以做为根节点的元素（也就是第一个元素按照字母表最靠前的，可能有不止一个），以此元素做为
根节点建立二叉树（如 jayflee 所说，可能存在循环）。
3 ，结果就是所有二叉树的所有分支的集合。
个人观点，仅供参考
云上飞翔 2008-04-11
- 打赏
- 举报
答：谢谢 nothing123 的解释。现在才算明白了。那就是 javaflee 的程序是正解了。
加载更多回复（7）
