PS PDF PS (2стр на лист)

Краткое пособие по написанию кратких программ

Д.В. Хмелёв

2002-05-17 - 2003-08-17

Настоящие заметки суммируют мой опыт в практике написания программ для решения задач, возникающих в рамках научной деятельности. Такой род занятий приводит к необходимости писать относительно несложные программы (до тысячи строк) за относительно короткий промежуток времени. «Относительно короткий» означает, что время написания программы сравнимо со временем её работы. Это, однако, не означает, что программу можно писать «как-нибудь». Дело в том, что по мере продолжения исследования может потребоваться модификация в том или ином направлении. Поэтому важна простота и читаемость кода.

Небольшая программа может выполнять весьма нетривиальные действия. Например, программа Лингвоанализатор (http://www.rusf.ru/books/analysis/ и http://zhurnal.lib.ru/) на самом деле укладывается в текст на Си длиной порядка тысячи строк (из которых лишь порядка ста реализуют основной алгоритм).

К изложенным требованиям добавляется также «чистота» взаимодействия с операционной системой, которая должна проявляться в закрытии файлов и освобождении динамической памяти даже при аварийном выходе. Любая операционка, включая Юникс, начинает себя плохо чувствовать (то есть, погружается в обмен с диском), когда программа начинает использовать оперативную память сверх физического объёма.

При решении исследовательских задач очень важно сосредоточиться на достижении поставленной цели, поэтому прежде, чем программировать, необходимо придумать наиболее простой способ её достижения. При его реализации необходимо руководствоваться наиболее прямыми методами. В настоящих заметках я попытаюсь показать подход, которого вполне достаточно для быстрого и корректного решения простых исследовательских задач. Заметки состоят из трёх частей. В первой описан общий подход к программированию. Вторая часть содержит описания хитростей, упрощающих программирование и шаблонов, увеличивающих скорость написания программ. Третья часть содержит примеры программ, которые можно быстро написать с использованием предлагаемых методов. Основная информация сосредоточена на страницах pageref-pageref, примеры можно и пропустить.

Данный текст подразумевает знакомство читателя с программированием на Си. В качестве вводного текста в программирование рекомендуется книга А. Шеня [1] «Программирование: теоремы и задачи». Есть несколько руководств по Си, доступных через сеть: http://lib.ru/CTOTOR/.

Читатель, прочитавший текст, направляется к чрезвычайно полезной книге «Численные рецепты для Си» [2], которая появилась незадолго до развала СССР и лишь в силу этого недоразумения не издана на русском. В [2] читатель найдёт готовые тексты программ на Си, которые практически полностью покрывают большинство много «популярных», причём не только численных. Текст свободно доступен из сети (www.nr.com), программы можно нехитрым образом извлечь из текста и они действительно будут работать.

1  Методы простого программирования

Будьте готовы к написанию нескольких небольших программ на разных языках, если одну часть задачи удобно делать на одном языке, а другую - на другом. Например, задачи вычислительного характера удобней всего решать на Си, в то время как сортировка и обработка данных проще в Перле¹. Символьные вычисления надо проводить в Maple, хотя перебирающую программу, которая выдаст Maple набор инструкций, какие уравнения решать, проще написать на Си, и т.д.

У нас, в основном, речь пойдёт о Си.

1.1  Среда программирования

Более того, в такой комбинации можно отлаживать программу по исходному тексту прямо в редакторе (совсем IDE, то есть)! См. раздел  2.8.

1.2  Ввод/вывод

Никогда не стоит устраивать ввод/вывод в двоичном режиме: хотя бы из-за того, что размер целого числа (int) и даже порядок байтов может измениться при перекомпиляции программы под другую платформу. Входные и выходные данные должны иметь текстовый формат и обрабатываться с помощью scanf и printf! Разработчики компиляторов вложили немало усилий в оптимизацию scanf и printf и такой способ ввода-вывода лишь в два-три раза уступает по скорости двоичному: за счёт записи на диск, в основном. Но если минимальный размер выходного файла так уж важен, можно поставить фильтр (вроде gzip), который будет на лету ужимать выходной файл. Нужно только помнить, что функция scanf ненадёжна при считывании строк: если подать слишком длинную строку на вход, то можно разрушить программу, а потом и систему. Некоторое решение этой задачи предложено в разделе 3.6

1.3  Графика

Но если совсем уж надо, то пользуйтесь GRX (http://www.gnu.de/software/GRX/) - переносимой графической библиотекой, которая компилируется со всеми системами, описанными в разделе 1.1.

1.4  Структуры данных

Заметим, что объектно-ориентированное программирование также вредно при написании коротких программ. Преимущества ООП начинают ощущаться на больших объёмах текста: в сотни тысяч строк. Для разработки исследовательских проектов ничего лучше Си пока не существует: просто нет времени отвлекаться на изучение тонкостей взаимодействия классов, перегрузки операций и т.п. Вообще, по мнению автора объекты должны появляться только в программах с графическим или псевдографическим интерфейсом, который дружит с пользователем.

Вышесказанное не отрицает того, что иногда массив хранит записи, т.е. сложные типы данных, определённые с помощью typedef:

  typedef struct{
    ...
  } complex_record;

Помните, что в тексте программы на Си можно задавать массивы практически неограниченной длины. Поскольку памяти нынче у компьютеров много, на одномерный массив, скорее всего, хватит. По меньшей мере, если вы пользуетесь системами из раздела 1.1. В старых компиляторах Borland C массивы больше одного сегмента памяти ( > 64Кб) приводили к труднообъяснимым ошибкам. Впрочем, и 64 килобайта - не мало!

Все используемые массивы следует определить в преамбуле программы с кратким описанием того, что в каждом из них храниться.

Иногда, впрочем, желательно, чтобы память под массив бралась у системы. Тогда следует написать отдельную процедуру free_arrays(), которая освобождает все динамически распределённые массивы, и обеспечить её вызов при выходе из программы с помощью функции atexit(free_arrays). Это гарантирует возвращение данных системе даже если программа вываливается аварийно по exit(1).

Вопреки распространённому мнению, размеры динамически распределённых массивов не являются фиксированными: их можно поменять (скажем, в сторону увеличения) с помощью функции realloc(): при этом положение блока данных может измениться (т.е. изменится указатель), но все данные будут перенесены корректно.

Иногда естественной структурой данных является, всё-таки, не массив, а список: когда, например, требуется реализовать арифметику многочленов многих переменных. Или эмулировать сложную систему массового обслуживания из пользователей, перемещающихся от одного прибора к другому.

На практике удобен в быстрой безошибочной реализации и использовании кольцевой однонаправленный список с заголовком. В таком списке всегда есть хотя бы один выделенный узел, называемый заголовком. Каждый узел имеет указатель на следующий, а указатель из последнего узла ведёт к заголовку:

Наличие заголовка чрезвычайно упрощает программирование, поскольку список никогда не пуст. Это на порядок уменьшает число проверок, необходимых для работы с элементами списка. Кольцевые списки легко склеивать друг с другом. При наличии указателя на какой-нибудь элемент списка можно вставлять узлы как после, так и до этого указателя (в последнем случае потребуется обменять значения, хранящиеся в узлах и передвинуть указатель). С помощью кольцевого списка очень просто реализовать собственный распределитель памяти (см. раздел 3.4). Зачем нужен свой распределитель памяти? Системные обладают следующими неустранимыми недостатками

а) занимают неизвестное время при вызове,

б) под каждый запрос выделяется не столько памяти, сколько запрошено, а количество, округлённое вверх до какого-нибудь двоично-шестнадцатирично-круглого числа,

