#include #include #include \"list.h\" /* these are the two procedures you are go

Question

#include
#include
#include "list.h"



/* these are the two procedures you are going to write */
s_ptr insert_ordered(int v, s_ptr head) { }

int in_ordered_list(int v, s_ptr head) { }


s_ptr insert_at_head(int v, s_ptr head) {
s_ptr new_node = NULL;
new_node = (s_ptr)malloc(sizeof(s_rec));
new_node->x = v;
new_node->next = head;
head = new_node;
return head;
}

void
print_list(s_ptr head) {
while (head != NULL) {
printf("%d ",head->x);
head = head->next;
}
}

s_ptr delete(int val, s_ptr list) {
s_ptr temp;
if (list == NULL) return NULL;
if (list->x == val) {
temp = list; list=list->next;
free(temp); return delete(val,list);
}
list->next = delete(val, list->next);
return list;
}

s_ptr iterative_delete(int val, s_ptr head) {
s_ptr p1, p2;
p1 = NULL;
p2 = head;
while (p2 != NULL) {
if (p2->x == val) {
if (p1 == NULL) {
head = p2->next; free(p2);
return head;
} else {
p1->next = p2->next; free(p2);
return head;
}
}
p1 = p2; p2 = p2->next;
}
}

s_ptr iterative_delete_all(int val, s_ptr head) {
s_ptr p1, p2;
p1 = NULL;
p2 = head;
while (p2 != NULL) {
if (p2->x == val) {
if (p1 == NULL) {
head = p2->next; free(p2);
p2 = head;
} else {
p1->next = p2->next; free(p2);
p2 = p1->next;
}
} else {
p1 = p2; p2 = p2->next;
}
}
return head;
}



int
in_list(int val,s_ptr head) {
if (head == NULL) {
return 0;
}
if (head->x == val) return 1+in_list(val,head->next);
return in_list(val,head->next);
}






Assignment Specifications
You are going to implement the following two functions:

* s_ptr insert_ordered(int v, s_ptr head) - In the code in class, we always inserted at the front of the list. Now, you are going to always insert new items such that they are in sorted order. This is essentially an insertions sort that you are implementing, one item at a time.
* int in_ordered_list(int v, s_ptr head) - search a sorted list. To do this correctly, you need to return from the function as soon as you encounter an item with a value greater than the item you are searching for.



It is very urgent and I need a very well commented program please........ Please help me with a well commented program. So I can understand better.
Thanks

Explanation / Answer

Hi, I just copied over the two functions that needed to be filled out. I compiled it under Visual Studio 2010 Professional. Please let me know if you have any questions. // Inserts a value in an ordered list. // Parameter v is the value that will be inserted into the list. // Parameter head is the pointer that is pointing to the first node in the list. // Returns the head of the list. s_ptr insert_ordered(int v, s_ptr head) { // Creates a new node that will be inserted into the list. s_ptr new_node = NULL; // Allocates enough space in memory for the new node. new_node = (s_ptr)malloc(sizeof(s_rec)); // Sets the value of the new node to v. new_node->x = v; // Creates an iterator to cycle through the list. s_ptr iterator = head; // Creates a space holder to point to the previous node in the list. s_ptr previous = NULL; // Cycles through the list until the end of the list has been reached. while(iterator != NULL) { // Checks to make sure that the current value of the iterator // is not greater than value that will be inserted. // If it is, then it will insert the new node in the spot right before it. if (iterator->x > v) { // Sets the previous node to point to the new node. previous->next = new_node; // Sets the new node to point to the next node in the list. new_node->next = iterator; // Function complete, so return the head value back to the user. // Breaking from the while loop will cause the new node // to be inserted at the end of the list as well. return head; } // Sets the previous pointer before moving the iterator // to the next value in the list. previous = iterator; // Sets the iterator to the next value in the list. iterator = iterator->next; } // This part of the code is reached only if the value is going to // be inserted at the end of the list or the list empty. // Sets the next value to null since it is the last value in the list. new_node->next = NULL; // Check to see if the list is empty. // If previous was set to a node, then the list was not empty, // but if previous remained NULL, then the list is empty because // the function never entered the while loop above. if (previous == NULL) { // Sets the first node to the new node. head = new_node; } else { // The list is not empty, so the node will be added at the end of the list. previous->next = new_node; } // Sets head to the new node. head = new_node; // Returns head back to the user. return head; } // This is a recursive function that goes through the list one by one. // Returns a 1 if found and a 0 if not found. int in_ordered_list(int v, s_ptr head) { // This checks to make sure that you haven't hit the end // of the list since the list is null terminated. // Ex: 1, 2, 3, 4, 5, NULL if(head == NULL) return 0; // This returns a 1 whenever the actual value // is found within the list. if(head->x == v) return 1; // Since the list is already in order, // it is assumed that as soon as the value in the list // is greater than the value that you are looking for, // it is not in the list. // Note: The assumption is that the list is in order // from least to greatest. If it is from greatest // to least, change it to: if (head->x x > v) return 0; // If none of the above conditions are satisfied, // then the function will move on to the next value in the list. return in_ordered_list(v, head->next); }

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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