1

Capítulo 2.

Definición de Estructuras de Datos en C. Se desea conocer las técnicas para diseñar estructuras de datos. Se repasan los conceptos de tipos básicos, para luego desarrollar las herramientas de creación de nuevas estructuras, haciendo énfasis en los conceptos de agrupación y vinculación. Dando ejemplos que posteriormente se emplearán en el texto.

2.1. Tipos primitivos. En los lenguajes de programación suele disponerse de tipos básicos o primitivos: caracteres, enteros con y sin signo, reales o flotantes de simple y doble precisión. Se dispone la forma de definir e inicializar variables de esos tipos, y también la forma de escribir constantes de esos tipos. Para los tipos primitivos existen numerosos y variados operadores que permiten construir expresiones con variables y constantes de dichos tipos. En determinados casos existen mecanismos automáticos para convertir valores de un tipo en otro, sin embargo es preferible la conversión explícita a través del molde o “cast”. Mediante las bibliotecas de entrada-salida pueden ingresarse o desplegarse valores de esos tipos.

2.2. Mecanismos de estructuración. Existen dos mecanismos básicos de estructuración de datos: la agrupación y la vinculación. 2.2.1. Grupos básicos. La estructura (struct) permite agrupar elementos de diferente tipo. El arreglo agrupa elementos de igual tipo. El string agrupa caracteres.

Profesor Leopoldo Silva Bijit

20-01-2010

2

Estructuras de Datos y Algoritmos

Estructura

Arreglo

String

Figura 2.1. Agrupaciones de datos. Se dispone de una forma de definir variables de esos grupos básicos, y los mecanismos de acceso a las componentes: el discriminador del campo (un punto) para las estructuras; y los paréntesis cuadrados o corchetes para delimitar el índice de la componente del arreglo. Las operaciones que están definidas para estos grupos básicos son muy reducidas, el programador debe crear sus propias funciones o métodos para efectuar operaciones más complejas sobre estos grupos básicos. En el caso de strings existe una biblioteca estándar de funciones que los manipulan (ver Apéndice 2). Las agrupaciones pueden ser tan complejas como sea necesario: ya que es posible crear arreglos de estructuras, y también estructuras que contengan arreglos y strings. 2.2.2. Vínculos. Pueden establecerse relaciones entre elementos de datos. Los siguientes diagramas ilustran las formas básicas de vinculación: vínculos de orden o secuencia en listas, relaciones jerárquicas en árboles, e interconexiones complejas en grafos.

árboles listas

grafos

Figura 2.2. Vínculos entre componentes de datos. Profesor Leopoldo Silva Bijit

20-01-2010

Definición de Estructuras de Datos en C.

3

El vínculo es el elemento de datos de una componente que permite accesar a otra componente. Una componente puede contener información de uno o más vínculos. El programador debe disponer de elementos del lenguaje que le permitan crear nuevos tipos de datos, y mediante estos tipos crear funciones o métodos que realicen operaciones sobre las componentes. Cuando el número máximo de componentes es conocido de antemano, las componentes pueden modelarse como una serie de arreglos agrupados en una estructura. En la cual se emplea uno o varios arreglos para establecer el o los vínculos entre las componentes. Se suele definir como cursor a una variable que contiene el valor del índice de una componente. Otro mecanismo para establecer vínculos es el puntero, que es una variable que contiene la dirección de otra componente. La vinculación a través de punteros suele emplearse preferentemente en situaciones dinámicas, en las cuales el número de las componentes varía durante la ejecución del programa; esto debido a que se crean, insertan y descartan componentes.

2.3. Ejemplos basados en arreglos. 2.3.1. Acceso a componentes del arreglo. El acceso a componentes se realiza vía indirección de un puntero constante que es el nombre del arreglo, con un offset dado por el índice del elemento. Se definen tipos de datos. typedef int Tipo; /* tipo de item del arreglo */ typedef int Indice; /* tipo del índice */ Es práctica usual, definir mediante una constante el tamaño máximo del arreglo #define MaxEntradas 10 Se definen e inician con valores dos arreglos Tipo A[MaxEntradas]={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; Tipo B[MaxEntradas]={ 10,11,12,13,14,15,16,17,18,19}; A las funciones que manipulan arreglos se les suele pasar el arreglo por referencia. Por ejemplo la función que imprime en una línea las componentes de un arreglo a. void mostrar(Tipo *a, Indice inferior, Indice superior) { Indice i; for (i = inferior; i agno); } Ejemplos de uso: printfecha(fecha3); printfecharef(pfecha3); También es útil disponer de un constructor de la estructura. Fecha setfecha (int dia, int mes, int agno) //retorno de estructura { Fecha f; f.dia=dia; f.mes=mes; f.agno= agno; //escritura en campos return(f); } Ejemplo de uso: fecha3 = setfecha(15, 6, 2005); También suele ser necesario desarrollar funciones para realizar operaciones de comparación entre estructuras. El siguiente prototipo ilustra un operador de comparación “mayor o igual que”, al cual se le pasan punteros a estructuras y devuelve un puntero a la estructura que es mayor o igual que la otra, el diseño de la función se deja como tarea. pFecha fechaGET(pFecha pf1, pFecha pf2);

