Skip to main content
 首页 » 编程设计

python之将邻接表变成表

2025年02月15日10cloudgamer

我在忙乱的项目中碰壁了。我在数据库中有一个邻接列表,其中有一系列嵌套类别。 它的格式为 Id,Cat​​egory,Parent_Id 并且效果很好。

我想将其显示为表格,以便人们可以添加和更改类别而不会造成太多混淆。这就是我失败的地方。我一辈子都想不出如何让它正确显示。

当我查询数据库时,我最终得到了一系列与此类似的嵌套元组:

((1L, 'First', None), (2L, 'Second', None), (3L, 'Third', None), (4L, 'Fourth', 1L), (5L, 'Fifth', 4L), (6L, 'Sixth', 3L), (7L, 'Seventh', 8L), (8L, 'Eighth', None)) 

数据稍有变化,因此无法保证顺序。我假设我需要某种递归函数来将它变成一个表,但我就是无法理解它。就像这样就好了:

First | Fourth | Fifth  
Second 
Third | Sixth 
Eighth | Seventh 

任何人都可以给我一些关于如何实现这一目标的指示吗?几乎不可能将外部模块安装到我正在处理的盒子上,而且它只运行 python 2.5,因此非常感谢任何帮助。

编辑:在发布之前我想出了以下代码:

list = ((1L, 'First', None), (3L, 'Third', None), (4L, 'Fourth', 1L), 
        (6L, 'Sixth', 3L), (7L, 'Seventh', 8L), (8L, 'Eighth', None),  
        (2L, 'Second', None), (5L, 'Fifth', 4L)) 
 
levels = [] 
levels.append([_[0] for _ in list if _[2] is None]) 
for x in xrange(0,len(list[0])): 
   levels.append([]) 
   for item in list: 
       levels[-1].append(item[0]) if item[2] in levels[-2] else None 
   if sum([len(_) for _ in levels]) == len(list): break 

从中我得到了每个级别的嵌套列表:

>>> levels

[[1L, 3L, 8L, 2L], [4L, 6L, 7L], [5L]]

从这里我有点迷路了。我想把它变成一个表格,我需要尽可能多的列表,因为完成的表格中会有行。我可以在列表嵌套中找到最长的列表来给出行数,它在两个维度上工作以填充让我感到困惑的表格。

实际输出不是东西。我可以毫不费力地以适合我的方式打印表格。创建表格的想法伤害了我。我知道可以使用 SQL 查询,例如 Suggest SQL Query to retrieve all leaf nodes from Adjacency List Model ,我只是希望有一种方法可以在 Python 中执行此操作,这样我就可以了解更多有关处理此类数据集的信息。

请您参考如下方法:

不太确定预期输出的格式,但这里有一种方法:

data = ((1L, 'First', None), (3L, 'Third', None), (4L, 'Fourth', 1L), 
        (6L, 'Sixth', 3L), (7L, 'Seventh', 8L), (8L, 'Eighth', None), (2L, 'Second', None), (5L, 'Fifth', 4L)) 
 
 
def get_tuple_by_id(tuple_id): 
    for item in data: 
        if item[0] == tuple_id: 
            return item 
 
 
def arrange_data(items): 
    new_list = () 
 
    for an_item in items: 
        parent_id = an_item[2] 
        if parent_id: 
            parent = get_tuple_by_id(parent_id) 
            new_tuple = an_item + (parent[1],) 
            new_list += (new_tuple,) 
        else: 
            new_list += (an_item,) 
 
    return sorted(new_list, key=lambda x: x[0]) 
 
 
def render(items): 
    print '{name:15}{parent}'.format(name='name', parent='parent') 
    print '{name:15}{parent}'.format(name='--------', parent='-------') 
    for item in items: 
        print '{name:15}{parent}'.format(name=item[1], parent=item[3] if item[2] else '') 
 
ad = arrange_data(data) 
render(ad) 

输出:

