4. Prefacio Modo y medios C++ C ++ C++ C++ C++ C java python
perl C# D
5. iv Repita mientras m > 0 y m < n si a[m] < a[x]
entonces m = m/2; de lo contrario m = 2*m fin si Fin repita
mientras C++ while (m > 0 and m < n) { if (a[m] < a[x]) m
= m/2; else m = 2*m; } C++ C++ C++ C++ C++ java C C++ java
6. v Biblioteca ALEPH ALEPH ALEPH ftp:://ftp.ula.ve/lrleon/
aleph bcpp [email protected] http://www.ing.ula. ve/aleph doxygen
Programacin literaria o noweb C++ C++ n if (n (...) int string
Square Triangle Circle
42. 1.2. Herencia 17 Medium_Type:Medium Figure -point: Point
+medium: Medium_Type +Figure(in point:Point) +Figure(in
figure:Figure) +~Figure() +get_point(): Point +draw(): void
+move(in p:Point): void +erase(): void +scale(in ratio:Ratio): void
+rotate(in angle:Angle): void Medium Type C++ + typedef Medium
Medium_Type; Medium Type void Square::draw() { /* .... */
Medium_Type m; // Instancia un objeto "medio de contraste" /* ....
*/ medium.put_line(...); } medium Figure Square::draw()
Square::draw()
43. 18 Cap tulo 1. Abstraccin de datos o1.2.3.4 Lo general y lo
genrico e are equals() 1.3 El problema fundamental de estructuras
de datos Key_Type:T Compare_Type:Compare Set +insert(in key:T):
void +search(in key:T): T * +remove(in key:T): void +size(): size_t
+swap(inout set:Set): void +join(in set:Set): Set +split(in
key:T,out l:Set,out r:Set): void +position(in key:T): int
+select(in pos:int): T* +split_pos(in pos:int,out l:Set, out
r:Set): void
44. 1.3. El problema fundamental de estructuras de datos 19 Set
T Compare Set Set C++ template struct Set { void insert(const T
& key); T * search(const T & key); void remove(const T
& key); const size_t size() const; void swap(Set & set);
void join(Set * set); void split(const T& key, Set *& l,
Set *& r); const int position(const T& key) const; T *
select(const int pos); void split_pos(const int & pos, Set
*& l, Set *& r); }; Set T insert() search() remove() size()
key Set swap(set) set this Set join(set) this set set join() 1.3.1
Comparacin general entre claves o T Compare Compare T Compare <
k1 k2 Compare () k1 < k2
45. 20 Cap tulo 1. Abstraccin de datos o if (Compare() (k1,
k2)) // k1 < k2? // accin a ejecutar si k1 < k2 o else if
(Compare() (k2, k1)) // k2 < k1? // accin a ejecutar si k2 <
k1 o else // Tienen que ser iguales // accin a ejecutar si k1 == k2
o1.3.2 Operaciones para conjuntos ordenables S =< k0, k2, . . .
, kn1 > n S split(key, l, r) l =< k0, k1, . . . , ki > r
=< ki+1, ki+2, . . . , kn1 > key l < r =< kpos, . . . ,
kn1 > pos 1.3.3 Circunstancias del problema fundamental
46. 1.4. Dise o de datos y abstracciones n 211.3.4
Presentaciones del problema fundamental C++ stdc++ set multiset ( ,
) C++ map multimap [] 1.4 Diseo de datos y abstracciones n 1.4.1
Tipos de abstraccin o
47. 22 Cap tulo 1. Abstraccin de datos o 1.4.2 El principio
n-a-n Figure
48. 1.4. Dise o de datos y abstracciones n 23 1.4.3 Induccin y
deduccin o o
49. 24 Cap tulo 1. Abstraccin de datos o draw() move() 1.4.4
Ocultamiento de informacin o
50. 1.5. Notas y recomendaciones bibliogrcas a 251.5 Notas y
recomendaciones bibliogrcas a Simula Simula Simula C++ C Smalltalk
C++ C++ C++ C++ C++
51. 26 Cap tulo 1. Abstraccin de datos o1.6 Ejercicios Xfig DIA
Medio locomocin Medio areo Medio terrestre Medio martimo
Helicoptero Energa Avin Barco Globo Dirigible Monopatn Submarino
Cohete Patineta Patines Carreta Bus Tren Moto Bicicleta Con Motor
Sin Motor
52. 1.6. Bibliograf a 27 S Set S Set template __Set
extraer(__Set & set, int i, int j); S i j S [0..i 1] [j + 1..n
1] n = |S| Bibliograf a
53. 28 Cap tulo 1. Abstraccin de datos o
54. Cap tulo 2Secuencias
55. 30 Cap tulo 2. Secuencias 2.1 Arreglos n [] C++ a[15] = 9 9
A[11] T sizeof(T) 0 1 2 3 4 5 6 7 8 9 10 Base T0 T1 T2 T3 T4 T5 T6
T7 T8 T9 T10
56. 2.1. Arreglos 31 i = base + i sizeof(T) C C++ 2.1.1
Operaciones bsicas con Arreglos a 2.1.1.1 Aritmtica de punteros e C
C++ T * arreglo ptr = new T[n T n T n arreglo ptr i *(arreglo ptr +
i) = 5; I(predicado) nana
57. 32 Cap tulo 2. Secuencias arreglo ptr i int sizeof(int)
*(arreglo ptr + i) arreglo ptr[i] i arreglo ptr ptr 2.1.1.2 B
squeda por clave u template int binary_search(T a[], const T &
x, int l, int r) { int m; // ndice del medio while (l a[m]? l = m +
1; else return m; // ==> a[m] == x ==> encontrado! } return
m; } binary search binary search() x l r a m = (l + r)/2 a[m] x x
a[m] binary search() x x x x n
58. 2.1. Arreglos 33 sequential search() 2.1.1.3 Insercin por
clave o template void insert_by_gap(T a[], const T & x, int
& n) { int pos_gap = binary_search(T, x, 0, n - 1); for (int i
= n; i > pos_gap; --i) a[i] = a[i - 1]; a[pos_gap] = x; ++n; }
binary search pos gap --i n n insert by gap() 2.1.1.4 Eliminacin
por clave o sequential search() binary search()
59. 34 Cap tulo 2. Secuencias template void
remove_in_unsorted_array(T a[], const T & x, int & n) { int
pos_gap = sequential_search(T, x, 0, n - 1); if (a[pos_gap] != x)
// excepcin: x no se encuentra en a[] o a[pos_gap] = a[n - 1]; --n;
} sequential search remove in unsorted array() template void
remove_in_sorted_array(T a[], const T & x, int & n) { int
pos_gap = binary_search(T, x, 0, n - 1); if (a[pos_gap] != x) //
excepcin: x no se encuentra en a[] ; o for (int i = pos_gap; i <
n; ++i) a[i] = a[i + 1]; --n; } binary search pos gap ++i n 2.1.2
Manejo de memoria para arreglos
60. 2.1. Arreglos 352.1.2.1 Arreglos en memoria esttica a
2.1.2.2 Arreglos en pila GNU void foo(size_t n) { int array[n]; ...
} foo() 2.1.2.3 Arreglos en memoria dinmica a C++ 1000 int * array
= new int [1000]; C++ static
65. 40 Cap tulo 2. Secuencias BitProxy + operator int () const
{ return byte_ptr->read_bit(bit_index); } i = array[40] int
BitProxy BitProxy int int array[40] = i + BitProxy& operator =
(const size_t & value) { byte_ptr->write_bit(bit_index,
value); return *this; } BitProxy BitProxy [] BitArray + int
read_bit(const size_t & i) const { const int bit_index = i % 8;
return array_of_bytes[i/8].read_bit(bit_index); } void
write_bit(const size_t & i, const unsigned int & value)
const { array_of_bytes[i/8].write_bit(i, value); } BitArray
BitArray + void resize(const size_t & new_dim) { const size_t
new_num_bytes = new_dim/8 + (((new_dim % 8) != 0) ? 1 : 0); Byte *
new_array_of_bytes = new Byte [new_num_bytes]; for (int i = 0, n =
Aleph::min(num_bytes, new_num_bytes); i < n; ++i)
new_array_of_bytes[i] = array_of_bytes[i]; num_bits = new_dim;
num_bytes = new_num_bytes; delete [] array_of_bytes; array_of_bytes
= new_array_of_bytes;
66. 2.1. Arreglos 41 } resize() 2.1.4 Arreglos Dinmicos a C C++
C realloc() void *realloc(void *ptr, size_t size); ptr malloc()
calloc() realloc() ptr size realloc() realloc() ptr2.1.5 El TAD
DynArray DynArray T DynArray size() DynArray
67. 42 Cap tulo 2. Secuencias cut() DynArray DynArray template
class DynArray { DynArray DynArray DynArray }; DynArray DynArray
T::T() T::~T() DynArray 2 2 1024 1024 1024 2.1.5.1 Estructura de
datos de DynArray DynArray Directorio: dir size Segmento: seg size
dir size Bloque: T block size dir size seg size dir size seg size
block size 32 Pentium III 232 232 short 4 2
68. 2.1. Arreglos 43 Bloques dir size block size Segmento seg
size Directorio DynArray touch() i Indice del segmento en el
directorio: seg sizeblock size pos in dir = i seg size block size
pos in dir Indice del bloque en el segmento: i block size pos in
seg = block size = i (seg size block size)
69. 44 Cap tulo 2. Secuencias pos in seg Indice del elemento en
el bloque: i pos in block = block size pos in block = (i (seg size
block size)) block size DynArray DynArray mutable size_t pow_dir;
mutable size_t pow_seg; mutable size_t pow_block; 2 2pow dir 2pow
seg 2pow block 2pow dir 2pow seg 2pow block Max Dim Allowed
std::length error std::overflow error seg size = 2pow seg block
size = 2 pow block pos in dir = 2pow seg i 2 pow block i = (pow
seg+pow block) 2 DynArray + mutable size_t seg_plus_block_pow;
70. 2.1. Arreglos 45 2(pow seg+pow block) seg plus block pow =
i (2pow seg 2pow block ) = i 2(pow seg+pow block) 2 i seg plus
block pow pos in dir = i seg plus block pow seg plus block pow i
seg plus block pow seg plus block pow DynArray + mutable size_t
mask_seg_plus_block; mask seg plus block mask seg plus block = 2seg
plus block pow 1 2seg plus block pow seg plus block pow seg plus
block pow seg plus block pow seg plus block pow AND C++ & = i
AND mask seg plus block = i & mask seg plus block mask seg plus
block seg plus block pow DynArray size_t mask_seg; size_t
mask_block; mask seg mask seg = 2pow seg 1 = seg size 1 ; pos in
seg = >> pow block mask block mask block = 2pow block 1 =
block size 1
71. 46 Cap tulo 2. Secuencias block size mask block pos in
block = (i & mask seg plus block) & mask block DynArray +
size_t index_in_dir(const size_t & i) const { return i >>
seg_plus_block_pow; } size_t modulus_from_index_in_dir(const size_t
& i) const { return (i & mask_seg_plus_block); } size_t
index_in_seg(const size_t & i) const { return
modulus_from_index_in_dir(i) >> pow_block; } size_t
index_in_block(const size_t & i) const { return
modulus_from_index_in_dir(i) & mask_block; } index in block
index in dir index in seg index in dir() i index in seg() i modulus
from index in dir()) index in block() i inline DynArray + mutable
size_t max_dim; // 2^(pow_dir + pow_seg + pow_block) - 1 max dim
DynArray + size_t current_dim; size_t num_segs; size_t
num_blocks;
72. 2.1. Arreglos 47 current dim num segs num blocks 2.1.5.2
Manejo de memoria NULL NULL DynArray + T *** dir;dir DynArray +
void fill_dir_to_null() { for (size_t i = 0; i < dir_size; ++i)
dir[i] = NULL; } void fill_seg_to_null(T ** seg) { for (size_t i =
0; i < seg_size; ++i) seg[i] = NULL; } fill dir to null fill seg
to null fill dir to null() NULL NULL fill seg to null() seg NULL
fill dir to null() fill seg to null() DynArray + void
allocate_dir() { dir = new T ** [dir_size]; fill_dir_to_null(); }
void allocate_segment(T **& seg)
73. 48 Cap tulo 2. Secuencias { seg = new T* [seg_size];
fill_seg_to_null(seg); ++num_segs; } allocate dir allocate segment
fill dir to null fill seg to null allocate dir() NULL allocate
segment() seg NULL NULLdir[i] == NULL dir[i][j] ==NULL DynArray T
DynArray + T default_initial_value; T * default_initial_value_ptr;
default initial value default initial value ptr NULL T::T()
DynArray default initial value ptr NULL DynArray + void
allocate_block(T *& block) { block = new T [block_size];
++num_blocks; if (default_initial_value_ptr == NULL) return; for
(size_t i = 0; i < block_size; ++i) block[i] =
default_initial_value; } allocate block allocate block() block
block default initial value T&operator = (const T&)
DynArray + void release_segment(T **& seg) { delete [] seg; seg
= NULL;
74. 2.1. Arreglos 49 --num_segs; } void release_block(T *&
block) { delete [] block; block = NULL; --num_blocks; } release
block release segment DynArray + void release_blocks_and_segment(T
** & seg) { for(size_t i = 0; i < seg_size ; ++i) if (seg[i]
!= NULL) release_block(seg[i]); release_segment(seg); } void
release_all_segments_and_blocks() { for(size_t i = 0; i <
dir_size ; ++i) if (dir[i] != NULL)
release_blocks_and_segment(dir[i]); current_dim = 0; } void
release_dir() { release_all_segments_and_blocks(); delete [] dir;
dir = NULL; current_dim = 0; } release all segments and blocks
release blocks and segment release block release segment 2.1.5.3
Especicacin e implantacin de mtodos p blicos o o e u DynArray
DynArray(const size_t & dim = 10000) : pow_dir (
Default_Pow_Dir ), pow_seg ( Default_Pow_Seg ),
78. 2.1. Arreglos 53 mask_seg = array.mask_seg; mask_block =
array.mask_block; current_dim = array.current_dim; num_segs =
array.num_segs; num_blocks = array.num_blocks;
default_initial_value_ptr = array.default_initial_value_ptr;
allocate_dir(array.dir); } allocate dir DynArray allocate dir()
DynArray DynArray + T & access(const size_t & i) { return
dir[index_in_dir(i)][index_in_seg(i)][index_in_block(i)]; } index
in block index in dir index in seg access() i DynArray + bool
exist(const size_t & i) const { const size_t pos_in_dir =
index_in_dir(i); if (dir[pos_in_dir] == NULL) return false; const
size_t pos_in_seg = index_in_seg(i); if
(dir[pos_in_dir][pos_in_seg] == NULL) return false; return true; }
index in dir index in seg exist() true i false DynArray + T *
test(const size_t & i) const { const size_t pos_in_dir =
index_in_dir(i); if (dir[pos_in_dir] == NULL) return NULL;
79. 54 Cap tulo 2. Secuencias const size_t pos_in_seg =
index_in_seg(i); if (dir[pos_in_dir][pos_in_seg] == NULL) return
NULL; return
&dir[index_in_dir(i)][index_in_seg(i)][index_in_block(i)]; }
index in block index in dir index in seg test() NULL DynArray + T
& touch(const size_t & i) { const size_t pos_in_dir =
index_in_dir(i); if (dir[pos_in_dir] == NULL)
allocate_segment(dir[pos_in_dir]); const size_t pos_in_seg =
index_in_seg(i); if (dir[pos_in_dir][pos_in_seg] == NULL)
allocate_block(dir[pos_in_dir][pos_in_seg]); if (i >=
current_dim) current_dim = i + 1; return
dir[pos_in_dir][pos_in_seg][index_in_block(i)]; } allocate block
allocate segment index in block index in dir index in seg DynArray
+ void reserve(const size_t & l, const size_t & r) { const
size_t first_seg = index_in_dir(l); const size_t last_seg =
index_in_dir(r); const size_t first_block = index_in_seg(l); const
size_t last_block = index_in_seg(r); for (size_t seg_idx =
first_seg; seg_idx = idx_last_seg; --idx_seg) // recorre
descendentemente los segmentos { if (dir[idx_seg] == NULL) // hay
un segmento? continue; // no ==> avance al siguiente }
current_dim = new_dim; // actualiza nueva dimensin o } index in dir
index in seg release all segments and blocks idx block idx seg idx
block idx first block idx seg == idx first seg idx block block size
1 idx seg != idx first seg
81. 56 Cap tulo 2. Secuencias // primer bloque a liberar int
idx_block = idx_seg == idx_first_seg ? idx_first_block : seg_size -
1; idx block idx last seg 0 (idx_seg > idx_last_seg and
idx_block >= 0) idx last block (idx_seg == idx_last_seg and
idx_block > idx_last_block) + // Libera descendentemente los
bloques reservados del segmento while ( or ) { if
(dir[idx_seg][idx_block] != NULL) // Hay un bloque aqu?
release_block(dir[idx_seg][idx_block]); --idx_block; } release
block if (idx_block < 0) release_segment(dir[idx_seg]); release
segment 2.1.5.4 Acceso mediante operador [] access() exist()
touch() reserve() [] DynArray
82. 2.1. Arreglos 57 Proxy DynArray + class Proxy { }; []
DynArray DynArray + Proxy operator [] (const size_t & i) {
return Proxy (const_cast&>(*this), i); } DynArray
std::length error std::bad alloc std::length error i i std::invalid
argument [] Proxy size_t index; size_t pos_in_dir; size_t
pos_in_seg; size_t pos_in_block; T **& ref_seg; T * block;
DynArray & array; DynArray index pos in dir pos in seg pos in
block index ref seg pos in dir ref seg[pos in seg] ref seg[pos in
seg][pos in block] index block
83. 58 Cap tulo 2. Secuencias ref seg[pos in seg][pos in block]
array DynArray Proxy(DynArray& _array, const size_t & i) :
index(i), pos_in_dir(_array.index_in_dir(index)),
pos_in_seg(_array.index_in_seg(index)),
pos_in_block(_array.index_in_block(index)),
ref_seg(_array.dir[pos_in_dir]), block (NULL), array(_array) { if
(ref_seg != NULL) block = ref_seg[pos_in_seg]; // ya existe un
bloque para la entrada i } DynArray index in block index in dir
index in seg i DynArrayarray DynArray ref seg block Proxy [] Proxy
T + operator T & () { return block[pos_in_block]; }block ==
NULL index std::invalid argument Proxy + Proxy & operator =
(const T & data) { block[pos_in_block] = data; return *this; }
Proxy & operator = (const Proxy & proxy) { if (proxy.block
== NULL) // operando derecho puede leer? throw
std::invalid_argument("right entry has not been still written");
block[pos_in_block] = proxy.block[proxy.pos_in_block]; return
*this; }
84. 2.1. Arreglos 59 T array[i] = variable array[i] = array[j]
if if (index >= array.current_dim) array.current_dim = index +
1; bool seg_was_allocated_in_current_call = false; if (ref_seg ==
NULL) // hay segmento? { // No ==> apartarlo!
array.allocate_segment(ref_seg); seg_was_allocated_in_current_call
= true; } allocate segment seg was allocated in current call + if
(block == NULL) // test if block is allocated {
array.allocate_block(block); ref_seg[pos_in_seg] = block; }
allocate block std::bad alloc new allocate segment() allocate
block() std::bad alloc new 2.1.5.5 Uso del valor por omisin o
DynArray
85. 60 Cap tulo 2. Secuencias i i i [] access() segmentation
fault i T::T() DynArray DynArray mat[n*n] (i,j) Matriz template
const T & Matriz::operator () (const long & i, const long
& j) const { const int & n = mat.size(); const long
index_dynarray = i + j*n; // posicin dentro de mat o if (not
mat.exist(index)) return Zero_Value; return mat.access(index); }
index dynarray not mat.exist(index) (i,j) Zero Value
mat.access(index) mat.access(index) not mat.exist(index) == true
T::T() set default initial value()
86. 2.2. Arreglos multidimensionales 61 set default initial
value() 2.2 Arreglos multidimensionales n m n m C++ T matriz[n][m];
[] matriz[i][j] = dato; dato j i = base + i m sizeof(T) + j
sizeof(T) n m n m C++ n m n m n m T ** matriz = new T * [n]; //
Aparta un arreglo de punteros a filas for (int i = 0; i < n;
++i) matriz[i] = new T [m]; // aparta la fila matriz[i] n matriz
matriz[i] C ++ n m m n
87. 62 Cap tulo 2. Secuencias C C++ 2.3 Iteradores Iterator
Set:template T:class Iterator +Set_Type +Item_Type +Iterator(in
ct:Set) +Iterator(in it:Iterator) +Iterator() +operator =(in
ct:Set) +operator =(in it:Iterator) +next(): void +prev(): void
+has_current(): bool +is_in_first(): bool +is_in_last(): bool
+current(): T +reset_first(): void +reset_last(): void +del(): void
+insert(in item:T): void +append(in item:T): void +set(in item:T):
void +position(): int Iterator Iterator Set T Set Set n T
88. 2.3. Iteradores 63 e0 e1 e2 ... ei ei+1 ... en2 en1 en Set
e0 en has current() false en true is in first() true is in last()
get current() Set std::overflow error next() prev() std::overflow
error std::underflow error ALEPH Iterator Iterator Set template
class Set, typename T, class Compare> T * search(Set & set,
const T & item) { for (typename Set::Iterator it(set);
it.has_current(); it.next()) if (are_equals() (it.get_current(),
item)) return &it.get_current(); return NULL; } reset first()
reset last() en1 del() next() del()
89. 64 Cap tulo 2. Secuencias insert() append() set() item item
position() Set [] Set Type Item Type Set Type Item Type get
current())2.4 Listas Enlazadas < t1, t2, t3, . . . , tn > n T
Restriccin de acceso: o t1 Ti i 1 < t1, t2, t3, . . . , ti1 >
Flexibilidad: ti < t1, t2, . . . , ti, ti+1, . . . , tn >
ti+1 < t1, t2, . . . , ti, . . . , tn > tj ti < t1, t2, .
. . , ti1, ti, tj, ti+1, . . . , tn >Espacio proporcional al
tamao: n f(n) = k n
90. 2.4. Listas Enlazadas 65 i (i 1) LISP ML CAML perl python
Pascal C C++ head A B C D E head C C++ struct Node { char data;
Node * next; }; data next Node next
91. 66 Cap tulo 2. Secuenciasfirst last A B C D E first A B C D
E 2.4.1 Listas enlazadas y el principio n a n ALEPH Slink
Dlink