home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / man / array.tex next >
Encoding:
Text File  |  1991-11-15  |  3.6 KB  |  97 lines
  1. {\magonebf 3.1 One Dimensional Arrays (array)}
  2.  
  3. An instance $A$ of the data type $array$ is a mapping from an interval 
  4. $I =[a..b]$ of integers, called the index set of $A$, to a set of 
  5. variables of a data type $E$, called the element type of $A$. $A(i)$ 
  6. is called the element at position $i$. 
  7.  
  8.  
  9.  
  10. \bigskip
  11. {\bf 1. Declaration of an array type}
  12.  
  13.  
  14. \decl array E 
  15.  
  16. introduces a new data type with name \name\ consisting of all arrays with 
  17. element type $E$.
  18.  
  19.  
  20.  
  21. \bigskip
  22. {\bf 2. Creation of an array }
  23.  
  24.  
  25. \create A (int\ a,\ int\ b)
  26.  
  27. creates an instance \var\ of type \name\ with index set $[a..b]$.
  28.  
  29.  
  30. \bigskip
  31. {\bf 3. Operations on an array A}
  32. \cleartabs
  33. \+&\hskip 1.5truecm &\hskip 6truecm &\cr
  34. \+\opa E\&   {int\ i}                     
  35.                                      {returns $A(i)$. \precond $a\le i\le b$  }
  36. \smallskip
  37. \+\op  int   low {}                  
  38.                                      {returns the minimal index $a$}
  39. \smallskip
  40. \+\op  int   high {}                 
  41.                                      {returns the maximal index $b$}
  42. \smallskip
  43. \+\op  void  sort {int\ (*cmp)(E\&, E\&)} 
  44.                      {sorts the elements of \var, using function $cmp$}
  45. \+\nop               {to compare two elements, i.e., if $(in_a,\dots,in_b)$}
  46. \+\nop               {and $(out_a,\dots,out_b)$ denote the values of the}
  47. \+\nop               {variables $(A(a),\dots,A(b))$ before and after the}
  48. \+\nop               {call of sort, then $cmp(out_i,out_j) \le 0$ for $i\le j$}
  49. \+\nop               {and there is a permutation $\pi$ of $[a..b]$ such that}
  50. \+\nop               {$out_i=in_{\pi(i)}$ for $a \le i \le b$.}
  51. \smallskip
  52. \+\op  void  sort {int\ (*cmp)(E\&, E\&),\ int\ l,\ int\ h}  {}
  53. \+\nop               {applies the above defined sorting operations to}
  54. \+\nop               {the sub-array \var$[l..h]$.}
  55. \smallskip
  56. \+\op  int   binary\_search {E\ x,\ int\ (*cmp)(E\&, E\&)}  {}
  57. \+\nop               {performs a binary search for $x$. Returns $i$}
  58. \+\nop               {with $A[i] = x$ if $x$ in $A$, $A$.low$()-1$}
  59. \+\nop               {otherwise. Function $cmp$ is used to compare}
  60. \+\nop               {two elements. \precond $A$ must be sorted}
  61. \+\nop               {according to $cmp$.}
  62. \medskip
  63. \+\op void       read {istream\ I}
  64.                      {reads $b-a+1$ objects of type $E$ from the}
  65. \+\nop               {input stream $I$ into the array $A$ using the}
  66. \+\nop               {overloaded $Read$ function (cf. section 1.5)}
  67. \smallskip
  68. \+\op void       read {}
  69.                      {Calls $A$.read($cin$) to read $A$ from the}
  70. \+\nop               {standard input stream $cin$.}
  71. \smallskip
  72. \+\op void       read {string\ s}
  73.                      {As above, uses string $s$ as a prompt.}
  74. \medskip
  75. \+\op void       print {ostream\ O,\ char\ space =\ '\ '}    {} 
  76. \+\nop               {Prints the contents of array $A$ to the output}
  77. \+\nop               {stream $O$ using the overload $Print$ function}
  78. \+\nop               {(cf. section 1.5) to print each element. The}
  79. \+\nop               {elements are separated by the character $space$.}
  80. \smallskip
  81. \+\op void       print {char\ space =\ '\ '}
  82.                      {Calls $A$.print($cout$, $space$) to print $A$ on}
  83. \+\nop               {the standard output stream $cout$.}
  84. \smallskip
  85. \+\op void       print {string\ s,\ char\ space =\ '\ '}    {} 
  86. \+\nop               {As above, uses string $s$ as a header.}
  87.  
  88.  
  89. \bigskip
  90. {\bf 4. Implementation}
  91.  
  92. Arrays are implemented by \CC vectors. The access operation takes time
  93. $O(1)$, the sorting is realized by quicksort (time $O(n \log n)$) and
  94. the binary\_search operation takes time $O(\log n)$, where $n = b-a+1$.
  95. The space requirement is $O(|I|)$.
  96.  
  97.