WIXLIB

aeiouaeiouvalarray has exited with status 0.1.2.ApuntadoresDefinición 2 Un apuntador es una variable que contiene una dirección dememoria.Supongamos una variable de tipo entero que se llama contenidoRAM y otravariable que se llama direccionRAM que puede contener una variable de tipoentero. En C/C una variable precedida del operador & devuelve la direcciónde la variable en lugar de su contenido. Ası́ que para asignar la dirección deuna variable a otra variable del tipo que contiene direcciones se usan sentenciascomo esta:direccionRam &contenidoRAMFigura 2. contenidoRAM se asigna a la localidad de memoria con dirección 7751En la figura 2 se ilustra el nombre de la variable contenidoRAM y se observaque se encuentra en la dirección 7751 de la memoria. El contenido de estalocalidad no se muestra. Una variable que contiene una dirección, tal comodireccionRAM, se llama variable apuntador o simplemente apuntador.Despues que la sentencia anterior se ejecuta, la dirección de contenidoRAMserá asignada a la variable apuntador direccionRAM. La relación se expresadiciendo que direccionRAM apunta a contenidoRAM. La figura 3 ilustra estarelación.El accceso al contenido de una celda cuya dirección está almacenada en lavariable direccionRAM es tan sencillo como poner al inicio de la variableapuntador un asterisco: *direccionRAM. Lo que se ha hecho es eliminar lareferencia directa. Por ejemplo, si se ejecutan las siguientes dos sentencias, elvalor de la celda llamada contenidoRAM será de 20 (véase la figura 4).10

Figura 3. Notación de flecha para los apuntadoresdireccionRAM &contenidoRAM;*direccionRAM 20;Figura 4. A contenidoRAM se le asigna el valor entero 201.2.1.Declaraciones de variables apuntadorC/C requiere una definición para cada variable. Para definir una variableapuntador direccionRAM que pueda contener la dirección de una variableint, se escribe:int *direccionRAM;Realmente existen dos partes separadas en esta declaración. El tipo de datode direccionRAM es:int *y el identificador para la variable esdireccionRAMEl asterisco que sigue a int significa “apuntador a”. Esto es, el siguiente tipode dato es una variable apuntador que puede contener una dirección a un int:int *11

En C/C una variable apuntador contiene la dirección de un tipo de datoparticular:char *direccion char;char *direccion int;El tipo de dato de direccion char es diferente del tipo de dato de la variableapuntador direccion int. En un programa que define un apuntador a untipo de dato y utliza éste para apuntar a otro tipo de dato, pueden ocurrirerrores en tiempo de ejecución y advertencias en tiempo de compilación. Unapráctica de programación pobre serı́a definir un apuntador de una forma yluego utilizar éste de alguna otra forma. Por ejemplo:int *direccion int;float un float 98.34;direccion int &un float;1.2.2.Utilización de punteros en sentencias sencillasVeamos el siguiente ejemplo:/*// changeVals.xcode*/(01) #include iostream (02)(03) int main (int argc, char * const argv[]) {(04) int A int 15, B int 37, Temp int;(05) int *direccion int;(06)(07) std::cout "El contenido de A int es:" A int "\n";(08) std::cout "El contenido de B int es:" B int "\n";(09) direccion int &A int;(10) Temp int *direccion int;(11) *direccion int B int;(12) B int Temp int;(13) std::cout "Despues del intercambio:" "\n\n";(14)(15) std::cout "El contenido de A int es:" A int "\n";(16) std::cout "El contenido de B int es:" B int "\n";(17)return 0;(18) }12

En la lı́nea (04) se han declarado tres variables de tipo entero, se da a cadacelda un nombre y se inicializan 2 de éstas. Supondremos que la dirección dememoria asignada para la variable A int es la dirección 5328, y la direcciónen memoria RAM asignada para la variable B int es la dirección 7916, y lacelda llamada Temp int se le ha asignado la dirección 2385. Véase la figura 5;Figura 5. Descripción de las tres variables en la memoriaEn la lı́nea (05) se define un apuntador a un tipo de dato entero llamadodireccion int. La sentencia asigna la celda y da a ésta un nombre.Luego, en la lı́nea (09), la tercera sentencia asigna a direccion int la dirección de A int (figura 6).Figura 6. direccion int dada la dirección de A intLa lı́nea (10) utiliza la expresión *direccion int para acceder al contenidode la celda a la cual apunta direccion int:Temp int *direccion int;Por consiguiente, el valor entero 15 se almacena en la variable Temp int. Sino se pone el * enfrente de direccion int;, la sentencia de asignación almacenarı́a ilegalmente el contenido de direccion int en la celda nombradaTemp int, pero se supone que Temp int contiene un entero, no una dirección.13

