Tejiendo Algoritmos - Leandro Rabindranath León
Preview:
DESCRIPTION
Libro escrito por el profesor de la Universidad de Los Andes, Leandro Rabindranath Leon
Citation preview
- 1. Tejiendo algoritmos lrleon@ula.ve
- 2. xfractint
- 3.
- 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 lrleon@ula.ve 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
- 61. 36 Cap tulo 2. Secuencias delete [] array; delete []
dmalloc valgrind 2.1.3 Arreglos de bits bool C++ true false bool
C++ bool 0 1 7 512 4 5121024 = 131072 4 128 131072 2 131072 = 32768
= 32 ; 8 BitArray class BitArray { BitArray BitArray }; BitArray
BitArray BitArray mutable size_t num_bits; mutable size_t
num_bytes;
- 62. 2.1. Arreglos 37 num bits num bytes array of bytes num
bytes BitArray + Byte * array_of_bytes; BitArray::Byte struct Byte
{ unsigned int b0 : 1; unsigned int b1 : 1; unsigned int b2 : 1;
unsigned int b3 : 1; unsigned int b4 : 1; unsigned int b5 : 1;
unsigned int b6 : 1; unsigned int b7 : 1; }; BitArray::Byte 8
unsigned int read_bit(const unsigned int & i) const { switch
(i) { case 0 : return b0; case 1 : return b1; // ... case 7 :
return b7; } } i void write_bit(const unsigned int & i, const
unsigned int & value) { switch (i) { case 0 : b0 = value;
break; case 1 : b1 = value; break; C++
- 63. 38 Cap tulo 2. Secuencias // ... case 7 : b7 = value;
break; } } i value Byte Byte() : b0(0), b1(0), b2(0), b3(0), b4(0),
b5(0), b6(0), b7(0) { /* empty */ } Byte BitArray BitArray
BitArray(const size_t & dim = 256) : num_bits(dim),
num_bytes(num_bits/8 + (((num_bits % 8) != 0) ? 1 : 0)),
array_of_bytes (new Byte [num_bytes]) { /* empty */ } ~BitArray() {
delete [] array_of_bytes; } BitArray BitArray + const size_t &
size() const { return get_len(); } [] i byte index array of bytes i
byte index = . 8 bit index bit index = i 8 . i = array[40]; 40 []
40 int [] read bit() array[40] = i; 40 i 40 i [] write bit() []
[]
- 64. 2.1. Arreglos 39 [] BitArray + class BitProxy { }; BitProxy
[] BitArray BitProxy BitArray + BitProxy operator [] (const size_t
& i) const { return BitProxy(const_cast(*this), i); } BitProxy
operator [] (const size_t & i) { return BitProxy(*this, i); }
BitArray BitProxy BitArray const BitArray BitProxy array of bytes
const size_t bit_index; Byte * byte_ptr; BitProxy BitProxy(BitArray
& array, const size_t & i) : bit_index(i % 8) { const
size_t byte_index = i/8; byte_ptr =
&array.array_of_bytes[byte_index]; } BitArray BitProxy BitProxy
[] BitArray byte ptr array of bytes bit index *byte ptr i std::out
of range() BitProxy byte ptr bit index []
- 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 ),
- 75. 50 Cap tulo 2. Secuencias seg_plus_block_pow ( pow_seg +
pow_block ), mask_seg_plus_block ( two_raised(seg_plus_block_pow) -
1 ), dir_size ( two_raised(pow_dir) ), seg_size (
two_raised(pow_seg) ), block_size ( two_raised(pow_block) ),
max_dim ( two_raised(seg_plus_block_pow + pow_dir) ), mask_seg (
seg_size - 1 ), mask_block ( block_size - 1 ), current_dim ( 0 ),
num_segs ( 0 ), num_blocks ( 0 ), default_initial_value_ptr (NULL)
{ allocate_dir(); } allocate dir DynArray 2 DynArray 12 4096
24+26+212 = 222 = 4194304 Max Bits Allowed = 32 32 22 1 Max Bits
Allowed Max Pow Block = 32 Default Pow Dir Default Pow Seg 1 = 21
2Default Pow Dir 2Default Pow Seg 221 = 24 26 221 = 536870912 ,
Default Pow Block pow block Max Pow Block pow_block
(std::min(std::max(next2Pow(dim/8), Default_Pow_Block),
Max_Pow_Block) ),
- 76. 2.1. Arreglos 51 Default Pow Block Max Pow Block DynArray
template const size_t DynArray::Default_Pow_Dir = 4; /* 16 */
template const size_t DynArray::Default_Pow_Seg = 6; /* 64 */
template const size_t DynArray::Default_Pow_Block = 12; /* 4096 */
template const size_t DynArray::Max_Bits_Allowed = 8 *
sizeof(size_t); template const size_t DynArray::Max_Dim_Allowed =
2*1024*1024*1024ul; template const size_t DynArray::Max_Pow_Block =
(Max_Bits_Allowed - Default_Pow_Dir - Default_Pow_Seg - 1);
DynArray next2Pow DynArray + static size_t next2Pow(const size_t
& number) { return
static_cast(ceil(log(static_cast(number))/log(2.0))); } copy
array() DynArray + void copy_array(const DynArray & src_array)
{ for (int i = 0; i < src_array.current_dim; ++i) if
(src_array.exist(i)) (*this)[i] = src_array.access(i); } DynArray
copy array() src array.exist(i) true i src array src
array.access(i) i src array src array.exist(i) (*this)[i] = ...
copy array() advance block index() len DynArray + size_t
divide_by_block_size(const size_t & number) const { return
number >> pow_block; }
- 77. 52 Cap tulo 2. Secuencias size_t
modulus_by_block_size(const size_t & number) const { return
number & mask_block; } void advance_block_index(size_t &
block_index, size_t & seg_index, const size_t & len) const
{ if (block_index + len < block_size) { block_index += len;
return; } seg_index += divide_by_block_size(len); block_index =
modulus_by_block_size(len); } DynArray + void allocate_dir(T ***
src_dir) { allocate_dir(); for (int i = 0; i < dir_size; i++) if
(src_dir[i] != NULL) allocate_segment(dir[i], src_dir[i]); }
allocate dir allocate segment allocate seg() allocate block(seg[i],
src seg[i]) allocate dir() copy array exactly() DynArray + void
copy_array_exactly(const DynArray & array) { release_dir(); //
liberar toda la memoria de this pow_dir = array.pow_dir; pow_seg =
array.fpow_seg; pow_block = array.pow_block; seg_plus_block_pow =
array.seg_plus_block_pow; mask_seg_plus_block =
array.mask_seg_plus_block; dir_size = array.dir_size; seg_size =
array.seg_size; block_size = array.block_size; max_dim =
array.max_dim;
- 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