Code:#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "LinkedList.h"
/* KOD FUNKCIJA */
/* Osnovna funkcija - poziva sve ostale funkicje */
void BasicCaller()
{
struct node* head, *a = NULL, *b = NULL;
struct node *lst1 = NULL, *lst2 = NULL , *lst3 = NULL;
int len, i;
printf("\nPOCETAK PROGRAMA!\n");
head = BuildOneTwoThree();
Push(&head, 13);
Push(&(head->next),42);
printf("Lista je:");
WriteList(head);
putchar('\n');
len = Length(head);
printf("\nDuzina liste je %d\n", len);
printf("Broj pojavljivanja broja 1 je %d.\n", Count(head,1));
printf("Element na poziciji 4 je %d\n", GetNth(head, 4));
printf("Iz liste je sa Pop obrisan element %d\n", Pop(&head));
InsertSort(&head);
WriteList(head);
WriteList1(head);
for(i=1;i<6;i++)
{
Push(&a, i);
Push(&b,i*10);
}
printf("\nAppend primjer - nadovezivanje a i b:\n");
printf("Lista a:");
WriteList1(a);
putchar('\n');
RecursiveReverse(&a);
printf("Recursive reverse a:\n");
WriteList(a);
putchar('\n');
printf("Lista b:");
WriteList1(b);
putchar('\n');
printf("Nadovezana b na a:");
Append(&a,&b);
putchar('\n');
WriteList1(a);
putchar('\n');
WriteList1(b);
putchar('\n');
printf("Rekurzivni reverse liste a:\n");
RecursiveReverse(&a);
WriteList1(a);
putchar('\n');
lst1 = BuildSpecial();
WriteList1(lst1);
putchar('\n');
lst2 = BuildDummy();
WriteList1(lst2);
putchar('\n');
lst3 = BuildLocalRef();
WriteList1(lst3);
putchar('\n');
}
/************************************************************************/
main()
{
BasicCaller();
}
/************************************************************************/
int Length(struct node* head)
{
/* Broj elemenata upisanih u listu */
int count = 0;
struct node* current = head;
/* Prvi nacin - primjena WHILE petlje */
/*
while( current != NULL )
{
count++;
current = current->next;
}
*/
/* Drugi nacin - FOR petlja */
for (current = head; current != NULL ; count++, current = current->next );
return count;
/* Treci nacin - rekurzija */
/*
if ( head == NULL )
return(0);
else
return(1+Length(head->next));
*/
} /* Kraj funkcije Length */
/***************************************************************************/
struct node* BuildOneTwoThree()
{
/* Kreiranje liste sa elementima 1,2,3 */
/* Prvi nacin - upotreba tri pokazivaca */
struct node* head = NULL;
struct node* second = NULL;
struct node* third = NULL;
head = (struct node *)malloc(sizeof(struct node));
second = (struct node *)malloc(sizeof(struct node));
third = (struct node *)malloc(sizeof(struct node));
head->data = 1;
head->next = second;
second->data = 2;
second->next = third;
third->data = 3;
third->next = NULL;
return head;
/* Drugi nacin - prihvatljiviji */
/*
struct node* pomoc = NULL;
Push(&pomoc,3);
Push(&pomoc,2);
Push(&pomoc,1);
return pomoc;
*/
}
/**************************************************************************/
void Push(struct node** headRef, int newData)
{
/* Upisivanje elementa na pocetnu poziciju u listi */
struct node* newNode;
newNode =(struct node *)malloc(sizeof(struct node));
// newNode = new struct node * ;
newNode->data = newData;
newNode->next = *headRef;
*headRef = newNode; /* headRef = &newNode; */
}
/***************************************************************************/
int Count(Lista head, int searchFor)
{
/* Koliko puta se dati broj pojavljuje u listi */
int count = 0;
Lista current = head;
/* Prvi nacin - primjena WHILE petlje */
/*
while( current != NULL )
{
if ( current == searchFor ) count++;
current = current->next;
}
return count;
*/
/* Drugi nacin - FOR petlja */
for (current = head; current != NULL ; current = current->next )
{
if ( current->data == searchFor ) count++;
}
return count;
}
/**************************************************************************/
int GetNth(Lista head, int n)
{
/* Odrediti n-ti element u listi */
Lista current = head;
int count = 0;
/* Prvi nacin - primjena WHILE petlje */
while( current != NULL )
{
if ( count == n ) return(current->data);
count++;
current = current->next;
}
assert(0);
}
/**************************************************************************/
void DeleteList(struct node** headRef)
{
/* Brisanje svih elemenata iz liste */
struct node* current = *headRef;
struct node *next;
while ( current != NULL )
{
next = current->next;
free(current);
current = next;
}
*headRef = NULL;
}
/**************************************************************************/
int Pop(struct node** headRef)
{
/* Cita prvi element liste i brise ga iz liste */
struct node* head;
int result;
head = *headRef;
assert(head != NULL);
result = head->data;
*headRef = head->next;
free(head);
return(result);
}
/*********************************************************************/
void InsertNtx( struct node** headRef, int index, int data)
{
/* umetanje podatka na poziciju datu indexom */
if ( index == 0 )
Push(headRef, data);
else
{
struct node* current = *headRef;
int i;
for (i=0;i<index-1; i++)
{
assert(current != NULL);
current = current->next;
}
assert( current != NULL );
Push(&(current->next), data);
}
}
/*************************************************************************/
void SortedInsert(struct node** headRef, struct node* newNode)
{
/* Upisivanje cvora u uredjenu listu */
struct node** currentRef = headRef;
while ((*currentRef != NULL) && ((*currentRef)->data < newNode->data))
{
currentRef = &((*currentRef)->next);
}
newNode->next = *currentRef;
*currentRef = newNode;
}
/*********************************************************************/
void InsertSort(struct node** headRef)
{
/* Uredjivanje elemenata liste u rastucu */
struct node* result = NULL;
struct node* current = *headRef;
struct node* next;
while (current != NULL)
{
next = current->next;
SortedInsert(&result, current);
current = next;
}
*headRef = result;
}
/**************************************************************************/
void WriteList(struct node* head)
{
/* Stampanje elemenata liste - rekurzivno*/
if (head != NULL)
{
printf("%d ", head->data);
WriteList(head->next);
}
}
/************************************************************************/
void WriteList1(struct node* head)
{
/* Stampanje elemenata liste - nerekurzivno*/
if ( head == NULL )
{
printf("Lista je prazna!\n");
return;
}
while (head != NULL)
{
printf("%d ", head->data);
head = head->next;
}
}
/**************************************************************************/
void Append(struct node** aRef, struct node** bRef)
{
/* Nadovezivanje liste b na listu a. b postaje NULL, a je nova lista */
struct node* current;
if(aRef == NULL)
{
*aRef = *bRef;
}
else
{
current = *aRef;
while (current->next != NULL)
{
current = current->next;
}
current->next = *bRef;
}
*bRef = NULL;
}
/*************************************************************************/
void RecursiveReverse(struct node** headRef)
{
/* Obrtanje liste u mjestu */
struct node* first;
struct node* rest;
if (*headRef == NULL) return;
first = *headRef;
rest = first->next;
if (rest == NULL) return;
RecursiveReverse(&rest);
first->next->next = first;
first->next = NULL;
*headRef = rest;
/*
WriteList(*headRef);
putchar('\n');
*/
}
/**********************************************************************/
/* Sledece tri funkcije kreiraju listu 1->2->3->4->5->6 */
struct node *BuildSpecial()
{
/* Prvi cvor dodaje se direktno na head, dok se svi ostali
cvorovi dodaju na kraj, tj. gdje pokazuje tail */
struct node *head = NULL;
struct node *tail;
int i;
Push(&head, 1);
tail = head;
for(i=2;i<=6;i++)
{
Push(&(tail->next), i);
tail = tail->next;
}
return(head);
}
struct node *BuildDummy()
{
/* Upotreba privremenog vjestackog cvora (dummy node) */
/* Moguce da taj cvor bude dio liste, pa se npr. prazna lista
ne predstavlja sa NULL vec samo sa dummy cvorom */
struct node dummy;
struct node *tail = &dummy;
int i;
dummy.next = NULL;
for(i=1;i<=6;i++)
{
Push(&(tail->next),i);
tail = tail->next;
}
return(dummy.next);
}
struct node* BuildLocalRef()
{
/* Lokalni reference-pointer, koji ukazuje na poslednji
pokazivac u listi (a ne na poslednji cvor) */
struct node *head = NULL;
struct node **lastRefPtr = &head;
int i;
for(i=1;i<=6;i++)
{
Push(lastRefPtr, i);
lastRefPtr = &((*lastRefPtr)->next);
}
return(head);
}
Jednostruko povezane liste?
Re: Jednostruko povezane liste?
Re: Jednostruko povezane liste?