#LyX 2.3 created this file. For more info see http://www.lyx.org/ \lyxformat 544 \begin_document \begin_header \save_transient_properties true \origin unavailable \textclass book \use_default_options true \maintain_unincluded_children false \language spanish \language_package default \inputencoding auto \fontencoding global \font_roman "default" "default" \font_sans "default" "default" \font_typewriter "default" "default" \font_math "auto" "auto" \font_default_family default \use_non_tex_fonts false \font_sc false \font_osf false \font_sf_scale 100 100 \font_tt_scale 100 100 \use_microtype false \use_dash_ligatures true \graphics default \default_output_format default \output_sync 0 \bibtex_command default \index_command default \paperfontsize default \spacing single \use_hyperref false \papersize default \use_geometry false \use_package amsmath 1 \use_package amssymb 1 \use_package cancel 1 \use_package esint 1 \use_package mathdots 1 \use_package mathtools 1 \use_package mhchem 1 \use_package stackrel 1 \use_package stmaryrd 1 \use_package undertilde 1 \cite_engine basic \cite_engine_type default \biblio_style plain \use_bibtopic false \use_indices false \paperorientation portrait \suppress_date false \justification true \use_refstyle 1 \use_minted 0 \index Index \shortcut idx \color #008000 \end_index \secnumdepth 3 \tocdepth 3 \paragraph_separation indent \paragraph_indentation default \is_math_indent 0 \math_numbering_side default \quotes_style swiss \dynamic_quotes 0 \papercolumns 1 \papersides 1 \paperpagestyle default \tracking_changes false \output_changes false \html_math_output 0 \html_css_as_file 0 \html_be_strict false \end_header \begin_body \begin_layout Section Pilas \end_layout \begin_layout Standard Una \series bold pila \series default o secuencia \series bold LIFO \series default ( \emph on Last In First Out \emph default ) \series bold \series default es una secuencia mutable de cero o más elementos en el que las inserciones, accesos y supresiones se realizan siempre por el mismo extremo, llamado \series bold tope \series default . Operaciones: \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash begin{verbatim} \end_layout \begin_layout Plain Layout Stack create(); \end_layout \begin_layout Plain Layout void push(Stack s, Element e); \end_layout \begin_layout Plain Layout void delete(Stack s); \end_layout \begin_layout Plain Layout Element pop(Stack s); \end_layout \begin_layout Plain Layout int isEmpty(Stack s); \end_layout \begin_layout Plain Layout \backslash end{verbatim} \end_layout \end_inset \end_layout \begin_layout Standard Podemos implementar una pila mediante una tabla o una lista enlazada, aunque si la tabla es de tamaño fijo tenemos que implementar la operación \family typewriter int isFull(Stack s); \family default . \end_layout \begin_layout Section Colas \end_layout \begin_layout Standard Una \series bold cola \series default o secuencia \series bold FIFO \series default ( \emph on First In First Out \emph default ) es una secuencia mutable de cero o más elementos en el que las inserciones se realizan en un extremo llamado \series bold posterior \series default o \series bold final \series default y los accesos y supresiones por el otro, llamado \series bold anterior \series default o \series bold frente \series default . Operaciones: \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash begin{verbatim} \end_layout \begin_layout Plain Layout Queue create(); \end_layout \begin_layout Plain Layout void append(Queue q, Element e); \end_layout \begin_layout Plain Layout void delete(Queue q); \end_layout \begin_layout Plain Layout Element pop(Queue q); \end_layout \begin_layout Plain Layout int isEmpty(Queue q); \end_layout \begin_layout Plain Layout \backslash end{verbatim} \end_layout \end_inset \end_layout \begin_layout Standard Podemos implementar una cola mediante una lista enlazada o una tabla de tamaño fijo circular, de forma que conforme se van sacando elementos al principio se pueden ir añadiendo más una vez se haya llegado al final de la tabla, si bien esto requiere implementar la operación \family typewriter int isFull(Queue q); \family default . \end_layout \begin_layout Section Listas \end_layout \begin_layout Standard Una \series bold lista \series default es una secuencia mutable de cero o más elementos ordenados de acuerdo a su posición. Los accesos, inserciones y supresiones pueden realizarse en cualquier posición de la lista, y cada valor de esta tiene asociado un valor de tipo \series bold posición \series default . Existe además una posición que indica el final de la lista y se usa para insertar elementos. Operaciones: \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash begin{verbatim} \end_layout \begin_layout Plain Layout List create(); \end_layout \begin_layout Plain Layout void insert(List l, Position p, Element e); \end_layout \begin_layout Plain Layout void delete(List l, Position p); \end_layout \begin_layout Plain Layout Element get(List l, Position p); \end_layout \begin_layout Plain Layout void set(List l, Position p, Element p); \end_layout \begin_layout Plain Layout unsigned length(List l); \end_layout \begin_layout Plain Layout Position begin(List l); \end_layout \begin_layout Plain Layout Position end(List l); \end_layout \begin_layout Plain Layout Position nth(List l, unsigned index); \end_layout \begin_layout Plain Layout Position next(List l, Position p); \end_layout \begin_layout Plain Layout Position prev(List l, Position p); \end_layout \begin_layout Plain Layout \backslash end{verbatim} \end_layout \end_inset \end_layout \begin_layout Standard Podemos implementar una lista mediante una tabla, en cuyo caso las posiciones son enteros, o mediante una lista enlazada. Si hace con una lista enlazada con simple enlace, conviene guardar los apuntadores de inicio y de fin, así como la longitud, y en este caso las posiciones son apuntadores al nodo anterior al que contiene el elemento, pues esto es necesario para borrar un elemento por posición. \end_layout \begin_layout Standard Las listas implementadas por estructuras enlazadas permiten insertar y borrar elementos en \begin_inset Formula $O(1)$ \end_inset , en vez de en \begin_inset Formula $O(n)$ \end_inset como sucedería tablas, si bien requieren un tiempo \begin_inset Formula $O(n)$ \end_inset para acceder a los elementos por índice en vez de \begin_inset Formula $O(1)$ \end_inset . \end_layout \begin_layout Section Conjuntos \end_layout \begin_layout Standard Un \series bold conjunto \series default es una colección mutable (en este caso finita) de elementos no repetidos y sin ordenación. Operaciones: \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash begin{verbatim} \end_layout \begin_layout Plain Layout Set create(); \end_layout \begin_layout Plain Layout void insert(Set c, Element e); \end_layout \begin_layout Plain Layout void delete(Set c, Element e); \end_layout \begin_layout Plain Layout int contains(Set c, Element e); \end_layout \begin_layout Plain Layout unsigned cardinal(Set c); \end_layout \begin_layout Plain Layout List toList(Set c); \end_layout \begin_layout Plain Layout \backslash end{verbatim} \end_layout \end_inset \end_layout \begin_layout Standard Podemos implementarlo como una lista enlazada o como una tabla, y en el último caso podemos aprovechar que los elementos no están ordenados para \begin_inset Quotes cld \end_inset rellenar huecos \begin_inset Quotes crd \end_inset al eliminar elementos en \begin_inset Formula $O(1)$ \end_inset . \end_layout \end_body \end_document