Let's consider a function addafter(val, P)
that will insert a
node containing value val
after p
so that sorted
order is maintained. Here's what we need to do
in pictures:
We want to add a node with data after p .
We are using the following struct definition:
|
|
Create the new node we want, with the proper data and
next values (drag your mouse to see the code below).
Node *T = new Node; T->data = val; T->next = p->next; |
|
Splice our new node in after the node p points to
(drag your mouse to see the code below).
p->next = T; |
|
Done! |
void addafter(double val, Node* p) // When you call this function, make sure p is not NULL
{
if( p == NULL )
{
cerr << "error!" << endl;
exit(1);
}
Node *T = new Node;
T->data = val;
T->next = p->next;
p->next = T // if p is NULL, p->next will make your program will crash!!!
}
L
is empty
add2front()
.
L
is non-empty
addafter()
on this last node. add2back
function that works in just this way.
|
|
add2front
and
addafter
, we can easily write a function
addinorder(val,L)
that will insert a new value
val
into L
so that sorted order is maintained.
There are two cases to consider when we write the function:
val
to the front of the list.
val
after some node in the list.
val
is smaller than any value in the list. Note we
are dealing with an already-sorted list, so we can easily check this
condition by comparing answer is when val
is smaller than the
value of the first node in the list!
if( L == NULL || val < L->data )
add2front(val, L);
addafter()
.
p
point to the currently-visited node.
p
points to the last node (i.e., p->next
is NULL
).
In this case we need to insert val
after this last node p
.
val
(i.e., 9)
gets smaller than p->next->data
(i.e., 11) for the first
time, you find the right node p
.
for(Node* p = L; p != NULL; p = p->next)
{
if( p->next == NULL || val < p->next->data )
{
addafter(data, p);
break;
}
}
void addinorder(double val, Node*& L)
{
if( L == NULL || val < L->data )
{
add2front(val, L);
}
else
{
for(Node* p = L; p != NULL; p = p->next)
{
if( p->next == NULL || val < p->next->data )
{
addafter(val, p);
break;
}
}
}
}
addinorder
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 addinorder
,
and when you're done, you'll have a sorted list of values. Not
bad, eh?
Suppose that you already have a list and it's not in sorted
order. You could easily create a sorted copy of the list by
moving through you list a node at a time and calling
addinorder
for that node's data.
Node* sortedcopy(Node* L)
{
Node* S = NULL; // a new empty list S
for(Node* p = L; p != NULL; p = p->next)
addinorder(p->data,S); // insert each data to the new list S using addinorder()
return S; // return the list S
}
This function returns a copy of the original list in sorted order.
addinorder
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