?.
Метод Хоара нестійкий.) Динамічний список
Динамічний список - це послідовність структур, кожна з яких містить посилання, що зв'язує її з іншою структурою. Для організації списків використовуються структури, що складаються з двох смислових частин - інформаційної та додаткової. Інформаційна частина містить підлягає обробці інформацію, в додатковій знаходяться покажчики на подальшу або попередню структуру списку:
Structst {char data [20]; * next; };// Указательнаструктуруst
Тут при описі покажчика використовуємо ще не описаний об'єкт structst * next, який буде служити посиланням на сусідній елемент списку. Залежно від методу доступу до елементів лінійного списку розрізняють різновиду лінійних списків. Найбільш відомі списки, звані стеком і очередью.Стек можна представити як стопку книг на столі, де додавання або взяття нової книги можливо тільки зверху. Таким чином, операції додавання і видалення елемента, а також доступу до елементу виконуються тільки в кінці списку. Черга - це список, де елементи видаляються з початку списку, а додаються в кінець списку (як звичайна черга в магазині).
Приклад створення і перегляду стека. Нехай потрібно ввести деяку послідовність символів, що закінчується крапкою, і надрукувати її у зворотному порядку.
# include lt; stdio.h gt;
# include lt; stdlib.h gt;
# include lt; conio.h gt;
{charch; * next;
} stack; ()
{stack * p, * q;
char a;
p=NULL; (CLS);
//заполненіестека
{a=getchar ();
q=(stack *) malloc (sizeof (stack));
q- gt; next=p;=q;
q- gt; ch=a;
} while (a!=. );
//друк стека c звільненням пам'яті
do
{p=q- gt; next; (q);=p; (% c , p- gt; ch);
} while (p- gt; next!=NULL); (); 0;
}
Приклад створення і перегляду одинзв'язного списку. Нехай потрібно помістити в список прізвища і вивести їх у порядку черговості. У даному прикладі використовуємо оператори new і delete.
# include lt; stdio.h gt;
# include lt; conio.h gt;
# include lt; stdlib.h gt;
{char data [20]; * next;} spis; * create (void);// функціясозданіяспіска (spis * head);// Функція перегляду спіска_spis (spis * head);// функціяосвобожденіяпамяті ()
{system ( CLS ); * head;// Адресголовиспіска=create (); (head); _ spis (head); ();
} * create (void)
{spis * p, * pred, * h;
//pred - покажчик на попередню структуру
//h- покажчик на перший структуру
h=pred=newspis;// виділення пам'яті для першої структури
printf ( fam: ); scanf (% s raquo ;, pred- gt; data); {p=new spis; ( n fam: ); scanf (% s raquo ;, p- gt; data); - gt; next=p;// посилання з попередньої на поточну
pred=p;// Збереження адреси поточної
printf ( закінчити? y/n );
} while (getch ()= y ); gt; next=NULL; h;
} list (spis * head)
{spis * p;
p=head;
while (p!=NULL)//поки не кінець списку
{printf ( n fio:% s , p- gt; data);=p- gt; next;// Просування за списком
}
} _ spis (spis * head)
{spis * p, * q;=p=head; (p!=NULL)
{= q- gt; next; q;=p;
}=NULL;
}
3. Код програми
# include lt; locale.h gt;
# include lt; stdio.h gt;
# include lt; stdlib.h gt;
# include lt; string.h gt;
# include lt; conio.h gt;
# include lt; iostream gt ;; N; [1 000]; i=0; S
{S * next, * head; [20]; name [20]; group [8]; d [11]; KS1; KS2;
} spis;
voidAdd (spis ** p, intflag) {// процедура для додавання студента в список
spis * temp=newspis; (flag == 1)
cout lt; lt; Введіть нового студента: lt; lt; endl lt; lt...
