Estructuras de Datos I - TDA Lista Implementación estatica Parte 1

Vista previa del material en texto

Estructuras de Datos I
Lista Implementación estática
Forma de arreglo (vector)
a
b
c
d
3
DATOS
ULTIMO
0
1
2
3
#define TAMAX 100
typedef _________ info;
typedef struct{
info datos[TAMAX];
int ultimo
} lista;
Lista
Lista
#define TAMAX 100
typedef alumno info;
typedef struct{
info datos[TAMAX];
int ultimo
} lista;
Int main(){
lista asistencias;
lista calificaciones;
asistencias.ultimo = 3;
printf(“Nombre es: ”, asistencia.datos[23].nombre.app);
}
Tipo de dato
Conjunto de valores
Conjunto de operaciones
Inicializa
DATOS
ULTIMO
0
1
2
3
Función: inicializa()
Recibe: lista vacía
Regresa: nada
Ultimo = -1
Función: inicializa()
Recibe: lista vacía
Regresa: nada
Ultimo = -1
#define TAMAX 100
typedef alumno info;
typedef struct{
info datos[TAMAX];
int ultimo
} lista;
Void inicializa(lista *Lista1){
Lista1->ultimo = -1;
}
Vacía
Función: vacia()
Recibe: lista
Regresa: booleano
¿ultimo == -1?
	Si: regresar verdadero
	No: regresar falso
int vacia(lista *Lista1){
if(Lista1->ultimo == -1){
	return VERDADERO;
}else{
	return FALSO
}
}
Función: vacia()
Recibe: lista
Regresa: booleano
¿ultimo == -1?
	Si: regresar verdadero
	No: regresar falso
#define VERDADERO 1
#define FALSO 0
Llena
Función: llena()
Recibe: lista
Regresa: booleano
¿ultimo == tamaño del arreglo - 1?
	Si: regresar verdadero
	No: regresar falso
int llena(lista *Lista1){
if(Lista1->ultimo == TAMAX - 1){
	return VERDADERO;
}else{
	return FALSO
}
}
Función: llena()
Recibe: lista
Regresa: booleano
¿ultimo == tamaño del arreglo - 1?
	Si: regresar verdadero
	No: regresar falso
Inserción
Existen dos tipos de inserción en una lista:
Dada una posición
Después de la posición dada
Inserción
a
b
c
d
3
DATOS
ULTIMO
0
1
2
3
w
NUEVO
2
Posición dada
Se debe considerar si la lista esta:
Llena
Posición dada es menor a 0
Posición es igual a la ultima posición del arreglo
4
5
6
n
…
Inserción
a
b
c
d
3
DATOS
ULTIMO
0
1
2
3
w
NUEVO
2
Posición dada
Posición aux
4
5
6
n
…
Inserción
a
b
c
d
3
DATOS
ULTIMO
0
1
2
3
w
NUEVO
2
Posición dada
4
Posición aux
Ultimo + 1
4
5
6
…
n
Inserción
a
b
c
d
3
DATOS
ULTIMO
0
1
2
3
w
NUEVO
2
Posición dada
4
Posición aux
4
5
6
…
n
d
aux - 1
Inserción
a
b
c
d
d
3
DATOS
ULTIMO
0
1
2
3
w
NUEVO
2
Posición dada
3
Posición aux - 1
4
5
6
…
n
c
aux - 1
Inserción
a
b
c
c
d
3
DATOS
ULTIMO
0
1
2
3
w
NUEVO
2
Posición dada
2
Posición aux - 1
4
5
6
…
n
Inserción
a
b
c
d
3
DATOS
ULTIMO
0
1
2
3
w
NUEVO
2
Posición dada
2
Posición aux - 1
4
5
6
…
n
Inserción
a
b
w
c
d
3
DATOS
ULTIMO
0
1
2
3
w
NUEVO
2
Posición dada
4
5
6
…
n
Inserción
a
b
w
c
d
4
DATOS
ULTIMO = ULTIMO + 1
0
1
2
3
w
NUEVO
2
Posición dada
4
5
6
…
n
Inserción dada una posición
Función: inserta()
Recibe: elemento, posición, lista
Regresa: nada
¿llena(lista) o posición < 0 o posición > ultimo + 1?
	Si: Mandar mensaje de error y 	terminar
aux = ultimo + 1
MIENTRAS aux > posición
	datos[aux] = datos[aux -1]
	aux = aux – 1;
Fin MIENTRAS
Datos[posicion] = elemento;
ultimo = ultimo + 1;
Función: inserta()
Recibe: elemento, posición, lista
Regresa: nada
¿llena(lista) o posición < 0 o ultimo + 1?
	Si: Mandar mensaje de error y 	terminar
aux = ultimo + 1
MIENTRAS aux > posición
	datos[aux] = datos[aux -1]
	aux = aux – 1;
Fin MIENTRAS
Datos[posicion] = elemento;
ultimo = ultimo + 1;
Void inserta(info elemento, int pos, list *Lista1){
Int aux;
If(llena(Lista1) || pos < 0 || pos > Lista1  ultimo + 1){
	return;
}
For(aux = Lista1ultimo + 1; aux > pos; aux--){
	Lista1Datos[aux] = Lista1Datos[aux - 1]; 
}
Lista1Datos[pos] = elemento;
Lista1ultimo++;
}