静态链表实现的两种方法


对象的多数组表示

     用三个数组next key prev 分别表示链表的后继 数据 前驱。

以下的代码分别展示了基本的字典操作和如何申请分配内存。

//由于有些语言不支持指针，所以我们可以用多数组表示的静态双链表。
#include <iostream>
#include <time.h>
#include <windows.h>
using namespace std;
#define MAX 10//于表头的前驱和表尾的后继都不存放元素，所以实际能存放的有效元素个数比MAX少2个
#define Null -1
int head=Null,Free=0;
int j=0;
struct List
{
    int next[MAX];
    int key[MAX];
    int prev[MAX];
};
int isIn(int *num,int index,int pat)//生成的随机数pat是否已经存在
{
    int i=0;
    for(i=0;i<index;++i)
        if(pat==num[i])
            return 1;
        return 0;   
}
int RAND(int *num)//随机抽取元素互异的key 这样key不会出现重复数值，易于以后的删除工作。
{
    int result=0;
    if (j>=MAX)
    {
        return Null;
    }
    while(1)
    {
        result=rand()%MAX;
        if(!isIn(num,j,result))
        {
            num[j]=result;
            j++;
            break;
        }
    }
    return result;
}
//链表初始化
void Initialization(struct List &T,int*num)
{
   Free=RAND(num);//[1,MAX-1]之间的数随机选择一个作为表头元素下标
   for (int i=0;i<MAX;i++)
   {
       T.key[i]=0;
       T.prev[i]=0;
   }
   int p=Free;
   for ( i=0;i<MAX-1;i++)
   {
       p=T.next[p]=RAND(num);
   }
   T.next[p]=Null;//链表最后的next指针为空。-1代表空
   j=0;//结构体T初始化后，临时数组num下标设置为0.
}  
//分配空间
int Allocate_object(struct List &T,int*num)
{
    if (Free==Null)
    {
        cerr<<"out of space!"<<endl;
        return Null;
    }
    else
    {    
      int x=Free; 
   Free=T.next[x];
      return x;
    }
}
//释放空间
void Free_object(struct List &T,int x)
{
   T.next[x]=Free;
   Free=x;
}
//插入数据
void insert(struct List &T,int k,int *num)
{
     int x=Allocate_object(T,num);//类似指针开辟一段内存空间
  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 (head==Null)
   {
       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 (i!=Null)
    {
        cout<<T.key[i]<<"->";
        i=T.next[i];
    }
    cout<<endl;
}
void main()
{
    struct List T;
    srand((unsigned)time(NULL));
    int num[MAX]={0};//临时存放next[MAX]和key[MAX]数组的值，目的是用于生成互异的随机数
    cout<<"初始化链表中。";
 for( int j=0; j <= 100; j++ )      // 打印百分比   
     {  
      cout.width(3);  
      cout << j << "%";  
         Sleep(40);  
      cout << "\b\b\b\b";//\b退格符号  
  }  
    cout << "\n";  
    Initialization(T,num);
    Print(T);
    cout<<"给链表添加数据中。";
 for(  j=0; j <= 100; j++ )      // 打印百分比   
 {  
  cout.width(3);  
  cout << j << "%";  
  Sleep(40);  
  cout << "\b\b\b\b";//\b退格符号  
 }  
    cout << "\n"; 
    for (int i=0;i<MAX+1;i++)
    {
  int k=RAND(num);
        insert(T,k,num);
    }
    insert(T,35,num);
    Print(T);
    cout<<"查找数据中。";
 for(  j=0; j <= 100; j++ )      // 打印百分比   
 {  
  cout.width(3);  
  cout << j << "%";  
  Sleep(40);  
  cout << "\b\b\b\b";//\b退格符号  
 }  
 cout << "\n"; 
    search(T,6);
    cout<<"删除数据中。";
 for( j=0; j <= 100; j++ )      // 打印百分比   
 {  
  cout.width(3);  
  cout << j << "%";  
  Sleep(40);  
  cout << "\b\b\b\b";//\b退格符号  
 }  
    cout << "\n"; 
    Delete(T,0);
    Delete(T,2);
 Delete(T,5);
 Delete(T,500);
 insert(T,25,num);
 Print(T);
}

对象的单数组表示

     用一个数组即可表示双链表，这种表示法比较灵活，因为它允许不同长度的对象存储于同一数组中。一般地我们考虑的数据结构多是由同构的元素构成，因此采用对象的多数组表示法足够满足我们的需求。

以下的代码分别展示了基本的字典操作和如何申请分配内存。

//我们用key next prev表示双链表，如果array[i-1]为key,那么array[i]为next,array[i+1]为prev。
#include <iostream>
#include <time.h>
#include <windows.h>
using namespace std;
#define MAX 120
#define Null -1
int head=0,Free=0;
int isIn(int *num,int index,int pat)//生成的随机数pat是否已经存在
{
    int i=0;
    for(i=0;i<index;++i)
        if(pat==num[i])
            return 1;
        return 0;   
}
int RAND(int *num,int &j)//随机抽取元素互异的key 这样key不会出现重复数值，易于以后的删除工作。
{
    
    int result=0;
    if (j==0)
    {
        num[j]=head;j++;
    }
    while(1)
    {
        if (MAX/3==0)//防止被除数为0
        {
            return Null;
        }
        else
        {
            result=(rand()%(MAX/3)) * 3 + 1;
        }
        if(!isIn(num,j,result))
        {
            num[j]=result;
            j++;
            break;
        } 
    }
    return result;
}
//分配空间
int Allocate_object(int *Array,int*num)
{
    static x;
    if (Free==Null)
    {
        cout<<endl;
        cerr<<"out of space!"<<endl;
        return Null;
    }
    else
    {   
        x=Free;
        Free=Array[x];
        return x;
    }
}
//释放空间
void Free_object(int *Array,int x)
{
    Array[x]=Free;
    Free=x;
}
//链表初始化
void Initialization(int *Array,int*num,int &j)
{
    for (int i=0;i<MAX;i++)
    {
         Array[i]=0;
    }
    int p=RAND(num,j);
    Free=head=p;
    for (i=0;i<MAX/3-1;i++)
    {
         p=Array[p]=RAND(num,j);
    }
   Array[p]=Null;//链表最后的next指针为空。-1代表空
}
int insert(int *Array,int *num,int &j)
{
    static p=head,q=Null;
    int x=Allocate_object(Array,num);
    if (p!=Null)
    {
        Array[p-1]=rand()%MAX+1;
        Array[p+1]=q;
        q=p;
        p=Array[x];
    }
    else cout<<"链表开辟的内存空间不足！ 无法插入！"<<endl;
    return p;
}
//查找数据
int search(int *Array,int k)
{
    int t=head;
    if (Array[t-1]==0)
    {
        cout<<"链表为空！无法查找！"<<endl;
        return Null;
    }
    while (t!=-1&&Array[t-1]!=k)
    {
        t=Array[t];
    }
    if (t==Null)
    {
        cout<<"不存在这个数据！"<<endl;
        return Null;
    } 
    else
    {
        cout<<"待查找数据已经找到！"<<endl;
        return t;//将待删除的数据下标返回，易于删除工作。
    }
}
//删除数据
void Delete(int Array[],int k)//删除特定值的删除函数
{
    int p=0;
    p=search(Array,k);
    if (p!=Null)
    {
        if (Array[p+1]!=Null)
        {
            Array[Array[p+1]]=Array[p];
        } 
        else
        {
            head=Array[p];
        }
        if (Array[p]!=Null)
        {
            Array[Array[p]+1]=Array[p+1];
        }
        Free_object(Array,p);
        cout<<"删除成功！"<<endl;
    }
    else
    {
       cout<<"待删除的数据不存在！无法删除！"<<endl;
    }
}
void Print(int *Array)
{
    int i=head;int flag=1;
    if (Array[head-1]==0)
    {
        cout<<"链表为空！"<<endl;
        return;
    }
    while (flag)
    {
        if (Array[i]==Null)
        {
            flag=0;
        }
        cout<<Array[i-1]<<"\t";
        i=Array[i];        
    }
}
void main()
{
    int Array[MAX];
    int num[MAX]={0};//临时存放数据的next指针的值，目的是用于生成互异的随机数
    int j=0;
    srand((unsigned)time(NULL));
    cout<<"初始化链表中。";
    for( int i=0; i <= 100; i++ )      // 打印百分比 
    {
        cout.width(3);
        cout << i << "%";
        Sleep(40);
        cout << "\b\b\b\b";//\b退格符号
    }
    cout << "\n";
    Initialization(Array,num,j);
    Print(Array);
    cout<<"给链表添加数据中。";
    for(  i=0; i<= 100; i++ )      // 打印百分比 
    {
        cout.width(3);
        cout << i << "%";
        Sleep(40);
        cout << "\b\b\b\b";//\b退格符号
    }
    insert(Array,num,j);
    insert(Array,num,j);
    insert(Array,num,j);
    insert(Array,num,j);
    insert(Array,num,j);
    for ( i=0;i<MAX/3;i++)
    {
        insert(Array,num,j);
    }
    Print(Array);
    cout<<"查找数据中。";
    for(  i=0; i <= 100; i++ )      // 打印百分比 
    {
        cout.width(3);
        cout << i << "%";
        Sleep(40);
        cout << "\b\b\b\b";//\b退格符号
    }
    cout << "\n";
    search(Array,5);
    cout<<"删除数据中。";
    for(  i=0; i <= 100; i++ )      // 打印百分比 
    {
        cout.width(3);
        cout << i << "%";
        Sleep(40);
        cout << "\b\b\b\b";//\b退格符号
    }
    cout << "\n";
    Delete(Array,5);
    Delete(Array,6);
    Delete(Array,7);
    Delete(Array,7);
    Delete(Array,6);
    Print(Array);
}
//多数组的双链表实现已经更新，使其更符合书中代码，尤其是插入函数。







相关内容