动态数组和链表实现 dynarray.cpp 完整实现

/*
 * Dynamisches Array mit void* Elementen
 */
#include <iostream>
#include <cstdlib>  // für malloc, realloc, free
#include <cstddef>  // für size_t
using namespace std;

/**
 * @brief Struktur für ein dynamisches Array, das void* Zeiger speichert.
 */
struct DynamicArray {
    void** data; // Zeiger auf das Array von void-Pointern
    size_t capacity; // Aktuelle Kapazität des Arrays
    size_t count; // Anzahl der tatsächlich gespeicherten Elemente
};

/**
 * @brief Initialisiert ein leeres Array mit Kapazität 4.
 * 
 * @param arr Zeiger auf das zu initialisierende Array
 */
void init_array(DynamicArray* arr) {
    arr->capacity = 4;
    arr->count = 0;
    arr->data = (void**)malloc(arr->capacity * sizeof(void*));
}

/**
 * @brief Gibt den allokierten Speicher frei.
 * 
 * @param arr Zeiger auf das Array
 */
void destroy_array(DynamicArray* arr) {
    free(arr->data);
    arr->data = nullptr;
    arr->capacity = 0;
    arr->count = 0;
}

/**
 * @brief Fügt ein Element an der angegebenen Position ein.
 * 
 * Elemente ab dieser Position werden nach hinten verschoben.
 * Wenn die Kapazität erschöpft ist, wird sie verdoppelt.
 * 
 * @param arr Zeiger auf das Array
 * @param index Position, an der eingefügt werden soll
 * @param element Zeiger auf das hinzuzufügende Element
 * @return Zeiger auf das Element, oder nullptr bei ungültigem Index
 */
void* insert(DynamicArray* arr, size_t index, void* element) {
    // Überprüfen, ob der Index gültig ist (0 <= index <= count)
    if (index > arr->count) {
        return nullptr;
    }

    // Wenn das Array voll ist, Kapazität verdoppeln
    if (arr->count == arr->capacity) {
        arr->capacity *= 2;
        void** new_data = (void**)realloc(arr->data, arr->capacity * sizeof(void*));
        if (new_data == nullptr) {
            return nullptr; // Speicherzuweisung fehlgeschlagen
        }
        arr->data = new_data;
    }

    // Elemente ab Index um eine Position nach hinten verschieben
    for (size_t i = arr->count; i > index; i--) {
        arr->data[i] = arr->data[i-1];
    }

    // Neues Element einfügen
    arr->data[index] = element;
    arr->count++;

    return element;
}

/**
 * @brief Entfernt das Element an der angegebenen Position.
 * 
 * Nachfolgende Elemente rücken auf.
 * 
 * @param arr Zeiger auf das Array
 * @param index Position des zu löschenden Elements
 * @return Zeiger auf das Element, oder nullptr bei ungültigem Index
 */
void* remove(DynamicArray* arr, size_t index) {
    // Überprüfen, ob der Index gültig ist (0 <= index < count)
    if (index >= arr->count) {
        return nullptr;
    }

    void* removed_element = arr->data[index];

    // Elemente nach dem gelöschten Element um eine Position nach vorne verschieben
    for (size_t i = index; i < arr->count - 1; i++) {
        arr->data[i] = arr->data[i+1];
    }

    arr->count--;

    return removed_element;
}

/**
 * @brief Fügt ein Element am Anfang des Arrays hinzu.
 * 
 * @param list Zeiger auf das Array
 * @param element Zeiger auf das hinzuzufügende Element
 * @return Zeiger auf das Element, oder nullptr bei ungültigem Index
 */
void* push_front(DynamicArray* arr, void* element) {
    return insert(arr, 0, element);
}

/**
 * @brief Fügt ein Element am Ende des Arrays hinzu.
 * 
 * @param arr Zeiger auf das Array
 * @param element Zeiger auf das hinzuzufügende Element
 * @return Zeiger auf das Element, oder nullptr bei ungültigem Index
 */
void* push_back(DynamicArray* arr, void* element) {
    return insert(arr, arr->count, element);
}

/**
 * @brief Entfernt das erste Element des Arrays.
 * 
 * @param arr Zeiger auf das Array
 * @return Zeiger auf das Element, oder nullptr bei ungültigem Index
 */
void* remove_front(DynamicArray* arr) {
    return remove(arr, 0);
}

/**
 * @brief Entfernt das letzte Element des Arrays.
 * 
 * @param arr Zeiger auf das Array
 * @return Zeiger auf das Element, oder nullptr bei ungültigem Index
 */
void* remove_back(DynamicArray* arr) {
    if (arr->count == 0) return nullptr;
    return remove(arr, arr->count - 1);
}

