C++

Forum

 
C++ Word search in randomly created list

F95 (64)
Need to create a program that creates a Library that is 1024 lines deep and a Recent_List that is 128 lines deep. The contents of each line for both lists will be chars between 2MB to 3MB in length (randomly assigned by program). The user will be prompted to type in a random word and the program will search for it in all lines of the Recent_List. The line(s) that contain the word will remain, those that do not contain the word will be ejected from the recent_list and be reinitialized at the bottom of the Library. Simultaneously, the recent_list will be truncated and the upper-most lines of the Library will be added to the empty lines of the recent_list. I am unsure how to do the search and truncation aspects of this program.

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
 
  #include <iostream> 
using namespace std;

char letters[26] = { 'A','B','C','D','E','F','G','H','I','J','K','L','M',
					'N','O','P','Q','R','S','T','U','V','W','X','Y','Z' };

long int count(int a)
{
	if (a == 0)
		return 2700;
	else
		return (2 * count(a - 1));
}

// Generate random words
char random()
{
	int  randomList = rand() % 26;         //Generate random number to be used to index array
	char randomPick = letters[randomList]; //Pick a letter from the array at random
	return randomPick;
}

struct Arrays
{
	long int sizeList[128];
	long int sizeLib[1024];
	char* ptrList[128];
	char* ptrLib[1024];
};

void initArrays(struct Arrays &o)
{
	// random_list
	for (int i = 0; i < 128; i++)
	{
		o.sizeList[i] = count(i);
	}
	// Dynamically allocate memory for recent_list
	for (int i = 0; i < 128; i++)
	{
		o.ptrList[i] = new char[o.sizeList[i]];

		// Insert letters into the arrays INSIDE the 'pointers' array
		for (long int j = 0; j < o.sizeList[i]; j++)
		{
			o.ptrList[i][j] = random();
		}
	}

	// Library
	for (int i = 0; i < 1024; i++)
	{
		o.sizeLib[i] = count(i);
	}
	// Dynamically allocate memory for recent_list
	for (int i = 0; i < 1024; i++)
	{
		o.ptrLib[i] = new char[o.sizeLib[i]];

		// Insert letters into the arrays INSIDE the 'pointers' array
		for (long int j = 0; j < o.sizeLib[i]; j++)
		{
			o.ptrLib[i][j] = random();
		}
	}
}

int main()
{
	Arrays a1;
	initArrays(a1);
	
	int input = 0;
	char str[100];

	// Prompt for user
	cout << "---------------------------------------------" << endl;
	cout << " Press 1 to search the Recent List for a word" << endl;
	cout << " Press 2 to exit the program" << endl;
	cout << "---------------------------------------------" << endl;
	cin >> input;

	while (input != 1 && input != 2)
	{
		cout << "-----------Please press only 1 or 2-----------" << endl;
		cout << " Press 1 to search the Recent List for a word" << endl;
		cout << " Press 2 to exit the program" << endl;
		cout << "---------------------------------------------" << endl;
		cin >> input;
	}

	while (input != 2)
	{
		cout << "Enter a word: ";
		cin >> str; 

	}
	return 0;
}
dutch (2548)
Regarding your count() function, the maximum unsigned long (assuming 64 bits) is 18446744073709551615.
Doubling 2700 127 times yields 459381195343266925675555720032887085465600.
Doubling it 1023 times is, well, even bigger.
dutch (2548)
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
 
#include <iostream> 
#include <cstdlib>
#include <ctime>
using namespace std;

// small numbers for initial testing
const int RecentSize = 10, LibrarySize = 20;
const int Low = 20, High = 30;

struct Arrays {
    char* recent[RecentSize];
    char* library[LibrarySize];
};

inline char rndchar() { return char('A' + rand() % 26); }

