|
hi, i have C exam next week, so i started solving questions from previous years exams and run into this question, the answer i come up to is far far from having reasonable length, it's too complicated and long , but i can't come up anything shorter.
the question is: write a function that receives an array of letters , and a pointer to final result string that hasn't allocated yet, the function supposed to take the array of letters and count the appearance of every letter and make the final result string look like that:
received array of letters : "abbacdeefg"
result string: "a 2;b 2;c 1;d 1;e 2;f 1;g 1"
in the result it should be alphabetically printed
here is the code that i wrote, it just doesn't makes sense that this is the actual solution:
void sortarray(char str[],char * final)
{
int i = 1,j, extra = 0;
char * letters, *lerrptr;
int * count, * cerrptr;
int size = 0, flag = 0;
letters = (char *) malloc(sizeof(char) * 1);
if(letters == NULL) exit(1);
count = (int *) malloc(sizeof(int) * 1);
if(count == NULL) exit(1);
letters[0] = str[0];
count[0] = 1;
size++;
while(str[i] != 0)
{
flag = 0;
for(j = 0 ; j < size ; j++)
{
if(str[i] == letters[j])
{
count[j]++;
flag = 1;
}
}
if(!flag)
{
flag = 0 ;
size++;
lerrptr = letters;
letters = (char *) realloc(letters,sizeof(char) * size);
if(letters == NULL)
{
free(lerrptr);
free(count);
exit(1);
}
cerrptr = count;
count = (int *) realloc(count,sizeof(int) * size);
if(letters == NULL)
{
free(cerrptr);
free(letters);
exit(1);
}
letters[size-1] = str[i] ;
count[size-1] = 1 ;
}
i++;
}
for(i = 0 ; i < size - 1; i++)
{
for(j = 0 ; j < size - 1 - i ; j++)
{
if(letters[j] < letters[j - 1])
{
letters[j] ^= letters[j+1];
letters[j+1] ^= letters[j];
letters[j] ^= letters[j+1];
count[j] ^= count[j+1];
count[j+1] ^= count[j];
count[j] ^= count[j+1];
}
}
}
for(i = 0 ; i < size ; i++) if(count[i] > 9) extra++;
final = (char *) malloc(sizeof(char) * (size * 4) + extra + 1);
j = 0;
for(i = 0 ; i < size ; i++)
{
final[i*4 + j] = letters[i];
final[i*4 + 1 + j] = ' ';
if(count[i] > 9)
{
final[i*4 + 2 + j] = count[i]/10 + 48;
j++;
final[i*4 + 2 + j] = count[i]%10 + 48 ;
}
else final[i*4 + 2 + j] = count[i] + 48;
final[i*4 + 3 + j] = ';';
}
final[i*4 + j] = 0;
printf(" %s ", final);
}
can anyone help me come up with more reasonable solution?
|
|
|
|
|
It's probably not the shortest possible solution, but to give you an idea maybe:
void sortarray(char str[],char *final)
{
int counter[26] = {0};
int finallength = 0;
int i;
for(i=0;str[i];i++)
counter[str[i]-'a']++;
for(i=0;i<26;i++){
if(counter[i])
finallength += 4;
if(counter[i] > 9)
finallength ++;
}
final = (char*)malloc(finallength+1);
final[0] = 0;
char part[6];
for(i=0;i<26;i++)
if(counter[i]){
sprintf(part,"%c %d;",i+'a',counter[i]);
strcat(final,part);
}
final[finallength-1] = 0;
printf(final);
}
I copied some behaviour from your code which I would like to comment on though:
1. sortarray receives char * final , i.e. a single pointer. While you can use malloc on this, the function which calls sortarray , does not get its pointer to final updated. To solve this, you would need to pass a double pointer (so char **).
2. We're ignoring the case where a letter may occur more than 99 times in a string. It's probably a fair assumption but it's good to be aware of this.
modified 13-Sep-18 21:01pm.
|
|
|
|
|
thanks a lot, yes i know , the question didn't implied i have to save it, (there is a problem i forgot to free it in the end thou)
and yes i hope the assumption is fair, the question doesn't actually mentions anything about it
|
|
|
|
|
Good catch about the free, I forgot it as well
Good luck with your exam!
modified 13-Sep-18 21:01pm.
|
|
|
|
|
|
Handling occurrence greater that 100 would requires a few extra lines.
int test = counter[i];
while (test >= 10)
{
++finalLength;
test /= 10;
}
Your code assume that the input string only contains the 26 lowercase letters. Without specification, we could assumes that we want to support all 256 possible 8 bit characters.
Filling of the final array could be a little more effecicient by using strlen and a pointer to the current output position.
As a final note, final length is 1 too big except for empty input. Thus is might be possible that the returned string contains one garbage character at the end.
Philippe Mori
|
|
|
|
|
Since you are using 8 bits characters, one solution would be to allocate an array (of integers) for all possible letters and initialize the whole array to 0. Then for each received letter, you increment the appropiate count (the array is indexed by the ordinal value of the character).
After that, you could compute the size of the string to create.
As an alternative, this could also be done while receiving letters. Each time a letter is used for the first time, you must add 4 characters. And each time an incrementation cause the number of digit to increment (from 9 to 10, 99 to 100 etc...) add 1 to the required number of digits.
Then you can allocate the array. A special case would be when the input is empty. You would have to uses a size of 1 instead of 0.
Finally as the indexed array is already in order, you can then write the result skipping any count of 0. An ; need to be added before outputting the letter, space and count except for the first outputted item.
Then final '\0' need to be appended at the end.
By the way an array and a loop could be used to have the list of value when one digit need to be added. That is an array with values like 10, 100, 1000... up to the desired maximum (1e10 to support 32 bit integer range).
In fact, the code would be much simpler and shorter by assuming worst case (256 * 13) assuming a 32 bit program. You then output to that buffer and at the end, you allocated the final string using the actual length (+ 1) of the outputted string.
If temporary memory usage is not a problem, it could then easily be done in less than 20 lines of code.
Philippe Mori
|
|
|
|
|
Hi,
atikot wrote: can anyone help me come up with more reasonable solution? This is shorter:
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
void CharCount(char str[], char** result)
{
int i;
unsigned int count[256];
if (!strlen(str))
return;
if (*result = (char*)malloc(min(strlen(str), 256) * 8))
{
char* out = *result;
memset(count, 0, sizeof(count));
for (i = 0; str[i]; i++)
++count[str[i]];
for (i = 0; i < 256; i++)
if (count[i])
out += sprintf(out, "%c %u;", (char)i, count[i]);
*--out = '\0';
}
}
int main()
{
char* out = NULL;
CharCount("abbacdeefg", &out);
if (out)
printf("%s\n", out);
free(out);
}
cheers,
AR
Code edited after Stefan_Lang[^]'s excellent review.
When the wise (person) points at the moon the fool looks at the finger (Chinese proverb)
modified on Monday, July 4, 2011 10:43 AM
|
|
|
|
|
Two things:
1. If applied to a very long string (e. g. a string containing an entire article or book) the result string becomes unreasonably large. You might want to determine the minimum between strlen(str) and 256 rather than just strlen(str) . Also, since you're printing the chars as ints, you'll need at least 6 bytes to store the result of "%c %d;" from sprintf() since the first value can be up to 3 digits long.
2. You're printing the characters as integers, against the specification. (note: you can safely do so since you won't count any nonprintable characters that might meddle with your output). Printing chars as chars will also shorten the output string (see above)
|
|
|
|
|
Hi Stefan,
Not sure this quick answer deserved such in-depth excellent review
My updated post should address your pertinent issues, and handle empty input string.
cheers,
AR
When the wise (person) points at the moon the fool looks at the finger (Chinese proverb)
|
|
|
|
|
I have written a simple, test case DLL for the Metatrader 4 platform but unfortunately it is not working, and the first thing I would like is to check that my parameter passing syntax is correct.
The C++ code
MT4_EXPFUNC void _stdcall updateBuffer( history * history, double * buffer, int Bars, int IndicatorCounted, int ma_period )
{
for( int ii = 0; ii < Bars; ii++ )
{
buffer[0] = history[ii].close;
}
}
The .mgh code
#import "test.dll"
void updateBuffer( double& history[][6], double& buffer[], int bars, int indicator_counted, int ma_period );
#import
The relevant parts of the .mq4 file
#import "test.dll"
void updateBuffer( double& history[][6], double& buffer[], int bars, int indicator_counted, int period );
#import
int start(){
updateBuffer(history, buffer, Bars, IndicatorCounted(), ma_period);
}
Could someone check that I have declared and am passing all parameters correctly?
|
|
|
|
|
The number of indirection see to not be the same. Why the declaration of parameters in C++ code are not exactly the same as the one in Metatrader 4? (By the way, I don't knows that platform).
In the first code snippet, there is an error. It is written history * history for the first parameter.
The [6] is also required in C++ as otherwise the compiler won't know that there are 6 consecutive doubles for that index level.
Otherwise a & is typically equivalent to an * at the assembly level. Same for a [] which is essentially equivalent to an * but this time at the source level.
Philippe Mori
|
|
|
|
|
I am simply trying to figure this out.
So, we have this API, GetQueuedCompletionStatus , which among others params, returning completion key which is "per device" and overlapped struct, which is "per call". Or something like this. In every example on the net and in platform SKD's samples, The Overlapped structure gets extended like this:
struct MyOverlapped
{
OVERLAPPED Overlp;
};
And then it is used with
GetQueuedCompletionStatus and other calls (WSAREcv, WSASend, etc). So the question is: why is that so? Why not use only completion key? From my observations, (debugging), data, which arrives with the completion key and data which gets extracted from casting MyOverlapped to received overlapped, is completely the same. For example, somewhere we do:
MyOverlapped * myOver = do_something_insert_something();
PostQueuedCompletionStatus(..., (ULONG_PTR)myOver, ...);
and inside worker thread, we have:
MyOverlapped * myOver = NULL;
GetQueuedCompletionStatus(..., (PULONG_PTR)&myOver, ...);
This code above returns the same what this code below:
MyOverlapped * myOver = do_something_insert_something();
PostQueuedCompletionStatus(..., (ULONG_PTR)0, &myOver->Overlp);
and then in worker thread:
MyOverlapped * myOver = NULL;
ULONG_PTR Data;
LPWSAOVERLAPPED Overlapped = NULL;
GetQueuedCompletionStatus(..., (PULONG_PTR)&Data, (LPOVERLAPPED *)&Overlapped);
myOver = (MyOverlapped *)Overlapped;
So why to extend Overlapped structure and whats the deal with these: "per device" and "per call"?
Thanks
011011010110000101100011011010000110100101101110
0110010101110011
|
|
|
|
|
The key is per-handle, not per device.
Many Win32 APIs have a pointer-sized parameter that applications can use and the system simply passes through. This is one of those.
Depending on implementation, one may need a place to store some data associated with the lifetime of the handle - a pointer to a C++ object, an index into an array, an ID number, etc. That may not be something wanted in the overlapped structure which technically is only used by the system for each overlapped operation.
As I've mentioned to you, I personally reuse the same custom OVERLAPPED structure object for multiple I/O calls, so for my implementations I can keep per-handle data there as well. So, yes the key is not relevant to me.
It's there if you need it, ignore it if you don't need it (the system ignores it)
Mark Salsbery
Microsoft MVP - Visual C++
|
|
|
|
|
Mark Salsbery wrote: The key is per-handle, not per device.
Thanks! This explains couple of things.
Ok, so (from that what i can see) if this will be a good practice (currently i am reusing custom Overlapped struct too):
1. Key data structure, which holds, lets say, a socket - accepted or connected or listening, some other things related to a socket, which are valid as long as our socket is valid, for example local and remote ip addr and port. - so all this lives as long as our socket lives
2. Extended Overlapped structure, which holds, for example, such info like current I/O operation and WSABUF and probably nothing else.
Or maybe all this is just playing around and doesn't matter at all and it's ok to just use extended Overlapped all the time? And, (probably) last (probably lame :P) question - it just came to my mind, for now my server prototype is running on localhost and not event close to be loaded so every call to wsasend / wsarecv completes right away without waiting and i am manually posting completion packets with PostQueuedCompletionStatus to simulate expected behavior, where key param is my struct of course, and IO operation is updated before packet is actually posted. So on the other end, i am parsing IO operations correctly. But, i am thinking now, if wsarecv will block and completion packet will arrive some time later - so how on the other end i can correctly parse current IO operation? And maybe exactly in such case - i need this extended overlapped and only, because on the other end (in worker thread in fact) - when packet will arrive, - i'll get this exact Overlapped and will be able to grab current IO?
Am i crazy, wrong or maybe this is how it is?
Thanks in advance
011011010110000101100011011010000110100101101110
0110010101110011
|
|
|
|
|
1. Agree.
2. Agree.
Or maybe ... So on other end ...
Which is how you can use an IOCP to be a job/task manager like you could also create using the Win32^ Job Object / Thread Pool functions.
But I am thinking now ...
wsarecv(OL) will not block your posting thread.
When GetQueuedCompletionStatus returns the results of the wsarecv, the specified buffer will be filled with the received data ... of course this means the buffer specified in OL must persist from time wsarecv(OL) is called until you are done with it after GetQueuedCompletionStatus.
If you did not get all data (i.e. only posted recv to get a header) then either post another async recv, or (depending on how you handle things) you may be able to call a sync recv to get rest of data (e.g. payload).
...cmk
The idea that I can be presented with a problem, set out to logically solve it with the tools at hand, and wind up with a program that could not be legally used because someone else followed the same logical steps some years ago and filed for a patent on it is horrifying.
- John Carmack
|
|
|
|
|
csrss wrote: ...my server prototype is running on localhost and not event close to be loaded so every call to wsasend / wsarecv completes right away without waiting and i am manually posting completion packets with PostQueuedCompletionStatus to simulate expected behavior, where key param is my struct of course, and IO operation is updated before packet is actually posted. So on the other end, i am parsing IO operations correctly. But, i am thinking now, if wsarecv will block and completion packet will arrive some time later
Maybe overthinking it? First, even if wsasend/wsarecv complete immediately, you still get completion packet from IOCP on an IOCP thread, so no need to handle special case of error on wsasend/wsarecv if there's no error or error code is "pending". Second, WSARecv won't block on an overlapped operation, so I'm not sure what you're thinking there.
Mark Salsbery
Microsoft MVP - Visual C++
|
|
|
|
|
Alright, thanks guys, going to experiment a bit longer with this.
By "blocking" i meant a situation where you "post" wsarecv / wsasend and it returns error_io_pending and then awaits for completion packet in worker thread :P
011011010110000101100011011010000110100101101110
0110010101110011
|
|
|
|
|
csrss wrote: By "blocking" i meant a situation where you "post" wsarecv / wsasend and it returns error_io_pending and then awaits for completion packet in worker thread :P
Gotcha. But technically that is not blocking...that's asynchronous I/O
Mark Salsbery
Microsoft MVP - Visual C++
|
|
|
|
|
One framework I created that used ICOP had the following classes:
IoObj - Base class for I/O
IoHnd - IFS handle based
File - OS file access
NetSocket - Network socket
NetIpClnt/NetIpSvc, NetTCP*, NetUdp*, NetIrda*, NetBth*, ...
NetFPT*, NetNNTP*, ...
WSAOVERLAPPED
IoOL - Base overlapped; adds flags, timestamps, type, control, buffer
NetIoOLAddr - specialied for sendto/recfrom, contains remote address
NetIoOLAccept - specialized for handling AcceptEx
IoCP - I/O completion port
The IoCP had the main posting functions and GetQueuedCompletionStatus loop.
To post a msg on an IoCP you'd pass an IoObj* and IoOL*.
The IoObj* would be the key, the IoOL* the overlapped (per call).
The IoCP GetQueuedCompletionStatus loop would call (something like) IoObj->Msg(IoOL*).
With the above you can use one or more IoCP instances to handle any combination of files, sockets, or other IoObj based objects (e.g. jobs/tasks).
I found both having key and OL convenient. Without an explicit key param you'd have to add it as state to your extended OL ... which you may want anyways.
...cmk
The idea that I can be presented with a problem, set out to logically solve it with the tools at hand, and wind up with a program that could not be legally used because someone else followed the same logical steps some years ago and filed for a patent on it is horrifying.
- John Carmack
|
|
|
|
|
Thanks for the reply. Currently i am trying to dig into IOCP and get some descent understanding what's going on behind scenes. Could you check my latest reply to Mark? There is some important question i am trying to figure out though. Thanks
011011010110000101100011011010000110100101101110
0110010101110011
|
|
|
|
|
Hi all,
i want to encrypt/decrypt the string.
what method or option is gud for this.
please help me for this.
if possible please provide me any sample or example.
thanks in advance.
|
|
|
|
|
If you are working under windows then check out The Cryptography API[^].
> The problem with computers is that they do what you tell them to do and not what you want them to do. <
> //TODO: Implement signature here<
|
|
|
|
|
Depending on your needs, the following may be sufficient:
CryptProtectData()
CryptUnprotectData()
They encrypt using either machine or user specific key and help you avoid having to mess with the Crypto API.
...cmk
The idea that I can be presented with a problem, set out to logically solve it with the tools at hand, and wind up with a program that could not be legally used because someone else followed the same logical steps some years ago and filed for a patent on it is horrifying.
- John Carmack
|
|
|
|
|
From my application, I need to launch another window which will display some data like an SDI application. Also, this launched window should
(a) find a separate mention in taskbar
(b) close when my application is closed
I think a good way to achieve this is to have an MFC DLL, exporting a function to launch this other window as we create an SDI document.
I don't want to perform any File I/O from the DLL currently, so I inherited from
CDocument without putting any code inside
Serialize .
So I have:
CSingleDocTemplate *pPeopleListDocumentTemplate;
pPeopleListDocumentTemplate = new CSingleDocTemplate(IDS_DUMMY_STRING, RUNTIME_CLASS(CPeopleDoc),
RUNTIME_CLASS(CFrameWnd), RUNTIME_CLASS(CDLLDocView));
That is, I give my frame class as CFrameWnd.
This kind of worked: I do see the document when I call the DLL function. But, the window is totally "transparent" initially, and takes the appearance of whatever's present on the screen behind it, and retains it as I move it. What are the properties of the Frame which I need to change? What will be a good time to change it?
|
|
|
|
|