Линейные списки , Стеки и очереди

ЛИНЕЙНЫЕ СПИСКИ

Предисловие

При том, что все просто, все равно возникают вопросы в форуме по этой теме.
Люди знают, что такое массив и при этом спрашивают про понятие линейного списка.
В данной статье рассматривается:

• Понятие линейного списка
• Стеки и очереди
• Сжатое и индексное хранение линейных списков

Понятие линейного списка

Линейный список - это конечная последовательность однотипных элементов (узлов), возможно, с повторениями. Количество элементов в последовательности называется длиной списка, причем длина в процессе работы программы может изменяться.
Линейный список F, состоящий из элементов D1, D2, ..., Dn, записывают в виде последовательности значений заключенной в угловые скобки F=<D1,D2,...,Dn>, или представляют графически (см.рис.1).


Рис.1. Изображение линейного списка.

Для выделения памяти под элементы хранения необходимо пользоваться функцией malloc(sizeof(DL)) или calloc(l,sizeof(DL)). D С++ используется оператор new, а для освобождения в C++ используется оператор delete.
Вот простой пример использования операторов new, delete. Они всегда должны использоваться в паре. При последовательном хранении элементы линейного списка размещаются в массиве d фиксированных размеров, например, 100, и длина списка указывается в переменной l, т.е. в программе необходимо иметь объявления вида

float d[100]; int l;

Размер массива 100 ограничивает максимальные размеры линейного списка. Список F в массиве d формируется так:

d[0]=7; d[1]=10; l=2;

При связанном хранении в качестве элементов хранения используются структуры, связанные по одной из компонент в цепочку, на начало которой (первую структуру) указывает указатель dl. Структура образующая элемент хранения, должна кроме соответствующего элемента списка содержать и указатель на соседний элемент хранения. Описание структуры и указателя в этом случае может имееть вид:

typedef struct snd /* структура элемента хранения */
{ float val; /* элемент списка */
struct snd *n ; /* указатель на элемент хранения */
} DL;
DL *p; /* указатель текущего элемента */
DL *dl; /* указатель на начало списка */

Стеки и очереди

В зависимости от метода доступа к элементам линейного списка различают разновидности линейных списков называемые стеком, очередью и двусторонней очередью.
Стек - это конечная последовательность некоторых однотипных элементов - скалярных переменных, массивов, структур или объединений, среди которых могут быть и одинаковые. Стек обозначается в виде: S=<S1,S2,...,Sn> и представляет динамическую структуру данных; ее количество элементов заранее не указывается и в процессе работы, как правило изменяется. Если в стеке элементов нет, то он называется пустым и обозначается S=< >.
Допустимыми операциями над стеком являются:
- проверка стека на пустоту S=< >,
- добавление нового элемента Sn+1 в конец стека - преобразование <S1,...,Sn> в <S1,...,Sn+1>;
- изъятие последнего элемента из стека - преобразование <S1,...,Sn-1,Sn> в <S1,...,Sn-1>;
- доступ к его последнему элементу Sn, если стек не пуст.
Таким образом, операции добавления и удаления элемента, а также доступа к элементу выполняются только в конце списка. Стек можно представить как стопку книг на столе, где добавление или взятие новой книги ввозможно только сверху.
Очередь - это линейный список, где элементы удаляются из начала списка, а добавляются в конце списка (как обыкновенная очередь в магазине).
Двусторонняя очередь - это линейный список, у которого операции добавления и удаления элементов и доступа к элементам возможны как вначале так и в конце списка. Такую очередь можно представить как последовательность книг стоящих на полке, так что доступ к ним возможен с обоих концов.
Реализация стеков и очередей в программе может быть выполнена в виде последовательного или связанного хранения. Рассмотрим примеры организации стека этими способами.
Одной из форм представления выражений является польская инверсная запись, задающая выражение так, что операции в нем записываются в порядке выполнения, а операнды находятся непосредственно перед операцией. Например, выражение
(6+8)*5-6/2
в польской инверсной записи имеет вид
6 8 + 5 * 6 2 / - .
Особенность такой записи состоит в том, что значение выражения можно вычислить за один просмотр записи слева направо, используя стек, который до этого должен быть пуст. Каждое новое число заносится в стек, а операции выполняются над верхними элементами стека, заменяя эти элементы результатом операции. Для приведенного выражения динамика изменения стека будет иметь вид
S = < >; <6>; <6,8>; (+) <14>; <14,5>; (*) <70>; <70,6>;
<70,6,2>; (/) <70,3>;(-) <67>.
Ниже приведена функция eval, которая вычисляет значение выражения, заданного в массиве m в форме польской инверсной записи, причем m[i]>0 означает неотрицательное число, а значения m[i]<0 - арифметические операции. В качестве кодировки операций сложения, вычитания, умножения и деления выбраны отрицательные числа -1, -2, -3, -4. Для организации последовательного хранения стека используется внутренний массив stack. Параметрами функции являются входной массив a и его длина l.