Este puede ser un error muy difı́cil de localizar puesto que muchos compiladores no emiten ninguna advertencia/error.Para empeorar el asunto, la mayorı́a de los apuntadores son cercanos, lo quesignifica que ocupan 2 bytes (4 bytes para aplicaciones de 32-bits), el mismotamaño que un entero en una PC.La sentencia (11) copia el contenido de la variable B int en la celda apuntadapor la dirección almacenada en direccion int(figura 7):*direccion int B int;Figura 7. Se copia el contenido de B int usando la notación de flecha de apuntadoresLa última sentencia en la lı́nea (12) simplemente copia el contenido de unavariable entera, Temp int en otra variable entera B int (figura 8Figura 8. Se copia Temp int en B int utilizando asignación normal.Debemos de asegurarnos de comprender la diferencia entre qué se referenciacuando una variable puntero está precedida por el operador de indirección ycuándo no está precedida por este operador.Para este ejemplo, la primera sintaxis es un apuntador a una celda que puedecontener un valor entero. La segunda sintaxis referencia la celda que contienela dirección de otra celda que puede contener un entero.14

1.2.3.Utilización incorrecta del operador de direcciónNo se puede utilizar el operador de dirección sobre toda expresión C/C . Elsiguiente ejemplo demuestra aquellas situaciones donde no se puede aplicar eloperador de dirección &.puedeAlmacenarDireccionDeConstante &37;int RAM int 5;puedeAlmacenarDireccionDeExpresionTemp &(RAM int 15);puedeAlmacenarDireccionDeRegistro &varRegistro;La primera sentencia trata de obtener ilegalmente la dirección de un valorconstante integrado. La sentencia no tiene sentido puesto que 37 no tiene unacelda de memoria asociada con éste.La segunda sentencia de asignación intenta devolver la dirección de la expresión RAM int 15. No existe dirección asociada con la expresión puesto que laexpresión en sı́ misma es realmente un proceso de manipulación de pila.Normalmente, el último ejemplo respeta la demanda del programador paradefinir varRegistro como un registro más que como una celda de almacenamiento en la memoria interna. Por consiguiente, no podrı́a devolverse yalmacenarse la dirección de celda de memoria. El compilador C/C da lamemoria de variable, no el almacenamiento de registro.1.3.Estructuras C/C Definición 3 Una estructura es un grupo de variables las cuales pueden serde diferentes tipos sostenidas o mantenidas juntas en una sola unidad. Launidad es la estructura.1.3.1.Sintaxis y reglas para estructuras en C/C En C/C se forma una estructura utilizando la palabra reservada struct,seguida por un campo etiqueta opcional, y luego una lista de miembros dentrode la estructura. La etiqueta opcional se utiliza para crear otras variables deltipo particular de la estructura:struct campo etiqueta{tipo miembro miembro 1;tipo miembro miembro 2;15

tipo miembro miembro 3;::tipo miembro miembro n;};Un punto y coma finaliza la definición de una estructura puesto que ésta esrealmente una sentencia C/C . Algunos de los ejemplos usan la estructura:struct stbarco{char sztipo[iString15 iNull char];char szmodelo[iString15 iNull char];char sztitular[iString20 iNull char];int ianio;long int lhoras motor;float fprecioventa;};En un programa, podemos asociar una variable con una estructura utilizandouna sentencia similar a la siguiente:struct stbarco stbarco usado;La sentencia define stbarco usado de tipo struct stbarco. La declaraciónrequiere el uso del campo etiqueta de la estructura. Si esta sentencia está contenida dentro de una función, entonces la estructura, llamada stbarco usado,tiene un ámbito local a esa función. Si la sentencia está contenida fuera detodas las funciones de programa, la estructura tendrá un ámbito global. Esposible declarar una variable usando esta sintaxis:struct stbarco{char sztipo[iString15 iNull char];char szmodelo[iString15 iNull char];char sztitular[iString20 iNull char];int ianio;long int lhoras motor;float fprecioventa;} stbarco usado;Aquı́ la declaración de variable va antes del punto y coma final. Cuando seasocia sólo una variable con el tipo estructura, el campo etiqueta puede sereliminado, por lo que serı́a posible escribir:struct {char sztipo[iString15 iNull char];char szmodelo[iString15 iNull char];16

char sztitular[iString20 iNull char];int ianio;long int lhoras motor;float fprecioventa;} stbarco usado;1.3.2.Utilización de miembros de estructurasPara accesar a los miembros de las estructuras se usa el punto u operadormiembro (.). La sintaxis es:estructuraNombre.miembroNombrePor ejemplo en:gets(stbarco usado.szmodelo);Aquı́, stbarco usado es el nombre asociado con la estructura, y szmodelo esuna variable miembro de la estructura, otro ejemplo:std::cin stbarco usado.sztipo;Esta sentencia leerá la marca del stbarco usado en el arreglo de caracteres,mientras la próxima sentencia imprimirá el precio de venta de stbarco usadoen la pantalla.srd::cout stbarco usado.fprecioventa;Ejemplo de estructuras:/* fractionStruct.cpp Programa para demostrar el uso de lostipos Struct en C , este tipo de datoses util para los programadores para crearsus propias estructuras de tipos.*/#include iostream using namespace std;// Definimos un nuevo tipo de estructura llamada Fraction// como la definicion se puso antes del "main"// los tipos Fraction se pueden usar como prototipos17

struct Fraction {// declaramos sus dos miembrosint numerator;int denominator;}; // Note el punto y coma al final// funciones prototiposvoid getFraction(Fraction &f);void printFraction(const Fraction &f);int main (int argc, char * const argv[]){// declaramos variables de tipo FractionFraction f1, f2;// obtenemos dos fracciones y las desplegamosgetFraction(f1);cout "\nf1 ";printFraction(f1);getFraction(f2);cout "\nf2 ";printFraction(f2);cout endl;return 0;}// pedimos al usuario los valores del denominador y numerador// los almacenamos en su adecuado lugar en la estrcututra; checamos si// el valor del denominador es valido y lo ponemos en 1 si no lo es.void getFraction(Fraction &f) {cout "\nEnter the numerator: ";cin f.numerator;cout "Enter the denominator: ";cin f.denominator;if (f.denominator 0) {cout "\nIllegal denominator! Denominator is being set to 1.\n";f.denominator 1;}}// imprimimos la fraccionvoid printFraction(const Fraction &f) {cout f.numerator "/"18

f.denominator "\n";}Nota sobre las funciones prototipos:Las funciones prototipo tienen los siguientes usos importantes:Establecen el tipo devuelto para las funciones que devuelven otros tiposdiferentes que int. Aunque las funciones que devuelven valores enteris nonecesitan prototipos, se recomienda tener prototipos.Sin prototipos completos, se hacen las conversiones estándares, pero no sechecan los tipos o los números de argumentos con el número de parámetros.Los prototipos se usan para inicializar apuntadores a funciones, antes deque las funciones sean definidas.La lista de parámetros se usa para checar la correspondencia de los argumentos en la llamada a la función con los parámetros en la definición de lafunciónconst en parmetros de funcionesEl especificador const puede ser utilizado en la definición de parámetros defunciones. Esto resulta de especial utilidad en tres casos. En los tres el finque se persigue es el mismo: indicar que la función no podrá cambiar dichosargumentos:Con parámetros de funciones que sean de tipo matriz (que se pasan porreferencia). Ejemplo: int strlen(const char[]);Cuando los parámetros son punteros (a fin de que desde dentro de la funciónno puedan ser modificados los objetos referenciados). Ejemplo: int printf(const char *format, .);Cuando el argumento de la función sea una referencia, previniendo ası́ que lafunción pueda modificar el valor referenciado. Ejemplo: int dimen(constX &x2);1.4.Ejercicios de programación1. El siguiente algoritmo es el método de inserción para ordenar elementosen un arreglo:insertionSort(A)for j: 2 to length[A]do key: A[j]- Inserta el elemento A[j]- en la secuencia ordenada A[1.j-1]i: j-119

while i 0 and A[i] keydo A[i 1] A[i]i: i-1A[i 1]: keya) desarrolle un programa en C/C del método de inserciónb) ilustre cómo opera el algoritmo insertionSort(A) usando como entrada el arreglo A 31,41,59,26,41,58 2. Reescriba el programa y nómbrelo insertionSortNondec para que ordene los elementos en orden decreciente3. Considere el siguiente problema de búsqueda:Input: Una secuencia de n números A ha1 , a2 , . . . , an i y un valor v.Output: Un ı́ndice i tal que v A[i] o el valor espacial N IL si v noocurre en A.Escriba un programa que resuelva este problema de búsqueda.4. Considere el problema de sumar dos números binarios de longitud n.Cada número se almacena en uno de los arreglos A y B de tamaño n. Lasuma se almacena en un arreglo C de tamaño n 1, también como unnúmero binario. Escriba un programa que resuelva este problema.20

