Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #define inf 1 << 29
- typedef int elementtype;
- typedef struct celltag {
- elementtype element;
- struct celltag* next;
- } celltype;
- typedef celltype* List;
- typedef celltype* position;
- position LiEnd( List L ) { // vraca pokazivac na zadnju element liste
- position p=L;
- while ( p->next != NULL )
- p = p->next;
- return p;
- }
- position LiMakeNull( List *Lp ) { //pretvara listu u praznu listu i vraca pokazivac na zadnji element
- *Lp = ( celltype* )malloc( sizeof(celltype) );
- (*Lp)->next = NULL;
- return( *Lp );
- }
- void LiInsert( elementtype x, position p, List *L ) { //ubacuje element iza pozicije p
- position temp = p->next;
- p->next = ( celltype* ) malloc( sizeof(celltype) );
- p->next->element = x;
- p->next->next = temp;
- }
- void LiDelete( position p, List *L ) { //briše element iza p
- position temp = p->next;
- p->next = p->next->next;
- free( temp );
- }
- position LiFirst( List L ){
- return L;
- }
- position LiNext( position p, List L ) {
- return p->next;
- }
- position LiPrevious( position p, List L ) {
- position temp = L;
- while ( temp->next != p )
- temp->next = temp->next->next;
- return temp;
- }
- elementtype LiRetrive( position p, List L ) {
- return p->next->element;
- }
- void ispisi(List l) {
- position temp = LiFirst(l);
- while (LiNext(temp, l) != NULL) {
- printf("%d ", LiRetrive(temp, l));
- temp = LiNext(temp, l);
- }
- }
- int odrediVelicinu(List l) {
- int ret = 0;
- position temp = LiFirst(l);
- while (LiNext(temp, l) != NULL) {
- ret++;
- temp = LiNext(temp, l);
- }
- return ret;
- }
- List Listcopy(List l1, int vel1, List l2, int vel2, List *nova) {
- position prvi = LiFirst(l1);
- position drugi = LiFirst(l2);
- List ret;
- LiMakeNull(&ret);
- while (prvi != LiEnd(l1) || drugi != LiEnd(l2)) {
- if (prvi == LiEnd(l1)) {
- LiInsert(LiRetrive(drugi, l2), LiEnd(ret), &ret);
- drugi = LiNext(drugi, l2);
- }
- else if (drugi == LiEnd(l2)) {
- LiInsert(LiRetrive(prvi, l1), LiEnd(ret), &ret);
- prvi = LiNext(prvi, l1);
- }
- else {
- int broj1 = LiRetrive(prvi, l1);
- int broj2 = LiRetrive(drugi, l2);
- if (broj1 < broj2) {
- LiInsert(broj1, LiEnd(ret), &ret);
- prvi = LiNext(prvi, l1);
- }
- else {
- LiInsert(broj2, LiEnd(ret), &ret);
- drugi = LiNext(drugi, l2);
- }
- }
- }
- LiMakeNull(nova);
- position temp = LiFirst(ret);
- while (LiNext(temp, ret) != NULL) {
- LiInsert(LiRetrive(temp, ret), LiEnd(*nova), nova);
- temp = LiNext(temp, ret);
- }
- }
- int main (void) {
- int n, i, a, oznaka1, oznaka2;
- int jesamUzeo[20];
- int velicina[20];
- int broj[20];
- List l[20];
- scanf("%d", &n);
- for (i=0; i<2*n; ++i) {
- LiMakeNull(&l[i]);
- jesamUzeo[i] = -1;
- velicina[i] = 0;
- }
- for (i=0; i<n; ++i) {
- jesamUzeo[i] = 0;
- scanf ("%d", &a);
- while (a != -1) {
- velicina[i]++;
- LiInsert(a, LiEnd(l[i]), &l[i]);
- scanf("%d", &a);
- }
- }
- int qq, j;
- for (qq=0; qq<n-1; ++qq) {
- int zadnji = 1;
- for (i = 0; i < n; ++i) {
- if (jesamUzeo[i] == 0) {
- printf("L%d: ", zadnji, velicina[i]);
- ispisi(l[i]);
- printf("\n");
- broj[i] = zadnji;
- zadnji++;
- }
- }
- int mini1 = inf, mini2=inf;
- int broj1=-1, broj2=-1;
- for (i = 0; i < n; ++i) {
- if (jesamUzeo[i] == 0) {
- if (mini1 > velicina[i]) {
- mini1 = velicina[i];
- broj1 = i;
- oznaka1 = broj[i];
- }
- }
- }
- for (i = 0; i < n; ++i) {
- if (jesamUzeo[i] == 0) {
- if (mini2 > velicina[i] && i != broj1) {
- mini2 = velicina[i];
- broj2 = i;
- oznaka2 = broj[i];
- }
- }
- }
- printf("Spajam L%d i L%d\n", oznaka1 < oznaka2 ? oznaka1 : oznaka2, oznaka1 < oznaka2 ? oznaka2 : oznaka1);
- Listcopy(l[broj1 < broj2 ? broj1 : broj2], velicina[broj1 < broj2 ? broj1 : broj2], l[broj1 >= broj2 ? broj1 : broj2], velicina[broj1 >= broj2 ? broj1 : broj2], &l[broj1 < broj2 ? broj1 : broj2]);
- velicina[broj1 < broj2 ? broj1 : broj2] = odrediVelicinu(l[broj1 < broj2 ? broj1 : broj2]);
- jesamUzeo[broj1 < broj2 ? broj2 : broj1] = 1;
- }
- printf("L1: "); ispisi(l[0]); printf("\n");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement