Cadeia de caracteres

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Esta página ou secção não cita fontes confiáveis e independentes, o que compromete sua credibilidade (desde fevereiro de 2011). Por favor, adicione referências e insira-as corretamente no texto ou no rodapé. Conteúdo sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)

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.

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 da inclusão/exclusão de elementos ou pela da 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.

Nas linguagens formais, uma cadeia de caracteres é uma sequência finita de símbolos escolhidos a partir de conjunto denominado alfabeto.

Teoria formal[editar | editar código-fonte]

Seja Σ 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 Σ.

  • Se o alfabeto Σ = {0, 1}, então 0, 1, 01, 000001 e 101 são cadeias sobre o alfabeto Σ.

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 λ.

  • Se o alfabeto Σ = {0, 1}, então |00| = 2, |0101| = 4 e |ε| = 0.'

O conjunto de todas as possíveis cadeias de tamanho n sobre um alfabeto Σ qualquer de tamanho é denotado por Σn.

  • Se o alfabeto Σ = {0, 1}, então Σ² = {00, 01, 10, 11}. Notar que Σ0 = {ε} para qualquer alfabeto Σ.

O conjunto de todas as possíveis cadeias sobre Σ de qualquer tamanho é denotado por Σ*. Em termos de Σn, Σ* = Σ0 ∪ Σ1 ∪ Σ2….

  • Se o alfabeto Σ = {0, 1} então Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, …}.

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-cadeias[editar | editar código-fonte]

Concatenaçã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; par 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áfica[editar | editar código-fonte]

Geralmente é 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 dado[editar | editar código-fonte]

Um 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.

Ícone de esboço Este artigo sobre programação de computadores é um esboço. Você pode ajudar a Wikipédia expandindo-o.