数据结构学生成绩管理系统

在现代教育中，学生成绩的管理已经成为了一个不可或缺的部分。借助数据结构，一个高效、可靠的学生成绩管理系统可以被轻松实现。

一、数据结构的选择

在构建学生成绩管理系统时，选择合适的数据结构尤为重要。为了方便管理，我们可以选择使用哈希表来存储学生信息、课程信息和成绩信息。哈希表又可以分为两种类型：基于链接和基于线性探测的哈希表。基于链接的哈希表使查找和插入操作更为高效，而基于线性探测的哈希表则更适合内存占用较小的场景。

以下是基于链接的哈希表的示例代码：

class HashTable {
  private:
    vector<LinkedList> table;
    int size;
    int capacity;
  
  public:
    HashTable(int capacity) {
        this->table.assign(capacity, LinkedList());
        this->size = 0;
        this->capacity = capacity;
    }

    void insert(string key, int value) {
        int hashValue = hash(key);
        LinkedList& list = table[hashValue];
        if (list.insert(key, value)) {
            size++;
        }
    }

    int get(string key) {
        int hashValue = hash(key);
        LinkedList& list = table[hashValue];
        return list.get(key);
    }

    bool remove(string key) {
        int hashValue = hash(key);
        LinkedList& list = table[hashValue];
        if (list.remove(key)) {
            size--;
            return true;
        }
        return false;
    }

    int getSize() const {
        return size;
    }

    int getCapacity() const {
        return capacity;
    }

  private:
    int hash(string key) const {
        const int P = 31;
        const int M = capacity;
        int hashValue = 0;
        int pPow = 1;
        for (int i = 0; i < key.length(); i++) {
            hashValue = (hashValue + (key[i] - 'a' + 1) * pPow) % M;
            pPow = (pPow * P) % M;
        }
        return hashValue;
    }
};

以上代码实现了一个基于链接的哈希表，其中用到了另一个数据结构——链表，用于解决哈希冲突的问题。

二、业务逻辑实现

在硬件和数据结构的基础上，学生成绩管理系统还需要实现各种业务逻辑，如插入成绩、查询成绩、删除成绩等功能。以下是一些常见的功能实现代码：

1. 插入成绩

void insertGrade(HashTable& table, string studentId, string courseId, int grade) {
    string key = studentId + ":" + courseId;
    table.insert(key, grade);
}

2. 查询成绩

int getGrade(HashTable& table, string studentId, string courseId) {
    string key = studentId + ":" + courseId;
    return table.get(key);
}

3. 删除成绩

bool removeGrade(HashTable& table, string studentId, string courseId) {
    string key = studentId + ":" + courseId;
    return table.remove(key);
}

三、可拓展性考虑

在实现数据结构时，需要考虑系统的可拓展性。在学生数量增加或者新的课程加入时，系统应该能够自动进行扩容，而不影响原有数据。以下是一个哈希表的自动扩容实现：

class HashTable {
  private:
    vector<LinkedList> table;
    int size;
    int capacity;
  
  public:
    HashTable(int capacity) {
        this->table.assign(capacity, LinkedList());
        this->size = 0;
        this->capacity = capacity;
    }

    void insert(string key, int value) {
        int hashValue = hash(key);
        LinkedList& list = table[hashValue];
        if (list.insert(key, value)) {
            size++;
        }
        if (size >= capacity) {
            resize();
        }
    }

    int get(string key) {
        int hashValue = hash(key);
        LinkedList& list = table[hashValue];
        return list.get(key);
    }

    bool remove(string key) {
        int hashValue = hash(key);
        LinkedList& list = table[hashValue];
        if (list.remove(key)) {
            size--;
            if (size < capacity / 2) {
                resize();
            }
            return true;
        }
        return false;
    }

    int getSize() const {
        return size;
    }

    int getCapacity() const {
        return capacity;
    }

  private:
    int hash(string key) const {
        const int P = 31;
        const int M = capacity;
        int hashValue = 0;
        int pPow = 1;
        for (int i = 0; i < key.length(); i++) {
            hashValue = (hashValue + (key[i] - 'a' + 1) * pPow) % M;
            pPow = (pPow * P) % M;
        }
        return hashValue;
    }

    void resize() {
        int newCapacity = capacity * 2;
        vector<LinkedList> newTable(newCapacity);
        for (int i = 0; i < capacity; i++) {
            LinkedList& list = table[i];
            Node* node = list.getFirstNode();
            while (node != nullptr) {
                int hashValue = hash(node->key);
                LinkedList& newList = newTable[hashValue];
                newList.insert(node->key, node->value);
                node = node->next;
            }
        }
        capacity = newCapacity;
        table = newTable;
    }
};

以上代码实现了哈希表的自动扩容功能，当哈希表中的元素数量超过容量时，会将哈希表的容量扩大为原来的两倍。