在数据结构中分配席位

Question

我需要存储n行m列的座位列表(代表教练/飞机等)。我还需要能够将座位分配给某个对象。

我在想，如果我能使用某种形式的数据结构，如类似于元组的键，映射可能是完美的。

。

map = { (0,0): null,
        (0,1): Person1Object,
        (0,2): Person2Object,
        ...
        (n,m): PersonNObject
      }

其中(0,0)表示座位的行和列。然后null表示没有人坐。

但是我不确定这个方法是否可能，因为我见过的地图通常使用字符串作为键。我还考虑过使用多维数组和列表来解决这个问题。

谁能告诉我存储这个数据集合的最佳方法?

谢谢

Answer 1

您可以使用PersonObject的二维数组来完成此操作，用法如下:

final PersonObject[][] seats = new PersonObject[x][y];
//set a person
seats[a][b] = myPerson
//get a person
final PersonObject myPerson = seats[a][b];

如果数据的大小是未知的，你可以使用List s而不是数组:

final List<List<PersonObject>> seats = new ArrayList<List<PersonObject>>();
//set a person
List<PersonObject> list = seats.get(a);
if(list == null) {
  list = new ArrayList<PersonObject>();
  seats.add(a, list);
}
list.add(b, myPerson);
//get a person
final PersonObject myPerson = seats.get(a).get(b);

注意，第二种方法更容易出错，因为您需要按顺序将人员放入行中，否则seats.add(a, list)将导致错误。如果人们没有按顺序放入列中，list.add(b, myPerson)将导致错误。

要解决这个问题，您可以使用您建议的数据结构，这看起来像

final Map<Integer, Map<Integer, PersonObject>> seats = new HashMap<Integer, Map<Integer, PersonObject>>();
//set a person
Map<Integer, PersonObject> map = seats.get(a);
if(map == null) {
  map = new HashMap<Integer, PersonObject>();
  seats.put(a, map);
}
map.put(b, myPerson);
//get a person
myPerson.get(a).get(b);

如果没有行a，这个get方法将抛出NullPointerException。这可以通过扩展HashMap和覆盖put方法来避免:

final Map<Integer, Map<Integer, PersonObject>> seats = new HashMap<Integer, Map<Integer, PersonObject>>(){
  @Override
  public  Map<Integer, PersonObject> get(Object key) {
     Map<Integer, PersonObject> map = super.get(key);
     if(map == null) {
        map = new HashMap<Integer, PersonObject>();
        put((Integer)key, map);
     }
     return map;
  }
};
//set a person    
map.seats.get(a).put(b, myPerson);
//get a person
myPerson.get(a).get(b);

由于外部Map现在自动创建内部映射，因此不会出现错误。这种结构在稀疏数据下工作得更好。

如果你允许查看第三方库，google guava有你需要的东西，一个Table，本质上是最终数据结构的包装。

另一种选择是使用Map<Point, PersonObject>，因为Point类已经存在，并且表示二维空间中的一个点。

final Map<Point, PersonObject> seats = new HashMap<Point, PersonObject>();
//set a person  
seats.put(new Point(a,b), myPerson);
//get a person
myPerson = seats.get(new Point(a,b));

Answer 2

如果n和m是已知的，为什么不使用数组代替呢?

PersonObject[][] seats = new PersonObject[n][m]; 

---

你描述的数据结构是可能的。应该是

Map<Integer, Map<Integer, PersonObject>> seats = ... 

但是它似乎不适合你的需要，因为它会引入很多你不需要的内存开销，而且处理起来也不是很方便。

Answer 3

您可以简单地使用PersonObjects的二维数组并使用索引作为行号和列号的指示

的例子:

PersonObject seatMatrix = new PersonObject[100][100];

表示第0行第1列被占用，执行如下操作:

seatMatrix[0][1] = new PersonObject();

要检查某个特定的(例如:第1行第1列)座位是否被占用，您可以这样做:

if(seatMatrix[1][1] != null)
{
     //this seat is taken
}
else
{
     // this seat is not taken!
}