算法问题(200分)

tmnet · 2001-06-17

我想设计一个游戏程序，问题是这样的： 首先我使用记录TCity保存“城市”的数据。 TCity=Record   Name:string[20];   prop:integer;   mancount,woman:integer;   rescount:integer;   pathcount:integer;//道路数量   end; 由于有许多城市，就使用了TLIST来保存城市列表。但我想不好，接下来该如何 保存“城市”间道路的信息。（道路有很多条，并且不确定。）请各位大侠赐教！ 或许，我原本的设计就不好，如果谁能提出更好的设计。我真的感激不尽！

mikedeakins · 2001-06-17

使用对象列表，定义类 CMap, CCity 和 CRoad。CMap 维护 CCity 的列表， CCity 维护和这个城市相关的 CRoad 列表。

wison · 2001-06-18

在这种不"确定"的情况下，最好就是用"动态"的啦：），举个例子：）， TRoad = Record    roadName : String; //道路名称    width    : integer;//宽度    ...... //其他你程序中需要的信息 end; TCity=Record   Name:string[20];   prop:integer;   mancount,woman:integer;   rescount:integer;   roadsRec : Array of TRoad ; end; 用法： var tempRec : TCity; tempRec.roadsRec := nil; SetLength( tempRec.roadsRec , 10 );//假设饿10条道路 //赋值 tempRec.roadRec[0].roadName := '中山大道'; ... ... showMessage(' roads count in city : ' + IntToStr( Length( tempRec.roadsRec ) );

tmnet · 2001-06-19

我想，mikedeakins 和 wison老兄还不明白我的意思。 我的意思是：    有许多“城市”，并且“城市”与“城市“之间有许多道路相连，而不是城市里面有 许多道路。

mikedeakins · 2001-06-19

>>CCity 维护和这个城市相关的 CRoad 列表。 你的领悟能力有待提高。

iie · 2001-06-19

链表是存储动态数据的传统方法，当然可变数组也可以

tmnet · 2001-06-19

另外，我想我还是完整的把我原来的思路讲讲，以便更好的让各位朋友帮忙。 我原来的设计：   1、使用TCity记录来存储城市数据。   2、使用TRoad记录来存储城市之间的道路数据。        TRoad=record          city1,city2:integer;          rect1,rect2:trect;          end;   3、如果要遍历所有城市，我就循环TCITY记录，如果要遍历所有道路，我就      循环TROAD记录。 但是，我发现上述方法存在很大的缺陷：    1、城市之间的关系不明确。    2、无法从一个城市移动到下一个城市（它们之间有路）。    3、通过城市，访问道路，或者通过城市删除、改变道路将很麻烦。 我认为，可能有更好的思路。到底谁能想出来呢？

tmnet · 2001-06-19

mikedeakins老兄的说法，其实我早就想过， 但是，我觉得很麻烦，而且在实际的实现过程中，存在缺陷： 1、城市的道路是共享的，即两个城市一条道路，这条道路到底归谁管理呢。 2、可变指针的管理也是非常头痛的事情。 我想问一下MIKEDEAKINS老兄，你能不能将你的想法讲的更详细一点。如果能解决我 说的两个缺陷，就更好了。

mikedeakins · 2001-06-19

CRoad 提供一个成员函数： CRoad::AttachToCity(CCity City1, CCity City2); 同时，CCity 同样提供一个成员函数： CCity::__AttachToRoad(CRoad Road); // 两个下划线表示不要直接调用 这种情况下，CRoad 对象可以维护其仅有的两个 CCity 端（CRoad 添加两个 CCity 类型 的成员变量）。调用 AttachToCity 的时候，这个函数再调用 __AttachToRoad 把自己注 册到两个 CCity 中。CCity 中使用 TList 保存所有注册的 CRoad 指针。 如果你不用这种设计，而是用了 record (struct in c/c++)，最大的问题就是如何维护： 你的程序如果要增加新的功能将不得不改写大量代码。况且，面向对象的程序也好懂一些。

mikedeakins · 2001-06-19

