# Sparse matrix

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

typedef struct {
    int row;
    int col;
    int value;
} term;

term a[101];

int main() {
    a[0].row = 4;  // Number of rows in the original matrix
    a[0].col = 3;  // Number of columns in the original matrix
    a[0].value = 4;  // Number of non-zero elements

    a[1].row = 0;
    a[1].col = 0;
    a[1].value = 1;

    a[2].row = 0;
    a[2].col = 1;
    a[2].value = 2;

    a[3].row = 1;
    a[3].col = 1;
    a[3].value = 3;

    a[4].row = 2;
    a[4].col = 0;
    a[4].value = 4;

    // Transpose the sparse matrix
    int rows = a[0].row;
    int cols = a[0].col;
    int terms = a[0].value;

    term transposed[101];
    transposed[0].row = cols;
    transposed[0].col = rows;
    transposed[0].value = terms;

    if (terms > 0) {
        int currentTerm = 1;
        for (int col = 0; col < cols; col++) {
            for (int i = 1; i <= terms; i++) {
                if (a[i].col == col) {
                    transposed[currentTerm].row = a[i].col;
                    transposed[currentTerm].col = a[i].row;
                    transposed[currentTerm].value = a[i].value;
                    currentTerm++;
                }
            }
        }
    }

    // Display the transposed sparse matrix
    printf("Transposed sparse matrix:\n");
    for (int i = 0; i <= terms; i++) {
        printf("%d %d %d\n", transposed[i].row, transposed[i].col, transposed[i].value);
    }

    return 0;
}

# Binary search tree

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

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

struct Node* insertion(struct Node* root, int value) {
    if (root == NULL) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = value;
        newNode->left = newNode->right = NULL;
        return newNode;
    }

    if (value <= root->data) {
        root->left = insertion(root->left, value);
    } else {
        root->right = insertion(root->right, value);
    }

    return root;
}

void inorder_traverse(struct Node* root) {
    if (root != NULL) {
        inorder_traverse(root->left);
        printf("%d ", root->data);
        inorder_traverse(root->right);
    }
}

int main() {
    int arr[5] = {1, 2, 3, 4, 5};
    struct Node* root = NULL;

    for (int i = 0; i < 5; ++i) {
        root = insertion(root, arr[i]);
    }

    inorder_traverse(root);

    return 0;
}

# Binary tree

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

char arr[7] = {'e', 'c', 'f', 'a', 'g', 'h'};

void inorder(char* btree, int index) {
    if (btree[index] != '\0') {
        inorder(btree, 2 * index);
        printf("%c ", btree[index]);
        inorder(btree, 2 * index + 1);
    }
}

int main() {
    char btree[20] = {'\0'};
    btree[1] = arr[0];
    int level = 1;

    for (int i = 1; i < 6; ++i) {
        level = 1;
        while (btree[level] != '\0') {
            if (arr[i] < btree[level])
                level = 2 * level;
            else
                level = 2 * level + 1;
        }
        btree[level] = arr[i];
    }

    for (int i = 0; i < 20; ++i) {
        if (btree[i] == '\0')
            printf("$ ");
        else
            printf("%c ", btree[i]);
    }
    printf("\n");

    inorder(btree, 1);

    return 0;
}

# Queue

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define MAX_SIZE 10
struct Queue{
	int arr[MAX_SIZE];
	int front;
	int rear;
};
void initializeQueue(struct Queue* q){
	q->front = -1;
	q->rear = -1;
}
int isEmpty(struct Queue* q){
	return (q->front == -1 && q->rear == -1);
}
int isFull(struct Queue* q){
	return ((q->rear + 1) % MAX_SIZE == q->front);
}
void enqueue(struct Queue* q, int data){
	if(isFull(q)){
		printf("Queue is full\n");
		return;
	}
	
	if(isEmpty(q)){
		q->front = 0;
		q->rear = 0;
	}
	else{
		q->rear = (q->rear + 1) % MAX_SIZE;
	}
	q->arr[q->rear] = data;
}
void dequeue(struct Queue* q){
	if(isEmpty(q)){
		printf("Queue is empty. Can\'t dequeue. \n");
		return -1;
	}
	int data = q->arr[q->front];
	if(q->front == q->rear){
		q->front = -1;
		q->rear = -1;
	}
	else{
		q->front = (q->front + 1) % MAX_SIZE;
	}
}
void displayQueue(struct Queue* queue) {
    if (isEmpty(queue)) {
        printf("Queue is empty.\n");
        return;
    }

    int i = queue->front;

    printf("Queue elements: ");
    while (i != queue->rear) {
        printf("%d ", queue->arr[i]);
        i = (i + 1) % MAX_SIZE;
    }
    printf("%d\n", queue->arr[queue->rear]);
}
int main(){
	struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
   	initializeQueue(q);
	for(int i = 0; i < 5; ++i){
		enqueue(q, i);
	}
	displayQueue(q);
	for(int i = 0; i < 6; ++i){
		dequeue(q);
		displayQueue(q);
	}
    return 0;
}

