Vinnaren i pepparkakshustävlingen!
2016-12-14, 17:13
  #1
Medlem
Hej fick i uppgift att göra ett program med olika familj medlemmar som sen skulle sortera de i slutet.
Men nu ska jag lägga till en funktion för binär sökning som söker efter ålder i en personvektor. Funktionen skall ha en rekursiv(anropa sig själv) algoritm.

Kod:
#include <iostream>
#include <string>
#include <vector>

using namespace std;

class 
Person // Klass: Innehåller en person
{
public:

        
string namn;
        
int alder;

    
void SkrivUt()
    {
        
cout << "Namn: " << namn <<", "<< alder << " \x8Fr." << endl// Talar om vad som ska skrivas ut
    
}
    
void setInfo(string _namnint _alder// Sätter den info som krävs
    
{
        
namn _namn;
        
alder _alder;
    }
};
int linsok(Person p[], int nint a// Linjär sökning av ålder
{
    for (
int i 0ni++)    // Går igenom hela listan
    
{
        if (
p[i].alder == a)    // Hittar det vi söker efter eller...
        
{
            return 
i;
        }
    }
    return -
1;    // ... så hittas inte personen
};
void bubblesort(Person p[], int n)
{
    
int i 0;

    for ( 
0ni++) // Yttre loop söker igenom hela listan
    
{

        
int nrLeft i// Inre loop, element för element

        
for (int j 0nrLeftj++)
        {
            if (
p[j].alder p[j+1].alder// Jämför elementen
            
{
                
// Byter plats
                
Person temp p[j];
                
p[j] = p[j+1];
                
p[j+1] = temp;
            }
        }
    }

}

int main() {

    
//Skapar en lista med personer - namn/ålder
    
cout << "-- Osorterad lista --" << endl << endl// Skriver ut titel

    
Person familj[4];
    
familj[0].setInfo("Noah"5); // Person 1. Börja från 0!
    
familj[0].SkrivUt(); // Anropar void SkrivUt()

    
familj[1].setInfo("Mike"32);
    
familj[1].SkrivUt();

    
familj[2].setInfo("Eva"33);
    
familj[2].SkrivUt();

    
familj[3].setInfo("Danin"12);
    
familj[3].SkrivUt();

    
cout << endl << "-- Sorterad lista --" << endl << endl// Skriver ut titel

    
bubblesort(familj3); //Anropar funktionen bubblesort för att sortera vektorn Familj.

    
for (int i 04i++) //Den sorterade listan skrivs ut
        
cout << "Namn: " << familj[i].namn << ", " << familj[i].alder << " \x8Fr." << endl// Berättar vad som ska skrivas ut


    
int index linsok(familj45); //Söker efter en viss person i vektorn Familj som innehåller 4 element och ska vara 5 år gammal

    
if (index == -1)
        
cout << "Personen hittas ej!"// Antingen hittas inte personen eller...
    
else
        
cout << endl << familj[index].namn << " finns p\x86 plats " << index << " i listan."// ... så hittar programmet personen och info skrivs ut.

    
cin.get();
    return 
0;


Pseudokoden för den binära sökningen är lite så här

OM mittersta värdet i vektorn är lika med det sökta värdet
Värdet hittat
ANNARS OM vektorn består av endast ett element
Sökta värdet finns inte i vektorn
ANNARS OM sökta värdet är mindre än mittersta värdet
Sök i nedre halvan av vektorn
ANNARS
Sök i övre halvan av vektorn
Citera
2016-12-14, 17:37
  #2
Medlem
svallerbyttans avatar
Kod:
int binarySearch(Person p[], int lowerIndexint upperIndexint age){
  
int middleIndex = (lowerIndex upperIndex)/2;
  if (
p[middleIndex].alder == age)
    return 
middleIndex//Age found
  
else if (lowerIndex == upperIndex)
    return -
1//Age not found
  
else if (p[middleIndex].alder age)
    return 
binarySearch(plowerIndexmiddleIndex-1age); //Check lower half
  
else if (p[middleIndex].alder age)
    return 
binarySearch(pmiddleIndex+1upperIndexage); //Check upper half

Notera att personvektorn måste vara sorterad innan du kör binärsökningen.

Ett alternativ är att du uppdaterar p[] i de rekursiva anropen och då kan skippa lowerIndex och upperIndex som argument. Tycker dock denna lösningen blev mer pedagogisk.
__________________
Senast redigerad av svallerbyttan 2016-12-14 kl. 18:02.
Citera
2016-12-14, 18:12
  #3
Medlem
Citat:
Ursprungligen postat av svallerbyttan
Kod:
int binarySearch(Person p[], int lowerIndexint upperIndexint age){
  
int middleIndex = (lowerIndex upperIndex)/2;
  if (
p[middleIndex].alder == age)
    return 
middleIndex//Age found
  
else if (lowerIndex == upperIndex)
    return -
1//Age not found
  
else if (p[middleIndex].alder age)
    return 
binarySearch(plowerIndexmiddleIndex-1age); //Check lower half
  
else if (p[middleIndex].alder age)
    return 
binarySearch(pmiddleIndex+1upperIndexage); //Check upper half

Notera att personvektorn måste vara sorterad innan du kör binärsökningen.

Ett alternativ är att du uppdaterar p[] i de rekursiva anropen och då kan skippa lowerIndex och upperIndex som argument. Tycker dock denna lösningen blev mer pedagogisk.


Tack för hjälpen. wow missade på en enkel sak egentligen men jag höll på själv och kom ganska nära. men nu förstår jag det ännu mer. VERKLIGEN tack
Citera
2017-04-26, 17:25
  #4
Medlem
Ett allmänt tips: när du definierar egna klasser och sedan vill jämföra objekt av dessa så kan du överskugga operatorer som t.ex. < och ==.

Då kan du istället för:

Kod:
  if (p[i].alder == a)    // Hittar det vi söker efter eller... 
        { 
            return i; 
        }

skriva

Kod:
  if (p[i] == a)    // Notera att du ej behöver skriva .alder
        { 
            return i; 
        }

eller

Kod:
  if (p[i] < p[j])    
        { 
            return i; 
        }

Ger lite snyggare kod och tillåter användning (ifall man vill använda dessa) av färdiga sorteringsalgoritmer från <algorithm>.
Citera

Stöd Flashback

Flashback finansieras genom donationer från våra medlemmar och besökare. Det är med hjälp av dig vi kan fortsätta erbjuda en fri samhällsdebatt. Tack för ditt stöd!

Stöd Flashback