[C] lineaire lijst sorteren

[rrrrob]

Ik ben aan het oefenen voor mijn c-examen voor a.s. maandag.
Nu heb ik hier thuis ff geen c compiler voor handen en ik wil toch graag weten of ik het goed doe. Dus als jullie even naar deze opgave en mijn antwoord zouden willen kijken...........

Dit is dus de opgave uit een oefententamen:

Schrijf een functie die van een lineairelijst met integers nagaat of deze gesorteerd is van klein naar groot.

gebruik onderstaand datatype:

code:

typedef struct _node 
{ 
    struct _node *next; 
    int w; 
}  El, *pEl;

mijn oplossing:

code:

bool Sorted (pEl L) 
//pre: L is een lineaire lijst 
//post: Sorted is true als L is gesorteerd van klein naar groot anders 
//is sorted false. 
{ 
    return L == NULL ? true : (L -> w) < (Sorted(L -> next)); 
}

zou dit kunnen werken?

[Soultaker]

De term 'lineaire lijst' zegt me niet zoveel (elke lijst is toch 'lineair'?); de datastructuur die je gebruikt staat over het algemeen bekend als 'linked list'. Verder dacht ik dat bool geen ANSI C datatype is.

Dat terzijde, is je oplossing niet correct. De expressie "(L->w) < (Sorted(L->next))" werkt natuurlijk niet, aangezien L->w een integer is en Sorted() een bool retourneerd. Nu kun je de twee in C wel vergelijken, maar het resultaat is natuurlijk vrij onzinnig. Deze expressie is wel aan te passen zo dat 'ie correct is, maar dan heb je nog steeds het probleem dat je een recursieve functie gebruikt. Dat betekent dat de grootte van de linked list van dezelfde orde is als de grootte van je stack. In het algemeen is je stack ook weer niet zo heel groot (denk aan een megabyte ofzo) dus eigenlijk is je oplossing niet al te geschikt. Probeer eens een iteratieve oplossing (met een for- of while-lusje, bijvoorbeeld) te schrijven.

[rrrrob]

Linked List <--> Lineaire lijst = hetzelfde, dacht ik de leraar gebruikt ze in ieder geval ook door elkaar.
Zo had ik het nog niet bekeken, ga ik is ff proberen.
Bedankt voor de tip.


edit:

zoiets dan?

code:

bool KleinGroot (pEl L)
{
  bool hulp=true;
  
  while (L->next != NULL)
  {
     if ( ! ((L->w) < (L->next->w)) )
     {
       hulp = false;
       break;
     }
     else
     L = L -> next;
  }
}

[ Voor 82% gewijzigd door rrrrob op 24-01-2004 15:31 ]

[PrisonerOfPain]

Het kan aan mij liggen maar voldoet hier eigenlijk niet gewoon ieder sorteer algoritme?

[rrrrob]

PrisonerOfPain schreef op 24 januari 2004 @ 15:46:
Het kan aan mij liggen maar voldoet hier eigenlijk niet gewoon ieder sorteer algoritme?

Dat weet ik niet, ik heb verder nog nooit iets moeten sorteren dus.....
we hebben in de praktikum opdrachtjes alleen lijsten moeten inlezen en naar scherm schrijven.
Nu voor het tentamen worden dit soort dingen gevraagd, en aangezien dit de 1e keer is dat ik een c tentamen krijg weet ik niet precies hoe en wat allemaal.
Maar ik probeer me natuurlijk wel zo goed mogelijk voor te bereiden.

[Cuball]

- wat als je ljist leeg is ?
- waarom met zo'n vieze break werken ?

oplossing met een lusje is stuk beter dan een recursieve funtie te gebruiken voor zo'n probleem

[rrrrob]

Cuball schreef op 24 januari 2004 @ 15:59:
- wat als je ljist leeg is ?
- waarom met zo'n vieze break werken ?

oplossing met een lusje is stuk beter dan een recursieve funtie te gebruiken voor zo'n probleem

- Lijst kan niet leeg zijn volgens de opdracht dus hoef ik daar ook niet op te controleren (misschien heb ik de opdracht hierboven niet helemaal goed omschreven )

- Waarom geen break? wat is er mis met een break??

[Infinitive]

