Самый простой способ связать множество элементов – сделать так, чтобы каждый элемент содержал ссылку на следующий элемент последовательности. Такую динамическую структуру называют однонаправленным (односвязным) линейным списком. Если каждый элемент списка содержит две ссылки: одну на следующий элемент, вторую на предыдущий, то такой список называют двунаправленным. А если последний элемент связать указателем с первым, то получится кольцевой список.
На рис.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)
Задание: Создать список из слов,в который все слова исходного текст входят только один раз.
Таблица № 7.
|
Наименование переменной |
Тип |
Назначение |
|
|
Входные данные |
head->a |
struct(char) |
Информационная часть стека |
|
a |
char |
Считывание строк из файла |
|
|
*s,p[100][100] |
char |
Разбиение строк на лексемы, после отбора не повторяющихся слов,заносятся в стек |
|
|
i |
int |
Счётчик для массива |
|
|
cnt |
int |
Счётчик для отбора слов |
|
|
Выходные данные |
head->a |
struct(char) |
Слова, которые не повторяются заносятся сюда |
Блок-схема функции 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. Стек из слов
Задание: Создать список из чисел. Исключить все повторяющиеся подряд элементы. Оставить по одному из них.
Таблица № 7.
|
Наименование переменной |
Тип |
Назначение |
|
|
Входные данные |
h->inf |
int |
Информационная часть очереди |
|
q[50] |
int |
Массив из чисел в который считывается из файла |
|
|
Выходные данные |
h->inf |
int |
Хранятся неповторяющиеся числа |
Блок-схема функции 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. Элементы очереди
Одним из отличительных признаков различных структур данных является характер отношений между элементами. По взаимной подчиненности элементов структуры данных подразделяются на линейные и нелинейные. В линейных структурах все элементы равноправны. К ним относятся массив, множество, стек, очередь.
В нелинейных структурах между элементами существуют отношения подчиненности или они могут быть связаны логическими условиями. К ним относятся деревья, графы, фреймы.
Дерево (корневое дерево) – это непустое множество элементов (узлов
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
