打印双链表

Question

我有一个家庭作业要写“先到先得”和“循环模拟”，并对它们进行比较。我开始创建一个链表来制作事件列表。我已经实现了插入和打印列表功能，但无法正常工作。我的朋友告诉我使用双链表，所以我重新创建了链表，并试图使打印功能工作。我有一个关于插入函数的问题，因为我在while循环中的语句顺序有误。在修复了许多错误后，print函数会多次打印同一个节点，而不是整个列表。我不知道程序的哪一部分是错的。我认为我在insert函数中有错误，我把指针指向了错误的地方，所以我把事件指向了它自己，或者我在print函数中有错误。

当我删除这行代码时，print函数只打印当前节点，而不打印其他内容。

新指针-

我想这意味着我在这部分有问题，但我不明白为什么。

 if(prevptr == NULL)                  //if putting node at the beginning of the list
 {
     printf("DONEW\n");
     newpointer->next = *eventlist;                    
     *eventlist = newpointer;
 }

你能告诉我代码有什么问题吗？

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

struct event {
       struct event *next;
       int processid;
       int arrivaltime;
       int cputime;
};
typedef struct event Event;
typedef Event *eventPtr;

Event create_node(int processid, int arrivaltime, int cputime);
void add_event(Event *newpointer, eventPtr *eventlist);
void print_node(Event node);
void print_eventlist(Event *eventlist);
Event get_nextevent(Event *eventlist);

int main(int argc, char* argv[])
{
    int sourcenum,a,b,c,i;
    Event tempevent;
    eventPtr eventlist = NULL;
    print_eventlist(eventlist);
    char* sources,timeSlice;
    if(argc != 3)
    printf("Proper usage is: main.c sources time-slice\n");
    else
    {
        sourcenum = atoi(argv[1]);
        timeSlice = atoi(argv[2]);
        for(i = 0; i < sourcenum ; i++)
        {
              //print_eventlist(&(*eventlist));
              printf("please enter the process-id, arrival-time and cpu-time.\n");
              scanf("%d %d %d",&a, &b, &c);
              printf("something\n");
              tempevent = create_node(a,b,c);
              printf("something\n");
              add_event(&tempevent, &eventlist);
              print_eventlist(eventlist);
        }
        print_eventlist(eventlist);    
    }
    return 0;
}


void add_event(Event *newpointer, eventPtr *eventlist)     //insert
{
     printf("DONE1\n");
     eventPtr currentptr, prevptr;
     printf("DONE2\n");
     prevptr = NULL;
     printf("DONE3\n");
     currentptr = *eventlist;
     printf("DONE4\n");
     while((currentptr != NULL && currentptr->arrivaltime < newpointer->arrivaltime))                  /*on every loop previous and current pointer gets upgraded*/
     {
             printf("DONEW\n");
             prevptr = currentptr;
             currentptr = currentptr->next;   
     }
     printf("DONEW\n");
     if(prevptr == NULL)                  //if putting node at the beginning of the list
     {
         printf("DONEW\n");
         newpointer->next = *eventlist;                    
         *eventlist = newpointer;
     }
     else //putting list between current and previous
     {
         printf("DONEW\n");
         prevptr->next = newpointer;
         newpointer->next = currentptr;
     }
     printf("DONE\n");
}

Event create_node(int processid, int arrivaltime, int cputime)
{
      Event *ptr;
      ptr = malloc(sizeof(Event));
      if(ptr != NULL)
      {
         ptr->processid = processid;       
         ptr->arrivaltime = arrivaltime;    
         ptr->cputime = cputime;
         ptr->next = NULL;
      }
      return *ptr;
}

void print_node(Event node)
{
  printf("process-id = %d\n",node.processid);
  printf("Arrival Time = %d\n",node.arrivaltime);
  printf("CPU time = %d\n",node.cputime);   
}

void print_eventlist(eventPtr currentPtr)                                           /*function receives an eventlist and prints all of the events*/
{
    if(currentPtr == NULL)
    {
        puts("List is empty\n");
    }
    else
    {
        puts("The List is:");
        while(currentPtr != NULL)
        {
            printf("==========================================\n");//list #%d\n",i);
            print_node(*currentPtr);
            printf("\n==========================================\n");
            currentPtr = currentPtr->next;
        }
        puts("NULL\n");
    }
}
    /*int i=0;                                     //This is what I had before
    eventPtr currentptr;
    *currentptr = *eventlist;
    printf("something!!!");
    while(currentptr != NULL)
    {
         i++;
         printf("==========================================\nlist #%d\n",i);
         print_node(*currentptr);
         printf("\n==========================================\n");
         currentptr = currentptr->next;            
    }
}*/

/*Event get_nextevent(Event *eventlist)
{    
    Event newstruct = create_node(eventlist->processid, eventlist->arrivaltime, eventlist->cputime);
    eventlist = eventlist->next;
    return newstruct;  
}*/

Answer 1

更改以下内容的类型：

 Event tempevent;

到

 eventPtr tempevent;

你的问题是你通过了

eventPtr create_node(int processid, int arrivaltime, int cputime)
{
      Event *ptr;
      ptr = malloc(sizeof(Event));
      if(ptr != NULL)
      {
         ptr->processid = processid;       
         ptr->arrivaltime = arrivaltime;    
         ptr->cputime = cputime;
         ptr->next = NULL;
      }
      return ptr;
}

Answer 2

在这段代码中有很多东西需要解决。

