nkcii sravneniya i perestanovki, my mozhem organizovat' sortirovku po razlichnym kriteriyam. Imenno takoj podhod ispol'zuetsya v nashej novoj programme sortirovki. Kak i prezhde, leksikograficheskoe sravnenie dvuh strok osushchestvlyaetsya funkciej STRCMP, a perestanovka funkciej SWAP; nam nuzhna eshche funkciya NUMCMP, sravnivayushchaya dve stroki na osnove chislennogo znacheniya i vozvrashchayushchaya uslovnoe ukaza- nie togo zhe vida, chto i STRCMP. |ti tri funkcii opisyvayutsya v MAIN i ukazateli na nih peredayutsya v SORT. V svoyu ochered' funkciya SORT obrashchaetsya k etim funkciyam cherez ih ukazateli. my urezali obrabotku oshibok v argumentah s tem, chtoby sosre- dotochit'sya na glavnyh voprosah. #DEFINE LINES 100 /* MAX NUMBER OF LINES TO BE SORTED */ MAIN(ARGC, ARGV) /* SORT INPUT LINES */ INT ARGC; CHAR *ARGV[]; \( CHAR *LINEPTR[LINES]; /* POINTERS TO TEXT LINES */ INT NLINES; /* NUMBER OF INPUT LINES READ */ INT STRCMP(), NUMCMP(); /* COMPARSION FUNCTIONS */ INT SWAP(); /* EXCHANGE FUNCTION */ INT NUMERIC = 0; /* 1 IF NUMERIC SORT */ IF(ARGC>1 && ARGV[1][0] == '-' && ARGV[1][1]=='N') NUMERIC = 1; IF(NLINES = READLINES(LINEPTR, LINES)) >= 0) \( IF (NUMERIC) SORT(LINEPTR, NLINES, NUMCMP, SWAP); ELSE SORT(LINEPTR, NLINES, STRCMP, SWAP); WRITELINES(LINEPTR, NLINES); \) ELSE PRINTF("INPUT TOO BIG TO SORT\N"); \) Zdes' STRCMP, NIMCMP i SWAP - adresa funkcij; tak kak izves- tno, chto eto funkcii, operaciya & zdes' ne nuzhna sovershenno analogichno tomu, kak ona ne nuzhna i pered imenem massiva. Peredacha adresov funkcij organizuetsya kompilyatorom. Vtoroj shag sostoit v modifikacii SORT: SORT(V, N, COMP, EXCH) /* SORT STRINGS V[0] ... V[N-1] */ CHAR *V[]; /* INTO INCREASING ORDER */ INT N; INT (*COMP)(), (*EXCH)(); \( INT GAP, I, J; FOR(GAP = N/2; GAP > 0; GAP /= 2) FOR(I = GAP; I < N; I++) FOR(J = I-GAP; J >= 0; J -= GAP) \( IF((*COMP)(V[J], V[J+GAP]) <= 0) BREAK; (*EXCH)(&V[J], &V[J+GAP]); \) \) Zdes' sleduet obratit' opredelennoe vnimanie na opisa- niya. Opisanie INT (*COMP)() govorit, chto COMP yavlyaetsya ukazatelem na funkciyu, kotoraya vozvrashchaet znachenie tipa INT. Pervye kruglye skobki zdes' neobhodimy; bez nih opisanie INT *COMP() govorilo by, chto COMP yavlyaetsya funkciej, vozvrashchayushchej ukaza- tel' na celye, chto, konechno, sovershenno drugaya veshch'. Ispol'zovanie COMP v stroke IF (*COMP)(V[J], V[J+GAP]) <= 0) polnost'yu soglasuetsya s opisaniem: COMP - ukazatel' na funk- ciyu, *COMP - sama funkciya, a (*COMP)(V[J], V[J+GAP]) - obrashchenie k nej. Kruglye skobki neobhodimy dlya pravil'nogo ob容dineniya komponentov. My uzhe privodili funkciyu STRCMP, sravnivayushchuyu dve stroki po pervomu chislennomu znacheniyu: NUMCMP(S1, S2) /* COMPARE S1 AND S2 NUMERICALLY */ CHAR *S1, *S2; \( DOUBLE ATOF(), V1, V2; V1 = ATOF(S1); V2 = ATOF(S2); IF(V1 < V2) RETURN(-1); ELSE IF(V1 > V2) RETURN(1); ELSE RETURN (0); \) Zaklyuchitel'nyj shag sostoit v dobavlenii funkcii SWAP, perestavlyayushchej dva ukazatelya. |to legko sdelat', neposredst- venno ispol'zuya to, chto my izlozhili ranee v etoj glave. SWAP(PX, PY) /* INTERCHANGE *PX AND *PY */ CHAR *PX[], *PY[]; \( CHAR *TEMP; TEMP = *PX; *PX = *PY; *PY = TEMP; \) Imeetsya mnozhestvo drugih neobyazyatel'nyh argumentov, ko- torye mogut byt' vklyucheny v programmu sortirovki: nekotorye iz nih sostavlyayut interesnye uprazhneniya. Uprazhnenie 5-11 --------------- Modificirujte SORT takim obrazom, chtoby ona rabotala s metkoj -R, ukazyvayushchej na sortirovku v obratnom (ubyvayushchem) poryadke. Konechno, -R dolzhna rabotat' s -N. Uprazhnenie 5-12 --------------- Dobav'te neobyazatel'nyj argument -F, ob容dinyayushchij vmeste propisnye i strochnye bukvy, tak chtoby razlichie registrov ne uchityvalos' vo vremya sortirovki: dannye iz verhnego i nizhne- go registrov sortiruyutsya vmeste, tak chto bukva 'a' propisnoe i 'a' strochnoe okazyvayutsya sosednimi , a ne razdelennymi ce- lym alfavitom. Uprazhnenie 5-13 --------------- Dobav'te neobyazatel'nyj argument -D ("slovarnoe uporyado- chivanie"), pri nalichii kotorogo sravnivayutsya tol'ko bukvy, chisla i probely. Pozabot'tes' o tom, chtoby eta funkciya rabo- tala i vmeste s -F. Uprazhnenie 5-14 --------------- Dobav'te vozmozhnost' obrabotki polej, tak chtoby mozhno bylo sortirovat' polya vnutri strok. Kazhdoe pole dolzhno sor- tirovat'sya v sootvetstvii s nezavisimym naborom neobyazatel'- nyh argumentov. (predmetnyj ukazatel' etoj knigi sortiroval- sya s pomoshch'yu argumentov -DF dlya kategorii ukazatelya i s -N dlya nomerov stranic).  * 6. Struktury *  Struktura - eto nabor iz odnoj ili bolee peremennyh, vozmozhno razlichnyh tipov, sgruppirovannyh pod odnim imenem dlya udobstva obrabotki. (V nekotoryh yazykah, samyj izvestnyj iz kotoryh paskal', struktury nazyvayutsya "zapisyami"). Tradicionnym primerom struktury yavlyaetsya uchetnaya kartoch- ka rabotayushchego: "sluzhashchij" opisyvaetsya naborom atributov ta- kih, kak familiya, imya, otchestvo (f.i.o.), adres, kod soci- al'nogo obespecheniya, zarplata i t.d. Nekotorye iz etih atri- butov sami mogut okazat'sya strukturami: f.i.o. Imeet nes- kol'ko komponent, kak i adres, i dazhe zarplata. Struktury okazyvayutsya poleznymi pri organizacii slozhnyh dannyh osobenno v bol'shih programmah, poskol'ku vo mnogih situaciyah oni pozvolyayut sgruppirovat' svyazannye dannye takim obrazom, chto s nimi mozhno obrashchat'sya, kak s odnim celym, a ne kak s otdel'nymi ob容ktami. V etoj glave my postaraemsya prodemonstrirovat' to, kak ispol'zuyutsya struktury. Program- my, kotorye my dlya etogo budem ispol'zovat', bol'she, chem mnogie drugie v etoj knige, no vse zhe dostatochno umerennyh razmerov. 6.1. Osnovnye svedeniya Davajte snova obratimsya k proceduram preobrazovaniya daty iz glavy 5. Data sostoit iz neskol'kih chastej takih, kak den', mesyac, i god, i, vozmozhno, den' goda i imya mesyaca. |ti pyat' peremennyh mozhno ob容denit' v odnu strukturu vida: STRUCT DATE \( INT DAY; INT MONTH; INT YEAR; INT YEARDAY; CHAR MON_NAME[4]; \); Opisanie struktury, sostoyashchee iz zaklyuchennogo v figurnye skobki spiska opisanij, nachinaetsya s klyuchevogo slova STRUCT. Za slovom STRUCT mozhet sledovat' neobyazatel'noe imya, nazyva- emoe yarlykom struktury (zdes' eto DATe). Takoj yarlyk imenuet struktury etogo vida i mozhet ispol'zovat'sya v dal'nejshem kak sokrashchennaya zapis' podrobnogo opisaniya. |lementy ili peremennye, upomyanutye v strukture, nazyva- yutsya chlenami. YArlyki i chleny struktur mogut imet' takie zhe imena, chto i obychnye peremennye (t.e. Ne yavlyayushchiesya chlenami struktur), poskol'ku ih imena vsegda mozhno razlichit' po kon- tekstu. Konechno, obychno odinakovye imena prisvaivayut tol'ko tesno svyazannym ob容ktam. Tochno tak zhe, kak v sluchae lyubogo drugogo bazisnogo ti- pa, za pravoj figurnoj skobkoj, zakryvayushchej spisok chlenov, mozhet sledovat' spisok peremennyh. Operator STRUCT \( ...\) X,Y,Z; sintaksicheski analogichen INT X,Y,Z; v tom smysle, chto kazhdyj iz operatorov opisyvaet X , Y i Z v kachestve peremennyh sootvestvuyushchih tipov i privodit k vyde- leniyu dlya nih pamyati. Opisanie struktury, za kotorym ne sleduet spiska pere- mennyh, ne privodit k vydeleniyu kakoj-libo pamyati; ono tol'- ko opredelyaet shablon ili formu struktury. Odnako, esli takoe opisanie snabzheno yarlykom, to etot yarlyk mozhet byt' ispol'- zovan pozdnee pri opredelenii fakticheskih ekzemplyarov struk- tur. Naprimer, esli dano privedennoe vyshe opisanie DATE, to STRUCT DATE D; opredelyaet peremennuyu D v kachestve struktury tipa DATE. Vneshnyuyu ili staticheskuyu strukturu mozhno inicializirovat', pomestiv vsled za ee opredeleniem spisok inicializatorov dlya ee komponent: STRUCT DATE D=\( 4, 7, 1776, 186, "JUL"\); CHlen opredelennoj struktury mozhet byt' ukazan v vyrazhe- nii s pomoshch'yu konstrukcii vida imya struktury . CHlen -------------------- Operaciya ukazaniya chlena struktury "." svyazyvaet imya struktu- ry i imya chlena. V kachestve primera opredelim LEAP (priznak visokosnosti goda) na osnove daty, nahodyashchejsya v strukture D, LEAP = D.YEAR % 4 == 0 && D.YEAR % 100 != 0 \!\! D.YEAR % 400 == 0; ili proverim imya mesyaca IF (STRCMP(D.MON_NAME, "AUG") == 0) ... Ili preobrazuem pervyj simvol imeni mesyaca tak, chtoby ono nachinalos' so strochnoj bukvy D.MON_NAME[0] = LOWER(D.MON_NAME[0]); Struktury mogut byt' vlozhennymi; uchetnaya kartochka sluzha- shchego mozhet fakticheski vyglyadet' tak: STRUCT PERSON \( CHAR NAME[NAMESIZE]; CHAR ADDRESS[ADRSIZE]; LONG ZIPCODE; /* pochtovyj indeks */ LONG SS_NUMBER; /* kod soc. Obespecheniya */ DOUBLE SALARY; /* zarplata */ STRUCT DATE BIRTHDATE; /* data rozhdeniya */ STRUCT DATE HIREDATE; /* data postupleniya na rabotu */ \); Struktura PERSON soderzhit dve struktury tipa DATE . Esli my opredelim EMP kak STRUCT PERSON EMP; to EMP.BIRTHDATE.MONTH budet ssylat'sya na mesyac rozhdeniya. Operaciya ukazaniya chlena struktury "." associiruetsya sleva napravo. 6.2. Struktury i funkcii V yazyke "C" sushchestvuet ryad ogranichenij na ispol'zovanie struktur. Obyazatel'nye pravila zaklyuchayutsya v tom, chto edins- tvennye operacii, kotorye vy mozhete provodit' so struktura- mi, sostoyat v opredelenii ee adresa s pomoshch'yu operacii & i dostupe k odnomu iz ee chlenov. |to vlechet za soboj to, chto struktury nel'zya prisvaivat' ili kopirovat' kak celoe, i chto oni ne mogut byt' peredany funkciyam ili vozvrashcheny imi. (V posleduyushchih versiyah eti ogranicheniya budut snyaty). Na ukaza- teli struktur eti ogranicheniya odnako ne nakladyvayutsya, tak chto struktury i funkcii vse zhe mogut s udobstvom rabotat' sovmestno. I nakonec, avtomaticheskie struktury, kak i avto- maticheskie massivy, ne mogut byt' inicializirovany; inicia- lizaciya vozmozhna tol'ko v sluchae vneshnih ili staticheskih struktur. Davajte razberem nekotorye iz etih voprosov, perepisav s etoj cel'yu funkcii perobrazovaniya daty iz predydushchej glavy tak, chtoby oni ispol'zovali struktury. Tak kak pravila zap- reshchayut neposredstvennuyu peredachu struktury funkcii, to my dolzhny libo peredavat' otdel'no komponenty, libo peredat' ukazatel' vsej struktury. Pervaya vozmozhnost' demonstriruetsya na primere funkcii DAY_OF_YEAR, kak my ee napisali v glave 5: D.YEARDAY = DAY_OF_YEAR(D.YEAR, D.MONTH, D.DAY); drugoj sposob sostoit v peredache ukazatelya. esli my opishem HIREDATE kak STRUCT DATE HIREDATE; i perepishem DAY_OF_YEAR nuzhnym obrazom, my smozhem togda na- pisat' HIREDATE YEARDAY = DAY_OF_YEAR(&HIREDATE); peredavaya ukazatel' na HIREDATE funkcii DAY_OF_YEAR . Funk- ciya dolzhna byt' modificirovana, potomu chto ee argument te- per' yavlyaetsya ukazatelem, a ne spiskom peremennyh. DAY_OF_YEAR(PD) /* SET DAY OF YEAR FROM MONTH, DAY */ STRUCT DATE *PD; \( INT I, DAY, LEAP; DAY = PD->DAY; LEAP = PD->YEAR % 4 == 0 && PD->YEAR % 100 != 0 \!\! PD->YEAR % 400 == 0; FOR (I =1; I < PD->MONTH; I++) DAY += DAY_TAB[LEAP][I]; RETURN(DAY); \) Opisanie STRUCT DATE *PD; govorit, chto PD yavlyaetsya ukazatelem struktury tipa DATE. Zapis', pokazannaya na primere PD->YEAR yavlyaetsya novoj. Esli P - ukazatel' na strukturu, to P-> chlen struktury ------------------ obrashchaetsya k konkretnomu chlenu. (Operaciya -> - eto znak mi- nus, za kotorym sleduet znak ">".) Tak kak PD ukazyvaet na strukturu, to k chlenu YEAR mozhno obratit'sya i sleduyushchim obrazom (*PD).YEAR no ukazateli struktur ispol'zuyutsya nastol'ko chasto, chto za- pis' -> okazyvaetsya udobnym sokrashcheniem. Kruglye skobki v (*PD).YEAR neobhodimy, potomu chto operaciya ukazaniya chlena stuktury starshe , chem * . Obe operacii, "->" i ".", associi- ruyutsya sleva napravo, tak chto konstrukcii sleva i sprava zkvivalentny P->Q->MEMB (P->Q)->MEMB EMP.BIRTHDATE.MONTH (EMP.BIRTHDATE).MONTH Dlya polnoty nizhe privoditsya drugaya funkciya, MONTH_DAY, pere- pisannaya s ispol'zovaniem struktur. MONTH_DAY(PD) /* SET MONTH AND DAY FROM DAY OF YEAR */ STRUCT DATE *PD; \( INT I, LEAP; LEAP = PD->YEAR % 4 == 0 && PD->YEAR % 100 != 0 \!\! PD->YEAR % 400 == 0; PD->DAY = PD->YEARDAY; FOR (I = 1; PD->DAY > DAY_TAB[LEAP][I]; I++) PD->DAY -= DAY_TAB[LEAP][I]; PD->MONTH = I; \) Operacii raboty so strukturami "->" i "." naryadu so () dlya spiska argumentov i [] dlya indeksov nahodyatsya na samom verhu ierarhii strashinstva operacij i, sledovatel'no, svyazy- vayutsya ochen' krepko. Esli, naprimer, imeetsya opisanie STRUCT \( INT X; INT *Y; \) *P; to vyrazhenie ++P->X uvelichivaet h, a ne r, tak kak ono ekvivalentno vyrazheniyu ++(P->h). Dlya izmeneniya poryadka vypolneniya operacij mozhno ispol'zovat' kruglye skobki: (++P)->h uvelichivaet P do dos- tupa k h, a (P++)->X uvelichivaet P posle. (kruglye skobki v poslednem sluchae neobyazatel'ny. Pochemu ?) Sovershenno analogichno *P->Y izvlekaet to, na chto ukazy- vaet Y; *P->Y++ uvelichivaet Y posle obrabotki togo, na chto on ukazyvaet (tochno tak zhe, kak i *S++); (*P->Y)++ uvelichi- vaet to, na chto ukazyvaet Y; *P++->Y uvelichivaet P posle vy- borki togo, na chto ukazyvaet Y. 6.3. Massivy sruktur Struktury osobenno podhodyat dlya upravleniya massivami svyazannyh peremennyh. Rassmotrim, naprimer, programmu pods- cheta chisla vhozhdenij kazhdogo klyuchevogo slova yazyka "C". Nam nuzhen massiv simvol'nyh strok dlya hraneniya imen i massiv ce- lyh dlya podscheta. odna iz vozmozhnostej sostoit v ispol'zova- nii dvuh parallel'nyh massivov KEYWORD i KEYCOUNT: CHAR *KEYWORD [NKEYS]; INT KEYCOUNT [NKEYS]; No sam fakt, chto massivy parallel'ny, ukazyvaet na vozmozh- nost' drugoj organizacii. Kazhdoe klyuchevoe slovo zdes' po su- shchestvu yavlyaetsya paroj: CHAR *KEYWORD; INT KEYCOUNT; i, sledovatel'no, imeetsya massiv par. Opisanie struktury STRUCT KEY \( CHAR *KEYWORD; INT KEYCOUNT; \) KEYTAB [NKEYS]; operdelyaet massiv KEYTAB struktur takogo tipa i otvodit dlya nih pamyat'. Kazhdyj element massiva yavlyaetsya strukturoj. |to mozhno bylo by zapisat' i tak: STRUCT KEY \( CHAR *KEYWORD; INT KEYCOUNT; \); STRUCT KEY KEYTAB [NKEYS]; Tak kak struktura KEYTAB fakticheski soderzhit postoyannyj nabor imen, to legche vsego inicializirovat' ee odin raz i dlya vseh chlenov pri opredelenii. Inicializaciya struktur vpolne analogichna predydushchim inicializaciyam - za opredeleni- em sleduet zaklyuchennyj v figurnye skobki spisok inicializa- torov: STRUCT KEY \( CHAR *KEYWORD; INT KEYCOUNT; \) KEYTAB[] =\( "BREAK", 0, "CASE", 0, "CHAR", 0, "CONTINUE", 0, "DEFAULT", 0, /* ... */ "UNSIGNED", 0, "WHILE", 0 \); Inicializatory perechislyayutsya parami sootvetstvenno chlenam struktury. Bylo by bolee tochno zaklyuchat' v figurnye skobki inicializatory dlya kazhdoj "stroki" ili struktury sleduyushchim obrazom: \( "BREAK", 0 \), \( "CASE", 0 \), . . . No kogda inicializatory yavlyayutsya prostymi peremennymi ili simvol'nymi strokami i vse oni prisutstvuyut, to vo vnutren- nih figurnyh skobkah net neobhodimosti. Kak obychno, kompilya- tor sam vychislit chislo elementov massiva KEYTAB, esli inici- alizatory prisutstvuyut, a skobki [] ostavleny pustymi. Programma podscheta klyuchevyh slov nachinaetsya s opredele- niya massiva KEYTAB. vedushchaya programma chitaet svoj fajl vvo- da, posledovatel'no obrashchayas' k funkcii GETWORD, kotoraya iz- vlekaet iz vvoda po odnomu slovu za obrashchenie. Kazhdoe slovo ishchetsya v massive KEYTAB s pomoshch'yu varianta funkcii binarnogo poiska, napisannoj nami v glave 3. (Konechno, chtoby eta funk- ciya rabotala, spisok klyuchevyh slov dolzhen byt' raspolozhen v poryadke vozrastaniya). #DEFINE MAXWORD 20 MAIN() /* COUNT "C" KEYWORDS */ \( INT N, T; CHAR WORD[MAXWORD]; WHILE ((T = GETWORD(WORD,MAXWORD)) != EOF) IF (T == LETTER) IF((N = BINARY(WORD,KEYTAB,NKEYS)) >= 0) KEYTAB[N].KEYCOUNT++; FOR (N =0; N < NKEYS; N++) IF (KEYTAB[N].KEYCOUNT > 0) PRINTF("%4D %S\N", KEYTAB[N].KEYCOUNT, KEYTAB[N].KEYWORD); \) BINARY(WORD, TAB, N) /* FIND WORD IN TAB[0]...TAB[N-1] */ CHAR *WORD; STRUCT KEY TAB[]; INT N; \( INT LOW, HIGH, MID, COND; LOW = 0; HIGH = N - 1; WHILE (LOW <= HIGH) \( MID = (LOW+HIGH) / 2; IF((COND = STRCMP(WORD, TAB[MID].KEYWORD)) < 0) HIGH = MID - 1; ELSE IF (COND > 0) LOW = MID + 1; ELSE RETURN (MID); \) RETURN(-1); \) My vskore privedem funkciyu GETWORD; poka dostatochno skazat', chto ona vozvrashchaet LETTER kazhdyj raz, kak ona nahodit slovo, i kopiruet eto slovo v svoj pervyj argument. Velichina NKEYS - eto kolichestvo klyuchevyh slov v massive KEYTAB . Hotya my mozhem soschitat' eto chislo vruchnuyu, gorazdo legche i nadezhnee poruchit' eto mashine, osobenno v tom sluchae, esli spisok klyuchevyh slov podverzhen izmeneniyam. Odnoj iz vozmozhnostej bylo by zakonchit' spisok inicializatorov ukaza- niem na nul' i zatem projti v cikle skvoz' massiv KEYTAB, poka ne najdetsya konec. No, poskol'ku razmer etogo massiva polnost'yu opredelen k momentu kompilyacii, zdes' imeetsya bolee prostaya vozmozhnost'. CHislo elementov prosto est' SIZE OF KEYTAB / SIZE OF STRUCT KEY delo v tom, chto v yazyke "C" predusmotrena unarnaya operaciya SIZEOF, vypolnyaemaya vo vremya kompilyacii, kotoraya pozvolyaet vychislit' razmer lyubogo ob容kta. Vyrazhenie SIZEOF(OBJECT) vydaet celoe, ravnoe razmeru ukazannogo ob容kta. (Razmer op- redelyaetsya v nespecificirovannyh edinicah, nazyvaemyh "baj- tami", kotorye imeyut tot zhe razmer, chto i peremennye tipa CHAR). Ob容kt mozhet byt' fakticheskoj peremennoj, massivom i strukturoj, ili imenem osnovnogo tipa, kak INT ili DOUBLE, ili imenem proizvodnogo tipa, kak struktura. V nashem sluchae chislo klyuchevyh slov ravno razmeru massiva, delennomu na raz- mer odnogo elementa massiva. |to vychislenie ispol'zuetsya v utverzhdenii #DEFINE dlya ustanovleniya znacheniya NKEYS: #DEFINE NKEYS (SIZEOF(KEYTAB) / SIZEOF(STRUCT KEY)) Teper' perejdem k funkcii GETWORD. My fakticheski napisa- li bolee obshchij variant funkcii GETWORD, chem neobhodimo dlya etoj programmy, no on ne na mnogo bolee slozhen. Funkciya GETWORD vozvrashchaet sleduyushchee "slovo" iz vvoda, gde slovom schitaetsya libo stroka bukv i cifr, nachinayushchihsya s bukvy, li- bo otdel'nyj simvol. Tip ob容kta vozvrashchaetsya v kachetve zna- cheniya funkcii; eto - LETTER, esli najdeno slovo, EOF dlya konca fajla i sam simvol, esli on ne bukvennyj. GETWORD(W, LIM) /* GET NEXT WORD FROM INPUT */ CHAR *W; INT LIM; \( INT C, T; IF (TYPE(C=*W++=GETCH()) !=LETTER) \( *W='\0'; RETURN(C); \) WHILE (--LIM > 0) \( T = TYPE(C = *W++ = GETCH()); IF (T ! = LETTER && T ! = DIGIT) \( UNGETCH(C); BREAK; \) \) *(W-1) - '\0'; RETURN(LETTER); \) Funkciya GETWORD ispol'zuet funkcii GETCH i UNGETCH, kotorye my napisali v glave 4: kogda nabor alfavitnyh simvolov pre- ryvaetsya, funkciya GETWORD poluchaet odin lishnij simvol. V re- zul'tate vyzova UNGETCH etot simvol pomeshchaetsya nazad vo vvod dlya sleduyushchego obrashcheniya. Funkciya GETWORD obrashchaetsya k funkcii TYPE dlya opredele- niya tipa kazhdogo otdel'nogo simvola iz fajla vvoda. Vot va- riant, spravedlivyj tol'ko dlya alfavita ASCII. TYPE(C) /* RETURN TYPE OF ASCII CHARACTER */ INT C; \( IF (C>= 'A' && C<= 'Z' \!\! C>= 'A' && C<= 'Z') RETURN(LETTER); ELSE IF (C>= '0' && C<= '9') RETURN(DIGIT); ELSE RETURN(C); \) Simvolicheskie konstanty LETTER i DIGIT mogut imet' lyubye znacheniya, lish' by oni ne vstupali v konflikt s simvolami, otlichnymi ot bukvenno-cifrovyh, i s EOF; ochevidno vozmozhen sleduyushchij vybor #DEFINE LETTER 'A' #DEFINE DIGIT '0' funkciya GETWORD mogla by rabotat' bystree, esli by obrashcheniya k funkcii TYPE byli zameneny obrashcheniyami k sootvetstvuyushchemu massivu TYPE[ ]. V standartnoj biblioteke yazyka "C" predus- motreny makrosy ISALPHA i ISDIGIT, dejstvuyushchie neobhodimym obrazom. Uprazhnenie 6-1 -------------- Sdelajte takuyu modifikaciyu funkcii GETWORD i ocenite, kak izmenitsya skorost' raboty programmy. Uprazhnenie 6-2 -------------- Napishite variant funkcii TYPE, ne zavisyashchij ot konkret- nogo naborasimvolov. Uprazhnenie 6-3 -------------- Napishite variant programmy podscheta klyuchevyh slov, koto- ryj by ne uchityval poyavleniya etih slov v zaklyuchennyh v ka- vychki strokah. 6.4. Ukazateli na struktury CHtoby proillyustrirovat' nekotorye soobrazheniya, svyazannye s ispol'zovaniem ukazatelej i massivov struktur, davajte snova sostavim programmu podscheta klyuchevyh strok, ispol'zuya na etot raz ukazateli, a ne indeksy massivov. Vneshnee opisanie massiva KEYTAB ne nuzhno izmenyat', no funkcii MAIN i BINARY trebuyut modifikacii. MAIN() /* COUNT C KEYWORD; POINTER VERSION */ \( INT T; CHAR WORD[MAXWORD]; STRUCT KEY *BINARY(), *P; WHILE ((T = GETWORD(WORD, MAXWORD;) !=EOF) IF (T==LETTER) IF ((P=BINARY(WORD,KEYTAB,NKEYS)) !=NULL) P->KEYCOUNT++; FOR (P=KEYTAB; P>KEYTAB + NKEYS; P++) IF (P->KEYCOUNT > 0) PRINTF("%4D %S/N", P->KEYCOUNT, P->KEYWORD); \) STRUCT KEY *BINARY(WORD, TAB, N) /* FIND WORD */ CHAR *WORD /* IN TAB[0]...TAB[N-1] */ STRUCT KEY TAB []; INT N; \( INT COND; STRUCT KEY *LOW = &TAB[0]; STRUCT KEY *HIGH = &TAB[N-1]; STRUCT KEY *MID; WHILE (LOW <= HIGH) \( MID = LOW + (HIGH-LOW) / 2; IF ((COND = STRCMP(WORD, MID->KEYWORD)) < 0) HIGH = MID - 1; ELSE IF (COND > 0) LOW = MID + 1; ELSE RETURN(MID); \) RETURN(NULL); \) Zdes' imeetsya neskol'ko momentov, kotorye stoit otme- tit'. Vo-pervyh, opisanie funkcii BINARI dolzhno ukazyvat', chto ona vozvrashchaet ukazatel' na strukturu tipa KEY, a ne na celoe; eto ob座avlyaetsya kak v funkcii MAIN, tak i v BINARY. Esli funkciya BINARI nahodit slovo, to ona vozvrashchaet ukaza- tel' na nego; esli zhe net, ona vozvrashchaet NULL. Vo-vtoryh, vse obrashcheniya k elementam massiva KEYTAB osu- shchestvlyayutsya cherez ukazateli. |to vlechet za soboj odno sushches- tvennoe izmenenie v funkcii BINARY: srednij element bol'she nel'zya vychislyat' prosto po formule MID = (LOW + HIGH) / 2 potomu chto slozhenie dvuh ukazatelej ne daet kakogo-nibud' poleznogo rezul'tata (dazhe posle deleniya na 2) i v dejstvi- tel'nosti yavlyaetsya nezakonnym. etu formulu nado zamenit' na MID = LOW + (HIGH-LOW) / 2 v rezul'tate kotoroj MID stanovitsya ukazatelem na element, raspolozhennyj poseredine mezhdu LOW i HIGH. Vam takzhe sleduet razobrat'sya v inicializacii LOW i HIGH. ukazatel' mozhno inicializirovat' adresom ranee oprede- lennogo ob容kta; imenno kak my zdes' i postupili. V funkcii MAIN my napisali FOR (P=KEYTAB; P < KEYTAB + NKEYS; P++) Esli P yavlyaetsya ukazatelem struktury, to lyubaya arifmetika s P uchityvaet fakticheskij razmer dannoj struktury, tak chto P++ uvelichivaet P na nuzhnuyu velichinu, v rezul'tate chego P ukazy- vaet na sleduyushchij element massiva struktur. No ne schitajte, chto razmer struktury raven summe razmerov ee chlenov, - iz-za trebovanij vyravnivaniya dlya razlichnyh ob容ktov v strukture mogut voznikat' "dyry". I, nakonec, neskol'ko vtorostepennyj vopros o forme za- pisi programmy. Esli vozvrashchaemaya funkciej velichina imeet tip, kak, naprimer, v STRUCT KEY *BINARY(WORD, TAB, N) To mozhet okazat'sya, chto imya funkcii trudno vydelit' sredi teksta. V svyazi s etim inogda ispol'zuetsya drugoj stil' za- pisi: STRUCT KEY * BINARY(WORD, TAB, N) |to glavnym obrazom delo vkusa; vyberite tu formu, kotoraya vam nravitsya, i priderzhivajtes' ee. 6.5. Struktury, ssylayushchiesya na sebya Predpolozhim, chto nam nado spravit'sya s bolee obshchej zada- chej, sostoyashchej v podschete chisla poyavlenij vseh slov v neko- torom fajle vvoda. Tak kak spisok slov zaranee ne izvesten, my ne mozhem ih uporyadochit' udobnym obrazom i ispol'zovat' binarnyj poisk. My dazhe ne mozhem osushchestvlyat' posledovatel'- nyj prosmotr pri postuplenii kazhdogo slova, s tem chtoby us- tanovit', ne vstrechalos' li ono ranee; takaya programma budet rabotat' vechno. (Bolee tochno, ozhidaemoe vremya raboty rastet kak kvadrat chisla vvodimyh slov). Kak zhe nam organizovat' programmu, chtoby spravit'sya so spiskom proizvol'nyh slov? Odno iz reshenij sostoit v tom, chtoby vse vremya hranit' massiv postupayushchih do sih por slov v uporyadochennom vide, po- meshchaya kazhdoe slovo v nuzhnoe mesto po mere ih postupleniya. ODnako eto ne sleduet delat', peremeshchaya slova v linejnom massive, - eto takzhe potrebuet slishkom mnogo vremeni. Vmesto etogo my ispol'zuem strukturu dannyh, nazyvaemuyu doichnym de- revom. Kazhdomu novomu slovu sootvetstvuet odin "uzel" dereva; kazhdyj uzel soderzhit: ukazatel' teksta slova ---------------------- schetchik chisla poyavlenij ----------------------- ukazatel' uzla levogo potomka ----------------------------- ukazatel' uzla pravogo potomka ------------------------------ Nikakoj uzel ne mozhet imet' bolee dvuh detej; vozmozhno ot- sutsvie detej ili nalichie tol'ko odnogo potomka. Uzly sozdayutsya takim obrazom, chto levoe podderevo kazhdo- go uzla soderzhit tol'ko te slova, kotorye men'she slova v etom uzle, a pravoe podderevo tol'ko te slova, kotorye bol'- she. CHtoby opredelit', nahoditsya li novoe slovo uzhe v dereve, nachinayut s kornya i sravnivayut novoe slovo so slovom, hranya- shchimsya v etom uzle. Esli slova sovpadayut, to vopros reshaetsya utverditel'no. Esli novoe slovo men'she slova v dereve, to perehodyat k rassmotreniyu levogo potomka; v protivnom sluchae issleduetsya pravyj potomok. Esli v nuzhnom napravlenii poto- mok otsutstvuet, to znachit novoe slovo ne nahoditsya v dereve i mesto etogo nedostayushchego potomka kak raz i yavlyaetsya mes- tom, kuda sleduet pomestit' novoe slovo. Poskol'ku poisk iz lyubogo uzla privodit k poisku odnogo iz ego potomkov, to sam process poiska po sushchestvu yavlyaetsya rekursivnym. V sootvets- tvii s etim naibolee estestvenno ispol'zovat' rekursivnye procedury vvoda i vyvoda. Vozvrashchayas' nazad k opisaniyu uzla, yasno, chto eto budet struktura s chetyr'mya komponentami: STRUCT TNODE \( /* THE BASIC NODE */ CHAR *WORD; /* POINTS TO THE TEXT */ INT COUNT; /* NUMBER OF OCCURRENCES */ STRUCT TNODE *LEFT; /* LEFT CHILD */ STRUCT TNODE *RIGHT; /* RIGHT CHILD */ \); |to "rekursivnoe" opisanie uzla mozhet pokazat'sya riskovan- nym, no na samom dele ono vpolne korrektno. Struktura ne imeet prava soderzhat' ssylku na samu sebya, no STRUCT TNODE *LEFT; opisyvaet LEFT kak ukazatel' na uzel, a ne kak sam uzel. Tekst samoj programmy okazyvaetsya udivitel'no malen'kim, esli, konechno, imet' v rasporyazhenii nabor napisannyh nami ranee procedur, obespechivayushchih nuzhnye dejstviya. My imeem v vidu funkciyu GETWORD dlya izvlecheniya kazhdogo slova iz fajla vvoda i funkciyu ALLOC dlya vydeleniya mesta dlya hraneniya slov. Vedushchaya programma prosto schityvaet slova s pomoshch'yu funk- cii GETWORD i pomeshchaet ih v derevo, ispol'zuya funkciyu TREE. #DEFINE MAXWORD 20 MAIN() /* WORD FREGUENCY COUNT */ \( STRUCT TNODE *ROOT, *TREE(); CHAR WORD[MAXWORD]; INT T; ROOT = NULL; WHILE ((T = GETWORD(WORD, MAXWORD)) \! = EOF) IF (T == LETTER) ROOT = TREE(ROOT, WORD); TREEPRINT(ROOT); \) Funkciya TREE sama po sebe prosta. Slovo peredaetsya funk- ciej MAIN k verhnemu urovnyu (kornyu) dereva. Na kazhdom etape eto slovo sravnivaetsya so slovom, uzhe hranyashchimsya v etom uz- le, i s pomoshch'yu rekursivnogo obrashcheniya k TREE prosachivaetsya vniz libo k levomu, libo k pravomu podderevu. V konce koncov eto slovo libo sovpadaet s kakim-to slovom, uzhe nahodyashchimsya v dereve (v etom sluchae schetchik uvelichivaetsya na edinicu), libo programma natolknetsya na nulevoj ukazatel', svidetel'- stvuyushchij o neobhodimosti sozdaniya i dobavleniya k derevu no- vogo uzla. V sluchae sozdaniya novogo uzla funkciya TREE vozv- rashchaet ukazatel' etogo uzla, kotoryj pomeshchaetsya v roditel'- skij uzel. STRUCT TNODE *TREE(P, W) /* INSTALL W AT OR BELOW P */ STRUCT TNODE *P; CHAR *W; \( STRUCT TNODE *TALLOC(); CHAR *STRSAVE(); INT COND; IF (P == NULL) \( /* A NEW WORD HAS ARRIVED */ P == TALLOC(); /* MAKE A NEW NODE */ P->WORD = STRSAVE(W); P->COUNT = 1; P->LEFT = P->RIGHT = NULL; \) ELSE IF ((COND = STRCMP(W, P->WORD)) == 0) P->COUNT++; /* REPEATED WORD */ ELSE IF (COND < 0)/* LOWER GOES INTO LEFT SUBTREE */ P->LEFT = TREE(P->LEFT, W); ELSE /* GREATER INTO RIGHT SUBTREE */ P->RIGHT = TREE(P->RIGHT, W); RETURN(P); \) Pamyat' dlya novogo uzla vydelyaetsya funkciej TALLOC, yavlya- yushchejsya adaptaciej dlya dannogo sluchaya funkcii ALLOC, napisan- noj nami ranee. Ona vozvrashchaet ukazatel' svobodnogo prost- ranstva, prigodnogo dlya hraneniya novogo uzla dereva. (My vskore obsudim eto podrobnee). Novoe slovo kopiruetsya funk- ciej STRSAVE v skrytoe mesto, schetchik inicializiruetsya edi- nicej, i ukazateli oboih potomkov polagayutsya ravnymi nulyu. |ta chast' programmy vypolnyaetsya tol'ko pri dobavlenii novogo uzla k rebru dereva. My zdes' opustili proverku na oshibki vozvrashchaemyh funkcij STRSAVE i TALLOC znachenij (chto nerazum- no dlya prakticheski rabotayushchej programmy). Funkciya TREEPRINT pechataet derevo, nachinaya s levogo pod- dereva; v kazhdom uzle snachala pechataetsya levoe podderevo (vse slova, kotorye mladshe etogo slova), zatem samo slovo, a zatem pravoe podderevo (vse slova, kotorye starshe). Esli vy neuverenno operiruete s rekursiej, narisujte derevo sami i napechatajte ego s pomoshch'yu funkcii TREEPRINT ; eto odna iz naibolee yasnyh rekursivnyh procedur, kotoruyu mozhno najti. TREEPRINT (P) /* PRINT TREE P RECURSIVELY */ STRUCT TNODE *P; \( IF (P != NULL) \( TREEPRINT (P->LEFT); PRINTF("%4D %S\N", P->COUNT, P->WORD); TREEPRINT (P->RIGHT); \) \) Prakticheskoe zamechanie: esli derevo stanovitsya "nesba- lansirovannym" iz-za togo, chto slova postupayut ne v sluchaj- nom poryadke, to vremya raboty programmy mozhet rasti slishkom bystro. V hudshem sluchae, kogda postupayushchie slova uzhe uporya- docheny, nastoyashchaya programma osushchestvlyaet dorogostoyashchuyu imi- taciyu linejnogo poiska. Sushchestvuyut razlichnye obobshcheniya dvo- ichnogo dereva, osobenno 2-3 derev'ya i AVL derev'ya, kotorye ne vedut sebya tak "v hudshih sluchayah", no my ne budem zdes' na nih ostanavlivat'sya. Prezhde chem rasstat'sya s etim primerom, umestno sdelat' nebol'shoe otstuplenie v svyazi s voprosom o raspredelenii pa- myati. YAsno, chto v programme zhelatel'no imet' tol'ko odin raspredelitel' pamyati, dazhe esli emu prihoditsya razmeshchat' razlichnye vidy ob容ktov. No esli my hotim ispol'zovat' odin raspredelitel' pamyati dlya obrabotki zaprosov na vydelenie pamyati dlya ukazatelej na peremennye tipa CHAR i dlya ukazate- lej na STRUCT TNODE, to pri etom voznikayut dva voprosa. Per- vyj: kak vypolnit' to sushchestvuyushchee na bol'shinstve real'nyh mashin ogranichenie, chto ob容kty opredelennyh tipov dolzhny udovletvoryat' trebovaniyam vyravnivaniya (naprimer, chasto ce- lye dolzhny razmeshchat'sya v chetnyh adresah)? Vtoroj: kak orga- nizovat' opisaniya, chtoby spravit'sya s tem, chto funkciya ALLOC dolzhna vozvrashchat' razlichnye vidy ukazatelej ? Voobshche govorya, trebovaniya vyravnivaniya legko vypolnit' za schet vydeleniya nekotorogo lishnego prostranstva, prosto obespechiv to, chtoby raspredelitel' pamyati vsegda vozvrashchal ukazatel', udovletvoryayushchij vsem ogranicheniyam vyravnivaniya. Naprimer, na PDP-11 dostatochno, chtoby funkciya ALLOC vsegda vozvrashchala chetnyj ukazatel', poskol'ku v chetnyj adres mozhno pomestit' lyuboj tip ob容kta. edinstvennyj rashod pri etom - lishnij simvol pri zaprose na nechetnuyu dlinu. Analogichnye dejstviya predprinimayutsya na drugih mashinah. Takim obrazom, realizaciya ALLOC mozhet ne okazat'sya perenosimoj, no ee is- pol'zovanie budet perenosimym. Funkciya ALLOC iz glavy 5 ne predusmatrivaet nikakogo opredelennogo vyravnivaniya; v glave 8 my prodemonstriruem, kak pravil'no vypolnit' etu zadachu. Vopros opisaniya tipa funkcii ALLOC yavlyaetsya muchitel'nym dlya lyubogo yazyka, kotoryj ser'ezno otnositsya k proverke ti- pov. Luchshij sposob v yazyke "C" - ob座avit', chto ALLOC vozvra- shchaet ukazatel' na peremennuyu tipa CHAR, a zatem yavno preob- razovat' etot ukazatel' k zhelaemomu tipu s pomoshch'yu operacii perevoda tipov. Takim obrazom, esli opisat' P v vide CHAR *P; to (STRUCT TNODE *) P preobrazuet ego v vyrazheniyah v ukazatel' na strukturu tipa TNODE . Sledovatel'no, funkciyu TALLOC mozhno zapisat' v vide: STRUCT TNODE *TALLOC() \( CHAR *ALLOC(); RETURN ((STRUCT TNODE *) ALLOC(SIZEOF(STRUCT TNODE))); \) eto bolee chem dostatochno dlya rabotayushchih v nastoyashchee vremya kompilyatorov, no eto i samyj bezopasnyj put' s uchetom buduyu- shchego. Uprazhnenie 6-4 ---------------- Napishite programmu, kotoraya chitaet "C"-programmu i pecha- taet v alfavitnom poryadke kazhduyu gruppu imen peremennyh, ko- torye sovpadayut v pervyh semi simvolah, no otlichayutsya gde-to dal'she. (Sdelajte tak, chtoby 7 bylo parametrom). Uprazhnenie 6-5 ---------------- Napishite programmu vydachi perekrestnyh ssylok, t.e. Programmu, kotoraya pechataet spisok vseh slov dokumenta i dlya kazhdogo iz etih slov pechataet spisok nomerov strok, v koto- rye eto slovo vhodit. Uprazhnenie 6-6 ---------------- Napishite programmu, kotoraya pechataet slova iz svoego fajla vvoda, raspolozhennye v poryadke ubyvaniya chastoty ih po- yavleniya. Pered kazhdym slovom napechatajte chislo ego poyavle- nij. 6.6. Poisk v tablice Dlya illyustracii dal'nejshih aspektov ispol'zovaniya struk- tur v etom razdele my napishem programmu, predstavlyayushchuyu so- boj soderzhimoe paketa poiska v tablice. |ta programma yavlya- etsya tipichnym predstavitelem podprogramm upravleniya simvol'- nymi tablicami makroprocessora ili kompilyatora. Rassmotrim, naprimer, operator #DEFINE yazyka "C". Kogda vstrechaetsya stroka vida #DEFINE YES 1 to imya YES i zamenyayushchij tekst 1 pomeshchayutsya v tablicu. Pozd- nee, kogda imya YES poyavlyaetsya v operatore vida INWORD = YES; Ono dolzhno byt' zameshcheno na 1. Imeyutsya dve osnovnye procedury, kotorye upravlyayut imena- mi i zamenyayushchimi ih tekstami. Funkciya INSTALL(S,T) zapisyva- et imya S i zamenyayushchij tekst T v tablicu; zdes' S i T prosto simvol'nye stroki. Funkciya LOOKUP(S) ishchet imya S v tablice i vozvrashchaet libo ukazatel' togo mesta, gde eto imya najdeno, libo NULL, esli etogo imeni v tablice ne okazalos'. Pri etom ispol'zuetsya poisk po algoritmu heshirovaniya - postupayushchee imya preobrazuetsya v malen'koe polozhitel'noe chis- lo, kotoroe zatem ispol'zuetsya dlya indeksacii massiva ukaza- telej. |lement massiva ukazyvaet na nachalo cepochnyh blokov, opisyvayushchih imena, kotorye imeyut eto znachenie heshirovaniya. Esli nikakie imena pri heshirovanii ne poluchayut etogo znache- niya, to elementom massiva budet NULL. Blokom cepi yavlyaetsya struktura, soderzhashchaya ukazateli na sootvetstvuyushchee imya, na zamenyayushchij tekst i na sleduyushchij blok v cepi. Nulevoj ukazatel' sleduyushchego bloka sluzhit priznakom konca dannoj cepi. STRUCT NLIST \( /* BASIC TABLE ENTRY */ CHAR *NAME; CHAR *DEF; STRUCT NLIST *NEXT; /* NEXT ENTRY IN CHAIN */ \); Massiv ukazatelej eto prosto DEFINE HASHSIZE 100 TATIC STRUCT NLIST *HASHTAB[HASHSIZE] /* POINTER TABLE */ Znachenie funkcii heshirovaniya, ispol'zuemoj obeimi funk- ciyami LOOKUP i INSTALL , poluchaetsya prosto kak ostatok ot deleniya summy simvol'nyh znachenij stroki na razmer massiva. (|to ne samyj luchshij vozmozhnyj algoritm, no ego dostoinstvo sostoit v isklyuchitel'noj prostote). HASH(S) /* FORM HASH VALUE FOR STRING */ CHAR *S; \( INT HASHVAL; FOR (HASHVAL = 0; *S != '\0'; ) HASHVAL += *S++; RETURN(HASHVAL % HASHSIZE); \) V rezul'tate processa heshirovaniya vydaetsya nachal'nyj in- deks v massive HASHTAB ; esli dannaya stroka mozhet byt' gde-to najdena, to imenno v cepi blokov, nachalo kotoroj uka- zano tam. Poisk osushchestvlyaetsya funkciej LOOKUP. Esli funkciya LOOKUP nahodit, chto dannyj element uzhe prisutstvuet, to ona vozvrashchaet ukazatel' na nego; esli net, to ona vozvrashchaet NULL. STRUCT NLIST *LOOKUP(S) /* LOOK FOR S IN HASHTAB */ CHAR *S; \( STRUCT NLIST *NP; FOR (NP = HASHTAB[HASH(S)]; NP != NULL;NP=NP->NEXT) IF (STRCMP(S, NP->NAME) == 0) RETURN(NP); /* FOUND IT */ RETURN(NULL); /* NOT FOUND */ Funkciya INSTALL ispol'zuet funkciyu LOOKUP dlya opredele- niya, ne prisutstvuet li uzhe vvodimoe v dannyj moment imya; esli eto tak, to novoe opredelenie dolzhno vytesnit' staroe. V protivnom sluchae sozdaetsya sovershenno novyj element. Esli po kakoj-libo prichine dlya novogo elementa bol'she net mesta, to funkciya INSTALL vozvrashchaet NULL. STRUCT NLIST *INSTALL(NAME, DEF) /* PUT (NAME, DEF) */ CHAR *NAME, *DEF; \( STRUCT NLIST *NP, *LOOKUP(); CHAR *STRSAVE(), *ALLOC(); INT HASHVAL; IF((NP = LOOKUP(NAME)) == NULL) \( /* NOT FOUND */ NP = (STRUCT NLIST *) ALLOC(SIZEOF(*NP)); IF (NP == NULL) RETURN(NULL); IF ((NP->NAME = STRSAVE(NAME)) == NULL) RETURN(NULL); HASHVAL = HASH(NP->NAME); NP->NEXT = HASHTAB[HASHVAL]; HASHTAB[HASHVAL] = NP; \) ELSE /* ALREADY THERE */ FREE((NP->DEF);/* FREE PREVIOUS DEFINITION */ IF ((NP->DEF = STRSAVE(DEF)) == NULL) RETURN (NULL); RETURN(NP); \) Funkciya STRSAVE prosto kopiruet stroku, ukazannuyu v ka- chestve argumenta, v mesto hraneniya, poluchennoe v rezul'tate obrashcheniya k funkcii ALLOC. My uzhe priveli etu funkciyu v gla- ve 5. Tak kak obrashchenie k funkcii ALLOC i FREE mogut prois- hodit' v lyubom poryadke i v svyazi s problemoj vyravnivaniya, prostoj variant funkcii ALLOC iz glavy 5 nam bol'she ne pod- hodit; smotrite glavy 7 i 8. Uprazhnenie 6-7 --------------- Napishite proceduru, kotoraya budet udalyat' imya i oprede- lenie iz tablicy, upravlyaemoj funkciyami LOOKUP i INSTALL. Uprazhnenie 6-8 --------------- Razrabotajte prostuyu, osnovannuyu na funkciyah etogo raz- dela, versiyu processora dlya obrabotki konstrukcij #DEFINE , prigodnuyu dlya ispol'zovaniya s "C"-programmami. Vam mogut takzhe okazat'sya poleznymi funkcii GETCHAR i UNGETCH. 6.7. Polya Kogda vopros ekonomii pamyati stanovitsya ochen' sushchestven- nym, to mozhet okazat'sya neobhodimym pomeshchat' v odno mashinnoe slovo neskol'ko razlichnyh ob容ktov; odno iz osobenno rasp- rosranennyh upotreblenij - nabor odnobitovyh priznakov v primeneniyah, podobnyh simvol'nym tablicam kompilyatora. vnesh- ne obuslovlennye formaty dannyh, takie kak interfejsy appa- ratnyh sredstv takzhe zachastuyu predpolagayut vozmozhnost' polu- cheniya slova po chastyam. Predstav'te sebe fragment kompilyatora, kotoryj rabotaet s simvol'noj tablicej. S kazhdym identifikatorom programmy svyazana opredelennaya informaciya, naprimer, yavlyaetsya on ili net klyuchevym slovom, yavlyaetsya li on ili net vneshnim i/ili staticheskim i t.d. Samyj kompaktnyj sposob zakodirovat' ta- kuyu informaciyu - pomestit' nabor odnobitovyh priznakov v ot- del'nuyu peremennuyu tipa CHAR ili INT. Obychnyj sposob, kotorym eto delaetsya, sostoit v oprede- lenii nabora "masok", otvechayushchih sootvetstvushchim bitovym po- ziciyam, kak v #DEFINE KEYWORD 01 #DEFINE EXTERNAL 02 #DEFINE STATIC 04 (chisla dolzhny byt' stepenyami dvojki). Togda obrabotka bitov svedetsya k "zhonglirovaniyu bitami" s pomoshch'yu operacij sdviga, maskirovaniya i dopolneniya, opisannyh nami v glave 2. Nekotorye chasto vstrechayushchiesya idiomy: FLAGS \!= EXTERNAL \! STATIC; vklyuchaet bity EXTERNAL i STATIC v FLAGS, v to vremya kak FLAGS &= \^(eXTERNAL \! STATIC); ih vyklyuchaet, a IF ((FLAGS & (EXTERNAL \! STATIC)) == 0) ... istinno, esli oba bita vyklyucheny. Hotya etimi idiomami legko ovladet', yazyk "C" v kachestve al'ternativy predlagaet vozmozhnost' opredeleniya i obrabotki polej vnutri slova neposredstvenno, a ne posredstvom pobito- vyh logicheskih operacij. Pole - eto nabor smezhnyh bitov vnutri odnoj peremennoj tipa INT. Sintaksis opredeleniya i obrabotki polej osnovyvaetsya na strukturah. Naprimer, sim- vol'nuyu tablicu konstrukcij #DEFINE, privedennuyu vyshe, mozhno by bylo zamenit' opredeleniem treh polej: STRUCT \( UNSIGNED IS_KEYWORD : 1; UNSIGNED IS_EXTERN : 1; UNSIGNED IS_STATIC : 1; \) FLAGS; Zdes' opredelyaetsya peremennaya s imenem FLAGS, kotoraya soder- zhit tri 1-bitovyh polya. Sleduyushchee za dvoetochiem chislo zadaet shirinu polya v bitah. Polya opisany kak UNSIGNED, chtoby pod- cherknut', chto oni dejstvitel'no budut velichinami bez znaka. Na otdel'nye polya mozhno ssylat'sya, kak FLAGS.IS_STATIE, FLAGS. IS_EXTERN, FLAGS.IS_KEYWORD I t.d., to est' tochno tak zhe, kak na drugie chleny struktury. Polya vedut sebya podobno nebol'shim celym bez znaka i mogut uchastvovat' v arifmetiches- kih vyrazheniyah tochno tak zhe, kak i drugie celye. Takim obra- zom, predydushchie primery bolee estestvenno perepisat' tak: FLAGS.IS_EXTERN = FLAGS.IS_STATIC = 1; dlya vklyucheniya bitov; FLAGS.IS_EXTERN = FLAGS.IS_STATIC = 0; dlya vyklyucheniya bitov; IF (FLAGS.IS_EXTERN == 0 &&FLAGS.IS_STATIC == 0)... dlya ih proverki. Pole ne mozhet perekryvat' granicu INT; esli ukazannaya shirina takova, chto eto dolzhno sluchit'sya, to pole vyravniva- etsya po granice sleduyushchego INT. Polyam mozhno ne prisvaivat' imena; neimenovannye polya (tol'ko dvoetochie i shirina) is- pol'zuyutsya dlya zapolneniya svobodnogo mesta. CHtoby vynudit' vyravnivanie na granicu sleduyushchego INT, mozhno ispol'zovat' special'n