void initArrays(Arrays &o) {
    for (int i = 0; i < RecentSize; i++) {
        int sz = rand() % (High - Low) + Low;
        o.recent[i] = new char[sz + 1];
        for (int j = 0; j < sz; j++) o.recent[i][j] = rndchar();
        o.recent[i][sz] = '\0';
    }
    for (int i = 0; i < LibrarySize; i++) {
        int sz = rand() % (High - Low) + Low;
        o.library[i] = new char[sz + 1];
        for (int j = 0; j < sz; j++) o.library[i][j] = rndchar();
        o.library[i][sz] = '\0';
    }
}

int main() {
    srand(time(0)); // seed rng
    Arrays a;
    initArrays(a);
    cout << "Recent:\n";
    for (int i = 0; i < RecentSize; ++i)
        cout << '\t' << a.recent[i] << '\n';
    cout << "Library:\n";
    for (int i = 0; i < LibrarySize; ++i)
        cout << '\t' << a.library[i] << '\n';
}

dhayden (5795)
struct Arrays ...
There's your problem right there :).

You're using the wrong data structure. Use an std::list of the strings. I'd use std::string to represent the contents of each list rather than a char array.

Store 1024 items in the list. The first 128 items are the "recent" items.

When you search, look at the first 128 items. If you don't find the string, unlink the item from the list and relink it at the end.

Be careful to not copy the strings since they are so large.
F95 (64)
@dutch I used your code as a guideline and I get it to compile and run but I get some errors/bugs. The 'errors' I'm getting is an exception thrown in the print_list() function: 0xC0000005: Access violation reading location 0xFDFDFDFD.

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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
 
#include <iostream> 
#include <cstdlib>
#include <ctime>
#include <cstring>
using namespace std;

// Constants used to create depth and width of recent_list and Library
const int recentList_Size = 10, library_Size = 15; // eventually will use 128 and 1024
const int Low = 20, High = 30; // eventually will be 2MB and 3MB

// Create pointers for recent_list and Library
struct Arrays {
	char* recent[recentList_Size];
	char* library[library_Size];
};

// Method to generate 26 CAPITAL letters using ascii value
inline char r_Letters() {
	return char('A' + rand() % 26);
}

// Build the array
void initArrays(Arrays& o) {
	for (int i = 0; i < recentList_Size; i++)  // Build recent_list vertically
	{
		int sz = rand() % (High - Low) + Low;  // Used to randomly generate array sized between 2MB and 3MB
		o.recent[i] = new char[sz + 1];        // Dynamically allocate memory to a pointer based on list size
		for (int j = 0; j < sz; j++)
			o.recent[i][j] = r_Letters();      // Fill horizontal array with randomly generated alphabet characters 
		o.recent[i][sz] = '\0';
	}
	for (int i = 0; i < library_Size; i++)     // Build Library (simialr method as the above)
	{
		int sz = rand() % (High - Low) + Low;
		o.library[i] = new char[sz + 1];
		for (int j = 0; j < sz; j++)
			o.library[i][j] = r_Letters();
		o.library[i][sz] = '\0';
	}
}

// Function used to print recent_list and Library
void print_list(Arrays* a) {
	cout << "Printing Lists..." << endl;

	cout << "Recent List: " << endl;
	for (int i = 0; i < recentList_Size; ++i)
		cout << '\t' << a->recent[i] << '\n';

	cout << "Library: " << endl;
	for (int i = 0; i < library_Size; ++i)
		cout << '\t' << a->library[i] << '\n';
}

