Baixe o app para aproveitar ainda mais
Prévia do material em texto
Bibliotecas da linguagem C e Algoritmos de Ordenação #include <stdio.h> Biblioteca de Entrada e Saída Padrão Principal funcionalidade •Todo programa em C que usar funções para entrada ou saída de dados como o resgate de valores digitados pelo usuário ou então exibição de mensagens de retorno exigirá a inclusão do cabeçalho stdio.h. Entrada e Saída 1.“printf”: A função (print formatted) exibe na tela do monitor uma lista “formatada” de números, caracteres, strings etc. O primeiro argumento da função é uma string que especifica o formato da impressão 2.“scanf”: A função (scanf format) lê do teclado e “formata” uma lista de números, caracteres, strings etc. O primeiro argumento da função é uma string que especifica o formato da lista a ser lida. Os demais argumentos são os endereços das variáveis onde os valores lidos, serão armazenados. A função trata todos os espaços em brancos como se fossem ‘ ‘. Exemplo de programa em C que calcula volume de uma Esfera Arquivos Para que um programa possa manipular um arquivo, é preciso associar a ele uma variável do tipo FILE (esse tipo está definido no arquivo-interface stdio.h). A operação de associação é conhecida como "abertura" do arquivo e é executada pela função fopen (= file open). O primeiro argumento da função é o nome do arquivo e o segundo argumento é "r" ou "w" para indicar se o arquivo deve ser aberto "para leitura" (= read) ou "para escrita" (= write). A função devolve o endereço de um FILE (ou NULL, se não encontra o arquivo especificado).Depois de usar o arquivo, é preciso "fechá-lo" com a função fclose (= file close). Digamos que o arquivo dados.txt contém uma sequência de números inteiros separados por brancos. O programa abaixo calcula a média dos números. Para ler o arquivo, o programa usa a função fscanf (abreviatura de file scanf): Programa que calcula média entre dois números usando arquivos Funções putc e getc A função mais básica de entrada de dados — mais básica que printf — é putc (= put character). Cada invocação da função grava um caractere no arquivo especificado. Se c é um caractere e f aponta um arquivo, putc( c, f) grava c no arquivo f. Por exemplo, putc( '*', stdout) exibe um * na tela do monitor. A função correspondente de leitura de caracteres é getc (= get character). Cada chamada da função lê um caractere do arquivo especificado. Se f aponta um arquivo então getc( f) lê o próximo caractere do arquivo. Em particular, getc( stdin) lê o próximo caractere do teclado. Funções stdin e stdout Qualquer processo (programa) tem 3 ficheiros automaticamente abertos : o da entrada padrão ( standar input), o da saída padrão ( standard output), e o da saída de erro ( standard error output). A menos que redirecionados, estão normalmente associados ao terminal, isto é , ao teclado, ao monitor e monitor respectivamente. A cada um destes ficheiros corresponde uma constante, definida em stdio.h que o identifica: •stdin standard input (teclado) •stout standard output (monitor) •stderr standard error (monitor) • O programa abaixo lê uma linha de caracteres do teclado, armazena essa linha em um vetor e em seguida exibe esses caracteres na tela do monitor. vamos supor que a linha tem no máximo 100 caracteres (incluindo o '\n' final): #include <ctype.h> Biblioteca de manipulação de caracteres Principal funcionalidade •A Biblioteca ctype.h contém funções e macros(um padrão de entrada deve ser substituído por um padrão de saída) para manipulação de caracteres. •Utilizando as funções desta biblioteca podemos verificar se um caractere é alfabético, numérico, se é maiúsculo, minúsculo, representa espaço em branco, etc. funções para conversão de caracteres maiúsculos e minúsculos: •Tolower() Converte o caractere de maiúsculo para minúsculo. •Toupper() Converte caractere de minúsculo para maiúsculo. funções para manipulação de caracteres : •isalnum() Verifica se o caractere é alfanumérico. •isalpha() Verificar se o caractere é uma letra do alfabeto. •iscntrl() Verificar se o caractere é um caractere de controle. funções para manipulação de caracteres : •isgraph() Verifica se o caractere tem representação gráfica. •islower() Verifica se o caractere é uma letra minúscula. •isupper() Verifica se o caractere é uma letra maiúscula. funções para manipulação de caracteres : •isprint() Verifica se o caractere é imprimível. •ispunct() Verifica se o caractere é um ponto. •isspace() Verificar se o caractere é um espaço em branco. funções para manipulação de caracteres : •isdigit() Verificar se o caractere é um número decimal. •isxdigit() Verifica se o caractere é um número hexadecimal. Exemplos •Tolower(),Toupper(): Exemplos •Isalpha(): Exemplos •Isdigit(): 1.QuickSort 2.BucketSort Algoritmos de Ordenação QuickSort •Baseia-se em um padrão de projeto fundamental para solução de problemas conhecida como Divisão e Conquista (Divide-and-Conquer). •O padrão pode ser descrito, de maneira geral, como sendo composto de 3 fases: 1.Divisão: divide-se os dados de entrada em dois ou mais conjuntos disjuntos (separados); 2.Recursão: soluciona-se os problemas associados aos subconjuntos recursivamente; 3.Conquista: obtém-se as soluções dos subproblemas e junta-se as mesmas em uma única solução. QuickSort (Características Gerais) •Inicialmente, o vetor de chaves C é particionado em três segmentos S1, S2 e S3. •S2 deverá conter apenas UMA chave denominada pivô. •S1 deverá conter todas as chaves cujos valores são MENORES ou IGUAIS ao pivô. Esse segmento está posicionado à esquerda de S2. •S3 deverá conter todas as chaves cujos valores são MAIORES do que o pivô. Esse segmento está posicionado à direita de S2. Princípio de Classificação/Ordenação •O particionamento é reaplicado aos segmentos S1 e S3 e a todos os segmentos correspondentes daí resultantes com quantidade de chaves MAIOR que 1. •Quando não restarem segmentos a serem particionados, o vetor estará ordenado. •Perguntas: 1.Qual é o pivô ideal ? 2.Como escolher este pivô ? QuickSort (Escolha do pivô) •O pivô ideal é aquele que produz segmentos S1 e S3 com tamanhos (aproximadamente) iguais: chave de valor mediano. •A identificação do pivô ideal requer a varredura de todo o vetor (o benefício não justifica o custo). •Deseja-se um critério de escolha simples e rápido. •Sem conhecimento prévio sobre a distribuição de valores das chaves, supõe-se que qualquer uma possa ser o pivô e arbitra-se, por exemplo, a primeira chave. •Caso o vetor já se encontre parcialmente ordenado, pode-se utilizar o elemento médio. QuickSort: Análise de Desempenho •Melhor caso: particionamento produz segmentos com mesmo tamanho. •Pior caso: Ocorrerá sempre que o vetor já estiver ordenado ou em ordem inversa e escolhermos a menor (ou maior) chave como particionadora. BucketSort •Bucket sort, é um algoritmo de ordenação que funciona dividindo um vetor em um número finito de recipientes. Cada recipiente é então ordenado individualmente, seja usando um algoritmo de ordenação diferente, ou usando o algoritmo bucketsort recursivamente. O bucketsort tem complexidade linear (Θ(n)) quando o vetor a ser ordenado contém valores que são uniformemente distribuídos. Vantagens e Desvantagens • O algoritmo de BucketSort é rápido. • Possui uma estabilidade através de remoção do primeiro elemento dasequência. • É eficiente para entradas de grande quantidade de valores. • Complexidade no pior caso é O(n). • Não recomendado para pequenas quantidades de entrada. Código Funcionamento do Código •Bucket sort funciona do seguinte modo: 1. Inicializa um vetor de "baldes", inicialmente vazios. 2. Vai para o vetor original, incluindo cada elemento em um balde. 3. Coloque os elementos dos baldes que não estão vazios no vetor original ordenadamente. Referências Página de Tutoriais para programação do GNU/Linux Ubuntu http://manpages.ubuntu.com/ Página do professor da USP Paulo Feofiloff http://www.ime.usp.br/~pf/algoritmos/aulas/io.html
Compartilhar