четверг, 7 мая 2009 г.

Работа с динамическими списками

Посмотрим как работают динамические списки. Из чего они состоят? Из структур, в каждой из которой есть указатель на предыдущую либо последующую. Это верно для одно связанных списков. У дву связанных есть указатель на предыдущую и последующую одновременно.
Структура может выглядеть так:

typedef struct S1{int a; int b; S1* prev;} S1_t;

- имеет указатель на предыдущую

typedef struct S2{int a; int b; S2* next;} S2_t;

- имеет указатель на последующую

Построим для первой структуры список из 10 элементов:


printf("first:\n");
// односвязанный список
S1_t *p1=0, *pLast=0;
//построение списка
for(int i=0;i<10;++i)
{
p1=(S1_t *)malloc(sizeof(S1_t));
memset(p1,0,sizeof(S1_t));
p1->a=i;
p1->b=i+10;
if(pLast)
p1->prev=pLast;
pLast=p1;
}


Выведем список на экран:

 
p1=pLast;
while(p1){
printf("a: %d b: %d\n", p1->a,p1->b);
p1=p1->prev;
}


Удалим из списка структуры, которые содержат первое нулевое поле либо четное:

 
p1=pLast;
S1_t* p11=pLast;
while(p1){
if(!(p1->a&1)){
if(p1==pLast){
p11=p1->prev;
pLast=p11;
free(p1);
p1=p11;
}else{
p11->prev=p1->prev;
free(p1);
p1=p11->prev;
}
}else{
p11=p1;
p1=p1->prev;
}
}


После работы надо освободить память:


p1=pLast;
while(p1){
pLast=p1->prev;
free(p1);
p1=pLast;
}


В начале работы со списком я всегда устанавливаю указатель p, с которым работаю, в начало списка.
При работе с одно связанным списком главное хранить указатель на последний элемент списка, если в списке указатели в структурах указывают с последующей на предыдущую структуры.
И надо хранить указатель на первую структуру в списке, если предыдущая структура хранит указатель на последующую.
В следующем посте я приведу пример для такой структуры.

Комментариев нет: