martes, 12 de enero de 2010

UNIDAD II: ESTRUCTURAS LINEALES

2.1 ARREGLOS DEFINICION

Arreglo: Es un acomodo de espacios (Como en una matriz) en los cuales es una colección de un tipo de dato, y pueden ser unidimensionales, bidimesionales o multidimensionales

Es un conjunto finito y ordenado de elementos homogéneos (del mismo tipo de datos). Es un tipo de dato estructurado simple o estático y pueden ser vectores o tablas (matrices).

En lenguaje C, se pueden definir conjuntos de datos conocidos como arreglos. Por ejemplo, si deseáramos guardar en un arreglo, diez valores enteros, debemos definir este arreglo de la siguiente manera: int elem[10]; Esta expresión es la declaración del arreglo. Donde int es el tipo de datos que almacena el arreglo, elem es el nombre del arreglo, y el número encerrado en los corchetes es el número de valores que contiene el arreglo. Cabe hacer notar que, el índice para el primer elemento es 0 y, el valor máximo del índice es igual a n-1 elementos del arreglo. En nuestro caso, el último elemento del arreglo elem será elem[9]. El programador deberá tener cuidado de no indicar elementos inexistentes en el arreglo, es decir, elementos cuyos índices son números con signo menores a 0 o elementos con índices mayores a los n-1 elementos del arreglo. De no-tener cuidado, el compilador de C no marcará error alguno, pero se produce un error en tiempo de ejecución.

Un arreglo se puede entender mejor representándolo como en la figura 2.1

Figura 2.1. Representación de un arreglo lineal.

Un punto importante es que, el nombre del arreglo es, por si mismo, un apuntador a la localidad de memoria que ocupa el primer elemento, es decir, el nombre del arreglo es una variable que contiene la dirección del primer elemento. Esto se puede expresar como sigue:

elem = &elem[0]

A continuación se presenta un programa que emplea arreglos para mostrar una serie de números y la palabra “hola”.

int main(void)

{

int y; int numeros[4] = {2, 4, 6, 8}; char palabra[ ] = {’h’, ‘o’, ‘l’, ‘a’,’\0′}; for (y=0; y<4;>

printf (“números [%d] = %d\n”, y, números[y] ); printf(“\n”); for (y=0; y<4;>

printf (“%c”, palabra[y] ); return (0); } ¿ Cuál es el resultado de la ejecución del programa anterior? En el ejemplo, la forma de inicialización del arreglo números solo es soportada por el estándar ANSI.


2.1.2 ARREGLOS UNIDIMENSIONALES

Un arreglo unidimensional es un tipo de datos estructurado que está formado de una colección finita y ordenada de datos del mismo tipo. Es la estructura natural para modelar listas de elementos iguales.

El tipo de acceso a los arreglos unidimensionales es el acceso directo, es decir, podemos acceder a cualquier elemento del arreglo sin tener que consultar a elementos anteriores o posteriores, esto mediante el uso de un índice para cada elemento del arreglo que nos da su posición relativa.

Para implementar arreglos unidimensionales se debe reservar espacio en memoria, y se debe proporcionar la dirección base del arreglo, la cota superior y la inferior.

REPRESENTACION EN MEMORIA

Los arreglos se representan en memoria de la forma siguiente: 

                x : array[1..5] of integer

Para establecer el rango del arreglo (número total de elementos) que componen el arreglo se utiliza la siguiente formula: 

                RANGO = Ls - (Li+1)

donde:

ls = Límite superior del arreglo

li = Límite inferior del arreglo

Para calcular la dirección de memoria de un elemento dentro de un arreglo se usa la siguiente formula: 

                A[i] = base(A) + [(i-li) * w]

donde :

A = Identificador único del arreglo

i = Indice del elemento

li = Límite inferior

w = Número de bytes tipo componente

Si el arreglo en el cual estamos trabajando tiene un índice numerativo utilizaremos las siguientes fórmulas: 

                RANGO = ord (ls) - (ord (li)+1)



               A[i] = base (A) + [ord (i) - ord (li) * w]

1.3 Arreglos Bidimensionales

Este tipo de arreglos al igual que los anteriores es un tipo de dato estructurado, finito ordenado y homogéneo. El acceso a ellos también es en forma directa por medio de un par de índices.

Los arreglos bidimensionales se usan para representar datos que pueden verse como una tabla con filas y columnas. La primera dimensión del arreglo representa las columnas, cada elemento contiene un valor y cada dimensión representa una relación

La representación en memoria se realiza de dos formas : almacenamiento por columnas o por renglones.

Para determinar el número total de elementos en un arreglo bidimensional usaremos las siguientes fórmulas:

RANGO DE RENGLONES (R1) = Ls1 - (Li1+1)

RANGO DE COLUMNAS (R2) = Ls2 - (Li2+1)

No. TOTAL DE COMPONENTES = R1 * R2

REPRESENTACION EN MEMORIA POR COLUMNAS

x : array [1..5,1..7] of integer

Para calcular la dirección de memoria de un elemento se usan la siguiente formula:

A[i,j] = base (A) + [((j - li2) R1 + (i + li1))*w]

REPRESENTACION EN MEMORIA POR RENGLONES

x : array [1..5,1..7] of integer

Para calcular la dirección de memoria de un elemento se usan la siguiente formula:

A[i,j] = base (A) + [((i - li1) R2 + (j + li2))*w]

donde:

i = Indice del renglón a calcular

j = Indice de la columna a calcular

li1 = Límite inferior de renglones

li2 = Límite inferior de columnas

w = Número de bytes tipo componente

1.4 Arreglos Multidimensionales

Este también es un tipo de dato estructurado, que está compuesto por n dimensiones. Para hacer referencia a cada componente del arreglo es necesario utilizar n índices, uno para cada dimensión

Para determinar el número de elementos en este tipo de arreglos se usan las siguientes fórmulas:

RANGO (Ri) = lsi - (lii + 1)

No. TOTAL DE ELEMENTOS = R1 * R2* R3 * …* Rn

donde:

i = 1 … n

n = No. total de dimensiones

Para determinar la dirección de memoria se usa la siguiente formula:

LOC A[i1,i2,i3,…,in] = base(A) + [(i1-li1)*R3*R4*Rn + (i2-li2)*R3*R2*… (in - lin)*Rn]*w

1.5 Operaciones Con Arreglos

Las operaciones en arreglos pueden clasificarse de la siguiente forma:

Lectura

Escritura

Asignación

Actualización

Ordenación

Búsqueda

a) LECTURA

Este proceso consiste en leer un dato de un arreglo y asignar un valor a cada uno de sus componentes.

La lectura se realiza de la siguiente manera:

para i desde 1 hasta N haz

x←arreglo[i]

b) ESCRITURA

