#include"LinkList.h"

//L不存在信息提示函数
void errorInfo() {
	printf("单链表未初始化！请先初始化！\n");
}


bool InitList(LinkList& L) {
	//L = (LinkList)malloc(sizeof(LNode));			//生成新结点作为头结点，用头指针L指向头结点
	L = new LNode;	//c++方式 #include<iostream>
	if (L == NULL) {
		return false;
	}
	L->next = NULL;			//头结点指针域为空
	return true;
}

bool GetElem(LinkList& L, int i, ElemType& e) {
	if (L == NULL) {
		errorInfo();
		return false;
	}
	LNode* p = L->next;							//初始化，p指向首元结点
	int j = 1;									//计数器j初值赋为1
	//顺着链域next向下访问，只要p不为空，或者没有到达i
	while (p && j<i)
	{
		p = p->next;							//p指向下一结点
		j++;									//计数器j加1
	}
	//添加j>i是防止i<=0(while确实没有执行，但p为真，这里j其实可以改为1)
	//!p防止i>n
	if (!p || j>i)
	{
		return false;
	}
	e = p->data;
	return true;
}
LNode* LocateElem(LinkList L, ElemType e, int(*myCompare)(ElemType, ElemType)) {
	if (L == NULL) {
		errorInfo();
		return NULL;
	}
	LNode* p = L->next;								//初始化，p指向首元结点
	while (p && !myCompare(p->data,e))				//顺着链域向后扫描，直到p为空或者找到
	{
		p = p->next;
	}
	return p;										//查找失败p为NULL
}

bool ListInsert(LinkList& L, int i, ElemType e) {
	if (L == NULL) {
		errorInfo();
		return false;
	}
	LNode* p = L;
	int j = 0;
	while (p && (j<i-1))
	{
		p = p->next;
		j++;
	}											//查找第i-1个结点，此时p指向该结点（后插操作）
	if (!p || j>i-1)
	{
		return false;							//i>n+1 || i<1
	}
	LNode* s = new LNode;						//生成新结点*s
	s->data = e;								//给新结点赋值
	s->next = p->next;							//新结点指针域指向p的下一个结点
	p->next = s;								//重链接链表
	return true;
}

bool ListDelete(LinkList& L, int i) {
	if (L == NULL) {
		errorInfo();
		return false;
	}
	LNode* p = L; 
	int j = 0;
	while ((p->next) && (j<i-1))	//查找第i-1个结点，用p指针指向该结点
	{
		p = p->next;
		++j;
	}
	if (!(p->next) || (j>i-1))		//当i>n 或 i<1时，位置不合法
	{
		return false;
	}
	LNode* q = p->next;				//临时保存被删除的结点的地址以备释放
	p->next = q->next;				//改变删除结点前驱结点的指针域
	delete q;						//释放删除结点的空间
	return true;
}

void TraverseList(LinkList L, void(*myPrint)(ElemType)) {
	if (L == NULL) {
		errorInfo();
		return;
	}
	LNode* p = L->next;
	printf("\n");
	printf("链表遍历如下：\n");
	while (p)
	{
		myPrint(p->data);
		p = p->next;
	}
}

void CreateList_HeadInsert(LinkList& L, int n, ElemType(*create)()) {
	//像栈，逆序输入n个元素的值，建立带头结点的单链表L
	L = (LinkList)malloc(sizeof(LNode));
	if (L==NULL)
	{
		return;
	}
	L->next = NULL;									//建立一个带头结点的空链表
	for (int i = 0; i < n; i++)
	{
		LNode* p = (LNode*)malloc(sizeof(LNode));	//生成新的结点*p
		if (p==NULL)
		{
			return;
		}
		p->data = create();							//给数据，数据域不同输入数据不同
		p->next = L->next;
		L->next = p;								//将新结点*p插入到头结点之后
	}
}

void CreateList_TailInsert(LinkList& L, int n, ElemType(*create)()) {
	//像队列。正序输入n个元素的值，建立带头结点的单链表L
	L = (LinkList)malloc(sizeof(LNode));			//先建立一个带头结点的空链表
	if (L == NULL)
	{
		return;
	}
	L->next = NULL;
	LNode* r = L;									//尾指针r指向头结点
	for (int i = 0; i < n; i++)
	{
		LNode* p = (LNode*)malloc(sizeof(LNode));	//生成新的结点*p
		if (p == NULL)
		{
			return;
		}
		p->data = create();					//给数据，数据域不同输入数据不同
		p->next = NULL;
		r->next = p;						//将新结点*p插入尾结点*r之后
		r = p;								//r指向新的尾结点*p
	}

}


bool ListInsert(DuLinkList& L, int i, ElemType e) {
	if (L == NULL)
	{
		return false;							//没有头结点
	}
	DuLNode* p = L;								//指向头结点
	DuLNode* q = L;
	int j = 0;
	while (p && (j < i))
	{
		q = p;									//防止p为空找不到前驱
		p = p->next;							//插在链尾用到q
		j++;
	}											//查找第i个结点，此时p指向该结点(在i结点前插入)
	if ((!p && j != i) || j > i)				//查找第i-1个结点会更好，因为需要在链尾插的时候没有第i个结点
	{
		return false;							//i>n || i<1
	}

	DuLNode* s = (DuLNode*)malloc(sizeof(DuLNode));		//新生成结点*s
	if (s == NULL)
	{
		return false;
	}
	s->data = e;								//将结点*s数据域设为e

	if (!p && j == i) {							//指向链尾
		s->prior = q;
		s->next = NULL;
		q->next = s;
		return true;
	}
	s->prior = p->prior;						//将结点插入*s，前驱为i位置结点前驱
	p->prior->next = s;							//*p前驱的后继变成*s
	s->next = p;								//*s的后继为*p
	p->prior = s;								//*p的前驱改为*s完成链接
	return true;
	//【感觉有问题】
}

bool ListDelete(DuLinkList& L, int i) {
	DuLNode* p = L;											//指向头结点
	int j = 0;
	while (p && (j < i))
	{
		p = p->next;							
		j++;
	}
	if (!p|| j > i|| i == 0)								//查找第i-1个结点会更好，因为需要在链尾插的时候没有第i个结点
	{//不能删除头结点
		return false;										//i>n || i<1
	}
	p->prior->next = p->next;
	p->next->prior = p->prior;
	free(p);
	return true;
}