programacion - en - c-metodologia - algoritmos - y-estructura - de - datos - editorial - mcgraw - hill

programacion - en - c-metodologia - algoritmos - y-estructura - de - datos -...

(Parte 3 de 7)

Capítulo 14. Listas enlazadas. Una lista enlazada es una estructura de datos que mantiene una colec- ción de elementos, pero el número de ellos no se conoce por anticipado o varía en un amplio rango. La lista enlazada se compone de elementos que contienen un valor y un puntero. El capítulo describe los fundamentos teóricos y las operaciones que se pueden realizar en la lista enlazada. También se descri- ben los distintos tipos de listas enlazadas.

Capítulo 15. Pilas y colas. Colas de prioridades. Las ideas abstractas de pila y cola se describen en el capítulo. Pilas y colas se pueden implementar de diferentes maneras, bien con vectores (arrays) o con listas enlazadas.

Capítulo 16. Árboles. Los árboles son otro tipo de estructura de datos dinámica y no lineal. Las ope- raciones básicas en los árboles junto con sus operaciones fundamentales se estudian en el Capítulo 2 1.

En todos los libros dedicados a la enseñanza y aprendizaje de técnicas de programación es frecuente incluir apéndices de temas complementarios a los explicados en los capítulos anteriores. Estos apéndi- ces sirven de guía y referencia de elementos importantes del lenguaje y de la programación de compu- tadoras.

Apéndice A. Lenguaje ANSI C. Guh de referencia. Descripción detallada de los elementos funda- mentales del estándar C.

Apéndice B. Códigos de caracteres ASCZZ. Listado del juego de caracteres del código ASCII utiliza- do en la actualidad en la mayoría de las computadoras.

Apéndice C. Palabras reservadas de C++. Listado por orden alfabético de las palabras reservadas en ANSIíiSO C++, al estilo de diccionario. Definición y uso de cada palabra reservada, con ejemplos sen- cillos de aplicación.

Apéndice D. Guh de sintuxis ANSUISO estándar C++. Referencia completa de sintaxis de C++ para que junto con las palabras reservadas facilite la migración de programas C a C++ y permita al lector con- vertir programas estructurados escritos en C a C++.

prólogo xxi i i

Apéndice E. Biblioteca de funciones estándar ANSI C. Diccionario en orden alfabético de las fun- ciones estándar de la biblioteca estándar de ANSIASO C++, con indicación de la sintaxis del prototipo de cada función, una descripción de su misión junto con algunos ejemplos sencillos de la misma.

Apéndice E Recursos de C (Libros, Revistas, URLS de Internet). Enumeración de los libros más sobre- salientes empleados por los autores en la escritura de esta obra, así como otras obras importantes com- plementarias que ayuden al lector que desee profundizar o ampliar aquellos conceptos que considere necesario conocer con más detenimiento. Asimismo se adjuntan direcciones de Internet importantes para el programador de C junto con las revistas más prestigiosas del sector informático y de computa- ción en el campo de programación.

de ciencias e ingeniería, formación profesional de grado superior,, así como autodidactas en asigna-

Un libro nunca es fruto único del autor, sobre todo si el libro está concebido como libro de texto y auto- aprendizaje, y pretende llegar a lectores y estudiantes de informática y de computación, y, en general, turas relacionadas con la programación (introducción, fundamentos, avanzada, etc.). Esta obra no es una excepción a la regla y son muchas las personas que nos han ayudado a terminarla. En primer lugar nuestros colegas de la Universidad Pontijicia de Salamanca en el campus de Madrid, y en particular del Departamento de Lenguajes y Sistemas Informáticos e Ingeniería de Software de la misma que desde hace muchos años nos ayudan y colaboran en la impartición de las diferentes asignaturas del departa- mento y sobre todo en la elaboración de los programas y planes de estudio de las mismas. A todos ellos les agradecemos públicamente su apoyo y ayuda.