Consiste en asignarle un valor a cada elemento del arreglo.

La escritura se realiza de la siguiente manera:

para i desde 1 hasta N haz

arreglo[i]←x

c) ASIGNACION

No es posible asignar directamente un valor a todo el arreglo, por lo que se realiza de la manera siguiente:

para i desde 1 hasta N haz

arreglo[i]←algún_valor

d) ACTUALIZACION

Dentro de esta operación se encuentran las operaciones de eliminar, insertar y modificar datos. Para realizar este tipo de operaciones se debe tomar en cuenta si el arreglo está o no ordenado.

Para arreglos ordenados los algoritmos de inserción, borrado y modificación son los siguientes:

1.- Insertar.

Si i<>

2.- Borrar.

Si N>=1 entonces

inicio

i←1

encontrado←falso

mientras i<=n y encontrado=falso

inicio

si arreglo[i]=valor_a_borrar entonces

inicio

encontrado←verdadero

N←N-1

para k desde i hasta N haz

arreglo[k]←arreglo[k-1]

fin

en caso contrario

i←i+1

fin

fin

Si encontrado=falso entonces

mensaje (valor no encontrado)

3.- Modificar.

Si N>=1 entonces

inicio

i←1

encontrado←falso

mientras i<=N y encontrado=false haz

inicio

Si arreglo[i]=valor entonces

arreglo[i]←valor_nuevo

encontrado←verdadero

En caso contrario

i←i+1

fin

fin


2.1.3 ARREGLOS BIDIMENCIONALES


LA APLICACION DE LOS ARREGLOS BIDIMENSIONALES SON DE GRAN UTILIDAD PARA PODER TRABAJAR CON MATRICES Y VECTORES UN EJEMPLO MUY CLARO DE ESTO ES:

int matriz[3][3]; 

    for(f=0;f<3;f++)

 {

  suma=0;

 for(c=0;c<3;c++)

   {

    suma=suma+matriz[c][f];

   }

 vectf[f]=suma;

 }

