Добре дошли!

Добре дошли в нашите форуми, пълни с полезна информация. Имате проблем с компютъра или телефона си? Публикувайте нова тема и ще намерите решение на всичките си проблеми. Общувайте свободно и открийте безброй нови приятели.

Моля, регистрирайте се за да публикувате тема и да получите пълен достъп до всички функции.

Задача

Нова тема

22 март 20188 г.

Здравейте ! Нужна ми е малко помощ със следната задача

struct elem
{
int key;
elem *next;
} *l=NULL , *r=NULL;

int pop_l(int &n)
{
   elem *p;
   if(l)
   {
       elem *p=l;
       n=l->key;
       l=l->next;
       delete p;
       if(l==NULL)
           r=NULL;
       return 1; }
   else
       return 0;
}

int pop_r(int &n)
{
   elem *p;
if(r)
   { n=r->key;
   if(l==r)
   {
       delete r;
       l=r=NULL; }
   else
   { p=l;
   while(p->next!=r)
       p=p->next;
   p->next=NULL;
   delete r;
   r=p; }
   return 1; }
   else
       return 0;
}

Цитирай

25 март 20188 г.

Форматирай кода с тагове code. Не мисля, че pop_x ще свърши работа, защото той премахва, а ти трябва да проверяваш кои ключове изпълняват условието

е->key % key == 0

Ако попваш всеки кей после трябва да го връщаш, ако не го удовлетворява. Просто напиши във функцията обхождане от l до r и премахваш тези, които удовлетворят условието.

ПС: Нямам престава защо форумът слага '>' след таг code.

Цитирай

25 март 20188 г.

#include <stdio.h>
#include <stdlib.h>

typedef struct nod
{
	int data;
	struct nod* next;
	struct nod* previous;
}node, *Node;

typedef struct deq
{
	Node front;
	Node back;
	int size;
}deque, *Deque;


Deque dequeConstruct()
{
	Deque a;
	a = (Deque)malloc(sizeof(deque));
	a->front = 0;
	a->back = 0;
	a->size = 0;
	return a;
}

void dequeDestruct(Deque a)
{
	Node c = a->front;
	Node d = c;
	while (a->size != 0)
	{
		d = d->next;
		free(c);
		a->size--;
		c = d;
	}
	free(a);
}

void dequePushFront(Deque a, int data)
{
	Node b = (Node)malloc(sizeof(node));
	b->data = data;
	b->next = 0;
	b->previous = 0;
	if (a->size == 0)
	{
		a->front = b;
		a->back = b;
		a->size++;
		return;
	}
	b->next = a->front;
	a->front->previous = b;
	a->front = b;
	a->size++;
}

void dequePushBack(Deque a, int data)
{
	Node b = (Node)malloc(sizeof(node));
	b->data = data;
	b->next = 0;
	b->previous = 0;
	if (a->size == 0)
	{
		a->front = b;
		a->back = b;
		a->size++;
		return;
	}
	a->back->next = b;
	b->previous = a->back;
	a->back = b;
	a->size++;
}

int dequePopFront(Deque a, int* isOK)
{
	Node c;
	int answer;
	if (a->size == 0)
	{
		*isOK = 0;
		return 0;
	}
	a->size--;
	*isOK = 1;
	answer = a->front->data;
	c = a->front;
	a->front = a->front->next;
	if (a->size == 0)
	{
		a->back = 0;
		free(c);
		return answer;
	}
	a->front->previous = 0;
	free(c);
	return answer;
}

int dequePopBack(Deque a, int* isOK)
{
	Node c;
	int answer;
	if (a->size == 0)
	{
		*isOK = 0;
		return 0;
	}
	a->size--;
	*isOK = 1;
	answer = a->back->data;
	c = a->back;
	a->back = a->back->previous;
	if (a->size == 0)
	{
		a->front = 0;
		free(c);
		return answer;
	}
	a->back->next = 0;
	free(c);
	return answer;
}

void dequeDeleteDivisibles(Deque a, int k)
{
	if (a->size == 0) return;
	Node c = a->front;
	Node d = c;
	while (c != 0)
	{
		c = c->next;
		if (d->data % k == 0)
		{
			a->size--;
			if (c != 0) c->previous = d->previous;
			if (d == a->front) a->front = c;
			else d->previous->next = c;
			free(d);
		}
		d = c;
	}
	if (a->size == 0) a->back = 0;
}

void dequePrint(Deque a)
{
	Node c = a->front;
	while(c != 0)
	{
		printf("%d ", c->data);
		c = c->next;
	}
}


int main()
{
	Deque a = dequeConstruct();
	for (int i = 1; i < 11; i++)
	{
		dequePushBack(a, i);
	}
	dequeDeleteDivisibles(a, 3);
	dequePrint(a);
	dequeDestruct(a);
	return 0;
}

Със сингъл линк, едната от функциите попбак или попфрант трябва да е с линейна сложност. Не мога да го измисля и двете да са с константна.

Затуй дабъл линк.

Те не, че трябват в случая, ама

Цитирай

25 март 20188 г.

В дек може да имаш само 1 Node, в него има prev и next.

Цитирай

25 март 20188 г.

Може да има един, няколко, а може и въобще да няма николко.

