How to create an empty array in C (without structure)

Hello,

If code_char.code were an int *, one way to handle it would be to represent the empty array by NULL. Then, when you need to access code_char.code, you start by checking if this address is not NULL. If it is and you want to correct the value of code_char.code, you just need to perform a dynamic allocation.

In your case, the fact that code_char is an int[256] means that, no matter what, this array is a memory block and its actual size is 256*sizeof(int). If you want an effective size notion, you need to store it separately. In your code, that's the role of code_char.lg: since this value stores the effective size of code_char.code, why not simply set it to 0 in the case where the code corresponds to the empty string? Because in practice, regardless of the effective length of code_char.code, since it is an int[256], it will always result in a 256 int array in memory.

Regarding the initial question, as Pierrot mentioned in his messages #18, there is no concept of an empty array in C, unlike C++ or Python. I might even go further, there really isn't any concept of a native array in the C language (unless you define your own structure). There is only a notion of a memory block. Pointer algebra means we can index a block according to the size of the pointed type, and that defines the operator [ ]. Because in reality:

tab[i] == *(tab + i)

... where tab corresponds to the address of the block. The offset of i "elements" depends on the pointed type. For example, if tab is of type int *, then the pointed type is int, and thus the i-th "element" is i * sizeof(int) bytes after the address tab, as highlighted by the following program:

#include <stdio.h> #include <stdlib.h> int main() { int * tab = malloc(10 * sizeof(int)); size_t i = 1; printf("tab = %p i = %zu\n", tab, i); printf("tab[i] = %p\n", &tab[i]); printf("tab + i = %p\n", tab + i); printf("((int) tab) + i * sizeof(int) = %p\n", ((long) tab) + i * sizeof(int)); free(tab); return 0; }

 (mando@silk) (~) $ gcc toto.c && ./a.out tab = 0x55de759dc2a0 i = 1 tab[i] = 0x55de759dc2a4 tab + i = 0x55de759dc2a4 ((int) tab) + i * sizeof(int) = 0x55de759dc2a4

We thus understand that the operator [ ] is merely a writing trick that juggles with pointers behind the scenes, and that there is no proper concept of an array.

Good luck

Could you explain what you want to do with it? Because I don't see the point at first glance.
And "empty" means that its length is 0, or that you don't want to put anything in it from the start?

It is possible to do  int tab[0];  but it is not ISO.

Yes, I want its size to be equal to 0.

Nothing when leaving, right.

How are you going to add elements to it?
It's not like Python where you can do appends, or C++ where you can use push_back.

I just tested it, you can do malloc of size 0, even if you have to do realloc afterwards.

But it's a pretty dubious way of doing things...

I will explain the context otherwise you won’t understand. I have to do an exercise on Huffman trees (I don’t know if you know about them)

I’ve been asked to write a function that allows me to get the code for each character and its length

Example:

The encoding will be:

• C: 000
• B: 001
• D: 1100
• ...

I have a function ConstruireCode whose prototype is:

void ConstruireCode(Arbre huff) { } typedef unsigned char Element; struct cellule { Element etiq; struct cellule *fd; struct cellule *fg; }; typedef struct cellule *Arbre; struct code_char { int lg; int code[256]; /* only contains 0 or 1 */ }; struct code_char tab;

• tab[i] contains the code for the character with ASCII code i
• tab[i].lg contains the length of the code (example for B: code length 3)
• tab[i].code contains the code for the character (like in my example B=001)

Why did I ask about the empty array?

To calculate the code for a letter, we need to traverse from the root to the leaf. The left side of the tree only has 0s and the right side only has 1s.

I want to write the function recursively, so I need a base case, which gives something like this:

