linked list ider

Har du overvejet at stjæle fra STL ?

http://www.cppreference.com/cpplist.html

jeg synes i hvert fald du skal slette output_all_nodes, da det ikke rigtig har noget med listen at gøre hvordan den bliver skrevet på skærmen. det skal brugeren selv klare. og ja, som arne siger, så kig på STL's list.

Der mangler måske funcktioner til at fjene et enkelt element fra listen, enten først eller sidst.
Du kunne også overveje om du vil kunne insætte og fjerne midt i listen.

bertalbrander ->

Hvis jeg skulle indsætte en ny node midt i listen, ville det så ikke være temlig langsom at køre alle de enkelte noder igennem for at komme til en bestemte ?

Jo, du ville være nødt til at løbe listen igennem, hvis den er meget stor vil det tage nogen tid, men i praksis vil det måske ikke være et stort problem.

Men hvis du ønsker en sorteret liste er du nok nødt til det. Du kan også få brug for det hvis du vil bruge listen til f.ex. en medlems kartotek, man kan ikke gå ud fra at det altid er den ældste eller nyeste medlem der opsiger sit medlemsskab.

Du kan også lave et binært træ, men det er en anden historie.

bertelbrander ->

Hvad mener du med at jeg kan bruge et binært træ ??

arne_v >> hvordan specifisere man sin data structur med STL C++ list´s ?

Et binært træ er en anden måde at gemme data.

I en linket liste ligger noderne i en lang række.

I et træ har hver node en left og en right node og strukturen kommer til at ligne et træ.

I et træ gemmer man noderne efter en nøgle, dette kan være et navn eller et nummer. Når man skal finde et navn i træet bruger man denne nøgle til at bestemme ruten i træ'et.

Hvis man har en linket liste med 1000 noder vil man i værste tilfælde være nødt til at lede alle 1000 igennem. I et træ ville man højest skulle checke 10 elementer fordi 2^10 er 1024.

bertelbrander -> det lyder ret smart med det binære træ.

bertelbrander -> Men er det ikke ret svært at programmere således binært træ ?

Man kan bruge en stl-list med:

#include <list>

class Whatever
{
  ...
};
std::list<Whatever>MyList;

Ja og nej.

Grundstammen er ret let, men der er flere ting der kan være besværlige:
1: Det er lidt besværligt at løbe listen igennem fra en ende af.
2: Det er lidt svært at slette tilfældige noder.
3: Hvis nøglen ikke er random kan træet blive skævt og man vil være nødt til at balancere det hvilket er lidt bøvlet.

stl har en map der (typisk) er et træ.

bertelbrander ->

Mener du:

Whatever indeholder de funktioner til listen, og list er selve vectoren og std er det namespace hvor list kommer fra ?

Eksempel på list:

#include <iostream>
#include <list>

using namespace std;

int main()
{
  list<int> lst;
  list<int>::iterator it;
  lst.push_back(3);
  lst.push_back(2);
  lst.push_back(1);
  for(it=lst.begin();it!=lst.end();it++) cout << *it << endl;
  lst.sort();
  for(it=lst.begin();it!=lst.end();it++) cout << *it << endl;
  return 0;
}

Whatever er en struct/class der indeholder det der skal gemmes, list er en stl-kontainer (en template class), der har metoder som push_back og pop_front til at operere på listen, std:: namespace, og listen kommer til at hedde MyList.

Jeg kan godt lave et lille eksempel.

Bertalbrander -> Det må du meget gerne :)

Hvad mangler der i Arne's eksempel?

Bertalbrander -> hmmm...jeg forstår det ikke helt....men det betyder heller ikke store...mit spørgsmål er bleven besvaret, så Arne giv et svar. :)

Takker for hjælpen Bertelbrander :)

Jeg lavede lige et eksempel, hvis der er noget du ikke forstår, så sprøg.

#include <list>
#include <iostream>
#include <string>

class MemberClass
{
public:
  MemberClass(std::string aName)
  {
      Name = aName;
      Number = NextNumber++;
  }
  friend std::ostream &operator << (std::ostream &os, const MemberClass &Member);
private:
  std::string Name;
  int Number;
  static int NextNumber;
};

std::ostream &operator << (std::ostream &os, const MemberClass &Member)
{
  os << Member.Number << " " << Member.Name << std::endl;
  return os;
}

std::list <MemberClass>MyList;

int main()
{
  int i;
  for(i = 0; i < 3; i++)
  {  // Add 3 members
      std::string St;
      std::cout << "Enter Name: ";
      std::cout.flush();
      std::getline(std::cin, St);
      MyList.push_back(MemberClass(St));
  }
  std::list <MemberClass>::iterator idx;
  // Print the list
  for(idx = MyList.begin(); idx != MyList.end(); idx++)
      std::cout << *idx;
}

int MemberClass::NextNumber;

svar

ok..he he...hvad er det ?

friend std::ostream &operator << (std::ostream &os, const MemberClass &Member);

std::ostream &operator << (std::ostream &os, const MemberClass &Member)

Det er det som gør at MemberClass kan udskrives med <<.

arne_v -> ok.  Det kan jeg godt se hver du mener lidt sådan.

Konstruktionen ser bizar ud. Men det er helt standard. Ja bortset fra at jeg
ikke ville have skrever linie skift i den.

den nederste linie...hvad er det til ?

int MemberClass::NextNumber;

static felter skal i C++ implementeres på den måde

arne_v >> ja, den ser lidt bizar ud, når man lige kigger på det hurtigt.  Men jeg tror jeg har fået meget godt fat i det nu. :)

Man kunne jo bare ændre sin MemberClass´s data members, og tilføje nogle flere...

Den sidste loop ville hardcore C++ programmører vist lave som:

std::copy(MyList.begin(), MyList.end(), std::ostream_iterator<MemberClass>(std::cout, "\n"));

Og include algorithm og iterator, samt fjene std::endl fra << operatoren