C语言 链表问题

Question

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

法典：

#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 = %dn", 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 INEXISTENTEn");
}

输出：

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 = %dn", 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 INEXISTENTEn");
}
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，它会发现函数调用中的怪诞滥用(双释放、释放未分配等(。