Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
576 views
in Technique[技术] by (71.8m points)

c - QUICKSORT on single linked list

I'm trying to write a simply C code for QUICKSORT on single linked list. Program will get a txt file with password and frequency of usage this password. Program should sort the passwords in order. Can someone guess what is wrong here?

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


typedef struct list_element{
    char passwort[100];
    int haufigkeit;
    struct list_element *next;
} list_element;

typedef struct list{
    list_element *first;
    list_element *last;
} list;


void init_list(list* mylist)
{
    mylist->first=NULL;
    mylist->last=NULL;
}


// Diese Funktion fügt Listenelemente am Anfang der Liste an
void insert_front(list_element* le, list* mylist)
{
    if(mylist->first == NULL){
        le->next = mylist-> first;
        mylist->first=le;
        mylist->last=le;
    }
    else {
        le->next = mylist-> first;
        mylist->first= le;
    }
}

// Speicher für Listenelemente wieder freigeben
void free_list(list* mylist)
{
    free((mylist)->first);
    free(mylist);
    mylist=NULL;
}


// Namen, Zahlen Paare in Liste einlesen
void read_data(char* filename, list* mylist)
{
    assert(mylist != NULL);
    FILE* f=fopen(filename,"r");
    assert(f != NULL);
    while (1)
    {
        list_element* temp = malloc(sizeof(list_element));// * Speicher allozieren
        fscanf(f,"%s %d",temp->passwort, &temp-> haufigkeit);// * Daten in list_element einlesen
        insert_front(temp, mylist); // * insert_front benutzen um list_element in Liste einzufügen
    }
    fclose(f);
}

// Pivot finden, das die Liste aufteilt
list_element* partition( list* input, list* left, list* right ){
list_element* pivot= input->first;

    while(input->first != input->last){
        list_element *i;
        for(i=input->first; i != NULL; i=i->next){
            if ((i -> haufigkeit) < (pivot -> haufigkeit)){
                insert_front( i, left);
            }
            else{
                insert_front( i, right);
            }
        }
    }
    return pivot;
}

void print_list(list* mylist){

    list_element* current =mylist-> first;
    while(current != NULL){
        printf("%d %c 
",current->passwort,current->haufigkeit);
        current=current->next;
    }
}
// Hauptfunktion des quicksort Algorithmus
void qsort_list(list* mylist){
    // HIER Code einfügen
    // list liste= mylist;
    list *right;
    list *left;
    list_element* pivot;
    while(mylist->first != mylist->last){
        partition(mylist, left, right );
    qsort_list(left);
    qsort_list(right);
    }
}

// Liste ausgeben

// Argumente einlesen, Liste kreieren, verarbeiten und ausgeben
int main(int argc, char** args)
{
    if (argc != 2)
    {
        printf("Nutzung: %s <Dateiname>
",args[0]);
        return 1;
    }
    list mylist;
    init_list(&mylist);
    read_data(args[1],&mylist);
    qsort_list(&mylist);
    printf("Sortierte Liste:
");
    print_list(&mylist);
    free_list(&mylist);
    return 0;
}
See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

When do you intent to break from this code snippet?

while (1)
{
  list_element* temp = malloc(sizeof(list_element));// * Speicher allozieren
  fscanf(f,"%s %d",temp->passwort, &temp-> haufigkeit);// * Daten in list_element einlesen
  insert_front(temp, mylist); // * insert_front benutzen um list_element in Liste einzufügen
}

PS: and there is no sense in posting german comments. Please indent the code and remove/translate the comments


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...