Asimismo deseamos expresar nuestro agradecimiento a la innumerable cantidad de colegas (profe- sores y maestros) de universidades españolas y latinoamericanas que utilizan nuestros libros para su clases y laboratorios de prácticas. Estos colegas no sólo usan nuestros textos sino que nos hacen suge- rencias y nos dan consejos de cómo mejorarlos. Nos sería imposible citarlos a todos por lo que sólo podemos mostrar nuestro agradecimiento eterno por su apoyo continuo.

De igual modo no podemos olvidarnos de la razón fundamentul de ser de este libro: los lectores. A ellos también mi agradecimiento eterno. A nuestros alumnos de España y Latinoamérica; a los que no siendo alumnos personales, lo son «virtuales» al saber que existen y que con sus lecturas, sus críticas, sus comentarios, hacen que sigamos trabajando pensando en ellos; y a los numerosos lectores profe- sionales o autodidactas que confian en nuestras obras y en particular en ésta. A todos ellos nuestro reco- nocimiento más sincero de gratitud.

Además de estos compañeros en docencia, no puedo dejar de agradecer, una vez más, a nuestra edi- tora -y, sin embargo, amiga- Concha Fernandez, las constantes muestras de afecto y comprensión que siempre tiene, y ésta no ha sido una excepción, hacia nuestras personas y nuestra obra. Sus conti- nuos consejos, sugerencias y recomendaciones, siempre son acertadas y, además, fáciles de seguir; por si eso no fuera suficiente, siempre benefician a la obra.

A riesgo de ser reiterativos, nuestro reconocimiento y agradecimiento eterno a todos: alumnos, lec- tores, colegas, profesores, maestros, monitores y editores. Gracias por vuestra inestimable e impagable ayuda.

En Carchelejo, Jaén (Andalucía) y en Madrid, Febrero de 2001.

Los autores

CAPíTULO 1

1.1. ¿Qué es una computadora? 1.2. ¿Qué es programación? 1.3. Organización física de una

1.4. Algoritmos y programas.

1.6. Los lenguajes de programa- 1.6. El lenguaje C: historia y ca- 1.7. Resumen.

ción. racterísticas. computadora.

doras.

computadoras o

informática a travks de uno de los lenguajes de programación más versatiles disponibles hoy día: el lenguaje C. Este capítulo le introduce a la computadora y sus componentes, así como a los lenguajes de programación, y a la metodo logía a seguir para la resolución de problemas con computadoras y con una herramienta denominada C.

La principal razón para que las personas aprendan lenguajes y teCnicas de programación es utilizar la computadora como ma herramienta para resolver problemas.

En esta obra, usted comenzará a estudiar la ciencia de CONCEPTOS CLAVE

Algoritmo.

* Athlon. Byte.

* Compilax=idn * Compilador.

Computadora.

Disquete. DWD. Editor. GB.

Inbl.

* Intérprete. fus.

* Lenguaje de programación.

Lenguaje ensamblador. Lenguajemáquina.

m. Memoria. Memoriaauxiliar.

Memoria central.

* Módem, MHZ. Mcroprocesador.

Ordenador. Pentium.

Portabiiidad. software. Unidad Central de Proceso.

4 Programación en C. Metodología, algoritmos y estructura de datos

1 .l. LQUÉ ES UNA COMPUTADORA?

Una computadora' es un dispositivo electrónico utilizado para procesar información y obtener resul- tados. Los datos y la información se pueden introducir en la computadora por la entrada (input) y a continuación se procesan para producir una salida (output, resultados), como se observa en la Figura 1.1. La computadora se puede considerar como una unidad en la que se ponen ciertos datos, o entrada de datos. La computadora procesa estos datos y produce unos datos de salida. Los datos de entrada y los datos de salida pueden ser, realmente, cualquier cosa, texto, dibujos o sonido. El sistema más sencillo de comunicarse con la computadora una persona es mediante un teclado, una pantalla (monitor) y un ratón (mouse). Hoy día existen otros dispositivos muy populares tales como escáneres, micrófonos, alta- voces, cámaras de vídeo, etc.; de igual manera, a través de módems, es posible conectar su computado- ra con otras computadoras a través de la red Internet.

