W katalogu domowym utworzyć podkatalog listy2int. Utworzyć w nim plik Makefile i pozostałe pliki, po jednym dla każdej funkcji:
/*
* main.h
*
* Plik naglowkowy.
*/
#include <stdio.h>
#include <stdlib.h>
/* typ logiczny */
typedef int bool;
#define TRUE 1
#define FALSE 0
typedef int Cargo;
typedef struct node Node;
/* definicja struktury */
struct node {
Cargo data; /* dane elementu */
struct node *next; /* wskaznik do nastepnego elementu */
struct node *prev; /* wskaznik do poprzedniego elementu */
};
int cmp_cargo(Cargo a, Cargo b);
bool add_head(Node *dlist[], Cargo item);
/* Dodanie elementu na poczatek listy */
bool add_tail(Node *dlist[], Cargo item);
/* Dodanie elementu na koniec listy */
bool add_list(Node *dlist[], Cargo item);
/* Wstawienie elementu do listy (lista posortowana) */
bool find_list(Node *dlist[], Cargo item);
/* Szukanie elementu na liscie */
void print_list(Node *dlist[]);
/* Wypisanie zawartosci listy */
int count_list(Node *dlist[]);
/* Zliczenie dlugosci listy */
bool del_head(Node *dlist[]);
/* Usuniecie elementu z poczatku listy */
bool del_tail(Node *dlist[]);
/* Usuniecie elementu z konca listy */
bool del_list(Node *dlist[], Cargo item);
/* Usuniecie danego elementu listy */
Cargo get_head(Node *dlist[]);
/* Usuniecie elementu z poczatku listy - zwraca cargo */
Cargo get_tail(Node *dlist[]);
/* Usuniecie elementu z konca listy - zwraca cargo */
#define is_empty(dlist) ((dlist[0] == NULL) ? TRUE : FALSE)
/* bool is_empty(Node *dlist[]); */
/*
* main.c
*/
#include "main.h"
int main(void)
{
Cargo number = 67; /* przykladowa liczba do sprawdzania */
/* Inicjalizujemy pusta liste */
Node *dlist[2] = { NULL, NULL };
if (add_list(dlist,22) == FALSE)
fprintf(stderr,"add_list: Brak pamieci\n");
if (add_list(dlist,11) == FALSE)
fprintf(stderr,"add_list: Brak pamieci\n");
if (add_list(dlist,44) == FALSE)
fprintf(stderr,"add_list: Brak pamieci\n");
print_list(dlist);
if (find_list(dlist,number) == FALSE)
printf("Nie znaleziono %d na liscie\n", number);
else
printf("Znaleziono %d na liscie\n", number);
while (!is_empty(dlist))
del_head(dlist);
return 0;
}
/*
* add_head.c
*
* Kod umieszczajacy na liscie nowy element.
* Element bedzie na poczatku listy.
*/
#include "main.h"
bool add_head(Node *dlist[], Cargo item)
{
Node *new_item; /* wskaznik do nowej struktury na liscie */
Node *head = dlist[0];
Node *tail = dlist[1];
/* przydzielenie pamieci nowej strukturze */
new_item = malloc(sizeof(Node));
if (new_item == NULL)
return FALSE;
new_item->data = item; /* wstawienie liczby do pola struktury */
if (head == NULL) { /* pusta lista */
new_item->next = NULL; /* */
new_item->prev = NULL; /* */
head = new_item; /* wskaznik head pokazuje nowa strukture */
tail = new_item; /* wskaznik tail pokazuje nowa strukture */
} else {
new_item->next = head; /* */
new_item->prev = NULL; /* */
head->prev = new_item; /* wskaznik head pokazuje nowa strukture */
head = new_item; /* nowy poczatek */
}
dlist[0] = head;
dlist[1] = tail;
return TRUE;
}
/*
* add_tail.c
*
* Kod umieszczajacy na liscie nowy element.
* Element bedzie na koncu listy.
*/
#include "main.h"
bool add_tail(Node *dlist[], Cargo item)
{
Node *new_item; /* wskaznik do nowej struktury na liscie */
Node *head = dlist[0];
Node *tail = dlist[1];
/* przydzielenie pamieci nowej strukturze */
new_item = malloc(sizeof(Node));
if (new_item == NULL)
return FALSE;
new_item->data = item; /* wstawienie liczby do pola struktury */
if (tail == NULL) { /* pusta lista */
new_item->next = NULL; /* */
new_item->prev = NULL; /* */
head = new_item; /* wskaznik head pokazuje nowa strukture */
tail = new_item; /* wskaznik tail pokazuje nowa strukture */
} else { /* koniec listy */
new_item->next = NULL; /* */
new_item->prev = tail; /* */
tail->next = new_item; /* wskaznik tail pokazuje nowa strukture */
tail = new_item; /* nowy koniec */
}
dlist[0] = head;
dlist[1] = tail;
return TRUE;
}
/*
* add_list.c
*
* Kod umieszczajacy na liscie nowy element.
* Lista bedzie od razu posortowana.
*/
#include "main.h"
bool add_list(Node *dlist[], Cargo item)
{
Node *current; /* za punktem wstawienia */
Node *new_item; /* wskaznik do nowej struktury na liscie */
Node *head = dlist[0];
Node *tail = dlist[1];
/* przydzielenie pamieci nowej strukturze */
new_item = malloc(sizeof(Node));
if (new_item == NULL)
return FALSE;
new_item->data = item; /* wstawienie liczby do pola struktury */
if (head == NULL) { /* wstawienie do pustej listy */
new_item->next = NULL; /* */
new_item->prev = NULL; /* */
head = new_item; /* wskaznik head pokazuje nowa strukture */
tail = new_item; /* wskaznik tail pokazuje nowa strukture */
dlist[0] = head;
dlist[1] = tail;
return TRUE;
}
current= head; /* szukamy miejsca wstawienia */
while (current != NULL && cmp_cargo(current->data, item) < 0)
current = current->next;
if (current == NULL) { /* wstawiamy na koniec listy */
new_item->next = NULL;
new_item->prev = tail;
tail->next = new_item;
tail = new_item; /* nowy koniec listy */
} else if (current == head) { /* wstawiamy przed poczatek listy */
new_item->next = head;
new_item->prev = NULL;
head->prev = new_item;
head = new_item; /* nowy poczatek listy */
} else { /* jestesmy w srodku listy */
new_item->next = current;
new_item->prev = current->prev;
current->prev->next = new_item;
current->prev = new_item; /* */
}
dlist[0] = head;
dlist[1] = tail;
return TRUE;
}
/*
* del_head.c
*
* Usuwanie elementu z poczatku listy.
*/
#include "main.h"
bool del_head(Node *dlist[])
{
Node *head = dlist[0];
Node *tail = dlist[1];
if (head == NULL)
return FALSE; /* lista jest juz pusta */
if (head == tail) { /* jeden element na liscie */
free(head);
head = NULL;
tail = NULL;
} else { /* sa co najmniej dwa elementy na liscie */
head = head->next;
free(head->prev);
head->prev = NULL;
}
dlist[0] = head;
dlist[1] = tail;
return TRUE;
}
/*
* del_tail.c
*
* Usuwanie elementu z konca listy.
*/
#include "main.h"
bool del_tail(Node *dlist[])
{
Node *head = dlist[0];
Node *tail = dlist[1];
if (tail == NULL)
return FALSE; /* lista jest juz pusta */
if (head == tail) { /* jeden element na liscie */
free(tail);
head = NULL;
tail = NULL;
} else { /* sa co najmniej dwa elementy na liscie */
tail = tail->prev;
free(tail->next);
tail->next = NULL;
}
dlist[0] = head;
dlist[1] = tail;
return TRUE;
}
/*
* del_list.c
*/
#include "main.h"
bool del_list(Node *dlist[], int item)
{
Node *head = dlist[0];
Node *tail = dlist[1];
Node *current; /* wskaznik do struktury na liscie */
current = head;
while (current != NULL && cmp_cargo(current->data, item) != 0)
current= current->next;
if (current == NULL)
return FALSE; /* nie znalazl i nie skasowal */
/* Tutaj element jest znaleziony, ale moze byc w roznych miejscach */
if (head == tail) { /* jeden element na liscie */
free(head);
head = NULL;
tail = NULL;
dlist[0] = head;
dlist[1] = tail;
return TRUE;
}
if (current == head) { /* usuwamy poczatek listy */
head = head->next;
free(head->prev);
head->prev = NULL;
} else if (current == tail) { /* usuwamy koniec listy */
tail = tail->prev;
free(tail->next);
tail->next = NULL;
} else { /* usuwamy element ze srodka listy */
current->prev->next = current->next;
current->next->prev = current->prev;
free(current);
current = NULL; /* dobry zwyczaj */
}
dlist[0] = head;
dlist[1] = tail;
return TRUE;
}
/*
* find_list.c
*/
#include "main.h"
bool find_list(Node *dlist[], Cargo item)
{
Node *current; /* aktualnie przeszukiwana struktura */
current = dlist[0]; /* zaczynamy szukac od poczatku */
while (current != NULL && cmp_cargo(current->data, item) != 0)
current = current->next;
return ( (current == NULL) ? FALSE : TRUE ); /* TRUE - znalazl */
}
/*
* count_list.c
*/
#include "main.h"
int count_list(Node *dlist[])
{
Node *current; /* biezaca struktura */
int counter = 0; /* licznik */
current = dlist[0]; /* head */
while (current != NULL) {
++counter;
current = current->next;
}
return counter;
}
Dopisać brakujące funkcje, skompilować i uruchomić program.
W katalogu domowym utworzyć podkatalog listy2char. Utworzyć w nim plik Makefile i pozostałe pliki, po jednym dla każdej funkcji:
/*
* main.h
*
* Plik naglowkowy.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* typ logiczny */
typedef int bool;
#define TRUE 1
#define FALSE 0
typedef char * Cargo;
typedef struct node Node;
/* definicja struktury */
struct node {
Cargo data; /* dane elementu */
struct node *next; /* wskaznik do nastepnego elementu */
struct node *prev; /* wskaznik do poprzedniego elementu */
};
/* FUNKCJE */
Dopisać brakujące funkcje, skompilować i uruchomić program.
Na bazie listy dwukierunkowej zaimplementować stos. W katalogu domowym utworzyć podkatalog stack2. Utworzyć w nim plik Makefile i pozostałe pliki, po jednym dla każdej funkcji:
/*
* main.h
*
* Plik naglowkowy.
*/
#include <stdio.h>
#include <stdlib.h>
/* typ logiczny */
typedef int bool;
#define TRUE 1
#define FALSE 0
typedef int Cargo;
typedef struct node Node;
/* definicja struktury */
struct node {
Cargo data; /* dane elementu */
struct node *next; /* wskaznik do nastepnego elementu */
struct node *prev; /* wskaznik do poprzedniego elementu */
};
/* FUNKCJE */
#define insert_stack add_head
#define remove_stack get_head
/* inny sposób:
#define insert_stack add_tail
#define remove_stack get_tail
*/
/*
* main.c
*/
#include "main.h"
int main(void)
{
/* Inicjalizujemy pusta liste/stos */
Node *dlist[2] = { NULL, NULL };
insert_stack(dlist, 12);
insert_stack(dlist, 34);
insert_stack(dlist, 10);
while (!is_empty(dlist)) {
printf("Usuwam %d\n", remove_stack(dlist));
}
return 0;
}
Dopisać brakujące funkcje, skompilować i uruchomić program.
Na bazie listy dwukierunkowej zaimplementować kolejkę FIFO. W katalogu domowym utworzyć podkatalog queue2. Utworzyć w nim plik Makefile i pozostałe pliki, po jednym dla każdej funkcji:
/*
* main.h
*
* Plik naglowkowy.
*/
#include <stdio.h>
#include <stdlib.h>
/* typ logiczny */
typedef int bool;
#define TRUE 1
#define FALSE 0
typedef int Cargo;
typedef struct node Node;
/* definicja struktury */
struct node {
Cargo data; /* dane elementu */
struct node *next; /* wskaznik do nastepnego elementu */
struct node *prev; /* wskaznik do poprzedniego elementu */
};
/* FUNKCJE */
#define insert_queue add_tail
#define remove_queue get_head
/* inny sposób:
#define insert_queue add_head
#define remove_queue get_tail
*/
/*
* main.c
*/
#include "main.h"
int main(void)
{
/* Inicjalizujemy pusta liste/kolejke */
Node *dlist[2] = { NULL, NULL };
insert_queue(dlist, 12);
insert_queue(dlist, 34);
insert_queue(dlist, 10);
while (!is_empty(dlist)) {
printf("Usuwam %d\n", remove_queue(dlist));
}
return 0;
}
Dopisać brakujące funkcje, skompilować i uruchomić program.
Na bazie listy dwukierunkowej zaimplementować kolejkę z priorytetami. W katalogu domowym utworzyć podkatalog pqueue2. Utworzyć w nim plik Makefile i pozostałe pliki, po jednym dla każdej funkcji:
/*
* main.h
*
* Plik naglowkowy.
*/
#include <stdio.h>
#include <stdlib.h>
/* typ logiczny */
typedef int bool;
#define TRUE 1
#define FALSE 0
typedef int Cargo;
typedef struct node Node;
/* definicja struktury */
struct node {
Cargo data; /* dane elementu */
struct node *next; /* wskaznik do nastepnego elementu */
struct node *prev; /* wskaznik do poprzedniego elementu */
};
/* FUNKCJE */
#define insert_pqueue add_list
#define remove_pqueue get_head
/*
* main.c
*/
#include "main.h"
int main(void)
{
/* Inicjalizujemy pusta liste/kolejke */
Node *dlist[2] = { NULL, NULL };
insert_pqueue(dlist, 12);
insert_pqueue(dlist, 34);
insert_pqueue(dlist, 10);
while (!is_empty(dlist)) {
printf("Usuwam %d\n", remove_pqueue(dlist));
}
return 0;
}
Dopisać brakujące funkcje, skompilować i uruchomić program.