Inputting into linked list and then sorting it

Howdy,

I need a little bit of help with the bottom of my program, where I think I'm inputting my data into a singly linked list. I had a family emergency and had to leave my computer at school, so I'm working with a text editor and no compiler or anything so I can't really check my code. But I was wondering if you could take a look at the bottom portion after where I declare " char input_buffer[122];". My TA told me what to do, and I think I'm doing what he said, but I'm not sure.

Basically, I have to take lines of input that look like this:

University ID#, Last, first, account, acount email, major, classification
711005290, Allen, Donaldson, d0a5290, [email protected], ENTL, U3

and do some sinlgy linked stuff and then sort it by last name. I think I can figure out how to sort it with qsort, but I really don't think I understand this singly linked stuff all that well and the very bottom of my code is where I try to import the data into one. So if you could point me in the right direction I'd appreciate it. Thank you.

Code:

#include <stdio.h> #include <string.h> #include <ctype.h> #include <stdlib.h> #include "lab-09.h" typedef struct Student_data { char UIN[10]; char *name; /*12-24 with 24 max*/ char *username; /*max of 12 */ char *email; /*max of 30 */ char major[5]; char class[3]; struct Student_data *next; } Student_data; /*Setup the program to accept multiple arguments as input*/ int main (int argc, char *argv[]) { int len=0, i=0, count=0, tempnum=0, cfg_lines=0, skip_lines, ss_result; char *line_ptr, one_line[96], temp[100], line[100]; FILE *input; FILE *config; FILE *output; if (4 != argc) { fputs ("Not enough arguments.\n", stderr); return 1; } /*Open the config file and extract all needed data*/ config=fopen(argv[1], "r"); if(config==NULL) { fputs("Configuration was unable to be opened\n",stderr); return 1; } else { fputs("Configuration was opened successfully\n",stderr); } /*Open the input and output files and prepare them for use with "r" and "w" respectively*/ input=fopen(argv[2], "r"); if(input==NULL) { fputs("Input file was unable to be opened\n",stderr); return 1; } else { fputs("Input file was opened successfully\n",stderr); } output=fopen(argv[3], "w"); if(output==NULL) { fputs("Output file was unable to be opened\n",stderr); return 1; } else { fputs("Output file was opened successfully\n",stderr); } line_ptr=fgets(one_line, 96, config); sscanf(one_line, "%d", &cfg_lines); int length[cfg_lines]; char tags[cfg_lines][80]; for(i=0; i<cfg_lines; i++) { line_ptr=fgets(one_line, 64, config); ss_result = sscanf(one_line,"%d %s", &length[i], &tags[i]); if (2 != ss_result) { fputs ("Problem with config file", stderr); return 1; } } line_ptr=fgets(one_line, 64, config); ss_result = sscanf(one_line,"%d", &skip_lines); if (1 != ss_result) { fputs ("Problem with config file", stderr); return 1; } /*end configuration stuff and input/output operations*/ /**/ char input_buffer[122]; Student_data *head, *cur; head = 0; for (i=0; i<=skip_lines; i++) { line_ptr=fgets(one_line, 64, input); } for(i=0; 1; i++) { /*Read one line from input;*//**/ line_ptr=fgets(input_buffer, 122, input); if(line_ptr==NULL) break; cur = calloc (1, sizeof(student_data); cur->name = calloc (lengths[1]+lengths[2]+1, sizeof(char)); cur->username = calloc(lengths[3] + 1), sizeof(char)); cur->email= calloc(lengths[4] + 1), sizeof(char)); /*use strstr to find all of the commas*//**/ char *last_name_comma = strstr (input_buffer, ","); if (! last_name_comma) { fputs (missing a field,stderr); return 1; } char *first_name_comma = strstr (last_name_comma+1, ","); if (! first_name_comma) { fputs (missing a field,stderr); return 1; } char *cs_account_comma = strstr (first_name_comma+1, ","); if (! cs_account_comma) { fputs (missing a field,stderr); return 1; } char *cs_email_comma = strstr (cs_account_comma+1, ","); if (! cs_email_comma) { fputs (missing a field,stderr); return 1; } char *major_name_comma = strstr (cs_email_comma+1, ","); if (! major_name_comma) { fputs (missing a field,stderr); return 1; } char *class_comma = strstr (major_name_comma+1, ","); if (! class_comma) { fputs (missing a field,stderr); return 1; } char *new_line = strstr(class_comma + 1, '\n'); *last_name_comma = 0; last_name_comma += 2; *first_name_comma = 0; first_name_comma += 2; *cs_account_comma = 0; cs_account_comma +=2; *cs_email_comma = 0; cs_email_comma += 2; *major_name_comma = 0; major_name_comma += 2; *class_comma = 0; class_comma += 2; *new_line = 0; strcpy (cur->UIN, last_name_comma); cur->next = head; head = cur; strcpy (cur->name, first_name_comma); cur->next = head; head = cur; strcpy (cur->username, cs_account_comma); cur->next = head; head = cur; strcpy (cur->email, cs_email_comma); cur->next = head; head = cur; strcpy (cur->major, major_name_comma); cur->next = head; head = cur; strcpy (cur->class, class_comma); cur->next = head; head = cur; strcpy (cur->next, new_line); cur->next = head; head = cur; } return 0; }