Profesor Leopoldo Silva Bijit

20-01-2010

Definición de Estructuras de Datos en C.

9

Se pueden crear arreglos de estructuras de tipo Fecha: Fecha ArrFecha[3]={ {1,1,2005},{30,6,2005},{31,12,2005}}; printf("mes %d \n", (ArrFecha+1)->mes); imprime 6 printf("dia %d \n", ArrFecha[2].dia); imprime 31 Es responsabilidad del programador no exceder los rangos del arreglo. 2.4.2. Lista simplemente enlazada en base a punteros. Es posible declarar el molde y definir tipos simultáneamente. En esta situación en lugar de moldenodo se podría haber puesto cualquier otro identificador. Esta forma suele describirse como declaración anónima. typedef struct moldenodo { int clave; struct moldenodo *proximo; } nodo, *pnodo; //instancias. Definiciones. nodo nodo1={1,NULL}; nodo nodo2={2,NULL}; nodo nodo3={3,NULL}; pnodo lista=&nodo1; Las siguientes asignaciones crean los vínculos. lista->proximo = &nodo2; nodo2.proximo = &nodo3; lista 1 nodo1

2

3

nodo2

nodo3

Figura 2.4. Lista simplemente enlazada, mediante punteros. En caso de definir la lista en forma dinámica, sólo es preciso definir la variable lista. El espacio para los nodos se solicita a través de llamados a malloc; debido a esto los nodos no tienen un nombre y sólo se los puede accesar vía punteros. En el caso del ejemplo, los nodos se han definido en forma estática, y tienen un nombre de variable asociado.

Profesor Leopoldo Silva Bijit

20-01-2010

10

Estructuras de Datos y Algoritmos

2.5. Estructuras más complejas. 2.5.1. Arreglo de listas. Pueden concebirse estructuras más complejas. Por ejemplo se desea disponer de un arreglo de punteros, donde cada elemento del arreglo es el inicio de una lista simplemente enlazada. Consideraremos que cada celda debe estar asociada a un string, donde los strings pueden ser de diferente largo. Se decide que no es conveniente almacenar los strings como arreglos de caracteres, esto implicaría un tamaño fijo para cada arreglo, con lo cual se ocuparía mal el espacio cuando deba almacenarse un string de pequeño largo, y la estructura puede colapsar si el largo del string es mayor que el tamaño máximo del arreglo. Es preferible asociar al nodo de la lista un puntero a un string, lo cual ocupa un tamaño fijo (normalmente los bytes ocupados por un entero). Definimos entonces los siguientes tipos: typedef struct moldecelda { char *nombre; struct moldecelda *next; } celda, *pcelda; #define BALDES 10 /* 10 celdas */ static pcelda hashtable[BALDES]; /*tabla punteros */ La palabra static, que precede a la definición, explícitamente indica que la tabla debe almacenarse en un segmento estático de la memoria. Es decir estará disponible, durante toda la ejecución del programa. Se ilustra un ejemplo de la estructura.

Índice

Tabla

String0

0 1 2 …. B-1

String i

String j

String k

Figura 2.5. Arreglo de listas.

Profesor Leopoldo Silva Bijit

20-01-2010

Definición de Estructuras de Datos en C.

11

Veremos que se pueden desarrollar algoritmos eficientes para buscar strings almacenados en la tabla, cuando estudiemos tablas de hash. 2.5.2. Arreglo de estructuras. El siguiente ejemplo de diseño de una estructura de datos, contempla un arreglo en el cual se califica el estado de cada celda. Suponemos que se almacena un entero, y para describir lógicamente el estado empleamos la definición de un tipo enumerativo, que permite el mapeo de nombres lógicos con enteros. Internamente se emplean enteros, pero el programador puede referirse a ellos mediante sus nombres equivalentes. typedef enum {vacio, ocupado, descartado} state; typedef struct hcelda { int clave; state estado; } celda; #define B 10 /* 10 celdas */ static celda hashtab[B]; /*arreglo de celdas */ static int ocupados; //ocupados de la tabla El programador puede escribir expresiones en términos del tipo enumerativo: (hashtab[i].estado != vacio && hashtab[i].estado != descartado) 2.5.3. Multiárboles. La descripción de un nodo que pueda tener un número variable de punteros que apunten a sus descendientes no es práctica. Ya que esto implica almacenar los vínculos en un arreglo, y si es arreglo debe tener un tamaño fijo. El cual debe escogerse considerando el máximo número de descendientes que soportará la estructura; mal empleando los recursos en el caso de un nodo sin hijos, o de nodos con un pequeño número de descendientes. Además siempre estará el riesgo de que aparezca un nodo con mayor número de descendientes que el tamaño máximo escogido. 1

