Thread: 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?

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; }