printf( "%-15s %d\n", tbl->name, tbl->value );
}
}
int main(){
char buf[80];
struct elem *ptr;
printtable(table);
for(;;){
printf( "-> " );
if( gets( buf ) == NULL) break; /* EOF */
if( ! strcmp( buf, "q" ))
exit(0); /* quit: выход */
ptr = find( buf, table, SIZE-1 );
if( ptr )
printf( "%d\n", ptr->value );
else {
printf( "--- Не найдено ---\n" );
printtable(table);
}
}
return 0;
}
7.26. Напишем функцию, которая преобразует строку так, что при ее печати буквы в ней
будут подчеркнуты, а цифры - выделены жирно. Формат текста с выделениями, который
создается этим примером, является общепринятым в UNIX и распознается некоторыми прог-
раммами: например, программа просмотра файлов less (more) выделяет такие буквы на
экране специальными шрифтами или инверсией фона.
#define LEN 9 /* потом напишите 256 */
char input[] = "(xxx+yyy)/123.75=?";
char output[LEN];
void main( void ){
int len=LEN, i; void bi_conv(); char c;
bi_conv(input, output, &len);
if(len > LEN){
printf("Увеличь LEN до %d\n", len);
len = LEN; /* доступный максимум */
}
for(i=0; i < len && (c = output[i]); ++i)
putchar(c);
putchar('\n');
}
/* Заметьте, что include-файлы не обязательно
* должны включаться в самом начале программы! */
#include <stdio.h>
#include <ctype.h>
#define PUT(c) { count++; \
if(put < *len){ *p++ = (c); ++put;}}
#define GET() (*s ? *s++ : EOF)
void bi_conv(
А. Богатырев, 1992-95 - 290 - Си в UNIX
/*IN*/ char *s,
/*OUT*/ char *p,
/*INOUT*/ int *len ){
int count, put, c;
for(count=put=0; (c=GET()) != EOF; ){
/* жирный: C\bC */
/* подчеркнутый: _\bC */
if(isalpha(c)){ PUT('_'); PUT('\b'); }
else if(isdigit(c)){ PUT( c ); PUT('\b'); }
PUT(c);
}
PUT('\0'); /* закрыть строку */
*len = count;
#undef PUT
#undef GET
}
Напишите программу для подобной обработки файла. Заметим, что для этого не нужны
промежуточные строки input и output и построчное чтение файла; все, что надо сделать,
это определить
#define PUT(c) if(c)putchar(c)
#define GET() getchar()
Напишите подобную функцию, удваивающую буквы в ссттррооккее.
7.27. Напишите программу, удаляющую из файла выделения. Для этого надо просто уда-
лять последовательности вида C\b
#include <stdio.h>
#define NOPUT (-1) /* не символ ASCII */
/* Названия шрифтов - в перечислимом типе */
typedef enum { NORMAL=1, ITALICS, BOLD, RED=BOLD } font;
int ontty; font textfont; /* текущее выделение */
#define setfont(f) textfont=(f)
#define getfont() (textfont)
#define SetTtyFont(f) if(ontty) tfont(f)
/* Установить выделение на экране терминала */
void tfont(font f){ /* только для ANSI терминала */
static font ttyfont = NORMAL;
if(ttyfont == f) return;
printf("\033[0m"); /* set NORMAL font */
switch(ttyfont = f){
case NORMAL: /* уже сделано выше */ break;
case BOLD: printf("\033[1m"); break;
case ITALICS: /* use reverse video */
printf("\033[7m"); break;
}
}
void put(int c){ /* Вывод символа текущим цветом */
if(c == NOPUT) return; /* '\b' */
SetTtyFont(getfont()); putchar(c);
setfont(NORMAL); /* Ожидать новой C\b посл-ти */
}
void
main(){ register int c, cprev = NOPUT;
/* Стандартный вывод - это терминал ? */
ontty = isatty(fileno(stdout));
setfont(NORMAL);
while((c = getchar()) != EOF){
А. Богатырев, 1992-95 - 291 - Си в UNIX
if(c == '\b'){ /* выделение */
if((c = getchar()) == EOF) break;
if(c == cprev) setfont(BOLD);
else if(cprev == '_') setfont(ITALICS);
else /* наложение A\bB */ setfont(RED);
} else put(cprev);
cprev = c;
}
put(cprev); /* последняя буква файла */
SetTtyFont(NORMAL);
}
7.28. Напишите программу печати на принтере листинга Си-программ. Ключевые слова
языка выделяйте двойной надпечаткой. Для выдачи на терминал напишите программу, под-
черкивающую ключевые слова (подчеркивание - в следующей строке). Упрощение: выде-
ляйте не ключевые слова, а большие буквы. Указание: для двойной печати используйте
управляющий символ '\r' - возврат к началу той же строки; затем строка печатается
повторно, при этом символы, которые не должны печататься жирно, следует заменить на
пробелы (или на табуляцию, если этот символ сам есть '\t').
7.29. Напишите программу, печатающую тексты Си-программ на принтере. Выделяйте клю-
чевые слова языка жирным шрифтом, строки "строка", символы 'c' и комментарии - курси-
вом. Шрифты для EPSON-FX совместимых принтеров (например EP-2424) переключаются
такими управляющими последовательностями (ESC означает символ '\033'):
ВКЛЮЧЕНИЕ ВЫКЛЮЧЕНИЕ
жирный шрифт (bold) ESC G ESC H
утолщенный шрифт (emphasized) ESC E ESC F
курсив (italics) ESC 4 ESC 5
подчеркивание (underline) ESC - 1 ESC - 0
повышенное качество печати ESC x 1 ESC x 0
(near letter quality) nlq draft
верхние индексы (superscript) ESC S 0 ESC T
нижние индексы (subscript) ESC S 1 ESC T
сжатый шрифт (17 букв/дюйм) '\017' '\022'
(condensed)
двойная ширина букв ESC W 1 ESC W 0
(expanded)
пропорциональная печать ESC p 1 ESC p 0
(proportional spacing)
Можно включить одновременно несколько из перечисленных выше режимов. В каждой из
следующих двух групп надо выбрать одно из трех:
pitch (плотность печати)
pica (10 букв/дюйм) ESC P
elite (12 букв/дюйм) ESC M
micron (15 букв/дюйм) ESC g
font (шрифт)
черновик (draft (Roman)) ESC k '\0'
текст (text (Sans Serif)) ESC k '\1'
курьер (courier) ESC k '\2'
Всюду выше 0 означает либо '0' либо '\0'; 1 означает либо '1' либо '\1'. Пример:
printf( "This is \033Gboldface\033H word\n");
А. Богатырев, 1992-95 - 292 - Си в UNIX
7.30. Составьте программу вывода набора файлов на печать, начинающую каждый очеред-
ной файл с новой страницы и печатающую перед каждым файлом заголовок и номер текущей
страницы. Используйте символ '\f' (form feed) для перевода листа принтера.
7.31. Напишите программу печати текста в две колонки. Используйте буфер для форми-
рования листа: файл читается построчно (слишком длинные строки обрубать), сначала
заполняется левая половина листа (буфера), затем правая. Когда лист полностью запол-
нен или файл кончился - выдать лист построчно, расписать буфер пробелами (очистить
лист) и повторить заполнение очередного листа. Указание: размеры листа должны переда-
ваться как аргументы main(), для буфера используйте двумерный массив букв, память для
него заказывайте динамически. Усложнение: не обрубайте, а переносите слишком длинные
строки (строка может потребовать даже переноса с листа на лист).
/* ПРОГРАММА ПЕЧАТИ В ДВЕ ПОЛОСЫ: pr.c */
#include <stdio.h>
#include <string.h>
#define YES 1
#define NO 0
#define FORMFEED '\f'
#define LINEFEED '\n'
extern char *malloc(unsigned);
extern char *strchr(char *, char);
void untab(register char *s);
void resetsheet( void );
void addsheet( char *s, FILE *fpout );
void flushsheet( FILE *fpout );
void printline( int y, char *s, char *attr,
FILE *fpout );
void doattr( register char *abuf,
register char *vbuf );
void printcopy( FILE *fpin, FILE *fpout );
void main(void);
char *strdup (const char *s){
char *p = malloc(strlen(s)+1); strcpy(p,s); return p;
/* return strcpy((char *) malloc(strlen(s)+1), s); */
}
/* ... текст функции untab() ... */
int Sline; /* строка на листе */
int Shalf; /* половина листа */
int npage; /* номер страницы */
int startpage = 1;
/* печать начиная с 1ой страницы */
int fline; /* номер строки файла */
int topline = 0; /* смещение до начала листа */
int halfwidth; /* ширина полулиста */
int twocolumns = YES; /* в две колонки ? */
int lshift, rshift = 1; /* поля слева и справа */
typedef unsigned short ushort;
int COLS = 128; /* ширина листа (букв) */
int LINES = 66; /* длина листа (строк) */
ushort *mem; /* буфер листа */
#define AT(x,y) mem[ (x) + (y) * COLS ]
/* Выделить буфер под лист и зачистить его */
void resetsheet ( void ){
register x;
if( mem == NULL ){ /* выделить память */
А. Богатырев, 1992-95 - 293 - Си в UNIX
if ((mem = (ushort *)
malloc (COLS * LINES * sizeof(ushort)))
== NULL ){
fprintf(stderr, "Out of memory.\n"); exit(1);
}
}
/* очистить */
for( x= COLS * LINES - 1 ; x >= 0 ; x-- )
mem[x] = ' ' & 0xFF;
halfwidth = (twocolumns ? COLS/2 : COLS )
- (lshift + rshift );
Sline = topline; Shalf = 0;
}
#define NEXT_HALF \
if( twocolumns == YES && Shalf == 0 ){ \
/* закрыть данную половину листа */ \
Shalf = 1; /* перейти к новой половине */ \
Sline = topline; \
} else \
flushsheet(fpout) /* напечатать лист */
/* Записать строку в лист */
void addsheet ( char *s, FILE *fpout )
{
register x, y;
register i;
char *rest = NULL;
int wrap = NO;
/* YES когда идет перенос слишком длинной строки */
/* в какое место поместить строку? */
x = (Shalf == 0 ? 0 : COLS/2) + lshift;
y = Sline;
i = 0; /* позиция в строке s */
while (*s) {
if( *s == '\f' ){
/* вынужденный form feed */
rest = strdup( s+1 ); /* остаток строки */
NEXT_HALF;
if( *rest ) addsheet(rest, fpout);
free( rest );
return;
}
if( i >= halfwidth ){
/* перенести длинную строку */
wrap = YES;
rest = strdup(s);
break;
}
/* Обработка выделений текста */
if( s[1] == '\b' ){
while( s[1] == '\b' ){
AT(x, y) = (s[0] << 8) | (s[2] & 0xFF);
/* overstrike */
s += 2;
}
s++; x++; i++;
} else {
AT (x, y) = *s++ & 0xFF;
А. Богатырев, 1992-95 - 294 - Си в UNIX
x++; i++;
}
}
/* Увеличить строку/половину_листа */
Sline++;
if (Sline == LINES) { /* полулист заполнен */
NEXT_HALF; }
if( wrap && rest ) { /* дописать остаток строки */
addsheet(rest, fpout); free(rest);
}
}
int again; /* нужна ли повторная надпечатка? */
/* Напечатать заполненный лист */
void flushsheet ( FILE *fpout ){
register x, y, xlast;
char *s, *p;
static char outbuf[BUFSIZ], attr[BUFSIZ];
/* attr - буфер под атрибуты выделений */
ushort c;
if( npage >= startpage )
for (y = 0; y < LINES; y++) {
/* обрезать концевые пробелы */
for (xlast = (-1), x = COLS - 1; x >= 0; x--)
if (AT (x, y) != ' ') { xlast = x; break; }
again = NO; s = outbuf; p = attr;
for (x = 0; x <= xlast; x++){
c = AT(x, y);
*s++ = c & 0xFF;
/* имеет атрибуты ? */
c >>= 8; c &= 0xFF;
*p++ = c ? c : ' ';
if( c ) again = YES;
}
*s = '\0'; *p = '\0';
printline(y, outbuf, attr, fpout);
}
npage++; /* next page */
resetsheet(); /* зачистить новый лист */
}
/* Напечатать одну строку листа */
void printline ( int y, char *s, char *attr,
FILE *fpout ){
register x;
if( again ){
doattr(attr, s); fprintf(fpout, "%s\r", attr );
}
fprintf(fpout, "%s", s);
/* перевод листа или строки */
fputc( y == LINES-1 ? FORMFEED : LINEFEED, fpout );
}
/* Проверить - нет ли атрибутов выделений */
void doattr ( register char *abuf,
register char *vbuf ){
for(; *abuf; abuf++, vbuf++ )
if( !strchr(" _-!|\177", *abuf))
*abuf = *vbuf;
}
А. Богатырев, 1992-95 - 295 - Си в UNIX
/* Копирование файла на принтер */
void printcopy ( FILE *fpin, FILE *fpout )
{
char inbuf[BUFSIZ];
npage = 1; /* первая страница имеет номер 1 */
fline = 0; /* текущая строка файла - 0 */
resetsheet(); /* зачистить буфер листа */
while( fgets(inbuf, sizeof inbuf - 1, fpin )
!= NULL ){
register l = strlen( inbuf );
if( l && inbuf[l-1] == '\n' )
inbuf[--l] = '\0' ;
fline++;
untab ( inbuf );
addsheet( inbuf, fpout );
}
if( !(Sline == topline && Shalf == 0))
/* если страница не была только что зачищена ... */
flushsheet(fpout);
fprintf(stderr, "%d строк, %d листов.\n",
fline, npage-1);
}
/* Вызов: pr < файл > /dev/lp */
void main (){ printcopy(stdin, stdout); }
Файл-принтер имеет в UNIX имя /dev/lp или подобное ему, а в MS DOS - имя prn.
7.32. Напишите программу, которая построчно считывает небольшой файл в память и
печатает строки в обратном порядке. Указание: используйте динамическую память -
функции malloc() и strcpy().
Объясним, почему желательно пользоваться динамической памятью. Пусть мы знаем,
что строки имеют максимальную длину 80 символов и максимальное количество строк равно
50. Мы могли бы хранить текст в двумерном массиве:
char text[50][80];
занимающем 50*80 = 4000 байт памяти. Пусть теперь оказалось, что строки файла в
действительности имеют длину по 10 букв. Мы
используем 50 * (10 + 1) = 550 байт
не используем 4000 - 50 * (10 + 1) = 3450 байт
(+1 нужен для символа '\0' на конце строки).
Пусть мы теперь пишем
char *text[50]; int i=0;
и при чтении очередной строки сохраняем ее так:
char buffer[81], *malloc(), *gets();
while( gets(buffer) != NULL ){
text[i] = (char *) malloc(strlen(buffer)+1);
/* +1 для хранения \0, который не учтен strlen-ом */
strcpy(text[i++], buffer);
}
то есть заказываем ровно столько памяти, сколько надо для хранения строки и ни байтом
больше. Здесь мы (если sizeof(char *)==4) используем
А. Богатырев, 1992-95 - 296 - Си в UNIX
50 * 4 + 50 * (10 + 1 + 4) = 950 байт
массив указателей + заказанная malloc память
(+4 - служебная информация malloc), но зато у нас не остается неиспользуемой памяти.
Преимуществом выделения памяти в виде массива является то, что эта память выделится
ГАРАНТИРОВАННО, тогда как malloc()-у может не хватить памяти (если мы ее прежде очень
много захватывали и не освобождали free()). Если malloc не может выделить участок
памяти требуемого размера, он возвращает значение NULL:
if((text[i] = malloc(....)) == NULL)
{ fprintf(stderr, "Мало памяти\n"); break; }
Распечатка строк:
for(--i; i >= 0; i-- ){
printf("%s\n", text[i]);
free( text[i] );
}
Функция free(ptr) "освобождает"|- отведенную ранее malloc()ом или calloc()ом область
памяти по адресу ptr так, что при новых вызовах malloc() эта область может быть пере-
использована. Данные в освобожденной памяти ПОРТЯТСЯ после free(). Ошибочно (и
опасно) освобождать память, которая НЕ БЫЛА отведена malloc()-ом!
Организация текста в виде массива ссылок на строки или списка ссылок на строки,
а не в виде двумерного текстового поля, выгодна еще тем, что такие строки проще
переставлять, сортировать, вставлять строку в текст, удалять строку из текста. При
этом переставляются лишь указатели в линейном массиве, а сами строки никуда не копи-
руются. В двумерном же байтовом массиве нам пришлось бы для тех же перестановок
копировать целые массивы байт - строки этой текстовой матрицы.
7.33. Напишите программу, печатающую строки файла в обратном порядке. Не считывать
файл целиком в память! Следует использовать метод "обратного чтения" либо метод
"быстрого доступа" к строкам файла, описанный в главе "Работа с файлами".
____________________
|- На самом деле все освобожденные куски включаются в список свободной памяти, и
склеиваются вместе, если два освобожденных куска оказались рядом. При новых вызовах
malloc сначала просматривается список свободной памяти - нет ли там области достаточ-
ного размера? Этот алгоритм описан у Кернигана и Ритчи.
А. Богатырев, 1992-95 - 297 - Си в UNIX
/* Инвертирование порядка строк в файле.
* Используется та идея, что файл-результат имеет тот же
* размер, что и исходный
*/
#include <sys/types.h>
#include <sys/stat.h>
#include <stdio.h>
#define BUFS 4096 /* максимальная длина строки */
void main(int argc, char **argv )
{
FILE *fp;
struct stat st;
long len;
char buffer[ BUFS+1 ];
FILE *fpnew; /* инверсный файл */
int lgt;
if( argc != 2 ){
printf("Error: must be filename\n");
exit(1);
}
if( (fp= fopen( argv[1], "r" )) == NULL ){
printf( "Can not open %s\n", argv[1] );
exit(2);
}
stat( argv[1], &st ); /* fstat(fileno(fp), &st); */
len = st.st_size; /* длина файла в байтах */
if( (fpnew = fopen( "inv.out", "w" ))== NULL ){
printf("Can not create file\n");
exit(3);
}
while( fgets( buffer, sizeof buffer, fp ) != NULL ){
lgt = strlen( buffer );
fseek(fpnew, len - lgt , 0);
/* Помните, что смещение у lseek и fseek -
* это число типа long, а не int.
* Поэтому лучше всегда писать
* lseek(fd, (long) off, whence);
*/
len -= lgt;
fprintf( fpnew, "%s", buffer );
/* или лучше fputs(buffer, fpnew); */
}
fclose( fp ); fclose( fpnew );
}
7.34. Напишите программу, которая читает файл, состоящий из "блоков" текста, разде-
ленных пустыми строками. Размер "блока" ограничен. Программа готовит файл для печати
на принтер так, чтобы ни один блок не разбивался на части:
А. Богатырев, 1992-95 - 298 - Си в UNIX
----------- -----------
|###### A | |###### A | лист1
|#### A | превращать |#### A |
|##### A | в |##### A |
| | | |
|###### B | | |
----------- -----------
|#### B | |###### B | лист2
| | |#### B |
... | |
то есть если блок не умещается на остатке листа, он должен быть перенесен на следую-
щий лист. Блоки следует разделять одной пустой строкой (но первая строка листа не
должна быть пустой!). Если блок длиннее страницы - не переносите его.
/* Решение задачи о переносе блоков текста,
* если они не умещаются на остатке листа */
#include <stdio.h>
#include <ctype.h>
extern void *malloc(unsigned);
extern int atoi(char *);
FILE *fpin = stdin, *fpout = stdout;
/* Спасти строку в динамически выделенной памяти */
char *strdup (const char *s) {
char *ptr = (char *) malloc (strlen (s) + 1);
if( ptr ) strcpy (ptr, s); return ptr;
}
int page_length = 66; /* длина страницы */
int current_line; /* текущая строка на странице (с нуля) */
int numbered = 0; /* нумеровать строки листа ? */
#define MAXLINES 256 /* макс. длина блока */
int stored = 0; /* запомнено строк */
char *lines[MAXLINES]; /* запомненные строки */
/* Запомнить строку блока в буфер строк */
void remember (char *s) {
if (stored >= MAXLINES) {
fprintf (stderr, "Слишком длинный блок.\n"); return;
} else if((lines[stored++] = strdup (s)) == NULL ){
fprintf (stderr, "Мало памяти (Out of memory).\n"); exit(13);
}
}
/* Переход на следующую страницу */
void newpage () {
current_line = 0; putc('\f', fpout);
}
А. Богатырев, 1992-95 - 299 - Си в UNIX
/* Перевод строки или листа */
void newline (void) {
if (current_line == page_length - 1)
newpage (); /* начать новый лист */
else {
current_line++;
if( numbered ) fprintf(fpout, "%02d\n", current_line);
else putc ('\n', fpout);
}
}
/* Переход на следующую страницу вставкой пустых строк */
void nextpage () {
while (current_line != 0)
newline ();
}
/* Выдать спасенный блок */
void throwout () {
register i;
for (i = 0; i < stored; i++) {
if( numbered )
fprintf(fpout, "%02d %s", current_line, lines[i]);
else fputs (lines[i], fpout);
newline (); free (lines[i]);
}
stored = 0;
}
/* Выдать блок, перенося на следующий лист если надо */
void flush () {
int rest_of_page = page_length - current_line;
/* осталось пустых строк на странице */
if ((stored > page_length && rest_of_page < page_length / 4) ||
rest_of_page < stored)
nextpage ();
throwout ();
if (current_line) /* не первая строка листа */
newline (); /* разделитель блоков */
}
/* Обработать входной файл */
void process () {
char buffer[512]; int l;
while (fgets (buffer, sizeof buffer, fpin) != NULL) {
if ((l = strlen (buffer)) && buffer[l - 1] == '\n')
buffer[ --l] = '\0';
if (l) remember (buffer);
/* а по пустой строке - выдать блок */
else if (stored) flush ();
}
if (stored) flush ();
nextpage();
}
А. Богатырев, 1992-95 - 300 - Си в UNIX
void main (int argc, char *argv[]) {
argc--; argv++;
while (*argv) {
if (**argv == '-') {
char *key = *argv + 1, *arg;
switch (*key) {
case 'l':
if (! key[1]) {
if( argv[1] ){
arg = argv[1]; argv++; argc--;
} else arg = "";
} else arg = key+1;
if( isdigit(*arg) ){
page_length = atoi(arg);
fprintf (stderr, "Длина страницы: %d строк\n", page_length);
} else fprintf(stderr, "-l ЧИСЛО\n");
break;
case 'n':
numbered++; break;
default:
fprintf (stderr, "Неизвестный ключ %s\n", key);
break;
}
}
argv++; argc--;
}
process ();
exit(0);
}
7.35. Составьте программу вывода строк файла в инверсном отображении, причем порядок
символов в строках также следует инвертировать. Например,
abcdef ... oklmn 987654321
..... превращать в .....
123456789 nmlko ... fedcba
Программа должна быть составлена двумя способами: при помощи обратного чтения файла и
рекурсивным вызовом самой функции инвертирования. Указание: при обратном чтении надо
читать файл большими кусками (блоками).
7.36. Напишите программу, читающую файл построчно и размещающую строки в отсортиро-
ванное двоичное дерево. По концу файла - распечатайте это дерево. Указание: исполь-
зуйте динамическую память и рекурсию.
А. Богатырев, 1992-95 - 301 - Си в UNIX
/* Двоичная сортировка строк при помощи дерева */
#include <stdio.h>
char buf[240]; /* буфер ввода */
int lines; /* номер строки файла */
typedef struct node{
struct _data{ /* ДАННЫЕ */
char *key; /* ключ - строка */
int line; /* номер строки */
} data;
/* СЛУЖЕБНАЯ ИНФОРМАЦИЯ */
struct node *l, /* левое поддерево */
*r; /* правое поддерево */
} Node;
Node *root = NULL; /* корень дерева (ссылка на верхний узел) */
/* Отведение памяти и инициализация нового узла */
Node *newNode(s)
char *s; /* строка */
{
Node *tmp;
extern char *malloc(); /* выделитель памяти */
tmp = (Node *) malloc(sizeof(Node));
if( tmp == NULL ){
fprintf( stderr, "Нет памяти.\n");
exit(1);
}
tmp -> l = tmp -> r = NULL; /* нет поддеревьев */
tmp -> data.line = lines; /* номер строки файла */
tmp -> data.key = malloc( strlen(s) + 1 );
/* +1 - под байт '\0' в конце строки */
strcpy(tmp -> data.key, s); /* копируем ключ в узел */
return tmp;
}
int i; /* Вынесено в статическую память, чтобы при каждом
* рекурсивном вызове не создавалась новая auto-переменная,
* а использовалась одна и та же статическая */
А. Богатырев, 1992-95 - 302 - Си в UNIX
/* Рекурсивная печать дерева */
void printtree(root, tree, level, c)
Node *root; /* корень дерева */
Node *tree; /* дерево */
int level; /* уровень */
char c; /* имя поддерева */
{
if( root == NULL ){ printf("Дерево пусто.\n"); return; }
if( tree == NULL ) return;
/* если есть - распечатать левое поддерево */
printtree (root, tree -> l, level + 1, '/'); /* 'L' */
/* распечатать ключ узла */
for( i=0; i < level; i++ )
printf(" ");
printf("%c%3d--\"%s\"\n",
c, tree-> data.line, tree -> data.key);
/* если есть - распечатать правое поддерево */
printtree(root, tree -> r, level + 1, '\\'); /* 'R' */
}
void prTree(tree) Node *tree;
{
printtree(tree, tree, 0, '*');
}
/* Добавить узел с ключом key в дерево tree */
void addnode(tree, key)
Node **tree; /* в какое дерево добавлять: адрес переменной,
* содержащей ссылку на корневой узел */
char *key; /* ключ узла */
{
#define TREE (*tree)
if( TREE == NULL ){ /* дерево пока пусто */
TREE = newNode( key );
return;
}
/* иначе есть хоть один узел */
if ( strcmp (key, TREE -> data.key) < 0 )
{
/* добавить в левое поддерево */
if ( TREE -> l == NULL ){
/* нет левого дерева */
TREE -> l = newNode(key);
return;
}
else addnode( & TREE ->l , key);
}
А. Богатырев, 1992-95 - 303 - Си в UNIX
else{
/* добавить в правое дерево */
if ( TREE -> r == NULL ){
/* нет правого поддерева */
TREE -> r = newNode(key);
return;
}
else addnode ( & TREE ->r, key) ;
}
}
/* Процедура удаления из дерева по ключу. */
typedef struct node *NodePtr;
static NodePtr delNode; /* удаляемая вершина */
void delete(key, tree)
char *key; /* ключ удаляемого элемента */
NodePtr *tree; /* из какого дерева удалять */
{
extern void doDelete();
if(*tree == NULL){
printf( "%s не найдено\n", key ); return;
}
/* поиск ключа */
else if(strcmp(key, (*tree)->data.key) < 0)
delete( key, &(*tree)->l );
else if(strcmp(key, (*tree)->data.key) > 0)
delete( key, &(*tree)->r );
else{ /* ключ найден */
delNode = *tree; /* указатель на удаляемый узел */
if(delNode->r == NULL) *tree = delNode->l;
else if(delNode->l == NULL) *tree = delNode->r;
else doDelete( & delNode->l );
free(delNode);
}
}
static void doDelete(rt) NodePtr *rt;
{
if( (*rt)->r != NULL ) /* спуск по правой ветви */
doDelete( &(*rt)->r );
else{
/* перенос данных в другой узел */
delNode->data = (*rt)->data;
delNode = *rt; /* для free() */
*rt = (*rt)->l;
}
}
А. Богатырев, 1992-95 - 304 - Си в UNIX
void main(){
extern char *gets(); char *s;
while (gets(buf) != NULL){ /* пока не конец файла */
lines++;
addnode( & root, buf );
}
prTree(root);
/* удалим строку */
freopen("/dev/tty", "r", stdin);
do{
printf( "что удалить ? " );
if((s = gets(buf)) == NULL) break;
delete(buf, &root);
prTree( root );
} while( s && root );
printf("Bye-bye.\n");
exit(0);
}
7.37. Напишите программу, которая читает со стандартного ввода 10 чисел либо слов, а
затем распечатывает их. Для хранения введенных данных используйте объединение.
#include <stdio.h>
#include <ctype.h>
#define INT 'i'
#define STR 's'
struct data {
char tag; /* тэг, пометка. Код типа данных. */
union {
int i;
char *s;
} value;
} a[10];
int counter = 0; /* счетчик */
void main(){
char word[128]; int i; char *malloc(unsigned);
/* Чтение: */
for(counter=0; counter < 10; counter++){
if( gets(word) == NULL ) break;
if( isdigit((unsigned char) *word)){
a[counter].value.i = atoi(word);
a[counter].tag = INT;
} else {
a[counter].value.s = malloc(strlen(word)+1);
strcpy(a[counter].value.s, word);
a[counter].tag = STR;
}
}
/* Распечатка: */
for(i=0; i < counter; i++)
switch(a[i].tag){
case INT: printf("число %d\n", a[i].value.i);
break;
case STR: printf("слово %s\n", a[i].value.s);
free(a[i].value.s);
break;
}
А. Богатырев, 1992-95 - 305 - Си в UNIX
}
7.38. Рассмотрим задачу написания функции, которая обрабатывает переменное число
аргументов, например функцию-генератор меню. В такую функцию надо подавать строки
меню и адреса функций, вызываемых при выборе каждой из строк. Собственно проблема,
которую мы тут обсуждаем - как передавать переменное число аргументов в подобные
функции? Мы приведем три программы использующие три различных подхода. Предпочтение
не отдано ни одному из них - каждый из них может оказаться эффективнее других в опре-
деленных ситуациях. Думайте сами!
7.38.1. Массив
/* Передача аргументов в функцию как МАССИВА.
* Следует явно указать число аргументов в массиве.
*/
#include <stdio.h> /* printf(), NULL */
#include <string.h> /* strdup() */
#include <stdlib.h> /* malloc() */
#define A_INT 1
#define A_STR 2
#define A_NULL 0
typedef struct arg {
int type;
union jack {
char *s;
int d;
} data;
struct arg *next;
} Arg;
void doit(Arg args[], int n){
int i;
for(i=0; i < n; i++)
switch(args[i].type){
case A_INT:
printf("%d", args[i].data.d);
break;
case A_STR:
printf("%s", args[i].data.s);
break;
default:
fprintf(stderr, "Unknown type!\n");
break;
}
}
А. Богатырев, 1992-95 - 306 - Си в UNIX
/* При инициализации union надо использовать тип
* первого из перечисленных значений.
*/
Arg sample[] = {
{ A_INT, (char *) 123 },
{ A_STR, (char *) " hello, " },
{ A_INT, (char *) 456 },
{ A_STR, (char *) " world\n" }
};
int main(int ac, char *av[]){
doit(sample, sizeof sample / sizeof sample[0]);
return 0;
}
7.38.2. Список
/* Передача аргументов в функцию как СПИСКА.
* Достоинство: список можно модифицировать
* во время выполнения программы: добавлять и
* удалять элементы. Недостаток тот же: список надо
* построить динамически во время выполнения,
* заранее этого сделать нельзя.
* Недостатком данной программы является также то,
* что список не уничтожается после использования.
* В C++ эта проблема решается при помощи использования
* автоматически вызываемых деструкторов.
*/
#include <stdio.h> /* printf(), NULL */
#include <string.h> /* strdup() */
#include <stdlib.h> /* malloc() */
#define A_INT 1
#define A_STR 2
#define A_NULL 0
typedef struct arg {
int type;
union jack {
char *s;
int d;
} data;
struct arg *next;
} Arg;
А. Богатырев, 1992-95 - 307 - Си в UNIX
void doit(Arg *arglist){
for( ; arglist; arglist=arglist->next)
switch(arglist->type){
case A_INT:
printf("%d", arglist->data.d);
break;
case A_STR:
printf("%s", arglist->data.s);
break;
default:
fprintf(stderr, "Unknown type!\n");
break;
}
}
Arg *new_int(int n, Arg *next){
Arg *ptr = (Arg *) malloc(sizeof(Arg));
ptr->type = A_INT;
ptr->data.d = n;
ptr->next = next;
return ptr;
}
Arg *new_str(char *s, Arg *next){
Arg *ptr = (Arg *) malloc(sizeof(Arg));
ptr->type = A_STR;
ptr->data.s = strdup(s);
ptr->next = next;
return ptr;
}
int main(int ac, char *av[]){
doit(
new_int(123,
new_str(" hello, ",
new_int(456,
new_str(" world\n",
NULL))))
);
return 0;
}
7.38.3. Функция с переменным числом параметров
/* Передача аргументов в функцию как СПИСКА АРГУМЕНТОВ
* ФУНКЦИИ с признаком конца списка.
*/
#include <stdio.h> /* printf(), NULL */
#include <stdarg.h> /* va_... */
#define A_INT 1
#define A_STR 2
#define A_NULL 0
А. Богатырев, 1992-95 - 308 - Си в UNIX
void doit(...){ /* переменное число аргументов */
va_list args;
/* второй параметр - аргумент, предшествующий ...
* Если такого нет - ставим запятую и пустое место!
*/
va_start(args, );
for(;;){
switch(va_arg(args, int)){
case A_INT:
printf("%d", va_arg(args, int));
break;
case A_STR:
printf("%s", va_arg(args, char *));
break;
case A_NULL:
goto breakloop;
default:
fprintf(stderr, "Unknown type!\n");
break;
}
}
breakloop:
va_end(args);
}
int main(int ac, char *av[]){