Bueno aqui les dejo un ejemplo de una clase de arreglos bidimensionales, con otra clase llamada Teclado ;) espero que le entiendan les puse muchas especificaciones:) //esta clase va hacer que imprima desde el teclado,, nombre alumno, calificaciones y promedio final, es una lista de 3 alumnos ;) suerte:) import java.io.*; public class Pava 

 {

	public static void main(String[]args)

	 {

Teclado leeDato=new Teclado();//Mandas traer la clase Teclado

int suma=0;//declaracion ‘suma’ es el k sakara el promedio String alumno[]=new String[3];//declaras el arreglo en donde le indicas que es de tipo ‘String’ es decir aceptara caracteres, el ‘3′ es el tamaño de nuestro arreglo int cali[][]=new int[3][4];//Calificaciones tipo entero(creo k es obvio no) el tamaño tambien es asigando aki double prom[]=new double[3];//arreglo donde se mostrara el promedio de alumnos, por lo k debe ser igual de tamaño a ‘alumno’ y ‘cali’ en este caso es 3 or(int i=0;i<3;i++)> 

 	 	  {

	 	  	System.out.println(“N Ombre? de alumno (a) (“+(i+1)+”)=“);

	 	  	alumno[i]=leeDato.getCadena();

	 	  	 for(int j=0;j<4;j++)

	 	  	  {

	 	  	  	 System.out.println(“Calificacion del alumno(a) (“+(j+1)+”)=“);

	 	  	  	 cali[i][j]=leeDato.getEntero();

	 	  	  }

	 	  }



	 	  for(int i=0;i<3;i++)

	 	   {

	 	   	for(int j=0;j<4;j++)

	 	   	 {

	 	   	 	suma+=cali[i][j];

	  	   	 }



	  	   	 prom[i]=suma/(double)4.0;

	  	   	 suma=0;

	 	   }





	 	   System.out.println(“Alumn@ \t\t\t Calificacion \t\t\t Promedio”);

	 	    for(int i=0;i<3;i++)

	 	     {

	 	     	System.out.print(alumno[i]+”\t\t”);

	 	     	 for(int j=0;j<3;j++)

	 	     	  {

	 	     	  	System.out.print(cali[i][j]+”\t”);



	 	     	  }

	 	     	  System.out.print(“ “);

	 	     	  System.out.println(prom[i]);

	 	     }

	 		 }

}

public class Arreglos { 

	public static void main(String []args)

