Pessoal de ADS. Por esses dias estarei colocando no blog algumas no\u00e7\u00f5es de programa\u00e7\u00e3o, como lista encadeada, aloca\u00e7\u00e3o din\u00e2mica, verifica\u00e7\u00e3o de c\u00f3digo com GDB, entre outras\u2026 Isso porque estou notando uma queda de rendimento de voc\u00eas em sala principalmente quando envolve programa\u00e7\u00e3o. Vamos l\u00e1!<\/p>\n\n\n\n
Normalmente para realizarmos a representa\u00e7\u00e3o de um grupo de dados, utilizamos a forma mais simples para tal que \u00e9 a dada atrav\u00e9s do uso de um vetor. Ao declararmos um vetor estamos reservando um espa\u00e7o de mem\u00f3ria unido e em sequ\u00eancia, para armazenarmos seus elementos. Em um vetor, acessamos seus elementos indexando o ponteiro para seu primeiro elemento.<\/p>\n\n\n\n
Ao realizarmos a declara\u00e7\u00e3o acima, estamos a partir do endere\u00e7o de mem\u00f3ria FF04, inclusive com este, alocando um total de 10 espa\u00e7os em mem\u00f3ria para que dados do tipo inteiro possam ser gravados nestes. Desta forma, vetor \u00e9 o endere\u00e7o da mem\u00f3ria onde o primeiro elemento do vetor est\u00e1 armazenado. De forma an\u00e1loga poder\u00edamos escrever a mesma situa\u00e7\u00e3o como &vetor[0]<\/strong>. Apesar de extremamente \u00fatil em v\u00e1rias situa\u00e7\u00f5es, o uso de vetores apresenta como grande desvantagem o fato deste n\u00e3o ser uma estrutura flex\u00edvel, haja vista que necessitamos dimension\u00e1-lo com um n\u00famero m\u00e1ximo de elementos. Seu redimensionamento em tempo de execu\u00e7\u00e3o n\u00e3o \u00e9 simples e pode requer um recurso computacional mais elevado. Com isso, ao utilizarmos um vetor, corremos o risco da necessidade de cresce-lo al\u00e9m do previsto durante a execu\u00e7\u00e3o do programa ou ent\u00e3o termos super dimensionado o problema e ficarmos com espa\u00e7o alocado para o mesmo sem que estes sejam utilizados. Ao fazermos uso portanto de estruturas din\u00e2micas, como estas alocam seus elementos usando aloca\u00e7\u00e3o din\u00e2mica de mem\u00f3ria, temos esta situa\u00e7\u00e3o resolvida.<\/p>\n\n\n\n
Listas Encadeadas<\/strong><\/h3>\n\n\n\n
Listas encadeadas s\u00e3o estruturas flex\u00edveis onde a cada novo elemento inserido na estrutura \u00e9 alocado um espa\u00e7o de mem\u00f3ria para que seja processado seu armazenamento. Listas encadeadas, devido ao uso do mecanismo de aloca\u00e7\u00e3o din\u00e2mica, ter\u00e3o sempre o espa\u00e7o de mem\u00f3ria utilizado variando de acordo com seu n\u00famero de elementos. Uma lista encadeada \u00e9 uma cole\u00e7\u00e3o de n\u00f3s, que armazenam dados, e de liga\u00e7\u00f5es com outros n\u00f3s. Os n\u00f3s podem estar localizados agora em qualquer lugar na mem\u00f3ria, e a passagem de um n\u00f3 para o outro se dar\u00e1 atrav\u00e9s do armazenamento dos endere\u00e7os de outros n\u00f3s. Na lista encadeada cada n\u00f3 conter\u00e1 um ou mais campos respons\u00e1veis pelo armazenamento das informa\u00e7\u00f5es, al\u00e9m de um campo que \u00e9 um ponteiro para uma pr\u00f3xima estrutura do mesmo tipo.<\/p>\n\n\n\n
De forma a fornecer um facilitador na compreens\u00e3o das listas, trabalharemos com o conceito de lista com cabe\u00e7a, ou seja, teremos sempre o conte\u00fado do primeiro n\u00f3 irrelevante. Este servir\u00e1 apenas para marcar o in\u00edcio da lista, n\u00e3o se alterar\u00e1, e quando estiver apontando para null, indicar\u00e1 que a lista est\u00e1 vazia.<\/p>\n\n\n\n<\/figure>\n\n\n\n
Fun\u00e7\u00e3o para inicializa\u00e7\u00e3o<\/strong><\/h3>\n\n\n\n
A fun\u00e7\u00e3o para inicializa\u00e7\u00e3o de uma lista deve criar o n\u00f3 inicial da lista mas tamb\u00e9m, no momento de sua cria\u00e7\u00e3o verificar se h\u00e1 espa\u00e7o livre na mem\u00f3ria para a efetiva\u00e7\u00e3o do processo. Iniciaremos neste momento atrav\u00e9s dos exemplos dados a constru\u00e7\u00e3o de um primeiro programa modelo, para tratamento de listas, o qual far\u00e1 uso de vari\u00e1veis globais de forma a eliminar a necessidade no momento de passagem de par\u00e2metros \u00e0s fun\u00e7\u00f5es. Um outro exemplo ser\u00e1 dado no decorrer de nossas aulas utilizando estes recursos.<\/p>\n\n\n\n
\nstruct noh {\n int mat;\n char *nome;\n char sexo[1];\n struct noh *prox;\n};\ntypedef struct noh lista;\nchar onome[256];\nlista *inicio=NULL;\nlista *atual=NULL;\nlista *anterior=NULL;\n\nvoid inicializa(){\n inicio =(lista*) malloc (sizeof (lista));\n if (!inicio){\n printf(\u201c\\nNao existe espaco na memoria!\u201d);\n exit(1);\n }\n inicio->prox = NULL;\n}<\/code><\/pre>\n\n\n\n
Fun\u00e7\u00e3o para inser\u00e7\u00e3o<\/strong><\/h3>\n\n\n\n
A partir do momento que temos nossa lista inicializada, podemos proceder com a inser\u00e7\u00e3o de novos elementos nesta. Lembrando que para cada novo elemento adicionado estaremos alocando um novo espa\u00e7o de mem\u00f3ria para este. Podemos realizar a inser\u00e7\u00e3o em qualquer lugar da lista, entretanto, a maneira mais simples de execu\u00e7\u00e3o desta tarefa \u00e9 dada com a inser\u00e7\u00e3o do novo elemento no in\u00edcio da lista. Sendo assim o novo elemento entrar\u00e1 logo ap\u00f3s nosso marcador de in\u00edcio da lista. O mais importante aqui \u00e9 realizar sempre sua programa\u00e7\u00e3o de maneira defensiva e com o m\u00e1ximo de cuidado nos detalhes de modo a n\u00e3o cometer falhas de direcionamento de pr\u00f3ximos n\u00f3s. Vejamos como ficaria nossa fun\u00e7\u00e3o de inser\u00e7\u00e3o.<\/p>\n\n\n\n<\/figure>\n\n\n\n
void insere(){\n lista *novo=NULL;\n novo = (lista*) malloc (sizeof (lista));\n if (!novo){\n printf(\"\\nNao existe espaco na memoria!\");\n exit(1);\n }\n printf(\"\\nDigite a matricula: \");\n scanf(\"%d\",&novo->mat);\n printf(\"\\nDigite o nome: \");\n scanf(\"%s\",onome);\n novo->nome = (char*) malloc (strlen(onome)+1);\n strcpy(novo->nome,onome);\n fflush(stdin);\n printf(\"\\nDigite o sexo: \");\n scanf(\"%s\",novo->sexo);\n fflush(stdin);\n if (inicio->prox == NULL){\n inicio->prox = novo;\n novo->prox = NULL;\n }else{\n novo->prox = inicio->prox;\n inicio->prox = novo;\n }\n}<\/code><\/pre>\n\n\n\n
Fun\u00e7\u00e3o para impress\u00e3o<\/strong><\/h3>\n\n\n\n
Nossa fun\u00e7\u00e3o de impress\u00e3o ter\u00e1 uma tarefa bem simples a ser realizada. Seu papel ser\u00e1 de a partir do marcador de in\u00edcio da lista, percorrer toda esta, e imprimir as informa\u00e7\u00f5es gravadas em seus campos. Antes de ler a solu\u00e7\u00e3o proposta abaixo para nosso estudo, tente criar a fun\u00e7\u00e3o de impress\u00e3o como um primeiro exerc\u00edcio de nossa disciplina. Dica: N\u00e3o se esque\u00e7a de verificar antes de tudo se alista n\u00e3o est\u00e1 vazia. Ao realizar a impress\u00e3o a mesma deve ocorrer, pela l\u00f3gica proposta acima, na ordem inversa a da entrada dos dados.<\/p>\n\n\n\n
void imprime(){\n if (inicio->prox==NULL)\n printf(\"\\nFila vazia!\\n\");\n else{\n atual=inicio;\n do{\n atual=atual->prox;\n printf(\"\\n\\nMatricula: %d\",atual->mat);\n printf(\"\\nNome: %s\",atual->nome);\n printf(\"\\nSexo: %s\",atual->sexo);\n } while (atual->prox!=NULL);\n }\n}<\/code><\/pre>\n\n\n\n
Fun\u00e7\u00e3o para busca sequencial<\/strong><\/h3>\n\n\n\n
Para verificarmos se um determinado elemento encontra-se presente em nossa lista, utilizaremos aqui de uma busca sequencial. Em nosso exemplo como citado anteriormente estamos trabalhando neste primeiro momento com vari\u00e1veis globais e com as fun\u00e7\u00f5es sem passagem de par\u00e2metros. Entretanto, adiante estaremos reescrevendo a mesma recebendo como par\u00e2metros um ponteiro para lista e uma informa\u00e7\u00e3o que necessitamos pesquisar. Vamos ao nosso exemplo:<\/p>\n\n\n\n
void busca(){\n int matbusca,encontrou=0;\n printf(\"\\n\\nDigite a matricula para busca: \");\n scanf(\"%d\",&matbusca);\n if (inicio->prox==NULL)\n printf(\"\\nFila vazia! Busca nao pode ser processada!\\n\");\n else{\n for (atual=inicio->prox; atual!=NULL; atual=atual->prox){\n if (matbusca==atual->mat){\n printf(\"\\n\\nMatricula: %d\",atual->mat);\n printf(\"\\nNome: %s\",atual->nome);\n printf(\"\\nSexo: %s\",atual->sexo);\n encontrou=1;\n }\n if (atual->prox==NULL && encontrou==0)\n printf(\"\\nRegistro nao encontrado!\\n\");\n }\n }\n}<\/code><\/pre>\n\n\n\n
Fun\u00e7\u00e3o para excluir um elemento da lista<\/strong><\/h3>\n\n\n\n
Implementaremos agora a fun\u00e7\u00e3o respons\u00e1vel por localizar e excluir um elemento da lista. Novamente \u00e9 importante estar atento a detalhes como: \u2013 lista est\u00e1 vazia? \u2013 o elemento a ser exclu\u00eddo n\u00e3o \u00e9 o primeiro da lista? A fun\u00e7\u00e3o para remover um elemento da lista \u00e9 um pouco mais complexa j\u00e1 que devemos guardar o elemento anterior ao procurado e fazer com que este aponte ap\u00f3s a exclus\u00e3o do elemento identificado para o posterior a ele, de forma a manter de maneira correta o encadeamento de nossa lista. Vamos ao nosso c\u00f3digo!<\/p>\n\n\n\n
void exclui(){\n int matbusca,encontrou=0;\n printf(\"\\n\\nDigite a matricula para exclusao: \");\n scanf(\"%d\",&matbusca);\n if (inicio->prox==NULL)\n printf(\"\\nFila vazia! Busca para exclusao nao pode ser processada!\\n\");\n else{\n anterior = inicio;\n for (atual=inicio->prox; atual!=NULL; atual=atual->prox){\n if (matbusca==atual->mat){\n anterior->prox = atual->prox;\n free(atual);\n encontrou=1;\n }\n if (encontrou == 1)\n break;\n anterior=atual;\n if (atual->prox==NULL && encontrou==0)\n printf(\"\\nRegistro para exclusao nao encontrado!\\n\");\n }\n }\n}<\/code><\/pre>\n\n\n\n
Observa\u00e7\u00f5es finais sobre listas encadeadas<\/strong><\/h3>\n\n\n\n
Tivemos a oportunidade de iniciar nosso estudo sobre listas atrav\u00e9s das listas de encadeamento simples. Notamos que pelo fato de n\u00e3o possuirmos o apontador para elementos anteriores, nosso caminhar pela lista fica prejudicado e necessitamos de solu\u00e7\u00f5es nada elegantes para a resolu\u00e7\u00e3o de problemas como uma exclus\u00e3o de um elemento no meio da lista. Partiremos no pr\u00f3ximo estudo para o tratamento das listas duplamente encadeadas, o que nos permitir\u00e1 controlar de maneira eficiente este caminhar, nos inserindo nos t\u00f3picos de filas e pilhas. Quando fazemos uso de linguagens de programa\u00e7\u00e3o que possuem coletores de lixo de mem\u00f3ria, n\u00e3o nos \u00e9 necess\u00e1rio desalocar o espa\u00e7o de mem\u00f3ria utilizado. Entretanto a linguagem C n\u00e3o possui este mecanismo e liberar a mem\u00f3ria utilizada \u00e9 algo essencial. Fazemos isso atrav\u00e9s do comando free().<\/p>\n","protected":false},"excerpt":{"rendered":"
Pessoal de ADS. Por esses dias estarei colocando no blog algumas no\u00e7\u00f5es de programa\u00e7\u00e3o, como lista encadeada, aloca\u00e7\u00e3o din\u00e2mica, verifica\u00e7\u00e3o de c\u00f3digo com GDB, entre outras\u2026 Isso porque estou notando uma queda de rendimento de voc\u00eas em sala principalmente quando envolve programa\u00e7\u00e3o. Vamos l\u00e1! Normalmente para realizarmos a representa\u00e7\u00e3o de um grupo de dados, utilizamos […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[18,30,8,31,22],"class_list":["post-250","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-busca","tag-c","tag-education","tag-lista","tag-software"],"_links":{"self":[{"href":"https:\/\/gpads.recife.ifpe.edu.br\/alsm\/csin\/index.php\/wp-json\/wp\/v2\/posts\/250","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/gpads.recife.ifpe.edu.br\/alsm\/csin\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/gpads.recife.ifpe.edu.br\/alsm\/csin\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/gpads.recife.ifpe.edu.br\/alsm\/csin\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/gpads.recife.ifpe.edu.br\/alsm\/csin\/index.php\/wp-json\/wp\/v2\/comments?post=250"}],"version-history":[{"count":3,"href":"https:\/\/gpads.recife.ifpe.edu.br\/alsm\/csin\/index.php\/wp-json\/wp\/v2\/posts\/250\/revisions"}],"predecessor-version":[{"id":257,"href":"https:\/\/gpads.recife.ifpe.edu.br\/alsm\/csin\/index.php\/wp-json\/wp\/v2\/posts\/250\/revisions\/257"}],"wp:attachment":[{"href":"https:\/\/gpads.recife.ifpe.edu.br\/alsm\/csin\/index.php\/wp-json\/wp\/v2\/media?parent=250"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/gpads.recife.ifpe.edu.br\/alsm\/csin\/index.php\/wp-json\/wp\/v2\/categories?post=250"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/gpads.recife.ifpe.edu.br\/alsm\/csin\/index.php\/wp-json\/wp\/v2\/tags?post=250"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
![\"\"](\"https:\/\/gpads.recife.ifpe.edu.br\/alsm\/csin\/wp-content\/uploads\/2023\/04\/imagem1.jpg\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/gpads.recife.ifpe.edu.br\/alsm\/csin\/wp-content\/uploads\/2023\/04\/fig2.jpg\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/gpads.recife.ifpe.edu.br\/alsm\/csin\/wp-content\/uploads\/2023\/04\/fig3.jpg\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/gpads.recife.ifpe.edu.br\/alsm\/csin\/wp-content\/uploads\/2023\/04\/fig41.jpg\")
<\/figure>\n\n\n\n