1

Тема: КіР розділ 5.6

Намагаюсь виконати програму приведену в розділі, але не виходить з'явилося декілька питань:
row.h

/* row.h */

#define MAXLINES 5000
#define MAXLEN 1000

int readlines(char *array[], int);
void writelines(char *array[], int);
void qsort(char *array[], int, int);
int getline(char *, int);

main.c

#include <stdio.h>
#include "row.h"

// Масив покажчиків
char *lineptr[MAXLINES];
int main(int argc, char *argv[])
{
    int nlines; //number of rows read

    // Зчитуємо рядки
    if((nlines = readlines(lineptr, MAXLINES)) >= 0){
        // Сортуємо
        qsort(lineptr, 0, nlines-1);
        // Виводимо результат
        writelines(lineptr, nlines);
        return 0;
    } else {
        printf("Error: too much rows\n");
        return 1;
    }
}

getline.c

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

/* Rows reading */
int readlines(char *lineptr[], int maxlines){
    int len, nlines;
    char *p, line[MAXLEN];

    nlines = 0;
    // Виконати функцію, доки є рядок довжиною більше 0
    while((len=getline(line, MAXLEN)) > 0){
        // Призначаємо покажчику p адресу покажчика на вільне місце в буфері
        if(nlines >= maxlines || (p = alloc(len)) == NULL)
            return -1;
        else{
            strcpy(p, line);
            lineptr[nlines++] = p;
        }
    }
    return nlines;
}

/* Rows printing */
void writelines(char *lineptr[], int nlines){
    while(nlines-- > 0)
        printf("%s\n", *lineptr++);
}

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

/* Ascendingly sorting v[left] ... v[right] */
void qsort(char *v[], int left, int right){
    int i, last;
    void swap(char *v[], int i, int j);

    if(left == right) // nothing to do if there are less than 2 elements in an array
        return;
    swap(v, left, (left+right)/2);
    last = left;
    for(i = left + 1; i <= right; i++)
        if(strcmp(v[i], v[left]) < 0)
            swap(v, ++last, i);
    swap(v, left, last);
    qsort(v, left, last-1);
    qsort(v, last+1, right);
}

/* Swap v[i] and v[j] */
void swap(char *v[], int i, int j){
    char *temp;

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

alloc.c

#define ALLOCSIZE 10000 // free space

char *alloc(int);
void afree(char *p);

static char allocbuf[ALLOCSIZE]; //memory for alloc
static char *allocp = allocbuf; //pointer to free place in buffer

char *alloc(int n){ //returns pointer on n symbols
    if(allocbuf + ALLOCSIZE - allocp >= n){
        allocp += n; //space is exist
        return allocp - n; //old p
    } else
        return 0; //no free space
}

void afree(char *p){
    if(p >= allocbuf && p < allocbuf + ALLOCSIZE)
        allocp = p;
}

2 Востаннє редагувалося Ярослав (23.01.2013 22:41:22)

Re: КіР розділ 5.6

Компілятор скаржиться на цей рядок

if(nlines >= maxlines || (p = alloc(len)) == NULL)

В row.h необхідно було дописати ініціалізацію цих двох функцій (alloc, afree), по ходу буду задавати іще питання.

3

Re: КіР розділ 5.6

alloc() - ваша функція за умовою, чи ви її створили, бо компілятор лаявся?

У другому випадку - імовірно, бракує підключення malloc.h.

4

Re: КіР розділ 5.6

Bartash, Функція описана в alloc.c. Автор теми здається вже вирішив проблему.

5

Re: КіР розділ 5.6

Replace написав:

Bartash, Функція описана в alloc.c. Автор теми здається вже вирішив проблему.

Точно, не побачив.
Вибачаюся.

З.І: просто в голову стрільнуло, що схожа за назвою функція була виявлена з бубном ув одній із XLS-бібліотек.
:)

6 Востаннє редагувалося Ярослав (24.01.2013 20:00:46)

Re: КіР розділ 5.6

Поясніть мені будь ласка що має робити функція qsort, в книзі сказано що вона сортує масив покажчиків таким чином, щоб елемент масиву з індексом 0 вказував на найменший елемент і так далі за зростанням, наприклад 0123 із рядків (0123, abcd, def). Але мені якось важко уявляється те, яким чином це тут досягається.

7

Re: КіР розділ 5.6

Сіль у функції strcmp().

Вона повертає:
-1, якщо лівий рядок "менший" за алфавітом;
0, якщо рядки алфавітно еквівалентні;
+1, якщо лівий рядок "більший" за алфавітом.

А так - схоже на звичайний бульбашковий алгоритм сортування.

8

Re: КіР розділ 5.6

void qsort(char *v[], int left, int right){
    int i, last;
    void swap(char *v[], int i, int j);
 
    if(left == right) // nothing to do if there are less than 2 elements in an array
        return;
    swap(v, left, (left+right)/2);
    last = left;
    for(i = left + 1; i <= right; i++)
        if(strcmp(v[i], v[left]) < 0)
            swap(v, ++last, i);
    swap(v, left, last);
    qsort(v, left, last-1);
    qsort(v, last+1, right);
}

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

void swap(char *v[], int i, int j);
void qsort(char *v[], int left, int right){
    int i, last;
 
    if(left == right) // nothing to do if there are less than 2 elements in an array
        return;
    swap(v, left, (left+right)/2);
    last = left;
    for(i = left + 1; i <= right; i++)
        if(strcmp(v[i], v[left]) < 0)
            swap(v, ++last, i);
    swap(v, left, last);
    qsort(v, left, last-1);
    qsort(v, last+1, right);
}