Skip to content

Instantly share code, notes, and snippets.

@ecnelises

ecnelises/StrangeLinkedListForInt.cc

Created October 10, 2018 05:25
Show Gist options
  • Save ecnelises/144c40d67279b2083dac3e96c762157e to your computer and use it in GitHub Desktop.
Save ecnelises/144c40d67279b2083dac3e96c762157e to your computer and use it in GitHub Desktop.
Download ZIP
一个可以用磁盘序列化的静态链表类
Raw
StrangeLinkedListForInt.cc
#include <iostream>
#include <vector>
#include <tuple>
#include <cstdio>
using namespace std;
// StrangeLinkedListForInt
// 一个可以用磁盘序列化的静态链表类
class StrangeLinkedListForInt {
public:
// 迭代器类
class iterator {
friend class StrangeLinkedListForInt;
public:
// 判断相等关系的函数
bool operator == (const iterator& it) {
return it.i == i && it.list == list;
}
bool operator != (const iterator& it) {
return it.i != i || it.list != list;
}
private:
void set_index(int index) {
i = index;
}
// 表示此迭代器指向的链表，必须要相等才可以起作用
StrangeLinkedListForInt* list;
int i;
};
private:
// 表示每个节点的结构
// 此链表的数据结构表示是静态的
// prev 表示上一个节点在 data 中的下标，next 表示下一个
// used 用以检查此节点是否已被使用
struct node {
int prev;
int next;
int value;
bool used;
};
private:
// 默认最大支持 300 元素
static const int max_size = 300;
// 额外留下头和尾表示特殊元信息
node data[max_size + 2];
// 记录链表长度
int length;
public:
StrangeLinkedListForInt() : length(0) {
for (int i = 1; i <= max_size; ++i) {
data[i].next = i + 1;
data[i].prev = -1;
data[i].used = false;
}
data[0].prev = -1; // 第一个元素的 prev 表示链表头
data[0].next = 1; // 第一个元素的 next 表示第一个可用节点
data[max_size + 1].prev = -1; // 最后一个元素的 prev 表示链表尾
}
// 在链表尾部插入
void insert_back(int elem) {
int pos = fake_alloc();
if (pos == -1) return;
if (length++ == 0) {
data[pos].prev = -1;
set_head(pos);
} else {
data[pos].prev = get_tail();
data[get_tail()].next = pos;
}
set_tail(pos);
data[pos].next = -1;
data[pos].value = elem;
}
// 在链表头部插入
void insert_front(int elem) {
int pos = fake_alloc();
if (pos == -1) return;
if (length++ == 0) {
data[pos].next = -1;
set_tail(pos);
} else {
data[pos].next = get_head();
data[get_head()].prev = pos;
}
set_head(pos);
data[pos].prev = -1;
data[pos].value = elem;
}
// 在迭代器位置后面插入
void insert_after(iterator it, int elem) {
if (!iterator_valid(it) || length == max_size) return;
if (get_tail() == it.i) {
insert_back(elem);
} else {
int next = data[it.i].next;
int new_item = fake_alloc();
if (new_item == -1) return;
data[new_item].value = elem;
data[it.i].next = new_item;
data[new_item].prev = it.i;
data[new_item].next = next;
data[next].prev = new_item;
++length;
}
}
// 移除头部元素
// 如果仅有一个元素，删除后链表将变为空状态
void remove_front(void) {
if (length == 0) return;
else if (length == 1) {
fake_free(get_head());
set_tail(-1);
set_head(-1);
} else {
int old_head = get_head();
int new_head = data[get_head()].next;
set_head(new_head);
data[new_head].prev = -1;
fake_free(old_head);
}
--length;
}
// 移除尾部元素
// 如果仅有一个元素，删除后链表将变为空状态
void remove_back() {
if (length == 0) return;
else if (length == 1) {
fake_free(get_tail());
set_tail(-1);
set_head(-1);
} else {
int old_tail = get_tail();
int new_tail = data[get_tail()].prev;
set_tail(new_tail);
data[new_tail].next = -1;
fake_free(old_tail);
}
--length;
}
// 移除迭代器位置的元素
// 如果迭代器无效（下标无效或指向的不是本链表），则不起作用
// 如果成功删除，迭代器将会失效
void remove(iterator it) {
if (!iterator_valid(it) || length == 0) return;
if (get_tail() == it.i) {
remove_back();
} else if (get_head() == it.i) {
remove_front();
} else {
int prev = data[it.i].prev;
int next = data[it.i].next;
fake_free(it.i);
data[prev].next = next;
data[next].prev = prev;
--length;
}
}
// 获取迭代器位置的值
// 如果迭代器无效（下标无效或指向的不是本链表），则返回 -1
int get_value(iterator it) {
if (!iterator_valid(it)) {
return -1;
}
return data[it.i].value;
}
// 获取迭代器下一个位置的迭代器
// 如果迭代器无效（下标无效或指向的不是本链表），则返回一个 end
iterator get_next(iterator it) {
if (!iterator_valid(it)) {
it.i = max_size + 1;
} else {
int tmp = data[it.i].next;
if (tmp == -1) {
it.i = max_size + 1;
} else {
it.i = tmp;
}
}
return it;
}
// 返回迭代器上一个位置的迭代器
// 如果迭代器无效（下标无效或指向的不是本链表），则返回一个 end
iterator get_previous(iterator it) {
if (!iterator_valid(it)) {
it.i = max_size + 1;
} else {
int tmp = data[it.i].prev;
if (tmp == -1) {
it.i = 0;
} else {
it.i = tmp;
}
}
return it;
}
// 返回开始位置的迭代器
iterator begin() {
iterator it;
it.list = this;
if (length > 0) {
it.i = get_head();
} else {
it.i = 0;
}
return it;
}
// 返回表示链表结束的迭代器，不指向任何元素
iterator end() {
iterator it;
it.list = this;
it.i = max_size + 1;
return it;
}
private:
// 判断迭代器是否无效
bool iterator_valid(const iterator& it) {
return it.list == this && it.i > 0 && it.i <= max_size && data[it.i].used;
}
// 模拟 malloc
int fake_alloc(void) {
if (length >= max_size) {
return -1;
}
int tmp = data[0].next;
data[0].next = data[data[0].next].next;
data[tmp].used = true;
return tmp;
}
// 模拟 free
void fake_free(int i) {
if (length == 0 || !data[i].used) return;
data[i].next = data[0].next;
data[0].next = i;
}
int get_head(void) {
return data[0].prev;
}
int get_tail(void) {
return data[max_size + 1].prev;
}
void set_head(int i) {
data[0].prev = i;
}
void set_tail(int i) {
data[max_size + 1].prev = i;
}
};
int main(void) {
const char* path = "list.bin";
FILE* fp = fopen(path, "wb+");
StrangeLinkedListForInt list1;
for (int i = 0; i < 5; ++i) {
list1.insert_back(i);
}
fwrite(&list1, 1, sizeof(StrangeLinkedListForInt), fp);
fclose(fp);
fp = fopen(path, "rb");
StrangeLinkedListForInt list2;
fread(&list2, 1, sizeof(StrangeLinkedListForInt), fp);
fclose(fp);
for (auto it = list2.begin(); it != list2.end(); it = list2.get_next(it)) {
cout << list2.get_value(it);
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment