2008-06-04, 02:34
  #1
Medlem
Tjenare , har haft vectorer nu ett tag i programmeringen och pga sjukdomn har jag missat en del , nu ska arbetet vara inlämnat om några dagar och min hjärna säger bara stopp.

Det jag vill åstakomma är en funktion som söker efter ID.

basgrejjer
Kod:
struct hoppla
{
    int id;
    string fnamn;
    string enamn;
};
vector<hoppla> klass; // En vektor av typen hoppla med namnet klass  

int elevAntal = 0; // Antal elver ska börja på noll 
hoppla elev; // en variabel av typen elev
char filnamn[16] = "";

Läsa in id,förnamn och efternamn:

Kod:
void oppna()
{
  char tecken[256];
  cout << "Skriv filnamn p\x86 txt-fil som ska \x94ppnas: ";
  cin >> filnamn;
  ifstream infil(filnamn);
  
  if(!infil.is_open())
  {
    cout << endl << "Det gick inte att l\x84sa filen, kontrollera filnamn f\x94rs\x94k igen!";
    cout << endl;
    system("PAUSE");
  }
  else
  {
      cout << endl << "Filen \x94ppnades" << endl;
      system("PAUSE");
    while (!infil.eof())
    {
      infil.getline(tecken, 256, '\n'); // hämta f\x94rsta raden (förnamn) från filen
      elev.fnamn = tecken; // spara fornamn
      infil.getline(tecken, 256, '\n');
      elev.enamn = tecken;
      klass.push_back(elev);
      elevAntal++;
    }
  }    
}

Sök-Funktionen:

Kod:
void sok()
 {
     int min = 0;
     int max = elevAntal-1;
     int antalSokningar = 0;
     int pos = -1;
     int tal = 0;
     hoppla venster;
     hoppla hoger;
     cout << "S\x94k efter: ";
     cin >> tal;
     while (min <= max && pos == -1)
     {
     int mitt = (min+max)/2;
     if (tal > (mitt))
     {
       min = mitt+1;
     }
     else if (tal < (mitt))
     {
      max = mitt-1;
     }
     else
     {
      pos = mitt;
     }
     antalSokningar++;
 }
  cout << "Antal sökningar: " << antalSokningar << endl;
  if (position != -1)
  {
    cout << "Talet finns på position:";
    cout << position+1 << endl;
  }
  else
  {
    cout << "Talet går inte att hitta";
  }
}

Mvh // Piraten
Citera
2008-06-04, 07:25
  #2
Medlem
För att binärsökning ska fungera så måste det du söker efter vara ordnat. Jag ser inte ens att du sätter ID till någonting. Grundtanken är att ifall du har det ordnat så kan du utesluta hälften av arrayen vid varje sökning.

Alltså, du börjar att söka i mitten. Är det eftersökta ID större än det som finns i mitten så kan du glömma alla index som är mindre eller lika med hälften. Sen är det bara att upprepa på den större halvan.

Det jag ser som kan vara fel just i ditt program är att du aldrig läser in ditt ID och att vectorn aldrig sorteras efter storleksordning m.a.p. ID. Om ID:na redan är sorterad i filen du läser ifrån så är det redan löst. I sökningsalgoritmen så måste du jämföra själva ID:t också.

Hoppas det hjälper dig något frammåt i alla fall.
__________________
Senast redigerad av Franzjäger 2008-06-04 kl. 07:30.
Citera
2008-06-04, 12:54
  #3
Medlem
Citat:
Ursprungligen postat av Franzjäger
För att binärsökning ska fungera så måste det du söker efter vara ordnat. Jag ser inte ens att du sätter ID till någonting. Grundtanken är att ifall du har det ordnat så kan du utesluta hälften av arrayen vid varje sökning.

Alltså, du börjar att söka i mitten. Är det eftersökta ID större än det som finns i mitten så kan du glömma alla index som är mindre eller lika med hälften. Sen är det bara att upprepa på den större halvan.

