数据结构列表与链表,数据结构List
基本数据结构：链表)-C plus-C blog
基本数据结构：链表
作者：C肖佳更新时间：2012年7月31日
在说链表之前，先说线性表。线性表是最基本、最简单、最常用的数据结构。线性表中数据元素之间的关系是一对一的，即除了第一个和最后一个数据元素之外，所有数据元素都是端到端的。线性表的存储方式有两种，一种是顺序存储结构，另一种是链式存储结构。
顺序存储结构意味着两个相邻的元素在内存中也是相邻的。这种存储方式的优点是查询的时间复杂度为O(1)，可以通过首地址和偏移量直接访问一个元素。搜索的自适应算法有很多，最快的可以达到O(logn)。缺点是插入和删除的时间复杂度最坏可以达到O(n)。如果在第一个位置插入一个元素，需要将数组中的每个元素向后移动一位。如果删除第一个位置的元素，需要将数组中的每个元素向前移动一位。另一个缺点是，当你不确定元素的数量时，你打开的数组必须保证能放下最大数量的元素。不幸的是，如果实际数量远小于最大数量，那么你打开的数组未使用的内存只能被浪费。
我们常用的阵列是典型的顺序存储结构，如图1所示。
链式存储结构是指两个相邻的元素在内存中可能不相邻，每个元素都有一个指针字段，一般存储指向下一个元素的指针。这种存储方式的优点是插入和删除的时间复杂度为O(1)，不会浪费太多内存。你只会在添加元素的时候申请内存，删除元素会释放内存。缺点是访问的时间复杂度最差是O(n)，关于搜索的算法很少，只能遍历，所以时间复杂度是线性的(O(n))，频繁的应用和内存释放也会消耗时间。
顺序表的特点是随机读取，即访问一个元素的时间复杂度为O(1)，链表的特点是插入和删除的时间复杂度为O(1)。根据实际情况，选择适合自己的收纳结构。
链表是存储在链中的线性表。根据指针字段的不同，链表分为单向链表、双向链表、循环链表等。
1.单向链表
最简单的一种链表是单向链表。每个元素包含两个字段，一个值字段和一个指针字段。我们称这样的元素为节点。在每个节点的指针字段中，都有一个指向下一个节点的指针，最后一个节点指向一个空值。图2是一个单向链表。
单向链表的节点分为两部分。第一部分存储或显示一个节点的信息，第二部分存储下一个节点的地址。单向链表只能单向遍历。
我写了一个简单的C版单向链表模板，所以我将用这段代码来说明如何写一个具体的单向链表(代码仅供学习)。当然，首先你要有C的基础知识和简单的模板元编程。
完全码
首先我们要写一个节点类，链表中的每个节点都是一个节点类的对象。如图3所示。
代码如下：
模板类别t
类别列表节点
{
公共：
slist node(){ next=NULL；}//初始化
Tdata//值
slistNode * next//指向下一个节点的指针
};
第二步是写单链表类的声明，包括属性和方法。
代码如下：
模板类别t
classmyslist
{
私人：
unsignedintlistlength
slistNode T * node//临时节点
slistNode T * lastnode//头节点
slistNode T * headnode//尾节点
公共：
myslist()；//初始化
unsignedintlength()；//链接列表元素的数量
void add(Tx)；//在页脚添加元素
void traversal()；//遍历整个链表并打印出来
boolisEmpty()；//判断链表是否为空。
slist node T * find(Tx)；//找到第一个值为X的节点，返回该节点的地址。如果找不到，则返回NULL。
void delete(Tx)；//删除第一个值为x的节点。
voidinsert(Tx，slist node T * p)；//在p节点后插入值为x的节点
void inserthead(Tx)；//在链表的开头插入一个节点
};
第三步是编写构造函数，初始化链表类的属性。
代码如下：
模板类别t
myslist T :myslist()
{
node=NULL
lastnode=NULL
headnode=NULL
list length=0；
}
第四步是实现add()方法。
代码如下：
模板类别t
voidmyslist T :add(Tx)
{
node=newslitnode T//申请新节点
node-data=x；//新节点被赋予x。
If(lastnode==NULL)//如果没有尾节点，则链表为空。节点既是头节点又是尾节点。
{
headnode=节点；
lastnode=node
}
否则//如果链表不为空
{
lastnode-next=node；//node是尾节点的下一个节点。
lastnode=node//节点成为尾节点，尾节点被赋值为节点。
}
列表长度；//元素数量1
}
第五步，实现traversal()函数，遍历并输出节点信息。
代码如下：
模板类别t
voidmyslist T :traversal()
{
node=headnode//指向带有临时节点的头节点
while(节点！=NULL)//遍历链表并输出
{
cout节点-数据结束；
node=node-next；
}
cout endl
}
第六步：实现isEmpty()函数，判断链表是否为空，为真则不为空。
代码如下：
模板类别t
boolmyslist T :isEmpty()
{
returnlist length==0；
}
步骤7:实现find()函数。
代码如下：
模板类别t
slistNode T *myslist T :find(Tx)
{
node=headnode//指向带有临时节点的头节点
while(节点！=空节点数据！=x)//遍历链表，跳出相同值的节点。
{
node=node-next；
}
returnnode//返回找到的节点的地址，如果没有找到，则返回NULL
}
第八步：实现delete()函数删除第一个值为x的节点，如图4所示。
代码如下：
模板类别t
voidmyslist T :Delete(Tx)
{
slistNode T * temp=headnode//申请一个临时节点指向头节点
if(temp==NULL)返回；//如果头节点为空，则链表没有元素，直接返回。
If(temp- data==x)//如果头节点的值是要删除的值，则删除cast节点。
{
head node=temp-next；//将头节点指向头节点的下一个节点
if(temp-next==NULL)lastnode=NULL；//如果链表中只有一个节点，删除后就没有节点了。将尾节点留空。
删除(临时)；//删除头节点
返回；
}
while(temp- next！=NULL temp- next- data！=x)//遍历链表，找到第一个值等于x的节点，temp表示这个节点的上一个节点。
{
temp=temp-next；
}
if(temp- next==NULL)返回；//如果没有找到，则返回
If(temp- next==lastnode)//如果找到了尾节点
{
lastnode=temp//将尾节点指向它的前一个节点
删除(temp-next)；//删除尾节点
temp-next=NULL；
}
否则//如果它不是尾节点，如图4所示
{
node=temp-next；//用临时节点node指向要删除的节点
temp-next=node-next；//待删除节点的上一个节点指向待删除节点的下一个节点
删除(节点)；//删除节点
node=NULL
}
}
第九步：实现insert()和insertHead()函数，在p节点后插入值为x的节点。如图5所示。
代码如下：
模板类别t
voidmyslist T :insert(Tx，slistNode T *p)
{
if(p==NULL)返回；
Node=newslistNode T //申请新的空间
node-data=x；//如图5所示
node-next=p-next；
p-next=节点；
If(node- next==NULL)//如果该节点是尾节点
lastnode=node
}
模板类别t
voidmyslist T :insertHead(Tx)
{
node=新闻列表Node T
node-data=x；
node-next=head node；
headnode=节点；
}
最后，我们完成一个简单的单向链表。这个单向链表代码有很多需要改进的地方，以后会修改，不定期更新。
双向链表
双向链表的指针字段有两个指针，每个数据节点分别指向直接后继和直接前任。单向链表只能从表头向后遍历，双向链表既可以向前遍历也可以向后向前遍历。除了双向遍历的优点，删除双向链表的时间复杂度会降低到O(1)，因为可以直接通过目的指针找到前驱节点，而单向链表要从头开始遍历才能找到前驱节点。缺点是每个节点多一个指针的空间开销。图6是一个双向链表。
第三，循环链表
循环链表是指链表的最后一个节点指向第一个节点，从而形成一个可以循环遍历的圆。单向循环链表可以单向遍历，双向循环链表头节点的指针也要指向最后一个节点，可以双向遍历。图7是一个双向循环链表。
第四，链表的相关问题
1.如何判断单个链表有环？
2.如何判断一枚戒指的切入点在哪里？
3.如何知道戒指的长度？
4.如何知道两个单链表(非循环的)是否相交？
5.如果两个单链表(非循环的)相交，怎么知道它们相交的第一个节点是什么？
6.如何知道两个单链表(带环的)是否相交？
7.如果两个单链表(有环的)相交，怎么知道它们相交的第一个节点是什么？
回答
