| C language content |
|---|
| Preprocessor Directives |
|---|
| Debugging and Testing |
|---|
Sure, let’s dive into the basics of some fundamental data structures: Stack, Queue, Tree, and Graph. I’ll describe each one in detail along with its implementation in C.
1. Stack
Description: A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. Elements can be added to or removed from only one end of the stack, known as the top.
Operations:
push(): Add an element to the top of the stack.pop(): Remove and return the top element of the stack.peek(): Return the top element without removing it.isEmpty(): Check if the stack is empty.isFull(): Check if the stack is full (for array-based implementation).
Array-based Implementation in C:
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
typedef struct {
int items[MAX];
int top;
} Stack;
void initStack(Stack *s) {
s->top = -1;
}
int isFull(Stack *s) {
return s->top == MAX - 1;
}
int isEmpty(Stack *s) {
return s->top == -1;
}
void push(Stack *s, int value) {
if (isFull(s)) {
printf("Stack is full\n");
return;
}
s->items[++(s->top)] = value;
}
int pop(Stack *s) {
if (isEmpty(s)) {
printf("Stack is empty\n");
exit(1);
}
return s->items[(s->top)--];
}
int peek(Stack *s) {
if (isEmpty(s)) {
printf("Stack is empty\n");
exit(1);
}
return s->items[s->top];
}
int main() {
Stack s;
initStack(&s);
push(&s, 10);
push(&s, 20);
push(&s, 30);
printf("Top element is %d\n", peek(&s));
printf("Popped element is %d\n", pop(&s));
printf("Top element is %d\n", peek(&s));
return 0;
}
2. Queue
Description: A queue is a linear data structure that follows the First In, First Out (FIFO) principle. Elements are added at the rear end and removed from the front end.
Operations:
enqueue(): Add an element to the rear end of the queue.dequeue(): Remove and return the front element of the queue.isEmpty(): Check if the queue is empty.isFull(): Check if the queue is full (for array-based implementation).
Array-based Implementation in C:
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
typedef struct {
int items[MAX];
int front, rear;
} Queue;
void initQueue(Queue *q) {
q->front = -1;
q->rear = -1;
}
int isFull(Queue *q) {
return q->rear == MAX - 1;
}
int isEmpty(Queue *q) {
return q->front == -1 || q->front > q->rear;
}
void enqueue(Queue *q, int value) {
if (isFull(q)) {
printf("Queue is full\n");
return;
}
if (q->front == -1) q->front = 0;
q->items[++(q->rear)] = value;
}
int dequeue(Queue *q) {
if (isEmpty(q)) {
printf("Queue is empty\n");
exit(1);
}
return q->items[(q->front)++];
}
int main() {
Queue q;
initQueue(&q);
enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);
printf("Dequeued element is %d\n", dequeue(&q));
printf("Dequeued element is %d\n", dequeue(&q));
return 0;
}
3. Tree
Description: A tree is a hierarchical data structure consisting of nodes, with a single node called the root. Each node contains a value and references to its children.
Basic Types of Trees:
- Binary Tree: Each node has at most two children.
- Binary Search Tree (BST): A binary tree where the left child contains values less than the parent and the right child contains values greater than the parent.
Binary Search Tree Implementation in C:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
Node* createNode(int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
}
Node* insert(Node* root, int value) {
if (root == NULL) return createNode(value);
if (value < root->data)
root->left = insert(root->left, value);
else
root->right = insert(root->right, value);
return root;
}
void inorderTraversal(Node* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}
int main() {
Node* root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
printf("Inorder traversal: ");
inorderTraversal(root);
return 0;
}
4. Graph
Description: A graph is a collection of nodes (vertices) and edges connecting pairs of nodes. Graphs can be directed or undirected and can contain cycles.
Basic Representation:
- Adjacency Matrix
- Adjacency List
Adjacency List Implementation in C:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int vertex;
struct Node* next;
} Node;
typedef struct {
int numVertices;
Node** adjLists;
} Graph;
Node* createNode(int vertex) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->vertex = vertex;
newNode->next = NULL;
return newNode;
}
Graph* createGraph(int vertices) {
Graph* graph = (Graph*)malloc(sizeof(Graph));
graph->numVertices = vertices;
graph->adjLists = (Node**)malloc(vertices * sizeof(Node*));
for (int i = 0; i < vertices; i++)
graph->adjLists[i] = NULL;
return graph;
}
void addEdge(Graph* graph, int src, int dest) {
Node* newNode = createNode(dest);
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
newNode = createNode(src);
newNode->next = graph->adjLists[dest];
graph->adjLists[dest] = newNode;
}
void printGraph(Graph* graph) {
for (int v = 0; v < graph->numVertices; v++) {
Node* temp = graph->adjLists[v];
printf("\n Vertex %d\n: ", v);
while (temp) {
printf("%d -> ", temp->vertex);
temp = temp->next;
}
printf("\n");
}
}
int main() {
Graph* graph = createGraph(5);
addEdge(graph, 0, 1);
addEdge(graph, 0, 4);
addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 3);
addEdge(graph, 3, 4);
printGraph(graph);
return 0;
}
This should give you a solid foundation on the basic data structures and their implementation in C. Each of these examples provides a starting point and can be expanded with more functionality and error checking as needed.
