Cadena (ordinador)
Aquesta entrada o secció de programació no cita les fonts necessàries o els presents són insuficients . |
Una cadena d’ informàtica és una seqüència de caràcters amb un ordre predeterminat. Les seqüències d'altres tipus de dades s'anomenen vectors o, en anglès, matrius .
Característiques
Pot estar compost de bytes en el cas de cadenes amb codificació ASCII o de paraules per a codificacions Unicode i UTF .
Sovint, la seqüència de dades que compon una cadena es conclou amb un caràcter especial anomenat NULL (com en el llenguatge C ) que serveix per indicar el final de la cadena, fins i tot si hi ha diferents mètodes de representació, alguns dels quals utilitzen un altre terminator o es basen en altres sistemes per determinar la longitud (per exemple, una dada que conté la longitud de la cadena emmagatzemada per separat).
En molts llenguatges de programació, com ara Java o C #, la cadena, per motius de seguretat, és un objecte no modificable (a Java fins i tot no es pot ampliar ). Això significa que sempre que s’assigna un valor nou a una cadena (concatenació, eliminació o addició de caràcters), es creen noves cadenes.
Per exemple, a C ++, la sentència
cadena a = "abc" + "def" ;
en realitat crea 4 cadenes: la cadena per representar a , la que representa "abc" , la que representa "def" i, finalment, la que emmagatzema el valor temporal "abcdef" . Precisament per aquest motiu, llenguatges com Java i C # proporcionen altres objectes, com StringBuffer o StringBuilder, que permeten operacions en cadenes que són més ràpides i menys costoses en termes d’ús de memòria.
Tipus de dades "cadena"
Un tipus de dades de cadena és un tipus de dades basat en la idea d’una cadena formal. Les cadenes són un tipus de dades tan important i útil que formen part de gairebé tots els llenguatges de programació . En alguns idiomes, només hi ha disponibles tipus primitius i en altres com a tipus compost.
Tot i que les cadenes formals poden tenir una longitud arbitrària (però finita), les cadenes dels llenguatges de programació tenen una longitud limitada. En general, hi ha dues categories de tipus de dades de cadena: cadenes de longitud fixa , que tenen una longitud màxima fixa, i cadenes de longitud variable , la longitud dels quals es pot canviar amb instruccions específiques. La majoria de cadenes dels llenguatges de programació moderns tenen una longitud variable. Malgrat el nom, fins i tot les cadenes de longitud variable tenen un límit de longitud; no obstant això, en general, el límit només depèn de la quantitat de memòria disponible a l'ordinador.
Els tipus de dades de cadenes també difereixen en funció de l’alfabet on es defineixen. Algunes cadenes estan dissenyades per funcionar en un sol alfabet prefixat (com ara l' alfabet llatí o no com a caràcters representables pel codi ASCII ) i d'altres en un alfabet arbitrari. Per exemple, a la biblioteca estàndard de C ++ , les cadenes es parametritzen amb l'alfabet de caràcters.
Representacions
La representació de les cadenes depèn principalment de l'elecció del conjunt de caràcters a utilitzar (com a alfabet) i del mètode de codificació dels caràcters (vegeu codificació de caràcters ). Les implementacions de cadenes més antigues es van dissenyar per funcionar amb conjunts de caràcters i codificacions definides per ASCII , o amb extensions més noves com la sèrie ISO 8859 . Les implementacions modernes solen utilitzar el gran conjunt de caràcters definit com Unicode juntament amb una gran varietat de codificacions complexes com UTF-8 i UTF-16 .
La majoria d’implementacions de cadenes s’assemblen a matrius els elements dels quals contenen codis corresponents als caràcters del conjunt de caràcters corresponent. La principal diferència és que en algunes codificacions l'equivalent a un sol caràcter lògic pot requerir diversos elements de la matriu. Un exemple d'això és la codificació UTF-8 on un sol caràcter lògic pot ocupar fins a quatre bytes. En aquests casos, la longitud lògica de la cadena difereix de la de la matriu.
La longitud d'una cadena es pot emmagatzemar implícitament mitjançant un caràcter de terminació especial. Aquest caràcter sol ser el caràcter nul o NULL que té un codi zero, una convenció que s’utilitza i perpetua pel popular llenguatge de programació C. La longitud d'una cadena també es pot emmagatzemar explícitament, per exemple, adjuntant un prefix amb un valor enter a la cadena, una convenció que s'utilitza per exemple a Pascal . Tingueu en compte que en el cas de cadenes finalitzades, el caràcter de terminació mai no serà admissible com a contingut d'una cadena.
Aquí teniu un exemple de cadena de terminació zero (o de terminació nul·la ) emmagatzemada en un buffer de 10 bytes, juntament amb la seva representació ASCII.
| F. | R. | A | No. | K. | NUL | k | I | f | w |
| 46 | 52 | 41 | 4E | 4B | 00 | 6B | 65 | 66 | 77 |
La longitud de la cadena és de 5 caràcters en aquest exemple, però ocupa 6 bytes. Els caràcters després de la finalització (6B 65 66 77, respectivament kefw a ASCII) no formen part de la cadena, podrien formar part d’una altra cadena, ja que simplement es malgasten.
La cadena equivalent a Pascal:
| llargada | F. | R. | A | No. | K. | k | f | f | w |
| 05 | 46 | 52 | 41 | 4E | 4B | 6B | 66 | 66 | 77 |
Al costat d’aquestes representacions comunes, altres són possibles.
L’ús de cordes (també anomenades cordes de pes pesat ) pot fer que determinades operacions com ara insercions, supressions i concatenacions siguin més eficients. [1]
Algorismes per a cadenes
S'han estudiat molts algorismes per a la manipulació de cadenes que es distingeixen per propòsit i per diferents opcions de compromís davant necessitats contrastades com l'amplitud del rang i l'eficiència.
Aquests algoritmes es situen en categories com les següents:
- Algoritmes de cerca de cadenes amb la tasca de trobar una subcadena determinada o una configuració de caràcters determinada,
- Algorismes d' ordenació (ordenació)
- Algorismes d’ expressió regular ,
- Escàners i analitzadors de cordes.
Els algoritmes més avançats per processar cadenes sovint utilitzen mecanismes formals elaborats i estructures de dades complexes, com ara arbres de sufixos i màquines d'estats finits .
Utilitats de llenguatges i llenguatges orientats al processament de cadenes
Les cadenes són un tipus de dades tan àmpliament utilitzat que indueixen el desenvolupament de nombrosos llenguatges destinats a facilitar el processament de les cadenes més sol·licitades per les aplicacions. Entre aquests hi ha:
Moltes utilitats d’ àmbit Unix realitzen manipulacions de cadenes relativament senzilles i es poden utilitzar per programar algoritmes de processament de cadenes força eficaços. Aquestes eines també poden tractar fitxers i fluxos acabats com a cadenes.
Els llenguatges de script recents, com Perl , Python , Ruby i Tcl , utilitzen expressions regulars per facilitar la manipulació del text.
