对象的多数组表示
用三个数组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);
}
//多数组的双链表实现已经更新，使其更符合书中代码，尤其是插入函数。