Forum » Programiranje » [C] Narascajoce sortiranje linearnega seznama
[C] Narascajoce sortiranje linearnega seznama
Gwanaroth ::
Torej imam linearni kazalcni seznam, kjer dodajam elemenete na zacetek, s tole funkcijo:
struct element *dodaj(struct element *p, char *vred)
{
struct element *q;
q = (struct element*)malloc(sizeof(struct element)); //kazalec na nov element
strcpy(q->ime,vred);
q->naslednji = p;
return(q);
}
Ko seznam napolnim z dolocenim stevilom elementov, bi ga pred izpisom rad sortiral, narascajoce, po abecedi.
V seznamu hranim nize znakov..
Kaksna ideja, kako bi napravil sortiranje, preden bi seznam izpisal ?
struct element *dodaj(struct element *p, char *vred)
{
struct element *q;
q = (struct element*)malloc(sizeof(struct element)); //kazalec na nov element
strcpy(q->ime,vred);
q->naslednji = p;
return(q);
}
Ko seznam napolnim z dolocenim stevilom elementov, bi ga pred izpisom rad sortiral, narascajoce, po abecedi.
V seznamu hranim nize znakov..
Kaksna ideja, kako bi napravil sortiranje, preden bi seznam izpisal ?
Lights often keep secret hypnosis..
Vesoljc ::
jah, uporabljas polja znakov, torej rabis strcmp. kar se pa samega sorta tice, pa lahko uporabis kak preprost bubblesort. predvidevam, da elemente v seznamu znas prevezovati?
Abnormal behavior of abnormal brain makes me normal...
AndrejS ::
Če imaš kazalčni seznam je najbolje , da že pri dodajanju sortiraš = dodaš na pravo mesto!
Gwanaroth ::
strcmp() primerja dolzini dveh stringov. Jaz bi rad sortiral po _abecedi_, ne dolzini stringa.
Za prevezovanje bi rabil kak konkreten primer.
Prilepim celotno kodo:
-------------------------
#include < stdio.h>
#include < stdlib.h>
#include < string.h>
#include < ctype.h>
struct element
{
char niz[10];
struct element *naslednji;
};
void izpis(struct element *p)
{
while(p!=NULL) {
printf("%s ",p->niz);
p=p->naslednji;
}
printf("\n");
}
struct element *dodaj(struct element *p, char *vred)
{
struct element *q;
q = (struct element*)malloc(sizeof(struct element)); //kazalec na nov element
strcpy(q->niz,vred);
q->naslednji = p;
return(q);
}
main() {
struct element *zacetek;
int i;
char a[15];
zacetek=NULL;
for(i=0; i< = 10; i++) {
printf("Vnesi besedo:\n");
scanf("%s",&a);
zacetek = dodaj(zacetek,a);
}
izpis(zacetek);
}
----------------------------
//edit: AndrejS: lahko podaš primer? Ker mi ni jasno, kako primerjat elemente seznama..
Za prevezovanje bi rabil kak konkreten primer.
Prilepim celotno kodo:
-------------------------
#include < stdio.h>
#include < stdlib.h>
#include < string.h>
#include < ctype.h>
struct element
{
char niz[10];
struct element *naslednji;
};
void izpis(struct element *p)
{
while(p!=NULL) {
printf("%s ",p->niz);
p=p->naslednji;
}
printf("\n");
}
struct element *dodaj(struct element *p, char *vred)
{
struct element *q;
q = (struct element*)malloc(sizeof(struct element)); //kazalec na nov element
strcpy(q->niz,vred);
q->naslednji = p;
return(q);
}
main() {
struct element *zacetek;
int i;
char a[15];
zacetek=NULL;
for(i=0; i< = 10; i++) {
printf("Vnesi besedo:\n");
scanf("%s",&a);
zacetek = dodaj(zacetek,a);
}
izpis(zacetek);
}
----------------------------
//edit: AndrejS: lahko podaš primer? Ker mi ni jasno, kako primerjat elemente seznama..
Lights often keep secret hypnosis..
Zgodovina sprememb…
- spremenilo: Gwanaroth ()
Phil ::
bool less (element *prvi,element *drugi) { // testira prvi _pred_ drugi
bool prvi_krajsi=true;
int min=strlen(prvi->niz); // dolzina ni nujno 10???
if (strlen(drugi->niz)<min) {
min=strlen(drugi->niz);
prvi_krajsi=false;
}
for (int i=0;i<min;i++) {
if (prvi->niz[i]<drugi->niz[i]) return true; // upostevamo ASCII ureditev
if (prvi->niz[i]>drugi->niz[i]) return false;
}
// do dolzine krajsega niza sta oba niza enaka
if (prvi_krajsi) return true;
return false;
}
void swap (element *prvi,element *drugi) { // zamenja samo string-a, samo strukturo seznama pusti pri miru!
char temp;
for (int i=0;i<10;i++) {
temp=prvi->niz[i];
prvi->niz[i]=drugi->niz[i];
drugi->niz[i]=temp;
}
}
void sort (element *vrh) {
element *temp=NULL;
while (vrh->naslednji!=NULL) {
temp=vrh->naslednji;
while (temp!=NULL) {
if (less(temp,vrh)) swap(temp,vrh);
temp=temp->naslednji;
}
vrh=vrh->naslednji;
}
}
Zelo na hitro spisano, nisem sprobal ampak AFAIK bi moralo delat.
LP
Vesoljc ::
> strcmp() primerja dolzini dveh stringov
klik
This function starts comparing the first character of each string. If they are equal to each other continues with the following pair until the characters differ or until end of string is reached.
klik
This function starts comparing the first character of each string. If they are equal to each other continues with the following pair until the characters differ or until end of string is reached.
Abnormal behavior of abnormal brain makes me normal...
Gwanaroth ::
Hvala vam, sem uredil.
Vse pointerje sem shranil posebej v eno tabelo, nato pa:
for(i=0;i < ST_ELEMENTOV;i++) { //sortiranje
for(j=0;j < ST_ELEMENTOV;j++) {
if(strcmp((char *)pointers[i],(char *)pointers[j]) > 0) {
temp=pointers[i];
pointers[i]=pointers[j];
pointers[j]=temp;
}
}
}
Danke schön še enkrat.
Vse pointerje sem shranil posebej v eno tabelo, nato pa:
for(i=0;i < ST_ELEMENTOV;i++) { //sortiranje
for(j=0;j < ST_ELEMENTOV;j++) {
if(strcmp((char *)pointers[i],(char *)pointers[j]) > 0) {
temp=pointers[i];
pointers[i]=pointers[j];
pointers[j]=temp;
}
}
}
Danke schön še enkrat.
Lights often keep secret hypnosis..
Jebiveter ::
Ja, to deluje, dokler uporabljas to tabelo za dostopanje do elementov. Sam se vedno nimas presortiranega seznama (ce se sprehodis po njem ni sortiran).
Verjetno je dostopanje direktno prek tabele pointerjev najhiteje kar se da, problem se pojavi, ce se v seznam doda/jo elementi... potem mors zgradit novo tabelo, staro delocirat, presortirat novo tabelo. Po moje je bolj uporabno, ce s pomocjo presortirane tabele presortiras se seznam in potem pri dodajanju vstavljas na mesto kamor spada in ne na konec seznama.
Verjetno je dostopanje direktno prek tabele pointerjev najhiteje kar se da, problem se pojavi, ce se v seznam doda/jo elementi... potem mors zgradit novo tabelo, staro delocirat, presortirat novo tabelo. Po moje je bolj uporabno, ce s pomocjo presortirane tabele presortiras se seznam in potem pri dodajanju vstavljas na mesto kamor spada in ne na konec seznama.
Certainty of death. Small chance of success. What are we waiting for?
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | [C] Obrni skladOddelek: Programiranje | 1146 (792) | Invictus |
| » | C strukture, kazalci naloga pomocOddelek: Programiranje | 1454 (1349) | DavidJ |
| » | [C++] Linker errorOddelek: Programiranje | 1280 (1280) | Quikee |
| » | [C] Povezani seznami in kazalciOddelek: Programiranje | 2554 (2121) | Good Guy |
| » | [NALOGA][C] fri-vsp - strukture (struct)Oddelek: Programiranje | 1545 (1386) | Vesoljc |