|
|_c__\0
|_x__\0
potrebuetsya prohod vpravo (vniz) na 10 shagov, potom vybor sredi 'a','b','c', potom -
vybor sredi '\0' i 'x'. Vsego: 15 shagov. Za schet togo, chto obshchij "koren'" prohoditsya
rovno odin raz, a ne kazhdyj raz zanovo. No eto i trebuet predvaritel'noj podgotovki
dannyh: prevrashcheniya strok v derevo!
8.18. Napishite funkciyu dlya "ekrannogo" redaktirovaniya vvodimoj stroki v rezhime
CBREAK. Napishite analogichnuyu funkciyu na curses-e. V curses-noj versii nado umet'
otrabatyvat': zaboj (udalenie simvola pered kursorom), otmenu vsej stroki, smeshchenie
vlevo/vpravo po stroke, udalenie simvola nad kursorom, vstavku probela nad kursorom,
zamenu simvola, vstavku simvola, pererisovku ekrana. Uchtite, chto parallel'no s izme-
neniem kartinki v okne, vy dolzhny vnosit' izmeneniya v nekotoryj massiv (stroku),
kotoraya i budet soderzhat' rezul'tat. |ta stroka dolzhna byt' argumentom funkcii redak-
tirovaniya.
Zaboj mozhno uproshchenno emulirovat' kak
addstr( "\b \b" );
ili
addch( '\b' ); delch();
Nedostatkom etih sposobov yavlyaetsya nekorrektnoe povedenie v nachale stroki (pri x==0).
Isprav'te eto!
8.19. Na curses-e napishite funkciyu redaktirovaniya teksta v okne. Funkciya dolzhna
vozvrashchat' massiv strok s obrezannymi koncevymi probelami. Variant: vozvrashchat' odnu
stroku, v kotoroj stroki okna razdelyayutsya simvolami '\n'.
8.20. Napishite funkciyu, risuyushchuyu pryamuyu liniyu iz tochki (x1,y1) v (x2,y2). Ukazanie:
ispol'zujte algoritm Brezenhema (minimal'nogo otkloneniya). Otvet: pust' funkciya
putpixel(x,y,color) risuet tochku v koordinatah (x,y) cvetom color.
void line(int x1, int y1, int x2, int y2,
int color){
int dx, dy, i1, i2, i, kx, ky;
register int d; /* "otklonenie" */
register int x, y;
short /* boolean */ l;
A. Bogatyrev, 1992-95 - 387 - Si v UNIX
dy = y2 - y1; dx = x2 - x1;
if( !dx && !dy ){
putpixel(x1,y1, color); return;
}
kx = 1; /* shag po x */
ky = 1; /* shag po y */
/* Vybor taktovoj osi */
if( dx < 0 ){ dx = -dx; kx = -1; } /* Y */
else if( dx == 0 ) kx = 0; /* X */
if( dy < 0 ){ dy = -dy; ky = -1; }
if( dx < dy ){ l = 0; d = dx; dx = dy; dy = d; }
else l = 1;
i1 = dy + dy; d = i1 - dx; i2 = d - dx;
x = x1; y = y1;
for( i=0; i < dx; i++ ){
putpixel( x, y, color );
if( l ) x += kx; /* shag po takt. osi */
else y += ky;
if( d < 0 ) /* gorizontal'nyj shag */
d += i1;
else{ /* diagonal'nyj shag */
d += i2;
if( l ) y += ky; /* prirost vysoty */
else x += kx;
}
}
putpixel(x, y, color); /* poslednyaya tochka */
}
8.21. Sostav'te programmu, kotoraya stroit grafik funkcii sin(x) na otrezke ot 0 do
2*pi. Uchtite takie veshchi: sosednie tochki grafika sleduet soedinyat' otrezkom pryamoj,
chtoby grafik vyglyadel nepreryvnym; ne zabyvajte privodit' double k int, t.k. koordi-
naty pikselov|- - celye chisla.
8.22. Napishite funkciyu, kotoraya zapolnyaet v massive bajt count bit podryad, nachinaya s
x-ogo bita ot levogo kraya massiva:
bajt 0 | bajt 1
7 6 5 4 3 2 1 0 | 7 6 5 4 3 2 1 0 : bity v bajte
0 1 2 3 4 5 6 7 | 8 9 10 11 12 13 14 15 : x
==========================
x=2, count=11
Takoj algoritm ispol'zuetsya v rastrovoj mashinnoj grafike dlya risovaniya gorizontal'nyh
pryamyh linij (togda massiv - eto videopamyat' komp'yutera, kazhdyj bit sootvetstvuet
pikselu na ekrane).
Otvet (prichem my zapolnyaem bity ne prosto edinicami, a "uzorom" pattern):
void horizLine(char *addr,int x,int count,char pattern){
static char masks[8] = {
0xFF, 0x7F, 0x3F, 0x1F, 0x0F, 0x07, 0x03, 0x01 };
/* indeks v etom massive raven chislu 0-bitov sleva */
____________________
|- Piksel (pixel, pel) - picture element, v mashinnoj grafike - tochka rastra na ek-
rane.
A. Bogatyrev, 1992-95 - 388 - Si v UNIX
register i;
char mask;
short lbits, rbits; /* chislo bitov sleva i sprava */
short onebyte; /* edinstvennyj bajt ? */
addr += x/8; /* v bajte 8 bit */
mask = masks[ lbits = x & 7 ]; /* x % 8 */
if( count >= (rbits = 8 - lbits)){
count -= rbits; onebyte = 0;
}else{
mask &= ~masks[ lbits = (x+count) & 7 ];
onebyte = 1;
}
/* Pervyj bajt */
*addr = (*addr & ~mask) | (pattern & mask);
addr++;
/* Dlya pattern==0xFF mozhno prosto
* *addr++ |= mask;
* poskol'ku (a &~m)|(0xFF & m) = (a &~m) | m =
* (a|m) & (~m|m) = (a|m) & 0xFF = a | m
* Pochemu zdes' nel'zya napisat' *addr++ = (*addr...) ?
* Potomu, chto ++ mozhet byt' sdelan DO vychisleniya
* pravoj chasti prisvaivaniya!
*/
if(onebyte) return;
/* Srednie bajty */
for(i = count/8; i > 0; --i)
*addr++ = pattern; /* mask==0xFF */
/* Poslednij bajt */
if((lbits = count & 7) == 0) return;
/* poslednij bajt byl polnym */
mask = ~masks[lbits];
*addr = (*addr & ~mask) | (pattern & mask);
}
Zametim, chto dlya bystrodejstviya podobnye algoritmy obychno pishutsya na assemblere.
8.23. Napishite pri pomoshchi curses-a "elektronnye chasy", otobrazhayushchie tekushchee vremya
bol'shimi ciframi (naprimer, razmerom 8x8 obychnyh simvolov) kazhdye 5 sekund. Ispol'-
zujte alarm(), pause().
8.24. Sostav'te programmu, realizuyushchuyu prostoj dialogovyj interfejs, osnovannyj na
menyu. Menyu hranyatsya v tekstovyh fajlah vida:
A. Bogatyrev, 1992-95 - 389 - Si v UNIX
fajl menu2_12
-----------------------------------------------
ZAGOLOVOK_MENYU
+komanda_vypolnyaemaya_pri_vhode_v_menyu
-komanda_vypolnyaemaya_pri_vyhode_iz_menyu
al'ternativa_1
komanda1_1
komanda1_2
al'ternativa_2
komanda2_1
komanda2_2 #kommentarij
komanda2_3
al'ternativa_3
>menu2_2 #eto perehod v drugoe menyu
al'ternativa_4
>>menu3_7 #hranimoe v fajle menu3_7
...
...
-----------------------------------------------
Programma dolzhna obespechivat': vozvrat k predydushchemu menyu po klavishe Esc (dlya etogo
sleduet hranit' "istoriyu" vyzovov menyu drug iz druga, naprimer v vide "polnogo imeni
menyu":
.rootmenu.menu1_2.menu2_4.menu3_1
gde menuI_J - imena fajlov s menyu), obespechit' vyhod iz programmy po klavisham 'q' i
ESC, vydachu podskazki po F1, vydachu polnogo imeni menyu po F2. Vyzov menyu pri pomoshchi
> oznachaet zameshchenie tekushchego menyu novym, chto sootvetstvuet zamene poslednej kompo-
nenty v polnom imeni menyu. Vyzov >> oznachaet vyzov menyu kak funkcii, t.e. posle
vybora v novom menyu i vypolneniya nuzhnyh dejstvij avtomaticheski dolzhno byt' vydano to
menyu, iz kotorogo proizoshel vyzov (takoj vyzov sootvetstvuet udlineniyu polnogo imeni,
a vozvrat iz vyzova - otsecheniyu poslednej komponenty). |tot vyzov mozhet byt' pokazan
na ekrane kak poyavlenie novogo "vyskakivayushchego" okna poverh okna s predydushchim menyu
(okno voznikaet chut' sdvinutym - skazhem, na y=1 i x=-2), a vozvrat - kak ischeznovenie
etogo okna. Zagolovok menyu dolzhen vysvechivat'sya v verhnej stroke menyu:
|-------------------
|--ZAGOLOVOK_MENYU---- |
| al'ternativa_1 | |
| al'ternativa_2 | |
| *al'ternativa_3 | |
| al'ternativa_4 |--
---------------------
Snachala realizujte versiyu, v kotoroj kazhdoj "al'ternative" sootvetstvuet edinstvennaya
stroka "komanda". Komandy sleduet zapuskat' pri pomoshchi standartnoj funkcii
system(komanda).
Uslozhnite funkciyu vybora v menyu tak, chtoby al'ternativy mozhno bylo vybirat' po
pervoj bukve pri pomoshchi nazhatiya knopki s etoj bukvoj (v lyubom registre):
Compile
Edit
Run program
8.25. Napishite na curses-e funkciyu, realizuyushchuyu vybor v menyu - pryamougol'noj tab-
lice:
A. Bogatyrev, 1992-95 - 390 - Si v UNIX
slovo1 slovo4 slovo7
slovo2 *slovo5 slovo8
slovo3 slovo6
Stroki - elementy menyu - peredayutsya v funkciyu vybora v vide massiva strok. CHislo
elementov menyu zaranee neizvestno i dolzhno podschityvat'sya vnutri funkcii. Uchtite,
chto vse stroki mogut ne pomestit'sya v tablice, poetomu nado predusmotret' "prokruchi-
vanie" strok cherez tablicu pri dostizhenii kraya menyu (t.e. tablica sluzhit kak by
"okoshkom" cherez kotoroe my obozrevaem tablicu bol'shego razmera, vozmozhno peremeshchaya
okno nad nej). Predusmotrite takzhe sluchaj, kogda tablica okazyvaetsya zapolnennoj ne
polnost'yu (kak na risunke).
8.26. Ispol'zuya biblioteku curses, napishite programmu, realizuyushchuyu kletochnyj avtomat
Konveya "ZHizn'". Pravila: est' pryamougol'noe pole (voobshche govorya beskonechnoe, no pri-
nyato v konechnoj modeli zamykat' kraya v kol'co), v kotorom zhivut "kletki" nekotorogo
organizma. Kazhdaya imeet 8 sosednih polej. Sleduyushchee pokolenie "kletok" obrazuetsya po
takim pravilam:
- esli "kletka" imeet 2 ili 3 sosedej - ona vyzhivaet.
- esli "kletka" imeet men'she 2 ili bol'she 3 sosedej - ona pogibaet.
- v pustom pole, imeyushchem rovno 3h zhivyh sosedej, rozhdaetsya novaya "kletka".
Predusmotrite: redaktirovanie polya, sluchajnoe zapolnenie polya, ostanov pri smerti
vseh "kletok", ostanov pri stabilizacii kolonii.
8.27. Pri pomoshchi curses-a napishite ekrannyj redaktor kodov dostupa k fajlu (v forme
rwxrwxrwx). Rasshir'te programmu, pozvolyaya redaktirovat' kody dostupa u gruppy faj-
lov, izobrazhaya imena fajlov i kody dostupa v vide tablicy:
NAZVANIE KODY DOSTUPA
fajl1 rwxrw-r--
fajl2 rw-r-xr-x
fajl3 rwxrwxr--
Imena fajlov zadavajte kak argumenty dlya main(). Ukazanie: ispol'zujte dlya polucheniya
tekushchih kodov dostupa sistemnyj vyzov stat(), a dlya ih izmeneniya - sistemnyj vyzov
chmod().
A. Bogatyrev, 1992-95 - 391 - Si v UNIX
* 9. Prilozheniya. *
9.1. Tablica prioritetov operacij yazyka C++
Operacii, raspolozhennye vyshe, imeyut bol'shij prioritet.
Operatory Associativnost'
--------------------------------------------------
1. () [] -> :: . Left to right
2. ! ~ + - ++ -- & *
(typecast) sizeof new delete Right to left
3. .* ->* Left to right
4. * / % Left to right
5. + - Left to right
6. << >> Left to right
7. < <= > >= Left to right
8. == != Left to right
9. & Left to right
10. ^ Left to right
11. | Left to right
12. && Left to right
13. || Left to right
14. ?: (uslovnoe vyrazhenie) Right to left
15. = *= /= %= += -= &=
^= |= <<= >>= Right to left
16. , Left to right
Zdes' "*" i "&" v stroke 2 - eto adresnye operacii; v stroke 2 "+" i "-" - unarnye;
"&" v stroke 9 - eto pobitnoe "i"; "(typecast)" - privedenie tipa; "new" i "delete" -
operatory upravleniya pamyat'yu v C++.
Associativnost' Left to right (sleva napravo) oznachaet gruppirovku operatorov
takim obrazom:
A1 @ A2 @ A3 eto
((A1 @ A2) @ A3)
Associativnost' Rigth to left (sprava nalevo) eto
A1 @ A2 @ A3 eto
(A1 @ (A2 @ A3))
9.2. Pravila preobrazovanij tipov.
9.2.1. V vyrazheniyah.
1. Esli operand imeet tip ne int i ne double, to snachala privoditsya:
signed char --> int rasshireniem znakovogo bita (7)
unsigned char --> int dopolneniem nulyami sleva
short --> int rasshireniem znakovogo bita (15)
unsigned short --> unsigned int dopolneniem nulyami sleva
enum --> int poryadkovyj nomer v perechislimom tipe
float --> double drobnaya chast' dopolnyaetsya nulyami
2. Esli lyuboj operand imeet tip double, to i drugoj operand privoditsya k tipu dou-
ble. Rezul'tat: tipa double. Zapishem vse dal'nejshie preobrazovaniya v vide shemy:
A. Bogatyrev, 1992-95 - 392 - Si v UNIX
esli est' to drugoj rezul'tat
operand tipa privoditsya k tipu imeet tip
if(double) -->double double
else if(unsigned long) -->unsigned long unsigned long
else if(long) -->long long
else if(unsigned int) -->unsigned int unsigned int
else oba operanda imeyut tip int int
Pri vyzove funkcij ih argumenty - tozhe vyrazheniya, poetomu v nih privodyatsya char,short
k int i float k double. |to govorit o tom, chto argumenty (formal'nye parametry) funk-
cij mozhno vsegda ob®yavlyat' kak int i double vmesto char,short i float sootvetstvenno.
Zato specifikator unsigned yavlyaetsya sushchestvennym.
9.2.2. V prisvaivaniyah.
op = expr;
Tip vyrazheniya expr privoditsya k tipu levoj chasti - op. Pri etom vozmozhny privedeniya
bolee "dlinnogo" tipa k bolee "korotkomu" pri pomoshchi usecheniya, vrode:
int --> char obrubaetsya starshij bajt.
long --> int obrubaetsya starshee slovo.
float --> int otbros drobnoj chasti
double --> int i obrubanie mantissy, esli ne lezet.
double --> float okruglenie drobnoj chasti.
Vot eshche nekotorye privedeniya tipov:
signed --> unsigned virtual'no (prosto znakovyj bit
unsigned --> signed schitaetsya znachashchim ili naoborot).
unsigned int --> long dobavlenie nulej sleva.
int --> long rasshirenie znakovogo bita.
float --> int preobrazovanie vnutrennego
int --> float predstavleniya: mashinno zavisimo.
Nekotorye preobrazovaniya mogut idti v neskol'ko stadij, naprimer:
char --> long eto
char --> int --> long
char --> unsigned long eto
char --> int --> unsigned long
9.3. Tablica shestnadcaterichnyh chisel (HEX).
%d %o %X pobitno
--------------------------------
0 0 0x0 0000
1 1 0x1 0001
2 2 0x2 0010
3 3 0x3 0011
4 4 0x4 0100
5 5 0x5 0101
6 6 0x6 0110
7 7 0x7 0111
A. Bogatyrev, 1992-95 - 393 - Si v UNIX
--------------------------------
8 010 0x8 1000
9 011 0x9 1001
10 012 0xA 1010
11 013 0xB 1011
12 014 0xC 1100
13 015 0xD 1101
14 016 0xE 1110
15 017 0xF 1111
16 020 0x10 10000
9.4. Tablica stepenej dvojki.
n 2**n | n 2**n
--------------|---------------
0 1 | 8 256
1 2 | 9 512
2 4 | 10 1024
3 8 | 11 2048
4 16 | 12 4096
5 32 | 13 8192
6 64 | 14 16384
7 128 | 15 32768
| 16 65536
9.5. Dvoichnyj kod: vnutrennee predstavlenie celyh chisel.
Celye chisla v bol'shinstve sovremennyh komp'yuterov predstavleny v vide dvoichnogo
koda. Pust' mashinnoe slovo sostoit iz 16 bit. Bity numeruyutsya sprava nalevo nachinaya
s 0. Oboznachim uslovno bit nomer i cherez b[i]. Znacheniem ego mozhet byt' libo 0, libo
1.
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 0| 0| 0| 0| 1| 0| 1| 1| 0| 1| 1| 0| 1| 1| 0| 0|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
Togda unsigned chislo, zapisannoe v slove, ravno
d = 2**15 * b[15] +
2**14 * b[14] +
...
2**1 * b[1] +
b[0];
(2**n - eto 2 v stepeni n). Takoe razlozhenie chisla d edinstvenno. Pri slozhenii dvuh
chisel bity skladyvayutsya po pravilam:
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0 i perenos 1 v razryad sleva
CHisla so znakom interpretiruyutsya chut' inache. Bit b[15] schitaetsya znakovym: 0 - chislo
polozhitel'no ili ravno nulyu, 1 - otricatel'no. Otricatel'nye chisla hranyatsya v vide
dopolnitel'nogo koda:
-a = ~a + 1
Naprimer:
A. Bogatyrev, 1992-95 - 394 - Si v UNIX
2 = 0000000000000010
~2 = 1111111111111101
~2+1 = 1111111111111110 = -2
-1 = 1111111111111111
-2 = 1111111111111110
-3 = 1111111111111101
-4 = 1111111111111100
-5 = 1111111111111011
Takoe predstavlenie vybrano ishodya iz pravila
a + (-a) = 0
znak|
2 = 0|000000000000010 slozhim ih
-2 = 1|111111111111110
---------|---------------
summa: 10|000000000000000
Kak vidim, proizoshel perenos 1 v bit nomer 16. No slovo soderzhit lish' bity 0..15 i
bit b[16] prosto ignoriruetsya. Poluchaetsya, chto summa ravna
0000000000000000 = 0
chto i trebovalos'. V dvoichnom kode vychitanie realizuetsya po sheme
a - b = a + (-b) = a + (~b + 1)
Vos'merichnye chisla sootvetstvuyut razbieniyu dvoichnogo chisla na gruppy po 3 bita i
zapisi kazhdoj gruppy v vide sootvetstvuyushchej vos'merichnoj cifry (smotri tablicu vyshe).
SHestnadcaterichnye chisla sootvetstvuyut razbieniyu na gruppy po 4 bita (nibble):
x = 0010011111011001
chislo: 0010 0111 1101 1001
16-richnoe: 0x 2 7 D 9 = 0x27D9
chislo: 0 010 011 111 011 001
8-richnoe: 0 0 2 3 7 3 1 = 023731
10. Primery.
V dannom prilozhenii privoditsya neskol'ko soderzhatel'nyh i dostatochno bol'shih
primerov, kotorye illyustriruyut kak sam yazyk Si, tak i nekotorye vozmozhnosti sistemy
UNIX, a takzhe nekotorye programmistskie priemy resheniya zadach pri pomoshchi Si. Mnogie
iz etih primerov soderzhat v kachestve svoih chastej otvety na nekotorye iz zadach.
Nekotorye primery pozaimstvovany iz drugih knig, no dopolneny i ispravleny. Vse pri-
mery provereny v dejstvii. Smysl nekotoryh funkcij v primerah mozhet okazat'sya vam
neizvesten; odnako v silu togo, chto dannaya kniga ne yavlyaetsya uchebnikom, my otsylaem
vas za podrobnostyami k "Operativnomu rukovodstvu" (man) po operacionnoj sisteme UNIX
i k dokumentacii po sisteme.
I v zaklyuchenie - neskol'ko slov o putyah razvitiya yazyka "C". CHistyj yazyk "C" uzhe
otstal ot sovremennyh tehnologij programmirovaniya. Takie metody kak moduli (yazyki
"Modula-2", "Ada", "CLU"), rodovye pakety ("Ada", "CLU"), ob®ektno-orientirovannoe
programmirovanie ("Smalltalk", "CLU") trebuyut novyh sredstv. Poetomu v nastoyashchee
vremya "C" postepenno vytesnyaetsya bolee moshchnym i intellektual'nym yazykom "C++" |-,
obladayushchim sredstvami dlya ob®ektno-orientirovannogo programmirovaniya i rodovyh
____________________
|- C++ kak i C razrabotan v AT&T; proiznositsya "Si plas-plas"
A. Bogatyrev, 1992-95 - 395 - Si v UNIX
klassov. Sushchestvuyut takzhe rasshireniya standartnogo "C" ob®ektno-orientirovannymi voz-
mozhnostyami ("Objective-C"). Bol'shoj prostor predostavlyaet takzhe sborka programm iz
chastej, napisannyh na raznyh yazykah programmirovaniya (naprimer, "C", "Pascal", "Pro-
log").
____________________
|=|=|= Avtor blagodarit avtorov programm i knig po Si i UNIX, po kotorym nekogda
uchilsya ya sam; kolleg iz IPK Minavtoproma/Demosa; programmistov iz setej Usenet i Rel-
com, davshih materialy dlya zadach i rassuzhdenij; slushatelej kursov po Si za mnogochis-
lennyj material dlya knigi.
A.Bogatyrev.
Uchen'yu ne odin my posvyatili god,
Potom drugih uchit' prishel i nam chered.
Kakie zh vyvody iz etoj vsej nauki?
Iz praha my prishli, nas veter uneset.
Omar Hajyam
Oglavlenie.
0. Naputstvie v kachestve vstupleniya. .......................................... 1
1. Prostye programmy i algoritmy. Syurprizy, sovety. ........................... 3
2. Massivy, stroki, ukazateli. ................................................ 81
3. Mobil'nost' i mashinnaya zavisimost' programm. Problemy s russkimi bukvami.
........................................................................... 122
4. Rabota s fajlami. .......................................................... 137
5. Struktury dannyh. .......................................................... 172
6. Sistemnye vyzovy i vzaimodejstvie s UNIX. .................................. 186
6.1. Fajly i katalogi. ........................................................ 189
6.2. Vremya v UNIX. ............................................................ 198
6.3. Svobodnoe mesto na diske. ................................................ 207
6.4. Signaly. ................................................................. 212
6.5. ZHizn' processov. ......................................................... 219
6.6. Truby i FIFO-fajly. ...................................................... 230
6.7. Nelokal'nyj perehod. ..................................................... 233
6.8. Hozyain fajla, processa, i proverka privelegij. ........................... 235
6.9. Blokirovka dostupa k fajlam. ............................................. 240
6.10. Fajly ustrojstv. ........................................................ 244
6.11. Mul'tipleksirovanie vvoda-vyvoda ......................................... 259
6.12. Prostoj interpretator komand. ........................................... 271
7. Tekstovaya obrabotka. ....................................................... 283
8. |krannye biblioteki i rabota s videopamyat'yu. ............................... 348
9. Prilozheniya. ................................................................ 391
9.1. Tablica prioritetov operacij yazyka C++ .................................... 391
9.2. Pravila preobrazovanij tipov. ............................................ 391
9.3. Tablica shestnadcaterichnyh chisel (HEX). ................................... 392
9.4. Tablica stepenej dvojki. ................................................. 393
9.5. Dvoichnyj kod: vnutrennee predstavlenie celyh chisel. ...................... 393
10. Primery. .................................................................. 394
Primer 1. Razmen monet. ......................................................
Primer 2. Podschet bukv v fajle. ..............................................
Primer 3. Centrirovanie strok. ...............................................
Primer 4. Razmetka teksta dlya nroff. .........................................
Primer 5. Invertirovanie poryadka slov v strokah. .............................
Primer 6. Puzyr'kovaya sortirovka. ............................................
Primer 7. Hesh-tablica. .......................................................
Primer 8. Prostaya baza dannyh. ...............................................
Primer 9. Vstavka/udalenie strok v fajl. .....................................
Primer 10. Bezopasnyj free, pozvolyayushchij obrashcheniya k avtomaticheskim peremen-
nym. .....................................................................
Primer 11. Poimka oshibok pri rabote s dinamicheskoj pamyat'yu. ..................
Primer 12. Kopirovanie/peremeshchenie fajla. ....................................
Primer 13. Obhod poddereva katalogov v MS DOS pri pomoshchi chdir. ..............
Primer 14. Rabota s signalami. ...............................................
Primer 15. Upravlenie skorost'yu obmena cherez liniyu. ..........................
Primer 16. Prosmotr fajlov v oknah. ..........................................
Primer 17. Rabota s ierarhiej okon v curses. CHast' proekta uxcom. ............
Primer 18. Podderzhka soderzhimogo kataloga. CHast' proekta uxcom. ..............
Primer 19. Rolliruemoe menyu. CHast' proekta uxcom. ............................
Primer 20. Vybor v stroke-menyu. CHast' proekta uxcom. .........................
Primer 21. Redaktor stroki. CHast' proekta uxcom. .............................
Primer 22. Vybor v pryamougol'noj tablice. CHast' proekta uxcom. ...............
Primer 23. UNIX commander - prostoj vizual'nyj SHell. Golovnoj modul' proekta
uxcom. ...................................................................
Primer 24. Obshchenie dvuh processov cherez "trubu". .............................
Primer 25. Obshchenie processov cherez FIFO-fajl. ................................
Primer 26. Obshchenie processov cherez obshchuyu pamyat' i semafory. ..................
Primer 27. Protokolirovanie raboty programmy pri pomoshchi psevdoterminala i
processov. ...............................................................
Primer 28. Ocenka fragmentirovannosti fajlovoj sistemy. ......................
Primer 29. Vosstanovlenie udalennogo fajla v BSD-2.9. ........................
Primer 30. Kopirovanie fajlov iz MS DOS v UNIX. ..............................
Primer 31. Programma, pechatayushchaya svoj sobstvennyj tekst. .....................
Primer 32. Formatirovanie teksta Si-programmy. ...............................
1.11. Treugol'nik iz zvezdochek. ............................................... 6
1.34. Prostye chisla. .......................................................... 10
1.36. Celochislennyj kvadratnyj koren'. ........................................ 12
1.39. Vychislenie integrala po Simpsonu. ....................................... 14
1.49. Sortirovka SHella. ....................................................... 20
1.50. Bystraya sortirovka. ..................................................... 21
1.67. Funkciya chteniya stroki. .................................................. 28
1.88. Perestanovki elementov. ................................................. 38
1.117. Shema Gornera. ......................................................... 58
1.137. Sistemnaya funkciya qsort - format vyzova. ............................... 67
1.146. Process kompilyacii programm. ........................................... 76
2.58. Funkciya bcopy. .......................................................... 108
2.59. Funkciya strdup. ......................................................... 111
2.61. Uproshchennyj analog funkcii printf. ....................................... 112
3.9. _ctype[] .................................................................. 126
3.12. Programma transliteracii: tr. ........................................... 129
3.16. Funkciya zapisi trassirovki (otladochnyh vydach) v fajl. ................... 132
3.18. Uslovnaya kompilyaciya: #ifdef .............................................. 132
4.39. Bystryj dostup k strokam fajla. ......................................... 161
4.45. |mulyaciya osnov biblioteki STDIO, po motivam 4.2 BSD. .................... 165
5.12. Otsortirovannyj spisok slov. ............................................ 180
5.16. Struktury s polyami peremennogo razmera. ................................. 183
5.17. Spisok so "stareniem". .................................................. 184
6.1.1. Opredelenie tipa fajla. ................................................ 189
6.1.3. Vydacha neotsortirovannogo soderzhimogo kataloga (ls). ................... 191
6.1.5. Rekursivnyj obhod katalogov i podkatalogov. ............................ 192
6.2.9. Funkciya zaderzhki v mikrosekundah. ...................................... 201
6.4.3. Funkciya sleep. ......................................................... 217
6.10.1. Opredelenie tekushchego kataloga: funkciya getwd. ......................... 252
6.10.2. Kanonizaciya polnogo imeni fajla. ...................................... 257
6.11.1. Mul'tipleksirovanie vvoda iz neskol'kih fajlov. ....................... 259
6.11.2. Programma script. ..................................................... 261
7.12. Programma uniq. ......................................................... 285
7.14. Rasshirenie tabulyacij v probely, funkciya untab. .......................... 285
7.15. Funkciya tabify. ......................................................... 285
7.25. Poisk metodom polovinnogo deleniya. ...................................... 288
7.31. Programma pechati v dve polosy. .......................................... 292
7.33. Invertirovanie poryadka strok v fajle. ................................... 296
7.34. Perenos nerazbivaemyh blokov teksta. .................................... 298
7.36. Dvoichnaya sortirovka strok pri pomoshchi dereva. ............................ 300
7.41. Funkciya match. .......................................................... 309
7.43. Funkciya kontekstnoj zameny po regulyarnomu vyrazheniyu. .................... 313
7.44. Algoritm bystrogo poiska podstroki v stroke. ............................ 316
7.52. Korrekciya pravopisaniya. ................................................. 321
7.67. Kal'kulyator-1. .......................................................... 330
7.68. Kal'kulyator-2. .......................................................... 336
8.1. Osypayushchiesya bukvy. ....................................................... 350
8.13. Ispol'zovanie biblioteki termcap. ....................................... 359
8.17. Razbor ESC-posledovatel'nostej s klaviatury. ............................ 371
11. Spisok literatury.
1) B.Kernigan, D.Ritchi, A.F'yuer. YAzyk programmirovaniya Si. Zadachi po yazyku Si. -
M.: Finansy i statistika, 1985.
2) M.Uejt, S.Prata, D.Martin. YAzyk Si. Rukovodstvo dlya nachinayushchih. - M.: Mir,
1988.
3) M.Bolski. YAzyk programmirovaniya Si. Spravochnik. - M.: Radio i svyaz', 1988.
4) L.Henkok, M.Kriger. Vvedenie v programmirovanie na yazyke Si. - M.: Radio i
svyaz', 1986.
5) M.Dansmur, G.Dejvis. OS UNIX i programmirovanie na yazyke Si. - M.: Radio i
svyaz', 1989.
6) R.Berri, B.Mikinz. YAzyk Si. Vvedenie dlya programmistov. - M.: Finansy i sta-
tistika, 1988.
7) M.Belyakov, A.Liverovskij, V.Semik, V.SHyaudkulis. Instrumental'naya mobil'naya ope-
racionnaya sistema INMOS. - M.: Finansy i statistika, 1985.
8) K.Kristian. Vvedenie v operacionnuyu sistemu UNIX. - M.: Finansy i statistika,
1985.
9) R.Got'e. Rukovodstvo po operacionnoj sisteme UNIX. - M.: Finansy i statistika,
1986.
10) M.Banahan, |.Ratter. Vvedenie v operacionnuyu sistemu UNIX. - M.: Radio i
svyaz', 1986.
11) S.Baurn. Operacionnaya sistema UNIX. - M.: Mir, 1986.
12) P.Braun. Vvedenie v operacionnuyu sistemu UNIX. - M.: Mir, 1987.
13) M.Bach. The design of the UNIX operating system. - Prentice Hall, Englewood
Cliffs, N.J., 1986.
14) S.Dewhurst, K.Stark. Programming in C++. - Prentice Hall, 1989.
15) M.Ellis, B.Stroustrup. The annotated C++ Reference Manual. - Addison-Wesley,
1990.
/* Primer 1 */
/* Zadacha o razmene monety:
* Poisk vseh vozmozhnyh koefficientov a0 .. an razlozheniya chisla S
* v vide
* S = a0 * c0 + a1 * c1 + ... + an * cn
* gde vesa c0 .. cn zadany zaranee i uporyadocheny.
* Vesa i koefficienty neotricatel'ny (ai >= 0, ci >= 0).
*/
#include <stdio.h>
/* Dostoinstva razmennyh monet (vesa ci) */
int cost[] = {
1, 2, 3, 5, 10, 15, 20, 50, 100, 300, 500 /* kopeek */
};
#define N (sizeof cost / sizeof(int))
int count[ N ]; /* chislo monet dannogo tipa (koefficienty ai) */
long nvar; /* chislo variantov */
main( ac, av ) char *av[];
{
int coin;
if( ac == 1 ){
fprintf( stderr, "Ukazhite, kakuyu monetu razmenivat': %s chislo\n",
av[0] );
exit(1);
}
coin = atoi( av[1] );
printf( " Tablica razmenov monety %d kop.\n", coin );
printf( " Kazhdyj stolbec soderzhit kolichestvo monet ukazannogo dostoinstva.\n" );
printf( "-------------------------------------------------------------------\n" );
printf( "| 5r. | 3r. | 1r. | 50k.| 20k.| 15k.| 10k.| 5k.| 3k.| 2k.| 1k.|\n" );
printf( "-------------------------------------------------------------------\n" );
change( N-1, coin );
printf( "-------------------------------------------------------------------\n" );
printf( "Vsego %ld variantov\n", nvar );
}
/* rekursivnyj razmen */
change( maxcoin, sum )
int sum; /* moneta, kotoruyu menyaem */
int maxcoin; /* indeks po massivu cost[] monety maksimal'nogo
* dostoinstva, dopustimoj v dannom razmene.
*/
{
register i;
if( sum == 0 ){ /* vsya summa razmenyana */
/* raspechatat' ocherednoj variant */
putchar( '|' );
for( i = N-1 ; i >= 0 ; i-- )
if( count[i] )
printf(" %3d |", count[ i ] );
else
printf(" |" );
putchar( '\n' );
nvar++;
return;
}
if( sum >= cost [ maxcoin ] ){
/* esli mozhno vydat' monetu dostoinstvom cost[maxcoin] ,
* to vydat' ee:
*/
count[ maxcoin ] ++; /* poschitali vydannuyu monetu */
/* razmenivaem ostatok summy :
* Pervyj argument - mozhet byt' mozhno dat' eshche odnu takuyu monetu ?
* Vtoroj argument - obshchaya summa ubavilas' na odnu monetu cost[maxcoin].
*/
change( maxcoin, sum - cost[maxcoin] );
count[ maxcoin ] --; /* ... Teper' poprobuem inoj variant ... */
}
/* poprobovat' razmen bolee melkimi monetami */
if( maxcoin )
change( maxcoin-1, sum );
}
/* Primer 2 */
/* Podschet kolichestva vhozhdenij kazhdoj iz bukv alfavita v fajl.
* Vydacha tablicy.
* Podschet chastoty ispol'zovaniya bitov v bajtah fajla.
*/
#include <stdio.h>
#include <ctype.h>
long bcnt[8];
char masks[8] = { /* maski bitov */
1, 2, 4, 8, 16, 32, 64, 128 };
long cnt[256]; /* schetchiki dlya kazhdoj iz 256 bukv */
/* raspechatka bukv v stile yazyka SI */
char *pr( c ){
static char buf[ 20 ];
switch( c ){
case '\n': return " \\n " ;
case '\r': return " \\r " ;
case '\t': return " \\t " ;
case '\b': return " \\b " ;
case '\f': return " \\f " ;
case '\033': return " ESC" ;
case '\0': return " \\0 " ;
case 0177: return " ^? " ;
}
if( c < ' ' ){
sprintf( buf, " ^%c ", c + 'A' - 1 );
}else if( isspace(c)){
sprintf( buf, " '%c'", c );
}else if( ! isprint( c ))
sprintf( buf, "\\%3o", c );
else sprintf( buf, " %c ", c );
return buf;
}
main( argc, argv ) char **argv; {
FILE *fp;
if( argc == 1 ) process( stdin );
else{ argv++; argc--;
while( *argv ){
printf( "----- FILE %s -----\n", *argv );
if((fp = fopen( *argv, "r" )) == NULL ){
printf( "Can not open\n" );
}else{ process( fp ); fclose( fp ); }
argv++; argc--;
}
}
exit(0);
}
/* obrabotat' fajl s pointerom fp */
process( fp ) FILE *fp;
{ register i; int c; int n;
/* zachistka schetchikov */
for( i=0; i < 256; i++ ) cnt[i] = 0L;
for( i=0; i < 8 ; i++ ) bcnt[i] = 0;
while( ( c=getc(fp)) != EOF ){
c &= 0377;
/* podschitat' bukvu */
cnt[ c ] ++;
/* podschet bitov */
for( i=0; i < 8; i++ )
if( c & masks[i] )
bcnt[ i ] ++;
}
/* vydacha rezul'tatov v COL kolonok */
#define COL 4
printf( "\tASCII map\n" );
for( n=i=0; i < 256; i++ ){
/* if( cnt[i] == 0l ) continue; */
printf( "%s %5ld |", pr(i), cnt[i] );
if( ++n == COL ){ n = 0; putchar('\n'); }
/* ili if((i % COL) == (COL-1)) putchar('\n'); */
}
printf( "\n\tBITS map\n" );
for( i=7; i >=0 ; i-- ) printf( "%6d ", i );
putchar( '\n' );
for( i=7; i >=0 ; i-- )
printf( "%6ld ", bcnt[i] );
putchar( '\n' ); putchar( '\n' );
}
/* Primer 3 */
/* Centrirovanie strok teksta. Primer na rabotu s ukazatelyami. */
/* Vhodnye stroki ne dolzhny soderzhat' tabulyacij */
/* Vyzov: a.out < vhodnoj_fajl */
#include <stdio.h>
extern char *gets();
#define WIDTH 60 /* shirina lista */
main(){
char rd[81]; register char *s;
char *head, /* nachalo teksta */
*tail; /* konec teksta */
register int len, i;
int shift; /* otstup */
/* CHitat' so standartnogo vvoda v rd po odnoj stroke,
* poka fajl ne konchitsya. Pri vvode s klaviatury konec fajla
* oboznachaetsya nazhatiem klavish CTRL+D
*/
while( gets( rd ) != NULL ){
if( !*rd ){
/* Stroka pusta */
putchar( '\n' ); continue;
}
/* propusk probelov v nachale stroki */
for( s = rd; *s == ' ' ; s++ );
if( ! *s ){
/* Stroka sostoit tol'ko iz probelov */
putchar( '\n' ); continue;
}
head = s;
/* vstat' na konec stroki */
while( *s ) s++;
/* iskat' poslednij neprobel */
s--;
while( *s == ' ' && s != rd ) s--;
tail = s;
/* Dlina teksta */ len = (tail-head) + 1;
/* raznost' ukazatelej - celoe */
shift = (WIDTH - len)/2;
if(shift < 0 ){
fprintf(stderr, "Stroka dlinnee chem %d\n", WIDTH );
shift = 0;
}
/* Pechat' rezul'tata */
for( i=0; i < shift; i++ ) putchar( ' ' );
while( head <= tail ) putchar( *head++ );
putchar( '\n' );
}
}
/* Primer 4 */
/* Predvaritel'naya razmetka teksta dlya nroff */
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h> /* prototip strchr() */
#include <locale.h>
FILE *fout = stdout; /* kanal vyvoda */
/* Sostoyaniya vyvoda */
#define SPACE 0 /* probely */
#define TEXT 1 /* tekst */
#define PUNCT 2 /* znaki prepinaniya */
#define UC(c) ((unsigned char)(c))
/* Vyvod stroki teksta iz bufera */
void putstr (FILE *fp, unsigned char *s) {
/* Punct - znaki prepinaniya, trebuyushchie prikleivaniya k
* koncu predydushchego slova.
* PunctS - znaki, vsegda trebuyushchie posle sebya probela.
* PunctN - znaki, kotorye mogut sledovat' za znakom
* prepinaniya bez probela.
*/
static char Punct [] = ",:;!?.)" ;
static char PunctS[] = ",:;" ;
static char PunctN[] = " \t\"'" ;
#define is(c, set) (strchr(set, UC(c)) != NULL)
int c, state = TEXT, cprev = 'X';
while ((c = *s) != '\0') {
/* Probely */
if(isspace(c)) state = SPACE;
/* Znaki prepinaniya. Probely pered nimi ignoriruyutsya.
*/ else if(is(c, Punct)){
switch(state){
case SPACE: if(is(cprev, Punct ) && cprev==c && c != ')')
putc(' ', fp);
/* a prosto probely - ignorirovat' */ break;
case PUNCT: if(is(cprev, PunctS)) putc(' ', fp); break;
}
putc(cprev = c, fp); /* vyvodim sam znak */
state = PUNCT;
} else {
/* Neskol'ko probelov svorachivaem v odin */
switch(state){
case SPACE: putc(' ', fp); break;
case PUNCT: if(!is(c, PunctN)) pu