Archived

This topic is now archived and is closed to further replies.

Russell

Sorting a doubly linked list in C

Recommended Posts

I am using a doubly linked list in C, and I have to write the output in sorted order by last name, then by first name if the last names are the same (like a telephone book). When I try to sort the list, the list has the correct first sorted entry, but no other entries (IE the list always has a size of 1, even if there were 10 entries before sorting). I have posted the relevant code below. My best guess is that I''m not removing nodes correctly, but I can''t figure out what I''m doing wrong. Help?
  
typedef struct Player Player;
struct Player {
	char	first_name[MAX_CHARS];
	char	last_name[MAX_CHARS];
	char	number[MAX_CHARS];
	char	position[MAX_CHARS];
	Player	* next_player;
	Player	* prev_player;
};

typedef struct List List;
struct List {
	Player	* head;
	Player	* tail;
};

void SortRoster (List * roster) {
	List	new_roster;
	Player	* player;

	new_roster.head = new_roster.tail = 0;

	while (roster->head != 0) {
		Player	* next_player = roster->head;
		for (player = roster->head; player != 0; player = player->next_player) {
			next_player = FirstPlayer(next_player, player);
		}
		RemovePlayer(next_player, roster);
		AddPlayer(next_player, &new_roster);
	}
	for (player = new_roster.head; player != 0; player = player->next_player) {
		RemovePlayer(player, &new_roster);
		AddPlayer(player, roster);
	}
}

void RemovePlayer (Player * player, List * roster) {
	
	if (player->next_player) {
		player->next_player->prev_player = player->prev_player;
	}

	if (player->prev_player) {
		player->prev_player->next_player = player->next_player;
	}

	if (roster->head == player)
		roster->head = player->next_player;
	if (roster->tail == player)
		roster->tail = player->prev_player;

	player->prev_player = 0;
	player->next_player = 0;
}

Player * FirstPlayer (Player * p1, Player * p2) {
	int result = strcmp(p1->last_name, p2->last_name);
	
	if (result < 0)
		return p1;
	if (result > 0)
		return p2;
	if (result == 0) {
		result = strcmp(p1->first_name, p2->first_name);
		if (result < 0)
			return p1;
		if (result > 0)
			return p2;
	}
	return p1;
}

void AddPlayer (Player * player, List * list) {
	if (list->head == 0) {
		list->head = player;
		list->tail = player;
	}
	else {
		player->prev_player = list->tail;
		list->tail->next_player = player;
		list->tail = player;
	}
}
  

Share this post


Link to post
Share on other sites
I''ll say this: For an easier linked list implementation, make initially list->head point to list->end and vice versa.

When you add nodes (to beginning), you do:

node->prev = list->head;
node->next = list->head->next;
list->head->next->prev = node;
list->head->next = node;

And when removing nodes, you do:

node->prev->next = node->next;
node->next->prev = node->prev;

No more conditionals.

Share this post


Link to post
Share on other sites
Second hint: write a CheckListSize function, and put it in asserts that you place at the start and end of your functions. eg. RemovePlayer should start with "int size; size = CheckListSize(list);" and end with "assert(CheckListSize(list) == size - 1);" You''ll soon find where you''re breaking the list.

[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]

Share this post


Link to post
Share on other sites
quote:
Original post by Kylotan
Second hint: write a CheckListSize function, and put it in asserts that you place at the start and end of your functions. eg. RemovePlayer should start with "int size; size = CheckListSize(list);" and end with "assert(CheckListSize(list) == size - 1);" You''ll soon find where you''re breaking the list.

I did as you suggested, but no asserts failed. This suggests (to me) that RemovePlayer works correctly and that players aren''t being added back, or that my list size function isn''t working.

  
int GetListSize (List * list) {
Player * player;
int size = 0;
for (player = list->head; player != 0; player = player->next_player)
size++;
return size;
}

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Kind of nitpicky thing that doesn''t even address your problem, but it''s confusing when the name of a struct is the same as one of the elements of the struct (next_player)

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
A couple of things. If you''re using a pure C compiler, variable declarations have to be the first statements in your functions. If you''re using a C++ compiler, i''d still be weary of declaring a variable in a loop. new_player is going to be redeclared each time you run the loop, which might have strange effects.

Does new_roster have the right list in it after the while loop?

Share this post


Link to post
Share on other sites
This is the wrong code, just at the end of SortRoster function:


      
for (player = new_roster.head; player != 0; player = player->next_player) {
RemovePlayer(player, &new_roster);
AddPlayer(player, roster);
}


After you move the player to the old roster, you can't keep using it to iterate through the new_roster.

But why must you copy the lists element by element anyway? Just do a
*roster = newroster;    



[edited by - Diodor on May 2, 2003 5:45:13 PM]

Share this post


Link to post
Share on other sites