Here you go--examples of calling each function is in main. Use gcc to compile:
#include "stdio.h"
typedef struct dog dog;
struct dog {
char name[20]; /* The dog's name */
char owner[20]; /* The owner of dog */
dog *next; /* Pointer to the next dog */
};
/* For list update operations, return new head pointer since that may
change (after deletion, sorting, etc.) */
dog *addtolist(dog *list, char *name, char *owner) { /* Traverse list
and add to the end */
dog *tmp, *cur;
tmp = (struct dog *)malloc(sizeof(struct dog));
strcpy(tmp->name, name);
strcpy(tmp->owner, owner);
tmp->next = NULL;
cur = list;
if (cur == NULL) {
list = tmp;
} else {
while (cur->next != NULL)
cur = cur->next;
cur->next = tmp;
}
return list;
}
dog *removefromlist(dog *list, char *name) { /* Traverse list and
remove matching element(s) */
dog *tmp = NULL, *cur;
cur = list;
while (cur != NULL) {
if (strcmp(cur->name, name) == 0) { /* A match in name */
if (cur->next == NULL && tmp == NULL) { /* Only element case */
free(cur);
list = NULL;
break;
} else {
if (tmp == NULL) { /* First element case */
list = cur->next;
free(cur);
cur = list;
} else {
tmp->next = cur->next;
free(cur);
cur = tmp->next;
}
continue;
}
}
tmp = cur;
cur = tmp->next;
}
return list;
}
/* print does not alter list so does not need to return head pointer */
void printlist(dog *list) {
dog *point;
point = list;
while (point != NULL)
{
printf("%s is owned by %s.\n", point->name, point->owner);
point = point->next;
}
}
dog *sortlist(dog *list) { /* This sort algorithm is based on
mergesort--see web page link in comments */
dog *p, *q, *e, *tail, *oldhead;
int insize, nmerges, psize, qsize, i;
if (!list)
return NULL;
insize = 1;
while (1) {
p = list;
oldhead = list; /* only used for circular linkage */
list = NULL;
tail = NULL;
nmerges = 0; /* count number of merges we do in this pass */
while (p) {
nmerges++; /* there exists a merge to be done */
/* step `insize' places along from p */
q = p;
psize = 0;
for (i = 0; i < insize; i++) {
psize++;
q = q->next;
if (!q) break;
}
/* if q hasn't fallen off end, we have two lists to merge */
qsize = insize;
/* now we have two lists; merge them */
while (psize > 0 || (qsize > 0 && q)) {
/* decide whether next element of merge comes from p or q */
if (psize == 0) {
/* p is empty; e must come from q. */
e = q; q = q->next; qsize--;
} else if (qsize == 0 || !q) {
/* q is empty; e must come from p. */
e = p; p = p->next; psize--;
} else if (strcmp(p->name, q->name) <= 0) {
/* First element of p is lower (or same);
* e must come from p. */
e = p; p = p->next; psize--;
} else {
/* First element of q is lower; e must come from q. */
e = q; q = q->next; qsize--;
}
/* add the next element to the merged list */
if (tail) {
tail->next = e;
} else {
list = e;
}
tail = e;
}
/* now p has stepped `insize' places along, and q has too */
p = q;
}
tail->next = NULL;
/* If we have done only one merge, we're finished. */
if (nmerges <= 1) /* allow for nmerges==0, the empty list case */
return list;
/* Otherwise repeat, merging lists twice the size */
insize *= 2;
}
}
main() { /* Main test program: examples of calling the above functions */
dog *list;
list = addtolist(NULL,"Jim","Jason");
printf("\nInitial list:\n");
printlist(list);
list = addtolist(list,"Jack","Jill");
list = addtolist(list,"John","Jennifer");
printf("\nAfter adding to list:\n");
printlist(list);
list = sortlist(list);
printf("\nAfter sorting list:\n");
printlist(list);
list = removefromlist(list,"Jack");
printf("\nAfter removing from list:\n");
printlist(list);
} |
