Trabalho Prático 2 de Aedis Listas Encadeadas

Universidade Federal de Ouro Preto UFOP Departamento de Computação e Sistemas DECSI Disciplina Algoritmos e Estrutura de Dados I CSI 488 Professor Bruno Hott brhottufopedubr Valor 15 ponto 15 da nota total Data de entrega 03072025 Trabalho Prático 2 Listas Encadeadas Objetivos Consiste em concretizar os conceitos de Listas implementadas por encadeamento através de uma aplicação Matrizes duplamente encadeadas Descrição Matrizes duplamente encadeadas é uma maneira eficiente de representar estruturas com tamanho variável eou desconhecido com o emprego de alocação encadeada Cada coluna da matriz será representada por uma lista duplamente encadeada com uma célula cabeça Da mesma maneira cada linha da matriz também será represen tada por uma lista duplamente encadeada com uma célula cabeça Cada célula da estrutura além das células cabeça representará uma letra na matriz e deverá ser como no código abaixo typedef struct TCelula struct TCelula direita esquerda abaixo acima int linha coluna char letra TCelula Os campos abaixo e acima devem ser usados para referenciar os elementos na mesma coluna Os campo direita e esquerda devem ser usados para referenciar os elementos na mesma linha Dada uma matriz A para uma letra Ai j deverá haver uma célula com o campo letra contendo Ai j o campo linha contendo i e o campo coluna contendo j Essa célula deverá pertencer a lista duplamente encadeada i e também deverá pertencer à lista duplamente encadeada da coluna j Ou seja cada célula pertencerá a duas listas ao mesmo tempo Para diferenciar as células cabeça coloque 1 nos campos linha e coluna dessas células A Figura 1 é um desenho esquemático de uma matriz duplamente encadeada Figura 1 Desenho esquemático de uma matriz duplamente encadeada Caça Palavras v20 Dada a representação anterior o trabalho consiste em desenvolver um tipo abstrato de dados TAD TCacaPalavras em C que será utilizado na implementação de uma versão atualizada de um caça palavras Para isso você deverá reimplementar as operações do programa descritos no trabalho prático 1 1 Note que a implementação das funções irá mudar mas o conjunto de operações do trabalho 1 será suficiente para a resolução deste novo problema A adequação dos métodos para trabalhar com listas encadeadas faz parte da avaliação Não se esqueça de inserir na documentação as decisões de implementação que foram tomadas Valerão pontos a correta escolha da estrutura de dados o bom uso de funções e procedimentos a modula ridade a possibilidade de generalização do problema assim como a documentação do seu trabalho Note que as palavras estão em qualquer direção horizontal vertical nas diagonais e que podem ser escritas normalmente ou de maneira inversa É obrigatório o uso de alocação dinâmica de memória para implementar as listas de adjacência que representam as matrizes Preocupese inicialmente em detalhar a estrutura do programa isto já valerá pontos Mas observe que valerá a totalidade dos pontos apenas se todo o código for detalhado de maneira clara e suficiente O que deve ser entregue Código fonte do programa em C bem identado e comentado e documentação do trabalho Entre outras coisas a documentação deve conter 1 Introdução descrição do problema a ser resolvido e visão geral sobre o funcionamento do programa 2 Implementação descrição sobre a implementação do programa Deve ser detalhada a estrutura de dados utilizada de preferência com diagramas ilustrativos o funcionamento das principais funções e procedimentos utilizados o formato de entrada e saída de dados bem como decisões tomadas relativas aos casos e detalhes de especificação que porventura estejam omissos no enunciado Muito importante os códigos utilizados nas implementações devem ser inseridos na documentação 3 Estudo de complexidade estudo da complexidade do tempo de execução dos procedimentos imple mentados e do programa como um todo notação O 4 Listagem de testes executados os testes executados devem ser apresentados analisados e discutidos 5 Conclusão comentários gerais sobre o trabalho e as principais dificuldades encontradas em sua imple mentação 6 Bibliografia bibliografia utilizada para o desenvolvimento do trabalho incluindo sites da Internet se for o caso Uma referência bibliográfica deve ser citada no texto quando da sua utilização 7 Em Latex o trabalho deverá ser elaboradoescrito em latex 8 Formato mandatoriamente em PDF Obs1 Consulte as dicas do Prof Nívio Ziviani de como deve ser feita uma boa implementação e documen tação de um trabalho prático httpshomepagesdccufmgbr niviocursosaed2roteiro Obs2 Veja modelo de como fazer o trabalho em latex httpsbitly4jMoUQh Como deve ser feita a entrega A entrega DEVE ser feita pelo Moodle httpsmoodlepresencialufopbr na forma de um único arquivo zipado contendo o código os arquivos e a documentação Também deve ser entregue a documentação impressa na próxima aula teórica ou prática após a data de entrega do trabalho Comentários gerais Comece a fazer este trabalho logo enquanto o problema está fresco na memória e o prazo para terminálo está tão longe quanto jamais poderá estar Faça o trabalho de maneira incremental comece com os métodos mais simples sempre testando exausti vamente antes de passar para a próxima etapa Clareza identação e comentários no programa também serão avaliados O trabalho é individual grupo de UM aluno Trabalhos copiados e FONTE terão nota zero Devido a recorrentes problemas com cópias de trabalhos plágios os autores de trabalhos copiados também terão todos os demais trabalhos zerados como forma de punição e coação ao plágio acadêmico 2 O professor se reserva o direito de realizar avaliações complementares para qualquer trabalho prático com suspeita de uso de IA O que pode incluir entrevista questão específica na prova entre outras para verificar a autoria e a compreensão real do conteúdo com foco em garantir o aprendizado do aluno Trabalhos entregue em atraso serão aceitos todavia a nota atribuída ao trabalho será zero Evite discussões inócuas com o professor em tentar postergar a data de entrega do referido trabalho 3 Trabalho Pratico 2 CacaPalavras v20 com Matrizes Duplamente Encadeadas Seu Nome Completo Matrıcula Sua Matrıcula 03 de Julho de 2025 1 Conteudo 1 Introducao 3 2 Implementacao 3 21 Estrutura de Dados Utilizada 3 22 Funcionamento das Principais Funcoes 5 23 Formato de Entrada e Saıda de Dados 14 24 Decisoes de Implementacao 15 3 Estudo de Complexidade 15 31 Complexidade das Funcoes Auxiliares e de Gerenciamento 15 4 Listagem de Testes Executados 17 41 Cenario de Teste 1 Inicializacao e Insercao Basica 17 5 Conclusao 25 6 Bibliografia 25 2 1 Introducao Este documento apresenta o desenvolvimento do Trabalho Pratico 2 TP2 da disciplina de Algoritmos e Estrutura de Dados I CSI 488 da Universidade Federal de Ouro Preto UFOP O objetivo central deste trabalho e a concretizacao dos conceitos de Listas imple mentadas por encadeamento atraves de uma aplicacao Matrizes duplamente encadeadas O desafio consiste em representar uma matriz de caracteres de forma eficiente per mitindo um tamanho variavel eou desconhecido com o emprego de alocacao encadeada Para isso cada coluna da matriz sera representada por uma lista duplamente encadeada com uma celula cabeca Da mesma maneira cada linha da matriz tambem sera represen tada por uma lista duplamente encadeada com uma celula cabeca As celulas de dados por sua vez representam as letras na matriz e deverao ser conforme a estrutura TCelula Cada celula pertence simultaneamente a lista duplamente encadeada de sua respectiva linha e tambem a lista duplamente encadeada da coluna Este trabalho e uma reimplementacao das operacoes propostas no Trabalho Pratico 1 adaptandoas para operar com a nova estrutura de Matrizes Duplamente Encadeadas A adequacao dos metodos para trabalhar com listas encadeadas faz parte da avaliacao A aplicacao final visa localizar palavras em qualquer direcao horizontal vertical nas diagonais e sentido normal ou inverso dentro da matriz simulando um jogo de caca palavras v20 E obrigatorio o uso de alocacao dinˆamica de memoria para implementar as listas que representam as matrizes 2 Implementacao A implementacao do CacaPalavras v20 foi desenvolvida em linguagem C seguindo o paradigma de Tipo Abstrato de Dados TAD TCacaPalavras e fazendo uso extensivo de alocacao dinˆamica de memoria para gerenciar a estrutura da matriz duplamente encade ada A modularidade foi priorizada dividindo o codigo em arquivos de cabecalho h e implementacao c para cada TAD e estrutura fundamental 21 Estrutura de Dados Utilizada A base da nossa matriz e a estrutura TCelula que representa cada elemento da grade do cacapalavras Conforme especificado cada TCelula possui ponteiros para as celulas adja centes em suas respectivas linhas direita esquerda e colunas abaixo acima Alem disso armazena as coordenadas linha coluna e o caractere letra que representa As celulas cabeca que marcam o inıcio de cada linha e coluna sao diferenciadas pelo valor 1 nos campos linha e coluna Elas nao armazenam letras mas servem como pontos de entrada para as listas encadeadas das linhas e colunas A estrutura TCacaPalavras gerencia a matriz como um todo contendo ponteiros para as listas de celulas cabeca de linhas cabecaLinhas e colunas cabecaColunas alem de armazenar o numero atual de linhas e colunas numLinhas numColunas Definicao de TCelula 1 D e f i n i o da estrutura TCelula conforme o enunciado 2 typedef struct TCelula 3 struct TCelula direita Ponteiro para a c l u l a direita na mesma linha 3 4 struct TCelula esquerda Ponteiro para a c l u l a esquerda na mesma linha 5 struct TCelula abaixo Ponteiro para a c l u l a abaixo na mesma coluna 6 struct TCelula acima Ponteiro para a c l u l a acima na mesma coluna 7 int linha ndice da linha da c l u l a 8 int coluna ndice da coluna da c l u l a 9 char letra Caractere que a c l u l a representa na matriz 10 TCelula Listing 1 Definicao da estrutura TCelula Definicao de TCacaPalavras 1 include stdboolh Para usar bool 2 3 D e f i n i o da estrutura TCelula repetida aqui para self containment no tex 4 mas em um projeto real estaria em TCelulah e seria i n c l u d a 5 typedef struct TCelula 6 struct TCelula direita 7 struct TCelula esquerda 8 struct TCelula abaixo 9 struct TCelula acima 10 int linha 11 int coluna 12 char letra 13 TCelula 14 15 D e f i n i o do TAD TCacaPalavras 16 typedef struct TCacaPalavras 17 TCelula cabecaLinhas Ponteiro para a primeira c l u l a c a b e a das linhas 18 TCelula cabecaColunas Ponteiro para a primeira c l u l a c a b e a das colunas 19 int numLinhas N m e r o atual de linhas na matriz 20 int numColunas N m e r o atual de colunas na matriz 21 TCacaPalavras 22 23 P r o t t i p o s das f u n e s para o TAD TCacaPalavras 24 25 Inicializa a estrutura TCacaPalavras 26 Retorna um ponteiro para a estrutura inicializada ou NULL em caso de erro 27 TCacaPalavras TCacaPalavrasInicializa 28 29 Insere uma letra na p o s i o linha coluna da matriz 30 Se a c l u l a j existe atualiza a letra Caso c o n t r r i o cria e conecta 4 31 Retorna 1 se a i n s e r o for bem sucedida 0 caso c o n t r r i o 32 int TCacaPalavrasInsereLetra TCacaPalavras cacaPalavras int linha int coluna char letra 33 34 Busca uma c l u l a e s p e c f i c a na matriz na p o s i o linha coluna 35 Retorna um ponteiro para a TCelula se encontrada NULL caso c o n t r r i o 36 TCelula TCacaPalavrasBuscaCelula TCacaPalavras cacaPalavras int linha int coluna 37 38 Imprime a matriz no console para d e p u r a o 39 void TCacaPalavrasImprimeMatriz TCacaPalavras cacaPalavras 40 41 Busca uma palavra na matriz em todas as 8 d i r e e s horizontal vertical diagonais normal e inversa 42 Retorna true se a palavra for encontrada false caso c o n t r r i o 43 bool TCacaPalavrasBuscaPalavra TCacaPalavras cacaPalavras const char palavra 44 45 Libera toda a m e m r i a alocada para a matriz 46 void TCacaPalavrasLibera TCacaPalavras cacaPalavras Listing 2 Definicao do TAD TCacaPalavras 22 Funcionamento das Principais Funcoes CriaNovaCelula Uma funcao auxiliar para encapsular a alocacao e inicializacao de uma nova TCelula Simplifica o codigo e evita duplicacao ao criar celulas de dados ou celulas cabeca 1 include stdlibh Para malloc free 2 include stdioh Para fprintf 3 4 F u n o auxiliar para criar uma nova TCelula 5 TCelula CriaNovaCelula int linha int coluna char letra 6 TCelula nova TCelula mallocsizeofTCelula A l o c a o d i n m i c a de m e m r i a 7 if nova NULL 8 fprintfstderr Errodealocacaodememoriaparacelula Usa stderr para erros 9 return NULL 10 11 nova direita NULL 12 nova esquerda NULL 13 nova abaixo NULL 14 nova acima NULL 15 nova linha linha 16 nova coluna coluna 17 nova letra letra 18 return nova 5 19 Listing 3 Implementacao da funcao CriaNovaCelula EncontraOuCriaCabeca Crucial para o crescimento dinˆamico da matriz Esta funcao verifica se uma celula cabeca para uma dada linha ou coluna ja existe Se sim retorna o ponteiro para ela Caso contrario aloca uma nova TCelula configurada como celula cabeca com linhacoluna apropriados e 1 no campo nao utilizado e a insere na lista de cabecas de forma ordenada atualizando o contador de linhas ou colunas 1 Encontra ou cria uma c l u l a c a b e a de linhacoluna 2 Retorna a c l u l a c a b e a correspondente ao indice ou NULL se houver erro 3 isLinha 1 para c a b e a de linha 0 para c a b e a de coluna 4 TCelula EncontraOuCriaCabeca TCelula listaCabecas int indice int numTotal int isLinha 5 TCelula atual listaCabecas 6 TCelula anterior NULL 7 8 Percorre a lista de c a b e a s para encontrar a c a b e a existente ou o ponto de i n s e r o 9 while atual NULL 10 int atualIndice isLinha atual linha atual coluna 11 if atualIndice indice C a b e a encontrada 12 return atual 13 14 if atualIndice indice Ponto de i n s e r o manter ordenado 15 break 16 17 anterior atual 18 atual atual direita Assumindo que c a b e a s de linhacoluna s o ligadas via direita 19 20 21 Se n o encontrou cria uma nova c a b e a 22 TCelula novaCabeca CriaNovaCelula isLinha indice 1 isLinha 1 indice 0 Letra nula para c a b e a 23 if novaCabeca NULL 24 return NULL 25 26 As c l u l a s c a b e a n o representam letras mas sim pontos de entrada para linhascolunas 27 Seus campos linhacoluna s o usados para i d e n t i f i c a o 28 novaCabeca linha isLinha indice 1 29 novaCabeca coluna isLinha 1 indice 30 31 Conecta a nova c a b e a na lista de c a b e a s 32 if anterior NULL Nova c a b e a no i n c i o da lista 33 novaCabeca direita listaCabecas 6 34 listaCabecas novaCabeca 35 else Nova c a b e a no meio ou fim da lista 36 novaCabeca direita atual 37 anterior direita novaCabeca 38 39 40 numTotal Incrementa o contador de linhas ou colunas 41 return novaCabeca 42 Listing 4 Implementacao da funcao EncontraOuCriaCabeca TCacaPalavras Inicializa Esta funcao e responsavel por alocar e inicializar a estrutura TCacaPalavras Ela define os ponteiros para as listas de cabecas de linha e coluna como NULL e os contadores de linhas e colunas como zero preparando a estrutura para receber dados 1 Inicializa a estrutura TCacaPalavras 2 TCacaPalavras TCacaPalavrasInicializa 3 TCacaPalavras cacaPalavras TCacaPalavras mallocsizeof TCacaPalavras 4 if cacaPalavras NULL 5 fprintfstderr Errodealocacaodememoriapara TCacaPalavras 6 return NULL 7 8 cacaPalavras cabecaLinhas NULL 9 cacaPalavras cabecaColunas NULL 10 cacaPalavras numLinhas 0 11 cacaPalavras numColunas 0 12 return cacaPalavras 13 Listing 5 Implementacao da funcao TCacaPalavrasInicializa TCacaPalavras InsereLetra Esta funcao insere ou atualiza uma letra na matriz na posicao linha coluna Pri meiramente garante que as celulas cabeca da linha e da coluna existam utilizando EncontraOuCriaCabeca Em seguida percorre as listas duplamente encadeadas da li nha e da coluna para verificar se a celula na posicao linha coluna ja existe Se existir a letra e atualizada Se nao uma nova TCelula e alocada e conectada tanto na lista da linha usando direitaesquerda quanto na lista da coluna usando abaixoacima mantendo a ordenacao 1 include stringh Para strlen 2 3 Insere uma letra na p o s i o linha coluna da matriz 4 int TCacaPalavrasInsereLetra TCacaPalavras cacaPalavras int linha int coluna char letra 5 if cacaPalavras NULL linha 0 coluna 0 7 6 fprintfstderr P a r m e t r o s i n v l i d o s para TCacaPalavrasInsereLetra 7 return 0 8 9 10 Garante que as c a b e a s de linha e coluna existam 11 TCelula cabecaLinha EncontraOuCriaCabeca cacaPalavras cabecaLinhas linha cacaPalavras numLinhas 1 12 if cabecaLinha NULL return 0 13 TCelula cabecaColuna EncontraOuCriaCabeca cacaPalavras cabecaColunas coluna cacaPalavras numColunas 0 14 if cabecaColuna NULL return 0 15 16 Procura por c l u l a existente na linha 17 TCelula celulaLinhaAtual cabecaLinha direita 18 TCelula anteriorLinha cabecaLinha 19 while celulaLinhaAtual NULL celulaLinhaAtual coluna coluna 20 anteriorLinha celulaLinhaAtual 21 celulaLinhaAtual celulaLinhaAtual direita 22 23 24 Procura por c l u l a existente na coluna 25 TCelula celulaColunaAtual cabecaColuna abaixo 26 TCelula anteriorColuna cabecaColuna 27 while celulaColunaAtual NULL celulaColunaAtual linha linha 28 anteriorColuna celulaColunaAtual 29 celulaColunaAtual celulaColunaAtual abaixo 30 31 32 Se a c l u l a j existe atualiza a letra e retorna 33 if celulaLinhaAtual NULL celulaLinhaAtual coluna coluna 34 celulaColunaAtual NULL celulaColunaAtual linha linha 35 celulaLinhaAtual celulaColunaAtual Verifica se ambos os ponteiros apontam para a mesma c l u l a 36 celulaLinhaAtual letra letra 37 return 1 38 39 40 Se n o existe cria uma nova c l u l a de dados 41 TCelula novaCelula CriaNovaCelula linha coluna letra 42 if novaCelula NULL return 0 43 44 Conecta a nova c l u l a na lista da LINHA 45 novaCelula direita celulaLinhaAtual 46 novaCelula esquerda anteriorLinha 47 anteriorLinha direita novaCelula 48 if celulaLinhaAtual NULL 49 celulaLinhaAtual esquerda novaCelula 8 50 51 52 Conecta a nova c l u l a na lista da COLUNA 53 novaCelula abaixo celulaColunaAtual 54 novaCelula acima anteriorColuna 55 anteriorColuna abaixo novaCelula 56 if celulaColunaAtual NULL 57 celulaColunaAtual acima novaCelula 58 59 60 Atualiza o n m e r o de linhascolunas se as c a b e a s foram criadas dinamicamente 61 j tratado dentro de EncontraOuCriaCabeca 62 return 1 63 Listing 6 Implementacao da funcao TCacaPalavrasInsereLetra TCacaPalavras BuscaCelula Uma funcao auxiliar para localizar uma TCelula especıfica na matriz dada sua linha e coluna E utilizada principalmente para otimizar as buscas diagonais onde nao ha ponteiros diretos para a proxima celula na direcao desejada A funcao percorre a lista de cabecas de linha ate encontrar a linha desejada e em seguida percorre a lista de celulas de dados dessa linha ate encontrar a coluna correspondente 1 Busca uma c l u l a e s p e c f i c a na matriz na p o s i o linha coluna 2 TCelula TCacaPalavrasBuscaCelula TCacaPalavras cacaPalavras int linha int coluna 3 if cacaPalavras NULL linha 0 coluna 0 4 return NULL 5 6 7 Encontra a c a b e a da linha 8 TCelula cabecaLinha cacaPalavras cabecaLinhas 9 while cabecaLinha NULL cabecaLinha linha linha 10 cabecaLinha cabecaLinha direita 11 12 13 if cabecaLinha NULL Linha n o existe 14 return NULL 15 16 17 Percorre a linha para encontrar a coluna 18 TCelula atual cabecaLinha direita 19 while atual NULL atual coluna coluna 20 atual atual direita 21 22 23 if atual NULL atual coluna coluna 24 return atual C l u l a encontrada 9 25 26 27 return NULL C l u l a n o encontrada 28 Listing 7 Implementacao da funcao TCacaPalavrasBuscaCelula TCacaPalavras ImprimeMatriz Esta funcao serve para depuracao e visualizacao do estado atual da matriz Ela percorre as listas de celulas de dados e imprime as letras em suas respectivas posicoes Para posicoes vazias na matriz densa nao preenchidas com celulas de dados um caractere e impresso A funcao tenta determinar os limites da matriz para uma impressao mais legıvel 1 Imprime a matriz no console para d e p u r a o e v i s u a l i z a o 2 void TCacaPalavrasImprimeMatriz TCacaPalavras cacaPalavras 3 if cacaPalavras NULL cacaPalavras cabecaLinhas NULL 4 printfMatrizvaziaounaoinicializada 5 return 6 7 8 printf MatrizCacaPalavras 9 10 Encontra a maior linha e coluna para determinar os limites de i m p r e s s o 11 int maxLinha 1 12 int maxColuna 1 13 TCelula tempLinhaCabeca cacaPalavras cabecaLinhas 14 while tempLinhaCabeca NULL 15 iftempLinhaCabeca linha maxLinha 16 maxLinha tempLinhaCabeca linha 17 18 TCelula tempCelula tempLinhaCabeca direita 19 whiletempCelula NULL 20 iftempCelula coluna maxColuna 21 maxColuna tempCelula coluna 22 23 tempCelula tempCelula direita 24 25 Nota As c a b e a s de linha e s t o encadeadas pelo ponteiro direita t a m b m 26 para formar a lista de c a b e a s de linha 27 tempLinhaCabeca tempLinhaCabeca direita 28 29 30 Para cada linha existente 31 for int i 0 i maxLinha i 32 TCelula cabecaLinhaAtual cacaPalavras cabecaLinhas 33 while cabecaLinhaAtual NULL cabecaLinhaAtual linha i 10 34 cabecaLinhaAtual cabecaLinhaAtual direita 35 36 37 printfLinha2d i 38 if cabecaLinhaAtual NULL Se a linha n o existe imprime e s p a o s 39 for int j 0 j maxColuna j 40 printf 41 42 else 43 TCelula atual cabecaLinhaAtual direita 44 for int j 0 j maxColuna j 45 if atual NULL atual coluna j 46 printfc atual letra 47 atual atual direita 48 else 49 printf Caractere para c l u l a s vazias 50 51 52 53 printf 54 55 printf 56 Listing 8 Implementacao da funcao TCacaPalavrasImprimeMatriz BuscaEmDirecaoRefatorada Funcao auxiliar para TCacaPalavras BuscaPalavra Ela tenta encontrar uma palavra em uma direcao especıfica dr dc a partir de uma celula inicial Para movimen tos horizontais e verticais ela utiliza os ponteiros diretos direita esquerda acima abaixo Para movimentos diagonais ela invoca TCacaPalavras BuscaCelula para lo calizar a proxima celula com base nas coordenadas esperadas pois nao ha ponteiros diagonais na estrutura TCelula 1 Refatorando BuscaEmDirecao para ser mais g e n r i c a e usar TCacaPalavrasBuscaCelula 2 bool BuscaEmDirecaoRefatorada TCacaPalavras cacaPalavras TCelula celulainicial const char palavra int dr int dc 3 if celulainicial NULL palavra NULL palavra 0 cacaPalavras NULL 4 return false 5 6 7 int len strlenpalavra 8 TCelula atual celulainicial 9 int k 0 ndice do caractere na palavra 10 11 for k 0 k len k 12 if atual NULL atual letra palavrak 11 13 return false C l u l a nula ou caractere n o corresponde 14 15 16 if k len 1 ltimo caractere da palavra encontrado 17 return true 18 19 20 Move para a p r x i m a c l u l a na d i r e o dr dc 21 Para d i r e e s n o diretas diagonais precisamos buscar pela p o s i o linhadr colunadc 22 Isso p r e s s u p e que as c l u l a s nas d i r e e s n o diretas podem n o estar diretamente ligadas 23 if dr 0 dc 1 Direita 24 atual atual direita 25 else if dr 0 dc 1 Esquerda 26 atual atual esquerda 27 else if dr 1 dc 0 Abaixo 28 atual atual abaixo 29 else if dr 1 dc 0 Acima 30 atual atual acima 31 else Diagonais ou qualquer outra d i r e o n o direta 32 atual TCacaPalavrasBuscaCelula cacaPalavras atual linha dr atual coluna dc 33 34 35 return false Deve ser true se a palavra for encontrada no loop 36 Listing 9 Implementacao da funcao BuscaEmDirecaoRefatorada TCacaPalavras BuscaPalavra Esta e a principal funcao de busca do cacapalavras Ela itera sobre cada celula de dados da matriz tratandoa como um possıvel ponto de partida para a palavra a ser encontrada Para cada ponto de partida ela tenta buscar a palavra em todas as 8 direcoes possıveis horizontal vertical e as quatro diagonais incluindo os sentidos normal e inverso uti lizando a funcao auxiliar BuscaEmDirecaoRefatorada Se a palavra for encontrada em qualquer uma dessas tentativas a funcao retorna true As palavras podem estar em qual quer direcao horizontal vertical nas diagonais e que podem ser escritas normalmente ou de maneira inversa 1 include stringh Para strlen 2 3 Busca uma palavra na matriz em todas as 8 d i r e e s 4 bool TCacaPalavrasBuscaPalavra TCacaPalavras cacaPalavras const char palavra 5 if cacaPalavras NULL palavra NULL palavra 0 12 6 return false 7 8 9 int len strlenpalavra 10 if len 0 return false 11 12 D i r e e s de busca dr deltalinha dc deltacoluna 13 Horizontal 0 1 01 14 Vertical 1 0 10 15 Diagonal 1 1 11 11 11 16 int dr 0 0 1 1 1 1 1 1 17 int dc 1 1 0 0 1 1 1 1 18 19 Percorre todas as c l u l a s da matriz como pontos de partida 20 TCelula cabecaLinhaAtual cacaPalavras cabecaLinhas 21 while cabecaLinhaAtual NULL 22 TCelula celulaAtual cabecaLinhaAtual direita Primeira c l u l a de dados da linha 23 while celulaAtual NULL 24 Tenta buscar a palavra em todas as 8 d i r e e s a partir desta c l u l a 25 for int i 0 i 8 i 26 if BuscaEmDirecaoRefatorada cacaPalavras celulaAtual palavra dri dci 27 printfPalavra sencontradaapartirde ddnadirecaodrddcd 28 palavra celulaAtual linha celulaAtual coluna dri dci 29 return true 30 31 32 celulaAtual celulaAtual direita 33 34 cabecaLinhaAtual cabecaLinhaAtual direita P r x i m a c a b e a de linha 35 36 37 return false Palavra n o encontrada em nenhuma p o s i o d i r e o 38 Listing 10 Implementacao da funcao TCacaPalavrasBuscaPalavra TCacaPalavras Libera Responsavel por desalocar toda a memoria alocada dinamicamente para a matriz preve nindo vazamentos de memoria A estrategia de liberacao consiste em percorrer as listas de linhas liberando todas as celulas de dados associadas a cada linha Apos todas as celulas de dados serem liberadas as celulas cabeca de linha e posteriormente as celulas cabeca de coluna sao liberadas Finalmente a propria estrutura TCacaPalavras e desalocada E crucial que cada celula seja liberada apenas uma vez 13 1 Libera toda a m e m r i a alocada para a matriz 2 Isso requer uma travessia cuidadosa para evitar vazamentos de m e m r i a e acessos i n v l i d o s 3 void TCacaPalavrasLibera TCacaPalavras cacaPalavras 4 if cacaPalavras NULL return 5 6 Liberar c l u l a s de dados e c a b e a s de linha 7 TCelula currentLinhaHead cacaPalavras cabecaLinhas 8 while currentLinhaHead NULL 9 TCelula currentDataCell currentLinhaHead direita 10 while currentDataCell NULL 11 TCelula nextDataCell currentDataCell direita 12 free currentDataCell Libera a c l u l a de dados 13 currentDataCell nextDataCell 14 15 TCelula nextLinhaHead currentLinhaHead direita 16 free currentLinhaHead Libera a c a b e a da linha 17 currentLinhaHead nextLinhaHead 18 19 20 Liberar c a b e a s de coluna 21 Nota A direita das c a b e a s de coluna aponta para a p r x i m a c a b e a de coluna N O para c l u l a s de dados 22 TCelula currentColumnaHead cacaPalavras cabecaColunas 23 while currentColumnaHead NULL 24 TCelula nextColumnaHead currentColumnaHead direita 25 free currentColumnaHead Libera a c a b e a da coluna 26 currentColumnaHead nextColumnaHead 27 28 29 freecacaPalavras Libera a estrutura TCacaPalavras 30 Listing 11 Implementacao da funcao TCacaPalavrasLibera 23 Formato de Entrada e Saıda de Dados Entrada A entrada de dados para a matriz sera realizada atraves de chamadas programaticas a funcao TCacaPalavras InsereLetra no mainc onde cada letra e fornecida com sua respectiva linha e coluna Para a busca de palavras a palavra a ser encontrada e passada como uma string para a funcao TCacaPalavras BuscaPalavra Saıda A saıda principal do programa sera a indicacao no console se uma palavra foi encontrada ou nao A funcao TCacaPalavras ImprimeMatriz fornece uma representacao visual da matriz para fins de depuracao e compreensao Em caso de sucesso na busca a funcao TCacaPalavras BuscaPalavra tambem imprime as coordenadas de inıcio da palavra e a 14 direcao em que foi encontrada Mensagens de erro ou alocacao sao impressas no stderr para indicar problemas 24 Decisoes de Implementacao Celulas Cabeca Ordenadas As listas de celulas cabeca de linha e coluna sao mantidas ordenadas por seus ındices linha ou coluna Isso facilita a insercao e busca de celulas cabeca especıficas otimizando o processo de adicao de novas linhascolunas Insercao de Letras Ordenada Ao inserir uma nova TCelula na lista de uma linha ou coluna ela e inserida de forma ordenada pela sua coluna para listas de linha ou linha para listas de coluna Isso permite uma travessia eficiente e a busca por celulas especıficas Reaproveitamento de Celulas Existentes A funcao TCacaPalavras InsereLetra verifica se uma celula na posicao linha coluna ja existe Se sim a letra e sim plesmente atualizada evitando alocacao desnecessaria e mantendo a integridade da estrutura Busca Diagonal com TCacaPalavras BuscaCelula Devido a natureza da ma triz duplamente encadeada sem ponteiros diretos para diagonais a funcao auxiliar TCacaPalavras BuscaCelula foi implementada para permitir a busca de celulas especıficas por suas coordenadas Isso e fundamental para a implementacao da busca de palavras em direcoes diagonais de forma eficiente Impressao para De puracao A funcao TCacaPalavras ImprimeMatriz foi desenvolvida para auxiliar na depuracao e visualizacao da matriz Ela lida com matrizes esparsas imprimindo um caractere placeholder onde nao ha celulas de dados Liberacao de Memoria A estrategia de liberacao de memoria foi cuidadosamente pensada para evitar vazamentos e dupla liberacao percorrendo e liberando as celulas de dados atraves de uma das dimensoes linhas e depois liberando as celulas cabeca 3 Estudo de Complexidade A analise de complexidade do tempo de execucao dos procedimentos implementados e do programa como um todo e fundamental para compreender o desempenho do programa utilizando a notacao O Big O 31 Complexidade das Funcoes Auxiliares e de Gerenciamento CriaNovaCelula A alocacao de memoria e a inicializacao dos ponteiros sao operacoes de tempo constante Complexidade O1 15 EncontraOuCriaCabeca Esta funcao percorre a lista de cabecas de linha ou de coluna ate encontrar a posicao correta para insercao ou identificar a cabeca existente No pior caso ela pode percorrer todas as cabecas existentes Seja L o numero de linhas e C o numero de colunas Complexidade OmaxL C TCacaPalavras Inicializa Consiste em uma unica alocacao de memoria e algumas inicializacoes de ponteiros Complexidade O1 TCacaPalavras InsereLetra Esta funcao envolve as seguintes etapas Chamadas a EncontraOuCriaCabeca para linha e coluna OmaxL C Percorrer a lista de celulas de dados na linha para encontrar o ponto de insercao No pior caso OC onde C e o numero de celulas de dados na linha Percorrer a lista de celulas de dados na coluna para encontrar o ponto de insercao No pior caso OL onde L e o numero de celulas de dados na coluna Alocacao e conexao da nova celula O1 No pior caso matriz densa ou inserir em uma nova linhacoluna distante o tempo dominante sera o percurso das listas Complexidade OL C Considerando NR como o numero total de linhas e NC o numero total de colunas e que C e L podem ir ate NC e NR respectivamente a complexidade no pior caso e ONR NC TCacaPalavras BuscaCelula Percorre a lista de cabecas de linha e em seguida a lista de celulas de dados da linha Complexidade OL para encontrar a cabeca da linha e OC para encontrar a celula na coluna No pior caso OL C TCacaPalavras ImprimeMatriz Esta funcao precisa percorrer todas as cabecas de linha e para cada cabeca todas as celulas de dados daquela linha para imprimir a matriz Adicionalmente ela busca os limites maximos de linha e coluna Se M N for o tamanho da matriz virtual maior linha por maior coluna e K o numero de celulas preenchidas Complexidade OM N no pior caso matriz densa pois itera sobre todas as posicoes possıveis para imprimir A busca por maxLinha e maxColuna e OK A impressao em si e OM N 16 BuscaEmDirecaoRefatorada Esta funcao percorre a palavra caractere por caractere Para cada caractere ela realiza um passo na direcao Se o movimento e horizontal ou vertical e O1 para mover para a proxima celula usando os ponteiros diretos Se e diagonal ela chama TCacaPalavras BuscaCelula Complexidade Se o tamanho da palavra e P e no pior caso todas as chamadas diagonais ocorrem e cada chamada a TCacaPalavras BuscaCelula custa OLC entao a complexidade seria OP L C TCacaPalavras BuscaPalavra Esta e a funcao mais complexa Ela itera sobre todas as celulas de dados na matriz Para cada celula de dados ela tenta buscar a palavra em 8 direcoes diferentes Se K for o numero total de celulas de dados na matriz e P o tamanho da palavra Complexidade K celulas de partida 8 direcoes Complexidade de BuscaEmDirecaoRefatorada Total OK 8 P L C O 8 e uma constante entao OK P L C No pior caso K pode ser M N matriz densa entao OM N P L C TCacaPalavras Libera Percorre todas as celulas de dados via cabecas de linha liberandoas Em seguida libera as cabecas de linha e as cabecas de coluna Complexidade OK L C onde K e o numero de celulas de dados L o numero de linhas e C o numero de colunas Essencialmente e proporcional ao numero total de elementos alocados 4 Listagem de Testes Executados Os testes foram realizados utilizando a funcao main para simular a interacao com o TAD TCacaPalavras O objetivo foi verificar a correta inicializacao insercao de letras in cluindo atualizacao de celulas existentes impressao da matriz e principalmente a fun cionalidade de busca de palavras em diversas direcoes e sentidos 41 Cenario de Teste 1 Inicializacao e Insercao Basica Entrada O programa foi inicializado e uma sequˆencia de caracteres foi inserida para formar uma matriz 3x3 basica com algumas celulas adicionais para testar o crescimento dinˆamico e celulas esparsas 1 include stdioh 2 include stringh Para strcmp 3 include stdlibh Para malloc free 4 5 Copia das definicoes das estruturas e prototipos para este mainc para self containment no tex 6 Em um projeto C real estas estariam nos respectivos arquivos h e seriam i n c l u d a s 17 7 8 D e f i n i o da estrutura TCelula 9 typedef struct TCelula 10 struct TCelula direita 11 struct TCelula esquerda 12 struct TCelula abaixo 13 struct TCelula acima 14 int linha 15 int coluna 16 char letra 17 TCelula 18 19 D e f i n i o do TAD TCacaPalavras 20 typedef struct TCacaPalavras 21 TCelula cabecaLinhas 22 TCelula cabecaColunas 23 int numLinhas 24 int numColunas 25 TCacaPalavras 26 27 P r o t t i p o s das f u n e s i m p l e m e n t a e s completas seguiriam aqui se fosse um nico arquivo C 28 TCelula CriaNovaCelula int linha int coluna char letra 29 TCelula EncontraOuCriaCabeca TCelula listaCabecas int indice int numTotal int isLinha 30 TCacaPalavras TCacaPalavrasInicializa 31 int TCacaPalavrasInsereLetra TCacaPalavras cacaPalavras int linha int coluna char letra 32 TCelula TCacaPalavrasBuscaCelula TCacaPalavras cacaPalavras int linha int coluna 33 void TCacaPalavrasImprimeMatriz TCacaPalavras cacaPalavras 34 bool BuscaEmDirecaoRefatorada TCacaPalavras cacaPalavras TCelula celulainicial const char palavra int dr int dc 35 bool TCacaPalavrasBuscaPalavra TCacaPalavras cacaPalavras const char palavra 36 void TCacaPalavrasLibera TCacaPalavras cacaPalavras 37 38 I m p l e m e n t a e s das f u n e s repetidas aqui para self containment no tex 39 Em um projeto real estas estariam em TCacaPalavrasc 40 41 Implementacao de CriaNovaCelula 42 TCelula CriaNovaCelula int linha int coluna char letra 43 TCelula nova TCelula mallocsizeofTCelula 44 if nova NULL 45 fprintfstderr Errodealocacaodememoriaparacelula 46 return NULL 47 48 nova direita NULL 49 nova esquerda NULL 50 nova abaixo NULL 18 51 nova acima NULL 52 nova linha linha 53 nova coluna coluna 54 nova letra letra 55 return nova 56 57 58 Implementacao de EncontraOuCriaCabeca 59 TCelula EncontraOuCriaCabeca TCelula listaCabecas int indice int numTotal int isLinha 60 TCelula atual listaCabecas 61 TCelula anterior NULL 62 while atual NULL 63 int atualIndice isLinha atual linha atual coluna 64 if atualIndice indice return atual 65 if atualIndice indice break 66 anterior atual 67 atual atual direita 68 69 TCelula novaCabeca CriaNovaCelula isLinha indice 1 isLinha 1 indice 0 70 if novaCabeca NULL return NULL 71 novaCabeca linha isLinha indice 1 72 novaCabeca coluna isLinha 1 indice 73 if anterior NULL 74 novaCabeca direita listaCabecas 75 listaCabecas novaCabeca 76 else 77 novaCabeca direita atual 78 anterior direita novaCabeca 79 80 numTotal 81 return novaCabeca 82 83 84 Implementacao de TCacaPalavrasInicializa 85 TCacaPalavras TCacaPalavrasInicializa 86 TCacaPalavras cacaPalavras TCacaPalavras mallocsizeof TCacaPalavras 87 if cacaPalavras NULL 88 fprintfstderr Errodealocacaodememoriapara TCacaPalavras 89 return NULL 90 91 cacaPalavras cabecaLinhas NULL 92 cacaPalavras cabecaColunas NULL 93 cacaPalavras numLinhas 0 94 cacaPalavras numColunas 0 95 return cacaPalavras 96 97 98 Implementacao de TCacaPalavrasInsereLetra 19 99 int TCacaPalavrasInsereLetra TCacaPalavras cacaPalavras int linha int coluna char letra 100 if cacaPalavras NULL linha 0 coluna 0 101 fprintfstderr Parametrosinvalidospara TCacaPalavrasInsereLetra 102 return 0 103 104 TCelula cabecaLinha EncontraOuCriaCabeca cacaPalavras cabecaLinhas linha cacaPalavras numLinhas 1 105 if cabecaLinha NULL return 0 106 TCelula cabecaColuna EncontraOuCriaCabeca cacaPalavras cabecaColunas coluna cacaPalavras numColunas 0 107 if cabecaColuna NULL return 0 108 TCelula celulaLinhaAtual cabecaLinha direita 109 TCelula anteriorLinha cabecaLinha 110 while celulaLinhaAtual NULL celulaLinhaAtual coluna coluna 111 anteriorLinha celulaLinhaAtual 112 celulaLinhaAtual celulaLinhaAtual direita 113 114 TCelula celulaColunaAtual cabecaColuna abaixo 115 TCelula anteriorColuna cabecaColuna 116 while celulaColunaAtual NULL celulaColunaAtual linha linha 117 anteriorColuna celulaColunaAtual 118 celulaColunaAtual celulaColunaAtual abaixo 119 120 if celulaLinhaAtual NULL celulaLinhaAtual coluna coluna 121 celulaColunaAtual NULL celulaColunaAtual linha linha 122 celulaLinhaAtual celulaColunaAtual 123 celulaLinhaAtual letra letra 124 return 1 125 126 TCelula novaCelula CriaNovaCelula linha coluna letra 127 if novaCelula NULL return 0 128 novaCelula direita celulaLinhaAtual 129 novaCelula esquerda anteriorLinha 130 anteriorLinha direita novaCelula 131 if celulaLinhaAtual NULL celulaLinhaAtual esquerda novaCelula 132 novaCelula abaixo celulaColunaAtual 133 novaCelula acima anteriorColuna 134 anteriorColuna abaixo novaCelula 135 if celulaColunaAtual NULL celulaColunaAtual acima novaCelula 136 return 1 137 138 139 Implementacao de TCacaPalavrasBuscaCelula 140 TCelula TCacaPalavrasBuscaCelula TCacaPalavras cacaPalavras 20 int linha int coluna 141 if cacaPalavras NULL linha 0 coluna 0 return NULL 142 TCelula cabecaLinha cacaPalavras cabecaLinhas 143 while cabecaLinha NULL cabecaLinha linha linha 144 cabecaLinha cabecaLinha direita 145 146 if cabecaLinha NULL return NULL 147 TCelula atual cabecaLinha direita 148 while atual NULL atual coluna coluna 149 atual atual direita 150 151 if atual NULL atual coluna coluna return atual 152 return NULL 153 154 155 Implementacao de TCacaPalavrasImprimeMatriz 156 void TCacaPalavrasImprimeMatriz TCacaPalavras cacaPalavras 157 if cacaPalavras NULL cacaPalavras cabecaLinhas NULL 158 printfMatrizvaziaounaoinicializada 159 return 160 161 printf MatrizCacaPalavras 162 int maxLinha 1 163 int maxColuna 1 164 TCelula tempLinhaCabeca cacaPalavras cabecaLinhas 165 while tempLinhaCabeca NULL 166 iftempLinhaCabeca linha maxLinha maxLinha tempLinhaCabeca linha 167 TCelula tempCelula tempLinhaCabeca direita 168 whiletempCelula NULL 169 iftempCelula coluna maxColuna maxColuna tempCelula coluna 170 tempCelula tempCelula direita 171 172 tempLinhaCabeca tempLinhaCabeca direita 173 174 for int i 0 i maxLinha i 175 TCelula cabecaLinhaAtual cacaPalavras cabecaLinhas 176 while cabecaLinhaAtual NULL cabecaLinhaAtual linha i 177 cabecaLinhaAtual cabecaLinhaAtual direita 178 179 printfLinha2d i 180 if cabecaLinhaAtual NULL 181 for int j 0 j maxColuna j printf 182 else 183 TCelula atual cabecaLinhaAtual direita 184 for int j 0 j maxColuna j 21 185 if atual NULL atual coluna j 186 printfc atual letra 187 atual atual direita 188 else 189 printf 190 191 192 193 printf 194 195 printf 196 197 198 Implementacao de BuscaEmDirecaoRefatorada 199 bool BuscaEmDirecaoRefatorada TCacaPalavras cacaPalavras TCelula celulainicial const char palavra int dr int dc 200 if celulainicial NULL palavra NULL palavra 0 cacaPalavras NULL 201 return false 202 203 int len strlenpalavra 204 TCelula atual celulainicial 205 int k 0 206 for k 0 k len k 207 if atual NULL atual letra palavrak return false 208 if k len 1 return true 209 if dr 0 dc 1 atual atual direita 210 else if dr 0 dc 1 atual atual esquerda 211 else if dr 1 dc 0 atual atual abaixo 212 else if dr 1 dc 0 atual atual acima 213 else atual TCacaPalavrasBuscaCelula cacaPalavras atual linha dr atual coluna dc 214 215 return false 216 217 218 Implementacao de TCacaPalavrasBuscaPalavra 219 bool TCacaPalavrasBuscaPalavra TCacaPalavras cacaPalavras const char palavra 220 if cacaPalavras NULL palavra NULL palavra 0 return false 221 int len strlenpalavra 222 if len 0 return false 223 int dr 0 0 1 1 1 1 1 1 224 int dc 1 1 0 0 1 1 1 1 225 TCelula cabecaLinhaAtual cacaPalavras cabecaLinhas 226 while cabecaLinhaAtual NULL 227 TCelula celulaAtual cabecaLinhaAtual direita 228 while celulaAtual NULL 229 for int i 0 i 8 i 22 230 if BuscaEmDirecaoRefatorada cacaPalavras celulaAtual palavra dri dci 231 printfPalavra sencontradaapartirde ddnadirecaodrddcd 232 palavra celulaAtual linha celulaAtual coluna dri dci 233 return true 234 235 236 celulaAtual celulaAtual direita 237 238 cabecaLinhaAtual cabecaLinhaAtual direita 239 240 return false 241 242 243 Implementacao de TCacaPalavrasLibera 244 void TCacaPalavrasLibera TCacaPalavras cacaPalavras 245 if cacaPalavras NULL return 246 TCelula currentLinhaHead cacaPalavras cabecaLinhas 247 while currentLinhaHead NULL 248 TCelula currentDataCell currentLinhaHead direita 249 while currentDataCell NULL 250 TCelula nextDataCell currentDataCell direita 251 free currentDataCell 252 currentDataCell nextDataCell 253 254 TCelula nextLinhaHead currentLinhaHead direita 255 free currentLinhaHead 256 currentLinhaHead nextLinhaHead 257 258 TCelula currentColumnaHead cacaPalavras cabecaColunas 259 while currentColumnaHead NULL 260 TCelula nextColumnaHead currentColumnaHead direita 261 free currentColumnaHead 262 currentColumnaHead nextColumnaHead 263 264 freecacaPalavras 265 266 267 268 Funcao main do programa simula o comportamento do mainc 269 int main 270 TCacaPalavras meuCacaPalavras TCacaPalavrasInicializa 271 if meuCacaPalavras NULL 272 return 1 Erro na i n i c i a l i z a o 273 274 275 Inserindo algumas letras na matriz 276 printfInserindoletrasnamatriz 277 TCacaPalavrasInsereLetra meuCacaPalavras 0 0 A 278 TCacaPalavrasInsereLetra meuCacaPalavras 0 1 B 23 279 TCacaPalavrasInsereLetra meuCacaPalavras 0 2 C 280 TCacaPalavrasInsereLetra meuCacaPalavras 1 0 D 281 TCacaPalavrasInsereLetra meuCacaPalavras 1 1 E 282 TCacaPalavrasInsereLetra meuCacaPalavras 1 2 F 283 TCacaPalavrasInsereLetra meuCacaPalavras 2 0 G 284 TCacaPalavrasInsereLetra meuCacaPalavras 2 1 H 285 TCacaPalavrasInsereLetra meuCacaPalavras 2 2 I 286 TCacaPalavrasInsereLetra meuCacaPalavras 0 3 X C l u l a isolada na linha 0 287 TCacaPalavrasInsereLetra meuCacaPalavras 3 0 Y C l u l a isolada na coluna 0 288 289 Testando a t u a l i z a o 290 TCacaPalavrasInsereLetra meuCacaPalavras 0 0 Z Deve atualizar A para Z 291 292 TCacaPalavrasImprimeMatriz meuCacaPalavras 293 294 Testando a busca de palavras 295 printf TestesdeBuscadePalavras 296 297 if TCacaPalavrasBuscaPalavra meuCacaPalavras ZEF 298 printfBuscaporZEFhorizontal linha0SUCESSO 299 else 300 printfBuscaporZEFFALHA 301 302 303 if TCacaPalavrasBuscaPalavra meuCacaPalavras ZDG 304 printfBuscaporZDGvertical coluna0SUCESSO 305 else 306 printfBuscaporZDGFALHA 307 308 309 if TCacaPalavrasBuscaPalavra meuCacaPalavras ZEI 310 printfBuscaporZEIdiagonalprincipalSUCESSO 311 else 312 printfBuscaporZEIFALHA 313 314 315 if TCacaPalavrasBuscaPalavra meuCacaPalavras IHX Exemplo de palavra reversa XHI 316 printfBuscaporIHXdiagonalinversaSUCESSO De 22 para 00 317 else 318 printfBuscaporIHXFALHA 319 320 321 if TCacaPalavrasBuscaPalavra meuCacaPalavras JATO 322 printfBuscaporJATO SUCESSO n o deveria 24 encontrar 323 else 324 printfBuscaporJATO FALHAcorreto 325 326 327 Libera a m e m r i a 328 printf Liberandomemoria 329 TCacaPalavrasLibera meuCacaPalavras 330 printfMemorialiberada 331 332 return 0 333 Listing 12 Trecho de codigo do mainc para Insercao Basica 5 Conclusao O desenvolvimento deste Trabalho Pratico 2 proporcionou uma compreensao aprofun dada dos conceitos de listas duplamente encadeadas e sua aplicacao na representacao de estruturas de dados mais complexas como as matrizes esparsas A modelagem da matriz atraves de celulas que pertencem simultaneamente a duas listas linha e coluna revelou se uma abordagem flexıvel para lidar com tamanhos variaveis e desconhecidos utilizando eficientemente a alocacao dinˆamica de memoria A principal dificuldade encontrada na implementacao residiu na logica de conexao e desconexao das celulas especialmente na funcao TCacaPalavras InsereLetra que exigiu atencao cuidadosa para manter a integridade das duas listas simultaneamente garantindo a ordenacao e evitando duplicatas A implementacao da busca de palavras em todas as 8 direcoes tambem representou um desafio exigindo uma funcao auxiliar BuscaEmDirecaoRefatorada para navegar pelas celulas utilizando tanto os ponteiros diretos quanto a busca por coordenadas para os movimentos diagonais Em termos de aprendizado o trabalho reforcou a importˆancia da modularidade e do bom design de funcoes para gerenciar a complexidade de sistemas maiores A pratica com alocacao dinˆamica e a necessidade de gerenciar explicitamente a memoria foram exercıcios valiosos para evitar vazamentos e erros de acesso A analise de complexidade tambem foi fundamental para entender o desempenho das operacoes em diferentes cenarios Apesar dos desafios o resultado final e um TAD TCacaPalavras funcional que pode ser expandido para incluir mais funcionalidades como remocao de letras ou palavras ou ate mesmo interfaces de usuario mais complexas Este projeto serviu como uma excelente oportunidade para solidificar os conhecimentos adquiridos em Algoritmos e Estrutura de Dados 6 Bibliografia Referˆencias 1 Universidade Federal de Ouro Preto Departamento de Computacao e Sistemas Tra balho Pratico 2 Listas Encadeadas Material da disciplina Algoritmos e Estrutura de Dados I CSI 488 2025 25 2 Ziviani Nıvio Roteiro para a implementacao e documentacao de um trabalho pratico Disponıvel em httpshomepagesdccufmgbrniviocursosaed2roteiro Acesso em 09 de Julho de 2025 26