我想在二進制檔案中保存一個鏈表陣列，但由于每個桶的鏈表長度不同，我不知道如何分配動態記憶體。
并且訪問包含整個鏈表的隨機位置而不讀取整個檔案，就像一種索引檔案？一些小費？
uj5u.com熱心網友回復：
我會做出這些假設：
- 每個串列的每個（非“null”）元素都是一個
int - 每個串列中有
MAX_INT或更少的元素
使您的檔案（記得以二進制模式打開）具有以下結構：
- 輸出
int包含第一個串列中專案數的 - 輸出
int該串列中的每個 - 對每個后續串列重復
這種方案有兩個缺點：
- 每個串列都有一個（大）最大元素數
- 您必須遍歷每個串列兩次才能保存（首先了解長度，再次保存每個專案）
它具有非常快速和直接加載的優點。
uj5u.com熱心網友回復：
這是一個簡單的代碼，您可以根據需要使用 fwrite 到檔案和從檔案中讀取，但您必須考慮big-endianorlittle-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
}
uj5u.com熱心網友回復：
如果有一個值永遠不會作為元素存盤在您的鏈表中，則解決方案不是很復雜——在這種情況下，您可以將鏈表視為一個美化的以空結尾的字串，其中任何值都不能存在于鏈表充當終結者。如果您沒有這種奢侈，那么您可以為每個值寫入一個額外的位元組，以確定該值是否是最后一個。這是第一個可能的解決方案的實作，盡管它可以很容易地修改為在第二種情況下作業：
#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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/464190.html