|
Документ взят из кэша поисковой машины. Адрес
оригинального документа
: 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 Поисковые слова: п п п п п п п |
Составьте программу вывода строк файла в инверсном отображении, причем порядок символов в строках также следует инвертировать. Например,
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
Назад | Содержание | Вперед