Embed Size (px)
Citation preview
Universidade Federal de Ouro Preto
Instituto de Ciências Exatas e Biológicas
Departamento de Computação
ALGORITMOS E ESTRUTURAS DE DADOS
Segundo Trabalho Prático
Johnnatan Messias Peixoto Afonso
Professor - David MenottiMonitor - Kayran dos Santos
Ouro Preto
6 de outubro de 2009
Sumário
1 Introdução 1
1.1 Considerações iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Especi�cação do problema . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Algoritmo e estruturas de dados 1
2.1 TAD - TBloco . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22.1.1 Assinatura das funções . . . . . . . . . . . . . . . . . . . . . . 22.1.2 Função Vazio . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.1.3 Função LehVazio . . . . . . . . . . . . . . . . . . . . . . . . . 32.1.4 Função Insere . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.1.5 Função Volta . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.1.6 Função PileOver . . . . . . . . . . . . . . . . . . . . . . . . . 42.1.7 Função MoveOver . . . . . . . . . . . . . . . . . . . . . . . . . 42.1.8 Função PileOnto . . . . . . . . . . . . . . . . . . . . . . . . . 52.1.9 Função MoveOnto . . . . . . . . . . . . . . . . . . . . . . . . 52.1.10 Função Imprime . . . . . . . . . . . . . . . . . . . . . . . . . . 62.1.11 Função Busca . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.1.12 Função Criar . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Main . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.2.1 Função STDAFX.H . . . . . . . . . . . . . . . . . . . . . . . . 10
3 Análise de complexidade dos algoritmos 10
3.1 Função Volta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103.2 Função PileOver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103.3 Função MoveOver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103.4 Função PileOnto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.5 Função start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.6 Função MoveOnto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.7 Função Imprime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.8 Função Busca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.9 Função Criar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4 Testes 12
5 Conclusão 14
Lista de Figuras
1 Argumentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 Comando . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 Arquivo de entrada . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 Execuxão do comando . . . . . . . . . . . . . . . . . . . . . . . . . . 135 Arquivo de saída . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2
Lista de Programas
1 TVetor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 Assinaturas do TBloco.h . . . . . . . . . . . . . . . . . . . . . . . . . 23 Vazio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 LehVazio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 Insere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 Volta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 PileOver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 MoveOver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 PileOnto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 510 Move Onto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 511 Imprime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 612 Busca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 613 Criar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 714 Main . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 715 Stdafx . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3
1 Introdução
Este trabalho consiste na implementação do TAD (Tipo Abstrato de Dados)TBloco para representar as listas encadeadas dos blocos para representarmos oMundo dos Blocos com as implementações das funções.
1.1 Considerações iniciais
• Além das explicações citadas acima das funções, favor considerar também oscomentários contidos no programa.
• Ambiente de desenvolvimento do código fonte: Microsoft Visual Studio 2008Professional.
• Linguagem utilizada: Linguagem C.
• Ambiente de desenvolvimento da documentação: TeXnicCenter 1.0 SRC-Editorde LATEX.
1.2 Especi�cação do problema
Várias áreas da ciência da computação usam domínios simpli�cados para abstrairdiversos tipos de problemas. Por exemplo, algumas das primeiras pesquisas deinteligência arti�cial nas áreas de planejamento e robótica eram feitas utilizando omundo dos blocos, no qual um braço robótico realizava tarefas simuladas envolvendoa manipulação de blocos [2]. Nesse trabalho você vai implementar um mundo deblocos bem simples [3], que vai funcionar de acordo com certas regras e obedecercomandos de movimentação de blocos dados pelo usuário, simulando o que seria amanipulação através um braço robótico. O seu mundo de blocos começa com cadabloco na sua posição inicial, e depois de uma série de comandos deve terminar emuma con�guração �nal.Os comandos possíveis para a manipulação do mundo de blocos são:
• move a onto b: Move o bloco a para cima do bloco b retornando eventuaisblocos que já estiverem sobre a ou b para as suas posições originais.
• move a over b: Coloca o bloco a no topo do monte onde está o bloco bretornando eventuais blocos que já estiverem sobre a às suas posições originais.
• pile a onto b: Coloca o bloco a juntamente com todos os blocos que estiveremsobre ele em cima do bloco b, retornando eventuais blocos que já estiveremsobre b as suas posições originais.
• pile a over b: Coloca o bloco a juntamente com todos os blocos que estiveremsobre ele sobre o monte que contem o bloco b.
2 Algoritmo e estruturas de dados
Foi criado um TAD, Tipo Abstrato de Dados para representar as listas en-cadeadas, bem como a quantidade de blocos e de listas encadeadas e também umapontador para os blocos.
1
2.1 TAD - TBloco
Para representar as listas encadeadas e os blocos foi criado um TAD TBloco.h
typedef struct Bloco ∗Apontador ; /∗ Apontador para a e s t r u t u r a TBlocodo t i p o Bloco ∗/
typedef struct Bloco{
int num;5 Apontador pProx ; /∗ Apontador pProx ; ∗/
} TBloco ; /∗ Blocos : Cé lu la ∗/
typedef struct
{10 Apontador pPrimeiro ; /∗ Apontador para o pr imeiro da l i s t a ∗/
Apontador pUltimo ; /∗ Apontador para o ú l t imo da l i s t a ∗/} TLista ; /∗ Li s t a dos b l o co s ∗/
typedef struct
15 {TLista ∗ v e t l i s t a ;int tamanho ;
}TVet l i s ta ; /∗ Estrutura dos v e t o r e s de l i s t a s encadeadas ∗/
Programa 1: TVetor
2.1.1 Assinatura das funções
Abaixo as assinaturas do TBloco.h.
void Vazio ( TLista ∗) ; /∗ Assinatura da função Vazio para c r i a r umal i s t a va z i a ∗/
void Criar ( TVet l i s ta ∗ , int numero ) ; /∗ Assinatura da função Criar parac r i a r l i s t a encadeada ∗/// qnt de l i s t a encadeadas
double LehVazio ( TLista ∗) ; /∗ Assinatura da função LehVazio parav e r i f i c a r se a l i s t a é ou não vaz ia ∗/
void I n s e r e ( TLista ∗ , int ) ; /∗ Assinatura da função Insere para i n s e r i rum b loco com um conteúdo a uma pos ição apontada ∗/
5 void Imprime ( TLista ∗) ; /∗ Assinatura da função Imprime que imprimeATENÇÃO ∗/
Apontador Busca ( TVet l i s ta ∗ , int , Apontador ∗ , int ∗) ; /∗ Assinatura dafunção Busca para receber uma l i s t a encadeada e i n s e r i r na l i s t a
um b loco antes de uma determinada pos ição ∗/void MoveOnto( TVet l i s ta ∗ , int , int ) ; /∗ Assinatura da função Move
Onto ∗/void PileOver ( TVet l i s ta ∗ , int , int ) ; /∗ Assinatura da função P i l e
Over ∗/void MoveOver ( TVet l i s ta ∗ , int , int ) ; /∗ Assinatura da função Move
Over ∗/10 void PileOnto ( TVet l i s ta ∗ , int , int ) ; /∗ Assinatura da função P i l e
Onto ∗/void Volta ( TVet l i s ta ∗ , Apontador ) ; /∗ Assinatura da função que v o l t a
os b l o co s de acordo com as operações de P i l e ou Move ∗/
Programa 2: Assinaturas do TBloco.h
2
2.1.2 Função Vazio
Essa função é chamada pela função Criar, criando uma lista encadeada vazia,fazendo uma alocação dinâmica (malloc) onde o último da lista passa a ser o primeiroe o primeiro aponta para o próximo bloco da lista recebendo NULL.
void Vazio ( TLista ∗ p l i s t a ) /∗ Essa função é chamada pe la função Criar ,cr iando uma l i s t a encadeada vaz ia ∗/
{p l i s t a−>pPrimeiro = (Apontador ) mal loc ( s izeof ( Bloco ) ) ;p l i s t a−>pUltimo = p l i s t a−>pPrimeiro ;
5 p l i s t a−>pPrimeiro−>pProx = NULL;}
Programa 3: Vazio
2.1.3 Função LehVazio
Essa função veri�ca se a lista é vazia, caso o primeiro da lista seja igual ao últimoela retornará 1, caso contrário, 0. Obs.: Essa função não foi usada no programa poisé muito caro chamar uma função, não sendo, portanto, viável a sua utilização umavez que pode ser facilmente implementado os comandos contidos nela em outrasfunções.
double LehVazio ( TLista ∗ p l i s t a ) /∗ Essa função v e r i f i c a se a l i s t aencadeada é vaz i a ∗/
{return ( p l i s t a−>pPrimeiro == p l i s t a−>pUltimo ) ;
}
Programa 4: LehVazio
2.1.4 Função Insere
Após criar uma lista vazia, usamos essa função para inserir novos elementosna lista encadeada, mas deve-se alocar dinamicamente (malloc) a memória paraarmazenar o elemento.
void I n s e r e ( TLista ∗ p l i s t a , int numero ) /∗ Essa função in s e r e um novob l oco em uma l i s t a encadeada ∗/
{p l i s t a−>pUltimo−>pProx = (Apontador ) mal loc ( s izeof ( TBloco ) ) ; /∗ p l i s t a
−>pUltimo−>pProx recebe recebe a quant idade e b y t e s a locado ∗/p l i s t a−>pUltimo = p l i s t a−>pUltimo−>pProx ;
5 p l i s t a−>pUltimo−>num = numero ;p l i s t a−>pUltimo−>pProx = NULL;
}
Programa 5: Insere
2.1.5 Função Volta
Essa função é responsável por voltar os blocos à suas posições originais após asoperações as operações de pilo e onto na execução do programa. Caso o apontadorseja NULL ele retorna, caso contrário, o primeiro da lista aponta para o próximo
3
que recebe p, em seguida o último da lista também recebe p. Fará isso até que pseja NULL, em seguida executará a próxima instrução que seria: p->pProx=NULL.
void Volta ( TVet l i s ta ∗pbloco , Apontador p) /∗ Função para v o l t a r osb l o co s depo i s das operações de MOVE e PILE ∗/
{i f (p==NULL)return ;
5 pbloco−>v e t l i s t a [ p−>num ] . pPrimeiro−>pProx=p ;pbloco−>v e t l i s t a [ p−>num ] . pUltimo=p ;Volta ( pbloco , p−>pProx ) ; /∗ Recurs iv idade : Enquanto p−>pProx f o r i g u a l
a NULL a função será chamada , caso contrár io , executa a in s t ruçãoabaixo : p−>pProx=NULL; ∗/
p−>pProx=NULL;}
Programa 6: Volta
2.1.6 Função PileOver
Coloca um bloco a juntamente com todos os blocos que estiverem sobre ele sobreo monte que contem um bloco b.
void PileOver ( TVet l i s ta ∗pbloco , int A, int B) /∗ Coloca um b loco ajuntamente com todos os b l o co s que es t i ve rem sobre e l e sobre o
monte que contem um b loco b . ∗/{
Apontador pantA , pantB ,pA,pB ;5 int l i s taA , l i s t aB ;
i f (A==B)return ;
pA=Busca ( pbloco ,A,&pantA,& l i s t aA ) ;pB=Busca ( pbloco ,B,&pantB ,& l i s t aB ) ;
10 i f ( (pA==NULL) | | ( pB==NULL) | | ( l i s t aA==l i s t aB ) )return ;
while (pB−>pProx!=NULL){
pB=pB−>pProx ;15 }
pB−>pProx=pA;pantA−>pProx=NULL;pbloco−>v e t l i s t a [ l i s t aB ] . pUltimo=pA;
}
Programa 7: PileOver
2.1.7 Função MoveOver
Coloca um bloco a no topo do monte onde está um bloco b retornando eventuaisblocos que já estiverem sobre a às suas posições originais.
void MoveOver ( TVet l i s ta ∗pbloco , int A, int B) /∗ Coloca um b loco a notopo do monte onde e s t á um b loco b retornando even tua i s b l o co s
que já es t i verem sobre a às suas po s i çõe s o r i g i n a i s ∗/{
Apontador pantA , pantB ,pA,pB ;5 int l i s taA , l i s t aB ;
4
i f (A==B)return ;
pA=Busca ( pbloco ,A,&pantA,& l i s t aA ) ;pB=Busca ( pbloco ,B,&pantB ,& l i s t aB ) ;
10 i f ( (pA==NULL) | | ( pB==NULL) | | ( l i s t aA==l i s t aB ) )return ;
i f (pA−>pProx!=NULL){
Volta ( pbloco ,pA−>pProx ) ;15 pA−>pProx=NULL;
pbloco−>v e t l i s t a [ l i s t aA ] . pUltimo=pA;}pB−>pProx=pA;pantA−>pProx=NULL;
20 pbloco−>v e t l i s t a [ l i s t aB ] . pUltimo−>pProx=pA;}
Programa 8: MoveOver
2.1.8 Função PileOnto
Coloca um bloco a juntamente com todos os blocos que estiverem sobre ele sobreo monte que contem um bloco b.
void PileOnto ( TVet l i s ta ∗pbloco , int A, int B) /∗ Coloca um b loco ajuntamente com todos os b l o co s que es t i ve rem sobre e l e sobre o
monte que contem um b loco b . ∗/{
Apontador pantA , pantB ,pA,pB ;5 int l i s taA , l i s t aB ;
i f (A==B)return ;
pA=Busca ( pbloco ,A,&pantA,& l i s t aA ) ;pB=Busca ( pbloco ,B,&pantB ,& l i s t aB ) ;
10 i f ( (pA==NULL) | | ( pB==NULL) | | ( l i s t aA==l i s t aB ) )return ;
i f (pB−>pProx!=NULL){
Volta ( pbloco , pB−>pProx ) ;15 pB−>pProx=NULL;
pbloco−>v e t l i s t a [ l i s t aB ] . pUltimo=pB;}pB−>pProx=pA;pantA−>pProx=NULL;
20 pbloco−>v e t l i s t a [ l i s t aB ] . pUltimo=pA;}
Programa 9: PileOnto
2.1.9 Função MoveOnto
Move um bloco a para cima do bloco b retornando eventuais blocos que já es-tiverem sobre a ou b para as suas posições originais.
void MoveOnto( TVet l i s ta ∗pbloco , int A, int B) /∗ Move um b loco a paracima do b l oco b retornando even tua i s b l o co s que já es t i ve rem
sobre a ou b para as suas po s i çõe s o r i g i n a i s . ∗/
5
{Apontador pantA , pantB ,pA,pB ;
5 int l i s taA , l i s t aB ;i f (A==B)return ;
pA=Busca ( pbloco ,A,&pantA,& l i s t aA ) ;pB=Busca ( pbloco ,B,&pantB ,& l i s t aB ) ;
10 i f ( (pA==NULL) | | ( pB==NULL) | | ( l i s t aA==l i s t aB ) )return ;
i f (pA−>pProx!=NULL){
Volta ( pbloco ,pA−>pProx ) ;15 pA−>pProx=NULL;
pbloco−>v e t l i s t a [ l i s t aA ] . pUltimo=pA;}i f (pB−>pProx!=NULL){
20 Volta ( pbloco , pB−>pProx ) ;pB−>pProx=NULL;pbloco−>v e t l i s t a [ l i s t aB ] . pUltimo=pB;
}pB−>pProx=pA;
25 pantA−>pProx=NULL;pbloco−>v e t l i s t a [ l i s t aB ] . pUltimo=pA;
}
Programa 10: Move Onto
2.1.10 Função Imprime
Função que percorre a lista até que o próximo elemento aponte para NULL,imprimindo os valores.
void Imprime ( TLista ∗ p l i s t a ) /∗ Função que percorre a l i s t a a té que opróximo elemento aponte para NULL, imprimindo os v a l o r e s ∗/
{Apontador paux ;paux=p l i s t a−>pPrimeiro−>pProx ;
5 while ( paux!=NULL){
p r i n t f ("%d " , paux−>num) ;paux = paux−>pProx ;
}10 }
Programa 11: Imprime
2.1.11 Função Busca
Essa função veri�ca se o elemento está na lista, caso esteja, teremos como retornoum ponteiro que no caso representa o elemento, caso contrário, retornará NULL.
Apontador Busca ( TVet l i s ta ∗pblocos , int numero , Apontador ∗pant , int ∗pla/∗Ponteiro de i n t e i r o pra l i s t a d e l e ∗/ )
{int i ;Apontador paux ;
6
5 for ( i =0; i<pblocos−>tamanho ; i++) /∗ Laço de r ep e t i ç ão até que o i s e j amenor que o o número de l i s t a s encadeadas ∗/
{paux=pblocos−>v e t l i s t a [ i ] . pPrimeiro−>pProx ;∗pant=pblocos−>v e t l i s t a [ i ] . pPrimeiro ;while ( paux!=NULL)
10 {i f ( paux−>num==numero ){∗pla=i ;return paux ;
15 }∗pant=paux ;paux=paux−>pProx ;
}}
20 ∗pla=−1;/∗ Li s t a q contem num q não e x i s t e ∗/return NULL;
}
Programa 12: Busca
2.1.12 Função Criar
Essa a função responsável por criar a lista encadeada, ela chama a função Vaziopara criar uma lista vazia e depois chama a função Insere para inserir os elementosnos blocos.
void Criar ( TVet l i s ta ∗blocos , int numero ) /∗ Essa a função re sponsáve lpor c r i a r a l i s t a encadeada , e l a chama a função Vazio para c r i a ruma l i s t a va z i a e depo i s chama a função Insere para i n s e r i r ose lementos nos b l o co s ∗/
{int i ;b locos−>v e t l i s t a = ( TLista ∗) mal loc ( s izeof ( TLista ) ∗numero ) ;
5 blocos−>tamanho = numero ;for ( i =0; i<numero ; i++){
Vazio (&( blocos−>v e t l i s t a [ i ] ) ) ;I n s e r e (&blocos−>v e t l i s t a [ i ] , i ) ;
10 }}
Programa 13: Criar
2.2 Main
Programa Main abaixo:
// TP2AEDSI−JOHN. cpp : Def ines the entry po in t f o r the conso l ea p p l i c a t i o n .
#include " s t d a f x . h"
5 int main ( int argc , char∗ argv [ ] ){
7
system (" co l o r 1b" ) ; /∗ Função re sponsáve l por de i xar a t e l a a zu l :−)∗/
int k , i =0, j =0, tam , qnt , a , b ;10 char word [ 2 1 ] [ 5 ] , carac ;
TVet l i s ta pbloco ;Apontador paux ;FILE ∗arqE ; /∗ Arquivo de entrada ∗/FILE ∗arqS ; /∗ Arquivo de sa ída ∗/
15
arqE=fopen ( argv [ 1 ] , "r" ) ; //arqE é para l e i t u r a do arqu ivo ( r−reade )arqS=fopen ( argv [ 2 ] , "w" ) ; //arqS é para e s c r e v e r no arqu i v (w−wr i t e )/∗ Obs . : argc é um i n t e i r o que ind i ca a quant idade de argumentos ∗//∗ argv é um ponte i ro do t i p o char onde : argv [ 0 ] é o nome do arqu ivo
execu táve l ,20 arqv [ 1 ] é o pr imeiro argumento , que no caso é entrada . t x t e o arqgv
[ 2 ] é o segundo argumento , que no caso é sa ida . t x t ∗/
p r i n t f ("|−−−−−−−− Mundo Dos Blocos −−−−−−−−|\n\n" ) ;i f ( ( ! arqE ) | | ( ! arqS ) ) /∗ Caso não s e j a encontrado os arquivos , será
impresso uma mensagem de erro ∗/p r i n t f ("Erro ao encontrar os arqu i vo s : %s e %s\n" , argv [ 1 ] , argv [ 2 ] ) ;
25
else /∗ Caso contrár io , o programa fará as outras i n s t r u çõ e s ∗/{
carac=getc ( arqE ) ; /∗ carac recebe os ca ra c t e r e s con t i do s no arquivo ,um por vez ∗/
while ( carac !=EOF) /∗ Enquando não chegar no f i n a l do arqu ivo : End OfF i l e as i n s t r u çõ e s con t i da s no wh i l e serão executadas ∗/
30 {j =0;while ( ( carac !=32)&&(carac !=EOF)&&(carac !=10) ) /∗Em ASCII 32 é o
space e 10 é o \0 que ind i ca o f i n a l da s t r i n g ∗/{
word [ i ] [ j ]= carac ;35 j++;
carac=getc ( arqE ) ; /∗ carac recebe os ca ra c t e r e s con t i do s noarquivo , um por vez ∗/
}word [ i ] [ j ]= ' \0 ' ;i++;
40 i f ( ( carac==10) | | ( carac==EOF) ) /∗ Caso carac s e j a i g u a l ao fim das t r in g , que no caso é o f i n a l da l i nha ou chegue no f i n a l doarqu ivo qnt recebe a conversão de s t r i n g para i n t e i r o ,convertendo−a em numeral ∗/
{i f ( ( word [ 0 ] [ 0 ] >48 )&&(word [ 0 ] [ 0 ] <58 ) ){
qnt=a t o i (word [ 0 ] ) ;45 Criar (&pbloco , qnt ) ; /∗ qnt é a quant idade de b l o co s a serem
cr iados l i d o s do arqu ivo de entrada ∗/}else /∗ Com i s s o será pulada a l i nha ∗/{
i f ( ( word [ 1 ] [ 0 ] >48 )&&(word [ 1 ] [ 0 ] <58 ) )50 a=a to i (word [ 1 ] ) ;
i f ( ( word [ 3 ] [ 0 ] >48 )&&(word [ 3 ] [ 0 ] <58 ) )b=a to i (word [ 3 ] ) ;
8
i f (word [0 ] [ 0 ]== 'm' ){
55 i f ( ( word [2 ] [ 0 ]== ' o ' )&&(word [2 ] [ 1 ]== ' v ' ) ) /∗ Será l i d o cadacarac t e r a té montar uma s t r in g , nesse caso , se f o r 'm'=move e "ov"=over , será executada a função MoveOver ∗/
MoveOver(&pbloco , a , b ) ;else /∗ Do contrár io , MoveOnto ∗/
MoveOnto(&pbloco , a , b ) ;}
60 else i f (word [0 ] [ 0 ]== ' p ' ){
i f ( ( word [2 ] [ 0 ]== ' o ' )&&(word [2 ] [ 1 ]== ' v ' ) ) /∗ Será l i d o cadacarac t e r a té montar uma s t r in g , nesse caso , se f o r ' p'=p i l e e e "ov"=over , será executada a função Pi leOver ∗/
PileOver(&pbloco , a , b ) ;else /∗ Do contrár io , Pi leOnto ∗/
65 PileOnto(&pbloco , a , b ) ;}else i f (word [0 ] [ 0 ]== ' q ' ) /∗ Quando or l i do , por f i n a l , o
ca rac t e r ' q ' , imp l i cará no f i n a l das in t ruçõe s con t i dasno arquivo , então , a p a r t i r de agora o programa fará asoperações , gerando um arqu ivo de sa ída com a so lução doproblema proposto , ou se ja , com o r e su l t a do esperado ∗/
{for ( j =0; j<qnt ; j++) /∗ Agora a l i s t a será percor r i da a té que
o próximo elemento aponte para NULL, gravando noarqu ivo de sa ída o r e su l t a do esperado ∗/
70 {paux=pbloco . v e t l i s t a [ j ] . pPrimeiro−>pProx ;f p r i n t f ( arqS , "%d : " , j ) ;while ( paux!=NULL){
75 f p r i n t f ( arqS , "%d " , paux−>num) ;paux = paux−>pProx ;
}f p r i n t f ( arqS , "\n" ) ;
}80 f c l o s e ( arqE ) ; /∗ Por f i n a l , arqE e arqS são fechados ∗/
f c l o s e ( arqS ) ;}else
{85 p r i n t f ("Não f o i l o c a l i z a d o o [ q u i t ] \n" ) ;
}}i =0;
}90 carac=getc ( arqE ) ;
}
p r i n t f ("\nArquivo de saida , %s , gerado com sucesso ! ! ! \ n" , argv [ 2 ] ) ;/∗ Por f i n a l , caso tudo ocorra bem , será impresso essa msginformando ao usuár io que o arqu ivo de sa ida f o i gerado comsucesso com o r e su l t a do esperado por e l e ∗/
}95
system ("PAUSE" ) ;return 0 ;
9
}
Programa 14: Main
2.2.1 Função STDAFX.H
No stdafx.h foi incluido todos os arquivos .h que serão usados pelo programa, os.h estão listados no programa abaixo:
#pragma once
#include " t a r g e t v e r . h"#include <s td i o . h>
5 #include <tchar . h>#include <s t d l i b . h>#include "TBloco . h"
10 /∗ Todas as e f e r ên c i a s ad i c i ona i s dos programas foram co locadas nos t d a f x . h ∗/
Programa 15: Stdafx
3 Análise de complexidade dos algoritmos
Considerando todas por comparação e no pior caso:
3.1 Função Volta
T (n) = 1 + T (n)T (0) = 0 (1)
O(n)
3.2 Função PileOver
f(n) = 5 (2)
O(5)
3.3 Função MoveOver
f(n) = 5 (3)
O(5)
10
3.4 Função PileOnto
f(n) = 5 (4)
O(5)
3.5 Função start
f(n) = 1 +n−1∑i=0
1 = n (5)
O(n)
3.6 Função MoveOnto
f(n) = 6 (6)
O(6)
3.7 Função Imprime
f(n) =n−1∑i=0
1 = n (7)
O(n)
3.8 Função Busca
f(n) =n−1∑i=0
n−1∑i=0
n∑i=0
1 = n3/2 (8)
O(n3)
3.9 Função Criar
f(n) =n−1∑i=0
1 = n (9)
O(n)
11
4 Testes
Alguns testes com o programa:Argumentos: entrada.txt saida.txt
Figura 1: Argumentos
Comando: TP2AEDSI-JOHN.exe entrada.txt johnnatan.txt
Figura 2: Comando
12
Arquivo de entrada: entrada.txt
Figura 3: Arquivo de entrada
Execução do comando
Figura 4: Execuxão do comando
Arquivo de saída: johnnatan.txt
13
Figura 5: Arquivo de saída
5 Conclusão
Neste trabalho foram revistos conceitos sobre alocação dinâmica, TAD(TiposAbstratos de Dados), listas encadeadas, argumentos argv, argc, pratica de ediçãode textos em LATEX, bem como o melhor entendimento sobre ordem de complexidadee maturidade na linguagem C. A maior di�culdade foi a abstração para a resoluçãodo problema proposto, mas, uma vez que entendido o que se pede, tornou-se simplesa implementação. Muito dos algoritmos são extraídos de [?].
Referências
[1] David Menotti Algoritmos e Estruturas de Dados I: Listas En-cadeadas. http://www.decom.ufop.br/prof/menotti/aedI092/slides/
aula09-10-ListaEnc.ppt, visitado em 03/10/2009.
[2] Márcio Santi Wikipédia, 2009 http://pt.wikipedia.org/wiki/Lista_
ligada/, visitado em 01/10/2009.
[3] Aldrovando Luís Azeredo Araújo Os Argumentos argc e argv, 1999. http://www.mtm.ufsc.br/~azeredo/cursoC/aulas/c790.html, visitado em 30/08/2009.
[4] Paulo Feo�lof Projeto de Algoritmos: Listas Encadeadas, 2009 http://www.
ime.usp.br/~pf/algoritmos/aulas/lista.html, visitado em 28/09/2009.
14
