Sortere fil indhold

Doh, output skal selvfølgelig se således ud:

Name: Allan    Grade: 3
Name: Jacob    Grade: 2
Name: Mette    Grade: 6
Name: Thomas    Grade: 4

:)

Har jeg ikke lavet den en gang ?

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

struct info
{
  char *name;
  int grade;
};

void qs_help(int n1,int n2,struct info *a)
{
  struct info tmp;
  int l = n1;
  int r = n2;
  int pivot = a[(n1+n2)/2].grade;
  do {
      while(a[l].grade<pivot) l++;
      while(a[r].grade>pivot) r--;
      if(l<=r) {
        tmp = a[l];
        a[l] = a[r];
        a[r] = tmp;
        l++;
        r--;
      }
  } while(l<=r);
  if(n1<r) qs_help(n1,r,a);
  if(l<n2) qs_help(l,n2,a);
  return;
}

void qs(int n,struct info *a)
{
  qs_help(0,n-1,a);
  return;
}

#define KEY1 "Name:"
#define KEY2 "Grade:"

int main()
{
  int i,n;
  char line[133],*p1,*p2;
  struct info data[5000];
  FILE *fp,*fp2;
  fp = fopen("list.dat", "r");
  n=0;
  while(!feof(fp)) {
      if(fgets(line,sizeof(line),fp))
      {
          p1 = strstr(line,KEY1) + strlen(KEY1);
          while(*p1==' ') p1++;
          p2 = strchr(p1,' ');
          data[n].name = (char *)malloc(p2-p1);
          strncpy(data[n].name,p1,p2-p1);
          data[n].name[p2-p1] = '\0';
          data[n].grade = atoi(strstr(line,KEY2)+strlen(KEY2));
          n++;
      }
  }
  fclose(fp);
  qs(n,data);
  fp2 = fopen("sortlist.dat", "w");
  for(i=0;i<n;i++)
  {
      fprintf(fp2,"%s %s %s %d\n",KEY1,data[i].name,KEY2,data[i].grade);
  }
  fclose(fp2);
  return 0;
}

Nå du vil have sorteret efter name i.s.f. grade ?

Stay tuned !

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

struct info
{
  char *name;
  int grade;
};

void qs_help(int n1,int n2,struct info *a)
{
  struct info tmp;
  char pivot[33];
  int l = n1;
  int r = n2;
  strcpy(pivot,a[(n1+n2)/2].name);
  do {
      while(strcmp(a[l].name,pivot) < 0) l++;
      while(strcmp(a[r].name,pivot) > 0) r--;
      if(l<=r) {
        tmp = a[l];
        a[l] = a[r];
        a[r] = tmp;
        l++;
        r--;
      }
  } while(l<=r);
  if(n1<r) qs_help(n1,r,a);
  if(l<n2) qs_help(l,n2,a);
  return;
}

void qs(int n,struct info *a)
{
  qs_help(0,n-1,a);
  return;
}

#define KEY1 "Name:"
#define KEY2 "Grade:"

int main()
{
  int i,n;
  char line[133],*p1,*p2;
  struct info data[5000];
  FILE *fp,*fp2;
  fp = fopen("list.dat", "r");
  n=0;
  while(!feof(fp)) {
      if(fgets(line,sizeof(line),fp))
      {
          p1 = strstr(line,KEY1) + strlen(KEY1);
          while(*p1==' ') p1++;
          p2 = strchr(p1,' ');
          data[n].name = (char *)malloc(p2-p1);
          strncpy(data[n].name,p1,p2-p1);
          data[n].name[p2-p1] = '\0';
          data[n].grade = atoi(strstr(line,KEY2)+strlen(KEY2));
          n++;
      }
  }
  fclose(fp);
  qs(n,data);
  fp2 = fopen("sortlist.dat", "w");
  for(i=0;i<n;i++)
  {
      fprintf(fp2,"%s %s %s %d\n",KEY1,data[i].name,KEY2,data[i].grade);
  }
  fclose(fp2);
  return 0;
}

