Complements de programació i bases de dades. Apunts

EST CPBD A p u N T s 000 000 000 DIPLOMATURA D'ESTADÍSTICA COMPLEMENTS DE PROGRAMACIÓ I BASES DE DADES LLENGUATGE ALGORÍSMIC I ESTRUCTURES DE DADES LINEALS (PART 1) Marta Franquesa Niubó Lloren� Roselló Saurí ' , UPC FACULTAT DE MATEMATIQUES I ESTADISTICA UNIVERSITAT P0LITECNICA DE CATALUNYA Biblioteca 111111111111111111111111111111111111111111111111111111111111 1400249382 ...... COMPLEMENTS DE PROGRAMACIÓ I BASES DE DADES Llenguatge Algorísmic Estructures de Dades Lineals (I) Apunts Marta Franquesa Niubó Lloren� Roselló Saurí Departament de Llenguatges i Sistemes Informa.�ics 7 d'octubre de 1996 1 Introducció Aquest apunts formen part d 'una serie de documents que anirán sortint al llarg del curs. Aquesta primera part consta de : •Un breu resum de la notació algorísmica que cal utilitzar per resoldre els problemes. J unt a.mb el llenguatge algorísmic es presenta la tra.ducció llenguatge PASCAL. •La part de Modularització la qual s 'ha traduit al TurboPASCAL (no al PASCAL standard) utilitzant com a eina la unit. •Un apartat dedicat a }'estructura de dades lineal CUA. 2 Llenguatge A)gorísmic En a.quest capítol es presenta. un resum de la. nota.ció del llenguatge a.lgorísmic i la. seva traducció al llengua.tge PASCAL. No es pretén fer una exposició exhaustiva dels llengua.tges sino un breu resum dels mateixos. algoritme N omAlgorisme usos definicio de constants definicio de tipus declaracio de variables sentencies falgoritme modul NomModul especificació usos de/inició de contants definició de tipus capfaleres de subprogrames fespecificació implementació implementació de subprogrames implementació de subprogrames privats fimplementació fmodul 1 program NomAlgorisme usos definició de constants definició de tipus declaració de variables begin sentencies end. accions_funcions unit NomModul interface usos de/inició de constants de/inició de tipus cap9leres de subprogrames implementation implementació de subprogrames implementació de subprogrames privats begin end. usos::= usa noms moduls fusa de/inició de constants::= const N omConstant : N omTipus = ExpressioConstant fconst definició de ti pus::= tipus NouTipus ftipus NouTipus:= NomNouTipus = Tipus_elemental NomNouTipus = (nl, n2, .. .) uses ( noms moduls )¡ ( és una llista separada per comes) const NomConstant = ExpressióConstant type NouTipus NomNouTipus = taula {1 .. n1,1 .. n2, ... J de NomTipus N omN ouTipus = tupla NomCampl, ... : NomTipus ftupla Tipus_elemental:= enter, real, caracter, boolea Implementació en PASCAL: NomNouTipus = Tipus_elemental NomNouTipus= (n1, n2, ... ) NomNouTipus=array[1. .n1,1. .n2, .... ] of NomTipus NomNou Tipus=record NomCamp1,NomCamp2, ... : NomTipus¡ end; Tipus_elemental:=integer, real, char, boolean 2 var declaració de variables::= var Nom Varl, Nom Var2, ... : NomTipus; NomVarl,N omVar2, ... : NomTipus fvar cap9aleres de subprogrames::= accio NomAcció( ParametresFormalsAcció) procedure NomAccio(ParametresFormalsAcció) funcio NomFunció( ParametresFormalsFunció ) retorna NomTipus funct ion N omFunció(ParametresFormalsFunció): Nom Ti pus cap9alera de Subprogrames privats::= accio privada NomAcció( ParametresFormalsAcció) funcio privada NomFunció( ParametresFormalsFunció) retorna NomTipus � Pascal � Pascal (PASCAL: els subprogrames privats es defineixen dins de la part d'implementació de les unitats sense indicar la seva privacitat) ParametresFormalsAccio:: = ent Nom Var: NomTipus ent/sor Nom Var: NomTipus sor Nom Var: NomTipus ParametresFormalsFuncio:: = ent Nom Var: NomTipus Sentencies::= assignació alternativa o condicional iterativa_M entre iterativa_Fer crida a subprograma assignació : : = Nom Var := expressió 3 Nom Var: Nom tipus var Nom Var: Nomtipus var Nom Var: Nomtipus En llenguatge algorísmic es consideren corree tes assignacions entre taules o tuples sempre que hi hagi concordancia de tipus. e funcio Esbuidcua(ent c: cua)retorna booleaes Esbuidacua := (c.cmpt = O) ffuncio funcio Esplenacua( ent c: cua)retorna boolea. es Explenacua. := ( cmpt = max) ffuncio fimplementacio fmodul 4 Estació de trens Marsens El cap de manteniment de l' estació de ferrocarril de Marsens ens encarrega que li dissenyem un algorisme que validi les maniobres que preveu per tal de formar els trens que li calen. Per portar a terme les maniobres l 'estació de Marsens només disposa d 'una via de maniobres que per un extrem acaba en un tope i per 1 'altre esta conectada a una via d 'entrada i a una altra de sortida. Una maniobra es defineix com una seqüencia de codis de moviment tal com {EESEESSS} que s'aplica a un conjunt donat d'identificadors ordenats de vagó tal com {idl, id2, id3, id4}. Els possibles moviments E i S signifiquen respectivament entrar i treure un vagó de la vía de maniobres de manera que, la seqüencia indicada, quan s'aplica al conjunt de vagons donat, produeix el nou conjunt {id2, id4, id3, idl }. U na seqüencia de moviments és admisible si conté tants codis E com S, tots els moviments indicats poden portar-se a terme i el tren format conté tots els vagons donats. Cada seqüencia de moviments s'acaba amb un símbol especial. La informació associada a un vagó consta d'un nombre natural (identificador) i d'un codi del conjunt {PP, PS, CA, CO} que indica el tipus de carrega del vagó. Cada seqüencia de vagons s'acaba amb un símbol especial. Es deman que: •lmplementis un modul per a gestionar una cua de vagons:CUAVAGO •lmplementis un modul per a gestionar una pila de vagons:PILAVAGO •Usant les estructures de dades implementades, dissenya l'algorisme definit com segueix: funció Maniobra_valida retorna boolea és { retorna CERT si la maniobra és valida i FALS en cas contrari } 7 Q<éld J ..lCS� 1 \