Programación 2

Links: University

Mejor estructura e implementación (1.5)

Jun 2021

• En el Servicio de Salud están recibiendo continuamente nuevas dosis de vacunas. Para evitar que caduquen es imprescindible que se usen primero las vacunas que han sido recibidas hace más tiempo. Qué estructura de datos debemos utilizar para gestionar el almacenamiento de las dosis?

• El Servicio de Salud desea enviar una carta al domicilio y un SMS al móvil de cada paciente a los que se va a administrar la vacuna para recordarle el lugar y la hora en que debe presentarde. Qué estructura de datos debemos utilizar para que podamos recuperar rápidamente esta información a partir del número de la tarjeta sanitaria?

• Para garantizar la distancia interpersonal durante los exámenes, la Facultad ha asignado varias aulas al examen de cada asignatura. Cada aula tiene una capacidad máxima y los extudiantes elegirán en una web el aula en la que van a hacer el examen (de entre aquellas en las que queden sitios libres). Antes de un examen queremos obtener el listado de los estudiantes, ordenado alfabéticamente por nombre, que se han asignado a cada aula. Qué estructura de datos debemos utilizar par a gestionar este listado?

Soluciones

• Una cola para que se usen primero las primeras dosis en llegar, dinámica porque no conocemos el número de dosis, si tuvieramos un límite de stock que podemos almacenar, entonces podría ser estática.

• Un AVL con clave el número de tarjeta que es la estructura más rapida para búsquedas, dinámico porque el número de pacientes varía en el tiempo.

• Una multilista, la primera será una lista estática con las aulas, y la segunda una lista ordenada por el nombre de los alumnos, estática con el número máximo de sitios.

JUL

• Un grupo de individuos con mochila decide competir con Spotify e implementar un buscador de música, de tal forma que a partir del nombre artístico de un grupo o solista, nos proporcione toda su información. Qué estructura sería la más adecuada para buscar eficientemente esta información?

• Una editorial desea editar una guia de los distintos vinos españoles, organizada por denominación de origen (Rioja, ribera del Duero, Rías Baizas, etc.) En cada categoría aparecerá una lista de los vinos que poseen dicha denominación. Cuál es la estructura más adecuada para almacenar esta información?

• La salida al mercado de la autobiografía de Belén Esteban ha dado lugar a que una conocida librería tenga un número exagerado de reservas del mismo. Qué estructura sería más adecuada para almacenar las reservas de los clientes de la librería si se quieren atender por orden de petición?

Soluciones

• Un AVL con el nombre del artista como clave. Implementación dinámica porque no sabemos cuantos artistas hay.

• Una multilista, donde la primera será una lista con las denominaciones, estática porque asumimos que hay un número limitado de ellas. Y una lista dinámica con los vinos de cada denominación.

• Una cola para servir las reservas por orden, dinámica porque no sabemos cuantas reservas podemos tener.

JUN

• Una empresa quiere montar un servicio de cafetería en el que se sirva preferentemente café aunque también dispondrá de té, bebidas gaseadas y zumos naturales. Para manter esta política, los camareros servirán primero a los clientes que hayan pedido café, según vayan llegando, y después a los clientes que hayan pedido te, bebidas gaseadas y zupo, en ese orden. Qué estructura sería la más adecuada para gestionar las peticiones de los clientes?

• Un conocido centro comercial ha decidido que a la hora de cancelar el alquiler de sus locales lo hará de aquellos que lleven menos tiempo ocupados. Qué estructura sería la más adecuada para determinar qué local debe ser desalojado en cada momento?

• Un diseñador de complementos decide ofrecer la posibilidad a sus clientas de comprar zapatos y bolsos de forma combinada. Para ello decide contratar el diseño de una aplicación que permita visualizar todos sus modelos de zapatos y para cada par de zapatos, la lista de bolsos con los que mejor combina. La estructura deberá permitir que las clientas avancen o retrocedan tanto en la lista de bolsos como en cada lista de zapatos. Qué esturctura sería la más adecuada para diseñar esta aplicación?

Soluciones

