WYSZUKIWANIE

#include <iostream>
#include <ctime>
#include <cmath>
#include <stdio.h>
#include <string>
#include <stdlib.h>

using namespace std;

const int N = 100; //długość tesktu
//const int M = 5 ; //długość wzorca

char T[N];
//char P[M];

void init(){
    int i;
    for(i=0;i<N;i++)
        T[i] = (char)(rand()%28 + 65);
    T[i]= '\0';
}

void searchN(){
    cout << "Tekst: " << endl;
    for(int i = 0; i<N; i++) cout << T[i];
    cout << "\nPodaj wzorzec: " << endl;
    string wzorzec;
    getline(cin, wzorzec);
    int M = wzorzec.length();
    //for(int i = 0; i<M; i++) cout << wzorzec[i]; cout << endl;
    int i = 0;
    bool czyZnaleziono = false;
    while(i<=N-M){
        int j = M-1;
        while(j>-1 && T[i+j]==wzorzec[j]) j--;
        if(j==-1){
            cout << "znaleziono na pozycji " << i << endl;
            czyZnaleziono = true;
        }
        i++;
    }
    if(!czyZnaleziono) cout << "Nie znaleziono" << endl;

} //zadanie 1

void KRsearch(){} //zadanie 2
void BMsearch(){} //zadanie

int main(int argc, char *argv[]){
    srand(time(NULL));
    init();
    searchN(); //zadanie 1
    KRsearch(); //zadanie 2
    BMsearch(); //zadanie 3
}


HASZ

#include <iostream>
#include <ctime>
#include <cmath>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

using namespace std;

const int N = 157;
char* T[N] = {0}; //tablica

int hash1(char* slowo){
    int n = strlen(slowo);
    int h = 0;
    for(int i = n-1; i>=0; i--){
        h += pow(3,i)*slowo[i];
    }
    h %= 157; //163;
    return h;
} //funkcja haszująca

char* init(){ //generuje losowy ciąg n-znakowy
    int n = rand()%9+1;
    int i;
    char *t = new char[n+1];
    for(i=0;i<n;i++)
        t[i] = (char)(rand()%28 + 65);
    t[i]= '\0';
    return t;
}

void dodaj(char* slowo){
    int hasz = hash1(slowo);
    while(T[hasz]!=0) hasz = (hasz+1)%N;
    T[hasz] = slowo;
}

void drukuj(){
    for(int i = 0; i<N; i++){
        cout << "T[" << i << "]: " << T[i] << endl;
        //for (list<char*>::iterator it=T[i].begin(); it != T[i].end(); ++it) cout << *it << "; "; cout << endl;
    }
} //wydruk całej tablicy (pozycja + słowo)

int main(int argc, char *argv[]){
    srand( time( NULL ) );
    for(int i =0; i< N;i++){
         char *s = init();
         dodaj(s);
    }
    drukuj();
}

PRIM

#include <iostream>
#include <ctime>
#include <iomanip>
using namespace std;

const int N = 5;
int graf[N][N]={
{0,2,100,100,6},
{100,0,1,3,100},
{4,100,0,1,2},
{100,100,100,0,1},
{3,100,100,100,0}
};

int poprzednik[N]={0};
int odwiedzony[N]={0};
int waga[N]={0};


int min()
{

    int poz;
    int min=100;
    for(int j=0;j<N;j++)
    {
        if(odwiedzony[j]==0 && min>waga[j])
            {
                min=waga[j];
                poz=j;
            }
    }
    odwiedzony[poz]=1;
    return poz;
}

void Prim(int s)
{
for(int i=0;i<N;i++)
        waga[i]=100;

waga[s]=0;
poprzednik[s]=-1;

for(int i=0;i<N;i++)
    {
    int u=min();
    for(int v=0;v<N;v++)
        {
        if(odwiedzony[v]==0 && graf[u][v]<waga[v])
        {
            poprzednik[v]=u;
            waga[v]=graf[u][v];
        }
            }
    }
}