в) в Си стандартными методами невозможно проверить, вся ли память освобождена.

Поэтому следует память распределять крупными кусками, в каждом из которых хранить списки из узлов фиксированного размера. Следует хорошо подумать и признаться себе, что в процессе работы программы размер этих узлов известен и неизменен! Кроме того, структуры данных с переменной длиной как раз и следует упрятать в списки!

Свой распределитель памяти реализовать просто: нужно все узлы хранить в массиве, а в незанятых узлах организовать кольцевой список с заголовком в нулевом элементе. Когда все свободные ячейки кончаются, необходимо расширить массив с помощью realloc(). При этом, память, занятая под массив, должна освобождаться автоматически с помощью функции, зарегистрированной в atexit(). В момент освобождения можно посчитать число узлов в списке свободной памяти и тем самым проконтролировать, что все списки программой корректно освобождены. Время при выделении ещё одной ячейки конечно за исключением тех случаев, когда приходится расширять массив с помощью realloc().

Пример распределителя: list/onedlist.c

Идея «закольцовывания» позволяет усовершенствовать и реализацию деревьев (см. [3,раздел 2.3.1] про threded trees).

Вообще, с помощью кольцевых списков можно реализовать любую динамическую структуру данных. Только прежде стоит подумать: а надо ли? Не проще ли воспользоваться стандартными библиотеками? Существует большое количество реализаций Б-деревьев, АВЛ-деревьев и прочих стандартных структур данных. Но если в задаче нужны подобные «стандартные структуры», то, возможно, следует сменить язык программирования.

1.5  Сортировка

  for(i=0;i<n;i++)
    for(j=i+1;j<n;j++)
      if(a[i]>a[j]) t=a[i], a[i]=a[j], a[j]=t;

1.6  Циклы и функции

1.7  Техника конечных автоматов

  enum {scan, slash, comment} state;
   for(state=scan;;){
     c=getc(f);
     switch(state==scan){
       case scan:  if(c=='/') {state=slash; break;}
              putc(c,stdout); 
             break;
       case slash: if(c=='/') {state=comment; break;}
              putc('/', stdout); 
              putc(c,stdout); 
             break;
       case comment: if(c=='\n') state=scan;
              putc(c,stdout); 
             break;
     } 
   }

1.8  Приоритет операций

1.9  С чего начать программу?

int main(){
  init();
  run();
  done();
  return 0;
}

1.10  Самопроверка

#include <assert.h>

...

int f(int n, int m, float **a){
  assert(m<=n);
  ...
}

1.11  Двумерные массивы

1.12  Построение комбинаторных объектов (перебор)

Очень часто под полным перебором имеется ввиду порождение всех возможных комбинаций из небольшого числа объектов. В самом простом случае перебор можно свести к процедуре прибавления единицы к числу из N цифр, которое представлено в системе счисления с основанием M. Однако это действие запрограммировать сложнее, чем написать рекурсивную функцию try1:

#define DigMax 100
int D[DigMax];
int N=2, M=3;

void print_digs(){
  int j;
  for(j=0;j<N;j++) printf("%3d ",D[j]);
  printf("\n");
}

void try1(int i){
  if(i>=N){print_digs(); return;}
  for(D[i]=0;D[i]<M;D[i]+=1)
    try1(i+1);
}

Если в этом числе запретить повторяющиеся цифры, то получится программа, генерирующая все неповторяющиеся комбинации из N цифр каждая из которых принимает значения от 0 до M-1. В частном случае N=M получится программа, генерирующая все перестановки. Для того, чтобы отсечь повторяющиеся числа необходимо при установке цифры D[i] проверять, что она ещё не занята. Это эффективно реализуется введением массива occupied:

int occupied[DigMax];
void try2(int i){
  if(i>=N){print_digs(); return;}
  for(D[i]=0;D[i]<M;D[i]+=1) {
    if(occupied[D[i]]) continue;
    occupied[D[i]]=!0;
    try2(i+1);
    occupied[D[i]]=0;
  }
}