2 5

3 6

7

8

4 9

10

11

Figura 2.6. Multiárbol.

Profesor Leopoldo Silva Bijit

20-01-2010

12

13

12

Estructuras de Datos y Algoritmos

El esquema anterior ilustra los vínculos. Este ejemplo refuerza el concepto que un vínculo puede ser un cursor o un puntero. El número variable de los vínculos asociados a un nodo pueden reemplazarse por sólo dos vínculos: uno que relaciona el nodo con el primer descendiente izquierdo, y otro que vincula a cada nodo con su hermano derecho. Nótese que en cada nivel puede observarse una lista de nodos que parte del nodo ubicado más a la izquierda y termina en un vínculo nulo después del último descendiente de un nodo.

Figura 2.7. Primer descendiente izquierdo, hermano derecho. Con esta visualización se requieren sólo dos vínculos por nodo. 2.5.3.1. Descripción mediante punteros. Una representación mediante punteros requiere definir la estructura del nodo según: typedef struct moldenodo { int valornodo; struct moldenodo *hijoizquierdo; struct moldenodo *hermanoderecho; struct moldenodo *padre; potros * datos_periféricos; } nodo, *pnodo; Donde se han definido los tipos asociados al nodo y al puntero a nodo. Se ha considerado que se almacenará un entero como clave o valor distintivo del nodo. Se ha agregado un puntero a una estructura que podría almacenar otros datos asociados al nodo, con el campo datos_periféricos. También se agrega un puntero al padre, ya que esta información reduce el tiempo de buscar al padre de un nodo determinado. 2.5.3.2. Descripción mediante arreglos de cursores. Se describe a continuación los valores que describen el multiárbol, de la Figura 2.6, mediante arreglos de cursores para el Hijo izquierdo y Hermano Derecho. Se ha considerado que un valor cero indica que no hay hijo izquierdo o hermano derecho o padre; si se desea usar el nodo cero, podría elegirse -1 como el cursor nulo.

Profesor Leopoldo Silva Bijit

20-01-2010

Definición de Estructuras de Datos en C.

13

Índice Hijo izquierdo Hermano derecho Padre Clave Otros datos 0 0 0 0 --1 2 0 0 1 -2 5 3 1 2 -3 7 4 1 3 -4 10 0 1 4 -5 0 6 2 6 -6 0 0 2 6 -7 0 8 3 7 -8 0 9 3 8 -9 0 0 3 9 -… Figura 2.8. Multiárbol mediante arreglo de cursores. Se ha agregado un arreglo de cursores para especificar el padre del nodo. Esta información facilita la búsqueda del padre de un nodo dado. Un diseño de la estructura de datos considera al multiárbol como una estructura cuyos campos son los diferentes arreglos. #define MAXNODOS 13 struct moldemultiarbol { int Hijo_izquierdo[MAXNODOS]; int Hermano_derecho[MAXNODOS]; int Padre[MAXNODOS]; int clave[MAXNODOS]; int dato1[MAXNODOS]; } arbol; arbol.Hijo_derecho[4] tiene valor 0; lo cual indica que es el último descendiente. La estructura puede contener más o menos información dependiendo de costo de las operaciones que se deseen implementar. Por ejemplo si sólo se desea conocer la conectividad de los nodos del multiárbol, basta que la estructura aporte información para conocer quien es el padre de cada nodo, con esta descripción si luego se desea conocer los hijos de cada nodo, resultará un algoritmo costoso. 2.5.3.3. Descripción por arreglo de padres.

Profesor Leopoldo Silva Bijit

20-01-2010

14

Estructuras de Datos y Algoritmos 0

1 4

2 5

6

3

7

8

9

10

11

12

Figura 2.9. Multiárbol mediante arreglo de padres. En un ambiente de grafos, es de interés describir un árbol que interconecta todos los vértices sin formar circuitos. Se ilustra un árbol de un grafo orientado, en el que se muestra el número asociado a cada vértice; se ha considerado el vértice 0, esto debido a que los arreglos en C, parten de índice cero. La información que describe el árbol anterior es: Vértice 0 1 2 3 4 5 6 7 8 9 10 11 12 Padre del vértice 0 0 0 0 1 1 2 2 2 3 3 3 3 Figura 2.10 Arreglo de padres. Empleando lenguaje de programación, queda: int PadreDelVertice[MAXNODOS]={0, 0, 0, 0, 1, 1, 2, 2, 2, 3, 3, 3, 3};

2.6. Un ejemplo real de estructuras. La realidad suele ser más compleja que los casos idealizados que se exponen en los cursos básicos. El diseño de una estructura más realista, es la que describe los encabezados de los paquetes ICMP e IP en un ambiente de red. Primero se definen dos tipos básicos, con fines de compatibilidad. Se mapean los tipos del lenguaje C, a tipos lógicos. Si los tamaños de los tipos básicos de un compilador para un procesador específico son diferentes, basta cambiar el nombre de los tipos básicos. Toda la codificación no es necesario modificarla, ya que queda en términos de u8_t y u16_t, que son los tipos usados en el programa. typedef unsigned char u8_t; //es el tipo byte. typedef unsigned short u16_t; //el entero de 16 bits

