### Arrays and Pointers assistance, please?

Pages: 12
So...In my current assignment, the user enters a word/string that is to be "suffixed" then to sort the suffixes....
I've written my sorting algorithms but they need to be modified to handle pointers.

If anyone could lend me a hand, how do I write code for an array to store a string that would be really appreciated! I understand that each letter becomes an element, but I'm not sure how to do it, I've tried several ways to write this but it doesn't work.

example of assignment run:
 ```String to be sorted: potato Sorted suffixes of "potato" 1. ato 2. o 3. otato 4. potato 5. tato 6. to```

What I have (incorrect way to store string into array, but my attempt idea):
 ``12345678910`` `````` string wordToSort; char* suffix[SIZE]; cout << "String to be sorted: "; cin >> wordToSort; for (int i; i < wordToSort.length(); i++) { wordToSort = suffix[i]; //wordToSort also needs to be the suffixes... }``````

the sorting algorithms are long and I still have to attempt to modify them so they can work with pointers so I just put this up as it's the start of everything.

Edit: I've spent quite abit of time looking up "how to store a string into an array" but I was unable to find anything useful on the search.

Edit2: I also need abit of help getting the suffixes. So, I noticed that the suffixes the array needs to store is the word - 1 letter every iteration. So, like the first element would be the whole word. the second element be the word - first letter, etc. I don't know how to do this either, it would be really nice if someone could teach me how.
Last edited on
When you include the string class you can do this

 `` `` ``string arr[SIZE];``

This will give you a string array so you can store a string as opposed to a character array. So if you do a for loop like this storing the strings into the array like this
 ``1234`` ``````for(int index = 0; index < SIZE; index++) { arr[index] = "Some string blah blah"; }``````

So when you you want to get the string at index 1 you don't get the first character like you would with a character array but the actual whole string.

My understanding of your problem is that when someone enters potato, you want the program to run like this.
Potato
otato
tato
ato
to
o
is that correct?
Thank you for responding! Yes that is correct!

edit2; I have all the sorting algorithms written if you need them aswell, they just arnt modified yet to work with pointers because I wanted this down first

edit3: can this string array be the same as my char array? Sorry, abit new to pointers. I kind learned that the * means that it points to the value of the address of that element.

so would this mean that

`char* suffix[SIZE]`
would point to the elements within the array suffix? ie: char* suffix[0] would return potato if potato was the first (0-th) element?
Last edited on
try this

 ``12345678910`` ``````int SIZE; string wordToSort; cin >> wordToSort; SIZE = wordToSort.length(); string suffixes[SIZE]; for(int index = 0; index < SIZE; index++) { suffixes[index] = wordToSort.substr(index, wordToSort.length()); }``````

basically what I'm doing here is creating a string array thats the same size as the inputted string to handle all possible suffixes and iterating through the array putting in a substring of the wordToSort
starting from the first full word and then when index = 1 I get the substring otato then when it equals 2 I get tato etc... then you have an array of strings that can hold all the possible suffixes, put the code for sorting the array up and I'll have a look at that as well.

In response to your edit, not it can't be a char array because a char array holds a list of characters and if suffix were a char array

`suffix[0]`

would only give you back P from the string potato, show me your sorting algorithm and we'll modify it to use string arrays.

I think a misread your last edit, did you want a pointer to a string array because if so then yes that is possible of course. Let me know if thats what you want and I'll show you how, or are you told to explicitly use char*?
Last edited on
oh my bad, i didnt say that SIZE in my code was
`const int 100000`

but the way you did it, that changes the size as the program runs? so would that be the same thing called "dynamic allocation"?
It isn't as such dynamic allocation because this array is still being created on the stack.
This is an example of an example of dynamically allocating a string array

 `` `` ``string *array = new string[size];``

The first way I showed you works exactly the same way except that it gets created on the stack whereas this example gets created on the heap. But for now thats unimportant, both ways are perfectly fine solutions. Will you post your sorting algorithm up so I can have a look at it.
 ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455`` ``````void display(string* A, int size){ for (int i = 0; i < size; i++) cout << setw(3) << *(A+i); cout << endl; } void swap(int A[], int i, int j){ int tmp = A[i]; A[i] = A[j]; A[j] = tmp; } int partition(int A[], int low, int high){ int i = low; int j = high; int mid = (low + high) / 2; int pivot = A[mid]; swap(A, low, mid); //swaps the pivot into A[low] while(i <= j) { //skip over elements <= the pivot while (i <= high && A[i] <= pivot) { i++; } //skip over elements > the pivot while(low <= j && pivot < A[j]) { j--; } //swap values at i & j if (i < j) swap(A, i, j); } swap(A, low, j); return j; } void QuickSort(int A[], int low, int high){ if(low < high) // recursive case { int mid = partition(A, low, high); QuickSort(A, low, mid-1); QuickSort(A, mid+1, high); } }``````

here it is! took me a while to create them :/ only to find out i have to fix them so they work with pointers.
----on a side note, when i run Visual Studio to execute the program, .exe crashes stops responding, i close that window, then the cmd window comes up with the "press any key to continue" anyway to fix this? Do you also need to see what's in main?

edit: all i probably need to do is just change `int A[]` to
`string* A`

but also, my assignment requires me to have
`char* suffix[SIZE]` as my suffix array, but i guess if this runs i wont have to? when i commented out the string version of the array to have the car instead, it underlines stuff in red suggesting an error....
Last edited on
Sorry can't help you with Visual Studio as I neither use Visual Studio or Windows. But I may be able to find out what the problem is by seeing the main being used.

I assume this is an assignment, all those methods you use like partition and swap are they required as per the assignment spec or can I change the function parameters to work differently?
Last edited on
Is there any chance you could show me the assignment itself?
definately! sorry!

my main:

 ``1234567891011121314151617181920`` ``````int main(){ string wordToSort; string suffix[SIZE]; //char* suffix[SIZE]; cout << "String to be sorted: "; cin >> wordToSort; cout << "Sorted suffixes of " << wordToSort << endl; for(int index = 0; index < SIZE; index++) { suffix[index] = wordToSort.substr(index, SIZE); } display(suffix, wordToSort.length()); return 0; }``````

String Suffixes
A suffix of a string s is a substring of s that ends with the last character of s.
For example, if s is the string potato, then the suffixes of s are potato, otato, tato, ato, to, and o.
(Technically the empty string can be considered a suffix, but we'll ignore that case.) Observe that the
number of suffixes of s is exactly equal to the length of s. We can number the suffixes and say that
the ith sux of s is the one that begins with the ith letter of s. We can represent all of the suffixes
of a string s by storing the string in a character array and then constructing an array of pointers that
point to the appropriate character in the string. For example, if suffix is our array of pointers then
suffix[1] will point to the rest o in the character array containing potato.
Program
Write a program that reads in a string (of maximum length 100000), constructs the suffix
array pointing to the appropriate character in the string, sorts the suffixes, and then displays them in
their sorted order. You must use the QuickSort algorithm, which you will need to modify to handle your
array of pointers. You may not make copies of the string or parts of the string in your code. You should
only need two 1D arrays: one for the string you read in and one to represent the suffixes. The suffix
array should be declared as an array of char pointers: `char* suffix[SIZE];`

This assignment requires very little new code to be written. You will have to modify QuickSort so that
it sorts an array of character pointers. Constructing the sux array takes only a few lines of code, as
does displaying it. But you do need a good understanding of pointers and how they work.
Last edited on
Ok thanks for that, just give me a few minutes to try something
Thank you so much for your help I really really do appreciate it!!
No worries man, I'm just so confused as to why anyone in their right mind would use
`char**` instead of the string object when you're learning C++, makes no sense to me anyway.

Heres the main I have so far
 ``12345678910111213141516`` ``````int main() { int SIZE; string wordToSort; cin >> wordToSort; SIZE = wordToSort.length(); char *suffixes[SIZE]; for(int index = 0; index < SIZE; index++) { suffixes[index] = &wordToSort[index]; } //The display function takes a pointer to a string as its argument so what the & means is //Give the pointer the address of the first string in the array suffixes display(suffixes, SIZE); }``````

basically does the same as the first piece of code I sent you but replaced the string with a char* array and I modified the display method slightly also. Let me work on it a bit more and I'll get back to
well i made the display function able to handle the pointer *grinz* *feels proud*

edit: when i use your `display(suffix, SIZE);` (ive changed suffixes to suffix for my sake) it underlines suffix in red telling me that char** is not compatible with char*/string* depending on what display had in it's first parameter. is there a way to fix that?
Last edited on
Did you modify QuickSort at all?

In response to your edit, I changed display slightly and I'll post up my change in a bit for you. It won't work with your display function.
Last edited on
not yet, id imagine the only thing i needed to do was change `int A[]` in the parameter to also be `string* A` or
`char* A` i just havent figured out which it should be, i was leaning towards char because it would eventually be a single letter

edit2: Just changed everything to `char* A` in the parameter for now, need to run it eventually to see if that's correct and if it would run. right now trying to find out a way to get it to run in the first place ahahhaha
Last edited on
I have changed it to `char * A[]` so I'll post my changes once I'm satisfied I'm after solving the problem.

Did you come up with the partition function?
Last edited on
yeah it's up there too! xD
Last edited on
What I meant was did you write that function or did your lecturer give you that function as part of the assignment?
the partition was given, i just needed to come up with the QuickSort which i had a friend check and he said it was A-OK hahaha
Pages: 12