where do i start with a bubble sort on a linked list???
Printable View
where do i start with a bubble sort on a linked list???
from the linked list , the solution will depend on how you implement the linked list
Post your list and I'll work on it later. After I hand out candies for the kids a.k.a Haloween
Also specify by what key data you want the list sorted according to.
struct empDetails {
int empNumber;
char empLastName[20];
char empFirstName[20];
float empRate;
struct empDetails *next;
};
int main(int argc, char *argv[])
{
int field;
struct empDetails *start, *temp, *tail;
FILE *records;
if (argc != 3) {
printf("\nError - Incorrect number of arguements.");
printf("\nSyntax: %s filename field.\n", argv[0]);
exit(1);
}
field = atoi(argv[2]);
if ((field < 1) || (field > 4)) {
printf("\nError - Field must be an integer value in range 1 to 4\n");
exit(1);
}
if ((records = fopen(recordFile, "r")) == NULL) {
printf("\nError - Unable to access %s\n", recordFile);
exit(1);
}
records = fopen(recordFile, "r"); /* Open file */
temp = (struct empDetails *) malloc(sizeof(struct empDetails));
fscanf(records, "%d%s%s%f", &temp->empNumber, temp->empLastName,
temp->empFirstName, &temp->empRate);
start = tail = temp;
while (!feof(records)) { /* Allocate memory, read and store data */
temp = (struct empDetails *) malloc(sizeof(struct empDetails));
fscanf(records, "%d%s%s%f", &temp->empNumber, temp->empLastName,
temp->empFirstName, &temp->empRate);
if (start == NULL) {
start = temp;
tail = temp;
}
else {
tail->next = temp;
tail = temp;
}
}
fclose(records);
}
sorting based on 3rd token from the command line
if 1 then sort based on empNumber
if 2 then sort based on empLastName
if 3 then sort based on empFirstName
if 4 then sort based on empRate
Okay, I'll work on it as soon as I get up in the morning. Sounds cool. BTW I have done this before but not recently so I'll probably look some of this up. I would do it tonight but it's late already.
Oh yeah, one more thing before I go to sleep. Lets put this thing in a function because it is useless without.
Okay, I'm working on it. I remember doing this somehow where a pointer to the head of the list was passed to the function, and a 'new' list was returned. A new list was actually built, while the old list was deleted. Damn, where are those labs? I have a book here, I'll see what I can come up with. Give me a few hrs. I want to use functions and organize your code that you have already.
Alright, I have found a way to sort a linked list. Does it have to be a bubble sort? The way I found to do it is that you pass a pointer to the list. You than disect that list while building a new ordered list. The new ordered lists gets returned. It's not exactly bubble sort although it is possible to use bubble sort. First though does it have to be? I think this other way is more efficient.
Dude, are you there? I'll post my answer in about 1 hr. Tell me if you specifically need bubble sort.
hi unregged
why dont you try this
get a fn t traverse until the end of list and hence return the no of nodes
(u might do this in the first pass of the bubble sort as well)
once you know the no of nodes you can bubble sort
my textbook tells me that it would be like
for 1 to n
for 1 to n-1
}
}
then as in bubble sort exchange the pointers instead of the data so its much faster
Okay well I finished the program, but I have one question. What is the second arguement? Why don't you make that the data filepath as in:
executablename datafilepath 1
Because this would make the most sense, but for now here is the code without setting it up like that, but arg 2 is doesn't mean crap all for now, unless you want that to mean something. Let me know.
Code:#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct empDetails {
int empNumber;
char empLastName[20];
char empFirstName[20];
float empRate;
struct empDetails *next;
};
struct empDetails * BuildList(struct empDetails *);
void PrintList(struct empDetails *);
struct empDetails * SortList(struct empDetails *, int);
int SortField(int argc , char *argv[] );
///////////////////////////////////////////////
int main(int argc, char *argv[])
{
struct empDetails * list = NULL;
int field = SortField(argc,argv);
list = BuildList(list);
PrintList(list);
printf("Above is the unsorted list.\n\n");
list = SortList(list, field);
PrintList(list);
printf("Above is the sorted list.\n\n");
return 0;
}
////////////////////////////////////////////////////////
struct empDetails * BuildList(struct empDetails * hp)
{
FILE *records;
struct empDetails *newp = NULL;
if ((records = fopen("recordFile.txt", "r")) == NULL) {
perror("\nError - No data file!");
exit(1);
}
newp = (struct empDetails *) malloc(sizeof(struct empDetails));
while( fscanf(records, "%d%s%s%f", &newp->empNumber, newp->empLastName,
newp->empFirstName, &newp->empRate) != EOF)
{
newp->next = NULL;
if(hp == NULL)
{
hp = newp;
}else
{
newp->next = hp;
hp = newp;
}
newp = (struct empDetails *) malloc(sizeof(struct empDetails));
}
//delete allocated memory for the last node which is not needed
free(newp);
fclose(records);
return hp;
}
////////////////////////////////////////////////////////////////////////
void PrintList(struct empDetails * hp)
{
while(hp)
{
printf("%d %s %s %.2f is at memory address %p\n", hp->empNumber,
hp->empLastName, hp->empFirstName, hp->empRate, hp);
hp = hp->next;
}
}
//////////////////////////////////////////////////////////////////
struct empDetails * SortList(struct empDetails * hp, int field)
{
struct empDetails *freep = NULL, *returnp = NULL;
struct empDetails *prep = NULL, *curtp = NULL;
struct empDetails *newp = NULL;
while(hp)
{
//node for new list that will be returned
newp = (struct empDetails *) malloc (sizeof(struct empDetails));
newp->empNumber = hp->empNumber;
strcpy(newp->empLastName, hp->empLastName);
strcpy(newp->empFirstName, hp->empFirstName);
newp->empRate = hp->empRate;
newp->next = NULL;
//get rid of old list node by node
freep = hp;
//If this is the first node of the new list
if(returnp == NULL)
{
returnp = newp;
}
if(field == 1 && newp->empNumber > returnp->empNumber)
{
newp->next = returnp;
returnp = newp;
}
if(field == 2 && strcmp(newp->empLastName,returnp->empLastName) > 0)
{
newp->next = returnp;
returnp = newp;
}
if( field == 3 && strcmp(newp->empFirstName, returnp->empFirstName) > 0)
{
newp->next = returnp;
returnp = newp;
}
if(field == 4 && newp->empRate > returnp->empRate)
{
newp->next = returnp;
returnp = newp;
}
else
{
prep = returnp;
curtp = returnp->next;
if(field == 1) while(curtp != NULL && newp->empNumber < curtp->empNumber)
if(field == 2) while(curtp != NULL && strcmp(newp->empLastName,curtp->empLastName) < 0)
if(field == 3) while(curtp != NULL && strcmp(newp->empFirstName,curtp->empFirstName) < 0)
if(field == 4) while(curtp != NULL && newp->empRate < curtp->empRate)
{
prep = curtp;
curtp = curtp->next;
}
prep->next = newp;
newp->next = curtp;
}//end of nested if else statments
//get next node of old list
hp = hp->next;
//free used node of old list
free(freep);
}//end of while
return returnp;
}
////////////////////////////////////////////////////////
int SortField(int argc , char *argv[] )
{
/*
sorting based on 3rd token from the command line
if 1 then sort based on empNumber
if 2 then sort based on empLastName
if 3 then sort based on empFirstName
if 4 then sort based on empRate
*/
int field;
if (argc != 3) {
printf("\nError - Incorrect number of arguements.");
printf("\nSyntax: %s filename field.\n", argv[0]);
exit(1);
}
field = atoi(argv[2]);
if ((field < 1) || (field > 4)) {
printf("\nError - Field must be an integer value in range 1 to 4\n");
exit(1);
}
return field;
}