Removing duplicates from string array.

[CBnewbie]

I need some help figuring out how to remove duplicates from an array. I've been working on this for a few days now, and every time I think I'm getting close, it just causes my program to shut down.

I've gt a text file with city names in it and mileage distances between the cities. But the cities are listed more than once. So out of 4 cities, I currently have an array with 12 elements. I need to remove the duplicates.

I'm not asking for someone to write the code for me... Just a little help on how to go about ignoring/removing the duplicates, so that I can end up with an array of just 4 unique city names. I'm still pretty new at this, sorry if this is a really basic question.

Thanks a lot, for any help!

-Charles...

[Ancient Dragon]

The easiest was is not to put the duplicates in the array in the first place. When you read a city name from the file check to see if the name is already in the array. If not, then add it.

[CBnewbie]

I've tried doing that, and it seems that each time I do that it doesn't grab everything. Maybe because they are listed like this:

city1 city2 mileage
city1 city2 mileage
etc...etc.

I've made some progress with it since posting. I've managed to sort the array so that I could try to compare one elsment to the next. But, when I try to remove the duplicates it still causes the program to crash... Here's what I've done so far... (forgive me if this code looks really pathetic...:) )

-------------------------------------

#include <iostream>
#include <fstream>
#include <iostream>
#include <iomanip>
#include <stdlib.h>

using namespace std;

void readFile1(ifstream &dataFile, string &city1Grab,  string &city2Grab, int &distanceGrab, int &i);
void display1(string city1[], int distance[][6], int i, int j);
string center(int width,string str1);

void sortArray();
void deleteDuplicates();

const int numCities=12;

const char NumberOfCities = 12;
const char firstElement = 0;
const char lastElement = NumberOfCities -1;

string city1[numCities]={"x"};

int main()
{
    string header1="Texas Department of Transportation";
    string header2="Mileage chart";
    string city1Grab, city2Grab, city2[numCities]={"x"};
    int distanceGrab, distance[6][6]={{0},{0}}, i=0, j=0, x=0;
    string city[4]={"no"}, test;

    for(i=0;i<4;i++)
    {
        city1[i]="x";
        cout << city1[i] << endl;
    }

     cout << center(80,header1);
     cout << center(80,header2) << endl << endl;

    ifstream dataFile;
    dataFile.open ("dot.txt");
    readFile1(dataFile, city1Grab,  city2Grab, distanceGrab, i);


        i=0;
        j=0;
    while(dataFile)
    {
        city1[i]=city1Grab;
        city1[i+6]=city2Grab;

        i++;
        readFile1(dataFile, city1Grab,  city2Grab, distanceGrab, i);

    }


for(i=0;i<numCities;i++)
{
cout << city1[i] << endl;
}
sortArray();
deleteDuplicates();
system("PAUSE");

for(i=0;i<numCities;i++)
{
cout << city1[i] << endl;
}
	return 0;
	dataFile.close();
}

void readFile1(ifstream &dataFile, string &city1Grab, string &city2Grab, int &distanceGrab, int &i)
{
    dataFile >> city1Grab >> city2Grab >> distanceGrab;

    return;
}

void display1(string city1[], int distance[][6], int i, int j)
{

    for(i=0;i<numCities;i++)
    {
        cout << setw(10) << left << city1[i];
    }

    return;
}

string center(int width,string str1)
{
    int sizeOfString;
    int padding;
    sizeOfString=str1.length();
    if ( width > sizeOfString)
    {
        padding=static_cast<float>((width-sizeOfString)/2);
        for (int i=0;i<padding;i++)
        {
        str1=' '+str1;
        }
        for (int i=0;i<padding;i++)
        {
        str1=str1+' ';
        }
    }

return str1;
}

void sortArray()
{

	int i,j;
	string temp;

	for(i=lastElement; i>=firstElement; i--)

	{
		for(j=firstElement; j<i; j++)

		{
			if(city1[j] > city1[j+1])
			{
				// Swap elements as needed
				temp = city1[j];
				city1[j] = city1[j+1];
				city1[j+1] = temp;
			}
		}
    }
    return;
}