int main() {
	srand(time(0)); // seed rng
	Arrays a;
	initArrays(a);
	int input;

	// Prompt for user
	cout << "----------------------------------------------" << endl;
	cout << " Press 1 to search the Recent List for a word " << endl;
	cout << " Press 2 to display Recent List and Library " << endl;
	cout << " Press 3 to exit the program" << endl;
	cout << "----------------------------------------------" << endl;
	cin >> input;

	// catch if input not within bounds
	while (input != 1 && input != 2 && input != 3)
	{
		cout << "-------- Please ONLY press 1, 2 or 3 ---------" << endl;
		cout << " Press 1 to search the Recent List for a word " << endl;
		cout << " Press 2 to display Recent List and Library " << endl;
		cout << " Press 3 to exit the program" << endl;
		cout << "---------------------------------------------" << endl;
		cin >> input;
	}

	while (input != 3)
	{
		if (input == 1) {
			// print_list(&a); // used for testing purposes | displays both lists of characters
			cout << "Enter a word to search for in the recent_list: ";

			char* search_word = new(char[11]); // 10 letter word, 11 character of \0 to mark the end of the string
												   // Dynamic memory used for comparison
			cin >> search_word;

			while (cin.get() != '\n') continue; // FLush buffer 

			cout << "Searching for: \"" << search_word << "\"\n"; // used for testing purposes

			// Array of booleans that will match the recentList length, where we are going
			// to mark if the array has word we are looking for
			bool words_found_at[recentList_Size] = { false };

			// Go through each array of letters and find the matching word
			int words_found = 0; // Keep count of instances word is found in each array of letters
			for (int i = 0; i < recentList_Size; i++) {
				// C++ function strstr used to compare chars of array to char inputted 
				if (strstr(a.recent[i], search_word) != NULL) {
					words_found++;            // increment counter
					words_found_at[i] = true; // Tab when word is found
				}
			}

			cout << search_word << " found in " << words_found << " arrays " << endl;

			// "Move" the arrays where the word was not found to a temp one
			char** recent_list_move = new (char* [words_found]);
			for (int i = 0, j = 0; i < recentList_Size; i++) {
				// instances in char array where word was not found
				if (words_found_at[i] == false) {
					recent_list_move[j] = a.recent[i]; // create temporary array of chars w/o word based on array position
					j++;
				}
			}

			// "Move" the arrays from the second queue which has the size of the words found
			char** library_list_move = new(char* [words_found]);
			for (int i = 0; i < words_found; i++) {
				library_list_move[i] = a.library[i];
			}

			// Shift Library up to maintain the FIFO order
			// j is used for the position of array after the top n arrays have been swapped to the recent_list
			for (int i = 0, j = words_found; i < library_Size; i++, j++) {
				a.library[i] = a.library[j];
			}

			// "Move" arrays of words not found from temp to the Library
			// Library_size - words_found gives the number of spaces needed to be filled
			for (int i = library_Size - words_found, j = 0; i < library_Size; i++, j++) {
				a.library[i] = recent_list_move[j];
			}

			// Find first index where word(s) have not been found, since that is the index
			// Keeps count of how many spaces need to be filled
			int shift_starts_at = 0;
			for (int i = 0; i < recentList_Size; ++i) {
				if (words_found_at[i] == false) {
					shift_starts_at = i;
					break;
				}
			}

			// Truncate recent_list up 
			for (int i = shift_starts_at, j = shift_starts_at; i < recentList_Size; i++) {
				if (words_found_at[i] == true) {
					a.recent[j] = a.recent[i];
					j++;
				}
			}

			// Fill in the recent_list with contents from library based on count
			// i will be the starting position after truncation | j will be used for the upper contents of the Library
			for (int i = recentList_Size - words_found, j = 0; i < recentList_Size; i++, j++) {
				a.recent[i] = library_list_move[j];
			}

			print_list(&a);
		}

		else // If user enters 2, display up-to-date recent_list
		{
			print_list(&a);
		}

		cout << "----------------------------------------------" << endl;
		cout << " Press 1 to search the Recent List for a word " << endl;
		cout << " Press 2 to display Recent List and Library " << endl;
		cout << " Press 3 to exit the program" << endl;
		cout << "----------------------------------------------" << endl;
		cin >> input;

		while (input != 1 && input != 2 && input != 3)
		{
			cout << "-------- Please ONLY press 1, 2 or 3 ---------" << endl;
			cout << " Press 1 to search the Recent List for a word " << endl;
			cout << " Press 2 to display Recent List and Library " << endl;
			cout << " Press 3 to exit the program" << endl;
			cout << "---------------------------------------------" << endl;
			cin >> input;
		}

	}
	return 0;
}
Last edited on
dhayden (5795)
Lines 128-130. Since j goes from words_found to words_found+library_Size-1, you access a.library out of bounds.

