From 5a2665c21b511ef90967af053f6a1d504b78afff Mon Sep 17 00:00:00 2001 From: Maksymilian Jopek Date: Sun, 26 Mar 2023 15:53:00 +0200 Subject: Stack, queue and graph data structures implemented in C using linked lists. --- .gitignore | 2 ++ Makefile | 20 ++++++++++++++++++++ src/graph.c | 27 +++++++++++++++++++++++++++ src/graph.h | 20 ++++++++++++++++++++ src/main.c | 55 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/queue.c | 48 ++++++++++++++++++++++++++++++++++++++++++++++++ src/queue.h | 20 ++++++++++++++++++++ src/stack.c | 50 ++++++++++++++++++++++++++++++++++++++++++++++++++ src/stack.h | 13 +++++++++++++ 9 files changed, 255 insertions(+) create mode 100644 .gitignore create mode 100644 Makefile create mode 100644 src/graph.c create mode 100644 src/graph.h create mode 100644 src/main.c create mode 100644 src/queue.c create mode 100644 src/queue.h create mode 100644 src/stack.c create mode 100644 src/stack.h diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..ed02be9 --- /dev/null +++ b/.gitignore @@ -0,0 +1,2 @@ +target/ +src/any* diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..623af48 --- /dev/null +++ b/Makefile @@ -0,0 +1,20 @@ +DIRS=target target/bin target/objs +BIN=target/bin/main +CC=gcc +# CFLAGS=-g -Wall -Wextra -Wpedantic -O1 -std=c17 +CFLAGS=-Wall -Wextra -Wpedantic -O1 -std=c17 +OBJS=target/objs/main.o target/objs/graph.o target/objs/queue.o target/objs/stack.o target/objs/any_stack.o + +$(shell mkdir -p $(DIRS)) +all: $(BIN) + +target/bin/main: $(OBJS) + $(CC) $(CFLAGS) -fsanitize=leak,undefined,address $(OBJS) -o $@ + # $(CC) $(CFLAGS) $(OBJS) -o $@ + +target/objs/%.o: src/%.c + $(CC) $(CFLAGS) -c $< -o $@ + +clean: + rm -rf target/ + diff --git a/src/graph.c b/src/graph.c new file mode 100644 index 0000000..f7c4b1d --- /dev/null +++ b/src/graph.c @@ -0,0 +1,27 @@ +#include +#include "graph.h" + +struct vertexList *vertexAlloc(size_t length) { + struct vertexList *vertices = malloc(sizeof(*vertices) * length); + for(size_t i = 0; i < length; i++) { + vertices[i].first = NULL; + vertices[i].last = NULL; + } + return vertices; +} + +void vertexAdd( + struct vertexList *list, size_t toWhich, size_t whichOne +) { + struct vertex *new = malloc(sizeof(*new)); + new->number = whichOne; + new->next = NULL; + if(list[toWhich].first == NULL) { + list[toWhich].first = new; + list[toWhich].last = new; + return; + } + list[toWhich].last->next = new; + list[toWhich].last = new; +} + diff --git a/src/graph.h b/src/graph.h new file mode 100644 index 0000000..3443c8f --- /dev/null +++ b/src/graph.h @@ -0,0 +1,20 @@ +#ifndef GRAPH_H_ +#define GRAPH_H_ + +#include + +struct vertex { + size_t number; + struct vertex *next; +}; + +struct vertexList { + struct vertex *first; + struct vertex *last; +}; + +struct vertexList *vertexAlloc(size_t length); +void vertexAdd(struct vertexList *v, size_t toWhich, size_t whichOne); + +#endif + diff --git a/src/main.c b/src/main.c new file mode 100644 index 0000000..07e629b --- /dev/null +++ b/src/main.c @@ -0,0 +1,55 @@ +#include "graph.h" +#include "queue.h" +#include "stack.h" +#include +#include + +#define GRAPH_SIZE 5 + +int main() { + Queue *queue = queueAlloc(); + queueAdd(queue, 1); + queueAdd(queue, 2); + queueAdd(queue, 3); + queueAdd(queue, 4); + queueAdd(queue, 5); + queueAdd(queue, 6); + printf("%d\n", queuePop(queue)); + printf("%d\n", queuePop(queue)); + printf("%d\n", queuePop(queue)); + printf("%d\n", queuePop(queue)); + printf("%d\n", queuePop(queue)); + printf("%d\n", queuePop(queue)); + queueFree(queue); + Stack *stack = stackAlloc(); + stackAdd(stack, 1); + stackAdd(stack, 2); + stackAdd(stack, 3); + stackAdd(stack, 4); + stackAdd(stack, 5); + stackAdd(stack, 6); + printf("%d\n", stackPop(stack)); + printf("%d\n", stackPop(stack)); + printf("%d\n", stackPop(stack)); + printf("%d\n", stackPop(stack)); + printf("%d\n", stackPop(stack)); + printf("%d\n", stackPop(stack)); + stackFree(stack); + + struct vertexList *graph = vertexAlloc(GRAPH_SIZE); + vertexAdd(graph, 0, 1); + vertexAdd(graph, 1, 2); + vertexAdd(graph, 1, 0); + vertexAdd(graph, 2, 3); + vertexAdd(graph, 3, 4); + vertexAdd(graph, 1, 4); + + for (int j = 0; j < GRAPH_SIZE; j++) { + printf("%d:", j); + for (struct vertex *i = graph[j].first; i != NULL; i = i->next) { + printf(" %ld,", i->number); + } + printf("\n"); + } +} + diff --git a/src/queue.c b/src/queue.c new file mode 100644 index 0000000..1d7a170 --- /dev/null +++ b/src/queue.c @@ -0,0 +1,48 @@ +#include "queue.h" +#include +#include + +Queue *queueAlloc() { + Queue *new = malloc(sizeof(Queue)); + new->first = NULL; + new->last = NULL; + return new; +} + +void queueAdd(Queue *queue, int item) { + struct queueItem *new = malloc(sizeof(struct queueItem)); + new->item = item; + if (queue->first) { + new->next = queue->last; + new->previous = NULL; + queue->last->previous = new; + queue->last = new; + } else { + new->next = NULL; + new->previous = NULL; + queue->first = new; + queue->last = new; + } +} + +int queuePop(Queue *queue) { + if (!queue->first) { + return -1; + } + int out = queue->first->item; + queue->first = queue->first->previous; + return out; +} + +void queueFree(Queue *queue) { + struct queueItem *qi = queue->last; + struct queueItem *t = NULL; + while (qi) { + // printf("Address:"); + // printf("%p\n", (void *)qi); + t = qi->next; + free(qi); + qi = t; + } + free(queue); +} diff --git a/src/queue.h b/src/queue.h new file mode 100644 index 0000000..0082bda --- /dev/null +++ b/src/queue.h @@ -0,0 +1,20 @@ +#ifndef QUEUE_H_ +#define QUEUE_H_ + +struct queue { + struct queueItem *first; + struct queueItem *last; +}; +typedef struct queue Queue; +struct queueItem { + int item; + struct queueItem *next; + struct queueItem *previous; +}; + +Queue *queueAlloc(); +void queueAdd(Queue *queue, int item); +int queuePop(Queue *queue); +void queueFree(Queue *queue); + +#endif diff --git a/src/stack.c b/src/stack.c new file mode 100644 index 0000000..7c83c87 --- /dev/null +++ b/src/stack.c @@ -0,0 +1,50 @@ +#include "stack.h" +#include +#include + +Stack *stackAlloc() { + Stack *new = malloc(sizeof(Stack)); + new->first = NULL; + new->last = NULL; + return new; +} + +void stackAdd(Stack *stack, int item) { + struct queueItem *new = malloc(sizeof(struct queueItem)); + new->item = item; + if (stack->first) { + // printf("stack->first is NOT NULL"); + new->next = NULL; + new->previous = stack->first; + stack->first->next = new; + stack->first = new; + } else { + // printf("stack->first is NULL"); + new->next = NULL; + new->previous = NULL; + stack->first = new; + stack->last = new; + } +} + +int stackPop(Stack *stack) { + if (!stack->first) { + return -1; + } + int out = stack->first->item; + struct queueItem *toFree = stack->first; + stack->first = toFree->previous; + free(toFree); + return out; +} + +void stackFree(Stack *stack) { + struct queueItem *s = stack->first; + struct queueItem *t = NULL; + while (s) { + t = s->previous; + free(s); + s = t; + } + free(stack); +} diff --git a/src/stack.h b/src/stack.h new file mode 100644 index 0000000..784180a --- /dev/null +++ b/src/stack.h @@ -0,0 +1,13 @@ +#ifndef STACK_H_ +#define STACK_H_ + +#include "queue.h" + +typedef struct queue Stack; + +Stack *stackAlloc(); +void stackAdd(Stack *stack, int item); +int stackPop(Stack *stack); +void stackFree(Stack *stack); + +#endif -- cgit v1.3.1