c - 链表问题

Question

我试图构建一个普通的链表，我需要实现 3 个函数，new、list 和 remove。 new 添加新节点；按优先级和创建日期顺序列出所有节点；删除以删除一个节点。我认为我的问题是删除列表的第一个节点。请帮助我:)

代码:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "SO01.h"
#define SIZE 5

void main(void){
  int i;
  list_t* array;
  array=(list_t*) malloc(sizeof(list_t)*(SIZE+1));
  for(i=0; i<=SIZE; i++)
    array[i].first=NULL;
  addNewTask(array, 3, 32);
  addNewTask(array, 4, 33);
  addNewTask(array, 4, 34);
  addNewTask(array, 5, 35);
  addNewTask(array, 5, 36);
  addNewTask(array, 5, 37);

  listTasks(array, 4);
  removeTask(array, 35);
  listTasks(array, 4);
}

void addNewTask(list_t* array1, int prioridade, int id){
  lst_iitem_t* task;
  task=(lst_iitem_t*) malloc(sizeof(lst_iitem_t));
  task->next=NULL;
  task->value=id;
  if(array1[prioridade].first==NULL)
    array1[prioridade].first=task;
  else{ 
    lst_iitem_t* aux;
    aux=array1[prioridade].first;
    while(aux->next != NULL)
      aux = aux->next; 
    aux->next=task;
  }
}

void listTasks(list_t* array1, int prioridade){
  int i;
  for(i=5; i>=prioridade; i--)
    printListFromBack(array1[i].first, i);
}

void printListFromBack(lst_iitem_t * root, int prioridade)
{
  if(!root)
    return;
  else
    if(root->next)
      printListFromBack(root->next, prioridade);
  printf("Prioridade = %d || Id = %d\n", prioridade, root->value);
}

void removeTask(list_t* array1, int id){
  int i;
  lst_iitem_t* curr=NULL, *prev=NULL;
  for(i=0; i<=5; i++){
    curr=array1[i].first;
    for(curr; curr != NULL; prev=curr, curr=curr->next){
      if(curr->value == id){
    if(prev==NULL){
      curr=curr->next;
      }else{
      prev->next=curr->next;
    }
    free(curr);
    return;
      }
    }
  }
  printf("TAREFA INEXISTENTE\n");
}

输出:

Prioridade = 5 || Id = 37
Prioridade = 5 || Id = 36
Prioridade = 5 || Id = 35
Prioridade = 4 || Id = 34
Prioridade = 4 || Id = 33
Prioridade = 5 || Id = 37
Prioridade = 5 || Id = 36
Prioridade = 5 || Id = 0       <----- why 0 appears?
Prioridade = 4 || Id = 37      <----- Repeating and wrong priority
Prioridade = 4 || Id = 36      <----- Same here
Prioridade = 4 || Id = 34
Prioridade = 4 || Id = 33

感谢您的帮助；)

Answer 1

你说得对，问题出在你从列表中删除第一项的方式上。下面的工作代码在 removeTask() 中进行了一个小修复，设置了 array1[i].first = curr->next; 而不是 curr = curr->next ;。它还具有用于释放数据的 freeTask() 函数，并在一些地方使用 assert() 来验证事情是否按预期工作。

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

typedef struct list_t list_t;
typedef struct lst_iitem_t lst_iitem_t;

struct list_t
{
    lst_iitem_t *first;
};

struct lst_iitem_t
{
    lst_iitem_t *next;
    int value;
};

void addNewTask(list_t *array1, int prioridade, int id);
void removeTask(list_t *array1, int id);
void listTasks(list_t *array1, int prioridade);
void printListFromBack(lst_iitem_t *root, int prioridade);
void freeTasks(list_t *array1);

#define SIZE 5

int main(void)
{
    int i;
    list_t *array;
    array = (list_t *) malloc(sizeof(list_t)*(SIZE+1));
    for (i = 0; i <= SIZE; i++)
        array[i].first = NULL;
    addNewTask(array, 4, 33);
    addNewTask(array, 3, 32);
    addNewTask(array, 4, 34);
    addNewTask(array, 5, 35);
    addNewTask(array, 5, 36);
    addNewTask(array, 5, 37);

    printf("Before:\n");
    listTasks(array, 4);
    removeTask(array, 35);
    printf("After:\n");
    listTasks(array, 4);
    freeTasks(array);
    return 0;
}

void addNewTask(list_t *array1, int prioridade, int id)
{
    lst_iitem_t *task;
    assert(prioridade >= 0 && prioridade <= SIZE);
    task = (lst_iitem_t *) malloc(sizeof(lst_iitem_t));
    task->next = NULL;
    task->value = id;
    if (array1[prioridade].first == NULL)
        array1[prioridade].first = task;
    else
    {
        lst_iitem_t *aux;
        aux = array1[prioridade].first;
        while (aux->next != NULL)
            aux = aux->next;
        aux->next = task;
    }
}

void listTasks(list_t *array1, int prioridade)
{
    int i;
    assert(prioridade >= 0 && prioridade <= SIZE);
    for (i = SIZE; i >= prioridade; i--)
        printListFromBack(array1[i].first, i);
}

void printListFromBack(lst_iitem_t *root, int prioridade)
{
    if (!root)
        return;
    else if (root->next)
        printListFromBack(root->next, prioridade);
    printf("Prioridade = %d || Id = %d\n", prioridade, root->value);
}

void removeTask(list_t *array1, int id)
{
    int i;
    for (i = 0; i <= SIZE; i++)
    {
        lst_iitem_t *curr;
        lst_iitem_t *prev = NULL;
        for (curr = array1[i].first; curr != NULL; prev = curr, curr = curr->next)
        {
            if (curr->value == id)
            {
                if (prev == NULL)
                {
                    assert(curr == array1[i].first);
                    array1[i].first = curr->next;
                }
                else
                    prev->next = curr->next;
                free(curr);
                return;
            }
        }
    }
    printf("TAREFA INEXISTENTE\n");
}

void freeTasks(list_t *array1)
{
    for (int i = 0; i <= SIZE; i++)
    {
        lst_iitem_t *curr = array1[i].first;
        while (curr != NULL)
        {
            lst_iitem_t *next = curr->next;
            free(curr);
            curr = next;
        }
    }
    free(array1);
}

示例输出:

Before:
Prioridade = 5 || Id = 37
Prioridade = 5 || Id = 36
Prioridade = 5 || Id = 35
Prioridade = 4 || Id = 34
Prioridade = 4 || Id = 33
After:
Prioridade = 5 || Id = 37
Prioridade = 5 || Id = 36
Prioridade = 4 || Id = 34
Prioridade = 4 || Id = 33

我运行了一些变体和额外的测试，我有理由确定它是干净的。我没有在 valgrind 下运行它，但我使用了一个调试 malloc，它可以发现函数调用中怪异的滥用行为(双重释放、释放未分配的等)。