есть у меня программа реализации дека, но в ней присутствуют ссылки на следующий и предыдущий элемент (двусвязный), помогите сделать так, чтобы дек был односвязным, т.е. указатель был только на следующий (правый) элемент дека
суть дека: добавление/удаление элементов с правого/левого конца
спасибо
#include "stdafx.h"
#include <iostream>
#include <clocale>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <string>
using namespace std;
typedef int ValueType;
typedef struct Node {
ValueType value;
struct Node *prev;
struct Node *next;
} Node;
typedef struct {
Node *start;
Node *end;
size_t size;
} Deque;
Deque *DequeNew(Deque *deque) {
deque->start = NULL;
deque->end = NULL;
deque->size = 0;
return deque;
}
Deque *DequeDelete(Deque *deque) {
while (deque->start != NULL) {
Node *next = deque->start->next;
free(deque->start);
deque->start = next;
}
deque->start = deque->end = NULL;
deque->size = 0;
return deque;
}
void DequePushBack(Deque *deque, ValueType value) {
Node *node = (Node*)malloc(sizeof(Node));
node->value = value;
node->next = node->prev = NULL;
if (deque->start == NULL) {
deque->end = deque->start = node;
} else {
deque->end->next = node;
node->prev = deque->end;
deque->end = node;
}
++deque->size;
}
ValueType DequePopBack(Deque *deque, int a) {
a=0;
if (deque->size == 0)
{
cout<<"Дек пуст \n";
return a;
exit;
}
else
{
ValueType result = deque->end->value;
Node *prev = deque->end->prev;
free(deque->end);
deque->end = prev;
if (deque->end == NULL)
deque->start = deque->end;
else
deque->end->next = NULL;
--deque->size;
return result;
}
}
void DequePushHead(Deque *deque, ValueType value) {
Node *node = (Node*)malloc(sizeof(Node));
node->value = value;
node->next = node->prev = NULL;
if (deque->start == NULL) {
deque->end = deque->start = node;
} else {
deque->start->prev = node;
node->next = deque->start;
deque->start = node;
}
++deque->size;
}
ValueType DequePopHead(Deque *deque, int a)
{
a=0;
if (deque->size == 0)
{
cout<<"Дек пуст \n";
return a;
exit;
}
else
{
ValueType result = deque->start->value;
Node *next = deque->start->next;
free(deque->start);
deque->start = next;
if (deque->start == NULL)
deque->end = deque->start;
else
deque->start->prev = NULL;
--deque->size;
return result;
}
}
ValueType DequeHead(Deque *deque) {
return deque->start->value;
}
ValueType DequeBack(Deque *deque) {
return deque->end->value;
}
Deque *DequePrint(Deque *deque, const char *format_string,
const char *last_string) {
Node *node;
for (node = deque->start; node != NULL; node = node->next)
printf(format_string, node->value);
printf(last_string);
return deque;
}
ValueType DequeSSS(Deque *deque, int a)
{
a=0;
if (deque->size == 0)
{
cout<<"Дек пуст \n";
return a;
exit;
}
else
{
ValueType result = deque->end->value;
ValueType s = deque->size;
cout<<"Размер дека: \n";
cout<<s;
cout<<" \n";
return result;
}
}
int main(int argc, char **argv) {
int r, pr, lev, size, a, fin,f;
string comm;
string c="command>";
short act;
setlocale(LC_ALL, "Russian_Russia.1251");
//создание пустого дека
Deque deque;
DequeNew(&deque); // que = NULL
cout<<"#Реализация дека с помощью функция free() и malloc() \n"<<endl;
do
{
act=-1;
cout<<c;
cin>>comm;
if (comm=="help")
{
act=1;
cout<<"addr <элемент> - включить элемент справа \n"
<<"addl <элемент> - Включить элемент слева \n "
<<"delr - Исключить элемент справа \n"
<<"dell - Исключить элемент слева \n"
<<"size - размер \n"
<<"exit - Размер дека \n"<<endl;
}
//Добавление справа
if (comm=="addr")
{
act=1;
cin>>lev;
while (!cin.good())
{
cout<<"Введите целое число\n";
cin.clear();
cin.ignore(255, '\n');
cin>>lev;
}
DequePushBack(&deque, lev);
DequePrint(&deque, "%4d", "\n");
}
if (comm=="addl")
{
act=1;
cin>>lev;
while (!cin.good())
{
cout<<"Введите целое число\n";
cin.clear();
cin.ignore(255, '\n');
cin>>lev;
}
DequePushHead(&deque, lev);
DequePrint(&deque, "%4d", "\n");
}
//удаление справа
if (comm=="delr")
{
act=1;
a=1;
DequePopBack(&deque, a);
DequePrint(&deque, "%4d", "\n");
}
//удаление слева
if (comm=="dell")
{
act=1;
a=1;
DequePopHead(&deque,a);
DequePrint(&deque, "%4d", "\n");
}
if (comm=="exit")
{
act=0;
}
if (act<0)
{
cout<<"\""<<comm<<"\" - не является командой\n"
<<"для получение справки по командам введите help \n"<<endl;
}
if (comm=="size")
{
act=1;
DequeSSS(&deque,a);
}
}while(act!=0);
DequeDelete(&deque);
return 0;
}
Просмотр тем