Hello,
I need to wwrite a function that will go through a dynamic character array that the user inputs then take it and delete the repeated characters. My program partially works but it seems as though whenever it deletes a set of repeated characters then it just stops rather than go through the whole char array. Here is my code:

#include<iostream>
#include<cstdlib>

using namespace std;

typedef char* CharArrayPtr;

void input(char sentence[], int& size);
void delete_repeats(char sentence[], int& size);

int main()
{
    int size;

    CharArrayPtr array;
    array = new char[81];

    input(array,size);
    delete_repeats(array,size);

    cout << "Resulting Array: ";
    for(int i = 0; i < size; i++ ) 
    {
        cout << array[i] << " ";
    }
    cout << endl << endl;

    delete [] array;

    system("pause");
    return 0;
}
void input(char sentence[], int& size)
{
    int walker = 0;

    cout << "Please enter a string of characters: ";
    do
    {
        cin.get(sentence[walker]); 
        walker++; 
    }while (sentence[walker - 1] != '\n'); 
    size = walker - 1;
}
void delete_repeats(char sentence[], int& size)
{
    for (int i = 0; i < size; i++)
    {   
        for (int j = i + 1; j < size; j++)  
        {
            if (sentence[i] == sentence[j])
            {   
                char *sentence = new char[size]; //allocate a new array of 'size' chars
                delete [] sentence;              // deallocate that array
                sentence = new char[size - 1];   // allocate new array with 'size - 1' chars
                j--;
                size--;
                for(int k = 0; k < size; k++)
                cout << sentence[k];
                cout << endl; 
            } 
        }
    }
}

Recommended Answers

All 27 Replies

I do not understand why you need to reallocate, when you are only removing letters and the size just shrinks if you do the deletions. And if you need to keep the original string, why not only keep letters which are not same as previous letter was in simple copy loop? Here version from your code, which also null terminates the string and does not store repeated characters. Naturally it crashes if user enters more than 80 letters, which is probably what you are supposed to fix.

#include <iostream>
#include <cstdlib>

using namespace std;

typedef char* CharArrayPtr;

void input(char sentence[], int& size);

int main()
{
    int size;

    CharArrayPtr array;
    array = new char[81];

    input(array,size);

    cout << "Resulting Array: ";
    for(int i = 0; i < size; i++ )
    {
        cout << array[i] << " ";
    }
    cout << endl << endl;
    return 0;
}
void input(char sentence[], int& size)
{
    int walker = 0;

    char prev = '\0', ch='\0';

    cout << "Please enter a string of characters: ";
    do
    {
        cin.get(ch);
        if(prev != ch) {
            sentence[walker++] = ch;
            prev = ch;
        }
    }while (prev != '\n');

    sentence[walker] = '\0';
    size = walker;
}

When you get duplicate, shift the array by 1 bit. You don't need to reallocate array I suppose.

Edit : When you get duplicate, shift the array by 1 char. You don't need to reallocate array I suppose.

@np complete

bit

char

I'm sorry I forgot to mention that I need to return a new dynamic array where all repeated letters are deleted instead of modifying the partially filled array.

Here is some pseduo code that might help

int counter = 0
original[] // array you get from user
nodup[] // array without duplicates.
char ch
nodup[0] = original[0]
loop i = 0 until size of original - 1
{
    ch = original[i]
    loop j = i + 1 until size of original - 1
    {
        if ch != original[j]
            nodup[++counter] = original[j]
    }
}

I changed up my program a little bit, but now the problem I am having that it only deletes repeated pairs not all repeats. How can I make it so that it deletes all the repeats in the word?

Code:

#include<iostream>
#include<cstdlib>
#include <cstring>

using namespace std;

void DeleteRepeats(char array[], int& size);
void Output(char array[], int size);

