Операции со списками при связном хранении

Удаление элемента, следующего за узлом, на который указывает р (см. рис. 12 ). Исключение элемента из цепочки данных сводится к изменению одной единственной ссылки и не требует перемещения остальных элементов, как это имело бы место, например, для массивов.

Рис. 12. Схема удаления элемента из списка.

r=p->n;

p->n=r->n;

free(r);

Добавление нового элемента в цепочку данных. Для этого достаточно изменить одну ссылку. Ниже показана вставка нового узла со значением new за элементом, определенным указателем р (см. рис. 13):

Рис. 13. Схема вставки элемента в список.

r=( SPIS*)malloc(1,sizeof(SPIS));

r->n=p->n; r->val=new; p->n=r;

Печать значений элементов списка. Рассматриваются два случая:

1) печать значения элемента списка определяемого указателем r:

r=dl;

while(r)

{ printf("\n элемент %d равен %f ",i,r->val);

r=r->n;

}

2) печать обоих соседей узла(элемента), определяемого указателем p (см. рис.14)

Рис.14. Схема выбора соседних элементов.

if((r=p->n)==NULL) printf("\n нет соседа справа");

else printf("\n сосед справа %f", r->val);

if(p==dl) printf("\n нет соседа слева" );

else { r=dl;

while( r->n!=p ) r=r->n;

printf("\n левый сосед %f", r->val);

}

Частичное упорядочение списка (см. рис.15)

Рис.15. Схема частичного упорядочения списка.

SPIS *v;

float k1;

k1=dl->val;

r=dl;

while( r->n!=NULL )

{ v=r->n;

if (v->valn=v->n

v->n=dl;

dl=v;

}

else r=v;

}

Стек

Стек - это конечная последовательность некоторых однотипных элементов - скалярных переменных, массивов, структур или объединений, среди которых могут быть и одинаковые. Размещение новых элементов в стек и удаление существующих из стека производится только с одного его конца, называемого вершиной стека.

Стек предполагает добавление и удаление из него элементов так, что стек является динамической, постоянно меняющейся структурой. Согласно определению, в стеке имеется только одно место для размеще­ния новых элементов - его вершина. Последний размещаемый элемент нахо­дится в вершине стека. Стек иногда называется списком с организацией LIFO - ”последний размещенный извлекается первым”. Если необходимо поддержи­вать информацию о промежуточных состояниях стека, то она должна разме­щаться вне стека. Внутри самого стека эта информация не поддерживается.

Допустимыми операциями над стеком являются:

- проверка стека на пустоту;

- добавление нового элемента на вершину стека;

- удаление элемента в вершины стека.

Стек можно представить как стопку книг на столе, где добавление или взятие новой книги возможно только сверху.

Ниже приводится текст программы, иллюстрирующий работу со стеком:

#include <stdio.h>

#include <alloc.h>

#include <conio.h>

#include <string.h>

struct zap {char inf[50];

zap *l;};

void push(zap **);

void pop(zap **);

void see(zap *);

void sort1(zap *);

void sort2(zap **);

void (*f[])(zap **)={push,pop,sort2};

void (*ff[])(zap *)={see,sort1};

main()

{ zap *s;

char l;

clrscr();

s=NULL;

while(1)

{ puts("\nвид операции:\n 1-создать/добавить\n 2-удалить");

puts(" 3-просмотреть\n 4-сортировка 1\n 5-сортировка 2");

puts(" 0-окончить");

fflush(stdin);

l=getch();

switch(l)

{ case '1': (*f[0])(&s); break;

case '2': if(s) (*f[1])(&s); break;

case '3': (*ff[0])(s); break;

case '4': if (s) (*ff[1])(s); break;

case '5': if (s) (*f[2])(&s); break;

case '0': return;

default: printf("Ошибка, повторите \n");

}

}

return 0;

}

// функция cоздания/добавления в стек

void push(zap **s)

{ zap *s1=*s;

do

{ if(!(*s=(zap *) calloc(1,sizeof(zap))))

{ puts("Нет памяти");

return;

}

puts("Введите информацию в inf");

fflush(stdin);

gets((*s)->inf);

(*s)->l=s1;

s1=*s;

puts("Продолжить (y/n)");

fflush(stdin);

} while(getch()=='y');

}

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

void see(zap *s)

{ zap *s1;

s1=s;

if (!s)

{ puts("Стек пуст");

return;

}

do

{ printf("%s\n",s1->inf);

s1=s1->l;

} while(s1);

puts("Вывод стека закончен");

}

// функция удаления последнего элемента стека

void pop(zap **s)

{ zap *s1;

s1=*s;

*s=(*s)->l;

free(s1);

puts("Последний элемент стека удален");

return;

}

// функция сортировки элементов стека

// перестановкой содержимого элементов стека

void sort1(zap *s)

{ zap *s1,*s2;

for(;s->l;s=s->l)

{ s1=s; // элемент стека для упорядочивания

for(s2=s->l;s2;s2=s2->l) // перебор последующих эл-тов справа от i-го

if(strcmp(s1->inf,s2->inf)>0)

s1=s2; // найдено новое меньшее значение

// по новому адресу

if(s1!=s)

{ strcpy(s2->inf,s1->inf);

strcpy(s1->inf,s->inf);

strcpy(s->inf,s2->inf);

}

}

puts("Сортировка стека выполнена");

}

// функция сортировки элементов стека

// перестановкой адресов элементов стека

void sort2(zap **s)

{ zap *ss,*s1,*s2,*s3,*s4=NULL;

ss=( zap *) calloc(1,sizeof(zap));

ss->l=*s; // ссылка на вершину стека

for(;ss->l->l;)

{ s1=ss->l; // элемент стека для упорядочивания

for(s2=ss->l; s2->l; s2=s2->l) // перебор последующих эл-тов стека

if(strcmp(s1->inf,s2->l->inf)>0) // найдено новое меньшее значение

{ s1=s2->l; // адрес текущего минимального эл-та

s3=s2; // адрес элемента перед минимальным

}

if(s1!=ss->l)

{ s3->l=s1->l;

s1->l=ss->l;

ss->l=s1;

}

ss=ss->l;

if(!s4) s4=s1; //новая вершина стека

}

puts("Сортировка стека выполнена");

*s=s4;

}