Output:

Name: Allan Grade: 3
Name: Jacob Grade: 2
Name: Mette Grade: 6
Name: Thomas Grade: 4

Svar

Men lad mig gætte: forklaringer ønskes !

Hvad mangler du forklaring til:
  - brug af array af struct
  - indlæsning af linier fra fil
  - parsning af linie
  - quick sort (ufffff)
  - udskrivning af linier til fil
?

Jo du har lavet den en gang, bortset fra at denne gang skal der sorteres alfabetisk :)

Mht. forklaring. Jeg er helt med på hvordan du åbner filen, men er lidt i tvivl om hvordan resten fungerer. Ud fra ovenstående kan jeg dog godt se hvordan du skriver linierne til filen, men resten må du meget meget gerne forklare. Håber ikke det er alt for meget at bede om.

fp = fopen("list.dat", "r");  /* åben fil */
  n=0;
  while(!feof(fp)) { /* så længe vi ikke har nået enden af filen */
      if(fgets(line,sizeof(line),fp)) /* læs en linie */
      {
          p1 = strstr(line,KEY1) + strlen(KEY1); /* find slut på "Name:" */
          while(*p1==' ') p1++; /* skip eventuelle blanke således at vi er ved start af navn */
          p2 = strchr(p1,' '); /* find mellemrum efter navn */
          data[n].name = (char *)malloc(p2-p1); /* kopier navn udfra start og slut */
          strncpy(data[n].name,p1,p2-p1);
          data[n].name[p2-p1] = '\0';
          data[n].grade = atoi(strstr(line,KEY2)+strlen(KEY2)); /* find tart på karakter og konverter til int */
          n++;
      }
  }
  fclose(fp); /* luk filen */

QuickSort er mere vanskelig at forklare.

Det er en meget hurtig sortering.

Den er rekursiv.

Den bygger på et princip om at man:
  - vælger en element
  - så putter man alle dem mindre på den ene side og alle dem større på den anden side
  - så sorterer man de 2 halvdele på samme måde

Prøv og stil uddybende spørgsmål om det du ikke forstår ?

Der er ikke nogen grund til at skrive en QuickSort selv. Det er en ANSI C funktion.
arne_v's kald af funktionen 'qs' kan erstattes med

  qsort(a,n,sizeof(struct info),compareNameUp);

hvor compareNameUp er den funktion der sammenligner to elementer.

int compareGradeUp(const void *data1, const void *data2)
{
  return ((struct info*)data1)->grade - ((struct info*)data2)->grade;
}

Hvis du hellere vil sortere i faldende orden:

int compareGradeUp(const void *data1, const void *data2)
{
  return ((struct info*)data2)->grade - ((struct info*)data1)->grade;
}

db

Og hvis man vil sortere efter name

int compareNameUp(const void *data1, const void *data2)
{
  return strcmp(((struct info*)data1)->name,((struct info*)data2)->name);
}

db

Hmmm, jeg roder vist lidt rundt i funktionsnavnene, men det skulle være til at forstå alligevel :-)

Der er 2 grunde til at jeg bruger en custom quick sort:
  - den er hurtigere på simple data typer
  - jeg ved at det ikke er første eller sidste element der bliver brugt
    pivot element (jeg er ikke sikker på at ANSI C definerer at det ikke
    være tilfældet)

Men i dette tilfælde er det måske upædagogisk fordi quick sort ikke
bare lig er noget man forstå.

Så kunne man lige så godt have brugt qsort.

Eller måske have lavet en god gammel bobbel sort.

OK ?

Beklager jeg ikke har svaret tidligere (har haft frygteligt meget om ørene), men ja, det ser ud til at give mening. Eneste lille spørgsmål er din brug af struct, hvad er det helt præcist du bruger den til?

Jeg gemmer hver linie en en struct (struktur) som indeholder både
navn og karakter. Så kan man nemlig arbejde på hele linier.

Takker mange gange for hjælp Arne.