sorted Linked list problem

jazzsc79 (2)
I am trying to write the program for sorted-liked list. By the way if I try to send the data to fuction from user input, the program gets crashed, but if I call the function with given data, it works fine. Could you tell me what's the problem. I comment out the problem part below (Case one and Case two).
Thank you.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
#include <iostream>
#include <string>
#include "songList.h"

using namespace std;

void main ()
{
	
	songList list;
	const int MAX_SIZE = 81;
	char songName[MAX_SIZE];



	bool check = true;
	while (check)
	{
//Case one start
		cout << "Enter the song name (to finish enter '~') : ";
		cin.getline(songName,MAX_SIZE);
		if (songName[0] == '~')
		{
			check = false;
		}
		list.addSong(songName);
//Case one end
//Case two start
		list.addSong("1111");
		list.addSong("2");
		list.addSong("3");
		list.addSong("4");
		list.addSong("5");
//Case two below 	
	}

	list.printSongList();

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
#include <iostream>
#include <string>
using namespace::std;


class songList
{
public:
	songList();
	~songList();
	void addSong(char * songName);
	void addReview();
	void printSongList() const;
	void printSongListReview() const;
private:
	struct songListStr
	{
		char * song;
		songListStr * review;
		songListStr * next;
	};
	struct reviewListStr
	{
		char * review;
		reviewListStr * next;
	};
	songListStr * songHead;
	reviewListStr * reviewHead;
	
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
 
#include <iostream>
#include <string>
#include "songList.h"

songList::songList()
{
	songHead = NULL;
	reviewHead = NULL;
	cout << "test" << endl;
}

songList::~songList()
{

}

void songList::addSong(char * songName)
{
	
	songListStr * tempHead = NULL;
	songListStr * preHead = NULL;
	songListStr * nextHead = NULL;

	if (songHead == NULL)
	{
		songHead = new songListStr;
		songHead->next = NULL;
		songHead->song = songName;
		songHead->review = NULL;
	}
	else
	{
		tempHead = songHead;
		if ( strcmp(songName,songHead->song) < 0 )
		{
			songHead = new songListStr;
			songHead->next = tempHead;
			songHead->song = songName;
			songHead->review = NULL;
			return;
		}

		if ( songHead->next == NULL)
		{
			songHead = new songListStr;
			songHead->next = NULL;
			songHead->song = songName;
			songHead->review = NULL;

			tempHead->next = songHead;
			songHead = tempHead;
			return;
		}

		while ( strcmp(songName,songHead->song) > 0 )
		{
			if ( songHead->next == NULL)
			{
				songHead = new songListStr;
				songHead->next = NULL;
				songHead->song = songName;
				songHead->review = NULL;

				nextHead->next = songHead;
				songHead = tempHead;
				return;
			}
			preHead = songHead;
			nextHead = songHead->next;
			songHead = songHead->next;
		}
		songHead = new songListStr;
		songHead->song = songName;
		songHead->next = nextHead;
		songHead->review = NULL;
		preHead->next = songHead;
		songHead = tempHead;
	}
}

void songList::addReview()
{
}

void songList::printSongList() const
{
	if (songHead == NULL)
	{
		cout << "The list is empty!" << endl;
	}
	else
	{
		songListStr * tempHead;
		tempHead = songHead;

		while (tempHead->next != NULL)
		{
			cout << tempHead->song << endl;
			tempHead = tempHead->next;
		}
		cout << tempHead->song << endl;
	}
}

void songList::printSongListReview() const
{
}
jsmith (5804)
Your addSong() function is wrong (the main else case). Also, are you trying to create a singly linked list or a doubly linked list? Your songListStr struct contains two pointers like you want it to be doubly linked, but the "prev" (review) pointer is always set to NULL.
satm2008 (148)
At a glance, I could tell you that your addSong() would need a simple loop to check where the new one needs to be inserted in the existing list.
First time, when it creates a new node it keeps the newone as head, but next time onwords, it is checking with only the songHead which would check only at second position and would not place the newly inserted at right place.
The while loops look errouneous though.

You are initializing tempHead with songHead but you are not using either.

Have a new loop to check with the existing nodes one after another starting from first and find right place for insertion. Within the loop you keep moving ahead until last but one but not so NULL.
The revised code would look like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
void songList::addSong(char * songName)
{
	songListStr * newSong = NULL;  // pointer to hold node		
	songListStr * tempHead = NULL;
	songListStr * preHead = NULL;
	songListStr * nextHead = NULL;

	//create new one hear
        newSong = new songListStr;
        newSong->song = songName;
        newSong->next = newSong->prev = NULL;

	if (songHead == NULL)
	{
		songHead = newSong;
		return;  // you are done here
	}
	else if (strcmp(songName,songHead->song) < 0) // needs to be inserted before head
	{
		newSong->next = songHead;
		songHead = newSong;	   // the newone is the head
	}
	else  //needs to find a right place for insertion
	{
		tempHead = songHead; // start from head (first)
		while (strcmp(songName,temHead->song) < 0 && tempHead->next) //check upto last node
		{
			tempHead = temp->next;
		}

		if ( strcmp(songName,temHead->song) < 0 )  // insert just before the current position
		{
			newSong->prev = tempHead->prev;
			tempHead->prev = newSong; 
			newSong->next = tempHead;
			return;
		}
		else // insert just after the current position
		{
			newSong->next = tempHead->next;
			tempHead->next = newSong;
			newSong->prev = tempHead;
			return;
		}

	}
}

Topic archived. No new replies allowed.