#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define STR_BUF_LEN 80
int k, g, j;
//g=0;
// Определяем типы ///////////////////////////////////////////////
enum BOOL
{
FALSE,
TRUE
}; // Перечисление для булевых значений
typedef char * T; // Тип данных по варианту
typedef struct Node * PNode; // Указатель на узел
typedef struct Node
{ // Структура узла
PNode prev; // Предыдущий
PNode next; // Следующий
T data; // Собственно данные (нагрузка)
} Node;
typedef struct
{ // Итератор
PNode node; // Узел итератора
} Iterator;
typedef Iterator * PIterator; // Указатель на итератор
typedef struct
{ // Список
PNode head; // Барьерный узел (БУ)
PIterator ci; // Итератор списка определяет тек.узел данного списка
int size; // Текущая длина списка
} List;
typedef List * PList; // Указатель на список
// Прототипы функций ////////////////////////////////////////////////
PList Create ( ); // Создать список
void Destroy ( PList l ); // Разрушить список
void Insert ( PList l, const T data ); // Вставить узел в список
void Update ( PIterator i, const T data ); // Изменить данные узла по итератору
enum BOOL Delete ( PList l, PIterator i ); // Удалить элемент из списка
PIterator First ( PList l, PIterator i ); // Первый элемент списка
PIterator Prev ( PList l, PIterator i ); // Следующий элемент
PIterator Next ( PList l, PIterator i ); // Следующий элемент
T Fetch ( PIterator i ); // Извлечь данные из итератора
void Display ( PList l ); // Отобразить список
enum BOOL Exec ( PList l ); // Задание по варинту
PList list;
////////////////////////////////
PList Create ( ) // Создать список
////////////////////////////////
{
PList l = (PList)malloc(sizeof(List)); // Выделить память под список
l->head = (PNode)malloc(sizeof(Node)); // Выделить память под барьерный эл-т (БЭ)
l->head->prev = l->head; // Инициализируем БЭ ссылка назад на БЭ
l->head->next = l->head; // ссылка вперёд на БЭ стало БЭ<-{БЭ}->БЭ
l->head->data = 0; // Пусть в данных БЭ записано 'T' (Terminator) ;)
l->ci = (PIterator)malloc(sizeof(Iterator)); // Место под итератор списка (тек.элемент списка)
l->ci->node = l->head; // Пусть итератор указывает сам на себя
l->size = 0; // Обнулить длину списка
return l; // Возвратим указатель на созданный список
}
/////////////////////////////////////////
void Destroy ( PList l ) // Разрушить список
/////////////////////////////////////////
{
// Удалить все созданные элементы
if ( First(l, l->ci) )
{ // Если встали на первый узел (если он есть)
Display(l);
while ( Delete(l, l->ci) ) // Удаляем узлы пока удаляются
Display(l);
}
// Освободить память данных списка и собственно списка
free(l->head);
free(l->ci);
free(l);
}
///////////////////////////////////////
void Insert ( PList l, const T data ) // Вставить узел в список
///////////////////////////////////////
{
PNode n = (PNode)malloc(sizeof(Node)); // Выделим память под структуру узла
PNode cnode = l->ci->node; // Тек.узел
n->data = data; // Сохраним данные
n->prev = cnode; // Ссылка на пред.узел
n->next = cnode->next; // Ссылка на след.узел
((PNode)cnode->next)->prev = n; // Ссылка со след.узла на новый узел
cnode->next = n; // Ссылка с тек.узла на новый
l->ci->node = n; // Делаем новый узел текущим
l->size++;
j = l->size; // Увеличим длину списка
}
/////////////////////////////////////////////////////////////
void Update ( PIterator i, const T data ) // Изменить данные узла по итератору
/////////////////////////////////////////////////////////////
{
free(i->node->data); // Освободить помять под старые данные
i->node->data = data;
}
//////////////////////////////////////////////////////////////
enum BOOL Delete ( PList l, PIterator i ) // Удалить узел из списка
//////////////////////////////////////////////////////////////
{
if ( i->node == l->head ) return FALSE; // Удалять БУ нельзя
PNode cnode = i->node; // Тек.узел
PNode pnode = cnode->prev; // Пред.узел
PNode nnode = cnode->next; // След.узел
// Разберёмся с взаимными ссылками оставшихся узлов
pnode->next = nnode; // (=P=C=N=) P.n->C.n | P.n->N
nnode->prev = pnode; // P<-N.p
// Назначение нового текущего узла
if ( cnode == l->ci->node )
{ // Удаляем текущий узел списка
if ( cnode->next == l->head ) // Если следующий узел барьерный
l->ci->node = cnode->prev;
else l->ci->node = cnode->next;
}
free(cnode->data); // Освободить память под данные
free(cnode); // Освобождение памяти
l->size--; // Длину списка уменьшим
return TRUE;
}
///////////////////////////////////////////
PIterator First ( PList l, PIterator i ) // Встать на первый узел списка
///////////////////////////////////////////
{
i->node = l->head->next; // Встаём
if ( i->node == l->head ) // Если это БУ
return i;
return i; // Возврат ссылки на итератор с первый узлом
}
////////////////////////////////////////////
PIterator Prev ( PList l, PIterator i ) // Переход на пред.узел
////////////////////////////////////////////
{
if ( i->node->prev == l->head ) // Если БУ
return 0;
i->node = i->node->prev;
return i; // Ссылка на итератор с пред.узлом
}
////////////////////////////////////////////
PIterator Next ( PList l, PIterator i ) // Переход на cлед.узел
////////////////////////////////////////////
{
if ( i->node->next == l->head ) // Если БУ
return 0;
i->node = i->node->next;
return i; // Ссылка на итератор со след.узлом
}
///////////////////////////////////////////////////
T Fetch ( PIterator i ) // Извлечь данные из итератора
///////////////////////////////////////////////////
{
return i->node->data;
}
//////////////////////////////////////////
void Display ( PList l ) // Отобразить список
//////////////////////////////////////////
{
printf(">>> List[%d]: ", l->size); // Вывод длины списка
Iterator i;
if ( First(l, &i) )
{ // Встаём на начало и если встали то
do
{
if ( i.node == l->ci->node ) // Вывод тек.узла
printf("\n> %s <", Fetch(&i));
else printf("\n %s", Fetch(&i)); // Вывод очередного (нетекущего) узла
} while ( Next(l, &i) ); // Переход на след.узел по списку пока переходится
}
puts("");
}
///////////////////////////////////////////
int main ( int argc, char * * argv )
//////////////////////////////////////////
{
printf("*** KP8 Start ***\n");
char action = -1; // Для кода операции
T buf2;
T gogi; // Временный указатель под данные узла
T buf = (T)malloc(STR_BUF_LEN); // Буфер для консольного ввода строки
// Определяем и создаём список для работы, экземпляр данных (уже не тип).
list = Create( ); // Создали список (Реальное выделение памяти)
while ( action != 0 )
{
printf("1-Prev 2-Next 3-Insert 4-Update 5-Delete 6-Display 7-Exec 0-Exit :");
scanf("%d", &action);
switch ( action )
{
case 0:
printf("EXIT\n");
break;
case 1:
Prev(list, list->ci);
Display(list);
break; // Left
case 2:
Next(list, list->ci);
Display(list);
break; // Right
case 3: // Insert
printf("Enter data: ");
scanf("\n%s", buf);
gogi = buf;
buf2 = (T)malloc(strlen(buf) + 1);
strcpy(buf2, buf);
Insert(list, buf2);
Display(list);
break;
case 4: // Update
printf("Update data[%s]: ", Fetch(list->ci));
scanf("\n%s", buf);
buf2 = (T)malloc(strlen(buf) + 1);
strcpy(buf2, buf);
Update(list->ci, buf2);
Display(list);
break;
case 5:
Delete(list, list->ci);
Display(list);
break; // Delete
case 6: /* Display */
Display(list);
break;
case 7:
for ( g = 0; g < 20; g++ )
Prev(list, list->ci);
//Display(list);
printf("\n");
//printf("\n> %s <", gogi);
printf("Input k\n");
scanf("%d", &k);
for ( g = 0; g < k; g++ )
Insert(list, gogi);
Display(list);
break;
default:
printf("ERROR: Nedopustimuy kod (%d)\n", action);
}
// Display(list);
}
Destroy(list); // Разрушим список (освобождение памяти)
free(buf); // Освободим буфер под ввод данных
printf("*** KP8 Finish ***\n");
}
