如何修改链表头文件支持多类型数据并适配关联链表

嘿，我来帮你搞定这两个链表相关的问题！

一、能否在main文件中声明struct data_t？ #

当然可以！不过你现有的头文件把data_t硬编码进去了，每次换数据类型都要改头文件，这显然不够灵活。要实现让data_t在main里定义，我们需要把链表改成通用型结构，这里推荐用C的模板来实现，既安全又方便，刚好你的代码里已经用到了C的引用（比如list_t& ls），完美适配。

修改后的通用链表头文件（命名为generic_list.h） #

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

// 用模板实现通用链表
template <typename T>
struct node_t {
    T data;
    node_t<T>* pNext;
};

template <typename T>
struct list_t {
    node_t<T>* pHead;
    node_t<T>* pTail;
};

// 创建新节点
template <typename T>
node_t<T>* newNode(const T& data) {
    node_t<T>* ptr = (node_t<T>*)malloc(sizeof(node_t<T>));
    if (ptr == NULL) {
        printf("\nCan not allocate memory!!!");
        return NULL;
    }
    ptr->data = data;
    ptr->pNext = NULL;
    return ptr;
}

// 初始化链表
template <typename T>
void initList(list_t<T>& ls) {
    ls.pHead = ls.pTail = NULL;
}

// 释放链表内存
template <typename T>
void lsFree(list_t<T>& ls) {
    node_t<T>* tmp;
    while ((tmp = ls.pHead) != NULL) {
        ls.pHead = ls.pHead->pNext;
        free(tmp);
    }
}

// 判断链表是否为空
template <typename T>
bool isEmpty(const list_t<T>& ls) {
    return ls.pHead == NULL;
}

// 获取链表长度
template <typename T>
int getSize(const list_t<T>& ls) {
    if (isEmpty(ls)) return 0;
    int size = 0;
    node_t<T>* ptr = ls.pHead;
    while (ptr != NULL) {
        size++;
        ptr = ptr->pNext;
    }
    return size;
}

// 根据节点指针获取索引（头节点为0）
template <typename T>
int get_node_index(const list_t<T>& ls, node_t<T>* node) {
    if (isEmpty(ls)) {
        printf("List is empty!!!\n");
        return -1;
    }
    int index = 0;
    node_t<T>* ptr = ls.pHead;
    while (ptr != node) {
        index++;
        ptr = ptr->pNext;
        // 防止传入不存在的节点导致死循环
        if (ptr == NULL) {
            printf("Node not found in list!!!\n");
            return -1;
        }
    }
    return index;
}

// 根据索引查找节点指针
template <typename T>
node_t<T>* findNode(const list_t<T>& ls, int id) {
    if (id < 0 || id >= getSize(ls)) {
        printf("Invalid index!!!\n");
        return NULL;
    }
    node_t<T>* ptr = ls.pHead;
    for (int i = 0; i < id; i++) {
        ptr = ptr->pNext;
    }
    return ptr;
}

// 添加节点到头部
template <typename T>
void addHead(list_t<T>& ls, node_t<T>* node) {
    if (isEmpty(ls)) {
        ls.pHead = ls.pTail = node;
    } else {
        node->pNext = ls.pHead;
        ls.pHead = node;
    }
}

// 删除头部节点
template <typename T>
void delHead(list_t<T>& ls) {
    if (isEmpty(ls)) {
        printf("List is empty!!!\n");
        return;
    }
    node_t<T>* tmp = ls.pHead;
    ls.pHead = ls.pHead->pNext;
    if (ls.pHead == NULL) { // 删除后链表为空
        ls.pTail = NULL;
    }
    free(tmp);
}

// 添加节点到尾部
template <typename T>
void addTail(list_t<T>& ls, node_t<T>* node) {
    if (isEmpty(ls)) {
        ls.pHead = ls.pTail = node;
    } else {
        ls.pTail->pNext = node;
        ls.pTail = node;
    }
}

// 删除尾部节点
template <typename T>
void delTail(list_t<T>& ls) {
    if (isEmpty(ls)) {
        printf("List is empty!!!\n");
        return;
    }
    if (ls.pHead == ls.pTail) { // 只有一个节点
        free(ls.pHead);
        ls.pHead = ls.pTail = NULL;
        return;
    }
    node_t<T>* ptr = ls.pHead;
    while (ptr->pNext != ls.pTail) {
        ptr = ptr->pNext;
    }
    free(ls.pTail);
    ls.pTail = ptr;
    ls.pTail->pNext = NULL;
}

// 在指定索引插入节点（新节点将占据该索引）
template <typename T>
void insert_at_id(list_t<T>& ls, int id, node_t<T>* node) {
    if (id < 0 || id > getSize(ls)) {
        printf("Invalid index for insertion!!!\n");
        return;
    }
    if (id == 0) {
        addHead(ls, node);
        return;
    }
    if (id == getSize(ls)) {
        addTail(ls, node);
        return;
    }
    node_t<T>* prev = findNode(ls, id - 1);
    node->pNext = prev->pNext;
    prev->pNext = node;
}

// 删除指定索引的节点
template <typename T>
void del_at_id(list_t<T>& ls, int id) {
    if (isEmpty(ls)) {
        printf("List is empty!!!\n");
        return;
    }
    if (id < 0 || id >= getSize(ls)) {
        printf("Invalid index for deletion!!!\n");
        return;
    }
    if (id == 0) {
        delHead(ls);
        return;
    }
    node_t<T>* prev = findNode(ls, id - 1);
    node_t<T>* tmp = prev->pNext;
    prev->pNext = tmp->pNext;
    if (tmp == ls.pTail) { // 删除的是尾节点
        ls.pTail = prev;
    }
    free(tmp);
}

