微软笔试题,大家讨论下。
考虑下面的图形表示方法:
图中的点用node对象来表示,而连接点的线用指针 node*来表示,每个node对象含有一个 node**型的数组,用于表示这个node对象向外放射的线。初始点含有一个全局指针提供此图形的handle。
请问:此设计的优点和缺点是什么,比如计算此图形包括几个点的复杂性。是否有更好的方法克服此设计的缺点?
------解决方案--------------------目的应该是考虑大家的设计和对C++的认识能力吧!
好处:
这样处理问题简洁,容易让人明白.
坏处:
不符合C++的设计对象的理念了,一个图虽然是点线组成,但是却定义成:node gra; 不奇怪吗?还有图的描画采用这种设计估计不容易实现!尤其是无向图.
------解决方案--------------------优点是正确抽象出了图中点的性质,可以轻松实现针对图中点的一些操作
缺点很多,例如求出图包括多少个点,多少条边,任意一个边的边长等操作实现起来比较复杂。
克服这一缺点的作法可以是将边抽象为带有两个点的有序对。
------解决方案--------------------看了ls的回答,有些明白了。
那这样的设计,主要是对点来进行设计,而将线作为点的辅助,这样在求点方面的运算,信息会比较够,但是对于其他的一些运算,就比较复杂了。
------解决方案--------------------我觉得是一组线要怎么存放的问题
题目中的存放是用一个数组来存放的, 也就是一个顺序数组.
还有一种存放方法是用list链来存放.
所以线的存放问题, 就是这两种数据结构的差别问题了.
从整体看来, 还可以把所有节点的线放在一个数组里.