1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
|
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "linked.hpp"
// unlink take a node out of the linked list, but does not dispose of the memory
int linked_list::unlink(linked_node *p)
{
linked_node *q;
if (first()) // if there are any nodes..
{
if (first()==p) // if they want to unlinkt the first node
{
fn->last()->set_next(fn->next()); // set the first's last's next to the first's next
fn->next()->set_last(fn->last()); // set the first next's last to the first last
if (fn->next()==fn) // if there is ony one node
{ fn=NULL; cn=NULL; } // clear the list
else fn=p->next(); // else point the first pointer to the next node
nn--; // decrement the number of nodes in the list
return 1;
}
else
{
q=first()->next();
while (q!=p && q!=first()) // find the node in the list
q=q->next();
if (q!=first()) // is it in the list at all?
{ q->last()->set_next(q->next()); // yes unlink the pointers
q->next()->set_last(q->last());
nn--;
return 1;
} // decrement the number of nodes
}
}
return 0;
}
// this function clears all the nodes in a linked list and dispose of the
// memory for each one by calling is't destructor
linked_list::~linked_list()
{
if (fn)
fn->last()->set_next(NULL); // set the last nodes next to NULL
// so we can go until we hit NULL
while (fn != NULL) // repeat until we get to that node
{
cn=fn->next();
delete fn; // delete the old node
fn=cn;
}
cn=NULL; // clear the list
nn=0; // set the number of nodes to 0
}
// this function returns the node number a node is in a linked list
// it start at the node and goes backwards until it reaches the first
// node
int linked_list::node_number(linked_node *p)
{
int x;
x=1;
while (p!=first())
{ x++; p=p->last(); }
return x;
}
// this function returns a pointer to the xth node
class linked_node *linked_list::get_node(int x)
{
class linked_node *p;
p=fn; // start tat the first node
while (x--!=1) p=p->next(); // go forward X-1 nodes
return p;
}
// this function adds a node to the end of a linked_list
void linked_list::add_end(class linked_node *p)
{
nn++;
if (fn==NULL) // if there are no nodes, then this one becomes the first
{ fn=p;
fn->set_next(fn); // and it poits to itself for first and last
fn->set_last(fn);
}
else
{
p->set_last(fn->last()); // otherwise add it in at the end
p->set_next(fn);
fn->last()->set_next(p);
fn->set_last(p); // the first's last pointer points to the node we just added
}
}
// to add a node at the fron of the list, just add it at the end and set
// the first pointer to it
void linked_list::add_front(class linked_node *p)
{
add_end(p);
fn=p;
}
// insert adds a node in the list according to is sort value
void linked_list::insert(class linked_node *p)
{
class linked_node *q;
// if there are nodes, or it belongs at the beginin call add front
if ((fn==NULL) || (p->compare(fn,sortby)>0))
add_front(p);
// else if it goes at the ned call add_end
else if (p->compare(fn->last(),sortby)<=0)
add_end(p);
else // otherwise we have to find the right spot for it.
{
nn++;
q=fn;
while (q!=fn->last()) // q starts at the front
{ q=q->next();
if (p->compare(q,sortby)>0) // repeat until we find a value greater than the one we are inserting
{ p->set_next(q);
p->set_last(q->last()); // insert it with pointers here
q->last()->set_next(p);
q->set_last(p);
q=fn->last(); // set q to the last node so we exit the loop
}
}
}
}
linked_list::linked_list(linked_node *first)
{ linked_node *prev;
fn=first; cn=first; sortby=1; nn=0;
if (first)
{ cn=first;
do
{
nn++;
prev=cn;
cn=cn->next();
} while (cn && cn!=first);
if (cn==NULL)
{
fn->set_last(prev);
prev->set_next(fn);
}
cn=first;
}
}
|
