PARTE II:
- �Cu�l es la diferencia entre memoria principal y memoria cach�?___________________________________________________________________________________________________________________________________________________________________________________________________________________
- 8 bytes es equivalente a:________ bits
- �Qu�s es un registro?:_____________________________________________________________________________________________________________________________
- �Para que nos sirven los puneteros?:___________________________________________________________________________________________________________________________
- �cu�l es la diferencia entre desreferenciaci�n e indirecci�n?__________________________________________________________________________________________________________________________
- Dise�e un programa en C, que lea un arreglo de 20, lea los valores,
luego los imprime y muestre la suma de sus elementos, usando notaci�n
de punteros - Dise�e un programa, que imprima, las direcciones de memoria de
los elementos de una arreglo de 5X5, elementos - Se desea conocer el n�mero de elementos de una cadena de caracteres,
ingresada por el usuario. (NOTA: el final de una cadena es representada
por un elemento nulo ��. Utilice aritm�tica de punteros para determinar
este valor) - Escriba un programa en C, que le permita al usuario, ingresar una cadena
de caracteres (no mayor a 100 elementos) y luego, la imprima, en forma inversa,
usando para ello, notaci�n de punteros. - Un programa en C, contiene la siguiente declaraci�n:
- es mcd(n,m) si m<n
- es mcd(n, residuo de m/n), en caso contrario
- la relaci�n, tiempo-espacio de la memoria, para una llamada recursiva
es mayor que para una iterativa, por eso, se debe hacer uso de la recursi�n
s�lo cuando, una soluci�n iterativa no sea posible. - si son posibles las dos soluciones (iterativa y recursiva), entonces es
mejor hacer uso de la soluci�n iterativa, puesto que una llamada
recursiva consume mayor tiempo y espacio en memoria. - hay por el contrario, muchos problemas que se resuelven exclusivamente
con recursi�n, ya que son demasiado extensos y complejos, por tanto
una soluci�n recursiva, presentar� una imagen m�s fiable,
comprensible y elegante. - los movimientos deben ser de uno en uno (es decir, no se pueden mover
dos o tres donas al mismo tiempo) - en una varilla, no puede quedar una dona peque�a, bajo una grande.
- �Qu� aspectos, son los que debo tomar en cuenta, cuando tengo que
decidir entre iteraci�n o recursi�n?_________________________________________________________________________________________________________________________________________________________________________________________________________________ - �Cu�ndo se produce una recursi�n infinita?_______________________________________________________________________________________________________________________________
- �Para que sirven los casos base?�y los casos generales?______________________________________________________________________________________________________________________________________________________________________________________________
- �En que consiste la t�cnica "divide y vencer�s"?______________________________________________________________________________________________________________________________________________________________________________________________
- Dise�e un programa que sume los primeros n m�ltiplos de
tres, en forma recursiva - Dise�e un funci�n (o programa completo) que, dado un vector,
determine el producto de todos sus elementos en forma recursiva. - el valor de e (una expresi�n matem�tica, puede representarse
de la siguiente manera: e=1/1!+1/2!+…+1/n!. Dise�e una funci�n
(o programa) que muestre el resultado recursivo de �sta sucesi�n. - Dado un vector, escriba un programa que busque un elemento ingresado por
el usuario, en el vector y con un mensaje en pantalla, indique si ese valor
se encuentra o no. - Escribir un programa, que comntenga una funci�n recursiva, para
calcular la funci�n de Ackermann, definida de la siguiente forma: - El combinatorio de dos n�meros, est� definido, por la expresi�n
siguiente: C(m, n)=m!/(n!x(m-n)!), escribir un programa en C, que calcule
el combinatorio, donde n! Es el factorial de n. - Dados dos vectores de enteros e igual tama�o, calcular la suma
de los productos de sus elementos: C=S (AiXBi). - Escriba un programa que transforme cualquier n�emro base 10, a
otra base b, que puede ser de 8 a 16, utilizar para ello recursividad. - Dise�e un programa que muetre cual es el valor mayor contenido
en un vector unidimensional. - Se tiene un conjunto de pesos p1, p2, p3…pn. y se desea estudiar, como
objetivo si existe una selecci�n de dichos objetos que totalicen
exactamente un peso v, dado. Por ejemplo, si el objetivo es V=12y los pesos
son: 4, 3, 6, 2, 1; se pueden elegir el primero, el tercero y el cuarto,
ya que: 4+6+2=12. El algotimo para solucionar este problema tiene como tarea
b�sica a�adir un nuevo peso , probar si con ese peso se logra
el objetivo o se avanza en el sentido de alcanzar la soluci�n. - listar las variables inmediantamente despu�s de cerrar la llave
de la estructura - Listar las variables que serp�n del tipo estructura creadas, inmeditamente
despu�s del identificador de la estructura; en la zona de declaraciones
del programa. - El operador punto (.)
- El operador puntero �flecha- (->)
MEMORIA DIN�MICA
Cap�tulo VII: Memoria Principal y Aritm�tica
de Punteros
Al iniciar �sta segunda parte, vamos a comentar algunos
aspectos que son de suma importancia y que el lector debe conocer y manejar,
como lo es el uso y funcionamiento de la memoria, dentro de la computadora.
Debemos iniciar diciendo que, La Memoria Principal; se
compone de un conjunto de celdas b�sicas dotadas de una determinada
organizaci�n.
Ya que, la Memoria, es el lugar donde se guardan datos
y programas.
Tipos de Memoria
La Memoria RAM
Es aquella memoria que �se volatiliza� al apagar el equipo.
A mayor cantidad de RAM, m�s ventanas se pueden abrir, m�s programas
funcionando simult�neamente y menos bloqueos de la PC. Existen
varios tipos de RAM, seg�n su forma de encapsulado.
M�DULOS DIP (Dual Inline Package): eran chips
de memoria de forma rectangular y chata. Presentaban dos l�neas
de pines en sus laterales. Una muesca o punto sobre el chip indicaban
cu�l es la pata n� 1 para evitar colocar el chip al rev�s en
el z�calo de la mother. Hoy no se utilizan memorias RAM en formato
DIP, pero s� todav�a como cach� en motherboards
u otras tarjetas.
M�DULOS SIP (Single Inline Package): se trataba
de m�dulos de memoria RAM cuyos chips de memoria se encontraban soldados
sobre una peque�a placa de circuito impreso que hac�a contacto
con la motherboard con una sola hilera de pines soldados en uno de
sus bordes. Los pines calzaban en un z�calo colocado en la mother.
M�DULOS SIMM (Single Inline Memory Module):
son m�dulos de memoria que tambi�n tienen una sola hilera de
pines. Una peque�a placa de circuito tiene soldada en una o ambas caras
varios chips de memoria. Estos m�dulos de memoria se presentan en dos
versiones. Existen:
-SIMM de 30 pines: organizan la cantidad total de
memoria en renglones de a 8 bits. (Mother 486)
-SIMM de 72 pines: organizan la cantidad total de
memoria en renglones de a 32 bits. (Mother 486 o Pentium)
M�DULOS DIMM (Double Inline Memory Module):
similares a los SIMM, aunque poseen 168 pines y organizan la memoria
en renglones de a 64 bits. Hay m�dulos DIMM de 168 pines para
16, 32, 64, 128, 256 y hasta 512 MBytes. (Mother Pentium o Pentium II en adelante).
M�DULOS DDR (Double Data Rate Synchronous DRAM):
esta tecnolog�a transmite al doble de la velocidad del bus del sistema. Estas
memorias se presentan en forma de m�dulos de 184 contactos o pines.
Z�calos y Bancos
Un banco es un conjunto de z�calos para insertar
chips individuales (como los DIP, o SIP), o m�dulos de memoria RAM
(SIMM de 30, SIMM de 72 o DIMM de 128 pines).
Una motherboard posee m�s de un banco de memoria
para agregar m�s memoria a la m�quina sin tener que retirar
la que estaba instalada. Cada banco de memoria puede poseer 1, 2 �
4 z�calos.
Un banco organiza la cantidad total de memoria en
renglones sucesivos seg�n el ancho del bus de datos del microprocesador.
Por ejemplo, en un Intel 486 (bus de datos de 32 bits), para colocar memorias
en los bancos deben respetarse las siguientes reglas:
1.- Un banco de memoria debe tener en todos sus z�calos la misma cantidad
de m�dulos.
2.- Debe llenarse primero el banco 0, luego el banco 1, y
as� sucesivamente (excepto si la motherboard posee autobanking).
3.- Un banco debe tener m�dulos de la misma velocidad.
No se puede colocar una memoria SIMM de 60 nanosegundos junto con otra de
distinta velocidad.
Memoria Cach�
Estas memorias son de tipo est�ticas. Son muy
veloces (10 ns) y tambi�n caras, ya que su proceso de fabricaci�n
es mucho m�s complejo. Con una memoria cach� el micro
lee una direcci�n de memoria y mientras procesa la informaci�n
el cach� lee las restantes posiciones de memoria principal consecutivas.
Cuando el micro necesite leer la pr�xima direcci�n de memoria,
su contenido se encontrar� en cach�. De esta manera, se acelera
mucho la velocidad de procesamiento.
Una declaraci�n de variable como:
int var;
produce una asociaci�n entre el nombre 'var' y un espacio
de almacenamiento en memoria. Por lo tanto hay dos elementos relacionados
con el nombre 'var': un valor que se puede almacenar alli y una direcci�n
de memoria para la variable, algunos autores se refieren a estos dos aspectos
como el "rvalue" y "lvalue" de la variable.
Adem�s del identificador "var", tenemos la palabra "int" que nos indica
el TIPO (type) de la variable. El tipo nos indica:
1-CUANTAS CELDAS DE MEMORIA (bytes) se asocian a ese nombre de variable.
2-DE QUE MODO SERAN INTERPRETADOS los datos que se encuentren en tal
localidad de memoria,
1-Un byte es la menor unidad de informaci�n que pueden direccional
la mayor�a de las computadoras. En la mayor�a de las arquitecturas
el tipo char ocupa un solo byte, por lo tanto es la unidad m�nima.
Un bool admite solo dos valores diferentes, pero es almacenado como
un byte. El tipo integer ocupa generalmente 2 bytes, un long
4, double 8, y asi con el resto de los tipos.
2-El otro punto es la relaci�n entre LO QUE HAY en una celda de memoria
y COMO ES INTERPRETADO. Lo que hay en un celda cuya extensi�n es un
byte es simplemente un conjunto de ocho estados posibles (8 bits) que a nivel
hardware admiten dos estados diferenciales, estados que pueden ser interpretados
como 'verdadero / falso', 0/1, o cualquier otro par de valores. Una celda
de memoria del sector de datos, podr�a contener algo como lo siguiente:
Que es esto? Depende en gran parte del TIPO (type) que hayamos asociado a
esa celda (y suponiendo que exista tal asociaci�n). Ese valor
interpretado como un Hexadecimal es 0x61, en decimal es 97, y si fue asociada
al tipo char representara la letra 'a', cuyo ASCII es igual a 97. En
ninguna localidad de memoria hay algo como la letra 'a', lo que encontramos
son valores binarios que en caso de estar asociados a char y en caso
de que lo saquemos en pantalla como char hara que veamos encendidos
ciertos pixeles de pantalla, en los cuales reconoceremos una representaci�n
de la letra 'a'.
La representaci�n binaria de datos ocupa demasiado espacio, por ese
motivo es preferible utilizar el sistema Hexadecimal, ademas de ser muy f�cil
de traducir a binario es mas econ�mico que este o el decimal. Observar
los bytes de un sector de memoria de un programa facilita la comprensi�n
sobre el modo en que cada tipo (type) se asocia a direcciones de memoria.
Supongamos un programa que declara, define e inicializa las siguientes variables:
Algunos Conceptos Importantes
BIT: Acr�nimo
del ingl�s "Binary Digit", o "D�gito Binario" es decir, cada
uno de los 0 (ceros) o 1 (unos) que utiliza el sistema de numeraci�n
en base 2. Esta es la forma en la que ordenador procesa toda la informaci�n.
Byte: Tambi�n llamado "octeto", es el conjunto
de 8 bit (ceros y unos) que se necesitan para codificar un car�cter,
al ser un valor muy peque�o, se utilizan sus m�ltiplos: kilobyte,
megabyte, gigabyte…
Palabra: Unidad direccionable formadas por bits. Desde
8 bits (1 byte) hasta 64 bits (8 bytes).
ASCII: Siglas de "American Standard Code for Informati�n
Interchange", o c�digo est�ndar americano para el intercambio
de informaci�n. El conjunto b�sico de caracteres ASCII comprende
s�lo las letras (del alfabeto ingl�s) y carece de acentos, de
letras no inglesas (como la �) y de formatos (negrita, cursiva…),
pero existen conjuntos de caracteres m�s amplios.
Unicode: Han Ampliado a 16 bits, que se usan. Se puede
representar todos los s�mbolos de los lenguajes de programaci�n.
BCD: (Binary Code Decimal) se utilizan s�lo
4 bits para representar las letras, los d�gitos y otros s�mbolos.
Estos grupos de 4 bits se llaman nibble.
Ejemplo:
0=0000
2=0010
9=1001
Apuntadores
Una de las cosas m�s dif�ciles que encuentran
los principiantes en C es entender el concepto de
apuntadores. Me he encontrado a menudo que la principal raz�n
por la que los principiantes tienen problemas con los apuntadores es que tienen
una muy pobre o m�nima concepci�n de las variables, (del modo
en que C hace uso de ellas). As� que comencemos con una discusi�n
sobre las variables de C en general. Una variable en un programa es algo con
un nombre, que contiene un valor que puede variar. El modo en que el compilador
y el enlazador (linker) manejan esto es que asignan un bloque espec�fico
de la memoria dentro de la computadora para guardar el valor de una variable.
El tama�o de este bloque depende del rango en que a
esta variable le es permitido variar. Por ejemplo, en PC�s
de 32 bits, el tama�o de una variable de tipo entero (int) es de 4
bytes, en una m�quina antigua de 16 bits los enteros tienen un tama�o
de 2 bytes. En C el tama�o de un tipo de variable como una de tipo
entero no tiene porqu� ser el mismo en todos los tipos de m�quinas.
Es m�s en C disponemos de diferentes tipos de variables enteras, est�n
los enteros largos (long int) y los enteros cortos (short int) sobre los que
puedes averiguar en cualquier texto b�sico sobre C. El presente documento
asume que se est� usando un sistema de 32 bits con enteros de 4 bytes.
Recordemos, el tama�o de los tipo de datos usados
en el lenguaje C:
| TABLA CON LOS TIPOS DE DATOS PREDEFINIDOS EN C | |||
| >ENTEROS: numeros completos y sus negativos | |||
| Palabra reservada: | Ejemplo | Tama�o (byte) | Rango de valores |
| Int | -850 | 2 | -32767 a 32767 |
| VARIANTES DE ENTEROS | |||
| short int | -10 | 1 | -128 a 127 |
| unsigned int | 45689 | 2 | 0 a 65535 |
| long int | 588458 | 4 | -2147483648 a 2147483647 |
| unsigned long | 20000 | 4 | 0 a 4294967295 |
| >REALES: n�meros con decimales o punto flotante | |||
| Palabra reservada: | Ejemplo | Tama�o (byte) | Rango de valores |
| Float | 85 | 4 | 3.4×10-38 a 3.4×1038 |
| VARIANTES DE LOS REALES | |||
| Double | 0.0058 | 8 | 1.7×10-308 a 1.7×10308 |
| long double | 1.00E-07 | 10 | 3.4×10-4932 a 1.1×104932 |
| >CAR�CTER: letras, digitos, s�mbolos, | |||
| Palabra reservada: | Ejemplo | Tama�o (byte) | Rango de valores |
| Char | 'O' | 1 | 0 ……255 |
Como ya se ha dicho, cuando hacemos una declaratoria, como
int a;
Le estamos indicando a la computadora la cantidad de almacenamiento
(tama�o, que para el caso es de 2 bytes), adem�s indica c�mo
se va a interpretar los datos guardados en ese lugar de la memoria (en nuestro
caso, enteros).
Y es a qui donde radica la importancia, de lo punteros, por
que como ya se dijo, los Punteros o Apuntadores, son variables que
contienen la direcci�n de otra variable.
En forma gr�fica, la podemos representarlo, como se
muestra en la figura de arriba. P, es apuntador hacia el entero identificado
como "a", en el cual, se reservan dos bytes, para guardar el entero.
3B, es la direcci�n de la variable. (NOTA: "3B", es s�lo
por decir un dato, para que el lector tenga la idea de una direcci�n
de memoria).
Cabe mencionar que, un puntero, es una variable q termina
con la direcci�n con la que comienza la variable a la que apunta:
Los usos principales, que tienen, los punteros, son los siguientes:
->Nos ayuda, para que una funci�n devuelva m�s
de un valor. Por ejemplo, una funci�n que devuelva un vector de enteros,
en dicha funci�n mandamos la direcci�n del primer elemento a
la funci�n principal, y a partir de ella, imprimimos todos los valores
contenidos en el vector.
->Mejor uso de la memoria din�mica. Esto es lo
que m�s nos tiene cuenta, el lector debe tener presente que, el uso
de punteros, ayuda a ahorrar memoria y por consiguiente, hace m�s efectivo
el uso y administraci�n de la misma.
La forma de declarar un apuntador, es la siguiente:
Int *p;
Int->indica que, es un puntero hacia un entero.
*->indica al compilador que esa variable, es un puntero
p-> Es el identificador del puntero.
Otros ejemplos:
float *q; /*apuntador hacia un flotante*/
char *z; /*puntero que contiene la direcci�n de una
variable que guarda un car�cter */
Para referirnos a un valor a trav�s de un apuntador,
lo hacemos mediante un proceso llamado indirecci�n.
Por ejemplo, para mandar a impresi�n el valor entero,
hacia el cual a punta "p", ser�a as�:
printf("%d", *p);
Los punteros, pueden ser inicializados a 0, NULL �
alguna direcci�n v�lida:
float *p1;
p1=0;
p1=NULL;
Ahora bien, para guardar la direcci�n de alguna variable,
en un puntero, debemos conocer un nuevo amigo:
&->Operador de Direcci�n.
P1=&a;
Con esa simple declaraci�n, estamos indic�ndole
al compilador que p1, contendr� le direcci�n de memoria de a.
Veamos algunos ejemplos:
Ejemplo 7.1
Dise�e un programa que muestre el uso de operadores
b�sicos en la declaraci�n de punteros empleando el direccionamiento
y el operador indirecci�n.
#include <stdio.h>
#include <conio.h>
main()
{
int a;
/*Declaraci�n de un puntero a un entero */
int *p;
clrscr();
printf("Ingrese un valor ENTERO para la variable:n");
scanf("%d", &a);
while(a<0)
{
printf("ERROR, el valor debe ser mayor que cero:n");
scanf("%d", &a);
}
clrscr();
/*Limpiamos la pantalla */
printf("a=%dn", a); /*Imprimo el valor de a*/
printf("La direcci�n de a es %pn", &a);
printf("*p=%pn", p); /*Imprimo la direcci�n que guarda
p*/
/*imprimo el valor guardado en la direccion a la que apunta
p*/
printf("a=%dn", *p);
printf("El tama�o de *p es %dn", sizeof(p));
getch();
return 0;
}
Explicaci�n:
Como ya se ha explicado, la forma de declaraci�n de
un puntero consiste en colocar al tipo de dato al cual apunta, el operador
asterisco (*), seguido del identificador del mismo. Debo hacer notar que,
para mandar a impresi�n una direcci�n de memoria, debo hacerlo
usando la expresi�n "%p", para lo cual es indistinto si mando
directamente la direcci�n de memoria, haciendo uso del operador &
(ejemplo: &a), o si le mando, a impresi�n el contenido de la variable
apuntador. (ejemplo: "*p=%pn", p).
La funci�n sizeof como su nombre lo indica,
se utiliza para determinar el tama�o (en bytes) de alguna variable
en espec�fico.
Ejemplo 7.2
Dise�e un programa, que sume dos variables de tipo
entero, por medio de apuntadores.
#include <stdio.h>
#include <conio.h>
main()
{
int a, b, c;
int *p1, *p2, *p3; /*declaracion de los punteros */
printf("Ingrese el valor de a:n");
scanf("%d", &a);
printf("Ahora el valor de b:n");
scanf("%d", &b);
c=a+b;
printf("a+b=%dn", c);
/*asiganamos las direcciones a los punteros correspondientes/
p1=&a;
p2=&b;
/*ahora desreferenciamos el valor de los punteros para sumarlos
*/
printf("*p1 + *p2=%dn", *p1+*p2);
p3=&c;
printf(" Direcci�n de a es %pn Direccion de b es %pn Y
la de c es %pnn", p1, p2, p3);
getch();
return 0;
}
con esta instrucci�n: *p1+*p2, estamos invocando
el valor guardado en la direcci�n a la que apunta p1 y p2, por tanto
se obtiene el mismo resultado, que si sum�ramos directamente las dos
variable (a+b).
Ejemplo 7.3
Programa que, asigna valores a punteros y juega un poco con
las direcciones y las desrefenciaciones.
#include <stdio.h>
#include <conio.h>
main()
{
int a, b,c, *p1, *p2;
void* p; /*puntero que apunta a void*/
p1=&a;/*guarda la direcci�n de a*/
*p1=1; /* a donde apunta p1, guarda el valor de uno */
p2=&b;
*p2=2;
p1=p2; /*En p1, guarda la direccion a la que apunta p2*/
*p1=0;
p2=&c;
*p2=3;/*a donde apunta p2, le asigno 3*/
printf("a =%dn b =%dn c =%dnn", a,b,c);
p=&p1; /*p contiene la direccion de p1*/
p=p2;
*p1=1;/*es como asignarle a C, el valor de 1*/
/*con los cambios realizados imprimimos el nuevo
valor de las variables */
printf("a =%dn b =%dn c =%dnn", a,b,c);
getch();
return 0;
}
La salida que presenta este c�digo, es la siguiente:
Punteros y Arreglos
Si mat es un arreglo unidimensional, la direcci�n
del primer elemento puede ser expresada tanto como &mat[0] o simplemente
como mat.
La direcci�n del elemento (i+1) se puede expresar
como (mat+i), donde mat, representa la rireci�n del arreglo e "i",
la posici�n espec�fica a la cual nos referimos.
Si &mat[i] y (mat +i) representan la direcci�n
del i-�simo elemento de mat, mat[i] y *(mat+i), representa el contenido
de esa direcci�n.
Por ejemplo, supongamos que tenemos el siguiente arreglo:
Int mat[]={2, 16, -4, 29, 234, 12, 0, 3}
Tenemos un arreglo de 8 posiciones, de las cuales ya hemos
aprendido que, para referirnos a cada uno de esos valores, lo podemos hacer
usando sub�ndices. As�:
Mat[0]=2;
Mat[1]=16;
…
pero podemos acceder a ellos de un modo alternativo, usando
punteros de la siguiente manera:
int *ptr;
ptr=&mat[0];
y de esa manera, podemos imprimir los valores de nuestro
arreglo, ya sea usando la notaci�n de arreglos o desreferenciando nuestro
puntero.
Ejemplo 7.4
Utilice un puntero para imprimir los valores de un puntero
de 6 posiciones.
#include <stdio.h>
#include <conio.h>
main()
{
int mat[]={2,3,5,9,10,4};/*declaracion del arreglo*/
int i;
int *ptr;
ptr=&mat[0];/*al puntero ptr, le asignamos la direccion
del primer
elemento del arreglo*/
clrscr();
printf("tttElementos del arreglo:nnn");
for(i=0; i<6; i++)
{
printf("mat[%d]=%dn", i, mat[i]); /*notacion de arreglos*/
printf("ptr+%d=%dn", i, *(ptr+i));/*notacion de punteros*/
}
getch();
return 0;
}
ahora, supongamos que, lo que tenemos es un arreglo multidimensional,
entonces, podemos acceder a el mediante la siguiente sintaxis:
multi[renglon][columna]
�
*(*(multi + renglon) + columna)
Para entender mejor lo que sucede, reemplacemos *(multi +
renglon) con una X, tal que la expresi�n nos quede como *(X
+ columna) Ahora vemos que esta X es como un apuntador ya que la expresi�n
se encuentra desreferenciada y sabemos que col es un entero. Aqu� la
aritm�tica a utilizar es de un tipo especial llamada "aritm�tica
de punteros". Eso
significa que, ya que hablamos de un arreglo de enteros,
la direcci�n a ser apuntada por (el valor de) X + columna + 1 debe
ser mayor que la direcci�n de X + columna por una cantidad que
es igual a sizeof(int) (el
tama�o del tipo de dato entero). Ya que sabemos la
estructura de memoria para arreglos bidimensionales, podemos determinar que
en la
expresi�n multi + renglon como se hizo arriba,
multi + renglon + 1 hace que esto se incremente por un valor igual
al necesario para "apuntar a" el siguiente rengl�n, lo cual
ser�a entonces COLUMNAS * sizeof (int).
Esto nos dice que si la expresi�n *(*(multi + renglones)
+ columnas) va a ser evaluada correctamente en tiempo de ejecuci�n,
el compilador debe generar c�digo que tome en consideraci�n
el valor de COLUMNAS, es decir, la segunda dimensi�n. Debido
a la equivalencia entre las dos formas de expresi�n, esto se hace cierto
ya sea que usemos la sintaxis de punteros o la de arreglos multi[renglon][columna].
As� que para evaluar cualquiera de estas dos expresiones,
se deben conocer 5 valores:
1. La direcci�n del primer elemento del arreglo, la
cual es conocida por la expresi�n multi, es decir, el
nombre del arreglo.
2. El tama�o y el tipo de los elementos que conforman
el arreglo, en este caso sizeof(int).
3. La segunda dimensi�n del arreglo.
4. El valor espec�fico del �ndice para la primera
dimensi�n, renglon en este caso.
5. El valor espec�fico del �ndice para la segunda
dimensi�n, columna en este caso.
Una vez que conocemos esto, consideremos el problema de dise�ar
una funci�n que manipula los elementos de un arreglo previamente declarado.
Por ejemplo, uno que establecer�a un valor de 1 todos los elementos
del
arreglo multi.
void set_value(int m_arreglo[][COLUMNAS])
{
int renglon, columna;
for (renglon = 0; renglon < RENGLONES; renglon++)
{
for (columna = 0; columna < COLUMNAS; columna++)
{
m_arreglo[renglon][columna] = 1;
}
}
}
Y para llamar a esta funci�n usar�amos entonces:
set_value(multi);
Dentro de esta funci�n, hemos usado los valores establecidos
por #define en RENGLONES y COLUMNAS, los
cuales establecen los l�mites para los ciclos. Pero
dentro de lo que le concierne al compilador, estas son
simples constantes, es decir, no hay nada que les relacione
directamente con el tama�o del arreglo dentro de la
funci�n. renglon y columna son variables
locales, por supuesto. La definici�n formal del par�metro le
permite
al compilador determinar las caracter�sticas del valor
del puntero que ser� pasado en tiempo de ejecuci�n.
Realmente no necesitamos la primera dimensi�n y, como
veremos m�s adelante, habr� ocasiones en las que
preferiremos no declararla en la definici�n de los
par�metros de una funci�n, no quiere decir que eso se vuelva
un h�bito o algo con lo que haya que ser consistente. Pero la segunda
dimensi�n debe ser usada como se ha mostrado en la expresi�n
del par�metro. La raz�n por la que la necesitamos es por la
forma de la evaluaci�n de m_arreglo[renglon][columna]. Mientras
que el par�metro define el tipo de datos (int en este caso) y las variables
autom�ticas para rengl�n y
columna son definidas en los ciclos for, s�lo un valor
puede ser pasado usando un �nico par�metro. En este caso, es
el valor de multi, como lo pasamos en la llamada a la funci�n,
es decir, la direcci�n de su primer
elemento, m�s bien referido como un apuntador al arreglo.
As� que la �nica manera que tenemos de informar al compilador
de la segunda dimensi�n es incluirlo expl�citamente en la definici�n
del par�metro de la funci�n. De hecho y por lo general todas
las dimensiones de orden mayor que uno, necesitan de arreglos multidimensionales.
Esto significa que si hablamos de arreglos de 3 dimensiones, la segunda y
tercera dimensiones deben estar especificadas en la definici�n del
par�metro.
Ejemplo 7.5
/*Programa que lee un arreglo y una matriz usando
aritm�tica de punteros */
#include <stdio.h>
#include <conio.h>
#define M 3
#define N 3
main()
{
int x[3][3], y[3];
int f=0,c=0;
clrscr();
for(f=0; f< M; f++)
{
for(c=0; c<N; c++)
{
printf("*(x+ %d)+%d)=", f,c);
scanf("%d", *(x+f)+c);
}
printf("Elemento %d del vector:n", f);
scanf("%d", &y[f]);
}
printf("IMPRESIONES:n");
printf("*** MATRIZ ***n");
for(f=0; f<M; f++)
for(c=0; c<N; c++)
printf("%d", *(*(x+f)+c));
printf("n*** VECTOR ***n");
for(f=0; f<M; f++)
printf("%d", *(y+f));
getch();
return 0;
}
Ejemplo 7.6
Uso de funciones
#include <stdio.h>
#include <conio.h>
void generacion(int a[3][3], int b[3][3]);
main()
{
int a[3][3]={1,2,3,4,5,6,7,8,9}; /*generamos dos matrices de igual tama�o*/
int b[3][3]={1,2,3,4,5,6,7,8,9};
int f,c;
printf("LAS MATRICES GENERADAS SON:nn");
printf("Matriz a:n");
for(f=0; f<3; f++)
{
for(c=0; c<3; c++)
printf("%d", a[f][c]);
printf("n");
}
printf("Matriz b:n");
for(f=0; f<3; f++)
{
for(c=0; c<3; c++)
printf("%d", b[f][c]);
printf("n");
}
generacion(a,b); /*la funci�n recibe como par�metros, las
dos matrices*/
getch();
return 0;
}
void generacion (int a[3][3], int b[3][3])
{
int d[3][3],f,c;
for(f=0; f<3; f++)
for(c=0; c<3; c++)
d[f][c]=a[f][c]*b[f][c];
for(f=0; f<3; f++)
for(c=0; c<3; c++)
printf("Valor de la Fila %d y columna %d = %d n", f,c,*(*(d+f)+c));
}
Ejemplo 7.7
Programa que dado un vector de enteros, aumenta en una unidad el valor de
los miembros del arreglo y env�a la direcci�n del primer elemento
como retorno a la funci�n principal. (Note, como hacer para devolver
m�s de un valor)
#include <stdio.h>
#include <conio.h>
/*funcion que devuelve una direcion de memoria*/
int *valores (int a[]);
main()
{
int a[]={2, 5, 9, 7, 10};
int *p, i;
clrscr();
printf("Los valores del puntero, aumentado en uno, son:n");
p=valores(a);
for(i=0; i<5; i++)
printf("* %d *", *(p+i));
getch();
return 0;
}
int *valores (int a[])
{
int i, *p;
for(i=0; i<5; i++)
a[i]=a[i]+1;
p=&a[0];
return (p);
}
Cuestionario
Ejercicios:
Char *mat[5]={"Yo", "Tu", "El", "Nosotros",
"Ellos"};
a)�Cu�l es el significado de mat?_________________________________
b)�Qu� significa (mat+2)?_________________________________________
c)�Qu� significa *(mat+2)?_________________________________________
Cap�tulo VIII: Recursi�n
La recursi�n, o recursividad, es una propiedad que
tienen algunas funciones de llamarse a s� mismas. Lo cual es una alternativa,
ante la iteraci�n.
El uso de funciones recursivas, ayudan a que �l programador
ahorre (en la mayor�a de los casos) muchas l�neas de c�digo.
Todos los ejemplos que se han presentado hasta ahora, est�n
bajo la l�nea de programaci�n estructurada, por tanto son soluciones
correctas. Sin embargo, como programadores, en muchas ocasiones nos
podemos enfrentar a la necesidad de utilizar funciones que se llamen a s�
mismas. En muchos libros, cursos o seminarios de programaci�n, se hace
mucho �nfasis a �ste t�pico, y por supuesto, no dejar�amos
pasar la oportunidad de hablar de ello y darle el lugar que se merece.
En forma gr�fica, una funci�n recursiva, ser�a
m�s o menos as�:
Funcion1(…)
{
…
funcion1(…);
…
}
en �ste cap�tulo, trataremos de darle mayor
prioridad a los ejemplos, es por ello, que, iniciaremos con el ejemplo m�s
emblem�tico de una funci�n recursiva, como es el caso del factorial.
Ejemplo 8.1
Realice una funci�n recursiva que muestre el factorial
de un n�mero ingresado por el usuario.
Un n�mero factorial, se define como:
n!=nx(n-1)X(n-2)x….x1
lo cual puede representarse as�:
0!=1
1!=1
2!=2X1
3!=3x2x1
y la forma recursiva para ello ser�a:
2!=2×1!
3!=3×2!
…
n!=nx(n-1)!
#include <stdio.h>
#include <conio.h>
int factorial (int n); /*declaraci�n de la funci�n*/
main()
{
int n, r;
printf("Ingrese el Valor del factorial que desea Calcular:n");
scanf("%d", &n);
while(n<0)
{
printf("Ingrese el Valor del factorial que desea Calcular:n");
scanf("%d", &n);
}
r=factorial(n); /*llamado de la funci�n*/
printf("El valor de %d!= %dn", n, r);
getch();
return 0;
}
int factorial (int n)
{
int r;
if(n==0)/*CASO BASE: al resultar cierta se sale de la recursi�n*/
r=1;
else
r=n*factorial(n-1); /*llamado recursivo de la funci�n
*/
return r;
}
Explicaci�n:
El programa, lo que hace, es mandarle el par�metro
a la funci�n factorial (supongamos que n=2). Entonces pregunta si n=0,
al evaluar, resulta falsa, por tanto nos vamos por el lado del else, y asigna
a r el valor de 3, por la llamada recursiva de n-1, (es decir 2. r=2*factorial(1)).
Y vuelve a evaluar la condici�n, resulta falsa y vuelve a llamar la
funci�n (r=1*factorial(0)). Por tanto, al evaluar la condici�n
esta vez, resultar� cierta, y le asigna el valor de 1, el cual lo retorna
a la llamada anterio (r=1*1), este resultado, lo devuelve a la llamada que
se hizo antes de �sta (r=2*1). Y este resultado, se devuelve a la llamada
anterior. �sta es la que se hizo en la funci�n original, y luego
se imprime ese valor
Antes de continuar, debemos hacer hincapi� en algo
muy importante, como lo es: la forma en la cual, dejar�amos de ejecutar
las llamadas iterativas, ya que debe existir alguna condici�n que,
al resultar cierta, ya no haga m�s llamadas recursivas y por el contrario,
empiece a retornar los valores de la funci�n. A esto se le llama Caso
Base.
Un Caso Base, son los casos del problema que se resuelven
sin recursi�n, para nuestro primer ejemplo es 0, por que el factorial
de cero, est� definido como 1 (uno).
Si el problema es lo suficientemente complejo, debemos hacer
uso de Los casos generales, que son definidos como la soluci�n
de uno o m�s problemas o un conjunto de pasos adicionales. Sin embargo,
debemos tener en cuenta que, los casos generales, deben avanzar hacia un caso
base, de lo contrario tendremos una recursi�n infinita.
Ejemplo 8.2
Realice una funci�n recursiva que calcule la suma
de dos enteros.
Soluci�n:
Si tenemos por ejemplo a+b, la suma ser�a "a",
siempre y cuando "b" sea cero, de lo contrario, recursivamente,
ser�a: 1+suma(a, b-1).
#include <stdio.h>
#include <conio.h>
int suma (int a, int b);
main()
{
int a, b, r;
clrscr();
printf("Ingrese el primer sumando:n");
scanf("%d", &a);
printf("Ingrese el segundo sumando:n");
scanf("%d", &b);
r=suma(a,b);
printf("%d + %d = %dn", a, b,r);
getch();
return 0;
}
int suma (int a, int b)
{
int r;
if(b==0)/*caso base*/
r=a;
else
r=1+suma(a, b-1);/*llamada recursiva, disminuimos b, para
que en un
return r;} momento dado, sea igual a cero*/
Ejemplo 8.3
Dise�e un programa que multiplique, dos valores enteros, recursivamente.
Sabemos muy bien que, a*b, es igual a sumar a+a+a+a+a+……b veces.
Pero si b=1, entonces, el producto es igual a "a".
#include <stdio.h>
#include <conio.h>
int multi (int a, int b);
main()
{
int a, b, r;
clrscr();
printf("Ingrese el valor del multiplicando:n");
scanf("%d", &a);
printf("Ahora el multiplicador:n");
scanf("%d", &b);
r=multi(a, b);
printf("%d * %d= %d", a, b, r);
getch();
return 0;
}
int multi (int a, int b)
{
int r;
if(b==1)/*elemento neutro de la multiplicaci�n, que es nuestro caso
base*/
r=a;
else
r=a+multi(a, b-1);/*llamada recursiva de la funci�n, disminuimos
b, para que llegue un momento en el que sea igual a 1, y le sumamos a, por
que as� est� definida la multiplicaci�n, como la suma
de "a", b veces*/
return r;
}
Ejemplo 8.4
Calcule, recursivamente la expresi�n: Xn
#include <stdio.h>
#include <conio.h>
int exp (int base, int p);
main()
{
int base, p, r;
clrscr();
printf("Ingrese la Base:n");
scanf("%d", &base);
printf("Exponente es:n");
scanf("%d", &p);
r=exp(base, p);
printf("%d^%d=%dnn", base, p, r);
getch();
return 0;
}
int exp (int base, int p)
{
int r;
if(p==0)
r=1;
else
r=base*exp(base, p-1);
return r;
}
Ejemplo 8.5
Obtenga, recursivamente el M�ximo Com�n Divisor,
mcd(m,n), de dos n�meros, sabiendo que:
-es n si n<m y n divide a m
#include <stdio.h>
#include <conio.h>
int mcd (int m, int n);
main()
{
int r, m, n;
clrscr();
printf("PROGRAMA QUE CALCULA EL M.C.D.n");
printf("Ingrese un N�mero:n");
scanf("%d", &m);
printf("El otro es:n");
scanf("%d", &n);
r=mcd(m,n);
printf("el mcd de %d y %d es %dn", m,n, r);
getch();
return 0;
}
int mcd (int m, int n)
{
int r;
if(n<=m && m%n==0)
r=n;
else
if(m<n)
r=mcd(m,n);
else
r=mcd(n, m%n);
return r;
}
Ejemplo 8.6:
Programa que calcula la secuencia de Fubonacci, recursivamente:
#include <stdio.h>
#include <conio.h>
int fubonacci (int n);
main()
{
int n, r;
printf("PROGRAMA QUE IMPRIME LA SECUENCIA DE FOBONACCIn");
printf("Ingrese el valor de n:n");
scanf("%d", &n);
printf("** %d **", r);
getch();
return 0;
}
int fobonacci (int n)
{
int r;
if(n==0 || n==1)
r=n;
else
r=fobonacci(n-1)+fobonacci(n-2);
return r;
}
Ejemplo 8.7:
/*Programa que calcula la suma de los primeros
n numeros enteros, positivos */
#include <stdio.h>
#include <conio.h>
int func (int n);
main()
{
int n, r;
clrscr();
printf("A partir de cero… �Hasta que n�emro desea sumar?n");
scanf("%d", &n);
r=func(n);
printf("La suma de los primeros %n numeros eneteros es:
%dn", n, r);
getch();
return 0;
}
int func (int n)
{
int r;
if(n==0)
r=0;
else
r=n+func(n-1);
return r;
}
Este programa, lo que hace es sumar desde cero, hasta el
n, n�mero entero.
Ejemplo 8.8:
Programa que calcula, la suma de los primeros n elementos
de un vector:
#include <stdio.h>
#include <conio.h>
int sumav(int v[], int n);
main()
{
int n, r, v[]={1,2,3,4,5,6,7,8,9};
clrscr();
printf("Ingrese el valor hasta el cual dsea sumar:n");
scanf("%d", &n);
while(n<0 || n>9)
{
printf("Error, numero no v lido vuelva a intertarlo:n");
scanf("%d", &n);
}
r=sumav(v, n);
printf("El valor de la suma es %dn", r);
getch();
return 0;
}
int sumav(int v[], int n)
{
int r;
if(n==0)
r=v[0];
else
r=v[n]+sumav(v, n-1);
return r;
}
Ejemplo 8. 9:
#include <stdio.h>
#include <conio.h>
/*programa que lee e imprime un arreglo de enteros
y despues hace una busqueda lineal recursiva de ciertos
valores digitados por el usuario */
int busquedalineal(int *V, int n, int b);
void main()
{
int arreglo[12];
int pos, i, num, bus, buscar=1;
pos=0;
printf("Digite 12 valores para guardarlos en el arreglo:n");
for(i=0; i<12; i++)
{
printf("Digite el elemento de la posici�n %d del vector:n",
i+1);
scanf("%d", &arreglo[i]);
}
printf("Los elementos del vector son:n");
for(i=0; i<12; i++)
{
printf("%d", arreglo[i]);
}
printf("n");
while(buscar)
{
printf("Digite un n�mero a buscar:");
scanf("%d", &num);
pos=busquedalineal(arreglo, 11, num);
if(pos)
printf("El numero %d se encuentra en el arreglon", num);
else
printf("El numero %d NO se encuentra en el arreglon",
num);
printf("�Desea Buscar otro numero? (S/N)n");
bus=getch();
if(bus=='s' || bus=='S')
buscar=1;
else
buscar=0;
}//fin del while
getch();
}//fin del main
/*Funci�n REcursiva de Busqueda Lineal */
int busquedalineal(int *V, int n, int b)
{
if(n==0)
return (V[0]==b);
else
if(V[n]==b)
return 1;
else
return busquedalineal (V, n-1, b);
}
Ejemplo 8.10:
/* Pograma que dado un vector de enteros
calcule:
1. el elemento maximo del arreglo
2. el elemento minimo del arreglo
3. la suma de los elementos del arreglo
4. el producto de los elementos del arreglo
5. el promedio de los elementos del arreglo */
#include <stdio.h>
#include <conio.h>
#define N 10
int max (int a[], int n);
int min (int a[], int n);
int sum (int a[], int n);
int multi (int a[], int n);
int prom (int a[], int n);
main()
{
int a[N], i=0, r, op, n=10, ban=1;
clrscr();
printf("ttBIENVENIDO (A)nn");
printf("Ingrese los valores del vector:n");
for(i=0; i<N; i++)
{
printf("Ingrese el elemento %d del arreglo:n", i);
scanf("%d", &a[i]);
}
clrscr();
printf("Los valores del arreglo son:n");
for(i=0; i<N; i++)
printf("** %d **", a[i]);
getch();
while(ban==1)
{
clrscr();
printf("*****************************************n");
printf("** �Que desea hacer? **n");
printf("** 1. El maximo elemento **n");
printf("** 2. El minimo elemento **n");
printf("** 3. La suma de sus elementos **n");
printf("** 4. Su producto **n");
printf("** 5. Su promedio **n");
printf("** 6. Sair **n");
printf("*****************************************n");
scanf("%d", &op);
switch(op)
{
case 1: clrscr();
r= max(a, n);
printf("el maximo elemto del vector es %dn", r);
break;
case 2: clrscr();
r=min(a, n);
printf("El elemnto minimo es %dn", r);
break;
case 3: clrscr();
r= sum(a, n);
printf("La suma de los elementos del vector es: %d n",
r);
break;
case 4: clrscr();
r=multi (a, n);
printf("Al multiplicar todos los elementos del vector
resulta %d n", r);
break;
case 5: clrscr();
r=prom(a, n);
printf("El promedio de los valores son: %d n", r);
break;
case 6: return 0;
default:
printf("ERROR, comando no valido!!n");
}
printf("�Desea Seguir? (1/2)n");
scanf("%d", &ban);
}
getch();
return 0;
}
int max (int a[], int n)
{
int r, aux;
if(n==0)
r=a[0];
else
{
aux=max(a, n-1);
if(a[n]>aux)
r=a[n];
else
r=aux;
}
return r;
}
int min (int a[], int n)
{
int r, aux;
if(n==0)
r=a[0];
else
{
aux=min(a, n-1);
if(a[n]<aux)
r=a[n];
else
r=aux;
}
return r;
}
int sum (int a[], int n)
{
int r;
if(n==0)
r=0;
else
r=a[n-1]+sum(a, n-1);
return r;
}
int multi (int a[], int n)
{
int r;
if(n==0)
r=1;
else
r=a[n-1] * multi(a, n-1);
return r;
}
int prom (int a[], int n)
{
int r;
r=sum(a, n)/N;
return r;
}
Hasta el momento, hemos visto algunos ejemplo del uso de
la recursi�n, pero hay que tener en cuenta, algunos aspectos importantes,
para decidir entre recursi�n o iteraci�n:
Recursi�n Infinita
Cuando habl�bamos de los ciclos (bucles), dec�amos
que, dentro del ciclo debe existir algo que modifique la condici�n,
para que, en un momento dado, se pueda salir del ciclo. Lo mismo pasa con
la iteraci�n.
Una Recursi�n Infita, implica que cada llamada
recursiva produce otra, y �sta a su vez produce otra llamada, y �ta
tambi�n produce otra llamada, y as� sucesivamente para SIEMPRE,
o al menos hasta que se termine la memoria de la computadora, para evitar
esto, hay que tener en cuenta, y muy bien definidos, los casos baes y los
casos generales del problema.
Algoritmos: Div�delos y Vencer�s
Una e las t�cnicas de programaci�n m�s
importante, es la denominada "Divide y vencer�s", que, como
ya hemos explicado en cap�tulos anteriores, consiste en subdividir
un programa grande y complejo, en peque�os programas m�s simples
y sencillos.
En recursi�n, normalmente este proceso da lugar a
casos base, es decir, problemas cuya soluci�n es inmediata, sin recursi�n.
Un algoritmo divide y vencer�s, puede ser llamado
recursivamente, a partir de un subconjunto (m�s peque�o) de
datos. La condici�n que deja de hacer las llamadas, es lo que hemos
denominado como caso base.
Torres de Hanoi
Quiz� el siguiente ejemplo, sea uno de los m�s
complejos de la recursi�n, por que consite en tres varillas, torres
o postes, paralelos; del cual el primero, posee tres donas, discos… en orden
de la m�s grande a la m�s peque�a, y se desean mover
de la varilla 1 a la varilla 3, pero bajo ciertas condiciones:
La siguiente imagen, representa, la forma m�s adecuada,
para realizar los movimientos:
Parece bastante complejo verdad?, en lo personal, me tom�
un poco de tiempo, entender y buscar la forma de mover las donas (debo confesar
que no soy muy bueno para ese tipo de jueguitos).
El ejemplo anterior constaba, unicamente de tres discos
(donas), pero puede generalizarse para n discos y tres varilas.
El algoritmo ser�a el siguiente:
If(n==1)
-Mover e disco 1 de la varilla inicial(1) a la varilla
final(3)
Else
-Mover n-1 discos desde varilla inicial(1) hasta varilla
la varilla temporal(2), utilizando la varilla 3, como auxiliar.
-mover el disco n desde varilla inicial a varilla final
-mover n-1 discos desde la varilla auxiliar central a varilla
final (3) utilizando como auxiliar a la varilla n�mero uno.
Ejemplo 8.11:
#include <stdio.h>
#include <conio.h>
void hanoi (int n, int inic, int temp, int fin);
main()
{
int n; /*numero de discos a mover*/
clrscr();
printf("Numero de discos:n");
scanf("%d", &n);
/*mover n discos desde 1 a 3, usando a 2 como auxiliar*/
hanoi(n, 1, 2, 3);
getch();
return 0;
}
void hanoi (int n, int inic, int temp, int final)
{
if(n>0)
{
/*mover n-1 discos de inic a temp*/
hanoi(n-1, inic, final, temp);
/*mover el que quede en inic a final*/
printf("Del poste %d al %dn", inic, final);
/*mover n-1 discos de temp a final*/
/*el temporal es inic*/
hanoi(n-1, temp, inic, final);
}
}
Cuestionario
1. �Qu� es recursi�n?:________________________________________________________________________________________________________________________________________
Descubre el error:
El siguiente c�digo, presenta algunos errores de l�gica,
de sintaxis y de ejecuci�n, �Puedes descubrirlos y corregirlos?
/* Programa que calcula la suma de dos vectores */
#include <stdio.h>
int suma (int a[], int b[], int n);
void main()
{
int a[5]={1,2,3,4,5};
int b[5]={1,2,3,4,5};
int n=5, r;
clrscr();
printf("el valor de la suma es:n");
r=suma(a,b, n);
printf("%d", r);
getch();
}
int suma (int a[], int b[], int n)
{
if(n!=0)
r=0;
else
{
r=a[n-1]+b[n-1]+suma(a, b, n-1);
}
return r;
}
/*Funci�n que suma a+b, usando una suceci�n*/
#include <stdio.h>
#include <conio.h>
int suma (int x, int b);
main()
{
int a,b,x=0, sum;
clrscr();
printf("PROGRAMA QUE USA LA FUNCION SUCC PARA SUMAR A+Bn");
printf("Ingrese el valor de a:");
scanf("%d", &a);
printf("b=");
scanf("%d", b);
sum=a+suma(x,b);
printf("%d + %d = %dnn", a,b,sum);
getch();
return 0;
}
int suma (int a, int b)
{
int r;
if(x==b)
r=x;
else
{
x++;
r=suma(a,b);
}
}
Ejercicios:
->A(m,n)=n+1, si m=0
->A(m,n)=A(m-1, 1) si n=0
->A(m,n)=A(m-1, A(m, n-1)) si m>0 y n>0
Cap�tulo IX: Estructuras
y Uniones
En este cap�tulo, vamos a aprender a usar una de las
caracter�sticas m�s singulares, peculiares y sobre todo, portentes
de C, como lo es, el uso de estructuras, uniones y TIPOS DE DATOS creados
por el programador, lo cual nos facilita muchas cosas ya que, no nos restringimos
a los tipos de datos que nos ofrece el lenguaje C.
Estructuras
Los arrays, son un ejemplo de estructuras (de tipo homog�neo),
sin embargo, �ste tipo de estructuras posee una gran limitante,
puesto que, s�lo admite datos del mismo tipo (entero, flotante, car�cter);
las estructuras que vamos a estudiar, estan compuestas por un grupo de variables,
no necesariamente del mismo tipo, en las cuales, podemos almacenar diferente
informaci�n (en cuanto a tipo), pero referente a un mismo t�pico.
Por ejemplo, en nuestro carn�t de identidad, del colegio,
de la universidad, aparecen muchos datops acerca de nosotros.
Nombres, apellidos, edad, direcci�n, fecha de nacimiento,
grado, secci�n, ciclo…
Estos datos, son de diferente tipo, pero, en C, podemos almacenarlos
utilizando un tipo de dato registro al que llamamos Estructura.
Por tanto, una estructura es una calecci�n de una
o m�s tipos de elementos denominados miembros, cada uno de los
cuales puede ser de un tipo de dato diferente.
La figura anterior, muestra, los datos (y el tipo) para cierto
registro, pero supongamos que dichos datos, son para alumnos de alguna universidad,
la cual cuenta con 500 alumnos… la cantidad de variables, ser�a impresionante,
por ejemplo tendr�amos que declarar 500 variables para los nombres,
500 para los apellidos, 500 para las edades, y as� sucesivamente.
Es ello que radica la importncia de las estructuras, por
que nos ahora tiempo adem�s que las estructuras son una herramienta
importante para la creaci�n de programas portentes y bases de datos.
Declaraci�n de una Estructura
Como toda variable, en C, debemos declarar una estructura
para poder hacer uso de ella, y la forma de hacerlo es la siguiente:
strcuct <nombre de la estructura>
{
<tipo de dato del miembro1> <nombre del miembro
1>;
<tipo de dato del miembro 2> <nombre de miembro
2>:
…
<tipo de dato del miembro n> <nombre del miembro
n>;
}
Por ejemplo, para los datos anteriores, la forma de declararla
ser�a la siguiente:
struct datos
{
char nombre[30];
char apellido[20];
int edad;
char direcci�n[100];
char fecha_nac[8];
};
Definici�n de variables del tipo estructura
Al igual que las funciones, las estructuras son declaradas
y definidas; en la declaraci�n es que, le estamos indicando al compilador
que las variables de tipo datos estar�n compuestas por los elemetos,
tales como nombre, apellido etc; pero adem�s, debemos defininir variables
que, ser�n de ese tipo. As� como en alguna parte de C, est�n
declarados los tipos de datos char, int, float; as� tambi�n
nosotros debemos definir las estructuras. Y cuando en el main, definimos las
variables que ser�n del tipo int, del tipo float o del tipo char, de
igual manera, debemos definir que variables ser�n del tipo de la estructura
que hemos creado. Para ello existen dos procedimientos:
Ejemplo:
1. struct datos
{
char nombre[30];
char apellido[20];
int edad;
char direcci�n[100];
char fecha_nac[8];
} alumno1, alumno2, alumno3;
2. struct datos alumno1, alumno2, alumno3;
Si por alg�n caso, los datos de las tres variables,
fuesen los mismos, podemos asignar los valores de �sta forma:
Alumno1=alumno2;
Alumno3=alumno2;
O tambi�n:
Alumno1=alumno3=alumno2;
Ya que, al contener los mismos miembros, es como si se tratacen
de datos tipo int, float o char, por consiguiente podemos hacer las asignaciones
anteriores.
Una esructuram la podemos inicializar as�:
struct datos
{
char nombre[30];
char apellido[20];
int edad;
char direcci�n[100];
char fecha_nac[8];
}alumno1 = {"Manuel",
"Ortez",
20,
"San Salvador, El Salvador",
"27/04/86",
};
o tambi�n as�:
struct datos alumno2={"Carolina",
"Pelayo",
20,
"San Salvador, El Salvador",
"14/05/86",
};
El tama�o de una estructura es determinado de forma
muy simple, consiste en sumar, el tama�o de todos los miembros, para
nuestro caso particular, el tama�o (en bytes) de la estructura datos
ser�a:
Ciertamente que, este proceso, lo podemos simplificar utilizando
la sentencia:
Sizeof(datos);
Cuyo resultado ser�: 160.
Acceso a una estructura.
Para acceder a una estructura, o bi�n a la informaci�n
guardada en ella, podemos hacer uso de dos nuevos amigos:
Por ejemplo:
Alumno1.nombre="Manuel";
Strcpy(alumno1.apellido, "Ortez");
Para utilizar el operador flecha, debemos hacer uso de punteros
(y cre�ste que ya nos hab�amos olvidado de los punteros verdad?).
Por ejemplo, si tenemos un puntero a una estructura:
.struct datos *ptr;
ptr=&alumno1;
ptr->edad=20;
Ejemplo 9.1
Dise�e un programa que guarde los datos de dos cd.
#include <stdio.h>
#include <conio.h>
/*declracion de la estructura*/
struct datos_cd
{
char titulo[20];
float precio;
char fecha[8];
};
main()
{
/*definicion de las variables estructuras*/
struct datos_cd cd1, cd2;
struct datos_cd *ptr;
int tam;
ptr=&cd2; /*asignacion de la direccion de cd2 al puntero*/
clrscr();
/*leemos los datos, usando el operador punto*/
printf("Introduzca el t�tulo del primer cd:n");
scanf("%s", &cd1.titulo);
printf("Intriduzca el precio del cd1:n");
scanf("%f", &cd1.precio);
printf("Ahora, la fecha de edicion (dd/mm/aa/):n");
scanf("%s", &cd1.fecha);
printf("Introduzca el t�tulo del segundo cd:n");
scanf("%s", &cd2.titulo);
printf("Intriduzca el precio del cd2:n");
scanf("%f", &cd2.precio);
printf("Ahora, la fecha de edicion (dd/mm/aa/):n");
scanf("%s", &cd2.fecha);
clrscr();
printf("tttAhora vamos a imprimir los valores guardados:nn");
printf("********************Datos del CD1*************************n");
printf("Titulo %s n", cd1.titulo);
printf("Precio %.2fn", cd1.precio);
printf("Fecha %sn", cd1.fecha);
printf("**********************************************************nn");
printf("********************Datos del CD2*************************n");
printf("Titulo %sn", ptr->titulo);
printf("Precio %.2fn", ptr->precio);
printf("Fecha %sn", ptr->fecha);
printf("**********************************************************nn");
printf("El tama�o de la estructura es %d bytesnn", sizeof(datos_cd));
getch();
return 0;
}
Estructuras Anidadas
Al igual que los ciclos, las decisiones, las expreciones,
etc, las estructuras tambi�n pueden estar dentro de otras, a esto es
que se le llama estructuras anidadas.
Supongamos que tenemos dos estructuras siguientes:
stuct empleado
{
char nom[30];
char puesto[10];
int edad;
float sueldo;
char municipio[20];
char ciudad[10];
char direcci�n[50];
};
struct cliente
{
char nom[30];
char fecha_deuda[8];
float saldo;
char municipio[20];
char ciudad[10];
char direcci�n[50];
};
observamos que, en ambas estructuras, hay fatos que se repiten,
los cuales los podr�amos ubicar en otra structura, as�:
struct direc
{
char municipio[20];
char ciudad[10];
char direcci�n[50];
};
por tanto, las estructuras de empleado y cliente, ser�a
de la siguiente forma:
stuct empleado
{
char nom[30];
char puesto[10];
int edad;
float sueldo;
struct direc direc_empleado;
};
struct cliente
{
char nom[30];
char fecha_deuda[8];
float saldo;
struct direc direc_cliente;
};
en C, podemos definir una estructura dentro de otra estructura,
claro siempre y cuando la declaraci�n de �sta, haya sido previo.
 P�gina anterior | Volver al principio del trabajo | P�gina siguiente  |