Операции со списками при связном хранении

При простом связанном хранении каждый элемент списка представляет собой структуру nd, состоящую из двух элементов: val - предназначен для хранения элемента списка, n - для указателя на структуру, содержащую следующий элемент списка. На первый элемент списка указывает указатель dl. Для всех операций над списком используется описание:

typedef struct nd

{ float val;

struct nd * n; } ND;

int i,j;

ND * dl, * r, * p;

Для реализации операций могут использоваться следующие фрагменты программ:

1) печать значения i-го элемента

r=dl;j=1;

while(r!=NULL && j++n;

if (r==NULL) printf("\n нет узла %d ",i);

else printf("\n элемент %d равен %f ",i,r->val);

2) печать обоих соседей узла(элемента), определяемого указателем p (см. Рис.4)

Рис.4. Схема выбора соседних элементов.

 

if((r=p->n)==NULL) printf("\n нет соседа справа");

else printf("\n сосед справа %f", r->val);

if(dl==p) printf("\n нет соседа слева");

else { r=dl;

while(r->n!=p) r=r->n;

printf("\n левый сосед %f", r->val);

}

3) удаление элемента, следующего за узлом, на который указывает р (см. Рис.5)

Рис.5. Схема удаления элемента из списка.

 

if ((r=p->n)==NULL) printf("\n нет следующего");

p->n=r->n; free(r->n);

4) вставка нового узла со значением new за элементом, определенным указателем р (см. Рис.6)

Рис.6. Схема вставки элемента в список.

 

r=malloc(1,sizeof(ND));

r->n=p->n; r->val=new; p->n=r;

5) частичное упорядочение списка в последовательность значений, s+t+1=l, так что K1'=K1; после упорядочения указатель v указывает на элемент K1' (см. Рис.7)

Рис.7. Схема частичного упорядочения списка.

 

ND *v;

float k1;

k1=dl->val;

r=dl;

while(r->n!=NULL)

{ v=r->n;

if (v->valn=v->n;

v->n=dl;

dl=v;

}

else r=v;

}

Постановка задачи

1. Элемент списка должен представлять собой структуру, состоящую из двух полей: одно поле – это какая-либо простейшая информация, заданная типом int или char, если в задании не оговорен какой-либо другой тип. Второе поле будет содержать указатель на следующий элемент списка или будет содержать признак конца списка.

2. Элементы списка должны вводиться с клавиатуры и размещаться в динамической памяти. Должен быть предусмотрен признак конца формирования списка, который сообщается пользователю.

3. После ввода списка вывести его на монитор.

4. Затем выполнить действия над элементами списка, заданные в конкретном варианте.

5. Элементы списка для поиска, сравнения, вставки и т.д. в список вводить с клавиатуры.

6. После выполнения преобразования над списком вывести результат на монитор.

Пример решения задачи

Все операции, которые необходимо выполнить над списком, подробно описаны в разделе 3.4.

Пример объявления элемента списка и всех указателей, необходимых для работы со списком (текущий элемент, голова списка и следующий).

 

typedef struct nd

{ <type> val;

struct nd * next; } ND;

ND * head, * current, * next;

Приняты следующие обозначения в описании вариантов заданий.

Параметры L, L1 и L2 обозначают списки, а параметры Е, E1 и Е2 -- данные типа <type> val, к которым применимы операции присваивания и проверки на равенство.

На рис. 8 представлена схема двух списков: с заглавным звеном и без заглавного звена. Под заглавным звеном подразумевается наличие элемента списка, в котором нет поля со значением, а есть только поле, которое содержит ссылку на начало списка.

Однонаправленный список без заглавного звена

Однонаправленный список с заглавным звеном

Рис.8.

Варианты заданий для лабораторной работы № 6