/* 数据结构 表的实现 List.h
 * author : star
 */

//防止重复定义
#ifndef LIST_H
#define LIST_H

#include "defs.h"

//初始化容量为n的线性表  
//时间复杂度O(1) 
int InitSqlist(SQLIST *L, int n)
{
	L->data = (ElemType *)malloc(n * sizeof(ElemType));
	if(L->data == NULL)
		return 0;
	L->size = n;
	L->len  = 0;
	return 1;
}

//销毁线性表
//时间复杂度O(1) 
void DestroySqlist(SQLIST *L)
{
	free(L->data);
	L->data = NULL;
	L->size = 0;
	L->len  = 0;
}

//判断线性表的空与满
//时间复杂度O(1)
int IsSqlistFull(SQLIST L)
{
	return L.len == L.size;
}
int IsSqlistEmpty(SQLIST L)
{
	return L.len == 0;
}

//获取第i个数据
//时间复杂度O(1)
//if(i >= 0 || i <= L->len) return L->data[i-1];

//追加数据
//时间复杂度O(1)
int AppendSqlistElem(SQLIST *L, ElemType e)
{
	if(IsSqlistFull(*L))
		return 0; 
	L->data[L->len] = e;
	++L->len;
	return 1;
}

//在i(i>=0)处插入数据
//时间复杂度O(n)
int InsertSqlistElemAt(SQLIST *L, ElemType e, int i)
{
	int k;
	if(i > L->len || IsSqlistFull(*L))
		return 0;
	for(k = L->len - 1; k >= i; --k)
		L->data[k+1] = L->data[k];
	L->data[i] = e;
	++L->len;
	return 1;
}

//删除表中i(i>=0)处的数据
//时间复杂度O(n)
int DeleteSqlistElemAt(SQLIST *L, int i)
{
	int k;
	if(i >= L->len || IsSqlistEmpty(*L))
		return 0;
	for(k = i+1; k < L->len; ++k)
		L->data[k-1] = L->data[k];
	--L->len;
	return 1;
}

//遍历线性表
//时间复杂度O(n)
void TraverseSqlist(SQLIST L)
{
	int i;
	for(i = 0; i < L.len; ++i)
		printf(FORMATSTR, L.data[i]);
}

//查找数据 
//时间复杂度O(n)
int SearchSqlist(SQLIST L, ElemType key)
{
	int i;
	for(i = 0; i < L.len; ++i)
		if(L.data[i] == key)
			return i;
	return -1;
}

//初始化链表  
//时间复杂度O(1)
int InitLinklist(LINKLIST *L)
{
	*L = (LINKLIST)malloc(sizeof(NODE));
	if(*L == NULL)
		return 0;
	(*L)->next = NULL;
	return 1;
}

//销毁链表
//时间复杂度O(n) 
void DestroyLinklist(LINKLIST *L)
{
	NODEPTR p, q;
	p = *L;
	while(p)
	{
		q = p;
		p = p->next;
		free(q);
	}
	*L = NULL;
}

//获取第i(i>=1)个元素 
//时间复杂度O(n)
NODEPTR GetLinklistElem(LINKLIST L, int i, NODEPTR *pre)
{
	NODEPTR p;
	int 	k;
	p = L; k = 0;
	while(k < i && p != NULL)
	{
		*pre = p;
		p = p->next;
		++k;
	}
	if(k < i) 
		*pre = NULL;
	return p;
}

//添加数据
//时间复杂度O(1)
int AddLinklistElem(LINKLIST L, ElemType e)
{
	NODEPTR p;
	p = (NODEPTR)malloc(sizeof(NODE));
	if(p == NULL)
		return 0;
	p->data = e;
	p->next = L->next;
	L->next = p;
	return 1;
}

//在i(i>=1)处插入数据
//时间复杂度O(n)
int InsertLinklistElemAt(LINKLIST L, ElemType e, int i)
{
	NODEPTR p, q, pre;
	q = (NODEPTR)malloc(sizeof(NODE));
	if(q == NULL)
		return 0;	
	q->data = e;
	p = GetLinklistElem(L, i, &pre);
	if(pre == NULL)
		return 0;
	q->next   = p;
	pre->next = q;
	return 1;
}

//删除表中i(i>=1)处的数据
//时间复杂度O(n)
int DeleteLinklistElemAt(LINKLIST L, int i)
{
	NODEPTR p, pre;
	p = GetLinklistElem(L, i, &pre);
	if(p == NULL)
		return 0;
	pre->next = p->next;
	free(p);
	return 1;
}

//遍历线性表
//时间复杂度O(n)
void TraverseLinklist(LINKLIST L)
{
	NODEPTR p;
	p = L->next;
	while(p)
	{
		printf(FORMATSTR, p->data);
		p = p->next;
	}
}

//查找数据 
//时间复杂度O(n)
NODEPTR SearchLinklist(LINKLIST L, ElemType e, NODEPTR *pre)
{
	NODEPTR p;
	*pre = L;
	p = L->next;
	while(p != NULL && p->data != e)
	{
		*pre = p;
		p = p->next;
	}
	if(p == NULL)
		*pre = NULL;
	return p;
}

//删除表中的数据
//时间复杂度O(n)
int DeleteLinklistElem(LINKLIST L, ElemType e)
{
	NODEPTR p, pre;
	p = SearchLinklist(L, e, &pre);
	if(p == NULL)
		return 0;
	pre->next = p->next;
	free(p);
	return 1;
}

//初始化链表  
//时间复杂度O(1)
int InitDBLinklist(DBLINKLIST *L)
{
	*L = (DBLINKLIST)malloc(sizeof(DBNODE));
	if(*L == NULL)
		return 0;
	(*L)->next = (*L)->prior = NULL;
	return 1;
}

//销毁双向链表
//时间复杂度O(n) 
void DestroyDBLinklist(DBLINKLIST *L)
{
	DBNODEPTR p, q;
	p = *L;
	while(p)
	{
		q = p;
		p = p->next;
		free(q);
	}
	*L = NULL;
}

//在双向链表结点后插入元素
//时间复杂度O(1) 
int InsertDBLinklistElemAfter(DBNODEPTR p, ElemType e)
{
	DBNODEPTR q;
	q = (DBNODEPTR)malloc(sizeof(DBNODE));
	if(q == NULL)
		return 0;
	q->data  = e;
	q->next  = p->next;
	q->prior = p;
	if(p->next != NULL)
		p->next->prior = q;
	p->next = q;
	return 1;
}

//遍历双向链表
//时间复杂度O(n)
void TraverseDBLinklist(DBLINKLIST L)
{
	DBNODEPTR p;
	p = L->next;
	while(p)
	{
		printf(FORMATSTR, p->data);
		p = p->next;
	}
}
//删除双向链表中的某个结点
//时间复杂度O(1) 
void DeleteDBLinklistElem(DBNODEPTR p)
{
	DBNODEPTR pre;
	pre = p->prior;
	if(pre != NULL)
		pre->next = p->next;
	if(p->next != NULL)
		p->next->prior = pre;
	free(p);
}

//查找双向链表的数据 
//时间复杂度O(n)
DBNODEPTR SearchDBLinklist(DBLINKLIST L, ElemType e)
{
	DBNODEPTR p;
	p = L->next;
	while(p != NULL && p->data != e)
		p = p->next;
	return p;
}

#endif