-
Notifications
You must be signed in to change notification settings - Fork 254
/
unordered_linked_list.go
155 lines (122 loc) · 3.58 KB
/
unordered_linked_list.go
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
/*
* Listas - Lista linear não ordenada
*
* Implementação da lista sequencial cujos elementos não estão ordenados
*
* link Go PlayGround: https://play.golang.org/p/3uFOquVlTD8
*/
package main
import "fmt"
var maxSize = 50
// Estrura que será guardada em cada posição da lista
type Registro struct {
valor int
// Outros campos podem ser adicionados aqui
}
// Estrutura que guarda um arranjo de Registro, e o número de elementos no arranjo
type Lista struct {
arranjoRegistros []Registro
numeroElementos int
}
// Cria uma nova lista
func criarLista() Lista {
lista := Lista{
arranjoRegistros: make([]Registro, maxSize),
numeroElementos: 0,
}
return lista
}
// reseta o contador de elementos da lista
func inicializar(lista *Lista) {
lista.numeroElementos = 0
}
// Recupera a quantidade de elementos da lista
func tamanho(lista *Lista) int {
return lista.numeroElementos
}
// Imprime valores dos elementos na lista
func imprimir(lista *Lista) {
for i := 0; i < lista.numeroElementos; i++ {
fmt.Printf("%v ", lista.arranjoRegistros[i].valor)
}
fmt.Println()
}
// Realiza busca sequencial na lista, percorrendo item por item
func buscaSequencial(lista *Lista, valor int) int {
i := 0
for i < lista.numeroElementos {
if valor == lista.arranjoRegistros[i].valor {
return i
}
i++
}
return -1
}
// Realiza busca sentinela na lista, percorrendo item por item
func buscaSentinela(lista *Lista, valor int) int {
i := 0
lista.arranjoRegistros[lista.numeroElementos].valor = valor
for valor != lista.arranjoRegistros[i].valor {
i++
}
if i == lista.numeroElementos {
return -1
}
return i
}
// Insere elementos na lista, em uma posição específica, e move todos os outros elementos para a direita
func insereElemento(lista *Lista, registro Registro, posicao int) bool {
if (lista.numeroElementos == maxSize) || posicao < 0 || posicao > lista.numeroElementos {
return false
}
for j := lista.numeroElementos; j > posicao; j-- {
lista.arranjoRegistros[j] = lista.arranjoRegistros[j-1]
}
lista.arranjoRegistros[posicao] = registro
lista.numeroElementos++
return true
}
// Exclui um elemento da lista
func excluirElemento(lista *Lista, valor int) bool {
posicao := buscaSequencial(lista, valor)
if posicao == -1 {
return false
}
for i := posicao; i < lista.numeroElementos-1; i++ {
lista.arranjoRegistros[i] = lista.arranjoRegistros[i+1]
}
lista.numeroElementos--
return true
}
func main() {
lista := criarLista()
inicializar(&lista)
fmt.Println("Inserindo valores na lista...")
insereElemento(&lista, Registro{valor: 20}, 0)
insereElemento(&lista, Registro{valor: 10}, 0)
insereElemento(&lista, Registro{valor: 70}, 0)
insereElemento(&lista, Registro{valor: 30}, 0)
insereElemento(&lista, Registro{valor: 60}, 0)
insereElemento(&lista, Registro{valor: 90}, 0)
insereElemento(&lista, Registro{valor: 80}, 0)
insereElemento(&lista, Registro{valor: 15}, 0)
insereElemento(&lista, Registro{valor: 1}, 0)
fmt.Println()
fmt.Println("Imprimindo lista...")
imprimir(&lista)
fmt.Println("Tamanho da lista:", tamanho(&lista))
fmt.Println()
fmt.Println("Excluindo elemento 80 da lista...")
excluirElemento(&lista, 80)
fmt.Println()
fmt.Println("Imprimindo lista...")
imprimir(&lista)
fmt.Println("Tamanho da lista:", tamanho(&lista))
fmt.Println()
fmt.Println("Buscando valores na lista:")
fmt.Println()
fmt.Println("Buscando posição do numero 15:")
fmt.Printf("Posição do número 15: %v \n\n", buscaSequencial(&lista, 15))
fmt.Println("Buscando posição do valor 100:")
fmt.Printf("Posição do número 100: %v \n\n", buscaSequencial(&lista, 100))
}