pointer of pointer of a structure data type unexpected variation

Code:

---


 Here is my problem: In the following code pcodewords is pointer of pointers of structure type. NodeConstruct, GetCodeWord and nextcw are functions with their own proper implementation. I am confused that eventhough the pointer pcodewords[0] is not affected by the do while loop, the printing results for its corrosponding structure variable before and after the do while loop are not the same.

 I am really stacked because of this . I really need your help guys and it is urgent! 10q anyway!

  pcodewords[0]=NodeConstruct(cw,n);
  //printing values for checking
  int *p=GetCodeWord(pcodewords[0]);

    for(int j=0;j<n;j++)

      printf("%d", *(p+j));

    printf("\n");

  int *cexist,i=1;

  do

  {

    cexist=nextcw(cw,n);

    if(cexist)

      pcodewords[i]=NodeConstruct(cexist,n);
    ++i;
  }while(cexist);

  pcodewords[0]=NodeConstruct(cw0,n);

  //printing the values for checking
 
    int *p=GetCodeWord(pcodewords[0]);

    for(int j=0;j<n;j++)

      printf("%d", *(p+j));

    printf("\n");

  }

---

Well, given that you execute

Code:

---

pcodewords[0]=NodeConstruct(cw,n);

---

and then

Code:

---

pcodewords[0]=NodeConstruct(cw0,n);

---

it's not too surprising that pcodewords[0] has changed. You're assigning it to a whole new node, as far as I can tell.

BTW, [code] [/code] tags are only supposed to go around your code, not the rest of your message too. Also, instead of long-winded explanations about what various variables are, it's much easier for us if you simply show the declarations of the variables and their types (if they're structures or what not).

I am new that is why i am not in the right track of presentation! Here is a clear code

Code:

---

#include<stdlib.h>


#include "node.h"
#include "functions.h"



int main()

{

  int n,d,w;

//inputs from user

  printf("Enter n,d,and w:\nn=");

  scanf("%d",&n);

  printf("d=");

  scanf("%d",&d);

  printf("w=");

  scanf("%d",&w);

  printf("n=%d, d=%d, w=%d\n",n,d,w);

//generate the codewords
  Node **pcodewords;
  pcodewords=malloc(sizeof *pcodewords);
  pcodewords[0]=NULL;

  int cw[n],cw0[n];

  //The initial codeword is 00000....111111

  for(int i=0;i<n-w;++i)

    cw[i]=cw0[i]=0;

  for(int i=n-w;i<n;++i)

    cw[i]=cw0[i]=1;

  pcodewords[0]=NodeConstruct(cw,n);

 /printing the codewords for checking
  for(int i=0;i<combination(n,w);i++)

  {
    int *p=GetCodeWord(pcodewords[i]);

    for(int j=0;j<n;j++)

      printf("%d", *(p+j));

    printf("\n");

  }
  int *cexist,i=1;

  do

  {

    cexist=nextcw(cw,n);

    if(cexist)

      pcodewords[i]=NodeConstruct(cexist,n);
    ++i;
  }while(cexist);

 
  //printing the codewords for checking
  for(int i=0;i<combination(n,w);i++)

  {
    int *p=GetCodeWord(pcodewords[i]);

    for(int j=0;j<n;j++)

      printf("%d", *(p+j));

    printf("\n");

  }
}

---

The following are the node.h and functions.h header files. if needed i can come up with their implementation

Code:

---

#ifndef NODE_H

#define NODE_H

typedef struct NodeStruct Node;

Node* NodeConstruct( int *cw,int n);

void NodeDestruct(Node *);

int* GetCodeWord(Node *);
int GetCsize(Node *n);
void SetCsize(Node *n, int a);

int Getd(Node *, Node *,int);

void SetChildNodes(Node *, Node **, int);
Node **GetChildNodes(Node *n);

#endif


#ifndef FUNCTIONS_H
#define FUNCTIONS_H

int *nextcw(int cw[], int n);
int combination(int n, int w);

#endif

---

I did check for different values of n and w. I couldn't get the same answer all the time. eg. for n=6 and w=3. I am waiting for a solution.

Here's how you allocate pcodewords.

Code:

