Siemka jestem tu nowy, i na starcie chciałbym się przywitać.
Mam taki problem potrzeba mi algorytm z tablicową implementacja kolejki, tylko że nie wiem jak się za to zabrać.
Przydało by się na blokach ale pseudo kod też powinien wystarczyć.
Więc czekam na jakieś wskazówki.
ZdejmijElement
ZdjetyElement = Kolejka[1]
i = 1
Dopóki i < LiczbaElementow
Kolejka[i] = Kolejka[i+1]
i = i + 1
LiczbaElementow = LiczbaElementow - 1
Pseudokod dla zdejmowania elementów. Elementy w kolejce numerowane są od 1. Trzeba jeszcze dodać sprawdzanie czy kolejce znajduje się co najmniej 1 element
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
typedef struct
{
int *begin,*end,*current,*last;
} Queue;
/* nie wywolywac */
void queue_increment_pointer(Queue* q, int** p)
{
++*p;
if (*p == q->end)
*p = q->begin;
}
Queue* queue_create(int size)
{
Queue* q;
if (size<0)
{
fprintf(stderr,"Negative size of queue!\n");
return NULL;
}
size++;
q = (Queue*)malloc(sizeof(Queue));
q->begin = (int*)malloc(size*sizeof(int));
q->end = q->begin+size;
q->current = q->last = q->begin;
return q;
}
void queue_free(Queue* q)
{
free(q->begin);
free(q);
}
void queue_push(Queue* q, int el)
{
*q->last = el;
queue_increment_pointer(q,&q->last);
if (q->current == q->last)
{
fprintf(stderr,"Queue overflow!\n");
return;
}
}
int queue_pop(Queue* q)
{
int ret;
if (q->current == q->last)
{
fprintf(stderr,"Queue empty!\n");
return -1;
}
ret = *q->current;
queue_increment_pointer(q,&q->current);
return ret;
}
int main()
{
Queue* q = queue_create(5);
queue_push(q,1);
assert(queue_pop(q)==1);
queue_push(q,1);
queue_push(q,2);
queue_push(q,3);
assert(queue_pop(q)==1);
assert(queue_pop(q)==2);
assert(queue_pop(q)==3);
queue_push(q,4);
queue_push(q,5);
queue_push(q,6);
assert(queue_pop(q)==4);
queue_push(q,7);
queue_push(q,8);
queue_push(q,9);
assert(queue_pop(q)==5);
assert(queue_pop(q)==6);
assert(queue_pop(q)==7);
assert(queue_pop(q)==8);
assert(queue_pop(q)==9);
printf("Error test (queue empty):\n");
assert(queue_pop(q)==-1);
printf("No error here:\n");
queue_push(q,4);
queue_push(q,5);
queue_push(q,6);
queue_push(q,4);
queue_push(q,5);
printf("--- end of no error zone ---\n");
printf("Error test (queue overflow):\n");
queue_push(q,6);
queue_free(q);
return 0;
}
Posiedziałem nad tym trochę i napisałem takie coś wzorując się na rożnych przykładach z neta
#include <stdio.h>
#include <stdlib.h>
#include <cstdio>
#define N 5
int main(void)
{
int kolejka[N];
int operacja, add_element, del_element, i;
int glowa=0;
int ogon=0;
int x=1;
while(x==1)
{
printf("1.Badanie\n"
"2.Wstawiania\n"
"3.Usuwanie\n"
"4.Wypisywanie\n"
"5.EXIT\n");
printf("Podaj numer operacji: ");
scanf("%d", &operacja);
switch(operacja)
{
case 1:
if(glowa==ogon)
{
printf("Kolejka pusta\n");
}
else if(ogon>N)
{
printf("Kolejka przepelniona\n");
}
else if(ogon<=N)
{
printf("Istnieja jeszcze wolnie miejsca\n");
}
else if(glowa>ogon)
{
printf("Niedomiar\n");
}
system("pause");
break;
case 2:
if(ogon>N)
{
printf("Kolejka przepelniona");
system("pause");
}
else
{
printf("Podaj element do dodania: ");
scanf("%d", &add_element);
kolejka[ogon]=add_element;
ogon++;
}
break;
case 3:
if(glowa>ogon)
{
printf("Niedomiar");
}
else
{
printf("Elementem usuniętym z kolejki jest %d\n", kolejka[glowa]);
glowa++;
}
system("pause");
break;
case 4:
if(glowa==ogon)
{
printf("Kolejka pusta\n");
}
else
{
printf("Zawartosc kolejki: ");
for(i=glowa; i<ogon; i++)
{
printf("%d ", kolejka[i]);
}
printf("\n");
}
system("pause");
break;
case 5:
x=0;
printf("Zegnamy\n");
system("pause");
break;
default:
printf("Zle wybrany numer operacji\n");
system("pause");
}
system("CLS");
}
return 0;
}
nie wiem tylko dlaczego mi zakańcza program podczas wyświetlania, czyli operacja 4.
system("pause");
Z tym usuwaniem jest ta że jak nawet usunę tego x=0 to i tak powtarza mi ta operacje 3 razy, i to jak wybieram operacje wyświetlania.
no i tak ma robić, skoro po wykonaniu case 4: nie masz break; :)
system("pause"); nie jest funkcją blokującą :)
> pause
bash: pause: command not found
daltego między innymi przestałem moderować na forum. Ile mozna wciąź powtarzać te same błedy. 'pause' jest niczym więcej niż pozostałością dosa. A wystrzy PATH (pod dosem, uniksem/linuksem) podmienć, żeby 'pause' się zmieniło w na przykład w 'del'. NTFS ma symlinki od win 2000 albo i od samego początku, a pod niksami sym/hard-linki z suidem są wbudowane z założenia.
Nigdy. Nigdy nie używa się funkcji system(), jeżeli mozna to samo zaimplementować wewnątrz kodu, bo zbyt wiele elementów zależnych jest od użytkownika, który uruchamia daną aplikację i może ustawić ENV(ironment) (, a za system("pause") powinien byc z automatu ban na forum)
poza tym zwykla ordynarna implementacja FIFO na liście, nawet jednokierunkowej.
ok, sots i klejka w jednym. push() umieszcza na koncu, pop() pobiera z konca a get() z poczatku, ergo:
push+pop -> stos (FILO/LIFO)
push+get -> kolejka (FIFO/LILO)
typedef int atomtype;
struct stos{
atomtype* tab; // atomtype musisz sobie zdefiniować, ty potrzebujesz inta
int wykorzystane; // ilosc wykorzystanych pol w tablicy dynamicznej
int przydzielone; // ilosc rzeczywiscie przydzielonych pol tablicy dynamicznej
};
void push(stos& st,atomtype& atom){ // push - wrzuc atom na stos
// element samokontroli stosu
if(st.wykorzystane==st.przydzielone){ // brak wiecej przydzielonego miejsca
if(!st.przydzielone){ // jesli nic nie przydzielone
st.przydzielone=1; // to przydziel 1 komorke
}else st.przydzielone*=2; // w przeciwnym przypadku st.przydzielone=st.przydzielone*2
// w ten sposob przydzielomy kolejno 1,2,4,8,16,32,... czyli potegi 2 ilosc komorek
st.tab=(atomtype*)realloc(st.tab,st.przydzielone*sizeof(atomtype)); //przydziel nowy (podwojny) rozmiar pamieci
}
//memcpy(&st.tab[st.wykorzystane],atom,sizeof(atomtype));
st.tab[st.wykorzystane]=atom; // w tym wypadku to co wyzej, ale po ludzku
st.wykorzystane++;
}
int pop(stos& st,atomtype& atom){
if(!st.wykorzystane)return 0; // stos jest pusty zwroc FALSE
st.wykorzystane--; // st.wykorzystane=st.wykorzystane-1;
//memcpy(atom,&st.tab[st.wykorzystane],sizeof(atomtype));
atom=st.tab[st.wykorzystane]; // w tym wypadku to co wyzej, ale po ludzku
// element samokontroli stosu
if(st.wykorzystane<=st.przydzielone/2){ // jezeli jest wykorzystane pol lub mniej komorek przydzielonych dla stosu
st.przydzielone/=2; // st.przydzielone=st.przydzielone/2
st.tab=(atomtype*)realloc(st.tab,st.przydzielone*sizeof(atomtype)); // przydziel polowe tego co bylo
}
return 1; // gdy na stosie cos bylo, zwroc TRUE
}
int get(stos& st,atomtype& atom){
if(!st.wykorzystane)return 0; // stos jest pusty zwroc FALSE
st.wykorzystane--; // st.wykorzystane=st.wykorzystane-1;
//memcpy(atom,st.tab,sizeof(atomtype)); // st.tab == &st.tab[0]
atom=*st.tab; // *st.tab == st.tab[0]
int i=0; // roznica pomiedzy get i pop
while(i<st.wykorzystane){ // sprawdz czy nie powinno byc <=, ale raczej nie powinno
//memcpy(&st.tab[i],&st.tab[i+1],sizeof(atomtype));
st.tab[i]=st.tab[i+1];
i++;
}
// element samokontroli stosu
if(st.wykorzystane<=st.przydzielone/2){ // jezeli jest wykorzystane pol lub mniej komorek przydzielonych dla stosu
st.przydzielone/=2; // st.przydzielone=st.przydzielone/2
st.tab=(atomtype*)realloc(st.tab,st.przydzielone*sizeof(atomtype)); // przydziel polowe tego co bylo
}
return 1; // gdy na stosie cos bylo, zwroc TRUE
}
void stworzstos(stos& st,int iloscpoczatkowa){
// Stworz stos i przydizel na poczatek czesc komorek
st.przydzielone=iloscpoczatkowa;
st.wykorzystane=0; // swiezy stosik, nie ma praw miec czegokolwiek wykorzystanego
st.tab=(atomtype*)malloc(iloscpoczatkowa*sizeof(atomtype)); // przydziel tablicy pamiec: iloscpoczatkowa*rozmiar komorki
}
void zwolnijstos(stos& st){ // wyczyść stos ze wszystkiego
if(st.tab)free(st.tab); // czyszczenie resztek
st.tab=0; // st.tab=NULL;
st.przydzielone=0; // no i oczywiście wyzeruj
st.wykorzystane=0;
}
W tym kodzie nie ma kontroli, czy malloc/realloc nie zwrocił 0/NULL, potrzebna tylko w funkcjach stworzstos i push, gdzie moze nastapic dodanie ilosci pamieci, pop i get conajwyżej zwalniają część pamięci, więc tu o problemie nie ma mowy.
Uzycie:
stworzstos() -> push()/get()/pop() x N -> zwolnijstos()
Po zwolnijstos() można uzywać push()/pop()/get() od nowa, bez tworzenia, ale można też stworzyć stos od nowa przydzielając początkową ilośc komórek.
dla szybkości mozna wprowadzić mapowanie albo/i zwiekszenie indeksu poczatkowego zamiast przpisywania tablicy przy get, tak aby kolejne pushe mogly wstawiac wartości za pobrane getem, ale trzeba zmienic wtedy algorytm samokontroli i wprowadzic klilka prostych obliczen (+,%, pewnie cos jeszcze) do geta i popa.