# Circular double linked list

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

struct LinkedList{
    int data;
    struct LinkedList* next;
    struct LinkedList* prev;
};

struct LinkedList* generateTheLinkedList(struct LinkedList** last, int data, struct LinkedList** firstNode){
    struct LinkedList* newNode = (struct LinkedList*)malloc(sizeof(struct LinkedList));
    
	newNode->prev = *last;
    newNode->next = (*firstNode) == NULL ? NULL : (*firstNode);
    newNode->data = data;

    if (*last != NULL)
        (*last)->next = newNode;

    *last = newNode;
	if(*firstNode == NULL) *firstNode = newNode;
	else (*firstNode)->prev = *last;

    return *last;
}
void insertion(struct LinkedList* firstNode, int newData){
	struct LinkedList* newNode = (struct LinkedList*)malloc(sizeof(struct LinkedList));
	newNode->data = newData;
	
    struct LinkedList* current = firstNode;
	while(current->data != 4){
    	current = current->next;
	}
	//The Back end
	newNode->next = current->next;
	current->next->prev = newNode;
	
	//The front end
	current->next = newNode;
	newNode->prev = current;
	
	
	
}

int main(){
    int arr[5] = {1, 2, 3, 4, 5};
    struct LinkedList* list = NULL;
    struct LinkedList* firstNode = NULL;
    for(int i = 0; i < 5; ++i){
        list = generateTheLinkedList(&list, arr[i], &firstNode);
    }
    
    // Insertion
    insertion(firstNode, -1);
    for(int i = 0; i < 6; ++i){
    	printf("%2d", firstNode->data);
    	firstNode = firstNode->next;
	}
	printf("\n");
	for(int i = 0; i < 6; ++i){
		printf("%2d", firstNode->data);
		firstNode = firstNode->prev;
	}
    return 0;
}

# Circular linked list

#include<stdio.h>
#include<stdlib.h>
struct LinkedList{
	int data;
	struct LinkedList* next;
};
void generateLinkedList(int data, int idx, struct LinkedList** list){
	struct LinkedList* newNode = (struct LinkedList*)malloc(sizeof(struct LinkedList));
	newNode->data = data;
	newNode->next = NULL;
	
    if (*list == NULL) {
        *list = newNode;
        (*list)->next = newNode;  // Set the next node to itself for circularity
    }
	else{
			
		struct LinkedList* current = *list;
		while (current->next != *list) {
            current = current->next;
        }
		current->next = newNode;
		newNode->next = *list;
	}
}


int main(){
	int arr[7] = {1, 2, 3, 4, 5, 6 ,7};
	struct LinkedList* first = NULL;
	int i = 0;
	for(; i < 7; ++i){
		generateLinkedList(arr[i], i, &first);
		
	}
	struct LinkedList* current = first;
	i = 0;
	
	for(; i < 15; ++i){
		printf("%d ", current->data);
		current = current->next;
	}

	struct LinkedList* temp = first->next;

	while(temp != first){
		struct LinkedList* next = temp->next;
		free(temp);
		temp = next;
	}
	free(first);
	
	
	return 0;
}

# Linked List
## Equation

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

struct LinkedList{
	int coef;
	int exp;
	struct LinkedList* next;
};

struct LinkedList* generateLinkedList(int coef, int exp, struct LinkedList** last) {
    struct LinkedList* newNode = (struct LinkedList*)malloc(sizeof(struct LinkedList));
    newNode->coef = coef;
    newNode->exp = exp;
    newNode->next = NULL;

    if (*last == NULL) {
        *last = newNode;
    } else {
        struct LinkedList* current = *last;
        current->next = newNode;
        *last = newNode;
	}
	return *last;
}

void print(struct LinkedList* current){
	while(current != NULL){
		printf("%dx^%d %c ", current->coef, current->exp, (current->next == NULL ? ' ' : '+'));
		current = current->next;
	}
	printf("\n");
}

int main(){
	int arr[5][2] = {{3, 3}, {3, 2}, {1, 1}, {5, 0}};
	int arr2[4][2] = {{-3, 3}, {2, 1}, {-6, 0}};
	struct LinkedList* first_linkedList = NULL;
	struct LinkedList* current_first = NULL;
	for(int i = 0; i < 4; ++i){
		first_linkedList = generateLinkedList(arr[i][0], arr[i][1], &first_linkedList);
		if(i == 0) current_first = first_linkedList;
	}
	struct LinkedList* second_linkedList = NULL;
	struct LinkedList* current_second = NULL;
	for(int i = 0; i < 3; ++i){
		second_linkedList = generateLinkedList(arr2[i][0], arr2[i][1], &second_linkedList);
		if(i == 0) current_second = second_linkedList;
	}
	print(current_first);
	print(current_second);
	struct LinkedList* third_linkedList = NULL;
	struct LinkedList* third_head = NULL;
	bool cfm = false;
	while(current_first != NULL && current_second != NULL){
		if(current_first != NULL && current_first->exp > current_second->exp){
			third_linkedList = generateLinkedList(current_first->coef, current_first->exp, &third_linkedList);
			current_first = current_first->next;
		}
		else if(current_second != NULL && current_first->exp < current_second->exp){
			third_linkedList = generateLinkedList(current_second->coef, current_second->exp, &third_linkedList);
			current_second = current_second->next;
		}	
		else{
			third_linkedList = generateLinkedList(current_second->coef + current_first->coef, current_first->exp, &third_linkedList);
			current_first = current_first->next;
			current_second = current_second->next;
		}
		if(!cfm){
			third_head = third_linkedList;
			cfm = true;
		}
	}
	print(third_head);
	return 0;
}

## Deleting the value

   while (current->next) {
        if (current->data == 2) {
            if (current->prev) {
                current->prev->next = current->next;
            }
            if (current->next) {
                current->next->prev = current->prev;
            }
            free(current);
            break;
        }
        current = current->next;
    }

## Adding the value

#include<stdio.h>
#include<stdlib.h>
struct LinkedList{
	int data;
	struct LinkedList* prev;
	struct LinkedList* next;
};
void generateALinkedList(int* arr, int idx, LinkedList** list){
	struct LinkedList* newNode = (struct LinkedList*)malloc(sizeof(struct LinkedList));
	newNode->data = arr[idx];
	newNode->prev = NULL;
	newNode->next = NULL;
	
	if(*list == NULL){
		//The first element
		*list = newNode;
	}
	else{
		struct LinkedList* current = *list;
		while(current->next != NULL){
			current = current->next;
		}
		current->next = newNode;
		newNode->prev = current;
	}
}
int main(){
	int arr[10] = {1, 2 ,3, 4, 5, 6, 7, 8, 9, 0};
	struct LinkedList* first = NULL;
	for(int i = 0; i < 10; ++i){
		generateALinkedList(arr, i, &first);
	} 
	struct LinkedList* current = first;
	bool goBack = false;
	while(current->next != NULL && (current == first || current->prev != NULL)){
		int tmp = current->data;
		if(tmp == 2){
			goBack = true;
		}
		printf("%d\n", current->data);
		if(goBack)
			current = current->prev;
		else
			current = current->next;

	}
}

## Binary tree : array
She use an array to implement binary tree.
And the point is that 2 * i + 1 will be the left child node and 2 * i + 2 will be the right child node.
For example:
A B C D E F G H I
0 1 2 3 4 5 6 7 8
B is 1 and its left child is 2 * 1 + 1 = 3 which is E

#include<stdio.h>
int main()
{
	/*
		4 1 6 _ 2 5 7 ___3___8 
	*/
	int n = 0;
	int arr[200] = {0};
	int temp = 0;
	int tmp = 0;
	scanf("%d", &n);
	for(int i = 0; i < n; ++i){
		scanf("%d", &tmp);
		if(i == 0) temp = arr[0] = tmp;
		else{
			if(tmp < temp){
				int j = 1;	
				int level = 1;
				while(arr[j]){
					if(tmp > arr[j]){
						j = 2 * level + 2;
					}
					else{
						j = 2 * level + 1;
					} 
					level = j;
				}
				arr[j] = tmp;
			}else{
				int j = 2;	
				int level = 2;			
				while(arr[j]){
					if(tmp > arr[j]){
						j = 2 * level + 2;
					}
					else{
						j = 2 * level + 1;
					}
					level = j;	
				}
				arr[j] = tmp;
			}
			for(int i = 0; i < 100; ++i){
				if(arr[i] != 0)
					printf("%d", arr[i]);
				else printf("_");
			}
			printf("\n");
		}		
	}
	printf("\n");
	for(int i = 0; i < 100; ++i){
		if(arr[i] != 0)
			printf("%d", arr[i]);
		else printf("_");
	}
   return 0;
}

In this example, I used level to represent the current position of the value and if the value is greater than its parent, then put it to the right,and vice versa.
## binary tree linked list.

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

struct node
{
    int data; //node will store an integer
    struct node *right_child; // right child
    struct node *left_child; // left child
};
struct node* queue[200] = {0};
char q[200] = {0};
int val, front = 0, rear = 0, i = 0;
void bfs_traverse(struct node *root) {
    val = root->data; 
    printf("%d ", val);
    if (front <= rear)
    {
        if (root->left_child != NULL){
            queue[++rear] = root->left_child;
            q[++i] = queue[rear]->data + '0';
		}else{
			q[++i] = '_';
			printf("_");
		}
        if (root->right_child != NULL){
            queue[++rear] = root->right_child;
            q[++i] = queue[rear]->data + '0';
        }else q[++i] = '_', printf("_");
		
	/*	for(int j = 0; j < i; ++j){
			printf("%c ", q[j]);
		}
		printf("\n");
    	*/
        bfs_traverse(queue[++front]);
        
    }
    return;
    
}
void search(struct node * root){
	if(root == NULL){
		printf("_");
		return;
	}	
	else{
		printf("%2d", root->data);
	}
	search(root->left_child);
	search(root->right_child);
}

//function to create a node
struct node* new_node(int x)
{
    struct node *p;
    p = malloc(sizeof(struct node));
    p->data = x;
    p->left_child = NULL;
    p->right_child = NULL;

    return p;
}

struct node* insert(struct node *root, int x)
{
    //searching for the place to insert
    if(root==NULL)
        return new_node(x);
    else if(x>root->data) // x is greater. Should be inserted to right
        root->right_child = insert(root->right_child, x);
    else // x is smaller should be inserted to left
        root->left_child = insert(root->left_child,x);
    return root;
}

int main()
{
	int n = 0;
    struct node *root = NULL;
	scanf("%d", &n);
	int tmp = n;
	while(n--){
		int temp = 0;
		scanf("%d", &temp);
		//if(n == tmp - 1)
		//	root = new_node(temp);
		root = insert(root, temp);
	}
	//search(root);
	queue[0] = root;
	printf("%d \n", queue[0]->data);
	q[0] = queue[0]->data + '0';
	bfs_traverse(queue[0]);
    return 0;
}

## Tree

### symmetric
https://leetcode.com/problems/symmetric-tree/submissions/

bool parallel_traverse(struct TreeNode* l, struct TreeNode* r){
    if(l == NULL && r == NULL) return true;
    if(l == NULL || r == NULL) return false;
    if(l->val != r->val) return false;
    return parallel_traverse(l->left, r->right) && parallel_traverse(l->right, r->left);
}
bool isSymmetric(struct TreeNode* root){
    if(root == NULL) return true;
    return parallel_traverse(root->left, root->right);
}

### right-side view
https://leetcode.com/problems/binary-tree-right-side-view/submissions/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
//To record the level and prioritize the right side of nodes
void input(struct TreeNode* root, int* returnSize, int* ans, int now){
    if(root == NULL){ return;}
    if(now > *returnSize){
        ans[*returnSize] = root->val;
        *returnSize += 1;
    }
    input(root->right, returnSize, ans, now+1);
    input(root->left, returnSize, ans, now+1);
}
int* rightSideView(struct TreeNode* root, int* returnSize){
    if(root == NULL){
        *returnSize = NULL;
        return NULL;
    }
    int *ans = (int*)malloc(sizeof(int) * 100);
    *returnSize = 0;
    input(root, returnSize, ans, 1);
    return ans;
}

https://leetcode.com/problems/binary-tree-right-side-view/submissions/
## stack

#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<limits.h>
#define LENGTH 5
#define EMPTY (-1)
#define STACK_EMPTY INT_MIN
typedef struct{
	int values[LENGTH];
	int top;
}stack;
bool push(stack *mystack, int value){
	if(mystack->top >= LENGTH - 1) return false;
	++mystack->top;
	mystack->values[mystack->top]= value;
	return true;
}
void top(stack *mystack){
	if(mystack->top == EMPTY){
		printf("No value\n");
		return;
	}
	printf("top: %d\n", mystack->values[mystack->top]);
}
int pop(stack *mystack){
	if(mystack->top == EMPTY) return STACK_EMPTY;
	int result = mystack->values[mystack->top];
	--mystack->top;
	return result;
}
int main(){
	stack s1; 
	s1.top = EMPTY;
	top(&s1);
	push(&s1, 10);
	top(&s1);
	int t = 0;
	while((t = pop(&s1)) != STACK_EMPTY){
		printf("t = %d\n", t);
	}
	return 0;
}