Algoritmica

PROGRAMACIÓN E INGENIERÍA DE SOFTWARE

A. ALGORÍTMICA I. Representación y manipulación 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 superior de la pila y los apuntadores de cola dan lossitios 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 la notación P=^D para indicar que P es un puntero a datos detipo 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 que se expandan ose contraigan, según se les agregue oelimine 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

1. Taxonomía de las estructuras de datos

Lynn Jack Dave Dos apuntadores pueden referirse almismo 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 directamente con 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, en una línea recta y cada entradasigue 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 4 2 5 8 3 6 9 1 2 4 3

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

7

7

8

9

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

1

Este es el orden en que la mayoría de los compiladores almacenan un arreglorectangular, 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.............x xx xxx 0 xxx xxx 0 xxx xx x...............x x . x . x . 0 x . x x 0 xx xx xx 0 xx xMatriz 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 que todas las entradas que no están sobre la diagonal principal son ceros. Una matriz tridiagonal es una matriz cuadrada enla 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 parte, para almacenar una matriz antisimétrica, se procede de la misma forma almacenando solamente los elementos de la matriz...