C++

Forum

 
How to find the longest increasing sublist?

dakman96 (10)
I need to find the longest increasing sublist of a set of mountain elevations. I do not see why the program isn't working, can someone help guide me in the right direction? Thanks in advance, here's the link to the assignment:

http://www.cs.ecu.edu/~karl/3300/fall15/Assignments/Assignment7/assn7.html

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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
 
#include <cstdio>
#include <iostream>
#include <string>
using namespace std;

const int ARRAYSIZE = 100;
const int TraceLevel = 1;

struct mountain
{
	string name;
	int elevation;

	mountain()
	{
		elevation = 0;
	}
};

struct List
{
	int mountIndex;
	List* next;

	List()
	{
		mountIndex = 0;
		next = NULL;
	}
};

//readGraph(A) takes the input of the names and heights of mountains, and stores them in A.  It also stores the number of elements.

void readMountains(mountain* mArray)
{
	int x = 0;
	while (true)
	{
		cin >> mArray[x].name;
		if (mArray[x].name == "end")
		{
			break;
		}
		else
		{
			cin >> mArray[x].elevation;
		}
		x++;
	}
}

//insert(BISlist, num, k) inserts index num into the BISlist.

void insert(List* BISlist, int num, int k)
{
	List* temp = BISlist;
	temp[num].mountIndex = k;
	temp[num].next = BISlist[num].next;
	BISlist[num] = temp[num];
}

//copyList(BISlist, num, k) copies a BIS list into the next index of the array.

void copyList(List* BISlist, int num)
{
	List* temp = BISlist;
	BISlist[num + 1] = temp[num];
}

//calcBIS(mArray, BISlist, num, k) finds the best increasing sublists of mountains, and stores the values into a list.  
//The last currently stored bis in the list is found that ends on a value that is less than the current moutain elevation.  If no 
//such elevation exists, the fist index of the array of lists is replaced with that elevation.

void calcBIS(mountain* mArray, List* BISlist, int num, int k)
{
		if (mArray[k].elevation > mArray[BISlist[num].mountIndex].elevation)
		{
			insert(BISlist, num, k);
			copyList(BISlist, num);
			k++;
			num++;
			calcBIS(mArray, BISlist, num, k);
		}
		else if (mArray[k].elevation < mArray[BISlist[num].mountIndex].elevation)
		{
			calcBIS(mArray, BISlist->next, num, k);
		}
		else
		{
			BISlist[0].mountIndex = k;
			copyList(BISlist, num);
			k++;
			calcBIS(mArray, BISlist, num, k);
		}
}

//reverseList(shortBIS) takes a BIS list and rearanges it into reverse order.

void reverseList()
{

}

//printList(A, shortBIS) prints the mountains in the array in BIS order.

void printList(mountain* mArray, List* BISlist, int num)
{
	if (BISlist!=NULL)
	{
		cout << BISlist[num].mountIndex << endl;
		printList(mArray, BISlist->next, num);
	}
}

int main(int argc, char** argv)
{
	int longestBIS, i;
	longestBIS = i = 0;
	mountain* mountArray = new mountain[ARRAYSIZE];
	List* BISList = new List[ARRAYSIZE];
	BISList[0].mountIndex = 0;
	readMountains(mountArray);
	calcBIS(mountArray, BISList, longestBIS, i);
	printList(mountArray, BISList, longestBIS);
	return 0;
}
Last edited on
dakman96 (10)
I also noticed that I believe one of my errors is in the insert function. Why can I not perform the command temp[num].next = BISlist[num]; instead of temp[num].next = BISlist[num].next;
Last edited on
dakman96 (10)
bump
cire (8284)
I do not see why the program isn't working, can someone help guide me in the right direction?


If I paste this in VC++ and peruse the warnings:
warning C4717: 'calcBIS': recursive on all control paths, function will cause runtime stack overflow


calcBIS is the recursive equivalent of an infinite loop.
Last edited on
dakman96 (10)
Sorry I didn't post an update but I actually fixed that part earlier but to no avail so far... Here's an update on what I have: thanks for the reply as well!

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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
 
#include <cstdio>
#include <iostream>
#include <string>
using namespace std;

const int ARRAYSIZE = 100;
const int TraceLevel = 1;

struct mountain
{
	string name;
	int elevation;

	mountain()
	{
		elevation = 0;
	}
};

struct List
{
	int mountIndex;
	List* next;

	List()
	{
		mountIndex = 0;
		next = NULL;
	}
};

//readGraph(A) takes the input of the names and heights of mountains, and stores them in A.  It also stores the number of elements.

void readMountains(mountain* mArray)
{
	int x = 0;
	while (true)
	{
		cin >> mArray[x].name;
		if (mArray[x].name == "end")
		{
			break;
		}
		else
		{
			cin >> mArray[x].elevation;
		}
		x++;
	}
}

//insert(BISlist, num, k) inserts index num into the BISlist.

void insert(List* BISlist, int num, int k)
{
	List* temp = BISlist;
	temp[num].mountIndex = k;
	temp[num].next = BISlist[num].next;
	BISlist[num] = temp[num];
}

//copyList(BISlist, num) copies a BIS list into the next index of the array.

void copyList(List* BISlist, int num)
{
	List* temp = BISlist;
	BISlist[num + 1] = temp[num];
}

//calcBIS(mArray, BISlist, num, k) finds the best increasing sublists of mountains, and stores the values into a list.  
//The last currently stored bis in the list is found that ends on a value that is less than the current moutain elevation.  If no 
//such elevation exists, the fist index of the array of lists is replaced with that elevation.

void calcBIS(mountain* mArray, List* BISlist, int num, int k)
{
	if (mArray[k].elevation != 0)
	{
		if (mArray[k].elevation > mArray[BISlist[num].mountIndex].elevation)
		{
			cout << "if 1";
			insert(BISlist, num, k);
			copyList(BISlist, num);
			k++;
			num++;
			calcBIS(mArray, BISlist, num, k);
		}
		else if (mArray[k].elevation < mArray[BISlist[num].mountIndex].elevation)
		{
			cout << "if 2";
			calcBIS(mArray, BISlist->next, num, k);
		}
		else
		{
			cout << "else";
			BISlist[0].mountIndex = k;
			copyList(BISlist, num);
			k++;
			calcBIS(mArray, BISlist, num, k);
		}
	}
}

//reverseList(shortBIS) takes a BIS list and rearanges it into reverse order.

void reverseList()
{

}

//printList(A, shortBIS) prints the mountains in the array in BIS order.

void printList(mountain* mArray, List* BISlist, int num)
{
	if (BISlist!=NULL)
	{
		cout << BISlist[num].mountIndex << endl;
		printList(mArray, BISlist->next, num);
	}
}

int main(int argc, char** argv)
{
	int longestBIS, i;
	longestBIS = i = 0;
	mountain* mountArray = new mountain[ARRAYSIZE];
	List* BISList = new List[ARRAYSIZE];
	BISList[0].mountIndex = 0;
	readMountains(mountArray);
	calcBIS(mountArray, BISList, longestBIS, i);
	//printList(mountArray, BISList, longestBIS);
	return 0;
}
cire (8284)
Perhaps you can explain what insert and copyList are supposed to be doing, because they are not doing what the names suggest they are.
Topic archived. No new replies allowed.