-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathindex.html
224 lines (194 loc) · 11 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Listas Encadeadas em C</title>
<link rel="stylesheet" type="text/css" href="/Site Contéudo/style.css" media="screen" />
</head>
<body>
<header id="cabecalho">
<p><a href="https://github.com/ron010-1" style="color: white">Github</a></p>
<p><a href="https://www.linkedin.com/in/riquelme-oliveira/" style="color: white">Linkedin</a></p>
<p><a href=""style="color: white">Portfólio</a></p>
</header>
<h1 class="LE">Listas Encadeadas</h1>
<div id="conceito">
<p>Uma Lista Encadeada é um sequência de objetos, lembrando, todos do mesmo tipo, na memória.
Cada objeto da sequência é armazenado em uma célula da lista: o primeiro elemento na primeira célula, o
segundo na segunda e continua.
Veja um exemplo na imagem abaixo:
</p>
<img src="/Site Contéudo/imagens/img1.png" alt="Abstração 1">
<p>Veja que cada célula guarda consigo um valor e ela aponta para a seguinte! Guarde bem esse conceito inicial
pois é a estrutura básica de uma lista encadeada.
ESTRUTURA: Guarda o valor do objeto e "aponta" para a próxima célula.
</p>
<p>A explicação irá conter tópicos com exemplos práticos e códigos, além de um projeto feito por mim que foi
produzido com o andamento de cada tópico.</p>
</div>
<div id="sumario">
<strong><p id="sumario">Sumário</p></strong>
<ul>
<li><a href="#estrutura">Estrutura da Lista Encadeada</a></li>
<li><a href="#endereco">Endereço de uma LE(Lista Encadeada)</a></li>
<li><a href="#busca">Busca em uma Lista Encadeada</a></li>
<li><a href="#cabeca">Cabeça da Lista</a></li>
<li><a href="#insere">Inserção em uma Lista Encadeada</a></li>
<li><a href="#remove">Remoção em uma Lista Encadeada</a></li>
<li><a href="#lista">Lista de Exercícios Completa</a></li>
<li><a href="#referencias">Referências</a></li>
<li><a href="https://github.com/ron010-1/edListas">Repositório GitHub</a></li>
</ul>
</div>
<div id="estrutura">
<h2>Estrutura da Lista Encadeada</h2>
<p>Apenas recapitulando a parte inicial, Lista Encadeadas é uma sequência de células; cada célula contém um
objeto(Lembrando que todos do mesmo tipo)
e o endereço da célula seguinte. Então, abaixo veja o código da declaração da Estrutura da Lista.
</p>
<div class="code1">
<pre>
<code>
struct TipoLista {
int valor;//Ou seja, o contéudo da célula, o seu valor.
struct TipoLista *proximo;//"Aponta", ponteiro.
};
</code>
</pre>
</div>
<p>Explicação do Código: Registramos uma nova estrutura, ou se desejar, Declaramos uma nova Estrutura, com o valor da célula e a seta que
aponta pro próximo termo que é um Ponteiro.</p>
<p><br>Veja novamente na imagem abaixo que a célula 1 está apontando para a célula 2 e assim sucessivamente.</p>
<img src="/Site Contéudo/imagens/img1.png" alt="Abstração 1">
<p><br><br>É conveniente tratar as células da lista como um novo tipo-de-dados (typedef):</p>
<pre><code>typedef struct lista celula; //Celula</code></pre>
<p><br>Vamos um pouco mais longe, digamos então que declararemos uma célula e um ponteiro para a célula.</p>
<pre><code>
celula c;//Célula c
celula *p;//Ponteiro p
</code></pre>
<p><br>Ok, declaramos as variáveis, se c é uma célula então c.valor é o contéudo(a variável valor da nossa estrutura), e c.proximo é o endereço de memória da próxima célula.
Se p é um ponteiro, então, p->valor é o contéudo da célula e p->proximo aponta pra próxima célula, E quando chegar na última célula ela irá apontar pra NULL,
pois não há nada. Então, a última célula é se e somente se p->proximo == NULL.</p>
<img src="/Site Contéudo/imagens/img2.png" style="margin-top: 20px; margin-bottom: 50px;" alt="Abstração 2">
</div>
<div id="endereco">
<h2>Endereço de uma Lista Encadeada</h2>
<p>O endereço de uma lista encadeada é o endereço de sua primeira célula. <strong>Considere que le é uma lista encadeada.</strong>
A lista está vazia se e somente le == NULL, isso quer dizer, a lista não possui células.</p>
<p>OBSERVAÇÃO: Listas são tendeciosas à funções e à procedimentos recursivos, geralmente, os algoritmos de lista encadeada ficam mais simples, otimizados com
chamadas recursivas, ademais, é fácil manipular listas recursivamente e você verá ao longo dos problemas e exemplos práticos.</p>
<pre><code>
//A seguinte função recursiva imrime o contéudo de uma lista encadeada le:
void imprime(TipoLista *le){
if(le != NULL){
printf("%d\n", le->conteudo);
imprime(le->proximo);
}
}
//Aqui a função Iterativa:
void imprime(TipoLista *le){
celula *p;
for(p=le; p!=NULL; p= p->proximo){
printf("%d\n", p->conteudo);
}
}
</code></pre>
</div>
<div id="busca">
<h2>Busca em uma Lista Encadeada</h2>
<p>A ideia principal desse tópico é a busca em uma Lista Encadeada, ou seja, a busca de um elemento x na minha Lista e saber se ele pertence ou não a ela.</p>
<pre><code>
//Função que retorna se um valor está na lista ou não.
//Se sim retorna o numero(tamanho) da célula, Se não retorna 0, ou seja, o valor não foi encontrado.
int buscaElemento(int num, struct TipoLista *p){
int contador=0;
while(p->proximo != NULL && p->valor != num){
p = p->proximo;
contador++;
}
if(p->valor == num){
return contador;
}else{
return 0; //False, nao encontrou o valor.
}
}
</code></pre>
<p>Iniciamos o contador com 0 para que a cada laço do loop seja iterado +1 no seu valor, pois assim retorna em qual célula o elemento estará caso ele estiver na lista. O laço WHILE continua até que o ponteiro não aponte para uma célula vazia e que o valor da célula seja diferente do valor que queremos achar.</p>
</div>
<div id="cabeca">
<h2>Cabeça da Lista - HEAD CELL</h2>
<p>Convém tratar a primeira célula de uma lista encadeada como um mero "marcador de início" e ignorar o contéudo da célula. A primeira célula é a cabeça.<br><mark>head cell = dunny cell.</mark></p>
<p>Uma Lista Encadeada está vazia se e somente se <mark>le->proximo == NULL</mark>. Para criar uma Lista Encadeada vazia com cabeça, basta dizer:</p>
<pre><code>
TipoLista *le;
le = malloc(sizeof(lista));
le->proximo = NULL;
</code></pre>
<p>A função malloc aloca dinamicamente memória para o Novo Nó de acordo com o sizeof da Estrutura.</p>
<p>Constantemente a head da lista é alterada, no exemplo que produzi a cada criação de um nó a cabeça muda, ainda que a lista não seja uma estrutura LIFO(last-in first-out) mas a cabeça indica o último que entrou.</p>
<pre><code>
for(i=1; i<=6; i++){
struct TipoLista *NovoNo = malloc(sizeof(lista));
NovoNo->valor = i*10;
NovoNo->proximo = le->proximo;//Insere o nó no início da lista.
le->proximo = NovoNo;//Atualiza a HEAD da lista, antes era NULL e agora é o NovoNo.
}
</code></pre>
</div>
<div id="insere">
<h2>Inserção em uma Lista Encadeada</h2>
<p>Suponha que quero inserir a nova célula entre a posição apontada por p e a posição seguinte. Considere o problema de inserir uma nova célula em uma Lista Encadeada. Só faz sentido se P é diferente de NULL.</p>
<p>Em tese, a inserção segue a mesma estrutura de código da mudança de cabeça da lista e adição de elementos.</p>
<pre><code>
//Função que insere uma nova célula na LE.
void insere(int x, lista *p){
lista *nova;
nova = malloc(sizeof(lista));
nova->valor = x;
nova->proximo = p->proximo;
p->proximo = nova;
}
</code></pre>
<p>No caso acima, inserimos a nova célula no início da Lista, mas se o p->prox==NULL então inserimos a nova célula no fim da lista.</p>
<p><mark>Então, temos duas opções, Insere na cabeça da Lista ou insere no final da Lista.</mark></p>
</div>
<div id="remove">
<h2>Remoção em uma Lista Encadeada</h2>
<p>Considere o problema de remover uma certa célula de uma Lista Encadeada. Como especificar a célula em questão? A ideia mais óbvia é apontar para a célula que quero remover. Mas é fácil perceber que essa ideia não é boa, é melhor apontar para a célula anterior à que remover.
Veja que por esse método não é possível remover a primeira célula, ou se p == NULL ou p->proximo==NULL.
</p>
<pre><code>
//Esta função recebe o endereço p de uma célula de uma LE e remove da lista a p->prox.
void remove(celula *p){
celula *lixo;
lixo = p->proximo;
p->proximo = lixo->proximo;
free(lixo);
}</code></pre>
<p>A função <mark>free</mark> desaloca o espaço de memória daquela variável, no caso em que estamos trabalhando é a célula da Lista.</p>
<hr>
</div>
<div id="atividades">
<hr>
<p>No link abaixo temos a lista de exercício disponibilizada no docs dividido por cada tópico que foi exposto aqui.</p>
<p><a href="https://docs.google.com/document/d/1C8IEz8sJBV0UbL93bA7cG0gLrMuewV_VZPnc8ozaiuQ/edit?usp=sharing"> Lista de Exercícios: IME</a></p>
<hr>
</div>
<div id="referencias">
<h2>Referências</h2>
<p>Instituto Militar de Engenharia(IME), estudo: <a href="https://www.ime.usp.br/~pf/algoritmos/aulas/lista.html">Listas Encadeadas</a></p>
<p>Canal do Youtube: <a href="https://www.youtube.com/channel/UCyw2sRlaDSYLiM07oZfL7BQ">de Aluno para Aluno</a></p>
<p>Professor André Lira, do Instituto Federal da Paraíba da cadeira de Estrutura de Dados em C</p>
<p>Wikipedia <a href="https://en.wikipedia.org/wiki/Linked_list">Listas Encadeadas</a></p>
<hr>
</div>
<footer>
<hr>
<p>Atualizado em 03/04/2024.</p>
<p>Oliveira, Riquelme.</p>
</footer>
<script src="index.js"></script>
</body>
</html>