Det jag ser som kan vara fel just i ditt program är att du aldrig läser in ditt ID och att vectorn aldrig sorteras efter storleksordning m.a.p. ID. Om ID:na redan är sorterad i filen du läser ifrån så är det redan löst. I sökningsalgoritmen så måste du jämföra själva ID:t också.

Hoppas det hjälper dig något frammåt i alla fall.

Har en bubbelsortering som sköter detta åt mig.

Kod:
void bubblesort()
{
    vector<hoppla>::iterator it;
    hoppla venster;
    hoppla hoger;
    hoppla temp;
    bool sorterad;
    do
    {
    sorterad = true;
    for (it = klass.begin(); it != klass.end()-1;it++)
    {
     venster = *it;
     hoger = *(it+1);
      if (venster.enamn > hoger.enamn)
      {
       temp = *it;
       *it = *(it+1);
       *(it+1) = temp;
       sorterad = false;
      }
    }
  }while(sorterad == false);
}
Citera
2008-06-04, 15:06
  #4
Medlem
När du sorterar så sorterar du m.a.p. efternamnet, men du söker efter ett tal? Enligt mig så bör du antingen sortera efter ID eller söka efter efternamnet. I dina if-satser så ser det ut som du vill jämföra så här: if (tal > klass[mitt].ID) osv., om jag fattat uppgiften rätt.
Citera
2008-06-04, 19:39
  #5
Medlem
Citat:
Ursprungligen postat av Franzjäger
När du sorterar så sorterar du m.a.p. efternamnet, men du söker efter ett tal? Enligt mig så bör du antingen sortera efter ID eller söka efter efternamnet. I dina if-satser så ser det ut som du vill jämföra så här: if (tal > klass[mitt].ID) osv., om jag fattat uppgiften rätt.

Jo tänkte skriva det men internetuppkopplingen dog , jag vill alltså söka efter efternamnet.

if satsen är det jag har problem med , därav en ogiltig operator.(jag testar lite hit o dit när jag inte orkar tänka )
Citera
2008-06-06, 06:51
  #6
Medlem
Någon ?

(vet att det är mot reglerna men får IG i kursen om detta inte är inne innan måndag )

Kan man söka efter stringar med binär sökning ?
Citera
2008-06-06, 09:31
  #7
Medlem
Marxamas avatar
Citat:
Ursprungligen postat av Pir4t
Någon ?

(vet att det är mot reglerna men får IG i kursen om detta inte är inne innan måndag )

Kan man söka efter stringar med binär sökning ?
Absolut - men du måste ha en funktion som jämför två strängar, och berättar vilken sträng som ligger först i bokstavsordning, så att säga. Java har så'nt inbyggt, och det var så länge se'n jag pysslade med C++ (och när jag gjorde det var string inte aktuellt), så jag vet inte om det finns någon sådan funktion du kan använda dig av... Det borde göra det, annars är det inga större problem att skriva en egen
Citera
2008-06-09, 00:32
  #8
Medlem
Citat:
Ursprungligen postat av Marxama
Absolut - men du måste ha en funktion som jämför två strängar, och berättar vilken sträng som ligger först i bokstavsordning, så att säga. Java har så'nt inbyggt, och det var så länge se'n jag pysslade med C++ (och när jag gjorde det var string inte aktuellt), så jag vet inte om det finns någon sådan funktion du kan använda dig av... Det borde göra det, annars är det inga större problem att skriva en egen

Jo funktionen kan jag skriva , men hur i helsike får jag ut värden ? :P

menar då :

Jag har en struct med :
Kod:
int id;
string fnamn;
string enamn;

Sedan deklarerar jag variabeln elev till med denna struct.
structnamn elev;

Vill jag komma åt något i structen så kör jag ju bara elev.fnamn eller liknande.

Sedan har jag ju även en vector som jag stoppar min elev i.

