Untitled
unknown
plain_text
a month ago
32 kB
0
Indexable
Never
#include <stdio.h> #include <stdlib.h> #define MAX 100 struct stackArray { int top; int arr[MAX]; }; struct queue { int front; int rear; int arr[MAX]; }; struct linkedList { int data; struct linkedList *next; }; struct Node { int data; struct Node *next; }; struct Stack { struct Node *top; }; struct QueueNode { int Data; struct QueueNode *next; }; struct Queue { struct QueueNode *Front; struct QueueNode *Rear; }; void stack_as_a_linked_list(); void displaylist(struct linkedList *h); struct stacklist *popsl(struct stacklist *s); void linear_search(); void binary_search(); void bubble_sort(); void selection_sort(); void merge_sort(int[], int, int); void input(); void display(int[], int); void input_q(); void display_q(int[], int); void merge(int[], int, int, int); int split(int[], int, int); void quick_sort(int[], int, int); void insertion_sort(); void radix_sort(); void insertion(); void deletion(); void stack_using_array(); void single_queue(); void double_queue(); void circular_queue(); struct linkedList *insertion_at_begin(struct linkedList *, int); void insertion_at_end(); void insertion_at_position(); void deletion_at_begin(); void deletion_at_end(); void deletion_at_position(); void reversing(); int isEmpty(struct stackArray *h); int isFull(struct stackArray *head); void dequeue(struct queue *q); void displayq(struct queue *h); void single_queue(struct queue *q); void pop(struct stackArray *hm); void displaystack(struct stackArray *he); void stack_using_array(struct stackArray *h); int isFullq(struct queue *head); int isEmptyq(struct queue *head); void traversal(struct linkedList *m); void displayList(struct linkedList *head); struct linkedList *deleteFirstNode(struct linkedList *head); struct linkedList *deleteLastNode(struct linkedList *head); struct linkedList *deleteNodeByValue(struct linkedList *head, int value); struct linkedList *inputList(); void displayStack(struct Stack *stack); int popsll(struct Stack *stack); void pushsll(struct Stack *stack, int value); struct Stack *createStack(); struct Queue *createQueue(); void Enqueue(struct Queue *queue, int value); int Dequeue(struct Queue *queue); void DisplayQueue(struct Queue *queue); void queue_using_linked_list(); void linear_search() { int size; printf("Enter the Size\n"); scanf("%d", &size); int arr[size]; int i; printf("Enter Elements\n"); for (int i = 0; i < size; i++) { scanf("%d", &arr[i]); } printf("Enter Element to be Searched\n"); int k, flag = 0; scanf("%d", &k); for (i = 0; i < size; i++) { if (arr[i] == k) { flag = 1; break; } } if (flag == 1) { printf("Element Found At index %d\n", i); } else { printf("Element Found\n"); } } void binary_search() { int size; printf("Enter the Size\n"); scanf("%d", &size); int arr[size]; printf("Enter Elements\n"); for (int i = 0; i < size; i++) { scanf("%d", &arr[i]); } printf("Enter Element to be Searched\n"); int k, flag = 0; int left = 0; int right = size - 1; while (left <= right) { int mid = (left + right) / 2; if (arr[mid] == k) { printf("Element Found\n"); break; } else if (arr[mid] < k) { left = mid + 1; } else { right = mid - 1; } } printf("Element Not Found\n"); } void bubble_sort() { int size; printf("Enter the Size\n"); scanf("%d", &size); int arr[size]; printf("Enter Elements\n"); for (int i = 0; i < size; i++) { scanf("%d", &arr[i]); } for (int i = 0; i < size; i++) { for (int j = 0; j < size - 1 - i; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } printf("After Sorting\n"); for (int i = 0; i < size; i++) { printf("%d\t", arr[i]); } printf("\n"); } void selection_sort() { int size; printf("Enter the Size\n"); scanf("%d", &size); int arr[size]; printf("Enter Elements\n"); for (int i = 0; i < size; i++) { scanf("%d", &arr[i]); } for (int i = 0; i < size; i++) { int min = i; for (int j = i + 1; j < size; j++) { if (arr[min] > arr[j]) { min = j; } } int temp = arr[min]; arr[min] = arr[i]; arr[i] = temp; } printf("After Sorting\n"); for (int i = 0; i < size; i++) { printf("%d\t", arr[i]); } printf("\n"); } void input() { int size; printf("Enter the Size\n"); scanf("%d", &size); int arr[size]; printf("Enter Elements\n"); for (int i = 0; i < size; i++) { scanf("%d", &arr[i]); } merge_sort(arr, 0, size); display(arr, size); } void merge_sort(int arr[], int left, int right) { if (left < right) { int mid = (left + right) / 2; merge_sort(arr, left, mid); merge_sort(arr, mid + 1, right); merge(arr, left, mid, right); } } void merge(int arr[], int left, int mid, int right) { int i, j, k; int n1 = mid - left + 1; int n2 = right - mid; // Create temporary arrays int L[n1], R[n2]; // Copy data to temporary arrays L[] and R[] for (i = 0; i < n1; i++) L[i] = arr[left + i]; for (j = 0; j < n2; j++) R[j] = arr[mid + 1 + j]; // Merge the temporary arrays back into arr[left..right] i = 0; // Initial index of first subarray j = 0; // Initial index of second subarray k = left; // Initial index of merged subarray while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } // Copy the remaining elements of L[], if there are any while (i < n1) { arr[k] = L[i]; i++; k++; } // Copy the remaining elements of R[], if there are any while (j < n2) { arr[k] = R[j]; j++; k++; } } void display(int arr[], int size) { printf("After Sorting\n"); for (int i = 0; i < size; i++) { printf("%d\t", arr[i]); } printf("\n"); } void insertion_sort() { int size; printf("Enter the Size\n"); scanf("%d", &size); int arr[size]; printf("Enter Elements\n"); for (int i = 0; i < size; i++) { scanf("%d", &arr[i]); } for (int i = 1; i < size; i++) { int j = i - 1; int key = arr[i]; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } printf("After Sorting\n"); for (int i = 0; i < size; i++) { printf("%d\t", arr[i]); } printf("\n"); } void input_q() { int size; printf("Enter the Size\n"); scanf("%d", &size); int arr[size]; printf("Enter Elements\n"); for (int i = 0; i < size; i++) { scanf("%d", &arr[i]); } quick_sort(arr, 0, size - 1); display_q(arr, size); } int split(int arr[], int left, int right) { int pivotgreater = right; int pivotless = left + 1; int pivot = arr[left]; while (pivotgreater >= pivotless) { while (arr[pivotgreater] > pivot) { pivotgreater--; } while (arr[pivotless] < pivot) { pivotless++; } if (pivotgreater > pivotless) { int temp = arr[pivotgreater]; arr[pivotgreater] = arr[pivotless]; arr[pivotless] = temp; } } int temp = arr[left]; arr[left] = arr[pivotgreater]; arr[pivotgreater] = temp; return pivotgreater; } void quick_sort(int arr[], int left, int right) { if (left < right) { int i = split(arr, left, right); quick_sort(arr, left, i - 1); quick_sort(arr, i + 1, right); } } void display_q(int arr[], int size) { printf("After Sorting\n"); for (int i = 0; i < size; i++) { printf("%d\t", arr[i]); } printf("\n"); } void insertion() { int size; printf("Enter the Size\n"); scanf("%d", &size); int arr[size]; printf("Enter Elements\n"); for (int i = 0; i < size; i++) { scanf("%d", &arr[i]); } printf("Enter Position\n"); int pos; scanf("%d", &pos); printf("Enter the Element\n"); int ele; scanf("%d", &ele); for (int i = size - 1; i >= pos; i--) { arr[i + 1] = arr[i]; } arr[pos] = ele; printf("After Sorting\n"); for (int i = 0; i < size; i++) { printf("%d\t", arr[i]); } printf("\n"); } void deletion() { int size; printf("Enter the Size\n"); scanf("%d", &size); int arr[size]; printf("Enter Elements\n"); for (int i = 0; i < size; i++) { scanf("%d", &arr[i]); } printf("Enter the Element to be deleted\n"); int del; int index; scanf("%d", &del); for (int i = 0; i < size; i++) { if (arr[i] == del) { index = i; } } for (int i = index; i < size; i++) { arr[i] = arr[i + 1]; } size--; printf("Updated Array\n"); for (int i = 0; i < size; i++) { printf("%d\t", arr[i]); } } void push(struct stackArray *hm, int value) { if (isFull(hm)) { printf("Stack Overflow\n"); return; } hm->top++; hm->arr[hm->top] = value; while (1) { printf("Do u Want To add more Elements?\n"); int chs; printf("1.Enter Elements\n"); printf("2.Pop\n"); printf("3.Display\n"); printf("4.Quit\n"); scanf("%d", &chs); if (chs == 1) { int es; scanf("%d", &es); hm->top++; hm->arr[hm->top] = es; } else if (chs == 2) { pop(hm); } else if (chs == 3) { displaystack(hm); } else { break; } } } void pop(struct stackArray *hm) { if (isEmpty(hm)) { printf("Stack Underflow\n"); return; } int data = hm->arr[hm->top]; hm->top--; printf("Popped element: %d\n", data); } void displaystack(struct stackArray *he) { if (isEmpty(he)) { printf("Stack Underflow\n"); return; } // printf(""); printf("Stack Elements\n\n"); for (int i = he->top; i >= 0; i--) { printf("%d\t", he->arr[i]); } printf("\n"); printf("\n"); } int isFull(struct stackArray *head) { if (head->top == MAX - 1) { return 1; } return 0; } int isEmpty(struct stackArray *head) { if (head->top == -1) { return 1; } return 0; } void stack_using_array(struct stackArray *h) { printf("1.Push\n"); printf("2.Pop\n"); printf("3.Display\n"); int chs; printf("Enter Choice\n"); scanf("%d", &chs); if (chs == 1) { int elem; printf("Enter element to push: "); scanf("%d", &elem); push(h, elem); } else if (chs == 2) { pop(h); } else if (chs == 3) { displaystack(h); } else { printf("Invalid Choice\n"); } } int isFullq(struct queue *h) { if (h->rear == MAX - 1) { return 1; } return 0; } void enqueue(struct queue *q, int value) { if (isFullq(q)) { printf("Queue is full\n"); return; } q->rear++; q->arr[q->rear] = value; while (1) { } } int isEmptyq(struct queue *h) { if (h->front == -1 && h->rear == -1) { return 1; } return 0; } void dequeue(struct queue *q) { if (isEmptyq(q)) { printf("Queue is empty\n"); return; } q->front++; int data = q->arr[q->front]; printf("Dequeued = %d\n", data); } void displayq(struct queue *h) { if (isEmptyq(h)) { printf("Queue is empty\n"); return; } for (int i = h->front; i <= h->rear; i++) { printf("%d\t", h->arr[i]); } printf("\n"); } void single_queue(struct queue *q) { printf("1.Enqueue\n"); printf("2.Dequeue\n"); printf("3.Display\n"); int ch; printf("Enter Choice\n"); scanf("%d", &ch); if (ch == 1) { int el; printf("Enter Element\n"); scanf("%d", &el); enqueue(q, el); } else if (ch == 2) { dequeue(q); } else { displayq(q); } } struct linkedList *inputl() { struct linkedList *head = NULL; struct linkedList *newNode; int value, choice, position; while (1) { printf("Enter a number (-0 to exit): "); scanf("%d", &value); if (value == -0) { break; } // Create a new node and populate it with data newNode = (struct linkedList *)malloc(sizeof(struct linkedList)); if (newNode == NULL) { printf("Memory allocation failed.\n"); exit(1); } newNode->data = value; newNode->next = NULL; // If the list is empty, set the new node as the head if (head == NULL) { head = newNode; } else { // Otherwise, traverse the list to the end and add the new node struct linkedList *temp = head; while (temp->next != NULL) { temp = temp->next; } temp->next = newNode; } // Display the updated list displaylist(head); } // Provide insertion options while (1) { printf("\nOptions:\n"); printf("1. Insert at beginning\n"); printf("2. Insert at end\n"); printf("3. Insert at specific position\n"); printf("Enter your choice (1, 2, 3) or -0 to exit: "); scanf("%d", &choice); if (choice == -0) { break; } // Handle insertion based on user choice printf("Enter the number to insert: "); scanf("%d", &value); // Create a new node and populate it with data newNode = (struct linkedList *)malloc(sizeof(struct linkedList)); if (newNode == NULL) { printf("Memory allocation failed.\n"); exit(1); } newNode->data = value; newNode->next = NULL; // Handle insertion based on user choice switch (choice) { case 1: // Insert at the beginning newNode->next = head; head = newNode; break; case 2: // Insert at the end if (head == NULL) { head = newNode; } else { struct linkedList *temp = head; while (temp->next != NULL) { temp = temp->next; } temp->next = newNode; } break; case 3: // Insert at specific position printf("Enter the position to insert: "); scanf("%d", &position); if (position <= 0) { printf("Invalid position.\n"); free(newNode); } else if (position == 1) { // Insert at the beginning newNode->next = head; head = newNode; } else { // Traverse the list to the specified position and insert the new node struct linkedList *temp = head; for (int i = 1; i < position - 1 && temp != NULL; ++i) { temp = temp->next; } if (temp == NULL) { printf("Invalid position.\n"); free(newNode); } else { newNode->next = temp->next; temp->next = newNode; } } break; default: printf("Invalid choice. Please enter 1, 2, 3, or -0.\n"); break; } // Display the updated list displaylist(head); } // Return the head of the list return head; } void displaylist(struct linkedList *head) { struct linkedList *current = head; printf("Linked List: "); while (current != NULL) { printf("%d -> ", current->data); current = current->next; } printf("NULL\n"); } void displayList(struct linkedList *d) { struct linkedList *current = d; printf("Linked List: "); while (current != NULL) { printf("%d -> ", current->data); current = current->next; } printf("NULL\n"); } struct linkedList *deleteFirstNode(struct linkedList *d) { if (d == NULL) { printf("List is empty. Cannot delete.\n"); } else { struct linkedList *temp = d; d = d->next; free(temp); printf("First node deleted.\n"); } return d; } struct linkedList *deleteLastNode(struct linkedList *d) { if (d == NULL) { printf("List is empty. Cannot delete.\n"); } else if (d->next == NULL) { free(d); d = NULL; printf("Last node deleted.\n"); } else { struct linkedList *temp = d; while (temp->next->next != NULL) { temp = temp->next; } free(temp->next); temp->next = NULL; printf("Last node deleted.\n"); } return d; } struct linkedList *deleteNodeByValue(struct linkedList *d, int value) { if (d == NULL) { printf("List is empty. Cannot delete.\n"); } else { if (d->data == value) { struct linkedList *temp = d; d = d->next; free(temp); printf("Node with value %d deleted.\n", value); return d; } struct linkedList *temp = d; while (temp->next != NULL && temp->next->data != value) { temp = temp->next; } if (temp->next == NULL) { printf("Node with value %d not found.\n", value); } else { struct linkedList *nodeToDelete = temp->next; temp->next = temp->next->next; free(nodeToDelete); printf("Node with value %d deleted.\n", value); } } return d; } struct linkedList *inputList() { struct linkedList *d = NULL; struct linkedList *newNode; int value; while (1) { printf("Enter a number (-0 to stop input): "); scanf("%d", &value); if (value == -0) { break; } // Create a new node and populate it with data newNode = (struct linkedList *)malloc(sizeof(struct linkedList)); if (newNode == NULL) { printf("Memory allocation failed.\n"); exit(1); } newNode->data = value; newNode->next = NULL; // If the list is empty, set the new node as the head if (d == NULL) { d = newNode; } else { // Otherwise, traverse the list to the end and add the new node struct linkedList *temp = d; while (temp->next != NULL) { temp = temp->next; } temp->next = newNode; } // Display the updated list displayList(d); } return d; } void reverse(struct linkedList *r) { if (r == NULL) return; reverse(r->next); printf("%d\t", r->data); } void stack_using_linked_list() { struct Stack *stack = createStack(); int value; while (1) { printf("Enter a number (-0 to stop input): "); scanf("%d", &value); if (value == -0) { break; } pushsll(stack, value); displayStack(stack); } int choice; while (1) { printf("\nOptions:\n"); printf("1. Pop element\n"); printf("2. Display stack\n"); printf("3. Exit\n"); printf("Enter your choice: "); scanf("%d", &choice); switch (choice) { case 1: value = popsll(stack); if (value != -1) { printf("Popped element: %d\n", value); } displayStack(stack); break; case 2: displayStack(stack); break; case 3: // Free the memory (optional, depending on your requirements) while (stack->top != NULL) { struct Node *temp = stack->top; stack->top = stack->top->next; free(temp); } free(stack); printf("Program exited successfully.\n"); return; default: printf("Invalid choice. Please enter 1, 2, or 3.\n"); break; } } } void displayStack(struct Stack *stack) { struct Node *current = stack->top; printf("Stack: "); while (current != NULL) { printf("%d -> ", current->data); current = current->next; } printf("NULL\n"); } int popsll(struct Stack *stack) { if (stack->top == NULL) { printf("Stack is empty.\n"); return -1; // Return -1 to indicate stack underflow } struct Node *temp = stack->top; int value = temp->data; stack->top = temp->next; free(temp); return value; } void pushsll(struct Stack *stack, int value) { struct Node *newNode = (struct Node *)malloc(sizeof(struct Node)); if (newNode == NULL) { printf("Memory allocation failed.\n"); exit(1); } newNode->data = value; newNode->next = stack->top; stack->top = newNode; } struct Stack *createStack() { struct Stack *stack = (struct Stack *)malloc(sizeof(struct Stack)); if (stack == NULL) { printf("Memory allocation failed.\n"); exit(1); } stack->top = NULL; return stack; } void queue_using_linkedlist() { struct Queue *queue = createQueue(); int Value; int Choice; while (1) { printf("Enter a number (-0 to stop input): "); scanf("%d", &Value); if (Value == -0) { break; } Enqueue(queue, Value); } while (1) { printf("Options:\n"); printf("1. Dequeue\n"); printf("2. Display Queue\n"); printf("3. Exit\n"); printf("Enter your choice: "); scanf("%d", &Choice); switch (Choice) { case 1: { int DequeuedValue = Dequeue(queue); if (DequeuedValue != -1) { printf("Dequeued element: %d\n", DequeuedValue); } DisplayQueue(queue); break; } case 2: DisplayQueue(queue); break; case 3: // Free the memory (optional, depending on your requirements) while (queue->Front != NULL) { struct QueueNode *Temp = queue->Front; queue->Front = queue->Front->next; free(Temp); } free(queue); printf("Program exited successfully.\n"); return; default: printf("Invalid choice. Please enter 1, 2, or 3.\n"); break; } } } void DisplayQueue(struct Queue *queue) { if (queue->Front == NULL) { printf("Queue is empty.\n"); return; } struct QueueNode *current = queue->Front; printf("Queue: "); while (current != NULL) { printf("%d -> ", current->Data); current = current->next; } printf("NULL\n"); } struct Queue *createQueue() { struct Queue *queue = (struct Queue *)malloc(sizeof(struct Queue)); if (queue == NULL) { printf("Memory allocation failed.\n"); exit(1); } queue->Front = NULL; queue->Rear = NULL; return queue; } int Dequeue(struct Queue *queue) { if (queue->Front == NULL) { printf("Queue is empty.\n"); return -1; // Return -1 to indicate queue underflow } struct QueueNode *temp = queue->Front; int Value = temp->Data; queue->Front = temp->next; if (queue->Front == NULL) { queue->Rear = NULL; } free(temp); return Value; } void Enqueue(struct Queue *queue, int Value) { struct QueueNode *newNode = (struct QueueNode *)malloc(sizeof(struct QueueNode)); if (newNode == NULL) { printf("Memory allocation failed.\n"); exit(1); } newNode->Data = Value; newNode->next = NULL; if (queue->Rear == NULL) { queue->Front = newNode; queue->Rear = newNode; } else { queue->Rear->next = newNode; queue->Rear = newNode; } } int main() { printf("1.Searching\n"); printf("2.Sorting\n"); printf("3.Array Operation\n"); printf("4.Stack\n"); printf("5.Queue\n"); printf("6.Linked List\n"); int ch; printf("Enter Your Choice\n"); scanf("%d", &ch); struct linkedList *d; struct stackArray *s; s->top = -1; struct queue *head = (struct queue *)malloc(sizeof(struct queue)); head->front = -1; head->rear = -1; struct stacklist *sl; struct linkedList *h; struct linkedList *rem; switch (ch) { case 1: printf("1.Linear Search\n"); printf("1.Binary Search\n"); int ch2; printf("Enter Your Choice\n"); scanf("%d", &ch2); switch (ch2) { case 1: linear_search(); break; case 2: binary_search(); break; default: printf("Wrong Choice\n"); break; } break; case 2: { int ch3; printf("1.Bubble Sort\n"); printf("2.Selection Sort\n"); printf("3.Merge Sort\n"); printf("4.Insertion Sort\n"); printf("5.Quick Sort\n"); printf("6.Radix Sort\n"); scanf("%d", &ch3); switch (ch3) { case 1: bubble_sort(); break; case 2: selection_sort(); break; case 3: input(); // merge_sort(); break; case 4: insertion_sort(); break; case 5: input_q(); // quick_sort(); break; default: printf("Enter Correct Choice\n"); break; } break; } case 3: printf("1.Insertion\n"); printf("2.Deletion\n"); int ch4; printf("Enter Your Choice\n"); scanf("%d", &ch4); switch (ch4) { case 1: insertion(); break; case 2: deletion(); break; default: printf("Enter Correct Choice\n"); break; } break; case 4: printf("1.Stack Using Array\n"); printf("2.Stack Using Linked List\n"); int ch5; printf("Enter Your Choice\n"); scanf("%d", &ch5); switch (ch5) { case 1: stack_using_array(s); break; case 2: stack_using_linked_list(); break; default: printf("Enter Correct Choice\n"); break; } break; case 5: printf("1.Single Ended Queue\n"); printf("2.Queue Using Linked_List\n"); int ch6; printf("Enter Your Choice\n"); scanf("%d", &ch6); switch (ch6) { case 1: single_queue(head); break; case 2: queue_using_linkedlist(); break; default: printf("Enter Correct Choice\n"); break; } break; case 6: printf("1.Insertion\n"); printf("2.Deletion\n"); printf("3.Reverse Linked List\n"); int ch7; printf("Enter Your Choice\n"); scanf("%d", &ch7); switch (ch7) { case 1: printf("1.Insertion At Beginning\n"); printf("2.Insertion At End\n"); printf("3.Insertion At Specific Position\n"); int ch71; scanf("%d", &ch71); printf("Enter Your Choice\n"); switch (ch71) { case 1: h = inputl(); displaylist(h); break; default: printf("Enter Correct Choice\n"); break; } break; case 2: d = inputList(); int choice, valueToDelete; while (1) { printf("\nDeletion Options:\n"); printf("1. Delete first node\n"); printf("2. Delete last node\n"); printf("3. Delete a specific node by value\n"); // printf("4. Exit\n"); printf("Enter your choice: "); int ch72; scanf("%d", &ch72); switch (ch72) { case 1: d = deleteFirstNode(d); displayList(d); break; case 2: d = deleteLastNode(d); displayList(d); break; case 3: printf("Enter the value to delete: "); scanf("%d", &valueToDelete); d = deleteNodeByValue(d, valueToDelete); displayList(d); break; } break; } break; case 3: rem = inputList(); printf("Before Reversing : \n"); displayList(rem); printf("After Reversing : \n"); reverse(rem); break; default: printf("Enter Correct Choice\n"); break; } } }