>>2、无法从一个城市移动到下一个城市（它们之间有路）。 按照我的设计，这个操作应当遍历一个 CCity 的道路列表，挨着查就行了。

creation-zy · 2001-06-19

大家说清楚一点嘛。   CMap类的实例应该仅有一个——WorldMap，其中含有两个成员链表，分别用于遍历所有的City和Road； CCity类中含有一个链表，其中包含了所有与之相连的Road的指针； CRoad类中含有两个指针，指向道路两端的城市对象。 type   CCity=class;   CRoad=class;   CityListRec=Record     City:CCity;     Next

ointer;   end;   PCityListRec=^CityListRec;   RoadListRec=Record     Road:CRoad;     Next

ointer;   end;   PRoadListRec=^RoadListRec;   CCity=class     RoadList:RoadListRec;     //...     __AttachToRoad(CRoad Road); //在此过程中将道路对象加入自身的道路链表   end;   CRoad=class     Citys:array[1..2]of CCity; //在Delphi中，对象实际上就是指针     //...     AttachToCity(CCity City1, CCity City2); //在此过程中，调用两个City对象的__AttachToRoad方法     //同时将Citys分别设置为City1,City2   end;   CMap=class     CityList

CityListRec; //为了提高查询效率，可以使用对象数组     RoadList

RoadListRec; //同上     //...   end; >遍历一个 CCity 的道路列表，挨着查   Right!   你的数据结构已经很简单了。我写了一个游戏，其中的CRoad类要复杂得多。 ps:既然是“算法问题”，为什么不放在“数据结构”分类？？ to mikedeakins: >两个下划线表示不要直接调用   还有没有别的规范，贴出来共享一下嘛！

mikedeakins · 2001-06-19

多谢 creation-zy 的解释：） 其实代码规范真的是仁者见仁，每个人都有自己的习惯。我自己的习惯就古怪得很（是 别人说的，我倒是很习惯），和 delphi 惯用的规范不太一样。

tmnet · 2001-06-20

creation-zy老兄的解释非常好。这个问题原先是要放在“数据结构”里的， 但是，在寻找的时候，我就是找不到。而且我习惯与到WINDOWS API里面看看。 所以，我选择了它。    另外，我大致看懂了mikedeakins老兄的想法。你的意思是：    1、构造MAP类    2、构造CITY类    3、构造ROAD类    4、其中ROAD类属于CITY类属于MAP类。    5、将一个ROAD类，分别注册到两个CITY中。以解决两个城市只有一条路的问题。       （但是，好象比较麻烦。而且，当我们要修改道路数据时，可能忘了修改其中的一个。         删除ROAD时，也只删除了一个。）    6、如果要读取数据，就挨个检查所有数据。 当然，这种方法好象也不是很好。如果说，要实现这个问题的话，我介绍的方法也可以。 但他不好。我希望寻找一种思路清晰、结构简单、查询方便的数据结构。但是，好象无法 找到。我在等一星期吧！如果真的没有，我真的只能采用以上方法了。        另外，我认为上述数据结构有一个很要命的缺陷：当我们从一个城市顺着道路到下一个 城市时，就可能产生死循环。因为，ROAD类在两个CITY中，可能又回到原来的地方了。 不瞒大家，我的算法学的不太好。主要精力用在语言和系统知识上。现在看来，麻烦来了。 最后，我想向creation-zy老兄要一点东西。你能不能将你写的游戏代码，借我看看。或者 让我看看CROAD类也好。（老天保佑，是用Pascal写的）。

mikedeakins · 2001-06-20

