Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Односвязный линейный список, очередь
Односвязный список (очередь) - такая упорядоченная структура данных, которые могут удаляться с одного ее конца (начало очереди ), а добавляются в другой ее конец (конец очереди). Очередь организована по принципу 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(" Сортировка выполнена" ); } |
Последнее изменение этой страницы: 2017-03-14; Просмотров: 674; Нарушение авторского права страницы