Write a function in C++ to generate an N-node random binary search t.pdf

Jul 2, 20230 likes27 views

Write a function in C++ to generate an N-node random binary search tree with distinct keys 1 through N. Assume that you have available a function, randInt(lower,upper), that generates a uniform random integer in the appropriate closed interval. What is the running time of your routine? Solution / A C++ prgroam to contrcut all unique BSTs for keys from 1 to n #include #include using namespace std; // node structure struct node { int key; struct node *left, *right; }; // A utility function to create a new BST node struct node *newNode(int item) { struct node *temp = new node; temp->key = item; temp->left = temp->right = NULL; return temp; } // A utility function to do preorder traversal of BST void preorder(struct node *root) { if (root != NULL) { cout << root->key << \" \"; preorder(root->left); preorder(root->right); } } // function for constructing trees vector constructTrees(int start, int end) { vector list; /* if start > end then subtree will be empty so returning NULL in the list */ if (start > end) { list.push_back(NULL); return list; } /* iterating through all values from start to end for constructing\\ left and right subtree recursively */ for (int i = start; i <= end; i++) { /* constructing left subtree */ vector leftSubtree = constructTrees(start, i - 1); /* constructing right subtree */ vector rightSubtree = constructTrees(i + 1, end); /* now looping through all left and right subtrees and connecting them to ith root below */ for (int j = 0; j < leftSubtree.size(); j++) { struct node* left = leftSubtree[j]; for (int k = 0; k < rightSubtree.size(); k++) { struct node * right = rightSubtree[k]; struct node * node = newNode(i);// making value i as root node->left = left; // connect left subtree node->right = right; // connect right subtree list.push_back(node); // add this tree to list } } } return list; } // Driver Program to test above functions int main() { // Construct all possible BSTs vector totalTreesFrom1toN = constructTrees(1, 3); /* Printing preorder traversal of all constructed BSTs */ cout << \"Preorder traversals of all constructed BSTs are \ \"; for (int i = 0; i < totalTreesFrom1toN.size(); i++) { preorder(totalTreesFrom1toN[i]); cout << endl; } return 0; } Output:.

$} // function for constructing trees vector constructTrees(int start, int end) { vector list; /* if start > end then subtree will be empty so returning NULL in the list */ if (start > end) { list.push_back(NULL); return list; } /* iterating through all values from start to end for constructing left and right subtree recursively */ for (int i = start; i <= end; i++) { /* constructing left subtree */ vector leftSubtree = constructTrees(start, i - 1); /* constructing right subtree */ vector rightSubtree = constructTrees(i + 1, end); /* now looping through all left and right subtrees and connecting them to ith root below */ for (int j = 0; j < leftSubtree.size(); j++) { struct node* left = leftSubtree[j]; for (int k = 0; k < rightSubtree.size(); k++) { struct node * right = rightSubtree[k]; struct node * node = newNode(i);// making value i as root node->left = left; // connect left subtree node->right = right; // connect right subtree list.push_back(node); // add this tree to list } } } return list;$

}
// Driver Program to test above functions
int main()
{
// Construct all possible BSTs
vector totalTreesFrom1toN = constructTrees(1, 3);
/* Printing preorder traversal of all constructed BSTs */
cout << "Preorder traversals of all constructed BSTs are ";
for (int i = 0; i < totalTreesFrom1toN.size(); i++)
{
preorder(totalTreesFrom1toN[i]);
cout << endl;
}
return 0;
}
Output:

