Шпаргалка по "Программированию и компьютерам"

 1. Методы поиска и сортировки в массивах.

 Методы  сортировки

 Сортировка  выбором

 Шаги  алгоритма:

 1. находим  минимальное значение в текущем  списке

 2. производим  обмен этого значения со значением  на первой позиции

 3. теперь  сортируем хвост списка, исключив  из рассмотрения уже отсортированный первый элемент

 template <class T>

 void Selection_sort( T a[], const int n )

 {

     for( int i=0; i<n-1; ++i )

     {

         int min = i;

         for( int j=i+1; j<n; ++j )     

             if( a[min] > a[j] ) min = j;

         T tmp = a[i];

         a[i] = a[min];

         a[min] = tmp;

     }

 }

 Сортировка  пузырьком

 Алгоритм  состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.

 template <class T>

 void Bubble_sort( T a[], const int n )

 {

     for (int i = n-1; i>0; --i)

         for (int j = 0; j<i; ++j)

             if (a[j] > a[j+1])

             {

                  swap(a[j], a[j+1]);

             }

 }

 Сортировка  вставками

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

 typedef int array_type; /* или typedef char array_type;*/

    void insertSort(array_type a[], int length) {

       int i, j;

       array_type value;

       for (i = 1; i < length; i++) {

           value = a[i];

           for (j = i-1; (j >= 0) && (a[j] > value); j--) {

               a[j+1] = a[j];

           }

           a[j+1] = value;

       }

   }

 Методы  поиска

 Двоичный (бинарный) поиск (также известен, как метод деления пополам) — алгоритм нахождения заданного значения монотонной (невозрастающей или неубывающей) функции. Поиск основывается на теореме о промежуточных значениях

 int function BinarySearch (Array A, int Lb, int Ub, int Key);

   begin

   do forever

     M = Lb + (Ub-Lb)/2;

     if (Key < A[M]) then

       Ub = M - 1;

     else if (Key > A[M]) then

       Lb = M + 1;

     else

       return M;

     if (Lb > Ub) then

     return -1;

   end;

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

 int function LinearSearch (Array A, int L, int R, int Key);

 begin

   for X = L to R do begin

     if A[X] = Key then

       return X

   end;

   return -1; // элемент не найден

 end;

 Поиск в ширину — метод обхода и разметки вершин графа.

 Поиск в ширину выполняется в следующем  порядке: началу обхода s приписывается  метка 0, смежным с ней вершинам — метка 1. Затем поочередно рассматривается  окружение всех вершин с метками 1, и каждой из входящих в эти окружения вершин приписываем метку 2 и т. д.

 push(start);

  while not empty do begin

    tek:=pop; 

    for i:=1 to a[tek,0] do if not used[a[tek,i]] then begin

      used[a[tek,i]]:=true;

      push(a[tek,i]);

    end;

   end; 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 2.Структурный тип данных. Поиск в таблицах (массивы структур).

 Структура - это набор из одной или более  переменных, возможно различных типов, сгруппированных под одним именем для удобства обработки. (В некоторых  языках, самый известный из которых  паскаль, структуры называются "записями").

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

 STRUCT DATE (

   INT  DAY;

   INT  MONTH;

   INT  YEAR;

   INT  YEARDAY;

   CHAR MON_NAME[4];

   );

 Член  определенной структуры может быть указан в выражении с помощью конструкции вида

   имя_структуры.член

 IF (STRCMP(D.MON_NAME, "AUG") == 0) ...

 Структуры могут быть вложенными; учетная карточка служащего может фактически выглядеть так:

 STRUCT  PERSON  (

      CHAR NAME[NAMESIZE];

      CHAR ADDRESS[ADRSIZE];

      LONG ZIPCODE;   /* почтовый индекс */

      LONG SS_NUMBER; /* код соц. Обеспечения */

      DOUBLE SALARY;  /* зарплата */

      STRUCT DATE BIRTHDATE; /* дата рождения */

      STRUCT DATE HIREDATE; /* дата поступления

       на работу */

   );

 Структуры особенно подходят для управления массивами связанных переменных. Рассмотрим, например, программу подсчета числа вхождений каждого ключевого слова языка "C". Нам нужен массив символьных строк для хранения имен и массив целых для подсчета. одна из возможностей состоит в использовании двух параллельных массивов KEYWORD и KEYCOUNT:

   CHAR *KEYWORD [NKEYS];

   INT  KEYCOUNT [NKEYS];

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

 CHAR *KEYWORD;

 INT  KEYCOUNT;

 и, следовательно, имеется массив пар.

 Каждый  элемент массива является структурой. Это можно было бы записать и так:

 STRUCT KEY  (

    CHAR *KEYWORD;

     INT  KEYCOUNT;

   );

 STRUCT KEY KEYTAB [NKEYS];

 Поиск в массиве структур осуществляется аналогично поиску в обычных массивах.

 Пример  функции поиска в массиве структур.

 void search(int count, int size, key *st)

 {

   for(int I; i<size; i++)

    {

         if(st->keykount > count)

            printf(“%s %i”, st->keykount, st->keyword);

    }

 } 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 3. Операции над строками.

 Строки - это последовательность символов, заключенная в кавычки. В конце  каждой строки компилятор добавляет  нулевой символ, представляемый управляющей  последовательностью \0.

 Строка  описывается как массив символов. Число элементов массива равно  числу элементов в строке плюс символ конца строки (\0). Символьная строка в программе может располагаться  на нескольких строках. Для переноса используется обратная дробная черта с последующим нажатием клавиши ввод. Обратная дробная черта игнорируется компилятором, и следующая строка считается продолжением предыдущей.

 Для работы со строками очень удобно использовать указатели.

 Описание  функции работы со строками содержится в файле <string.h> библиотеки стандартных функций.

 Соединение  последовательностей символов.

 char *strcat(char *s1,char *s2)

 Функция возвращает указатель на полученную строку.

 Поиск первого вхождения символа в  строку.

 char *strchr(char *s,int c)

 Функция просматривает строку (обращение к строке с помощью указателя s)

 и ищет символ с кодом c. Возвращает указатель  на найденный символ или пустое

 значение.

 Сравнение строк.

 int strcmp(char *s1,char *s2)

 Сравниваются  две указанные строки. Результат - переменная типа int:

 s1<s2 отрицательное значение

 s1==s2 значение 0

 s1>s2 положительное значение

 4.Копирование  символов.

 char *strcpy(char *s1,char *s2)

 Копируется  последовательность символов, указанная параметром s1 по адресу s2.

 Определение длины строки (без завершающего нуля).

 int strlen(char *s) 

 5. Переменные типа  «указатель». Организация  списковых структур.

 Указатель – переменная, значением которой  является адрес памяти другой переменной.

 Инициализация указателей:

 присваивание указателю адреса существующего объекта

 с помощью  операции получения адреса (int *p = &a – в указатель записывается адрес а)

 с помощью  значения другого инициализированного  указателя (int *r = p)

 с помощью  имени массива или функции, которые  трактуются как адрес (int b[10]; int *t  = b – присваивание адреса начала массива)

 присваивание  указателю адреса области памяти в явном виде (char* vp = (char *)0xB8000000)

 присваивание  пустого значения (int *r = NULL)

 выделение участка динамической памяти и присваивания её адреса указателю.  Переменные, под которые в процессе выполнения программы выделяется память, называются динамическими, а все остальные – статическими. Синтаксис операции выделения памяти: