Lesson Summaries of Semester 1 and 2
Lesson Summaries of Semester 1 and 2
Rangkuman Pembelajaran Selama Semester 1 dan 2 (Semester 1 and 2 Subject Summary):
Here are the main points that I'd like to share with you in order to refresh your memory about the basics.
1. How to output something in C:
3. Conditional Statements in C:
Long version:
4. How to do looping in C?
Using for keyword:
5. How to initialize and declare an array in C?
Int arrayNumbers[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
Char arrayCharacters[10] = {};
arrayCharacter[1] = ‘A’;
6. How to do searching in an array:
7. How to do sorting in array:
8. How to process file in C:
If (file != NULL){
Fprintf(file, “This is a sample text!”);
}
Fclose(file);
Char temp[100] = {};
Rangkuman Pembelajaran Selama Semester 2 (Semester 2 Subject Summary):
===================================Prerequisities======================================
1. In order to learn data structure, you need to know how pointers in program does the job. Here are some quick notes for us to remember:
Pointer is a type of data that references the other data. By using pointer, we have the power to change the value of the pointer. Pointer is marked by using *. To assign a reference to the pointer variable, we can use &.
2. This is the example implementation of using pointer. When you assign a value into the pointer, it will immediately give value change to variable a as well.
Int a = 10;
Int *aPointer = &a;
*aPointer = 30;
Printf(“%i”, *aPointer);
3. Another thing we can do is by building up memory that we can use inside the pointer. How do we add the memory? We can use malloc (sizeof(Type)) in order to reserve it. For example:
Int *a = (int*) malloc(3 * sizeof(int));
4. The thing to remember when using malloc is that it returns void pointer, so in order to convert into a specific data type, we can use typecasting. Sizeof means we want to determine how much size is used for such types of data structures.
By using this command, we have reserved 3 integer memory blocks for variable a. The declare result is similar to: int a[3].
5. If we don’t want to use the memory again, don’t forget to use free() command in order to save memory space. This will help to retain back memory that we have just used at runtime. Remember not to waste a lot of memory that we don’t want to use anymore, as this can cause memory leak!
=====================================================================================
1. Linked List: a linear data structure, which represents as a chain that connects from one data to one another. The elements in a linked list were connected by using pointers.
Struct Node{
Char name[40];
Int age;
}
We can do the following things in linked list:
These are the variants of linked list:
2. Stack and Queue
-> Stack is by means use linked list for implementation. Stack represents as when we are building a house, which we always put or remove the head of the building first. We don’t want to remove the middle part first as this can cause the building to fall.
Operations in stack include:
Operations in queue include:
3. Hash Table and Hashing
Hash table is a type of data structure that takes advantage of array by giving a specific key as an index. This process of processing keys is called hashing. By hashing, we can insert a data with a hashed index.
However, we sometimes may meet collisions, that’s when two data conflict because a specific datum has been placed into a specific index. Hence here’s the technique to prevent collision:
#include <stdio.h>
4. Binary Tree
Binary tree is a type of data structure that represents a tree. By using binary tree, we have another new term that is called ‘height’, which represents how depth is the data.
There’s another type which is called binary search tree. Binary search tree shares similar properties of binary tree. However, there are certain conditions when dealing with data in binary tree:
Here is the link:
https://drive.google.com/file/d/12w_mRAodcUndY9VxEVYhGQs8ke9MMhC2/view?usp=sharing
Happy Coding!
Rangkuman Pembelajaran Selama Semester 1 dan 2 (Semester 1 and 2 Subject Summary):
Here are the main points that I'd like to share with you in order to refresh your memory about the basics.
1. How to output something in C:
- Printf(“This is a text %s”, someText);
- Printf(“This is a text %i”, someNumber);
2. How to input something in C:
- Scanf(“%[^\n]”, someString); // Input a sentence
- Scanf(“%i”, &someNumber); // Input a number
3. Conditional Statements in C:
Long version:
If (statement 1 < statement 2){
printf(“Number 1 is larger than number 2”);
}
Else if (statement 2 > statement 1){
Printf(“Number 2 is larger than number 1”);
}
Else{
Printf(“Same number”);
}
Short version by using ternary operator:
Int value = number 1 < number 2 ? 1 : 0;
4. How to do looping in C?
Using for keyword:
For (int i = 0; i < loopingTimes; i++){
Printf(“Some looping here!\n”);
}
Using while keyword:
While (number < 10){
number++;
}
Using do while keyword:
Do{
Printf(“Some looping here\ n”);
Number1++;
}while(number 1 < number 2);
IMPORTANT!
Do while will execute at least once, while ‘for’ and ‘while’ checks the given condition first in order to do the looping.
5. How to initialize and declare an array in C?
Int arrayNumbers[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
Char arrayCharacters[10] = {};
arrayCharacter[1] = ‘A’;
6. How to do searching in an array:
- Linear Search:
We’ll just have to iterate the variable from index 0 until the end of the array
- Binary Search:
Compare the value of the array in the middle
If match, return the middle index
Else if the value of the index is greater: move to the right half
Else if smaller: move to the left half
7. How to do sorting in array:
- Bubble Sort: repeatedly swapping the number until all numbers in the array is already ordered
- Selection Sort: repeatedly find a minimum number in an array, then put it in the beginning. We have two variables here, that indicates how many elements that haven’t been sorted and so do the sorted one
- Insertion Sort: removes one element from the input data, then finds the location where it should be orderly placed and finally insert the data there.
- Merge Sort: we divide the smallest unit (1 element), then compare each element with the adjacent list to sort and merge 2 adjacent lists. Finally, all the elements are sorted and merged
- Quick Sort: a divide and conquer algorithm. Similar to merge sort, it divides the input array into 2 smaller arrays. However, we’ll do what we call partitioning, which would reorder the array. All elements that have lower values were placed before the pivot and higher values were placed after the pivot.
8. How to process file in C:
- Writing File:
If (file != NULL){
Fprintf(file, “This is a sample text!”);
}
Fclose(file);
- Read File:
Char temp[100] = {};
If (file != NULL){
While(Fscanf(file, “%s”, temp)){
Printf(“%s”, temp);
}
}
Fclose(file);
Rangkuman Pembelajaran Selama Semester 2 (Semester 2 Subject Summary):
===================================Prerequisities======================================
1. In order to learn data structure, you need to know how pointers in program does the job. Here are some quick notes for us to remember:
Pointer is a type of data that references the other data. By using pointer, we have the power to change the value of the pointer. Pointer is marked by using *. To assign a reference to the pointer variable, we can use &.
Int a = 10;
Int *aPointer = &a;
*aPointer = 30;
Printf(“%i”, *aPointer);
Int *a = (int*) malloc(3 * sizeof(int));
By using this command, we have reserved 3 integer memory blocks for variable a. The declare result is similar to: int a[3].
=====================================================================================
1. Linked List: a linear data structure, which represents as a chain that connects from one data to one another. The elements in a linked list were connected by using pointers.
Example of linked list internal data structure:
Struct Node{
Char name[40];
Int age;
Struct Node* next;
}
We can do the following things in linked list:
- Insert a data, either add it at the front, middle, or back of linked list
- Delete a data, either remove it at the front, middle, or back of linked list
- Traverse the nodes one by one to see the contents of linked list
These are the variants of linked list:
- Circular Linked List: A linked list that has no NULL pointer. Instead, the pointer moves back to the beginning of the data if the pointer has reached the end.
- Double linked list: A linked list that has 2 pointers, previous and next. This pointer gives us more flexibility on modifying the data, such as insertion, deletion, and update
- Circular-Double linked list: A linked list that has properties of both circular and double linked list
Here are the differences about linked list compared to arrays:
- We can allocate memory dynamically, this means we can play with the memory while in runtime mode. We can free, add memory, or relocate memory if we wish!
- Keep in mind that in array, we can directly point to the index where a datum lays. However, in linked list, we have to do linear search, by traversing from one datum to another datum to find.
- Speed is not as good as array, as in array, the data are laid sequentially (one datum is located beside another datum). Which means, linked list's data are laid randomly, not beside each other. That's why, there are many more data structurse that were made in order to maintain its search and deletion speed. Linked list is a fundamental data structure that we have to learn in order to learn more about them, as fundamental knowledge lays here.
Implementation code for linked list:
#include <stdio.h>
#include <stdlib.h>
struct Node{
int number;
struct Node* next;
};
Node* head= NULL;
Node* tail= NULL;
Node* oneNode(int number){
Node* temp = (Node* ) malloc(sizeof(Node));
temp->number = number;
temp->next = NULL;
return temp;
}
void pushFront(Node* node){
if (head == NULL){
head = node;
tail = node;
}
else{
Node* newNode = node;
newNode->next = head;
head = newNode;
}
}
void pushTail(Node* node){
if (head == NULL){
head = node;
tail = node;
}
else{
tail->next = node;
tail = tail->next;
}
}
void searchNode(){
Node* temp = head;
printf("You have these data: ");
int length = 0;
while (temp != NULL){
length++;
printf(" %i ", temp->number);
temp = temp->next;
}
printf("Current length is: %i\n",length);
}
void popHead(){
Node* oldHead = head;
head = head->next;
oldHead->next = NULL;
free(oldHead);
}
void popTail(){
Node* temp = head;
while (temp->next->next != NULL){
temp = temp->next;
}
tail = temp;
free(tail->next);
tail->next = NULL;
}
int main(){
int size = 0;
printf("Enter the number of elements you'd like to add: ");
scanf("%i", &size);
getchar();
for (int i = 0; i < size; i++){
printf("Type H (head), or T(tail) (H [number], T[number]) to insert the data: ");
int number = 0;
char letter;
scanf("%c %i", &letter, &number);
if (letter == 'H'){
pushFront(oneNode(number));
}
else if (letter == 'T'){
pushTail(oneNode(number));
}
getchar();
}
searchNode();
printf("Enter the number of elements you'd like to delete: ");
scanf("%i", &size);
getchar();
for (int i = 0; i < size; i++){
printf("Type H (head), or T(tail) (H , T) to delete the data: ");
char letter;
scanf("%c", &letter);
if (letter == 'H'){
popHead();
}
else if (letter == 'T'){
popTail();
}
searchNode();
getchar();
}
}
#include <stdlib.h>
struct Node{
int number;
struct Node* next;
};
Node* head= NULL;
Node* tail= NULL;
Node* oneNode(int number){
Node* temp = (Node* ) malloc(sizeof(Node));
temp->number = number;
temp->next = NULL;
return temp;
}
void pushFront(Node* node){
if (head == NULL){
head = node;
tail = node;
}
else{
Node* newNode = node;
newNode->next = head;
head = newNode;
}
}
void pushTail(Node* node){
if (head == NULL){
head = node;
tail = node;
}
else{
tail->next = node;
tail = tail->next;
}
}
void searchNode(){
Node* temp = head;
printf("You have these data: ");
int length = 0;
while (temp != NULL){
length++;
printf(" %i ", temp->number);
temp = temp->next;
}
printf("Current length is: %i\n",length);
}
void popHead(){
Node* oldHead = head;
head = head->next;
oldHead->next = NULL;
free(oldHead);
}
void popTail(){
Node* temp = head;
while (temp->next->next != NULL){
temp = temp->next;
}
tail = temp;
free(tail->next);
tail->next = NULL;
}
int main(){
int size = 0;
printf("Enter the number of elements you'd like to add: ");
scanf("%i", &size);
getchar();
for (int i = 0; i < size; i++){
printf("Type H (head), or T(tail) (H [number], T[number]) to insert the data: ");
int number = 0;
char letter;
scanf("%c %i", &letter, &number);
if (letter == 'H'){
pushFront(oneNode(number));
}
else if (letter == 'T'){
pushTail(oneNode(number));
}
getchar();
}
searchNode();
printf("Enter the number of elements you'd like to delete: ");
scanf("%i", &size);
getchar();
for (int i = 0; i < size; i++){
printf("Type H (head), or T(tail) (H , T) to delete the data: ");
char letter;
scanf("%c", &letter);
if (letter == 'H'){
popHead();
}
else if (letter == 'T'){
popTail();
}
searchNode();
getchar();
}
}
-> Stack is by means use linked list for implementation. Stack represents as when we are building a house, which we always put or remove the head of the building first. We don’t want to remove the middle part first as this can cause the building to fall.
Operations in stack include:
- Search: we just traverse the node from the beginning to the end.
- Push Head: we just insert the information at the beginning of the linked list.
- Pop Head: we just remove the information at the beginning of the linked list.
On what case do I use stack?
- Infix conversion to prefix and posfix expression. It's really hard to process infix expression for computers. That's why to process the equations efficiently, we can use postfix and prefix expression.
Operations in queue include:
- Search: we just traverse the node from the beginning to the end.
- Push Tail: we just insert the information at the beginning of the linked list.
- Pop Head: we just remove the information at the end of the linked list.
On what case do I use queue?
- To traverse all the nodes in binary tree, we can use queue to save which nodes that have been visited in order to visit its neigbors.
Stack and Queue Implementation:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Node{
char name[30];
int age;
struct Node* next;
struct Node* prev;
};
struct Queue{
struct Node* head;
struct Node* tail;
};
#include <stdlib.h>
#include <string.h>
struct Node{
char name[30];
int age;
struct Node* next;
struct Node* prev;
};
struct Queue{
struct Node* head;
struct Node* tail;
};
struct Stack{
struct Node* head;
struct Node* tail;
};
struct Node* head;
struct Node* tail;
};
Queue* queue = NULL;
Stack* stack = NULL;
Node* temp = NULL;
Node* currNewNode = NULL;
Node* currToBeRemoved = NULL;
Node* curr = NULL;
int choice = 0;
char tempName[20] = {};
int tempValue = 0;
Stack* stack = NULL;
Node* temp = NULL;
Node* currNewNode = NULL;
Node* currToBeRemoved = NULL;
Node* curr = NULL;
int choice = 0;
char tempName[20] = {};
int tempValue = 0;
Node* oneNode(int value, char name[30]){
currNewNode = (Node*) malloc(sizeof(Node));
strcpy(currNewNode->name, name);
currNewNode->age = value;
currNewNode->next = NULL;
currNewNode->prev = NULL;
return currNewNode;
}
currNewNode = (Node*) malloc(sizeof(Node));
strcpy(currNewNode->name, name);
currNewNode->age = value;
currNewNode->next = NULL;
currNewNode->prev = NULL;
return currNewNode;
}
Node* pushHead(Node* node, Node* head){
if (head == NULL){
return node;
}
else{
head->prev = node;
node->next = head;
head = head->prev;
return head;
}
}
if (head == NULL){
return node;
}
else{
head->prev = node;
node->next = head;
head = head->prev;
return head;
}
}
Node* pushTail(Node* node, Node* tail){
if (tail == NULL){
return node;
}
else{
tail->next = node;
node->prev = tail;
tail = tail->next;
return tail;
}
}
if (tail == NULL){
return node;
}
else{
tail->next = node;
node->prev = tail;
tail = tail->next;
return tail;
}
}
void viewAllData(Node* head){
if (head == NULL){
printf("The data is empty!\n");
}
else{
curr = head;
while (curr != NULL){
printf("=========================================\n");
printf("Name: %s\n", curr->name);
printf("Age: %i\n", curr->age);
printf("=========================================\n\n");
curr = curr->next;
}
}
getchar();
}
Node* popHead(Node* head){
if (head == NULL){
printf("There are no people yet...\n");
return head;
}
else if (head->next == NULL){
currToBeRemoved = head;
head = NULL;
return head;
}
else{
currToBeRemoved = head;
head = head->next;
head->prev = NULL;
return head;
}
}
if (head == NULL){
printf("The data is empty!\n");
}
else{
curr = head;
while (curr != NULL){
printf("=========================================\n");
printf("Name: %s\n", curr->name);
printf("Age: %i\n", curr->age);
printf("=========================================\n\n");
curr = curr->next;
}
}
getchar();
}
Node* popHead(Node* head){
if (head == NULL){
printf("There are no people yet...\n");
return head;
}
else if (head->next == NULL){
currToBeRemoved = head;
head = NULL;
return head;
}
else{
currToBeRemoved = head;
head = head->next;
head->prev = NULL;
return head;
}
}
int checkIntegerLimit(int min, int max, char message[100]){
int temp = 0;
do{
printf("%s ", message);
scanf("%i", &temp);
getchar();
}while(temp < min || temp > max);
return temp;
}
int giveDeletedData(Node* node){
if (node == NULL){
printf("There is no data!\n");
getchar();
return -1;
}
else{
printf("You have removed: %s (%i)\n", node->name, node->age);
getchar();
return 1;
}
}
int temp = 0;
do{
printf("%s ", message);
scanf("%i", &temp);
getchar();
}while(temp < min || temp > max);
return temp;
}
int giveDeletedData(Node* node){
if (node == NULL){
printf("There is no data!\n");
getchar();
return -1;
}
else{
printf("You have removed: %s (%i)\n", node->name, node->age);
getchar();
return 1;
}
}
void queueSimulator(){
do{
system("cls");
printf("Queue Simulator\n");
printf("1. Push Tail (Enqueue)\n");
printf("2. Pop Head (dequeue)\n");
printf("3. View People\n");
printf("4. Exit\n");
choice = checkIntegerLimit(1, 4, "Choose:");
if (choice == 1){
printf("Please enter the name: ");
scanf("%[^\n]", tempName);
getchar();
tempValue = checkIntegerLimit(1, 99, "Please enter the age[1-99]:");
queue->tail = pushTail(oneNode(tempValue, tempName), queue->tail);
if (queue->head == NULL){
queue->head = queue->tail;
}
}
else if (choice == 2){
queue->head = popHead(queue->head);
if (queue->head == NULL){
queue->tail = NULL;
}
if (giveDeletedData(currToBeRemoved) == 1){
free(currToBeRemoved);
currToBeRemoved = NULL;
}
}
else if (choice == 3){
viewAllData(queue->head);
}
}while(choice != 4);
}
do{
system("cls");
printf("Queue Simulator\n");
printf("1. Push Tail (Enqueue)\n");
printf("2. Pop Head (dequeue)\n");
printf("3. View People\n");
printf("4. Exit\n");
choice = checkIntegerLimit(1, 4, "Choose:");
if (choice == 1){
printf("Please enter the name: ");
scanf("%[^\n]", tempName);
getchar();
tempValue = checkIntegerLimit(1, 99, "Please enter the age[1-99]:");
queue->tail = pushTail(oneNode(tempValue, tempName), queue->tail);
if (queue->head == NULL){
queue->head = queue->tail;
}
}
else if (choice == 2){
queue->head = popHead(queue->head);
if (queue->head == NULL){
queue->tail = NULL;
}
if (giveDeletedData(currToBeRemoved) == 1){
free(currToBeRemoved);
currToBeRemoved = NULL;
}
}
else if (choice == 3){
viewAllData(queue->head);
}
}while(choice != 4);
}
void stackSimulator(){
do{
system("cls");
printf("Stack Simulator\n");
printf("1. Push Head\n");
printf("2. Pop Head\n");
printf("3. View People\n");
printf("4. Exit\n");
choice = checkIntegerLimit(1, 4, "Choose:");
if (choice == 1){
printf("Please enter the name: ");
scanf("%[^\n]", tempName);
getchar();
tempValue = checkIntegerLimit(1, 99, "Please enter the age[1-99]:");
stack->head = pushHead(oneNode(tempValue, tempName), stack->head);
if (stack->tail == NULL){
stack->tail = stack->head;
}
}
else if (choice == 2){
stack->head = popHead(stack->head);
if (stack->head == NULL){
stack->tail = NULL;
}
if (giveDeletedData(currToBeRemoved) == 1){
free(currToBeRemoved);
currToBeRemoved = NULL;
}
}
else if (choice == 3){
viewAllData(stack->head);
}
}while(choice != 4);
}
do{
system("cls");
printf("Stack Simulator\n");
printf("1. Push Head\n");
printf("2. Pop Head\n");
printf("3. View People\n");
printf("4. Exit\n");
choice = checkIntegerLimit(1, 4, "Choose:");
if (choice == 1){
printf("Please enter the name: ");
scanf("%[^\n]", tempName);
getchar();
tempValue = checkIntegerLimit(1, 99, "Please enter the age[1-99]:");
stack->head = pushHead(oneNode(tempValue, tempName), stack->head);
if (stack->tail == NULL){
stack->tail = stack->head;
}
}
else if (choice == 2){
stack->head = popHead(stack->head);
if (stack->head == NULL){
stack->tail = NULL;
}
if (giveDeletedData(currToBeRemoved) == 1){
free(currToBeRemoved);
currToBeRemoved = NULL;
}
}
else if (choice == 3){
viewAllData(stack->head);
}
}while(choice != 4);
}
void mainMenu(){
do{
system("cls");
printf("Stack and Queue Simulator :) ...\n");
printf("Please choose the app you'd like to use:\n");
printf("1. Queue Simulator\n");
printf("2. Stack Simulator\n");
printf("3. Exit\n");
choice = checkIntegerLimit(1, 3, "Choose:");
if (choice == 1){
queueSimulator();
}
else if (choice == 2){
stackSimulator();
}
}while(choice != 3);
printf("Goodbye!\n");
getchar();
}
do{
system("cls");
printf("Stack and Queue Simulator :) ...\n");
printf("Please choose the app you'd like to use:\n");
printf("1. Queue Simulator\n");
printf("2. Stack Simulator\n");
printf("3. Exit\n");
choice = checkIntegerLimit(1, 3, "Choose:");
if (choice == 1){
queueSimulator();
}
else if (choice == 2){
stackSimulator();
}
}while(choice != 3);
printf("Goodbye!\n");
getchar();
}
int main(){
queue = (Queue*) malloc(sizeof(Queue));
queue->head = NULL;
queue->tail = NULL;
stack = (Stack*) malloc(sizeof(Stack));
stack->head = NULL;
stack->tail = NULL;
mainMenu();
return 0;
}
queue = (Queue*) malloc(sizeof(Queue));
queue->head = NULL;
queue->tail = NULL;
stack = (Stack*) malloc(sizeof(Stack));
stack->head = NULL;
stack->tail = NULL;
mainMenu();
return 0;
}
Hash table is a type of data structure that takes advantage of array by giving a specific key as an index. This process of processing keys is called hashing. By hashing, we can insert a data with a hashed index.
However, we sometimes may meet collisions, that’s when two data conflict because a specific datum has been placed into a specific index. Hence here’s the technique to prevent collision:
- Linear Probing: Moving next datum into next index
- Chaining: By involving linked list, we can attach the data without having to move to the next index. We can do the same operations for hash table like what we do linked list.
#include <stdio.h>
#include <stdlib.h>
struct Hash{
struct Node* head;
struct Node* tail;
};
struct Node{
int value;
Node* next;
Node* prev;
};
Node* curr = NULL;
Hash hashTable[10] = {};
Node* oneNode(int value){
curr = (Node*) malloc(sizeof(Node));
curr->value = value;
curr->next = NULL;
curr->prev = NULL;
return curr;
}
void pushHead(Node* newNode, int arraySize){
int locationData = newNode->value % arraySize;
if (hashTable[locationData].head == NULL){
hashTable[locationData].head = newNode;
hashTable[locationData].tail = newNode;
}
else{
hashTable[locationData].tail->next = newNode;
newNode->prev = hashTable[locationData].tail;
hashTable[locationData].tail = hashTable[locationData].tail->next;
hashTable[locationData].tail->next = NULL;
}
}
void popMiddle(int value, int maxSize){
int locationIndex = value % maxSize;
if (hashTable[locationIndex].head == NULL){
printf("No data.\n");
}
else if(hashTable[locationIndex].head == hashTable[locationIndex].tail){
curr = hashTable[locationIndex].head;
hashTable[locationIndex].head = NULL;
hashTable[locationIndex].tail = NULL;
free(curr);
}
else if (hashTable[locationIndex].head->value == value){
curr = hashTable[locationIndex].head;
hashTable[locationIndex].head = hashTable[locationIndex].head->next;
hashTable[locationIndex].head->prev = NULL;
free(curr);
}
else if (hashTable[locationIndex].tail->value == value){
curr = hashTable[locationIndex].tail;
hashTable[locationIndex].tail = hashTable[locationIndex].tail->prev;
hashTable[locationIndex].tail->next = NULL;
free(curr);
}
else{
curr = hashTable[locationIndex].head;
while (curr != NULL && curr->value != value){
curr = curr->next;
}
if (curr == NULL){
printf("No data!\n");
}
else{
printf("Reached here!\n");
curr->prev->next = curr->next;
curr->next->prev = curr->prev;
curr->next = NULL;
curr->prev = NULL;
free(curr);
}
}
}
void searchNode(int size){
for (int i = 0; i < size; i++){
curr = hashTable[i].head;
printf("%d: ", i+1);
while (curr != NULL){
printf("%d ", curr->value);
curr = curr->next;
}
printf("\n");
}
}
int main(){
printf("============A hash table simulator===========\n");
printf("Please enter how many data to be inserted: ");
int size = 0;
scanf("%i",& size);
int number = 0;
for (int i = 0; i < size; i++){
printf("Please state the number: ");
scanf("%i",& number);
pushHead(oneNode(number), 10);
}
searchNode(10);
printf("Please enter how many data to be deleted: ");
scanf("%i",& size);
for (int i = 0; i < size; i++){
printf("Please state the number: ");
scanf("%i",& number);
popMiddle(number, 10);
}
searchNode(10);
printf(“\n”);
printf(“Thank you for using the app.\n”);
return 0;
}
Binary tree is a type of data structure that represents a tree. By using binary tree, we have another new term that is called ‘height’, which represents how depth is the data.
Example of binary tree internal data structure:
Struct Node{
Char name[40];
Int age;
Struct Node* next;
}
There’s another type which is called binary search tree. Binary search tree shares similar properties of binary tree. However, there are certain conditions when dealing with data in binary tree:
- Left side of the tree must be smaller than the parent
- Right side of the tree must be larger than the parent
- Breadth-First-Search: search by traversing neighbor nodes first and we use queue for the implementation. After neighbor nodes have been visited, we just move to the next neighbor nodes that lies in queue to scan the deeper nodes. ]
- Depth-First-Search: There are three methods to use: inorder (left-print-right), preorder(print, left, right), postorder(left, right, print) traversal.
- AVL Tree
- Red-Black Tree
- B-Tree (2-3 Tree)
- Heap / Priority Queue (an array that represents as a tree)
On what case do I use binary tree?
- In file explorer, folder represents a parent node that contains children, which can be files or another folder
Binary Tree implementation code:
LinkedListNode* oneNode(TreeNode* newNode){
currLinkedList = (LinkedListNode*) malloc(sizeof(LinkedListNode));
currLinkedList->refNode = newNode;
currLinkedList->next = NULL;
return currLinkedList;
}
TreeNode* oneTreeNode(int value){
tempTreeNode = (TreeNode*) malloc(sizeof(TreeNode));
tempTreeNode->data = value;
tempTreeNode->left = NULL;
tempTreeNode->right = NULL;
}
void pushTail(LinkedListNode* newNode){
if (headLinkedList == NULL){
headLinkedList = newNode;
tailLinkedList = newNode;
}
else{
tailLinkedList->next = newNode;
tailLinkedList = tailLinkedList->next;
}
}
TreeNode* popHead(){
if (headLinkedList != NULL){
currLinkedList = headLinkedList;
headLinkedList = headLinkedList->next;
return currLinkedList->refNode;
}
else{
return NULL;
}
}
TreeNode* insertNode(TreeNode* newNode, TreeNode* currentNode){
if (root == NULL){
return newNode;
}
if (currentNode->left != NULL && currentNode->right != NULL){
pushTail(oneNode(currentNode->left));
pushTail(oneNode(currentNode->right));
}
printf("Checking... %i\n", currentNode->data);
if (currentNode->left == NULL){
currentNode->left = newNode;
return;
}
else if (currentNode->right == NULL){
currentNode->right = newNode;
return;
}
else{
TreeNode* checkNode = popHead();
return insertNode(newNode, checkNode);
}
}
void eraseDataLinkedList(){
while (headLinkedList != NULL){
currLinkedList = headLinkedList;
headLinkedList = headLinkedList->next;
free(currLinkedList);
}
headLinkedList = NULL;
currLinkedList = NULL;
}
void searchUsingBFS(){
pushTail(oneNode(root));
tempTreeNode = popHead();
while (tempTreeNode != NULL){
printf("%i ", currLinkedList->refNode->data);
if (tempTreeNode->left != NULL){
pushTail(oneNode(tempTreeNode->left));
}
if (tempTreeNode->right != NULL){
pushTail(oneNode(tempTreeNode->right));
}
tempTreeNode = popHead();
}
}
int main(){
printf("=============A binary tree simulator=============\n");
printf("How many data to be inserted?");
int numberOfData = 0;
scanf("%i",& numberOfData);
int data = 0;
int i = 0;
for (i = 0; i < numberOfData; i++){
printf("Please insert the data (%i): ", i+1);
tempTreeNode = root;
scanf("%i",& data);
if (root == NULL){
root = insertNode(oneTreeNode(data), tempTreeNode);
}
else{
insertNode(oneTreeNode(data), tempTreeNode);
}
eraseDataLinkedList();
}
printf("Searching using breadth first traversal: ");
searchUsingBFS();
eraseDataLinkedList();
return 0;
}
Binary Search Tree code implementation:
#include <stdio.h>
I hope after you have seen my notes, you'll finally regain your coding knowledge. Finally, this is a bonus app from me. It's called Anthony's App Store. You can make modifications for my app if you wish.
#include <stdlib.h>
#include <string.h>
struct Node{
char name[100];
int age;
unsigned long long int nameInASCII;
struct Node* right;
struct Node* left;
} typedef Node;
Node* head = NULL;
Node* temp = NULL;
unsigned long long int giveASCIILength(char nameNew[]){
int index = 0;
unsigned long long int asciiLength = 0;
for (index; nameNew[index] != '\0'; index++){
asciiLength += nameNew[index];
}
return asciiLength;
}
Node* oneNode(int ageNew, char nameNew[100]){
temp = (Node*) malloc(sizeof(Node));
temp->age = ageNew;
strcpy(temp->name, nameNew);
temp->nameInASCII = giveASCIILength(nameNew);
temp->left = NULL;
temp->right = NULL;
return temp;
}
int tempNumber = 0;
unsigned long long int tempLongNumber = 0;
char tempSentence[100] = {};
int length = 0;
int age = 0;
char tempName[100] = {};
void printLine(char message[]){
printf("%s\n", message);
}
int giveRangedNumber(int min, int max, char message[]){
do{
printf("%s ", message);
scanf("%i",& tempNumber);
getchar();
}while(tempNumber< min || tempNumber > max);
return tempNumber;
}
char* giveRangedSentenceLength(int min, int max, char message[]){
do{
printf("%s ", message);
scanf("%[^\n]", tempSentence);
getchar();
length = strlen(tempSentence);
}while(length< min || length > max);
return tempSentence;
}
void printContents(Node* node){
printLine("=========================");
printf("Name: %s\n", node->name);
printf("ASCII value: %llu\n", node->nameInASCII);
printf("Age: %i\n", node->age);
printLine("=========================");
printLine("");
}
void inorderTraversal(Node* current){
if (current != NULL){
inorderTraversal(current->left);
printContents(current);
inorderTraversal(current->right);
}
}
void preorderTraversal(Node* current){
if (current != NULL){
printContents(current);
inorderTraversal(current->left);
inorderTraversal(current->right);
}
}
void postorderTraversal(Node* current){
if (current != NULL){
inorderTraversal(current->left);
inorderTraversal(current->right);
printContents(current);
}
}
void searchOperations(){
int choice = 0;
do{
system("cls");
printLine("Search operation:");
printLine("1. Inorder Traversal");
printLine("2. Preorder Traversal");
printLine("3. Postorder Traversal");
printLine("4. Back");
printLine("If there are no data to be displayed, it means that your content is still empty!");
choice = giveRangedNumber(1, 4, "Choose:");
if (choice == 1){
inorderTraversal(head);
printLine("Done searching!");
getchar();
}
else if (choice == 2){
preorderTraversal(head);
printLine("Done searching!");
getchar();
}
else if (choice == 3){
postorderTraversal(head);
printLine("Done searching!");
getchar();
}
}while(choice != 4);
}
Node* insertBST(Node* newNode, Node* curr){
if (head == NULL){
head = newNode;
return head;
}
else if (curr != NULL){
if (newNode->nameInASCII < curr->nameInASCII){
curr->left = insertBST(newNode, curr->left);
}
else if (newNode->nameInASCII > curr->nameInASCII){
curr->right = insertBST(newNode, curr->right);
}
else{
printLine("A data has the same ASCII value. Cannot be inserted!");
}
}
else{
curr = newNode;
}
return curr;
}
Node* deleteData(Node* current, unsigned long long int asciiValue){
if (head == NULL){
printLine("We cannot delete the data because the name does not exist!");
getchar();
return NULL;
}
else if (current == NULL){
printLine("We could not find the data you requested! Try rechecking your spelling and type again!");
getchar();
}
else if (asciiValue < current->nameInASCII){
current->left = deleteData(current->left, asciiValue);
}
else if (asciiValue > current->nameInASCII){
current->right = deleteData(current->right, asciiValue);
}
else{
// Found the data!
if (current->left == NULL && current->right == NULL){
// No children at all
free(current);
return NULL;
}
else if (current->left == NULL){
// if we want to traverse left-right but there is no value on the left
strcpy(current->name, current->right->name);
current->nameInASCII = current->right->nameInASCII;
current->age = current->right->age;
free(current->right);
current->right = NULL;
}
else{
temp = current->left;
while(temp->right->right != NULL){
printf("Reached here!");
temp = temp->right;
}
strcpy(current->name, temp->right->name);
current->nameInASCII = temp->right->nameInASCII;
current->age = temp->right->age;
free(temp->right);
temp->right = NULL;
}
}
return current;
}
void mainMenu(){
int choice = 0;
do{
system("cls");
printLine("Welcome to Binary Search Tree program!");
printLine("Please choose what to do:");
printLine("1. Insert data");
printLine("2. Delete data");
printLine("3. Search");
printLine("4. Exit");
choice = giveRangedNumber(1, 5, "Choose: ");
if (choice == 1){
printLine("====This will sort the data by ASCII values====");
age = giveRangedNumber(1, 99, "Please enter the age[1-99]:");
strcpy(tempName, giveRangedSentenceLength(10, 100, "Please enter the name [10-100]:"));
head = insertBST(oneNode(age, tempName), head);
printLine("Your data has been inserted!");
getchar();
}
else if (choice == 2){
strcpy(tempName, giveRangedSentenceLength(10, 100, "Please enter the name to be deleted[10-100]:"));
tempLongNumber = giveASCIILength(tempName);
head = deleteData(head, tempLongNumber);
}
else if (choice == 3){
searchOperations();
}
else if (choice == 4){
printLine("Thank you for using my app! :) :) :)");
}
}while(choice != 4);
}
int main(){
mainMenu();
return 0;
}
All these code implemetations that I've provided are taken from my past blogsand exercises.
Here is the link:
https://drive.google.com/file/d/12w_mRAodcUndY9VxEVYhGQs8ke9MMhC2/view?usp=sharing
Happy Coding!
Comments
Post a Comment