linked-list.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 10

struct Node
{
  int Data;
  struct Node *Next;
};

void Add(struct Node **PointerToFirst, int Data, int index);
void DeleteOne(struct Node **PointerToFirst, int index);
void PrintArray(struct Node *Head);
int GetOne(struct Node *Head, int index);

void PrintArray(struct Node *Head)
{
  struct Node *tmp = Head;

  while (tmp)
  {
    printf("%d ", tmp->Data);
    tmp = tmp->Next;
  }

  printf("\n\n");
}

void Add(struct Node **list, int Data, int index)
{
  struct Node *nowy = (struct Node *)malloc(sizeof(struct Node));
  nowy->Data = Data;

  if (*list)
  {
    if (index == 0)
    { //Dodaje na sam poczatek, przesuwam cala jebana list o jeden
      nowy->Next = *list;
      *list = nowy;
    }
    else
    {
      struct Node *tmp = *list;
      //deklarujemy poczatek po to zeby 'przeskoczyc' do niego az trafimy w podany index
      int i;
      for (i = 0; i < index - 1; i++)
      {
        tmp = tmp->Next;
      }

      nowy->Next = tmp->Next;
      tmp->Next = nowy;
    }
  }
  else
  {
    //List jest pusta
    nowy->Next = 0;
    *list = nowy;
  }
}

void DeleteOne(struct Node **PointerToFirst, int index)
{
  //Potrzebujemy dwa Node, jeden zeby przy usunieciu "scalic" dwa obok siebie
  struct Node *temp = *PointerToFirst, *PointerToPrevious;

  if (index == 0)
  {
    // Jezeli usuwamy elemnt z poczatku, to po prostu "przesuwamy" jeden element

    *PointerToFirst = temp->Next;
    free(temp);
    return;
  }

  int i;
  for (i = 0; i < index; i++)
  {
    //Caly czas musimy pamietac poprzedni element
    PointerToPrevious = temp;
    temp = temp->Next;
  }
  //Just in case bo jezeli w nastepnym kroku wezmiemy poprzedni element i bedziemy chcieli jakby go scalic to sie wyjebie
  if (temp == NULL)
    return;

  PointerToPrevious->Next = temp->Next;

  free(temp); // Free memory
  printf("\n\n");
}

int GetOne(struct Node *Head, int index)
{
  printf("\n");
  struct Node *tmp = Head;
  int i;
  for (i = 0; i < index; i++)
  {
    tmp = tmp->Next;
  }
  return tmp->Data;
}

void swap(struct Node *a, struct Node *b)
{
  int temp = a->Data;
  a->Data = b->Data;
  b->Data = temp;
}

void BubbleSort(struct Node *Head)
{
  int swapped, i;
  struct Node *FirstTemp;
  struct Node *SecondTemp = NULL;

  if (Head == NULL)
    return;

  do
  {
    swapped = 0;
    FirstTemp = Head;

    while (FirstTemp->Next != SecondTemp)
    {
      if (FirstTemp->Data > FirstTemp->Next->Data)
      {
        swap(FirstTemp, FirstTemp->Next);
        swapped = 1;
      }
      FirstTemp = FirstTemp->Next;
    }
    SecondTemp = FirstTemp;
  } while (swapped);
}

int BinarySearch(struct Node *Head, int From, int To, int searched)
{
  int middleIndex = (From + To) / 2;
  int compared = GetOne(Head, middleIndex);

  if (searched == compared)
    return middleIndex;

  if ((To - From) > 1)
  {
    if (compared < searched)
    {
      return BinarySearch(Head, middleIndex, To, searched);
    }
    else
    {

      return BinarySearch(Head, From, middleIndex, searched);
    }
  }
  else
  {
    return -1;
  }
}

int StartBinarySearch(struct Node *Head, int length, int searched)
{
  //list, from, to, searched
  return BinarySearch(Head, 0, length, searched);
}

int main()
{

  struct Node *FirstNode = 0;
  int binarySearchedElement = 80;
  int indexOnList = 7;

  Add(&FirstNode, 10, 0);
  Add(&FirstNode, 20, 0);
  Add(&FirstNode, 30, 0);
  Add(&FirstNode, 40, 0);
  Add(&FirstNode, 50, 0);
  Add(&FirstNode, 60, 0);
  Add(&FirstNode, 70, 0);
  Add(&FirstNode, 80, 0);
  Add(&FirstNode, 90, 0);
  Add(&FirstNode, 100, 0);
  Add(&FirstNode, 110, 0);

  printf("Nieposortowana lista \n");
  PrintArray(FirstNode);

  BubbleSort(FirstNode);

  printf("Posortowana lista \n");
  PrintArray(FirstNode);

  printf("Binarne wyszukiwanie elementu %d ma index %d\n", binarySearchedElement, StartBinarySearch(FirstNode, N, binarySearchedElement));
  printf("Pobranie elementu o indexie %d, listy ma wartość %d", indexOnList, GetOne(FirstNode, indexOnList));

  free(FirstNode);

  return 0;
}