紧凑的多重数组的静态双向链表实现

相关问题：

              我们往往希望双向链表的所有元素在存储器中保持紧凑，例如，在多数组表示中占用前m个下标位置.(在页式虚拟存储的计算环境下，即为这种情况。)假设除指向链表本身的指针外没有其他指针指向该链表元素，试说明如何实现过程ALLOCATE-OBJECT和FREE-OBJECT，使得该表示保持紧凑。(提示，使用栈的数组实现)。

思考过程：

              如果当前数组是紧凑的，设数组已经有n个数据，位于数组前n个位置（栈顶指针为n）。插入一个元素时，需要分配空间，那么栈顶指针+1，也就是第n+1个位置分配给新元素。删除一个元素时，如果删除的元素下标小于栈顶，那么删除后释放内存时，需要把栈顶元素填充到原删除元素的下标位置处，栈顶指针-1,使之保持紧凑。如果删除的元素下标等于栈顶时（按照题意，在分配和释放内存时一定总是保持紧凑的，所以数组中始终是前面的连续空间有数据并且最多不会超过栈顶下标位置，如果超过了就不是紧凑的链表，所以不会出现大于栈顶的情况）那么直接删除，栈顶下标-1即可。

代码如下：

//10.3-4紧凑的多数组静态双向链表
#include <iostream>
#include <time.h>
using namespace std;
#define MAX 10//于表头的前驱和表尾的后继都不存放元素，所以实际能存放的有效元素个数比MAX少2个
#define Null -1
int head=-1,Free=0;
struct List
{
    int next[MAX];
    int key[MAX];
    int prev[MAX];
    int top;
};
//链表初始化
void Initialization(struct List &T)
{
   for (int i=0;i<MAX;i++)
   {
       T.key[i]=0;
       T.prev[i]=0;
   }
   int p=head;
   for ( i=0;i<MAX-1;i++)
   {
      T.next[i]=i+1;
   }
   T.next[i]=Null;//链表最后的next指针为空。-1代表空
   T.top=Null;
}  
//分配空间
int Allocate_object(struct List &T)
{
    static x=0;
    if (Free==MAX)
    {
        cout<<endl;
        cerr<<"out of space!"<<endl;
        return Null;
    }
    else
    {   
        T.top++;//分配空间时，先增加栈顶上限。
        x=T.top;
        Free=T.top+1;//Free指向栈顶下一个位置
        return x;
    }
}
//释放空间
void Free_object(struct List &T,int x)
{//释放空间时，为了使数组紧凑，所以待删除x小于栈顶T.top，那么就需要把删除后的x空位用栈顶位置的数据填充上，
 //这样小于栈顶的位置全部都有有效数据，从而使数据更紧凑。
    if (x<T.top)
    {
        T.key[x]=T.key[T.top];
        //if (T.next[T.top]!=x)//这个判断我还不清楚是否有必要，如果程序出错，加上这个判断试试
        //{
            T.next[x]=T.next[T.top];
        //}
        //if(T.prev[T.top]!=x)//同上
        //{
            T.prev[x]=T.prev[T.top];
        //}
        T.prev[T.next[x]]=x;
        T.next[T.prev[x]]=x;
        if (head==T.top)
        {
            head=x;
        }
    }
    T.top--;Free--;
}
//插入数据
void insert(struct List &T,int k)
{
    int x=Allocate_object(T);//类似指针开辟一段内存空间
    if (x==Null)
    {
        return ;
    }
    T.next[x]=head;
    T.key[x]=k;
    if (head!=Null)
    {
        T.prev[head]=x;
    }
    head=x;
    T.prev[x]=Null;
}
//查找数据
int search(struct List &T,int k)
{
   int t=head;
   if (T.key[t]==0)
   {
       cout<<"链表为空！无法查找！"<<endl;
       return Null;
   }
   while (t!=-1&&T.key[t]!=k)
   {
       t=T.next[t];
   }
   if (t==Null)
   {
       cout<<"不存在这个数据！"<<endl;
       return Null;
   } 
   else
   {
      cout<<"待查找数据已经找到！"<<endl;
      return t;//将待删除的数据下标返回，易于删除工作。
   }
}
//删除数据
void Delete(struct List &T,int k)//删除特定值的删除函数
{ 
    int p=0;
        p=search(T,k);
        if (p!=Null)
        {
       
            if (T.prev[p]!=Null)
            {
                T.next[T.prev[p]]=T.next[p];
            } 
            else
            {
                head=T.next[p];
            }
            if (T.next[p]!=Null)
            {
                T.prev[T.next[p]]=T.prev[p];
            }
            cout<<"删除成功！"<<endl;
            Free_object(T,p);
        } 
        else
        {
            cout<<"待删除的数据不存在！无法删除！"<<endl;
        }
}
void Print(struct List &T)
{
    int i=head;
    if (head==Null)
    {
        cout<<"此链表为空！"<<endl;
        return;
    }
    while (T.next[i]!=Null/*&&T.key[i]!=NULL*/)
    {
        cout<<T.key[i]<<"->";
        i=T.next[i];
    }
    cout<<T.key[i]<<" ";
    cout<<endl;
}
void main()
{
    struct List T;
    srand((unsigned)time(NULL));
    int num[MAX]={0};//临时存放next[MAX]数组的值，目的是用于生成互异的随机数
    cout<<"初始化链表中。";
    int NUM[MAX]={0};//用于存放循环插入的随机数据，便于删除。
    Initialization(T);
    Print(T);
    for (int i=0;i<=MAX;i++)
    {
        int k=rand()%100;
        NUM[i]=k;
        insert(T,k);
    }
    Print(T);
    for ( i=0;i<MAX;i++)
    {
        Delete(T,NUM[i]);
    }
    Print(T);
    insert(T,34);
    insert(T,56);
    insert(T,3);
    insert(T,13);
    Delete(T,34);
    Print(T);
    insert(T,18);
    insert(T,23);
    Delete(T,3);
    Delete(T,18);
    Delete(T,100);
    insert(T,25);
    insert(T,16);
    Delete(T,23);
    Print(T);    
}

紧凑的多重数组的静态双向链表实现,布布扣,bubuko.com

紧凑的多重数组的静态双向链表实现

原文：http://blog.csdn.net/z84616995z/article/details/20291697