Dynamic Array Of Structures - Often Changing - HOW?

Hi All,

I need to code processing of files in C - That part is easy.
The content of these files is linked, so I need to hold the record data that I read from one file until I get some more information relating to that record, or get an end record for it, which will be in another, later, file.

I was thinking dynamic array of structure, which works in principle, but I'm not sure about removing only some of the data - I don't know that it's possible?

I want to hold the information in memory, appending new information, and only get rid of the allocated memory for a particular instance of my data once I receive an end record for it, write it away and free memory, retaining structures for all the other records.

I guess the easiest way to explain it is to say it's like a restaurant order (in processing, but the data is a structure).

table 1 orders some drinks
table 3 orders some drinks
table 2 orders some drinks
table 1 orders starters
table 3 orders mains
table 1 orders mains
table 2 orders starters
table 2 orders mains
table 3 orders desert
table 3 requests bill **
table 2 orders desert
table 1 orders coffee
table 2 requests bill **
table 1 requests bill **

Requesting bill signifies the end of keeping information on that table, so output and get rid of anything to do with that particular table.

Assume my restaurant is big - It has 100000 tables !!!!

Any help on what is best to use would be appreciated.

Many Thanks

You need something with fast insertion/deletion and fast lookup (ordered). Perhaps an AVL tree?

How about an array of pointers to your order struct using the table number (minus 1 or whatever) for the index. You're looking at the size of a pointer in your environment times the number of tables (probably something like 400,000 bytes) just for accessing orders but the lookup would be extremely fast (O(1)), and if most of the tables have an order most of the time, you're really not wasting much memory. And hey...it's 400k, right?

Thanks for the replies.
Do I really need to do a tree, since I know the indexed value is there any alternative to give me direct access to that particular item in the list. In essence if I can have something like a database where I can update certain fields in the structure based on the structure key being known ?

Thanks

a good way to approach this type of problem is to start simple, with a data structure that just uses a linear search to find the matching key. yes, not efficient but easy to program with just an array big enough to hold all the entries. . then if you want more direct access you have a choice of data structures and algorithms. binary search of a sorted array, a tree, a hash table. they each have tradeoffs. binary search and sort are supported by the C standard library so its a good next step.

Here study how this works... it'll probably give you some ideas...
And... it's persistent data, so you can even reboot without losing the info.

Code:

---

//random access file demo
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <ctype.h>
#include <string.h>

#define FNAME "random.dat"

// test data struct
struct t_Record
  { int number;
    char word[16]; }
  Record;



///////////////////////////////////////////////////////
// Random Access File Handlers
//

// open or create the file
FILE *FileOpen(char* Filename)
  { FILE* pFile;
    pFile = fopen(Filename,"rb+");
    if (!pFile)
      pFile = fopen(Filename,"wb+");
    return pFile; }


// Write a record to the file
int WriteRecord(FILE *File, int RecNum)
  { if( fseek(File, RecNum * sizeof(Record), SEEK_SET) == 0 )
      if ( fwrite(&Record,sizeof(Record),1,File) )
        return 1;
    return 0; }


// read a record from the file
int ReadRecord(FILE *File, int RecNum)
  { if( fseek(File, RecNum * sizeof(Record), SEEK_SET) == 0 )
      if ( fread(&Record,sizeof(Record),1,File) )
        return 1;
    return 0; }


int AddRecord(FILE *File)
  { fseek(File,0,SEEK_END);
    fwrite(&Record,sizeof(Record),1,File);
    return (ftell(File) / sizeof(Record)) - 1; }



//////////////////////////////////////////////////////////////
// View a Record
//

int ViewRecord (FILE *File, int RecNum)
  { if (! ReadRecord(File,RecNum))
      { printf("Invalid record\n");
        return -1; }
    printf("-----\n");
    printf("Record        : %d\n",RecNum);
    printf("Number Value  : %d\n",Record.number);
    printf("Word Value    : %s\n",Record.word);
    printf("-----\n"); 
    return RecNum; }



//////////////////////////////////////////////////////////////
// Add a new record
//

int AddNewData(FILE *File)
  { memset(&Record,0,sizeof(Record));
    printf("\nEnter a number : ");
    scanf("%d", &Record.number);
    printf("Enter a word : ");
    scanf(" %s",Record.word);
    return AddRecord(File); }



//////////////////////////////////////////////////////////////
// Edit a record
//

int EditRecord(FILE *File, int RecNum)
  { if (! ReadRecord(File,RecNum))
      { printf("Invalid record\n"); 
        return -1; }
    printf("\n-----\n");
    printf("Record        : %d\n",RecNum);
    printf("Number Value  : %d\n",Record.number);
    printf("Word Value    : %s\n",Record.word);
    printf("-----\n"); 
   
    do
      { while(getchar() != '\n');
        printf("Change Values: Number, Word or Save (N, W or S) ? ");
        switch (toupper(getchar()))
          { case 'N' :
              printf("\nEnter new number : ");
              scanf("%d",&Record.number);
              break;
            case 'W' :
              printf("Enter new word : ");
              scanf(" %15s", Record.word);
              break;
            case 'S' :
              if (WriteRecord(File,RecNum))
                printf("\nRecord #%d updated\n",RecNum);
              return RecNum; } }
    while(1);
    return -1; }


////////////////////////////////////////////////////////////////
// List records
//

void ListRecords(FILE *File )
  { int i = 0;
    printf("\nRecord    Number\tWord\n\n");
    while (ReadRecord(File,i))
      { printf("%3d%16d\t%s\n",i,Record.number,Record.word);
        i++; }
    printf("\n\n"); }



////////////////////////////////////////////////////////
// this is for demonstration purposes only
// you would not do this in a real program
void InitFile(FILE* File)
 { int x, y;
  memset(&Record,sizeof(Record),0);
  for (x = 0; x < 10; x++)
      { Record.number = rand();
        for (y = 0; y < ((Record.number % 15) + 1); y++)
          Record.word[y] = (rand() % 26) + 'a';
        Record.word[y] = 0;
        if (! WriteRecord(File,x))
          printf("Oh drat!");  } }
 


//////////////////////////////////////////////////////////
// program mains
//
int main (void)
  { int Rec = 0; // record number
    FILE *File;

    srand(time(NULL));

    File = FileOpen(FNAME);
    if (!File)
      { printf("Curses foiled again!\n\n");
        exit(-1); }

    printf("Random Access File Demonstration\n\n");
 
    do
      { printf("Menu : Dummy, Add, Edit, View, List, Quit (D, A, E, V, L or Q) : ");
        switch(toupper(getchar()))
          { case 'D' :
              printf("Creating dummy file of 10 entries\n");
              InitFile(File);
              break;
            case 'A' :
              Rec = AddNewData(File);
              printf("Record #%d Added\n\n", Rec);
              break;             
            case 'E' :
              printf("\nRecord number (-1 Cancels): ");
              scanf("%d",&Rec);
              if (Rec > -1)
                EditRecord(File,Rec);
              break;
            case 'V' :
              printf("\nRecord number (-1 Cancels): ");
              scanf("%d",&Rec);
              if (Rec > -1)
                ViewRecord(File,Rec);
              break;
            case 'L' :
              ListRecords(File);
              break;
            case 'Q' :
              fclose(File);
              return 0; }
             
        while(getchar() != '\n'); }
    while (1);
    return 0; }

---