#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define INFEASIBLE  -1
#define OVERFLOW -2
/*
#define ElemType int
#define Status int
*/
typedef int ElemType;
typedef int Status;
/*
#define LNode LNode
#define LEN sizeof(LNode)
#define MLC (LNode *)malloc
#define MLCS (LNode *)malloc(sizeof(LNode))
*/
/*
//线性表的基本操作定义声明

Status InitList(SqList &L);
//操作结果：构造一个空的线性表L。 1

Status DestroyList(SqList &L);
//初始条件：线性表L已存在。
//操作结果：销毁线性表L。 2

Status ClearList(SqList &L);
//初始条件：线性表L已存在。
//操作结果：将L重置为空表。 3

bool ListEmpty(SqList L);
//初始条件：线性表L已存在。
//操作结果：若L为空表，则返回TRUE，否则返回FALSE。 4

int ListLength(SqList L);
//初始条件：线性表L已存在。
//操作结果：返回L中数据元素的个数。 5

Status GetElem(SqList L, int i, ElemType &e);
//初始条件：线性表L已存在，1<=i<=ListLength(L)。
//操作结果：用e返回L中第i个数据元素的值。 6

int LocateElem(SqList L, int e, bool(*equal)(ElemType, ElemType));
//初始条件：线性表L已存在，compare()是数据元素判定函数。
//返回L中第一个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在，则返回值为0. 7

Status PriorElem(SqList L, ElemType cur_e, ElemType &pre_e);
//初始条件：线性表L已存在。
//操作结果：若cur_e是L中的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。 8

Status NextElem(SqList L, ElemType cur_e, ElemType &next_e);
//初始条件：线性表L已存在。
//操作结果：若cur_e是L中的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。9

Status ListInsert(SqList &L, int i, ElemType e);
//初始条件：线性表L已存在，1<=i<=ListLength(L)+1.
//操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1. 10

Status ListDelete(SqList &L, int i, ElemType &e);
//初始条件：线性表L已存在且非空，1<=i<=ListLength(L).
//操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1. 11

Status ListTraverse(SqList L, bool(*visit)(ElemType));
//初始条件：线性表L已存在
//操作结果：依次对L的每个元素调用函数visit().一旦visit()失败,则操作失败。 12
*/
/*
//线性表的基本操作定义声明
InitList(&L) //初始化线性表L  1
DestroyList(&L) //销毁线性表L  2
ClearList(&L) //清空线性表L  3
ListEmpty(L) //判断线性表是否为空 4
ListLength(L) //求线性表L的长度 5
GetElem(L,i,&e) //取线性表L的第i个元素 6
LocateElem(L,e,compare()) //定位检索线性表L中元素e 7
PriorElem(L,cur_e,&prio_e) //返回线性表L中元素e的直接前驱元素 8
NextElem(L,cur_e,&next_e) //返回线性表L中元素e的直接后继元素 9
ListInsert(&L,i,e) //在线性表L的第i个元素之前插入元素e,返回Bool 10
ListDelete(&L,i,e) //删除线性表L的第i个元素,被删除元素e的值,返回Bool 11
ListTraverse(L,visit()) //遍历线性表:依次对L的每个元素调用visit() 12
*/
/*进阶算法
//reverseList(&L1) //逆置 单链表
//mergeList(&L1,L2) //合并 两个线性表L 15
//visit(e) //  一般是指树型链表结构中对某个节点内容进行访问的函数， 13
//compare(e1,e2) //比较两个元素的大小,返回Bool 14
//compareList(L1,L2) //比较两个线性表L的大小,返回Bool 14
//mergeList(&L1,L2) //合并两个线性表L 15
//Status AppendBefore(List &L, ElemType e) //头插元素
//Status AppendAfter(List &L, ElemType e) //尾插元素
*/
/*---------------线性单链表----------------
单链表 初始化 创建 头插法 尾插法 插入 删除 查找 合并 长度
*/
typedef struct LNode { //封装 结构体 链表的结点==数据元素Elem,结点的指针==链表==数据对象Obj
	ElemType data; //数据Domain ,数据项item
	struct LNode *next; //指针,引用Reference	
}LNode, *LinkList, *LNodePtr;//类型重定义struct LNode为LNode，类型重定义 LNode的*指针 为LinkList
Status InitList(LinkList &L) { //初始化线性链表 产生一个头结点。单链表指针在外面传进来	
	//head
	//?→NULL?
	//表头指针 从函数外面传进来
	L = (LNode *)malloc(sizeof(LNode));
	if (!L) { /* 存储分配失败 */
		exit(OVERFLOW);
	}
	L->next = Null;//结尾指向空
	return TRUE;
}
Status CreateList_Link_Tail_Guan(LinkList &L, int n) {
	//单向链表的创建过程
	//ptemp辅助指针
	// ↓=head
	// ?→NULL
	//ptemp
	//   ↓.next +1
	// ??→NULL
	//ptemp
	//    ↓.next +1
	// ???→NULL
	/*
	从上面的示意图可以看出，我们需要一个辅助指针一直指向最后一个结点，
	这个辅助结点就是为了让每次添加的结点都放置在最后一个位置。
	*/
	//表头指针 从函数外面传进来
	LinkList head = &L, ptemp, pnew;
	ptemp = head;//ptemp辅助指针 必须保证指向尾部,pointer points at head, CORE
	for (int i = n; i >= 1; --i) { // crete n num LNode
		pnew = (LinkList)malloc(sizeof(LNode));//生成新结点 SeCORE 开辟新节点
		scanf(%i, &pnew->data);//scanf data to dataArea,  SeCORE 输入数据
		pnew->next = NULL;//the pnew must be tail LNode.  CORE	
		ptemp->next = pnew;//对象obj(*ptemp).next 连接link to pnew, CORE
		ptemp = pnew;//ptemp++  CORE
	}
}
void CreateList_Link_Head_Yan(LinkList &L, int n) {
	//头插法 生成单链表 完整表
	//逆位序输入n个元素的值，建立带表头结点的单链线性表L
	L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL;//L->next表示头结点的指针,先建立一个带头结点的单链表
	for (i = n; i > 0; --i) {
		p = (LinkList)malloc(sizeof(LNode));
		scanf(&p->data);//输入元素值
		p->next = L->next;//挪动 头指针的后继
		L->next = p;//挪动 头指针的后继
	}
}
Status Insert_Link(LinkList L, int i, ElemType e) {
	LinkList pre, ins; //pre为前驱结点,ins为新结点
	pre = L;
	int l = 1;
	while (p && j < i - 1) { //寻找第i个结点,指针下移,j最后停在i
		p = p->next; ++j;
	}
	if (!p || j > i) return FALSE;//第i个元素不存在
	ins = (LinkList)malloc(LEN);
	ins->data = http://www.mamicode.com/e;>