int generate_combinat(){
  int i; 
  printf("Все варианты:\n"); 
  try1(0);
  for(i=0;i<N;i++) occupied[i]=0;
  printf("Без повторных цифр:\n"); 
  try2(0);
}

Комбинации:            Без повторных цифр:
  0   0                  0   1            
  0   1                  0   2            
  0   2                  1   0            
  1   0                  1   2            
  1   1                  2   0            
  1   2                  2   1            
  2   0 
  2   1 
  2   2 

В качестве упражнения напишите try3(), которая будет выводить все варианты расстановки ферзей, не бьющих друг друга, на шахматной доске N×N.

Из вышесказанного ясно, что рекурсия может сильно упростить программирование перебора, причём с точки зрения затрат времени и памяти она практически эквивалентна нерекурсивному решению: в самом деле, слишком много комбинаторных объектов не обработаешь, а стек вызовов нынче длинный, если только в него не пихать десять параметров... О порождении комбинаторных объектов без рекурсии хорошо написано во [1,глава 2].

1.13  Двумерная рекурсия

Тогда мы инициализируем массив was[0..n-1][0..m-1] нулями и вызываем функцию mark.

float a[n][m];
int was[n][m];

float S=0;

void mark(int i, int j){
  if((i<0)||(i>=n)) return;
  if((j<0)||(j>=m)) return;
  if(was[i][j]) return;
  was[i][j]=!0;
  if(a[i][j]!=0) S+=1.0;
  mark(i+1,j); 
  mark(i-1,j);
  mark(i,j+1);
  mark(i,j-1);
}

1.14  Динамическое программирование

#define MaxN 20
int Cnk[Maxn+1][Maxn+1];

void generate_Cnk(int maxn){
  int n,k;
  int maxk=maxn;
  assert(maxn<=MaxN);
  for(n=0;n<=maxn;n++) {
    Cnk[n][0]=Cnk[n][n]=1;
  }
  for(n=1;n<=maxn;n++){
    for(k=1;k<n;k++)
      Cnk[n][k]=Cnk[n-1][k-1]+Cnk[n-1][k];
  }
}

1.15  Промежуточные версии программы

1.16  Оценка времени работы

Как оценить время работы программы при каком-нибудь большом n?

Нужно запустить программу 2 раза, чтобы определить параметры C и a. Точнее,

logT » logC+alogn

Поэтому, зная время выполнения T₁ при n=n₁ и время выполнения T₂ при n=n₂, получаем систему линейных уравнений

logT1 » logC+a logn1,

logT2 » logC+a logn2,

на logC и loga. Решение находится легко:

