Реализ списков на основе динам стру.#include<stdio.h>, <stdlib.h> #include<locale.h>, <conio.h> struct date { int day; }; struct node { date data; node *next; }; void getData (node *p) { do { printf("День даты\n"); } while (!scanf("%d", &p->data.day)||p->data.day < 1||p->data.day > 31); void insert (node **start) { node *p = new node; getData(p); if(!*start){ p->next = NULL; *start = p; return;} node *prev=*start,*post=*start; while (post){ if(post->data.day>p->data.day) { p->next = post; if (post==*start)*start= p; else prev->next = p; return; } prev = post; post = post->next;} p->next = NULL; prev->next = p;} node * find (node*start,int dat) { node *p = start; while (p){ if (p->data.day == dat) return p; p = p->next; } return false;} node* remov (node**start,int dat) { if(!*start) return false; node *pdat; pdat = find(*start, dat); if (pdat){ if (pdat == *start) *start = (*start)->next; Else { node *prev = *start; while (prev){ if (prev->next==pdat)break; prev = prev->next;} prev->next = pdat->next;} return pdat;} return false;} void print (node *start) { node *p = start; while (p){ if (p==start) printf ("День"); printf ("%d\n", p->data.day); p = p->next;} }
Двусвязный список и его программная реализация. Двусвязный список позволяет выполнять «движение» от элемента к элементу в обоих направлениях. В этом случае элемент включает два указателя: на предыдущий и последующий элементы списка. А так как список имеет и начало, и конец, описываются еще два указателя – начала и конца списка #include"stdafx.h","conio.h" #include"iostream","locale.h" struct node { int info; node *next; } void 1(node**begin,node**end) { node *temp = new node; p->info=rand(); p->next=NULL; *begin=*end=p; } void AddQ (node **end) { node *p = new node; p->info=rand()%100; (*end)->next=p; p->next=NULL; *end=p;} void DelQ (node *begin, node **end) { node *p=begin; if(*begin==*end) *begin==*end=NULL; else *begin=p->next; delete p;} void printQ(node *begin) { node *p=begin; while(p){ printf("%d ", p->info); p=p->next;} } void DellAllQ(node **begin, node **end){ node *p; while(begin->next!=NULL){ p=begin->next; begin->next = begin->p; delete p;} *end=begin; }
Кольцевые списки. Кольцевой список — это список, у которого последний элемент связан с первым. Кольцевой список можно сделать как односвязным, так и двухсвязным. Рассмотрим вкратце односвязный кольцевой список. Кольцевой список не имеет первого и последнего элемента. Число служебных переменных иногда может быть и больше, и меньше: все зависит от назначения создаваемой программы.
Многосвязные (слоеные) списки. В одном элементе списка может быть задано сколько угодно связей для того, чтобы при выборке заданного подмножества информационного поля не выполнять полный просмотр, в каждую запись включается дополнительное поле ссылок, каждая из которых связывает в линейный список элементы соответствующего подмножества. В результате каждая подзадача работает со своим подмножеством как с линейным списком. Специфика слоеного списка проявляется только в операции исключения (исключение эл-та из какого-либо списка не означает необходимость удаления эл-та из памяти, т.к он может оставаться в составе других списков)
Поиск. Массив А элементов – множество данных, в котором имеется элемент, является фиксированным. Искомый элемент – образец Х. Если нет дополнительной информации о разыскиваемых данных, то самый простой способ – это последовательный просмотр элементов массива (линейный поиск). Условия окончания линейного поиска: 1. Элемент найден (a[i]=x) 2. Массив просмотрен, ничего не обнаружено Алгоритм 1: i=0; while((i<N)&&(a[i]!=x))i++; Алгоритм 2: a[N]=x; i=0; while(a[i++]!=x); //поиск с барьером Если i=N, то эл-та в массиве не существует.
|
