Файл: Алгоритмы и структуры данных-Кр-ИВТ-3у-Назаренко.pdf

6 

  return Success; 

} 

int p4(Link* Start, Link*& Find, int Key) 

{ 

  Link* Cur = Start->next; 

  int Success = 0; 

  while (Cur != Start && !Success) 

  { 

    if (Cur->Value == Key) 

    { 

      Find = Cur; 

      Success = 1; 

      break; 

    } 

    Cur = Cur->next; 

  } 

  return Success;  

} 

Процедуры сортировки 

void s1(float* item, int n) 

{ 

  int a,b; 

  float buf; 

  for (a = 1; a<n; ++a) 

    for (b = n-1; b>=a; --b) 

      if (item[b-1]>item[b]) 

      { 

        buf = item[b-1]; 

        item[b-1] = item[b]; 

        item[b] = buf; 

      } 

} 

7 

void s2(float* item, int n) 

{ 

  int a,b,c; 

  float buf; 

  int change; 

  for (a = 0; a<n-1; ++a) 

  { 

    change = 0; 

    c = a; 

    buf = item[a]; 

    for (b = a+1; b<n; ++b) 

      if (item[b]<buf) 

      { 

        buf = item[b]; 

        c = b; 

        change = 1; 

      } 

    if (change) 

    { 

      item[c] = item[a]; 

      item[a] = buf; 

    } 

  } 

} 

void s3 (float* item, int n) 

{ 

  int a,b; 

  float buf; 

  for (a = 1; a<n; ++a) 

  { 

     buf = item[a]; 

     b = a-1; 

     for (b = a-1; b>=0 && buf < item[b]; b--) 

8 

       item[b+1] = item[b]; 

    item[b+1] = buf; 

  } 

} 

void s4(float* item, int n) 

{ 

  int step[5] = {9,5,3,2,1}; 

  int i,j,k,h; 

  float buf; 

  for (k = 0; k<ST; k++) 

  { 

    h = step[k]; 

    for (i = h; i<n; i++) 

    { 

      buf = item[i]; 

      for(j = i-h; buf<item[j] && j>=0; j-=h) 

        item[j+h] = item[j]; 

      item[j+h] = buf; 

    } 

  } 

} 

void s5(float* item, int left, int right) 

{ 

  int i,j; 

  float comp,buf; 

  i = left; j = right; 

  comp = item[(left+right)/2]; 

  do { 

    while (item[i]<comp && i<right) 

      i++; 

    while (comp<item[j] && j>left) 

      j--; 

9 

    if (i<=j) { 

      buf = item[i]; 

      item[i] = item[j]; 

      itme[j] = buf; 

      i++; j--; 

    } 

  } while(i<=j); 

  if (left<j) 

    s5(item, left, j); 

  if (i<right) 

    s5(item, i, right); 

} 

10 

Пример выполнения контрольной работы 

Пусть номер студенческого билета 083457. 

Тогда две последние цифры: A = 5, B = 7. 

Сумма цифр A + B = 5 + 7 = 12. 

(A+B)

4

 = 30. Последняя цифра = 0. 

1. Тип списка – 1-связный кольцевой. 

2. Тип данных – длинные беззнаковые целые числа (unsigned long int). 

3. Тип звена списка: 

struct Zveno { 

  unsigned long int Data; 

  Zveno *next; 

}; 

Процедуры работы со связным списком выбираются по типу списка – для 1-связного 

кольцевого списка. 

4. Процедура добавления звена: 

void i1(Zveno* Pred, unsigned long int data) 

{ 

  Zveno* Loc = new Link1; 

  Loc->Data = data; 

  Loc->next = Pred->next; 

  Pred->next = Loc; 

} 

5. Процедура удаления звена: 

void d2(Zveno* Pred) 

{ 

  Zveno* Loc; 

  Loc = Pred->next; 

  Pred->next = Loc->next; 

  delete Loc; 

}