C 双向链表结构

Question

我正在做一个双向链表。据我所知，它正在发挥作用，但我来这里是为了确保并查看我的做法是否正确。

另一方面，当我做这个的时候，我遇到了其他与双向链表无关但与 C 文件之间的结构和“可见性”相关的问题。如果您明白我应该针对这两个其他疑问提出其他问题，请告诉我。否则请随时启发我。

在我的 file1.c 上我有这个:

代码

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

typedef struct team{
    char *name;
    char *teamPlace;
}Team;

typedef struct nodeTeam{
    int numberOfTeams;
    Team team;
    struct nodeTeam *next;
    struct nodeTeam *prev;
}NodeTeam;

int createsListOfTeams(NodeTeam **head, NodeTeam **tail);
void printListOfTeams(NodeTeam *listofTeams);
int addNodeTeamsSorted(NodeTeam *head, NodeTeam **tail, Team team);

int main()
{
    NodeTeam *headEquipas,*tailEquipas;
    Team eq;
    /*Creates the doubly linked list*/
    if(createsListOfTeams(&headEquipas,&tailEquipas)){
        printf("\nError\n");
        return 0;
    }
    /*Add the teams to the doubly linked list. At the end, all teams will be sorted by name*/
    eq.name = "D team";
    eq.teamPlace = "D team place";
    if (addNodeTeamsSorted(headEquipas,&tailEquipas,eq)){
        printf("\nError\n");
        return 0;
    }

    eq.name = "A team";
    eq.teamPlace = "A team place";
    if (addNodeTeamsSorted(headEquipas,&tailEquipas,eq)){
        printf("\nError\n");
        return 0;
    }

    eq.name = "C team";
    eq.teamPlace = "C team place";
    if (addNodeTeamsSorted(headEquipas,&tailEquipas,eq)){
        printf("\nError\n");
        return 0;
    }

    eq.name = "B team";
    eq.teamPlace = "B team place";
    if (addNodeTeamsSorted(headEquipas,&tailEquipas,eq)){
        printf("\nError\n");
        return 0;
    }

    /*Will print all the teams*/
    printListOfTeams(headEquipas);

    return 0;
}

在我的 file2.c 上有这个

代码

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

    typedef struct team{
        char *name;
        char *teamPlace;
    }Team;

    typedef struct nodeTeam{
        int numberOfTeams;
        Team team;
        struct nodeTeam *next;
        struct nodeTeam *prev;
    }NodeTeam;

    /*Add the teams to the doubly linked list. At the end, all teams will be sorted by name*/
    int createsListOfTeams(NodeTeam **head, NodeTeam **tail){
        (*head) = (NodeTeam *)malloc(sizeof(NodeTeam));

        if ((*head) == NULL){
            return -1;
        }
        (*head)->numberOfTeams = 0;
        (*head)->team.teamPlace = "";
        (*head)->team.name = "";
        (*head)->next = NULL;
        (*head)->prev = NULL;

        *tail = *head;
        return 0;
    }

    /*Creates the doubly linked list*/
    int addNodeTeamsSorted(NodeTeam *head, NodeTeam **tail, Team team){
        NodeTeam *no,*listIni;


        no = (NodeTeam*) malloc(sizeof(NodeTeam));
        if (no == NULL){
            return -1;
        }

        /*copy of my list*/
        listIni = head;

        no->team = team;
        /*to see is it's the first element of my list*/
        if(head->numberOfTeams == 0)
        {
            no->next = head->next;
            no->prev = head;
            head->next = no;
            *tail = no;

        }
        else{ /*If not the first element*/
            head = head->next;
            while(head->prev != *tail && strcmp(head->team.name,no->team.name) < 0 && strcmp((*tail)->team.name,no->team.name)>0){
                head = head->next;
                (*tail) = (*tail)->prev;
            }
            if(strcmp(head->team.name,no->team.name) >= 0 || head->prev == *tail){
                no->next = head;
                no->prev = head->prev;
                (head->prev)->next = no;
                head->prev = no;

            }
            else if(strcmp((*tail)->team.name,no->team.name) <= 0){
                no->next = (*tail)->next;
                no->prev = (*tail);
                (*tail)->next = no;
                *tail = no;

            }
        }

        /*Updates the number of element of the list*/
        head = listIni;
        head->numberOfTeams++;

        return 0;
    }
    /*Prints my lists*/
    void printListOfTeams(NodeTeam *listofTeams){
        printf("|   number of teams %22d |\n",listofTeams->numberOfTeams);
        printf("|      team name      |        team place      |\n");
        printf("--------------------------------------------------\n");
        listofTeams = listofTeams->next;
        while (listofTeams != NULL){
            printf("| %-21s | %-22s |\n",listofTeams->team.name,listofTeams->team.teamPlace);
            listofTeams = listofTeams->next;
        }
        printf("--------------------------------------------------\n\n");
    }

