#include
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
//Status 是函数返回值类型,其值是函数结果状态代码。
typedef int ElemType;
//ElemType 为可定义的数据类型,此设为int类型
struct LNode
{
ElemType data; //结点的数据域
struct LNode *next; //结点的指针域
};
LNode *CreateNode(ElemType x)//作用:生成一个头结点
{
LNode *t=new LNode;
if(t==0){
return 0;
}
t->data=x;
t->next=0;
return 0;
}
Status InitList(LNode *&L)//作用:构造一个空的链表L
{
L = CreateNode(0); //头结点数据域没有用
if(L==0)return ERROR; //如果没构成成功,返回error
return OK;
}
Status push_head(LNode *&L,ElemType x)//作用:在头结点后面插入数据
{
LNode *t=CreateNode(x);
if(t==0)return ERROR;
t->next=L->next;
L->next=t;
return OK;
}
LNode *Locate_i(LNode *&L,int i) //作用:将i的地址赋给指针p
{//查找第i个结点,返回其地址
if(i<0)return 0; //i=0不合法
if(i==0)return L;//把头结点看做0号结点
LNode *p=L->next;//p指向第一个结点
int j=1; //计数器 初值为1
while(j<i&&p)
{
p=p->next;
j++;
}
return p;//返回地址
}
Status GetElem(LNode *&L, int i, ElemType &x)//作用:将i的data赋值给x
{
LNode *p=Locate_i(L,i);
if(p==0)return ERROR;
x=p->data; //取第i个结点的数据域
return OK;
}
LNode *LocateElem(LNode *&L, int x) //作用:在链表中查找
{//在带头结点的单链表L中查找值为x的元素
LNode *p = L->next;
while(p){
if(p->data==x){
return p;
}
p=p->next;
}
return 0;
}
Status ListInsert(LNode *&L, int i, ElemType x) //作用:在链表中插入一个结点
{//在带头结点的单链表L中第i个位置插入值为x的新结点
LNode *p=Locate_i(L,i-1); //查找第i-1个位置
if(p==0)return ERROR; //找不到插入的位置
LNode *t=CreateNode(x); //为x生成结点
t->next=p->next;
p->next=t;
return OK;
}
Status ListDelete(LNode *&L, int i) //作用:删除单链表中的一个结点
{//在带头结点的单链表L中,删除第i个位置
LNode *p,*q;
p=Locate_i(L,i-1); // 找到第i-1个结点
if(p==0)return ERROR;
q=p->next; //临时保存被删结点的地址以备释放
if(q==0)return ERROR;
p->next=q->next; //改变删除结点前驱结点的指针域
delete q; //释放删除结点的空间
return OK;
}