Arrays and Pointers assistance, please?

[ThirdAge]

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):

        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.

[masterofpuppets690]

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

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?

[ThirdAge]

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?

[masterofpuppets690]

try this

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*?

[ThirdAge]

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"?

[masterofpuppets690]

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.

[ThirdAge]

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....

[masterofpuppets690]

Can you show me your main function too please?
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?

[masterofpuppets690]

Is there any chance you could show me the assignment itself?

[ThirdAge]

definately! sorry!

my main:

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 Suffixes
A suffix 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 suffixes of s are potato, otato, tato, ato, to, and o.
(Technically the empty string can be considered a suffix, but we'll ignore that case.) Observe that the
number of suffixes of s is exactly equal to the length of s. We can number the suffixes and say that
the ith sux of s is the one that begins with the ith letter of s. We can represent all of the suffixes
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 suffix
array pointing to the appropriate character in the string, sorts the suffixes, 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 suffixes. The suffix
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 sux 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.

[masterofpuppets690]

Ok thanks for that, just give me a few minutes to try something

[ThirdAge]

Thank you so much for your help I really really do appreciate it!!

[masterofpuppets690]

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

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

[ThirdAge]

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?

[masterofpuppets690]

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.

[ThirdAge]

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

[masterofpuppets690]

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?

[ThirdAge]

yeah it's up there too! xD

[masterofpuppets690]

What I meant was did you write that function or did your lecturer give you that function as part of the assignment?

[ThirdAge]

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