Зацикливание программы. В чем проблема?

@Artishok · Регистрация: 27.12.2009

Author24 — интернет-сервис помощи студентам

дек через массив реализация.
работает все кроме функции pop_front.на ней происходит зацикливание программы. в чем проблема?

C

#include <iostream>
#define maxn 1000
 
using namespace std;
 
typedef struct
{
    int dh,dt;
    int val[maxn];
} deque;
 
void push_front(deque *d, int x)
{
if (d->dh<1) d->dh +=maxn; //chtob ukazateli ne bili menshe null
 d->val[(--d->dh)%maxn]=x;
}
 
void push_back(deque *d,int x)
{
    d->val[(d->dt++)%maxn]=x;
}
 
int pop_front(deque *d)
{
    return d->val[(d->dh++)%maxn]; //зацикливается в этой функции.
}
 
int pop_back(deque *d)
{
    if (d->dt<1) d->dt +=maxn;
    return d->val[(--d->dt)%maxn];
}
int main()
{
    deque a;
    int dlen;
    if (a.dt>a.dh) dlen=(a.dt-a.dh)%maxn;
    else dlen=maxn-(a.dh-a.dt)%maxn;
    a.dt=0;
    a.dh=0;
    push_back(&a,10);
    push_back(&a,15);
    push_back(&a,56);
    push_back(&a,34);
    push_back(&a,30);
    push_back(&a,23);
    push_back(&a,40);
    //push_front(&a,15); 
    while (a.dh !=a.dt-3) //proverki
    {
        std::cout<<pop_front(&a)<<endl;
    }
    std::cout<<"etap 2"<<endl;
    if (a.dh==a.dt) std::cout<<"finita"<<endl; 
    else                            //nebolshaia proverka raboti
    {
    while (a.dh !=a.dt)
    {
        std::cout<<pop_front(&a)<<std::endl;
    }
    }
    if (a.dh==a.dt) std::cout<<"finita"<<endl;
    return 0;
}

@Chainyk · 26.09.2010, 23:43

Сообщение от Artishok

(--d->dh)

Вот в етом выражении сначала будет сделан декремент, а потом доступ к полю переменной d. Если нужно сделать декремент dh, то нужно добавить скобки

@Artishok · 26.09.2010, 23:46 **[ТС]**

куда?

все равно зацикливается.
ну функция эта.я в коде коммент не там написал

@PointsEqual · 26.09.2010, 23:48

C++

1	((--d)->dh)

@Artishok · 26.09.2010, 23:51 **[ТС]**

все равно зацикливается

@Chainyk · 27.09.2010, 00:29

Какой компилятор стоит? У меня на ВизуалСтудио 2008 здесь:

C++

if (a.dt>a.dh) dlen=(a.dt-a.dh)%maxn;
        else dlen=maxn-(a.dh-a.dt)%maxn;
        a.dt=0;
        a.dh=0;

ошыбка времени выполнения (использование неинициал. данных). Поменял вот так, все в пошаговом сделал до ретурн 0, нет зацыкливания:

C++

#include <iostream>
#define maxn 1000
 
using namespace std;
 
typedef struct
{
        int dh,dt;
        int val[maxn];
} deque;
 
void push_front(deque *d, int x)
{
if (d->dh<1) d->dh +=maxn; //chtob ukazateli ne bili menshe null
 d->val[(--d->dh)%maxn]=x;
}
 
void push_back(deque *d,int x)
{
        d->val[(d->dt++)%maxn]=x;
}
 
int pop_front(deque *d)
{
        return d->val[(d->dh++)%maxn]; //зацикливается в этой функции.
}
 
int pop_back(deque *d)
{
        if (d->dt<1) d->dt +=maxn;
        return d->val[(--d->dt)%maxn];
}
 
 
int _tmain(int argc, _TCHAR* argv[])
{
    deque a;
        int dlen;
        a.dt=0;
        a.dh=0;
        if (a.dt>a.dh) dlen=(a.dt-a.dh)%maxn;
        else dlen=maxn-(a.dh-a.dt)%maxn;
        push_back(&a,10);
        push_back(&a,15);
        push_back(&a,56);
        push_back(&a,34);
        push_back(&a,30);
        push_back(&a,23);
        push_back(&a,40);
        //push_front(&a,15); 
        while (a.dh !=a.dt-3) //proverki
        {
                std::cout<<pop_front(&a)<<endl;
        }
        std::cout<<"etap 2"<<endl;
        if (a.dh==a.dt) std::cout<<"finita"<<endl; 
        else                            //nebolshaia proverka raboti
        {
        while (a.dh !=a.dt)
        {
                std::cout<<pop_front(&a)<<std::endl;
        }
        }
        if (a.dh==a.dt) std::cout<<"finita"<<endl;
        return 0;
}

Но если нужно реализовать двустороннюю очередь, то лучше з оператором NEW и указателями, а то сейчас есть массив к которому применяються непонятные функции

@Artishok · 27.09.2010, 00:32 **[ТС]**

C++

1	push_front(&a,15);

вот здесь зацикливание.просто оно комментарием выделено

Сообщение от Chainyk

Какой компилятор стоит?

c-free

@Chainyk · 27.09.2010, 01:01

