Программа, которая создает очередь символов.
#include<iostream>
#include<iomanip>
#include<math.h>
#include<conio.h>
#include<String.h>
#include<ctype.h>
#include <stdlib.h>
#include<windows.h>
using namespace std;
// структура, которая описывает один узел:
struct Node
{
char data; // элемент данных
Node* next; // указатель на следующий узел
};
int main()
{
if(SetConsoleCP(1251)==0)
{
cerr<<"Fialed to set codepage!"<<endl;
}
if(SetConsoleOutputCP(1251)==0)
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
// Указатели на первый, текущий и предыдущий узел:
Node *firstPt=NULL, *token=NULL, *prev=NULL;
cout<<"Введите строку символов \n";
char ch, flag=1;
// создаем очередь:
do
{
ch = _getche(); // считываем символ с клавиатуры
token = new Node; // выделяем место под текущий узел
token->data = ch; // записываем элемент данных
token->next = NULL; // указатель на следующий элемент равен 0
if (flag) // если создан первый узел
{
firstPt = token; flag = 0; // запоминаем его адрес
}
else prev -> next = token;
// в противном случае запоминаем в ранее созданном узле адрес нового узла
prev = token; // текущий узел становится предидущим
} while (ch != '\r'); // пока не будет нажата клавиша <Enter>
cout<<endl;
//Вывод:
cout <<"Очередь:\n";
token = firstPt; // адрес первого узла
while (token) // пока указатель на текущий узел не равен 0
{
cout<<token -> data; // выводим элемент данных
token = token->next; // переходим к следующему узлу
}
cout <<endl;
_getch();
return 0;
}
Программа, которая создает закольцованный список и затем последовательно удаляет из списка каждый m-й элемент до тех пор, пока не будут удалены все.
#include<iostream>
#include<iomanip>
#include<conio.h>
#include<String.h>
#include<ctype.h>
#include<stdlib.h>
#include<windows.h>
using namespace std;
// структура, которая описывает один узел:
struct Node
{
int num;
Node* ptr;
};
// функция, которая добавляет 1 элемент в список:
void Add(Node*& pLast, int i)
/* первый параметр – ссылка на указатель, который будет хранить адрес последнего добавленного элемента, второй параметр – значение элемента данных, которое будет записано в этот узел */
{
Node* pNext = new Node; // выделяем место под новый узел
if (pLast) pLast -> ptr = pNext;
// если предыдущий узел существует, подсоединяем новый узел к предыдущему
pNext -> num = i; // записываем элемент данных
pNext -> ptr = NULL;
// указатель, записанный в последнем узле пока никуда не указывает
pLast = pNext; // новый узел становится последним
}
// -----------------------------------------------------------
// функция, которая удаляет узел с номером m:
int Del(Node*& pToken, int m)
// первый параметр – адрес текущего узла
{
int n; // элемент данных из удаляемого узла
if (pToken->ptr != pToken) // если узел - не единственный
{
// Отсчет:
for (int i = 1; i < m; i++)
pToken = pToken->ptr; // переходим к следующему узлу
//Адрес удаляемого элемента:
Node* tmp = pToken->ptr;
n = tmp->num; // запоминаем значение элемента данных
pToken->ptr = tmp->ptr;
// запоминаем в узле перед удаляемым адрес узла, который расположен за удаляемым
delete tmp; // удаляем узел
}
else // если узел – единственный, просто удаляем его
{
n = pToken -> num;
delete pToken;
pToken = NULL;
}
return n;
}
//------------------------------------------------------------
int main()
{
if(SetConsoleCP(1251)==0)
{
cerr<<"Fialed to set codepage!"<<endl;
}
if(SetConsoleOutputCP(1251)==0)
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
do
{
int n, m;
do
{
cout << "Задайте начальное количество элементов >=1 --> ";
cin >> n;
} while (n < 1);
do
{
cout << "Задайте номер удаляемого элемента от 1 до "<< n << " --> ";
cin >> m;
} while ( m < 1 || m > n);
// Указатели на начало и конец списка:
Node *pBegin = NULL, pLast = NULL;
//Формирование списка:
for (int i = 1; i <= n; i++)
{
Add(pLast, i);
if (i == 1) pBegin = pLast;
}
// Закольцуем список:
pLast->ptr = pBegin;
//Занимаем начальную позицию:
Node* pToken = pLast;
// Удаление:
do
{
cout<<"" << Del(pToken, m) << ' ';
} while (pToken);
cout << endl;
cout << "\nНажмите любую клавишу\n";
} while (_getch()!=27);
return 0;
}