Programa u

Datos de Datos de entrada salida

Figura 1.1. Proceso de información en una computadora.

Los componentes físicos que constituyen la computadora, junto con los dispositivos que realizan las tareas de entrada y salida, se conocen con el término hardware (traducido en ocasiones por mate- rial). El conjunto de instrucciones que hacen funcionar a la computadora se denomina programa que se encuentra almacenado en su memoria; a la persona que escribe programas se llama programador y al conjunto de programas escritos para una computadora se llama software (traducido en ocasiones por logical). Este libro se dedicará casi exclusivamente al software, pero se hará una breve revisión del hardware como recordatorio o introducción según sean los conocimientos del lector en esta materia,

1.2. ORGANIZACIÓN FíSlCA DE UNA COMPUTADORA (HARDWARE)

La mayoría de las computadoras, grandes o pequeñas, están organizadas como se muestra en la Figu- ra 1.2. Ellas constan fundamentalmente de tres componentes principales: unidad central de proceso (UCP) o procesador (compuesta de la UAL, Unidad aritmético-lógica y la UOC, Unidad de Control), la memoria principal o central y el programa.

' En España está muy extendido el término ordenador para referirse a la traducción de la palabra inglesa computer.

Introducción a la ciencia de la computación y a la programación 5

t Entrada de datos Salida de datos t Figura 1.2. Organización física de una computadora.

Si a la organización física de la Figura 1.2 se le añaden los dispositivos para comunicación con la computadora, aparece la estructura típica de un sistema de computadora: dispositivos de entrada, dis- positivo de salida, memoria externa y el procesador/memoria central con su programa (Fig. 1.3).

1.2.1. Dispositivos de Entrada/Salida (E/S)

Los dispositivos de EntraddSalida (E/S) [InputlOutput (UO, en inglés)] permiten la comunicación entre la computadora y el usuario. Los dispositivos de entrada, como su nombre indica, sirven para introdu- cir datos (información) en la computadora para su proceso. Los datos se leen de los dispositivos de entrada y se almacenan en la memoria central o interna. Los dispositivos de entrada convierten la infor- mación de entrada en señales eléctricas que se almacenan en la memoria central. Dispositivos de entra- da típicos son los teclados; otros son: lectores de tarjetas -ya en desuso-, lápices Ópticos, palan- cas de mando (joystick), lectores de códigos de barras, escáneres, micrófonos, etc. Hoy día tal vez el dispositivo de entrada más popular es el ratón (mouse) que mueve un puntero electrónico sobre la pantalla que facilita la interacción usuario-máquina2.

Dispositivos de entrada

- I Dispositivos

de entrada I

UCP (Procesador) Unidad de control I

Memoria central

Unidad aritmética y lógica

Dispositivos de salida

Memoria externa

almacenamiento permanente

Figura 1.3. Organización física de una computadora.

’ Todas las acciones a realizar por el usuario se realizarán con el ratón con la excepción de las que se requieren de la escri- tura de datos por teclado.

6 Programación en C. Metodología, algoritmos y estructura de datos

Los dispositivos de salida permiten representar los resultados (salida) del proceso de los datos. El di+ positivo de salida típico es la pantalla (CRT)' o monitor. Otros dispositivos de salida son: impresoras (imprimen resultados en papel), trazadores gráficos (plotters), reconocedores de voz, altavoces, etc.

El teclado y la pantalla constituyen -en muchas ocasiones- un Único dispositivo, denominado terminal. Un teclado de terminal es similar al teclado de una máquina de escribir moderna con la dife- rencia de algunas teclas extras que tiene el terminal para funciones especiales. Si está utilizando una computadora personal, el teclado y el monitor son dispositivos independientes conectados a la compu- tadora por cables. En ocasiones a la impresora se la conoce como dispositivo de copia dura («hard copy»), debido a que la escritura en la impresora es una copia permanente (dura) de la salida, y a la pantalla se le denomina en contraste: dispositivo de copia blanda (eso$ copy»), ya que se pierde la pantalla actual cuando se visualiLa la siguiente.

