Создание многофайлового проекта в среде VS 2012 на языке Cи

Самый простой способ связать множество элементов – сделать так, чтобы каждый элемент содержал ссылку на следующий элемент последовательности. Такую динамическую структуру называют  однонаправленным (односвязным) линейным списком. Если каждый элемент списка содержит две ссылки: одну на следующий элемент, вторую на предыдущий, то такой список называют двунаправленным. А если последний элемент связать указателем с первым, то получится кольцевой список. 

На рис.5.1 приведена структура односвязного списка. На нем поле INF - информационное поле, данные, NEXT - указатель на следующий элемент списка. В поле указателя последнего элемента списка находится специальный признак NULL, свидетельствующий о конце списка.

Рис. 5.1. Односвязный список

Однако, обработка односвязного списка не всегда удобна, так как существует возможность перемещения по списку лишь в одну сторону. Такую возможность обеспечивает двусвязный список, каждый элемент которого содержит два указателя: на следующий и предыдущий элементы списка. Структура линейного двусвязного списка приведена на рис.5.2 , где поле NEXT - указатель на следующий элемент, поле PREV - указатель на предыдущий элемент. В крайних элементах соответствующие указатели должны содержать NULL, как и показано на рисунке.

Для удобства обработки списка добавляют еще один особый элемент - указатель конца списка. Наличие двух указателей в каждом элементе усложняет список и приводит к дополнительным затратам памяти, но в то же время обеспечивает более эффективное выполнение некоторых операций над списком.

Разновидностью рассмотренных видов линейных списков является кольцевой список, который может быть организован на основе как односвязного, так и двусвязного списков. При этом в односвязном списке указатель последнего элемента должен указывать на первый элемент; в двусвязном списке в первом и последнем элементах соответствующие указатели переопределяются, как показано на рисунке 5.3.

При работе с такими списками несколько упрощаются некоторые процедуры, выполняемые над списком. Однако, при просмотре такого списка следует принять меры предосторожности, чтобы не попасть в бесконечный цикл.

Далее подробно рассмотрим два частных случая однонаправленного списка (стек и очередь) и общий случай двунаправленного списка.

Стек – это частный случай однонаправленного списка, добавление элементов в  который и выборка элементов из которого выполняется с одного конца. Другие операции со стеком не определены. При выборке элемент исключается из стека. Стек реализует принцип LIFO (last in – first out, последним пришел – первым вышел).

Структура содержит базовый элемент, в котором есть:

·  информационное поле inf, которое может быть любого типа кроме файлового, и будет использоваться для хранения значений, например чисел, строк и др.

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

Очередь – это частный случай списка, добавление элементов в который выполняется в один конец, а выборка осуществляется из другого конца. Другие операции с очередью не определены. При выборке элемент исключается из очереди. Очередь реализует принцип FIFO (first in-first out –первым вошел, первым вышел). В программировании очереди применяются при математическом моделировании, буферном вводе-выводе и других задачах.

Организация очереди:

Структура содержит базовый элемент, в котором есть:

·  информационное поле inf, которое может быть любого типа, кроме файлового, и будет использоваться для хранения значений.

·  ссылочное поле next, в котором хранится адрес следующего элемента очереди, и которое будет использоваться для организации связи элементов. (2)

5.2. Практические задачи

5.2.1. Стек

Задание: Создать список из слов,в который все слова исходного текст входят только один раз.

Таблица № 7.

Блок-схема функции stack().

Листинг программы(неполный):

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#define open_file "Невозможно открыть файл.\n"

#define text "Исходный текст:\n"

#define spisok "Исходный список элементов:\n"

#define out_spisok "Полученный список элементов:\n"

struct st

{

char a[100]; //информационное поле целого типа

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

}*head;

st *in_s()

{

return NULL;

}

void push (st *&s, char i[100]);

char *pop(st *&s);

int empty_st(st *s);

void stack();

void main_menu()

{

int q;

for(;;)

{

printf("1-Стек\n");

printf("2-Вернуться к главному меню\n");

do

{

printf("Выберите пункт меню:");

scanf("%d",&q);

}while(q<0||q>3);

switch(q)

{

case 1:

{

stack();      

system("pause");

system("cls");

break;

}

case 2: return;

}

}

}

Полный листинг программы приведён в приложении.

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

Рис.5.6. Стек из слов

5.2.2. Очередь

Задание: Создать список из чисел. Исключить все повторяющиеся подряд элементы. Оставить по одному из них.

Таблица № 7.

Блок-схема функции tqueue_f()

Листинг программы(неполный):

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#define open_file "Невозможно открыть файл.\n"

#define text "Исходный текст:\n"

#define spisok "Исходный список элементов:\n"

#define out_spisok "Полученный список элементов:\n"

struct tqueue

{

int inf;

tqueue *next;

}*h,*t;

void init_tq(tqueue *&h, tqueue *&t);

void insert_tq(tqueue *&h,tqueue *&t, int item);

int take_tq(tqueue *&h, tqueue *&t);

int empty_tq(struct tqueue *h);

void tqueue_f();

void main_menu()

{

int q;

for(;;)

{

printf("1-Очередь\n");

printf("2-Вернуться к главному меню\n");

do

{

printf("Выберите пункт меню:");

scanf("%d",&q);

}while(q<0||q>3);

switch(q)

{

case 1:

{

tqueue_f();

system("pause");

system("cls");

break;

}

case 2: return;

}

}

}

Полный листинг программы приведён в приложении.

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

Рис.5.7. Элементы очереди

6. Тема «Нелинейные структуры данных»

6.1. Теоритическая часть

Одним из отличительных признаков различных структур данных является характер отношений между элементами. По взаимной подчиненности элементов структуры данных подразделяются на линейные и нелинейные. В линейных структурах все элементы равноправны. К ним относятся массив, множество, стек, очередь.

В нелинейных структурах между элементами существуют отношения подчиненности или они могут быть связаны логическими условиями. К ним относятся деревья, графы, фреймы.

Дерево (корневое дерево) – это непустое множество элементов (узлов