Вот так:

C++

#include <iostream>
#define maxn 1000
 
using namespace std;
 
typedef struct
{
        int dh,dt;
        int val[maxn];
} deque;
 
void push_front(deque *d, int x)
{
if (d->dh<1) d->dh +=maxn; //chtob ukazateli ne bili menshe null
 d->val[(--d->dh)%maxn]=x;
}
 
void push_back(deque *d,int x)
{
        d->val[(d->dt++)%maxn]=x;
}
 
int pop_front(deque *d) 
{
    int temp = d->dh++;
    if (d->dh==1000)
        d->dh=0;
        return d->val[temp%maxn]; //зацикливается в этой функции.
}
 
int pop_back(deque *d)
{
        if (d->dt<1) d->dt +=maxn;
        return d->val[(--d->dt)%maxn];
}
 
 
int _tmain(int argc, _TCHAR* argv[])
{
    deque a;
        int dlen;
        a.dt=0;
        a.dh=0;
        if (a.dt>a.dh) dlen=(a.dt-a.dh)%maxn;
        else dlen=maxn-(a.dh-a.dt)%maxn;
        push_back(&a,10);
        push_back(&a,15);
        push_back(&a,56);
        push_back(&a,34);
        push_back(&a,30);
        push_back(&a,23);
        push_back(&a,40);
        push_front(&a,15); 
        while (a.dh !=a.dt-3) //proverki
        {
                std::cout<<pop_front(&a)<<endl;
        }
        std::cout<<"etap 2"<<endl;
        if (a.dh==a.dt) std::cout<<"finita"<<endl; 
        else                            //nebolshaia proverka raboti
        {
        while (a.dh !=a.dt)
        {
                std::cout<<pop_front(&a)<<std::endl;
        }
        }
        if (a.dh==a.dt) std::cout<<"finita"<<endl;
        return 0;
}

У Вас указатель на голову очереди уходил 1001,1002. Двунаправленную очередь лучше реализовывать с динамическим выделением памяти и указателями

@Artishok · 27.09.2010, 01:07 **[ТС]**

Сообщение от Chainyk

динамическим выделением памяти и указателями

это и так ясно.но задание было именно с массивами
да все работает.
значит все-таки в pop_front было зацикливание....

@Chainyk · 27.09.2010, 01:19

Я имею ввиду вот что:

C++

typedef struct deque
{
        int data;
        deque *prev;
        deque *next;
        deque *head;
        deque *tail;
};
 
typedef deque DQ;
 
deque* Init (int n)
{
    DQ *temp = new DQ;
    temp->data = n;
    temp->prev=temp->next=NULL;
    temp->head=temp->tail=temp;
    return temp;
}
 
deque* push_back (int n, deque *rhs)
{
    DQ *tmp = new DQ;
    tmp->data=n;
    tmp->prev=rhs;
    tmp->next=NULL;
    tmp->tail=tmp;
    tmp->head=rhs->head;
    return tmp;
}
 
int _tmain(int argc, _TCHAR* argv[])
{
    DQ *dq;
    dq = Init(3);
    dq = push_back(4,dq->tail);
    return 0;
}

Здесь не все функции (нужно для обоих концов push и pop и проверку на пустоту), ето пример. Хотя и ето не очень, я на 2-ом курсе как то иначе делал... Если делать с массивами, тогда зачем структура? Можно и попроще

@Artishok · 27.09.2010, 01:27 **[ТС]**

вообще-то надо было это сделать на паскале но я хотел тренировать си
можно конечно обойтись и без структуры но в таком случае это будет больше похоже на обычный массив где элементы не имеют полей

@Artishok ЧакЭ одобряЭ 285 / 284 / 86 Регистрация: 27.12.2009 Сообщений: 1,767
	27.09.2010, 01:27 [ТС]	11
	вообще-то надо было это сделать на паскале но я хотел тренировать си можно конечно обойтись и без структуры но в таком случае это будет больше похоже на обычный массив где элементы не имеют полей 0

@Chainyk 15 / 15 / 2 Регистрация: 24.08.2010 Сообщений: 94
	26.09.2010, 23:43	2
	Сообщение от Artishok (--d->dh) Вот в етом выражении сначала будет сделан декремент, а потом доступ к полю переменной d. Если нужно сделать декремент dh, то нужно добавить скобки 1

@Artishok ЧакЭ одобряЭ 285 / 284 / 86 Регистрация: 27.12.2009 Сообщений: 1,767
	26.09.2010, 23:46 [ТС]	3
	куда? все равно зацикливается. ну функция эта.я в коде коммент не там написал 0

@Artishok ЧакЭ одобряЭ 285 / 284 / 86 Регистрация: 27.12.2009 Сообщений: 1,767
	26.09.2010, 23:51 [ТС]	5
	все равно зацикливается 0

@Artishok ЧакЭ одобряЭ 285 / 284 / 86 Регистрация: 27.12.2009 Сообщений: 1,767
	27.09.2010, 01:07 [ТС]	9
	Сообщение от Chainyk динамическим выделением памяти и указателями это и так ясно.но задание было именно с массивами да все работает. значит все-таки в pop_front было зацикливание.... 0