Write a program that accepts an arithmetic expression of unsigned integers in postfix notation and builds the arithmetic expression tree that represents that expression. From that tree, the corresponding fully parenthesized infix expression should be displayed and a file should be generated that contains the three address format instructions. This topic is discussed in the week 4 reading in module 2, section II-B. The main class should create the GUI shown below: Pressing the Construct Tree button should cause the tree to be constructed and using that tree, the corresponding infix expression should be displayed and the three address instruction file should be generated. The postfix expression input should not be required to have spaces between every token. Note in the above example that 9+- are not separated by spaces. The above example should produce the following output file containing the three address instructions: Add R0 5 9 Sub R1 3 R0 Mul R2 2 3 Div R3 R1 R2 Inheritance should be used to define the arithmetic expression tree. At a minimum, it should involve three classes: an abstract class for the tree nodes and two derived classes, one for operand nodes and another for operator nodes. Other classes should be included as needed to accomplish good object-oriented design. All instance data must be declared as private. You may assume that the expression is syntactically correct with regard to the order of operators and operands, but you should check for invalid tokens, such as characters that are not valid operators or operands such as 2a, which are not valid integers. If an invalid token is detected a RuntimeException should be thrown and caught by the main class and an appropriate error message should be displayed. Three Adddress Generator Enter Postfix Expression 359 2 3 Construct Tree Infix Expression ((3-(5 9))/ (2* 3 Solution #include #include #include #include #include struct TREE //Structure to represent a tree { char data; struct TREE *right,*left,*root; }; typedef TREE tree; /* Stack Using Linked List */ struct Stack //Structure to represent Stack { struct TREE *data; struct Stack *next,*head,*top; //Pointers to next node,head and top }; typedef struct Stack node; node *Nw; //Global Variable to represent node void initialize(node *&n) { n = new node; n -> next = n -> head = n -> top = NULL; } void create(node *n) { Nw = new node; //Create a new node Nw -> next = NULL; //Initialize next pointer field if(n -> head == NULL) //if first node { n -> head = Nw; //Initialize head n -> top = Nw; //Update top } } void push(node *n,tree *ITEM) { node *temp = n -> head; if(n -> head == NULL) //if First Item is Pushed to Stack { create(n); //Create a Node n -> head -> data = ITEM; //Insert Item to head of List n -> head = Nw; return; //Exit from Function } create(n); //Create a new Node Nw -> data = ITEM; //Insert Item while(temp -> next != NULL) temp = temp -> next; //Go to Last Node temp -> next = Nw; //Point New node n -> top = Nw; //Upda.

DS group binary tree all information M.pptxAjajKhan23

hi i have to write a java program involving link lists. i have a pro.pdfarchgeetsenterprises

hi i have to write a java program involving link lists. i have a problem with the nodes, as it is posting errors with the nodes. please help me with this problem. thank you. public class LinkLists { /* only need to store a single pointer to the node at the head * of the list. * The pointer is null if the list is empty. * Also record the size of the list. */ protected Node head; /* invariant: size is the number of nodes in the list pointed to by head */ protected int size; /* no-arguments default constructor creates an empty list */ public LinkLists() { head = null; // start with an empty list size = 0; } /* accessor method */ public int size() { return size; } /* value to add to the end of the list */ public void add(T value) { head = addAtEnd(head, value); size++; } /* node of the list to which the value should be added * value to add to the end of the list */ private Node addAtEnd(Node node, T value) { if (node == null) { // special case return new Node(value, null); } else if (node.getNext() == null) { // other special case node.setNext(new Node(value, null)); } else { addAtEnd(node.getNext(), value); } return node; } /* iterative implementation of the same method * value to add to the end of the list */ public void add2(T value) { if (head == null) { head = new Node(value, null); } else { Node node = head; // guaranteed not to be null initially while (node.getNext() != null) { node = node.getNext(); // guaranteed not to be null here } // now, node.getNext() is guaranteed to be null // similar to the second special case in addAtEnd node.setNext(new Node(value, null)); } size++; } public void remove(int position) throws BadItemCountException { if ((position < 1) || (position > size)) { throw new BadItemCountException(\"invalid position \" + position + \", only 1..\" + size + \" available\"); } if (position == 1) { head = head.getNext(); } else { Node node = head; for (int i = 2; i < position; i++) { node = node.getNext(); } node.setNext(node.getNext().getNext()); } size--; // one less item } public String toString() { return toString(head); } private String toString(Node node) { if (node == null) { return \"\"; } else { return node.getValue() + \"\ \" + toString(node.getNext()); } } public static void main(String[] args) { /* create two empty lists, make sure they print out correctly */ LinkLists list1 = new LinkLists(); LinkLists list2 = new LinkLists(); System.out.println(\"list1 = \'\" + list1 + \"\', list2 = \'\" + list2 + \"\'\"); System.out.println(\"list1.size() = \" + list1.size() + \", list2.size() = \" + list2.size()); /* insert some items, keep checking */ list1.add(\"hello\"); list1.add(\"world\"); list2.add(\"foo\"); list2.add(\"bar\"); list2.add(\"baz\"); System.out.println(\"list1 = \'\" + list1 + \"\', list2 = \'\" + list2 + \"\'\"); System.out.println(\"list1.size() = \" + list1.size() + \", list2.size() = \" + list2.size()); /* remove an item at an invalid position */ boolean caught = false; try { list2.remove(4); } catch .

C program to insert a node in doubly linked listSourav Gayen

This C program implements functions to create and manipulate a doubly linked list. It allows the user to choose from a menu to create a list, insert nodes at the beginning, end, or a specified position, and display the list. Functions are defined to create a list by dynamically allocating nodes and linking them together, insert nodes at different positions by updating next and prev pointers, and display the list by traversing from head to tail.

DATASTRUCTURES PPTS PREPARED BY M V BRAHMANANDA REDDYMalikireddy Bramhananda Reddy

This document discusses binary search trees and provides source code to implement binary search tree traversal operations. It explains that a binary search tree is a binary tree where the left child of a node is less than the parent and the right child is greater. It provides code for preorder, inorder, and postorder traversals of the binary search tree and outputs the traversal order for a sample tree.

Lab-2.4 101.pdf21E135MAHIESHWARJ

The document contains C program code to implement three data structures using linked lists: 1) A stack using a singly linked list with push, pop, and display functions. 2) A queue using a singly linked list with enqueue, dequeue, and display functions. 3) A program to merge two sorted linked lists by comparing nodes and appending to the merged list. Pseudocode and sample test cases are provided for each problem.

How do you stop infinite loop Because I believe that it is making a.pdffeelinggift

How do you stop infinite loop? Because I believe that it is making an infinite circular list. c++ code: Here is the list class: #ifndef LIN_J_LIST #define LIN_J_LIST typedef unsigned int uint; #include #include using namespace std; /** * a simplified generic singly linked list class to illustrate C++ concepts * @author Jerry Lin * @version 2/17/17 */ template< typename Object > class List { private: /** * A class to store data and provide a link to the next node in the list */ class Node { public: /** * The constructor * @param data the data to be stored in this node */ explicit Node( const Object & data ) : data{ data }, next{ nullptr } {} Object data; Node * next; }; public: /** * The constructor for an empty list */ List() : size{ 0 }, first{ nullptr }, last{ nullptr } {} /** * the copy constructor-creates and copy the list */ List( List && rhs ) = delete; List( const List & rhs ) { count = 0; size = 0; if(rhs.size != 0) { push_front(rhs.front()); Node * current = rhs.first; Node * tempNode = first; size++; while(current->next != nullptr) { current = current->next; Node *newNode = new Node(current->data); //transfer the data. basic op. count++; tempNode->next = newNode; last = newNode; tempNode = tempNode->next; size++; } } // you document and implement this method } /** * the operator= method-copies the list */ List & operator=( List && rhs) = delete; List & operator=( const List & rhs ) { count = 0; size = 0; if( size != 0 ) { Node * current = first; Node * temp; while( current != nullptr ) { temp = current; current = current->next; delete temp; } } if(rhs.size!= 0) { push_front(rhs.front()); Node * current = rhs.first; Node * tempNode = first; //create a temporary to store size++; while(current -> next != nullptr) { current = current->next; Node *newNode = new Node(current->data); //transfer the data. basic op count++; tempNode->next = newNode; last = newNode; tempNode = tempNode -> next; size++; } } return *this; // you document and implement this method } /** * accessor * @return count */ int get_count() const { return count; } /** * The destructor that gets rid of everything that\'s in the list and * resets it to empty. If the list is already empty, do nothing. */ ~List() { if( size != 0 ) { Node * current = first; Node * temp; while( current != nullptr ) { temp = current; current = current->next; delete temp; } } } /** * Put a new element onto the beginning of the list * @param item the data the new element will contain */ void push_front( const Object& item ) { Node * new_node = new Node( item );//basic op. if(is_empty()) { last = new_node; } else { new_node->next = first; } first = new_node; size++; /* you complete the rest */ } /** * Remove the element that\'s at the front of the list. Causes an * assertion error if the list is empty. */ void pop_front() { assert( !is_empty() ); Node * temp = first; if( first == last ) { first = last = nullptr; } else { first = first->next; } delete temp; size--; } /** * Accessor to return the da.

Please read the comment ins codeExpressionTree.java-------------.pdfshanki7

Please read the comment ins code ExpressionTree.java ---------------------------------- /** * This is the class for Expression Tree. * Used to create Expression Tree and Evaluate it */ /** * Following logic is used to construct a Tree * Here we use stack for Preparing Tree * Loop through given Expression String * If Character is Operand , Create node and push to stack * If Character is Operator then * 1)Create Node for Operator * 2)Pop 2 nodes from Stack and Made * OpretorNode--> left == first node pop * OpretorNode--> right == second node pop * At the end of creation of Expression Tree, Stack have only one node , which is root of Expression tree */ /** Class ExpressionTree **/ class ExpressionTree { /** class TreeNode * Stored Character ==> Digit(0..9) or a Operator +,-,*,/ * Left Node and Right Node * * **/ class TreeNode { char data; TreeNode left, right; /** constructor **/ public TreeNode(char data) { this.data = data; this.left = null; this.right = null; } } /** class StackNode **/ class StackNode { TreeNode treeNode; StackNode next; /** constructor **/ public StackNode(TreeNode treeNode) { this.treeNode = treeNode; next = null; } } private static StackNode top; /** constructor * Constructor takes input string like \"+-+7*935*82*625\" * Input should be in Prefix notation * **/ public ExpressionTree(String expression) { top = null; //Call Method for prepare expression tree buildTree(expression); } /** function to clear tree **/ public void clear() { top = null; } /** function to push a node **/ private void push(TreeNode ptr) { if (top == null) top = new StackNode(ptr); else { StackNode nptr = new StackNode(ptr); nptr.next = top; top = nptr; } } /** function to pop a node * When it find operator pop 2 elements from Stack * * **/ private TreeNode pop() { if (top == null) throw new RuntimeException(\"Underflow\"); else { TreeNode ptr = top.treeNode; top = top.next; return ptr; } } /** function to get top node **/ private TreeNode peek() { return top.treeNode; } /** function to insert character **/ private void insert(char val) { try { //If Operand , Create node and push to Stack if (isDigit(val)) { TreeNode nptr = new TreeNode(val); push(nptr); } //If Operator , Create node and popup 2 elements and make them its right and left else if (isOperator(val)) { TreeNode nptr = new TreeNode(val); nptr.left = pop(); nptr.right = pop(); push(nptr); } } catch (Exception e) { System.out.println(\"Invalid Expression\"); } } /** function to check if digit **/ private boolean isDigit(char ch) { return ch >= \'0\' && ch <= \'9\'; } /** function to check if operator **/ private boolean isOperator(char ch) { return ch == \'+\' || ch == \'-\' || ch == \'*\' || ch == \'/\'; } /** function to convert character to digit **/ private int toDigit(char ch) { return ch - \'0\'; } /** function to build tree from input */ public void buildTree(String eqn) { for (int i = eqn.length() - 1; i >= 0; i--) insert(eqn.charAt(i)); } /** function to evaluate tree */ public dou.

A)B) C++ program to create a Complete Binary tree from its Lin.pdfanton291

A) B) // C++ program to create a Complete Binary tree from its Linked List // Representation #include #include #include using namespace std; // Linked list node struct ListNode { int data; ListNode* next; }; // Binary tree node structure struct BinaryTreeNode { int data; BinaryTreeNode *left, *right; }; // Function to insert a node at the beginning of the Linked List void push(struct ListNode** head_ref, int new_data) { // allocate node and assign data struct ListNode* new_node = new ListNode; new_node->data = new_data; // link the old list off the new node new_node->next = (*head_ref); // move the head to point to the new node (*head_ref) = new_node; } // method to create a new binary tree node from the given data BinaryTreeNode* newBinaryTreeNode(int data) { BinaryTreeNode *temp = new BinaryTreeNode; temp->data = data; temp->left = temp->right = NULL; return temp; } // converts a given linked list representing a complete binary tree into the // linked representation of binary tree. void convertList2Binary(ListNode *head, BinaryTreeNode* &root) { // queue to store the parent nodes queue q; // Base Case if (head == NULL) { root = NULL; // Note that root is passed by reference return; } // 1.) The first node is always the root node, and add it to the queue root = newBinaryTreeNode(head->data); q.push(root); // advance the pointer to the next node head = head->next; // until the end of linked list is reached, do the following steps while (head) { // 2.a) take the parent node from the q and remove it from q BinaryTreeNode* parent = q.front(); q.pop(); // 2.c) take next two nodes from the linked list. We will add // them as children of the current parent node in step 2.b. Push them // into the queue so that they will be parents to the future nodes BinaryTreeNode *leftChild = NULL, *rightChild = NULL; leftChild = newBinaryTreeNode(head->data); q.push(leftChild); head = head->next; if (head) { rightChild = newBinaryTreeNode(head->data); q.push(rightChild); head = head->next; } // 2.b) assign the left and right children of parent parent->left = leftChild; parent->right = rightChild; } } // Utility function to traverse the binary tree after conversion void inorderTraversal(BinaryTreeNode* root) { if (root) { inorderTraversal( root->left ); cout << root->data << \" \"; inorderTraversal( root->right ); } } // Driver program to test above functions int main() { // create a linked list shown in above diagram struct ListNode* head = NULL; push(&head, 36); /* Last node of Linked List */ push(&head, 30); push(&head, 25); push(&head, 15); push(&head, 12); push(&head, 10); /* First node of Linked List */ BinaryTreeNode *root; convertList2Binary(head, root); cout << \"Inorder Traversal of the constructed Binary Tree is: \ \"; inorderTraversal(root); return 0; } c) #include #include using namespace std; template class bintree { bintree *left; T data; bintree *right; public : bintree() { left=right=NULL; } void create(); void preorder(); void inorder(); void pos.

