数据结构列表与链表,数据结构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.如果两个单链表(有环的)相交,怎么知道它们相交的第一个节点是什么?
回答
郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。