Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Топ:
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Интересное:
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Дисциплины:
2017-07-01 | 199 |
5.00
из
|
Заказать работу |
|
|
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 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!