不带头结点的单链表

单链表也可以不设头结点，如图2
12 所示。显
然，基于这种结构的基本操作和带有头结点的线性链
表基本操作是不同的。bo2-8.cpp 是不带头结点的线
性链表的基本操作。

// bo2-8.cpp 不带头结点的单链表(存储结构由c2-2.h定义)的部分基本操作(9个)
#define DestroyList ClearList // DestroyList()和ClearList()的操作是一样的
void InitList(LinkList &L)
{ // 操作结果：构造一个空的线性表L(见图2.13)
L=NULL; // 指针为空
}
void ClearList(LinkList &L)
{ // 初始条件：线性表L已存在。操作结果：将L重置为空表(见图2.13)
LinkList p;
while(L) // L不空
{
p=L; // p指向首元结点
L=L->next; // L指向第2个结点(新首元结点)
free(p); // 释放首元结点
}
}
Status ListEmpty(LinkList L)
{ // 初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE；否则返回FALSE
if(L)
return FALSE;
else
return TRUE;
}
int ListLength(LinkList L)
{ // 初始条件：线性表L已存在。操作结果：返回L中数据元素的个数
int i=0;
LinkList p=L;
while(p) // p指向结点(没到表尾)
{
p=p->next; // p指向下一个结点
i++;
}
return i;
}
Status GetElem(LinkList L,int i,ElemType &e)
{ // L为不带头结点的单链表的头指针。当第i个元素存在时，其值赋给e并返回OK；否则返回ERROR
int j=1;
LinkList p=L;
if(i<1) // i值不合法
return ERROR;
while(j<i&&p) // 没到第i个元素，也没到表尾
{
j++;
p=p->next;
}
if(j==i) // 存在第i个元素
{
e=p->data;
return OK;
}
else
return ERROR;
}
int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
{ // 初始条件：线性表L已存在,compare()是数据元素判定函数(满足为1；否则为0)
// 操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。
// 若这样的数据元素不存在，则返回值为0
int i=0;
LinkList p=L;
while(p)
{
i++;
if(compare(p->data,e)) // 找到这样的数据元素
return i;
p=p->next;
}
return 0;
}
Status ListInsert(LinkList &L,int i,ElemType e)
{ // 在不带头结点的单链线性表L中第i个位置之前插入元素e
int j=1;
LinkList p=L,s;
if(i<1) // i值不合法
return ERROR;
s=(LinkList)malloc(sizeof(LNode));
// 生成新结点
s->data=e; // 给s的data域赋值
if(i==1) // 插在表头(见图2.14)
{
	s->next=L;
L=s; // 改变L
}
else
{ // 插在表的其余处(见图2.15)
while(p&&j<i-1) // 寻找第i-1个结点
{
p=p->next;
j++;
}
if(!p) // i大于表长+1
return ERROR;
s->next=p->next;
p->next=s;
}
return OK;
}
Status ListDelete(LinkList &L,int i,ElemType &e)
{ // 在不带头结点的单链线性表L中,删除第i个元素,并由e返回其值
int j=1;
LinkList p=L,q;
if(i==1) // 删除第1个结点(见图2.16)
{
L=p->next; // L由第2个结点开始
e=p->data;
free(p); // 删除并释放第1个结点
}
else
{
while(p->next&&j<i-1) // 寻找第i个结点,并令p指向其前驱
{
p=p->next;
j++;
}
if(!p->next||j>i-1) // 删除位置不合理
return ERROR;
q=p->next; // 删除并释放结点
p->next=q->next;
e=q->data;
free(q);
}
return OK;
}
void ListTraverse(LinkList L,void(*vi)
(ElemType))
{ // 初始条件：线性表L已存在
// 操作结果：依次对L的每个数据元素调用
// 函数vi()
LinkList p=L;
while(p)
{
vi(p->data);
p=p->next;
}
printf("
");
}

// bo2-9.cpp 不带头结点的单链表(存储结构由c2-2.h定义)的部分基本操作(2个)
Status PriorElem(LinkList L,ElemType cur_e,ElemType &pre_e)
{ // 初始条件：线性表L已存在
// 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，
// 返回OK；否则操作失败，pre_e无定义，返回INFEASIBLE
LinkList q,p=L; // p指向第一个结点
while(p->next) // p所指结点有后继
{
q=p->next; // q为p的后继
if(q->data==cur_e)
{
pre_e=p->data;
return OK;
}
p=q; // p向后移
}
return INFEASIBLE;
}
Status NextElem(LinkList L,ElemType cur_e,ElemType &next_e)
{ // 初始条件：线性表L已存在
// 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，
// 返回OK；否则操作失败，next_e无定义，返回INFEASIBLE
LinkList p=L; // p指向第一个结点
while(p->next) // p所指结点有后继
{
if(p->data==cur_e)
{
next_e=p->next->data;
return OK;
}
p=p->next;
}
return INFEASIBLE;
}

// main2-8.cpp 检验bo2-8.cpp和bo2-9.cpp的主程序
#include"c1.h"
typedef int ElemType;
#include"c2-2.h"
#include"bo2-8.cpp"
#include"bo2-9.cpp"
#include"func2-3.cpp" // 包括equal()、comp()、print()、print2()和print1()函数
void main()
{
	LinkList L;
ElemType e,e0;
Status i;
int j,k;
InitList(L);
for(j=1;j<=5;j++)
{
i=ListInsert(L,1,j);
if(!i) // 插入失败
exit(ERROR);
}
printf("在L的表头依次插入1～5后：L=");
ListTraverse(L,print); // 依次对元素调用print()，输出元素的值
i=ListEmpty(L);
printf("L是否空：i=%d(1:是0:否)
",i);
ClearList(L);
printf("清空L后：L=");
ListTraverse(L,print);
i=ListEmpty(L);
printf("L是否空：i=%d(1:是0:否)
",i);
for(j=1;j<=10;j++)
ListInsert(L,j,j);
printf("在L的表尾依次插入1～10后：L=");
ListTraverse(L,print);
i=GetElem(L,5,e);
if(i==OK)
printf("第5个元素的值为%d
",e);
for(j=0;j<=1;j++)
{
k=LocateElem(L,j,equal);
if(k)
printf("第%d个元素的值为%d
",k,j);
else
printf("没有值为%d的元素
",j);
}
for(j=1;j<=2;j++) // 测试头两个数据
{
GetElem(L,j,e0); // 把第j个数据赋给e0
i=PriorElem(L,e0,e); // 求e0的前驱
if(i==INFEASIBLE)
printf("元素%d无前驱
",e0);
else
printf("元素%d的前驱为%d
",e0,e);
}
for(j=ListLength(L)-1;j<=ListLength(L);j++) // 最后两个数据
{
GetElem(L,j,e0); // 把第j个数据赋给e0
i=NextElem(L,e0,e); // 求e0的后继
if(i==INFEASIBLE)
printf("元素%d无后继
",e0);
else
printf("元素%d的后继为%d
",e0,e);
}
k=ListLength(L); // k为表长
for(j=k+1;j>=k;j--)
{
i=ListDelete(L,j,e); // 删除第j个数据
if(i==ERROR)
printf("删除第%d个元素失败
",j);
else
printf("删除第%d个元素成功，其值为%d
",j,e);
}
printf("依次输出L的元素：");
ListTraverse(L,print);
DestroyList(L);
printf("销毁L后：L=%u
",L);
}

运行结果如下：

/*
在L的表头依次插入1～5后：L=5 4 3 2 1
L是否空：i=0(1:是0:否)
清空L后：L=
L是否空：i=1(1:是0:否)
在L的表尾依次插入1～10后：L=1 2 3 4 5 6 7 8 9 10
第5个元素的值为5
没有值为0的元素
第1个元素的值为1
元素1无前驱
元素2的前驱为1
元素9的后继为10
元素10无后继
删除第11个元素失败
删除第10个元素成功，其值为10
依次输出L的元素：1 2 3 4 5 6 7 8 9
销毁L后：L=0
Press any key to continue
*/