Yhhjhjh

Disponível somente no TrabalhosFeitos
  • Páginas : 14 (3475 palavras )
  • Download(s) : 0
  • Publicado : 12 de abril de 2012
Ler documento completo
Amostra do texto
Prof. Esp. Ricardo Barbosa
professorricardobarbosa@aedu.com
http://twitter.com/barbosa_prof

Áreas de Interesse:






Análise e Desenvolvimento de Sistemas
Banco de Dados
Sistemas Web
Linguagens de Programação
Metodologias de Desenvolvimento de Sistemas
1

1

Estrutura de Dados
Prof. Esp. Ricardo Barbosa
professorricardobarbosa@aedu.com

Faculdade AnhangueraEducacional
Fev/2012
2

2

Objetivos da Disciplina
Ao final da disciplina o aluno, deverá estar apto a:
Conhecer e desenvolver estruturas de dados.

3

Prof. Ricardo Barbosa

3

Bibliografia Básica
TENENBAUM, Aaron M; SOUZA, Tereza Cristina Félix de.
Estruturas de Dados usando C. 1ª ed. São Paulo:
Makron Books,1995

4

Prof. Ricardo Barbosa

4

Listas Lineares
1.
2.
3.4.
5.
6.
7.

Definição de lista e operações
Listas encadeadas
Listas circulares
Listas duplamente encadeadas
Listas circulares duplamente encadeadas
Listas de tipos estruturados
Listas heterogêneas

5

Prof. Ricardo Barbosa

5

Listas Lineares
1. DEFINIÇÃO DE LISTA E OPERAÇÕES
Uma lista é uma sequência de um ou mais itens x1, x2, ..., xn
na qual xi é de um determinado tipo en representa o
tamanho
tamanho da lista.
Algumas propriedades:
• Assumindo n≥1, x1 é o primeiro elemento e xn é o último
elemento da lista
• xi precede xi+1 para i = 1, 2, ..., n-1
• xi sucede xi-1 para i = 2, 3, ..., n
• o elemento xi é dito estar na i-ésima posição da lista
6

Prof. Ricardo Barbosa

6

Listas Lineares
1. DEFINIÇÃO DE LISTA E OPERAÇÕES
As principais operações emlistas lineares são:










Criar uma lista linear vazia
Inserir um novo item após o i-ésimo item
Retirar o i-ésimo item
Localizar o i-ésimo item para examinar ou alterar o conteúdo
Combinar duas ou mais listas lineares em uma única lista
Partir uma lista linear em duas ou mais listas
Fazer uma cópia de uma lista linear
Ordenar os itens da lista em ordem ascendenteou descendente
Buscar um item que satisfaz uma determinada propriedade
7

Prof. Ricardo Barbosa

7

Listas Lineares
2. LISTAS ENCADEADAS
Uma Lista é uma estrutura abstrata de dados (TAD) linear e
dinâmica (em oposição os vetores que são estáticos).
Uma lista encadeada é composta por nós que apontam para
o próximo elemento da lista, com exceção do último, que não
aponta para ninguém.Para compor uma lista encadeada,
basta guardar seu primeiro elemento.

8

Prof. Ricardo Barbosa

8

Listas Lineares
2. LISTAS ENCADEADAS
Em uma lista encadeada, para cada um dos elementos
inseridos é realizada alocação de memória para
armazenamento.
armazenamento. Assim, o espaço total de memória gasto
pela estrutura é proporcional ao números de elementos
armazenados.
Não épossível garantir que os elementos em uma lista
ocupem espaços contínuos na memória do computador,
portanto, não temos acesso direto aos elementos da lista.
Para percorrer todos os elementos de uma lista é necessário
guardar o seu encadeamento.
9

Prof. Ricardo Barbosa

9

Listas Lineares
2. LISTAS ENCADEADAS

PRIMEIRO

INFO1

INFO2

INFO3

INFO4

NULL



Exemplo de umalista encadeada
10

Prof. Ricardo Barbosa

10

Listas Lineares
2. LISTAS ENCADEADAS – Definição da estrutura
struct lista {
int info;
struct lista *prox;
};

Tomemos como exemplo o organização
de valores inteiros em uma lista
encadeada.
PRIMEIRO

typedef struct lista Lista;

7

4

9

NULL

Perceba que a definição da estrutura para representar cada
elemento da lista éauto-referenciada, pois, além de membro
para armazenar a informação, há um membro que é um ponteiro
para o próximo elemento da lista.
O tipo Lista (sinônimo de struct lista) representa um nó da lista.
11

Prof. Ricardo Barbosa

11

Listas Lineares
2. LISTAS ENCADEADAS – Função de criação
/* Função para criar a lista */

Lista* lista_criar()
{
return NULL;
}

Como a lista é...
tracking img