Profesor Leopoldo Silva Bijit

20-01-2010

Definición de Estructuras de Datos en C.

15

/* The ICMP and IP headers. */ typedef struct { /* IP header. */ u8_t vhl, tos, len[2], ipid[2], ipoffset[2], ttl, proto; u16_t ipchksum; u16_t srcipaddr[2], destipaddr[2]; /* ICMP (echo) header. */ u8_t type, icode; u16_t icmpchksum; u16_t id, seqno; } uip_icmpip_hdr;

Problemas resueltos. P2.1. Se tiene el siguiente programa: #include #include #define MAX 5 typedef struct nn { int i1; int i2; struct nn * next; } nodo, * pnodo; pnodo lista1=NULL; pnodo lista2=NULL; pnodo getnodo(void) { pnodo p; if( (p=(pnodo)malloc(sizeof(nodo)))==NULL) return(NULL); else return(p); } void Push(pnodo *ref, int dato1, int dato2) { pnodo newnodo; if ( (newnodo=getnodo( )) == NULL) exit(1); newnodo->i1 = dato1; newnodo->i2 = dato2; newnodo->next = *ref; Profesor Leopoldo Silva Bijit

20-01-2010

16

Estructuras de Datos y Algoritmos

*ref = newnodo; }

void crealista(void) { int i; for(i=0; inext;} return (qq); } pnodo busca2(pnodo p, int j, pnodo q) { if(p !=NULL) { while( p->i1 != j ) p = p->next; if (p != NULL) while (q !=NULL) { if(p->i2 == q->i1) return(q); q = q->next; } return (NULL); } return(NULL); } int main(void) { pnodo tt; crealista(); printf(" %d \n", ( *(busca(lista1)) ).i1); printf(" %d \n", busca(lista2)->i2); if( (tt=busca2(lista1, 3, lista2)) !=NULL) printf(" %d \n", tt->i2); return(0); } a) Explicar, empleando un diagrama, el paso por referencia de Push. b) Diagrama de la estructura después de ejecutar crealista(); c) Explicar acción realizada por busca. d) Explicar acción realizada por busca2. e) Determinar qué imprime el programa. Solución. a) En la función crealista, se tiene un ejemplo de uso de Push. Consideremos el llamado: Push(&lista1, 0, 1). En la definición de Push, el primer argumento es un puntero a puntero a nodo. Profesor Leopoldo Silva Bijit

20-01-2010

Definición de Estructuras de Datos en C.

17

Dentro de la función, la ocurrencia de *ref, denota a la variable, cuya dirección es pasada en la invocación a la función, en el caso del ejemplo referencia a variable global lista1. Si *ref, aparece a la derecha, formando parte de una expresión, su valor es el almacenado en lista1; si aparece a la izquierda, se escribe en la variable lista. Luego de la invocación a la función, se tiene el siguiente esquema para las variables. Datos

Stack

Lista1 newnodo

?

ref dato1 = 0 dato2 = 1

Figura P2.1. Nótese que los argumentos son variables almacenadas en el stack, iniciadas con los valores de los parámetros de la invocación. La variable local newnodo, al no estar inicializada en su definición apunta a cualquier lado. Razón por la cual, conviene definirlas e inicializarlas simultáneamente. Después de un llamado exitoso a getnodo(); es decir, malloc asignó una estructura en el heap, un diagrama de la situación es el siguiente: Datos

Stack

heap

Lista1 newnodo

i1 = ?

ref

i2 = ?

dato1 = 0

next = ?

dato2 = 1

Figura P2.2. El resto de la función, escribe en los campos de la estructura creada en el heap. Y además, en último término, sobreescribe en la variable global lista1(en el ejemplo que se analiza).

Profesor Leopoldo Silva Bijit

20-01-2010

18

Estructuras de Datos y Algoritmos

Datos

Stack

heap

Lista1 newnodo

i1 = 0

ref

i2 = 1

dato1 = 0

next

dato2 = 1

Figura P2.3 Al salir de Push, desaparecen las variables automáticas, ubicadas en el stack, y la situación queda: Datos

Stack

heap

Lista1 i1 = 0 i2 = 1 next

Figura P2.4 Si se hubiera pasado solamente un puntero a nodo como referencia, se tendría el diseño:

void Push2(pnodo ref, int dato1, int dato2) { pnodo newnodo; if ( (newnodo=getnodo()) == NULL) exit(1); newnodo->i1 = dato1; newnodo->i2 = dato2; newnodo->next = ref; ref = newnodo; } Y un ejemplo de uso, sería: Push2(lista1, 0, 1); Lo cual no es equivalente al diseño anterior. Puede comprobarse efectuando un diagrama. Profesor Leopoldo Silva Bijit