a=  log(T2/T1) log(n2/n1 .

logC=  log(n2)log(T1)-log(n1)log(T2) log(n2/n1) ,

Подобная техника называется экстраполяцией. Её можно использовать, например, когда программа вычисляет значение интеграла I по сетке порядка n и сходимость медленная, то есть, I_n-I_n+1 » C/n^a, где I_n - значение интеграла на сетке порядка n. Это означает обычно, что

In=I+  C1 n +  C2 n +ј+  Cs ns .

Запустив программу s+1 раз при разных значениях n=n₀, ..., n_s мы получаем систему линейных уравнений на I, C₁, ..., C_s.

Для вычисления I можно воспользоваться следующей итеративной процедурой. Определим a_m,0=I_nm, m=0,ј,s. И далее для i=1, ..., s положим

am,i=am,i-1+  am,i-1-am-1,i-1 (nm/nm-1)i-1 ,  для m=i,ј,s.

А теперь надо взять I=a_s,s. Нетрудно сообразить, что мы всего-навсего решили систему уравнений относительно I.

2  Упрощающие приёмы программирования в Си

2.1  Программа из нескольких файлов

prog: $(patsubst   %.c,%.o,$(wildcard   *.c))
        gcc -lm -g $^ -o $@
%.o: %.c
        gcc -c -g -MD $<
include $(wildcard   *.d)

Описанный makefile весьма полезен, когда используются функции из пакета «Численных рецептов для Си» [2]: нужно просто скопировать файлы с нужными функциями в свою директорию плюс файлы nr.h, nrutil.h, nrutil.c. После этого нужно написать собственную prog.c программу, в которой есть функция main.

2.2  Вывод двумерного массива в виде таблицы

  for(i=0;i<n;i++,printf("\n"))
    for(j=0;j<m;j++)
      printf(" %3d", a[i][j]);

2.3  Перенаправление ввода/вывода внутри программы

#include <stdio.h>

...

main(){
  freopen("input.txt","rt", stdin);
  freopen("output.txt","wt", stdout);
  ...
}

2.4  getc

2.5  Ускорение чтения из файла

2.6  О EOF

 int  c=getc(f);

2.7  Хитрая функция sscanf

{
 char s[1000], r[1000];
  ...
  sscanf(s,"%[^=\n]",res);
  ...
}

Пользоваться функцией sscanf для разбора строк безопаcно, если размер строк-результатов не меньше длины сканируемой строки. С использованием vsscanf можно автоматически контролировать соответствие формата считываемым данным: см. раздел 3.6. Функциями scanf или fscanf для считывания строк не стоит пользоваться никогда. Альтернативу даёт функция scanline, описанная в разделе 3.6.

2.8  Отладка

Чтобы отлаживать программу, нужно компилировать её с отладочной информацией (с флагом -g см. раздел 2.1). После этого в XEmacs надо переключиться в буфер, содержащий текст программы и затем в меню Tools выбрать опцию Debug (GDB). В появившемся окошке со списком файлов в текущей директории следует выбрать исполнимый файл программы и GDB откроется прямо внутри XEmacs. После этого необходимо набрать в приглашении GDB ключевую команду b main, вставляющую точку останова на вызове функции main().

(gdb) b main

(gdb) r

Если окошко (gdb) находится в фокусе ввода, то оно подменяет стандартные графические кнопки своими. Пользуясь этими кнопками можно проходить программу по шагам. Можно вставлять дополнительные точки останова с помощью команды b <имя функции> или b <номер строки>. Остальные инструкции смотрите в справке.

Одно полезное указание для работающих в Юникс. Если программа (cкажем, по имени prog) аварийно завершила работу (с ошибкой сегментации, например), то система сбрасывает на диск файл core. Набрав затем в командной строке

yozhik:~/prog$ gdb prog core

3  Примеры

3.1  Слова из разных букв

#include <stdio.h>
#include <string.h>
#define max_length 10000
unsigned char s[max_length];
int in_s[256];

int allletersdiff(unsigned char *s){
 int i,n;
  memset(in_s,0,sizeof(*in_s)*256);
  while(*s){
    if(in_s[*s]) return 0;
    in_s[*s++]=!0;
  }
  return !0;
}

int main(){
 unsigned char *t;
  while(fgets(s,max_length,stdin)){
    t=strchr(s,'\n');
    if(t) *t=0;
    if(strlen(s)<14) {continue;}
    if(allletersdiff(s)){
      printf("%d %s\n",strlen(s), s);
    }
  }
}

Начало входного файла:

в
ввечеру
ввезённый
ввезти
ввек
вверг
ввергнувший
ввергнул
ввергнулся
ввергнутый
...

Результат работы, отформатированный в 2 столбца

14 взбудоражиться          14 подстёгиваемый  
14 возбуждающийся          15 предоставляющий 
14 воспламеняющий          14 представляющий  
14 вразумительный          14 проглядывающий  
14 вымогательский          14 проклюнувшийся  
14 гладкошёрстный          14 промелькнувший  
14 гипотермальный          14 промахнувшийся  
15 четырёхполюсник         14 продлевающийся  
15 четырёхугольник         14 проблематичный  
14 звукосниматель          14 пробуждавшийся  
14 злорадствующий          14 пробуждающийся  
14 здравомыслящий          14 разгильдяйство  
14 захлебнувшийся          15 раболепствующий 
14 захлопнувшийся          14 трезвомыслящий  
14 защёлкнувшийся          14 угледобывающий  
14 отделывающийся          15 узкоспециальный 
14 обёртывающийся          14 утверждающийся  
14 повреждающийся          14 демпфироваться  
15 поздравительный         14 десятирублёвка  
14 покряхтывающий          14 десятирублёвый  
14 поразвлёкшийся          14 десятиугольный  
14 похрустывающий          14 долженствующий  
14 подвергающийся          14 экзаменующийся  
14 подчёркиваемый          14 безрасчётливый  
14 подчёркивается          16 благоденствующий
14 подчёркиваться          14 блаженствующий  
14 подчёркиваются          16 бумагопрядильный
14 подключавшийся          14 сокрушительный  
14 подхлестнувший

./diffletters <russian.dict.stripped >res

3.2  Равносоставленные слова

Программа sort.c:

#include <stdio.h>
#define max_length 10000
unsigned char s[max_length];
void sort(unsigned char *s){
 int i,j,n;
 unsigned char tmp;
  n=strlen(s);
  for(i=0;i<n;i++)
    for(j=i+1;j<n;j++)
      if(s[i]>s[j]) tmp=s[i], s[i]=s[j], s[j]=tmp;
}

int main(){
 unsigned char *t;
  while(fgets(s,max_length,stdin)){
    t=strchr(s,'\n');
    if(t) *t=0;
    printf("%d %s ",strlen(s), s);
    sort(s);
    printf("%s\n",s);
  }
}

Начало входного файла:

в
ввечеру
ввезённый
ввезти
ввек
вверг
ввергнувший
ввергнул
ввергнулся
ввергнутый
...

1 в в
7 ввечеру ееруввч
9 ввезённый ёейннввыз
6 ввезти еитввз
4 ввек еквв
5 вверг егрвв
11 ввергнувший егийнрувввш
8 ввергнул еглнрувв
10 ввергнулся еглнярсувв
10 ввергнутый егйнртуввы
...

Скрипт finddupl, объединяющий равносоставленные слова:

#!/usr/local/bin/perl -w
use strict;
my %sorted=();
my %duplsize=(); #здесь храним длину слова

my ($size,$sr,$wrd);
print STDERR "Читаем файл...";
while(<STDIN>){
  ($size,$wrd,$sr)= split ;
  if(!exists($sorted{$sr})){
    $sorted{$sr}=$wrd;
    next;
  }

  $duplsize{$sr}=$size;
  $sorted{$sr}.=" ".$wrd;

}

print STDERR "\b\b Выдаём результаты...";
my $key;
foreach $key(sort {$duplsize{$b}<=>$duplsize{$a}} keys %duplsize){
  printf "%d %s\n",$duplsize{$key}, $sorted{$key};
}
print STDERR "\b\b Закончили.\n";

Начало выходного файла:

18 термоэлектрический электрометрический электротермический
16 недоброкачествен доброкачественен
16 гидрометрический гидротермический
16 заинтересованный анестезированный
15 голографический графологический
15 пантеистический антисептический
15 ратификационный тарификационный
15 нерасторжимость старорежимность
14 изометрический изотермический
14 раскрашиваться расшаркиваться
14 распустившийся расступившийся
14 геометрический геотермический
14 катеростроение ракетостроение
14 заинтересовать анестезировать
14 несоответствен соответственен
14 ратифицировать тарифицировать
13 пропитывающий притопывающий
13 разламываются размалываются
13 залоснившийся заслонившийся
13 кавитационный активационный
13 красовавшийся расковавшийся
13 разламываться размалываться
13 разводившийся раздвоившийся
13 разламывается размалывается
13 оправдавшийся продававшийся
13 развалившийся разливавшийся
13 оправлявшийся провалявшийся
13 одобрительный ободрительный
13 перебросивший посеребривший
13 равновесность своенравность
13 неприкосновен прикосновенен
13 кисломолочный молочнокислый
13 неподвластный подставленный
13 несоразмерный соразмеренный
13 разгоревшийся разогревшийся
13 оскорбившийся скоробившийся
13 отпросившийся построившийся
13 электрометрия электротермия
13 непосредствен посредственен
13 нерасторжимый старорежимный
12 повадившийся подавившийся
12 навалившийся наливавшийся
12 перевираться перевариться
12 постраничный просчитанный
12 каустический акустический
12 воспрещаться просвещаться
12 заминающийся занимающийся
12 коренившийся искоренявший
12 освещающийся совещающийся
12 заголившийся изолгавшийся
12 переламывать перемалывать
12 озлобившийся обозлившийся
12 воспрещающий всепрощающий просвещающий
12 зародившийся изодравшийся
12 числительный сличительный
12 непритворный притворенный
12 расторгаться растрогаться
12 воротившийся отворившийся
12 недружествен дружественен
12 двухведёрный двухвёдерный
12 сплотившийся столпившийся
12 плакирование прокаливание
12 претвориться проветриться
12 почудившийся подучившийся
12 воспрещавший просвещавший
12 кредиторский директорский
12 опустившийся оступившийся
12 расстающийся срастающийся
12 обвалившийся обливавшийся
12 отправленный потравленный
12 освещавшийся совещавшийся
12 полуведёрный полувёдерный
12 закопавшийся показавшийся
12 запоминаться позаниматься
12 запиравшийся запарившийся
12 крестовидный декстриновый
12 неопрятность потерянность
12 распуститься расступиться
12 восторгаться сторговаться
12 припустивший приступивший
12 велосипедный непоседливый
12 пригнувшийся присягнувший
12 восторженный створоженный
12 поручившийся проучившийся
12 несвоевремен своевременен
12 переваливший переливавший
12 подраставший пострадавший
12 пропустивший проступивший
12 оплавившийся повалившийся поливавшийся
12 завалившийся заливавшийся
12 воспрещённый просвещённый
12 перевалиться переливаться
12 добивавшийся добавившийся
12 ковариантный актированный
12 расставшийся сраставшийся
12 оплешивевший пошевеливший
12 прорастивший простиравший
12 просветитель терпеливость
12 вывалившийся выливавшийся
12 перевидавший передавивший
12 вертикальный кильватерный
...

./diffletters <russian.dict.stripped |./finddupl >resall

3.3  Конечный автомат для декодирования Quoted-Printable букв

void read_qp(FILE*in,FILE*out){
  enum {scan, eq, dig} state;
  int c;
  int dig1;
  state=scan;
  for(;;){
    c=getc(in);
    if(state==scan){
      if(c==EOF){return;}
      if(c=='='){state=eq; continue;}
      putc(c,out);
      continue;
    } 
    if(state==eq){
      if(c==EOF){ putc('=', out); return;}
      if(isxdigit(c)){ dig1=c; state=dig; continue;}
      if(c=='\n'){state=scan; continue;}
      putc('=',out);
      putc(c,out);
      state=scan;
      continue;
    }
    if(state==dig){
      if(c==EOF){ putc('=', out); putc(dig1, out); return;}
      if(isxdigit(c)){ 
        int cc=getxdigit(dig1)*16+getxdigit(c);
        putc(cc,out); 
        state=scan; 
        continue;
      }
      putc('=', out); 
      putc(dig1, out);
      putc(c,out);
      state=scan;
      continue;
    }
  }
}

3.4  Распределитель памяти

Исходный код: list/onedlist.c

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

// Собственный распределитель памяти для записей 
// фиксированного типа value_t. Записи типа value_t 
// хранятся с массиве node_t node[], и заключены
// при этом в элементы типа node_t. функция get_node()
// распределяет один элемент в массиве node и его и 
// возвращает, функция free_node(node_id p) возвращает 
// узел p в список свободной памяти. 
//
// Адресоваться к элементам необходимо с помощью 
// макросов VALUE(p) и NEXT(p): понятное дело, 
// выделенные элементы можно связывать в список.

// Определяем данные. Это определение можно вынести в .h файл
typedef int monom_id;
typedef struct{
  int v,d;
} variable_t;

// А теперь определяем внутренние структуры данных
typedef monom_id node_id;

typedef variable_t value_t;

//А вот здесь можно поставить и 
//typedef union
//Только тогда пользователю самому придётся ссылки 
//определять в value_t, а оно ему надо?
typedef struct {
  value_t value;
  node_id next;
} node_t;

static node_t *node=NULL;
static int node_size;
#define NEXT(p) (node[p].next)
#define VALUE(p) (node[p].value)


#define node_init_size 1000
#define node_increase_size 1000

void free_node_array(){
  //Проверка, что все узлы освобождены
  node_id p; int i;
  for(i=1,p=NEXT(0); p; p=NEXT(p) ) i++;
  if(node_size!=i)
    fprintf(stderr, 
            "В свободном списке обнаружено аж %d узлов\n"
            "а должно быть %d.\nВсе %d возвращены системе.\n",
            i,node_size,i);
  //вот и проверили...

  free(node);
}

Самая главная функция: распределяет 1 узел, индекс которого и возвращает.

Все свободные узлы в массиве node[] связаны в кольцевой список с заголовком в node[0].

node_id get_node(void){
  int p;
  // при первом вызове массива node вообще нету. 
  if(node==NULL) {
    int i;
    // пытаемся его распределить
    node=(node_t*) malloc(node_init_size*sizeof(node_t));
    if(node==NULL){
      fprintf(stderr,"Не хватает памяти для массива node!\n");
      exit(1);
    }
    // регистрируем функцию, его освобождающую, которая
    // автоматически будет вызываться при выходе из
    // программы (даже если он аварийный по exit(1)).
    atexit(free_node_array);

    node_size=node_init_size;
    // Закольцевали весь массив в список свободной памяти
    for(i=0;i<node_init_size-1;i++) NEXT(i)=i+1;
    NEXT(i)=0;
  }
  // Так случилось, что в списке свободной памяти только
  // node[0] и остался.
  if(NEXT(0)==0){
    int i; 
    node_t *realloced_node;
    // пытаемся выделить памяти побольше
    realloced_node=(node_t*)
      realloc(node,(node_size+node_increase_size)*sizeof(node_t));
    if(!realloced_node){
      fprintf(stderr,
         "Не хватает памяти для увеличения массива node!\n");
      exit(1);
    }
    fprintf(stderr,"Заняли ещё памяти под массив node...\n");
   
    node=realloced_node;
    // Теперь добавленные узлы цепляем в кольцевой список
    // с началом в нуле
    NEXT(0)=node_size;
    for(i=node_size;i<node_size+node_increase_size-1;i++)
      NEXT(i)=i+1;
    NEXT(i)=0;
    node_size+=node_increase_size; 
  }
  //Наконец, добрались до того, что функция и должна делать!

  // Возвращаем пользователю элемент, следующий за нулём
  p=NEXT(0);
  // Нулевой элемент указывает нынче на следующий
  NEXT(0)=NEXT(p); 
  // А сам возвращаемый элемент закольцован на себя.
  NEXT(p)=p;
  return p;
}

Возвращение блудного узла в список свободных.

void free_node(node_id p){
  // Вставляем блудный узел сразу после нуля.
  NEXT(p)=NEXT(0);
  NEXT(0)=p;
}

Одночлен, хранящийся в массиве v преобразуется в кольцевой список, память под который распределяется с помощью get_node().

Переменные в массиве v должны быть отсортированы по значениям идентификаторов

monom_id make_monom(variable_t v[]){
  node_id p,q1,q;
  int i;
 
  p=get_node();
  q1=p;
  VALUE(p).v=0;
  for(i=0;v[i].v;i++){
    q=get_node();
    NEXT(q1)=q; 
    VALUE(q)=v[i];
    assert(VALUE(q).v>VALUE(q1).v);
    NEXT(q)=p;
    q1=q;
  }
  return p;
}

Возвращение одночлена в список свободной памяти.

void free_monom(monom_id p){
  node_id p1,p2;
  p1=p;
  do{
    p2=p1;
    p1=NEXT(p1);
    free_node(p2);
  }while(p1!=p);
}

Печать одночлена. Предполагается, что идентификаторы переменных являются попросту номерами букв.

void print_monom(monom_id p){
  node_id q;
  for(q=NEXT(p);q!=p; q=NEXT(q))
    printf("%c^{%d}",(char) VALUE(q).v, VALUE(q).d);
}

А вот и пример одночлена, с идентификаторами в виде кодов букв. и функции main, тестирующей распределение одночленов.

static variable_t x[7]= {{'a', 2}, {'b', 1}, {'c',3}, 
           {'x', 2}, {'y', 1}, {'z',3}, {0,0}};

int main(){
  monom_id  monom=make_monom(x);
  monom_id monoms[1000];
  int i;
  
  // Распределяем память под ещё 1000 одночленов
  // с целью проверить алгоритм на надёжность
  for(i=0;i<1000;i++)
    monoms[i]=make_monom(x);


  // Освобождаем память
  for(i=0;i<1000;i++)
    free_monom(monoms[i]);

  print_monom(monom);
  printf("\n");
  free_monom(monom);
}

3.5  Считывание строки неограниченной длины

К дополнительным недостаткам fgets относится ограниченность при считывании строк из файла. Здесь приведён текст функции, которая считывает строку неограниченной длины, выделяя под строку дополнительную память при необходимости. Опять-таки, если памяти не хватает, то вызывается exit(1).

В файле "rt.h" подключены стандартные библиотеки ввода вывода.

Исходный код: lib/fgetlong.c. Вся библиотека: lib/

#include "rt.h"
  ///////////////////////////////////////////////////////
 /////              ЗАГРУЗКА ДАННЫХ                /////
///////////////////////////////////////////////////////

//Строка из входного файла может быть неограниченной длины
//которая вначале имеет initial_size байт и увеличивается
//по мере необходимости на incremental_size
#define initial_size 1000
#define incremental_size 1000

static char *s=NULL;
static int length_of_string=0; static int current_size=0;

void free_s(){
  free(s);
  //fprintf(stderr,"Системе возвращена память, занятая под буфер"
  //        " чтения входного файла: %d байт\n",current_size);
}

//возвращает адрес длинной строки. Гарантируется, что адрес строки 
//не изменится между вызовами функций fgetlongs
char *longs_pointer(void){
  return s;
}

//добавляет букву к строке s
void addchar(int c){
  if(length_of_string==current_size) {
    if(s){
     char*news;
      news=(char*)realloc(s, current_size+incremental_size);
      if(news==NULL){
        char t[200];
        sprintf(t,
          "Ошибка при realloc в функции addchar() --- не удалось запросить\n"
          "%d байт динамически распределяемой памяти",current_size);
        perror(t); exit(1);
      }
      current_size+=incremental_size;
      s=news;
    } else {
      s=(char*)malloc(initial_size);
      if(s==NULL){ perror("Ошибка при malloc в функции addchar()"); exit(1);}
      current_size=initial_size;
      if(atexit(free_s)){
           perror("Ошибка регистрации функции atexit(free_s)\n"); exit(1);
      }
    }
  }
  s[length_of_string]=c;
  length_of_string++;
}

// если файл кончился или произошла какая ошибка, возвращает 0 иначе ---
// длину считанной строки. В длину строки всегда включается последний символ 
// \n, ежели он присутствует. Если параметр line!=NULL, то значение *line 
// увеличивается на 1. Это позволяет считать число прочитанных,строк 
int fgetlongs(FILE *f,int *line){
  int c;
  length_of_string=0;
  for(;;){
    c=fgetc(f);
    if(c==EOF){
      if(length_of_string){
        addchar(0); if(line) (*line)++; return length_of_string;
      }
      return 0;
    }
    if(c=='\n'){
      addchar('\n');
      addchar(0); if(line) (*line)++;  return length_of_string;
    }
    addchar(c);
  }
}

3.6  Считывание строки неограниченной длины с автоматическим контролем числа прочитанных параметров.

Исходный код: lib/scanline.c. Вся библиотека: lib/

#include "rt.h"
#include <assert.h>


int scanline(FILE*f, int *line, char *fmt,...){
  va_list argptr;
  int cnt,args_to_scan=0;
  int characters_read;
  char *scanfmt=fmt;

  assert(line);
  if(!(characters_read=fgetlongs(f,line))){
    fprintf(stderr,"Неожиданный конец файла после строки %d\n"
            "ожидаемый формат следующей строки (номер %d): %s\n",
            *line,(*line)+1,fmt);
    exit(1);
  }
  while((scanfmt=strchr(scanfmt,(unsigned char)'%'))!=NULL){
    scanfmt++;args_to_scan++;
  }
  va_start(argptr,fmt);
  cnt=nvsscanf(characters_read,longs_pointer(),fmt,argptr);
  va_end(argptr);
  if(cnt!=args_to_scan){
    fprintf(stderr,"Ошибка в строке %d\n"
            "ожидаемый формат строки: %s\n"
            "a в файле конфигурации : %s\n",*line,fmt,longs_pointer());
    exit(1);
  }
  return cnt;
}

Пример использования:

#include "rt.h"
#include <assert.h>
int n;
int line=0;
void load_data(FILE*f){
 int i,j,k;
  scanline(f,&line,"n=%d",&n);
  if(n <=0){
    fprintf(stderr,"Неправильное число %d в строке %d\n",n,line);
    exit(1);
  }
}

В заключение приведём описание файла rt.h. Исходный код: lib/rt.h. Вся библиотека: lib/

#ifndef _RT_H
#define _RT_H
#include <stdlib.h>
#include <stdio.h>
#include <stdarg.h>

////////////////////////////////////////////////////////
//Функции nvsscanf.c
/* 
   myvsscanf ()

   аналог функции vsscanf. Проблема в том, что функция vsscanf 
   не входит в стандарт ANSI C и потому в некоторых компиляторах 
   не определена 
 */
int myvsscanf (const char *string, const char *format, va_list args);
/* 
   nsscanf ()

   аналог функции vsscanf, но с явным ограничением длины
   сканируемой строки. То есть, строка считается окончившейся не по 
   символу с нулевым кодом, а по определению имеет длину
   string_length
 */
int nvsscanf (int string_length, const char *string,  
              const char *format, va_list args);
//Функции nvsscanf.c
////////////////////////////////////////////////////////


////////////////////////////////////////////////////////
// Функции из fgetlong.c

//возвращает адрес длинной строки. Гарантируется, что адрес строки 
//не изменится между вызовами функций fgetlongsс() или fgetlongs()
char *longs_pointer(void);

// Функция fgetlongsc считывает длинную строку из файла в строку, 
// доступную затем по адресу longspointer()

// если файл кончился или произошла какая ошибка, возвращает 0 иначе ---
// длину считанной строки. В длину строки всегда включается последний символ 
// \n, ежели он присутствует. Если параметр line!=NULL, то значение *line 
// увеличивается на 1. Это позволяет считать число прочитанных,строк 
int fgetlongs(FILE *f,int *line);

// Функции из fgetlong.c
////////////////////////////////////////////////////////

////////////////////////////////////////////////////////
// Функции из scanline.c
// Считывает строку с помощью fgetlongs(), сканирует аргументы,
// в случае несовпадения числа аргументов с действительно прописанным
// вываливается по exit(1).
// *line должен указывать на целое число, хранящее количество 
// уже прочитанных строк и инициализируемое нулём.
int scanline(FILE*f, int *line, char *fmt,...);
// Функции из scanline.c
////////////////////////////////////////////////////////
#endif

3.7  Разбор командной строки

К сожалению, часто необходимо конвертировать строковые аргумены в числовые, причём требуется, чтобы аргументы лежали в заданном диапазоне. Следующие функции проверяют аргумент на нахождение в заданном диапазоне. Если min_val > max_val, то допустимы все числа, большие или равные min_val.

static unsigned int get_int_range(char *integer,
                                  const char *optionname,
                                  int min_val,
                                  int max_val){
  char *s=integer;
  static char *range_errmsg=
    "Mistake in option %s: an integer in the range %d..%d is expected\n";
  static char *min_range_err_msg=
    "Mistake in option %s: an integer not less than %d is expected\n";
  char *errmsg;
  int n;
  if(min_val<=max_val)
    errmsg=range_errmsg;
  else
    errmsg=min_range_err_msg;

  if(*s == '-'){
    s++;
  }
  while(*s){
    if(isdigit(*s)){
      s++;
    }else{
      fprintf(stderr,errmsg,optionname,min_val,max_val);
      exit(ERROR_WRONG_ARGUMENT);
    }
  }
  if(sscanf(integer,"%d", &n)!=1){
    fprintf(stderr,errmsg,optionname,min_val,max_val);
    exit(ERROR_WRONG_ARGUMENT);
  }
  if(n<min_val){
    fprintf(stderr,errmsg,optionname,min_val,max_val);
    exit(ERROR_WRONG_ARGUMENT);
  }
  if((min_val<=max_val)&&(n>max_val)){
    fprintf(stderr,errmsg,optionname,min_val,max_val);
    exit(ERROR_WRONG_ARGUMENT);
  }
  return n;
}

// не забудьте подключить <ctype.h> <stdlib.h>
// пример вызова:
//  thickness=get_double_range(optarg,"--thickness",1e-50,0);

double get_double_range(char *real,
                        const char *optionname,
                        double min_val,
                        double max_val){
  char *s=real;
  static char *range_errmsg=
    "Mistake in option %s: a real number in the range %lf..%lf is expected\n";
  static char *min_range_err_msg=
    "Mistake in option %s: a real number not less than %lf is expected\n";
  char *errmsg;
  double n;
  if(min_val<=max_val)
    errmsg=range_errmsg;
  else
    errmsg=min_range_err_msg;

  if(*s == '-'){
    s++;
  }
  while(*s){
    if(isdigit(*s)||(toupper(*s)=='E')||(toupper(*s)=='D')
         ||(*s=='.')||(*s=='+')||(*s=='-')){
      s++;
    }else{
      fprintf(stderr,errmsg,optionname,min_val,max_val);
      exit(ERROR_WRONG_ARGUMENT);
    }
  }
  if(sscanf(real,"%lf", &n)!=1){
    fprintf(stderr,errmsg,optionname,min_val,max_val);
    exit(ERROR_WRONG_ARGUMENT);
  }
  if(n<min_val){
    fprintf(stderr,errmsg,optionname,min_val,max_val);
    exit(ERROR_WRONG_ARGUMENT);
  }
  if((min_val<=max_val)&&(n>max_val)){
    fprintf(stderr,errmsg,optionname,min_val,max_val);
    exit(ERROR_WRONG_ARGUMENT);
  }
  return n;
}

4  Дальнейшее чтение

Рекомендуется также замечательная книга по алгоритмам на строках, последовательностях и деревьях [5], которая снабжена также текстами программ доступными со страницы http://www.cs.ucdavis.edu/~gusfield/.

Книги [6,3,7] хорошо бы прочитать для общего образования, но на практике они мало пригодны, поскольку затраты времени на реализацию изложенных там алгоритмов зачастую слишком велики. Кроме того, в силу недоведённости алгоритмов до машины, в них встречаются серьёзные ошибки. Недаром к книгам Д.Кнута имеются сотни страниц исправлений! Реализации простых алгоритмов уже есть в [2] в виде, лёгком для адаптации (только надо внимательно прочитать введение в [2]!).

В качестве справочника по Си можно (с осторожностью!) пользоваться текстом [4], основное достоинство которого состоит в доступности через сеть: сам текст написан довольно сумбурно. Куча информации по Си выложена (на английском) по адресу http://www.lysator.liu.se/c/.

Многие рекомендуют книгу [8], но я её не рекомендую: слишком большой объём текста плюс примеры на новом языке (Modula-2), не лишённые ошибок, лишь затрудняют адаптацию алгоритмов в жизни.

СПИСОК ЛИТЕРАТУРЫ

[1]

А. Шень. Программирование: теоремы и задачи. МЦНМО, Москва, 1995. Свободно распространяемый текст, доступен со страницы автора ftp://ftp.mccme.ru/users/shen/progbook/.

[2]

William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery. Numerical recipes in C. Cambridge University Press, Cambridge, second edition, 1992. The art of scientific computing, доступна на www.nr.com, http://lib-www.lanl.gov/numerical/index.html, http://www.ulib.org/webRoot/Books/Numerical_Recipes/bookcpdf.html.

[3]

Д. Кнут. Искусство программирования для ЭВМ. Том 1: Основные алгоритмы. Издат. «Мир» Москва, 1977. Перевод Г. П. Бабенко, Е. Г. Белага and Л. В. Майстрова, под редакцией К. И. Бабенко.

[4]

А. Богатырёв. Хрестоматия по программированию на Си в Unix. 1992-95. Свободно распространяемый текст, доступен с http://lib.ru/CTOTOR/book.txt.

[5]

Dan Gusfield. Algorithms on strings, trees, and sequences. Cambridge University Press, Cambridge, 1997. Computer science and computational biology, реализации алгоритмов можно найти на http://www.cs.ucdavis.edu/~gusfield/.

[6]

А. Ахо, Дж. Хопркрофт, and Дж. Ульман. Структуры данных и алгоритмы. Изд. дом <Вильямс>, Москва, 2000.

[7]

Дональд К. Кнут. Искусство программирования для ЭВМ. Том 3: Сортировка и поиск. «Мир», Москва, 1978. [Sorting and searching], Перевод Н.И.Вьюковой, В.А.Галатенко и А.Б.Ходулева под редакцией с предисловием Ю.М.Баяковского и В.М.Старкмана. Частично есть в интернете по адресу http://lib.ru/CTOTOR/KNUT/.

[8]

Н. Вирт. Алгоритмы + структуры данных = программы. Мир, Москва, 1984.

Примечания:

¹У Перла есть, впрочем заметный недостаток при обработке текстов: в нём сложно реализовать посимвольную обработку строк - и здесь Си впереди планеты всей.