Well, I'm not that friend of recursion, too, but my iterative solution killed the testing framework ^^ Your for-loop has to start at 1, else you reach the first element of the right sub-list. The 2nd for-loop is redundant. lastRight = in.first.previous; will do the same much quicker and less error-prone. Except for the missing recursive calls, the merge part and testing for special cases, it doesn't look so bad.

This function is nearly the same as the above one. However, the 2-argument version (I will call it ms2 from now on, and the 3-argument version ms3) was just the, one could say, "standardized interface" that must be used. ms2 calls ms3 like it is the same function. You could also call ms3 just once within ms2, resulting in one more level on the call stack. The implementations of the functions are equal, except for the fact, that the head in ms3 is just used as a return value, which isn't returned at all, because it is accessible in the caller, even if modified. All copies, pointers and auxiliary LEs are assigned referring to the first element. This consumes less time, and is easier in my opinion, even though I wouldn't say that it's impossible without this additional parameter. And of course the trivial case must be caught in ms3 to end the recursion, which isn't necessary in ms2.

OK, here is a pseudo code version of my implementation.

DLL mergesort ( DLL in, int n ) { // in is the list head, n the number of elements to sort
check for special cases and handle them separately: in == null, n == 0; n == 1; n == 2 => rearrange if necessary
m = floor ( n / 2 )
get first and last elements of left and right sub-lists: f.e. with a for-loop then the left first is the element pointed at by the list head, the right last is the previous of this,
last left and first right are at position m and m+1
wrap around left and right sub-lists
mergesort ( in, m, first left )
first left = in.first
mergesort ( in, n-m, first right )
first right = in.first
merge ( first left, first right )
return in
}
mergesort ( DLL in, LE first, int n ) { // in: head, first: first list element, n: number of elements
as the mergesort function above, except that the trivial case n == 1 must be handled, because this is the break condition for the recursion
if n == 1 => in.first = first // in.first means the first element of the list
this function also calls the 3-argument version of mergesort // the 2-argument version is just the entry point
all list elements must be addressed via the first one, not via the head, the head is just needed for the trivial case to connect the single LE to it
recursive calls and merge as above
return
}
merge (DLL in, LE first left, LE first right, int n ) {
first decide if the first element is of the left or the right sub-list, connect it to the head and move one step fwd in the sub-list
finished = f
counter = 1
while ( counter < n && !finished ) {
if next element is of left sub-list and it is not the first one => connect it to the sorted list, move fwd one step
else if next element is of right sub-list => same for right sub-list
else if the beginning of one sub-list is reached again => connect the other one to the sorted list, finished = t
move one step fwd in sorted list so that you are at the current end
counter++
}
return
}

I know that this looks somehow quick and dirty, but if you have any questions feel free to ask.

In my opinion it's not an advantage for the algorithm. It can be an advantage when dealing with the data structure itself. However, if you split the list, you have to reconnect the first to the last element of the sub-list and vice versa. It's also not that easy to check whether you reached the last element, cause you need help pointers or something similar.

I'm gonna write you down a few lines the next days, but at the moment I'm quite busy.

It has, but if I execute the program, I get an MAC error message "Segmentation fault". I got this one time with the recursive version, but the next run finished without any errors? Does anyone know what can cause this error, a simple Java program shouldn't do this.

In the meantime I wrote a fully working recursive implementation. However, I'm now working on an iterative version, because I'm not that fan of recursion for performance reasons.

Hello guys, I have to write an in-place version of Merge-Sort which works on doubly linked lists for university. This wouldn't be the problem, but there are a few conditions to meet. - the algo must work in-place (additional memory usage in O(log n)) - I cannot create new list elements or entire lists, just copies (ListElement left = new List Element() isn't possible but ListElement left = first is possible) - the algo should be recursive, but this is not necessary - each call of the algo must return a head pointer to the first element of the sub-list - the merge part must also return a head pointer

