Programación e ingeniería de software



Descargar 0,78 Mb.
Página1/12
Fecha de conversión15.03.2017
Tamaño0,78 Mb.
  1   2   3   4   5   6   7   8   9   ...   12

PROGRAMACIÓN E INGENIERÍA DE SOFTWARE

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 (R, E, RP)

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 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 la notació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 que se 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

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



Jack


Dave



NIL

Vectores, matrices, cubos, hipercubos (R, E, RP)


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 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.

Este es el orden en que 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 xx x...............x x

. x 0 xxx 0 x . xx 0

. x xxx x . xx

. x xxx x . xx

. x 0 xxx 0 x . 0 xx

xx.............x xx x 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 que todas 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| <= 1. La transpuesta de una matriz es la matriz obtenida al intercambiar sus renglones por columnas correspondientes. Es decir, que la matriz B sea la transpuesta de la matriz A significa que B[j,i] = A[i,j] para todos los índices (permitidos) i y j. Una matriz triangular superior es aquella en que todas las entradas bajo la diagonal principal son cero. La transpuesta de una matriz triangular inferior será una matriz triangular superior.
Matrices Simétricas y Antisimétricas

Una matriz A de n x n elementos es simétrica si A [i,j] es igual A[j,i], y esto se cumple para todo i y para todo j.


0 4 0 0


4 0 0 6

0 0 8 9 Matriz simétrica

0 6 9 0

una matriz A de n x n elementos es antisimétrica si A [i,j] es igual a –A [j,i], y esto se cumple para todo i y para todo j; considerando a i <> j.

0 4 0 0

-4 0 0 6



0 0 8 9 Matriz antisimétrica

0 -6 -9 0

para almacenar en un arreglo unidimensional una matriz simétrica, se puede hacer almacenando solamente los elementos de una matriz triangular inferior o superior; por ejemplo: almacenando la matriz triangular inferior .

A [1,1] A [2,1] A [2,2] A [3,1] A [3,2] A [3,3] A [4,1] A [4,2] A [4,3] A [4,4]




I >= 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 triangular inferior o superior.


A [1,1] A [1,2] A [1,3] A [1,4] A [2,2] A [2,3] A [2,4] A [3,3] A [3,4] A [4,4]


i >= j
1 2 3 4 5 6 7 8 9 10

Listas: simples, ligadas, doblemente ligadas, colas, pilas (stacks), colas de prioridades (R, E, RP)

Listas


Una lista es una colección de elementos llamados generalmente nodos. El orden entre los nodos se establece por medio de punteros, es decir, direcciones o referencias a otros nodos. Un nodo consta de dos partes:

  • Un campo información que será del tipo de datos que se quiera almacenar en una lista.

  • Un campo liga de tipo puntero que se utiliza para establecer la liga o el en lace con otro nodo de la lista.

Si el nodo fuera el ultimo de la lista este campo tendrá como valor: nil (vacío).


Al emplearse el campo liga para relacionar dos nodos no es necesario almacenar físicamente a los nodos en espacios contiguos.
Ejemplo de lista

P

García


Pérez


López

Santos

NIL

El primer nodo de la lista esta apuntado por una variable P, de tipo puntero (P almacena la dirección del primer nodo). El campo liga del ultimo nodo de la lista tiene un valor nil que indica que dicho nodo no apunta a ningún otro. Las operaciones que pueden llevarse acabo en una lista son:



  • Recorrido de la lista.

  • Inserción de un elemento.

  • Borrado de un elemento.

  • Búsqueda de un elemento.



Lista doblemente ligada


Una lista doblemente ligada es aquella en que cada nodo tiene dos ligas, una para el siguiente nodo de la lista y otra para el nodo precedente. De este modo es posible moverse en cualquier dirección atraves de la lista conservando solo un apuntador.


Lista doblemente ligada con apuntadores.



Colas


La cola se define como una lista en la que todas las adiciones a la lista se hacen a un extremo y todas las eliminaciones se efectúan en el otro extremo. Las colas se llaman también primero en entrar, primero en salir (first-in-first-out) o PEPS (FIFO). Al elemento en una cola lista para manejarse, es decir, el primer elemento que se removerá de la cola, lo llamamos cabeza de cola o frente de la cola, y el ultimo elemento, es decir al más reciente agregado, extremo o fondo de la cola. Las operaciones de una cola son:

  • Determinar si la cola esta vacía o no.

  • Recobrar el primer nodo de la cola, si no esta vacía.

  • Insertar un nuevo nodo después del ultimo nodo de la cola.

  • Eliminar el primer nodo de la cola, si no esta vacía.

Pilas


La pila se define como una lista en la que todas las inserciones y eliminaciones se hacen por un extremo, llamado tope de la pila. Cuando agregamos un elemento a la pila decimos que se le inserta “empujándolo” en la pila y cuando sacamos un elemento decimos que se le extrae de la pila. Otro nombre que se usa para en ocasiones para designar pilas es el de listas UEPS (LIFO),basado en la propiedad último en entrar primero en salir (last in, first out).


1


2

3

.



.

.

Tope



Maxpila es una constante que da el máximo tamaño permitido de la pila.
Type pila = record

Tope: 0 ....maxpila;

Entrada: array [ 1 . . .maxpila] of elemento

End;
Cuando queremos insertar un elemento en una pila llena ocurre un desbordamiento y cuando queremos extraer un elemento de una pila vacía es insuficiencia. Las operaciones de una pila son:



  • Determinar si la pila esta vacía o no.

  • Recobrar el ultimo nodo de la pila, si no esta vacía.

  • Insertar un nuevo nodo después del ultimo nodo de la pila.

  • Eliminar el ultimo nodo de la pila, si no esta vacía.



Colas de prioridad

Una cola de prioridad es una estructura de datos con solo dos operaciones:

  1. insertar un elemento.

  2. suprimir el elemento que tenga la llave más grande (o la más pequeña).

Si los elementos tienen llaves iguales, la regla habitual establece que el primer elemento introducido deberá ser el primero en eliminarse. Por ejemplo: en un sistema de computo de tiempo compartido, un extenso numero de tareas puede estar esperando para hacer uso de la CPU. Una de ellas tendrá mayor prioridad que otras. De ahí que el conjunto de las que esperan formen una cola de prioridad.

Arboles: binarios, n-arios (R, E, RP)

  1   2   3   4   5   6   7   8   9   ...   12


La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal