Forgrening i programmering er en operation, der bruges i tilfælde, hvor udførelsen eller ikke-udførelsen af et bestemt sæt kommandoer skal afhænge af opfyldelsen eller ikke-opfyldelsen af en bestemt betingelse. Forgrening er en af de tre (sammen med den sekventielle udførelse af kommandoer og løkken ) grundlæggende strukturer for struktureret programmering .
De vigtigste former for implementering af forgrening i imperative programmeringssprog er den betingede operatør (operatør if) og operatør med flere værdier (switch, case, switch). I tidlige sprog på lavt niveau implementeres forgrening gennem den betingede filialoperatør .
Den betingede operatør implementerer udførelsen af visse kommandoer, forudsat at et eller andet logisk udtryk (betingelse) tager værdien "sand" true. På de fleste programmeringssprog begynder en betinget erklæring med et nøgleord if(oversat fra engelsk - "hvis"). Der er følgende former for den betingede operatør - med en gren og to.
Når man udfører en betinget sætning med én gren if <условие> then <команды> end, evalueres betingelsen, og hvis den er sand, endudføres kommandoerne op til nøgleordet, ellers fortsætter programudførelsen med kommandoen efter den betingede sætning. På lavniveausprog ( assemblers ) er dette den eneste tilgængelige form for den betingede erklæring. På nogle sprog bruges et særligt nøgleord til en betinget operator med én gren (normalt denne then, oversat fra engelsk - "det").
Når du udfører en betinget operator med to grene if <условие> then <команды1> else <команды2> end , hvis betingelsen er sand, udføres kommandoerne efter nøgleordet ; hvis betingelsen er thenfalsk, udføres kommandoerne efter nøgleordet else. Hvis det er nødvendigt at kontrollere flere forhold sekventielt, er det muligt at kaskadere betingede udsagn:
if condition 1 then commands 1 else if condition 2 then commands 2 else if condition 3 then commands 3 ... else if condition N + 1 then commands N + 1 else commands end ;I dette tilfælde vil betingelserne blive kontrolleret sekventielt, og så snart sand er opfyldt, vil det tilsvarende sæt af kommandoer blive udført, og udførelsen vil gå til kommandoen efter den betingede sætning. Hvis ingen af betingelserne er sande, udføres kommandoerne fra grenen else.
En række programmeringssprog indeholder en speciel konstruktion til cascading af betingede udsagn, som giver dig mulighed for at skrive flere forgreninger noget mere kompakt og mindre tilbøjelige til at skrive fejl:
if condition1 then commands1 elsif condition2 then commands2 elsif condition3 then commands3 ... else commands end ; rækkefølgen for udførelse af denne sætning svarer nøjagtigt til ovenstående kaskade af simple if-then-else-sætninger, og forskellen er rent formel: i stedet for indlejrede flere betingede sætninger, er denne konstruktion en enkelt helhed og indeholder et ekstra nøgleord elsif, der kræver et andet tilstand efter sig.Pascal arvede syntaksen fra Algol -60, ifølge hvilken kun én kommando kan placeres i grenene af en betinget operator. Derfor, for at rumme flere kommandoer der, grupperes de i en sammensat sætning ved hjælp af nøgleordsparet beginog end. Den anden gren er valgfri. beginog ender kun nødvendige, hvis der er flere operatører (f.eks. af hensyn til kodeens ensartethed ). I eksemplet er valgoperatoren i Pascal:
Hvis betingelse, så start udsagn ; end else start statements ; ende ;Behovet for en betinget operatør i Algol og Pascal er blevet kritiseret siden starten. Kritikere sagde, at adskillige sammensatte sætninger roder programmet, forstyrrer normal indrykning og fremkalder fejl (hvis du glemmer den sammensatte sætning, hvor den er nødvendig i den sidste gren af if-sætningen, vil compileren ikke bemærke noget, men når du udfører et program fra en gruppe af udsagn, der skal udføres i denne gren, i henhold til betingelsen, vil kun den første blive udført, alle resten - altid). De næste generationer af sprog - efterkommere af Algol forsøgte at slippe af med denne mangel. Blandt dem er tre almindeligt kendte sprog: Algol-68 , Modula-2 og Ada . Konstruktionen af if-sætningen i dem er næsten den samme, op til individuelle søgeord:
I alle tilfælde er "commandX" et vilkårligt antal udsagn adskilt af semikolon. I alle tilfælde er alle grene af den betingede erklæring, undtagen den første ("dengang"-grene), valgfri og kan springes over. Hvis der ikke er nogen "andet"-gren, og ingen af betingelserne er opfyldt, overføres kontrollen til kommandoen efter nøgleordet for betinget fuldførelse (END, FI eller END IF).
C og C++ (og efter dem Java , C# , PHP og mange andre sprog) har en betinget operator, der strukturelt ligner Pascal. beginForskellen er, at betingelsen skal skrives i parentes, og endkrøllede parenteser bruges i stedet for nøgleord {}:
hvis ( < betingelse > ) { < operatører > } andet { < operatører > }I Nemerle , i modsætning til de fleste sprog, hvor en operator ifkan have enten en eller to grene, skal en operator if(syntaksen er fuldstændig magen til C-sproget) have to grene. En betinget operator med en gren begynder med nøgleordet when, derudover har sproget en anden betinget operator - unless, som er en "omvendt når" - i den udføres kommandoerne fra den betingede gren, hvis betingelsen er falsk.
when ( condition ) { statements } unless ( condition ) { statements }I Forth har den betingede operator en anden form end på andre sprog på grund af postfix-notationen og stakorganiseringen. Den betingede operator består af tre ord IF ELSE THEN[1] .
< betingelse > HVIS < udtryk _1_ hvis _ betingelse _ er sand > ELSE < udtryk _2_ hvis _ betingelse _ er falsk > SÅHer <условие>skubber den bare værdien oven på stakken, IFanalyserer flaget, og hvis:
Hvis fraværende ELSE, opnås en vælger med én gren: udtryk mellem IFog THENudføres kun, hvis flaget ikke er nul.
Fortran havde i starten kun aritmetisk IF , hvor der afhængigt af udtrykkets fortegn blev lavet en overgang til en af de tre etiketter. For eksempel en del af koden for kvadratisk ligningsløserrutine:
DN = B * B - 4 * A * C IF ( DN ) 90 , 10 , 10 10 D = SQRT ( DN ) X1 = ( - B + D ) / ( 2 * A ) X2 = ( - B - D ) / ( 2 * A )Derefter blev logiske (booleske) udtryk tilføjet og en logisk IF med én sætning, evalueret af GOTO, senere - en strukturel IF (med flere betingelser), for eksempel:
DN = B * B - 4 * A * C _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 2 * A ) ELSE !(ingen kode for negativ diskriminant) SLUT HVISPerl understøtter den multi-betingede if-struktur, såvel som sætningsmodifikatorer, som er skrevet efter den del af sætningen, der udføres. For eksempel er de følgende to eksempler identiske i funktionalitet:
if ( $a == 0 ) { ++ $nul_antal ; } ++ $nul_antal hvis $a == 0 ;I stedet for if, kan du skrive med mindre, hvilket får værdien af det betingede udtryk til at blive inverteret før kontrol. Samme handling gennem, medmindre:
++ $nul_antal, medmindre $a != 0 ;For en sammensat sætning (blok) er kun den strukturelle form tilladt, ikke modifikatoren. For eksempel:
if ( $a == 0 ) { ... } else if ( $a > 0 ) { ... } else { ... }Det endelige søgeord er ikke nødvendigt på grund af kravet om, at udsagn under betingelserne skal formateres i blokke {...}.
Der er ingen ækvivalent med medmindre for elsif-grene.
Erlang bruger to betingede udsagn - hvis og sag. Begge har en resultatværdi, der er lig med værdien af den sidste sætning i den udførte gren og kan bruges (tildelt til et navn, videregivet til en funktion...), så der er ingen separat ternær betinget sætning i den . I case-opgørelsen udføres Pattern Matching med mulighed for yderligere betingelser på værdierne i den sammenlignede, og i if-sætningen kun tilstandstestning. Beskyttelsestest tillader et begrænset sæt operationer og indbyggede funktioner.
Sagseksempel (sletning af en begivenhedspost fra tidstræet):
{ NewEBW , NewEBN } = case dict : find ( EBN , Node ) af fejl -> { EBW , EBN }; { ok , Expiry } -> { gb_trees : delete_any ({ Expiry , Node }, EBW ), dict : erase ( Node , EBN )} end ,Eksempler på hvis:
if NeedLater -> erlang : send_after ( trunc ( 1000 * ( 1 + Elapsed )), self (), i_apply_nodes_portion ); sandt -> nej ende , Efter2 = hvis %% Hvis det var for langt siden, planlæg timeout med det samme. Efter1 =< ? EXPIRY_STEP_MIN -> ? EXPIRY_STEP_MIN ; Efter1 >= ? EXPIRY_STEP_MAX -> ? EXPIRY_STEP_MAX ; sand -> Efter 1 slutning ,Afbryderens design har flere (to eller flere) grene. Switchen udfører en given gren afhængigt af værdien af det evaluerede nøgleudtryk. Den grundlæggende forskel mellem denne instruktion og en betinget operator er, at det udtryk, der bestemmer valget af den eksekverbare gren, ikke returnerer en logisk, men en heltalsværdi eller en værdi, hvis type kan castes til et heltal. Nogle sprog tillader, at nogle udtryk af typen ikke-heltal (for eksempel tekststrenge) kan bruges i en switch.
Prototypen på den moderne syntaktiske konstruktion var springinstruktionen, der blev brugt i de gamle programmeringssprog. Denne kommando specificerede et vælgerudtryk, der returnerede en heltalsværdi og et sæt etiketter. Da kommandoen blev udført, blev udtrykket evalueret, og dets værdi blev brugt som nummeret på den etiket (i kommandolisten), som overgangen blev foretaget til. Sådanne konstruktioner var for eksempel i programmeringssprogene Fortran ("computed GOTO") og BASIC . Den attraktive side af designet er dets ret høje effektivitet: for at bestemme den ønskede gren (springmarkør) er det ikke nødvendigt at sekventielt sammenligne resultatet af vælgerudtrykket med mange værdier, det er nok at gemme en række ubetingede springinstruktioner med de nødvendige adresser i hukommelsen, så når kommandoen udføres, beregnes det ønskede element direkte ud fra udtryksværdier. I dette tilfælde afhænger hastigheden af kommandoudførelsen ikke af antallet af etiketter. På moderne sprog er implementeringen af en switch-sætning også ofte implementeret som en jump-tabel, der består af ubetingede springkommandoer til de tilsvarende kodefragmenter. Udtrykket, der skal evalueres, konverteres til en jump table shift-værdi, der specificerer den kommando, der skal udføres. På sprog, hvor selektorudtrykket kan have en ikke-heltalsværdi, er det langt fra altid muligt direkte at evaluere den ønskede gren af switchkonstruktionen, så de bruger andre metoder til at optimere eksekveringen.
I moderne programmeringssprog på højt niveau har en switch-kommando normalt et navn switch(oversat fra engelsk - "switch") eller case(oversat fra engelsk - "case"). Imidlertid kan beregnet etiketvalg bevares i moderne programmeringssprog på lavt niveau, såsom JL-instruktionen i STL-programmeringssproget til de programmerbare logiske controllere S7-300 og S7-400 fremstillet af Siemens .
For eksempel i C er kommandosyntaksen:
skifte ( i ) { tilfælde 0 : case 1 : // sekvens af udsagn bryde ; case 2 : // sekvens af udsagn bryde ; standard : ; }Her er i et vælgerudtryk, der skal være af en heltals-castbar type, hver gren af udførelse begynder med nøgleordet case, efterfulgt af værdien af det udtryk, som denne gren skal udføres under. Et interessant træk ved C-sproget er, at switchen i det tolkes nøjagtigt som en kommando til at hoppe på en beregnet etiket, og grenoverskrifterne ( case значение :) spiller rollen som etiketter. For at afslutte switch-sætningen, efter at filialkoden er fuldført, bruges en speciel kommando break. Hvis der ikke er en sådan kommando i grenen, efter udførelsen af koden for den valgte gren, vil udførelsen af koden efter den begynde. Denne funktion kan bruges til optimering, selvom den kan forårsage svære at finde fejl (hvis programmøren ved et uheld går glip af en pause, vil compileren ikke kaste en fejl, men programmet vil køre forkert). Standardgrenen udføres, når ingen af de andre grene er egnede.
Syntaksen for C switch-kommandoen nedarves af mange sprog, men dens semantik er ikke altid fuldstændig C-lignende. For eksempel giver C# dig mulighed for at bruge et strengtypevælgerudtryk og passende etiketter.
Rækkefølgen for udførelse af et program med betingede udsagn kan blive væsentligt påvirket af logikken i evalueringen af betingede udtryk, der er vedtaget på sproget. Når betingelsen er et komplekst boolesk udtryk, såsom "f(x) > 0 OG g(y) > 0", er der to strategier til at evaluere dets resultat:
Den anden mulighed er den mest almindelige for industrielle sprog (især for Algol, Fortran, C++, C, Java, JavaScript, ECMAScript, JScript, C#, Python). Disse sprog har en streng regel: "Et logisk udtryk evalueres altid fra venstre mod højre, og dets evaluering stopper, så snart resultatet af hele udtrykket bliver defineret." Det betyder, at hvis et udtryk består af flere underbetingelser kombineret med AND-operatoren (AND), så stopper evalueringen af udtrykket, så snart en af underbetingelserne viser sig at være falsk (da "falsk AND enhver værdi" altid resulterer i "falsk") og omvendt, hvis flere underbetingelser kombineres med OR-operatoren (OR), stopper evalueringen efter den første sande underbetingelse, da hele udtrykket i dette tilfælde er sandt, uanset yderligere evaluering. Men et udtryk, der indeholder den eksklusive OR-operator (XOR), kan ikke evalueres fuldt ud, da en af værdierne i det ikke kan bestemme resultatet af beregningen af hele udtrykket.
Sprogene Ada og Erlang bruger forskellige nøgleord til disse varianter: ordene og og eller betyder fuld evaluering, og og derefter, ellers (Ada), og også, orelse (Erlang) - ufuldstændig. I Erlang har andalso og orelse lavere forrang end sammenligningsoperatorer, hvilket undgår parenteser omkring elementære forhold. Visual Basic .NET-sproget har lignende nøgleord: AndAlso og OrElse.
Den faste evalueringsrækkefølge af underbetingelser (det logiske udtryk evalueres altid fra venstre mod højre) introduceres for at kunne styre evalueringsrækkefølgen af udtrykket og indsætte først de forhold, der skal evalueres først. Det er i øvrigt sådan, logiske udtryk adskiller sig fra aritmetiske udtryk, for hvilke rækkefølgen af underudtryksevaluering på de fleste sprog (medmindre den er bestemt af operationernes prioritet og associativitet) ikke er specificeret af sproget og kan være anderledes i forskellige sager.
Valget af denne særlige eksekveringslogik skyldes, at den giver dig mulighed for at forenkle de logiske udtryk, der bruger afhængige elementer. Det klassiske eksempel er en lineær søgning i et array:
// Søg i en matrix af heltal i Pascal-sprog // Parametre - den ønskede værdi og en åben matrix af heltal // Resultat - indekset for det fundne element eller -1 hvis elementet ikke er fundet funktion Find ( e : heltal ; var a : matrix af heltal ) : heltal ; var i : heltal ; begynde i := 0 ; mens ( i <= Høj ( a )) AND ( a [ i ] <> e ) do inc ( i ) ; //!!! hvis i <= Høj ( a ) så Find := i andet Find := - 1 ; ende ;Algoritmen implementeret af programmet er ret indlysende, men der er en subtilitet i implementeringen (se linjen markeret med udråbstegn): sløjfebetingelsen består af to dele forbundet af AND-operatoren. Den første underbetingelse kontrollerer, om indeks i er gået ud over arrayet, den anden kontrollerer, om det aktuelle element i arrayet ikke er lig med den ønskede værdi. Hvis arrayet ikke indeholder den ønskede værdi, vil værdien af variablen i, efter at have kontrolleret det sidste element, stige med én; ved næste iteration vil den første underbetingelse være falsk, og løkken slutter uden at kontrollere den anden underbetingelse. Hvis de logiske udtryk blev evalueret fuldt ud, så hvis der ikke var noget element i arrayet efter den sidste iteration, ville der opstå en fejl: et forsøg på at bestemme a[i] ville forårsage en forkert hukommelsesadgang.
Det skal bemærkes, at ud over ufuldstændig evaluering af udtrykkets værdi, spiller den faste rækkefølge for evaluering af underbetingelser også en væsentlig rolle her: da checken for out-of-bounds-array skrives først, vil den altid være udføres før kontrollen for at nå den ønskede værdi. Hvis rækkefølgen, som underudtrykkene blev evalueret i, var udefineret, ville det være umuligt at garantere rigtigheden af det givne programfragment.
Med den fulde beregning af logiske udtryk skal ovenstående algoritme skrives omtrent i følgende form:
// Søg i en matrix af heltal på Pascal-sprog // Hypotetisk variant med fuld evaluering af logiske udtryk // Parametre - den ønskede værdi og en åben matrix af heltal // Resultat - indekset for det fundne element eller -1 hvis elementet blev ikke fundet funktion Find ( e : heltal var a : matrix af heltal ) : heltal ; _ var i : heltal ; f : boolesk ; // yderligere variabel-loop termineringsflag begynder i := 0 ; f := falsk ; mens ikke f gør hvis i > Høj ( a ) så f := sand andet hvis a [ i ] = e så f := sand andet inc ( i ) ; hvis i <= Høj ( a ) så Find := i andet Find := - 1 ; ende ;Som du kan se, var vi nødt til kunstigt at indstille rækkefølgen, som udgangsbetingelserne blev beregnet i, og indføre en ekstra variabel. Det er for at undgå sådanne tricks, at den ufuldstændige evaluering af logiske udtryk introduceres.
Bemærk: Koden ovenfor er et eksempel på brug af IF-sætningen, men ikke mere. Denne kode kan ikke bruges som regel til at skrive algoritmer i Pascal.
Den optimale algoritme til at finde et tal i et array er:
funktion Find ( e : heltal ; var a : matrix af heltal ) : heltal ; var i : heltal ; begynde Resultat := - 1 ; for i := Lav ( a ) til Høj ( a ) begynder hvis a [ i ] = e , så begynder Resultat := i ; bryde ; ende ; ende ; ende ;