|
Cadeia de caracteres
Na programação de computadores, uma cadeia de caracteres ou string é uma sequência de caracteres, geralmente utilizada para representar palavras, frases ou textos de um programa.[1] Nas maioria das linguagens de programação, as cadeias de caracteres podem ser expressas tanto na forma literal, como através de algum tipo de variável. Quando expressos através de variáveis, o conteúdo da cadeia geralmente pode ser alterado pela inclusão/exclusão de elementos ou pela substituição de seus elementos por outros elementos, formando uma nova cadeia. Assim, uma cadeia de caracteres é vista como sendo um tipo de dado e normalmente é implementada através de um arranjo de bytes que armazena os elementos da cadeia em sequência, utilizando alguma codificação preestabelecida.[2] Nas linguagens formais, uma cadeia de caracteres é uma sequência finita de símbolos escolhidos a partir de conjunto denominado alfabeto.[2] Teoria formalSeja Σ um conjunto finito e não vazio de símbolos (ou caracteres) chamado de o alfabeto. Uma cadeia sobre Σ é qualquer sequência finita de caracteres contidos em Σ.[3]
O comprimento ou cardinalidade da cadeia é a quantidade de caracteres utilizados para sua composição. À cadeia de comprimento zero dá-se o nome de cadeia vazia e é usualmente denotada na literatura pelos símbolos ε ou λ.
O conjunto de todas as possíveis cadeias de tamanho n sobre um alfabeto Σ qualquer de tamanho é denotado por Σn.
O conjunto de todas as possíveis cadeias sobre Σ de qualquer tamanho é denotado por Σ*. Em termos de Σn, Σ* = Σ0 ∪ Σ1 ∪ Σ2….
Apesar do conjunto Σ* possuir infinitos elementos, todos os elementos de Σ* possuem comprimento finito. Um conjunto de cadeias sobre um alfabeto Σ (isto é, qualquer subconjunto de Σ*) é chamado de linguagem formal sobre Σ. Concatenação e sub-cadeiasConcatenação é uma importante operação binária em Σ*. Para qualquer duas cadeias s e t em Σ*, sua concatenação é definida pela sequência de caracteres de s seguida pela sequência de caracteres em t, denotada por st. Por exemplo se Σ = {a, b, …, z}, s = bear e t = hug, então st = bearhug e ts = hugbear. A concatenação de cadeias é uma operação associativa, mas não comutativa. A cadeia vazia serve como um elemento identidade: para qualquer cadeia s, εs = sε = s. Portanto, o conjunto Σ* e a operação de concatenação formam um monóide. A cadeia s é dita uma subcadeia (ou fator) de t se existem cadeias (possivelmente vazias) u e v de forma que t = usv. Ordenação lexicográficaGeralmente é necessário definir uma ordenação em um conjunto de cadeias. Se um alfabeto Σ possui uma relação de ordem (como a ordem alfabética) pode-se definir uma relação de ordem em Σ* chamada ordem lexicográfica. Note que como Σ é finito, é sempre possível definir uma ordenação em Σ e portanto em Σ*. Por exemplo, se Σ = {0, 1} e 0 < 1, então a ordenação lexicográfica em Σ* é ε < 0 < 00 < 000 < … < 011 < 0110 < … < 01111 < … < 1 < 10 < 100 < … < 101 < … < 111 … Cadeia de caracteres como tipo de dadoUm tipo de dado cadeia de caracteres (referido em programação geralmente como string) é uma modelagem de uma cadeia formal de caracteres. São bastante usados em programação, sendo implementados em quase todas as linguagens de programação. Em algumas linguagens esse tipo é definido nativamente, em outras é um tipo composto, derivado. Referências
|
Portal di Ensiklopedia Dunia