int main()
{
int s;
cout<<"Podaj wierzcholek od ktorego zaczynasz (1 - "<<N<<"): ";
cin>>s;
s=s-1;
Prim(s);

cout<<"w: ";
for(int i=0;i<N;i++)
    cout<<setw(2)<<i+1<<" ";
cout<<endl;
cout<<"p: ";
for(int i=0;i<N;i++)
    cout<<setw(2)<<poprzednik[i]+1<<" ";
cout<<endl;
cout<<"k: ";
for(int i=0;i<N;i++)
    cout<<setw(2)<<waga[i]<<" ";

}

DIJKSTRA

#include <iostream>
#include <ctime>
#include <iomanip>
using namespace std;

const int N = 5;
int graf[N][N]={
{0,2,100,100,6},
{100,0,1,3,100},
{4,100,0,100,2},
{100,100,1,0,1},
{3,100,100,100,0}
};

int odwiedzony[N]={0};
int droga[N]={0};
int poprzednik[N]={0};

int min()
{

    int poz;
    int min=100;
    for(int j=0;j<N;j++)
    {
        if(odwiedzony[j]==0 && min>droga[j])
            {
                min=droga[j];
                poz=j;
            }
    }
    odwiedzony[poz]=1;
    return poz;
}

void dijkstra(int s){
    for(int i=0;i<N;i++)
        {
        droga[i]=100;
        poprzednik[i]=-1;
        odwiedzony[i]=0;
        }
    droga[s]=0;

    for(int x=0;x<N;x++)
        {
        int u=min();
        for(int v=0;v<N;v++)
            {
            if(graf[u][v]>0)
                {
                if(droga[v]>droga[u]+graf[u][v])
                    {
                    droga[v]=droga[u]+graf[u][v];
                    poprzednik[v]=u;
                    }
                }
            }
        }
}


int main()
{
int s;
cout<<"Podaj wierzcholek od ktorego zaczynasz (1 - "<<N<<"): "<<endl;
cin>>s;
s=s-1;
dijkstra(s);
cout<<endl;
cout<<"w: ";
for(int i=0;i<N;i++)
{
    cout<<setw(2)<<i+1<<" ";
}
cout<<endl;
cout<<"p: ";
for(int i=0;i<N;i++)
{
cout<<setw(2)<<poprzednik[i]+1<<" ";
}
cout<<"\nd: ";
for(int i=0;i<N;i++)
{
cout<<setw(2)<<droga[i]<<" ";

}
}

GRAFY BFS DFS

#include <iostream>
#include <time.h>
#include <queue>
using namespace std;
const int N = 5;
int graf[N][N];
int odwiedzony[N]={0}; //0 – nieodwiedzony, 1 – odwiedzony


void init(){ //losowy graf
 for(int i=0;i<N;i++)
 for(int j=0;j<N;j++)
 graf[i][j]=rand()%2;
}
queue <int> kolejka;


void listaSasiedztwa(){
    for(int s=0;i<N;s++){
        cout << s;
        for(int i=0;i<N;i++){
            if(graf[s][i]==1){
                cout << "->" << i;
            }
        }
    }
    cout << endl;
}


void BFS(int s){
for(int i=0;i<N;i++)
{
    odwiedzony[i]=0;
}
odwiedzony[s]=1;
kolejka.push(s);
while(!kolejka.empty())
    {
        int u=kolejka.front();
        cout<<u<<" ";
        for(int i=0;i<N;i++)
            if(odwiedzony[i]==0 && graf[u][i]==1)
            {
                odwiedzony[i]=1;
                kolejka.push(i);
            }
        kolejka.pop();
    }

}


void visit(int u)
{
    cout<<u<<" ";
    odwiedzony[u]=1;
    for(int i=0;i<N;i++)
    {
        if(odwiedzony[i]==0 && graf[u][i]==1)
        visit(i);
    }
}

void DFS(){
for(int i=0;i<N;i++)
    {
    odwiedzony[i]=0;
    }

for(int i=0;i<N;i++)
    {
    if(odwiedzony[i]==0)
    visit(i);
    }
}




int main(int argc, char *argv[]){
srand(time(NULL)); init();
cout<<"Wygenerowany graf:\n";
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
    cout<<graf[i][j]<<" ";
}
cout<<endl;
}
cout<<"DFS: \n";
DFS();