• Una cola de prioridad donde la prioridad vendría definidad por el tipo de bebida pedida. Al no haber número de clientes fijo la implementación más adecuada sería una lista estática de 4 elementos (tipos de bebidad) de colas dinámicas, para los clientes que pidan cada una de las bebidas.

• Una pila ya que de esta forma el local que menos tiempo lleve ocupado será el primero. Su implementación será estática ya que el número de locales en principio no debería variar.

  • Una multilista ambas doblemente enlazadas. El primer nivel de la multilista almacenaría los zapatos, y el segundo nivel los bolsos a juego. El doble enlace no permitirá acceder al elemento anterior y siguiente. La implementación será dinámica ya que no conocemos el número de elementos.

JUN_b

• Instante, conocido servicio de mensajería rápida, desea premiar la fidelidad de sus clientes repartiendo mensualmente puntos en función del número de envíos que haga con la compañia. Así tendrá caracterizado el tipo de cliente (vip, habitual o potencial) que podrá canjear dichos puntos por diferentes servicios. El sistema de información de la empresa necesita acceder eficientemente a los datos del cliente minimizando tiempo y recursos del proceso de búsqueda.

• Anticuarius es una nueva casa de subastas online. Pronto dispondrán de un portal web donde el ususario podrá consultar el horario en que se subastará cada pieza de arte así como los precios de salida. Qué estructura única permitiría buscar la puja, la más cara, o n-ésima según el horario de la subasta?

• Para la puja necesitará una estructura de datos reutilizable que almacene las sucesivas ofertas por pieza subastada. Cada puja debe superar la última realizada. Al finalizar el tiempo se contacta con el usuario que hubiera hecho la puja más alta. Si no respondiera con el siguiente, y así hasta encontrar una respuesta o dar la puja por desieta. Las restricciones de tiempo obligan a procesar no más de 300 solicitudes.

Soluciones

• Un AVL, es la estructura con la búsqueda más eficiente. Implementación dinámica porque no sabemos cuantos usuarios hay, y no querriamos limitar el número de ellos tampoco.

• Una lista multienlazada con dos criterios de orden, precio y horario, implementación dinámica porque no tenemos un límite de subastas.
  También podría ser una multilista compuesta por una lista estática con las franjas horarias y una lista dinámica con las piezas ordenadas por precio para cada franja horaria.

• Una pila estática con 300 elementos, donde solo añades un elemento a la pila si supera el precio de la cima actual.

Dic 2006

• Una empresa de seguridad necesita implementar un programa de monitorización cíclica de cámaras de videovigilancia que dado un conjunto de identificadores de cámaras, se conecte durante toda la noche a cada una de ellas en secuencia para mostrar su imagen durante breves instantes. La secuencia de cámaras debe ser siempre la misma, para no despistar a los agentes de la sala de control. Qué estructura de datos debe utilizarse para almacenar los identificadores de las cámaras y saber cuál de ellas se debe mostrar en cada momento?

• Una empresa de reparto de empanadas a domicilio precisa ampliar su sitema informático con un programa que asigne cada nuevo pedido al motorista que lleva más tiempo desocupado. Normalmente hay 10 motoristas trabajando, pero los fines de semana y los días en que se retrasmite fútbol por la televixión se cuenta con más personal. Además cada vez que un motorista regresa a la empresa después de servir un pedido, introduce su identificador en el sistema informático para indicar que ha quedado libre. Qué estructura de datos utilizaremos para almacenar los identificadores de los motoristas disponibles?

• Un popular programa de televisión pretende realizar un sorteo utilizando el siquiente método: un notario proporcionará un listado con los números de teléfono de aquellos telespectadores que se han apuntado al sorteo. de entre esos números se elegirá uno al azar y se llamará. Si responde corretamente a una pregunta, se le asignará el premio; en caso contrario, se repetirá el proceseo con el número anterior del listado, con el siquiente, con el anterior del anterior, con el siquiente del siqueinte, y así sucesivamente hasta que alguien responda correctament o se termine el listado. Qué estructura de datos debemos utilizar para almacenar los números de teléfono?

Soluciones

