Указатели и динамические структуры данных (связные списки) в языках С/С++

ЗАДАНИЕ

связный двунаправленный список указатель на курсовую работу студента Филиппова Ильи Александровича Группа ПС-118.

• 1. Дисциплина «программирование на языках высокого уровня»
• 2. Тема работы «Указатели и динамические структуры данных (связные списки) в языках С/С++»
• 3. Срок сдачи студентом законченной работы «___"___________2013 г.
• 4. Перечень вопросов, подлежащих разработке

Вид списка: двухсвязный кольцевой список Элемент списка: строка символов произвольной длины Операции над списком:

• *вставка элемента в начало, в конец списка
• *получение значения элемента по индексу
• *удаление элемента по индексу
• *очистка всех элементов списка
• *подсчет количества элементов в списке

Специальная операция: поиск анаграмм в списке.

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

5. Календарный план.

Двухсвязный список.

Двунаправленный (двусвязный) кольцевой список — это структура данных, состоящая из последовательности элементов, каждый из которых содержит информационную часть и два указателя на соседние элементы (рисунок 1). При этом два соседних элемента должны содержать взаимные ссылки друг на друга.

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

Описание простейшего элемента такого списка выглядит следующим образом:

struct имя_типа {.

информационное поле;

адресное поле 1;

адресное поле 2;};

где информационное поле — это поле любого, ранее объявленного или стандартного, типа; адресное поле 1 — это указатель на объект того же типа, что и определяемая структура, в него записывается адрес следующего элемента списка; адресное поле 2 — это указатель на объект того же типа, что и определяемая структура, в него записывается адрес предыдущего элемента списка.

Рисунок 1 — Двунаправленный список Схема фрагмента алгоритма программы Функция очистки всех элементов списка (void Spisok: Clear ()).

Листинг программы с комментариями Файл head.h.

#ifndef _CIRCL_H.

#define _CIRCL_H.

#include.

#include.