	{

		int suma=0;

		float prom[]=new float [6];

		String alumno[]= new String [6];

		int cal[][]=new int [6][4]



		for(int i=0;i<6;i++)

			{

			 System.out.println(“Nombre del alumno”+(i+1);

			 alumno[i]=lee.cadena;

			 for(int j=0;j<4;j++)

				{

				 System.out.println(“Calificacion #”+(j+i);

				 cal[i][j]=lee.entero;

				}

			}





		for(int i=0;i<6;i++)

		{

			for(int j=0;j<4;j++)

			{

				suma+=cal[i][j];

			}



			prom[i]=suma/(float)4.0;

				suma=0;

		}



		System.out.println(“Alumn@      Calificacion        Promedio”);

		System.out.println();



		for(int i=0;i<6;i++)

		{

			System.out.print(alumno[i]+\t\t);

			for(int j=0;j<4;j++)

			{

				System.out.print(cal[i][j]+” “\t\t);

			}

			System.out.print(“        “);

			System.out.println(prom[i]);

		}

	}

}


2.1.4 ARREGLOS MULTIDIMENSIONALES

Este también es un tipo de dato estructurado, que está compuesto por n dimensiones. Para hacer referencia a cada componente del arreglo es necesario utilizar n índices, uno para cada dimensión

Para determinar el número de elementos en este tipo de arreglos se usan las siguientes fórmulas:

RANGO (Ri) = lsi - (lii + 1)

No. TOTAL DE ELEMENTOS = R1 * R2* R3 * …* Rn

donde:

i = 1 … n

n = No. total de dimensiones

Para determinar la dirección de memoria se usa la siguiente formula:

LOC A[i1,i2,i3,…,in] = base(A) + [(i1-li1)*R3*R4*Rn + (i2-li2)*R3*R2*… (in - lin)*Rn]*w

2.1.5 RESOLUCION DE PROBLEMAS CON ARREGLOS


2.1.6 CLASES PARA IMPLEMENTACION DE ARREGLOS


2.2 PILAS DEFINICION

Las pilas son otro tipo de estructura de datos lineales, las cuales presentan restricciones en cuanto a la posición en la cual pueden realizarse las inserciones y las extracciones de elementos.

Una pila es una lista de elementos en la que se pueden insertar y eliminar elementos sólo por uno de los extremos. Como consecuencia, los elementos de una pila serán eliminados en orden inverso al que se insertaron. Es decir, el último elemento que se metió a la pila será el primero en salir de ella.

En la vida cotidiana existen muchos ejemplos de pilas, una pila de platos en una alacena, una pila de latas en un supermercado, una pila de papeles sobre un escritorio, etc.

Debido al orden en que se insertan y eliminan los elementos en una pila, también se le conoce como estructura LIFO (Last In, First Out: último en entrar, primero en salir).

2.2.2 OPERACION CON PILAS

Una Pila se compone de los siguientes elementos:

arreglo de datos

El numero maximo

El numero minimo

El tipo de datos de la pila

los indices Tope y Base de la Pila

Operaciones Elementales

Iniciar

Insertar

Eliminar

Axiomas

Insertar:

Si Tope = Maximo 

     Mensaje( O Verflow)

de lo Contrario

Tope = Tope +1

Pila Tope = Valor

//Codigo Fuente PILAS

  1. include
  2. include
  3. include

int pila[5],cima=−1,maxpila=4,c=0,op,x,i,n; char r=‘n’;

void meter(int *pila,int *cima,int maxpila,int item) { 

	if(*cima==maxpila)

		{cout<<”\nDesbordamiento”<<”\n”;}

	else

	      {*cima=*cima+1;

	       pila[*cima]=item;}

}

void sacar(int *pila,int *cima,int *item) { if(*cima==0) 

		{cout<<”\nSubdesbordamiento”;}

	else

	      {*item=pila[*cima];

	       *cima=*cima-1;}

}

int main() {clrscr(); 

	do

	{clrscr();

	 cout<<”\n1.-Insertar”;

	 cout<<”\n2.-Eliminar”;

	 cout<<”\n3.-SALIR”;

	 cout«”\nInserta una opcion “;cin»op;



		switch(op)

		{case 1:

		cout«”¨Cuantos datos deseas insertar? “;cin»n;

		if(n>5)

		{cout<<”\nMemoria insuficiente”;

		getch();}

		else

		{for(i=0;i		{cout«”\nIntroduce un numero “;cin»x;

		c=c+1;

		cout<<”\nDatos insertados “<		clrscr();

		meter(pila,&cima,maxpila,x);}

		getch();}

		break;

		case 2:

		sacar(pila,&cima,& x);

		cout<<”\nEl dato borrado fue “<		getch();

		break;

		case 3:

		cout«”DESEA SALIR (S/N) “;cin»r;

		break;

		default:

		cout<<”Ingresa numero valido\n”;

		getch();

		break;

	}while(r==‘n’ || r==‘N’);

return 0; }

2.2.3 CLASES PARA IMPLEMENTACION DE PILAS

Ejemplo completo sobre la implementación de pilas manejando Visual Studio .net 2003

//----LIO

  1. include “stdafx.h”
  2. using

using namespace System;

using namespace System::Collections;

public __gc class Ejemplo Stack?{

public: 

    static void Imprime(I Enumerable? __gc *Mi Coleccion?)







	{







       System::Collections::I Enumerator? __gc *Mi Enumerador?

= Mi Coleccion→Get Enumerator?(); 

        while (Mi Enumerador→Move Next?())







           Console::Write(S”\t{0}”, Mi Enumerador→Current);







       Console::Write Line?();



   }

};

int main() { 

    Stack __gc *Mi Pila? = new Stack();







   Mi Pila→Push(S”Hola”);







   Mi Pila→Push(S”Mundo”);







   Mi Pila→Push(S”!”);







   // Despliega las propiedades y valores de los pila.







   Console::Write Line(S”Mi Pila”);







   Console::Write Line(S”\tCount:    {0}”,

__box(Mi Pila→Count)); 

    Console::Write(S”\tValores:”);







	Ejemplo Stack::Imprime(Mi Pila);







	system(“pause”);







	return 0;

}


2.3 COLAS DEFINICION

Una cola es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pop por el otro. También se le llama estructura FIFO (del inglés First In First Out), debido a que el primer elemento en entrar será también el primero en salir.

El tipo cola representa la idea que tenemos de cola en la vida real. La cola para subir al autobús está compuesta de elementos (personas), que dispone de dos extremos comienzo y fin. Por el comienzo se extraerá un elemento cuando haya comprado el billete para su viaje, y si llega una nueva persona con intención de usar el autobús, tendrá que colocarse al final y esperar que todos los elementos situados antes que él abandonen la cola.


2.3.2 TIPOS

2.3.2.1 COLAS SIMPLES

En las colas el elemento que entro en primer lugar también es el primero en salir por ello se conocen como listas FIFO (First in - First out).

Así pues la diferencia con las pilas recibe en el modo de entrada y salida de datos. En las colas las inserciones se realizan al final de la lista no al principio por ello las colas se usan para almacenar datos que necesiten ser procesados según el orden de llegada.

Nodo I M F

En la informática muchas aplicaciones para las colas (colas de aplicación) etc. . Por ejemplo un sistema de tiempo compartido suele tener un procesador central y una serie de periféricos compartidos: discos, impresoras, etc.

Los recursos se comparten con diferentes usuarios y se utiliza una cola para almacenar el programa por los diferentes usuarios que esperan su turno de ejecución. El procesador atiende por riguroso orden de llamado de usuario.

2.3.2.2 COLAS CIRCULARES

  • Colas circulares (anillos): en las que el último elemento y el primero están unidos.
  • Colas de prioridad: En ellas, los elementos se atienden en el orden indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se atenderán de modo convencional según la posición que ocupen. Hay 2 formas de implementación:
  1. Añadir un campo a cada nodo con su prioridad. Resulta conveniente mantener la cola ordenada por orden de prioridad.
  2. Crear tantas colas como prioridades haya, y almacenar cada elemento en su cola.
  • Bicolas: son colas en donde los nodos se pueden añadir y quitar por ambos extremos; se les llama DEQUE (Double Ended QUEue). Para representar las bicolas lo podemos hacer con un array circular con Inicio y Fin que apunten a cada uno de los extremos. Hay variantes:
  • Bicolas de entrada restringida: Son aquellas donde la inserción sólo se hace por el final, aunque podemos eliminar al inicio ó al final.
  • Bicolas de salida restringida: Son aquellas donde sólo se elimina por el final, aunque se puede insertar al inicio y al final.

2.3.2.3 COLAS DOBLES

Existe una variable de la cola simple que es la bicola (doble cola). Es una cola bidimensional en la que las inscripciones y eliminaciones se pueden realizar en cualquiera de los dos extremos de la cola.

Inserción Eliminación

Inicio



Final

Eliminación Inserción

Existen dos variantes de la bicola (cola doble):

Cola doble con entrada restringida: Acepta valor, inserciones solo al final de la columna.

Cola doble con salida restringida: Acepta eliminaciones solo al inicio de la cola.

Indica Memoria Dinámica

Crear I I=NULL

Crear M M=NULL

Crear F F=NULL

Mientras si (Quiere dar de alta)

Si I=Null Entonces

Crear Nodo I

I sig=NULL

M=I

F=I

Si no

Crear nodo F

Fsig =M

M=F

2.3.3 OPERACIONES CON COLAS

La definición de la estructura de datos tipo cola queda completa al incluir las operaciones que se pueden realizar en ella. Las operaciones básicas que pueden efectuarse son:

Insertar un elemento en la cola

Eliminar un elemento de la cola

Las inserciones se llevaran a cabo por el FINAL de la cola, mientras que las eliminaciones se harán por el FRENTE —recuerde que el primero en entrar es el primero en salir.

Considerando que una cola puede almacenar un máximo número de elementos y que además FRENTE indica la posición del primer elemento y FINAL la posición del último, se presentan a continuación los algoritmos correspondientes a las operaciones mencionadas.

2.3.4 CLASES PARA IMPLEMENTACION DE COLAS

Mediante Vectores

Esta realización se caracteriza por :

Es sencilla e intuitiva, ya que se basa en un vector.

fin apunta al último dato.

ini apunta a la posición anterior a la que contiene al primer dato.

Declaración del tipo de dato

unit cola1;

interface;

const

Maxcola = 100; {tamaño del vector}

nulo = 0;

type

tDato = integer ;

tPos = nulo..Maxcola ;

tCola = record

Datos : array [1..Maxcola] of tDato ;

ini,fin : tPos ;

end ;

Al añadir los elementos vamos incrementando fin , y al borrarlos decrementamos ini .

Para evitar que el índice final se salga del vector podemos usar un vector circular mediante una

función que dada una posición, devuelva la siguiente :

function Siguiente (p : integer):integer;

begin

Siguiente:=p mod MaxEl+1 { Esto equivale a: if p=MaxEl then p:=1 else inc (i)}

end ;

En las colas circulares debe prestarse atención a que los índices no se crucen.
Publicado por en

No hay comentarios:

Publicar un comentario

Suscribirse a: Enviar comentarios (Atom)