Једноструко спрегнуте листе – задаци

1. Написати програм на програмском језику C за унос целих бројева у једноструко спрегнуту листу. У програму дефинисати ф-је за следеће радње над низовима:
– Унос на почетак листе
– Унос на крај листе
– Уређивање листе
– Уметање елемената у уређену листу
– Исписивање листе
– Изостављање елемената из листе
– Одређивање дужине листе
– Брисање свих елемената из листе
У main() функцији предвиди мени уз помоћ кога ће се вршити избор неке од горе описаних функција. Излазак из програма је условљен избором 0 у менију.
Програм треба да буде модуларног типа чији су модули: lista.h i lista.c

/* lista.h - Definicije paketa funkcija za obradu lista    */

#include <stdio.h>
#include <stdlib.h>
typedef struct elem{int broj; struct elem *sled;}Elem;
int duz (Elem *lst) {                   /* Broj elemenata liste.          */
  int n = 0; while (lst) { n++; lst = lst -> sled; } return n;
}

void pisi (Elem *lst) {                 /* Ispisivanje liste.             */
  while (lst) { printf ("%d ", lst->broj); lst = lst -> sled; }
}

Elem *na_pocetak (Elem *lst, int b) {   /* Dodavanje na pocetak.          */
  Elem *novi = malloc (sizeof(Elem));
  novi->broj = b; novi->sled = lst;
  return novi;
}

Elem *na_kraj (Elem *lst, int b) {      /* Dodavanje na kraj.             */
  Elem *novi = malloc (sizeof(Elem));
  novi->broj = b; novi->sled = NULL;
  if (!lst) return novi;
  else {
    Elem *tek = lst;
    while (tek->sled) tek = tek->sled;
    tek->sled = novi;
    return lst;
  }
}

Elem *citaj1 (int n) {   /* Citanje liste stavljajuci brojeve na pocetak. */
  Elem *prvi = NULL; int i;
  for (i=0; i<n; i++) {
    Elem *novi = malloc (sizeof(Elem));
    scanf ("%d", &novi->broj); novi->sled = prvi;
    prvi = novi;
  }
  return prvi;
}

Elem *citaj2 (int n) {   /* Citanje liste stavljajuci brojeve na kraj.    */
  Elem *prvi = NULL, *posl = NULL; int i;
  for (i=0; i<n; i++) {
    Elem *novi = malloc (sizeof(Elem));
    scanf ("%d", &novi->broj); novi->sled = NULL;
    if (!prvi) prvi = novi; else posl->sled = novi;
    posl = novi;
  }
  return prvi;
}

Elem *umetni (Elem *lst, int b) {       /* Umetanje u uredjenu listu.     */
  Elem *tek = lst, *pret = NULL, *novi;
  while (tek && tek->broj < b) { pret = tek; tek = tek->sled; }
  novi = malloc (sizeof(Elem));
  novi->broj = b; novi->sled = tek;
  if (!pret) lst = novi; else pret->sled = novi;
  return lst;
}

void brisi (Elem *lst) {                /* Brisanje svih elemenata liste. */
  while (lst) { Elem *stari = lst; lst = lst->sled; free (stari); }
}

Elem *izostavi (Elem *lst, int b){ /* Izostavljanje svakog pojavljivanja. */
  Elem *tek = lst, *pret = NULL;
  while (tek)
    if (tek->broj != b) { pret = tek; tek = tek->sled; }
    else {
      Elem *stari = tek;
      tek = tek->sled;
      if (!pret) lst = tek; else pret->sled = tek;
      free (stari);
    }
  return lst;
}

/* lista.c - Ispitivanje paketa funkcija za obradu lista.                */

#include "lista.h"
#include <stdio.h>

void main () {
  Elem *lst = NULL; int kraj = 0, izbor, broj, n;
  while (!kraj) {
    printf ("\n1. Dodavanje broja na pocetak liste\n"
              "2. Dodavanje broja na kraj liste\n"
              "3. Umetanje broja u uredjenu listu\n"
              "4. Izostavljanje broja iz liste\n"
              "5. Brisanje svih elemenata liste\n"
              "6. Citanje uz obrtanje redosleda brojeva\n"
              "7. Citanje uz cuvanje redosleda brojeva\n"
              "8. Odredjivanje duzine liste\n"
              "9. Ispisivanje liste\n"
              "0. Zavrsetak rada\n\n"
              "Vas izbor? "
            );
    scanf ("%d", &izbor);
    switch (izbor) {
    case 1: case 2: case 3: case 4:
      printf ("Broj?      "); scanf ("%d", &broj);
      switch (izbor) {
      case 1: /* Dodavanje broja na pocetak liste: */
        lst = na_pocetak (lst, broj); break;
      case 2: /* Dodavanje broja na kraj liste: */
        lst = na_kraj (lst, broj);    break;
      case 3: /* Umetanje broja u uredjenu listu: */
        lst = umetni (lst, broj);     break;
      case 4: /* Izostavljanje broja iz liste: */
        lst = izostavi (lst, broj);   break;
      }
      break;
    case 5: /* Brisanje svih elemenata liste: */
      brisi (lst); lst = NULL; break;
    case 6: case 7: /* Citanje liste: */
      printf ("Duzina?    "); scanf ("%d", &n);
      printf ("Elementi?  "); brisi (lst);
      switch (izbor) {
      case 6: /* uz obrtanje redosleda brojeva: */
        lst = citaj1 (n); break;
      case 7: /* uz cuvanje redosleda brojeva: */
        lst = citaj2 (n); break;
      }
      break;
    case 8: /* Odredjivanje duzine liste: */
      printf ("Duzina=    %d\n", duz (lst)); break;
    case 9: /* Ispisivanje liste: */
      printf ("Lista=     "); pisi (lst); putchar ('\n'); break;
    case 0: /* Zavrsetak rada: */
      kraj = 1; break;
    default: /* Pogresan izbor: */
      printf ("*** Neozvoljeni izbor! ***\a\n"); break;
    }
  }
}

2. Саставити у програмском језику C следеће функције за обраду једноструко спрегнутих листа:
– обртање редоследа елемената листе (замена првог елемента са последњим, другог са претпоследњим…)
– спајање две уређене листе у једну уређену листу коришћењем елемената почетних листи.
Саставити програм за испитивање претходних функција. За помоћне радње користити модул lista.h из претходног задатка.

/* lista2.c - Jos funkcija za obradu lista.                               */

#include "lista.h"
#include <stdio.h>

Elem *obrni (Elem *lst) {          /* Obrtanje redosleda elemenata.       */
  Elem *tek = lst, *pret = NULL;
  while (tek) {
    Elem *sled = tek->sled;
    tek->sled = pret;
    pret = tek;
    tek = sled;
  }
  return pret;
}

void uredi (Elem *lst) {           /* Uredjivanje liste.                  */
  Elem *i, *j;
  for (i=lst; i; i=i->sled)
    for (j=i->sled; j; j=j->sled)
      if (j->broj < i->broj) {
        int b = i->broj; i->broj = j->broj; j->broj = b;
      }
}

Elem *fuzija (Elem *lst1, Elem *lst2) { /* Fuzija dve uredjene liste.     */
  Elem *lst = NULL, *posl=NULL, *tek;
  while (lst1 && lst2) {
    if (lst1->broj < lst2->broj) { tek = lst1; lst1 = lst1->sled; }
      else                       { tek = lst2; lst2 = lst2->sled; }
    tek->sled = NULL;
    if (!lst) lst = tek; else posl->sled = tek;
    posl = tek;
  }
  if (lst1) { if (!lst) lst = lst1; else posl->sled = lst1; }
    else    { if (!lst) lst = lst2; else posl->sled = lst2; }
  return lst;
}

void main () {                     /* Glavni program.                     */
  while (1) {
    Elem *lst1, *lst2, *lst3; int n;
    printf ("Duzina prve liste?    "); scanf ("%d", &n);
  if (n <=0) break;
    printf ("Elementi prve liste?  "); lst1 = citaj2 (n);
    if (n == 0) putchar ('\n');
    printf ("Duzina druge liste?   "); scanf ("%d", &n);
  if (n <=0) break;
    printf ("Elementi druge liste? "); lst2 = citaj2 (n);
    if (n == 0) putchar ('\n');
    lst1 = obrni (lst1);
    printf ("Obrnuta prva lista:   "); pisi (lst1); putchar ('\n');
    lst2 = obrni (lst2);
    printf ("Obrnuta druga lista:  "); pisi (lst2); putchar ('\n');
    uredi (lst1);
    printf ("Uredjena prva lista:  "); pisi (lst1); putchar ('\n');
    uredi (lst2);
    printf ("Uredjena druga lista: "); pisi (lst2); putchar ('\n');
    lst3 = fuzija (lst1, lst2);
    printf ("Fuzija obe liste:     "); pisi (lst3); printf ("\n\n");
    brisi (lst3);
  }
}

Оставите одговор

Попуните детаље испод или притисните на иконицу да бисте се пријавили:

WordPress.com лого

Коментаришет користећи свој WordPress.com налог. Одјавите се /  Промени )

Google+ photo

Коментаришет користећи свој Google+ налог. Одјавите се /  Промени )

Слика на Твитеру

Коментаришет користећи свој Twitter налог. Одјавите се /  Промени )

Фејсбукова фотографија

Коментаришет користећи свој Facebook налог. Одјавите се /  Промени )

Повезивање са %s