Попытка qsort на K & R "Язык программирования C"

Question

Я довольно новичок в этом, поэтому я попытался скомпилировать main на странице 119 (§5.11) вместе с его зависимостями. Мне удалось получить чистую сборку с этим:

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

#define ALLOCSIZE 10000
#define MAXLINES 5000
#define MAXLEN 1000

int getline(char *, int);
char *alloc(int);
char *lineptr[MAXLINES];

int readlines(char *lineptr[], int nlines);
void writelines(char *lineptr[], int nlines);

void qsort(void *lineptr[], int left, int right, 
           int (*comp)(void *, void *));

int numcmp(char *, char *);

static char allocbuf[ALLOCSIZE];
static char *allocp = allocbuf;


/* getline:  read a line, return length */
int getline(char *line, int max)
{
   if (fgets(line, max, stdin) == NULL)
      return 0;
   else
      return strlen(line);
}


char *alloc(int n)
{
   if (allocbuf + ALLOCSIZE - allocp >= n) {
      allocp += n;
      return allocp - n;
   } else
      return 0;
}


/* readlines:  read input lines */
int readlines(char *lineptr[], int maxlines)
{
   int len, nlines;
   char *p, line[MAXLEN];

   nlines = 0;
   while ((len = getline(line, MAXLEN)) > 0)
      if (nlines >= maxlines || (p = alloc(len)) == NULL)
         return -1;
      else {
         line[len-1] = '\0'; /* delete newline */
         strcpy(p, line);
         lineptr[nlines++] = p;
      }
   return nlines;
}


/* writelines:  write output lines */
void writelines(char *lineptr[], int nlines)
{
   int i;

   for (i = 0; i < nlines; i++)
      printf("%s\n", lineptr[i]);
}


void swap(void *v[], int i, int j)
{
   void *temp;

   temp = v[i];
   v[i] = v[j];
   v[j] = temp;   
}


/* qsort:  sort v[left]...v[right] into increasing order */
void qsort(void *v[], int left, int right,
           int (*comp)(void *, void *))
{
   int i, last;
   void swap(void *v[], int, int);

   if (left >= right)
      right;
   swap(v, left, (left + right)/2);
   last = left;
   for(i = left+1; i <= right; i++)
      if((*comp)(v[i], v[left]) < 0)
         swap(v, ++last, 1);
   swap(v, left, last);
   qsort(v, left, last-1, comp);
   qsort(v, last+1, right, comp);
}


#include <stdlib.h>

/* numcmp:  compare s1 and s2 numerically */
int numcmp(char *s1, char *s2)
{
   double v1, v2;

   v1 = atof(s1);
   v2 = atof(s2);
   if (v1 < v2)
      return -1;
   else if (v1 > v2)
      return 1;
   else
      return 0;
}


/* strcmp01:  return <0 if s<t , 0 if s==t, >0 if s>t */
int strcmp01(char *s, char *t)
{
   for( ; *s == *t; s++, t++)
      if(*s == '\0')
         return 0;
   return *s - *t;
}


/* sort input lines */
main(int argc, char *argv[])
{
   int nlines;
   int numeric = 0;

   if (argc > 1 && strcmp01(argv[1], "-n") == 0)
      numeric = 1;
   if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
      qsort((void **) lineptr, 0, nlines-1,
         (int (*)(void*,void*))(numeric ? numcmp : strcmp01));
      writelines(lineptr, nlines);
      return 0;
   }
   else {
      printf("input too big to sort\n");
      return 1;
   }
}

Но когда я запускаю его в окне DOS (Win 7, чего стоит), командная строка курсора принимает несколько строк ввода с клавиатуры и .... А что именно? После того, как я набрал несколько строк, ничего не происходит. Я просто нажал Ctrl C и вернулся в командную строку.

В качестве альтернативы я собрал несколько строк материала в файл test.txt и попытался запустить

[DIR\]mybuild.exe <[DIR\]test.txt

Это просто выдает ошибку (появляется диалоговое окно Win 7, в котором говорится, что "mybuild.exe перестал работать"). находит файл test.txt; это просто "перестать работать".

Что я могу сделать, чтобы успешно запустить эту программу? (Я просто пытаюсь это никогда не видеть, чтобы это работало где-то раньше.) Спасибо всем за вашу помощь.

Answer 1

1. нажмите F6 или Ctrl + Z, чтобы завершить ввод в консоли.

2. добавив fprintf (stderr, ...) к вашему коду, я обнаружил, что в программе фактически не хватает стека. вы, вероятно, ошиблись в qsort. как

if (left> = right) право;

void qsort(void *v[], int left, int right,
           int (*comp)(void *, void *))
{
   int i, last;
   void swap(void *v[], int, int);

fprintf(stderr, "left %d  right %d\n", left, right);
   if (left >= right)
      right;
   swap(v, left, (left + right)/2);
   last = left;
   for(i = left+1; i <= right; i++)
      if((*comp)(v[i], v[left]) < 0)
         swap(v, ++last, 1);
   swap(v, left, last);
   qsort(v, left, last-1, comp);
   qsort(v, last+1, right, comp);
}

Answer 2

if (left >= right)
    right;

Вы имели в виду

if (left >= right)
    return;

Answer 3

Добавьте несколько printf() в стратегических местах, чтобы увидеть, что ваша программа делает.

Для начала попробуйте выяснить, застрял ли он внутри readlines(), qsort() или writelines().

Итак, добавьте несколько printf() в main, непосредственно перед вызовом каждой из этих функций. После того, как вы узнаете, в каком из них застрял компьютер, вы можете повторить эту технику для самой этой функции, возможно, отобразив значение локальных переменных, чтобы помочь вам понять, что происходит.

Answer 4

Если вы просто пытаетесь протестировать qsort, вы можете просто получить массив строк и просто передать его в ваш известный тестовый пример.

Если вы хотите читать из файла, вам нужно использовать что-то вроде fopen, чтобы открыть файл:

http://msdn.microsoft.com/en-us/library/z5hh6ee9%28VS.80%29.aspx

Как только вы откроете его, вы сможете читать слова, используя fread.

Этот пример показывает открытие, запись, чтение, закрытие файла:

http://msdn.microsoft.com/en-us/library/kt0etdcs%28VS.100%29.aspx

Я бы хотел просто иметь статический массив, для начала, просто чтобы протестировать вашу реализацию qsort.