Data Structures Practical 11
Question 1
Create an interactive game where the user enters a list of strings, and the program sorts them using insertion sort. Allow the user to add or remove strings dynamically and see the sorting process step by step.
strinsertion.c
C
#include <stdio.h>
#include <string.h>
#include <conio.h>
#define MAX_ITEMS 20
#define MAX_CHAR 50
void displayList(char arr[MAX_ITEMS][MAX_CHAR], int size);
void insertionSortStepByStep(char arr[MAX_ITEMS][MAX_CHAR], int size);
int addString(char arr[MAX_ITEMS][MAX_CHAR], int size);
int removeString(char arr[MAX_ITEMS][MAX_CHAR], int size);
void main()
{
char stringList[MAX_ITEMS][MAX_CHAR];
int size = 0;
int choice;
do {
printf("=== STATIC INSERTION SORT PROGRAM ===\n\n");
printf("Current List:\n");
displayList(stringList, size);
printf("\n");
printf("1. Add a string\n");
printf("2. Remove a string\n");
printf("3. Sort step-by-step\n");
printf("4. Exit\n");
printf("Enter your choice (1-4): ");
scanf("%d", &choice);
switch (choice)
{
case 1:
size = addString(stringList, size);
break;
case 2:
size = removeString(stringList, size);
break;
case 3:
if (size < 2)
{
printf("\nNeed at least 2 strings to sort! Press any key...");
getch();
}
else
{
insertionSortStepByStep(stringList, size);
}
break;
case 4:
printf("\nExiting program...\n");
break;
default:
printf("\nInvalid choice! Press any key...");
getch();
}
} while (choice != 4);
getch();
}
void displayList(char arr[MAX_ITEMS][MAX_CHAR], int size)
{
int i;
for (i = 0; i < size; i++)
{
printf("%d: %s\n", i+1, arr[i]);
}
}
int addString(char arr[MAX_ITEMS][MAX_CHAR], int size)
{
if (size >= MAX_ITEMS)
{
printf("\nList is full!", MAX_ITEMS);
return size;
}
printf("\nEnter the string to add: ");
scanf("%s",arr[size]);
printf("String added successfully! Press any key...");
return size + 1;
}
int removeString(char arr[MAX_ITEMS][MAX_CHAR], int size)
{
int index, i;
if (size == 0)
{
printf("\nList is already empty!");
return size;
}
printf("\nEnter the number of the string to remove (1-%d): ", size);
scanf("%d", &index);
fflush(stdin);
index--;
if (index < 0 || index >= size)
{
printf("Invalid index! Press any key...");
return size;
}
for (i = index; i < size - 1; i++)
{
strcpy(arr[i], arr[i + 1]);
}
printf("String removed successfully! ");
return size - 1;
}
void insertionSortStepByStep(char arr[MAX_ITEMS][MAX_CHAR], int size)
{
int i, j;
char key[MAX_CHAR];
printf("--- Beginning Insertion Sort Step-by-Step ---\n\n");
printf("Initial array structure:\n");
displayList(arr, size);
printf("-----------------------------------------\n");
for (i = 1; i < size; i++)
{
strcpy(key, arr[i]);
for (j = i - 1; j >= 0; j--)
{
if (strcmp(arr[j], key) > 0)
{
strcpy(arr[j + 1], arr[j]);
}
else
{
break;
}
}
strcpy(arr[j + 1], key);
}
printf("=== Sorting Complete! ===\n\nFinal Sorted List:\n");
displayList(arr, size);
printf("\nPress any key to return to main menu...");
getch();
}
Output
Question 2
Implement insertion sort with a custom comparison function that sorts strings based on a specific criterion (e.g., number of vowels, number of consonants, etc.).
strinsertion2.c
C
#include <stdio.h>
#include <string.h>
#include <conio.h>
int count_vowels(char str[]);
int compare_strings(char str1[], char str2[]);
void insertion_sort(char arr[20][30], int n);
void main()
{
char strings[20][30];
int n;
int i;
printf("Enter the number of strings you want to sort (max 20): ");
scanf("%d", &n);
printf("Enter %d strings (one per line, no spaces):\n", n);
for (i = 0; i < n; i++) {
printf("String %d: ", i + 1);
scanf("%s", strings[i]);
}
insertion_sort(strings, n);
printf("\nSorted array (by number of vowels, ascending):\n");
for (i = 0; i < n; i++)
{
printf("- %s (Vowels: %d)\n", strings[i], count_vowels(strings[i]));
}
getch();
}
int count_vowels(char str[])
{
int count = 0;
int i = 0;
while (str[i] != '\0')
{
char ch = str[i];
if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u'||
ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' || ch == 'U')
{
count++;
}
i++;
}
return count;
}
int compare_strings(char str1[], char str2[])
{
int v1 = count_vowels(str1);
int v2 = count_vowels(str2);
return v1 - v2;
}
void insertion_sort(char arr[20][30], int n)
{
int i, j;
char key[30];
for (i = 1; i < n; i++)
{
strcpy(key, arr[i]);
for (j = i - 1; j >= 0; j--)
{
if(count_vowels(arr[j])>count_vowels(key))//if (strcmp(arr[j], key) > 0)
{
strcpy(arr[j + 1], arr[j]);
}
else
{
break;
}
}
strcpy(arr[j + 1], key);
}
}
Output
