Libros de la guia egel

PROGRAMACIÓN E INGENIERÍA DE SOFTWARE

A. ALGORÍTMICA
I. Representación y manipulación de datos
1. Taxonomía de las estructuras de datos

• Apuntadores
Un apuntador (también llamado liga) se de fine como una variable que indica la localización de alguna otra variable;
por ejemplo: alguna sección de datos. Así, un apuntador de pila indica la localización del elemento en el tope superiorde la pila y los apuntadores de cola dan los sitios de la cabeza y el extremo de la cola.
Estructuras dinámicas de datos.
Este tipo de estructura es generado a partir de un tipo de dato conocido con el nombre de puntero o de referencia. Un
dato puntero almacena una dirección o referencia a un dato. Por tanto, debe distinguirse entre un dato puntero y el
dato al cual se apunta. Se usara lanotación P=^D para indicar que P es un puntero a datos de tipo D. Se genera un
valor para una variable de tipo puntero cuando se asigna dinámicamente, memoria a un dato apuntado por ella. La
principal ventaja de los punteros o apuntadores es que se puede adquirir posiciones de memoria que se necesitan, y
liberarlas cuando ya no se requieran. De esta manera se pueden crear estructuras dinámicas quese expandan ose
contraigan, según se les agregue o elimine elementos. El dinamismo de estas estructuras soluciona el problema de
decidir cual es la cantidad optima de memoria que debe reservarse para un problema dado. Al proceso que asigna y
reasigna la memoria en esta forma se le conoce como asignación dinámica de memoria.
Estructura con apuntadores Nil

Lynn
Jack
Dave

Dos apuntadorespueden referirse al mismo registro o
un apuntador no puede referirse a ningún registro.

NIL
• Vectores, matrices, cubos, hipercubos
Vectores o Arreglos
Un arreglo o vector contiene un numero constante de posiciones, es decir su tamaño se fija cuando el programa se
compila. Arreglo o vector el cual contiene un numero constante de posiciones. Los arreglos también se corresponden
directamentecon los vectores, termino matemático utilizado para las listas indexadas de objetos. Análogamente , los
arreglos bidimensionales se corresponden con las matrices.
Arreglos Rectangulares
Casi todos los lenguajes de alto nivel proporcionan medios convenientes y eficaces para almacenarlos y acceder a
ellos. El almacenamiento en la computadora se arregla en una secuencia contigua, es decir, enuna línea recta y cada
entrada sigue a la otra. La forma de leer un arreglo rectangular, es leer las entradas del primer renglón de izquierda a
derecha, después las entradas del segundo renglón así hasta terminar de leer el ultimo renglón.
1

2

3

4

5

6

7

8

9

1

2

3

4

5

[1,1] [1,2] [1,3]
6

7

8

9

[2,1] [2,2] [2,3] ...

1

Este es el orden enque la mayoría de los compiladores almacenan un arreglo rectangular, y se denomina
ordenamiento por renglón mayor.
Matrices
Arreglos Triangulares
Una matriz triangular inferior puede definirse formalmente como un arreglo cuadrado en el cual la entrada es 0 en
cada posición donde el índice de columna sea mas grande que el índice del renglón.
x
. x
0
.
x
.
x
.
x
xx.............xxx
xxx
0
xxx
xxx
0
xxx
xx

x...............x
x
.
x
.
x .
0
x .
x

x
xx

0
xx
xx
0
xx
x

Matriz Triangular Inferior
Matriz Tridiagonal
Matriz Triangular Superior
Matriz Diagonal
La diagonal principal de una matriz cuadrada se compone de las entradas para las cuales los índices de renglón y de
columna son iguales. Una matriz Diagonal es una matriz cuadrada en la quetodas las entradas que no están sobre la
diagonal principal son ceros. Una matriz tridiagonal es una matriz cuadrada en la que todas las entradas son cero
excepto posiblemente aquellas sobre la diagonal principal y sobre las diagonales inmediatamente arriba y debajo de
ella. Es decir, T es una matriz tridiagonal si T [ij] = 0 a menos que | i – j| = j

1 2
3
4
5
6
7
8 9 10
por otra...