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
|
//
// Copyright (c) 1994, 1995, 2006 by Mike Romberg ( mike.romberg@noaa.gov )
//
// This file may be distributed under terms of the GPL
//
#ifndef __LLIST_H__
#define __LLIST_H__
#include <stdio.h>
#define MAXCURR 4 // number of 'current' pointers
class LList {
public:
// The first constructor is used for unordered lists ( stacks, queques ).
// The second constructor is used for ordered lists. It's
// parameter is a pointer to the function to be used for ordering the
// list. This function must behave in the following way:
// int Cmp_Fun ( void *data, void *key )
//
// *data is a pointer to the type of information
// to be stored in the list.
//
// *key is a pointer to the location within the data
// which will be used to order the list. In some
// cases these two pointers will be of the same
// type.
//
// function returns :
//
// 0.........*data = *key
// > 0.......*data > *key
// < 0.......*data < *key
LList( void ); // for unordered lists
LList( int ( *cmp_fun )( void *data, void *key ) ); // for ordered lists
virtual ~LList( void ); // frees nodes but not data
// Stack like functions.
// pop returns NULL if the list is empty.
// push returns 1 on sucess and 0 upon failure.
int push( void *data );
void *pop( void );
// Queue like functions
// dequeue returns NULL if the list is empty.
// enqueue returns 1 on sucess and 0 upon failure.
int enqueue( void *data ) { return( push( data ) ); }
void *dequeue( void );
// Ordered list functions
// for insert *key points to some part of *data used for sorting.
// for find and removematch *key points to the "search" key.
// - insert returns 1 on sucess and 0 on failure
// - find and removematch return a pointer to the data stored in the list if
// sucessful and NULL if not.
int insert( void *data, void *key );
void *find( void *key );
void *removematch( void *key );
// Misc. llist functions
int putontop( void *data ); // oposite of push
void remove( void *data ); // removes *data from the list if it's there
void *findn( int n ); // returns nth element if found or NULL if not
void *operator[](int n) // returns nth element if found or NULL if not
{ return findn(n); }
int index( void *data ); // returns the index of *data or 0 if not there
// Sets the a pointer for the linked list to the nth element in
// the list. This function and the three that follow are intended to
// be used for a stepwise search of a linked list. This function sets
// curr_ to the nth element in the list. incc sets the same pointer
// to the next element in the list. decc sets it to the previous
// element in the list. findc returns a pointer to the element
// curr_ is "currently" pointing to. If n is not valid for the list
// curr_ is set to NULL.
void setc( int n, int which = 0 );
void incc( int which = 0 );
void decc( int which = 0 );
void *findc( int which = 0 );
// This function will save a linked list to the file pointed to
// by *fp. The file should be binary. n is saved first and then
// each item on the list is saved. size is the number of bytes of
// each item on the list. The list will remain intact after this
// function is called.
void save( int size, FILE *fp );
// This function reads a linked list from the file pointed to
// by *fp ( previously saved by the above function ). Space is
// allocated for each item, and it is placed into the list in it's
// old position. size is the number of bytes each item occupies.
// This function will return 1 upon sucess and 0 upon failure.
int restore( int size, FILE *fp );
// This function will remaove all of the elements in the linked
// list pointed to by L and free the memory each element occupied.
void kill( void );
int n( void ) const { return( n_ ); } // number of elements in the list
protected:
class LNode {
public:
LNode( void *data = NULL );
void *data_;
LNode *next_;
LNode *prev_;
};
int n_; // number of nodes in the list
LNode *top_, *btm_; // pointers to various nodes
LNode *curr_[MAXCURR];
// a comparison function for ordered lists
int ( *cmp_fun_ )( void *data, void *key );
LNode *findnode( void *key );
void *deletenode( LNode *ptr );
LNode *findnnode( int i );
private:
};
#endif
|