void ConstruireCode(Arbre huff) { if Estfeuille(huff) tab[i].code=creer_un_tableau_vide else //ConstruireCode(Filgauche(huff)) //ConstruireCode(Fildroit(huff)) }

In my solution, I haven’t yet found a way to put only 0s to the left and only 1s to the right.

I therefore need to create an empty array to handle my base case.

If a tree is reduced to a leaf (1 node), it should not have a code, so I need an empty array to indicate that there is nothing.

Example in Python:

from __future__ import annotations from typing import Dict from heapq import heappush, heappop class Node(): """ Node of the Huffman tree. """ def __init__(self: Node, value: int, letter: str = "", left: Node = None, right: Node = None) -> None: self.value = value self.letter = letter self.left = left self.right = right def __lt__(self, n: Node): """ Comparison of two nodes = comparison of values """ return self.value < n.value def create_huffman_codes(a: Node) -> Dict[str, str]: """ Given a Huffman tree, returns a dictionary where keys are binary strings and values are corresponding characters. Wrapper function for the function huffman_codes_traversal. """ dic = {} huffman_codes_traversal(a, dic, "") return dic def huffman_codes_traversal(a: Node, dic: Dict[str, str], code: str) -> None: if is_leaf(a): dic[code] = a.letter else: huffman_codes_traversal(a.left, dic, code + "0") huffman_codes_traversal(a.right, dic, code + "1")

In this Python version, nothing is represented by "". In the given C version, the structure code_char contains an array code with the character's code. So by analogy, I think I need an empty array instead.

In the Python version, nothing is symbolized by " " and given the structure that I have, code-char contains an array code with the character code, so by analogy here I think I should have an empty array.

I already did a Huffman. I had made a frequency table 256 long.
Each element was a node and I accumulated the frequency there.

I only kept the elements with a non-zero frequency and sorted them in descending order.
I think I built the tree iteratively, but it can probably be done recursively.
It seems to me that I built a code table with the length of each, this time recursively.

Yes, that's right, my exercise asks me to create the table of codes

Example :

Huffman[97] = a ​​​​​​​Huffman[97].code = [0011] Huffman[97].lg = 4

So, is my idea of creating an empty array a good one or not?

If so, how do I create one in C?

If you read the Python version (see #6) you will understand what I want to do.

As I told you, I created my code table from the frequency table. This table was made up of nodes.
So, in the end, I ended up with a binary tree with a root.
It is from this point that I believe you will create your code table recursively.
I can still post my code.
But it won't be colored because I am blind and I use my computer with a screen reader.
It doesn't give me access to the options bar.

To answer your question, it's not a good idea to start with an empty table.

I don't know if it will work for mine, but in any case, I also have a frequency table.

For example, if I have: bal alh

tab[97] = 2 // a tab[98] = 1 // b ...

I also have a function init_huffman that returns a priority queue whose elements are nodes with their frequency as priority. Do you think it looks like your frequency table?

But I'm still curious; I would really like to see your code.

Here is my code:

// Huffman Tree. #include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct Node Node; struct Node {     Node *left;     Node *right;     int occur;     char code; }; typedef struct Bits Bits; struct Bits {     unsigned char number;     unsigned char bits; }; void *getArea(char *name, int size) {     void *area = malloc(size);     if(area) return area;     perror(name);     printf("Required: %d\n", size);     exit(EXIT_FAILURE); } Node *getNode(char symbol) {     Node *node = getArea("getNode", sizeof(Node));     node->left = NULL;     node->right = NULL;     node->occur = 0;     node->code = symbol;     return node; } void setTree(Node *node, Bits convert[], Bits bits, int level) {     if(node->left) {   // not a leaf     bits.number++;     setTree(node->right, convert, bits, level+1);     bits.bits |= 1<<level;     setTree(node->left, convert, bits, level+1); } else {     convert[node->code] = bits; } } int compare(const void *freq1, const void *freq2) {     int cmp =(*((Node **)freq2))->occur - (*((Node **)freq1))->occur;     if(cmp != 0) return cmp;     return ( *((Node **)freq1))->code - (*((Node **)freq2))->code; } void freeTree(Node *node) {     if(node->left) freeTree(node->left);     if(node->right) freeTree(node->right);     free(node); } int main(void) {     Node **frequency = getArea("frequency", sizeof(Node *) * 256);     unsigned char text[] = "this is an example of a huffman tree";     for(int i=0; i < 256; i++) frequency[i] = NULL;     // Increase occurrences.     for(int i=0; text[i]; i++) {         char code = text[i];         if(frequency[code] == NULL) frequency[code] = getNode(code);         frequency[code]->occur++;     }     // Keep only if there is at least one occurrence.     int count = 0;     for(int i=0; i < 256; i++)         if(frequency[i])             frequency[count++] = frequency[i];     // Sort frequencies in descending order.     qsort(frequency, count, sizeof(Node **), compare);     // Build the tree from the nodes.     Node *newNode;     int rest = count;     while(rest > 1) {         newNode = getNode('\0');         newNode->left = frequency[rest-2];         newNode->right = frequency[rest-1];         newNode->occur = frequency[rest-2]->occur + frequency[rest-1]->occur;         rest -= 2;         // Move the node up in the array         int i;         for(i=rest; i>0 && newNode->occur > frequency[i-1]->occur; i--) frequency[i] = frequency[i-1];         frequency[i] = newNode;         rest++;     }     free(frequency);     Bits *convert = getArea("convert", sizeof(Bits) * 256);     Bits bits;     bits.number=0;     bits.bits=0;     for(int i=0; i<256; i++) convert[i] = bits;     setTree(newNode, convert, bits, 0);     unsigned char *memory = getArea("memory", strlen(text)*8);   // === review     int in =  0;     // traverse the text and convert it     for(int i=0; text[i]; i++) {         char code =text[i];         for(int s=0; s < convert[code].number; s++) {             memory[in++] = (convert[code].bits >> s) & 1;         }     }     free(convert);     // decode the file     printf("%d bits\n", in);     int out = 0;     int acc = 0;     Node *node = newNode;     while(out < in) {         if(node->left == NULL) {             memory[acc++] = node->code;             node = newNode;         }         if(memory[out++])         node = node->left;         else         node = node->right;     }     memory[acc++]=node->code;     memory[acc]='\0';     // display the result     printf("\n%s\n", memory);     free(memory);     freeTree(newNode);     return 0; }

I read everything, but I don't see from what point you calculate the character code.

I do it in the setTree function with the convert array. The setTree function is recursive.

Alright, thanks. I've looked into it, and I think it's very different from the signature of my functions and my structures, but thank you.

Let's go back to my initial problem. I just want to know how to create an empty array.

Example:

struct array{    int *arr;    int size; } void create_empty_array(){    array a; a.size = 0; }

How can I do it without using struct array ??

What you want to do without structure is impossible in C. In C++, I would use std::vector
and you know how to do it in Python.
In your example, you are not returning the structure to the calling function.

Okay, I understand better, thank you.