4º tema

7/24/2019 4 tema

1/11

4ESTRUCTURASDEDATOS(I):ARRAYS. CADENASDECARACTERESEn captulos anteriores se ha estudiado el concepto de datos de tipo simple (entero, real ycarcter). A veces, los datos a tratar en un programa no son elementos individuales de informacin,

sino que existe cierta relacin entre ellos. En esos casos, los lenguaes de programacin permitentra!aar con estructuras de datos, es decir, colecciones de datos ms simples con relacionesesta!lecidas entre ellos. Estas estructuras de datos posi!ilitan, por un lado, representar lainformacin de una manera ms natural y clara y, por otro, un tratamiento de la informacin mscmodo y eficiente. En este captulo se tratarn dos de las estructuras de datos ms ha!ituales en

programacin" los arrays y las cadenas de caracteres.

4.1 INTRODUCCIN#na estructura de datoses una coleccin de datos caracteri$ada por su organi$acin y por lasoperaciones definidas so!re ella. %os tipos de datos utili$ados para declarar estructuras de datos sedenominan tipos compuestosy se construyen a partir de los tipos simples ya estudiados.

&istinguimos dos categoras de estructuras de datos"

Estticas:su tama'o se determina a priori, antes del comien$o de la eecucin del programa,y este no podr incrementarse ni disminuirse en tiempo de eecucin. Esto implicar quecuando se tra!ae con una estructura de datos esttica cuyo tama'o se desconoce en la fase dedise'o, sea necesario esta!lecer un tama'o mximo y reservar espacio en memoria para esemximo (con el posi!le desperdicio de memoria que esto pueda conllevar). Entre lasestructuras de datos estticas distinguimos arrays, cadenas de caracteresy registros.

Dinmicas:su tama'o se determina en tiempo de eecucin, reservando y li!erando espacioen memoria en el momento que interese. Esto permitir, por tanto, optimi$ar al mximo elespacio de ocupacin en memoria, aunque requiere una gestin de memoria ms complicada.&istinguimos listas, rbolesygrafos.

En esta asignatura nos centraremos en las estructuras de datos estticas, adecuadas como unaprimera aproximacin al maneo de estructuras de datos por ser ms sencillas de gestionar.

#na caracterstica comn a todas las estructuras de datos es la existencia de un nico

identificador que hace referencia a la misma en su conunto. Adems, cada tipo de estructura de

*

7/24/2019 4 tema

2/11

4. ESTRUCTURASDEDATOS(I): ARRAYS. CADENASDECARACTERES

datos dispone de su propio mecanismo para hacer referencia de forma independiente a los elementosque la integran.

4.2 ARRAYS#n array es una coleccin de elementos de un mismo tipo, donde cada elemento puede

identificarse por su posicin dentro de la estructura. +odo array posee un identificador que lodesigna y una serie de ndicesque toman valores enteros y permiten diferenciar por su posicin a losdistintos elementos que lo constituyen.

4.2.1 ARRAYSUNIDIMENSIONALES

#n array unidimensionalpuede considerarse como una lista ordenada de valores. %leva asociadoun nico ndice que designa la posicin de sus elementos dentro de la lista, comen$ando en lenguae desde -. &e!ido a su similitud con el concepto matemtico de vector, los arrays unidimensionalestam!in se conocen con el nom!re de vectores.

En la siguiente figura se representa grficamente un vector que representa el nmero deha!itantes (en unidades de millar) de /-- po!laciones"

- / 0 11habitantes 2- 3 4 ... /0-

5ara hacer referencia a cada elemento del vector, tanto en algoritmia como en , se utili$a la

siguiente sintaxis"identificador[ndice]

5or eemplo, el nmero de ha!itantes de la tercera po!lacin se designa habitantes[2]y sucontenido es igual a 4.

En algoritmia, la declaracin de estructuras de datos de tipo vector utili$a el siguiente diagramasintctico"