vill jag åt en elev (alltså alla delar av elev) så använder jag ju
klass.at(1) och för att komma åt bara en del använder jag klass.at(1).fnamn.

Hur kör jag nu ihop detta till en binär sökning ?

Detta fick vi av våran lärare :

Kod:
int binar_sok(string data[], int antal)
{
  int min = 0;
  int max = antal-1;
  int antalSokningar = 0;
  int pos = -1;
  
  while (min <= max && pos == -1)
  {
    int mitt = (min+max)/2;
    if (sokord > data[mitt])
    {
      min = mitt+1;
    }
    else if (sokord < data[mitt])
    {
      max = mitt-1;
    }
    else
    {
      pos = mitt;
    }
    antalSokningar++;
  }

Hur kan jag skicka in alla vectorns efternamn till funktionen ? eller ska jag skicka in hela vectorn ?
antal har jag redan en räknare (elevAntal) till.

Hjälp uppskattas
Citera
2008-06-09, 03:21
  #9
Medlem
Finns det något sätt man kan redigera sina inlägg här ?

Löste iaf det

Kod för dom som kan använda det :

Globala saker :
Kod:
#include <iostream>
#include <fstream>
#include <iomanip>
#include <conio.h>
#include <string>
#include <vector> // För att få tillgång till vektorfunktionerna

using namespace std;

struct hoppla
{
    int id;
    string fnamn;
    string enamn;
};
vector<hoppla> klass; // En vektor av typen hoppla med namnet klass  

hoppla elev; // en variabel av typen elev
char filnamn[16] = "";
unsigned int i;

void cls()
{
system("CLS");
}

Öppna "databas"
Kod:
void oppna()
{
  char tecken[256];
  cout << "Skriv filnamn p\x86 txt-fil som ska \x94ppnas: ";
  cin >> filnamn;
  ifstream infil(filnamn);
  
  if(!infil.is_open())
  {
    cout << endl << "Det gick inte att l\x84sa filen, kontrollera filnamn f\x94rs\x94k igen!";
    cout << endl;
    system("PAUSE");
  }
  else
  {
  cout << endl << "Filen \x94ppnades.." << endl << "L\x84ser in data" << endl;
    while (!infil.eof())
    {
      infil.getline(tecken, 256, '\n'); // Hämta rad (id) från filen och strunta i det då int inte fungerar med char
      elev.id = klass.size();           // Spara id till structen
      infil.getline(tecken, 256, '\n'); // Hämta rad (fnamn) från filen
      elev.fnamn = tecken;              // Spara fnamn till structen
      infil.getline(tecken, 256, '\n'); // Hämta rad (enamn) från filen
      elev.enamn = tecken;              // Spara enamn till structen
      klass.push_back(elev);            // Spara elev
    }
    if(klass.size()==1)
    {klass.erase (klass.begin());}
    else
    {klass.erase (klass.end());}
  cout << "Klart, l\x84ste totalt: " << klass.size() <<" poster." << endl;
  system("PAUSE");
  }    
}

Lägga till :
Kod:
void skriva()
{    
  cout << "Mata in elever i klassen, avsluta med !" << endl;
  cout << "F\x94rnamn: ";
  cin >> elev.fnamn;
  while (elev.fnamn != "!") // så länge som f\x94rnamn inte \x84r !
  {
    elev.id = klass.size(); 
    cout << "Efternamn: ";
    cin >> elev.enamn;
    klass.push_back(elev); // Tryck in en elev i vektorn klass
    cout << "F\x94rnamn: ";
    cin >> elev.fnamn;
  }
}

Spara :
Kod:
void spara()
{
      if(klass.empty()==false)
      {
      ofstream rensa_fil( filnamn, ios::trunc );
      rensa_fil.close();
      ofstream skriv_fil(filnamn, ios::app );
      cout << "Sparar...."<< klass.size() << "poster" << endl;
      for(i=0;i<=klass.size()-1;i++)
       {
       skriv_fil << klass[i].id << endl;
       skriv_fil << klass[i].fnamn << endl;
       skriv_fil << klass[i].enamn << endl;
       }
      skriv_fil.close();
      cout << "Sparat !" << endl;
      }
      else
      {
      cout << "Vektorn \x84r tom !" << endl;
      }
     system("PAUSE");
}
Sortering:
Kod:
void bubblesort()
{
    if(klass.size()>=2){
    vector<hoppla>::iterator it;
    hoppla venster;
    hoppla hoger;
    hoppla temp;
    bool sorterad;
    do
    {
    sorterad = true;
    for (it = klass.begin(); it != klass.end()-1;it++)
    {
     venster = *it;
     hoger = *(it+1);
      if (venster.enamn > hoger.enamn)
      {
       temp = *it;
       *it = *(it+1);
       *(it+1) = temp;
       sorterad = false;
      }
    }
  }while(sorterad == false);
  cout << "Sorterat !!" << endl;}
  else{cout << "F\x84r lite namn f\x94r att sortera" << endl;}
  system("PAUSE");
}

Sökning :
Kod:
void sok()
 {
     int min = 0;
     int max = klass.size()-1;
     int antalSokningar = 0;
     int pos = -1;
     string namn;
     cout << "S\x94k efter efternamnet: ";
     cin >> namn;
     
     while (min <= max && pos == -1)
     {
     int mitt = (min+max)/2;
     
     if (namn > klass[mitt].enamn)
     {min = mitt+1;}
     else if (namn < klass[mitt].enamn)
     {max = mitt-1;}
     else
     {pos = mitt;}
     
     antalSokningar++;
     }
     
  cout << "Antal s\x94kningar: " << antalSokningar << endl;
  if (pos != -1)
  {
    cout << "Efternamnet finns i vector:";
    cout << pos << endl;
    cout << klass[pos].id <<" "<<  klass[pos].fnamn <<" "<< klass[pos].enamn << endl;
  }
  else
  {
    cout << "Talet g\x86r inte att hitta" << endl;
  }
  system("PAUSE");
}

Kan man snygga till koden på några ställen är det guld värt om ni skriver det

Tack för denna gång // Piraten
Citera
2008-06-09, 04:55
  #10
Medlem
anakatas avatar
Det där var ju ett otroligt dåligt exempel på hur man använder binärsökning. Binärsökning används för att hitta gränsvärden och inget annat. Vad du behöver för att leta efter ett visst namn så effektivt som möjligt är en hashtabell.
Citera
2008-06-17, 05:22
  #11
Medlem
Citat:
Ursprungligen postat av anakata
Det där var ju ett otroligt dåligt exempel på hur man använder binärsökning. Binärsökning används för att hitta gränsvärden och inget annat. Vad du behöver för att leta efter ett visst namn så effektivt som möjligt är en hashtabell.

Jo , somsagt inte jag som gav uppgiften :P
Citera
2008-06-17, 08:24
  #12
Medlem
Citat:
Ursprungligen postat av anakata
Det där var ju ett otroligt dåligt exempel på hur man använder binärsökning. Binärsökning används för att hitta gränsvärden och inget annat. Vad du behöver för att leta efter ett visst namn så effektivt som möjligt är en hashtabell.


Nej, det är inget dåligt exempel. Har man en sorterad datamängd så är en binärsökning ett bra alternativ, en hash tabell funkar också, men det finns inget som säger att en hashtabell skulle vara det mest effektiva.
Ett stort problem med hashtabeller är ju att det kan bli väldigt mycket oanvänt minne, speciellt om hash-funktionen inte är anpassad till datan, och då blir den varken effektiv ur ett tids- eller minnes-perspektiv.
Citera

Skapa ett konto eller logga in för att kommentera

Du måste vara medlem för att kunna kommentera

Skapa ett konto

Det är enkelt att registrera ett nytt konto

Bli medlem

Logga in

Har du redan ett konto? Logga in här

Logga in