float eval (float *m, int l)
{ int p,n,i;
float stack[50],c;
for(i=0; i<l ;i++)
if ((n=m[i])<0)
{ c=st[p--];
switch(n)
{ case -1: stack[p]+=c; break;
case -2: stack[p]-=c; break;
case -3: stack[p]*=c; break;
case -4: stack[p]/=c;
}
}
else stack[++p]=n;
return(stack[p]);
}

Рассмотрим другую задачу. Пусть требуется ввести некоторую последовательность символов, заканчивающуюся точкой, и напечатать ее в обратном порядке (т.е. если на входе будет "ABcEr-1." то на выходе должно быть "1-rEcBA"). Представленная ниже программа сначала вводит все символы последовательности, записывая их в стек, а затем содержимое стека печатается в обратном порядке. Это основная особенность стека - чем позже элемент занесен в стек, тем раньше он будет извлечен из стека. Реализация стека выполнена в связанном хранении при помощи указателей p и q на тип, именованный именем STACK.

#include<stdio.h>
typedef struct st /* объявление типа STACK */
{ char ch;
struct st *ps; } STACK;
main()
{ STACK *p,*q;
char a;
p=NULL;
do /* заполнение стека */
{ a=getch();
q=malloc(sizeof(STR1));
q->ps=p; p=q;
q->ch=a;
} while(a!='.');
do /* печать стека */
{ p=q->ps;free(q);q=p;
printf("%c",p->ch);
} while(p->ps!=NULL);
}

Сжатое и индексное хранение линейных списков

При хранении больших объемов информации в форме линейных списков нежелательно хранить элементы с одинаковым значением, поэтому используют различные методы сжатия списков.
Сжатое хранение. Пусть в списке B=<K1,K2,...,Kn> несколько элементов имеют одинаковое значение V, а список B'=<K1', K2',...,Kn' > получается из B заменой каждого элемента Ki на пару Ki'=(i, Ki). Пусть далее B"=< K1",K2",...,Km" > -подсписок B', получающийся вычеркиванием всех пар Ki=(i, V). Сжатым хранением В является метод хранения В", в котором элементы со значением V умалчиваются. Различают последовательное сжатое хранение и связанное сжатое хранение. Например, для списка B=<C,X,Y,X,X,S,H,X,T>, содержащего несколько узлов со значением Х, последовательное сжатое и связанное сжатое хранения, с умалчиванием элементов со значением Х, представлены на рис.2.


Рис.2.Последовательное (а) и связное (б) сжатое хранение списка.

Достоинство сжатого хранения списка при большом числе элементов со значением V заключается в возможности уменьшения объема памяти для его хранения.
Поиск i-го элемента в связанном сжатом хранении осуществляется методом полного просмотра, при последовательном хранении - методом бинарного поиска.
Преимущества и недостатки последовательного сжатого и связанного сжатого хранений аналогичны преимуществам и недостаткам последовательного и связанного хранений.
Рассмотрим следующую задачу. На входе заданы две последовательности целых чисел M=<M1,M2,...,M10000>, N=<N1,N2,...,N10000 >, причем 92% элементов последовательности М равны нулю. Составить программу для вычисления суммы произведений Mi * Ni, i=1,2,...,10000.
Предположим, что список М хранится последовательно сжато в массиве структур m с объявлением:

