Реализации алгоритмов/Связный список
Свя́зный спи́сок — базовая динамическая структура данных в информатике, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки на следующий и/или предыдущий узел списка.
Пример реализации односвязного списка на C[править]
Заголовочный файл list.h:
#ifndef LIST_H
#define LIST_H
#include <stdio.h>
#include <stdlib.h>
typedef struct list {
int val;
struct list *next;
}List;
static List* list_new(int val);
void list_add(List **list, int val);
void list_node_del(List **node);
void list_del_by_value(List **list, int val);
void list_free(List *list);
#endif
Файл list.c:
#include "list.h"
static List* list_new(int val) {
List *list = (List*)malloc(sizeof(List));
list->val = val;
list->next = NULL;
return list;
}
void list_add(List **list, int val) {
for(; *list != NULL; list = &(*list)->next);
*list = list_new(val);
}
void list_node_del(List **node) {
free(*node);
(*node) = (*node)->next;
}
void list_del_by_value(List **list, int val) {
for(; *list != NULL; list = &(*list)->next) {
if((*list)->val == val) {
list_node_del(list);
break;
}
}
}
void list_free(List *list) {
for(; list != NULL; list = list->next)
free(list);
}
Пример реализации на 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.
Пример реализации на Haskell[править]
List a = Nil | a :+ (List a) deriving Show infixr 5 :+ -- пример создания списка 1 :+ 2 :+ Nil