Linguagem C
86 pág.

Linguagem C


DisciplinaAlgoritmos e Estrutura de Dados I720 materiais7.908 seguidores
Pré-visualização18 páginas
exchange=1; 
 } 
 } 
 for (a=1; a<count; a++) 
 { 
 if (p[a-1]>p[a]) 
 { 
 temp=p[a-1]; 
 p[a-1]=p[a]; 
 p[a]=temp; 
 exchange=1; 
 } 
 } 
 } while (exchange); 
} 
 
13.2 Ordenação por Seleção 
A ordenação por seleção consiste, em cada etapa, em selecionar o maior (ou o 
menor)elemento e alocá-lo em sua posição correta dentro da futura lista ordenada. Durante a 
aplicação do método de seleção a lista com n registros fica decomposta em duas sub listas, uma 
contendo os itens já ordenados e a outra com os restantes ainda não ordenados. No início a sub lista 
ordenada é vazia e a outra contém todos os demais.No final do processo a sub lista ordenada 
apresentará (n-1) itens e a outra apenas 1. As etapas(ou varreduras) como já descrito acima consiste 
em buscar o maior elemento da lista não ordenada e colocá-lo na lista ordenada. 
void selecao(int *p, int count) 
{ 
 int a, b, c, exchange, temp; 
 for (a=0; a<count-1; a++) 
 { 
 exchange=0; 
 c=a; 
 temp=p[a]; 
 for(b=(a+1); b<count; b++) 
 { 
 if (p[b]<temp) 
 { 
 c=b; 
 temp=p[b]; 
 exchange=1; 
 } 
 } 
 if (exchange) 
 { 
 p[c]=p[a]; 
 p[a]=temp; 
 } 
 } 
} 
 
13.3 Ordenação por Inserção 
O algoritmo de ordenação por inserção é bastante simples e eficiente para uma 
quantidade pequena de números. A idéia de funcionamento é semelhante ao ordenamento de cartas 
de baralho na mão de um jogador. A mão esquerda começa &quot;vazia&quot; e a mão direita insere uma 
&quot;carta&quot; de cada vez na posição correta. Ao final, quando todas as &quot;cartas&quot; foram inseridas, elas já 
 70
estão ordenadas. Durante o processo de ordenação por inserção a lista fica dividida em duas sub 
listas, uma com os elementos já ordenados e a outra com elementos ainda por ordenar. No início, a 
sub lista ordenada é formada trivialmente apenas pelo primeiro elemento da lista. Nos métodos de 
ordenação por inserção, a cada etapa i, o i-ésimo elemento é inserido em seu lugar apropriado entre 
os(i-1) elementos já ordenados. 
void insercao(int *p, int count) 
{ 
 int a, b, temp; 
 for (a=1; a<count; a++) 
 { 
 temp=p[a]; 
 for (b=(a-1); b>=0 && temp<p[b]; b--) 
 p[b+1] = p[b]; 
 p[b+1]=temp; 
 } 
} 
 
13.4 \u201cShell Sort\u201d 
O algoritmo de ordenação shell é um algoritmo de ordenação por inserção. O algoritmo 
foi criado por Donald L. Shell em 1959. Neste algoritmo, ao invés dos dados serem comparados 
com os seus vizinhos, é criado um gap. O gap, no início, é igual à parte inteira da divisão do 
número de elementos da lista por 2. Por exemplo, se a nossa lista tem 15 elementos, o gap inicial é 
igual a 7. São então comparados os elementos 1o. e 8o., 2o. e 9o., e assim por diante. A maior parte 
dos elementos já vão para suas posições aproximadas. Ao terminar de passar por todos os elementos 
da lista, o gap é diminuído em 1 e é feita uma nova passagem. Isso é repetido até que o gap seja 
igual a 0. 
void shell(int *p, int count) 
{ 
 int i, j, gap, k, x, a[5]={9,5,3,2,1}; 
 print(p, count); 
 for (k=0; k<5; k++) 
 { 
 gap = a[k]; 
 for (i=gap; i<count; i++) 
 { 
 x=p[i]; 
 for (j=i-gap; x<p[j] && j>=0; j=j-gap) 
 p[j+gap] = p[j]; 
 p[j+gap] = x; 
 } 
 } 
} 
 
13.5 \u201cQuicksort\u201d 
O algoritmo de ordenação quicksort é um algoritmo de ordenação por troca. Baseia-se 
na escolha de um elemento central. A partir da posição 0, começamos a procurar um elemento 
maior do que x, até encontrarmos. O mesmo processo ocorre a partir da posição n-1, procurando um 
elemento menor do que x. 
 71
Quando o índice da esquerda (i) for menor do que o índice da direita (j), trocamos estes 
valores, até que i>=j. O processo se repete de forma recursiva para cada subconjunto (esquerda e 
direita do elemento x), até termos um subconjunto com um único elemento. 
void quicksort(int *p, int count) 
{ 
 qs(p, 0, count-1); 
} 
 