• Una cola circular, estática porque conocemos el número de cámaras, y no varía

• Una cola, dinámica porque el número de motoristas puede variar. Cada vez que un motorista sale a repartir, lo eliminamos, y cuando vuelve se añade de nuevo.

• Una lista doblemente enlazada, dinámica porque no conocemos cuanta gente va a participar

Verdadero/Falso (1)

• En el TAD Cola los elementos se organizan de forma circular

  FALSO Pueden, pero no es necesariamente la única forma de implementar una cola

• En una implementación dinámica de las listas es imposible tener acceso eficiente al último elemento de la lista

  FALSO Con una implementación circular tenemos acceso eficiente tanto al primer como al último elemento

• En una pila los elementos se extraen en orden inverso al de entrada

  VERDADERO Una pila sigue el orden LIFO (Last In First Out)

• Los árboles completos son árboles binarios de búsqueda equilibrados

  FALSO Un árbol completo no tiene porqué ser un árbol de búsqueda

• En la implementación de una operación se debe incluir código que controle el cumplimeinto de las precondiciones de su especificación

  FALSO Las precondiciones son un contrato con el usuario de la función, el programador asume que se van a cumplir

• Una cola de prioridad implementada con una única lista ordenada por prioridad siempre tiene que ser implementada de forma estática

  FALSO Si queremos tener una cola de tamaño variable podemos implementarla dinámicamente

• El TAD Lista puede funcionar como un TAD Pila

  VERDADERO Si solo introducimos y borramos elementos desde un extremo de la lista

• Un árbol binario completo con tres niveles contiene como máximo 6 nodos

  FALSO Contiene como máximo 7 nodos

• En la especificación de una operación, las poscondiciones indican lo que ocurre si no se cumplen las precondiciones.

  FALSO Las poscondiciones indican lo que ocurre si la función se ejecuta bien

• Una cola de prioridad se comporta en ocasiones como una cola estándar

  VERDADERO Si todos los elementos tienen la misma prioridad

• Una multilista es una lista que debe permitir el recorrido ordenado de los elementos atendiendo a más de un criterio

  FALSO Eso sería una lista con dós criterios de ordenación, en una multilista cada elemento de la primera tiene asociada otra lista

• En un AVL, una eliminación puede obligar a realizar una rotación como máximo

  FALSO A diferencia de la inserción, la eliminación puede necesitar más de una rotación

• Las precondiciones establecen qué controles debemos efectuar sobre los valores de los parámetros de entrada de una operación para que ésta tenga éxito.

  VERDADERO Las precondiciones son un contrato entre el programador del TAD y el usuario, si no las cumplimos no se garantiza que funcionen

• Una cola de prioridad puede implementarse a partir de una lista ordenada

  VERDADERO Si usamos como criterio de ordenación la prioridad

• Una lista doblemente enlazada permite recorrer la lista en función de dos criterios de ordenación distintos

  FALSO Una lista doblemente enlazada permite recorrer la lista en dos sentidos

• Para que un árbol binario sea considerado árbol AVL, la condición suficiente que debe cumblir todo nodo N es que la diferencia de atura entre el subárbol derecho y el izquierdo de ese nodo no sea superior, en valor absoluto, a una unidad

  VERDADERO

• El único criterio para elegir una implementación estática o dinámica es el consumo de memoria previsto

  FALSO El borrado de elementos en una implementación estática es más lento, eso también es un criterio a tener en cuenta

• La eliminación de una clave en un árbol binario de búsqueda balanceado obliga siempre a realizar al menos una rotación

  FALSO Si el AVL estaba perfectamente balanceado no tiene porque hacer ninguna rotación

• Un recorrido inorden de un árbol AVL devuelve la secuencia ordenada de claves

  VERDADERO

• En la especificación de un operador de un TAD debe indicarse el algoritmo que se va a utilizar

  FALSO Debe especifircarse lo que realiza la función, pero no entrar en tanto detalle

• En una cola de prioridad, en un mismo momento, no puede haber dos elementos con la mismo prioridad

  FALSO Si hay más de un elemento con la misma prioridad se escoge el orden por otro criterio, como el orden de entrada

