home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Power-Programmierung
/
CD1.mdf
/
magazine
/
drdobbs
/
1987
/
06
/
holublst.jun
< prev
next >
Wrap
Text File
|
1987-05-05
|
20KB
|
561 lines
Listing 1 -- pq.c
_____________________________________________________________
1| #include <stdio.h>
2|
3| /* PQ.C General-purpose priority-queue routines.
4| * (C) 1987 Allen I. Holub. All Rights Reserved.
5| *
6| * typedef char *PQ; Dummy typedef for priority queue.
7| *
8| * PQ *pq_create( numele, elesize, cmp, swap, initheap )
9| * int numele; Max # of elements in the queue
10| * int elesize; Size of one element in bytes
11| * int (*cmp)(); Pointer to comparison function
12| * int (*swap)(); Pointer to swap function
13| * char *initheap; Inital heap or NULL to allocate
14| *
15| * pq_ins( p, item ) Insert Item into queue
16| * PQ *p; Pointer to priority queue
17| * char *item; Pointer to item to insert
18| * Return number of empty slots
19| * before insertion (0 if none).
20| *
21| * int pq_del( p, target ) Delete item from queue
22| * PQ *p; Pointer to priority queue
23| * char *target; Pointer to place to put deleted
24| * item.
25| * Return # of items in queue before
26| * delete (0 if nothing deleted).
27| *
28| * char *pq_look( queue ) Look at (don't delete) top element
29| * PQ *queue; Pointer to queue.
30| *
31| * int pq_numele( queue ) Return # of elements in queue.
32| * PQ *queue; Pointer to queue.
33| *
34| *-----------------------------------------------------------
35| */
36|
37| typedef struct
38| {
39| int (*cmp)(); /* compares two objects */
40| int (*swap)(); /* swap two objects */
41| int itemsize; /* size of one element in heap */
42| int nitems; /* Number of items in the heap */
43| int maxitem; /* Maximum number of items in heap */
44| char *bottom; /* Ptr. to most-recently added item */
45| char *heap; /* pointer to the heap itself */
46| }
47| PQ;
48|
49| /*-----------------------------------------------------------*/
50|
51| static void reheap_down( p )
52| PQ *p;
53| {
54| /* Reheap the Heap, starting at the top and working
55| * down;
56| */
57|
58| int parent; /* index of parent */
59| int child; /* index of child */
60| char *pparent; /* pointer to parent */
61| char *pchild; /* pointer to child */
62| char *psibling; /* pointer to child's sibling */
63| char *heap; /* pointer to heap */
64|
65| heap = p->heap;
66|
67| for( parent = 0, child = 1; child < p->nitems ;)
68| {
69| pparent = heap + (parent * p->itemsize);
70| pchild = heap + (child * p->itemsize);
71|
72| if( child+1 < p->nitems )
73| {
74| psibling = pchild + p->itemsize ;
75|
76| if( (*p->cmp)(pchild, psibling) < 0 )
77| {
78| pchild = psibling;
79| ++child;
80| }
81| }
82|
83| if( (*p->cmp)( pparent, pchild ) >= 0)
84| break;
85|
86| (*p->swap)( pparent, pchild );
87|
88| parent = child;
89| child = (parent * 2) + 1;
90| }
91| }
92|
93| /*-----------------------------------------------------------*/
94|
95| static void reheap_up( p )
96| PQ *p;
97| {
98| /* Reheap the Heap, starting at the bottom and working up.
99| * Note that we must use a divide-by-2 rather than a
100| * shift-right in the while loop because -1/2 == 0 but
101| * -1 >> 1 == -1.
102| */
103|
104| int parent; /* index of parent */
105| int child; /* index of child */
106| char *pparent; /* pointer to parent */
107| char *pchild; /* pointer to child */
108| char *heap; /* pointer to heap */
109|
110| child = p->nitems - 1;
111| heap = p->heap;
112|
113| while( (parent = (child-1) / 2) >= 0 )
114| {
115| pchild = heap + (child * p->itemsize);
116| pparent = heap + (parent * p->itemsize);
117|
118| if( (*p->cmp)( pparent, pchild ) >= 0)
119| break;
120|
121| (*p->swap)( pparent, pchild );
122| child = parent;
123| }
124| }
125|
126| /*-----------------------------------------------------------*/
127|
128| PQ *pq_create( numele, elesize, cmp, swap, initheap )
129|
130| int numele; /* max # of elements in the queue */
131| int elesize; /* size of one element in byte */
132| int (*cmp)(); /* pointer to comparison function */
133| int (*swap)(); /* pointer to swap function */
134| char *initheap; /* inital heap, NULL to allocate */
135| {
136| /* Create a priority queue that can hold at most
137| * "numele" elements, each of size "elesize". The
138| * cmp function is passed two pointers to queue
139| * elements and it should behave as follows:
140| *
141| * (*cmp)(p1, p2)
142| *
143| * For descending priority queues [pq_get() returns the
144| * largest item].
145| * *p1 < *p2 return < 0
146| * *p1 == *p2 return == 0
147| * *p1 > *p2 return > 0
148| *
149| * For ascending priority queues [pq_get() returns the
150| * smallest item].
151| * *p1 < *p2 return > 0
152| * *p1 == *p2 return == 0
153| * *p1 > *p2 return < 0
154| *
155| * If the initheap argument is NULL, an empty heap is
156| * created automatically, otherwise initheap must point
157| * at an initialized numele-element-long heap.
158| */
159|
160| PQ *p, *malloc() ;
161| int heapsize;
162|
163| heapsize = numele * elesize ; /* heap size in bytes */
164|
165| if( initheap )
166| {
167| if( !(p = malloc(sizeof(PQ))) )
168| return 0;
169|
170| p->heap = initheap;
171| p->bottom = initheap + ((numele - 1) * elesize);
172| p->nitems = numele;
173| }
174| else
175| {
176| if( !(p = malloc(sizeof(PQ) + heapsize)) )
177| return 0;
178|
179| p->heap = (char *)(p + 1);
180| p->nitems = 0;
181| p->bottom = p->heap - elesize ;
182| }
183|
184| p->cmp = cmp;
185| p->swap = swap;
186| p->itemsize = elesize;
187| p->maxitem = numele ;
188| return p;
189| }
190|
191| /*-----------------------------------------------------------*/
192|
193| pq_ins( p, item )
194| PQ *p; /* Pointer to priority queue */
195| char *item; /* Pointer to item to insert */
196| {
197| /* Insert a new item into the priority queue (provided
198| * that space is available.
199| *
200| * Return the number of empty slots in the queue before
201| * the insertion. This number is 0 if the queue is
202| * full and nothing is inserted. Algorithm is:
203| *
204| * if( space is available in the queue )
205| * increase queue size
206| * copy new item into bottom of queue
207| * reheap from the bottom up.
208| */
209|
210| int space_avail = p->maxitem - p->nitems;
211|
212| if( space_avail > 0 )
213| {
214| ++( p->nitems );
215| memcpy( p->bottom += p->itemsize, &item, p->itemsize );
216| reheap_up( p );
217| }
218|
219| return space_avail ;
220| }
221|
222| /*-----------------------------------------------------------*/
223|
224| int pq_del( p, target )
225|
226| PQ *p; /* pointer to priority queue */
227| char *target; /* place to copy current largest item */
228| {
229| /* Copy the largest item in the priority queue to
230| * the address held in target, then delete the item.
231| *
232| * Return the number of items in the queue before the
233| * delete. If this number is 0, then nothing was
234| * in the queue and *target will not have been
235| * modified. Algorithm is:
236| *
237| * if( there's something in the queue ) [1]
238| * remember pointer to former first item [2]
239| * replace the first item with the last one [3]
240| * shrink the heap by one element [4]
241| * reheap from the top down [5]
242| */
243|
244| int slots_in_use;
245|
246| if( slots_in_use = p->nitems ) /* 1 */
247| {
248| memcpy( target, p->heap, p->itemsize ); /* 2 */
249| memcpy( p->heap, p->bottom, p->itemsize ); /* 3 */
250|
251| --(p->nitems) ; /* 4 */
252| p->bottom -= p->itemsize;
253|
254| reheap_down( p ); /* 5 */
255| }
256|
257| return slots_in_use ;
258| }
259|
260| /*-----------------------------------------------------------*/
261|
262| char *pq_look( queue )
263| PQ *queue;
264| {
265| /* Return a pointer to the largest/smallest element
266| * in the priority queue but don't dequeue it.
267| */
268|
269| return queue->heap;
270| }
271|
272| /*-----------------------------------------------------------*/
273|
274| int pq_numele( queue )
275| PQ *queue;
276| {
277| /* Return number of items in queue
278| */
279|
280| return queue->nitems;
281| }
282|
283| /*===========================================================*/
284| #ifdef MAIN
285|
286| int Descending = 1; /* Change these in Codeview */
287| int Makequeue = 1; /* to change the tests. */
288|
289| cmp( s1, s2 )
290| char **s1, **s2;
291| {
292| int rval;
293| rval = strcmp( *s1, *s2 );
294|
295| if( Descending )
296| return rval;
297| else
298| return ( rval < 0 ) ? 1 :
299| ( rval > 0 ) ? -1 :
300| /* rval == 0 */ 0 ;
301| }
302|
303| /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
304|
305| swap( s1, s2 )
306| char **s1, **s2;
307| {
308| char *tmp;
309|
310| tmp = *s1;
311| *s1 = *s2;
312| *s2 = tmp;
313| }
314|
315| /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
316|
317| printq( p )
318| PQ *p;
319| {
320| int i;
321|
322| printf("Queue is:\n");
323|
324| printf( "\tcmp............. 0x%04x\t", p->cmp );
325| printf( "\tswap............ 0x%04x\n", p->swap );
326| printf( "\titemsize........ %d\t", p->itemsize );
327| printf( "\tnitems.......... %d\n", p->nitems );
328| printf( "\tmaxitem......... %d\t", p->maxitem );
329| printf( "\tbottom.......... 0x%04x\n", p->bottom );
330| printf( "\theap............ 0x%04x\t", p->heap );
331| printf( "\tbottom - heap... %d\n\n", (char **)p->bottom -
332| (char **)p->heap );
333| if( p->nitems <= 0 )
334| printf("\tqueue is empty\n");
335|
336| else for( i = 0 ; i < p->nitems ; i++ )
337| {
338| printf("\t%-2d: %10.10s (0x%04x) (children: %2d, %2d)\n",
339| i, ((char **)p->heap)[i], ((char **)p->heap)[i],
340| (2*i)+1, (2*i)+2 );
341| }
342| }
343|
344| /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
345|
346| main()
347| {
348| PQ *queue;
349| char buf[80];
350| int i;
351| char *p;
352|
353| static char *testq[] =
354| {
355| "0", "1", "2", "3", "4", "5", "6", "7", "8", "9"
356| };
357|
358| if( Makequeue )
359| queue = pq_create( 10, sizeof(char*), cmp, swap, 0 );
360| else
361| queue = pq_create( 10, sizeof(char*), cmp, swap, testq);
362|
363| if( !queue )
364| {
365| printf("pq_create failed\n");
366| exit( 1 );
367| }
368|
369| printf("+-------------------------------------------+\n");
370| printf("| Enter i<string><CR> to add string to |\n");
371| printf("| queue, d<CR> to dequeue top element, q to |\n");
372| printf("| exit the program. |\n");
373| printf("+-------------------------------------------+\n");
374|
375| while( 1 )
376| {
377| printq( queue );
378| printf( "\n[i|d|q][string] :" );
379| gets ( buf );
380|
381| if( *buf == 'q' )
382| exit( 1 );
383|
384| else if( *buf == 'i' )
385| {
386| i = pq_ins( queue, strsave(buf + 1) );
387|
388| if( i )
389| printf("%d slots avail. before insert\n", i);
390| else
391| printf("Queue was full, did nothing\n\n");
392| }
393| else
394| {
395| i = pq_del( queue, (char*) &p );
396| printf("%d slots used before delete, got <%s>\n",
397| i, p);
398| if( i )
399| {
400| free( p );
401| p = "nothing";
402| }
403| }
404| }
405| }
406|
407| #endif
Listing 2 -- strsave.c
____________________________________________________________
1| char *strsave( str )
2| char *str;
3| {
4| /* Save the indicated string in a malloc()ed section
5| * of static memory. Return a pointer to the copy or
6| * 0 if malloc failed.
7| */
8|
9| register char *rptr;
10| extern char *malloc();
11|
12| if( rptr = malloc( strlen(str) +1 ))
13| {
14| strcpy( rptr, str );
15| return rptr;
16| }
17|
18| return (char *)0;
19| }
Listing 3 -- freq.c
_______________________________________________________________
1| #include <stdio.h>
2|
3| /* FREQ.C Print a list of the frequency
4| * of occurance of all bytes
5| * in a list of files given on the command line.
6| * Frequencies are printed as a probability x 100.
7| * For example, if we read a total of 20 characters,
8| * 5 of which are 'e', the probability of an 'e'
9| * occuring in the input is 5/20 (.25) and freq will
10| * output (.25 * 100) or 25.
11| */
12|
13| typedef struct
14| {
15| int val;
16| double count;
17| } ITEM;
18|
19| #define TABSIZE 256
20| ITEM Tab[ TABSIZE ]; /* I'm counting on this being */
21| /* initialized to zero. */
22|
23| /*----------------------------------------------------------*/
24|
25| cmp( item1, item2 )
26| ITEM *item1, *item2;
27| {
28| /* Comparison function used by ssort(), below.
29| * Count is the primary sort field and val is
30| * the secondary field.
31| */
32|
33| int rval;
34|
35| return ( item1->count < item2->count ) ? -1 :
36| ( item1->count > item2->count ) ? 1 :
37| /* item1->count == item2->count */
38| item1->val - item2->val ;
39| }
40|
41| /*----------------------------------------------------------*/
42|
43| main( argc, argv )
44| char **argv;
45| {
46| char *bin_to_ascii(); /* in pchar.c */
47| FILE *fp;
48| int i;
49| double smallest;
50| double largest;
51| double numchars = 0.0 ;
52| double sum = 0.0 ;
53| double probability = 0.0 ;
54|
55| reargv( &argc, &argv ); /* Needed only for */
56| /* On Command! shell */
57|
58| for( --argc, ++argv ; --argc >= 0 ; argv++ )
59| {
60| if( !(fp = fopen( *argv, "rb")) )
61| perror( *argv );
62| else
63| {
64| fprintf( stderr, "%s\n", *argv );
65|
66| while( (i = getc(fp)) != EOF )
67| {
68| ++ numchars;
69| ++ Tab[ i & 0xff ].count ;
70| }
71|
72| fclose( fp );
73| }
74| }
75|
76| /* Find largest and smallest elements and at the same
77| * time initialize the val fields of the Tab entries.
78| */
79|
80| largest = 0.0;
81| smallest = numchars ;
82|
83| for( i = 0 ; i <= 0xff ; i++ )
84| {
85| Tab[i].val = i;
86|
87| if( Tab[i].count > 0.00000001
88| && Tab[i].count < smallest )
89| smallest = Tab[i].count;
90|
91| if( Tab[i].count > largest )
92| largest = Tab[i].count;
93| }
94|
95| /* Sort the list by probability. A shell sort is used.
96| * You can replace the ssort call below with a call to
97| * the qsort() subroutine, available with many compilers.
98| * Qsort() takes the same arguments as ssort().
99| * A version of qsort appeared in the in the C Chest,
100| * DDJ #102 (April, 1985; also Bound Volume 10, p.316).
101| * The ssort() subroutine appeared in DDJ #113, C Chest
102| * (March, 1986) p. 70.
103| */
104|
105| ssort( Tab, TABSIZE, sizeof(ITEM), cmp );
106|
107| /*
108| * Print the list. Each element is printed as three
109| * numbers: the value of the charcter (in hex), the
110| * probability of that character apearing in the input,
111| * and the probabability normalized so that the least-
112| * frequently occuring probability has the value 1.
113| */
114|
115| for( i = 0 ; i < TABSIZE ; i++ )
116| {
117| probability = Tab[i].count / numchars ;
118| sum += probability;
119|
120| printf( "0x%02x\t%7.6f\t%1.0f\n",
121| Tab[i].val,
122| probability,
123| Tab[i].count / smallest );
124| }
125|
126| fprintf( stderr, "Total = %8.6f (N = %8.2f)\n",
127| sum, numchars );
128| }