所以这是我的树问题:

Q1 - 这是实现头部和尾部分别指向列表开头和结尾的双向链表的正确方法吗？

Q2 - 为什么要在我的两个文件中声明 struct team 和 struct nodeTeam？由于它们都在同一个项目中，声明不应该对我项目中的所有文件“可见”吗？

Q3 - 在 struct team 中，为什么我必须声明 char *name 而不是 char name[31]?

Answer 1

我根据您之前的评论进行了一些编辑，并更仔细地分析了您的代码。我错误地解释了一个关于头项和尾项的评论，尽管你在设计一个循环列表

1. 我花时间复制/粘贴/编译您的代码。虽然它几乎可以工作，但我必须说我会以另一种方式设计

   • 将 prev/next 指针移动到 struct team
   • 并用指向第一个 team 的 nodeTeam 指针替换 head 的 team 成员。

   这会有以下好处:

   • 防止为每个 numberOfTeams 复制但仅对第一个有意义的 nodeTeams 空间的无用浪费
   • 避免混淆概念上的 head 和实际的第一队

   通过添加队列表中的指针值

   printf("| %-21s | %-22s | %p - p=%p n=%p\n",listofTeams->team.name, listofTeams->team.teamPlace, listofTeams, listofTeams->prev, listofTeams->next);

   我注意到您的链接中可能存在错误:

   | A team | A team place | 0x101d00980 - p=0x101d00920 n=0x101d009e0

   | B team | B team place | 0x101d009e0 - p=0x101d00980 n=0x101d009b0

   | C team | C team place | 0x101d009b0 - p=0x101d00980 n=0x101d00950

   | D team | D team place | 0x101d00950 - p=0x101d009b0 n=0x0

   您可以看到 next 指针没问题，但是 prev 指针显示可疑的重复项(0x101d00920 确实是“头”)。

   如果您跟踪代码的执行并检查它在 addNodeTeamsSorted() 中做了什么，您会注意到一切正常直到第 3 步(在现有 A 和 D 之后添加团队 C):

   • 由于为找到插入新项的位置而对头部和尾部进行了奇怪的双重修改，头部和尾部交叉:尾部实际上指向“A”而头部指向“D”(不要忘记，而 head 是Nodeteam * 及其修改不会传播到函数外部，tail 是一个 Nodeteam ** ，因此当它被更改为调用者和下一次调用时它将是错误的
   • 在测试的 else if 部分的第 4 步(添加“B”)中，您正确更改了 no 的上一个/下一个，(*tail) 的下一个 但是不是 no->next 的 prev 所以你有
     • 'B' -> next = 'C' : OK
     • 'B' -> prev = 'A' : 好的
     • *tail (='A') -> next = 'B' : OK
     • 'C' -> prev still = 'A' : 错误

2. 这不是编译器想的那样。他只处理编译单元，一次一个。 .c 中未声明的内容和不同的包含的 .h 将保持未知。如果您想在两个模块之间共享结构声明，并防止代码维护错误，请剪切 typedef 并将它们放在一个公共(public)头文件(例如 equipa.h )中，该头文件将包含在两个 .c 中

3. 您必须使用 char* 而不是 char[]，因为在 file1.c 的 main() 中，您是从文字字符串直接赋值，而编译器不允许您将文字字符串赋给 char 数组。如果您想使用 char[] 而不是更改您的

   eq.nome = "D team";

   像复制字符串一样

   strcpy(eq.nome, "D team");

   当然，我只是在处理概念，实际上你应该注意使用 strncpy() 和 sizeof(eq.nome) 复制的字符串不要超过缓冲区