Los dispositivos de entraddsalida y los dispositivos de almacenamiento secundario o auxiliar (memoria externa) se conocen también con el nombre de di.sposirivci.\ perlféricos o simplemente peri- féricos ya que, normalmente, son externos a la computadora. Estos dispositivos son unidad de discos (disquetes, CD-ROM, DVDs, cintas, videocámaras,etc.).

Figura 1.4. Dispositivo de salida (impresora)

1.2.2. La memoria central (interna)

ejemplo, para que un programa se pueda ejecutar (correr, rodar, funcionar, en inglés run), debe ser

La memoria central o simplemente memoria (interna o principal) se utiliza para almacenar informa- ción (RAM, Random Access Memory). En general, la información almacenada en memoria puede ser de dos tipos: las instrucciones de un programa y los duros con los que operan las instrucciones. Por situado en la memoria central, en una operación denominada carga (load) del programa. Después, cuan- do se ejecuta (se realiza, funciona) el programa, cualquier dato u procesur por el programa se debe lle- var a la memoria mediante las instrucciones del programa. En la memoria central, hay también datos diversos y espacio de almacenamiento temporal que necesita el programa cuando se ejecuta con él a fin de poder funcionar.

Introducción a la ciencia de la computación y a la programación 7

Cuando un programa se ejecuta (realiza, funciona) en una computadora, se dice que se ejecuta.

Con el objetivo de que el procesador pueda obtener los datos de la memoria central más rápida- mente, la mayoría de los procesadores actuales (muy rápido\) utilitan con frecuencia una memoriu denominada cuche‘que sirva para almacenamiento intermedio de datos entre el procesador y la memo- ria principal La memoria caché -en la actualidad- \e incorpora casi siempre al procesador.

La memoria central de una computadora es una zona de almacenamiento organizada en centenares o millares de unidades de almacenamiento individual o celdas. La memoria central consta de un con- junto de (*eldar úe memoria (estas celdas o posiciones de memoria se denominan también palahms, aunque no «guardan» analogía con las palabras del lenguaje). El número de celdas de memoria de la memoria central, dependiendo del tipo y inodelo de computadora; hoy día el número suele ser millones (32.64, 128, etc.) Cada celda de ineinoria consta de un cierto número de bits (normalmente 8, un hite).

La unidad elemental de memoria se llama byte (octeto). Un h\te tiene la capacidad de almacenar un carácter de información, y está formado por un conjunto de unidades más pequeñas de almacenamien- to denominadas hifv, que son dígitos binarim (O o 1 ).

Figura 1.5. Computadora portátil digital.

Generalinente. se acepta que un byte contiene ocho bits. Por umigiitente, si \e desea almacenar la frase

la computadora utili/ará exactamente 27 byte\ conscculivos de iTictnoria. Obsérvese que, además de las letras, existen cuatro espacios en blanco y un punto (un espacio es un carácter que emplea también un byte). De modo similar, el número del pasaporte

1’5 4d/t!iI ocupará 9 bytes. pero si se almacena como 15 148 /891

8 Programación en C. Metodología, algoritmos y estructura de datos

ocupará 1 1. Estos datos se llaman alfanuméricos, y pueden constar del alfabeto, dígitos o incluso carac- teres especiales (símbolos: $, #, *, etc.).

Mientras que cada carácter de un dato alfanumérico se almacena en un byte, la información numé- rica se almacena de un modo diferente. Los datos numéricos ocupan 2,4 e incluso 8 bytes consecutivos, dependiendo del tipo de dato numérico (se verá en el Capítulo 3).

(Parte 3 de 7)

Comentários