home *** CD-ROM | disk | FTP | other *** search
/ minnie.tuhs.org / unixen.tar / unixen / PDP-11 / Trees / V6 / usr / doc / c / c6 < prev    next >
Encoding:
Text File  |  1975-06-26  |  10.8 KB  |  467 lines
  1. .ul
  2. 16.  Examples.
  3. .et
  4. These examples are intended to illustrate
  5. some typical C constructions as well as
  6. a serviceable style of writing C programs.
  7. .ms
  8. 16.1  Inner product
  9. .et
  10. This function returns the inner product of
  11. its array arguments.
  12. .sp .7
  13. .nf
  14. .bG
  15.     double inner^(^v1, v2, n^)^
  16.     double v1^[^^]^, v2^[^^]^;
  17.     {
  18.         double sum^;
  19.         int i^;
  20.         sum = 0.0^;
  21.         for ^(^i=0^; i<n^; i\fR++\fG^)^
  22.             sum \fR=+\fG v1^[^i^] \** v2^[^i^]^;
  23.         return^(^sum^)^;
  24.     }
  25. .fi
  26. .eG
  27. .sp .7
  28. The following version is somewhat more efficient,
  29. but perhaps a little less clear.
  30. It uses the facts that parameter arrays are
  31. really pointers, and that all parameters are passed
  32. by value.
  33. .sp .7
  34. .nf
  35. .bG
  36.     double inner^(^v1, v2, n^)^
  37.     double \**v1, \**v2^;
  38.     {
  39.         double sum^;
  40.         sum = 0.0^;
  41.         while^(^n\fR\fR\(mi\(mi\fG\fG^)^
  42.             sum \fR=+\fG \**v1\fR++\fG  \**  \**v2\fR++\fG^;
  43.         return^(^sum^)^;
  44.     }
  45. .fi
  46. .eG
  47. .sp .7
  48. The declarations for the parameters are really exactly
  49. the same as in the last example.
  50. In the first case array declarations ``^[^^^]^'' were given
  51. to emphasize that the parameters would be referred
  52. to as arrays; in the second, pointer declarations
  53. were given because the indirection operator and
  54. ++ were used.
  55. .ms
  56. 16.2  Tree and character processing
  57. .et
  58. Here is a complete C program
  59. ^(^courtesy of R. Haight^)^ which reads a document
  60. and produces an alphabetized list of words
  61. found therein together with
  62. the number of occurrences of each word.
  63. The method keeps a binary tree of words
  64. such that the left descendant tree for
  65. each word has all the words lexicographically smaller than
  66. the given word,
  67. and the right descendant has all the larger
  68. words.
  69. Both the insertion and the printing routine
  70. are recursive.
  71. .pg
  72. The program calls the library routines \fIgetchar\fR to
  73. pick up characters
  74. and \fIexit\fR to terminate execution.
  75. \fIPrintf\fR is called to print
  76. the results according to a format
  77. string.
  78. A version of
  79. \fIprintf\fR is given below ^(^\(sc16.3^)^.
  80. .pg
  81. Because all the external definitions for
  82. data are given at the top, no \fGextern\fR
  83. declarations are necessary within the functions.
  84. To stay within the rules, a type declaration
  85. is given for each non-integer function
  86. when the function is used before
  87. it is defined.
  88. However, since all such
  89. functions return pointers which are
  90. simply assigned to other pointers,
  91. no actual harm would result from
  92. leaving out the declarations; the
  93. supposedly \fGint\fR function values would be assigned
  94. without error or complaint.
  95. .sp .7
  96. .nf
  97. .in .5i
  98. .bG
  99. .ta .5i 1i 3i
  100. # define nwords 100    /\** number of different words \**/
  101. # define wsize 20    /\** max chars per word \**/
  102. struct tnode {        /\** the basic structure \**/
  103.     char tword^[^wsize^]^;
  104.     int count^;
  105.     struct tnode \**left^;
  106.     struct tnode \**right^;
  107. }^;
  108. .sp .7
  109. struct tnode space^[^nwords^]^;    /\** the words themselves \**/
  110. int nnodes nwords^;    /\** number of remaining slots \**/
  111. struct tnode \**spacep space^;    /\** next available slot \**/
  112. struct tnode \**freep^;    /\** free list \**/
  113. /\**
  114.  \** The main routine reads words until end-of-file \
  115. ^(^\(aa\\0\(aa returned from "getchar"^)^
  116.  \** "tree" is called to sort each word into the tree.
  117.  \**/
  118. .ta .5i 1i 1.5i 2i 2.5i 3i
  119. main^(^^)^
  120. {
  121.     struct tnode \**top, \**tree^(^^)^;
  122.     char c, word^[^wsize^]^;
  123.     int i^;
  124. .sp .5
  125.     i = top = 0^;
  126.     while ^(^c=getchar^(^^)^^)^
  127.         if ^(^\(aaa\(aa<=c && c<=\(aaz\(aa \(or\(or \(aaA\(aa<=c && c <=\(aaZ\(aa^)^ {
  128.             if ^(^i<wsize\(mi1^)^
  129.                 word^[^i\fR++\fG^]^ = c^;
  130.         } else
  131.             if ^(^i^)^ {
  132.                 word^[^i\fR++\fG^]^ = \(aa\\0\(aa^;
  133.                 top = tree^(^top, word^)^;
  134.                 i = 0^;
  135.             }
  136.     tprint^(^top^)^;
  137. }
  138. /\**
  139.  \** The central routine.  If the subtree pointer is null, \
  140. allocate a new node for it.
  141.  \** If the new word and the node\(aas word are the same, increase \
  142. the node\(aas count.
  143.  \** Otherwise, recursively sort the word into the left or right subtree according
  144.  \** as the argument word is less or greater \
  145. than the node\(aas word.
  146.  \**/
  147. struct tnode \**tree^(^p, word^)^
  148. struct tnode \**p^;
  149. char word^[^^]^;
  150. {
  151.     struct tnode \**alloc^(^^)^;
  152.     int cond^;
  153. .sp .5
  154.     /\** Is pointer null? \**/
  155.     if ^(^p\fR==\fG0^)^ {
  156.         p = alloc^(^^)^;
  157.         copy^(^word, p\(mi>tword^)^;
  158.         p\(mi>count = 1^;
  159.         p\(mi>right = p\(mi>left = 0^;
  160.         return^(^p^)^;
  161.     }
  162.     /\** Is word repeated? \**/
  163.     if ^(^^(^cond=compar^(^p\(mi>tword, word^)^^)^ \fR==\fG 0^)^ {
  164.         p\(mi>count\fR++\fG^;
  165.         return^(^p^)^;
  166.     }
  167.     /\** Sort into left or right \**/
  168.     if ^(^cond<0^)^
  169.         p\(mi>left = tree^(^p\(mi>left, word^)^;
  170.     else
  171.         p\(mi>right = tree^(^p\(mi>right, word^)^;
  172.     return^(^p^)^;
  173. }
  174. /\**
  175.  \** Print the tree by printing the left subtree, the \
  176. given node, and the right subtree.
  177.  \**/
  178. tprint^(^p^)^
  179. struct tnode \**p^;
  180. {
  181.     while ^(^p^)^ {
  182.         tprint^(^p\(mi>left^)^;
  183.         printf^(^"%d:  %s\\n", p\(mi>count, p\(mi>tword^)^;
  184.         p = p\(mi>right^;
  185.     }
  186. }
  187. /\**
  188.  \** String comparison: return number ^(^>, =, <^)^ 0
  189.  \** according as s1 ^(^>, =, <^)^ s2.
  190.  \**/
  191. compar^(^s1, s2^)^
  192. char \**s1, \**s2^;
  193. {
  194.     int c1, c2^;
  195. .sp .5
  196.     while^(^^(^c1 = \**s1\fR++\fG^)^ \fR==\fG ^(^c2 = \**s2\fR++\fG^)^^)^
  197.         if ^(^c1\fR==\fG\(aa\\0\(aa^)^
  198.             return^(^0^)^;
  199.     return^(^c2\(mic1^)^;
  200. }
  201. /\**
  202.  \** String copy: copy s1 into s2 until the null
  203.  \** character appears.
  204.  \**/
  205. copy^(^s1, s2^)^
  206. char \**s1, \**s2^;
  207. {
  208.     while^(^\**s2\fR++\fG = \**s1\fR++\fG^)^;
  209. }
  210. /\**
  211.  \** Node allocation: return pointer to a free node.
  212.  \** Bomb out when all are gone.  Just for fun, there
  213.  \** is a mechanism for using nodes that have been
  214.  \** freed, even though no one here calls "free."
  215.  \**/
  216. struct tnode \**alloc^(^^)^
  217. {
  218.     struct tnode \**t^;
  219. .sp .5
  220.     if ^(^freep^)^ {
  221.         t = freep^;
  222.         freep = freep\(mi>left^;
  223.         return^(^t^)^;
  224.     }
  225.     if ^(^\fR\(mi\(mi\fGnnodes < 0^)^ {
  226.         printf^(^"Out of space\\n"^)^;
  227.         exit^(^^)^;
  228.     }
  229.     return^(^spacep\fR++\fG^)^;
  230. }
  231. /\**
  232.  \** The uncalled routine which puts a node on the free list.
  233.  \**/
  234. free^(^p^)^
  235. struct tnode \**p^;
  236. {
  237.     p\(mi>left = freep^;
  238.     freep = p^;
  239. }
  240. .sp .7
  241. .fi
  242. .eG
  243. .in 0
  244. To illustrate a slightly different technique of
  245. handling the same problem, we will repeat
  246. fragments of this example with the tree nodes
  247. treated explicitly as members of an array.
  248. The fundamental change is to
  249. deal with the subscript
  250. of the array member under
  251. discussion, instead of a pointer to it.
  252. The \fGstruct\fR declaration becomes
  253. .sp .7
  254. .nf
  255. .bG
  256.     struct tnode {
  257.         char tword^[^wsize^]^;
  258.         int count;
  259.         int left;
  260.         int right;
  261.     };
  262. .fi
  263. .eG
  264. .sp .7
  265. and \fIalloc\fR becomes
  266. .sp .7
  267. .nf
  268. .bG
  269.     alloc^(^^)^
  270.     {
  271.         int t;
  272. .sp .5
  273.         t = \fR\(mi\(mi\fGnnodes;
  274.         if ^(^t<=0^)^ {
  275.             printf^(^"Out of space\\n"^)^;
  276.             exit^(^^)^;
  277.         }
  278.         return^(^t^)^;
  279.     }
  280. .fi
  281. .eG
  282. .sp .7
  283. The \fIfree\fR stuff has disappeared because
  284. if we deal with exclusively with
  285. subscripts some sort of map has
  286. to be kept, which is too much trouble.
  287. .pg
  288. Now the \fItree\fR routine returns
  289. a subscript also, and it becomes:
  290. .sp .7
  291. .nf
  292. .bG
  293.     tree^(^p, word^)^
  294.     char word^[^^]^;
  295.     {
  296.         int cond;
  297. .sp .5
  298.         if ^(^p\fR==\fG0^)^ {
  299.             p = alloc^(^^)^;
  300.             copy^(^word, space^[^p^]^.tword^)^;
  301.             space^[^p^]^.count = 1;
  302.             space^[^p^]^.right = space^[^p^]^.left = 0;
  303.             return^(^p^)^;
  304.         }
  305.         if ^(^^(^cond=compar^(^space^[^p^]^.tword, word^)^^)^ \fR==\fG 0^)^ {
  306.             space^[^p^]^.count\fR++\fG;
  307.             return^(^p^)^;
  308.         }
  309.         if ^(^cond<0^)^
  310.             space^[^p^]^.left = tree^(^space^[^p^]^.left, word^)^;
  311.         else
  312.             space^[^p^]^.right = tree^(^space^[^p^]^.right, word^)^;
  313.         return^(^p^)^;
  314.     }
  315. .fi
  316. .eG
  317. .sp .7
  318. The other routines are changed similarly.
  319. It must be pointed out that
  320. this version is noticeably
  321. less efficient than the first because
  322. of the multiplications which
  323. must be done
  324. to compute an offset in \fIspace\fR
  325. corresponding to the subscripts.
  326. .pg
  327. The observation that subscripts
  328. ^(^like ``a^[^i^]^''^)^ are less efficient
  329. than pointer indirection ^(^like ``\**ap''^)^
  330. holds true independently of whether or not
  331. structures are involved.
  332. There are of course many situations where subscripts
  333. are indispensable, and others where the loss
  334. in efficiency is worth a gain in clarity.
  335. .ms
  336. 16.3  Formatted output
  337. .et
  338. Here is a simplified version of the \fIprintf\fR routine, which is
  339. available in the C library.
  340. It accepts a string ^(^character array^)^
  341. as first argument, and prints subsequent arguments
  342. according to specifications contained in
  343. this format string.
  344. Most characters in the string are simply
  345. copied to the output; two-character sequences beginning
  346. with ``%'' specify that the next argument
  347. should be printed in a style as follows:
  348. .sp .7
  349. .nf
  350.     %d    decimal number
  351.     %o    octal number
  352.     %c    \s8ASCII\s10 character, or 2 characters if \
  353. upper character is not null
  354.     %s    string ^(^null-terminated array of characters^)
  355.     %f    floating-point number
  356. .sp .7
  357. .fi
  358. The actual parameters for each function
  359. call are laid out contiguously in
  360. increasing storage locations;
  361. therefore, a function with a variable number
  362. of arguments
  363. may take the address of ^(^say^)^ its first argument,
  364. and access the remaining arguments by use
  365. of subscripting ^(^regarding the arguments
  366. as an array^)^
  367. or by indirection combined with
  368. pointer incrementation.
  369. .pg
  370. If in such a situation
  371. the arguments have mixed types, or if in general
  372. one wishes to insist that an lvalue should
  373. be treated as having a given type, then
  374. \fGstruct\fR declarations like those illustrated below
  375. will be useful.
  376. It should be evident, though,
  377. that such techniques are implementation dependent.
  378. .pg
  379. \fIPrintf\fR depends as well on the fact that
  380. \fGchar\fR and \fGfloat\fR arguments
  381. are widened respectively to \fGint\fR and \fGdouble\fR,
  382. so there are effectively only two sizes of arguments
  383. to deal with.
  384. \fIPrintf\fR calls the library routines
  385. \fIputchar\fR to write out single characters
  386. and \fIftoa\fR to dispose of
  387. floating-point numbers.
  388. .sp .7
  389. .in .5i
  390. .bG
  391. .nf
  392. printf^(^fmt, args^)^
  393. char fmt^[^^]^;
  394. {
  395.     char \**s^;
  396.     struct { char \**\**charpp^; };
  397.     struct { double \**doublep^; };
  398.     int \**ap, x, c^;
  399. .sp .5
  400.     ap = &args^;             /\** argument pointer \**/
  401.     for ( ; ; ) {
  402.         while^(^^(^c = \**fmt\fR++\fG^)^ != \(aa%\(aa^)^ {
  403.             if^(^c \fR==\fG \(aa\\0\(aa^)^
  404.                 return^;
  405.             putchar^(^c^)^;
  406.         }
  407.         switch ^(^c = \**fmt\fR++\fG^)^ {
  408.         /\** decimal \**/
  409.         case \(aad^\(aa:
  410.             x = \**ap\fR++\fG^;
  411.             if^(^x < 0^)^ {
  412.                 x = \(mix^;
  413.                 if^(^x<0^)^ {      /\** is \(mi infinity \**/
  414.                     printf^(^"\(mi32768"^)^;
  415.                     continue^;
  416.                 }
  417.                 putchar^(^\(aa\(mi\(aa^)^;
  418.             }
  419.             printd^(^x^)^;
  420.             continue^;
  421.         /\** octal \**/
  422.         case \(aao\(aa:
  423.             printo^(^\**ap\fR++\fG^)^;
  424.             continue^;
  425.         /\** float, double \**/
  426.         case ^^\(aaf^\(aa:
  427.             /\** let ftoa do the real work \**/
  428.             ftoa^(^\**ap.doublep\fR++\fG^)^;
  429.             continue^;
  430.         /\** character \**/
  431.         case \(aac\(aa:
  432.             putchar^(^\**ap\fR++\fG^)^;
  433.             continue^;
  434.         /\** string \**/
  435.         case \(aas\(aa:
  436.             s = \**ap.charpp\fR++\fG^;
  437.             while^(^c = \**s\fR++\fG^)^
  438.                 putchar^(^c^)^;
  439.             continue^;
  440.         }
  441.         putchar^(^c^)^;
  442.     }
  443. }
  444. /\**
  445.  \** Print n in decimal^; n must be non-negative
  446.  \**/
  447. printd^(^n^)^
  448. {
  449.     int a^;
  450.     if ^(^a=n/10^)^
  451.         printd^(^a^)^;
  452.     putchar^(^n%10 + \(aa0\(aa^)^;
  453. }
  454. /\**
  455.  \** Print n in octal, with exactly 1 leading 0
  456.  \**/
  457. printo^(^n^)^
  458. {
  459.     if ^(^n^)^
  460.         printo^(^^(^n>>3^)^&017777^)^;
  461.     putchar^(^^(^n&07^)^+\(aa0\(aa^)^;
  462. }
  463. .br
  464. .fi
  465. .eG
  466. .in 0
  467.