1 Востаннє редагувалося Ярослав (22.04.2013 07:35:09)

Тема: Вправа 5.15 КіР: Ігнорування регістру в порівнянні двох рядків

Вітаю, форумчани!
Виконую я цю вправу і не можу зрозуміти що я роблю не правильно:
Перевіряємо з опцією -f
Зробимо простий ввід:
aaa
aaA
aAA
AAA
Який програма має визначати як тотожні рядки і функція strcmp має повернути 0.
Так і є, але після цього qsort все одно сортує якось рядки і ефект несортування в такому випадку не досягається.

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

#define MAXLINES 5000 /* max #lines to be sorted */
char *lineptr[MAXLINES]; /* pointers to text lines */
int ign_case = 0;

int readlines(char *lineptr[], int nlines);
void writelines(char *lineptr[], int nlines, int reversal);
void qsort1(void *lineptr[], int left, int right, int (*comp)(void *, void *));
int numcmp(char *, char *);
int strcmp1(char *, char *);

/* sort input lines */
int main(int argc, char *argv[])
{
    int nlines; /* number of input lines read */
        int numeric = 0, reversal = 0;
        
        printf("Soring lines:\n");
        if(argc>1){
            while(argc-- > 1){
                if(strcmp(argv[argc], "-n") == 0){
                    numeric = 1;
                    printf("  numeric\n");
                } else if(strcmp(argv[argc], "-r") == 0){
                    reversal = 1;
                    printf("  reversal\n");
                } else if(strcmp(argv[argc], "-f") == 0){
                    ign_case = 1;
                    printf("  ignore case\n");
                } else 
                    printf("[ERROR] Unknown param: %s\n", argv[argc]);
            }
        } else {
            printf("  alphabetical\n");
        }
    if((nlines = readlines(lineptr, MAXLINES)) >= 0) {
        qsort1((void **) lineptr, 0, nlines-1, 
                        (int (*)(void*, void*))(numeric ? numcmp : strcmp1));
         writelines(lineptr, nlines, reversal);
         return 0;
    } else {
        printf("error: input too big to sort\n");
        return 1;
    }
}

#define MAXLEN 1000 /* max length of any input line */

int getline1(char *, int);
char *alloc(int);

/* readlines: read input lines */
int readlines(char *lineptr[], int maxlines){
    int len, nlines;
    char *p, line[MAXLEN];
    
    nlines = 0;
    while ((len = getline1(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;
}

int getline1(char *s, int max){
    int i=0;
    while((*s = getchar()) != '\n' && *s != EOF && i < max-1){
        s++;
        i++;
    }
    if(*s == '\n')
            i++;
        if(*s == EOF)
            return 0;
    return i;
}

/* writelines:  write output lines */
void writelines(char *lineptr[], int nlines, int reversal){
    int i;
    if(reversal){
       while (nlines-- > 0)
           printf("%s\n", lineptr[nlines]);
    }
       while (nlines-- > 0)
           printf("%s\n", *lineptr++);
}

/* qsort1: sort v[left]...v[right] into increasing order */
void qsort1(void *v[], int left, int right, int(*comp)(void *, void *)){
    int i, last;
    void swap(void *v[], int i, int j);
    
    if (left >= right) /* do nothing if array contains */
        return; /* fewer than two elements */
    
    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, i);
    
    swap(v, left, last);
    qsort1(v, left, last-1, comp);
    qsort1(v, last+1, right, comp);
} 

/* swap:  interchange v[i] and v[j] */
void swap(void *v[], int i, int j){
    void *temp;
    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
}

#define ALLOCSIZE 10000 /* size of available space */
static char allocbuf[ALLOCSIZE]; /* storage for alloc */
static char *allocp = allocbuf; /* next free position */

char *alloc(int n) /* return pointer to n characters */
{
    if (allocbuf + ALLOCSIZE - allocp >= n) { /* it fits */
        allocp += n;
        return allocp - n; /* old p */
    } else /* not enough room */
    return 0;
} 



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;
}

int strcmp1(char *s1, char *s2){
/*!!!*/    if(ign_case){
/*!!!*/    while(*s1 == *s2 || 
/*!!!*/                ( (*s1 < *s2) ? (*s1+32 == *s2) : (*s2+32 == *s1) ) ){
/*!!!*/            printf("%c comp %c\n", *s1, *s2);
/*!!!*/            s1++;
/*!!!*/            s2++;
/*!!!*/            if(*s1 == '\0')
/*!!!*/                return 0;
/*!!!*/        }
    } else {
        for( ; *s1 == *s2; s1++, s2++)
            if(*s1 == '\0')
                return 0;
    }
    printf("strcmp: %d\n", *s1 - *s2);
    return *s1 - *s2;
}

2

Re: Вправа 5.15 КіР: Ігнорування регістру в порівнянні двох рядків

І Тебе вітаймо, keithfay!
Не дуже зрозумів, Тобі потрібно, щоб сортування повертало вхідний результат?

3

Re: Вправа 5.15 КіР: Ігнорування регістру в порівнянні двох рядків

Маєте на увазі, що порівнює без регістру, а сортує з регістром? Та ж qsort() у даній реалізації і не виявляє регістронечутливість. :)