class Spisok{ //класс.

private:

struct Elem{ //структура.

char* data; //указатель на массив.

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

Elem *prev; //указатель не предыдущий элемент.

int index; //индекс элемента};

Elem *first; //указатель на первый элемент.

Elem *Last; //указатель на последний элемент.

void MoveIndexDown (int index); //процедура корректирования индекса, необходимая при удалениидобавлении в начало.

void MoveIndexUp (int index); //процедура корректирования индекса, необходимая при удалениидобавлении в начало.

public:

int count; //количество.

Spisok (); //конструктор

~Spisok (); //деструктор

Elem *FindElem (int index); //функция поиска элемента по индексу.

void Del (int index); //процедура удаления элемента по индексу.

char* Get (int index); //функция, возвращающая указатель на массив элемента #index.

void Add (char* data); //процедура добавления элемента в конец.

void AddToHead (char* data); //процедура добавления элемента в начало.

void Clear (); //процедура очистки списка.

void Anagr (char* FName);//поиск анаграмм};

#endif _CIRCL_H.

Файл func.cpp.

#include «head.h» .

void Spisok: MoveIndexDown (int index){.

Elem *idx;//буфер

for (int i=index+1;i<=count;i++){//уменьшение индексов элементов после Iтого на 1.

idx=FindElem (i);

idx->index=i-1;}}.

void Spisok: MoveIndexUp (int id){//увеличение индексов элементов после Iтого на 1.

Elem *idx=FindElem (id+1);

while (idx≠first){.

idx->index=idx->index+1;

idx=idx->next;}}.

Spisok:Spisok (){.

first=NULL; //обнуление.

Last=NULL;

count=0;}.

Spisok:~Spisok (){.

Clear ();//очистка списка}.

Spisok:Elem *Spisok:FindElem (int index){.

if (first==NULL){return NULL;}.

Elem *buf=first;

while (buf->next≠first){ //перебор всех элементов с первого до последнего, пока не совпадут индексы.

if (buf->index==index){.

return buf;

}else{.

if (buf≠NULL){buf=buf->next;}}}.

void Spisok: Del (int index){.

Elem *buf;//буфер

buf=FindElem (index);//поиск элемента по индексу.

MoveIndexDown (index);//смещение индексов.

if (buf->prev≠NULL){buf->prev->next=buf->next;}else{first=buf->next;}//замена указателей предыдущего и следующего элементов.

if (buf->next≠NULL){buf->next->prev=buf->prev;}.

buf->index=-1;

if (buf==first){first=first->next;}//проверка на первый и последний элементы.

if (buf==Last){Last=Last->prev;}.

delete[] (buf->data);//освобождение мамяти под строку.

delete (buf);//освобождение памяти под элемент.

Spisok:count—; //уменьшение количества элементов}.

char* Spisok: Get (int index){.

return FindElem (index)->data;//поиск элемента и возвращение указателя на строку}.

void Spisok: Add (char* data){.

Elem *next = new Elem; //выделение памяти под новый элемент.

next->data=data;

if (first==NULL){first=next;}//проверка существования первого, если нету новый будет первым.

next->index=count+1;//присваивание индекса.

next->prev=Last;//задание указателя на предыдущий.

next->next=first;//задание указателя на следующий.

if (Last≠NULL){Last->next=next;}//задание указателя предыдущего на новый.

Last=next;//делаем новый последним созданным.

Spisok:count++;//увеличение количества}.

void Spisok: AddToHead (char* data){.

if (first==NULL){Add (data);}else{//проверка на наличие первого.

MoveIndexUp (1);//смещение индексов вверх.

Elem *next = new Elem;//выделение памяти под новый элемент.

next->data=data;

next->next=first;//создание связей.

first->prev=next;

first->index=2;

first=next;

next->prev=Last;

Last->next=next;

next->index=1;

Spisok:count++;//увеличение количества}}.

void Spisok: Clear (){.

int b;//буфер

Elem *nex;//буфер

Elem *buf;//буфер

if (first≠NULL){//проверка на отсутствие элементов.

b=count;// получаем количество элементов.

buf=first;

for (int i=1;i<=b;i++){//перебор всех элементов.

nex=buf;

if (buf->next≠NULL){buf=buf->next;}.

if (nex≠NULL){.

delete[](nex->data);//очищение памяти строки элемента.

delete (nex);//очищение памяти элемента}}.

first=NULL;//обнуление первого.

Last=NULL;//обнуление последнего.

count=0;//обнуление количества}}.

void sort (char** arr, int count){//функция сортировки строки.

char buf;//буфер для перестановки.

bool c;//индикатор наличия перестановок.

for (int i=0;i.

do{//сортировка символов в каждой строке.

c=0;

for (int j=0;j.

if ((arr[i][j].

buf=arr[i][j];

arr[i][j]=arr[i][j+1];

arr[i][j+1]=buf;

c=1;}}}while (c);}}.

void Spisok: Anagr (char* FName){.

if (first==NULL){return;}//проверка на пустой список.

char** arr=new char*[count+1]; //массив-буфер для сортировки.

arr[count]='';

int j=0;

Elem* buf=first;

do{//заполняем массив.

buf=FindElem (j+1);

arr[j]=new char[strlen (buf->data)+1];

for (int i=0;i.

if (buf≠NULL){arr[j][i]=buf->data[i]; }}.

arr[j][strlen (arr[j])]='';

j++;}.

while (j<=count);

sort (arr, count);//сортируем символы в каждой строке массива.

std:ofstream out (FName);//запись в файл и вывод на экран.

std:cout<<" Найденные анаграммы:" <

for (int a=0;a.

for (int b=a+1;b.

if ((strcmp (arr[a], arr[b])==0)&&(strlen (arr[a])==strlen (arr[b]))){//ставниваем отсортированные строки для поиска анаграмм.

std:cout<< «<<

out<< «<<

out.close ();//закрываем файл.

for (int i=0;i.

delete[] arr[i]; }.

delete arr;}.

Файл main.cpp.

#include «head.h» .

void main (){.

setlocale (LC_ALL," Russian");//установка языка.

std:cout<<" Вариант 32″ <

std:cout<<" Вид списка: двухсвязный кольцевой список" <

std:cout<<" Элемент списка: строка символов произвольной длины" <

fflush (stdin);

system («PAUSE»);

Spisok Obj;

char s=' ';

while (s≠'0'){.

system («CLS»);//очистка экрана.

std:cout<<" Операции над списком:" <

std:cout<<" 1. Вставка элемента в конец списка" <

std:cout<<" 2. Вставка элемента в начало списка" <

std:cout<<" 3. Получение значения элемента по индексу" <

std:cout<<" 4. Удаление элемента по индексу" <

std:cout<<" 5. Очистка всех элементов списка" <

std:cout<<" 6. Подсчет количества элементов в списке" <

std:cout<

std:cout<<" Специальная операция:" <

std:cout<<" 7. Поиск анаграмм в списке" <

std:cout<

std:cout<<" 0. Выход" <

std:cout<

std:cout<<" Выберите операцию:" <

std:cin>>s;//считывание команды.

fflush (stdin);

switch (s){//обработка.

case '0':exit (0);

case '1':{.

system («CLS»);

std:cout<<" 1. Вставка элемента в конец списка" <

char* buf = new char[256];

std:cout<<" Введите строку:" <

gets (buf);

fflush (stdin);

buf[strlen (buf)+1]='';

Obj.Add (buf);

break;}.

case '2':{.

system («CLS»);

std:cout<<" 2. Вставка элемента в начало списка" <

char* buf = new char[256];

std:cout<<" Введите строку:" <

gets (buf);

fflush (stdin);

buf[strlen (buf)+1]='';

Obj.Add (buf);

break;

}.

case '3':{.

system («CLS»);

std:cout<<" 3. Получение значения элемента по индексу" <

std:cout<<" Введите индекс (список индексируется с 1):" <

int idx=0;

std:cin>>idx;

if ((idxObj.count)){std:cout<<" Неверный ввод" <

char* buf = Obj. Get (idx);

std:cout<

std:cout<

system («PAUSE»);

break; }.

case '4':{.

system («CLS»);

std:cout<<" 4. Удаление элемента по индексу" <

std:cout<<" Введите индекс (массив индексируется с 1):" <

int idx=0;

std:cin>>idx;

if ((idxObj.count)){std:cout<<" Неверный ввод" <

Obj.Del (idx);

std:cout<<" Удалено" <

system («PAUSE»);

break; }.

case '5':{.

system («CLS»);

std:cout<<" 5. Очистка всех элементов списка" <

Obj.Clear ();

std:cout<<" Очищено" <

system («PAUSE»);

break; }.

case '6':{.

system («CLS»);

std:cout<<" 6. Подсчет количества элементов в списке" <

std:cout<<" Количество элементов = «<

system («PAUSE»);

break; }.

case '7':{.

system («CLS»);

std:cout<<" 7. Поиск анаграмм в списке" <

std:cout<<" Введите имя файла (не больше 20 символов):" <

char* FName=new char[21];

gets (FName);

Obj.Anagr (FName);

system («PAUSE»);

break; }}}}.

Выводы

В результате выполнения проекта мы овладели приемами работы с указателями и организации на их базе динамических структур в виде связных списков на языкe C++. Были разработаны классы и функции для реализации связного списка.

• 1. Страуструп Б. Язык программирования С++ / пер. с англ — Издательство Бином, 2011 г. — 1136 с.
• 2. Шилдт, Г. Полный справочник по C++ / Герберт Шилдт; пер. с англ. Д. Клюшин. — Вильямс, 2008. — 800 с.
• 3. Связный список. — http://ru.wikipedia.org/wiki/%D1%E2%FF%E7%ED%FB%E9_%F1%EF%E8%F1%EE%EA