Организация структуры данных. Определение структуры элемента

Министерство образования и науки РФ

Федеральное агентство по образованию

Государственное образовательное учреждение высшего профессионального образования

 «Комсомольский-на-Амуре Государственный Технический Университет»

Факультет компьютерных технологий

Кафедра МОП ЭВМ

ЛАБОРАТОРНАЯ РАБОТА 3

по курсу «Структуры и алгоритмы обработки данных»

Выполнил:                                                                                                         Рогозин В.А.

Проверил:                                                                                                          Хусаинов А.А.

Вариант:                                                                                                            15

Комсомольск-на-Амуре

2006

Задание:     

Организовать структуру данных дек. Определить структуру элемента - строка символов и написать подпрограммы добавления, удаления и чтения элемента. Написать тестовую программу.

Алгоритм работы программы:

Структура элемента:

deque   //дек элемент состоящий из строки

{

char *text ;  //строка символов элемента

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

};

·  Для добавления элемента в начало дека определена подпрограмма

void   insert(deque **q, char *item);.

Для добавления элемента в конец дека определена подпрограмма

void   append(deque **q, char *item);

·  Для чтения элемента дека определена подпрограмма

char *peek(deque **q, int *error);, которая возвращает текст заданного элемента дека.                                            

·  Для удаления первого элемента определена подпрограмма  

char *take_out(deque **q, int *error);                                       

если такого элемента нет, то возвращается 1, иначе удаляется элемент и возвращается его значение

·  Для удаления последнего элемента определена подпрограмма  

char *delend(deque **d, int *error);

если такого элемента нет, то возвращается 0, иначе удаляется элемент и возвращается его значение

Текст программы:

#include <alloc.h>

#include <conio.h>

#include <stdio.h>

#include <string.h>

#define deque struct deq

void  insert(deque **q, char *item);//Добавление в начало дека

void  append(deque **q, char *item);//Добавление в конец дека

char *take_out(deque **q, int *error);//Удаление первого элемента дека

char *peek(deque **q, int *error);//Чтение элемента дека

char *delend(deque **d, int *error);// Удаление последнего элемента дека

int isempty(deque **q);//Проверка

void show_deque(deque *q);//Вывод дека

deque   //дек элемент состоящий из строки

{

char *text ;

deque *next ;

};

void main()

{

clrscr();

char *names[] = {"Город","Улица", "Дом" ,"Квартира"};

deque *d1 = 0; //Создание головного элемента

show_deque(d1);//Вывод начального дека

int err=0;

for (int i=0; i<4; i++) append(&d1,names[i]);

printf("\nСписок из пяти элементов\n");

show_deque(d1);//Вывод полученного дека

insert(&d1,"Страна");  //Добавление элементов

insert(&d1,"Регион");//в начало дека

show_deque(d1);

printf("\n удаленый элемент %s", delend(&d1,&err));

printf("\n5 элементов (удаление из конца)\n");

show_deque(d1);

printf("\n удаленый элемент %s", take_out(&d1,&err));

printf("\n4 элементов (удаление из начала)\n");

show_deque(d1);

getch();

}

//Добавление в начало дека

void  insert ( deque **q, char *item )

{

deque *new_item;

new_item = (deque * ) malloc (sizeof(deque) );

new_item -> text = item;

new_item -> next = *q ;  *q = new_item;

}

//Добавление в конец дека

void  append( deque **q, char *item )

{

deque *current = *q, *prev = 0;

deque *new_node = (deque * ) malloc (sizeof(deque) );

new_node -> text = item;

new_node -> next = 0;

while(current)

{

prev = current; current = current->next;

}

if (prev) prev->next = new_node;

else *q = new_node;

}

//Удаление первого элемента дека

char *take_out ( deque **q, int *error )

{

deque *old_item = *q;

char* old_info = 0;

if ( *q )

{

old_info = old_item -> text;

*q = ( *q ) -> next;

free (old_item );

*error = 0;

}

else *error = 1;

return ( old_info ) ;

}

//Чтение элемента дека

char *peek( deque **q, int *error)

{

if ( *q ) { *error = 0 ; return (*q) -> text;}

else { *error = 1 ; return 0;}

}

// Удаление последнего элемента дека

char *delend(deque **d, int *error)

{

deque *current = *d, *prev = *d;

char* oldinfo=0; *error = 0;

if((*d) == 0)    // if empty

{ *error=1; return 0; }

if (current->next==0) // if 1 element

{

*d=0; oldinfo = current->text;

free (current); return oldinfo;

}

else

while (current->next != 0)

{

prev = current; current = current->next;

}

oldinfo = current->text; free( current);

prev->next = 0; return oldinfo;

}

//Проверка

int isempty(deque **q)

{

if(*q) return 0;       // непустой

else return 1;     // пустой

}

//Вывод дека

void show_deque( deque *q )

{

printf("\n");

if ( q )

{

printf(" %s ", q->text); //printf( " %-7d ", q->length);

show_deque(q->next);

}

}

Результат работы программы:

                         

Список использованных источников:

1.  Хусаинов А.А., Михайлова Н.Н. Структуры и алгоритмы обработки данных: Учеб. пособие. – Комсомольск-на-Амуре: Комсомольский-на-Амуре гос. техн. ун-т, 2002..