Документ взят из кэша поисковой машины. Адрес
оригинального документа
: http://www.sao.ru/hq/sts/linux/book/bogatyrev_c_unix/gl_7_3.shtml
Дата изменения: Unknown Дата индексирования: Sat Sep 11 19:53:41 2010 Кодировка: koi8-r Поисковые слова: annular |
Составьте программу вывода строк файла в инверсном отображении, причем порядок символов в строках также следует инвертировать. Например,
abcdef ... oklmn 987654321 ..... превращать в ..... 123456789 nmlko ... fedcba
Программа должна быть составлена двумя способами: при помощи обратного чтения файла и рекурсивным вызовом самой функции инвертирования. Указание: при обратном чтении надо читать файл большими кусками (блоками).
Напишите программу, читающую файл построчно и размещающую строки в отсортированное двоичное дерево. По концу файла - распечатайте это дерево. Указание: используйте динамическую память и рекурсию.
/* Двоичная сортировка строк при помощи дерева */ #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-переменная, * а использовалась одна и та же статическая */ /* Рекурсивная печать дерева */ 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); } 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; } } 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); }
Напишите программу, которая читает со стандартного ввода 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; } }
Рассмотрим задачу написания функции, которая обрабатывает переменное число аргументов, например функцию-генератор меню. В такую функцию надо подавать строки меню и адреса функций, вызываемых при выборе каждой из строк. Собственно проблема, которую мы тут обсуждаем - как передавать переменное число аргументов в подобные функции? Мы приведем три программы использующие три различных подхода. Предпочтение не отдано ни одному из них - каждый из них может оказаться эффективнее других в определенных ситуациях. Думайте сами!
/* Передача аргументов в функцию как МАССИВА. * Следует явно указать число аргументов в массиве. */ #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; } } /* При инициализации 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; }
/* Передача аргументов в функцию как СПИСКА. * Достоинство: список можно модифицировать * во время выполнения программы: добавлять и * удалять элементы. Недостаток тот же: список надо * построить динамически во время выполнения, * заранее этого сделать нельзя. * Недостатком данной программы является также то, * что список не уничтожается после использования. * В 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; 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; }
/* Передача аргументов в функцию как СПИСКА АРГУМЕНТОВ * ФУНКЦИИ с признаком конца списка. */ #include <stdio.h> /* printf(), NULL */ #include <stdarg.h> /* va_... */ #define A_INT 1 #define A_STR 2 #define A_NULL 0 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[]){ doit( A_INT, 123, A_STR, " hello, ", A_INT, 456, A_STR, " world\n", A_NULL ); return 0; }
Напишите несколько функций для работы с упрощенной базой данных. Запись в базе данных содержит ключ - целое, и строку фиксированной длины:
struct data { int b_key; /* ключ */ char b_data[ DATALEN ]; /* информация */ };
Напишите:
Файл организован как несортированный массив записей без дубликатов (т.е. ключи не могут повторяться). Поиск производить линейно. Используйте функции fread, fwrite, fseek. Последняя функция позволяет вам позиционироваться к n-ой записи файла:
fseek( fp, (long) n * sizeof(struct data), 0 );
Перепишите эту программу, объявив ключ как строку, например
char b_key[ KEYLEN ];
Если строка-ключ короче KEYLEN символов, она должна оканчиваться '\0', иначе используются все KEYLEN букв и '\0' на конце отсутствует (так же устроено поле d_name в каталогах файловой системы). Усовершенствуйте алгоритм доступа, используя хеширование по ключу (hash - перемешивание, см. пример в приложении). Вынесите ключи в отдельный файл. Этот файл ключей состоит из структур
struct record_header { int b_key ; /* ключ */ long b_offset; /* адрес записи в файле данных */ int b_length; /* длина записи (необязательно) */ };
то есть организован аналогично нашей первой базе данных. Сначала вы ищете нужный ключ в файле ключей. Поле b_offset у найденного ключа задает адрес данного в другом файле. Чтобы прочитать его, надо сделать fseek на расстояние b_offset в файле данных и прочесть b_length байт.
Организуйте базу данных в файле как список записей. В каждой записи вместо ключа должен храниться номер очередной записи (ссылка). Напишите функции: поиска данных в списке (по значению), добавления данных в список в алфавитном порядке, (они просто приписываются к концу файла, но в нужных местах переставляются ссылки), распечатки списка в порядке ссылок, удалению элементов из списка (из самого файла они не удаляются!). Ссылка (номер) первой записи (головы списка) хранится в первых двух байтах файла, рассматриваемых как short.
Введите оптимизацию: напишите функцию для сортировки файла (превращению перемешанного списка в линейный) и вычеркивания из него удаленных записей. При этом файл будет перезаписан. Если файл отсортирован, то поиск в нем можно производить более эффективно, чем прослеживание цепочки ссылок: просто линейным просмотром. Третий байт файла используйте как признак: 1 - файл был отсортирован, 0 - после сортировки в него было что-то добавлено и линейный порядок нарушен.
© Copyright А. Богатырев, 1992-95
Си в UNIX
Назад | Содержание | Вперед