InsertAfter - присоединяет новый узел после текущего.

InsertAfter - присоединяет новый узел после текущего. - student2.ru

DeleteAfter – удаляет узел, следующий за текущим.

InsertAfter - присоединяет новый узел после текущего. - student2.ru

Листинг 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 InsertAfter - присоединяет новый узел после текущего. - student2.ru

// вставка элемента в начало списка

template <class T>

void InsertFront(Node<T>* & head, T item)

{

// создание нового узла, чтобы он указывал на

// первоначальную голову списка

// изменение головы списка

head = GetNode (item, head);

}

InsertRear

InsertAfter - присоединяет новый узел после текущего. - student2.ru

//Вставка узла: 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

InsertAfter - присоединяет новый узел после текущего. - student2.ru

// удалить первый узел списка

template <class T>

void DeleteFront(Node<T>* & head)

{

// сохранить адрес удаляемого узла

Node<T> *p = head;

// убедиться в том, что список не пуст

if (head != 0)

{

// передвинуть голову к следующему узлу и удалить оригинал

head = head->NextNode();

delete p;

}

}

Delete

InsertAfter - присоединяет новый узел после текущего. - student2.ru

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();

}

}

Наши рекомендации