20-01-2010

Definición de Estructuras de Datos en C.

19

Las listas con cabecera ( header ) permiten diseños alternativos. b) Después de crealista, el espacio queda: Datos Lista1

Lista2

heap i1=4

i1 = 3

i1 = 2

i1 = 1

i1 = 0

i2 = 5

i2 = 4

i2 = 3

i2 = 2

i2 = 1

next

next

next

next

next

i1 =1

i1 = 2

i1 = 3

i1 = 4

i1 = 5

i2 = 3

i2 = 2

i2 = 1

i2 = 0

next

next

next

next

i2 = -1 next

Figura P2.5. c) A la función busca, se le pasa la dirección del primer nodo de la lista. Si la lista es vacía, retorna un puntero nulo. Si no es vacía, con pp recorre la lista, dejando qq apuntado al nodo corriente y con pp al próximo. Cuando se llega con pp, al final de la lista, qq apunta al último nodo de la lista. d) La función busca2 intenta encontrar el valor j en el campo i1 del nodo apuntado por el argumento p. Si la lista es vacía retorna un puntero nulo; en caso de encontrar el valor j, busca a partir del nodo apuntado por q, el valor del campo i1 que sea igual al valor del campo i2 del nodo donde quedó apuntando p. Si lo encuentra, retorna un puntero al nodo que cumple la condición anterior; en caso contrario, retorna un puntero nulo. La invocación: busca2(lista1, 3, lista2), después del primer while, deja p apuntando al segundo nodo de la lista1, el segundo while deja q apuntando al cuarto nodo de la lista2; ya que busca en ésta el valor 4 en el campo i1. El diseño de la función incurre en un error frecuente, en este tipo de problemas. ¿Qué ocurre si el valor j no se encuentra en ningún campo i1 de la lista apuntada por p?. Cuando p tome valor nulo, intentará leer p->i1 en las primeras direcciones de memoria, las cuales suelen pertenecer a un segmento del sistema operativo. Lo más seguro que la ejecución del proceso aborte debido a un error de segmentación. Se podría corregir, cambiando: while( p->i1 != j ) p = p->next; por:

while ((p != NULL)&&( p->i1 != j )) p = p->next;

Lo cual funciona debido a que el and opera con cortocircuito.

Profesor Leopoldo Silva Bijit

20-01-2010

20

Estructuras de Datos y Algoritmos

e) En primer término imprime el campo i1 del último nodo de la lista1. Luego el campo i2 del último nodo de la lista2. Finalmente el campo i2 de la lista 2, cuyo campo i1 es 4; ya que en la lista1, el campo i2 es 4, cuando el campo i1 es 3. Imprimiría: 0 -1 0 P2.2. Escribir una función: int btoi(char *str, int *pvalor) que convierta un string binario pasado en str (Ej. "110101") a un entero a ser retornado en pvalor (Ej. 53). La función retorna 0 si no hay error y retorna -1 si el string binario tiene un carácter que no es '0' o '1'. Nota: 1101 (en binario) = 1x23+1x22+0x21+1x20 = 8 + 4 + 1 = 13 en decimal /* Uso de la funcion */ #include #include #include int btoi(char *str, int *pvalor); main() { int valor=0; char str[10]; strcpy(str, "110101"); if( !btoi(str, &valor) ) printf("string binario: %s, int:%d\n", str, valor); } Solución. int btoi(char *str, int *pvalor) { int i=0, largo=0, temp=0; largo = strlen(str) - 1; //índice del dígito menos significativo while(i =0) { if (*(str + i) == '1') { temp += pot; printf(" %d %d \n",temp, pot);} else if (*(str + i) == '0') ; else return -1; //no es 1 ó 0 i--;pot*=2; } *pvalor = temp; return 0; } P2.3. Se tiene la siguiente función: char *f1(char *s, int c) { while( *s ) { if( *s == (char) c ) return (char *) s; s++; } return (char *) 0; } a) Explicar los cast que se emplean y su necesidad. b) Qué realiza la función. c) Si se tiene char *string="12345678"; explicar que despliega: printf("%s\n", f1(string, '3')) ; Solución. El cast (char) c se emplea, debido a que el segundo argumento de la función es de tipo entero, para convertirlo a carácter y efectuar la comparación con un carácter del string. No es necesario, ya que por defecto, los valores de tipo carácter son promovidos automáticamente a enteros con signo. Por ejemplo se puede pasar equivalentemente el valor 65 ó 0x45 ó „A‟. Esto permite pasar caracteres de control que no son imprimibles, como argumentos. La comparación también se podía haber explicado según: ( (int) *s == c ). Es preferible usar cast, de tal modo de comparar valores de igual tipo. El cast en return (char *) s; no es necesario, ya que s es de tipo puntero a char. Profesor Leopoldo Silva Bijit

20-01-2010

22

Estructuras de Datos y Algoritmos

El cast return (char *) 0; es necesario para retornar un puntero nulo a carácter. b) Revisa y encuentra la primera ocurrencia del carácter (char) c, en el string apuntado por s; retornado un puntero al carácter de s que es igual a (char) c. Si el string es nulo, retorna un puntero nulo a carácter; también si no encuentra (char) c en el string. c) Despliega el string: 345678, seguido de un terminador de línea, ya que el llamado f1(string, '3') retorna un puntero al string “345678". P2.4. Se tiene la siguiente función: int f2(char *s1, char *s2) { while( *s1++ == *s2 ) if( *s2++ == '\0' ) return(1); return(0); } a) Explicar que realiza la función. Indicando las condiciones en las que retorna un cero o un uno b) Dar un ejemplo de uso. Definiendo las variables que sean necesarias. Solución. a) Compara dos strings. Retorna 1 sólo si los strings son iguales. Reconoce la igualdad de dos strings nulos. Retorna cero, si los strings son diferentes. Si los caracteres, en la misma posición, de s1 y s2 son iguales va recorriendo ambos strings. Si los primeros caracteres de los strings fuesen iguales, retorna un cero si string s1 es más corto que el string s2 (ya que no se cumple la condición del while); lo mismo sucede si string 1 es más largo que el string s2. b) char *s1="12345678"; char *s2="12345"; if ( f2(s1,s2)==0) printf("no son iguales\n"); else printf("son iguales\n"); P2.5. Se tiene la estructura para un nodo, con clave de tipo entera y tres punteros a nodo.

clave p1

p2

p3

a) Definir los tipos: nodo y pnodo (puntero a nodo). b) Diseñar, empleando malloc, la función con prototipo: pnodo creanodo(int clave); que solicita espacio e inicializa el nodo con punteros nulos y la clave del nodo con el valor del argumento. c) Si se tiene la siguiente definición: pnodo pn; dibujar un diagrama con los datos, luego de ejecutada la secuencia: Profesor Leopoldo Silva Bijit

20-01-2010

Definición de Estructuras de Datos en C.

23

pn=creanodo(5); pn->p3=pn; pn->p1=creanodo(3); pn->p1->p3=pn; pn->p2=creanodo(8); pn->p2->p3=pn->p1;

d) Escribir el segmento que forma el siguiente diagrama: pn

4 p1

6 p2

p3

p1

p2

p3

Figura P2.6. Solución. a) typedef struct moldenodo { int clave; struct moldenodo *p1; struct moldenodo *p2; struct moldenodo *p3; } nodo , *pnodo; b) pnodo creanodo(int clave) { pnodo p; if ((p = (pnodo) malloc(sizeof(nodo))) == NULL) { printf ("Memoria insuficiente para crear nodo\n"); exit(1); } p->clave=clave;p->p2=NULL;p->p1=NULL;p->p3=NULL; return(p); } c) Los diagramas se ilustran después de ejecutada la instrucción. Profesor Leopoldo Silva Bijit

20-01-2010

24

Estructuras de Datos y Algoritmos pn=creanodo(5); pn 5

Figura P2.7. pn->p3=pn; pn 5

Figura P2.8. pn->p1=creanodo(3);

pn 5

3

Figura P2.9. pn->p1->p3=pn; pn 5

3

Figura P2.10.

Profesor Leopoldo Silva Bijit

20-01-2010

Definición de Estructuras de Datos en C.

25

pn->p2=creanodo(8); pn 5

3

8

Figura P2.11. pn->p2->p3=pn->p1; pn 5

3

8

Figura P2.12. c) pn= creanodo(6); pn->p2=pn; pn->p3=pn; pn->p1=creanodo(4); pn->p1->p1=pn->p1; pn->p1->p3=pn; pn->p1->p2=pn;

Profesor Leopoldo Silva Bijit

20-01-2010

26

Estructuras de Datos y Algoritmos

pn

4 p1

6 p2

p3

p1

p2

p3

Figura P2.13. P2.6. Se tiene el siguiente programa. #include typedef struct nn { int x; struct nn * p; struct nn * q; int y; } t, *pt; t w, z; pt px=&w; void main(void) { px->p=&z; w.q = px->p; px->q->q=px; z.p = w.p; w.x = z.x = 2; (*px).y = 8; (*(w.q)).y =9; px=(pt) malloc(sizeof(t)); px->p=px->q = (pt ) 0; px->x=px->y=12; } Efectuar un diagrama de los datos después de ejecutar las instrucciones de main. Solución. Profesor Leopoldo Silva Bijit

20-01-2010

Definición de Estructuras de Datos en C.

27

Antes de main, el espacio de variables puede visualizarse según:

px w z

x

x p

p q

q

y

y

Figura P2.13.

px w x p

px->p =&z

q

w.q=px->p;

y

z x p

q

y

Figura P2.14.

Profesor Leopoldo Silva Bijit

20-01-2010

28

Estructuras de Datos y Algoritmos