Link List Programming Linked List in CppAnil Yadav

THE CODE HAS A SEGMENTATION FAULT BUT I CANNOT FIND OUT WHERE. NEED .pdffathimahardwareelect

THE CODE HAS A SEGMENTATION FAULT BUT I CANNOT FIND OUT WHERE. NEED HELP FIXING THIS CODE? THIS IS THE PROBLEM Write a program that allows the user to enter two positive integers and outputs their sum. Sounds simple? Here\'s the catch: The numbers may be any size! They may be way too large to store in a single variable. You may not assume any particular maximum number of digits. HERE IS THE CODE #include #include struct node /* Linked list node*/ { int data; struct node* next; }; struct node *newNode(int data) /* Function to create a new node with giving the data*/ { struct node *new_node = (struct node *) malloc(sizeof(struct node)); new_node->data = data; new_node->next = NULL; return new_node; } void push(struct node** head_ref, int new_data) /* Function to insert a node at the beginning of the Doubly Linked List*/ { struct node* new_node = newNode(new_data); /*allocate a node*/ new_node->next = (*head_ref); /* link the old list off to the new node*/ (*head_ref) = new_node; /*move the head to point to the new node*/ } /* Adding the contents of two linked lists and return the head node of resultant list*/ struct node* addTwoLists (struct node* first, struct node* second) { struct node* res = NULL; /* res is head node of the resultant list*/ struct node *temp, *prev = NULL; int carry = 0, sum; while (first != NULL || second != NULL) /*while both the lists exists*/ { /* Calculate value of next digit in resultant list. // The next digit is sum of following things // (i) Carry // (ii) Next digit of first list (if there is a next digit) // (ii) Next digit of second list (if there is a next digit)*/ sum = carry + (first? first->data: 0) + (second? second->data: 0); carry = (sum >= 10)? 1 : 0; /* update carry for next calulation*/ sum = sum % 10; /*update sum if it is greater than 10*/ temp = newNode(sum); /*Create a new node with sum as data*/ if(res == NULL) /*if this is the first node then set it as head of the resultant list*/ res = temp; else /* If this is not the first node then connect it to the rest.*/ prev->next = temp; prev = temp; /* Set prev for next insertion*/ if (first) first = first->next; /* Move first pointers to next node*/ if (second) second = second->next; /*Move second pointer to the next node*/ } if (carry > 0) temp->next = newNode(carry); return res; /* return head of the resultant list*/ } void printList(struct node *node) /* function to print a linked list*/ { while(node != NULL) { printf(\"%d \", node->data); node = node->next; } printf(\"\ \"); } int main(void) /* program to test above function*/ { struct node* res = NULL; struct node* first = NULL; struct node* second = NULL; printf(\"Enter first positive integer: \"); scanf(\"%d\",&first); printList(first); printf(\"Enter second positive integer: \"); scanf(\"%d\",&second); printList(second); /*Add the two lists and see result*/ res = addTwoLists(first, second); printf(\"Sum is: %d\"); printList(res); return 0; } Solution #include #include typedef struct Node { int da.

