一，静态链表
简介
静态链表使用连续的内存，每个结点记录一个数据和指向下一结点的指针。
可以高效的进行插入删除操作。
是用整形游标代替结点指针的“单链表”。
结构
- 结点类型
struct node{
size_t curser;
int value;
};
- 静态链表类型
链表中储存结点构成的数组
struct StaticList {
node* head;
node* pool;
size_t size;
StaticList();
StaticList(size_t size);
void insert(size_t index, int value);
void del(size_t index);
size_t len() const;
size_t get(size_t index) const;
void append(int value);
void print_a() const;
void print_v() const;
size_t _malloc_list();
};
二，操作
初始化
预留链表头部的两个结点分别命名为head和pool，head和pool分别是两个独立的链表的头节点。
head是已记录数据的结点组成的链表的头节点，而pool用来记录没有数据的。
初始时没有储存数据，head的游标（curser）指向head本身。pool的游标指向下一个空结点（2），以此类推，最后一个空结点指向pool（1）。
构造函数如下：
StaticList::StaticList(){
StaticList(20);
size = 20;
}
StaticList::StaticList(size_t size){
head = (node*)malloc(sizeof(node)*(size+2));
pool = head+1;
head->curser = 0;
head->value = 0;
for(size_t i=1; i <= size+1; i++){
head[i].curser = i+1;
head[i].value = 0;
}
head[size+1].curser = 1;
this->size = size;
}
尾部添加元素
找到head的链表中游标指向的0的结点即最后一个记录数据的结点，操作与单链表相似。
需要先从pool中申请一个空结点：
size_t StaticList::_malloc_list(){
if (pool->curser == 1){
throw 1;
}
size_t n = pool->curser;
pool->curser = head[pool->curser].curser;
return n;
}
再把数据添加到空结点中：
void StaticList::append(int value){
size_t i=0;
size_t newnode = _malloc_list();
for(; head[i].curser != 0; i=head[i].curser);
head[newnode].value = value;
head[newnode].curser = head[i].curser;
head[i].curser = newnode;
}
获取链表储存数据数
size_t StaticList::len() const {
size_t length=0;
for(size_t i=head->curser; i!=0; i=head[i].curser){
length++;
}
return length;
}
插入元素
插入同样用_malloc_list申请空结点，在修改head链表的指针，进行插入。
void StaticList::insert(size_t index, int value){
size_t target = 0;
if(len()<=index){
throw 1;
}
for(; index > 0; index--){
target = head[target].curser;
}
size_t newnode = _malloc_list();
head[newnode].curser = head[target].curser;
head[newnode].value = value;
head[target].curser = newnode;
}
删除元素
直接修改pool链表的指针，跳过待删除的结点即可。
void StaticList::del(size_t index){
size_t target1 = 0, target2=0;
if (len()-1 < index){
throw 1;
}
for(; index>0; index--)
target1 = head[target1].curser;
target2 = head[target1].curser;
head[target1].curser = head[target2].curser;
head[target2].curser = pool->curser;
pool->curser = target2;
}
获取元素
size_t StaticList::get(size_t index) const {
size_t target = 0;
if (len()-1 < index)
throw 1;
for(;index!=0; index--){
target = head[target].curser;
}
return target;
}
打印链表
//打印详细信息
void StaticList::print_a() const {
cout << "index curser value" << endl;
for(size_t i=0; i<=size+1; i++){
cout << i << '\t' << head[i].curser << '\t' << head[i].value << endl;
}
}
// 打印值
void StaticList::print_v() const {
size_t i=head->curser;
for(; head[i].curser!=0; i=head[i].curser){
cout << head[i].value << ' ';
}
cout << head[i].value << endl;
}
三，完整代码
点击查看代码
#include <iostream>
#include <vector>
using std::vector;
using std::cout, std::cin, std::endl;
struct node{
size_t curser;
int value;
};
struct StaticList {
StaticList();
StaticList(size_t size);
void insert(size_t index, int value);
void del(size_t index);
size_t len() const;
size_t get(size_t index) const;
void append(int value);
void print_a() const;
void print_v() const;
size_t _malloc_list();
node* head;
node* pool;
size_t size;
};
StaticList::StaticList(){
StaticList(20);
size = 20;
}
StaticList::StaticList(size_t size){
head = (node*)malloc(sizeof(node)*(size+2));
pool = head+1;
head->curser = 0;
head->value = 0;
for(size_t i=1; i <= size+1; i++){
head[i].curser = i+1;
head[i].value = 0;
}
head[size+1].curser = 1;
this->size = size;
}
void StaticList::print_a() const {
cout << "index curser value" << endl;
for(size_t i=0; i<=size+1; i++){
cout << i << '\t' << head[i].curser << '\t' << head[i].value << endl;
}
}
void StaticList::print_v() const {
size_t i=head->curser;
for(; head[i].curser!=0; i=head[i].curser){
cout << head[i].value << ' ';
}
cout << head[i].value << endl;
}
void StaticList::append(int value){
size_t i=0;
size_t newnode = _malloc_list();
for(; head[i].curser != 0; i=head[i].curser);
head[newnode].value = value;
head[newnode].curser = head[i].curser;
head[i].curser = newnode;
}
size_t StaticList::_malloc_list(){
if (pool->curser == 1){
throw 1;
}
size_t n = pool->curser;
pool->curser = head[pool->curser].curser;
return n;
}
size_t StaticList::len() const {
size_t length=0;
for(size_t i=head->curser; i!=0; i=head[i].curser){
length++;
}
return length;
}
void StaticList::del(size_t index){
size_t target1 = 0, target2=0;
if (len()-1 < index){
throw 1;
}
for(; index>0; index--)
target1 = head[target1].curser;
target2 = head[target1].curser;
head[target1].curser = head[target2].curser;
head[target2].curser = pool->curser;
pool->curser = target2;
}
size_t StaticList::get(size_t index) const {
size_t target = 0;
if (len()-1 < index)
throw 1;
for(;index!=0; index--){
target = head[target].curser;
}
return target;
}
void StaticList::insert(size_t index, int value){
size_t target = 0;
if(len()<=index){
throw 1;
}
for(; index > 0; index--){
target = head[target].curser;
}
size_t newnode = _malloc_list();
head[newnode].curser = head[target].curser;
head[newnode].value = value;
head[target].curser = newnode;
}
int main(){
StaticList list(10);
list.append(2);
list.append(3);
list.append(3);
list.append(3);
list.insert(4, 1);
list.del(3);
list.print_a();
list.print_v();
return 0;
}