double
):
Node* search(dobule value, Node* L);As we discussed with "search" in the case of arrays, it's best to have a function
bool match(double a, double b);
— where the types of the arguments a and b match the type
of the data in the Node — that takes care of determining
whether the data in an individual Node matches the value being
searched for.
As an exercise, try downloading Ex0.cpp and see if you can provide a definition for the "search" function. If you've done it properly, the program should run like this:
~/$ ./prog 34.2 , 54.98 , 92.0, 83.9; search 54.98 Found! search 54.88 Not Found! search 12 Not Found! quitI'll provide you with two solutions, an iterative solution and a recursive solution.
insert_in_order(val,L)
that will insert a new value val
into L
so that sorted order is maintained. Here's what we need to do in
pictures:
Start: We want to add val to the list
L .
 
Move p to point to the node after which
val should be added.
 
Create the new node we want, with the proper data and
next values.
Node *T = new Node; T>data = val; T>next = p>next;  
Splice our new node in after the node p points to.
p>next = T;  
Done! 
p
to point to the node after which we
want to insert our new node".
Attempt 1:  Node *p = L; while(p>next>data < val) p = p>next; add2front(val,p>next); 
Commentary: What makes p special
is that it's the first node in your list whose next
node has a bigger data value than val .
That's what we're looking for here. The only problem
is that this'll crash if val is bigger
than everything currently in the list. To deal with this,
we should also stop moving p if it's the
last node in the list  i.e. if p>next
is NULL .

Attempt 2:  Node *p = L; while(p>next != NULL && p>next>data < val) p = p>next; add2front(val,p>next); 
Commentary: This works like a champ, but it
contains the hidden assumption that val
will never need to come before the first node.

Attempt 3:  if (L>data < val) { Node *p = L; while(p>next != NULL && p>next>data < val) p = p>next; add2front(val,p>next); } else add2front(val,L); 
Commentary:
This is fine, except that it crashes if L
is the empty list, because the test L>data
implicitly assumes that L is really
pointing to something!

Success!  if (L != NULL && L>data < val) { Node *p = L; while(p>next != NULL && p>next>data < val) p = p>next; add2front(val,p>next); } else add2front(val,L); 
Commentary: This does exactly what we want, in all cases! 
insert_in_order
function:
void insertinorder(double val, Node* &L) { if (L != NULL && L>data < val) insertinorder(val,L>next); else add2front(val,L); } 
void insertinorder(double val, Node* &L) { if (L != NULL && L>data < val) { Node *p = L; while(p>next != NULL && p>next>data < val) p = p>next; add2front(val,p>next); } else add2front(val,L); } 
insertinorder
we can sort stuff pretty
easily with linked lists. For example, if you want to read in a
bunch of values and put them in sorted order, you can simply put
them in a list as you read them using insertinorder
,
and when you're done, you'll have a sorted list of values. Not
bad, eh? Of course, as we know from selection sort there are
many, many different "orders" you can put things into when you
sort. If you recall, we used the before(a,b)
function
to determine whether element a
must come before
element b
in sorted order. We really ought to write
insertinorder
so it relies on a "before" function as
well. This program uses linked lists and
insertinorder
with a "before" function to read in words
from the user and write them back sorted by incresing length, with
ties broken by alphabetical order. Here's an example of the
program in action:
Enter words, terminated with a semicolon : the quick brown fox jumped over the lazy dog ; dog fox the the lazy over brown quick jumped
insertinorder
for that node's data.
Node* sortedcopy(Node* L) { Node* S = NULL; for(Node* p = L; p != NULL; p = p>next) insertinorder(p>data,S); return S; }This function returns a copy of the original list in sorted order.
insertinorder
function from above so
that duplicate values are not inserted, but rather simply
ignored. Thus, if used on the example code in which words
are entered, only unique words would appear — no
duplicates.
~/$ ./prog hi , bye , yo , ciao , hi , hallo , yo , sianara ; sinara 1 hallo 1 ciao 1 yo 2 bye 1 hi 2