c - 如何在函数中使用链接列表

Question

我刚开始使用链接列表，不太确定我是否做得对。我正在尝试初始化一个链接列表并用.txt文件中的信息填充它。然后使用打印功能，我只想打印出链接列表中的信息。但是每次我试图遍历链表并打印出指针中的内容时，它都会崩溃。任何提示都会有帮助和感激。这是我的代码：

struct employeeData {
   int EMP_ID;
   char name[20];
   int dept;
   int rank;
   double salary;
   };

struct employeeData employee;

struct node {
   struct employeeData employee;
   struct node *next;
   };

struct node *myList = NULL;

struct node initializeList (struct employeeData employee[], struct node myList[]);
void print (struct employeeData employee[], struct node myList[]);

int main () {
    int x;

    initializeList(&employee, &*myList);
    print(&employee, &*myList);

    System("PAUSE");
    return 0;
}

struct node initializeList (struct employeeData employee[], struct node myList[]){
         struct node *newNode = (struct node*)(malloc(sizeof(struct node)));

 FILE *ifp;

 ifp = fopen("empInfo.txt", "r");

 fscanf(ifp, "%d %s %d %d %lf\n", &newNode->employee.EMP_ID, newNode->employee.name, &newNode->employee.dept, &newNode->employee.rank, &newNode->employee.salary);
 //newNode->next = NULL;
 myList = newNode;
 struct node *temptr = myList;

 while (newNode->employee.EMP_ID != 0) {

       fscanf(ifp, "%d %s %d %d %lf\n", &newNode->employee.EMP_ID, newNode->employee.name, &newNode->employee.dept, &newNode->employee.rank, &newNode->employee.salary);

       temptr->next = newNode; 
       newNode->next = NULL;   
       } 

 return *myList;
}

void print (struct employeeData employee[], struct node myList[]){

         struct node *temptr = myList;
                           printf("WOW");

 while(temptr->next!=NULL){
                           printf("WOW");
          printf("%d %s %d %d %lf\n", temptr->employee.EMP_ID, temptr->employee.name, temptr->employee.dept, temptr->employee.rank, temptr->employee.salary);
          temptr = temptr->next;
          }
}

Answer 1

首先，您不必创建两个独立的结构来创建链接列表。。
你可以这样做：

struct list {
    /* struct members */
    struct list *next;
}

就这样！另外，在函数中，应该注意指针的衰减。。简单地说，就是当你给一个函数传递一个数组时，这个函数把它作为指针接收（这在技术上是不同的）。处理这个问题的最佳方法是接收一个数组作为 struct employeeData ** data_array，一个指针作为 struct employeeData * data。所以在 struct employeeData employee[]中没有意义。另外，this: &*employee与this: employee完全相同，只是第二个稍有效率，因为在第一个变量中，您得到变量的地址，然后取消对它的引用，实际上什么也不做。
在结构定义中。。
不需要定义名为node的结构，因为这只会使程序复杂化并使您感到困惑。实际上实现链表的方法是添加一个与其在中定义的结构类型相同的成员，正如我在earlier中所解释的。
下面是改进版：

struct employeeData {
   int EMP_ID;
   char name[20];
   int dept;
   int rank;
   double salary;
   struct employeeData *next;
};

在 initializeList function ..
如果只想在函数中复制第二个参数，就不需要它了。。
另外，在返回malloc'd指针之前，不需要取消对它的限制，因为函数调用方可能无法推断出他需要在之后释放它以防止内存泄漏，除非他使用了valgrind这样的工具。。
您也不需要调用 fscanf两次。
我还将函数重命名为：getEmployeeData，因为我认为这更有意义。
这是改进功能的最终形式：

struct employeeData *getEmployeeData (const char * filename) {
    FILE *ifp = fopen(filename, "r");
    if ( ifp == NULL )
        return NULL;

    struct employeeData *employee = malloc(sizeof(struct employeeData));
    struct employeeData *temptr = employee;

    int num = (int)getNumberOfLines(filename);

    for (int line = 1;
        (fscanf(ifp, "%d %s %d %d %lf\n", &temptr->EMP_ID, temptr->name, &temptr->dept, &temptr->rank, &temptr->salary) == 5)
            && line < num; ++line) {

        temptr->next = malloc(sizeof(struct employeeData));
        temptr = temptr->next;
    }

    fclose(ifp); /* fopen uses malloc internally */
    return employee;
}