int main()
{
    int size, A;
    char Duplicates[100];

    int Walker = 0;
    cout << "Please enter an array of characters: ";
    do
    {
        cin.get(Duplicates[Walker]); 
        Walker++; 

    }while (Duplicates[Walker - 1] != '\n'); 
    size = Walker - 1;


    DeleteRepeats(Duplicates, size);

    system("pause");    
    return 0;
}

void DeleteRepeats(char array[], int& size)
{
    int usize = 0;
    char* noDupp;
    noDupp = new char[size];

    char* Walker = noDupp;


    for (int i = 0; i < size; i++)
    {
        for (int j = i + 1; j < size; j++)
        {
            if (array[i] != array[j])
            {
                *Walker = array [i];
                Walker++;
                usize++;
            }
            i++;
            j--;
        }
    }
    Output(noDupp, usize);
    delete [] noDupp;
}

void Output(char array[], int size)
{
    cout << "Resulting Array: ";
    char *Walker = 0;
    Walker = array;

    for(int i = 0; i < size; i++ ) 
    {
        cout << *Walker++ << " ";
    }
    cout << endl << endl;
}

Please explain this loop. It doesn't make any sense to me.

for (int i = 0; i < size; i++)
{
    for (int j = i + 1; j < size; j++)
    {
        if (array[i] != array[j])
        {
            *Walker = array [i];
            Walker++;
            usize++;
        }
        i++;
        j--;
    }
}

And please explain IN DETAIL. Don just say it does 'this'

Hello Walt,
Sure, so that function "DeleteRepeats" takes in a array that has duplicate characters and these for loops are to address the first(i) and second(j) elements of that array. I did this so that I can compare the two later on and if they are not equal then it copies that character into another dynamic array called noDupp through the means of another pointer called "Walker." Then regardless of whether or not the forst and second elements of the array are equal the i and j gets plus plused. I hope it makes sense.

but now the problem I am having that it only deletes repeated pairs not all repeats. How can I make it so that it deletes all the repeats in the word?

If you are allowed to have a different order of chars in the result, just sort the original array first and it will remove all the duplicates.

If not, you need a to lookup the duplicated values (perhaps using a set). Something like:

char* remove_duplicates_preserve_order( const char* cstr )
{
    bool already_seen[ std::numeric_limits<unsigned char>::max() + 1 ] = { false } ;
    int cnt_unique = 0 ;
    for( const char* p = cstr ; *p ; ++p )
    {
        const unsigned char u = *p ;
        if( !already_seen[u] ) { already_seen[u] = true ; ++cnt_unique ; }
    }
    char* result = new char[ cnt_unique + 1 ] ;
    result[cnt_unique] = 0 ; // null-terminate

    bool already_copied[ std::numeric_limits<unsigned char>::max() + 1 ] = { false } ;
    for( char* p = result ; *cstr ; ++cstr )
    {
        const unsigned char u = *cstr ;
        if( !already_copied[u] ) { already_copied[u] = true ; *p = *cstr ; ++p ; }
    }

    return result ;
}

If you are allowed to use C++, std::string in conjuction with std::set<> would make the code a lot shorter, and a lot cleaner.

Hello vijayan, Unforetuneately I am not too familiar with vectors. Do you can show me a non-vector solution.

Member Avatar for iamthwee

Seriously, apart from the time complexity issue use a recursive function to delete is much much easier?

Then regardless of whether or not the forst and second elements of the array are equal the i and j gets plus plused. I hope it makes sense.

No. All you did was say "it does 'this'". What does each and every line do and why? A comment like
Walker++; // increment Walker
is not acceptable. Why are you incrementing Walker? What's it's purpose?

for (int i = 0; i < size; i++)
{
    for (int j = i + 1; j < size; j++)
    {
        if (array[i] != array[j])
        {
            *Walker = array [i];
            Walker++;
            usize++;
        }
        i++;
        j--;
    }
}