• En un AVL, una inserción puede obligar a realizar entre 0 y h rotaciones, donde h es la altura del árbol

  FALSO Una inserción necesitará máximo 1 rotación para quedar equilibrado

• En un árbol binario, cada nodo puede tener 0,1 ó 2 hijos

  VERDADERO

• En una cola de prioridades el primer dato que entra es el primero que sale, ya que sique una disciplina FIFO

  FALSO El primer dato que sale será el de mayor prioridad indeperdientemente del orden de entrada

• El orden en el que se han insertado los datos en un árbol binario de búsqueda afectará a la eficiencia de las operaciones de búsqueda que se realicen sobre él

  VERDADERO Si insertamos por ejemplo por orden ascendente nos quedará un árbol degenerado. Esto se solventa con un AVL

• Los árboles AVL basan su eficiencia en el hecho de que tienen la forma de un árbol completo

  FALSO tienen la forma de un arbol lleno no necesariamente de un árbol completo

Identifica errores (0.75)

Para identificar errores la mejor forma es siguiendo paso a paso lo que hace la función,
posiblemente apuntar los datos que va guardando

Errores comunes

• Problemas de * y & en punteros
• Problemas con malloc y free (no se reselva memoria o se borra mal)
• Enlaza mal los punteros en una lista

Ejemplo

#include <stdio.h>
#include <stdlib.h>
 
typedef struct tNode* tPosL;
struct tNode{
    int datum;
    tPosL next;
};
 
void corrects (int max, tPosL L){
    tPosL i; //struct tNode i;
    for(i=L; i!=NULL; i=i->next){
        if(i->datum > max)
            i->datum = max;
        printf("%d ", i->datum);
    }
}
 
int main(){
    tPosL q, L;
    L = malloc(sizeof(struct tNode));
    printf("Typed first value: "); scanf("%d", &L->datum);
    //q = malloc(sizeof(struct tNode));
    q = L;
    for(int i=2; i<=10; i++){
        q->next = malloc(sizeof(struct tNode));
        q = q->next;
        printf("Typed first value: "); scanf("%d", &q->datum);
    }
    q->next = NULL;
    corrects(5,L); //corrects(5,&L);
...
 
}
 

Arboles Binarios de búsqueda (1.25)

Determina y ejecuta una función

identifica recorrido

  a
 /  \\
b   c

/ \ / \
d e g h
/ / \
f j k
/
l

Preorden

a b d e f c g h j l k

• raiz, izquierda, derecha

Posorden

d b f e a g c l j h k

• izquierda, derecha, raiz

Inorden

d f e b g l j k h c a

• izquierda, raiz, derecha

Anchura

a b c d e g h f j k l

• por filas

aplica función de recorrido

modifica AVL

Rotaciones simples

• LL

   c            b
  /             /  \\
  

  b a c
  /
  a

• RR

  a b
  \ / \
  b a c
  \
  c

Rotaciones complejas

• LR

  c            b
  

  / / \
  a a c
  \
  b

• RL

  a b
  \ / \
  c a c
  /
  b

Programar (5.5)

Implementa un TAD (3)

Cola circular estática

isEmpty
enqueue
dequeue

Lista estática ordenada

deleteAtPosition
findItem

Cola estática de 100 posiciones

isEmptyQueue
enqueue
dequeue

Cola estática de 10 posiciones

enqueue
front

Lista estática ordenada

isEmptyList
findItem
insertItem

Lista estática ordenada

createEmptyList
insertItem
deleteItem
findItem
size

Cola dinámica

createEmptyQueue
enqueue
dequeue
isEmptyQueue

Cola estática y dinámica

enqueue
dequeue

Lista dinámica ordenada

insertItem
deleteItem

Implementa una función para la práctica (2.5)

Estructuras de datos

Implementación estática

• Borrado lento
• Espacio limitado

Lista estatica

• Inserción rápida
• Busqueda lenta
• Borrado lento
• Tamaño limitado

#define LNULL -1
#define MAX 1000
 
typedef int tItemL;
typedef int tPosL;
 
