МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
КАФЕДРА АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ
Индивидуальное домашнее задание
по дисциплине
«Структуры и алгоритмы»
на тему:
«Линейные связные блоковые списки»
|
|
Студент |
|
|
|
Ключанских А.С |
|
|||||||||
|
|
|
|
подпись, дата |
|
фамилия, инициалы |
|
|||||||||
|
|
Группа |
|
АС-10 |
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|||||||||
|
|
Принял |
|
|
|
|
|
|||||||||
|
|
|
|
|
|
Журавлева М.Г. |
|
|||||||||
|
|
ученая степень, звание |
|
подпись, дата |
|
фамилия, инициалы |
|
|||||||||
Липецк 2011
-
Задание
-
Осуществить программную реализацию индексированного списка, которая должна включать:
-
Вставить элемент в голову списка (InsertToHead)
-
Удалить элемент из головы списка (DeleteFromHead)
-
Вставить элемент в хвост списка (InsertToTail)
-
Удалить элемент из хвоста списка (DeleteFromTail)
-
Вставить элемент в произвольную позицию i (Insert(i))
-
Удалить элемент из произвольной позиции i (Delete(i))
-
Получить значение элемента в голове (GetHeadElement)
-
Получить значение элемента в хвосте (GetTailElement)
-
Получить значение элемента в произвольной позиции i (GetElement(i))
-
Установить значение элемента в голове (SetHeadElement)
-
Установить значение элемента в хвосте (SetTailElement)
-
Установить значение элемента в произвольной позиции (SetElement(i))
-
Очистить список (Clear).
Размер индексной таблицы должен задаваться пользователем. Необходимо обеспечить должным образом обработку исключительных ситуаций (выход за границы массива, ввод некорректной информации и пр.). Список следует выводить на экран по запросу пользователя вместе со всей сопутствующей информацией (кэш, индексная таблица, блоки).
-
Генерацию списка по запросу пользователя для указанных им входных данных. Для индексированных списков указывается количество узлов, размер индексной таблицы. Следует обеспечить возможность применения всех реализованных функций к сгенерированному списку.
-
Оценку производительности, включающую расчет различных временных характеристик. В этом случае списки генерируются многократно, согласно заданным законам распределениямДля индексированных списков следует провести сравнительный анализ среднего времени выполнения операций произвольного доступа с соответствующим временем в неиндексированном списке и оценить зависимость (показать график) среднего времени произвольного доступа от размера индексной таблицы.
-
Листинг программы
#include <stdio.h>
#include <conio.h>
void vvod_simvola(struct element *p);
void form_index_tabl();
void InsertToHead();
void DeleteFromHead();
void InsertToTail();
void DeleteFromTail();
void Insert();
void Delete();
void GetHeadElement();
void GetTailElement();
void GetElement();
void SetHeadElement();
void SetTailElement();
void SetElement();
void Clear();
void PromeshPrint();
void SozdElement();
void IndexTab();
struct element
{
char *str;
element *next;
element *prev;
}*head, *p, *q, *r;
struct index
{
int num;
element *ukaz;
} *in;
int razmer_index_tab, del = 0, del1;
int main()
{
int k = 1, num;
char l;
head = NULL;
//i?aaiecoai eioa?oaen iieuciaaoaey
printf("1 - InsertToHead\n2 - DeleteFrom-Head\n3 - InsertToTail\n4 - DeleteFrom-Tail\n5 - Insert(i)\n6 - Delete(i)\n7 - Ge-tHeadElement\n8 - GetTailElement\n9 - Ge-tElement(i)\n10 - SetHeadElement\n11 - SetTailElement\n12 - SetElement(i)\n13 - Clear\n14 - Print\n15 - SozdElement (per-vyj)\n16 - KorrectIndexTab\n\nVyberite dejstvie\n\n");
num = 1;
while((num > 0)&&(num < 17))
{
scanf("%d",&num);
if (num == 1)
InsertToHead();
else if (num == 2)
DeleteFromHead();
else if (num == 3)
InsertToTail();
else if (num == 4)
DeleteFromTail();
else if (num == 5)
Insert();
else if (num == 6)
Delete();
else if (num == 7)
GetHeadElement();
else if (num == 8)
GetTailElement();
else if (num == 9)
GetElement();
else if (num == 10)
SetHeadElement();
else if (num == 11)
SetTailElement();
else if (num == 12)
SetElement();
else if (num == 13)
Clear();
else if (num == 14)
PromeshPrint();
else if (num == 15)
SozdElement();
else if (num == 16)
IndexTab();
else
{
printf("Vy dejstvitel'no hotite prekratit' rabotu? (y/n)\n");
while ((l != 'y')&&(l != 'n'))
{
l = getch();
}
if (l == 'n')
num = 1;
}
}
//ia?aou eiaaeniie oaaeeou
printf("\n\nVywesti rezyl'tat raboty pro-grammy? (y/n)\n");
l = ' ';
while ((l != 'y')&&(l != 'n'))
{
l = getch();
}
if (l == 'y')
{
PromeshPrint();
getch();
}
//oaaeaiea nienea (k - i?ieciae ieii?aiey i?enoee nienea)
if (head != NULL)
{
while(k > 0)
{
k = 0;
p = head;
while (p->next != NULL)
{
p = p->next;
k++;
}
delete p->str;
delete p;
}
delete p->str;
delete p;
}
return 0;
}
//ooieoey aey anoaaee aeaiaioa a aieiao (naia anoaaea - ioaaeuiay ooieoey)
//e i?iaa?ea ia ?aaiiia?iinou ?ani?aaaeaiey nnueie a eiaaeniie oaaeeoa
void InsertToHead()
{
if (head == NULL)
{
printf("Spisok ne sischestvuet... Sozdajte element\n\n");
return;
}
p = head;
q = new element;
q->next = p;
p->prev = q;
q->prev = NULL;
q->str = NULL;
head = q;
if (razmer_index_tab > 0)
in[0].ukaz = head;
p = q;
printf("Vvedite stroku\n\n");
if (razmer_index_tab > 1)
in[razmer_index_tab-1].num++;
vvod_simvola(p);
form_index_tabl();
}
//oaaeaiea yeaiaioa ec aieiau
void DeleteFromHead()
{
if (head == NULL)
{
printf("Spisok ne sischestvuet... Sozdajte element\n\n");
return;
}
if (razmer_index_tab > 1)
{
in[razmer_index_tab - 1].num--;
}
if (head->next != NULL)
{
p = head;
p->next->prev = NULL;
head = in[0].ukaz = p->next;
delete p->str;
delete p;
}
else
{
delete head->str;
delete head;
head = NULL;
}
form_index_tabl();
printf("\nVyberite dejstvie\n");
}
//aiaaaeaiea yeaiaioa a eiiao nienea
void InsertToTail()
{
if (head == NULL)
{
printf("Spisok ne sischestvuet... Sozdajte element\n\n");
return;
}
p = head;
if (razmer_index_tab >1)
{
p = in[razmer_index_tab-1].ukaz;
in[razmer_index_tab-1].num++;
}
else if (p->next != 0)
while (p->next != 0)
{
p = p->next;
}
q = new element;
p->next = q;
q->prev = p;
if (razmer_index_tab > 1)
in[razmer_index_tab - 1].ukaz = q;
p = q;
p->next = NULL;
p->str = NULL;
printf("Vvedite stroku\n\n");
vvod_simvola(p);
form_index_tabl();
}
//oaaeaiea iineaaiaai yeaiaioa a nienea
void DeleteFromTail()
{
if (head == NULL)
{
printf("Spisok ne sischestvuet... Sozdajte element\n\n");
return;
}
p = head;
if (razmer_index_tab > 1)
{
p = in[razmer_index_tab - 1].ukaz;
in[razmer_index_tab - 1].num--;
q = p->prev;
q->next = NULL;
in[razmer_index_tab - 1].ukaz = q;
delete p->str;
delete p;
}
else if (p->next != NULL)
{
while (p->next != NULL)
{
p = p->next;
}
q = p->prev;
q->next = NULL;
delete p->str;
delete p;
in[razmer_index_tab - 1].ukaz = q;
}
else
{
delete p->str;
delete p;
head == NULL;
}
form_index_tabl();
printf("\nVyberite dejstvie\n");
}
void Insert()
{
int i, j, n, n1;
if (head == NULL)
{
printf("Spisok ne sischestvuet... Sozdajte element\n\n");
return;
}
printf("V kakuju poziziyu vy hotite vstavit' element?\n\n");
scanf("%d",&i);
if ((i < 1)||((razmer_index_tab > 1)&&(i > in[razmer_index_tab-1].num)))
{
printf("Nevozmoshno vypol-nit'...\n\nVyberite dejstvie\n");
return;
}
else if (i == 1)
{
InsertToHead();
return;
}
else if (razmer_index_tab > 1)
{
if (i == in[razmer_index_tab-1].num)
{
InsertToTail();
return;
}
else
{
for (j = 1; (i>in[j].num)&&(j<razmer_index_tab); j++);
if (i > in[razmer_index_tab-1].num)
{
printf("Nevozmoshno vypol-nit'...\n\nVyberite dejstvie\n");
return;
}
for (n1 = j; n1 < razmer_index_tab; n1++)
{
in[n1].num++;
}
n1 = (in[j-1].num + in[j].num)/2;
if (n1-i > 0)
{
n = in[j-1].num;
p = in[j-1].ukaz;
for (j = 0; n < i; j++)
{
p = p->next;
n++;
}
}
else
{
n = in[j].num;
p = in[j].ukaz;
for (j = 0; n < i; j++)
{
p = p->prev;
n++;
}
}
}
}
else
{
p = head;
n = 1;
while(n < i)
{
p = p->next;
n++;
}
}
r = new element;
r->str = NULL;
q = p->prev;
r->next = p;
r->prev = q;
q->next = r;
p->prev = r;
p = r;
printf("Vvedite stroku\n\n");
vvod_simvola(p);
form_index_tabl();
}
void Delete()
{
int i, j, n, n1;
if (head == NULL)
{
printf("Spisok ne sischestvuet... Sozdajte element\n\n");
return;
}
printf("S kakoy pozizii vy hotite udalit' ele-ment?\n\n");
scanf("%d",&i);
if ((i < 1)||((i > in[razmer_index_tab-1].num)&&(razmer_index_tab > 1)))
{
printf("Nevozmoshno vypol-nit'...\n\nVyberite dejstvie\n");
return;
}
else if (i == 1)
{
DeleteFromHead();
return;
}
else if (razmer_index_tab > 1)
{
if (i == in[razmer_index_tab-1].num)
{
DeleteFromTail();
return;
}
else
{
for (j = 1; (i>in[j].num)&&(j<razmer_index_tab); j++);
if (i > in[razmer_index_tab-1].num)
{
printf("Nevozmoshno vypol-nit'...\n\nVyberite dejstvie\n");
return;
}
for (n1 = j; n1 < razmer_index_tab; n1++)
{
in[n1].num--;
}
n1 = (in[j-1].num + in[j].num)/2;
if (n1-i > 0)
{
n = in[j-1].num;
p = in[j-1].ukaz;
if (i == n)
in[j].ukaz = p->prev;
for (j = 0; n < i; j++)
{
p = p->next;
n++;
}
}
else
{
n = in[j].num;
p = in[j].ukaz;
for (j = 0; n < i; j++)
{
p = p->prev;
n++;
}
}
}
}
else
{
p = head;
n = 1;
while(n < i)
{
p = p->next;
n++;
}
}
q = p->prev;
q->next = p->next;
delete p->str;
delete p;
form_index_tabl();
printf("\nVyberite dejstvie\n");
}
//iieo?eou ia?aue yeaiaio nienea
void GetHeadElement()
{
if (head == NULL)
{
printf("Spisok ne sischestvuet... Sozdajte element\n\n");
return;
}
printf("\nElement v golove - %s\nVyberite dejstvie\n",head->str);
}
//iieo?eou iineaaiee yeaiaio ec nienea
void GetTailElement()
{
if (head == NULL)
{
printf("Spisok ne sischestvuet... Sozdajte element\n\n");
return;
}
p = head;
if (razmer_index_tab >1)
p = in[razmer_index_tab-1].ukaz;
else if (p->next != 0)
while (p->next != 0)
{
p = p->next;
}
printf("Poslednij element - %s\nVyberite deystvie\n",p->str);
}
//iieo?eou eaeie-eeai yeaiaio ec nienea
void GetElement()
{
int i, j, n, n1;
if (head == NULL)
{
printf("Spisok ne sischestvuet... Sozdajte element\n\n");
return;
}
printf("Kakoj element vy hotite polu-chit'?\n\n");
scanf("%d",&i);
if ((i < 1)||((i > in[razmer_index_tab-1].num)&&(razmer_index_tab > 1)))
{
printf("Nevozmoshno vypol-nit'...\n\nVyberite dejstvie\n");
return;
}
else if (i == 1)
{
GetHeadElement();
return;
}
else if (razmer_index_tab > 1)
{
if (i == in[razmer_index_tab-1].num)
{
GetTailElement();
return;
}
else
{
for (j = 1; (i>in[j].num)&&(j<razmer_index_tab); j++);
if (i > in[razmer_index_tab-1].num)
{
printf("Nevozmoshno vypol-nit'...\n\nVyberite dejstvie\n");
return;
}
n1 = (in[j-1].num + in[j].num)/2;
if (n1-i > 0)
{
n = in[j-1].num;
p = in[j-1].ukaz;
for (j = 0; n < i; j++)
{
p = p->next;
n++;
}
}
else
{
n = in[j].num;
p = in[j].ukaz;
for (j = 0; n < i; j++)
{
p = p->prev;
n++;
}
}
}
}
else
{
p = head;
n = 1;
while(n < i)
{
p = p->next;
n++;
}
}
printf("\nElement v pozicii %d - %s\nVyberite dejstvie\n",i,p->str);
}
//onoaiiaeou ia?aue yeaiaio nienea
void SetHeadElement()
{
char f;
if (head == NULL)
{
printf("Spisok ne sischestvuet... Sozdajte element\n\n");
return;
}
p = head;
if (p->str != NULL)
{
printf("Shelaete zamenit' znachenie?\nHead - %s (y/n)\n",head->str);
while((f!='y')&&(f!='n'))
f = getch();
if (f == 'n')
return;
}
vvod_simvola(p);
}
//onoaiiaeou iineaaiee yeaiaio nienea
void SetTailElement()
{
char f;
if (head == NULL)
{
printf("Spisok ne sischestvuet... Sozdajte element\n\n");
return;
}
p = head;
if (razmer_index_tab >1)
p = in[razmer_index_tab-1].ukaz;
else if (p->next != 0)
while (p->next != 0)
{
p = p->next;
}
if (p->str != NULL)
{
printf("Shelaete zamenit' znachenie?\nTail - %s (y/n)\n",p->str);
while((f!='y')&&(f!='n'))
f = getch();
if (f == 'n')
return;
else
printf("Vvedite znachenie\n");
}
vvod_simvola(p);
}
//onoaiiaeou eaeie-eeai yeaiaio nienea
void SetElement()
{
int i, j, n, n1;
char f;
if (head == NULL)
{
printf("Spisok ne sischestvuet... Sozdajte element\n\n");
return;
}
printf("Element s kakoj pozicii vy hotite us-tanovit'?\n\n");
scanf("%d",&i);
if ((i < 1)||((i > in[razmer_index_tab-1].num)&&(razmer_index_tab > 1)))
{
printf("Nevozmoshno vypol-nit'...\n\nVyberite dejstvie\n");
return;
}
else if (i == 1)
{
SetHeadElement();
return;
}
else if (razmer_index_tab > 1)
{
if (i == in[razmer_index_tab-1].num)
{
SetTailElement();
return;
}
else
{
for (j = 1; (i>in[j].num)&&(j<razmer_index_tab); j++);
if (i > in[razmer_index_tab-1].num)
{
printf("Nevozmoshno vypol-nit'...\n\nVyberite dejstvie\n");
return;
}
n1 = (in[j-1].num + in[j].num)/2;
if (n1-i > 0)
{
n = in[j].num;
p = in[j].ukaz;
for (j = 0; n < i; j++)
{
p = p->next;
n++;
}
}
else
{
n = in[j-1].num;
p = in[j-1].ukaz;
for (j = 0; n < i; j++)
{
p = p->prev;
n++;
}
}
}
}
else
{
p = head;
n = 1;
while(n < i)
{
p = p->next;
n++;
}
}
if (p->str != NULL)
{
printf("Shelaete zamenit' znachenie?\nTail - %s (y/n)\n",p->str);
while((f!='y')&&(f!='n'))
f = getch();
if (f == 'n')
return;
}
printf("\nVvedite stroku\n");
vvod_simvola(p);
}
//i?enoeou nienie
void Clear()
{
if (head == NULL)
{
printf("Spisok ne sischestvuet... Sozdajte element\n\n");
return;
}
p = head;
p->str = NULL;
while (p->next != NULL)
{
p = p->next;
p->str = NULL;
}
printf("\nVyberite Dejstvie\n");
}
//ia?aou anaai nienea ni neo?aaiie eioi?iaoeae
void PromeshPrint()
{
if (head == NULL)
{
printf("Spisok ne sischestvuet... Sozdajte element\n\n");
return;
}
int num = 0;
//ia?aou eiaaeniie oaaeeou
printf("\n\nIndeksnaya tablica\n\Nnomer ssylki Ssylka\n\n");
while (num < razmer_index_tab)
{
printf(" %d - %d\n",num + 1,in[num].num);
num++;
}
//ia?aou nienea
p = head;
num = 1;
printf("\nSpisok:\n\n");
printf(" %d - %s\n",num,p->str);
while (p->next != NULL)
{
num++;
p = p->next;
printf(" %d - %s\n",num,p->str);
}
printf("\nVyberite dejstvie\n");
}
//aaanoe yeaiaio neiaieuiiai oeia (eniieu-coaony a a?oaeo ooieoeyo)
void vvod_simvola(struct element *p)
{
int n = 1;
char f = ' ', *str;
p->str = NULL;
while(f != '\r')
{
f = getch();
if ((f=='\b')&&(n>1))
{
printf("\b \b");
n--;
str = new char[n];
for (int i = 0; i<n; i++)
{
str[i] = p->str[i];
}
str[n - 1] = '\0';
delete p->str;
p->str = str;
}
else if (n==100)
{
printf("\nBol'she vvodit' nel'zja");
return;
}
else if ((f!=13)&&(f!='\b'))
{
printf("%c",f);
n++;
str = new char[n];
for (int i = 0; i<n-2; i++)
{
str[i] = p->str[i];
}
str[n-2] = f;
str[n-1] = '\0';
delete p->str;
p->str = str;
}
}
printf("\nVyberite sleduyusch'ee dejstvie\n");
}
//oi?ie?iaaiea ?aaiiia?iie eiaaenie oaaeeou
void form_index_tabl()
{
if (razmer_index_tab < 3)
return;
int num = 0;
int del1 = 0;
del1 = in[razmer_index_tab - 1].num/(razmer_index_tab - 1);
if (del != del1)
{
p = head;
del = del1;
for (int i = 1; i<razmer_index_tab-1; i++)
{
for (int j = 0; j<del; j++)
{
p = p->next;
num++;
}
in[i].num = num + 1;
in[i].ukaz = p;
}
}
}
void SozdElement()
{
if (head != NULL)
{
printf("Spisok susch'estvuet\n\n");
return;
}
p = new element;
for (int i = 0; i<razmer_index_tab; i++)
{
in[i].num = 1;
in[i].ukaz = p;
}
p->next = NULL;
p->prev = NULL;
p->str = NULL;
head = p;
printf("\nVvedite stroku\n");
vvod_simvola(p);
}
void IndexTab()
{
int n;
del1 = 0;
if (razmer_index_tab > 1)
{
p = in[razmer_index_tab - 1].ukaz;
n = in[razmer_index_tab - 1].num;
}
else
{
p = head;
n = 1;
while(p->next != NULL)
{
p = p->next;
n++;
}
}
delete[] in;
printf("\nVvedite razmer indexnoj tabli-cy\n");
scanf("%d",&razmer_index_tab);
in = new index[razmer_index_tab];
for (int i = 0; i<razmer_index_tab - 1; i++)
{
in[i].num = 1;
in[i].ukaz = head;
}
in[razmer_index_tab - 1].ukaz = p;
in[razmer_index_tab - 1].num = n;
in[0].num = 1;
in[0].ukaz = head;
form_index_tabl();
printf("\nVyberite dejstvie\n");
}