// 反转链表
template <typename T>
void reverse_list(list_t<T>& ls) {
    if (isEmpty(ls) || getSize(ls) == 1) return;
    node_t<T>* prev = NULL;
    node_t<T>* curr = ls.pHead;
    node_t<T>* next = NULL;
    ls.pTail = ls.pHead; // 原来的头变成新的尾
    while (curr != NULL) {
        next = curr->pNext;
        curr->pNext = prev;
        prev = curr;
        curr = next;
    }
    ls.pHead = prev; // 原来的尾变成新的头
}

// 导出链表到文件
template <typename T>
void lsOut(const list_t<T>& ls, FILE* fout) {
    if (isEmpty(ls)) {
        printf("List is empty!!!\n");
        return;
    }
    node_t<T>* ptr = ls.pHead;
    while (ptr != NULL) {
        fwrite(&ptr->data, sizeof(T), 1, fout);
        ptr = ptr->pNext;
    }
}

// 将指定节点移动到头部
template <typename T>
void move_to_head(list_t<T>& ls, node_t<T>* ptr) {
    if (ptr == ls.pHead) return; // 已经是头节点，无需操作
    int index = get_node_index(ls, ptr);
    if (index == -1) return;
    node_t<T>* new_node = newNode(ptr->data);
    addHead(ls, new_node);
    del_at_id(ls, index);
}

// 交换两个节点的数据
template <typename T>
void swap(node_t<T>* n1, node_t<T>* n2) {
    T tmp = n1->data;
    n1->data = n2->data;
    n2->data = tmp;
}

注：这个模板版本顺便优化了原代码里的一些边界问题，比如防止索引越界、处理链表为空或只有单个节点的情况，避免了原代码可能出现的死循环或崩溃。

在main中自定义data_t的用法示例 #

#include "generic_list.h"

// 在main所在的文件里定义自己的data_t
struct data_t {
    char name[20];
    char food[20];
};

int main() {
    list_t<data_t> my_list;
    initList(my_list);

    // 创建数据节点
    data_t person1 = {"Alice", "Pizza"};
    node_t<data_t>* node1 = newNode(person1);
    addTail(my_list, node1);

    data_t person2 = {"Bob", "Burger"};
    node_t<data_t>* node2 = newNode(person2);
    addTail(my_list, node2);

    // 遍历输出
    node_t<data_t>* ptr = my_list.pHead;
    while (ptr != NULL) {
        printf("Name: %s, Food: %s\n", ptr->data.name, ptr->data.food);
        ptr = ptr->pNext;
    }

    lsFree(my_list);
    return 0;
}

这样你就不用每次修改头文件了，想定义什么类型的data_t都可以在main或者其他业务文件里操作。

二、如何用通用链表操作food_t和person_t的关联链表？ #

你的关联链表结构是：每个person_t节点对应一个food_t链表，也就是说每个人有自己的食物列表。用我们上面的模板链表，只需要分别实例化list_t<food_t>和list_t<person_t>即可，下面是具体的代码示例：

首先在main里定义你的结构体 #

#include "generic_list.h"

// 定义食物结构体
struct food_t {
    char fname[20];
    int time;
};

// 定义人物结构体，包含一个食物链表
struct person_t {
    char pname[20];
    list_t<food_t> food_list; // 直接用模板链表作为成员，方便操作
};

int main() {
    // 初始化人物链表
    list_t<person_t> person_list;
    initList(person_list);

    // 创建第一个人物及其食物列表
    person_t alice;
    strcpy(alice.pname, "Alice");
    initList(alice.food_list); // 初始化Alice的食物链表

    food_t pizza = {"Pizza", 15};
    node_t<food_t>* pizza_node = newNode(pizza);
    addTail(alice.food_list, pizza_node);

    food_t salad = {"Salad", 5};
    node_t<food_t>* salad_node = newNode(salad);
    addTail(alice.food_list, salad_node);

    // 将Alice加入人物链表
    node_t<person_t>* alice_node = newNode(alice);
    addTail(person_list, alice_node);

    // 创建第二个人物Bob
    person_t bob;
    strcpy(bob.pname, "Bob");
    initList(bob.food_list);

    food_t burger = {"Burger", 10};
    node_t<food_t>* burger_node = newNode(burger);
    addTail(bob.food_list, burger_node);

    node_t<person_t>* bob_node = newNode(bob);
    addTail(person_list, bob_node);

    // 遍历输出所有人的食物
    node_t<person_t>* person_ptr = person_list.pHead;
    while (person_ptr != NULL) {
        printf("\n%s's favorite foods:\n", person_ptr->data.pname);
        node_t<food_t>* food_ptr = person_ptr->data.food_list.pHead;
        while (food_ptr != NULL) {
            printf("- %s (cook time: %d mins)\n", food_ptr->data.fname, food_ptr->data.time);
            food_ptr = food_ptr->pNext;
        }
        person_ptr = person_ptr->pNext;
    }

    // 注意：释放内存时要先释放每个人的食物链表，再释放人物链表
    person_ptr = person_list.pHead;
    while (person_ptr != NULL) {
        lsFree(person_ptr->data.food_list);
        person_ptr = person_ptr->pNext;
    }
    lsFree(person_list);

    return 0;
}

关键说明 #

• 我们把person_t里的food_t* food改成了list_t<food_t> food_list，这样直接用模板链表管理食物，能调用头文件里的所有链表操作函数（比如添加、删除、反转等）。
• 释放内存时要先遍历人物链表，逐个释放每个人的食物链表，最后再释放人物链表，避免内存泄漏。
• 所有原头文件里的函数都可以直接用来操作person_list和每个人的food_list，完全通用。

内容的提问来源于stack exchange，提问作者Tung Hoang