Code:
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
struct _node {
char *name;
int ID;
struct _node *next;
};
typedef struct _node node;
char *buffer;
int LLsize (node *head) {
node *then;
int i=1;
if ((then=head->next)==NULL) return 0;
while ((then=then->next)!=NULL) i++;
return i;
}
void LLadd (node *head, char *data, int num) {
node *new, *ptr;
new=malloc(sizeof(node));
if (head->next==NULL) head->next=new;
else {ptr=head->next;
while (ptr->next!=NULL) ptr=ptr->next;
ptr->next=new;}
new->name=malloc(strlen(data)+1);
strcpy(new->name,data);
new->ID=num;
new->next=NULL;
}
int streamline (FILE *strIN) {
int i=0, chr;
buffer=malloc(1);
while ((chr=fgetc(strIN))!=EOF) {
if (buffer==NULL) return -1;
if (chr=='\n') { buffer[i]='\0';
return i+1;}
buffer[i]=chr;
buffer=realloc(buffer,++i+1);
}
buffer[i]='\0';
return 0;
}
int comparewords (char *one, char *two) {
int depth=0, dv, retv=0;
while (1) { dv=depth;
if ((one[depth] == 0) && (two[depth] == 0)) return 0;
else if (one[depth] == 0) return 1;
else if (two[depth] == 0) return 2;
if (one[depth] == two[depth]) depth++;
else if (one[dv] < two[dv]) {
retv=1;
} else if (one[dv] > two[dv]) {
retv=2;
}
if (retv>0) return retv;
}
return -1; //impossible
}
int comparenames (char *one, char *two) {
int retv,i;
char name1[256], name2[256], first1[128], last1[128], first2[128], last2[128];
strcpy(name1,one); strcpy(name2,two); // use copies and render lowercase
for (i=0;i<strlen(name1);i++) if ((name1[i]<97) && name1[i]!=' ') name1[i]+=32;
for (i=0;i<strlen(name2);i++) if ((name2[i]<97) && name2[i]!=' ') name2[i]+=32;
sscanf(name1,"%[A-Za-z] %[A-Za-z]",first1,last1);
sscanf(name2,"%[A-Za-z] %[A-Za-z]",first2,last2);
if ((retv=comparewords(last1,last2))!=0) return retv;
if ((retv=comparewords(first1,first2))!=0) return retv;
return 0; // names are identical
}
int main () {
int num, retv, flag, i, tmp, count=0;
char name[256], *ptr;
FILE *fstRO=fopen("/root/test/names.txt","ro");
node *head, *now;
if (fstRO==NULL) {puts("fopen fail");
return -1;}
head=malloc(sizeof(node));
head->name=NULL; // head will be empty
head->next=NULL;
while ((retv=streamline(fstRO))!=0) {
if (retv<0) {puts("Memory allocation error!");
return -2;}
if (sscanf(buffer, "%[A-Za-z. ]:%d",name,&num)==2) LLadd(head,name,num);
free(buffer);
}
fclose(fstRO);
puts("____unsorted____");
now=head->next;
printf("%s (ID %d)\n",now->name,now->ID);
while ((now=now->next)!=NULL) printf("%s (ID %d)\n",now->name,now->ID);
printf("\nNumber of names=%d\n",num=LLsize(head));
while (1) { flag=0;
now=head->next;
for (i=0;i<(num-1);i++) {
if ((retv=comparenames(now->name,now->next->name))==2) {
ptr=now->name;
tmp=now->ID;
now->name=now->next->name;
now->ID=now->next->ID;
now->next->name=ptr;
now->next->ID=tmp;
flag=1;
}
now=now->next;
}
count++;
if (flag==0) break;
}
printf("Iterated list %d times\n\n",count);
puts("____Sorted____");
now=head->next;
printf("%s (ID %d)\n",now->name,now->ID);
while ((now=now->next)!=NULL) printf("%s (ID %d)\n",now->name,now->ID);
while (head->next!=NULL) {
now=head->next;
free(head->name);
free(head);
head=now;
}
free(head);
puts("\nDone.");
return 0;
}
The output looks like this:
Originally Posted by Bjarne Stroustrup (2000-10-14)
