數據結構學生成績管理系統

在現代教育中，學生成績的管理已經成為了一個不可或缺的部分。藉助數據結構，一個高效、可靠的學生成績管理系統可以被輕鬆實現。

一、數據結構的選擇

在構建學生成績管理系統時，選擇合適的數據結構尤為重要。為了方便管理，我們可以選擇使用哈希表來存儲學生信息、課程信息和成績信息。哈希表又可以分為兩種類型：基於鏈接和基於線性探測的哈希表。基於鏈接的哈希表使查找和插入操作更為高效，而基於線性探測的哈希表則更適合內存佔用較小的場景。

以下是基於鏈接的哈希表的示例代碼：

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;
    }
};

以上代碼實現了哈希表的自動擴容功能，當哈希表中的元素數量超過容量時，會將哈希表的容量擴大為原來的兩倍。