InsertAfter - присоединяет новый узел после текущего.
DeleteAfter – удаляет узел, следующий за текущим.
Листинг 11 Односвязные списки
Класс Node
#pragma once
template <class T>
class Node
{
private:
// next указывает на адрес
// следующего узла
Node<T> *next;
public:
// открытые данные
T data;
// конструктор
Node (const T& item, Node<T>* ptrnext = 0) : data(item), next(ptrnext){}
// методы модификации списка
void InsertAfter(Node<T> *p);
Node<T> *DeleteAfter();
// получение адреса следующего узла
Node<T> *NextNode() const { return next; }
};
// вставить узел р после текущего узла
template <class T>
void Node<T>::InsertAfter(Node<T> *p)
{
// p указывает на следующий за текущим узел,
// а текущий узел — на р.
p->next = next;
next = p;
}
// удалить узел, следующий за текущим, и возвратить его адрес
template <class T>
Node<T> *Node<T>::DeleteAfter()
{
// сохранить адрес удаляемого узла
Node<T> *tempPtr = next;
// если нет следующего узла, возвратить NULL
if (next == 0)
return 0;
// текущий узел указывает на узел, следующий за tempPtr.
next = tempPtr->next;
// возвратить указатель на несвязанный узел
return tempPtr;
}
Функции: NodeLib
//Создание узла
// выделение узла с данным-членом item и указателем nextPtr
template <class T>
Node<T> *GetNode(const T& item, Node<T> *nextPtr = 0)
{
Node<T> *newNode;
// выделение памяти при передаче item и NextPtr конструктору.
// завершение программы, если выделение памяти неудачно
newNode = new Node<T>(item, nextPtr);
if (newNode == 0){
cerr << "Ошибка выделения памяти!" << endl;
exit(1);
}
return newNode;
}
InsertFront
// вставка элемента в начало списка
template <class T>
void InsertFront(Node<T>* & head, T item)
{
// создание нового узла, чтобы он указывал на
// первоначальную голову списка
// изменение головы списка
head = GetNode (item, head);
}
InsertRear
//Вставка узла: InsertRear
template <class T>
void InsertRear(Node<T>* & head, const T& item)
{
Node<T> *newNode, *currPtr = head;
// если список пуст, вставить item в начало
if (currPtr == 0)
InsertFront(head,item) ;
else
{
// найти узел с нулевым указателем
while(currPtr->NextNode() != 0)
currPtr = currPtr->NextNode();
// создать узел и вставить в конец списка
// (после currPtr)
newNode = GetNode(item);
currPtr->InsertAfter(newNode);
}
}
Программа:
В этой программе беспорядочно смешиваются буквы слова для создания слова-путаницы. Процесс сканирует каждый символ в строке и произвольно помещает его либо в начало, либо в хвост списка.
#include <iostream>
#include <string>
#include <cstdlib>
#include "nodelib.h"
#include "node.h"
int main()
{
// список узлов для символов головоломки (Jumbled)
Node<char> *jumbleword = 0;
// входная строка, генератор случайных чисел, счетчики
string s;
int i, j;
// ввести четыре строки
for (i - 0; i < 4; i++)
{
cin >> s;
// использование Random(2) для определения направления движения
// символа:в начало (value <<0), или в конец (value << 1) списка
for (j = 0; j < s.length() ; j++)
if (rand()%2)
InsertRear(jumbleword, s[j]);
else
InsertFront(jumbleword, s[j]);
// печать входной строки и ее перепутанного варианта
cout << "String/Jumble:" << s << " ";
PrintList(jumbleword);
cout << endl << endl;
ClearList (jumbleword);
}
}
DeleteFront
// удалить первый узел списка
template <class T>
void DeleteFront(Node<T>* & head)
{
// сохранить адрес удаляемого узла
Node<T> *p = head;
// убедиться в том, что список не пуст
if (head != 0)
{
// передвинуть голову к следующему узлу и удалить оригинал
head = head->NextNode();
delete p;
}
}
Delete
template <class T>
void Delete (Node<T>* & head, T key)
{
Node<T> *currPtr = head, *prevPtr = 0;
// завершить функцию, если список пустой
if (currPtr == 0)
return;
// прохождение по списку до совпадения с ключем или до конца
while (currPtr != 0 && currPtr->data != key)
{
prevPtr * currPtr;
currPtr = currPtr->NextNode();
}
// если currPtr не равно 0, ключ в currPtr.
if (currPtr != 0)
{
// prevPtr == 0 означает совпадение в начале списка
if(prevPtr == 0)
head = head->NextNode();
else
// совпадение во втором или последующем узле
// prevPtr->DeleteAfter() отсоединяет этот узел
prevPtr->DeleteAfter();
// удаление узла
delete currPtr;
}
}
PrintList
enum AppendNewline {noNewline,addNewline};
// печать связанного списка
template <class T>
void PrintList(Node<T> *head, AppendNewline addnl = noNewline)
{
// currPtr пробегает по списку, начиная с головы
Node<T> *currPtr = head;
// пока не конец списка, печатать значение данных
// текущего узла
while(currPtr != 0)
{
if(addnl == addNewline)
cout << currPtr->data << endl;
else
cout << currPtr->data << " ";
// перейти к следующему узлу
currPtr = currPtr->NextNode();
}
}