руются. В двумерном же байтовом массиве нам пришлось бы для тех же перестановок
копировать целые массивы байт - строки этой текстовой матрицы.
7.33. Напишите программу, печатающую строки файла в обратном порядке. Не считывать
файл целиком в память! Следует использовать метод "обратного чтения" либо метод
"быстрого доступа" к строкам файла, описанный в главе "Работа с файлами".
____________________
[*] На самом деле все освобожденные куски включаются в список свободной памяти, и
склеиваются вместе, если два освобожденных куска оказались рядом. При новых вызовах
malloc сначала просматривается список свободной памяти - нет ли там области достаточ-
ного размера? Этот алгоритм описан у Кернигана и Ритчи.
А. Богатырев, 1992-95 - 297 - Си в UNIX
/* Инвертирование порядка строк в файле.
* Используется та идея, что файл-результат имеет тот же
* размер, что и исходный
*/
#include
#include
#include
#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
#include
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
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;
}
/* иначе есть хоть один узел */
