Примеры программ к Лабораторной работе N9. "Структуры данных и связный список"

/* films1.c - использование массива структур */
#include <stdio.h>

#define TSIZE 45 /* размер массива для хранения названия	*/
#define FMAX 5	/* максимальное количество названий фильмов */

struct film {
	char title[TSIZE];
	int rating;
};

int main(void){
	struct film movies[FMAX];
	int i = 0;
	int j;
	puts("Введите название первого фильма:");
	while (i < FMAX && gets(movies[i].title) != NULL &&	movies[i].title[0] != '\0')	{
		puts("Введите свое значение рейтинга <0-10>:");
		scanf("%d", &movies[i++].rating);
		while(getchar() != '\n')
			continue;
		puts("Введите название следующего фильма (или пустую строку для прекращения ввода):");
	}
	if (i == 0)
		printf("Данные не были введены. ");
	else
		printf ("Список фильмов:\n");
	for (j = 0; j < i; j++)
	printf("Фильм: %s Рейтинг: %d\n", movies[j].title,	movies[j].rating);
	printf("Программа завершена.\n");
	return 0;
}

/* films2.c - использование связного списка структур */
#include <stdio.h>
#include <stdlib.h> /* содержит прототип функции malloc() */
#include <string.h> /* содержит прототип функции strcpy() */
#define TSIZE 45	/* размер массива для хранения названия */

struct film {
	char title[TSIZE];
	int rating;
	struct film *next; /* указывает на следующую структуру в списке */
};

int main(void)
{
	struct film *head = NULL;
	struct film *prev, *current;
	char input[TSIZE];

	/* Сбор и сохранение информации */
	puts("Введите название первого фильма:");
	while (gets(input) != NULL && input[0] != '\0')	{
		current = (struct film *) malloc(sizeof(struct film));
		if (head == NULL) /* первая структура	*/
			head = current;
		else	/* последующие структуры */
			prev->next = current;
		current->next = NULL;
		strcpy(current->title, input);
		puts("Введите свое значение рейтинга <0-10>:");
		scanf("%d", &current->rating);
		while(getchar() != '\n')
			continue;
		puts("Введите название следующего фильма (или пустую строку для прекращения ввода информации):");
		prev = current;
	}

	/* Отображение списка фильмов */
	if (head == NULL)
		printf("Данные не были введены. ");
	else
		printf ("Список фильмов:\n");
	current = head;
	while (current != NULL)	{
		printf ("Фильм: %s Рейтинг: %d\n", current->title, current->rating);
		current = current->next;
	}

	/* Программа выполнена, поэтому можно освободить память */
	current = head;
	while (current != NULL){
		free(current);
		current = current->next;
	}

	printf ("Программа завершена.\n");

	return 0;
}

/* films3.c - использование связного списка в стиле ADT */
/* компилировать вместе с list.с */

#include <stdio.h>
#include <stdlib.h> /* прототип функции exit()	*/
#include "list.h" /* определение типов List, Item */

void showmovies(Item item);

int main(void) {

	List movies;
	Item temp;

	/* инициализация */
	InitializeList(&movies);

	if (ListIsFull(&movies))
	{
		fprintf (stderr, "Доступная память отсутствует! Программа завершена.\n");
		exit (1);
	}
	/* сбор и сохранение информации */
	puts("Введите название первого фильма:");
	while (gets(temp.title) != NULL && temp.title[0] != '\0') {
		puts ("Введите свое значение рейтинга <0-10>:");
		scanf("%d", &temp.rating);
		while (getchar() != '\n')
			continue;
		if (AddItem(temp, &movies)==false) {
			fprintf(stderr,"Проблема с резервированием памяти\n");
			break;
		}

		if (ListIsFull(&movies))
		{
			puts("Список полон.");
			break;
		}
		puts("Введите название следующего фильма (или пустую строку для прекращения ввода):");
	}

	/* отображение */
	if (ListIsEmpty(&movies))
		printf("Данные не были введены. ");
	else
	{
		printf ("Список фильмов:\n");
		Traverse(&movies, showmovies);
	}

	printf("Вы ввели %d фильмов.\n", ListItemCount(&movies));

	/* очистка */
	EmptyTheList(&movies);

	printf("Программа завершена.\n");

	return 0;
}

void showmovies(Item item)
{
	printf("Фильм: %s Рейтинг: %d\n", item.title, item.rating);
}

/* list.h - файл заголовка для простого типа list	*/
#ifndef LIST_H_
#define LIST_H_
#include <stdbool.h> /* функциональная возможность C99	*/

/* объявления, характерные для программы */
#define TSIZE 45 /* размер массива для хранения названия	*/
struct film
{
	char title[TSIZE];
	int rating;
};