It seems to me that your database will end up looking like this:

[ Last, First, User, Email, Major, Class, Next ]
0 = [ Allen, 0, 0, 0, 0, 0, null ]
1 = [ 0, Donaldson, 0, 0, 0, 0, 0 ]
2 = [ 0, 0, d0a5290, 0, 0, 0, 1 ]
3 = [ 0, 0, 0, [email protected], 0, 0, 2 ]
4 = [ 0, 0, 0, 0, ENTL, 0, 3 ]
5 = [ 0, 0, 0, 0, 0, U3, 4 ]
Giving you this kind of 1-dimensional cascade down a 2-dimensional array because you progress to the next node each time you apply some data to the current node. You should not progress to the next node until you have applied all the data to the current node.

Code:

... //apply ALL data to current node strcpy (cur->UIN, last_name_comma); strcpy (cur->name, first_name_comma); strcpy (cur->username, cs_account_comma); strcpy (cur->email, cs_email_comma); strcpy (cur->major, major_name_comma); strcpy (cur->class, class_comma); strcpy (cur->next, new_line); //NOW progress to next node cur->next = head; head = cur; ...

Another thing I'd mention here is that you might consider breaking your nodes into 2 pieces. One for the linked list node, and the other for the student data. This will make it much easier to swap data when you're sorting.

Code:

typedef struct { char UIN[10]; char *name; /*12-24 with 24 max*/ char *username; /*max of 12 */ char *email; /*max of 30 */ char major[5]; char class[3]; } tStudent_data; typedef struct Node { void *data; struct Node *next; } tNode; void swap(tNode *a, tNode *b) { void *temp = a->data; a->data = b->data; b->data = temp; }

Although, considering that you're constructing the list with the hopes to eventually sort it, it would be far more efficient to use insertion sort during construction, rather than using qsort post-construction. The way this works is, as each node is added, it scans through the existing nodes until it finds one that is greater than it, at which point it stops, and inserts itself before that node. Besides, with a singly linked list, it's difficult to say how qsort would work, or any sort for that matter, since you can't jump around or even step backwards in the list without taking N runtime for that instruction alone.

Here's the insertion sort code (utilizing the 2-piece nodes I mentioned above):

Code:

int compare(char *t1, char *t2); //t1>t2 = 1, t2>t1 = -1, t2=t1 = 0 void add(tNode *head, void *data) { tNode *prev = NULL,*cur = head; tNode *n = malloc(sizeof(tNode)); n->data = data; while (cur != NULL) { if (compare(cur->data->UIN,data->UIN) == -1) { n->next = cur; if (prev == NULL) { head = n; //can I do this? Will this update the external pointer? } else { prev->next = n; } return; } prev = cur; cur = cur->next; } prev->next = n; }

You'd have to code the compare function yourself.

(notice, I have not tested this code and am unsure whether it would work or not. Anybody who looks at this is encouraged to look it over and critique it)

Hey, that makes a lot of sense man. You've just like quadrupled my understanding of this stuff. I should have access to my computer soon, and a compiler and whatnot, so I'll be able to test out all my code and try doing what you suggested. Thanks again.

A linked list is an extremely poor (i.e. probably the WORST) choice for storing data that is about to be sorted.

Why? It's pretty easy to sort a linked list. You can if you like, allocate an array of pointers to node, set them all to the elements of the list, sort that, and then just walk through and relink the pointers.

Code:

for( x = 0; x < nodes; x++ ) array[ x ]-> next = x + 1 < nodes ? array[ x + 1 ] : NULL;

Quzah.

Quote:

Originally Posted by quzah

Why? It's pretty easy to sort a linked list. You can if you like, allocate an array of pointers to node, set them all to the elements of the list, sort that, and then just walk through and relink the pointers.

Yeah, but that's not really "sorting the linked list." The only sorting algorithms I can think of that map directly and efficiently to a linked list are bubble sort and insertion sort, and neither of those sorts is particularly efficient.

Quote:

Yeah, but that's not really "sorting the linked list."

If the list gets sorted, does it really matter?

Quote:

The only sorting algorithms I can think of that map directly and efficiently to a linked list are bubble sort and insertion sort, and neither of those sorts is particularly efficient.

Isn't merge sort supposed to be good for sorting stuff that comes in over a stream? That's a lot like traversing a linked list, so merge sort should be good for them too, and it's a lot more efficient that bubble sort and insertion sort.

Quote:

Originally Posted by Noir

If the list gets sorted, does it really matter?

If the sorting of the data is just some secondary objective, no. If the only purpose is to read some data and then sort it, I have no idea why a person would use a linked list.

Quote:

Isn't merge sort supposed to be good for sorting stuff that comes in over a stream? That's a lot like traversing a linked list, so merge sort should be good for them too, and it's a lot more efficient that bubble sort and insertion sort.

True. Honestly, I was trying to avoid having to answer questions about it ;)