Prog-0201 (linked list)

#include "stdafx.h"
#include <stdlib.h>

typedef int DATA;
struct Node {
    DATA value;   // дані
    Node *next;   // поле зв'зку
};

typedef struct Node NODE;
typedef struct Node* PNODE;

struct LIST {
    PNODE Head, Tail;
} firstList = { NULL, NULL };

PNODE makeNode(DATA val);
void initList(LIST *lst , DATA val);
bool addNodeToEnd(PNODE *tail, DATA val);
bool addNodeToHead(PNODE *head, DATA val);
bool addNodeByIndex(PNODE *head, DATA val, unsigned pos);
PNODE FindNode(PNODE head, DATA key);
bool DeleteNode(PNODE *head, DATA key);
bool DeleteNodeByIndex(PNODE *head, unsigned pos);
void PrintList(const LIST *list);
// void SortList();
// void MergeList();

struct STACK {
    PNODE top;
};
void s_push(STACK *st, DATA value);
bool s_pop(STACK *st, DATA *value);

struct QUEUE {
    PNODE Head, Tail;
};

void q_push(QUEUE *q, DATA value);
bool q_pop(QUEUE *q, DATA *value);

int _tmain(int argc, _TCHAR* argv[])
{
    initList(&firstList, 12); //12
    addNodeToHead(&firstList.Head, 99); // 99 12
    PrintList(&firstList);
    addNodeToEnd(&firstList.Tail, 111); // 99 12 111
    PrintList(&firstList);
    for (int i = 1; i<15; i++)
        addNodeToEnd(&firstList.Tail, i);
    PrintList(&firstList);
    DeleteNode(&firstList.Head, 20);
    if (FindNode(firstList.Head, 20) != NULL)
        printf_s("\nYes!\n");
    else
        printf_s("\nNo!\n");
    PrintList(&firstList);
    if (DeleteNodeByIndex(&firstList.Head, 14))
        printf_s("\nYes!\n");
    else
        printf_s("\nNo!\n");
    PrintList(&firstList);
    addNodeByIndex(&firstList.Head, 1111, 5);
    PrintList(&firstList);

    STACK a={ NULL };
    int x;
    push(&a, 1);
    push(&a, 2);
    push(&a, 3);
    while (pop(&a, &x))
    {
        printf("%d", x);
    };
    QUEUE q1 = { NULL, NULL };
    q_push(&q1, 1);
    q_push(&q1, 2);
    q_push(&q1, 3);
    while (q_pop(&q1, &x))
    {
        printf("%d", x);
    };
    return 0;
}

PNODE makeNode(DATA val)
{
    PNODE tmp;
    tmp = (PNODE)calloc(1, sizeof(NODE));
    tmp->value = val;
    tmp->next = NULL;
    return tmp;
}

void initList(LIST *lst, DATA val)
{
    lst->Head = lst->Tail = makeNode(val);
}

bool addNodeToEnd(PNODE *tail, DATA val)
{
    PNODE temp = makeNode(val);
    (*tail)->next = temp;
    *tail = temp;
    return true;
}

bool addNodeToHead(PNODE *head, DATA val)
{
    PNODE temp = makeNode(val);
    temp->next = *head;
    *head = temp;
    return true;
}

PNODE FindNode(PNODE head, DATA key)
{
    PNODE temp;
    for (temp = head; temp != NULL; temp = temp->next)
        if (temp->value == key) break;
    return temp;
}

bool DeleteNode(PNODE *head, DATA key)
{
    PNODE temp = *head, temp1 = *head;
    if ((*head)->value == key)
    {
        *head = temp->next;
        free(temp);
        return true;
    }
    else
    {
        for (temp = (*head)->next; temp != NULL; temp1 = temp, temp = temp->next)
            if (temp->value == key) {
            temp1->next = temp->next;
            free(temp);
            return true;
            }
    }
    return false;
}

bool DeleteNodeByIndex(PNODE *head, unsigned pos)
{
    PNODE temp = *head, temp1 = *head;
    if (!pos) {
        *head = temp->next;
        free(temp);
        return true;
    }
    else {
        for (temp = (*head)->next; temp != NULL; temp1 = temp, temp = temp->next)
            if (pos-- == 1) {
            temp1->next = temp->next;
            free(temp);
            return true;
            }
    }
    return false;
}

void PrintList(const LIST *list)
{
    PNODE temp;
    for (temp = list->Head; temp != NULL; temp = temp->next)
    {
        printf_s("%d ", temp->value);
    }
    printf("\n--------------------\n");
}

bool addNodeByIndex(PNODE *head, DATA val, unsigned pos)
{
    PNODE temp, temp1 = *head;
    if (!pos--)
        return addNodeToHead(head, val);
    for (temp = (*head)->next; temp != NULL; temp1 = temp, temp = temp->next)
    {
        if (!pos--) {
            PNODE new_element = makeNode(val);
            new_element->next = temp;
            temp1->next = new_element;
            return true;
        }
    }
    if (!pos) {
        PNODE new_element = makeNode(val);
        new_element->next = temp;
        temp1->next = new_element;
        return true;
    }
    return false;
}

PNODE addNode(DATA number, PNODE next)
{
    PNODE tnode = makeNode(number);
    tnode->next = next;
    return tnode;
}

int Length(PNODE head)
{
    int count = 0;
    for (PNODE current = head; current != NULL; current = current->next) count++;
    return count;
}

void FrontBackSplit(PNODE source, PNODE* frontRef, PNODE* backRef)
{

    int len = Length(source);
    int i;
    PNODE current = source;
    if (len < 2)
    {
        *frontRef = source;
        *backRef = NULL;
    }
    else
    {
        int hopCount = (len - 1) / 2;
        for (i = 0; i<hopCount; i++)
        {
            current = current->next;
        }
        // початковий список розбивается на два подсписка
        *frontRef = source;
        *backRef = current->next;
        current->next = NULL;
    }
}

PNODE SortedMerge(PNODE a, PNODE b)
{
    PNODE result = NULL;
    if (a == NULL)
        return b;
    else
        if (b == NULL)
            return a;
    if (a->value <= b->value)
    {
        result = a;
        result->next = SortedMerge(a->next, b);
    }
    else
    {
        result = b;
        result->next = SortedMerge(a, b->next);
    }
    return(result);
}


void MergeSort(PNODE* headRef)
{
    PNODE head = *headRef;
    PNODE a;
    PNODE b;
    // вирождений випадок– довжина списка рівна 0 чи 1
    if ((head == NULL) || (head->next == NULL))
    {
        return;
    }
    FrontBackSplit(head, &a, &b);
    MergeSort(&a); // рекурсивне сортування підсписків
    MergeSort(&b);
    *headRef = SortedMerge(a, b);
}

void s_push(STACK *st, DATA value)
{
    PNODE temp;
    temp = makeNode(value);
    if (st->top != NULL)
        temp->next = st->top;
    st->top = temp;
}
bool s_pop(STACK *st, DATA *value){
    PNODE var;
    bool res = st->top != NULL;
    if (res)
    {
        var = st->top;
        st->top = st->top->next;
        *value = var->value;
        free(var);
    }
    return res;
}

void q_push(QUEUE *q, DATA value)
{
    if (q->Head == NULL)
        initList((LIST *)q, value);
    else
        addNodeToEnd(&q->Tail, value);
}

bool q_pop(QUEUE *q, DATA *value)
{
    bool res = (q->Head != NULL);
    if (res)
    {
        *value = q->Head->value;
        DeleteNodeByIndex(&q->Head, 0);
    }
    return res;
}