Писане в местоположението извън масива

Току що започнах да уча програмиране. Това е първият ми пост. Чета книга "Език за програмиране C" от Керниган и Ричи и попаднах на пример, който не разбирам (раздел 1.9, стр. 30).

Тази програма приема текст като вход, определя най-дългия ред и го отпечатва. Деклариран е ред на символен масив [MAXLINE], където MAXLINE е 1000. Това трябва да означава, че последният елемент от този масив има индекс MAXLINE-1, който е 999. Въпреки това, ако погледнете функцията getline, която се предава line[ ] масив като аргумент (и MAXLINE като lim), изглежда, че ако въведеното от потребителя е ред, по-дълъг от MAXLINE, i ще се увеличава, докато i = lim, тоест i = MAXLINE. Следователно изразът line[i] = '\0' ще бъде line[MAXLINE] = '\0'.

Това ми изглежда грешно - как можем да пишем в местоположението на линия [MAXLINE], ако размерът на линия [] е MAXLINE. Няма ли да пише в местоположението извън масива?

Единственото обяснение, което мога да измисля, е, че когато декларира char array[size], езикът C всъщност създава char array[size+1] масив, където последният елемент е запазен за NULL знака. Ако е така, това е доста объркващо и не се споменава в книгата. Може ли някой да потвърди това или да обясни какво се случва?

#include <stdio.h>
#define MAXLINE 1000 /* maximum input line length */
int getline(char line[], int maxline);
void copy(char to[], char from[]);

/* print the longest input line */
main()
{
    int len;                           /* current line length */
    int max;                          /* maximum length seen so far */
    char line[MAXLINE];          /* current input line */
    char longest[MAXLINE];     /* longest line saved here */

    max = 0;

    while ((len = getline(line, MAXLINE)) > 0)
           if (len > max) {
           max = len;
           copy(longest, line);
           }
    if (max > 0) /* there was a line */
           printf("%s", longest);

return 0;
}

/* getline: read a line into s, return length */
int getline(char s[],int lim)
{
    int c, i;

    for (i=0; i < lim-1 && (c=getchar())!=EOF && c!='\n'; ++i)
        s[i] = c;
    if (c == '\n') {
        s[i] = c;
        ++i;
    }
    s[i] = '\0';

return i;
}

/* copy: copy 'from' into 'to'; assume to is big enough */
void copy(char to[], char from[])
{
    int i;
    i = 0;

    while ((to[i] = from[i]) != '\0')
        ++i;
}

person MichaelSB    schedule 27.08.2013    source източник


Отговори (4)


Този for цикъл изглежда прави четенето в getline:

for (i=0; i < lim-1 && (c=getchar())!=EOF && c!='\n'; ++i)
    s[i] = c;

Изглежда, че i се увеличава, докато достигне lim - 1, а не lim (където lim тук е равно на MAXLINE в случая, за който говорихте). Следователно, ако редът е по-дълъг от MAXLINE, той спира след прочитане на MAXLINE-1 знака и закрепва '\0' в края, както очаквате.

person Dennis Meng    schedule 27.08.2013
comment
когато i = lim-2 оператор s[i] = c се изпълнява, тогава i се увеличава, така че сега i = lim-1. След това символът '\n' се записва в s[i], което означава s[lim-1] = '\n'. След това i се увеличава отново, така че i = lim и накрая '\0' се записва в s[i], което означава s[lim] = '\0'. Дали това е правилно? - person MichaelSB; 27.08.2013
comment
@MichaelSB Не. Ако прочетете този оператор if, вие закрепвате само новия ред if c == '\n', което може да е вярно само ако новият ред е прочетен чрез getchar(). Ако случаят е такъв, тогава i трябва да е все още по-малко от lim - 1 или в противен случай дори няма да изпълни getchar() поради късо съединение. - person Dennis Meng; 27.08.2013
comment
Кажи го така. Да предположим, че if-изявлението се оказа вярно. Единственият начин, по който това може да се случи, е да излезем от този цикъл чрез c != '\n', ставайки невярно. Ако случаят е такъв, тогава i < lim - 1 и (c=getchar())!=EOF трябва да са били верни поради късо съединение. Следователно i все още е по-малко от lim - 1, когато захващаме новия ред, и можем да сме сигурни, че i < lim, когато добавяме крайната нула. - person Dennis Meng; 27.08.2013
comment
О, сега го виждам. Ако входният ред е по-дълъг от lim, той ще бъде отрязан и няма да бъде добавен нов ред, а само NULL. Има смисъл. Благодаря ти. - person MichaelSB; 27.08.2013

Ако погледнете този ред, можете да видите, че той спира цикъла два знака преди ограничението. i < lim -1

