c - 将节点插入排序的链表的函数

Question

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_MODEL 25
#define MAX_LINE 50
typedef struct car{
    char* model;
    char* color;
    int year;
    struct car* next;
}car;
car* readFromFile(FILE*);
car* insertInSortedOrder(car*, char*, char*, int);
car* createCar(char*, char*, int);
void printCars(car*);

int main(int argc, char** argv){

    //creating a file pointer, opening file
    FILE* fptr;
    fptr = fopen(*(argv+1), "r");
    car* head = NULL;

    //this first reads cars from files, puts it into linked list and prints
    head = readFromFile(fptr);
    puts("do we get here");
    printCars(head);
    return 0;
}
///this function reads information from a text file, sends it to insertInSortedOrder function
car* readFromFile(FILE* fptr){

    char *M, *C, *year;
    char *readLine= malloc(sizeof(car)*MAX_MODEL);
    int yr;

    car *head=NULL;
    while(fgets(readLine,MAX_LINE,fptr)!= NULL){
            M = strtok(readLine,"|");
            C = strtok(NULL,"|");
            year = strtok(NULL,"|");
            yr = atoi(year);
            head = insertInSortedOrder(head,M,C,yr);
    }
    return head;
}
//this function sends new info to createCar to put it into a list, gets it and puts it
//into sorted order according to alphabetical order by model
car* insertInSortedOrder(car* head, char* model, char* color, int year){

    //if list is emppty
    if(head == NULL){
            head = createCar(model,color,year);
    }
    else{
            car *new = createCar(model,color,year);
            car *current,*previous;
            current = head;
            previous = NULL;
            puts("here?");
            //compares new car model to next model, if  next is greater than new, move onto next pair
            while(strcmp(new->model,current->model) < 0){
            puts("here2");
            previous = current;
            current = current->next;
            puts("here2.5");
            }
            puts("here3");
            //if only one thing in the list
            if(previous->next == NULL){
                    //new car is next on list
                    if(strcmp(previous->model,new->model) > 0){
                            previous->next = new;
                    }
                    //new car goes into top of list
                    else{
                            head = new;
                            head->next = previous;
                    }
            }
            //doing stuff at middle or end
            //if new is greater than current
            else{
          puts("here4");
                    previous->next = new;
                    new->next = current;
            }
    }
    return head;
}
//this function creates a new "node" for the list, returns pointer
car* createCar(char* model, char* color, int year){

    car *newCar = malloc(sizeof(car));
    newCar->color = malloc(sizeof(char)*MAX_MODEL);
    newCar->model = malloc(sizeof(char)*MAX_MODEL);

    strcpy(newCar->model,model);
    strcpy(newCar->color,color);
    newCar->year = year;
    newCar->next = NULL;

    return newCar;
 }
//this function prints out all of things in linked list
void printCars(car* head){

    if(head == NULL)
            printf("List is empty\n");

    else{
            printf("The list of cars in inventory are:\n");
            while(head!=NULL){
            printf("%-5d %-25s %-13s",head->year,head->model,head->color);
            printf("\n");
            head = head->next;
            }
    }
}

这个程序的目的是读入一个文件，该文件包含一个包含车型名称、颜色名称和年份的汽车列表。读入后，按车型类型升序放入链表。这是正在读入的文件:

Tesla S|royal|2015|
GMC Yukon|white|2005|
Dodge Charger|lime|2010|
Honda Civic|cobalt|1996|
Nissan Titan|saddlewood|2008|
Chevrolet Silverado|saddlewood|1999|
Ford Focus|lime|2000|
Toyota Tacoma|gunmetal|2009|
Tesla X|black|2016|
Nissan Maxima|white|2013|
Ford Explorer|forest|1996|
Chevrolet Corvette|cherry|1982|
Tesla 3|cherry|2017|
Nissan 370Z|royal|2011|
Ford F150|cherry|2006|
Honda Accord|white|2004|
Mitsubishi Eclipse|black|2002|
Toyota Tundra|cobalt|2017|
Dodge Challenger|lemon|1970|
Chevrolet Camaro|black|1966|

在命令提示符中输入“./a.out cars.txt”后，输出为

here?
here2
here2.5
Segmentation fault

由于我的 puts 语句，我知道段错误发生在我的“insertInSortedOrder”函数的 while 循环中的某个地方。非常感谢任何帮助使此功能正常工作的帮助，谢谢

好的，我已经将插入函数更改为:

car* insertInSortedOrder(car* head, char* model, char* color, int year){

    //if list is emppty
    if(head == NULL){
            head = createCar(model,color,year);
    }
    else{
            car *new = createCar(model,color,year);
            car *current,*previous;
            current = head;
            previous = NULL;
            //compares new car model to next model, if  next is greater than new, move onto next pair
            while( strcmp(new->model,current->model)  <  0){
                    //if current is only node in list or end of list
                    if(current->next == NULL){
                            current->next = new;
                            return head;
                    }
                    else{
                            //move forward to compare new
                            previous = current;
                            current = current->next;
                    }
            }
            //when new is greater than current, put new on top of it
            previous = new;
            previous->next = current;
    }
    return head;
}

现在打印:

The list of cars in inventory are:
2015  Tesla S                   royal
2005  GMC Yukon                 white
2010  Dodge Charger             lime 
1999  Chevrolet Silverado       saddlewood
1982  Chevrolet Corvette        cherry
1966  Chevrolet Camaro          black

太棒了!没有更多的段错误，但现在我想我只是没有好的算法

Answer 1

在分析了您的函数 insertInSortedOrder() 并阅读了@JonathanLeffler 的警告之后，我已经定位了您的排序列表中缺少项目的问题。

Error in the case of 'new is greater than current'

• 无条件覆盖previous指针

使用代码 previous = new; 而不检查 previous 是否指向一个节点将直接用新项目覆盖列表的一部分。

• 当 previous == NULL 时不改变 head

当 previous == NULL 时，new 项将替换 head。

使用以下代码:

if (previous==NULL) {
    // new becomes the first node
    new->next = head;
    head = new;
}
else {
    // new is inserted between previous and current
    new->next = previous->next;
    previous->next = new;
}

代替代码:

previous = newitem;
previous->next = current;