cout<<"\nBFS: \n";
BFS(0);
}


KOLEJKA

#include <iostream>
using namespace std;
const int N=5;
int rozmiarKolejki=0;
int kolejka[N]={0};



void zanurzanie(int N, int i)
{
    int l,r,wiekszy;
    l=2*i+1;
    r=2*i+2;
    if(l<=N && kolejka[l]>kolejka[i])
    wiekszy=l;
    else
    wiekszy=i;
    if(r<=N && kolejka[r]>kolejka[wiekszy])
    wiekszy=r;
    if(wiekszy!=i)
    {
        swap(kolejka[i],kolejka[wiekszy]);
        zanurzanie(N,wiekszy);
        }
}
void wynurzanie(int i)
{
    int ojciec;
    if(i>0)
    {
    ojciec=(i-1)/2;
    if(kolejka[i]>kolejka[ojciec])
    {
        swap(kolejka[i],kolejka[ojciec]);
        wynurzanie(ojciec);
        }
    }

}

void insert(int i)
{
    kolejka[rozmiarKolejki]=i;
    wynurzanie(rozmiarKolejki);
    rozmiarKolejki++;

}



int extract()
{
    if(rozmiarKolejki<1)
    cout<<"Kolejka pusta"<<endl;
    else
    {
        swap(kolejka[0],kolejka[rozmiarKolejki]);
        rozmiarKolejki=rozmiarKolejki-1;
        zanurzanie(rozmiarKolejki,0);
    }

}

int main()
{
insert(12);
insert(15);
insert(10);
insert(3);
for(int i=0;i<rozmiarKolejki;i++)
cout<<kolejka[i]<<" ";

extract();
extract();
cout<<endl;
for(int i=0;i<rozmiarKolejki;i++)
cout<<kolejka[i]<<" ";

insert(7);
insert(5);
insert(9);
insert(11);
cout<<endl;
for(int i=0;i<rozmiarKolejki;i++)
cout<<kolejka[i]<<" ";

extract();
extract();
extract();
extract();
extract();
extract();
cout<<endl;
for(int i=0;i<rozmiarKolejki;i++)
cout<<kolejka[i]<<" ";
}


KOPIEC

#include <iostream>
using namespace std;

const int N=14;
int kopiec[N]={7,6,8,5,6,4,1,2,3,2,6,4,6,6};


void zanurzanie(int N, int i)
{
    int l,r,wiekszy;
    l=2*i+1;
    r=2*i+2;
    if(l<N && kopiec[l]>kopiec[i])
    wiekszy=l;
    else
    wiekszy=i;
    if(r<N && kopiec[r]>kopiec[wiekszy])
    wiekszy=r;
    if(wiekszy!=i)
    {
        swap(kopiec[i],kopiec[wiekszy]);
        zanurzanie(N,wiekszy);
        }
}
void wynurzanie(int i)
{
    int ojciec;
    if(i>0)
    {
    ojciec=(i-1)/2;
    if(kopiec[i]>kopiec[ojciec])
    {
        swap(kopiec[i],kopiec[ojciec]);
        wynurzanie(ojciec);
        }
    }

}

void tworzenie()
{
    for(int i=N/2;i>=0;i--)
    zanurzanie(N,i);
}

void sortowanie()
{
    int X=N-1;
    for(int i=X;i>0;i--)
    {
        swap(kopiec[0],kopiec[i]);

        X--;
        zanurzanie(X,0);
    }
}


int main()
{

cout<<"Zanurzanie: ";
zanurzanie(N,0);
for(int i=0;i<N;i++)
cout<<kopiec[i]<<" ";

cout<<"\nWynurzanie: ";
wynurzanie(13);
for(int i=0;i<N;i++)
cout<<kopiec[i]<<" ";

cout<<"\nTworzenie: ";
tworzenie();
for(int i=0;i<N;i++)
cout<<kopiec[i]<<" ";

cout<<"\nSortowanie: ";
sortowanie();
for(int i=0;i<N;i++)
cout<<kopiec[i]<<" ";
}