struct
{ int nm;
float val; } m[10000];

Для определения конца списка добавим еще один элемент с порядковым номером m[j].nm=10001, который называется стопером (stopper) и располагается за последним элементом сжатого хранения списка в массиве m.
Программа для нахождения искомой суммы имеет вид:

# include <stdio.h>
main()
{ int i,j=0;
float inp,sum=0;
struct /* объявление массива */
{ int nm; /* структур */
float val; } m[10000];
for(i=0;i<10000;i++) /* чтение списка M */
{ scanf("%f",&inp);
if (inp!=0)
{ m[j].nm=i;
m[j++].val=inp;
}
}
m[j].nm=10001; /* stopper */
for(i=0,j=0; i<10000; i++)
{ scanf("%f",&inp); /* чтение списка N */
if(i==m[j].nm) /* вычисление суммы */
sum+=m[j++].val*inp;
}
printf( "сумма произведений Mi*Ni равна %f",sum);
}

Индексное хранение используется для уменьшения времени поиска нужного элемента в списке и заключается в следующем. Исходный список B = < K1,K2, ...,Kn > разбивается на несколько подсписков В1,В2, ..., Вm таким образом, что каждый элемент списка В попадает только в один из подсписков, и дополнительно используется индексный список с М элементами, указывающими на начало списков В1,В2, ...,Вm.
Считается, что список хранится индексно с помощью подсписков B1,B2, ...,Bm и индексного спискa X = < ADG1,ADG2,... ADGm >, где ADGj - адрес начала подсписка Bj, j=1,M.
При индексном хранении элемент К подсписка Bj имеет индекс j. Для получения индексного хранения исходный список В часто преобразуется в список В' путем включения в каждый узел еще и его порядкового номера в исходном списке В, а в j-ый элемент индексного списка Х, кроме ADGj, может включаться некоторая дополнительная информация о подсписке Bj. Разбиение списка В на подсписки осуществляется так, чтобы все элементы В, обладающие определенным свойством Рj, попадали в один подсписок Bj.
Достоинством индексного хранения является то, что для нахождения элемента К с заданным свойством Pj достаточно просмотреть только элементы подсписка Bj; его начало находится по индексному списку Х, так как для любого К, принадлежащего Bi, при i не равном j свойство Pj не выполняется.
В разбиении В часто используется индексная функция G(K), вычисляющая по элементу К его индекс j, т.е. G(K)=j. Функция G обычно зависит от позиции К, обозначаемой поз.K, в подсписке В или от значения определенной части компоненты К - ее ключа.
Рассмотрим список B=< K1,K2, ...,K9 > с элементами К1=(17,Y), K2=(23,H), K3=(60,I), K4=(90,S), K5=(66,T), K6=(77,T), K7=(50,U), K8=(88,W), K9=(30,S).
Если для разбиения этого списка на подсписки в качестве индексной функции взять Ga(K)=1+(поз.K-1)/3, то список разделится на три подсписка:

B1a=<(17,Y),(23,H),(60,I)>,
B2a=<(90,S),(66,T),(77,T)>,
B3a=<(50,U),(88,W),(30,S)>.

Добавляя всюду еще и начальную позицию элемента в списке, получаем:

B1a'=<(1,17,Y),(2,23,H),(3,60,I)>,
B2a'=<(4,90,S),(5,66,T),(6,77,T)>,
B3a'=<(7,50,U),(8,88,W),(9,30,S)>.

Если в качестве индексной функции выбрать другую функцию Gb(K)=1+(поз.K-1)%3, то получим списки:

B1b"=<(1,17,Y),(4,90,S),(7,50,U)>,
B2b"=<(2,23,H),(5,66,T),(8,88,U)>,
B3b"=<(3,60,I),(6,77,T),(9,30,S)>.

Теперь для нахождения узла K6 достаточно просмотреть только одну из трех последовательностей (списков). При использовании функции Ga(K) это список B2a' , а при функции Gb(K) список B3b".
Для индексной функции Gc(K)=1+K1/100, где K1 - первая компонента элемента К, находим:

