Ⅰ 链表的定义
定义 ： 链表 是一种物理存储单元上 非连续、非顺序 的存储结构，由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。
在链表的储存上，每个结点不仅包含所存的元素信息，还包含元素间的 逻辑信息 。
在每个结点除了包含的数据域外，还包明指山含一个 指针域 ，用以指向其后继结点。
带头结点的单链表中， 头指针head 指向头结点，头结逗芦点的值域不含任何信息，从头结点的后继结点开始储存信息。头指针head 始终 不等于NULL ， head->next 等于NULL的时候，链表为空。
不带头结点的单链表中的 头指针head 直接指向开始结点，当head等于NULL时，链表为空。
双链表就是在单链表结点上增添了一个指针域，指向当前节点的 前驱 。
相比于单链表，双链表能够从 终端结点 反向走到 开始结点 。
只需要将单链表 最后一个 指针域（ 空指针 ）指向链表中的 第一个结点 即可。（如果循环单链表带头结点，则指向头结点；不带头结点，则指向开始结点）。
循环单链表可以实现从 任何一个结点 出发，访问链表中任何结点。（注意：此处应该区分与顺序表随机访问的特点。循环单链表指的是从一个结点出发，而不是知道一个结点从而迅速找到任何一个结点，因此循环单链表 不具有 随机访问特性。）
带头结点 的循环单链表，当 head 等于 head->next 时，链表为空； 不带头结点 的循环单链表，当 head 等于 NULL 时，链表为空。
双链表 终端节点的next指针 指向链表中第一个结点，将链表中的第一个结点的 prior指针 指向终端结点。
不带头结点 的循环双链激中表， head 等于 NULL ，链表为空
带头结点 的循环双链表是没有空指针的，其为空状态下， head->next 与 head->prior 必然都等于 head ，故一下四种语句都可判断为空
静态链表借助 一维数组 表示。
静态链表结点空间来自于一个 结构体数组 （一般链表结点空间来自整个内存），数组中每个结点含两个分量：
注意：静态链表的指针不是通常所说储存内存地址的指针型变量，而是储存数组下标的整型变量，其功能类似于指针，故在此称为指针
顺序表储存空间时一次性分配的，链表的是多次分配的
（注： 存储密度 = 结点值域所占存储量/结点结构所占存储总量 ）
顺序表存储密度 = 1
链表存储密度 < 1
顺序表可以 随机存取 ，也可以 顺序存取
链表只能 顺序存取
顺序表平均需要移动一半元素
链表不需要移动元素，仅需 修改指针
Ⅱ 单双向链表原理
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
1链表操作编辑
双向链表
双向链表
线性表的双向链表存储结构：
带头结点的双向循环链表的基本操作：
销毁双向循环链表L：
重置链表为空表：
验证是否为空表：
2元素操作编辑
计算表内元素个数
赋值：
查找元素：
查找元素前驱：
查找元素后继：
查找元素地址：
元素的插入：
元素的删除：
正序查找：
逆序查找：
3循环链表编辑
循环链表是一种链式存储结构，它的最后一个结点指向头结点，形成一个环。因此，从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的操作和单链表的操作基本一致，差别仅仅在于算法中的循环条件有所不同。
Ⅲ 双向循环链表的主要优点
双向链表的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
单链表的缺点是只能往前，不能后退，虽然有循环单链表，但后退的成本还是很高的，需要跑一圈。在这个时候呢，双向链表就应运而生了，再加上循环即双向循环链表就更加不错了。所谓双向链表只不过是添加了一个指向前驱结点的指针，双向循环链表是将最后一个结点的后继指针指向头结点。
(3)循环双链表的存储结构扩展阅读：
循环链表是一种链式存储结构，它的最后一个结点指向头结点，形成一个环。因此，从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的操作和单链表的操作基本一致，差别仅仅在于算法中的循环条件有所不同。
单向链表（单链表）其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。 通过指针连接起来，但是只能单向遍历的内存块。由于它是单向的，或者说不可逆的，所以我们可以把它比作人生：小学->中学->大学->工作->养老。
Ⅳ 线性表- 链式存储结构- 循环链表
循环链表(Circular Linked List)
循环链表是一种首尾相接的链表
循环链表
( )单循环链表 ——在单链表中 将终端结点的指针域NULL改为指向表头结点或开始结点即可
( )多重链的循环链表 ——将表中结点链在多个环上
带头结点的单循环链搏亩表
注意
判断空链表的条件是head==head >胡森next;
仅设尾指针的单循环链表
用尾指针rear表示的单循环链表对开始结点a 和终端结点a n 查找时间都是O( ) 而表的操作常常是在表的首尾位置上进行 因此 实用中多采用尾指针表示单循环链表 带尾指针的单循环链表可见下图
注意
判断空链表的条件为rear==rear >next;
循环链表的特点
循环链表的特点是无须增加存储量 仅对表的链接方式稍作改变 即可使得表处理更加方便灵活
【例】在链表上实现将两个线性表(a a … a n )和(b b … b m )连接成一个线性表(a … a n b …b m )的运算
分析 若在单链表或头指针表示的单循环表上做这种链接操作 都需要遍历第一个链表 找到结点a n 然后将结点b 链到a n的后面 其执行时间是O(n) 若在尾指针表示的单循环链表上实现 则只需修基做森改指针 无须遍历 其执行时间是O( )
相应的算法如下
LinkList Connect(LinkList A LinkList B)
{//假设A B为非空循环链表的尾指针
LinkList p=A >next;//①保存A表的头结点位置
A >next=B >next >next;//②B表的开始结点链接到A表尾
free(B >next);//③释放B表的头结点
B >next=p;//④
return B;//返回新循环链表的尾指针
}
注意
①循环链表中没有NULL指针 涉及遍历操作时 其终止条件就不再是像非循环链表那样判别p或p >next是否为空 而是判别它们是否等于某一指定指针 如头指针或尾指针等
②在单链表中 从一已知结点出发 只能访问到该结点及其后续结点 无法找到该结点之前的其它结点 而在单循环链表中 从任一结点出发都可访问到表中所有结点 这一优点使某些运算在单循环链表上易于实现
lishixin/Article/program/sjjg/201311/23305
Ⅳ 如何建立双向循环链表并输入数据
至少需要一个元素，空的不能能建立数据结构。
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;
}
}
}
Ⅵ 如何实现线性表不同的存储结构
额，有点麻烦。
1、设计四种线性表：顺序存储结构、单链表、循环链表、双向链表的数据存储结构，用户选择某种后就新建一个相应的线性表。
2、针对这四种线性表：顺序存储结构、单链表、循环链表、双向链表，每种都分别设计以下五个（或更多的函数）：初始化线性表、插入数据、删除数据、查找数据、清空线性表等基本操作。所以至少需要4x5=20个函数！每种结构对应至少5个操作！
3、实际上，可以使用C++的标准模板库来迅速搞定，之前做实验我们偷懒用的STL搞的，STL标准模板库将常用的操作全部封装了起来，使用非常简单，比如一个pop()就可以从容器尾部删除元素，push_back()就是从元素尾部插入元素，更多网络一下就搞懂了。再比如单链表可以用容器vector/list来实现，双向链表可以用容器deque来实现，顺序就数组了，循环链表用容器vector自己配个长度控制变量也可以搞定！
希望以上可以对你有所帮助，望采纳~~
Ⅶ C语言二级考试循环链表是循环队列的链式存储结构
循环队列本身是一种顺序存储结构，而循环列表是一种链式存储结构。两者之间是平级关系。
线性链表是线性表的链式存储结构，包括单链表，双链表，循环链表等。
队列的顺序存储结构一般采用循环队列的形式。
循环队列的操作是按数组取摸运算的，所以是顺序存储，而循环链表本身就是收尾相连的，所以循环链表不是循环队列，两种不同的存储结构，虽然实现的功能是一样的，实现循环两种方式 顺序存储就是循环队列，链式存储就是循环链表。
(7)循环双链表的存储结构扩展阅读：
1、比顺序存储结构的存储密度小(链式存储结构中每个结点都由数据域与指针域两部分组成，相比顺序存储结构增加了存储空间)。
2、逻辑上相邻的节点物理上不必相邻。
3、插入、删除灵活 (不必移动节点，只要改变节点中的指针)。
4、查找节点时链式存储要比顺序存储慢。
5、每个节点是由数据域和指针域组成。
6、由于簇是随机分配的，这也使数据删除后覆盖几率降低，恢复可能提高。
Ⅷ 双向循环链表为空的条件
双向循环链表为空的判断条件，这里要分为有头节点和无头节点。
有头节点的双向循环链表，当头节点的前向指针和后驱指针都指向头节点时表示此双向循环链表为空。（head->pro==head && head->next==head）
无头节点的双向循环链表，当head为昌铅空时，表明此双向循环无头结点链表为空。（head==NULL）
另外，单向此枣循环链表为空的条件是什么呢？
同样要分为有头节点和无头节点。
有头节点：head->next==head
无头节点：head==NULL
总结就是：有头节点的循环链表在任何时候指针都不会为空，当头节点指向自己时，链表为耐扒好空。
无头结点的循环链表head等于空就表示链表为空。
Ⅸ 二叉链表和循环链表分别是不是线性结构
二叉链表和循环链表不是线性结构，线性结构有：线性表，栈，队列，双队列，串。
非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图。
二叉链表是树的二叉链表实现方式，以二叉链表作为树的存储结构。所以二叉链表不是线性结构。
循环链表是链式存贮结构，是表中最后一个结点的指针域指向头结点，整个链表形成一个环，属于图。所以不是线性结构。
(9)循环双链表的存储结构扩展阅读
循环链表的特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。
循环链表中没有NULL指针。涉及遍历操作时，其终止条件就不再是像非循环链表那样判别p或p->next是否为空，而是判别它们是否等于某一指定指针，如头指针或尾指针等。
在单链表中，从一已知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前的其它结点。而在单循环链表中，从任一结点出发都可访问到表中所有结点，这一优点使某些运算在单循环链表上易于实现。
Ⅹ 循环链表和双向链表的区别是是什么
1、最后一个结点指针指向不同
在建立一个循环链表时，必须使其最后一个结点的指针指向表头结点，而不是像双向链表那样置为NULL。此种情况还用于在唤宴最后一个结点后插入一个新的结点。
2、判断链域值不同
在判断是否到表尾时，是判断该结点链域的值是否是表头结点，当链域值等于表头指针时，说明已到表尾。而非像单链表那样判断链域值是否为NULL。
3、访问方式：
循环链表：可以从任何一个结点开始，顺序向后访问到达任意结点
双向链表：可以从任何结点开始任意向前向后双向访问
4、操作：
循环链表：只能在当前结点后插入和删除
双链表：可以在当前结点前面或者后面插入，可以删除前趋和后继（包括结点自己）
5、存储：
循环链表存储密度大于双链表
(10)循环双链表的存储结构扩展阅读
线性表的链式存储表示的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素与其直接后继数据元素 之间的逻辑关系，对数据元素 来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。
由这两部分信息组成一个"结点"（如概述旁的图所示），表示线性表中一个数据元素。线性表的链式存储表示，有一个缺点就是要找一个数，必须要从头开始找起，十分麻烦。
根据情况，也可以自己设计链表的其它扩展。但是一般不会在边上附加数据，因为链表的点和边基本上是一一对应的（除了第一个或者最后一个节点，但是也不会产生特殊情况）。不过有一个特例是如果链表支持在链表的昌祥一段中把前和后指针反向，反向标记加在边上可能会更方便。
对于非线性的链表，可以参见相关的其他数据结构，例如树、图。另外有一种基于多个线性链表的数据结构：跳表，插入、删除和查找等基本操作的速度可以达到O(nlogn），和平衡二叉树一样。
其中存储数据元素信息的域称作数据域（设域名为data），存储直接后继存储位置的域称为指针域（设域名为next）。指针域中存储的信息又称做指针或链。
由分别表示,，?，的N 个结点依次相链构成的链表，称为线性表的链式存储表示，由于此类和迅银链表的每个结点中只包含一个指针域，故又称单链表或线性链表。