typedef struct {
    tItemL data[MAX];
    tPosL lastPos;
} tList;
 
void createEmptyList(tList *L);
bool insertItem(tItemL d, tPosL p, tList *L);
tPosL findItem(tItemL d, tList L);
tItemL getItem(tPosL p, tList L);
void deleteAtPosition(tPosL p , tList *L);
bool isEmptyList(tList L);
 
void createEmptyList(tList *L){
  L->lastPos = LNULL;
}
 
bool insertItem(tItemL d, tPosL p, tList *L) {
  tPosL i;
 
  if (L->lastPos == MAX - 1) //Check if list is full
    return false;
  else {
    L->lastPos++;
    if (p == LNULL) { // Insert at the end
      L->data[L->lastPos] = d;
    } else {
      for (i = L->lastPos; i >= p + 1;i--) //moves elements
        L->data[i] = L->data[i - 1];
      L->data[p] = d;
    }
    return true;
  }
}
 
tPosL findItem(tItemL d, tList L) {
  tPosL p;
 
  if (isEmptyList(L)) {
    return LNULL;
  } else {
    for (p = 0; (p < L.lastPos) && (L.data[p] != d); p++) ;
 
    if (L.data[p] == d) {
      return p;
    } else
      return LNULL;
  }
}
 
tItemL getItem(tPosL p, tList L) {
  return L.data[p];
}
 
void deleteAtPosition(tPosL p, tList *L) {
  tPosL i;
 
  L->lastPos--;
  for (i = p; i <= L->lastPos; i++)
    L->data[i] = L->data[i + 1]; //Move elements
}
 
bool isEmptyList(tList L) {
  return L.lastPos == LNULL;
}

Pila estática

• Acceso rápido a la cima de la pila
• Acceso lento a cualquier otro elemento

#define SNULL -1
#define SMAX 10
 
typedef int tItemS;
typedef int tPosS;
 
typedef struct Stack{
  tItemS data[SMAX];
  tPosS top;
} tStack;
 
void createEmptyStack(tStack *S);
bool push(tItemS d, tStack *S);
void pop(tStack *S);
tItemS peek(tStack S);
bool isEmptyStack(tStack S);
 
void createEmptyStack(tStack *S){
  S->top = SNULL;
}
 
bool push(tItemS d, tStack *S){
  if(S->top == SMAX-1)
    return false;
  else {
    S->top++;
    S->data[S->top] = d;
    return true;
  }
}
 
void pop(tStack *S){
  S->top--;
}
 
tItemS peak(tStack S){
  return S.data[S.top];
}
 
bool isEmptyStack(tStack S){
  return (S.top == SNULL);
}

Cola estática (circular)

• Acceso rápido a el primer elemento
• Acceso lento a cualquier otro elemento

#define QMAX 10
 
typedef int tItemQ;
 
typedef struct Queue{
  tItemQ data[QMAX];
  int front, rear;
} tQueue;
 
void createEmptyQueue(tQueue *Q);
bool enqueue(tItemQ d, tQueue *Q);
void dequeue(tQueue *Q);
tItemS front(tQueue Q);
bool isEmptyQueue(tQueue Q);
 
void createEmptyQueue(tQueue *Q){
  Q->front = 0;
  Q->rear = QMAX -1
}
 
int addOne(int i){
  if(i == QMAX -1)
    return 0;
  else
    return ++i;
}
 
bool enqueue(tItemQ d, tQueue *Q){
  if(Q->front == addOne(addOne(Q->rear)))
    return false;
  else {
    Q->rear = addOne(Q->rear);
    Q->data[Q->rear] = d;
    return true;
  }
}
 
void dequeue(tQueue *Q){
  Q->front = addOne(Q->front);
}
 
tItemS front(tQueue Q){
  return Q.data[Q.front];
}
 
bool isEmptyQueue(tQueue Q){
  return (Q.front == addOne(Q.rear));
}

\newpage

Implementación dinámica

• Borrado rápido
• Espacio ilimitado

Lista dinamica

• Inserción rapida
• Borrado rápido
• Busqueda lenta

