Array initialisation at o(1) time

Συζητήσεις για την γλώσσα C και C++

Συντονιστές: WebDev Moderators, Super-Moderators

Απάντηση
alexis_ced
Δημοσιεύσεις: 6
Εγγραφή: 06 Φεβ 2006 19:55

Array initialisation at o(1) time

Δημοσίευση από alexis_ced » 06 Φεβ 2006 20:01

loipon exw ton akoloutho kwdika kai kapou xtipaei lathos kai exw kollhsei,einai gia arxikikopoihsh pinaka se time O(1).
methodos arxikopoishs se time O(1) einai h akolouthi:

Πρόβλημα: Δίνεται array Α [0...Ν-1], το οποίο πρέπει να αρχικοποιηθεί με την τιμή 0, σε κάθε θέση του. Να δώσετε ένα τρόπο για να αποφευχθεί η αρχικοποίηση.
Απάντηση:
Χρησιμοποιούμε επιπλέον πίνακες AUX και S, και οι δυο μεγέθους Ν, χωρίς να χρειάζονται αρχικοποίηση. Ο S υλοποιεί μια στοίβα η οποία κρατά όλες τις θέσεις του Α που έχουν έγκυρες τιμές. Οι θέσεις του πίνακα AUX χρησιμοποιούνται για τυχαία προσπέλαση της στοίβας με τρόπο που θα φανεί παρακάτω. Επίσης χρησιμοποιείται η μεταβλητή TOP που δείχνει στην κορυφή της στοίβας. Αρχικά TOP=-1, συνθήκη ισοδύναμη με την αρχικοποίηση του Α με μηδενικά.
Κατά τη διάρκεια της εκτέλεσης, διατηρούμε την εξής συνθήκη:
A = s, αν και μόνο αν 0≤AUX ≤TOP && S[AUX] = i (1)
Οπότε, όταν χρειαστεί να γράψουμε ή να διαβάσουμε μια τιμή από το Α, ελέγχουμε την τήρηση της παραπάνω συνθήκης. Αν επαληθεύεται, μπορούμε να συνεχίσουμε να κάνουμε την πράξη. Διαφορετικά το i, πρέπει να εισαχθεί στη στοίβα και να ενημερωθεί γι’ αυτό και ο AUX, δηλαδή
TOP = TOP+1;
S[TOP]= i;
AUX = TOP;
A = s;
Έστω ότι ο Α δεν έχει καμία τιμή και ότι για πρώτη φορά αποφασίζουμε να γράψουμε στη θέση Α[850]. Τότε αυξάνουμε το TOP, λαμβάνοντας TOP=0 και θέτουμε S[0]=850, δηλαδή ενημερώνουμε τη στοίβα ότι ο Α έχει έγκυρη τιμή στη θέση Α[850].

Μόνο ο έλεγχος 0≤AUX≤TOP δεν θα αρκούσε γιατί ο AUX είναι μη αρχικοποιημένος. Συνεπώς θα μπορούσε, για παράδειγμα, για κάποιο i, να ισχύει 0≤AUX≤TOP, αλλά ο AUX να περιέχει σκουπίδια στη συγκεκριμένη θέση μνήμης
και η επαλήθευση της ανισότητας να είναι γι’ αυτό το λόγο ψευδής. Αυτή η περίπτωση μπορεί να απεικονιστεί στο παραπάνω σχήμα αν επιχειρήσει κάποιος να προσπελάσει τη διεύθυνση Α[910] και έστω AUX[910]=1. Επειδή S[1]=3 σημαίνει ότι η θέση Α[910] δεν έχει αρχικοποιηθεί και άρα περιέχει μη έγκυρα δεδομένα. Το επόμενο βήμα θα ήταν να γινόταν εισαγωγή του 910 στη στοίβα και να τεθεί Α[910]=0 (τιμή αρχικοποίησης)
Η στοίβα δεν μπορεί να χρησιμοποιηθεί από μόνη της γιατί θέλουμε να επαληθεύουμε αν κάποια τιμή του i, έχει περαστεί μέσα στη στοίβα χωρίς μεγάλη επιβάρυνση. Για να πετύχουμε Ο(1) επιβάρυνση ανά βήμα προσπέλασης χρειαζόμαστε και τη βοήθεια του AUX.

episinaptw kai ton kwdika mou se c++

alexis_ced
Δημοσιεύσεις: 6
Εγγραφή: 06 Φεβ 2006 19:55

Array initialisation at o(1) time

Δημοσίευση από alexis_ced » 06 Φεβ 2006 20:02

#include <iostream>
#include "dstack.h"

using namespace std;

DStack::DStack(int N) // initalize a stack with N items
{
bottom_ = new float[N];
top_ = bottom_;
size_ = N;
}

DStack::~DStack() // how to reclaim memory from local
{ // stacks when exiting functions
delete [] bottom_;
}

int DStack::num_items() const // number of items currently in stack
{
return (top_ - bottom_ );
}

void DStack::push(float val) // push a new value
{
*top_ = val;
top_++;
}

float DStack::pop() // pop value from top
{
top_--;
return *top_;
}


int DStack::full() const // 1 if full, 0 empty
{
return (num_items() >= size_);
}


int DStack::empty() const // 1 if empty, 0 full
{
return (num_items() <= 0);
}



void DStack::print() const
{

cout << "Stack currently holds " << num_items() << " items: " ;
for (float *element=bottom_; element<top_; element++)
{
cout << " " << *element;
}
cout << "\n";

}

float DStack::get_top_()
{
return *top_;}

float DStack::getpos(int posit)
{
return posit;
}



int main()
{

int num;

int *A;
int *AUX;

cout<<"Enter the number of items in the array :\t";
cin>>num;
if(num<=0){cout<<"Invalid input!\a\n"; return 1;}

A=new int[num]; //->&#196;&#221;&#243;&#236;&#229;&#245;&#243;&#231; &#247;&#254;&#241;&#239;&#245;
AUX=new int[num];
if(A==NULL||AUX==NULL)
{
cout<<"Allocation error!!\a\n";
return 1;
}


DStack S(num);


int s,pos,number;



while(pos!=-1){
cout<<"Give position to write a number: "<<endl;
cin>>pos;
cout<<"give number :"<<endl;
cin>>number;

if (0<=AUX[pos] && AUX[pos]<=S.get_top_() && getpos(AUX[pos])=pos)
A[pos] = s;
else
{
top_ = S.get_top_()+1;
S[top_]= pos;
AUX[pos] = S.get_top_();
A[pos] = s;
}}

return 0;
}


kai to header file

// dstack.h -- Dynamic stack (DStack) declaration and function prototypes.
//

class DStack
{
private:
float *bottom_;
float *top_;
int size_;

public:
DStack(int size);
void push(float val);
int num_items() const;
float pop();
int full() const;
int empty() const;
void print() const;
float get_top_();
float getpos(int posit);
~DStack();
};

Απάντηση

Επιστροφή στο “C, C++”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης