Пример программы работы с двунаправленным списком
Двунаправленные списки позволяют упростить работу и обеспечить просмотр элементов списка в обоих направлениях. Элементы такого списка имеют по два поля - указателя, одно из которых Ladr содержит адрес соседнего слева элемента (см. ниже рисунок и программу) или NULL, если соседнего слева нет, а другое поле Radr - адрес соседнего справа элемента или NULL, если соседнего справа нет. При работе с двунаправленными списками для доступа к элементам обычно используют два указателя: один nach хранит адрес первого элемента, а другой kon – адрес последнего элемента. В этом случае начало и конец становятся равноправными, определение начального и последнего элементов является условным.
kon
nach
Рассматриваемая программа позволяет выполнять такие операции, как добавление нового элемента в конец существующего списка, просмотр содержимого списка, определение длины списка, поиск заданного элемента в списке, вставка нового элемента после или перед заданным элементом, удаление заданного элемента из списка.
Добавление нового списка в конец двунаправленного списка отличается от такой же операции для однонаправленного списка. При добавлении нового элемента в двунаправленный список выполняются разные действия при добавлении первого (в пустой список) и не первого (в непустой список) элементов. При добавлении первого элемента указатели на соседние элементы (поля Ladr и Radr) получают нулевое значение, а указатели на первый и последний (nach и kon) элементы получают одинаковые значения – адрес первого (единственного на этот момент) элемента. При добавлении не первого элемента в двунаправленный список указатель (поле Radr) на последующий элемент получает нулевое значение, а указатель на предшествующий элемент (поле Ladr) получает адрес предшествующего, добавленного в список перед этим элемента (адрес из переменной kon). При этом значение указателя nach на первый элемент свое значение не изменяет, а изменяется значение указателя kon на последний, добавляемый элемент.
Пример программы 13.
#include "stdafx.h"
#include "stdio.h"
#include "conio.h"
#include <math.h>
#include "D:\\temp\\RusString.h"
typedef struct elem
{
int inf;
elem *Ladr;
elem *Radr;
};
void add(elem **nach, elem **kon);// добавление элемента в список
void prosm(elem *nach);//просмотр содержимого списка
int dlina(elem *nach);//определение длины списка
elem* poisk(int b,elem *nach, bool *pr,int *n);//поиск заданного элемента в списке
bool wstawkapered(elem **nach);//вставка нового элемента перед заданным
bool wstawkaposle(elem *nach,elem **kon);//вставка нового элемента после заданного
bool udalenie(elem **nach,elem **kon);//удаление заданного элемента
void menu();
int _tmain(int argc, _TCHAR* argv[])
{
elem *nach,*kon,*q;
int b,n;
bool pr;
int ch;
nach=NULL;
kon=NULL;
do
{
menu();
scanf("%d",&ch);
switch (ch)
{
case 1:add(&nach,&kon);
break;
case 2:if (nach==NULL)
OutPuts("Список пуст");
else
prosm(nach);
break;
case 3:printRus("Длина списка = ");
printf("%d\n",dlina(nach));
break;
case 4:printRus("Введите значение для поиска: ");
scanf("%d",&b);
q=poisk(b,nach,&pr,&n);
if (pr)
{
printRus("Номер элемента ");
printf("%d\n",n);
printRus("Адрес элемента ");
printf("%p\n",q);
}
else
OutPuts("Нет элемента в списке ");
break;
case 5:if (wstawkapered(&nach))
OutPuts("Элемент вставлен ");
else
OutPuts("Вставка не возможна ");
break;
case 6: if (wstawkaposle(nach,&kon))
OutPuts("Элемент вставлен ");
else
OutPuts("Вставка не возможна ");
break;
case 7: if (udalenie(&nach,&kon))
OutPuts("\nЭлемент удалён");
else
OutPuts("\nУдаление не возможно ");
break;
case 8:
break;
default:{}
}
}while (ch!=8);
return 0;
}
void add(elem **nach, elem **kon)
{// добавление элемента в список
int a;
elem *t;
printRus("Введите значение элемента: ");
scanf("%d",&a);
t=new(elem);
t->inf=a;
if (*nach==NULL)
{
t->Ladr=NULL;
t->Radr=NULL;
*nach=t;
*kon=t;
}
else
{
t->Radr=NULL;
t->Ladr=*kon;
(*kon)->Radr=t;
*kon=t;
}
}
void prosm(elem *nach)
{ //просмотр содержимого списка
elem *t;
t=nach;
while (t!=NULL)
{
printf("t->inf= %d\n",t->inf);
t=t->Radr;
}
}
int dlina(elem *nach)
{//определение длины списка
int dl=0;
elem* t;
t=nach;
while (t!=NULL)
{
dl++;
t=t->Radr;
}
return dl;
}
elem* poisk(int b,elem *nach, bool *pr,int *n)
{//поиск заданного элемента в списке
elem* t,*q;
*n=0;
t=nach;
q=t;
*pr=false;
while ((t!=NULL)&&(!*pr))
{
(*n)++;
if (t->inf==b)
{
*pr=true;
q=t;
}
else
t=t->Radr;
}
if (!*pr)
*n=0;
return q;
}
bool wstawkapered(elem **nach)
{//вставка заданного элемента перед заданным (левее, т.е. ближе к началу списка)
int pris,dob,n;
bool pr;
elem *t,*q;
OutPuts("Введите значение того элемента,");
printRus("перед которым нужно вставить новый элемент: ");
scanf("%d",&pris);
q=poisk(pris,*nach,&pr,&n);
if (pr)
{
elem*t=new(elem);
printRus("Введите значение добавляемого элемента: ");
scanf("%d",&dob);
t->inf=dob;
if (n>1)
{
t->Radr=q;
t->Ladr=q->Ladr;
q->Ladr=t;
t->Ladr->Radr=t;
}
if(n==1)
{
t->Radr=q;
t->Ladr=q->Ladr;
q->Ladr=t;
*nach=t;
}
}
return pr;
}
bool wstawkaposle(elem *nach,elem **kon)
{//вставка заданного элемента после заданного
int pris,dob,n;
bool pr;
elem *t,*q;
OutPuts("Введите значение того элемента,");
printRus("после которого нужно вставить новый элемент: ");
scanf("%d",&pris);
q=poisk(pris,nach,&pr,&n);
if (pr)
{
elem*t=new(elem);
printRus("Введите значение добавляемого элемента: ");
scanf("%d",&dob);
t->inf=dob;
if (n<dlina(nach)) //q!=kon
{
t->Radr=q->Radr;
t->Ladr=q;
q->Radr=t;
t->Radr->Ladr=t;
}
if (n==dlina(nach)) //q=kon
{
t->Ladr=q;
q->Radr=t;
t->Radr=NULL;//q->Radr;
*kon=t;
}
}
return pr;
}
bool udalenie(elem **nach,elem **kon)
{//удаление заданного элемента
int pris,n,dl,i;
elem *t,*q;
bool pr;
printRus("Введите значение удаляемого элемента: ");
scanf("%d",&pris);
q=poisk(pris,*nach,&pr,&n);
if (pr)
{
if (q==*nach) //удаление первого элемента
{
t=q;
*nach=(*nach)->Radr;//*nach=t->Radr;
if (*nach==NULL)
*kon=NULL; //удаление единственного элемента
else
(*nach)->Ladr=NULL;
delete q;
}
else
if (q==*kon) //удаление последнего элемента
{
t=q;
t->Ladr->Radr=NULL;
*kon=t->Ladr;
delete q;
}
else //удаление срединного элемента
{
t=q->Ladr;
t->Radr=q->Radr;
q->Radr->Ladr=q->Ladr;
delete q;
}
}
return pr;
}
void menu()
{
OutPuts("\n\tВыберите пункт меню \n");
OutPuts("1 Добавить элемент");
OutPuts("2 Просмотр списка");
OutPuts("3 Длина списка");
OutPuts("4 Поиск элемента");
OutPuts("5 Добавить перед ");
OutPuts("6 Добавить после ");
OutPuts("7 Удалить элемент");
OutPuts("8 Выход");
}