» »

[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 ?
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..
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.
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.
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.
Certainty of death. Small chance of success. What are we waiting for?


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

[C] Obrni sklad

Oddelek: Programiranje
101066 (712) Invictus
»

C strukture, kazalci naloga pomoc

Oddelek: Programiranje
51375 (1270) DavidJ
»

[C++] Linker error

Oddelek: Programiranje
51197 (1197) Quikee
»

[C] Povezani seznami in kazalci

Oddelek: Programiranje
242453 (2020) Good Guy
»

[NALOGA][C] fri-vsp - strukture (struct)

Oddelek: Programiranje
101455 (1296) Vesoljc

Več podobnih tem