El valor enterorepresenta el nmero de elementos del vector y, por tanto, el rango de valores quepuede tomar el ndice (en , desde - a valor entero6 /, am!os inclusive).

%a traduccin a de esta declaracin se reali$a segn el siguiente diagrama sintctico"

3

tipoidentificador

de variable ;

,

[valor

entero ]

tipoidentificador

de variable :

,

VARIABLES [valor

entero ]

7/24/2019 4 tema

3/11


5or eemplo, las declaraciones del vector habitantesen algoritmia y en emplearan lasiguiente sintaxis"

En algoritmia"

7A89A:%E;

ha!itantes

7/24/2019 4 tema

4/11


!) 8epresentacin algortmica"

CODIFICACIN:

/*************************/

/*** E D A D E S ***/

/*************************/#include

7/24/2019 4 tema

5/11


4.2.2 ARRAYSMULTIDIMENSIONALES

A veces, existen datos cuya representacin es ms adecuada en forma de ta!la con dos o msndices, por eemplo, para tratar la disposicin de las fichas en un ta!lero de aedre$ (DD casillas) ovalores diarios durante los meses de una dcada (2//0/- valores). 5ara ello, se pueden emplear

arrays multidimensionales.#n array bidimensional (tam!in denominado matri$) puede considerarse como un array

unidimensional cuyos elementos son vectores. As, por eemplo, la representacin del censo deha!itantes de /-- po!laciones en las 2 ltimas dcadas podra efectuarse mediante una matri$ dedimensiones /--2, como se muestra en la siguiente figura"

habitantes Fndice de dcada- / 0

Fndice depo!lacin

- 2/ 0D 2-/ /- D 3... ... ... ...11 *- 1- /0-

5ara referenciar a cada elemento de un array !idimensional se utili$an dos ndices. El primero serefiere a la fila y el segundo a la columna que ocupa dicho elemento. ;e utili$a la siguiente sintaxis"

identificador[fila][columna]

5or eemplo, el nmero de ha!itantes de la segunda po!lacin en el censo de la primera dcadase designa habitantes[1][0]y su contenido es igual a /-.

Anlogamente, pueden declararse arrays de tantas dimensiones como se quiera, teniendo como

nica limitacin el tama'o de la memoria del ordenador. El nmero total de elementos del array esel producto del nmero de elementos de cada dimensin. 5or eemplo, un array de dimensin2/-0 tendr *- elementos. @o o!stante, o!srvese que a mayor nmero de dimensiones, menorser la legi!ilidad de la solucin y mayor la dificultad de su maneo, pues cada ndice harreferencia a una caracterstica de los datos y de!emos sa!er en qu orden de!e situarse cada uno delos ndices (por eemplo, primero el cdigo de po!lacin, a continuacin la dcada, etc.).

En general, un elemento de un array nGdimensional se referencia con la siguiente sintaxis"

identificador[ndice$][ndice%]...[ndicen]

Al igual que en el caso de los vectores, todos los elementos de un array multidimensional de!enser de igual tipo. ;i unto con el nmero de ha!itantes del eemplo anterior quisiramos almacenarel nom!re de la entidad que reali$ el censo (representado por un dato de tipo cadena de caracteres),sera preciso declarar una nueva matri$ de tama'o /--2 en ve$ de a'adir una nueva dimensin alarray original, ya que los datos a almacenar son de distinto tipo.

En algoritmia, la declaracin de una estructura de datos array multidimensional utili$a elsiguiente diagrama sintctico"

Ahora, cada valor enterorepresenta el nmero de elementos de la dimensin correspondiente y,por tanto, el rango de valores que puede tomar su ndice (en , desde - a valor entero6 /).

4-

tipoidentificador

de variable :

,

VARIABLES [valor

entero ]

7/24/2019 4 tema

6/11


%a traduccin a de esta declaracin se reali$a segn el siguiente diagrama sintctico"

5or eemplo, la declaracin de la matri$ habitantes vista anteriormente empleara lasiguiente sintaxis"

En algoritmia"

7A89A:%E;ha!itantes

7/24/2019 4 tema

7/11


CODIFICACIN:

/***************************************/

/*** S & ' A C L & ' N A S ***/

/***************************************/#include ;

/* Lectura desde teclado de la matri" or filas */!o (i=0; i =>+1) scan!(l!&'[i][>]); 6

/* Clculo de la suma de cada columna y visuali"aci#n de resultados */

!o (>=0; >

7/24/2019 4 tema

8/11


4.3.1 OPERACIONESCONCADENAS

#na cadena de caracteres no es ms que un vector de caracteres delimitado por el carcter nulo.5or ello, en la mayora de los casos, podemos operar con las cadenas del mismo modo que concualquier otro vector. @o o!stante, existe una !i!lioteca de funciones en (con archivo de ca!ecera

stin.h) que permiten manear las cadenas de caracteres de un modo ms cmodo. En estaseccin estudiaremos algunas de ellas.

ASIGNACIN

Al igual que con cualquier otro vector, para almacenar en una varia!le de tipo cadena una cadenade caracteres, el uso del operador de asignacin requerira asignar uno a uno los caracteres quecomponen la cadena al elemento correspondiente de la varia!le mediante el uso de una estructurarepetitiva for do. En lugar de ello, puede reali$arse la misma asignacin ms cmodamenteutili$ando la funcin interna stc-. Esta funcin emplea dos parmetros" el primero, la varia!le

cadena que reci!ir la asignacin, y el segundo, la cadena a asignar.5or eemplo, dada la varia!le cadenadeclarada en la seccin anterior, la instruccin de

stc-(cadena123@5ABCD0);almacenar en dicha varia!le el valor 123@5ABCD0.

%a funcin stc- copia todos los caracteres contenidos en el segundo parmetro hastaencontrar el carcter nulo. 5or ello, el programador de!e asegurarse de reservar suficiente espaciodurante la declaracin de la varia!le que va a al!ergar el contenido que se le asigna. 5or eemplo, lainstruccin stc-(cadena123@5ABCD0123@5); no sera correcta, ya que se estnintentando asignar /* caracteres (/4 significativos ms el carcter nulo) a una cadena para la quesolo se han reservado /4.

En algoritmia, nos referiremos a esta operacin con el operador de asignacin I.

LECTURAYESCRITURA

Aunque una cadena de caracteres es un vector de caracteres y podemos hacer referencia a suscaracteres individuales utili$ando la notacin de vectores, a diferencia de otros tipos de vectores,

para leer por teclado o escri!ir en pantalla una cadena de caracteres !asta con incluir el nom!re de lavaria!le entre los parntesis de una instruccin etso -int!, respectivamente, tal y como seestudi en el aptulo 2.

COMPARACIN

%a comparacin de cadenas posee gran importancia en la ordenacin de datos alfa!ticos,!squeda de textos, etc. El criterio de clasificacin se !asa en el orden numrico de los caracteressegn su cdigo de A;99.

&os cadenas sern iguales si contienen exactamente los mismos caracteres situados en el mismoorden. En otro caso, el resultado de la comparacin ser el del primer par de caracteres distintossituados en una misma posicin. En este sentido, la presencia de cualquier carcter se considerarsiempre mayor que la ausencia de carcter.

42

7/24/2019 4 tema

9/11


En , para compro!ar si dos cadenas son iguales se utili$ar la funcin interna stc'-, quetiene como parmetros las dos cadenas de caracteres a comparar. El valor devuelto por la funcintiene el siguiente significado"

#n valor positivo significa que la primera cadena es mayor (sucede alfa!ticamente) a lasegunda.

#n valor igual a cero significa que am!as cadenas son idnticas. #n valor negativo significa que la primera cadena es menor (precede alfa!ticamente) a la

segunda.

Eemplos de comparaciones son"

stc'-(notenote) 0

stc'-(cibeciudad) negativo

stc'-(EFG EFG) positivo

stc'-(li'ai'a) positivo

stc'-(casacasaca) negativo

En algoritmia, representaremos las comparaciones entre cadenas mediante los operadoresrelacionales (?, J, K, , L, M).

CLCULODELALONGITUD

5ara calcular la longitud de una cadena en lenguae se utili$a la funcin interna stlen.omo parmetro se especificar un valor de tipo cadena. &evolver un valor entero igual a lalongitud actual de la cadena (sin contar el carcter nulo). En algoritmia nos referiremos a estaoperacin con la pala!ra longitud.

CONCATENACIN

%a concatenacin consiste en la unin de varias su!cadenas en una nica cadena. En algoritmia,utili$aremos el operador de suma (+) para representar la concatenacin. 5or eemplo,

N5A8AN>N:89;A;N ? N5A8A:89;A;N

5uede o!servarse que se unen las cadenas sin insertar espacios en !lanco entre ellas, por lo queestos de!ern incluirse explcitamente en alguna de las cadenas a concatenar si se desea que

permane$can separadas.

En lenguae , la concatenacin se consigue mediante la funcin interna stcat, que a'ade unacadena al final de otra cadena. #tili$a dos parmetros" el primero, la varia!le cadena destino de laconcatenacin, y el segundo, la cadena que se a'ade.

5or eemplo, dada la varia!le cadena de secciones anteriores, tras las siguientes dosinstrucciones"

stc-(cadenaHEIE);stcat(cadenaJI%GEG);

la varia!le cadenacontendr el valor HEIEJI%GEG.

4

7/24/2019 4 tema

10/11


BSQUEDA

%a operacin de !squeda consiste en locali$ar una determinada cadena como parte de otracadena ms grande. En , la funcin que reali$a este cometido es stst, que utili$a dos

parmetros de tipo cadena" el primero, la cadena donde se !uscarO el segundo, la su!cadena a

locali$ar. El valor devuelto es un puntero a la su!cadena !uscada en la primera aparicin dentro dela cadena explorada. ;i la su!cadena no aparece en la cadena, el valor devuelto ser ". En larepresentacin algortmica se utili$ar la pala!ra buscar.

5or eemplo, dada la cadena cadena?NEn un lugar de la Bancha de...N

stst(cadena"de") /n un lua de la $ancha de... K

stst(cadena"e") /n un lua de la $ancha de...

stst(cadena"ade") devuelve el valor "

EJEMPLO 4.3."esarrollar un programa que lea dos cadenas de m%imo 100 caracteres y muestre el n*mero de

veces que la segunda aparece incluida en la primera, sin contabili#ar solapamientos.

ANLISIS:a) &atos de entrada"

')NA+100" %ongitud mxima de las cadenas. &ato fio. cad/=" ;u!cadena a !uscar. +eclado

!) &atos de salida" rep" @mero de veces que la su!cadenasubaparece en la cadena cad(sin solapamientos). Bonitor.

c) omentarios" ;e emplear una varia!le para contar el nmero de ocurrencias de la su!cadena en la cadena. &e!ido a que la funcin stst slo !usca la primera ocurrencia de una su!cadena, ha!r que ir

desechando la parte de la cadena ya inspeccionada. 5or ello, se utili$ar un puntero que apunte a cadaocurrencia de la su!cadena, lo que nos permitir determinar qu parte de la cadena queda por explorar.

DISEO:a) 5arte declarativa"

C@;+A@+E;%C@BAP?/--

7A89A:%E;cad/=,su!/=,Qp"carcterrep"entero

!) 8epresentacin algortmica"

44

re/eticiones

BLOCK

escribir(Cadenas)

while do

BLOCK/ 1 "#LL

re/re/+

re/0leer(cadsub)

escribir(re/)/buscar(cadsub)

cad/+lon2itud(sub) /buscar(cadsub)

7/24/2019 4 tema

11/11


CODIFICACIN:

/***************************************/

/*** E + E , - C - N E S ***/

/***************************************/#include

Documents

4º tema