I am having a problem with my program in C, for some reason it does not give back the right results I am looking for. When I run it it shows the instructions twice and then says invalid choice even when I have not inputted a choice, when I do put a choice it doesn't out output what I want it to even though I believe the code is right.
This is the question:
And this is the output that the program gives:
The code is as follows:
#include <stdio.h>
#include <stdlib.h>
int arr[100005];
int n;
void max(int index){
if (index>=n)return;
int left=2*index 1;
int right = 2*index 2;
int mx_ind=index;
if (left < n && arr[left]>arr[mx_ind]){
mx_ind=left;
}
if (right < n && arr[left]>arr[mx_ind]){
mx_ind=right;
}
if (mx_ind !=index){
int tmp=arr[mx_ind];
arr[mx_ind]=arr[index];
arr[index]=tmp;
max(mx_ind);
}
}
int insert(int num,int location){
int p;
while (location>0)
{
p=(location-1)/2;
if(num>=arr[p])
{
arr[location]=arr[p];
}
else break;
location=p;
}
arr[location]=num;
return 0;
}
void del(int index){
arr[index]=arr[n-1];
n=n-1;
max(index);
}
void buildmaxheap(){
for (int i=n/2-1;i>=0;i--){
max(i);
}
}
void display(){
for (int i=0;i<n;i ){
printf("%d",arr[i]);
printf("\n");
}
}
int returnmax(){
return arr[0];
}
int extractmax(){
int mx=arr[0];
del(0);
return mx;
}
int main()
{
printf("enter num of elements");
scanf("%d",&n);
printf("enter value of elements");
for(int i=0;i<n;i ){
scanf("%d",&arr[i]);
}
buildmaxheap();
int num,index;
char choice;
while(1){
printf("1. extract max\n");
printf("2. insert new key\n");
printf("3. change key at A[i]\n");
printf("4. delete key at A[i] \n");
printf("5. return max\n");
printf("6. exit\n");
printf("Enter your choice:");
scanf("%c",&choice);
switch(choice)
{
case '1':
printf("Max value is : %d\n", extractmax);
break;
case '2':
scanf("%d",&num);
insert(num,n);
n ;
printf("Content of array is:");
display();
break;
case '3':
scanf("%d %d",&index,&num);
arr[index]=num;
if (arr[(index-1)/2]>num)max(index);
else insert(num,index);
printf("content of array is : ");
display();
break;
case '4':
scanf("%d",&index);
del(index);
printf("Content of array is : \n");
display();
break;
case '5':
printf("Max value is : %d\n", extractmax);
break;
case '6':
exit(1);
break;
default:printf("invalid choice\n");
}
}
return 0;
}
Any help would be appreciated.
CodePudding user response：
A few issues:
The "invalid choice" output occurs because
choicegets a white space (line break) as value. To avoid that white space is taken as the choice, exclude that by prefixing thescanfformat string with a space:scanf(" %c", &choice)In
maxyou have a bug in the secondifcondition. You should userightas index instead ofleftFor some operations it is required that the array is not empty. This should be checked to avoid problems.
In case 3 the expression
arr[(index - 1) / 2]is invalid whenindexis zero.
Furthermore, I would suggest not calling exit(1) when the user chooses 6, but make that a while condition.
Here is a corrected version:
#include <stdio.h>
#include <stdlib.h>
int arr[100005];
int n;
void max(int index) {
if (index >= n) return;
int left = 2 * index 1;
int right = left 1;
int mx_ind = index;
if (left < n && arr[left] > arr[mx_ind]) {
mx_ind = left;
}
if (right < n && arr[right] > arr[mx_ind]) { // bug fix
mx_ind = right;
}
if (mx_ind != index) {
int tmp = arr[mx_ind];
arr[mx_ind] = arr[index];
arr[index] = tmp;
max(mx_ind);
}
}
int insert(int num, int location){
int p;
while (location > 0) {
p = (location - 1) / 2;
if (num >= arr[p]) {
arr[location] = arr[p];
}
else break;
location = p;
}
arr[location] = num;
return 0;
}
void del(int index) {
arr[index] = arr[n - 1];
n--;
max(index);
}
void buildmaxheap() {
for (int i = n / 2 - 1; i >= 0; i--) {
max(i);
}
}
void display() {
for (int i = 0; i < n; i ) {
printf("%d ", arr[i]);
}
printf("\n");
}
int returnmax() {
return arr[0];
}
int extractmax() {
int mx = arr[0];
del(0);
return mx;
}
int main() {
printf("enter num of elements: ");
scanf("%d", &n);
printf("enter value of elements: ");
for(int i = 0; i < n; i ) {
scanf("%d", &arr[i]);
}
buildmaxheap();
int num,index;
char choice = ' ';
while (choice != '6') { // Nicer to add the condition here
// Maybe always start each iteration with this:
printf("Content of array is: ");
display();
printf("1. extract max\n");
printf("2. insert new key\n");
printf("3. change key at A[i]\n");
printf("4. delete key at A[i] \n");
printf("5. return max\n");
printf("6. exit\n");
printf("Enter your choice: ");
scanf(" %c", &choice); // Skip white space
switch (choice) {
case '1':
if (n == 0) { // Add this protection
printf("The array is empty\n");
} else {
// Should call the function
printf("Max value is: %d\n", extractmax());
}
break;
case '2':
scanf("%d", &num);
insert(num, n);
n ;
break;
case '3':
// Help the user:
printf("Enter index and new value: ");
scanf("%d %d", &index, &num);
// Add this protection:
if (index >= n) {
printf("The array does not have this index\n");
} else {
arr[index] = num;
// Add case for when index is 0
if (index == 0 || arr[(index - 1) / 2] > num) max(index);
else insert(num, index);
}
break;
case '4':
// Help the user:
printf("Enter index: ");
scanf("%d", &index);
// Add this protection:
if (index >= n) {
printf("The array does not have this index\n");
} else {
del(index);
}
break;
case '5':
if (n == 0) { // Add this protection
printf("The array is empty\n");
} else {
// Call the function, and the right one:
printf("Max value is : %d\n", returnmax());
}
break;
case '6':
break; // Just break and use while condition to quit (no exit())
default:
printf("invalid choice '%c'\n", choice);
}
}
return 0;
}
The names for the functions max and insert are misleading. max is not returning a maximum value, and insert is not making the list longer. It is more common to name these functions respectively siftDown and siftUp, or something similar.