px w x p

q

y

px->q->q=px z x

z.p=w.p

p

q

y

Figura P2.15.

px w x

2

p

w.x=z.x=2

q

y

8

(*px).y=8;

z x 2 p

q

(*(w.q)).y=9 y

9

Figura P2.16.

Profesor Leopoldo Silva Bijit

20-01-2010

Definición de Estructuras de Datos en C.

29

px

px =(pt)malloc(sizeof(t));

w x

2

p x

12

p y

y

q 8

q z

12 x 2

px ->p=px->q=(pt)0; p y

q 9

px ->x=px->y=12;

Figura P2.17.

Ejercicios propuestos. E1. Determinar qué imprimen los siguientes segmentos: a ) printf(“\n%o %x %d”, 17, 017, 0x17) ; b) n = 3 ; printf(“-05d %5d”, n, n) ; c) x = 1234E-2 ; printf(“%6.3f”, x) ; d) j =2; if ( ( '1' -1 ) == --j ) printf("verdad"); else printf("falso"); E2. Colocar paréntesis y evaluar las expresiones siguientes: Si es preciso puede indicar los resultados de expresiones intermedias. a) a != b && c + 1 == ! c + 2 con a1) a=2 ; b=3 ; c = 1; a2) a=3 ; b=2 ; c=2 ; b) 1 + 2 * ( n += 8) / 4 con n=3 ; c) a < b ? a < b ? a+1 : a+2 : a+3 con a=2 ; b= 3 ;

Profesor Leopoldo Silva Bijit

20-01-2010

30

Estructuras de Datos y Algoritmos

E3. Se tiene el siguiente programa: Qué efectúa la función, indicar tipo de parámetros. Escribir el prototipo y dónde debe ubicarse en el programa. Qué escribe el programa principal. void main() { int i=11, j ; j = funcion( i++, 5) ; printf(“\n%d %d”, j, i); j = funcion( j+i, j-3) ; printf(“\n%d %d”, j, i); } int funcion( int x, int y) { int s,t ; for( s=0 ; x != 0 ; x--) for ( t=0 ; t != y ; s++,t++) ; return( s ) ; } E4. Escribir programa. a) Que genere los primeros 20 números de la secuencia: 1, 4, 7, 10, 14, .... b) Que genere b elementos de la secuencia a partir del a-ésimo. Leer a y b. E5. Indicar que escribe el programa. #include int func(int *, float *, char); void show(); float f1=1, f2=2.2; int i1=2, i2; void main() { i2 = func(&i1, &f2, '1'); show(); i1 = func(&i2, &f1, '2'); show(); for(;;); } void show() { printf("\ni1= %d i2= %d" ,i1,i2); printf("\nf1= %f f2= %f",f1, f2); } int func(int *i, float *f, char ch) { *f = (float)(*i+2); *i = (int)(*f)+2; printf("\n%c ", ch); return(*i+2); }

Profesor Leopoldo Silva Bijit

20-01-2010

Definición de Estructuras de Datos en C.

31

E6. Indicar qué imprime el programa. #include int a[5]; int i; void arreglo(int j){ for(i=0;i1); i = (i&0x7fff); } void prt(int i) { int j; for (j=15; j>=0; j--)(1p.x ); printf(“%d \n “, *(pi-1)) ; pi = &m2.a[0]; printf(%d \n “, *(pi+1)); } E10. Determinar la salida. #include int f2(int x, int y, int z) {int i; for(i=0; i=1;(*q)>>=1;if(k) *q=(*q)|0x8000; else *q=(*q)&0x7fff; s=m; } E14. Describir un multiárbol Mediante un arreglo de listas de los hijos de cada nodo. El arreglo debe tener una entrada por cada nodo, además considerar que la raíz pueda se cualquier nodo.

Profesor Leopoldo Silva Bijit

20-01-2010

Definición de Estructuras de Datos en C.

35

Índice general. CAPÍTULO 2. ............................................................................................................................................ 1 DEFINICIÓN DE ESTRUCTURAS DE DATOS EN C......................................................................... 1 2.1. TIPOS PRIMITIVOS. ............................................................................................................................. 1 2.2. MECANISMOS DE ESTRUCTURACIÓN. ................................................................................................. 1 2.2.1. Grupos básicos. ......................................................................................................................... 1 2.2.2. Vínculos. .................................................................................................................................... 2 2.3. EJEMPLOS BASADOS EN ARREGLOS. ................................................................................................... 3 2.3.1. Acceso a componentes del arreglo. ........................................................................................... 3 Definición de matrices. .................................................................................................................................... 4 Definición de arreglo de arreglos. .................................................................................................................... 5 Arreglo de punteros a renglones. ..................................................................................................................... 5 Arreglo de punteros a caracteres. ..................................................................................................................... 6

