3 Replies - 9220 Views - Last Post: 02 November 2009 - 05:26 AM Rate Topic: -----

#1 morgog  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 27
  • Joined: 23-April 09

How to sort a Binary file - without using an array

Post icon  Posted 30 October 2009 - 04:38 AM

Hi
We have a project that requires us to create a binary files with a struct of:


struct person_type
{
int age;
int id;
char name[20];
};



I have created the binary file(Person.txt).

Part 2 of the project is to read the binary file with a struct of:


struct index_type
{
int id;
int offset;
};



and write the index_type struct to a file(Index.txt)

I have created the 2nd file with the id number of file 1 & the offest for the record in file 1.

The 3rd part of the project is to sort the binary data (Index.txt) WITHOUT USING A READ ARRAY .. and then code any screen inquiries to the Index.txt file as a reference to the Index.txt file.

We are using Visual Studio 2005 for C (not C++).
There are another 4 sections of the assignment, and I should be able to finish the remaining parts, But I am at a loss as to how to sort the Index.txt file (in id order) without using a read array.

Any suggestions would be appreciated.

Cheers

Is This A Good Question/Topic? 0
  • +

Replies To: How to sort a Binary file - without using an array

#2 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5795
  • View blog
  • Posts: 12,628
  • Joined: 16-October 07

Re: How to sort a Binary file - without using an array

Posted 30 October 2009 - 04:49 AM

View Postmorgog, on 30 Oct, 2009 - 05:38 AM, said:

The 3rd part of the project is to sort the binary data (Index.txt) WITHOUT USING A READ ARRAY .. and then code any screen inquiries to the Index.txt file as a reference to the Index.txt file.


Neat.

This is pretty much a random access file exercise. I'd probably use a bubble sort, just because it sounds like the least work; and probably less file IO.

Read the first two records, swap them if you have to, using a seek to backup up. Then read the next record, swap in needed, and so on. You will repeat this process until you've read the file in its entirety and no swaps were done.

If you don't have to do it in place, it's probably easer to write to a scratch file, then read that and write back, and so on.

Sounds like fun. Good luck.
Was This Post Helpful? 1
  • +
  • -

#3 morgog  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 27
  • Joined: 23-April 09

Re: How to sort a Binary file - without using an array

Posted 02 November 2009 - 03:44 AM

Thanks for the advise.
I followed your advise and eventually it worked.

void Sort()
{
	int StructureSize, Idx1, Idx2;

	FILE * binaryFile;
	binaryFile = fopen("Index.txt","rb+");
	index_type Index, IndexTemp;
	StructureSize = sizeof(Index);
	fseek(binaryFile, 0, SEEK_END);
	int fileSize = ftell(binaryFile);
	rewind(binaryFile);


	for (Idx1 = 0; Idx1 < fileSize; Idx1 += StructureSize)
	{
		for (Idx2 = 0; Idx2 < fileSize - StructureSize; Idx2 += StructureSize)
		{
			fread(&Index, StructureSize, 1, binaryFile);
			fread(&IndexTemp, StructureSize, 1, binaryFile);

			if (Index.id > IndexTemp.id)
			{
				fseek(binaryFile, -(StructureSize * 2), SEEK_CUR);
				fwrite(&IndexTemp, StructureSize, 1, binaryFile);
				fwrite(&Index, StructureSize, 1, binaryFile);
				fseek(binaryFile, -StructureSize, SEEK_CUR);
			}
			else
			{
				fseek(binaryFile, -StructureSize, SEEK_CUR);
			}
		}

		rewind(binaryFile);
	}

	fclose(binaryFile);
}



However, I'm still not understanding how I can move the pointer in the (binary)file.
I can move the pointer a line at a time to complete the "bubble sort", but when it comes to moving the pointer to the central record of the (binary)file, nothing seems to work.
The file I'm working from is 40bytes long, with each record 8 bytes.

It's clear to me that I'm doing something fundamentally wrong, but given code above ... Could anyone give me a clue as to how I can advance the pointer to the middle record of the file?

Any help would be appreciated.

Cheers

This post has been edited by morgog: 02 November 2009 - 03:46 AM

Was This Post Helpful? 0
  • +
  • -

#4 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5795
  • View blog
  • Posts: 12,628
  • Joined: 16-October 07

Re: How to sort a Binary file - without using an array

Posted 02 November 2009 - 05:26 AM

View Postmorgog, on 2 Nov, 2009 - 04:44 AM, said:

However, I'm still not understanding how I can move the pointer in the (binary)file.
I can move the pointer a line at a time to complete the "bubble sort", but when it comes to moving the pointer to the central record of the (binary)file, nothing seems to work.


Your code works. In it, you're alway moving back two, so moving inside the file does not seem to be an issue for you. Good job.

If it helps, here is my solution for the problem. Note you can get away with less reads if you remember the last.
#include <stdlib.h>
#include <stdio.h>

#define INDEX_FILE_NAME "index.txt"

typedef struct IndexStruct {
	int id, offset;
} Index;


void addIndex(Index *index) {
	FILE *fp;
	
	if ((fp = fopen(INDEX_FILE_NAME, "ab"))!=NULL) {
		fwrite(index, sizeof(Index), 1, fp);
		fclose(fp);
	}
}

void addIndexData(int id, int offset) {
	Index index = {id, offset};
	addIndex(&index);
}


void showIndex(Index *index) { printf("%d\t%d\n", index->id, index->offset); }

void showFile() {
	FILE *fp;
	
	if ((fp = fopen(INDEX_FILE_NAME, "rb"))!=NULL) {
		size_t itemSize = sizeof(Index);
		Index item;
		fread(&item,1,itemSize, fp);
		while (!feof(fp)) {
			showIndex(&item);
			fread(&item,1,itemSize, fp);
		}
		fclose(fp);
	}
}


void sortFile() {
	FILE *fp;
	
	if ((fp = fopen(INDEX_FILE_NAME, "rb+"))!=NULL) {
		size_t itemSize = sizeof(Index);
		Index data1, data2;
		int flag = 1;
		
		// bubble sort
		while(flag) {
			flag = 0;
			fread(&data1, itemSize, 1, fp);
			fread(&data2, itemSize, 1, fp);
			while (!feof(fp)) {
				if (data2.id < data1.id) {
					fseek(fp, (itemSize * -2), SEEK_CUR);
					fwrite(&data2, itemSize, 1, fp);
					fwrite(&data1, itemSize, 1, fp);
					flag = 1;
				} else {
					data1 = data2;
				}
				fread(&data2, itemSize, 1, fp);
			}
			if (flag) { rewind(fp); }
		}
		fclose(fp);
	}
}



int main() {
	remove(INDEX_FILE_NAME);
	addIndexData(3, 10*sizeof(Index));
	addIndexData(5, 12*sizeof(Index));
	addIndexData(1, 3*sizeof(Index));
	addIndexData(2, 4*sizeof(Index));
	
	printf("Before sort\n");
	showFile();
	
	sortFile();
	printf("After sort\n");
	showFile();
	
	remove(INDEX_FILE_NAME);
	
	return 0;
}



Was This Post Helpful? 1
  • +
  • -

Page 1 of 1