Реализации алгоритмов/Связный список

Материал из Викиучебника — открытых книг для открытого мира
Перейти к навигации Перейти к поиску

Свя́зный спи́сок — базовая динамическая структура данных в информатике, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки на следующий и/или предыдущий узел списка.

Пример реализации односвязного списка на C[править]

Заголовочный файл list.h:

 1 #ifndef LIST_H
 2 #define LIST_H
 3 
 4 #include <stdio.h>
 5 #include <stdlib.h>
 6 
 7 typedef struct list {
 8 	int val;
 9 	struct list *next;
10 }List;
11 
12 static List* list_new(int val);
13 void list_add(List **list, int val);
14 void list_node_del(List **node);
15 void list_del_by_value(List **list, int val);
16 void list_free(List *list);
17 
18 #endif

Файл list.c:

 1 #include "list.h"
 2 
 3 static List* list_new(int val) {
 4 	List *list = (List*)malloc(sizeof(List));
 5 	list->val = val;
 6 	list->next = NULL;
 7 	return list;
 8 }
 9 
10 void list_add(List **list, int val) {
11 	for(; *list != NULL; list = &(*list)->next);
12 	*list = list_new(val);
13 }
14 
15 void list_node_del(List **node) {
16 	free(*node);
17 	(*node) = (*node)->next;
18 }
19 
20 void list_del_by_value(List **list, int val) {
21 	for(; *list != NULL; list = &(*list)->next) {
22 		if((*list)->val == val) {
23 			list_node_del(list);
24 			break;
25 		}
26 	}
27 }
28 
29 void list_free(List *list) {
30 	for(; list != NULL; list = list->next)
31 		free(list);
32 }

Пример реализации на Java[править]

public class Node {
  //содержимое текущего элемента списка
  private int element;
  //указатель на следующий элемент списка
  private Node next;
  //вывод содержимого текущего элемента
  public int getElement(){
    return element;
  }
  //установка содержимого для текущего элемента списка
  public void setElement(int e){
    element = e;
  }
  //получение указателя на следующий элемент списка
  public Node getNext() {
    return next;
  }
  //установка следующего элемента списка
  public void setNext(Node n) {
    next = n;
  }
}

Пример реализации односвязного списка на C#[править]

class Node
    {
        public void SetNextNode(Node _nextNode)
        {
            this.next = _nextNode;
        }
        public int Element
        { 
            get
            {
                return this.element;
            }
            set
            {
                this.element = value;
            }
        }

        public Node Next
        {
            get
            {
                return this.next;
            }
        }

        private Node next;
        private int element;
    }

class List
    {
        public List()
        {
            // создание пустого списка
            this.headNode = null;
            this.tailNode = this.headNode;
            this.Length = 0;
        }
        public void Push(int _element)
        {
            if (headNode == null)
            {
                // создать узел, сделать его головным
                this.headNode = new Node();
                this.headNode.Element = _element;
                // этот же узел и является хвостовым
                this.tailNode = this.headNode;
                // следующего узла нет
                this.headNode.SetNextNode(null);
            }
            else
            {
                // создать временный узел
                Node newNode = new Node();
                // следующий за предыдущим хвостовым узлом - это наш временный новый узел
                this.tailNode.SetNextNode(newNode);
                // сделать его же новым хвостовым
                this.tailNode = newNode;
                this.tailNode.Element = _element;
                // следующего узла пока нет
                this.tailNode.SetNextNode(null);
            }

            ++this.Length;
        }
        public int this[int _position]
        {
            get
            {
                // дабы не загромождать пример, 
                // опустим проверку на валидность переданного параметра '_position'
                Node tempNode = this.headNode;
                for (int i = 0; i < _position; ++i)
                    // переходим к следующему узлу списка
                    tempNode = tempNode.Next;
                return tempNode.Element;
            }
        }

        public int Length { get; private set; }
        private Node headNode;
        private Node tailNode;
    }

Реализации на Pascal[править]

