Algorithmes et structures de données en Go : guide pour débutants

Introduction aux algorithmes et structures de données en Go

Go (Golang) est un langage de programmation compilé moderne, développé chez Google. Il combine les performances du C++ avec la simplicité de Python, ce qui en fait un choix idéal pour apprendre les algorithmes et les structures de données. Dans cet article, nous allons explorer les concepts fondamentaux qui vous aideront à commencer à écrire du code efficace en Go.

Comprendre les structures de données et les algorithmes est une compétence clé pour tout développeur. Ils permettent d'organiser efficacement les données et de résoudre les problèmes de manière optimale. Go fournit des types intégrés puissants, comme les slices et les map, mais la connaissance des structures de base vous aidera à créer des solutions plus complexes.

Structures de données principales en Go

Tableaux et slices (Arrays and Slices)

En Go, les tableaux ont une longueur fixe, tandis que les slices sont dynamiques. Les slices sont un outil plus flexible, utilisé le plus souvent.

package main

import "fmt"

func main() {    // Tableau de longueur fixe    var arr [5]int = [5]int{1, 2, 3, 4, 5}    fmt.Println("Tableau :", arr)

    // Slice — tableau dynamique    slice := []int{10, 20, 30, 40, 50}    fmt.Println("Slice :", slice)

    // Ajout d'un élément au slice    slice = append(slice, 60)    fmt.Println("Slice après append :", slice)

    // Slice à partir d'une partie du tableau    subSlice := arr[1:4]    fmt.Println("Sous-slice :", subSlice)}

Les slices en Go sont une référence au tableau sous-jacent. Ils contiennent un pointeur vers le premier élément, la longueur et la capacité. Cela les rend très efficaces pour travailler avec des séquences de données.

Pile (Stack) en Go

La pile est une structure de données fonctionnant selon le principe LIFO (Last In, First Out). En Go, une pile se réalise facilement à l'aide d'un slice.

package main

import (    "fmt"    "errors")

type Stack []int

func (s *Stack) Push(v int) {    *s = append(*s, v)}

func (s *Stack) Pop() (int, error) {    if len(*s) == 0 {        return 0, errors.New("la pile est vide")    }    index := len(*s) - 1    element := (*s)[index]    *s = (*s)[:index]    return element, nil}

func main() {    var stack Stack        stack.Push(1)    stack.Push(2)    stack.Push(3)        for len(stack) > 0 {        val, err := stack.Pop()        if err == nil {            fmt.Println("Extrait :", val)        }    }}

Les piles sont utilisées dans les algorithmes de parcours d'arbres, la vérification des parenthèses, l'annulation d'actions (undo) et l'analyse d'expressions.

File d'attente (Queue) en Go

La file d'attente fonctionne selon le principe FIFO (First In, First Out). En Go, on peut la réaliser à l'aide d'un slice ou d'une liste doublement chaînée.

package main

import "fmt"

type Queue []int

func (q *Queue) Enqueue(v int) {    *q = append(*q, v)}

func (q *Queue) Dequeue() (int, bool) {    if len(*q) == 0 {        return 0, false    }    element := (*q)[0]    *q = (*q)[1:]    return element, true}

func main() {    queue := Queue{}        queue.Enqueue(10)    queue.Enqueue(20)    queue.Enqueue(30)        for len(queue) > 0 {        val, ok := queue.Dequeue()        if ok {            fmt.Println("Extrait :", val)        }    }}

Les files d'attente sont utilisées dans les systèmes de gestion de tâches, la mise en mémoire tampon des données et les algorithmes de recherche en largeur (BFS).

Algorithmes de base de tri et de recherche

Tri à bulles (Bubble Sort)

Algorithme de tri simple qui parcourt plusieurs fois le tableau, compare les éléments adjacents et les échange s'ils sont dans le mauvais ordre.

package main

import "fmt"

func bubbleSort(arr []int) {    n := len(arr)    for i := 0; i < n-1; i++ {        for j := 0; j < n-i-1; j++ {            if arr[j] > arr[j+1] {                arr[j], arr[j+1] = arr[j+1], arr[j]            }        }    }}

func main() {    data