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

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

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

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. N-натуральных чисел являются элементами двунаправленного списка L, вычислить:X₁*X_n+X₂*X_n-1+...+X_n*X₁. Вывести на экран каждое произведение и итоговую сумму.

Алгоритм:

1) Создаём структуру.

2) Формируем список целых чисел.

3) Продвигаемся по списку: от начала к концу в одном цикле, от конца к началу в другом цикле и перемножаем данные, содержащиеся в соответствующих элементах списка.

4) Суммируем полученные результаты.

5) Выводим на печать

#include <stdio.h>

#include <stdlib.h>

typedef struct list_elem {//структура - элемент списка

int date;//полe данных

struct list_elem *next,*pred;

/*указатели адресов следующего и предыдущего

элементов списка*/

} SPK;

SPK* NewElem (SPK *pnev);

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

void PrintList();//функция вывода списка на печать

void ITOG();

//функция нахождения суммы произведений элементов

SPK *list_start,*list_end;

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

void main(){

int N;

printf("\nInput size of the list: ");

scanf("%d",&N);

SPK *end=NULL;//указатель адреса последнего элемента

printf("\nINPUT DATE:");

do { //цикл формирования списка

end=NewElem(end);

if (end==NULL)

break;

N--;

}

while(N > 0);

printf("\n\n\nOur List: ");

PrintList();

ITOG();

}

SPK* NewElem (SPK *lel) {

int num=1; //номер вводимого элемента

lel=(SPK*)malloc(sizeof(SPK));

//выделение памяти для элемента списка

printf("\n%d element: ",num);

printf("\tInput date: ");

scanf("%d",&lel->date); //ввод числа

if (list_start==NULL) {

//если список пуст, то поля адресов равны 0

lel->next=lel->pred=NULL;

list_start=list_end=lel;

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

}

else {

list_end->next=lel;

/*указатель последнего элемента указывает на

присоединяемый элемент*/

lel->pred=list_end;

/*указатель присоединяемого элемента указывает на

последний элемент*/

lel->next=NULL;

list_end=lel;

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

}

num++;

return lel;

}

void PrintList() {

SPK *lel=list_start;

while(lel!=NULL) {

//пока не найден последний элемент списка

printf("%4d",lel->date);

lel=lel->next;

//передвигаем указатель на следующий элемент

}

}

void ITOG() {

SPK *lel=list_start;

SPK *mel=list_end;

int mltp,itog=0;

while(lel!=NULL) {

mltp=(lel->date)*(mel->date);//умножение элементов

printf("\n\n%d * %d = %d",lel->date,mel->date,mltp);

itog=itog+mltp;//суммирование произведений

lel=lel->next;

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

mel=mel->pred;

//идем по списку из последнего элемента в первый

}

printf("\n\nITOG = %d",itog);

}

Пример 2.

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

#include <iostream.h>

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

int key;//ключевое поле

point* pred,*next;//адресные поля

};

//Создание двунаправленного списка

point*make_list(){

int n;

cout<<"n-?";cin>>n;

point *p,*r,*beg;

p=new (point);//создать первый элемент

beg=p;/*запомнить адрес в переменную beg, в которой

хранится начало списка*/

cout<<"key-?";cin>>p->key;//заполнить ключевое поле

p->pred=0;p->next=0;//запомнить адресные поля

for(int i=1;i<n;i++){//добавить элементы в конец списка

r=new(point);//новый элемент

cout<<"key-?";cin>>r->key;//адресное поле

p->next=r;//связать начало списка с r

r->pred=p;//связать r с началом списка

r->next=0;//обнулить последнее адресное поле

p=r;//передвинуть p на последний элемент списка

}

return beg;//вернуть первый элемент списка

}

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

void print_list(point *beg){

if (beg==0) {//если список пустой

cout<<"The list is empty\n";

return;

}

point*p=beg;

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

cout<<p->key<<"\t";

p=p->next;//перейти на следующий

}

cout<<"\n";

}

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

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

if (beg==0) {//если список пустой

cout<<"The list is empty\n";

return beg;

}

point *p=beg;

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

beg=beg->next;

//переставить начало списка на следующий элемент

if(beg==0)return 0;//если в списке только один элемент

beg->pred=0;//обнулить адрес предыдущего элемента

delete p;//удалить первый

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

}

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

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

/*пройти по списку либо до элемента с предыдущим

номером, либо до конца списка*/

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

//если в списке нет элемента с номером k

point*r=p->next;//встать на удаляемый элемент

p->next=r->next;//изменить ссылку

delete r;//удалить r

r=p->next;//встать на следующий

if(r!=0)r->pred=p;//если r существует, то связать элементы

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

}

//Вставка в двунаправленный список элемента с номером k

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

if (beg==0) {//если список пустой

cout<<"The list is empty\n";

return beg;

}

point *p;

p=new(point);

//создать новый элемент и заполнить ключевое поле

cout<<"key-?";cin>>p->key;

if(k==0) {//если добавляется первый элемент

p->next=beg;//добавить перед beg

p->pred=0;//обнулить адрес предыдущего

beg->pred=p;//связать список с добавленным элементом

beg=p;//запомнить первый элемент в beg

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

}

point*r=beg;//встать на начало списка

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

/*пройти по списку либо до конца списка, либо до

элемента с номером k-1*/

p->next=r->next;//связать р с концом списка

if(r->next!=0)r->next->pred=p;

//если элемент не последний, то связать конец списка с р

p->pred=r;//связать р и r

r->next=p;

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

}

void main(){

point*beg=0;

int i,k;

do {

cout<<"1. Make list\n";

cout<<"2. Print list\n";

cout<<"3. Add point\n";

cout<<"4. Del point\n";

cout<<"5. Exit\n";

cin>>i;

switch(i) {

case 1: beg=make_list();

break;

case 2: print_list(beg);

break;

case 3: cout<<"\nk-?";

cin>>k;

beg=add_point(beg,k);

break;

case 4: cout<<"\nk-?";

cin>>k;

beg=del_point(beg,k);

break;

}

}

while(i!=5);

}

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

Задания

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

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

3.Для решения задачи сформируйте двунаправленный список. Даны действительные числа a₁ , a₂ , . . . , a_2n (n >= 2, заранее неизвестно и вводится с клавиатуры). Вычислите: max (min (a₁, a_2n ) , min (a₃, a_2n-2 ) , . . . , min (a_2n-1, a₂ ) ) .

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

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

2.Для решения задачи сформируйте двунаправленный список с символьным информационным полем. Удалите из последовательности символов все элементы, у которых равные соседи (первый и последний символы считать соседями).

3.Дана последовательность, состоящая только из нулей и единиц. Удалите из нее все группы подряд идущих одинаковых символов, длина которых больше n. Первый и последний символы считать соседями.