双向循环链表是什么？

在单链表中，从一已知结点出发，只能访问该结点及其后续结点，无法找到该结点之前的其他结点。而在单循环链表中，虽然从任一结点出发都可访问表中所有结点，但访问该结点的直接前驱结点的时间复杂度为O（n）。另外，在单链表中，若已知某结点的存储位置p，则将一新结点s插入p之前（称为前插），不如插入p之后方便，因为进行前插操作必须知道p的直接前驱位置。同理，删除p本身不如删除p的直接后继方便。因此，由于单链表的缺点，引入了双向链表。

创新互联公司从2013年创立，是专业互联网技术服务公司，拥有项目成都网站制作、网站设计网站策划，项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命，1280元常熟做网站,已为上家服务,为常熟各地企业和个人服务,联系电话:18982081108

1.双向链表（DoubleLinkedList）的概念双向链表指的是构成链表的每个结点中设立两个指针域：一个指向其直接前驱的指针域prior，一个指向其直接后继的指针域ne*t。这样形成的链表中有两个方向不同的链，故称为双向链表。

2.双向循环链表将双向链表的头结点和尾结点链接起来也能构成循环链表，其称为双向循环链表。

2.双向链表C语言实现的类型定义4.双向链表示意图双向链表示意，如图1所示。

图1双向链表示意

66037663626

编写主函数实现双向链表的基本操作

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; }

如何建立双向循环链表并输入数据

至少需要一个元素，空的不能能建立数据结构。

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;

}

}

}

网站标题：vb点虐 的双向链表 双向链表的基本操作c
文章地址：http://pwwzsj.com/article/ddjeiph.html