so if the first element of the array does not equal the second element then the contents of what Walker is pointing to gets assigned the first array element. Walker is then plus plused so that the next time array[i] != array[j] we don't replace the the same thing in Walker over and over again. usize is simply used for output reasons, we need to know how big the new dynamic array is so that we can output it correctly.

@iamthwee I don't know what you mean by:

recursive function to delete

Member Avatar for iamthwee

@iamthwee I don't know what you mean by:

It doesn't honestly get any easier, in fact I'm surprised nobody has mentioned it sooner.

If I give the code you'd get the answer so I'm not going to. Try to think about it and I'm sure it will come to you. Using recursion would make this problem about ten lines of code (max) to solve and will print it out preserving the original order.

Member Avatar for iamthwee

Additionally, pyTony has given you another solution on a plate with a better time complexity than a recursive solution? Any particular reason why this isn't good enough?

Just wondering?

Any particular reason why this isn't good enough?

Probably because loops are still too hard and recursion is taught two classes beyond this one? Remember, just because you understand recursion and vectors and all that high level stuff does not mean someone in their first class has ever even heard of them, let alone been taught it.
8-]

so if the first element of the array does not equal the second element then the contents of what Walker is pointing to gets assigned the first array element. Walker is then plus plused so that the next time array[i] != array[j] we don't replace the the same thing in Walker over and over again. usize is simply used for output reasons, we need to know how big the new dynamic array is so that we can output it correctly.

Yeah, that's what it does all right. I still have absolutely no idea what Walker is for but getting loaded with a bunch of letters.

Try outputting Walker after each loop and see if it contains what you expect. In fact, after the first loop do you even know what should be in Walker???

Member Avatar for iamthwee

Probably because loops are still too hard

He's using loops now.

and recursion is taught two classes beyond this one?

I can understand this point. Agreed.

Remember, just because you understand recursion and vectors and all that high level stuff does not mean someone in their first class has ever even heard of them, let alone been taught it.

I never mentioned vectors or any higher level stuff, just recursion.

Again my 2nd question was :-

"given pyTony's solution which doesn't involve recursion or vectors or any high level stuff. Why is this not good enough?"

Perhaps the OP missed it?

Probably because loops are still too hard

He's using loops now.

I would say he's learning loops now ;-)

I never mentioned vectors or any higher level stuff, just recursion.

But everyone else does when arrays are used. It was a blanket "stop suggesting sh!t beyond the noob's level" comment...

Do you can show me a non-vector solution.

Hmm.. Thesnippet I posted dores not use vectors; instead it uses C-style null-terminated arrays of char (and dynamically allocated memory). With annotatations:

// input: an array of char terminated by a null-character
// returns: a dynamically allocated array of unique chars in the input
//          terminated by a null-character

char* remove_duplicates_preserve_order( const char* cstr )
{
    // 1. get a count of the number of unique chars in the input array
    // ---------------------------------------------------------------

    bool already_seen[UCHAR_MAX] = { false } ; // to look up already seen chars 
    int cnt_unique = 0 ; // number of unique chars in the string

    // for every char in the input array till we encounter the null-character
    for( const char* p = cstr ; *p ; ++p ) 
    {
        const unsigned char u = *p ;

        // if we have not seen this char earlier, increment cnt_unique 
        // and set already_seen[u] to true
        if( !already_seen[u] ) { already_seen[u] = true ; ++cnt_unique ; }
    }


    // 2. allocate memory for the result (a null-terminated array of chars)
    // --------------------------------------------------------------------

    char* result = new char[ cnt_unique + 1 ] ; // + 1 for the null-termination 
    result[cnt_unique] = 0 ; // null-terminate result


    // 3. copy unique chars in the input array to the result array
    // -----------------------------------------------------------

    // look up table to check if we had alredy copied a char to the result
    bool already_copied[UCHAR_MAX] = { false } ;

    // for every char in the input array till we encounter the null-character
    // copy the char to the result array if we hadn't copied it earlier
    for( char* p = result ; *cstr ; ++cstr ) 
    {
        const unsigned char u = *cstr ;

        // if we have not copied this char earlier, copy it to result
        // and set already_copied[u] to true
        if( !already_copied[u] ) { already_copied[u] = true ; *p = *cstr ; ++p ; }
    }

    // 4. and finally return the array of unique chars
    // -----------------------------------------------

    return result ; 
}

