Introduccion Listas
Enviado por espiando • 20 de Enero de 2014 • 657 Palabras (3 Páginas) • 260 Visitas
La bibliograf�a b�sica para el tema 8, \emph{Estructura de datos
Lista}, son los Cap�tulos 6 y 11 del Nyhoff'06. Sin embargo, hay unas cuestiones y
diferencias entre la lista implementada en las transparencias y la
explicada en el libro que trataremos brevemente en este documento.
Estas diferencias afectan fundamentalmente a la inserci�n y borrado
de elementos en una lista y b�sicamente son las dos siguientes:
\begin{enumerate}
\item Las operaciones que se usan para insertar elementos.
\item La forma en que se indica d�nde insertar y borrar los elementos.
\end{enumerate}
Conviene aclarar que la versi�n de las transparencias imita en los
dos puntos anteriores a la lista de la STL.
\subsection*{Operaciones b�sicas para insertar elementos}
Las operaciones b�sicas para insertar elementos en la lista de la STL
son \verb+insert+ que inserta un elemento antes del nodo indicado por
un iterador y \verb+push_back+ que inserta un elemento al final de la
lista. La implementaci�n de las transparencias utiliza las mismas
operaciones.
Sin embargo, en el libro se explican como operaciones b�sicas de
inserci�n \verb+InsertaDespues+ (que corresponde a \verb+insert+) y
\verb+push_front+, es decir, insertar el primero (p�gina 290).
Adem�s, en el libro no aparece el c�digo completo de ambas operaciones.
Es importante se�alar tambi�n, que la explicaci�n que da el libro
para la operaci�n \verb+insert+ del contenedor \verb+list+ de la STL
en la \verb+Tabla 11.2+ (p�gina 606) no es clara: \verb+insert+ inserta
el nuevo elemento \emph{antes} del nodo \emph{apuntado} por \verb+pos+.
Trataremos este \emph{apuntador} a continuaci�n.
\subsection*{C�mo se indica d�nde insertar y borrar elementos}
Las listas, a diferencia de las pilas y las colas, permiten insertar un elemento
en cualquier posici�n y borrar cualquier elemento. Por tanto, hay que
identificar de alg�n modo d�nde queremos insertar o qu� nodo queremos
borrar. Esto se puede conseguir de diversas formas:
\begin{enumerate}
\item Indicando el contenido del nodo anterior/posterior al que se va
a insertar o indicando el contenido del nodo a borrar en su caso.
\item Indicando la posici�n que ocupar� el nuevo elemento o que ocupa el
elemento a borrar: primero, segundo, tercero, etc.
\item Pasando a las funciones de inserci�n y borrado \emph{algo} que
\emph{apunte} a ese nodo. Es decir, pasando un \emph{apuntador} al
nodo anterior/posterior al que se inserta o al nodo que se quiere
borrar.
...