正文
vb.net的双向链表 c#双向链表
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
双向循环链表是什么？
在单链表中vb.net的双向链表，从一已知结点出发，只能访问该结点及其后续结点，无法找到该结点之前vb.net的双向链表的其他结点。而在单循环链表中，虽然从任一结点出发都可访问表中所有结点，但访问该结点的直接前驱结点的时间复杂度为O（n）。另外，在单链表中，若已知某结点的存储位置p，则将一新结点s插入p之前（称为前插），不如插入p之后方便，因为进行前插操作必须知道p的直接前驱位置。同理，删除p本身不如删除p的直接后继方便。因此，由于单链表的缺点，引入了双向链表。
1.双向链表（DoubleLinkedList）的概念双向链表指的是构成链表的每个结点中设立两个指针域：一个指向其直接前驱的指针域prior，一个指向其直接后继的指针域ne*t。这样形成的链表中有两个方向不同的链，故称为双向链表。
2.双向循环链表将双向链表的头结点和尾结点链接起来也能构成循环链表，其称为双向循环链表。
2.双向链表C语言实现的类型定义4.双向链表示意图双向链表示意，如图1所示。
图1双向链表示意
66037663626
相关问答
Q1: 双向链表的原理与实现
顾名思义，双向链表跟单链表和循环列表最大的差别，就是同时拥有前驱指针和后驱指针，基于这一个特性，查询某结点的前一个结点，时间复杂度可以达到O(1)，非常高效。双向链表的存取时间复杂度是O(n)，增删时间复杂度为O(1)，跟其他链表没啥区别。
双向链表表示意图：
所以双向链表的结点定义如下：
class Node{
Object data; //元素值
Node pre; //前驱指针
Node next; //后驱指针
}
对于双向链表做增删操作，有一定的顺序要求，顺序不对，很可能会造成空指针异常。
双向链表增加结点示意图：
双向链表删除结点示意图：
将不常被访问的数据进行淘汰，来保证有限空间的使用，在计算机cache当中广为应用，因为cache的大小有限，为了尽可能多的命中热数据，就可以将冷数据进行淘汰，充分利用内存空间。
-》put进数据时，将其放于链尾，因为链尾的数据最不容易被淘汰，并且插入之前需要判断一下空间是否已满，如果满了，就需要将链头的数据淘汰掉。
-》get数据时，如果未在cache中命中，就返回-1，来模拟cache未命中的现象，如果命中，将该数据从当前位置删除，并移至链尾。
之前也提到过，双向链表同其他链表一样，存取时间复杂度都是O(n)，因为都是需要遍历链表才行，增删操作的时间复杂度都是O(1)。实现LRU的过程，如果是put操作，那么针对双向链表的操作只有删除第一个结点，然后添加尾结点，时间复杂度为O(1)，如果是get操作，需要先遍历查找到对应的结点，然后在进行增删操作，前者时间复杂度为O(n)，后者时间复杂度为O(1)，所以加起来还是O(n)。
后续为大家介绍一种实现LRU算法，并且时间复杂度为O(1)的实现方式。
LRU算法的原理与实现
Q2: 建立双向链表 实现对双向链表的插入 删除操作·
#include iostream
using namespace std;
struct Node
{
int data; //节点中vb.net的双向链表的数据 结构体Nodevb.net的双向链表的成员变量
Node* next; //指向下一节点的指针vb.net的双向链表，习惯用next命名 结构体Node的成员变量
Node( const int d=int() ) //结构体也可以有构造函数 ,d=T()来指定默认值
:data(d),next(NULL) //用构造函数来初始化成员变量data和指针
{} //所有数据类型，默认初始化都为0，这里data默认初始化为0
};
class Chain //封装链表
{
private: //数据成员通常都是private的
Node* head; //首先，我们要一个Node型的指针来保存链表的第一个节点vb.net的双向链表；
int length; //再用一个整型变量来记录当前链表内的节点数
public:
Chain() //在构造函数里建立一个空链表，即head指向NULL
:head(NULL),length(0){} //节点数为0;
//当我们在类中定义函数时（不是声明），相当于在前面加上一个inline修饰
void delall() //这个函数用来删除链表中的所有节点
{
Node* pdel; //定义一个Node型指针用来保存要删除的节点
while( head != NULL ) //当head的指向不为NULL时，就是链表中还存在节点
{
pdel = head; //这里备份head的当前指向节点
head = head-next; //把head的指向改变为下一节点
delete pdel; //把head的原指向给删除掉
} //如此一直下去，尾节点的next肯定是指向NULL的，那删除最后一个的时候
//head就被赋值为NULL，不满足循环条件，退出循环
length = 0; //把节点数归零
}
~Chain(){ delall(); } //在析构函数中调用delall函数，来完成对象销毁时清理工作
//这样一个链表必须具备的功能就实现vb.net的双向链表了。下面我们来实现他的增、删、查、改功能
Node* getpoint( int position ) //对链表的操作，其实全部通过指针来实现的，
{ //那就需要定义一个函数来返回当前节点的指针（引用）
if( position0 || positionlength ) //对节点编号进行合法检查
position = length; //如果是非法节点编号，那么就把他修改为最后一个节点编号
if( position==0 ) //如果编号为0，那就是第一个节点了，
return head; //直接返回head就是指向第一个节点的，注意返回的是head本身
Node* head_bak = head; //如果编号合法并且不是第一个节点，就开始遍历链表
for( int i=1; i position; i++ ) //为什么不直接用head
{ //注意这里修改的是成员变量。你把head改了，以后到哪找链表
//我们都是通过head一个一个的往下找节点的。head被修改了。后果显而易见
head_bak = head_bak-next; //通过备份的指针来遍历到指定编号前一个节点
} //i不从0开始，减少运算，提高效率
return head_bak-next; //这里如果返回head_bak的话。那就是需要的前一个节点了
}
void insert( const int data, int position ) //如果不修改参数的话，使用引用做参数的时候，最好加上const
{
Node* pin = new Node(data); //需要调用Node的构造函数
pin-next = getpoint(position); //把指定位置的指针返回给新节点的指针
//也就是说，把新的节点的next指向原来这个位置的节点。
getpoint(position) = pin; //getpoint()返回的是引用，我们可以直接修改它
//前面的一个节点的next指向我们新的节点。
length++; //链表的节点数+1
}
int del( const int data )
{
int position = find(data);
if( position !=-1 ) //-1代表没找到
{
Node* pnext = getpoint(position); //用getponit()来获得指定节点的指向信息
Node* pbak = pnext; //用来备份节点的指向信息
pnext = pnext-next; //把next指向改为下下个节点。
delete pbak;
length--;
}
return position;
}
//把重载，直接输出链表
friend ostream operator( ostream os, const Chain oc )
{
Node* phead = oc.head;
os "[ ";
while( phead !=NULL ) //判断是否到尾节点
{
os phead-data ' ';
phead = phead-next;
}
os "] "; //这个函数，应该没什么好说的了
return os; //如果还是不理解，当成固定模式去背吧
}
};
void show()
{
cout "******************************" endl;
cout "2- 向链表内添加节点（数据，节点号）" endl;
cout "3- 删除链表内某一个数据（数据）" endl;
cout "0- 退出" endl;
cout "******************************" endl;
}
int main()
{
Chain link;
int position, data, choice, data_new;
while( choice != 0 )
{
show();
cout "请选择：";
cin choice;
switch ( choice )
{
case 2 :
cout "请输入要插入的数据和插入位置：" ;
cin data position;
link.insert( data,position );
cout link endl;
break;
case 3 :
cout "请输入要删除的数据：";
cin data;
link.del( data );
cout link endl;
break;
default :
break;
}
}
}
Q3: 双向链表的插入及删除图解
第一步vb.net的双向链表：首先找到插入位置vb.net的双向链表，节点 s 将插入到节点 p 之前
第二步：将节点 s 的前驱指向节点 p 的前驱，即 s-prior = p-prior;
第三步：将节点 p 的前驱的后继指向节点 s 即 p-prior-next = s;
第四步：将节点 s 的后继指向节点 p 即 s-next = p;
第五步：将节点 p 的前驱指向节点 s 即 p-prior = s;
第一步：找到即将被删除的节点 p
第二步：将 p 的前驱的后继指向 p 的后继，即 p-prior-next = p-next;
第三步：将 p 的后继的前驱指向 p 的前驱，即 p-next-prior = p-prior;
第四步：删除节点 p 即 delete p;
Q4: 如何建立双向循环链表并输入数据
至少需要一个元素，空的不能能建立数据结构。
1.循环链表
循环链表是与单链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。循环链表的运算与单链表的运算基本一致。所不同的有以下几点：
1)在建立一个循环链表时，必须使其最后一个结点的指针指向表头结点，而不是象单链表那样置为NULL。此种情况还使用于在最后一个结点后插入一个新的结点。
2)在判断是否到表尾时，是判断该结点链域的值是否是表头结点，当链域值等于表头指针时，说明已到表尾。而非象单链表那样判断链域值是否为NULL。
2.双向链表
双向链表其实是单链表的改进。
当我们对单链表进行操作时，有时你要对某个结点的直接前驱进行操作时，又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后继结点地址的链域，那么能不能定义一个既有存储直接后继结点地址的链域，又有存储直接前驱结点地址的链域的这样一个双链域结点结构呢？这就是双向链表。
3.双向循环链表例程:
#include stdio.h
#include stdlib.h
typedef struct tagDbNode
{
int data;
struct tagDbNode * left;
struct tagDbNode * right;
} DbNode, * pdbNode;
//创建结点
pdbNode CreateNode(int data)
{
pdbNode pnode = (pdbNode)malloc(sizeof(DbNode));
pnode-data = data;
pnode-left = pnode-right = pnode; //创建新结点时，让其前驱和后继指针都指向自身
return pnode;
}
//创建链表
pdbNode CreateList(int head) //参数给出表头结点数据 （表头结点不作为存放有意义数据的结点）
{
pdbNode pnode = (pdbNode)malloc(sizeof(DbNode));
pnode-data = head;
pnode-left = pnode-right = pnode;
return pnode;
}
//插入新结点,总是在表尾插入; 返回表头结点
pdbNode InsertNode(pdbNode node, int data) // 参数1是链表的表头结点，参数2是要插入的结点（结
点数据为data）
{
pdbNode pnode = CreateNode(data);
// 从左到右恢复链接
node-left-right = pnode;
pnode-right = node;
// 从右到左恢复链接
pnode-left = node-left;
node-left = pnode;
return node;
}
//查找结点，成功则返回满足条件的结点指针，否则返回NULL
pdbNode FindNode(pdbNode node, int data) // 参数1是链表的表头结点，参数2是要查找的结点（其中
结点数据为data）
{
pdbNode pnode = node-right;
while (pnode != node pnode-data != data)
{
pnode = pnode-right;
}
if (pnode == node) return NULL;
return pnode;
}
//删除满足指定条件的结点, 返回表头结点, 删除失败返回NULL（失败的原因是不存在该结点）
pdbNode DeleteNode(pdbNode node, int data) // 参数1是链表的表头结点，参数2是要删除的结点（其
中结点数据为data）
{
pdbNode pnode = FindNode(node, data);
if (NULL == pnode) return NULL;
pnode-left-right=pnode-right;
pnode-right-left=pnode-left;
free(pnode);
return node;
}
//获取链表的长度
int GetLength(pdbNode node) // 参数为链表的表头结点
{
int nCount = 0;
pdbNode pnode = node-right;
while (pnode!= node)
{
pnode = pnode-right;
nCount++;
}
return nCount;
}
//顺序打印整个链表
void PrintList(pdbNode node) // 参数为链表的表头结点
{
pdbNode pnode;
if (NULL == node) return;
pnode= node-right;
while (pnode != node)
{
printf("%d ", pnode-data);
pnode = pnode -right;
}
printf("\n");
}
//将链表反序打印
void ReverPrint(pdbNode node) //参数为链表的表头结点
{
pdbNode pnode;
if (NULL == node) return;
pnode= node-left;
while (pnode != node)
{
printf("%d ", pnode-data);
pnode = pnode-left;
}
printf("\n");
}
//删除链表
void DeleteList(pdbNode node) //参数为链表表头结点
{
pdbNode pnode = node-right;
pdbNode ptmp;
if (NULL == node) return;
while (pnode != node)
{
ptmp = pnode-right;
free(pnode);
pnode = ptmp;
}
free(node);
}
//测试程序
#include stdio.h
#include stdlib.h
#include "dblist.h"
#define FALSE 0
#define TRUE 1
typedef unsigned int bool;
void main()
{
int nChoose;
int data;
bool bFlag = FALSE;
pdbNode pnode;
pdbNode list = CreateList(0);
while(bFlag == FALSE)
{
printf("Main Menu\n");
printf("1. Insert\n");
printf("2. Delete Node\n");
printf("3. Find\n");
printf("4. Length\n");
printf("5. Positive Print\n");
printf("6. Negative Print\n");
printf("7. Delete List\n");
printf("0. quit\n\n");
scanf("%d", nChoose);
switch(nChoose)
{
case 1:
printf("Input the data to insert:");
scanf("%d", data);
list = InsertNode(list, data);
PrintList(list);
printf("\n");
break;
case 2:
printf("Input the data to delete: ");
scanf("%d", data);
DeleteNode(list, data);
PrintList(list);
printf("\n");
break;
case 3:
printf("Input the data to find: ");
scanf("%d", data);
pnode = FindNode(list, data);
if (NULL != pnode)
{
printf("Find succeed!\n");
printf("\n");
}
else
{
printf("Find failed!\n");
printf("\n");
}
break;
case 4:
printf("The list's length is %d\n", GetLength(list));
printf("\n");
break;
case 5:
PrintList(list);
printf("\n");
break;
case 6:
ReverPrint(list);
printf("\n");
break;
case 7:
DeleteList(list);
printf("\n");
break;
case 0:
DeleteList(list);
bFlag = TRUE;
}
}
}
Q5: 编写主函数实现双向链表的基本操作
int delete(info * h, int no) { info t; if(h == NULL || *h == NULL) return 0; t = *h; do{ if(t-no == no){ if(t == *h){ if( t-next == t) *h = NULL; else{ *h = t-next; t-prior -next = t-next;t-next -prior = t-prior;} } else { t-prior -next = t-next;t-next -prior = t-prior; } free(t); return 1; } t = t-next; }while(t != *h); return 0; }
关于vb.net的双向链表和c#双向链表的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。