public DoublyLinkedList mergesort(DoublyLinkedList in, int numOfElements) {

    if (numOfElements > 1) {

        DoublyLinkedList firstLeft = in;
        DoublyLinkedList firstRight = in;

        for ( int i = 0; i < numOfElements / 2; i++ ) {
            firstRight.first = firstRight.first.next;
        }

        DoublyLinkedList left = mergesort ( firstLeft, (int)Math.floor(numOfElements / 2 ) );
        DoublyLinkedList right = mergesort ( firstRight, (int)Math.ceil(numOfElements / 2 ) );
        return merge ( left, right );

    } else {
        return in;
    }

}

My problem is that I'm somehow stuck right at the beginning. The algo itself shouldn't be the problem, but the additional conditions make the whole thing quite difficult for me. Of course I've already searched for useful algos or something, but I didn't find anything. Thanks in advance for your help and best wishes, Manfred

Yeah, I think you're right. However, the image size would make memory allocation easier.

Learning purpose ... not really. I know that there are a lot of libraries out there, which can load bitmaps. Actually I was just bored to death and wanted to do something. And I wanted a bitmap structure/class which gives me full control over all parameters and single values. Oh, and thanks, the parameters are now displayed correctly. There is just one thing I do not understand: The value which contains the image size is always 0x00.

Hello guys, I'm trying to write a funtion to read a simple bitmap, but I've encountered a serious problem. As model I used the description of the bitmap file format from wikipedia http://en.wikipedia.org/wiki/BMP_file_format[^] and as far as I know this is definitely the correct format. I also used the same 2x2 24-bit bitmap[^] to test my function, but except for the first value (the magic number or identifier) all other read values are wrong.

#include <stdint.h>
#include <stdio.h>

/*Data types-->*/
typedef uint8_t BYTE;
typedef uint16_t BYTE2;
typedef uint32_t BYTE4;
/*<--Data types*/

/*Bitmap file header-->*/
typedef struct BMP_FILE_HEADER
{
BYTE2 MagicNumber;
BYTE4 FileSize;
BYTE2 Reserved1;
BYTE2 Reserved2;
BYTE4 Offset;
} BMP_FILE_HEADER;
/*<--Bitmap file header*/

/*Bitmap information header-->*/
typedef struct BMP_INFO_HEADER
{
BYTE4 HeaderSize;
BYTE4 ImageWidth;
BYTE4 ImageHeight;
BYTE2 NumberOfColorPanels;
BYTE2 ColorDepth;
BYTE4 Compression;
BYTE4 ImageSize;
BYTE4 HorizontalResolution;
BYTE4 VerticalResolution;
BYTE4 NumberOfColors;
BYTE4 NumberOfImportantColors;
} BMP_INFO_HEADER;
/*<--Bitmap information header*/

/*Virtual bitmap-->*/
typedef struct BITMAP
{
BMP_FILE_HEADER bmpFileHeader;
BMP_INFO_HEADER bmpInfoHeader;
BYTE* bmpData;
} BITMAP;
/*<--Virtual bitmap*/

/*Compression types and values-->*/
#define BI_RGB 0
#define BI_RLE8 1
#define BI_RLE4 2
#define BI_BITFIELDS 3
#define BI_JPEG 4
#define BI_PNG 5
/*<--Compression types and values*/

BITMAP readbmp(const char* _pcFileName)
{
FILE* bmp = fopen(_pcFileName, "rb");

BITMAP bitmap;
fread(&bitmap.bmpFileHeader, sizeof(BMP\_FILE\_HEADER), 1, bmp);

fread(&bitmap.bmpInfoHeader, sizeof(BMP\_INFO\_HEADER), 1, bmp);

fseek(bmp, bitmap.bmpFileHeader.Offset, SEEK\_SET);

    bitmap.bmpData = (BYTE\*)malloc(bitmap.bmpInfoHeader.ImageSize);
fread(bitmap.bmpData, bitmap.bmpInfoHeader.ImageSize, 1, bmp);

fclose(bmp);

return bitmap;

}