4

Re: Вправа 5.15 КіР: Ігнорування регістру в порівнянні двох рядків

Ось моє припущення. Зверніть увагу сюди:

int strcmp1(char *s1, char *s2){
/*!!!*/ if(ign_case){
/*!!!*/ while(*s1 == *s2 ||
/*!!!*/ ( (*s1 < *s2) ? (*s1+32 == *s2) : (*s2+32 == *s1) ) ){
/*!!!*/ printf("%c comp %c\n", *s1, *s2);
/*!!!*/ s1++;
/*!!!*/ s2++;
/*!!!*/ if(*s1 == '\0')
/*!!!*/ return 0;
/*!!!*/ }
}

В разі такого вводу:
ааа
аАА
функція має повернути 0
Тепер глянемо на це:

void qsort1(void *v[], int left, int right, int(*comp)(void *, void *)){
int i, last;
void swap(void *v[], int i, int j);
if (left >= right) /* do nothing if array contains */
return; /* fewer than two elements */
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, i);
swap(v, left, last);
qsort1(v, left, last-1, comp);
qsort1(v, last+1, right, comp);
} 

swap(v, left, (left + right)/2); бере серединний елемент і ставить його ліворуч
Потім опрацьовується це:

/*!!!*/ for (i = left+1; i <= right; i++)
/*!!!*/ if ((*comp)(v[i], v[left]) < 0)
/*!!!*/ swap(v, ++last, i);

І кожного разу воно отримує 0
Функція swap не працює, рядки мають залишитись на місті
swap(v, left, last); Мало б повернути серединний елемент на місце, але інкремент last не відбувається, тому серединний елемент залишається там де був.
Що із цим можна поробити?

5

Re: Вправа 5.15 КіР: Ігнорування регістру в порівнянні двох рядків

Я отут зараз писав повідомлення про те що в цьому прикладі, хлопець теж має ту саму проблему, а тепер до мене дійшло, що таки задача вирішена, бо якщо ми ігноруємо регістр, то не має значення який може бути рядок
такий: ааа
чи такий: ааА
Задача полягає в тому, щоб програма їх сприймала як еквівалентні. І ця мета досягнута.
А от збереження порядку вхідних рядків з ігноруванням регістру - це уже інша задача.

6

Re: Вправа 5.15 КіР: Ігнорування регістру в порівнянні двох рядків

keithfay написав:

Я отут зараз писав повідомлення про те що в цьому прикладі, хлопець теж має ту саму проблему, а тепер до мене дійшло, що таки задача вирішена, бо якщо ми ігноруємо регістр, то не має значення який може бути рядок
такий: ааа
чи такий: ааА
Задача полягає в тому, щоб програма їх сприймала як еквівалентні. І ця мета досягнута.
А от збереження порядку вхідних рядків з ігноруванням регістру - це уже інша задача.

Мінус мені у карму: забув про існування toupper. :(