钓鱼网站开发,服务器免费体验,西宁做网站君博专注,营销网站建设教程链表的元素用数组存储#xff0c; 用数组的下标模拟指针。 一、理解 如果有些程序设计语言没有指针类型#xff0c;如何实现链表#xff1f; 在使用指针类型实现链表时#xff0c;我们很容易就可以直接在内存中新建一块地址用于创建下一个结点#xff0c;在逻辑上#x… 链表的元素用数组存储 用数组的下标模拟指针。 一、理解 如果有些程序设计语言没有指针类型如何实现链表 在使用指针类型实现链表时我们很容易就可以直接在内存中新建一块地址用于创建下一个结点在逻辑上我们好像链表是顺序的一样我们根本不用管他们在内存中是如何存储的直接“顺序”地遍历即可。 我们用静态链表使用数组存储元素和下标也想实现逻辑上是顺序的。实际上我们只需要用数组模拟指针我们在创建一个新结点时只需要找到一块“空地”即可创建成功我们在保证data不动的情况下直接修改next数组就能实现指针的变换即一旦创建成功数据的值就存在一个固定的位置而是通过改变“存指针的数组”来改变指向。我们也不需要去考虑到底存在哪逻辑上一样可以想象成和普通链表一样的。可以模拟为 int new_placefind_empty();
data[new_place]new_data;//利用空地“创建新节点”并赋值
next[last_place]new_place;//链表中最后一个结点指向该结点
next[new_place]-1;//新建结点指向为-1 同理实现双向循环静态链表使用left和right数组的下标就可以实现两个左右指针。 二、例题 例题有若干个盒子从左至右依次编号为 1,2,3,...,n。可执行以下指令保证X不等于Y ➢L X Y表示把盒子X移动到盒子Y左边如果X 已在Y左边则忽略该指令。 ➢R X Y表示把盒子X移动到盒子Y右边如果X 已在Y右边则忽略该指令。 这里使用双向循环链表来实现。 vectorint data(n1);//留出一个头结点
vectorint left(n1);
vectorint right(n1);
for(int i1;in;i){data[i]i;//创建结点并赋值 if(i!1)left[i]i-1;//初始化左指针指向前一个结点(用下标模拟指针)else left[i]n;if(i!n)right[i]i1;//初始化左指针指向后一个结点(用下标模拟指针)else right[i]1;
}
while(cinDirectxy){//x和y虽然是盒子编号但是data[x]就是盒子x所以left[x]就是盒子x左边指向的盒子if(DirectL||DirectR)if(DirectL){while(right[x]!y){//右边指向的盒子不等于y 1--2--1--2right[left[x]]right[x];left[right[x]]left[x];left[x]right[x];right[x]right[left[x]];left[right[x]]x;right[left[x]]x;}}else{while(left[x]!y){right[left[x]]right[x];left[right[x]]left[x];right[x]left[x];left[x]left[left[x]];right[left[x]]x;left[right[x]]x;}}
}
int i1;
while(i!-1){cout盒子编号data[i]endl;iright[i];
}