您可能会注意到（与您的函数版本不同）我这样做： temptr->next = malloc(sizeof(struct employeeData))。这无疑是程序崩溃的原因，因为您只对节点的第一个元素malloc，并尝试对甚至没有在内存中分配的结构成员使用fscanf。这就是为什么你必须在使用前分配它。记住，一个节点中的每个元素（大部分）都是独立的，即使在内存分配中也是如此。
这个函数更简单，效率更高。您可能还注意到，我调用了另一个名为 getNumberOfLines的函数，该函数获取文件中的行数。
这里是：

size_t getNumberOfLines(const char * filename) {
    FILE *stream = fopen(filename, "r");
    if ( stream == NULL )
        return EOF;

    size_t lines = 0;
    char c;
    while (( c = getc(stream))  != EOF )
        if ( c == '\n' )
            lines++;
    fclose(stream);
    return lines;
}

我这样做的原因是，如果 fscanf找不到要存储在变量中的格式化文本，它只是将“0”存储为浮点、in t、char甚至字符串。
所以，如果 fscanf扫描一个空行，它只在所有变量中存储0。。
为了防止这种情况，您必须确保 fscanf只扫描占用的行，即使它们的格式不正确，因为检查 fscanf是否返回5（需要存储的变量数）的另一个条件在该行格式不正确时将不为真，但是如果该行甚至没有被占用（这是我在gcc实现方面的经验，如果不需要，请删除它）。
打印功能

void print (struct employeeData *employee){
    for( struct employeeData *temptr = employee; ( temptr != NULL ); temptr = temptr->next )
        printf("%d %s %d %d %lf\n", temptr->EMP_ID, temptr->name, temptr->dept, temptr->rank, temptr->salary);
}

我想我解释了这里所有的想法。我们继续。。
释放记忆
我们需要释放动态内存，以防止内存泄漏，当你试图释放一个链接列表，变得更加棘手！如果你试图按顺序释放它们，那肯定是行不通的，除非你的程序运行时发生了某种普遍的巧合！原因很简单。。这是因为唯一可以链接到下一个列表的方法是通过手头结构的一个成员。显然，如果您从内存中删除了结构的所有成员，那么您就不知道在哪里查找下一个列表！解决这个问题的一种方法是通过递归，如下所示：

void releaseData(struct employeeData *data) {

    /* freeing nodes in reverse because nodes are connected in memory, if you free the first, you lose grasp on the second and the third, resulting in a memory leak .. */
    if (data->next)
        releaseData2(data->next);
    free(data);
}

但我不喜欢这种方法，因为它会触发为函数及其参数分配内存，然后释放它们，并跟踪调用函数，实际上这是一个限制，完全取决于要确定的操作系统和运行内核。所以你可以看到，这种方法基本上是可以避免的，只有在没有其他方法的情况下才会使用，这就是为什么我创建了这个方法：

void releaseData(struct employeeData *data) {

    /* freeing nodes in reverse because nodes are connected in memory, if you free the first, you lose grasp on the second and the third, resulting in a memory leak .. */

    struct employeeData * temptr = data;
    int num = 0, first = 1;

    while ( temptr != NULL ) {
        if ( temptr->next != NULL ) {
            if (first) {
                while ( temptr->next != NULL ) {
                    temptr = temptr->next;
                    num++;
                }
                first = 0;
            } else {
                for(int i = 0; i < num - 1; ++i)
                    temptr = temptr->next;
                num--;
            }
        }
        free(temptr);
        temptr = (num == 0) ? NULL : data;
    }

    /* We could have used recursion, but that come with unnecessary overhead and less memory efficiency */

}

如你所见，这一个要复杂得多，但它也更有效。
我们使用两个变量来跟踪循环： num和 first。
num用于计算有多少嵌套节点要通过，因为当我 free指针时，它肯定不是 NULL所以循环是无限的，因为它只是检查其中的值。。
first用于指示是否是第一次运行循环，因为如果是，我们肯定不知道其中有多少节点。
我认为函数的其余部分是不言而喻的，所以我把它留给您来解决。
主要功能

int main () {
    /* Never dereference a malloc'd pointer before freeing it, so we'll get the pointer returned from the function as is */
    struct employeeData *employee = getEmployeeData("empInfo.txt"); /* Getting employee data in the struct */
    print(employee); /* Printing them out */
    releaseData(employee); /* Freeing Dynamic Memory */
    return 0;
}

就这样。