How to build a Linked List that can insert any type of data. For exa.pdfarpittradersjdr

How to build a Linked List that can insert any type of data. For example: SLinkedList abc1; SLinkedList abc2; SLinkedlist abc3; Please answer in C plus plus, you don\'t need to develop all function, just insert data is enough. Thank you. Solution #include #include #define LEFT 2 #define RIGHT 3 typedef struct linked_list { double data; struct linked_list *next; }node;//node declaration for single linked list /*function prototype declaration*/ void insertion(node **,double); void erase(node **,node **); //void left_or_right(node **,node **,int); node *makenode(double); void show(node **,node **); /*main*/ int main() { system(\"clear\"); char choice; double item; node *start=NULL,*prev=NULL; do { printf(\"\ ===========================\ \\tMENU\ ===========================\ \\t1.Insert\ \\t2.Exit\ Enter your choice :: \"); scanf(\"\ %c\",&choice); switch(choice) { case \'1\': printf(\"\ Enter item :: \"); scanf(\"%lf\",&item); insertion(&start,item);//insert function calling show(&start,&prev); break; case \'2\': erase(&prev,&start); printf(\"\ You are exited from the whole program.\ \ \"); exit(1); default: printf(\"\ \\tWrong Choice\ \"); } } while(choice!=\'2\'); return 0; } void show(node **start,node **prev)/*this function displays the whole linked list*/ { if((*start)!=NULL) { printf(\"\ \ X <- \"); node *temp=NULL,*p=*prev,*q=NULL; while(p!=NULL) { if(temp==NULL) { temp=makenode(p->data); } else { q=makenode(p->data); q->next=temp; temp=q; } p=p->next; } while(temp!=NULL) { printf(\"%.0lf <- \",temp->data); q=temp; temp=temp->next; free(q); q=NULL; } printf(\"\\b| \"); p=*start; while(p!=NULL) { if(p==*start) { printf(\"%.0lf |-> \",p->data); } else { printf(\"%.0lf -> \",p->data); } p=p->next; } printf(\" X \ \ \"); } else { printf(\"\ \ \\tEmpty Linked List\ \ \"); } } void insertion(node **start,double item)//this function inserts a new node in the linked list { node *temp=makenode(item),*p=NULL; if(*start==NULL) { *start=temp; } else { p=*start; while(p->next!=NULL) { p=p->next; } p->next=temp; } } node *makenode(double item) { node *temp=NULL; temp=(node *)malloc(sizeof(node)); if(temp==NULL) { printf(\"\ Dynamic memory allocation failed.\ \"); exit(0); } temp->data=item; temp->next=NULL; } void erase(node **prev,node **start)//this function deletes all nodes of the linked list when the program terminates { node *p=NULL; while(*start!=NULL) { p=*start; *start=(*start)->next; free(p); p=NULL; } while(*prev!=NULL) { p=*prev; *prev=(*prev)->next; free(p); p=NULL; } }.

DSA(1).pptxDaniyalAli81

The document summarizes key concepts about linked lists including different types like singly linked lists, doubly linked lists, and circular linked lists. It provides code examples for creating nodes and performing operations like insertion, deletion, and traversal for each type of linked list. Specifically, it shows code for inserting nodes at the head, tail, and middle of singly, doubly, and circular linked lists. It also includes code for deleting nodes from singly, doubly, and circular linked lists.

