Другие операции над связанным списком

Добавление объекта в начало списка является самой простой операцией со связанным списком. Гораздо сложнее добавить элемент в конец списка:

voi kableClass* pLC)

на начало списка LinksbleCIass* pCurxent = pHead; будем просматривать список, пока не найдем псследний элемент списка - он должен содержать О ь указателе pNext

while (pCurrent->pNext != fLinkabieClass* ) 0]

pCurrent = pCurrent->pNext;

теперь заставим этот объект указывать па LC pCurrent->pNext = pLC;

присвоим 0 указателю на следующий объект в новом конечном элементе, пометив его как последний в списке pLC->pNext = (LinkableClassS.* ) О ;

Тело функции addTail () начинается с просмотра всего списка с самого начала до элемента, значение поля pNext которого равно нулю. Этот элемент и является последним в списке. После этого функция addTail () добавляет объект pLC* к концу списка.

(В действительности приведенная функция содержит одну ошибку. Кроме проверки элементов списка на равенство нулю, необходимо проверять и головной элемент списка - pHead. Ноль в pHead означает, что список пуст.)

Функция remove () схожа с предыдущей. Она удаляет указанный объект из списка и возвращает 1, если удаление прошло без ошибок, и 0 в противном случае.

voi kableClass* pLC)

LinkabieClass* pCurrent = pHead;

если список пуст, мы не найдем в нем *pLC if (oCurrent (LinkabieClass*) 0)

return 0;

прэсмотриы весь список до конца в поисках указанного элемента while (pCurrent->pNext);

если следуюций объект является искомым объектом if(pLC==pCurrent->pNext)

...то заставим текуций объект указыватв на следуюций за ним pCurrent->pNext = pLC->pNext;

это не обязательно, но лучше удалить указатель на следуюций объект в удаляемом элементе pLC->pNext = (LinkableClass&*)0;

return 1;

return 0;

Сначала функция проверяет, не пуст ли список. Если список пуст,

функция возврашает О (поскольку в этом случае объекта *pLC точно нет в списке). Если список не пуст, remove О просматривает все элементы списка, пока не найдет

искомый объект. Если функция находит объект, она присваивает текущему указателю

pNext значение указателя pNext из найденного объекта. Б1ло бы неплохо, если бы, внимательно рассмотрев приведенный фрагмент, вы могли сказать, в каком случае он

будет работать неправильно. Свойства связанных списков

Связанные списки имеют все те преимущества, которых нет у массивов. Связанные списки могут удлиняться и укорачиваться по мере добавления или удаления элементов. Добавление объекта в середину списка выполняется легко и быстро - при этом нет необходимости перемещать существующие элементы. Кроме того, сортировка элементов в связанном списке проводится гораздо быстрее, чем в массиве элементов.

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

Jlfiotfuuuta £iHked£lst2)ata

Программа использует связанный список для хранения списка

объектов, содержащих имена студентов и их номера социальпого страхования.

LinkedListData - хранит имена студентов

в связанном списке объектов

#include <stdiD.h>

ttinclude <io3tream.li>

Iinciude <string.h>

/ ataSet - содержит имена и номера социального страхования

class NameDataSet

public:

char szFirstName[128]; char szLastName [128]; int nSocialSecurity;

связь со следующим элементом списка NameDataSet* pNext;

указатель на первый элемент списка NameDataSet* pHead = 0;

addTail - добавляет новый элемент в связанный список void addTail(NameDataSet* pNDS)

сразу же обнулим указатель на следующий элемент, поскольку этот элемент будет последним в списке pNDS->pNext = 0;

если список пуст,

то головной указатель должен будет

указывать на вставляемый элемент if (pHead == 0)

pHead = pNDS; return;

если список не пуст, найдем последний элемент списка NameDataSet* pCurrent = pHead; while(pCurrent->pNextJ

pCurrent = pCurrent->pNext;

добавим текущий элемент к кон списка pCurrent->pNext = pNDS;

Data - считывает и номер социального

страхования; возвращает ноль,

если больше нечего считывать

NameDataSet* getData ()

создаем новый объект для заполнения NameDataSet* pNDS = new NameDataSet;

считаем имя

cout ХпВведите имя: ;

cin pND3->szFirstName;

если в поле имени введено

if ((stricmp(pNDS->3zFirstName, exit ) == 0))

...уничтожить еще пустой объект... delete pNDS;

, . .и вернуть ноль, чтобы прервать цикл ввода return 0;

считаем оставшиеся члены cout Введите фамилию: ; cin pNDS->3zLastName;

cout Введите номер социального страхования: ; cin pNDS->nSocialSecurity;

обнулим указатель на следующий элемент pND£->pNe;<t = 0;

нем адрес созданного объекта

return pNDS;

выводим один экземпляр класса NameDataSet

void displayData(NameDataSet* pNDS)

cout; pNDS->szFirstNam.e

pNDS->szLastName