Je hebt de break en hulpvariable niet nodig: je zou meteen een return false kunnen doen. Je weet nu dat als je de loop voortijdig verlaat, dat dan niet aan de klein-naar-groot-sorteer-eigenschap is voldaan. Als je wel de loop op een normale manier verlaat, dus als code in je functie na de while-loop wordt uitgevoerd, dat dan wel aan de eigenschap voldaan wordt en je een return true kan doen.

Aan de andere kant kan zo'n hulpvariable handig zijn. In plaats van de break zou je van je loopconditie kunnen maken: (L->next != NULL && hulp). Het voordeel hierbij is dat je nu alleen de loop kan verlaten wanneer deze conditie niet meer geldt. Dit is eenvoudiger wanneer je de correctheid van je code zou willen bewijzen (topics: "loop invariant" / "loop inductie").

Verder natuurlijk niet je "return hulp;" aan het eind van deze functie vergeten
En misschien dat je ook een toepasselijkere naam kan verzinnen voor je hulpvariable nu je toch bezig bent?

[ Voor 32% gewijzigd door Infinitive op 24-01-2004 16:47 ]

[rrrrob]

Infinitive schreef op 24 januari 2004 @ 16:44:
Je hebt de break en hulpvariable niet nodig: je zou meteen een return false kunnen doen. Je weet nu dat als je de loop voortijdig verlaat, dat dan niet aan de klein-naar-groot-sorteer-eigenschap is voldaan. Als je wel de loop op een normale manier verlaat, dus als code in je functie na de while-loop wordt uitgevoerd, dat dan wel aan de eigenschap voldaan wordt en je een return true kan doen.

Aan de andere kant kan zo'n hulpvariable handig zijn. In plaats van de break zou je van je loopconditie kunnen maken: (L->next != NULL && hulp). Het voordeel hierbij is dat je nu alleen de loop kan verlaten wanneer deze conditie niet meer geldt. Dit is eenvoudiger wanneer je de correctheid van je code zou willen bewijzen (topics: "loop invariant" / "loop inductie").

Verder natuurlijk niet je "return hulp;" aan het eind van deze functie vergeten
En misschien dat je ook een toepasselijkere naam kan verzinnen voor je hulpvariable nu je toch bezig bent?

Nog 1 laatste poging dan, naam is niet het belangrijkste in dit geval denk ik:

code:

bool Sorted (pEl L)
{
  bool hulp=true;
  
  while (L->next != NULL && hulp)
  {
     if ( ! ((L->w) < (L->next->w)) ) hulp = false;
     else L = L -> next;
  }
  return hulp; // natuurlijk deze niet vergeten
}

[Soultaker]

Hij lijkt me goed, zo. Zelf zou ik het korter doen en die hulpvariabele afschaffen. Sowieso vind ik 'hulp' geen variabelenaam; noem 'm dan gelijk 'a' of kies een echt zinnige naam 'gesorteerd' ofzo.

[PrisonerOfPain]

Mag ik vragen waar je de oude L dan laat?

[Verwijderd]

1. Je functie werk verkeerd als er twee dezelfde getallen in de lijst voorkomen (hij zal dan altijd false teruggeven, ookal is de lijst wel gesorteerd).

2. bool is geen C type (wel C++), in C gebruik je normaalgesproken het type int (0 = false en alles wat niet nul is is true). De waardes 'true' en 'false' bestaan dus ook niet in C. Wel kun je ze zelf definiëren, b.v.
#define TRUE 1
#define FALSE 0
Het is conventie om ze dan met hoofdletters te definiëren.

3. Over conventies (dit zijn geen programmeerfouten): normaalgesproken begin je functie- en variabelenamen niet met een hoofdletter, dus gebruik sorted i.p.v. Sorted en l i.p.v. L.

Verder zou hij inderdaad nog wel iets eleganter/eenvoudiger/korter kunnen...
Succes met je tentamen!