B1=<(17,Y),(23,H),(60,I),(90,S)>,
B2=<(66,T),(77,T)>,
B3=<(50,U),(88,W)>,
B4=<(30,S)>.

Чтобы найти здесь узел К с первым компонентом-ключом К1=77, достаточно просмотреть список B2.
При реализации индексного хранения применяется методика А для хранения индексного списка Х (функция Ga(X) ) и методика C для хранения подсписков B1,B2,...,Bm (функция Gc(Bi) ), т.е. используется, так называемое, A-C индексное хранение.
В практике часто используется последовательно-связанное индексное хранение. Так как обычно длина списка индексов известна, то его удобно хранить последовательно, обеспечивая прямой доступ к любому элементу списка индексов. Подсписки B1,B2,...,Bm хранятся связанно, что упрощает вставку и удаление узлов(элементов). В частности, подобный метод хранения используется в ЕС ЭВМ для организации, так называемых, индексно-последовательных наборов данных, в которых доступ к отдельным записям возможен как последовательно, так и при помощи ключа.
Последовательно-связанное индексное хранение для приведенного примера изображено на рис.3, где X=<ADG1,ADG2,ADG3,ADG4>.


Рис.3. Последовательно-связанное индексное хранение списка.

Рассмотрим еще одну задачу. На входе задана последовательность целых положительных чисел, заканчивающаяся нулем. Составить процедуру для ввода этой последовательности и оргазанизации ее последовательно-связанного индексного хранения таким образом, чтобы числа, совпадающие в двух последних цифрах, помещались в один подсписок.
Выберем в качестве индексной функции G(K)=K%100+1, а в качестве индексного списка Х - массив из 100 элементов. Следующая функция решает поставленную задачу:

#include <stdio.h>
#include <stdlib.h>
typedef struct nd
{ float val;
struct nd *n; } ND;
int index (ND *x[100])
{ ND *p;
int i,j=0;
float inp;
for (i=0; i<100; i++) x[i]=NULL;
scanf("%d",&inp);
while (inp!=0)
{ j++;
p=malloc(sizeof(ND));
i=inp%100+1;
p->val=inp;
p->n=x[i];
x[i]=p;
scanf("%d",&inp);
}
return j;
}

Возвращаемым значением функции index будет число обработанных элементов списка.
Для индексного списка также может использоваться индексное хранение. Пусть, например, имеется список B=<K1,K2,...,K10> с элементами
K1=(338,Z), K2=(145,A), K3=(136,H), K4=(214,I), K5 =(146,C),
K6=(334,Y), K7=(333,P), K8=(127,G), K9=(310,O), K10=(322,X).
Требуется разделить его на семь подсписков, т.е. X=<X1,X2,...,X7> таким образом, чтобы в каждый список B1,B2,...,B7 попадали элементы, совпадающие в первой компоненте первыми двумя цифрами. Список Х, в свою очередь, будем индексировать списком индексов Y=<Y1,Y2,Y3>, чтобы в каждый список Y1,Y2,Y3 попадали элементы из X, у которых в первой компоненте совпадают первые цифры. Если списки B1,B2,...,B7 хранить связанно, а списки индексов X,Y индексно, то такой способ хранения списка B называется связанно-связанным связанным индексным хранением.

По просьбе трудящихся, делаем добавление.

Однонаправленные и двунаправленные списки.

Предисловие

В данной статье рассматривается:

1.Однонаправленные списки:

• Использование стека (реализованного в виде однонаправленного списка) при работе с выражениями, записанными в "польской"(префиксной) форме записи.
• Красивые (но, увы, крайне неэффективные) решения списочных задач.

2.Двунаправленные списки.

Однонаправленные списки

Посредством объектов, распределяемых в динамической памяти, можно организовывать различные динамические структуры данных, такие, как списки (однонаправленные и двунаправленные) и двоичные деревья. Мы ограничимся лишь самыми простыми примерами, поскольку содержательные вопросы использования динамических структур к используемому языку программирования отношения не имеют. Начнем, как это обычно и делают, с однонаправленных списков.

