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

Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...

Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...

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

2017-07-01 200
InsertAfter - присоединяет новый узел после текущего. 0.00 из 5.00 0 оценок
Заказать работу

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

}

}

 


Поделиться с друзьями:

Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...

Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...

Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...

Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...



© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.025 с.