Date post: | 02-Feb-2016 |
Category: |
Documents |
Upload: | carmelo-cordoba-fidalgo |
View: | 219 times |
Download: | 0 times |
Introducción
Estructuras de datos
PROPÓSITO DEL CURSO
Estudiar las estructuras de datos básicas utilizadas en la resolución de problemas de cómputo.
Utilizar algoritmos recursivos como una técnica de control de flujo en la solución de problemas.
Conocer y utilizar las técnicas de ordenación más comunes.
Utilizar las estructuras y algoritmos estudiados para elaborar un proyecto de programación.
TemarioUNIDAD 1: INTRODUCCION A LAS ESTRUCTURAS DE DATOSDEFINICIÓN DE TIPO DE DATOSTIPOS DE DATOS ABSTRACTOSTIPOS DE DATOS EN C
UNIDAD 2: PILASDEFINICIÓN Y REPRESENTACIÓN DE PILASAPLICACIONES
UNIDAD 3: RECURSIÓNDEFINICIÓN DE FUNCIONES RECURSIVASAPLICACIONES DE LA RECURSIÓN
UNIDAD 4: ESTRUCTURAS LINEALESDEFINICIÓN Y REPRESENTACIÓN DE LISTAS Y COLASAPLICACIONESDEFINICIÓN Y REPRESENTACIÓN DE LISTAS CIRCULARESAPLICACIONES
Temario cont.
UNIDAD 5: ÁRBOLESDEFINICIÓN Y REPRESENTACIÓN DE ÁRBOLES BINARIOSAPLICACIONESÁRBOLES GENERALESAPLICACIONES
UNIDAD 6: ORDENAMIENTO ALGORITMOS SIMPLES DE ORDENACIÓNALGORITMOS AVANZADOS DE ORDENACIÓN
UNIDAD 7: BUSQUEDA BÚSQUEDA LINEAL Y BINARIAHASH
Bibliografía
ESTRUCTURAS DE DATOS EN C. Aaron M. Tenenbaum y Moshe A. Augenstein, Prentice Hall.
ESTRUCTURA DE DATOS.Cairó y Guardati, Mc Graw Hill
ALGORITMOS Y ESTRUCTURAS DE DATOS. Nicklaus Wirth, Prentice Hall.
ALGORITMOS + ESTRUCTURAS DE DATOS = PROGRAMAS. Nicklaus Wirth, Prentice Hall.
Evaluación
La evaluación se realizará por lo menos con tres exámenes y/o proyectos, los cuales medirán principalmente la habilidad de aplicar cada uno de los elementos vistos en clase, codificando programas que resuelvan un problema particular, preferentemente con un enfoque orientado a objetos.
Forma de calificar: Exámenes Parciales 40 %Examen Final 20 %Prácticas 20 %Proyecto Final 20 %
•Cualquier significado puede ser asignado a un patrón de
bits en particular siempre y cuando sea hecho de forma
consistente.
•Es la interpretación del patrón de bits la que da el
significado.
•El método utilizado para interpretar un patrón de bits se
denomina TIPO DE DATO.
TIPOS DE DATOS
Un entero binario se representa como una secuencia de 1’s y 0’s. Ejemplos:00110100 = 0x28+0x27+1x26+1x25 +0x24+0x23+1x22+0x21+0x20 = 32 + 16 + 4 = 52Un entero negativo se puede representar en complemento de 1 o de 2. Ejemplo:
complemento de 1 complemento de 2-52= 11001011 11001100
En BCD cada dígito decimal se representa con 4 binarios. Ejemplo:
3478 = 0011 0100 0111 1000 3 4 7 8
ENTEROS BINARIOS Y DECIMALES
Los reales se representan en notación de punto flotante.Se utiliza una mantisa y una base elevada a un exponente. Usando 24 bits para la mantisa y 8 bits para el exponente, ambas en complemento de 2, tendríamos como ejemplo:
el número 387.53 = 38753 x 10–2, se representa por
38753 = 0000 0000 1001 0111 0110 0001(mantisa)–2 = 1111 1110 (exponente)
387.53 = 0000 0000 1001 0111 0110 0001 1111 1110
Note que el exponente es de la base 10.
NÚMEROS REALES
Otros ejemplos
0 0000 0000 0000 0000 0000 0000 0000 0000
100 0000 0000 0000 0000 0000 0001 0000 0010
0.5 0000 0000 0000 0000 0000 0101 1111 1111
0.000005 0000 0000 0000 0000 0000 0101 1111 1010
12000 0000 0000 0000 0000 0000 1100 0000 0011
-387.53 1111 1111 0110 1000 1001 1111 1111 1110
-12000 1111 1111 1111 1111 1111 0100 0000 0011
Límites
El mayor número representable en esta notación es
(223–1)x10127
El menor número representable en esta notación es
10–128
ActividadEscriba (si es posible) los siguientes números enteros como secuencias binarias de 8 y 16 bits.
105
–15
2748
Escriba los siguientes números reales como secuencias de bits usando 32 bits.
450.3 1.6x10–19
15x10–80 2.7182818284590
Un tipo de datos se puede implantar por hardware o por software.
Implantación por hardware es aquella en la que se construyen circuitos para realizar la operaciones.
Implantación por software es aquella en la que las operaciones se realizan mediante programas con instrucciones del hardware.
IMPLANTACIÓN DE DATOS
Implementación de cadenasSuponga la existencia en el hardware de la operación:
MOVER(fuente, destino, longitud)
Así también las operaciones aritméticas comunes y saltos normales.
Deseamos representar cadenas de longitud variable donde el primer carácter se la longitud de la cadena.
Haciendo uso de MOVER deseamos implementar la operación
MOVERVAR(fuente, destino)
Donde “fuente” designa la cadena que se moverá y “destino” el lugar donde se moverá.
MOVERVAR
MOVER(fuente, destino, 1);
for(i = 1; i<destino; i++)
MOVER(fuente[i], destino[i], 1)
var[i] denota la posición i-ésima a partir de var.
CONCATVAR
La operación CONCATVAR concatena dos cadenas.
4 H o l a
7 a t o d o s
11 H o l a a t o d o s
Código de CONCATVAR
z = c1 + c2;//mueve la longitud
MOVER(z, c3, 1);
for(i = 1; i<=c1; i++)//mueve primera cadena
MOVER(c1[i], c3[i], 1);
for(i = 1; i<=c2; i++){//mueve segunda cadena
x = c1 + i;
MOVER(c2[i], c3[x], 1);
}
Operación de CONCATVAR
4 H o l a
7 a t o d o s
11
c1
c2
c3 mueve la longitud
11
c3
H o l a
11
c3
H o l a a t o d o s
mueve primera cadena
mueve segunda cadena
Otra formaMOVERVAR(c2, c3[c1]);
MOVERVAR(c1, c3);
z = c1 + c2;
MOVER(z, c3, 1);
4 H o l a
7 a t o d o s
7
c1
c2
c3 MOVERVAR(c2,c3[c1])
c3
H o l a
11
c3
H o l a a t o d o s
MOVERVAR(c1,c3)
z = c1+c2;MOVER(z,c3,1);
c3[c1]
a t o d o s
a t o d o s
Cadenas terminadas en nulo
En C las cadenas se terminan por un nulo (‘\0’).
La implementación de MOVERVAR es en ese caso:
i = 0;
while(fuente[i]){
MOVER(fuente[i],destino[i],1);
i++;
}
La implementación de CONCATVAR es en ese caso:
i = 0;
while(c1[i]){//mover primera cadena
MOVER(c1[i],c3[i],1);
i++;
}
j = 0;
while(c2[j]){//mover segunda cadena
MOVER(c1[j++],c3[i++],1);
}
Tipos de datos abstractos ADTUn Tipo de Datos Abstracto (ADT) consta de dos partes:
Definición de valor
Definición de operador
Definición de valor: Definición de operador
Cláusula de definiciónEncabezado
Condición Precondiciones
Postcondiciones
Números racionales como ADT
/* definición de valores */
abstract typedef <integer, integer> RACIONAL;
condition RACIONAL[1] <> 0;
/* definición de operadores */
abstract RACIONAL makeRacional(int a, int b)
precondition b <> 0;
postcondition makeRacional[0] == a;
makeRacional[1] == b;
Números racionales como ADTcont.
abstract RACIONAL add(RACIONAL a, RACIONAL b)
postcondition add[1] == a[1]*b[1];
add[0] == a[0]*b[1]+a[1]*b[0];
/* written a+b */
abstract RACIONAL mult(RACIONAL a, RACIONAL b)
postcondition mult[0] == a[0]*b[0];
mult[1] == a[1]*b[1];
/* written a*b */
abstract equal(RACIONAL a, RACIONAL b)
postcondition equal == (a[0]*b[1] == a[1]*b[0]);
/* written a == b */
Secuencias como definición de valor
Una secuencia es un conjunto ordenado de elementos.
Se puede representar enumerando los elementos:
S = <s0, s1, …, sn–1>
Se definen funciones:
first(S) – primero de la secuencia S.
last(S) – último de la secuencia S.
Las secuencias de elementos de tipo tp se definen como
abstract typedef <<tp>> stp1;
Secuencias como definición de valor(cont.)
Enumerando los tipos de cada elemento:
abstract typedef <<tp1, tp2, ..,tpn>> stp2;
Secuencias con n elementos del mismo tipo se definen:
abstract typedef <<tp,n>> stp3;
Ejemplos
Secuencia de enteros de cualquier longitud.
abstract typedef <<integer>> intsec;
Secuencia de 3 elementos uno entero, uno real y uno carácter
abstract typedef <<integer,float,char>> stp3;
Secuencia de 10 enteros
abstract typedef <<integer,10>> intsec;
ADT para cadenas de longitud variable
abstract typedef <<char>> STRING;
abstract length(STRING s)
postcondition length = len(s);
abstract STRING concat(STRING s1, s2)
postcondition concat = s1 + s2;
abstract STRING substr(STRING s, int i,j)
precondition 0<=i<len(s);
0<=j<=len(s)-i;
postcondition substr = sub(s,i,j);
ADT para cadenas de longitud variable (cont.)
abstract pos(STRING s1, s2)
postcondition /* lastpos = len(s1)-len(s2)*/
((pos==-1)&&(for(i=0;i<lastpos;i++)
(s2<>sub(s1,i,len(s2)))))
||
((pos>=0)&&(pos<=lastpos)
&&(s==sub(s1,pos,len(s2)))
&&(for(i=1;i<pos;i++)
(s2<>sub(s1,i,len(s2)))))
El for es verdadero si se cumple para toda i o si el límite inferior es mayor que el superior.
TareaEscriba funciones en C que acepten dos cadenas de 0s y 1s que representen enteros binarios no negativos e imprima la cadena representando su suma y su producto, respectivamente.
Escriba una especificación de ADT para números complejos a + bi, donde abs(a + bi) es sqrt(a2 + b2), (a + bi) + (a + bi) es (a + c) + (b + d)i, (a + bi) * (a + bi) es (a*c – bd) + (ad + bc)i y –(a + bi) es (– a) + (–b) i
Tipos básicos en C
int - Enteros, pueden ser short (corto), long (largo) o usigned (sin signo). El tamaño real depende de la implementación.
float - números reales de 4 bytes.
char - caracteres de un byte.
double - reales de doble precisión.
Apuntadores - Un apuntador puede señalar a cualquier tipo de datos pero debe indicarse a que tipo señala.
Tamaño de los datos en CTipo Rangounsigned char 0 a 255char -128 a 127enum -32,768 a 32,767unsigned int 0 a 65,535short int -32,768 a 32,767int -32,768 a 32,767unsigned long 0 a 4,294,967,295Long -2,147,483,648 a 2,147,483,647float 3.4x10-38 a 3.4x10+38
double 1.7x10-308 a 1.7x10+308
long double 3.4x10-4932 a 1.1x10+4932
Estructuras de datos en C
Existen dos estructuras básicas en C:
arreglos – estructura homogenea
estructuras – estructuras heterogeneas.
Se pueden combinar libremente estructuras y arreglos para construir tipos de datos más complejos.
Arreglos en CDeclaración
tipo identificador[tamaño];
Ejemplo
int a[100];
Las dos operaciones básicas son la extracción y el almacenamiento.
Extracción – acepta una arreglo y un índice y regresa un elemento del arreglo: a[i]
Almacenamiento – acepta una arreglo, un índice y una variable x y asigna el valor de x a un elemento del arreglo: a[i] = x;
Los arreglos en C inician siempre con el subíndice 0.
Arreglos como ADTabstract typedef <<eltype, ub>> ARRTYPE(ub, eltype);
condition type(ub) == int;
abstract eltype extract(ARRTYPE(ub,eltype) a,int i);
/* written a[i] */
precondition 0<=i<ub;
postcondition extract ai;
abstract store(ARRTYPE(ub,eltype) a,int i,eltype elt);
/* written a[i] = elt */
precondition 0<=i<ub;
postcondition a[i] == elt;
Implantación de arreglos unidimensionales
La declaración
int b[100];
Reserva 100 localidades sucesivas en la memoria para almacenar cada una un valor entero.
Al elemento b[0] lo denominamos base(b). Si esize es el tamaño de un entero, entonces para localizar al alemento i-ésimo se calcula la dirección
base(b) + esize*i
En C se expresa por
b[i] o *(b + i)
Arreglos con elementos de tamaño variable
4 H o l a
7 a t o d o s
10 c o m e s t a n
10 c o m p u t a d o r
o
Arreglos con elementos de tamaño variable
\0H o l a
a t o d o s
c o m e s t a n
c o m p u t a d o r
\0
\0
\0
o
Arreglos con elementos de tamaño variable
4
7
H o l a
a t o d o s
c o m e s t a n
c o m p u t a d o r
o10
10
Cadenas en C
Las cadenas en C son secuencias de caracteres terminadas con el carácter nulo (‘\0’).
Las funciones para manipular cadenas se encuentran en la biblioteca strinh.h.
Algunas funciones de esta biblioteca se revisan a continuación.
int strlen(char s[])
int strlen(char s[]){
int i;
for(i = 0; s[i] != ‘\0’; i++);
return i;
}
int strpos(char s1[], char s2[])int strpos(char s1[], char s2[]){
int len1,len2,i,j1,j2;
len1 = strlen(s1); len2 = strlen(s2);
for(i = 0; i+len2<len1; i++);
for(j1=i,j2=0;j2<=len2&&s1[j1]==s2[j2];j1++,j2++)
if(j2==len2)
return i;
return -1;
}
int strcat(char s1[], char s2[])
int strcat(char s1[], char s2[]){
int i, j;
for(i = 0; s[i] != ‘\0’; i++);
for(j = 0; s[j] != ‘\0’; s1[i++]=s2[j++]);
}
int substr(char s1[], i, j, char s2[])
int substr(char s1[], int i, int j ,char s2[]){
int k, m;
for(k = i, m = 0; m<j; s2[m++] = s1[k++]);
s2[m] = ‘\0’;
}
Arreglos bidimensionales
Un arreglo bidimensional es un arreglo en el que los cada elemento es a su un arreglo.
La siguiente declaración en C, declara un arreglo de 6 elementos en donde cada elemento es a su vez un arreglo de 4 elementos:
int c[6][4];
La representación que se utiliza normalmente es la de renglón-mayor.
El primer renglón ocupa la primer tira de elementos, el segundo renglón la segunda, y así sucesivamente.
Renglón 0
Renglón 1Renglón 2Renglón 3
Renglón 4Renglón 5
Columna
0
Columna
1
Columna
2
Columna
3
A[0][0]
A[0][1]
A[0][2]
A[0][3]
A[1][0]
A[1][1]
A[1][2]
A[1][3]
A[2][0]
A[2][1]
A[2][2]
A[2][3]
A[3][0]
A[3][1]
A[3][2]
A[3][3]
A[4][0]
A[4][1]
A[4][2]
A[4][3]
A[5][0]
A[5][1]
A[5][2]
A[5][3]
Renglón 0{Renglón 1{
Renglón 2{Renglón 3{
Renglón 4{Renglón 5{
Cálculo de direcciónDada la declaración
ar[r1][r2]
La dirección de un elemento ar[i1][i2] se calcula mediante
base(a) + (i1*r2 + i2)*esize
Arreglos de más dimensiones se manejas de manera similar
EstructurasUna estructura identifica cada uno de los objetos que la forman mediante un identificador.
A cada objeto de le llama miembro de la estructura. En algunos lenguajes se les llama campos y a la estructura se le llama registro.
Declaración de estructuras en C
struct{
char first[10];
char midinit;
char last[20];
}sname, ename;
struct nametype{
char first[10];
char midinit;
char last[20];
};
struct nametype sname, ename;
La declaración define sname y ename como variables de estructura
Acceso a miembrosPara acceder a los miembros de una estructura se utiliza el operador punto.
printf(“%s”,sname.first);
ename.midinit = ‘M’;
for(i=0; i<20; i++)
sname.last[i] = ename.last[i];
Estructuras anidadasstruct addstype{
char straddr[40];
char city[10];
char state[2];
char zip[5];
};
struct nmadtype{
struct nametype name;
struct addrtype add;
};
nmadtype nmad1,nmad2;
nmad1.name.midini = nmad2.name.midini;
nmad2.add.city[4] = nmad1.name.first[1];
for(i = 1; i<10 ;i++)
nmad1.name. first[i] = nmad2.name. first[i];
Ejemplo: números racionales
#include <stdio.h>#include <conio.h>
struct racional{ int num, den;};
Los números racionales se pueden declarar como un estructura:
racional reduce(racional r){ racional s; int a,b,t; if(r.num>r.den){ a = r.num; b = r.den; } else { b = r.num; a = r.den; } while(b!=0){ t = a % b; a = b; b = t; } s.num = r.num / a; s.den = r.den / a; return s;}
Algoritmo de Euclides para reducir un racional
racional mult(racional a, racional b){ racional c; c.num = a.num*b.num; c.den = a.den*b.den; return reduce(c);}
racional divi(racional a, racional b){ racional c; c.num = a.num*b.den; c.den = a.den*b.num; return reduce(c);}
racional suma(racional a,racional b){ racional c; c.num = a.num*b.den+a.den*b.num; c.den = a.den*b.den; return reduce(c);}
racional resta(racional a,racional b){ racional c; c.num = a.num*b.den-a.den*b.num; c.den = a.den*b.den; return reduce(c);}
void imprime(racional a){ printf("%d/%d\n",a.num,a.den);}
UnionesUna unión es una estructura en la que una misma área de memoria se comparte entre varias variables.
union nombre{
tipo nombre1;
tipo nombre1;
...
};
Solo se puede acceder a una variable a la vez.
ejemplo
union prueba{ int a; double b; char c;};main(){ prueba x; x.a = 5; printf("a= %d, b= %f, c= %c\n",x.a,x.b,x.c); x.b = 5.0; printf("a= %d, b= %f, c= %c\n",x.a,x.b,x.c); x.c = '5'; printf("a= %d, b= %f, c= %c\n",x.a,x.b,x.c); getch();}
a= 5, b= 0.000000, c= ♣
a= 0, b= 5.000000, c=
a= 53, b= 5.000000, c= 5
Ejemplo 2
struct fecha{ int dia,mes,anyo;};struct persona{ char nombre[20],apellido[20]; fecha nacimiento; char sexo; union{ struct { float peso,estatura; }varon; struct { int medidas[3]; }hembra; };};
void escribePersona(persona p){ printf("nombre: %s %s\n",p.nombre,p.apellido); printf("fecha de nacimiento: %d/%d/%d\n", p.nacimiento.dia,p.nacimiento.mes,p.nacimiento.anyo); if(p.sexo=='H'){ printf("sexo: masculino\n"); printf("peso: %.1f, estatura: %.1f\n", p.varon.peso,p.varon.estatura); } else{ printf("sexo: femenino\n"); printf("medidas: %d, %d, %d\n",p.hembra.medidas[0], p.hembra.medidas[1],p.hembra.medidas[2]); }}
main(){ persona a = {"Juan","Perez",{3,4,1980},'H',80,1.83}, b = {"Luisa","Lane",{16,7,1990},'M',90,60}; escribePersona(a); escribePersona(b); b.hembra.medidas[0]=90; b.hembra.medidas[1]=60; b.hembra.medidas[2]=90; escribePersona(b); getch();}
nombre: Juan Perezfecha de nacimiento: 3/4/1980sexo: masculinopeso: 80.0, estatura: 1.8nombre: Luisa Lanefecha de nacimiento: 16/7/1990sexo: femeninomedidas: 1119092736, 1114636288, 0nombre: Luisa Lanefecha de nacimiento: 16/7/1990sexo: femeninomedidas: 90, 60, 90
Tipo coordenadastruct coordenada{
int tipo;
union {
struct{double x,y;}rect;
struct{double r,theta;}pol;
};
};a.rect.x - componente x de aa.rect.y - componente y de aa.pol.r - distancia al origen de aa.pol.theta - ángulo con eje x de a
Calculo de distancia#define CARTESIANA 0#define POLAR 1double distancia(coordenada a,coordenada b){ double d; switch(a.tipo){ case CARTESIANA:switch(b.tipo){ case CARTESIANA: d = sqrt((a.rect.x-b.rect.x)*(a.rect.x-b.rect.x)+ (a.rect.y-b.rect.y)*(a.rect.y-b.rect.y)); break; case POLAR: d = sqrt((a.rect.x-b.pol.r*cos(b.pol.theta))* (a.rect.x-b.pol.r*cos(b.pol.theta))+ (a.rect.y-b.pol.r*sin(b.pol.theta))* (a.rect.y-b.pol.r*sin(b.pol.theta))); break; }break;
case POLAR:switch(b.tipo){ case CARTESIANA: d = sqrt((a.pol.r*sin(a.pol.theta)-b.rect.x)* (a.pol.r*sin(a.pol.theta)-b.rect.x)+ (a.pol.r*cos(a.pol.theta)-b.rect.y)* (a.pol.r*cos(a.pol.theta)-b.rect.y)); break; case POLAR:d = sqrt(a.pol.r*a.pol.r+b.pol.r*b.pol.r- 2*a.pol.r*b.pol.r*cos(a.pol.theta-b.pol.theta)); break; } } return d;}
Enumeraciones
Para definir una enumeración se utiliza la palabra reservada enum.
C asigna enteros consecutivos (comenzando por 0) a los valores de las etiquetas a menos que se asignen valores explícitamente.
La sintaxis es la siguiente:
enum nombre {etiquetas};
ejemplo
#include <stdio.h>#include <conio.h>enum diaSemana {lunes, martes, miercoles, jueves, viernes,sabado, domingo};char dias[7][10] ={"lunes","martes","miercoles", "jueves","viernes","sabado","domingo"};main(){ diaSemana dia; do{ printf("Teclee el numero del dia (0 a 6): "); scanf("%d",&dia); }while(dia<lunes || dia>domingo); printf("El dia es: %s",dias[dia]); getch();}
#include <stdio.h>#include <conio.h>
/* enum para definir constantes de tipo entero */enum {SEC = 1, MIN = 60, HORA = 60*60, DIA = 24*60*60};
main(){ int segundos; printf("Escriba numero de segundos: "); scanf("%d",&segundos); printf("%d segundos = %d minutos = %d horas" " = %d dias\n", segundos, segundos/MIN, segundos/HORA, segundos/DIA); getch();}
enum escapes{BELL='\a', BACKSPACE='\b', HTAB='\t', RETURN = '\r', NEWLINE = '\n', VTAB = '\v' }; enum boolean { FALSE = 0, TRUE };
enum days {Jan=31, Feb=28, Mar=31, Apr=30, May=31, Jun=30, Jul=31, Aug=31, Sep=30, Oct=31, Nov=30, Dec=31};
tareaSe desea manejar la información de libros, revistas y películas. De los libros se quiere mantener la siguiente información: código, autor, título, editorial, año; de las revistas la siguiente información: código, nombre, mes, año; de las películas la siguiente información: código, título, director, productora, año. Declare estructuras para cada elemento de información. Luego declare una unión para representar los tres tipos de elementos. Declare un arreglo llamado tabla que contenga 100 elementos del tipo unión.
Escriba una función para desplegar la información de un elemento de la tabla del problema anterior, ya sea libro, revista o película.