Permalänk
Medlem

[C++]Insertion sort

Tjena!

Sitter här o luggar lite inför tentan och har fastnat vid sorteringen...
På föreläsningarna har vi gått igenom tre sorterings algoritmer, Selection, bubble och insertion. Men främst valde föreläsaren att koncentrera sig på selection sort fast bara med nummer.

Så jag undrar hur gör jag om jag vill sortera i bokstavsordning med selection sort.
Om jag har tex en array med bilar (Ford,Saab, Mercedes, BMW, Fiat) och jag vill få de sorterade i bokstavsordning.

Jag gjorde följande men går icke...

void showModelSorted(Cell cell[], int nrOfCells) { string temp; int minIndex; for(int i=0;i<(nrOfCells-1);i++) { minIndex=i; temp=cell[i]; for(int j=i+1;j<nrOfCells;j++) { if(cell[j]<temp) { temp=cell[j]; minIndex=j; } } cell[minIndex]=cell[i]; cell[i]=temp; } } }

Permalänk
Hedersmedlem

Det går inte för att du då förmodligen gör fel. Du får gärna beskriva lite mer vad som blir fel. Blir något rätt eller är allt helt galet? Får du exceptions?

Permalänk
Medlem

får fel på följande lika med och mindre än.
temp=cell[i];
if(cell[j]<temp)
temp=cell[j];
temp=cell[j];
"no operator "<" matches these operands"

Permalänk
Medlem

Vad är Cell för typ? Du har antagligen glömt att definiera jämförelseoperatorn "<" för den typen iallafall. Nu är jag lite ringrostig på C++ men jag tror att det blir någonting i stil med detta:

bool operator<(Cell c1, Cell c2) { // Jämför vilken som ska ligga först och returnera // true eller false. }

Operatorn ska sedan vara en vänfunktion till din typ så att du kan komma åt de interna variablerna i objekten.

Permalänk
Medlem

sorry men nu blev jag sjukt förvirrad

Permalänk
Hedersmedlem
Skrivet av Z3R0:

sorry men nu blev jag sjukt förvirrad

Vad är Cell för något? Är det vettigt att jämföra ett sådant objekt med ett annat och har du definierat vad det är som avgör vilket som är störst?

Permalänk
Medlem
Skrivet av Elgot:

Vad är Cell för något? Är det vettigt att jämföra ett sådant objekt med ett annat och har du definierat vad det är som avgör vilket som är störst?

Cell är min konstruktor och cell är en array.

nope det har jag inte gjort, hur gör jag det?

tanken är att när programmet körs så ska en meny komma upp, där man kan välja att lägga till bilar och när man gjort det så kan man välja att få de sorterade i bokstavsordning.

Permalänk
Medlem

Kolla upp funktionen operator<() och överlagra så den passar för klassen.

Antagligen vill du jämföra namnen; i så fall borde din lösning vara något i stil med (om de returnerar en char[] med namnet med funktionen name()):

bool operator<(Cell cell1, Cell cell2) { return (std::strcmp(cell1.name(), cell2.name()) < 0) }

Visa signatur

Stationär: Intel-baserad, Arch + KDE
Bärbar: Dell XPS 13, Arch + KDE

Permalänk
Medlem

"Kolla upp funktionen operator<() och överlagra så den passar för klassen." detta förstår jag inte riktigt :-/

Jag vill typ jämföra första bokstaven i namnet och på så sätt få de sorterade i bokstavsordning.

Permalänk
Medlem
Skrivet av Z3R0:

"Kolla upp funktionen operator<() och överlagra så den passar för klassen." detta förstår jag inte riktigt :-/

Jag vill typ jämföra första bokstaven i namnet och på så sätt få de sorterade i bokstavsordning.

Problemet du har är att Cell1 < Cell2 betyder ingenting (än). Cell är en strukt du har skapat, därmed måste du också själv definera vad som gör en cell större än en annan cell. Säg att cell har en medlem "str" som är en string, och du vill att "<" ska betyda "första bokstaven i strängen mindre än". Då får du lägga en medlemsfunktion i "Cell" som något åt detta håll:

bool operator<(Cell cell1) { return (str < cell1.str) }

Visa signatur
Permalänk
Medlem

Finns ingen egentlig anledning att blanda in operatoröverlagring.

Du gör

temp=cell[i];

och på något sätt konverteras din cell[i] till en sträng där.
Sedan gör du

if(cell[j]<temp)

och jämför alltså mellan en string och en cell, det går inte. Du måste jämföra det innuti cellen, vad nu det kan tänkas vara.

"Överkurs" (för denna uppgift):
En överlagrad operator är bara en genväg för detta, men om du bara ska göra jämförelsen en gång behöver du inte den. Du sparar dessutom inte en cell utan en string, så operatorn måste vara mellan cell och string, inte cell och cell som andra har föreslagit.

Visa signatur

void@qnet
teeworlds, stålverk80, evil schemer, c, c++
Languages shape the way we think, or don't.

Permalänk
Medlem

Jag har nu lagt
bool operator<(Cell cell1);
som public

sen har jag gjort en sånhär.
bool Cell::operator<(Cell cell1)
{
return (this->name< cell1.name);
}

Känns dock som jag e ute o cyklar :-/

Permalänk
Medlem
Skrivet av Z3R0:

Jag har nu lagt
bool operator<(Cell cell1);
som public

sen har jag gjort en sånhär.
bool Cell::operator<(Cell cell1)
{
return (this->name< cell1.name);
}

Känns dock som jag e ute o cyklar :-/

Jag missade visst att lägga in [0] i min kod, så din kod blir då:

bool Cell::operator<(Cell cell1) { return (this->name[0]< cell1.name[0]); }

Sedan får du ändra i sorteringen så att variabeln "temp" är av typ "cell" och inte "string". Jdv har nog däremot rätt, det går lätt att helt enkelt ändra i sorteringen så att själva "<"-delen jämför strängarna i cell istället. Men nu när du ändå börjat med operator-överlagring tycker jag du kan göra klart det så att du lär dig hur det funkar. (i båda fallen måste temp vara av typen cell iaf)

(Talavis exempel inkluderar för övrigt fler bokstäver än bara de första, och är helt klart att föredra som sortering i bokstavsordning)

Visa signatur
Permalänk
Medlem

hm..jag ändrade min funktion sen jag skapade denna tråden... så den ser ut såhär nu.

void showModelSorted(Cell cell[], int nrOfCells) { string temp; int i; for(i=1;i<nrOfCells;i++) { temp=cell[i]; int j; for(j=i-1;j>=0 && cell[j]>temp;j--) { cell[j+1]=cell[j]; } cell[j+1]=temp; } for(i=0;i<nrOfCells;i++) cout<<cell[i]<<" "; cout<<endl; }

Men jag förstår inte riktigt vad du menar ändra temp så den är av samma typ som cell, cell är en array.

Permalänk
Medlem
Skrivet av Z3R0:

hm..jag ändrade min funktion sen jag skapade denna tråden... så den ser ut såhär nu.

void showModelSorted(Cell cell[], int nrOfCells) { string temp; int i; for(i=1;i<nrOfCells;i++) { temp=cell[i]; int j; for(j=i-1;j>=0 && cell[j]>temp;j--) { cell[j+1]=cell[j]; } cell[j+1]=temp; } for(i=0;i<nrOfCells;i++) cout<<cell[i]<<" "; cout<<endl; }

Men jag förstår inte riktigt vad du menar ändra temp så den är av samma typ som cell, cell är en array.

cell är en array av Cell. Detta går INTE:

string temp = cell[i]

Detta går:

Cell temp = cell[i]

Skulle rekommendera att du inte kallar en array av "Cell" för "cell", blir lagom förvirrande.

Visa signatur
Permalänk
Medlem

så här ser koden ut i början av main.

Cell *cell=NULL; int capacity=0, choice=0; int nrOfCells=0; cell=new Cell[capacity]; cout<<"How many phone slots do you need?"; cin>>capacity;

Permalänk
Medlem
Skrivet av Z3R0:

så här ser koden ut i början av main.

Cell *cell=NULL; int capacity=0, choice=0; int nrOfCells=0; cell=new Cell[capacity]; cout<<"How many phone slots do you need?"; cin>>capacity;

Ok? Vad är fel? Kompilerar den?

Visa signatur
Permalänk
Medlem

Jag har gjort det stora misstaget och inte skrivit funktionen för menyn än så jag kan inte kompilera, för om jag gör det så frågar den mig hur många platser min array ska ha sen dör den eftersom menyn inte finns...

men jag får fortfarande fel på två ställen i sorterings funktionen.

void showModelSorted(Cell cell[], int nrOfCells) { Cell temp; int i; for(i=1;i<nrOfCells;i++) { temp=cell[i]; int j; for(j=i-1;j>=0 && cell[j]>temp;j--)//fel på > { cell[j+1]=cell[j]; } cell[j+1]=temp; } for(i=0;i<nrOfCells;i++) { cout<<cell[i]<<" ";//fel på << } cout<<endl; }

Permalänk
Medlem
Skrivet av Z3R0:

Jag har gjort det stora misstaget och inte skrivit funktionen för menyn än så jag kan inte kompilera, för om jag gör det så frågar den mig hur många platser min array ska ha sen dör den eftersom menyn inte finns...

men jag får fortfarande fel på två ställen i sorterings funktionen.

void showModelSorted(Cell cell[], int nrOfCells) { Cell temp; int i; for(i=1;i<nrOfCells;i++) { temp=cell[i]; int j; for(j=i-1;j>=0 && cell[j]>temp;j--)//fel på > { cell[j+1]=cell[j]; } cell[j+1]=temp; } for(i=0;i<nrOfCells;i++) { cout<<cell[i]<<" ";//fel på << } cout<<endl; }

För det första felet. Vi har definierat "<" men inte ">", vänd på olikheten.

För det andra felet är det precis samma sak igen. Du har inte definierat hur cout skulle skriva ut en "Cell" och då går det inte. Detta bör funka istället:

cout << cell[i].name << " ";

Visa signatur
Permalänk
Medlem

cell[i].name
föjande står.
IntelliSense: member "Cell::name" (declared at line 11 of "h:\mobiltelefon\Cell.h") is inaccessible
h:\mobiltelefon\cellhandler.cpp 139 17 Mobiltelefon

förmodligen oåtkomligt för att name är privat...

Permalänk
Medlem
Skrivet av Z3R0:

cell[i].name
föjande står.
IntelliSense: member "Cell::name" (declared at line 11 of "h:\mobiltelefon\Cell.h") is inaccessible
h:\mobiltelefon\cellhandler.cpp 139 17 Mobiltelefon

förmodligen oåtkomligt för att name är privat...

Ändra till public då!

Visa signatur
Permalänk
Medlem

Kan jag göra men våran föreläsare säger att tex namn ska va privata så att de inte kan ändras "utifrån", har dock en funktion som är public som är getName.
Ser detta "ok" ut cell[i].getName()?

Permalänk
Medlem
Skrivet av Z3R0:

Kan jag göra men våran föreläsare säger att tex namn ska va privata så att de inte kan ändras "utifrån", har dock en funktion som är public som är getName.
Ser detta "ok" ut cell[i].getName()?

Absolut, det funkar!

Visa signatur
Permalänk
Medlem

Nu anser jag att jag är klar med själva uppgiften och har några få fel och dessutom har jag gjort saker som jag inte tror jag kan/får göra...

Skulle vara jätte trevligt om du kunde kolla igenom min kod, så jag iaf har nåt jag vet är korrekt som jag kan plugga på.

Cell.h
C++ | #ifndef CELL_H #define CELL_H #include <iostream

Cell.cpp
C++ | #include "Cell.h" Cell::Cell(string name,int pr

CellHandler.cpp
C++ | #include "Cell.h" #include <fstream> int menu(

tacksam för all hjälp!

Permalänk
Medlem

Lär dig använda referenser, de flesta ställen där du skickar Cell och std::string som argument hade du kunnat skicka const-referenser istället och sparat onödiga kopieringar. Samma sak i getName och liknande, returnera en const-referens istället för en kopia av strängen.

Sedan ser du inte ut att allokera minne korrekt. Du borde allokera efter att du läst in hur många element du ska ha (capacity).

Visa signatur

void@qnet
teeworlds, stålverk80, evil schemer, c, c++
Languages shape the way we think, or don't.

Permalänk
Medlem

det första du nämner med referenser... Jag har ingen aning vad det är :-/ kan vara så att vi inte gått igenom det än, eftersom föreläsaren har visat oss det.

Skulle du kunna förklara minnesallokeringen lite mer utförligt?

Permalänk
Medlem

Om du har en funktion som ser ut som

void func(ComplexClass c)

så kommer det skapas en ny instans av ComplexClass, och copykonstruktorn kommer köras. Då är det ofta mer effektivt att skriva

void func(const ComplexClass &c)

få kommer man bara få en const-referens till den redan befintliga instansen och inget kopierande eller extra exekverande av kod sker. En referens är som en pekare, men beter sig som en vanlig variabel. Att sätta referensen som const gör att man inte råkar ändra på dess innehåll. Du bör consta alla metoder som inte ändrar på sin instans också, så at de går att anropa på const-referenser/pekare.

När det gäller minnet gör du

int capacity=0, choice=0; int nrOfCells=0; cell=new Cell[capacity];

och sedan sätter du capacity till vad användaren vill, utan att allokera minne för den mängden, det gör att du får en minnesöverskrivning. Anropa new först efter att capacity lästs in.

Visa signatur

void@qnet
teeworlds, stålverk80, evil schemer, c, c++
Languages shape the way we think, or don't.

Permalänk
Medlem

Tack för att du tog din tid och försökte förklara, men det känns bara som jag kommer röra till det innan tentan om jag lägger ner tid i nåt som vi inte gått igenom än.

minnesallokering.
menar du nåt i stil med

cout<<"How many phone slots do you need?"; cin>>capacity; cell=new Cell[capacity];