8. (10pts) Using your doubly-linked list and reverse function, write a function

Question

8. (10pts) Using your doubly-linked list and reverse function, write a function isPalyndrome(struct listnode* head) that returns 1 if the string encoded in your list is a palyndrome and 0 if it is not.

9. (10pts) Construct a binary search tree (BST) that stores integers (i.e. the descendants to the left of a node are less than or equal to the node and the descendants to the right of the node are greater than or equal to the node). Insert integers 100, 75, 50, 125, 25, 150 into the tree. Write the function preorderPrint(treenode*) that uses recursion to perform a preorder traversal of the tree and print the values.

10. (10pts) See previous problem. Write the function nr_preorder_print(treenode*) that performs a preorder traversal of the tree WITHOUT recursion. Instead, implement a stack (singly-linked list manipulated with push(...)/pop(...) functions) to aid with the traversal.

11. (10 pts) Write the function bitcount(unsigned x) that returns the number of 1-bits in the unsigned integer argument x.

12. (10 pts) Write the function invert(unsigned int x, int p, int n) that returns x with the n bits that begin in position p inverted, leaving the others unchanged. Example: x = 0000 1111 1010 1010 1010 p = 7 n = 5 y = invert(x, p, n) = 0000 1110 0101 1010 1010

13. (10 pts) Write the function rightRot(int x, int n) that returns the value of the integer x rotated to the right by n bit positions. Example: x = 0000 0000 0011 1100 y = rightRot(x, 4) = 1100 0000 0000 0011

14. (20pts) Write the function setBits(int x, int p, int n, int y) that returns x with the n bits that begin at position p set to the rightmost n bits of y. All other bits should remain unchanged. Example: x = 1010 1010 1010 1010 y = 1100 1100 1100 1100 z = setBits(x, 2, 4, y) = 1011 0010 1010 1010

Explanation / Answer

Solution:

Multiple question asked

8)
#include <stdio.h>
#include <stdlib.h>

// Define structure
struct listNode
{
char val;
struct listNode *next;
struct listNode *prev;  
};

// Reverse function
void reverse(struct listNode **head)
{
     struct listNode *te = NULL;
     struct listNode *curr = *head;
     while (curr != NULL)
     {
       te = curr->prev;
       curr->prev = curr->next;
       curr->next = te;            
       curr = curr->prev;
     }    
     if(te != NULL )
        *head = te->prev;
}   

// Insert to linked list
void insertDLL(struct listNode** head, char newVal)
{
    struct listNode* ne =(struct listNode*) malloc(sizeof(struct listNode));
    ne->val = newVal;
    ne->prev = NULL;
    ne->next = (*head);
    if((*head) != NULL)
      (*head)->prev = ne ;
    (*head)    = ne;

}

// print the list
void printDLL(struct listNode *nod)
{

while(nod!=NULL)
{
   printf("%c ", nod->val);
   nod = nod->next;
}
}

// Check palindrome
bool isPalyndrome(struct listNode* head)
{
   char ar[100],ar1[100];
   int i=0;
   struct listNode *temp=head;
   while(temp!=NULL)
   {
      ar[i++]=temp->val;
      temp=temp->next;
   }
   reverse(&head);
   i=0;
   while(head!=NULL)
   {
      if(head->val!=ar[i++])
          return false;
      head=head->next;
   }
   return true;
}

int main()
{
struct listNode* head = NULL;
insertDLL(&head, 'm');
insertDLL(&head, 'a');
insertDLL(&head, 'd');
insertDLL(&head, 'a');
insertDLL(&head, 'm');
if(isPalyndrome(head))
      printf("Palindrome ");
else
      printf("Not Palindrome ");
getchar();
return 0;
}

Output:

Palindrome

Related Questions

Navigate

• Browse (All)
• Browse 8
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.