// 存储结构的定义
typedef struct LNode{
int data; // 数据域 (这里的数据域是存储一个整数）
struct LNode next; // 指针域
}LNode,LinkList; // LinkList为指向结构体LNode的指针类型

// 单链表的初始化
LinkList InitList(LinkList &L)
{
// 生成空的链表，L指向头结点
L = new LNode;
// 头结点的指针域置空
LNode->next = null;
return L;
}

// 查找第i个元素
int GetElem(LinkList L,int i)
{
// 初始化
LNode p = L->next;
j = 1;
while(p && (i<j))
{
p = p->next;
j++;
}
return p->data;
}

// 查找数据域为e的结点
LNode *LocateElem(LinkList L,int e)
{
// 初始化
LNode p = L->next;
while(p && p->data != e)
{
p->next;
}
retuen p;
}

// 在i处插入一个新的结点，其数据域为e
void ListInsert(LinkList &L,int i,int e)
{
LNode p = new LNode;
p = L->next;
int j = 0;
while(p && (j < i - 1))
{
p = p->next;
j++;
}
LNode s = new LNode; // 生成新的结点
s->data = e; // 给结点赋值
s->next = p->next; // 将新的结点指向p
p->next = s->next; // 将p指向s
}

// 删除位置为i的结点
void ListDelete(LinkList &L, int i)
{
LNode p = new LNode;
p = L->next;
int j = 0;
while(p->next && j < i-1)
{
p = p->next;
j++;
}
LNode q = new LNode;
q = p->next;
p->next = q->next;
delete q;
}

// 前插法创建单链表
void CreateList_H(LinkList &L,int n)
{
// 创建空链表
L = new LNode;
L->next = null;
// 插入n个元素
for(int i = 1; i <= n; i++)
{
LNode p = new LNode;
scanf("%d",&p->data);
// 将新结点插入到头结点后
p->next = L->next;
L->next = p;
}
}

// 后插法
void CreateList_R(LinkList &L,int n)
{
L = new LNode;
L->next = null;
LNode r = L; // 创建尾指针指向L的头结点
for(int i = 1; i <= n; i++)
{
LNode p = new LNode;
scanf("%d",&p->data);
p->next = null; // 将p指向空作为尾结点
r->next = p; // 尾结点指向p，p为尾结点
r = p; // r指向新的尾结点
}
}