I would like to save an array of linked lists in a binary file, but I don't know how to assign the dynamic memory due to the varying lengths of linked lists for each bucket.
And to access a random position containing the whole linked list without reading the whole file, like a kind of index file? Some tip?
CodePudding user response：
I will make these assumptions:
- Every (non-“null”) element of each list is an
int - There are
MAX_INTor fewer elements in each list
Make your file (remember to open in binary mode) have the following structure:
- Output an
intcontaining the number of items in the first list - Output each
intin that list - Repeat for each subsequent list
This scheme has two drawbacks:
- each list has a (large) maximum number of elements
- you must traverse each list twice to save (first to learn the length, again to save each item)
It has the advantage of being very quick and direct to load.
CodePudding user response：
here is a simple code,you can use fwrite to file and fread from file as you wish,but you must consider the big-endian or little-endian
#include <stdio.h>
#include <stdlib.h>
typedef struct _Node {
struct _Node *next;
int val;
} Node;
void serialize(Node arr[], int size[], int len) {
FILE *f = fopen("serialize.bin", "wb");
//write arr len
fwrite(&len, sizeof(int), 1, f);
//write array
for (int i = 0; i < len; i) {
//write linklist len
fwrite(&size[i], sizeof(int), 1, f);
Node *tmp = &arr[i];
while (tmp) {
fwrite(&tmp->val, sizeof(int), 1, f);
tmp = tmp->next;
}
}
fclose(f);
}
Node *deserialize() {
FILE *f = fopen("serialize.bin", "rb");
int len;
fread(&len, sizeof(int), 1, f);
Node *ret = malloc(len * sizeof(Node));
for (int i = 0; i < len; i) {
int linklen;
int val;
Node *tmp = &ret[i];
fread(&linklen, sizeof(int), 1, f);
fread(&val, sizeof(int), 1, f);
ret[i].val = val;
ret[i].next = NULL;
linklen--;
while (linklen--) {
fread(&val, sizeof(int), 1, f);
tmp->next = malloc(sizeof(Node));
tmp->next->next = NULL;
tmp->next->val = val;
tmp = tmp->next;
}
}
return ret;
}
int main() {
#define ARRAY_LEN 3
Node arr[ARRAY_LEN];
int size[ARRAY_LEN];
arr[0].next = malloc(sizeof(Node));
arr[0].val = 1;
arr[0].next->next = malloc(sizeof(Node));
arr[0].next->val = 2;
arr[0].next->next->next = NULL;
arr[0].next->next->val = 3;
size[0] = 3;
arr[1].next = malloc(sizeof(Node));
arr[1].val = 11;
arr[1].next->next = NULL;
arr[1].next->val = 22;
size[1] = 2;
arr[2].next = NULL;
arr[2].val = 33;
size[2] = 1;
serialize(arr, size, ARRAY_LEN);
Node *ret = deserialize();
//TODO free memory
return 0; //end of code
}
CodePudding user response：
The solution is not very complicated if there is a value that is never stored as an element in your linked list-- in that case, you can treat the linked list like a glorified null-terminated string, where whatever value that cannot exist in the linked list acts as the terminator. If you don't have such luxury, then you can write an extra byte with each value that determines if the value is the last one or not. Here's an implementation of the first possible solution, though it can be easily modified to work in the case of the second:
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#define NODE_V_SIZE sizeof(int)
const int list_end = -1;
typedef struct Node {
int value;
struct Node *prev, *next;
} Node;
void free_nodes(Node *head) {
while (head) {
Node *to_free = head;
head = head->next;
free(to_free);
}
}
Node* new_node(int value) {
Node *node = malloc(sizeof(Node));
if (!node) {
return NULL;
}
node->prev = NULL;
node->next = NULL;
node->value = value;
return node;
}
int write_nodes(int fd, Node *head) {
while (head) {
if (write(fd, &head->value, NODE_V_SIZE) != NODE_V_SIZE) {
return -1;
}
head = head->next;
}
if (write(fd, &list_end, NODE_V_SIZE) != NODE_V_SIZE) {
return -1;
}
return 0;
}
Node* read_nodes(int fd) {
Node *head = NULL;
Node *cur = NULL;
int in;
while (1) {
if (read(fd, &in, NODE_V_SIZE) != NODE_V_SIZE) {
free_nodes(head);
return NULL;
}
if (in == list_end) {
return head;
}
if (cur) {
cur->next = new_node(in);
if (!cur->next) {
free_nodes(head);
return NULL;
}
cur->next->prev = cur;
cur = cur->next;
} else {
cur = new_node(in);
if (!cur) {
return NULL;
}
head = cur;
}
}
}
Node* new_random_list(int modifier) {
Node *head = new_node(0);
if (!head) {
printf("out of memory\n");
exit(1);
}
Node *cur = head;
for (int i = 0; i < 10; i ) {
cur->next = new_node((i modifier)*3);
if (!cur->next) {
free_nodes(head);
printf("out of memory\n");
exit(1);
}
cur = cur->next;
}
return head;
}
int main() {
#define NHEADS 10
// open file
int fd = open("dat", O_RDWR);
if (fd == -1) {
printf("failed to open file\n");
exit(1);
}
// make NHEADS number of 10 nodes linked together and write them to fd
for (int i = 0; i < NHEADS; i ) {
Node *head = new_random_list(i);
if (write_nodes(fd, head)) {
printf("failed to serialize nodes\n");
exit(1);
}
free_nodes(head);
}
// read from fd to populate got then print it, repeat NHEADS times
lseek(fd, 0, SEEK_SET);
for (int i = 0; i < NHEADS; i ) {
Node *got = read_nodes(fd);
if (!got) {
printf("failed to deserialize nodes\n");
exit(1);
}
Node *head = got;
while (got) {
printf("%d\n", got->value);
got = got->next;
}
printf("\n");
free_nodes(head);
}
close(fd);
return 0;
}