2.La pilaUno de los conceptos más útiles en las ciencias de la computación es el de pila.En esta sección vamos a definir este concepto de manera abstracta y veremoscómo se usa para convertirse en una herramienta concreta y de gran valor enlas soluciones de problemas. La información contenida en esta sección se hatomado de [TA83].2.1.Definición y ejemplosDefinición 4 Una pila (stack) es una colección ordenada de elementos en lacual se pueden insertar nuevos elementos por un extremo y se pueden retirarotros por el mismo extremo; ese estremos se llama “la parte superior” de lapila.Si tenemos un par de elementos en la pila, uno de ellos debe estar en la partesuperior de la pila, que se considera “el más alto” en la pila que el otro. Enla figura 9 el elemento F es el más alto de todos los elementos que están en lapila. El elemento D es el más alto de los elementos A,B,C, pero es menor quelos elementos E y F.Figura 9. Pila con 6 elementosPara describir cómo funciona esta estructura, debemos agregar un nuevo elemento, el elemento G. Después de haber agregado el elemento G a la pila, lanueva configuración es la que se muestra en la figura 10.De acuerdo con la definición, existe solamente un lugar en donde cualquierelemento puede ser agregado a la pila. Después de haber insertado el nuevoelemento, G ahora es el elemento en la cima. Debedos aclarar en qué piladeseamos insertar elementos, puesto que es posible tener más de una pila almismo tiempo.21