name           parent 
--------       ------- 
First           
Second          
Third           
Fourth         First 
Fifth          Fourth 
Sixth          Third 
Seventh        Eighth 
Eighth          

下面是一个显示表格和嵌套级别的解决方案。它使用 python 2.5 支持的 prettytable。

安装表格渲染器:pip install prettytable

from prettytable import PrettyTable 
 
 
data = ((1L, 'First', None), (3L, 'Third', None), (4L, 'Fourth', 1L), 
        (6L, 'Sixth', 3L), (7L, 'Seventh', 8L), (8L, 'Eighth', None), (2L, 'Second', None), (5L, 'Fifth', 4L)) 
 
 
def get_tuple_by_id(tuple_id): 
    for item in data: 
        if item[0] == tuple_id: 
            return item 
 
 
def arrange_data(items): 
    new_list = () 
 
    for an_item in items: 
        parent_id = an_item[2] 
        if parent_id: 
            parent = get_tuple_by_id(parent_id) 
            new_tuple = an_item + (parent[1],) 
            new_list += (new_tuple,) 
        else: 
            new_list += (an_item,) 
 
    return sorted(new_list, key=lambda x: x[0]) 
 
 
ad = arrange_data(data) 
t = PrettyTable(['Category', 'Level']) 
 
for item in ad: 
    t.add_row([item[1], 1 if item[2] else 0]) 
 
print t 

结果:

+----------+-------+ 
| Category | Level | 
+----------+-------+ 
|  First   |   0   | 
|  Second  |   0   | 
|  Third   |   0   | 
|  Fourth  |   1   | 
|  Fifth   |   1   | 
|  Sixth   |   1   | 
| Seventh  |   1   | 
|  Eighth  |   0   | 
+----------+-------+ 

注意:如果你的数据是多层嵌套的,那么一些修改也可以实现。目前它只考虑 0 或 1 级嵌套。

下面使用递归函数处理多层嵌套:

from prettytable import PrettyTable 
 
 
data = ( 
    (1L, 'First', None),  
    (2L, 'Second', None),  
    (3L, 'Third', None),  
    (4L, 'Fourth', 1L), 
    (5L, 'Fifth', 4L), 
    (6L, 'Sixth', 3L),  
    (7L, 'Seventh', 8L),  
    (8L, 'Eighth', None),  
    (9L, 'Ninth', 5L), 
    (10L, 'Tenth', 9L), 
    (11L, 'Eleventh', 10L), 
    (12L, 'Twelfth', 11L)) 
 
 
def get_tuple_by_id(tuple_id, level=1): 
    for item in data: 
        if item[0] == tuple_id: 
            parent_id = item[2] 
            if parent_id: 
                level += 1 
                return get_tuple_by_id(parent_id, level) 
            else: 
                return (item, level) 
 
 
def arrange_data(items): 
    new_list = () 
 
    for an_item in items: 
        parent_id = an_item[2] 
        if parent_id: 
            parent, level = get_tuple_by_id(parent_id) 
            print an_item, level 
 
            new_tuple = an_item + (level,) 
            new_list += (new_tuple,) 
        else: 
            an_item += (0,) 
            new_list += (an_item,) 
 
    return sorted(new_list, key=lambda x: x[0]) 
 
 
ad = arrange_data(data) 
t = PrettyTable(['Category', 'Level']) 
 
for item in ad: 
    t.add_row([item[1], item[3]]) 
 
print t 

输出:

+----------+-------+ 
| Category | Level | 
+----------+-------+ 
|  First   |   0   | 
|  Second  |   0   | 
|  Third   |   0   | 
|  Fourth  |   1   | 
|  Fifth   |   2   | 
|  Sixth   |   1   | 
| Seventh  |   1   | 
|  Eighth  |   0   | 
|  Ninth   |   3   | 
|  Tenth   |   4   | 
| Eleventh |   5   | 
| Twelfth  |   6   | 
+----------+-------+ 

更多关于递归函数的信息,如果您有兴趣:https://en.wikipedia.org/wiki/Recursion_(computer_science)