数据结构-python中的“n到n”关系使用什么

Question

在摆弄字典后，我得出结论，我需要一个允许n to n查找的数据结构。一个例子是：一个课程可以由几个学生访问，每个学生可以访问几个课程。

实现这一目标的最具蟒蛇风格的方式是什么？这不会超过500名学生和100门课程，以保持榜样。所以我想避免使用真正的数据库软件。

谢谢！

Answer 1

由于您的工作集很小，我认为将学生ID作为列表存储在Course类中没有问题。在课堂上寻找学生就像做一样简单

course.studentIDs

要查找学生所在的课程，只需迭代课程并找到ID:

studentIDToGet = "johnsmith001"
studentsCourses = list()
for course in courses:
    if studentIDToGet in course.studentIDs:
        studentsCourses.append(course.id)

还有其他方法可以做到这一点。你可以有一个studentID的字典映射到courseID，或者有两个字典，一个映射studentID:courseIDs，另一个映射courseID:studentIDs，当更新时，相互更新。

我编写代码的实现可能是最慢的，这就是为什么我提到您的工作集足够小，不会有问题。我提到但没有显示代码的其他实现需要更多的代码才能使它们工作，但这些代码不值得付出努力。

Answer 2

它完全取决于您希望结构能够快速执行哪些操作。

如果你想快速查找与课程和学生相关的属性，例如，学生在特定课程的学习上花费了多少小时，或者如果他完成了课程，学生在课程中的成绩是多少，如果他已经完成了课程等等。你可能需要一个包含n*m元素的向量，其中n是学生人数，m为课程数量。

另一方面，如果学生所修课程的平均数量远小于课程总数(在真实情况下可能是这样(，并且你想快速查找学生所修的所有课程，你可能想使用一个由n个列表组成的数组，可调整大小的矢量或类似的——取决于您是否希望能够使用列表；这可能是为了快速删除列表中间的元素，或者快速访问随机位置的元素。如果你们都想快速删除列表中间的元素，并快速随机访问列表元素，那么也许某种树结构最适合你们。

大多数树数据结构在对数时间内对树中的元素数量执行所有基本操作。注意，一些树数据结构在这些运算符上的摊销时间与树中元素的数量成线性，即使随机构建的树的平均时间是对数的。发生这种情况的一个典型例子是，如果使用二进制搜索树并使用越来越大的元素构建它。不要那样做；在这种情况下，在使用元素构建树之前先对其进行加扰，或者使用分治方法将列表拆分为两部分和一个pivot元素，并使用pivot创建树根，然后从列表的左侧和右侧递归创建树，这些也使用分治方法，并将它们分别作为左子项和右子项附加到根。

对不起，我不懂python，所以我不知道什么数据结构是语言的一部分，你必须自己创建。

Answer 3

我认为您需要对学生和课程进行索引。否则，你可以很容易地列出元组，以存储所有学生、课程组合：[(St1，Crs1(，(St1、Crs2(..(St2、Crs1(…(Sti、Crsi(…]，然后每次需要时都进行线性查找。对于多达500名学生来说，这也不错。

但是，如果您想以任何一种方式快速查找，都没有内置的数据结构。你可以简单地使用两个字典：

courses = { crs1: [ st1, st2, st3 ], crs2: [ st_i, st_j, st_k] ... } 
students = { st1: [ crs1, crs2, crs3 ], st2: [ crs_i, crs_j, crs_k] ... } 

对于给定的学生，查找课程现在就是学生；对于给定的课程c，查找学生就是课程[c]。

Answer 4

对于像您想要做的事情这样简单的事情，您可以创建一个带有数据成员和方法的简单类来维护它们并使它们彼此保持一致。对于这个问题，需要两本词典。一个由学生姓名(或id(键入，记录每个人正在学习的课程，另一个记录每个班的学生。

可以使用"collections"模块中的defaultdicts而不是普通的dicts，以使操作更加方便。我的意思是：

from collections import defaultdict
class Enrollment(object):
    def __init__(self):
        self.students = defaultdict(set)
        self.courses = defaultdict(set)
    def clear(self):
        self.students.clear()
        self.courses.clear()
    def enroll(self, student, course):
        if student not in self.courses[course]:
            self.students[student].add(course)
            self.courses[course].add(student)
    def drop(self, course, student):
        if student in self.courses[course]:
            self.students[student].remove(course)
            self.courses[course].remove(student)
        # remove student if they are not taking any other courses
        if len(self.students[student]) == 0:
            del self.students[student]
    def display_course_enrollments(self):
        print "Class Enrollments:"
        for course in self.courses:
            print '  course:', course,
            print ' ', [student for student in self.courses[course]]
    def display_student_enrollments(self):
        print "Student Enrollments:"
        for student in self.students:
            print '  student', student,
            print ' ', [course for course in self.students[student]]
if __name__=='__main__':
    school = Enrollment()
    school.enroll('john smith', 'biology 101')
    school.enroll('mary brown', 'biology 101')
    school.enroll('bob jones', 'calculus 202')
    school.display_course_enrollments()
    print
    school.display_student_enrollments()
    school.drop('biology 101', 'mary brown')
    print
    print 'After mary brown drops biology 101:'
    print
    school.display_course_enrollments()
    print
    school.display_student_enrollments()

运行时产生以下输出：

Class Enrollments:
  course: calculus 202   ['bob jones']
  course: biology 101   ['mary brown', 'john smith']
Student Enrollments:
  student bob jones   ['calculus 202']
  student mary brown   ['biology 101']
  student john smith   ['biology 101']
After mary brown drops biology 101:
Class Enrollments:
  course: calculus 202   ['bob jones']
  course: biology 101   ['john smith']
Student Enrollments:
  student bob jones   ['calculus 202']
  student john smith   ['biology 101']