Doublylinklistritu1806

This document presents information on doubly linked lists including their representation, initialization, node creation, and various operations like insertion, deletion, and traversal. It discusses inserting and deleting nodes at the beginning or end of the list, as well as inserting before or after a specified node. Code examples are provided for initializing a doubly linked list and performing each operation.

DAA Lab Work.docxDeepusri2000Srivasta

write recursive function that calculates and returns the length of a.pdfarpitcomputronics

write recursive function that calculates and returns the length of a linked list Solution // C code to determine length of linked list recursively #include #include // node of linked list struct node { int key; struct node* next; }; // push key to linked list void push(struct node** root, int new_element) { struct node* nodeNew = (struct node*) malloc(sizeof(struct node)); nodeNew->key = new_element; nodeNew->next = (*root); (*root) = nodeNew; } // recursively get length of linked list int lengthLinkedlist(struct node* root) { // base case if (root == NULL) return 0; // recursively call the function return 1 + lengthLinkedlist(root->next); } int main() { struct node* root = NULL; push(&root, 11); push(&root, 34); push(&root, 4); push(&root, 23); push(&root, 14); push(&root, 88); push(&root, 56); push(&root, 84); push(&root, 6); /* Check the count function */ printf(\"Length of Linked list: %d\ \", lengthLinkedlist(root)); return 0; } /* output: Length of Linked list: 9 */.

#includeiostream#includecstdio#includecstdlibusing names.pdfKUNALHARCHANDANI1

Introduction---to-Expression---Trees.pdfkhetyidris

Using the provided table interface table.h and the sample linked lis.pdfconnellalykshamesb60

Using the provided table interface table.h and the sample linked list code linkedList.c, complete an implementation of the Table ADT. Make sure that you apply the concepts of design by contract (DbC) to your implementation. Once you have fully implemented the table, create a main.c file that implements a testing framework for your table. Your table implementation must ensure that values inserted are unique, and internally sorted within a linked list. table.h linkedList.c Solution khsdg #include #include typedef enum BOOL { false, true } bool; // Linked list node definition typedef struct Node node; struct Node { int number; node *next; }; static node *top = NULL; // used to track where we are for the list traversal methods static node *traverseNode = NULL; // \"destroy\" will deallocate all nodes in a linked list object // and will set \"top\" to NULL. void destroy() { node *curr = top; node *temp = NULL; while ( curr != NULL ) { // flip order to see it blow up... temp = curr; curr = curr->next; free( temp ); } top = NULL; } // \"build\" will create an ordered linked list consisting // of the first \"size\" even integers. void build( int size ) { node *newNode = NULL; int i = 0; // make sure we don\'t have a list yet destroy(); for ( i=size ; i>0 ; i-- ) { newNode = malloc( sizeof( node ) ); newNode->number = i*2; newNode->next = top; top = newNode; } } // starts a list traversal by getting the data at top. // returns false if top == NULL. bool firstNode( int *item ) { bool result = false; if ( top ) { *item = top->number; traverseNode = top->next; result = true; } return result; } // gets the data at the current traversal node and increments the traversal. // returns false if we\'re at the end of the list. bool nextNode( int *item ) { bool result = false; if ( traverseNode ) { *item = traverseNode->number; traverseNode = traverseNode->next; result = true; } return result; } // \"print\" will output an object\'s entire linked list // to the standard output device -- one \"number\" per line. void print() { int value; if ( firstNode( &value ) ) { do { printf( \"%d\ \", value ); } while ( nextNode( &value ) ); } } int main( int argc, char *argv[] ) { build( 10 ); print(); destroy(); build( 5 ); build( 20 ); print(); destroy(); return 0; }.

