C: Indsætte element på n-te plads i linked list
Hej,Jeg skal have sorteret en linket liste efter karakter, startende med den laveste.
Det er jeg også næsten færdig med, men den virker ikke helt.
funktionen gradelist opretter min linkede liste.
funktionen orderlist splitter min linkede liste op i to nye lister, en med det første element fra den originale liste (head) og en med de resterende (remaining).
funktionen sortlist sorterer de to nye lister ved at itere igennem remaining-listen og sammenligne det element vi står på i remaining med head-listen og hvis det er mindre så indsætte det før head-elementet.
Det virker også fint nok, men hvis remaining-elementet nu er større, er jeg nødt til at iterere igennem head-listen for at være sikker på at remaining-elementet ikke er mindre end andre elementer i head-listen. Det gør jeg sådan (current peger på det første element i head):
while(current != NULL){
if (remaining->grade <= current->grade){
parent = current;
printf("Indsaet her!%d <= %d", remaining->grade, current->grade);
temp = (Node*)malloc(sizeof(Node));
temp->name = remaining->name;
temp->grade = remaining->grade;
temp->next = parent;
head->next = temp;
break;
}
current = current->next;
}
Hvis remaining-elementet er mindre eller lig head-elemtentet vi står på, skal det indsættes før dette, men det kan jeg simpelthen ikke få til at virke ordentligt.
Kan nogen guide mig på rette vej?
Koden står herunder:
struct node{
char* name;
int grade;
struct node* next;
};
typedef struct node Node;
#include<stdio.h>
#include<stdlib.h>
Node *makestartlist();
void gradelist(Node* node);
void orderlist(Node* node);
void sortlist(Node* remaining, Node* head);
int get_high(Node* node);
int listlenghth(Node* node);
main(){
int choice, count;
char quit;
Node* nodelist;
//Make default linked list
nodelist = makestartlist();
do{
// User-interface
printf("*********MENU**********\n");
printf("3. Order list in increasing order\n");
printf("7. Stop\n");
scanf("%d", &choice);
switch (choice) {
case 3 :
orderlist(nodelist);
break;
default :
break;
}
} while(choice != 7);
}
Node *makestartlist(){
int i;
Node *first=NULL, *parent=NULL, *node;
// Declare array of structs
Node students[10] = {
{"Lars",10},
{"Bent",7},
{"Hans",9},
{"Lise",3},
{"Lone",5},
{"Inger",6},
{"Bo",11},
{"Else",8},
{"Atli",13},
{"Jens",0}
};
for (i=0; i<10 ;i++){
node = (Node*)malloc(sizeof(Node)); //Allocate memory
if (i == 0) first = node;
node -> name = students[i].name; //Add name
node -> grade = students[i].grade; //Add grade
node -> next = NULL;
if (i>0) parent -> next = node;
parent = node;
}
return first;
}
int listlength(Node* node){
int count = 0;
if (node != NULL){
while(node != NULL){
count++;
node = node->next;
}
}
else if (node == NULL){
count = 0;
}
return count;
}
void gradelist(Node* node){
printf("\n**********Show grade list*************\n");
//Print linked list
if (node != NULL){
while(node != NULL){
printf("Student: %s\tGrade: %d\n", node->name, node->grade);
node = node->next;
}
}
else {
printf("No students!");
}
printf("*********************************************\n\n");
}
void orderlist(Node* node){
/*
head contains the first element from the original linked list
remaining contatins the rest of the list
*/
Node *head=NULL, *first_head=NULL, *remaining, *first=NULL, *parent=NULL;
int i = 0, headlistlength;
printf("Order list in increasing order\n");
if (node != NULL){
head = (Node*)malloc(sizeof(Node));
head->name = node->name;
head->grade = node->grade;
head->next = NULL;
node = node->next;
while (node != NULL){
remaining = (Node*)malloc(sizeof(Node));
if (i == 0) first = remaining;
remaining->name = node->name;
remaining->grade = node->grade;
remaining->next = NULL;
if(parent != NULL) parent->next = remaining;
parent = remaining;
i++;
node = node->next;
}
}
remaining = first;
sortlist(remaining, head);
}
void sortlist(Node* remaining, Node* head){
int i = 0;
Node *first_head = head, *current=head, *temp=head, *parent=head;
int high = 0;
while(remaining != NULL){
current = head;
// Virker
if (listlength(head) == 1){
if (remaining->grade > head->grade){
temp = (Node*)malloc(sizeof(Node));
temp->name = remaining->name;
temp->grade = remaining->grade;
temp->next = NULL;
current->next = temp;
}
else{
head = (Node*)malloc(sizeof(Node));
head->name = remaining->name;
head->grade = remaining->grade;
head->next = current;
first_head = head;
}
}
else{
// Virker
if (remaining->grade <= head->grade){
head = (Node*)malloc(sizeof(Node));
head->name = remaining->name;
head->grade = remaining->grade;
head->next = current;
first_head = head;
}
else{
if (remaining->grade > head->grade){
high = get_high(current);
// Virker
if (high < remaining->grade){
temp = (Node*)malloc(sizeof(Node));
temp->name = remaining->name;
temp->grade = remaining->grade;
temp->next = NULL;
while(current->next != NULL){
current = current->next;
}
current->next = temp;
first_head = head;
}
// Virker IKKE :(
else{
while(current != NULL){
if (remaining->grade <= current->grade){
parent = current;
printf("Indsaet her!%d <= %d", remaining->grade, current->grade);
temp = (Node*)malloc(sizeof(Node));
temp->name = remaining->name;
temp->grade = remaining->grade;
temp->next = parent;
head->next = temp;
break;
}
current = current->next;
}
first_head = head;
}
}
}
}
gradelist(first_head);
remaining = remaining->next;
}
}
int get_high(Node* node){
int high=0;
while (node != NULL){
if (node->grade > high) high = node->grade;
node = node->next;
}
return high;
}