void qs(int *p, int left, int right) 
{ 
 int i, j, x, y; 
 i=left; 
 j=right; 
 x=p[(left+right)/2]; 
 do 
 { 
 while ((p[i]<x) && (i<right)) 
 i++; 
 while ((x<p[j]) && (j>left)) 
 j--; 
 if (i<=j) 
 { 
 y=p[i]; 
 p[i]=p[j]; 
 p[j]=y; 
 i++; 
 j--; 
 } 
 }while (i<=j); 
 if (left<j) 
 qs(p, left, j); 
 if (i<right) 
 qs(p, i, right); 
} 
 
 
 
 
 72
14. ESTRUTURAS DE DADOS 
Um programa consiste de duas coisas: algoritmos e estruturas de dados. A estrutura de 
dados é importante para armazenar os dados e recuperá-los, quando necessário, de forma 
automática em uma ordem predeterminada. De acordo com a forma de acesso (armazenamento e 
recuperação) aos dados, existem basicamente quatro tipos de estruturas: 
\u2022 Pilha; 
\u2022 Filas; 
\u2022 Listas; 
\u2022 Árvores Binárias. 
 
14.1 Pilhas 
Pilhas são estruturas de armazenagem e recuperação de dador em ordem LIFO (Last-in, 
First-out), isto é, o último item colocado na pilha será o primeiro a ser removido. As duas operações 
básicas (armazenar e recuperar) são tradicionalmente chamadas de push e pop, respectivamente. 
 
 
 
 
 
 
 
 
 
Figura 14.1 Ilustração exemplo da função push. 
 
 
 
 
 
 
 
 
 
Figura 14.2 Ilustração exemplo da função pop. 
G 
U 
P 
A 
 
W 
G 
 
P 
A 
 
U 
P
A
G 
A
P 
 
 
 
 
 
A 
 
 
 
 
 
 
 
 
A 
 
P
A
G
P
A
G 
U 
P 
A 
 
G
U
P
A
W
A P G U W
 73
 
14.2 Filas 
Filas são estruturas de armazenagem e recuperação de dados em ordem FIFO (First In, 
First Out), isto é, o primeiro item colocado na fila será o primeiro a ser removido. A fila opera 
utilizando duas funções: entra e sai. As filas podem ser utilizadas em simulações, distribuição de 
eventos, entre outros. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 14.3 Ilustração função entra e função sai de uma fila. 
 
14.2.1 Filas Circulares 
Quando uma Fila atinge o limite do vetor de armazenamento, não é mais possível 
colocar nenhum item na fila. Um melhoramento das Filas simples seria a Fila Circular. Desta forma, 
 
 X 
 YX 
Z YX 
X 
Y 
Z 
Z YX
Z Y X 
Z Y 
Z 
 74
qualquer número de itens poderia ser colocado na fila, desde que itens também estejam sendo 
retirados (Fig. 14.4). 
 
 
 
 
 
 
 
 
 
 
 
Figura 14.4 Ilustração de uma fila circular. 
 
14.3 Listas Ligadas 
São estruturas de armazenagem e recuperação de dados de forma randômica. Cada 
porção de informação é armazenada em um item de informação e que carrega consigo um elo ao 
próximo item de informação, ou seja, uma lista encadeada. As listas encadeadas podem ser 
singularmente (simples) ou duplamente encadeadas. 
 
14.3.1 Listas Singularmente Ligadas 
Uma lista singularmente encadeada requer que cada item de informação contenha um 
elo com o próximo item da lista. Cada item de informação consiste em uma estrutura que inclui 
campos de informação e ponteiro de enlace. 
A adição de um nó pode ser realizada no início ou ao longo de uma lista ligada. A 
adição de um nó no início de uma lista ligada é realizada em quatro etapas: 
a) Um nó vazio é criado. Ele está vazio no sentido de que o programa que realiza a inserção 
não atribui quaisquer valores aos campos de dados do nó; 
b) O campo info do nó é inicializado com um valor em particular; 
c) Devido ao nó ser incluído no início da lista, o elo proximo se torna um ponteiro para o 
primeiro nó da lista, isto é, o valor corrente de topo; 
A 
B 
 75
d) O novo nó precede todos os nós da lista, mas esse fato tem que ser refletido no valor do 
Primeiro. Consequentemente, o ponteiro Primeiro é atualizado para se tornar o ponteiro 
para o novo nó. 
O processo de adicionar um novo nó ao longo da lista de forma ordenada é realizada em 
quatro etapas: 
a) Um nó vazio é criado. Ele está vazio no sentido de que o programa que realiza a inserção 
não atribui quaisquer valores aos campos de dados do nó; 
b) O campo info do nó