2.3.2. Lista simplemente enlazada en base a cursores. ....................................................................... 6 2.4. EJEMPLOS BASADOS EN ESTRUCTURAS. ............................................................................................. 7 2.4.1. Estructura para fecha. ............................................................................................................... 7 2.4.2. Lista simplemente enlazada en base a punteros. ....................................................................... 9 2.5. ESTRUCTURAS MÁS COMPLEJAS....................................................................................................... 10 2.5.1. Arreglo de listas. ..................................................................................................................... 10 2.5.2. Arreglo de estructuras. ............................................................................................................ 11 2.5.3. Multiárboles. ........................................................................................................................... 11 2.5.3.1. Descripción mediante punteros. ........................................................................................................ 12 2.5.3.2. Descripción mediante arreglos de cursores. ...................................................................................... 12 2.5.3.3. Descripción por arreglo de padres. .................................................................................................... 13

2.6. UN EJEMPLO REAL DE ESTRUCTURAS. .............................................................................................. 14 PROBLEMAS RESUELTOS. ........................................................................................................................ 15 P2.1. Se tiene el siguiente programa: ............................................................................................... 15 P2.2. Escribir una función: ............................................................................................................... 20 P2.3. Se tiene la siguiente función: ................................................................................................... 21 P2.4. Se tiene la siguiente función: ................................................................................................... 22 P2.5. Se tiene la estructura para un nodo, ........................................................................................ 22 P2.6. Se tiene el siguiente programa. ................................................................................................ 26 EJERCICIOS PROPUESTOS. ....................................................................................................................... 29 E1. Determinar qué imprimen los siguientes segmentos: ................................................................ 29 E2. Colocar paréntesis y evaluar las expresiones siguientes: ........................................................... 29 E3. Se tiene el siguiente programa: .................................................................................................. 30 E4. Escribir programa. ..................................................................................................................... 30 E5. Indicar que escribe el programa. ................................................................................................ 30 E6. Indicar qué imprime el programa. ............................................................................................. 31 E7. Indicar qué imprime el programa. .............................................................................................. 31 E8. Indicar qué imprime el programa. .............................................................................................. 31 E9. Indicar qué escribe el programa. ................................................................................................ 32 E10. Determinar la salida. ................................................................................................................ 32 E11. Determinar la salida. ................................................................................................................ 33 E12. Determinar la salida. ................................................................................................................ 33

Profesor Leopoldo Silva Bijit

20-01-2010

36

Estructuras de Datos y Algoritmos E13. Explicar que realizan las funciones. ..........................................................................................34 E14. Describir un multiárbol .............................................................................................................34 ÍNDICE GENERAL. ....................................................................................................................................35 ÍNDICE DE FIGURAS. ................................................................................................................................36

Índice de figuras. FIGURA 2.1. AGRUPACIONES DE DATOS. ........................................................................................................2 FIGURA 2.2. VÍNCULOS ENTRE COMPONENTES DE DATOS. ............................................................................2 FIGURA 2.2.A. MATRIZ DE CARACTERES ......................................................................................................4 FIGURA 2.2.B. ARREGLO DE PUNTEROS A ARREGLOS DE CARACTERES ........................................................5 FIGURA 2.3. LISTA SIMPLEMENTE ENLAZADA................................................................................................7 FIGURA 2.4. LISTA SIMPLEMENTE ENLAZADA, MEDIANTE PUNTEROS. ...........................................................9 FIGURA 2.5. ARREGLO DE LISTAS. ...............................................................................................................10 FIGURA 2.6. MULTIÁRBOL. ..........................................................................................................................11 FIGURA 2.7. PRIMER DESCENDIENTE IZQUIERDO, HERMANO DERECHO. .......................................................12 FIGURA 2.8. MULTIÁRBOL MEDIANTE ARREGLO DE CURSORES. ..................................................................13 FIGURA 2.9. MULTIÁRBOL MEDIANTE ARREGLO DE PADRES........................................................................14 FIGURA 2.10 ARREGLO DE PADRES. .............................................................................................................14 FIGURA P2.1. ...............................................................................................................................................17 FIGURA P2.2. ...............................................................................................................................................17 FIGURA P2.3 ................................................................................................................................................18 FIGURA P2.4 ................................................................................................................................................18 FIGURA P2.5. ...............................................................................................................................................19 FIGURA P2.6. ...............................................................................................................................................23 FIGURA P2.7. ...............................................................................................................................................24 FIGURA P2.8. ...............................................................................................................................................24 FIGURA P2.9. ...............................................................................................................................................24 FIGURA P2.10. .............................................................................................................................................24 FIGURA P2.11. .............................................................................................................................................25 FIGURA P2.12. .............................................................................................................................................25 FIGURA P2.13. .............................................................................................................................................26 FIGURA P2.13. .............................................................................................................................................27 FIGURA P2.14. .............................................................................................................................................27 FIGURA P2.15. .............................................................................................................................................28 FIGURA P2.16. .............................................................................................................................................28 FIGURA P2.17. .............................................................................................................................................29

Profesor Leopoldo Silva Bijit

20-01-2010