Edit: je gebruikt ook nog C++ stijl commentaren (die met //), dat is ook geen C. In C mag je alleen /* ... */ commentaren gebruiken.

[ Voor 10% gewijzigd door Verwijderd op 24-01-2004 18:43 ]

[rrrrob]

Verwijderd schreef op 24 januari 2004 @ 18:39:
1. Je functie werk verkeerd als er twee dezelfde getallen in de lijst voorkomen (hij zal dan altijd false teruggeven, ookal is de lijst wel gesorteerd).

klopt, is met een "=" erbij ook opgelost, maar daar zal de leraar in een schriftelijk tentamen niet zoveel moeite mee hebben.

2. bool is geen C type (wel C++), in C gebruik je normaalgesproken het type int (0 = false en alles wat niet nul is is true). De waardes 'true' en 'false' bestaan dus ook niet in C. Wel kun je ze zelf definiëren, b.v.
#define TRUE 1
#define FALSE 0
Het is conventie om ze dan met hoofdletters te definiëren.

hmm, het vak heet c, het boek dat we gebruiken is "de programmeertaal c" en de programeeromgeving is borland c++. En de leraar gebruikt bool ook in zijn voorbeelden dus.....

3. Over conventies (dit zijn geen programmeerfouten): normaalgesproken begin je functie- en variabelenamen niet met een hoofdletter, dus gebruik sorted i.p.v. Sorted en l i.p.v. L.

Verder zou hij inderdaad nog wel iets eleganter/eenvoudiger/korter kunnen...
Succes met je tentamen!

Edit: je gebruikt ook nog C++ stijl commentaren (die met //), dat is ook geen C. In C mag je alleen /* ... */ commentaren gebruiken.

conventies, nooit van gehoord misschien volgend semester. (of ik heb niet goed opgelet)

[Soultaker]

rrrrob schreef op 24 januari 2004 @ 18:56:
hmm, het vak heet c, het boek dat we gebruiken is "de programmeertaal c" en de programeeromgeving is borland c++. En de leraar gebruikt bool ook in zijn voorbeelden dus.....

Nou? Dus wat?

[.oisyn]

Verwijderd schreef op 24 januari 2004 @ 18:39:
3. Over conventies (dit zijn geen programmeerfouten): normaalgesproken begin je functie- en variabelenamen niet met een hoofdletter, dus gebruik sorted i.p.v. Sorted en l i.p.v. L.

Dit is natuurlijk rijnste onzin. Jij doet dat zo, en ik ook, maar dat wil nog niet zeggen dat iedereen dat maar moet doen. Als hij z'n functies en variabelen wilt laten beginnen met hoofdletters is daar natuurlijk niets mis mee.

en rrrrob, je leraar mag dan wel bool gebruiken, maar dat wil nog niet zeggen dat het ook goed is. Eigenlijk gebruiken jullie volgens mij gewoon een C++ compiler om C-code te compileren, wat in de meeste gevallen wel goed gaat. Alleen je zit wel ineens met het feit dat dingen die in C fout horen te gaan ook ineens goed kunnen gaan (zoals het gebruik van bool)

[WildernessChild]

Het kan nog iets simpeler:

C:

bool Sorted (pEl L)
{
  while (L->next) {
    if(L->w > L->next->w)
      return false;
    L = L->next;
  }
  return true;
}

Dit dus afgezien van bovenstaande conventies en dat het type bool in C niet bestaat. Verder ook niet getest... veel succes ermee
Oh ja, een lege lijst kan hier dus niet bestaan omdat je altijd tenminste een element hebt, namelijk dat waarnaar de pointer verwijst. Of wordt anders een NULL-pointer gegeven?

[farlane]

.oisyn schreef op 26 januari 2004 @ 15:06:
Alleen je zit wel ineens met het feit dat dingen die in C fout horen te gaan ook ineens goed kunnen gaan (zoals het gebruik van bool)

En andersom ....

[Macros]

Zelfde code, alleen dan poging voor onleesbaarheids prijs

C:

bool Sorted(pEl L){ 
  for(;L->next;L=L->next)
    (L->w > L->next->w)?return 0:;
  return 1; 
}

[.oisyn]

farlane schreef op 26 januari 2004 @ 23:24:

En andersom ....

wat in de meeste gevallen wel goed gaat

Macros schreef op 27 januari 2004 @ 00:54:
Zelfde code, alleen dan poging voor onleesbaarheids prijs

C:

bool Sorted(pEl L){ 
  for(;L->next;L=L->next)
    (L->w > L->next->w)?return 0:;
  return 1; 
}

het lijkt me wel noodzakelijk dat het gewoon compiled

[ Voor 50% gewijzigd door .oisyn op 27-01-2004 00:59 ]