Удаление элементов из однонаправленного списка

Из динамических структур можно удалять элементы, т.к. для этого достаточно изменить значения адресных полей.

Рис. Удаление элемента из списка

point* del_point(point*beg,int k) {

//удаление элемента с номером k из списка

point*p=beg;

if (k==0) { //удаление первого элемента

beg=beg->next;

delete p;

return beg;

}

//проходим по списку до элемента с номером k-1

for(int i=1;i<k&&p->next!=0;i++)

p=p->next;

/*если такого элемента в списке нет, то возвращаем

указатель на начало списка в качестве результата

функции*/

if (p->next==0) return beg;

point* r=p->next;//ставим указатель r на k-й элемент

p->next=r->next;//связываем k-1 и k+1 элемент

delete r;//удаляем k-й элемент из памяти

return beg;

}

Пример1. Создание и печать однонаправленного списка

#include <iostream.h>

#include<string.h>

//описание структуры

struct point{

char *name; //информационное поле

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

point*next; //адресное поле

};

point* make_point(){

//создание одного элемента

point*p=new(point);//выделить память

char s[20];

cout<<"\nEnter the name:";

cin>>s;

//выделить память под динамическую строку символов

p->name=new char[strlen(s)+1];

strcpy(p->name,s);

//записать информацию в строку символов

cout<<"\nEnter the age";

cin>>p->age;

p->next=0;//сформировать адресное поле

return p;

}

void print_point(point*p) {

//печать информационных полей одного элемента списка

cout<<"\nNAME:"<<p->name;

cout<<"\nAGE:"<<p->age;

cout<<"\n--------------------------------\n";

}

point* make_list(int n) {

//формирование списка из n элементов

point* beg=make_point();//сформировать первый элемент

point*r;

for(int i=1;i<n;i++) {

r=make_point();//сформировать следующий элемент

//добавление в начало списка

r->next=beg;//сформировать адресное поле

beg=r;//изменить адрес первого элемента списка

}

return beg;//вернуть адрес начала списка

}

int print_list(point*beg) {

//печать списка, на который указывает указатель beg

point*p=beg;//р присвоить адрес первого элемента списка

int k=0;//счетчик количества напечатанных элементов

while(p) { //пока нет конца списка

print_point(p);

//печать элемента, на который указывает элемент p

p=p->next;//переход к следующему элементу

k++;

}

return k;//количество элементов в списке

}

void main() {

int n;

cout<<"\nEnter the size of list";

cin>>n;

point*beg=make_list(n);//формирование списка

if (!print_list(beg))

cout<<"\nThe list is empty";}

Перед компиляцией кода в среде MSVC++ необходимо в меню Options/Project отключить режим Use Microsoft Foundation Classes.

Задания

1.Наберите код программы из Примера 1. Выполните компиляцию и запуск программы.

2.Сформируйте однонаправленный список с символьным информационным полем. На основе кода из Примера 1 выполните удаление из этого списка элемента с указанным номером. Выполните печать списка до и после изменений.

3.Сформируйте однонаправленный список с вещественным информационным полем. Добавьте в этот список заданный элемент после первого элемента с аналогичным информационным полем. Выполните печать списка до и после изменений.

Домашние задания

1. Индивидуальное задание. Номер варианта определяется по журналу. Решите задачу данной группы, выполняя следующие требования:

1) Сформировать однонаправленный список, тип информационного поля указан в варианте.

2) Распечатать полученный список.

3) Выполнить обработку списка в соответствии с заданием.

4) Распечатать полученный список.

5) Удалить список из памяти.

Варианты индивидуального задания