Не давая формального определения однонаправленного списка, поясним лишь, что он представляет собой структуру данных, каждый элемент которой имеет ссылку (указатель) на следующий элемент. Последний элемент в поле ссылки содержит NULL. Для работы с однонаправленным списком необходимо иметь указатель на его голову (первый элемент), ведь двигаться по такому списку можно лишь в одном направлении.(См. Рис.1).


Рис.1

В приведенной ниже программе продемонстрированы некоторые типичные учебные задачи на однонаправленные списки. Необходимые пояснения даны в комментариях.

#include <stdio.h>
#include <alloc.h>
/* Структура для описания односвязного (однонаправленного) списка*/
typedef int ELEMTYPE;
typedef struct node { ELEMTYPE elem; struct node * next;} *LIST;
/* Инициализация списка/ как пустого */
LIST init(LIST *l)
 { return *l=NULL;}
/* Добавление элемента в голову списка */
LIST cons (ELEMTYPE e,LIST l)
 { LIST news=(LIST)malloc(sizeof(struct node));
  news->elem=e;
  news->next=l;
  return news;
}
/* Печать списка целых */
void printlist(LIST l)
  { printf("\n") ;
    while (l!=NULL) (printf("%5d",l->elem);l=l->next;;}
}
 
/* Добавление элемента в конец списка */
 LIST last(ELEMTYPE e,LIST l)
  { LIST head;
     if (!l) { l=(LIST)malloc(sizeof(struct node)) ;
                  l->elem=e;
                  l->next=NULL;
                  return l;
             }
       else { head=l;
       while (l->nexti=NULL) l=l->next;
       l->next= (LIST) malloc (sizeof (struct node) ) ;
       l=l->next;
       l->elem=e;
       l->next=NULL;
       return head;
      }
}
 
/* Удвоить все вхождения данного элемента в список */
 
LIST doubleE(ELEMTYPE E,LIST l)
  { LIST head=l,tmp;
     while (l)
      if (l->elem==E)
     {/* вставить после него */
       tmp=l->next;
       l->next=(LIST)malloc(sizeof(struct node)) ;
       l->next->elem=l->elem;
       l->next->next=tmp;
       l=tmp;
     }
      else l=l->next;
    return head;
}
 
/* Удалить из списка все вхождения заданного элемента */
 LIST delE(ELEMTYPE E,LIST l)
  { LIST head=l,w;
     if (!l) return head;
     while (l->next)
         if (l->next->elem==E) {w=l->next;l->next=l->next->next; free(w);}
         else l=l->next;
     return head;
   }
/* Тестирующая программа */
 void main(void)
  {
    LIST p;
    init(&p) ;
    p=last(0,p); p=cons(l,p); p==cons (2, p) ; p=cons(3,p); p=last(4,p);
    p=last(5,p); p=last(6,p); p=cons(2,p); p=last(4,p);
    printlist(p);
    p=doubleE(2,p) ;
    printlist(p) ;
    p=doubieE(4,p) ;
    printlist(p) ;
    p=delE(4/p) ;
    printlist (p) ;
}

Использование стека (реализованного в виде однонаправленного списка) при работе с выражениями, записанными в "польской"(префиксной) форме записи

Рассмотрим пример использования однонаправленного списка для организации стека в алгоритмах перевода арифметического выражения в "польскую" (префиксную) форму записи и вычисления значения выражения, записанного в такой форме. Начнем с вычисления выражения — соответствующий алгоритм записывается совсем просто. Чтобы не уделять слишком много внимания техническим деталям, будем считать, что выражение, записанное в префиксной форме записи, содержит только цифры и знаки четырех бинарных арифметических операций. Вот примеры таких выражений: +12, +—123, *+12+34, ~*+12+345 — и т.д.

В приведенной ниже программе реализован следующий алгоритм.

Просматриваем выражение, записанное в префиксной форме записи, с конца, Если встречается число (в нашем случае — цифра), бросаем его в стек. Если встречается знак операции, вынимаем из стека два верхних числа, производим над ними данную операцию и результат снова бросаем в стек. То, что останется в стеке, когда выражение закончится, и есть результат (следует обратить внимание, что первым извлекается из стека второй операнд, т.е. для операций вычитания и деления — вычитаемое и делитель соответственно),

#include <stdio.h>
#include <alloc.h>
#include <dos.h>
/* Описание стека - однонаправленного списка. В этой программе
ничто не мешает сделать стек глобальным */
struct node {float data;struct node *next;} *stack;
/* Поместить элемент в стек */
void push (float x)
 { struct node *w=(struct node*)malloc(sizeof(struct node)) ;
    w->data=x;
    w->next=stack;
    stack=w;
  }
/* Снять значение со стека и вернуть его */
float pop(void)
   { float ret=stack->data;
      struct node *w=stack;
      stack=stack->next;
      free (w) ;
      return ret;
   }
/* Функция вычисления выражения в префиксной форме записи */
 float value(char *s)
  { float x,y;
    char *start=s;
    while (*s) s++;s--;
    for (;s>=start;s--)
     if ((*s)>='0'&&(*s)<='9') push(*s-'0');
     else switch (*s)
           { case '+':x=pop();y=pop();push(x+y);break;
              case '-':x=pop();y=pop();push(y-x);break;
              case '*':x=pop();y=pop();push(x*y);break;
              case '/':x=pop();y=pop();push(y/x) ;
            }
         return pop() ;
 }
 
void main(void)
 { stack==NULL;
    if (_argc<2) printf("\nНет параметра в командной строке");
       else printf("\n%f",value(_argv[1]));
}

Теперь приведем программу перевода выражения, записанного в инфиксной форме записи, в префиксную форму записи. Как и в предыдущем примере, будем считать, что выражение состоит из цифр, но теперь, помимо знаков четырех арифметических операций, оно может содержать скобки.

Для перевода выражения из инфиксной в префиксную форму записи оно просматривается с конца. В отличие от предыдущей программы в стеке хранятся не числа, а знаки операций, причем они не просто там хранятся, но и взаимодействуют между собой. В частности, операции с меньшим приоритетом ("+" и "—") "выбрасывают" из стека расположенные ниже операции с большим приоритетом "*" и "/", если они не "защищены" скобкой ")". При появлении парной скобки "(" из стека "в порядке общей очереди" выбрасываются все расположенные между скобками знаки операций (сами скобки при этом "уничтожаются").

 
#include <stdio.h>
#include <alloc.h>
#include <dos.h>
#include <string.h>
 
/* Описание стека - однонаправленного списка. В этой программе
ничто не мешает сделать стек глобальным */
struct node {char data;struct node *next;} *stack;
/* Поместить элемент в стек */
void push(char x)
 { struct node *w=(struct node*)rnalloc (sizeof (struct node)) ;
     w->data=x;
     w->next=stack;
     stack=w;
 }
/* Снять значение со стека и вернуть его */
  char pop(void)
 { float ret=stack->data;
    struct node *w=stack;
    stack=stack->next;
    free(w) ;
    return ret;
  }
/* "Подсмотреть" значение на вершине стека */
 char pick(void)
 { return stack->data;}
/* Функция вычисления выражения в префиксной форме записи */
 char * infix2prefix(char *s) { char *tempres=(char*)malloc(strlen(s)+1),*res;
 int i=0,j;
 char *start=s;
 while (*s) s++;s--;
     for (;s>=start;s--)
         if ( (*s)>='0'&&(*s)<='9') tempres[i++]=*s;
         else switch (*s)
     { case '*':case '/':push (*s) ,break;
        case '+':case'-': while (pick()=='*'|| pick ()=='/') tempres[i++]=pop();
                      push(*s);break;
        case ')':push(*s); break;
        case '(':while (pick()!=')') tempres[i++]=pop();pop();
     }
     res=(char *)malloc(i);
     i--;j=0;
     while (i>=0) res[j++]=tempres[i--] ;
     res[j]=0;
     return res;
}
 