Figura 10. Operación de insertar el elemento G en la pila PCuando se desea retirar un elemento de la pila, solo basta ordenar que searetirado un elemento; no podemos decir “retira C de la pila”, porque C noestá en la cima de la pila y solamente podemos retirar el elemento que está enla cima. Para que la sentencia “retira C de la pila” tenga sentido, debemosreplantear las órdenes a algo como:Retira de la pila hasta que el elemento retirado sea C.Ni siquiera es necesario decir: “Retira un elemento de la pila.” porque essobreentendido que solamente se puede sacar un elemento a la vez.Siguiendo nuestro ejemplo, ahora deseamos retirar de la pila P. La configuración global de la pila es como se muestra en la figura 11Figura 11. Operación de retirar de la pila PEl concepto de pila es muy importante en computación y en especial en teorı́ade lenguajes de programación. En lenguajes procedurales como Pascal o C, lapila es una estructura indispensable, debido a las llamadas a función.Resulta que el flujo de instrucciones va de arriba hacia abajo, y cuando ocurreuna llamada a alguna función, el estado global del sistema se almacena en unregistro y éste en una pila. Ası́ que la pila va a contenr todas las llamadas aprocedimientos que se hagan.22

Cuando se termina de ejecutar algún procedimiento, se recupera el registro queestá en la cima de la pila. En ese registro están los valores de las variables comoestaban antes de la llamada a la función, o algunas pueden haber cambiado sivalor, dependiendo del ámbito de las variables.Cada elemento en la pila que es retirado, significa que se ha terminado deejecutar alguna función. Cuando se termina de ejecutar el programa, la pilade llamadas a subprogramas debe haber quedado en 0 también, de otro modopodrı́a causar algun tipo de error.Esto nos lleva a pensar en otras utilidades de la pila. La pila sirve para encontrar errores.La dinámica de la pila, es decir, la manera en cómo entran los datos a laestructura de datos y cómo salen, se denomina fifo, que viene del ingés firstin first out (primero en entrar, primero en salir).Figura 12. Dinámica de la pila PEn la figura 12 se muestran “fotografı́as” en distintos momentos de la pila,cuando se desea insertar H justo debajo de F. Para hacer esto se requiere,retirar tantos elementos como sean necesarios, aquı́ se han retirado de la cimaG y F para luego insertar H, que quedará posteriormente debajo de F.Lo que sucede es que, cuando se retira el elemento G se debe hacer una evaluación para determinar si el elemento retirado es el elemento objetivo, en estecaso el elemento objetivo es F, puesto que se desea insertar un elemento debajode F.Después de haber insertado F, insertamos de nuevo los elementos F y G en eseorden, además de insertar finalmente el elemento I que queda en la cima de lapila. Enseguida veremos con más detalle las operaciones básicas de las pilas.23

2.2.Operaciones básicasLas operaciones básicas de una pila son:1.2.3.4.En la pila S, insertar un elemento e: push(S,e),Retirar un elemento de la pila S: pop(S),Verificar si la pila S está vacı́a: stackempty(S) ySaber cuál es el elemento en la cima de la pila S: stacktop(S).enseguida cada una de estas operaciones:2.2.1.La operación pushEsta operación sirve para insertar un elemento e en la pila S, lo vamos aescribir como:push(S,e)Después de hacer esta operación sucede que:El elemento en la cima de la pila S ahora es e2.2.2.La operación popPara retirar un elemento de la pila S y asignarlo a una variable del mismo tipoque el tipo de los elementos de la pila, usaremos la operación pop escribiéndolacomo:v pop(S);En donde v es una variable que almacena el valor del elemento que estaba enla cima de S. Hacer esta operación tiene algunas implicaciones:La variable v debe ser del mismo tipo que los elementos almacenados en lapila.Solamente se puede retirar un elemento de la pi

Apuntes para el curso de "Estructuras de datos en C/C " Dr. Abdiel E. C aceres Gonz alez ITESM-CCM 2 de junio de 2005 Resumen Una estructura de datos es una manera de almacenar y organizar datos para facilitar el acceso y modificaciones. No hay una estructura de datos que sirva para todos los