Also, you search through the recent list, but not the rest of the library. Is that your intention? Usually a "recent list" just indicates which items in the collection (the library) were used recently.
F95 (64)
I got it to work but I added comments where I need the code to be improved. Any help would be welcomed
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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
 
#include <iostream> 
    #include <cstdlib>
    #include <ctime>
    #include <cstring>
    using namespace std;

    // Constants used to create depth and width of recent_list and Library
    const int recentList_Size = 128, library_Size = 1024; // Number of 'lines' in the 
    // recent_list and Library
    // Used to create variable sizes of chars
    const int btm = 2000000, top = 3000000; 
    // Was told to use power of 2s, but a quick cout of 2^21 gives 23 not 2M

    // Create pointers for recent_list and Library
    struct Arrays {
	    char* recent[recentList_Size];
	    char* library[library_Size];
    };

    // Method to generate 26 CAPITAL letters using ascii value
    inline char random_letter() {
	    return char('A' + rand() % 26);
    }

    // Build the array
    // Was told to check memory?
    void initArrays(Arrays& o) {
	    for (int i = 0; i < recentList_Size; i++) // Build recent_list vertically
	    {
		    int sz = rand() % (top - btm + 1) + btm;  // Used to randomly generate array sized between 2MB and 3MB
		    o.recent[i] = new char[sz + 1];       // Dynamically allocate memory to a pointer based on list size
		    for (int j = 0; j < sz; j++)
			    o.recent[i][j] = random_letter(); // Fill horizontal array with randomly generated alphabet characters 
		    o.recent[i][sz] = '\0';
	    }
	    for (int i = 0; i < library_Size; i++)    // Build Library (simialr method as the above)
	    {
		    int sz = rand() % (top - btm + 1) + btm;
		    o.library[i] = new char[sz + 1];
		    for (int j = 0; j < sz; j++)
			    o.library[i][j] = random_letter();
		    o.library[i][sz] = '\0';
	    }
    }

    int main() {
	    srand(time(0));
	    Arrays a;
	    initArrays(a);
	    int input;

	    // Prompt for user
	    cout << "----------------------------------------------" << endl;
	    cout << " Press 1 to search the Recent List for a word " << endl;
	    cout << " Press 2 to exit the program" << endl;
	    cout << "----------------------------------------------" << endl;
	    cin >> input;

	    // catch if input not within bounds
	    while (input != 1 && input != 2)
	    {
		    cout << "-------- Please ONLY press 1 or 2 ---------" << endl;
		    cout << " Press 1 to search the Recent List for a word " << endl;
		    cout << " Press 2 to exit the program" << endl;
		    cout << "---------------------------------------------" << endl;
		    cin >> input;
	    }

	    while (input != 2)
	    {
			    cout << "Enter a word to search for in the recent_list: ";

			    char* search_word = new(char[16]); // 15 letter word, 16 character of \0 to mark the end of the string
									               // Dynamic memory needed for comparison
			    cin >> search_word;
			    while (cin.get() != '\n') continue; // FLush buffer

			    // Array of booleans that will match the recent_List length, where we are going to mark if the array has 
			    // the word we are looking for.
			    bool words_found_at[recentList_Size] = { false };

			    // Go through each array of letters and find the matching word
			    // Keep count of instances where word is and is not found in each array of letters
			    int words_found = 0;
			    int words_not_found = 0;
			    for (int i = 0; i < recentList_Size; i++) {
				    // C++ function strstr used to compare chars of array to char inputted 
				    if (strstr(a.recent[i], search_word) != NULL) {
					    words_found++;            // Increment counter
					    words_found_at[i] = true; // Tab when word is found (original code)
				    }
			    }
			    words_not_found = recentList_Size - words_found;

			    cout << search_word << " found in " << words_found << " arrays " << endl;
			    cout << words_not_found << " arrays were ejected " << endl;

			    if (words_found != 0) {
				    // "Move" the arrays where the word was not found to a recent_list temp
				    char** recent_list_move = new char* [words_not_found];
				    for (int i = 0, j = 0; i < recentList_Size; i++) {
					    // instances in char array where word was not found
					    if (words_found_at[i] == false) {
						    recent_list_move[j] = a.recent[i]; // create temp array of chars w/o word(s) based on position
						    j++;
					    }
				    }

				    // Based on the num of words not found, "move" the arrays from the contents from the Library
				    // to another temp array in FIFO order
				    char** library_list_move = new char* [words_not_found];
				    for (int i = 0; i < words_not_found; i++) {
					    library_list_move[i] = a.library[i];
				    }

				    // Shift Library up to maintain the FIFO order
				    // j is used for the position of array after the top 'n' array(s) have been moved to the recent_list
				    for (int i = 0, j = words_not_found; i < library_Size; i++, j++) {
					    if (j < 15)
					    {
						    a.library[i] = a.library[j];
					    }
					    else
					    {
						    a.library[i] = NULL; // j goes out of bounds of array when i = 12
					    }
				    }

				    // "Move" arrays of words from recent_list temp to the Library
				    // (library_Size - words_not_found) used to place recent_list temp contents at the bottom of Library
				    for (int i = library_Size - words_not_found, j = 0; i < library_Size; i++, j++) {
					    a.library[i] = recent_list_move[j];
				    }

				    // Find first index where word(s) have not been found, since that is the index
				    // Keeps count of how many spaces need to be filled
				    int shift_starts_at = 0;
				    for (int i = 0; i < recentList_Size; i++) {
					    if (words_found_at[i] == false) {
						    shift_starts_at = i;
						    break;
					    }
				    }
				    // Truncate recent_list up 
				    for (int i = shift_starts_at, j = shift_starts_at; i < recentList_Size; i++) {
					    if (words_found_at[i] == true) {
					    	a.recent[j] = a.recent[i];
					    	j++;
					    }
				    }

				    // Fill in the recent_list with contents from library based on count
				    // 'i' will be the starting position of the recent_list after truncation
				    for (int i = recentList_Size - words_not_found, j = 0; i < recentList_Size; i++, j++) {
					    a.recent[i] = library_list_move[j];
				    }
			    }

		    // Prompt for user
		    cout << "---------------------------------------------" << endl;
		    cout << " Press 1 to search the Recent List for a word " << endl;
		    cout << " Press 2 to exit the program" << endl;
		    cout << "---------------------------------------------" << endl;
		    cin >> input;

		    while (input != 1 && input != 2 && input != 3)
		    {
			    cout << "---------Please press only 1, 2 or 3---------" << endl;
			    cout << " Press 1 to search the Recent List for a word" << endl;
			    cout << " Press 2 to exit the program" << endl;
			    cout << "---------------------------------------------" << endl;
			    cin >> input;
		    }

	    }
    // Recommended to de-allocate memory before exiting but unsure how to do so
	    return 0;
    }
dhayden (5795)
It looks correct, but I still have to ask if you're doing the right thing. Usually a "recent list" in a "library" means that the recent list is just the most recently found items in the library. And when you search, why don't you search the entire library instead of just the recent list?

If this is a homework problem, could you post the actual assignment? I worry that you're misinterpreting it. It would be a shame to hand in code that correctly does what you think it should do, only to find out that what you think it should do is wrong. By the way, this happens frequently in the real world.
https://www.businessballs.com/local/pix/businessballs/treeswing/tree-swing-s-hogh.jpg
Topic archived. No new replies allowed.