---

  Node **pcodewords;
  pcodewords=malloc(sizeof *pcodewords);
  pcodewords[0]=NULL;

---

Okay, so after this pcodewords is an array of Node*s with one element, and that element is set to NULL. Fair enough so far.

But then you do this:

Code:

---

  for(int i=0;i<combination(n,w);i++)

  {
    int *p=GetCodeWord(pcodewords[i]);
    // ...

---

In other words, you read from pcodewords[i]. But that will only work if pcodewords[i] exists, which it won't unless i==0! So I think that instead of allocating one element, you meant to use something like this:

Code:

---

  Node **pcodewords;
  pcodewords=malloc(sizeof *pcodewords * combination(n, w));

---

That would give you enough pcodewords[i]'s to prevent seg faults. But then there's still the issue of pcodewords[i] not being initialized! You only do this in the do-while loop after this for loop. I suspect this for loop was debugging code. So get rid of it.

So . . . yeah. If you allocated enough memory to begin with, and don't access pcodewords[i] until it's been initialized, then you should be all right. My modified code is as follows, with modifications in colour.

Code:

---

#include<stdlib.h>


#include "node.h"
#include "functions.h"



int main()

{

  int n,d,w;

//inputs from user

  printf("Enter n,d,and w:\nn=");

  scanf("%d",&n);

  printf("d=");

  scanf("%d",&d);

  printf("w=");

  scanf("%d",&w);

  printf("n=%d, d=%d, w=%d\n",n,d,w);

//generate the codewords
  Node **pcodewords;
  pcodewords=malloc(sizeof *pcodewords * combinations(n,w));
  pcodewords[0]=NULL;

  int cw[n],cw0[n];

  //The initial codeword is 00000....111111

  for(int i=0;i<n-w;++i)

    cw[i]=cw0[i]=0;

  for(int i=n-w;i<n;++i)

    cw[i]=cw0[i]=1;

  pcodewords[0]=NodeConstruct(cw,n);

 //printing the codewords for checking
  /*for(int i=0;i<combination(n,w);i++)

  {
    int *p=GetCodeWord(pcodewords[i]);

    for(int j=0;j<n;j++)

      printf("%d", *(p+j));

    printf("\n");

  }*/
  int *cexist,i=1;

  do

  {

    cexist=nextcw(cw,n);

    if(cexist)

      pcodewords[i]=NodeConstruct(cexist,n);
    ++i;
  }while(cexist);

 
  //printing the codewords for checking
  for(int i=0;i<combination(n,w);i++)

  {
    int *p=GetCodeWord(pcodewords[i]);

    for(int j=0;j<n;j++)

      printf("%d", *(p+j));

    printf("\n");

  }
}

---

I haven't seen the rest of your code, but you should be careful about GetCodeWord's return value. If it's an ordinary array, then you'll be accessing invalid memory. If it's a static array, good for you. If it's dynamically allocated, you might consider freeing it at some point.

Hello DWK, You really got my problem and gave me a proper solution. It means a lot for me . Anyway, 10q and Long life for you and yours!

BTW, could you suggest me an algorithm to use to implement the following problem with c:

eg. For n=6, number of ones(w)=3, the following binary words can be obtained in lexicographic order
000111
001011
001101
001110
010011
010101
010110
011001
011010
011100
100011
100101
100110
101001
101010
101100
110001
110010
110100
111000

What I want to do is to find all the possible solutions ,with maximum number of words, fulfilling
a minimum distance condition, eg d=3.

I am really stacked so plz forward me your suggestion asa possible 10q!

First note that the idea I've presented below assumes that you don't have to store each number as you generate it. It just prints the solutions as they are found. If you do need to store the generated bitstrings, it's easy enough to pass a pointer to the stack of words found so far to the function along with the number of words you've added.

Personally, I'd be inclined to try a recursive solution to this problem. Here's some code which generates all the binary numbers of length 6. Note that the numbers will always be in lexicographical order, since it recurses first on '0' and then on '1'.

Code:

---

#include <stdio.h>

void binary_numbers(char *buffer, int digit, int length) {
    if(digit + 1 >= length) {
        buffer[digit] = 0;  /* add terminating NULL character to the string */
       
        printf("%s\n", buffer);
        return;
    }
   
    buffer[digit] = '0';
    binary_numbers(buffer, digit + 1, length);
   
    buffer[digit] = '1';
    binary_numbers(buffer, digit + 1, length);
}

int main() {
    char buffer[6] = {0};
    binary_numbers(buffer, 0, sizeof(buffer)/sizeof(*buffer));
   
    return 0;
}

---

What the code does is basically add onto the end of the buffer, adding zeros and ones in sequence. It's reasonably efficient; it does require on the order of 2^n recursive calls, but the recursive depth will never be more than n (or n+1? whatever), since it recurses for every letter in the buffer.

Anyway, you can easily adopt that code so that it only prints those numbers with three 1's in them, for example; perhaps by counting the number of ones you print. That's pretty inefficient, though, if the number of digits is large and the number of 1's is small.

So a better idea is to only generate numbers with the correct number of 1's. The code would operate pretty much the same as before, except that you'd have to detect if you were getting near the end and hadn't added enough 1's yet. In other words, if you need N more 1's and there are only M characters left, if N == M then you'd better use a 1 and not a 0. :)

