Aula 02 - TAD - Structs [Reparado]

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Aula 02 – Tipos Abstratos de Dados (TAD)
DCC 302 – Estrutura de Dados I
Prof. Acauan Ribeiro
Tipos de Dados - Conceitos
Tipo de Dados: Define o conjuntos de valores (domínio) que uma variavel pode assumir.
Ex.: int
…-2, -1 , 0 , 1, 2, 3…
Para cada dado armazenado no computador, devemos definir o conjunto de valores que ele pode assumir. Denominamos a esse conjunto de tipo de dados. Por exemplo, um dado (variável) do tipo lógico pode assumir o valor verdadeiro ou falso .
Estrutura de Dados: Trata-se de um relacionamento lógico entre os tipos de dados.
Tipos de Dados Simples
Tipo de dados compostos
A partir desses tipos de dados simples, podemos agrupá-los e formar outros tipos de dados, os quais denominamos de dados compostos. Os tipos de dados compostos derivam dos tipos simples e são úteis para armazenar grandes quantidades de um tipo de dados. Por exemplo, quando há necessidade de armazenar uma frase inteira ou, os tempos dos atletas que disputaram uma corrida. 
Nestes dois exemplos, podemos criar tipos compostos que atendam às necessidades de cada problema. Para armazenar uma frase inteira podemos usar o tipo char que armazena caracteres, como as letras 'a', 'b' e 'x', para formar um vetor de caracteres, que denominamos de strings. Seguindo a mesma linha de raciocínio, podemos criar um vetor do tipo double para armazenar os tempos
Tipo de dados compostos
Veremos a seguir os dois principais tipos de dados compostos,
são eles:
Vetor: É um conjunto de dados do mesmo tipo. Os vetores podem ser do tipo numérico, que armazenam valores do tip inteiro, tais como float, double, ou vetores que armazenam dados literais, que armazenam textos, podendo ser um caracter ou string.
Matriz: Conceitualmente, uma matriz é o vetor de vetores ou um vetor com mais de uma dimensão.
Tipo de dados compostos
Vetor[]
Tipo de dados compostos
Matriz[][]
Tipos Abstratos de Dados (TADs)
Agrupa a estrutura de dados juntamente com as operações que podem ser feitas sobre esses dados
O TAD encapsula a estrutura de dados. Os usuários do TAD só tem acesso a algumas operações disponibilizadas sobre esses dados
Usuário do TAD x Programador do TAD
Usuário só “enxerga” a interface, não a implementação
Tipos Abstratos de Dados (TADs)
Dessa forma, o usuário pode abstrair da implementação específica.
Qualquer modificação nessa implementação fica restrita ao TAD
A escolha de uma representação específica é fortemente influenciada pelas operações a serem executadas
Exemplo: Lista de números inteiros
Operações
Faz Lista Vazia
Insere número no começo da lista
Remove de uma posição i
20 13 02 30
Implementação por Vetores:
void Insere(int x, Lista L) {
 for(i=0;...) {...}
 L[0] = x;
}
20
13
02
30
Implementação por Listas Encadeadas
void Insere(int x, Lista L) {
 p = CriaNovaCelula(x);
 L^.primeiro = p;
 ...
}
Programa usuário do TAD:
int main() {
 Lista L;
 int x;
 x = 20;
 FazListaVazia(L);
 Insere(x,L);
 ...
}
Implementação de TADs
Em linguagens orientadas por objeto (C++, Java) a implementação é feita através de classes
Em linguagens estruturadas (C, pascal) a implementação é feita pela definição de tipos juntamente com a implementação de funções
Como vocês não vimos o conceito de orientação por objetos*, vamos utilizar os conceitos de C 
(Typedef e Structs)
Veremos alguns conceitos de Orientação por objetos (classes, etc) que será aprofundado em outras disciplinas (POO).
Estruturas (Structs) em C / C++
Uma estrutura é uma coleção de uma ou mais variáveis, possivelmente de tipos diferentes, colocadas juntas sob um único nome para manipulação conveniente
Por exemplo, para representar um aluno são necessárias as informações nome, matrícula, conceito
Ao invés de criar três variáveis, é possível criar uma única variável contendo três campos.
Em C, usa-se a construção struct para representar esse tipo de dado
Para que serve uma struct em C?
Vamos supor que você foi contratado por uma grande empresa para criar um aplicativo de C que armazena todas as informações dos funcionários, um banco de dados.
Como você faria para armazenar as idades deles?
Vamos supor que tem 300 funcionários.
int idades[300];
E os nomes? Vamos separar 50 caracteres para cada pessoa.
Temos que ter 300 vetores (strings), cada um com 50 caracteres. Ficaria:
char nomes[300][50];
O mesmo para sua data de admissão, o salário de cada um, seus números de identificação, horários, cargos etc.
Para que serve uma struct em C?
Mas como você faria saber as informações de um funcionário especificamente?
Poderíamos pegar cada posição para uma pessoa. Por exemplo, o funcionário Bruce Dickinson seria o de número 50.
Ou seja, para pegar o nome dele, vá para a posição 49 da matriz de strings.
Para saber o salário dele, vá na posição de número 49 do vetor de floats que representa os salários. Na posição 49 do vetor de inteiros podemos obter a idade deles e assim vai.
Isso tudo é possível, mas extremamente trabalhoso, confuso e nada organizado.
É para isso que existem as structs.
O que é uma struct em C
Struct, ou estrutura, é um bloco que armazenam diversas informações.
Poderíamos criar uma estrutura para cada funcionário, e dentro dessa estrutura tem variável do tipo int (para idade), do tipo string (para armazenar o nome), têm floats (que armazenam o salário de cada um), etc. E cada estrutura teria um nome, que seria algo relacionado com o funcionário.
Assim, sempre que quiséssemos um dado de um funcionário, bastaríamos ter acesso a estrutura dele, e todas as informações viriam juntas.
Essas estruturas, ou structs, podem ter quantos elementos você queira e dos tipos que você quiser. Você primeiro define a estrutura, seu nome e elementos.
Depois você escolhe quantos elementos daquela estrutura quer ter, e os declara com nomes diferentes.
Após isso, em vez de você manipular as milhares de variáveis dos mais diversos tipos que tenha criado, você trabalha só com a estrutura.
Assim não tem que se ‘estressar’ com cada detalhe da estrutura. Esses detalhes são definidos somente uma vez, na declaração da estrutura.
Declarando a Struct em C
Como já foi dito, struct nada mais é que um conjunto, ou bloco, de variáveis. A sintaxe é a seguinte
struct Nome_de_sua_struct
{
                tipos nome_dos_tipos;
};
Vamos declarar, como exemplo, uma struct para representar os dados dos funcionários:
struct Funcionario
{
                int idade;
                char *nome;
                float salario;
};
O tipo struct
Podemos ver as structs como um tipo de dado.
Por exemplo, “Funcionario”, que foi declarado anteriormente, pode ser visto como um novo de tipo de variável. É uma variável, ou um tipo, que define os funcionários.
Essa visão, de que criamos um novo tipo de variável, é tão certa que é possível criar e declarar mais variáveis do tipo “struct Funcionario”.
A sintaxe para declarar outras structs do tipo “struct Funcionario” é:
struct Funcionario empregado1;
struct Funcionario chefe;
struct Funcionario secretaria;
É aí que reside a beleza e importância das structs.
Note que no momento da criação do modelo da struct “Funcionario”, declaramos um inteiro, uma string e um float dentro da struct.
Assim, todas as structs do tipo “Funcionario” terão uma variável inteira, uma string e um float.
O tipo struct
Outra maneira de declarar variáveis de um tipo struct que queremos, é criar esses elementos  após as chaves na hora de criar a struct Funcionario.
Veja:
struct Funcionario
{
                int idade;
                char *nome;
                float salario;
}empregado1, chefe, secretaria;
Como acessar, alterar e ler os elementos de uma struct em C
Vamos pegar nosso exemplo do tipo “struct Funcionario”.
Criamos 3 funcionários desse tipo, e todos eles terão os mesmos elementos internos, com os mesmos nomes: idade, nome e salario.
Se tem o mesmo nome, como vamos diferenciar esses elementos,
então?
Pelo nome da variável do tipo “struct Funcionario”.
Para acessar o elemento ‘elemento’ da struct de nome “MinhaStruct”, usamos a sintaxe:
MinhaStruct.elemento
Apenas isso, basta botar um ponto após o nome que você escolheu para a struct.
Após isso, estamos acessando normalmente a variável:
chefe.idade -> é um inteiro como outro qualquer.
empregado1.nome -> é uma string como outra qualquer.
secretaria.salario -> é um float como outro qualquer.
typedef
A palavra reservada typedef nada mais é do que um atalho em C para que possamos nos referir a um determinado tipo existente com nomes sinônimos.
Por exemplo, com o typedef, em vez de termos que nos referir como 'struct Aluno', poderíamos usar somente 'Aluno' para criar structs daquele tipo.
Em vez de escrever sempre 'struct Funcionario', poderíamos escrever apenas 'Funcionario' e então declarar várias structs do tipo 'Funcionario'.
Embora possamos criar atalhos com typedef para outros tipos, o typedef é comumente usado com structs.
Exercícios
Faça os exercicios que estão no ambiente (ava.ufrr.br):
Atividade I – Aula 2 
Atividade II – Aula 2
Referências
http://www.cprogressivo.net
CELES, W; CERQUEIRA, R; & RANGEL, J. L. Introdução a Estrutura de Dados: Com técnicas de programação em C. Rio de Janeiro: Editora Campus/Elsevier, 2004.