воскресенье, 7 апреля 2013 г.

Связные списки в С++


Связные списки являются примитивными конструкциями в некоторых языка программирования, но не в С++. Указатели для ссылок и структуры для узлов описывается следующим образом:
struct node
{
  Item item;
  node *next;
};
typedef node *link;
Связный список - это набор элементов, причем каждый из них является частью узла (node), который также содержит ссылку (link) на узел.

Узлы определяются ссылками на узлы, поэтому связные списки иногда называют самоссылочными (self-referent) структурами. Более того, хотя узел обычно ссылается на другой узел, возможна ссылка на самого себя, поэтому связные списки могут представлять собой циклические (cyclic) структуры.
Обычно под связным списком подразумевается реализация последовательного расположения набора элементов. Начиная с некоторого узла, мы считаем его первым элементом последовательности. Затем прослеживается ссылка на другой узел, который дает нам второй элемент последовательности и т.д. Поскольку список может быть циклическим, последовательность иногда представляется бесконечностью. Чаще список, соответствует простому последовательному расположению элементов, принимая одно из следующих соглашений для ссылки последнего узла:
  • Это пустая (null) ссылка, не указывающая на какой-либо узел.
  • Ссылка указывает на фиктивный узел (dummy node), который не содержит элементов.
  • Ссылка указывает на первый узел, что делает список циклическим.
В качестве примера рассмотрим следующую программу решение задачи Иосифа (Флавия):

Для представления людей, расставленных в круг, построим циклический связный список, где каждый элемент (человек) содержит ссылку на соседний элемент против хода часовой стрелки. Целое число i представляет  i-того человека в круге. После создания циклического списка из одного узла вставляются узлы 2 до N. В результате образуется окружность с узлами от 1 до N. При этом переменная x указывает на N. Затем пропускаем M-1 узлов, начиная с 1-го, и устанавливаем значение ссылки (M-1)-го узла таким образом, чтобы пропустить М-ый узел. Продолжаем эту операцию, пока не останется один узел.
// Задача Иосифа (Циклические списки)


#include 
#include 

using namespace std;

struct node
{
  int item;
  node *next;

  node(int x, node *t)
  {
    item = x;
    next = t;
  }
};

typedef node *link;

int main(int argc, char *argv[])
{
  int i;
  int N = atoi(argv[1]);
  int M = atoi(argv[2]);

  link t = new node(1, 0);
  t->next = t;

  link x = t;

  for (i = 2; i <= N; i++)
  {
    x = (x->next = new node(i, t));
  }

  while(x != x->next)
  {
    for (i = 1; i < M; i++)
    {
      x = x->next;
    }

    x->next = x->next->next;
  }

  return 0;
}

Комментариев нет :

Отправить комментарий