void main(void)
  { char *s=(char *)malloc(strlen(_argv[1])+3) ;
   /* "Навесим" на строку лишние внешние скобки - так проще ее обрабатывать */
  strcpy(s+l,_argv[l]);
  s[0]=' (' ;strcat(s,") ") ;
  stack=NULL;
  if (_argc<2) printf("\nНет параметра в командной строке");
  else printf("\n%s",infix2prefix(s)) ;
}

Красивые (но, увы, крайне неэффективные) решения списочных задач

Ноги" приведенных ниже решений списочных задач растут из языка Лисп. Мы иногда показываем ребятам, что задачи на списки можно решать и таким способом, хотя, разумеется, эти решения не могут быть использованы в реальных производственных задачах (но их можно и модифицировать для повышения эффективности).

Определим структуру для однонаправленного списка и четыре функции (car, cdr, cons, null), которые назовем "примитивами". Названия функций совпадают с "лисповскими" первоисточниками (для удобства чтения мы повторим ряд небольших фрагментов, которые использовались в приведенных выше программах):

typedef int elemtype;
struct node { elemtype elem;
                     struct node *next;
};
typedef struct node *List;
elemtype car(list k)
   { return l->elem;}
elemtype cdr(list 1)
  { return l->next;}
   list cons(elemtype e,list l)
   { list tmp=(list)malioc(sizeof(struct node)) ;
   tmp->next=l;
   tmp->elem=e;
   return tmp;
}
int null(list l)
 { return (l==NULL);}

Продемонстрируем, как посредством данных примитивов можно решать различные списочные задачи. Пусть, к примеру, нам надо найти последний элемент непустого списка. Как мы будем это делать? Разумеется, дойдем до конца списка (т.е. найдем такой элемент, у которого ссылка на следующий равна NULL), и вот он — последний элемент. Это совсем простое итеративное решение, в нем описывается, как найти последний элемент. Но посмотрим на задачу с другой стороны: а что такое последний элемент непустого списка? Если список состоит из одного элемента, то это — его первый элемент ("голова"). А если в списке больше одного элемента, то последний элемент списка — это последний элемент его "хвоста". Запишем это:

int last (list l)
  { if (null(cdr(l))) return car(l);
      else return last(cdr (l));
   }

Теперь попробуем получить "начало" непустого списка (часть списка без последнего элемента). Итеративное решение этой задачи очевидно, но рекурсивное записывается еще проще! Что такое "начало" списка? Если список состоит из одного элемента, то его начало пусто. В противном случае начало списка есть первый элемент ("голова"), добавленный к началу "хвоста". Это мы и запишем:

list begin(list l}
   { if (null(cdr(l))) return NULL;
      else return cons(car(l),begin(cdr(l)));
 }

Пока мы решили две совсем простые задачки, которые и итеративно решаются "на счет раз". А вот более сложная: пусть требуется получить список, перевернутый по отношению к данному (учтите, список однонаправленный). Попробуйте решить эту задачу итеративно, а потом (только потом!) взгляните на рекурсивное решение:

list reverse(list l)
   { if (null(l)) return NULL;
     else return cons(last(l),reverse(begin (l)));
    }

Двунаправленные списки

Как и при рассмотрении однонаправленных списков, мы не станем давать формального определения двунаправленного списка, а ограничимся описанием данной структуры. Каждый элемент двунаправленного списка имеет как минимум два ссылочных поля. Одно служит для указания на элемент, предшествующий данному, другой указывает на следующий элемент списка. Обычно эти поля называются prev и next соответственно. У первого элемента списка поле prev==NULL, у последнего — next=-NULL. При работе с двунаправленным списком нет необходимости иметь указатель именно на первый элемент, ведь по такому списку можно "ходить" в двух направлениях.(См. Рис.2)


Рис.2

При использовании двунаправленного списка мало что меняется по сравнению с однонаправленным — просто при каждой операции приходится "заботиться" еще об одном поле связи. Ниже приведена программа с теми же самыми функциями, что ранее были реализованы для однонаправленных списков, только применительно к двунаправленным спискам.