首先，您在create_节点中泄漏内存。该函数应设计为动态分配事件，使用传递的参数进行准备，并将其作为地址返回给调用者，以分配给调用者端的指针：

Event* create_node(int processid, int arrivaltime, int cputime)
{
    Event *ptr = malloc(sizeof(*ptr));
    if (ptr == NULL)
    {
        perror("Failed to allocate Event.");
        exit(EXIT_FAILURE);
    }

    ptr->processid = processid;
    ptr->arrivaltime = arrivaltime;
    ptr->cputime = cputime;
    ptr->next = NULL;
    return ptr;
}

接下来，您的add_event函数应该将一个事件指针作为列表头，最好是该指针的地址，以便在初始插入时对其进行修改。插入函数有两种思想：（1）始终返回列表头；（2）使用指向列表头参数的指针，并根据需要通过取消引用对其进行修改。我更喜欢后者，因为它使代码非常简单。在你的情况下更是如此，因为新事件的创建是在其他地方完成的。

// link an event on to the end of our linked list.
void add_event(Event** pp, Event* event)
{
    while (*pp)
        pp = &(*pp)->next;
    *pp = event;
}

考虑到我还修复了不正确的timeSlice变量，它是char，应该是int。更重要的是，您拥有的逻辑将有一个空列表头节点，这不会给您带来任何好处。您可以使用指针，然后调用我们的add_event函数并传递其地址。它将正确插入节点。

最终产品看起来像这样（带有次要mod）：

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

typedef struct event
{
    struct event *next;
    int processid;
    int arrivaltime;
    int cputime;
} Event;

Event* create_node(int processid, int arrivaltime, int cputime);
void add_event(Event** head, Event *event);
void print_node(const Event* node);
void print_eventlist(const Event *eventlist);

int main(int argc, char* argv[])
{
    int sourcenum,a,b,c,i,timeslice;
    Event* events = NULL;

    if(argc != 3)
    {
        printf("Proper usage is: main.c sources time-slice\n");
        exit(EXIT_FAILURE);
    }

    // TODO: these really should be using strtol() for better
    //  error detection. left as exercise for author.
    sourcenum = atoi(argv[1]);
    timeslice = atoi(argv[2]);

    for(i = 0; i < sourcenum ; i++)
    {
        printf("please enter the process-id, arrival-time and cpu-time.\n");
        if (scanf("%d %d %d",&a, &b, &c) == 3)
        {
            add_event(&events, create_node(a,b,c));
            print_eventlist(events);
        }
    }
    return 0;
}

// link an event on to the end of a linked list.
void add_event(Event** pp, Event* event)
{
    while (*pp)
        pp = &(*pp)->next;
    *pp = event;
}

Event* create_node(int processid, int arrivaltime, int cputime)
{
    Event *ptr = malloc(sizeof(*ptr));
    if (ptr == NULL)
    {
        perror("Failed to allocate Event.");
        exit(EXIT_FAILURE);
    }

    ptr->processid = processid;
    ptr->arrivaltime = arrivaltime;
    ptr->cputime = cputime;
    ptr->next = NULL;
    return ptr;
}

void print_node(const Event* node)
{
    if (node != NULL)
    {
        printf("process-id = %d\n",node->processid);
        printf("Arrival Time = %d\n",node->arrivaltime);
        printf("CPU time = %d\n",node->cputime);
    }
    else
    {
        printf("NULL\n");
    }
}

void print_eventlist(const Event* currentPtr)
{
    puts("==========================================");
    while(currentPtr != NULL)
    {
        print_node(currentPtr);
        puts("==========================================");
        currentPtr = currentPtr->next;
    }
    puts("NULL");
    puts("==========================================");//list #%d\n",i);
}

样本输出

从请求5个条目的命令行获取。

please enter the process-id, arrival-time and cpu-time.
1 1 1 
==========================================
process-id = 1
Arrival Time = 1
CPU time = 1
==========================================
NULL
==========================================
please enter the process-id, arrival-time and cpu-time.
2 2 2 
==========================================
process-id = 1
Arrival Time = 1
CPU time = 1
==========================================
process-id = 2
Arrival Time = 2
CPU time = 2
==========================================
NULL
==========================================
please enter the process-id, arrival-time and cpu-time.
3 3 3 
==========================================
process-id = 1
Arrival Time = 1
CPU time = 1
==========================================
process-id = 2
Arrival Time = 2
CPU time = 2
==========================================
process-id = 3
Arrival Time = 3
CPU time = 3
==========================================
NULL
==========================================
please enter the process-id, arrival-time and cpu-time.
4 4 4
==========================================
process-id = 1
Arrival Time = 1
CPU time = 1
==========================================
process-id = 2
Arrival Time = 2
CPU time = 2
==========================================
process-id = 3
Arrival Time = 3
CPU time = 3
==========================================
process-id = 4
Arrival Time = 4
CPU time = 4
==========================================
NULL
==========================================
please enter the process-id, arrival-time and cpu-time.
5 5 5
==========================================
process-id = 1
Arrival Time = 1
CPU time = 1
==========================================
process-id = 2
Arrival Time = 2
CPU time = 2
==========================================
process-id = 3
Arrival Time = 3
CPU time = 3
==========================================
process-id = 4
Arrival Time = 4
CPU time = 4
==========================================
process-id = 5
Arrival Time = 5
CPU time = 5
==========================================
NULL
==========================================

不管怎样，希望它能给你一些好主意。