If you don't like the recursive solution . . . well, like with all recursive functions, you could write an iterative (loop-based) solution to this problem too. I think it would be a lot more complicated, though. Why don't you see if you can figure out the recursive version . . . .

Or you could use a combination-generating algorithm to generate all the possible combos of 3 out of 6 (123, 124, 125, 126, 134, .....) and use that to place the 0's in your string.

Hello DWK, I really understand and enjoy the recursive implemmentation version you did above. But I have already generated and stored the codewords( eg. 000111 is a codeword) for any value of n and w using the iterative method. My problem is the following:

Having all of the codewords( eg. for n=6 and w=3, the above list is the answer), I want to generate and store all possible maximum combination that fullfill hamming distance codition(eg. d>3). Hamming distance between two codewords is the number of coordinates they differ each other(eg 000111 &101010 give d=4). I have already implemented hamming distance checking function for two codewords.

For instance, for the above example if d>3, 000111,011001,101010 and 110100 are one possible solution. 000111,011010,110001,and 101100 are another solution. we can have a number of such solutions with size 4 meeting d>3 criteria. I want to generate and store all of them. Hope I am clear now.

10q for your help!

Oh, I see. Sorry, I misunderstood you. I think I need more clarification, however: if you are looking for solutions with size 4, and there are 5 codewords which meet the d>3 criteria, does that mean that this solution is not a size 4 solution, or does it mean that you can get 5 size 4 solutions out of this size 5 solution by taking subsets of size 4? In other words, are you looking for solutions with a maximal size of 4 or solutions with a size of exactly 4?

I can't think of an easy way to solve this problem besides the reasonably obvious solution of checking every codeword against every other codeword. For example: pick the first word and compare it against every other word. If d>3, increment the "matching" count for both the first word and also the word it matched. At the end, if the count is >= 4 (or == 4, depending on your problem), then you've found a solution set. You'd probably also want to record the matching words as you find them so that you can print them in an efficient manner.

Something like that should work. Unless I'm overlooking something.

Anyway, this is all pretty complicated; is this actually what your program is trying to do, or is this a mean towards an end?

Quote:

---

I have already implemented hamming distance checking function for two codewords.

---

If you stored those numbers in ints instead of in strings you could use the C XOR operator (^) combined with left shift and AND to do this checking very quickly. Just a thought.

Quote:

---

Or you could use a combination-generating algorithm to generate all the possible combos of 3 out of 6 (123, 124, 125, 126, 134, .....) and use that to place the 0's in your string.

---

Yeah, that would probably be an even better idea . . . :)

Nice to have you to discuss this way. Let me answer your questions and explain more about the problem.

I said size 4 since i know that 4 is the maximum possible number of codewords for the given parameters in the above example(n=6,d>=3,w=3). You can't get 5 or more. So you can assume that the maximum possible size for any parameters set is known.And what i need is those with only with this maximum size( 4 for instance in the above case). But we can have a lot of combination with this size. My point is to get all of the combination on hand. This point is not the end of my project. There will be further processing of the solutions. But it is a crucial point.

10Q and looking forward to see your suggestion of an algorithm.