Односвязные списки

При работе с совокупностью данных обычно используются массивы. Их преимущество очевидно, когда используется циклическая обработка информации. Если при работе с информацией приходится менять порядок элементов, то использование массивов приводит к большим затратам времени, так как приходится перемещать значительные объёмы информации. Например, необходимо создать список фамилий (рис. 11.1).

	Афанасьев
	Бирюкова
	Васильева
	Миронов
	Сергеева
	Яковлева

Рис. 11.1. Исходный список фамилий

При внесении дополнительной фамилии «Баринова» (рис. 11.2), необходимо будет переместить все фамилии, начиная со второй, на одну позицию ниже. При больших списках это может занимать значительное время.

	Афанасьев
	Баринова
	Бирюкова
	Васильева
	Миронов
	Сергеева
	Яковлева

Рис. 11.2. Список с добавленной фамилией «Баринова»

Если в новом списке нужно удалить фамилию «Васильева» (рис. 11.3), то также возникает необходимость в перемещении информации, что тоже приводит к значительным затратам времени.

	Афанасьев
	Баринова
	Бирюкова
	Миронов
	Сергеева
	Яковлева

Рис. 11.3. Список с удаленной фамилией «Васильева»

Для более эффективной работы с такими списками лучше использовать структуру. Содержимое её полей можно разделить на две части. Одна содержит информацию о конкретном объекте, а другая (указатель) содержит адрес, по которому находится следующий объект. Таким образом, данный связный список представляет собой отдельные записи, связанные между собой указателями, и называется односвязным (однонаправленным) списком. Схематически его можно изобразить так, как показано на рис. 11.4, где указатель first совпадает с адресом первого элемента списка.

Рис. 11.4. Схематическое изображение односвязного списка,

представленного на рис. 11.3

Если нужно внести в список новую фамилию, то, двигаясь по списку, сначала необходимо определить те элементы, между которыми должна быть вставлена новая фамилия. Пусть необходимо добавить новую фамилию «Васильева», находящуюся под условным номером «7», в список, представленный на рис. 11.3. Передвигаясь по списку, определяем, что данная фамилия должна находиться между фамилиями «Бирюкова» и «Миронов».

В этом случае в поле адреса третьего элемента должен быть адрес седьмого элемента, а в поле адреса седьмого элемента необходимо занести адрес четвертого элемента (рис.11.5) [4].

Рис. 11.5. Схематическое изображение списка при добавлении новой фамилии

«Васильева» в список, представленный на рис. 11.3

Если необходимо удалить кого-либо из списка, то, двигаясь по списку, нужно найти этот объект и перестроить связи таким образом, чтобы данный элемент был исключен из списка. Не следует забывать, что необходимо освобождать память, выделенную под этот элемент. Пусть в списке, представленном на рис.11.5, удаляется фамилия «Афанасьев», которая идет первой в односвязном списке. Тогда следует перенастроить указатель first и освободить место, занимаемое этим объектом. Если удаляется фамилия внутри списка (например, «Миронов»), то связь объекта «7.Васильева» перенаправляется по связи удаляемого объекта.

Структура для описания таких объектов может иметь вид:

struct persona { char *name; // Фамилия человека

persona *next; // Указатель на следующий объект

};

Следует обратить внимание на то, что структура persona используется до конца ее описания. Это единственный случай нарушения принципа использовать лишь то, что описано выше. Это сделано для того, чтобы создавать такую структуру данных.

Листинг 11.1. В программе формирующий односвязный список, состоящий из фамилий, которые вводятся с клавиатуры. Отметим, что фамилии следует вводить на английском языке. Затем из сформированного списка удаляется указанная фамилия.

Файл “stdafx.h”

#pragma once

#define WIN32_LEAN_AND_MEAN

#include <stdio.h>

#include <tchar.h>

#include <string.h>

#include <iostream>

using namespace std;

Файл “Spisok.h”

// Структура, описывающая объект односвязного списка:

struct persona

{

char *name;

persona *next;

};

// Прототип функции, добавлябщей новый элемент в односвязный список:

persona* add_persona(persona*first, char* new_name);

// Прототип функции, удаляющей элемент из односвязного списка:

persona* del_persona(persona*first, char* del_name);

// Прототип функции печати односвязного списка:

void print_persona(persona*first);

//L10_1.cpp

#include "stdafx.h"

#include "Spisok.h"

persona* add_persona(persona*first, char* new_name)

{

persona*ptr,*prev,*new_el;

// Создание нового элемента списка:

new_el=new persona;

// Заполнение информационной части объекта:

(*new_el).name=strdup(new_name);

// Поле связи нулевое. В процессе встраивания оно при необходимости

// переопределяется:

(*new_el).next=NULL;

// Проверка существования связного списка:

if(first==NULL)

{

// Список пуст и элемент вносится как единственный:

first=new_el;

return first;

}

// Поиск места для нового элемента:

ptr=first;

prev=NULL;

while(ptr && strcmp((*ptr).name, new_name)<0)

{

prev=ptr;

ptr=(*ptr).next;

}

if(prev==NULL)

// Новый элемент должен добавляться в начало списка,

// так как передвижения по списку не было:

{

(*new_el).next=first;

first=new_el;

}

else

// Новый элемент добавляется в середину или в конец списка:

{

(*prev).next=new_el;

(*new_el).next=ptr;

}

return first;

}

void print_persona(persona*first)

{

setlocale(LC_CTYPE, ".866");

persona*ptr=first;

while(ptr!=NULL)

{

cout<<(*ptr).name<<'\n';

ptr=(*ptr).next;

}

setlocale(LC_CTYPE,"russian");

}

persona* del_persona(persona*first, char* del_name)

{

persona*ptr,*prev;

ptr=first;

prev=NULL;

// Поиск удаляемой фамилии:

while(ptr && strcmp((*ptr).name, del_name)!=0)

{

prev=ptr;

ptr=(*ptr).next;

}

if(ptr==NULL) // Фамилия не найдена

{

cout<<"Такой фамилии нет!\n";

return first;

}

if(prev==NULL)

{

// Удаляется первая фамилия списка:

first=(*first).next;

delete (*ptr).name;

delete ptr;

}

else

{

// Удаляется фамилия в середине списка или в конце его:

(*prev).next=(*ptr).next;

delete (*ptr).name;

delete ptr;

}

return first;

}

int _tmain()

{ char st[50];

persona *first=NULL,*ptr;

setlocale(LC_CTYPE,"russian");

// Построение односвязного списка:

cout<<"Введите фамилию ";

cin>>st;

do

{

first=add_persona(first,st);

cout<<"Введите фамилию или нажмите 0, если хотите прекратить ввод ";

cin>>st;

}while(strcmp(st, "0")!=0);

// Печать построенного списка:

print_persona(first);

cout<<"Введите удаляемую фамилию ";

cin>>st;

// Удаление фамилии из односвязного списка:

first=del_persona(first,st);

// Печать полученного односвязного списка:

print_persona(first);

cin.get();

cin.get();

return 0;

}

Результат выполнения программы листинга 11.1 представлен на рис. 11.6.

Рис. 11.6. Результат работы программы листинга 11.1