#include <iostream>

#define END -9999999

using namespace std;

struct elem 
{
    int key;
    elem *next;
    elem *prev;
} ;

struct deque
{
    elem *start;
    elem *end;
} ;



void push_front(deque &d, int n)
{
     elem *p=new elem;
     p->key = n;
     p->next = d.start;
     p->prev=NULL;
     if (d.start) d.start->prev=p;
     else d.end=p;
     d.start=p;
}

int pop_front(deque &d)
{
    if (d.start==NULL) return 0;
    elem *p=d.start;
    int n=p->key;
    d.start=p->next;
    if (d.start) d.start->prev=NULL;
    else d.end=NULL;
    delete p;
    return n;
}

void push_back(deque &d, int n)
{
     elem *p=new elem;
     p->key = n;
     p->next= NULL;
     p->prev=d.end;
     if (d.end) d.end->next=p;
     else d.start=p;
     d.end=p;
}

int pop_back(deque &d)
{
    if (d.end==NULL) return 0;
    elem *p=d.end;
    int  n=p->key;
    d.end=p->prev;
    if (d.end) d.end->next=NULL; 
    else d.start=NULL;
    delete p;
    return n;
}

void deletenode(deque &d, int k)
{
     int n;
     push_back(d,END);
     
     while(1)
     {
         n=pop_front(d);
         if (n==END) break;
         if (n%k) push_back(d,n);
     }
}



int main()
{
    deque d={NULL,NULL};
    for (int i=1; i<=20; i++)
    { 
        push_back(d, i);
        cout<<i<<"  ";
    }
    cout<<endl;
    deletenode(d, 3);
    while(d.start)
    {
        cout<<pop_front(d)<<"  ";
    }
    cout<<endl;
}

Цитирай

25 март 20188 г.

То не е и задължително да е с линкед лист.

Може да е и с динамичен масив.

Например въвеждането да започва от средата на масива, а ако се достигне до края или до началото, размера се умножава по две, а данните се ре алокират така, щото да са по средата на новия масив.

Цитирай

27 март 20188 г.

#include <stdio.h>
#include <stdlib.h>

typedef struct
{
	int capacity;
	int size;
	int* array;
	int back;
	int front;
}dequea, *Dequea;

Dequea dequeaConstruct()
{
	Dequea a = (Dequea)malloc(sizeof(dequea));
	a->capacity = 8;
	a->size = 0;
	a->array = (int*)malloc(a->capacity * sizeof(int));
	a->back = 4;
	a->front = 3;
}

void dequeaDestruct(Dequea a)
{
	free(a->array);
	free(a);
}

void dequeaIncrease(Dequea a)
{
	a->capacity = a->capacity << 1;
	int* newarray = (int*)malloc(a->capacity * sizeof(int));
	for (int i = a->front + 1, j = (a->capacity - a->size) / 2; i < a->back; i++, j++)
	{
		newarray[j] = a->array[i];
	}
	a->front = (a->capacity - a->size) / 2 - 1;
	a->back = a->front + a->size + 1;
	free(a->array);
	a->array = newarray;
}

void dequeaPushBack(Dequea a, int data)
{
	if (a->back == a->size)
	{
		dequeaIncrease(a);
	}
	a->array[a->back] = data;
	a->size++;
	a->back++;
}

void dequeaPushFront(Dequea a, int data)
{
	if (a->front < 0)
	{
		dequeaIncrease(a);
	}
	a->array[a->front] = data;
	a->size++;
	a->front--;
}

int dequeaPopBack(Dequea a, int* isOK)
{
	if (a->size < 1)
	{
		*isOK = 0;
		return 0;
	}
	*isOK = 1;
	a->back--;
	a->size--;
	return a->array[a->back];
}

int dequeaPopFront(Dequea a, int* isOK)
{
	if (a->size < 1)
	{
		*isOK = 0;
		return 0;
	}
	*isOK = 1;
	a->front++;
	a->size--;
	return a->array[a->front];
}

void dequeaDeleteDivisibles(Dequea a, int k)
{
	if (a->size == 0) return;
	int i, j;
	for (i = a->front + 1, j = i; i < a->back; i++, j++)
	{
		if (a->array[i] % k == 0)
		{
			j--;
			continue;
		}
		a->array[j] = a->array[i];
	}
	a->back = j;
	a->size = a->back - a->front - 1;
}

void dequeaPrint(Dequea a)
{
	for (int i = a->front + 1; i < a->back; i++)
	{
		printf("%d ", a->array[i]);
	}
	printf("\n");
}

int main()
{
	Dequea a = dequeaConstruct();
	for (int i = 10; i >=1; i--)
	{
		dequeaPushFront(a, i);
	}
	for (int i = 11; i < 21; i++)
	{
		dequeaPushBack(a, i);
	}
	dequeaDeleteDivisibles(a, 3);
	dequeaPrint(a);
	dequeaDestruct(a);
}

Имплементация с динамичен масив

Цитирай

Архивирана тема

Темата е твърде стара и е архивирана. Не можете да добавяте нови отговори в нея, но винаги можете да публикувате нова тема, в която да продължи дискусията. Регистрирайте се или влезте във вашия профил за да публикувате нова тема.