/**
 * @brief Gibt das Element an der angegebenen Position zurück.
 * 
 * @param arr Zeiger auf das Array
 * @param index Position des Elements
 * @return Zeiger auf das Element, oder nullptr bei ungültigem Index
 */
void* get(DynamicArray* arr, size_t index) {
    if (index >= arr->count) {
        return nullptr;
    }
    return arr->data[index];
}

/**
 * @brief Gibt die Anzahl der gespeicherten Elemente zurück.
 * 
 * @param arr Zeiger auf das Array
 * @return Anzahl der Elemente
 */
size_t size(DynamicArray* arr) {
    return arr->count;
}

/**
 * @brief Gibt die aktuelle Kapazität zurück.
 * 
 * @param arr Zeiger auf das Array
 * @return Kapazität des Arrays
 */
size_t get_capacity(DynamicArray* arr) {
    return arr->capacity;
}

int main() {
    DynamicArray arr;
    init_array(&arr);

    // Testdaten
    int a = 10, b = 20, c = 30, d = 40, e = 50;

    cout << "Füge Elemente hinzu..." << endl;
    push_back(&arr, &a);
    push_back(&arr, &b);
    push_back(&arr, &c);
    push_back(&arr, &d);
    push_back(&arr, &e);

    cout << "Größe: " << size(&arr) << endl;
    cout << "Kapazität: " << get_capacity(&arr) << endl;

    cout << "\nElemente im Array:" << endl;
    for (size_t i = 0; i < size(&arr); i++) {
        int* val = (int*)get(&arr, i);
        if (val != nullptr) {
            cout << "Element " << i << ": " << *val << endl;
        }
    }

    cout << "\nEntferne Element an Index 2..." << endl;
    remove(&arr, 2);

    cout << "Elemente nach Löschung:" << endl;
    for (size_t i = 0; i < size(&arr); i++) {
        int* val = (int*)get(&arr, i);
        if (val != nullptr) {
            cout << "Element " << i << ": " << *val << endl;
        }
    }

    destroy_array(&arr);
    return 0;
}

linkedlist.cpp 完整实现

/*
 * Einfach verkettete Liste mit void* Elementen
 */
#include <iostream>
#include <cstddef>  // für size_t
using namespace std;

/**
 * @brief Struktur für einen Knoten in der verketteten Liste.
 */
struct Node {
    void* data; // Zeiger auf die gespeicherten Daten
    Node* next; // Zeiger auf den nächsten Knoten
};

/**
 * @brief Struktur für eine einfach verkettete Liste.
 * 
 * Die Liste speichert void* Zeiger und ermöglicht effizientes
 * Einfügen und Löschen von Elementen.
 */
struct LinkedList {
    Node* head; // Zeiger auf den ersten Knoten
    size_t count; // Anzahl der Elemente in der Liste
};

/**
 * @brief Initialisiert eine leere Liste.
 * 
 * @param list Zeiger auf die zu initialisierende Liste
 */
void init_list(LinkedList* list) {
    list->head = nullptr;
    list->count = 0;
}

/**
 * @brief Gibt alle Knoten frei.
 * 
 * @param list Zeiger auf die Liste
 */
void* destroy_list(LinkedList* list) {
    Node* current = list->head;
    while (current != nullptr) {
        Node* next = current->next;
        delete current;
        current = next;
    }
    list->head = nullptr;
    list->count = 0;
    return nullptr;
}

/**
 * @brief Fügt ein Element an der angegebenen Position ein.
 * 
 * @param list Zeiger auf die Liste
 * @param index Position, an der eingefügt werden soll
 * @param element Zeiger auf das hinzuzufügende Element
 * @return Zeiger auf das Element, oder nullptr bei ungültigem Index
 */
void* insert(LinkedList* list, size_t index, void* element) {
    // Überprüfen, ob der Index gültig ist (0 <= index <= count)
    if (index > list->count) {
        return nullptr;
    }

    Node* new_node = new Node;
    new_node->data = element;

    if (index == 0) {
        // Am Anfang einfügen
        new_node->next = list->head;
        list->head = new_node;
    } else {
        // Den Vorgänger des einzufügenden Knotens finden
        Node* prev = list->head;
        for (size_t i = 0; i < index - 1; i++) {
            prev = prev->next;
        }

        // Neuen Knoten einfügen
        new_node->next = prev->next;
        prev->next = new_node;
    }

    list->count++;
    return element;
}

/**
 * @brief Entfernt das Element an der angegebenen Position.
 * 
 * @param list Zeiger auf die Liste
 * @param index Position des zu löschenden Elements
 * @return Zeiger auf das Element, oder nullptr bei ungültigem Index
 */
