CODEWITHSUNDEEP
c++structfind-occurrences
davidgrim
davidgrim

Reputation: 21

Program that takes a users inputted characters and displays them in descending order of occurrence

"Write a program that reads in a sequence of characters entered by the user and terminated by a period ('.'). Your program should allow the user to enter multiple lines of input by pressing the enter key at the end of each line. The program should print out a frequency table, sorted in decreasing order by number of occurences, listing each letter that ocurred along with the number of times it occured. All non-alphabetic characters must be ignored. Any characters entered after the period ('.') should be left in the input stream unprocessed. No limit may be placed on the length of the input."

I don't know where to begin with this. So far this is what I have come up with:

#include<iostream>
using namespace std;



  int main(){


        int count=0;
    char ch[count];
    int i=0;

    cout<<"Enter a sequence of characters (end with '.'): ";
    cin>>ch[count];
    while(ch[count]!='.')
    {
        count++;
        cin>>ch[count];


    }

    cout<<"There were "<<count<<" characters in the string"<<endl;
    return 0;
 }

Right now the program takes in the users input and displays the number of characters in it, but I cannot get it to display any of the characters, let alone in descending order. The sort isn't my problem, that I fully understand how to program, but I cannot display the chars stored in the input stream.

My instructor suggested we use a struct but right now I just need some direction to go. The output should be formatted as the following:

Enter a sequence of characters (end with '.'): do be Do bo. xyz


Letter:    Number of Occurrences

o     3
d     2
b     2
e     1

I'm not asking for anyone to do the coding for me, I simply need help on where to start, and how to get the chars to display. We cannot use the string class and thus any string functions other than strlen().

Upvotes: 0

Views: 3156

Answers (2)

Stephan Lechner
Stephan Lechner

Reputation: 35154

There are two parts to be solved. First, reading in the characters one by one, ignoring any non-alpha char, and count the others; Second, print the scores in descending order.

The first part can be solved by simply treating a character as an ASCII-value between 0 and 255 (i.e. in the range of unsigned char), and having an array of counts for each of these values.

Second, you could simple run through the counts, find the maximum, and then print it. Continue this until all values > 0 have been considered.

See the following code illustrating this approach:

#include <sstream>

int main() {

    stringstream ss("do be Do bo. xyz");
    unsigned char c;
    unsigned int counts[256] = {0};
    while (ss >> c && c != '.') {
        if (! isalpha(c)) {
            continue;
        }
        c = tolower(c);
        counts[c]++;
    }

    while (1) {
        // find next maximum
        int max = 0;
        int maxPos = -1;
        for (int i=0; i<256; i++) {
            if (counts[i] > max) {
                max = counts[i];
                maxPos = i;
            }
        }
        if (max == 0) {
            break;
        }
        else {
            cout << (char)maxPos << ":" << max << endl;
            counts[maxPos] = 0; // don't consider this pos in next run
        }
    }
}

Output:

o:3
b:2
d:2
e:1

Upvotes: 1

An0num0us
An0num0us

Reputation: 961

You can read the input one char at a time (this is what you will use) or read entire chunks of it (faster solution) if the input is loaded from a text file or it is checked by an online judge or something similar that loads the entire input at once, but that is a sidenote.

First of all, I would start with adding this line to your code right at the beginning of your main

ios::sync_with_stdio(false);

This line will make your code significantly faster because C++'s I/O is not synchronised with C's I/O anymore, so it removes a significant overhead, but keep in mind that you will get meaningless garbage if you mix the two I/O libraries after that line.

Once the I/O is ready, I would add the code that reads the input and counts the occurences. To achieve that, you should be interested in one particular function - get. Now you just need an array of ints that is larger than 0 (must fit any characters that might appear as input, the set of the characters should be specified somewhere, but a safe number would be 256 for ASCII), a loop, a condition that terminates the loop (char from input == '.') and you are almost done reading and counting (no functions needed for it!).

Sorting isn't that terrible after all. A bubble sort is probably not the way to go in most cases, but how many characters are there? 40-ish? 50-ish? 100-ish? Unless you go beyond 300-500 characters, it is not worth to implement the best ever unknown to makind O(lgn) time, O(1) space, stable sorting algorithm because it is likely to perform worse on average than the simpler algorithms. Look for merge sort or quick sort if you want a heavy-duty algorithm, or look for simpler alternatives, e.g. bubble sort (the simplest and the slowest) or insertion sort.

Upvotes: 2

Related Questions