for (i=0; i < lim-1 && (c=getchar())!=EOF && c!='\n'; ++i)

Ако символът е \n, той се добавя, така че 0-байтът е точно на границата в този случай, ако редът е точно един байт по-къс от границата (което е правилно, защото 0-байтът също е включен).

person Devolus    schedule 27.08.2013

Не, мисля, че е чисто.

Обърнете внимание, че след написването на книгата POSIX стандартизира функция getline() с напълно различен интерфейс; това може да причини известна скръб, но може да се поправи чрез преименуване на функцията от K&R.

Кодът е:

int getline(char s[],int lim)
{
    int c, i;

    for (i = 0; i < lim-1 && (c=getchar()) != EOF && c != '\n'; ++i)
        s[i] = c;
    if (c == '\n') {
        s[i] = c;
        ++i;
    }
    s[i] = '\0';

    return i;
}

Да разгледаме 2 случая:

  1. 998 знака, последвани от нов ред.
  2. 999 знака, последвани от нов ред.

В първия случай, когато знакът преди новия ред се чете, i е 997, което е по-малко от 999 (lim-1), така че getchar() се изпълнява, символът не е нито EOF, нито нов ред, и s[997] се присвоява, а i се увеличава до 998. Тъй като i все още е по-малко от 999, новият ред се чете и цикълът се прекратява. Тъй като c е нов ред, на s[998] се дава нов ред и i се увеличава до 999. След това присвояването s[i] = '\0'; записва в елемент 999, което е безопасно.

Анализът във втория случай е подобен. Когато знакът преди новия ред е прочетен, i е 998, което е по-малко от 999, така че getchar() се изпълнява, знакът не е нито EOF, нито нов ред, така че s[998] се присвоява и i се увеличава до 999. Тъй като i вече не е по-малко отколкото 999, цикълът излиза без четене на новия ред; тъй като c не е нов ред, тялото на if след цикъла не се изпълнява; тогава нулата се записва в s[999], което е безопасно.

Ако EOF бъде открит преди новия ред (така че файлът не завършва с нов ред и технически не е текстов файл според стандарта C), цикълът е безопасно прекъснат без препълване на буфера.

Има ли случай, който не е покрит?

Това се нарича тестване на граничните условия. Важно е да тествате точно под лимит (за да сте сигурни, че работи добре) и на лимита (за да сте сигурни, че се справя добре). През повечето време алгоритъмът не се нуждае от повече от един тест точно под и един тест на границата; понякога, ако алгоритъмът обработва няколко числа от двете страни на ограничение (напр. средно 3 клетки), тогава трябва да направите повече тестове на горната граница. Тестването на долната граница също е важно - тестването за 0, 1, 2, ... е много ценно.

person Jonathan Leffler    schedule 27.08.2013
comment
Много добро обяснение, благодаря. Какви са правилата за приемане на отговор? Денис Менг отговори първи на въпроса ми и ми помогна да видя грешката си, но вашият отговор е по-изчерпателен, така че не съм сигурен кой отговор трябва да отбележа като приет. - person MichaelSB; 27.08.2013
comment
От вас зависи – изберете отговора, който смятате, че е помогнал най-много. Няма да се обидя, ако продължиш с отговора на Денис — помогна ти и той стигна по-рано, така че е валидно да го избереш (и като цяло не мисля, че трябва да го променяш). Вече имате достатъчно репутация, за да гласувате за отговорите, както и да ги приемате (браво!); можете да гласувате „за“, както сметнете за добре (въпреки че тъй като съм на дневния си лимит за гласове „за“, това няма да повлияе на резултата ми, ако гласувате „за“ за отговора ми, но броят на гласовете „за“ нараства и е хубаво). Така че всичко зависи от вас... - person Jonathan Leffler; 27.08.2013

общ отговор

четенето/записването извън разпределената памет е недефинирано поведение.

В много случаи това ще доведе до страховития Segmentation fault.

В някои случаи може да се измъкнете поради чист късмет (напр. защото действителната памет, до която сте имали достъп, съществува физически/логически и не се използва по друг начин).

простият отговор е: не правете това!! защитете кода си срещу достъп до памет извън границите.

C никога не прави никаква магия, като разпределяне на n+1 байта, когато наистина сте поискали да разпределите само n байта.

що се отнася до конкретния ти пример

for (i=0; i < lim-1 /* ... */ ; ++i)

това наистина няма да увеличи i до lim, тъй като условието гарантира, че i е по-малко от lim-1, така че веднага щом достигне lim-1 (което все още е валиден индекс в рамките на s[]), то ще спре for-цикъла.

person umläute    schedule 27.08.2013