Unforetuneately I am not too familiar with vectors.

Get familiar with it and learn the basics of how to use the standard library as early as possible in your learning process. Do not be led astray by people who have compiled C code using a C++ compiler all their lives and would like every one else to be in the same sorry state that they now find themselves in. That is not what you should be aspiring to be.

commented: Nooooob, remember? Dynamic memory? C'mon!!! -3

Ok so I changed my code yet again. I don't really understand the solutions you guys gave me. Here is my code:

void DeleteRepeats(char array[], int size)
{
    int usize = 0;
    char* noDupp;
    noDupp = new char[size];
    cout << size << endl;
    char* Walker = noDupp;
    char* Walker2 = noDupp;

    for (int i = 0; i <= size; i++)
    {
        cout << array [i] << endl;
        for (int j = 0; j < usize; j++)
        {
            if (array[i] != *Walker2++)
            {
                cout << *Walker2;
                cout << "Copying contents" << endl;
                *Walker = array[i];
                Walker++;
                usize++;
            }
        }
    }
    cout << "DONE" << endl;
    Output(noDupp, usize);

    delete [] noDupp;
}

now my only question is that in my "if" statement I am trying to make it so that Walker 2 goes through my dynamic array and searches for the letter we are currently on in the static array. Is such a thing possible?

Ok so what I am trying to is take in a static array in this function. Then the size of the static array is used to create a new dynamic array (noDupp). Then two pointers are created and set to the begining of this new dynamic array. We then enter a for loop so that we can go through all the elements of the static array for analysis/copying. Then If array[i] is not equal to the anything inside dynamic array it copies the static arrays elements into the dynamic array.

Is such a thing possible?

Yes. You would find it easier to solve a bigger problem by breaking it down into a set of smaller problems, each of which is easy to solve. For example:

Problem : return a dynamically allocated array containing unique chars from the input array.

Sub-problem one: check if a char in the array is a duplicate char. Is it present at an earlier position in the array?

// is char at array[pos] a duplicate? (present at an earlier position in the array)
bool is_duplicate( const char array[], std::size_t pos )
{
    for( std::size_t i = 0 ; i < pos ; ++i )
       if( array[i] == array[pos] ) return true ;

    return false ;
}

Sub-problem two: How many unique characters are there in the input array?

// get a count of unique chars in the array
std::size_t count_unique( const char array[], std::size_t size )
{
    std::size_t unique_cnt = 0 ;

    for( std::size_t i = 0 ; i < size ; ++i )
        if( !is_duplicate( array, i ) )  ++unique_cnt ;

    return unique_cnt ;
}

The bigger problem can now be reduced to:
a. Determine the number of unique characters are there in the input array
b. Dynamically allocate an array of that many chars.
c. For each char in the input array, if it is not a duplicate, copy it to the result array

char* array_without_dups( const char array[], std::size_t size, 
                          std::size_t& no_dups_array_size )
{
    no_dups_array_size = count_unique( array, size ) ;
    char* no_dups_array = new char[ no_dups_array_size ] ;

    char* walker = no_dups_array ;
    for( std::size_t i = 0 ; i < size ; ++i )
        if( !is_duplicate( array, i ) ) // if char at array[i] is not a duplicate
        {
            *walker = array[i] ; // copy it to the result array
            ++walker ;
        }

    return no_dups_array ;
}

Also, look up std::string http://www.cprogramming.com/tutorial/string.html
And then you can try rewriting the code using std::string. And realize how much easier it is to program when we use standard C++.