#define LNULL NULL
 
typedef int tItemL;
typedef struct tNode* tPosL;
 
struct tNode {
  tItemL data;
  tPosL next;
};
 
typedef tPosL tList;
 
void createEmptyList(tList *L);
bool insertItem(tItemL d, tPosL p, tList *L);
tPosL findItem(tItemL d, tList L);
tItemL getItem(tPosL p, tList L);
void deleteAtPosition(tPosL p , tList *L);
bool isEmptyList(tList L);
 
void createEmptyList(tList *L) {
  *L = LNULL;
}
 
bool createNode(tPosL *p) {
  *p = malloc(sizeof(struct tNode));
  return (*p != NULL);
}
 
bool insertItem(tItemL d, tPosL p, tList *L) {
  tPosL q, r;
 
  if(!createNode(&q)) {
    return false;
  }else{
    q->data = d;
    q->next = LNULL;
    if(isEmptyList(*L)){
      *L = q;
    }else if(p == LNULL){ //end of list
      for (r = *L; r->next != LNULL; r = r->next); //move to end
      r->next = q;
 
    }else if(p == *L){ //first element
      q->next = p;
      *L = q;
 
    }else{
      q->data = p->data; //data exchange
      p->data = d;
      q->next = p->next;
      p->next = q;
    }
    return true;
  }
}
 
tPosL findItem(tItemL d, tList L) {
  tPosL p;
 
  for (p = L; (p != LNULL) && (p->data != d); p = p->next);
  return p;
}
 
 
tItemL getItem(tPosL p, tList L) {
  return p->data;
}
 
void deleteAtPosition(tPosL p, tList *L) {
  tPosL q;
 
  if(p == *L){ //first element
    *L = (*L)->next;
  }else if(p->next == LNULL){ //last element
    for (q = *L; q->next->next != LNULL; q = q->next);
    q->next = LNULL;
 
  }else{
    q = p->next;
    p->data = q->data;
    p->next = q->next;
    p = q;
  }
 
  free(p);
}
 
bool isEmptyList(tList L) {
  return (L == LNULL);
}

Pila dinámica

• Acceso rápido a la cima de la pila
• Acceso lento a cualquier otro elemento

#define SNULL NULL
 
typedef int tItemS;
typedef struct tNodeS *tPosS;
 
struct tNodeS{
  tItemS data;
  tPosS down;
};
 
typedef tPosS tStack;
 
void createEmptyStack(tStack *S);
bool push(tItemS d, tStack *S);
void pop(tStack *S);
tItemS peek(tStack S);
bool isEmptyStack(tStack S);
 
void createEmptyStack(tStack *S){
  *S = SNULL;
}
 
bool createNode(tPosS *p){
  *p = malloc(sizeof(struct tNodeS));
  return (*p != SNULL);
}
 
bool push(tItemS d, tStack *S){
  tPosS aux;
 
  if(!(createNOde(&aux)))
    return false;
  else {
    aux->data = d;
    aux->down = *S;
    *S = aux;
    return true;
  }
}
 
void pop(tStack *S){
  tPosS aux;
 
  aux = *S;
  *S = (*S)->down;
  free(aux);
}
 
tItemS peak(tStack S){
  return S->data;
}
 
bool isEmptyStack(tStack S){
  return (S == SNULL);
}

Cola dinámica (circular)

• Acceso rápido a el primer elemento
• Acceso lento a cualquier otro elemento

#define QNULL NULL
 
typedef int tItemQ;
typedef struct tNodeQ *tPosQ;
 
struct tNodeQ{
  tItemQ data;
  tPosQ next;
};
 
typedef tPosQ tQueue;
 
void createEmptyQueue(tQueue *Q);
bool enqueue(tItemQ d, tQueue *Q);
void dequeue(tQueue *Q);
tItemQ front(tQueue Q);
bool isEmptyQueue(tQueue Q);
 
void createEmptyQueue(tQueue *Q){
  *Q = QNULL;
}
 
bool createNode(tPosQ *p){
  *p = malloc(sizeof(struct tNodeQ));
  return (*p != QNULL);
}
 