Исправлено, работает!

type spisok=^element; //Сперва требуется обозначить список как тип
 element = Record //обозначаем элементы списка как запись, чтобы поместить туда данные и указатель на следующий элемент
 info:integer; //поле info отвечает за данные, которые хранит элемент списка (может быть любого типа)
 next:spisok; //так как список линейный, у нас будет указатель только на следующий элемент
end;

var first,elem,last:spisok; //создаём переменные начального элемента, вспомогательного элемента и конечного элемента типов список

 begin

 New(elem); //создаём новый элемент в динамической памяти
 elem^.next:=nil; //зануляем указатель на следующий элемент (так как его нету)
 elem^.info:=random(40)-20; //заполняем поле информации генератором рандома
 first:=elem;
 last:=elem; //так как элемент пока первый и последний, присваиваем оба элемента ему

// Процедура добавления элемента в конец списка

 New(elem);
 elem^.info:=random(40)-20;
 elem^.next:=nil;
 last^.next:=elem; //следующий от последнего теперь наш элемент
 last:=elem; // и наш элемент и есть теперь последним

//Процедура добавления элемента в начало списка

 New(elem);
 elem^.info:=random(40)-20;
 elem^.next:=first; //следующим есть первый элемент
 first:=elem; //наш элемент теперь первый

//Процедура удаления элемента с начала списка

 New(elem);
 elem:=first; //присваиваем нашему элементу значение первого
 first:=first^.next; //первым стал следующий элемент
 dispose(elem); //удаляем наш элемент

//Процедура удаления элемента с конца списка (тут потяжелее, так как список линейный)

 New(elem);
 elem:=first;
 while(elem^.next<>last) do
 begin //крутим цикл, пока не дойдем до элемента стоящего перед последним
 elem:=elem^.next; 
 elem^.next := nil; //делаем следующий от него элемент 0
 dispose(last); //удаляем последний элемент
 last:=elem; //теперь наш элемент последний
 end;

Пример реализации на Free Pascal[править]

type spisok=^element; //Сперва требуется обозначить список как тип

element=record //обозначаем элементы списка как запись, чтобы поместить туда данные и указатель на следующий элемент
 info:integer; //поле info отвечает за данные, которые хранит элемент списка (может быть любого типа)
 next:spisok; //так как список линейный, у нас будет указатель только на следующий элемент
 end;

var p, first,elem,last:spisok; //создаём вспомогательную переменную элемента, переменные начального элемента, вспомогательного элемента и конечного элемента типов список

 begin

 New(elem); //создаём новый элемент в динамической памяти
 elem^.next:=nil; //зануляем указатель на следующий элемент (так как его нету)
 elem^.info:=random(40)-20; //заполняем поле информации генератором рандома
 first:=elem;
 last:=elem; //так как элемент пока первый и последний, присваиваем оба элемента ему

// Процедура добавления элемента в конец списка

 New(elem);
 elem^.info:=random(40)-20;
 elem^.next:=nil;
 last^.next:=elem; //следующий от последнего теперь наш элемент
 last:=elem; // и наш элемент и есть теперь последним

//Процедура добавления элемента в начало списка

 New(elem);
 elem^.info:=random(40)-20;
 elem^.next:=first; //следующим есть первый элемент
 first:=elem; //наш элемент теперь первый

//Процедура удаления элемента с начала списка

 New(elem);
 elem:=first; //присваиваем нашему элементу значение первого
 first:=first^.next; //первым стал следующий элемент
 dispose(elem); //удаляем наш элемент

//Процедура удаления элемента с конца списка (тут потяжелее, так как список линейный)

 New(elem);
 elem:=first;
 while(elem^.next<>last) do //крутим цикл, пока не дойдем до элемента стоящего перед последним
 p:=elem^.next;
 elem^.next := nil; //делаем следующий от него элемент 0
 dispose(last); //удаляем последний элемент
 last:= p; //теперь наш элемент последний
 end.