i faint. 请原谅我冒昧问一句：你看明白 creation-zy 实际上是在解释我写的思路了吗？ 如果你没看出来，我也没话说，你补课先。 如果你看出来了，好，我接着说说。 东西是死的，可是人是活的呀！ CCity CCity::GetLinkedCity(CRoad Road); 调用： CCity CRoad::GetTheOtherCity(CCity City); 调用的时候把 this (self) 作为参数。 动动脑子难道就这么难？ >> 5、将一个ROAD类，分别注册到两个CITY中。以解决两个城市只有一条路的问题。 >>      （但是，好象比较麻烦。而且，当我们要修改道路数据时，可能忘了修改其中的一个。 >>        删除ROAD时，也只删除了一个。） CRoad 提供一个成员函数： CRoad::AttachToCity(CCity City1, CCity City2); 同时，CCity 同样提供一个成员函数： CCity::__AttachToRoad(CRoad Road); // 两个下划线表示不要直接调用 这段话您看明白没有？使用的时候只需要调用 CRoad::AttachToCity(CCity City1, CCity City2); 把道路信息注册到城市之中是 CCity::__AttachToRoad(CRoad Road); 完成的，但是绝对不是直接 调用！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！ 而是由 CRoad::AttachToCity 在内部调用的。你不会仿照这个思路构造一个 DetachXXX 函数，负责删除道路吗？如果这样使用，又怎么会出现那个白痴问题？

tmnet · 2001-06-21

根据大家的想法，我设计了下面这些代码。请大家帮我看看，有什么可以添加和删除  的地方。尽请指教！      Tcity=class//城市类        private         froadlist:tlist;//道路列表         fcityinfo:tcityinfo;         function getroadcount: integer;         function getcityinfo: tcityinfo;         procedure setcityinfo(const Value: tcityinfo);//城市信息        public         constructor Create;         destructor Destroy; override;         procedure addroad(leadinfo:troadinfo);         procedure deleteroad(index:integer);         procedure clearroad;         property roadCount:integer read getroadcount;         property CityInfo:tcityinfo read getcityinfo write setcityinfo;        end;      Troad=class        private          froadinfo:troadinfo;          fcity1,fcity2:tcity;          function getcity1: tcity;          function getcity2: tcity;          procedure setcity1(const Value: tcity);          procedure setcity2(const Value: tcity);          function getroadinfo: troadinfo;          procedure setroadinfo(const Value: troadinfo);//道路类        public          property roadInfo:troadinfo read getroadinfo write setroadinfo;          property city1:tcity read getcity1 write setcity1;          property city2:tcity read getcity2 write setcity2;        end;      Tmap=class//地图类        private          fcitylist:tlist;          function getcitycount: integer;          function getcityinfo(index: integer): tcityinfo;          procedure setcityinfo(index: integer; const Value: tcityinfo);        public          constructor Create;          destructor Destroy; override;          procedure Addcity(city:tcityinfo);          procedure Deletecity(index:integer);          procedure clear;          property cityCount:integer read getcitycount;          property city[index:integer]:tcityinfo read getcityinfo write setcityinfo;        end; 我喜欢使用TLIST来保存对象指针，这样编程简单一些。 另外，我是一个完美主义者，总希望寻找更简单、更能解决问题的方法。 或许，你们介绍的方法已经很好了。不过，我已经在尝试这种方法了。

tmnet · 2001-07-01

各位对不起了，因为前段时间无法连上“大富翁”所以没有给各位加分。 当然，我觉得可能还有更好的答案。但是我非常感谢各位的无私帮助。 另外，在“控件—开发”栏目里也有我的一个问题，如果您看到，也请帮我解答一下。谢谢！

tmnet · 2001-07-01

多人接受答案了。

算法问题(200分)

tmnet

Unregistered / Unconfirmed

mikedeakins

Unregistered / Unconfirmed

wison

Unregistered / Unconfirmed

tmnet

Unregistered / Unconfirmed

mikedeakins

Unregistered / Unconfirmed

iie

Unregistered / Unconfirmed

tmnet

Unregistered / Unconfirmed

tmnet

Unregistered / Unconfirmed

mikedeakins

Unregistered / Unconfirmed

mikedeakins

Unregistered / Unconfirmed

creation-zy

Unregistered / Unconfirmed

mikedeakins

Unregistered / Unconfirmed

tmnet

Unregistered / Unconfirmed

mikedeakins

Unregistered / Unconfirmed

tmnet

Unregistered / Unconfirmed

tmnet

Unregistered / Unconfirmed

tmnet

Unregistered / Unconfirmed

Similar threads