Note: anything starting with std:: is not a 'language extension' - it is a core, integral part of C++.

Hello again vijayan121,
Thank you very much I get it! but real quick why do you do this, what difference does it make?

std::size_t size

std::size_t defined in the header <cstddef> can store the maximum size of a theoretically possible object of any type (including array).

std::size_t is commonly used for array indexing and loop counting. Programs that use other types, such as unsigned int, for array indexing may fail on, e.g. 64-bit systems when the index exceeds UINT_MAX or if it relies on 32-bit modular arithmetic.

from: http://en.cppreference.com/w/cpp/types/size_t

Here is my final code vijayan121 tell me what you think.

#include<iostream>
#include<cstdlib>
#include <cstring>

using namespace std;

bool IsDuplicate(char array[], int size);
int SizeUnique(char array[], int size);
void DeleteRepeats(char array[], int size, int SizeUnique);
void Output(char* array, int size);

int main()
{
    int size, sizeUnique;
    char Duplicates[100];

    int Walker = 0;
    cout << "Please enter an array of characters: ";
    do
    {
        cin.get(Duplicates[Walker]); 
        Walker++; 

    }while (Duplicates[Walker - 1] != '\n'); 
    size = Walker - 1;
    sizeUnique = SizeUnique(Duplicates, size);
    DeleteRepeats(Duplicates, size, sizeUnique);

    system("pause");    
    return 0;
}

bool IsDuplicate(char array[], int position)
{   
    for(int j = 0; j < position; j++)
    {
        if(array[position] == array[j]) 
        {
            return true;    
        }
    }
    return false;
}

int SizeUnique(char array[], int size)
{
    int sizeUnique = 0 ;
    for(int i = 0; i < size; i++)
    {
        cout << "i = " << i << endl;
        if(IsDuplicate(array, i) == false)
        {
            sizeUnique++;
        }
    }
    return sizeUnique;
}

void DeleteRepeats(char array[], int size, int sizeUnique)
{
    cout << sizeUnique << endl;
    char* noDupp = new char[sizeUnique] ;
    char* Walker = noDupp;
    for(int i = 0; i < size; i++)
    if(!IsDuplicate(array, i)) // if char at array[i] is not a duplicate
    {
        *Walker = array[i] ; // copy it to the result array
        Walker++;
    }
    cout << "DONE" << endl;
    Output(noDupp, sizeUnique);

    delete [] noDupp;
}

void Output(char* array, int size)
{
    cout << "Resulting Array: ";
    char *Walker = array;

    for(int i = 0; i < size; i++ ) 
    {
        cout << *Walker++ << " ";
    }
    cout << endl << endl;
}

void DeleteRepeats(char array[], int size, int sizeUnique) is not const-correct.
A const-correct version would be:
void DeleteRepeats( const char array[], int size, int sizeUnique )
http://www.cprogramming.com/tutorial/const_correctness.html

http://www.parashift.com/c++-faq-lite/overview-const.html

Also, void DeleteRepeats(char array[], int size, int sizeUnique ) does not return anything to the caller. It is just a function for printing out the unique (non-duplicated) characters in the input array.

For that, you just need to iterate through each char in the input array and then print it out if it is not present at an earlier position in the array. And perhaps the function could have been given a more meaningful name. Something like this would suffice, wouldn't it?

// is char at array[pos] a duplicate? (present at an earlier position in the array)
bool is_duplicate( const char array[], std::size_t pos )
{
    for( std::size_t i = 0 ; i < pos ; ++i )
       if( array[i] == array[pos] ) return true ;

    return false ;
}

// print out each unique char in the array
void print_unique( const char array[], std::size_t size )
{
    for( std::size_t i = 0 ; i < size ; ++i ) // for each position i in the array
        if( !is_duplicate( array, i ) ) // if the char at array[i] is not a duplicate
            std::cout << array[i] ; // print it out
    std::cout << '\n' ;
}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.