#include <stdio.h>
#include <alloc.h>
  /* Структура для описания двусвязного (двунаправленного) списка*/
  typedef int ELEMTYPE;
  typedef struct node2 { ELEMTYPE elem; struct node2 *prev, *next;} *LIST2;
  /* Инициализация списка, как пустого */
   LIST2 init(LIST2 *1)
   { return *1=NULL;}
  /* Добавление элемента в голову списка */
  LIST2 cons (ELEMTYPE e,LIST2 l)
 { LIST2 n=(LIST2)malloc(sizeof(struct node2));
  n->elem=e;
  n->next=l;
  n->prev=NULL;
  l->prev=n;
  return n;
}
 
/* Печать списка целых */
void printlist(LIST2 1)
   { printf("\n");
        while (1!=NULL) {printf("%5d",1->elem);1=l->next;;}
}
/* Добавление элемента в конец списка */
 LIST2 last(ELEMTYPE e,LIST2 1)
   { LIST2 head;
      if (!1) { l=(LIST2)malloc(sizeof(struct node2));
                  l->elem=e;
                  l->next=NULL;
                  l->prev=NULL;
                  return l;
                 }
                 else { head=l;
                          while (l->nextl=NULL) l==l->next;
                          l->next=(LIST2)malloc(sizeof(struct node2)) ;
                          l->next->prev=l;
                          l=l->next;
                          l->elem=e;
                          l->next=NULL;
                          return head;
                        }
 }
 
/* Удвоить все вхождения данного элемента в список */
 LIST2 doubleE(ELEMTYPE E,LIST2 l)
  { LIST2 head=l,tmp;
        while (l)
        if (l->elem==E)
        {/* вставить после него */
          tmp=l->next;
          l->next=(LIST2)malloc(sizeof(struct node2)) ;
          l->next->elem=l->elem;
          l->next->next=tmp;
          l->next->prev=l;
          l->tmp;
         }
         else l=l->next;
      return head;
}
 
/* Удалить из списка все вхождения заданного элемента */
LIST2 delE(ELEMTYPE Е,LIST2 1)
 { LIST2 head=l,w;
    if (!l) return head;
    while (l->next)
         if (l->next->elem==E)
            { w=l->next; l->nехt=l->nехt->nехt;
                if (l->next!=NULL) l->next->prev=l;
                free(w) ;
            }
         else l=l->next;
      return head;
 }
 
/* Тестирующая программа */
 void main(void)
  {
    LIST2 p;
    init(&p) ;
    p=last(0,p); p=cons(1,p); p=cons(2,p); p=cons(3,p); p=last(4,p);
    p=last(5,p); p=last(6,p); p=cons(2,p); p=last(4,p);
    printlist(p);
    p=doubleE(2,p) ;
    printlist(p) ;
    p=doubleE(4,p) ;
    printlist(p) ;
    p=delE(4,p) ;
    printlist(p);
 
}

Сообщение отредактировано: Gazon - 14.06.04, 13:29

Gazon, мы вряд ли можем выложить статью от тебя, если не известно ее происхождение.
Даже если привести ссылку на оригинал http://www.otd.tstu.ru/is/lang/Cpp/g2/21.html, то все равно не известно мнение авторов - как они отнесутся что их копируют и распространяют. Прошу тебя высказаться по этому поводу.

1.Информация взета не из одного источника(и не вся имеет источник).
2.Эта информация утверждена в качестве учебного пособия и свободно распространяется в интрернете, а следовательно может всеми использоваться(нет никаких нарушений прав).

Сообщение отредактировано: Gazon - 15.06.04, 11:55

Короче все ведут к тому, чтобы не дать тебе Dgm.

Guest, ты знаешь что модераторам доступно видеть айпишники, с которых отправлено сообщение в форум?
Пока это еще не ведет ни к чему. Пока что модераторы думают.

Добавлено в 15.06.04, 15:59:
Gazon, просьба еще раз, точнее указать источник статьи.

Учеб. пособие. Тамбов. Изд-во Тамб. гос. техн. ун-та, 2001. 192 с.

Статья хорошая, и плюсы принесла.
Мне понравилась, кратко и по сути

Сообщение отредактировано: Leprecon - 16.06.04, 17:14