void deleteDuplicates()
{
int i,j;
int tmp=0;
bool flag;

for(i=0; i<=lastElement; i++)
{

	flag=false;

	if(city1[i] == city1[i+1])
	{
		flag=true; //found duplicate
		tmp++;     //increment num of duplicates
	}

	{

		for(j=i-tmp;j<=lastElement;j++)
		{
			city1[j] = city1[j+tmp];
		}
	}

}
    return;
}

-------------------------------

[Ancient Dragon]

why would you want to remove the duplicates ? The distance from London to Paris is going to be different than from London to New York. So you would need London in that array twice.

It would probably be easier to do what you want by using two different arrays of city names then trying to stuff both city1 and city2 into the same array as you are doing on lines 50 and 51.

[CBnewbie]

I tried to figure out how to work it while leaving the duplicates in, but that really threw me for a loop trying to figure out a way to do that. here's what I start with:

Abilene Amarillo 200
Abilene Dallas 220
Abilene Waco 360
Amarillo Dallas 350
Amarillo Waco 440
Dallas Waco 95

and I am supposed to end with this:

Abilene     Amarillo     Dallas     Waco

Abilene       0              200            220         360

Amarillo      200           0               350         440

Dallas         220          350            0             95

Waco          360          440            95           0

and I have to use a one dimensional array for the cities, and a two dimensional array for the mileage (haven't even got to that yet). This is making me feel really stupid right now, cause everything else I've done has been real easy. I must just be missing something really obvious, or something...

Thanks,
Charles...

[VernonDozier]

I tried to figure out how to work it while leaving the duplicates in, but that really threw me for a loop trying to figure out a way to do that. here's what I start with:

Abilene Amarillo 200
Abilene Dallas 220
Abilene Waco 360
Amarillo Dallas 350
Amarillo Waco 440
Dallas Waco 95

and I am supposed to end with this:

Abilene     Amarillo     Dallas     Waco

Abilene       0              200            220         360

Amarillo      200           0               350         440

Dallas         220          350            0             95

Waco          360          440            95           0

and I have to use a one dimensional array for the cities, and a two dimensional array for the mileage (haven't even got to that yet). This is making me feel really stupid right now, cause everything else I've done has been real easy. I must just be missing something really obvious, or something...

Thanks,
Charles...

I don't see any duplicates in your input list. A duplicate would be the same PAIR of cities twice, not the same city twice. You have it defined here as the same city twice:

void deleteDuplicates()
{
int i,j;
int tmp=0;
bool flag;

for(i=0; i<=lastElement; i++)
{

	flag=false;

	if(city1[i] == city1[i+1])
	{
		flag=true; //found duplicate
		tmp++;     //increment num of duplicates
	}

	{

		for(j=i-tmp;j<=lastElement;j++)
		{
			city1[j] = city1[j+tmp];
		}
	}

}

Line 12 is not a good test for duplicates. You are flagging too much as a duplicate. I don't see you using your city2 array. This problem is crying out for a struct:

struct citydistance
{
     string city1;
     string city2;
     int distance;
}

Have a one dimensional array of type citydistance. Read the data into this array and store it. Check for any duplicates as you read in the data. A duplicate is where city1 and city2 have occurred as a pair earlier in the array. You'll have to check to make sure that the cities haven't occurred before in reverse order (i.e. (Dallas, Waco) is the same as (Waco, Dallas)).

Once you have it all read in, then you'll fill in a 2-D array of integers called distance.

You may want to make a one-dimensional array of cities that is of type string. In THIS array, a duplicate will be any city that has already seen before. I think you are mixing up the different types of arrays and what their sizes are and what the definition of "duplicate" is for each. Assuming you have 6 cities, your cities array will have 6 elements, your distance array will be a 6 x 6 array, and your citydistance array would probably have 15 elements (6 * (6 - 1) / 2).