bool enqueue(tItemQ d, tQueue *Q){
  tPosQ p;
 
  if(!createNode(&p))
    return false;
  else {
    p->data = d;
    p->next = QNULL;
 
    if(isEmptyList(*Q))
      p->next = p;
    else{
      p->next = (*Q)->next;
      (*Q)->next = p;
    }
    *Q = p;
    return true;
  }
}
 
void dequeue(tQueue *Q){
  tPosQ p;
 
  if ((*Q)->next == *Q) { //one element
    *Q = QNULL;
  } else {
    p = (*Q)->next;
    (*Q)->next = p->next;
    free(p);
  }
 
}
 
tItemQ front(tQueue Q){
  return Q->next->data;
}
 
bool isEmptyQueue(tQueue Q){
  return (Q == QNULL);
}

\newpage

Lista ordenada

• Busqueda más rápida

Estática

bool insertItem(tItemL item, tList *L);
tPosL findItem(tItemL item, tList L);
 
bool insertItem(tItemL item, tList *L){
  tPosL pos;
 
  if(L->lastPos == MAX-1){ //en caso de lista llena
    return false;
  }else{
    L->lastPos++;
    if(isEmptyList(*L) || item > L->data[L->lastPos]){ //en caso de lista vacia
       L->data[L->lastPos] = 0;
    }else{ //en caso general
       for(pos = L->lastPos; (i>0)&&(L->data[pos] > item); pos--){
         L->data[pos] = L->data[pos-1];
       }
       L->data[pos] = item;
    }
    return true;
  }
}
 
tPosL findItem(tItemL item, tList L){
  tPosL pos;
 
  if(isEmptyList(L)){
    return LNULL;
  }else{
    for(pos = 0; (p < L.lastPos)&&(L.data[pos] <= item); pos++);
    if (L.data[pos] == item) return pos;
    else return LNULL;
  }
}

Dinámica

bool insertItem(tItemL item, tList *L);
tPosL findItem(tItemL item, tList L);
 
bool insertItem(tItemL d, tList *L) {
  tPosL q, p;
 
  if(!createNode(&q)){
    return false;
  }else{
    q->data = d;
    q->next = LNULL;
 
    if(isEmptyList(*L)){
      *L = q;
    }else if (d < (*L)->data) { //first element
      q->next = *L;
      *L = q;
    }else {
      p = findPosition(*L, d);
      q->next = p->next;
      p->next = q;
    }
    return true;
  }
}
 
tPosL findItem(tItemL d, tList L) {
  tPosL p;
 
  for (p = L; (p != LNULL) && (p->data < d); p = p->next);
  if (p != LNULL && p->data == d) {
    return p;
  } else {
    return LNULL;
  }
}

\newpage

Árboles binarios

• Busqueda e inserción rápida
• Borrado lento

Implementación dinámica

#define TNULL NULL
 
typedef int tItemT;
typedef struct tNodeT *tPosT;
struct tNodeT{
  tItemT data;
  tPosT left;
  tPosT right;
}
typedef tPosT tBinTree;
 
void createEmptyTree(tBinTree *T);
tBinTree leftChild(tBindTree T);
tBinTree rightChild(tBindTree T);
tItemT root(tBindTree T);
bool isEmptyTree(tBinTree T);
 
void createEmptyTree(tBinTree *T) {
  *T = TNULL;
}
 
bool createNode(tPosT *p) {
  *p = malloc(sizeof(struct tNodeT));
  return *p != TNULL;
}
 
bool BuildTree(tBinTree LTree, tItemT d, tBinTree Rtree, tBinTree *T) {
  if (createNode(T)) {
    (*T)->data = d;
    (*T)->left = LTree;
    (*T)->right = Rtree;
    return true;
 
  } else {
    return false;
  }
}
 
tBinTree LeftChild(tBinTree T) {
  return T->left;
}
 
tBinTree RightChild(tBinTree T) {
  return T->right;
}
 
tItemT Root(tBinTree T) {
  return T->data;
}
 
bool IsEmptyTree(tBinTree T) {
  return (T == TNULL);
}