/* определения обобщенного типа	*/
typedef struct film Item;
typedef struct node
{
	Item item;
	struct node * next;
} Node;

typedef Node * List;

/* прототипы функций	*/
/* операция:	инициализация списка	*/
/* начальные условия: plist указывает на список */
/* конечные условия: список инициализирован пустым значением	*/
void InitializeList(List * plist);

/* операция:	определение того, является ли список пустым */
/*	plist указывает на инициализированный список */
/* конечные условия: функция возвращает значение True, если список	*/
/*	пуст, и False - в противном случае	*/
bool ListIsEmpty(const List *plist);

/* операция:	определение того, является ли список полным	*/
/*	plist указывает на инициализированный список	*/
/* конечные условия: функция возвращает значение True, если список */
/* полон, и False - в противном случае */
bool ListIsFull(const List *plist) ;

/* операция: определение количества элементов в списке */
/* plist указывает на инициализированный список */
/* конечные условия: функция возвращает число элементов в списке */
unsigned int ListItemCount(const List *plist);

/* операция: добавление элемента в конец списка */
/* начальные условия: item - элемент, добавляемый в список */
/* plist указывает на инициализированный список */
/* конечные условия: если возможно, функция добавляет элемент в */
/* конец списка и возвращает значение True; */
/* в противном случае она возвращает значение */
/* False */
bool AddItem(Item item, List * plist);

/* операция: применение функции к каждому элементу списка */
/* plist указывает на инициализированный список */
/* pfun указывает на функцию, которая принимает */
/* аргумент Item и не имеет возвращаемого */
/* значения */
/* конечное условие: функция, указанная pfun, выполняется один */
/* раз для каждого элемента в списке */
void Traverse(const List *plist, void (* pfun)(Item item) );

/* операция: освобождение зарезервированной памяти, если */
/* таковая существует */
/* plist указывает на инициализированный список */
/* конечные условия: любая память, зарезервированная для списка, */
/* освобождается, и список устанавливается в */ /* пустое состояние */
void EmptyTheList(List * plist);

#endif

/* list.c - функции, поддерживающие операции со списком */
#include <stdio.h>
#include <stdlib.h>
#include "list.h"

/* прототип локальной функции */
static void CopyToNode(Item item, Node * pnode);

/* функции интерфейса */
/* устанавливает список в пустое состояние */
void InitializeList(List * plist) {
	* plist = NULL;
}

/* возвращает значение true, если список пуст */
bool ListIsEmpty(const List * plist) {
	if (*plist == NULL)
		return true;
	else
		return false;
}

/* возвращает значение true, если список полон */
bool ListIsFull(const List * plist) {
	Node * pt;
	bool full;
	pt = (Node *) malloc(sizeof(Node));
	if (pt == NULL)
		full = true;
	else
		full = false;
	free (pt);
	return full;
}

/* возвращает количество узлов */
unsigned int ListItemCount(const List * plist) {
	unsigned int count =0;
	Node * pnode = *plist; /* установка на начало списка */
	while (pnode != NULL) {
		++count;
		pnode = pnode->next; /* установка на следукщий узел */
	}
	return count;
}

/* создает узел для хранения элемента и добавляет его в конец */
/* списка, указанного переменной plist (медленная реализация) */
bool AddItem(Item item, List * plist) {
	Node * pnew;
	Node * scan = *plist;
	pnew = (Node *) malloc(sizeof(Node));
	if (pnew == NULL)
		return false; /* выход из функции в случае ошибки */
	CopyToNode(item, pnew);
	pnew->next = NULL;
	if (scan == NULL) /* список пуст, поэтому помещает */
		*plist = pnew; /* pnew в начало списка */
	else
	{
		while (scan->next != NULL)
			scan = scan->next; /* ищет конец списка */
		scan->next = pnew; /* добавляет pnew в конец */ 
	}
	return true;
}

/* посещает каждый узел и выполняет функцию, указанную pfun */
void Traverse (const List * plist, void (* pfun)(Item item) ) {
	Node * pnode = *plist; /* устанавливает указатель на начало списка */
	while (pnode != NULL) {
		(*pfun)(pnode->item); /* применяет функцию к элементу */
		pnode = pnode->next; /* переход к следующему элементу */
	}
}

/* освобождает память, зарезервированную функцией malloc() */
/* устанавливает указатель списка в значение NULL */
void EmptyTheList(List * plist){
	Node * psave;
	while (*plist != NULL){
		psave = (*plist)->next; /* сохранение адреса следуюцего узла */
		free(*plist);			/* освобождение текущего узла	*/
		*plist = psave;			/* переход к следующему узлу	*/
	}
}

/* определение локальной функции */
/* копирует элемент в узел */
static void CopyToNode(Item item, Node * pnode) {
	pnode->item = item; /* копирование структуры */
}