图1为线性表(ZHAO, QIAN, SUN, LI, ZHOU, WU, ZHENG, WANG)的逻辑状态。头指针
指示链表中第一个结点(即第一个数据元素的存储映像)的存储位置。同时,由于最后一个数据元素没有直接后继,则线性链表中最后一个结点的指针为“空”(NULL)。
图1 线性链表的逻辑状态
由上述描述可见,单链表可由头指针来唯一确定,在C语言中可用“结构指针”来描述。
view plaincopy to clipboardprint?
-
-
typedef
struct
LNode{
-
ElemType data;
-
struct
LNode *next;
-
}LNode, *LinkList;
有时在单链表的第一个结点之前附设一个结点,称之为头结点
。
头结点的数据域可以不存储任何信息,也可以存储如线性表长度等类的附加信息,头结点的指针域存储指向第一个结点的指针(即第一个元素结点的存储位置)。如图2(a)所示,此时,单链表的头指针指向头结点。若线性表为空,则头结点的指针域为“空”,如图2(b)所示。
图2 带头结点的单链表
(a)非空表;(b)空表
循环链表
是另一种形式的链式存储结构。它的特点是表中最后一个节点的指针域指向头结点,整个链表形成一个环。由此,从表中任一结点出发均可找到表中其他结点,如图3所示为单链的循环链表
。
图3 单链循环表 (a)非空表;(b)空表
循环链表的操作和线性链表基本一致,差别仅在于算法中的循环条件不是p或p->next
是否为空,而是它们是否等于头指针,但有的时候,若在循环链表中设立尾指针而不设头指针(如图4(a)所示),可使某些操作简化。例如将两个线性表合并成
一个表时,仅需将一个表的尾表和另一个表的头表相接。当线性表以图2.4(a)的循环链表作存储结构时,这个操作仅需改变两个指针值即可,运算时间为O
(1)。合并后的表如图4(b)所示。
图4 仅设尾指针的循环链表 (a)两个链表;(b)合并后的表
以上讨论的链式存储结构的节点中只有一个指示直接后继的指针域,由
此,从某个结点出发只能顺指针往后寻查其他结点。若要寻查节点的直接前趋,则需从表头指针出发。换句话说,在单链表中,NextElem的执行时间为
O(1),而PriorElem的执行时间为O(n)。为克服单链表这种单向性的缺点,可利用双向链表
。顾名思义,在双向链表的结点中有两个指针域,其一指向直接后继,另一指向直接前趋。在C语言中可描述如下:
view plaincopy to clipboardprint?
-
-
typedef
struct
DuLNode{
-
ElemType data;
-
struct
DuLNode *prior;
-
struct
DuLNode *next;
-
}DuLNode, *DuLinkList;
和单链的循环表类似,双向链表也可以有循环表,如图5(c)所示,链表中存有两个环,图5(b)所示为只有一个表头结点的空表。在双向链表中,若d为指向表中某一个结点的指针(即d为DuLinkList型变量),则显然有
d->next->prior=d->prior->next=d
图5 双向链表示例 (a)结点结构;(b)空的双向循环链表;(c)非空的双向循环链表
分享到:
相关推荐
假设以带头结点的循环链表表示一个队列,并且只设一个队尾指针指向尾元素结点(注意不设头指针),试写出相应的置空队、入队、出队的算法。(Java描述)
/*尾插法创建一个带头结点链表*/ node *creat(node *head) { node *r,*s; int x; r=head; printf("在新链表中输入数据以0结束:"); scanf("%d",&x); while(x) { s=(node*)malloc(sizeof(node)); s->data=...
数据结构算法习题答案带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针).docx
已知head指向一个带头结点的单向链表, 链表中每个结点包含数据域(data)和指针域(next)。 请编写函数实现如图所示链表逆置
有详细的讲解和代码,而且代码不是伪码,方便大家学习。
设ha和hb分别是指向两个带头结点的非递减(递增)有序单链表的头指针。要求设计一个算法,将这两个有序链表合并成一个非递增(递减)有序的单链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其它存储...
本程序是采用带头结点的单向循环链表写成的,当指针指到要出列的结点时,先输出结点的序列号,再删除之,直到所有结点都出列完
数据结构算法 习题 答案 带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针).pdf
数据结构算法-习题-答案-带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点注意不设头指针.docx
设head为单链表的头指针,并设单链表带有头结点,编写算法将单链表中的数组元素按照其值递增有序的顺序进行就地排列
一个带头结点的单循环链表,结点类型为(data.next),以haed为头指针,每个结点的data域存放的是一个整数,试构造一个删除所有值大于min,小于max的结点的算法
给定一个索引(位置),返回指向该位置的数据元素的指针,如果给定的位置号不合法,则返回空指针。 给定数据元素x,如果表中有该元素,则返回x第一次出现的索引,若x 不存在,则返回-1. 删除给定索引的数据元素。 ...
带表头结点的单链表,通过了运行,没有错误
要在一个带头结点的单向循环链表中删除头结点,得到一个新的不带头结点的单向循 环链表,若结点的指针域为next,头指针为head,尾指针为p,,则可执行head=head- > next; p->next=head。 5.在双向链表中,每个结点...
自考数据结构
typedef struct N0de //定义结点 { int data; struct N0de *next; }N0de,*QueuePtr; typedef struct //定义尾结点 { QueuePtr rear; }LinkQueue;
创建空的双向链表; 逐字符读取键盘输入的合法...(【提示】:可以利用双向链表的头指针和尾指针,其中头指针往链表尾部移动,尾指针向链表头部方向移动。当头尾指针最后能相遇时,则可认为输入字符串是首尾对称的。)
查看学生信息相当于通过头指针依次读取所有结点来输出整个链表;总分运用了选择排序法。项目的头文件SS.h主要放置结构体和极少部分变量的定义和函数声明。项目的源文件有2个,主函数在源文件main.cpp实现函数调用,...
在O(1)时间删除链表结点给定单向链表的头指针和一个结点指针,定义一个函数在O(1)时间删除该结点,链表结点与函数的定义如下:// 要删除的结点不是尾结点//
2.头插法(用头插法建立链表);3.显示(打印链表);4.求表长(输出链表长度);5.后插(在指定节点后面插入);6.前插(在指定节点前面插入);7.按位置插入(将元素插入指定位置);8.排序(将元素升序排列);9....