多数组实现链表结构 c++实现代码

浏览数：15 / 时间：2015年06月08日

对每个属性使用一个数组表示，多数组可以表示一组同构的对象。指针放在额外的数组中，用下标来表示。

这次实现代码基于10.3-5, 主要为了实现compacitify 操作，即把链表的所有元素在存储器中保持紧凑，本题是都放到前n个位置（n个元素）。

思想是从网上看来的，移动元素的过程中保持链表中元素的相互指向不变，而自由表中并不需要，因为它什么都没有存储。

这里实现了一个List_Freelist类，支持Delete，Insert,Compacitify,Print,Get_Next 等操作。

#include <iostream>
#include <vector>

using namespace std;
const int M = 100;

class List_Freelist{
public:
    List_Freelist(int totalsize);
    void Delete(int x);
    void Insert(int key);
    void Compactify();
    int Get_Next(int x);
    void Print();
    ~List_Freelist(){}
private:
    vector<int> next;
    vector<int> key;
    vector<int> prev;
    int free_list; //head of freelist
    int list;      //head of list 
    int Allocate_Object();
    void Free_Object(int x);
};

List_Freelist::List_Freelist(int totalsize){
    if (totalsize <= 0)
    {
        cout << "size too small";
        throw;
    }
    next.resize(totalsize);
    key.resize(totalsize);
    prev.resize(totalsize);
    list = -1;
    free_list = 0;
    for (int i = 0; i < totalsize - 1; ++i)
        next[i] = i + 1;
    next[totalsize - 1] = -1;
}

void List_Freelist::Delete(int x) {
    if (prev[x] == -1 && next[x] == -1)
        list = -1;
    if (prev[x] != -1)
        next[prev[x]]=next[x];
    if (next[x] != -1)
        prev[next[x]] = prev[x];
    Free_Object(x);
}

int List_Freelist::Allocate_Object(){
    if (free_list == -1)
    {
        cout << "overflow";
        throw;
    }
    int temp = free_list;
    free_list = next[free_list];
    return temp;
}

void List_Freelist::Free_Object(int x){
    next[x] = free_list;
    free_list = x;
}

void List_Freelist::Insert(int value){
    int temp = Allocate_Object();
    key[temp] = value;
    prev[temp] = -1;
    next[temp] = list;
    if (list != -1)
        prev[list]=temp;
    list = temp;
}

int List_Freelist::Get_Next(int x){
    if (next[x] == -1){
        cout << "end of list";
        throw;
    }
    else return key[next[x]];
}
void List_Freelist::Print(){
    if (list == -1){
        cout << "empty list";
        return;
    }
    int temp = list;
    while (next[temp] != -1){
        cout << key[temp]<<" ";
        temp = next[temp];
    }
}
void List_Freelist::Compactify(){
    if (free_list == -1)
        return;
    if (list == -1)
        return;
    int i = free_list;
    while (i != -1){
        prev[i] = INT_MIN;
        i = next[i];
    }
    int left = 0, right = next.size() - 1;
    while (true){
        while (prev[left] != INT_MIN&&left<right)//防止溢出
            ++left;
        while (prev[right] == INT_MIN)
            --right;
        if (left >= right)
            break;
        prev[left] = prev[right];
        key[left] = key[right];
        next[left] = next[right];

        next[right] = left;//记录交换之后链表元素的地址
        ++left;
        --right;
    }
    
    ++right;
    //整理链表，保证其正确性
    for (int i = 0; i < right; ++i){
        if (prev[i] >= right)
            prev[i] = next[prev[i]];
        if (next[i] >= right)
            next[i] = next[next[i]];
    }
    //更新链表head
    if (list >= right)
        list = next[list];
    //整理自由表
    for (int i = right; i < next.size()-1; i++)
        next[i] = i + 1;
    next[next.size() - 1] = -1;
    //更新自由表head
    free_list = right;
}

int main(){
    List_Freelist lf(15);
    for (int i = 0; i < 15; ++i)
        lf.Insert(i);
    lf.Print();
    cout << endl;
    lf.Delete(2);
    lf.Delete(4);
    lf.Delete(6);
    lf.Print();
    cout << endl;
    lf.Compactify();
    lf.Print();
    cout << endl;
}