To test my function i wrote a short program, which reads the above mentioned bitmap.

#include <iostream>
#include "readbmp.h"

I wrote a default constructor (empty and parameterless) and now it works. However, I do not know why; the default constructor is never called. By the way, I know that a default constructor is not any self written one^^

Hello guys, I'm trying to write a simple class in c++ including a short constructor. Despite the fact that there are no obvious mistakes, there's always the same error message C2512: no appropriate default constructor available I do not call the default constructor, but my self written one, also the parameter lists match. Does anyone already know this problem? If not I can post the listings. Thanks and best wishes.

Thanks for the answer. I've done a lot of microprocessor programming in the last time and there I use char whenever possible (it's the smallest type and working without causing any troubles). However, that's pure C and there are (I know) a few differences to C++. Normally I use C++ for game programming and mathematical things and that's more or less the first time I do something with strings in C++, so this is all in all just a try.

Hello guys, I want to split a string into substrings using strtok(). The code is

#include "stdafx.h"

#using #include #include #include using namespace System;
using namespace std;

char str2list(char* str, char** list, const char* delimiters)
{
for (char c = 0; c < sizeof(list) / sizeof(char*); c++)
{
list[c] = strtok(str, delimiters);
if (list[c] == NULL) break;
}
return c;
}

int _tmain()
{
char** arglist;
arglist = new char*[16];
char* exmp = "I have a problem!";
str2list(exmp, arglist, " ");
for (char c = 0; c < sizeof(arglist) / sizeof(char*); c++)
{
cout << arglist[c] << endl;
}
delete[] arglist;
return 0;
}

When I try to execute the program a runtime error occurs saying that there is a null-reference exception in the line list[c] = strtok(str, delimiters);. To ensure that there is enough free memory I even used the new operator. Does anyone have an idea why this doesn't work? Thanks and best wishes.

I found out that if I just use the struct and not struct pointers as map value type it's working without making any problems. Anyway, I don't understand why. In the meantime I also found a few code examples using a struct or a class as map value type, but I didn't see any examples using struct pointers.

Hello guys, I wanna make a map that contains an integer key and a struct as value type. struct SRect { int iX, iY, iW, iH; }; map RectMap; This piece of code compiles fine. However, if I want to insert a pair into the map a runtime error occurs. void MakeParamRect(int iID, int iX, int iY, int iW, int iH) { RectMap[iID]->iX = iX; RectMap[iID]->iY = iY; RectMap[iID]->iW = iW; RectMap[iID]->iH = iH; } I've also tried it using the insert() function. RectMap.insert(make_pair(iID, {iX, iY, iW, iH})); In this case the struct notation with the curly brackets seems to produce the error (compiler says that a semicolon is missing before the first {). How can I make this code work, or is a struct not a valid value type for a map (it is valid in my opinion)? Thanks for your help.

According to MS and several forums you have to place a file called mspdb80.dll in \WINDOWS\system32\ if this error occurs. I already added this file becuase I needed it in another project. However, there was another version of this file too called mspdb60.dll. I deleted the 80-version and my IDE workes again. :)

Hello guys, I've a big problem with VC++2008. Till now it was working fine, than I created a new project tried to compile it and I get the error message: fatal error c1902: error in program database manager. check installation. I didn't change anything within my IDE I just tried to compile a project. I already tried to reinstall the IDE but this didn't help, I still get this error. I'll try de-installing VC++2008 and deleting all components, maybe than a reinstallation will work. At the same time I got this problem with my VC++2005. Same error but I tried to recompile an old project when it occured. However, my VS2003.NET is still working fine. But I need VC++2008 for a special project. Does anyone have an idea about this? Thanks and best wishes, Manfred

Thanks, this was my problem. I knew that variables must be defined at the beginning of their scope when programming micro processors, didn't know that this is also important when writing Windows programs. Thanks a lot.