void* remove(LinkedList* list, size_t index) {
    // Überprüfen, ob der Index gültig ist (0 <= index < count)
    if (index >= list->count) {
        return nullptr;
    }

    Node* to_remove;
    void* removed_data;

    if (index == 0) {
        // Kopf-Element entfernen
        to_remove = list->head;
        list->head = to_remove->next;
    } else {
        // Den Vorgänger des zu entfernenden Knotens finden
        Node* prev = list->head;
        for (size_t i = 0; i < index - 1; i++) {
            prev = prev->next;
        }

        // Zu entfernenden Knoten finden und entfernen
        to_remove = prev->next;
        prev->next = to_remove->next;
    }

    removed_data = to_remove->data;
    delete to_remove;
    list->count--;

    return removed_data;
}

/**
 * @brief Fügt ein Element am Anfang der Liste ein.
 * 
 * @param list Zeiger auf die Liste
 * @param element Zeiger auf das hinzuzufügende Element
 */
void* push_front(LinkedList* list, void* element) {
    return insert(list, 0, element);
}

/**
 * @brief Fügt ein Element am Ende der Liste ein.
 * 
 * @param list Zeiger auf die Liste
 * @param element Zeiger auf das hinzuzufügende Element
 */
void* push_back(LinkedList* list, void* element) {
    return insert(list, list->count, element);
}

/**
 * @brief Gibt das Element an der angegebenen Position zurück.
 * 
 * @param list Zeiger auf die Liste
 * @param index Position des Elements (0-basiert)
 * @return Zeiger auf das Element, oder nullptr bei ungültigem Index
 */
void* get(LinkedList* list, size_t index) {
    if (index >= list->count) {
        return nullptr;
    }

    Node* current = list->head;
    for (size_t i = 0; i < index; i++) {
        current = current->next;
    }

    return current->data;
}

/**
 * @brief Gibt die Anzahl der gespeicherten Elemente zurück.
 * 
 * @param list Zeiger auf die Liste
 * @return Anzahl der Elemente
 */
size_t size(LinkedList* list) {
    return list->count;
}

/**
 * @brief Entfernt das erste Element aus der Liste.
 * 
 * @param list Zeiger auf die Liste
 * @return Zeiger auf das Element, oder nullptr bei ungültigem Index
 */
void* remove_front(LinkedList* list) {
    return remove(list, 0);
}

/**
 * @brief Entfernt das letzte Element aus der Liste.
 * 
 * @param list Zeiger auf die Liste
 * @return Zeiger auf das Element, oder nullptr bei ungültigem Index
 */
void* remove_back(LinkedList* list) {
    if (list->count == 0) return nullptr;
    return remove(list, list->count - 1);
}

int main() {
    LinkedList list;
    init_list(&list);

    // Testdaten
    int a = 10, b = 20, c = 30, d = 40;

    cout << "Füge Elemente hinzu..." << endl;
    push_back(&list, &a);
    push_back(&list, &b);
    push_front(&list, &c);
    push_back(&list, &d);

    cout << "Größe: " << size(&list) << endl;

    cout << "\nElemente in der Liste:" << endl;
    for (size_t i = 0; i < size(&list); i++) {
        int* val = (int*)get(&list, i);
        if (val != nullptr) {
            cout << "Element " << i << ": " << *val << endl;
        }
    }

    cout << "\nEntferne erstes Element..." << endl;
    remove_front(&list);
    cout << "Neue Größe: " << size(&list) << endl;

    cout << "\nElemente nach Löschung:" << endl;
    for (size_t i = 0; i < size(&list); i++) {
        int* val = (int*)get(&list, i);
        if (val != nullptr) {
            cout << "Element " << i << ": " << *val << endl;
        }
    }

    destroy_list(&list);
    return 0;
}

主要实现细节说明 动态数组 (DynamicArray) 内存管理: 使用malloc初始化内存，realloc扩容，free释放 扩容策略：容量翻倍（从4开始） 注意：realloc可能返回新地址，必须更新data指针 插入操作: 检查索引有效性（0 ≤ index ≤ count） 如果需要，先扩容 将index及之后的元素后移 插入新元素，count增加 删除操作: 检查索引有效性（0 ≤ index < count） 保存要删除的元素 将删除位置之后的元素前移 count减少 返回被删除的元素 链表 (LinkedList) 节点结构: 每个节点包含数据指针和指向下一个节点的指针 使用new/delete管理内存 插入操作: 处理两种情况：在头部插入（index=0）和在中间/尾部插入 在头部插入：新节点的next指向当前head，更新head 在其他位置：找到前驱节点，调整指针 删除操作: 处理两种情况：删除头部节点（index=0）和删除其他节点 删除头部：更新head为head->next 删除其他节点：找到前驱节点，调整指针 释放被删除节点的内存 返回被删除元素的指针 内存清理: destroy_list遍历整个链表，逐个释放节点 重置head和count

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com