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

Преминах в ситуация, в която трябваше да внедря структура от данни тип опашка. Това е така:

(1) Да предположим, че има масив data[50]= {1,2,3,4,5,6};

(2) int Front трябва да сочи към първия индекс, а int rear трябва да сочи към последния индекс.

(3) Сега трябва да добавя първи и втори елемент от този масив. Да предположим, че правя това (i+2=3) и това 3 ще бъде зададено най-накрая чрез rear+1 (data[rear+1]), Сега, когато се случи второто изпълнение, не трябва да вземаме предвид първите два елемента (те вече са добавени), така че в този случай можем да направим data[front+2]. Но обърнете внимание тук, моля, защото това +2 ще бъде направено само за първи път, след това ще бъде само +1 (тъй като добавихме само един елемент, а за първи път добавихме 2 елемента) .И елементът, получен при добавяне, трябва да отиде на последно място в индекса като полученото "3" ще отиде най-накрая като това {1,2,3,4,5,6,3}.

(4) Така че трябва да вземем предвид

(4.a) Увеличаване на задната част с едно при всяко добавяне.

(4.b) Увеличаване на фронта с един (приемете първото добавяне, където добавяме два елемента).

(5) Идеята ми да направя това е следната:

    #include <stdio.h>
    #define MAX 50
    int data[MAX];
    int rear = - 1;
    int front = - 1;

    void main()
    {
     int rear=6, front=0;
     data[size]={1,2,3,4,5,6};
     int count=size;
     //First do addition of the first two elements
     data[rear]= data[0]+data[1];
     for(i=front; i<size*2-1 ; i++) //we are doing data*2-1 because we know the final obtained on doing all the addition until there is 1 element will have the size (size*2-1).
      {
       do
        { 
         //here we do addition data[rear+1]=data[front]+data[rear];
         // rear++;     
         count--;
        }while (count>1);
       }
      for(i=0; i<size*2-1 ; i++)
      {
       printf("%d ", data[i]); //Now this must print "1,2,3,4,5,6,3,6,9,12,21" (addition of element at front and rear)
      }         

    }

**Моето съмнение е как да увелича фронта с две добавяния за първи път и чрез увеличаване с един след първото добавяне, така че първият винаги да сочи към елемента, който трябва да се добави (увеличаването не е трудно, направих го). Моля, помогнете ми за предното увеличение, Алгоритъмът и кодът ще са много благодарни.


c arrays queue algorithm data-structures
person user3206225    schedule 06.02.2014    source източник
comment
Няма size и има множество начини за справяне с проблемите с откриването на пълно срещу празно в кръгов буфер. Някои от тях тук.   -  person WhozCraig    schedule 06.02.2014
comment
@WhozCraig съжалявам, че все още не мога да разбера какво казахте току-що. Бихте ли ми обяснили подробно.   -  person user3206225    schedule 06.02.2014

Отговори (2)


arrow_upward
1
arrow_downward 

int max = 50;
int index = 0;
int endIndex = 5; //You can compute the length. I will just hard code
int list[max] = {1,2,3,4,5,6};
int front = list[index];
int rear = list[endIndex];

while (index!= endIndex) 
{
if (index==0)
{
        index++;
        list[endIndex+index] = front+list[index];
        rear = list[endIndex+index];
        index++;
        front = list[index];
}
else 
{
        list[rear+1] = front + rear;
        index++;
        front = list[index];
        rear = list[endIndex+index];
}
}

Това трябва да прави това, което търсите. Не съм го тествал, но вярвам, че е това, което описахте.

person Alex Johnson    schedule 06.02.2014
comment
Благодаря, че се опитахте да ми помогнете, но вашият код ще даде изход 3,4,5,6,0,0,0,0,0.... но изходът на желанието е 1,2,3,4,5,6 ,3,6,10,15,21 (така че не мога да го маркирам правилно за момента). Моля, помогнете :), мисля, че трябва да използваме указатели, защото начинът, по който казвате, ще загуби първите два елемента в окончателен списък [размер]; (Имам предвид, че няма да показва и 1 и 2). Но трябва да ги покажа, когато отпечатам списъка [размер], но те не трябва да участват в допълнение, ако се добавят веднъж. (Имам предвид, че ако 1+2=3, тези 3 отиват накрая като 1234563, тогава предната част трябва да сочи към 3, за да добавите с 3-те най-накрая) - person user3206225; 06.02.2014
comment
и този списък Sizeof ще даде размера на целия масив (а не броя на елементите), но не се притеснявайте, мога да коригирам това. Но проблемът е това, което споменах в първия коментар, моля, опитайте да ми помогнете в това. Благодаря - person user3206225; 06.02.2014
comment
Редактирах предишното си изпращане. Съжалявам за закъснението. Имах някои грешки с някои от моите променливи, така че извадих една и твърдо кодирах дължината на масива. Вижте дали това може да реши проблемите ви. - person Alex Johnson; 06.02.2014
comment
резултатът от този код е { 1 0 3 4 6 6 0 0 0 0 0 0 }, все още не е правилен :) - person user3206225; 06.02.2014
comment
Най-накрая го направих, можете да видите по-долу пълния ми код. И благодаря, че се опитахте да ми помогнете. - person user3206225; 07.02.2014

arrow_upward
1
arrow_downward

Най-накрая успях да реша въпроса, оставям тук моя код за други (ако го използват в бъдеще):

#include <stdio.h>

void main()
{
int max = 50;
int index = 0,Front=0,Rear,min,min2,location,i,location2,flag[30],check=0,j;

int data[50] = {1,2,3,4};
 Rear=3;
//Rear=size-1
for(i=0; i<=Rear;i++)
{
flag[i]=0;
 //printf("");
 }
int count=Rear;
do
{
//printf("check5 \n ");
if(Front==0)
 {
printf("check1 \n ");

Rear++;
 data[Rear]=data[Front] +data[1];
    flag[Front]=1;
    flag[Rear]=0;
        flag[1]=1;
 printf("datafront: %d\n ", data[Front]);
  printf("*****************dataRear: %d\n ", data[Rear]);
 printf("Front : %d\n ", Front);
printf("Rear : %d \n", Rear);
 //printf("flagRear: %d\n ", flag[Front]);
Front=Front+2; 
//Rear++;
 }

   if(data[Front]==data[Rear] && flag[Rear] ==0 && flag[Front]==0 ) 
 { 
    printf("check3 \n ");
     printf("Front : %d\n ", Front);
    // Rear++;
printf("Rear : %d \n", Rear);
printf("dataFront1: %d\n ", data[Front]);
printf("dataRear1: %d\n ", data[Rear]);
    data[Rear+1]= data[Front] +data[Rear];
    printf("************dataRear[Rear+1]: %d\n ", data[Rear+1]);
    flag[Front]=1;
    flag[Rear]=1;
    flag[Rear+1]=0;
    printf("check Front front : %d\n", Front);
                for(j=Front+1;j<=Rear;j++)
                {
                if(flag[j]==0)
                {
                Front=j;    
                 break;             
                }
                }           
//  Front++; 
    Rear++;
}

  if(data[Front]<data[Rear] && flag[Rear] ==0 && flag[Front]==0) 
   {         
         printf("check4 \n ");   
                 printf("Front : %d\n ", Front);
printf("Rear : %d \n", Rear);
printf("dataFront1: %d\n ", data[Front]);
printf("dataRear1: %d\n ", data[Rear]);
 printf("Flagcheck data[6].flag : %d \n",flag[6]);
                int start= Front+2;
                min= data[Front];
                for(j=Front+1;j<=Rear;j++)
                {
                if(flag[j]==0)
                {
                min2=data[j];
                location2=j;
                printf("j = %d \n",j);
                break;
                }
                }
                location=Front;

                 for(i=start;i<=Rear;i++) 
                {
                    if (data[i] <min && flag[i]==0) 
                    {
                        min=data[i];
                        location=i;     
                        min2=min;   
                    }
                    if (data[i]<min2&& flag[i]==0) 
                    {
                        min2=data[i];
                        location2=i;
                    }       
                }
                data[Rear+1]= min2+min; 
                printf("min= %d\n", min);
                printf("min2= %d\n", min2);
                printf("location= %d\n", location);
                printf("location2= %d\n", location2);
                printf(" ***********data[Rear+1] = %d\n", data[Rear+1]);
                flag[location2]=1;
                flag[location]=1;
                flag[Rear+1]=0;

                for(j=location+1;j<=Rear;j++)
                {
                if(flag[j]==0)
                {
                Front=j;    
                 break;             
                }
                }           
                Rear=Rear+1;                
 printf("Front : %d\n ", Front);
printf("Rear : %d \n", Rear);
 }  
//printf("\n");
//printf("Front : %d\n ", data[Front]);
//printf("Rear : %d \n", data[Rear]);
count--;
} while(Front!=Rear && count>0);
for (i=0;i<15;i++)
{
 printf(" %d  ", data[i]);
}
//char path[100]={'\0'};
//traverse_tree(data, 10,path);
printf("\n");
}
////
person user3206225    schedule 07.02.2014