2015-10-22
485
Для розв'язання задач можна використовувати масив таких структур, списки, дерева різного типу тощо. Головним при цьому є питання швидкодії. Для організації даних у вигляді хеш-таблиці визначимо масив покажчиків, кожен елемент якого зберігатиме адресу першого елемента деякого однозв'язного списку.
|
|
|
До одного списку записуватимуться елементи таблиці, для яких однакове значення має спеціальна хеш-функція. Хеш-функція, аналізуючи рядок, повертає деяке ціле значення, що є індексом відповідного елемента масиву покажчиків (hashtable). У найпростішому варіанті значення функції хешування отримується як залишок від ділення суми символьних значень рядка на розмір масиву. При цьому доступ до голови відповідного списку здійснюється моментально: hashtable[hashfunc(...)]. Розмір масиву фіксований (у нашій програмі HASHSIZE дорівнює 21). У загальному випадку його вибір – це досить складне питання, він залежить від розміру таблиці та інших факторів. Наведемо всю програму з коментарями за її окремими блоками:
#include <stdio.h>#include <string.h> /*прототип для strchr()*/extern void *malloc(unsigned size);/*типи ключа та значення: у нашому випадку – це рядки*/typedef unsigned char uchar;typedef uchar *VAL; typedef uchar *KEY; /*Для роботи необхідно реалізувати операціїint HASHFUNC(KEY); int EQKEY(KEY, KEY);void FREEVAL(VAL); void SETVAL(VAL, VAL);void FREEKEY(KEY); void SETKEY(KEY, KEY);*/#define HASHSIZE 21 /*обсяг масиву*/uchar *strudup(const uchar *s){/*створення копії рядка в "купі"*/ uchar *p=(uchar*) malloc(strlen(s)+1); strcpy(p,s); return p;}/*одна з можливих хеш-функцій*/unsigned int hash; /*останнє пораховане значення хеш-функції*/int HASHFUNC(KEY key){unsigned int i=0; uchar *keysrc=key;while(*key){ i=(i<<1)|(i>>15); /*ROL*/ i^=*key++;}hash=i% HASHSIZE;printf("hash(%s)=%d\n", keysrc, hash); return hash;}#define EQKEY(s1, s2) (strcmp(s1, s2)==0)#define FREEKEY(s) free(s)#define FREEVAL(s) free(s)#define SETVAL(at,s) at=strudup(s)#define SETKEY(at,s) at=strudup(s)#define KEYFMT "%s"#define VALFMT "%s" /*=========== типонезалежна частина ============*/struct cell {struct cell *next; /*покажчик на черговий елемент*/KEY key; /*ключ*/VAL val; /*значення*/}*hashtable[HASHSIZE]; /*хеш-таблиця*/ /*отримання значення за ключем*/struct cell *get(KEY key){struct cell *p;for(p=hashtable[HASHFUNC(key)]; p; p=p->next) if(EQKEY(p->key, key)) return p; return NULL; /*відсутнє*/} /*занести пару ключ: значення в таблицю*/void set(KEY key, VAL val){struct cell *p; /*перевірити, чи не було елемента з таким ключем*/if((p=get(key))==NULL){/*не було*/ if(!(p=(struct cell*) malloc(sizeof(*p)))) return; SETKEY(p->key, key); p->next=hashtable[hash]; /*hash обчислене в get()*/ hashtable[hash]=p;} else /*уже було: змінити значення*/ FREEVAL(p->val);SETVAL(p->val, val);} /*знищення за ключем*/int del(KEY key){int indx=HASHFUNC(key);struct cell *p, *prev=NULL; if((p=hashtable[indx])==NULL) return 0; for(;p;prev=p, p=p->next) if(EQKEY(p->key, key)){ FREEVAL(p->val); FREEKEY(p->key); if(p==hashtable[indx]) /*голова списку*/ hashtable[indx]=p->next; else prev->next=p->next; free((void*)p); return 1; /*знищений*/ } return 0; /*не було такого*/} /*роздрукувати пару ключ: значення*/void printcell(struct cell *ptr){ putchar('('); printf(KEYFMT, ptr->key); putchar(','); printf(VALFMT, ptr->val); putchar(')');} /*друк таблиці (для налагодження)*/void printtable(){ register i; struct cell *p; printf("----TABLE CONTENTS----\n"); for(i=0; i<HASHSIZE; i++) if((p=hashtable[i])!=NULL){ printf("%d: ", i); for(; p; p=p->next) printcell(p), putchar(' '); putchar('\n'); }} /*ітератор*/struct celliter { int index; struct cell *ptr;};/*видати чергове значення*/struct cell *nextpair(struct celliter *ci){ struct cell *result; while((result=ci->ptr)==NULL){ if(++(ci->index)>=HASHSIZE) return NULL; /*більше немає*/ ci->ptr=hashtable[ci->index]; } ci->ptr=result->next; return result;}/*ініціалізація ітератора*/struct cell *resetiter(struct celliter *ci){ ci->index=(-1); ci->ptr=NULL; return nextpair(ci); /*перше значення*/} void main(){ /*таблиця з імен і розмірів файлів поточного каталогу*/ struct celliter ci; struct cell *cl; char key[40], value[40]; struct cell *val; extern FILE *popen(); FILE *fp; char *s; /*popen() читає виведення команди, заданої в 1-му аргументі*/ fp=popen("ls -s", "r"); while(fscanf(fp, "%s%s", value, key)==2) set(key, value); pclose(fp); /*popen() потрібно закривати pclose();*/ for(;;){printf("-> "); /*запрошення*/if(!gets(key)) break; /*EOF*/if(*key=='-'){/*КЛЮЧ: видалити*/ printf(del(key+1)? "OK\n": "немає такого\n"); continue; } if(!*key||!strcmp(key,"=")){ /*=:роздрукувати таблицю*/ printtable(); continue; } if(s=strchr(key,'=')){ /*КЛЮЧ=ЗНАЧЕННЯ: додати*/ *s++='\0'; set(key, s); continue; } if((val=get(key))==NULL) /*КЛЮЧ: знайти значення*/ printf("немає такого ключа\n"); else{printf("значення"); printf(VALFMT, val->val); putchar('\n'); } } /*друк таблиці за допомогою ітератора*/ for(cl=resetiter(&ci); cl; cl=nextpair(&ci)) printcell(cl), putchar('\n');}2. Складені описувачі. Напишемо програму, яка:
|
|
|
а) підраховує кількість усіх допустимих у мові С складених описувачів заданої довжини;
б) генерує довільний складений описувач заданої довжини;
в) друкує всі допустимі складені описувачі заданої довжини.
У допустимих описувачах ураховуватимемо лише тривіальні ознаки масивів і функцій – дужки [ ], (). Розглянемо поняття довжини як кількість кроків інтерпретації.
Якщо позначити через V ознаку покажчика, М – масиву, F – функції, то за правилами розшифровки довільна послідовність FFVVMFVV задає схему утворення описувача (інтерпретуємо її зліва направо). Описувач буде допустимим, якщо в цій послідовності немає комбінацій вигляду FM (масив функцій), FF (функція повертає функцію), MF. Схему створення допустимого складеного описувача можна подати так:
V – покажчик M-масив F-функція
V-V M-V F-V
V-M M-M
V-F
Якщо останньою була ознака покажчика, то вона може утворити всі три ознаки, масиву – дві й, нарешті, ознака функції – лише одну ознаку покажчика.
Для підрахунку кількості всіх можливих описувачів ми можемо використати лише три змінних – v, m, f типу long, які б зберігали в собі на кожному кроці кількість описувачів, у яких останньою при інтерпретації була б відповідно ознака покажчика, масиву та функції. Неважко помітити, що ці кількості за 1 крок зростають за правилом
v1=v+m+f;
m1=m+v;
f1=v;
Наведемо відповідний підрахунок у вигляді функції:
Long kilkist(int n)
{
long v=1, m=1, f=1, v1,m1,f1;
int i;
for(i=1;i<n;i++)
{
v1=v+m+f;
m1=m+v;
f1=v;
v=v1;
m=m1;
f=f1;
}
return (v+m+f);
}
Тоді main -функція має вигляд
#include <stdio.h>
Void main(void)
{
int n;
printf("введіть довжину процесу інтерпретації описувача n>=1\n');
|
|
|
scanf("%d',&n);
printf("шукана кількість: %ld\n',kilkist(n));
}
Нескладний аналіз показує, що код, записаний у тілі циклу for у функції kilkist(), може бути спрощений і записуватися без використання допоміжних змінних v1, m1, f1.
Тоді функція має вигляд
Long kilkist(int n)
{
long v=1, m=1, f=1, v1;
int i;
for(i=1;i<n;i++)
{
v+=m+f;
f=v-m-f;
m+=f;
}
return (v+m+f);
}
Для розв'язання другої частини задачі спочатку отримаємо всі можливі схеми інтерпретації указаної довжини та реалізуємо їх. Для цього нам необхідно мати:
a функцію, що генерує схеми;
a функцію-інтерпретатор, що будує конкретний описувач за заданою схемою;
a функцію, що формує список.
Ураховуючи вищезгадану схему, можемо вибрати різні структури даних, наприклад тернарні дерева. Однак ми зупинимось на однозв'язному списку, одночасно демонструючи технологію роботи зі списками. Виберемо таку структуру:
Struct inter
{
struct inter *next; // покажчик на наступний елемент
char *s; // поле, де зберігається інтерпретаційна схема