This assignment and the next (#5) involve design and development of a.pdfEricvtJFraserr

This assignment and the next (#5) involve design and development of a sequential non contiguous and dynamic datastructure called LinkedList. A linked list object is a container consisting of connected ListNode objects. As before, we are not going to use pre-fabricated classes from the c++ library, but construct the LinkedList ADT from scratch. The first step is construction and testing of the ListNode class. A ListNode object contains a data field and a pointer to the next ListNode object (note the recursive definition). #This assignment requires you to 1. Read the Assignment 4 Notes 2. Watch the Assignment 4 Support video 3. Implement the following methods of the ListNode class -custom constructor -setters for next pointer and data 4. Implement the insert and remove method in the main program 5. Scan the given template to find the above //TODO and implement the code needed //TODO in ListNodecpp.h file public: ListNode(T idata, ListNode<T> * newNext); public: void setNext(ListNode<T> * newNext); public: void setData(T newData); // TODO in main program void remove(ListNode<int> * &front,int value) void insert(ListNode<int> * &front,int value) # The driver is given ListNodeMain.cpp is given to you that does the following tests 1. Declares a pointer called front to point to a ListNode of datatype integer 2. Constructs four ListNodes with data 1,2,4 and adds them to form a linked list. 3. Inserts ListNode with data 3 to the list 4. Removes node 1 and adds it back to test removing and adding the first element 5. Removes node 3 to test removing a middle node 6. Removes node 4 to test removing the last node 7. Attempt to remove a non existent node 8. Remove all existing nodes to empty the list 9. Insert node 4 and then node 1 to test if insertions preserve order 10.Print the list Main.cpp #include <iostream> #include "ListNodecpp.h" // REMEMBER each ListNode has two parts : a data field // and an address field. The address is either null or points to the next node //in the chain //Requires: integer value for searching, address of front //Effects: traverses the list node chain starting from front until the end comparing search value with listnode getData. Returns the original search value if found, if not adds +1 to indicate not found //Modifies: Nothing int search(ListNode<int> * front, int value); //Requires: integer value for inserting, address of front //Effects: creates a new ListNode with value and inserts in proper position (increasing order)in the chain. If chain is empty, adds to the beginning //Modifies: front, if node is added at the beginning. //Also changes the next pointer of the previous node to point to the //newly inserted list node. the next pointer of the newly inserted pointer //points to what was the next of the previous node. //This way both previous and current links are adjusted //******** NOTE the use of & in passing pointer to front as parameter - // Why do you think this is needed ?********** void insert(ListNode<int> * &fr.

Lab Week 2 Game Programming.docxteyaj1

This program implements a doubly linked list to print the list forward and backward. It defines a Node struct with data, next and prev pointers. It inserts nodes at the head of the list using InsertAtHead() and prints the list forward using Print() and backward using ReversePrint(). It initially inserts two nodes and prints the list both ways. It then inserts three more nodes at the head and prints the list again forward and backward.

I have C++ question that I do not know how to do, Can you teach me t.pdffasttrackscardecors

I have C++ question that I do not know how to do, Can you teach me this question: Draw a CLASS diagram for Binary Search Tree (BTS) : can you explain me each step, thank you Solution //program to convert Binary Tree to Binary Search Tree #include #include // A binary tree node structure struct node { int data; struct node *left; struct node *right; }; void storeInorder (struct node* node, int inorder[], int *index_ptr) { // Base Case if (node == NULL) return; // first store the left subtree storeInorder (node->left, inorder, index_ptr); // Copy the root\'s data inorder[*index_ptr] = node->data; (*index_ptr)++; // increase index for next entry // finally store the right subtree storeInorder (node->right, inorder, index_ptr); } /* A helper function to count nodes in a Binary Tree */ int countNodes (struct node* root) { if (root == NULL) return 0; return countNodes (root->left) + countNodes (root->right) + 1; } // Following function is needed for library function qsort() int compare (const void * a, const void * b) { return ( *(int*)a - *(int*)b ); } /* A helper function that copies contents of arr[] to Binary Tree. This functon basically does Inorder traversal of Binary Tree and one by one copy arr[] elements to Binary Tree nodes */ void arrayToBST (int *arr, struct node* root, int *index_ptr) { // Base Case if (root == NULL) return; /* first update the left subtree */ arrayToBST (arr, root->left, index_ptr); /* Now update root\'s data and increment index */ root->data = arr[*index_ptr]; (*index_ptr)++; /* finally update the right subtree */ arrayToBST (arr, root->right, index_ptr); } // This function converts a given Binary Tree to BST void binaryTreeToBST (struct node *root) { // base case: tree is empty if(root == NULL) return; /* Count the number of nodes in Binary Tree so that we know the size of temporary array to be created */ int n = countNodes (root); // Create a temp array arr[] and store inorder traversal of tree in arr[] int *arr = new int[n]; int i = 0; storeInorder (root, arr, &i); // Sort the array using library function for quick sort qsort (arr, n, sizeof(arr[0]), compare); // Copy array elements back to Binary Tree i = 0; arrayToBST (arr, root, &i); // delete dynamically allocated memory to avoid meory leak delete [] arr; } /* Utility function to create a new Binary Tree node */ struct node* newNode (int data) { struct node *temp = new struct node; temp->data = data; temp->left = NULL; temp->right = NULL; return temp; } /* Utility function to print inorder traversal of Binary Tree */ void printInorder (struct node* node) { if (node == NULL) return; /* first recur on left child */ printInorder (node->left); /* then print the data of node */ printf(\"%d \", node->data); /* now recur on right child */ printInorder (node->right); } /* Driver function to test above functions */ int main() { struct node *root = NULL; /* Constructing tree given in the above figure 10 / \\ 30 15 / \\ 20 5 */ root = newNode(10); root->left = newNode(30.

Write a C++ function that delete nodes in a doubly linkedlist- It shou.docxnoreendchesterton753

Write a C++ function that delete nodes in a doubly linkedlist. It should delete all nodes that have that specific value. Finally, return the head of the linkedlist. node * DN(node *head, int value) { } The linkedlist structure: struct n { int value; node *next; node *previous; }; Solution #include<stdio.h> #include<stdlib.h> #include<assert.h> /* Link list node */ struct node { int data; struct node* next; }; /* Function to delete the entire linked list */ void deleteList(struct node** head_ref) { /* deref head_ref to get the real head */ struct node* current = *head_ref; struct node* next; while (current != NULL) { next = current->next; free(current); current = next; } /* deref head_ref to affect the real head back in the caller. */ *head_ref = NULL; } /* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */ void push(struct node** head_ref, int new_data) { /* allocate node */ struct node* new_node = (struct node*) malloc(sizeof(struct node)); /* put in the data */ new_node->data = new_data; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref)Â Â Â = new_node; } /* Drier program to test count function*/ int main() { /* Start with the empty list */ struct node* head = NULL; /* Use push() to construct below list 1->12->1->4->1 */ push(&head, 1); push(&head, 4); push(&head, 1); push(&head, 12); push(&head, 1); printf(\"\ Deleting linked list\"); deleteList(&head); printf(\"\ Linked list deleted\"); } .

Use C++ Write a function to merge two doubly linked lists. The input.pdfshalins6

Use C++ Write a function to merge two doubly linked lists. The input lists have their elements in sorted order, from lowest to highest. The output list should also be sorted from lowest to highest. Your algorithm should run in linear time on the length of the output list. Provide an algorithm for your function Implement and show some samples of your running function Solution /* This is a C++ program to merge two sorted linked lists and produce a list in a Sorted order */ #include #include #include /* Link list node */ struct node { int data; struct node* next; }; /* This function is used to pull off the front node of the source and put it in destnation */ void letusMoveNode(struct node** destRef, struct node** sourceRef); /* This is a function used for performing merging of two linked lists.It takes two lists sorted in increasing order, and splices their nodes together to make one big sorted list which is returned. */ struct node* letssortlists(struct node* a, struct node* b) { /* Let us first have dummyone first node to hang the result on */ struct node dummyone; /*next the tail points to the last result node */ struct node* tail = &dummyone; /* As a result, tail->next is the place to add new nodes to the result. */ dummyone.next = NULL; while (1) { if (a == NULL) { /*we will check that if either list runs out, use the other list */ tail->next = b; break; } else if (b == NULL) { tail->next = a; break; } if (a->data <= b->data) letusMoveNode(&(tail->next), &a); else letusMoveNode(&(tail->next), &b); tail = tail->next; } return(dummyone.next); } /* letusMoveNode() function is a function which takes the node from the front of the source, and move it to the front of the dest. Before calling letusMoveNode(): source == {1, 2, 3} dest == {1, 2, 3} Affter calling letusMoveNode(): source == {3, 4} dest == {1, 2, 3, 4} */ void letusMoveNode(struct node** destReference, struct node** sourceReference) { /*This is the front source node */ struct node* newNode = *sourceReference; assert(newNode != NULL); /* now we will advance the source pointer */ *sourceReference = newNode->next; /*next we will link the old dest off the new node */ newNode->next = *destReference; /* Fineally we will move dest to point to the new node */ *destReference = newNode; } /* This IS A function which is used to insert a node at the beginning of the linked list */ void insertpush(struct node** head_reference, int new_data) { /* This is used to allocate node */ struct node* new_node = (struct node*) malloc(sizeof(struct node)); /* now we will put in the data */ new_node->data = new_data; /* The next step is to link the old list off the new node */ new_node->next = (*head_reference); /*Finally we will move the head to point to the new node */ (*head_reference) = new_node; } /* This is a function to print nodes in a given linked list */ void printList(struct node *node) { while (node!=NULL) { printf(\"%d \", node->data); node = node->next; } } /*This is the driver program to test ab.

take the following code and give details of what each line of code i.pdffastechsrv

take the following code and give details of what each line of code is doing #include #include #include using namespace std; /* * Node Declaration */ struct node { int info; struct node *next; }*start; /* * Class Declaration */ class single_llist { public: node* create_node(int); void insert_begin(); void insert_pos(); void insert_last(); void delete_pos(); void sort(); void search(); void update(); void reverse(); void display(); single_llist() { start = NULL; } }; /* * Main :contains menu */ main() { int choice, nodes, element, position, i; single_llist sl; start = NULL; while (1) { cout<>choice; switch(choice) { case 1: cout<<\"Inserting Node at Beginning: \"<info = value; temp->next = NULL; return temp; } } /* * Inserting element in beginning */ void single_llist::insert_begin() { int value; cout<<\"Enter the value to be inserted: \"; cin>>value; struct node *temp, *p; temp = create_node(value); if (start == NULL) { start = temp; start->next = NULL; } else { p = start; start = temp; start->next = p; } cout<<\"Element Inserted at beginning\"<>value; struct node *temp, *s; temp = create_node(value); s = start; while (s->next != NULL) { s = s->next; } temp->next = NULL; s->next = temp; cout<<\"Element Inserted at last\"<info<<\"->\"; temp = temp->next; } cout<<\"NULL\"< Solution ANSWER :: ASSMUING THE TOTAL LINE IN CODE ARE 158*(INCLUDING COMMENTS) SO... PROGRAM STARTS WITH SPECIFING HEADER FILES AND GLOBAL VARIABLE DECLARATION THEN Node Declaration USING STRUCTURES, THEN WE WANT TO DECLARE THE CLASS USING SINGLE LINKED LIST AND THE PROTOTYPE IS PUBLIC IN THE PUBLIC WE WANT TO CREATE THE NODE AS INTEGER DATATYPE THE NODE CONSIST OF insert_begin(); insert_pos();-> INDICATES THE CURRENT POSSITION insert_last();->INSERT AT LAST delete_pos();->TO DELETE THE NUMBER AT CURRENT POSITION sort();->START THE SORTING search();->USED TO SEARCH update();->UPDATE THE NODE reverse();->REVERSE NUMBERS display();->TO DISPLAY THE NODE single_llist()->FIFO WE ARE STARTING TAKING NULL VALUE AND THEN TAKE USER DEFIND FUNCTION MAIN() CREATE THE DATATYPES choice, nodes, element, position, i OBJECT CREATION OF SLL IS SL USING WHILE LOOP THE NODE INSERT AT THE BEGINING OR ENDING STAGE WE ARE USING SWITCH CASES TO PERFORM SLL ON NODE NODE CREATION AS node *single_llist::create_node(int value) ALSO DECLARE THE TEMP IS TAKEN AS NULL VALUE INSERT THE ELEMENT AT THE BEGINING USING IF CONDITION WE CAN INSERT THE NODE AT THE BEGINING struct node *temp, *p; temp = create_node(value); if (start == NULL) { start = temp; start->next = NULL; } else { p = start; start = temp; start->next = p; AND THEN INSERT THE NODE AT THE LAST struct node *temp, *s; temp = create_node(value); s = start; while (s->next != NULL) { s = s->next; } temp->next = NULL; s->next = temp; USING WHILE LOOP WE ARE INSERTING THE NODE AT LAST USING THIS BELLOW CODE WE CAN SEARCH THE ELEMENTS IN THE NODE struct node *temp; if (start == NULL) { cout<<\"The List is Empty\"<info<<\"->\"; temp = temp->next; } cout.

C++ Please write the whole code that is needed for this assignment- wr.docxBrianGHiNewmanv

Once you have all the structures working as intended- it is time to co.docxfarrahkur54

Once you have all the structures working as intended, it is time to compare the performances of the 2. Use runBenchmark() to start. a. First, generate an increasing number (N) of random integers (1000, 5000, 10000, 50000, 75000, 100000, 500000 or as far as your computing power will let you) i. Time and print how long it takes to insert the random integers into an initially empty BST. Do not print the tree. You can get a random list using the java class Random, located in java.util.Random. To test the speed of the insertion algorithm, you should use the System.currentTimeMillis() method, which returns a long that contains the current time (in milliseconds). Call System.currentTimeMillis() before and after the algorithm runs and subtract the two times. (Instant.now() is an alternative way of recording the time.) ii. Time and print how long it takes to insert the same random integers into an initially empty AVL tree. Do not print the tree. iii. If T(N) is the time function, how does the growth of TBST(N) compare with the growth of TAVL(N)? Plot a simple graph to of time against N for the two types of BSTs to visualize your results. b. Second, generate a list of k random integers. k is also some large value. i. Time how long it takes to search your various N-node BSTs for all k random integers. It does not matter whether the search succeeds. ii. Time how long it takes to search your N-node AVL trees for the same k random integers. iii. Compare the growth rates of these two search time-functions with a graph the same way you did in part a. public class BinarySearchTree<AnyType extends Comparable<? super AnyType>> { protected BinaryNode<AnyType> root; public BinarySearchTree() { root = null; } /** * Insert into the tree; duplicates are ignored. * * @param x the item to insert. * @param root * @return */ protected BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> root) { // If the root is null, we've reached an empty leaf node, so we create a new node // with the value x and return it if (root == null) { return new BinaryNode<>(x, null, null); } // Compare the value of x to the value stored in the root node int compareResult = x.compareTo(root.element); // If x is less than the value stored in the root node, we insert it into the left subtree if (compareResult < 0) { root.left = insert(x, root.left); } // If x is greater than the value stored in the root node, we insert it into the right subtree else if (compareResult > 0) { root.right = insert(x, root.right); } // If x is equal to the value stored in the root node, we ignore it since the tree does not allow duplicates return root; } /** * Counts the number of leaf nodes in this tree. * * @param t The root of the tree. * @return */ private int countLeafNodes(BinaryNode<AnyType> root) { // If the root is null, it means the tree is empty, so we return 0 if (root == null) { return 0; } // If the root has no children, it means it is a leaf node, so we return 1 if (root.left == .

Write a program to implement below operations with both singly and d.pdfthangarajarivukadal

Write a program to implement below operations with both singly and doubly linked list. Use inheritance to define singly linked list and doubly linked list. Add Node() Delete Node() Update Node() Delete All() Size() Solution #include using namespace std; class List; class Node { friend class List; protected: int Data; Node *Link; }; class List:public Node { friend class Node; private: Node *Start; public: List() { Start=NULL; } Node Insert(int x); Node Delete(int &x); void Display(); }; Node List::Insert(int x) { Node *New=new Node; New->Data=x; New->Link=Start; Start=New; return *this; } Node List::Delete(int &x)//deletes first node { Node *Del=Start; Start=Start->Link; delete Del; return *this; } void List::Display() { Node *P=Start; while(P!=NULL) { cout<Data<<\" \"; P=P->Link; } } int main() { List L; L.Insert(4); L.Insert(64); L.Insert(3); L.Insert(90); L.Insert(66); L.Insert(13); L.Display(); } Double Linked List.

In what ways are humans also primatesSolutionBoth humans and .pdfinfo824691

In what ways are humans also primates? Solution Both humans and primates (Pottos, lemurs) do possess vertebral column and possess finger digits for the catching prey. The primates are often locomotion on its front knuckles, which is same as primate character of locomotion in apes, gorillas and chimpanzees & humans. The behavioral aspects and hunting prey finally chewing & eating the prey are main similar aspects of primates and humans commonly Primates have enable to keep its claws followed by middle digits similar to humans that support its entire weight along with metacarpophalangeal joints and interphalangeal joints finally produces \"hook-and-pull\" digger with enlarged supraspinous fossa. This type of movement is going to enable to increase pulling power of forelimbs. The adaptations historically developed by primates are nearly similar to humans for \"homeostatic capabilities\", such as “various excretory routes & connective tissues such as blood” to eliminate nitrogenous waste etc. They have neurological innervations to these organs to mediate homeostasis similar to humans. For example, skin and sweating is often referred as an evolutionary adaptation in primates because sweat glands in humans (vertebrate animals) eliminate nitrogenous wastes such as urea, uric acid because they live in terrestrial and land environment. The development of nephrons and lungs to eliminate excess bicarbonate to keep the body with homeostasis is another major homeostatic capability. The body is going to generate heat from the liver and body hair on the humans & primates do maintain constant body temperature (negative feedback for thermoregulation) to mediate homeostasis finally to promote metabolism. Other anti-stress hormones released in gorillas body often maintain homeostasis.

i need Understand the role of capillaries in fluidnutrient exchange.pdfinfo824691

i need Understand the role of capillaries in fluid/nutrient exchange. How is blood directed to or away from particular capillary beds? Solution Capillaries are the tiniest blood vessels that are present in the body of an organism and facilitate the transition between arteries and veins. The Arteries bring the blood from the heart to the various organs of the body and the size of these vessels decreases to form arterioles and the further decreases till the time it becomes a capillary. These capillaries are small in size but more in number and thus form a network over any specific organ. these capillaries then as the blood flows further turn into broader blood vessels and eventually the veins which carry the blood back to the heart. These capillaries can be called as microscopic blood vessels as many a times they may have walls that are made of only a single celled endothelial layer. Their microscopic structure makes material exchange possible as capillaries are the only blood vessels that can carry out the fluid and nutrient exchange. Due to the presence of a large network the surface area for exchange by these capillaries is huge. The capillaries at any time hold only about 5% of the total blood volume and the human body has approximately 40 billion capillaries. the size of the capillaries is only 5–10 nm in diameter. At any given time only a around 25 percent of capillaries are fully filled with blood, especially in tissues at rest, as blood flow in microvessels is dependent on the metabolic activity of the tissue and is regulated at the sites of their origin by sphincter muscles. There are three types of capillaries based on their structures – Continuous capillaries, fenestrated capillaries and sinusoids. Continuous capillaries are found in the skin and muscles which have an uninterrupted lining of endothelial cells held together by tight junctions. Fenestrated capillaries are found wherever active capillary absorption or filtrate formation occurs like small intestine etc., having pores in the endothelium to facilitate diffusion. The Sinusoids have a slow blood flow and are modified by leaky pored capillaries with lumens for exchange of large molecules. The structurally different capillaries are present to facilitate the transport according to the functional requirement of the body. The main function of capillaries is exchange of material – Gases, nutrients and fluids. The exchange of gases is primarily of oxygen and carbon di oxide. This exchange occurs by basic diffusion through the semipermeable layers. The gases move from higher to lower concentration. In the lungs the oxygen enters the blood though the blood capillaries and the carbon di oxide is taken up at regions where oxygen is given out of the blood, in organs that have accumulated the increased carbon di oxide levels after respiration process is done. Gases can easily pass through the semi permeable layers of the capillary walls. The lipid soluble substances can also easily pass .

More Related Content

Similar to Write a function in C++ to generate an N-node random binary search t.pdf (20)