/********************** 声明部分 **********************/
#include
#include
#include
#define LIST_INIT_SIZE 10 //定义最初申请的内存的大小
#define LIST_INCREMENT 2 //每一次申请内存不足的时候扩展的大小
#define OVERFLOW false //异常抛出返回值
#define ERROR false //异常抛出返回值
#define FALSE false //异常抛出返回值
#define TRUE true //程序正确执行抛出返回值
#define INFEASIBLE false //异常抛出返回值
#define OK true //程序正确执行抛出返回值
typedef int ElemType; //别名声明，其实int可以用任意的名字代入
typedef bool Status; //别名声明
/********************** 结构体定义部分 **********************/
struct LNode
{
ElemType data; //数据域
LNode *next; //指针域
};
typedef LNode *LinkList;
/********************** 函数块部分 **********************/
/********************** 构造一个空的线性表 **********************/
void InitList(LinkList &L)
{
//初始条件：无
L=(LinkList)malloc(sizeof(LNode)); //产生头结点，并使L指向此头结点
if(!L) //储存分配失败
exit(OVERFLOW);
L->next=NULL; //指针域为空
}
/***************销毁线性表*****************/
void DestroyList(LinkList &L)
{
LinkList q;
while(L)
{
q=L->next;
free(L);
L=q;
}
}
/**************清空线性表**************/
void ClearList(LinkList &L)
{
LinkList q,p;
p=L->next;
while(p)
{
q=p->next;
free(p);
p=q;
}
L->next=NULL;
}
/*******判断线性表是否空*******/
int ListEmpty(LinkList &L)
{
if(L->next)
return 0;
else
return 1;
}
/************返回线性表的长度************/
int ListLength(LinkList &L)
{
int i=0;
LinkList p=L->next;
while(p)
{
i++;
p=p->next;
}
return i;
}
/********************** 用e返回L中第i个元素的值 **********************/
Status GetElem(LinkList &L,int i,ElemType &e)
{
//初始条件：线性表已经存在，L为带头结点的单链表的头指针
int j=1;
LinkList p=L->next;
while(p&&j
p=p->next;
j++;
}
if(!p||j>i)
return ERROR;
e=p->data;
return OK;
}
/**************查找元素的位置**************/
int LocateElem(LinkList &L, ElemType e,
int (*compare)(ElemType, ElemType))
{
int i=0;
LinkList p=L->next;
while(p)
{
if(compare(p->data,e))
i++;
p=p->next;
}
if(i<=ListLength(L))
return i;
else
return 0;
}
/********************** 在L中第i个位置之前插入新的数据元素e，L的长度加1 **********************/
Status ListInsert(LinkList &L,int i,ElemType e)//不改变L
{
//初始条件：线性表已经存在，1<=i<=ListLength(L)+1
int j=0;
LinkList p=L,s;
while(p&&j
p=p->next;
j++;
}
if(!p||j>i-1
) //i小于1或者大于表长
return ERROR;
s=(LinkList)malloc(sizeof(LNode)); //生成新节点
s->data=e; //插入L中
s->next=p->next;
p->next=s;
return OK;
}
/********************** 删除L的第i个元素，并用e返回其值，L的长度减1 **********************/
Status ListDelete(LinkList &L,int i,ElemType &e)
{
//初始条件：线性表已经存在，1<=i<=ListLength(L)+1
int j=0;
LinkList p=L,q;
while(p->next&&j
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;
}
/***********用pre_e返回cur_e的前驱************/
int PriorElem(LinkList &L,ElemType cur_e,ElemType &pre_e)//
{
LinkList q,p=L->next;
while(p->next)
{
q=p->next;
if(q->data==cur_e)
{
pre_e=p->data;
return OK;
}
p=q;
}
return INFEASIBLE;
}
/************next_e返回cur_e的后继*************/
int NextElem(LinkList &L,ElemType cur_e,ElemType &next_e)
{
LinkList p=L->next;
while(p->next)
{
if(p->data==cur_e)
{
next_e=p->next->data;
return OK;
}
p=p->next;
}
return INFEASIBLE;
}
/********************************以此对L的每个数据元素调用函数vi()*****************************/
void ListTraverse(LinkList L,void (*vi)(ElemType &))
{
LinkList p=L->next;
while(p!=NULL)
{
vi(p->data);
p=p->next;
}
printf("\n");
}
/*********************输出格式（%d）*********************/
void print(ElemType &c)
{
printf("%d ",c);
}
/************比较功能函数***************/
Status equal(ElemType c1,ElemType c2)
{
if(c1==c2)
return TRUE;
else
return FALSE;
}
/**************主函数********************/
void main()
{
int i,j,e,k;
LinkList La;
InitList(La);
printf("输入单链表La中的五个元素：");
for(i=1;i<=5;i++)
{
scanf("%d",&e);
ListInsert(La,i,e);
}
printf("单链表的长度：%d\n",ListLength(La));
i=ListEmpty(La);
printf("La是否空:i=%d (1:是 0:否)\n",i);
ClearList(La);
printf("清空La后：La=");
ListTraverse(La,print);
printf("L是否空:i=%d (1:是 0:否)\n",i=ListEmpty(La));
printf("请再次输入单链表La中的五个元素：");
for(i=1;i<=5;i++)
{
scanf("%d",&e);
ListInsert(La,i,e);
}
printf("输入要查找的第几个元素：");
scanf("%d",&i);
printf("查找的元素为：");
GetElem(La,i,e);
printf("%d\n",e);
printf("La:");
ListTraverse(La,print);
printf("输入要删除元素的位置：");
scanf("%d",&i);
ListDelete(La,i,e);
printf("La:");
ListTraverse(La,print);
printf("删除的元素为：%d\n",e);
while(1)
{
printf("输入一个链表中的元素：");
scanf("%d",&j);
if((k=PriorElem(La,j,e))==INFEASIBLE)
printf("此元素无前驱！\n");
else
br
eak;
}
printf("此元素的前驱为%d\n",e);
while(1)
{
printf("输入一个链表中的元素：");
scanf("%d",&j);
if((k=NextElem(La,j,e))==INFEASIBLE)
printf("此元素无后继！\n");
else
break;
}
printf("此元素的后继为%d\n",e);
DestroyList(La);
printf("销毁La后: La=%u\n",La);
}