Build a sorted double-linked list such that you can go around the list either wa

Question

Build a sorted double-linked list such that you can go around the list either way to print the ordered list forward or in reverse. For example, you build a list of characters, then you can print it out as:
"a b c d e" or "e d c b a". The input is of an random character list is from the keyboard.

Explanation / Answer

struct node { int number; struct node *next; };void insert_node(int value) { struct node *new_node = NULL; struct node *cur_node = NULL; struct node *last_node = NULL; int found; /* 1 means found a place to insert the new node in, 0 means not*/ new_node = (struct node *)malloc(sizeof(struct node *)); if(new_node == NULL) { printf("memory problem "); } new_node->number = value; /* If the first element */ if (head == NULL) { new_node->next = NULL; head = new_node; } else if (new_node->number number) { new_node->next = head; head = new_node; } else { cur_node = head; found = 0; while (( cur_node != NULL ) && ( found == 0 )) { if( new_node->number number ) { found = 1; } else { last_node = cur_node; cur_node = cur_node->next; } } /* We got the right place to insert our node */ if( found == 1 ) { new_node->next = cur_node; } /* Insert at the tail of the list */ else { last_node->next = new_node; new_node->next = NULL; } }//merge sortstruct node *addnode(int number, struct node *next) { struct node *tnode; tnode = (struct node*)malloc(sizeof(*tnode)); if(tnode != NULL) { tnode->number = number; tnode->next = next; } return tnode; } /* perform merge sort on the linked list */ struct node *merge_sort(struct node *head) { struct node *head_one; struct node *head_two; if((head == NULL) || (head->next == NULL)) return head; head_one = head; head_two = head->next; while((head_two != NULL) && (head_two->next != NULL)) { head = head->next; head_two = head->next->next; } head_two = head->next; head->next = NULL; return merge(merge_sort(head_one), merge_sort(head_two)); } /* merge the lists.. */ struct node *merge(struct node *head_one, struct node *head_two) { struct node *head_three; if(head_one == NULL) return head_two; if(head_two == NULL) return head_one; if(head_one->number number) { head_three = head_one; head_three->next = merge(head_one->next, head_two); } else { head_three = head_two; head_three->next = merge(head_one, head_two->next); } return head_three; }void main(){node temp;temp=start;int i;couti;switch(i){case 1:insertion sort(i);while(temp->next!=null){coutnull;}whlie(temp->pre!=0){cout

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

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