Scribd
Upload
8 views4 pages

C Programs for Sorting and Lists

The document contains solutions to multiple programming questions involving stacks, linked lists, and problem solving. For the stack sorting question, it explains an approach using stack operations like push, pop, and insert to sort a stack in ascending order. For finding the nth last element of a linked list, it provides a solution using two pointers - one advances n nodes, and the other advances until the first reaches the end, then counts back to find the nth last node. It also includes solutions for determining ugly numbers, and calculating the maximum number of bananas that can be transferred between two cities given constraints.

Uploaded by

Kannadasan Venugopal
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
8 views4 pages

C Programs for Sorting and Lists

The document contains solutions to multiple programming questions involving stacks, linked lists, and problem solving. For the stack sorting question, it explains an approach using stack operations like push, pop, and insert to sort a stack in ascending order. For finding the nth last element of a linked list, it provides a solution using two pointers - one advances n nodes, and the other advances until the first reaches the end, then counts back to find the nth last node. It also includes solutions for determining ugly numbers, and calculating the maximum number of bananas that can be transferred between two cities given constraints.

Uploaded by

Kannadasan Venugopal
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Q) Given a stack S, write a C program to sort the stack (in the ascending

order)

It can be done using just the stack operations like this:


void sort(stack)
{
    type x;

    if (!isEmpty(stack)) {
        x = pop(stack);
        sort(stack);
        insert(x, stack);
    }            
}
void insert(x, stack)
{
    type y;

    if (!isEmpty(stack) && top(stack) < x) {


        y = pop(stack);
        insert(x, stack);
        push(y, stack);
    } else {
        push(x, stack);
  }
}

Sajid, I think sort should look like,

void sort(stack)
{
    type x;

    if (!isEmpty(stack)) {
        x = pop(stack);
        sort(stack);
    } else
        insert(x, stack);          
}
 
That wouldn't work for:

    stack = 132

Because it omits to reinsert x:

if (!isEmpty(stack)) { /* stack=132 */
    x = pop(stack); /* stack=13 x=2*/ 
    sort(stack); /*stack=31 x=2*/
} else
    insert(x, stack);
}

Q.3.)Given a linked list, your are asked to find out the nth last element in
the linked-list. (n would be given as the argument to the function)

Last nth element is ( l - n + 1)th element from the beginning, so having two pointers:
- Two pointers indicates the list->head at first
- First pointer goes to nth node from the beginning
- Both pointers goes simultaneously until first pointer comes to the end of the list
- Now second pointer walks ( l - n ) nodes, head node is also assumed one walk for two pointers.
- Then secod pointer now indicates the last nth element.

Test Cases:
- List is null
- List is empty
- List with length 1 ( get 1 )
- List with length 2 ( get 1, 2 )
- List with length 3 ( get 3, 1, 2 )
- Any value larger than the size of list

int getLastNth( list_t *list, unsigned int n ) {


int counter;
node_t *p, *q;

if ( NULL == list ) {
fprintf( stderr, "list is null...(getLastNth)\n" );
exit(1);
}

p = list->head;
q = list->head;
for ( counter = 0; p && counter < n - 1; p = p->next, counter++ );

if ( NULL == p ) {
fprintf( stderr, "Index is out boundary...(getLastNth)\n" );
exit(1);
}

while ( p->next ) {
q = q->next;
p = p->next;
}
return q->data;
}

Q) Ugly number is the number whose only prime factors are 2, 3 or 5. By convention, 1 is
included.

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15 are the first 11 ugly numbers.

Write a C program to print nth ugly number using while loop.


* N is a number input given by the user.

//This program will give nth Ugly number


int main(){
int n,count = 0,i=1,temp;
printf(“Enter a number\t:”);
scanf(“%d”,&n);
while(count < n){
temp = i;
while(!(temp%2)) temp /= 2;
while(!(temp%3))temp /= 3;
while(!(temp%5)) temp /= 5;
if(temp==1){
++count;
}
else if(i==1){
++count;
}
if(count == n){
printf(“%d”,i);
}
i++;
}
getch();
}

Q) There are 2 cities A and B, dist. between them is 1000 Km


we have 3000 bananas in city A and a elephant can carry max 1000 bananas at
any given time and it needs to eat a banana every 1 Km.

How Many Max. No. of bananas one can transfer to city B?

Note : the elephant cannot go without bananas to eat.

533.

Pick up 1000, go 200 km, drop 600, return. Pick up 1000, go 200 km, drop
600, return. Pick up 1000, go 200 km, drop 800. Now you have 2000
bananas at 200 km.

Pick up 1000, go 333 km, drop 334, return. Pick up 1000, go 333 km, drop
667. Now you have 1001 bananas at 533 km.
Pick up 1000, go 467 km, drop 533 banans. You now have 533 bananas in
city B and one banana rotting away at 533 km.

You might also like