fork(4) download
copy 
  1. // CSCI 3300
  2. // Assignment: 7
  3. // Author:     Sam Twaiti
  4. // File:       lis.cpp
  5. // Tab stops:  8
  6.  
  7. // this program takes a list of mountains and value from the standard input
  8. // then prints out the longest increasing sublist from it. 
  9.  
  10.  
  11. #include <cstdio>
  12. using namespace std;
  13. #include <iostream>
  14. #include <string>
  15.  
  16. const int maxNumbers = 100;
  17. const int maxName = 100;
  18.  
  19. struct mountain
  20. {
  21. 	char* name;
  22. 	int elevation;
  23.  
  24. 	mountain()
  25. 	{
  26. 		elevation = 0;
  27. 	}
  28. };
  29.  
  30. struct List
  31. {
  32. 	int item;
  33. 	List* next;
  34.  
  35. 	List(List* nxt, int it)
  36. 	{
  37. 		next = nxt;
  38. 		item = it;
  39. 	}
  40. };
  41.  
  42. struct bookOfMt
  43. {
  44. 	int numOfMts;
  45. 	mountain* allMountains;
  46. 	List* bis[maxNumbers];
  47. 	bookOfMt(int nm, mountain* ma)
  48. 	{
  49. 		numOfMts = nm;
  50. 		allMountains = ma;
  51. 	}
  52. };
  53.  
  54. bookOfMt newMountain()
  55. {
  56. 	mountain* n = new mountain[maxNumbers];
  57. 	int count = 0;
  58. 	int k;
  59. 	for(k = 0; k < maxNumbers; k++)
  60. 	{
  61. 		n[k].name = new char[maxName];
  62. 		scanf("%s", n[k].name);
  63. 		scanf("%d", &n[k].elevation);
  64. 		if(feof(stdin))
  65. 		{
  66. 			break;
  67. 		}
  68. 		if (n[k].elevation != 0)
  69. 		{
  70. 			count++;
  71. 		}
  72. 	}
  73. 	bookOfMt z(count, n);
  74. 	return z;
  75. }
  76.  
  77.  
  78. int positionS(bookOfMt z, int k, int count)
  79. {
  80. 	int s = count;
  81. 	while(z.bis[s] != NULL && z.allMountains[z.bis[s]->item].elevation > z.allMountains[k].elevation)
  82. 	{
  83. 		s--;
  84. 	}
  85. 	return s+1;
  86. }
  87.  
  88.  
  89. int Counter(int s, int count)
  90. {
  91. 	return max(s, count);
  92. }
  93.  
  94.  
  95. List* reverseList(bookOfMt z, int count)
  96. {
  97. 	List* l = NULL;
  98. 	while(z.bis[count] != NULL)
  99. 	{
  100. 		l = new List(l, z.bis[count]->item);
  101. 		z.bis[count] = z.bis[count] -> next;
  102. 	}
  103. 	return l;
  104. }
  105.  
  106.  
  107. void resultPrinter(bookOfMt z, int count)
  108. {
  109. 	List* l = reverseList(z,count);
  110. 	for(List* ptr = l; ptr != NULL; ptr = ptr -> next)
  111. 	{
  112. 		printf("%-30s ",z.allMountains[ptr->item].name);
  113. 		printf("%10d\n",z.allMountains[ptr->item].elevation);
  114. 	}
  115. }
  116.  
  117.  
  118. void insertCell(bookOfMt z)
  119. {
  120. 	int count = 0;
  121. 	int k, s;
  122. 	for(k = 0; k < z.numOfMts; k++)	
  123. 	{
  124. 		s = positionS(z, k, count);
  125. 		z.bis[s] = new List(z.bis[s-1],k);
  126. 		count = Counter(s, count);
  127. 	}
  128. 	resultPrinter(z, count);
  129. }
  130.  
  131.  
  132. int main(int argc, char** argv)
  133. {
  134. 	bookOfMt z = newMountain();
  135. 	int k;
  136. 	for(k = 0; k < maxNumbers; k++)
  137. 	{
  138. 		z.bis[k] = NULL;
  139. 	}
  140. 	insertCell(z);
  141. 	return 0;
  142. }
  143.  
  144.  
Success #stdin #stdout 0s 3460KB
comments (?)
stdin
copy 
Eiger            3970
Everest          8848
Denali           5500
Fuji             3776
GangkharPuensum  7570
K2               8611
Kilamanjaro      5895
Matterhorn       4478
Olympus          2917
Tocopuri         5808
Tupungato        6570
Whitney          4421
stdout
copy 
Fuji                                 3776
Matterhorn                           4478
Tocopuri                             5808
Tupungato                            6570
https://ideone.com/yUPuAk
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!