Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- ZRS - C++ radionica
- TEMA : Dvostruko povezana cirkularna lista
- Zadatak: Tjelesni
- Autor: Kristijan Burnik, udruga informaticara Bozo Tezak
- */
- #include <iostream>
- #include <cstdlib>
- #include <vector>
- using namespace std;
- // cvor u dvostrukoj povezanoj listi
- typedef struct node {
- int index;
- node * prev;
- node * next;
- node() {
- next = NULL;
- prev = NULL;
- }
- node(int _index) {
- index = _index;
- next = NULL;
- prev = NULL;
- }
- } node;
- // ovdje cemo pohraniti cvorove (alocirati memoriju)
- vector<node> v;
- int main() {
- int n,p;
- // unosimo ulazne podatke
- cin >> n >> p;
- // pripremi memoriju za cvorove
- v.resize(n);
- // stvori prvi cvor
- v[0] = node(1);
- // stvori sve ostale cvorove i povezi ih
- for (int i = 1; i < n ; i++) {
- // popuni cvor sa index = i + 1
- v[i] = node(i+1);
- // sljedeci od prethodnog je trenutni
- v[i-1].next = &v[i];
- // prethodni od trenutnog
- v[i].prev = &v[i-1];
- }
- // uzmi reference na prvi i zadnji cvor u krugu
- node * prvi = &v[0];
- node * zadnji = &v[n-1];
- // povezi prvi cvor sa zadnjim u listi (zaokruzi listu)
- // lista je od ovog koraka cirkularna!
- zadnji->next = prvi;
- prvi->prev = zadnji;
- int steps = 0 ;
- // putujemo redom po svim stolcima ukrug dok je broj stolaca veci od P
- for ( node * t = prvi ; n > p ; t = t->next ) {
- // ako je p-ti korak i ako nismo na 1. stolcu, uklanjamo ga
- if ( (steps % p) == 0 && t->index != 1) {
- // cvor a je prethodni od trenutnog
- // cvor b je sljedeci od trenutnog
- node * a, *c;
- a = t->prev;
- c = t->next;
- // jednostavno "preskacemo" trenutni cvor
- a->next = c;
- c->prev = a;
- // smanjujemo broj stolaca
- n--;
- // ispisujemo koji stolac smo izbacili
- cout << t->index << " ";
- }
- // brojimo korake
- steps++;
- }
- cout << endl;
- // ispisi preostale stolce, njih P
- int i = 0;
- for ( node * t = prvi ; i < p ; t = t->next , i++ ) {
- cout << t->index << " ";
- }
- cout << endl;
- system("pause");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement