Односвязный линейный список, очередь

Односвязный список (очередь) - такая упорядоченная структура данных, которые могут удаляться с одного ее конца (начало очереди ), а добавляются в другой ее конец (конец очереди). Очередь организована по принципу FIFO - ”первый вошел - первый вышел”. Для очереди определены следующие операции:

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

- добавление нового элемента в конец (хвост) очереди;

- удаление элемента из начала (головы) очереди;

- поиск и модификация элемента в очереди.

- упорядочивание элементов очереди.

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

#include < stdio.h>

#include < alloc.h>

#include < conio.h>

#include < string.h>

struct zap

{ char inf[50];

zap *nx; };

void add(zap **);

void del(zap **);

void del_any(zap **, char *);

void see(zap *);

void sort(zap **);

main()

{ zap *h, *t;

char l, *st;

st=(char *)malloc(10);

h=NULL;

clrscr();

while(1)

{ puts(" вид операции: 1-создать очередь" );

puts(" 2-вывод содержимого очереди" );

puts(" 3-удаление элемента из очереди" );

puts(" 4-удаление любого элемента из очереди" );

puts(" 5-сортировка очереди" );

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

fflush(stdin);

switch(getch())

{ case '1': add(& h); break;

case '2': see(h); break;

case '3': if(h) del(& h); break;

case '4': if(h)

{ fflush(stdin);

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

gets(st);

del_any(& h, st); }

break;

case '5': if (h) sort(& h); break;

case '0': return;

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

// функция создания очереди

void add(zap **h)

{ zap *n;

puts(" Создание очереди \n" );

do

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

{ puts(" Нет свободной памяти" );

return; }

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

scanf(" %s", n-> inf);

if (! *h) // очередь еще не создана

*h=n; // хвост очереди

else

{ n-> nx=*h; // очередной элемент очереди

*h=n; } // передвигаем указатель на хвост

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

fflush(stdin);

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

// функция вывода содержимого очереди

void see(zap *h)

{ puts(" Вывод содержимого очереди \n" );

if (! h)

{ puts(" Очередь пуста" );

return; }

do

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

h=h-> nx;

} while(h);

return; }

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

void del(zap **h)

{ zap *f, *pr;

if (! (*h)-> nx) // в очереди только один элемент

{ free(*h);

*h=NULL; // очередь пуста

return; }

pr=*h;

while(pr-> nx-> nx)

pr=pr-> nx;

free(pr-> nx); // удаление первого элемента из очереди

pr-> nx=NULL;

return; }

// функция удаления любого элемента очереди

void del_any(zap **h, char *st)

{ zap *f, *pr;

if (! (*h)-> nx & & // в очереди только один элемент

(! strcmp((*h)-> inf, st) || *st=='\0'))

{ free(*h);

*h=NULL; // очередь пуста

return; }

pr=*h;

f=pr; // далее f предыдущий к pr элемент

while(pr)

{ if (! strcmp(pr-> inf, st)) // найден элемент со строкой st

{ if (pr==*h) {*h=pr-> nx; free(pr); f=pr=*h; }

else

{ f-> nx=pr-> nx; // обходим элемент pr

free(pr); // удаляем элемент pr очереди

pr=f-> nx; } } // выбор следующего элемента очереди pr

else {f=pr; pr=pr-> nx; } }} // переход к следующему элементу

// функция сортировки содержимого очереди

void sort(zap **h)

{ zap *s1=*h, *s2, *s3, *s4, *hh=NULL;

s1=*h; // ссылка на хвост очереди

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

for(; s1-> nx; s1=s1-> nx) // выбор исходного элемента очереди

{ for(s2=s1-> nx; s2; s3=s3-> nx, s2=s2-> nx) // перебор последующих за S1

{ if (s2==s1-> nx) s3=s1; // S3-элемент расположенный перед S2

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

{ s3-> nx=s2-> nx;

s2-> nx=s1; // элемент с min становится перед S1

s4-> nx=s2; // S4- элемент расположенный перед S1

s1=s2; }} // новый адрес S1- (после замены S1< -> S2)

if(! hh)

{ hh=s1; // модификация текущего указателя на хвост очереди

free(s4); }

s4=s1; }

*h=hh; // возврат возможно измененного указателя на хвост

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

Двусвязный линейный список

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

typedef struct ndd

{ float val; // значение элемента

struct ndd * n; // указатель на следующий элемент

struct ndd * m; // указатель на предыдующий элемент

} NDD;

NDD *dl, *p, *r;

Графическая интерпретация списка с двумя связями приведена на рис. 12.

Вставка нового узла со значением new за элементом, определяемым

указателем p, осуществляется при помощи операторов:

r=malloc(NDD);

r-> val=new;

r-> n=p-> n;

(p-> n)-> m=r;

p-> =r;

Удаление элемента, следующего за узлом, на который указывает p

p-> n=r;

p-> n=(p-> n)-> n;

( (p-> n)-> n )-> m=p;

free(r);

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

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

#include < stdio.h>

#include < alloc.h>

#include < conio.h>

#include < string.h>

struct zap

{ char inf[50];

zap *pr;

zap *nx; };

void add(zap **, zap **);

void ins(zap **, char *);

void del_any(zap **, zap **, char *);

void see(zap *, int);

void sort(zap **, zap **);

 

void main(void)

{ zap *h, *g; // указатели на хвост и голову очереди

char l, *st;

st=(char *)malloc(10);

h=g=NULL;

clrscr();

while(1)

{ puts(" вид операции: 1-создать очередь" );

puts(" 2-вывод содержимого очереди" );

puts(" 3-вставка нового элемента в очередь" );

puts(" 4-удаление любого элемента из очереди" );

puts(" 5-сортировка очереди" );

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

fflush(stdin);

switch(getch())

{ case '1': add(& h, & g); break;

case '2': clrscr();

puts(" 0-просмотр с хвоста\n1- просмотр с головы" );

l=getch();

if( l=='0')se e(h, 0);

else see(g, 1);

break;

case '3': if(h)

{ gets(st);

ins(& h, st);

}br eak;

case '4': if(h)

{ge ts(st);

del_any(& h, & g, st);

}br eak;

case '5': if (h) sort(& h, & g); break;

case '0': return;

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

// функция создания очереди и добавления (только) в хвост очереди

void add(zap **ph, zap **pg)

{ zap *n;

puts(" Создание очереди \n" );

do

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

{ puts(" Нет свободной памяти" );

return; }

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

scanf(" %s", n-> inf);

if (! *ph ||! *pg) // очередь еще не создана

{ *ph=n; // указатель на хвост очереди

*pg=n; } // указатель на голову очереди

else

{ n-> nx=*ph; // указатель на элемент (хвост) очереди

(*ph)-> pr=n; // хвост указывает на новый элемент

*ph=n; // передвигаем указатель хвоста на новый элемент

}

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

fflush(stdin);

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

// функция вывода содержимого очереди

// вывод начинать с хвоста (i==0) или головы (i==1)

void see(zap *p, int i)

{ puts(" Вывод содержимого очереди \n" );

if (! p)

{ puts(" Очередь пуста" );

return; }

do

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

if(! i) p=p-> nx;

else p=p-> pr;

} while(p);

return; }

 

// функция добавления элемента в очередь (до головы очереди)

// добавление работает правильно только если очередь упорядочена

// с хвоста по возрастанию [ (хвост) 1 2 5 7 9 (голова) вставить 4 ]

void ins(zap **ph, char *s)

{ zap *p=*ph, *n;

while(p & & strcmp(p-> inf, s)< 0) p=p-> nx;

if(! (n=(zap *) calloc(1, sizeof(zap))))

{ puts(" Нет свободной памяти" );

return; }

strcpy(n-> inf, s); // копирует s n-> inf

p-> pr-> nx=n; // предыдущий элемент очереди указывает

// на вводимый элементт (n)

n-> nx=p; // новый элемент указывает на следующий

// элемент очереди p

n-> pr=p-> pr; // новый элемент указывает на предыдующий

// элемент очереди p

p-> pr=n; // последующий элемент очереди указывает на

// вводимый элемент

}

// функция удаления любого одного элемента очереди

// p1- указатель на хвост p2- на голову очереди

void del_any(zap **p1, zap **p2, char *st)

{ zap *ph=*p1;

if (! *p1 ||! p2)

{ puts(" Очередь пуста" );

return; }

if (ph-> nx==NULL & & // в очереди только один элемент

(! strcmp(ph-> inf, st) || *st=='\0'))

{ free(ph);

*p1=*p2=NULL; // очередь пуста

return; }

while(ph & & strcmp(ph-> inf, st)) ph=ph-> nx;

if (! strcmp(ph-> inf, st)) // найден элемент со строкой st

{ if(ph==*p1) // удаляемая вершина - хвост очереди

{ *p1=(*p1)-> nx; // новый указатель на хвост очереди

(*p1)-> pr=NULL; }

else if(ph==*p2) // удаляемая вершина - голова очереди

{ *p2=(*p2)-> pr; // новый указатель на голову очереди

(*p2)-> nx=NULL; }

else

{ ph-> pr-> nx=ph-> nx; // обходим элемент pr

ph-> nx-> pr=ph-> pr; }

free(ph); }} // удаляем элемент pr очереди

// функция сортировки содержимого очереди

void sort(zap **ph, zap **pg)

{ zap *s1, *s2, *s3;

for(s2=*pg; s2; s2=s2-> pr)

for(s1=*ph; s1-> nx; s1=s1-> nx)

{ if(strcmp(s1-> nx-> inf, s1-> inf)> 0)

{ s3=s1-> nx; // s3- вершина следующая за s1

if(! s1-> pr) *ph=s1-> nx; // модификация хвоста очереди

s1-> nx=s1-> nx-> nx; // s1-nx указывает через вершину

if(s1-> nx) s1-> nx-> pr=s1; // s1-> nx выше был модифицирован

else s2=*pg=s1; // s1-> nx==NULL -коррекция головы

s3-> pr=s1-> pr;

s3-> nx=s1;

if (s3-> pr) s3-> pr-> nx=s3;

s1-> pr=s3;

s1=s1-> pr; }} // откат для s1=s1-> nx в цикле for

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

⇐ Предыдущая123456Следующая ⇒

Поделиться: