#include<stdio.h>
#include<stdlib.h>
#include<string.h>

//定义元素类型
typedef struct {	
	char* name; //元素名
	int value; //元素值
}Elem;
Elem* createElem(char* name, int value); //指定元素名和元素值创建一个新元素
bool alterElem(Elem* e, char* newName, int newValue); //修改元素的值为新的值
bool copyElem(Elem* eCopy, Elem* e); //将元素e的值复制给eCopy。（eCopy仅为一个指针）
bool isSameElem(Elem* e1, Elem* e2); //判断两个元素的所有属性是否相同（元素名和元素值都相同）
void printElem(Elem* e); //打印元素信息

//单链表结构。定义元素结点类型：
typedef struct LNode{
    Elem* data;   //每个结点存放一个元素指针（数据域）
	LNode* next; //指针指向下一个结点（指针域）
}LNode, *LinkList;
/*上述定义方式等价于：
typedef struct LNode LNode; //强调这是一个结点
typedef struct LNode *LinkList; //强调这是一个链表
*/

/****************************************创建、初始化和释放*****************************************/
LinkList createList(); //创建一个空链表并初始化
void releaseList(LinkList list); //释放线性表开辟的内存空间
/*************************************************增*************************************************/
bool headInsertList(LinkList list, Elem* e); //头插。在表头位置插入元素e。插入成功返回true，失败返回false
bool tailInsertList(LinkList list, Elem* e); //尾插。在表尾插入元素e。插入成功返回true，失败返回false
bool insertList(LinkList list, int pos, Elem* e); //指定位置插入元素。在单链表的第pos（1≤pos≤n）个位置插入元素e，成功返回true，失败返回false。
/*************************************************删*************************************************/
bool headDeleteList(LinkList list); //头删,删除表中的第1个元素。删除成功返回true，失败返回false
bool tailDeleteList(LinkList list); //尾删，删除表尾元素。删除成功返回true，失败返回false
bool deleteList(LinkList list, int pos); //指定位置删除元素。删除单链表list的第pos（1≤pos≤n）个数据元素。删除成功返回true，删除失败返回false。
bool clearList(LinkList list); //清空单链表。清空成功返回true，清空失败返回false。
/*************************************************改*************************************************/
bool alterList(LinkList list, int pos, char* newName, int newValue); //修改表中第pos（1≤pos≤n）个元素的值。修改成功返回true，修改失败返回false。
/*************************************************查*************************************************/
int locateElem(LinkList list, char* name, int value); //根据元素名和元素值来查找数据元素e在表中的位置，如果有，返回位置pos（1≤pos≤n）；如果没有，返回-1
Elem* getElem(LinkList list, int pos); //返回单链表中第pos（1≤pos≤n）个元素的Elem指针。查找失败返回NULL。
bool isNotLegalPosition(LinkList list, int pos); //判断插入位置pos（1≤pos≤n）是否非法。非法则返回true，合法则返回false。
bool isEmpty(LinkList list); //判断单链表是否为空
LNode* getPointer(LinkList list, int pos); //返回指向第pos个元素结点的指针
int listLength(LinkList list); //求单链表的长度
void printList(LinkList list); //打印单链表
/*************************************************其它*************************************************/
LinkList mergeList(LinkList list1, LinkList list2); //合并单链表。将list2加入到list1后面，返回合并后的新表。合并失败返回NULL
LinkList reverseList(LinkList list); //反转单链表元素，返回一个倒序的新表。反转失败返回NULL。
LinkList reversePartList(LinkList list, int startPos, int endPos); //反转部分单链表元素。反转从第startPos到第endPos的元素，包括startPos和endPos位置的元素。反转失败返回NULL。
int sameElemCount(LinkList list1, LinkList list2); //返回两个单链表中相同元素个数
bool alterListFromOther(LinkList list, int pos, LinkList otherList, int otherPos); //将表list的第pos个元素设置设置为与表otherList的第otherPos个元素相同

void main() {
	LinkList list = createList(); //创建一个带头结点的空链表并初始化
	printf("/*************************************************增*************************************************/\n");
	//头插法插入元素
	headInsertList(list, createElem("a", 1));
	printf("头插法插入元素：（a，1），操作后表为：");printList(list);
	//指定索引处插入元素
	insertList(list, 2, createElem("b", 2));
	printf("在第2个位置插入元素：（b，2），操作后表为：");printList(list);
	insertList(list, 2, createElem("c", 3));
	printf("在第2个位置插入元素：（c，3），操作后表为：");printList(list);
	printf("单链表的长度为：%d\n",listLength(list));


	releaseList(list);
}

//指定元素名和元素值创建一个新元素
Elem* createElem(char* name, int value) { 
	Elem* e = (Elem*) malloc(sizeof(Elem));
	if(e == NULL) { //开辟失败则直接返回
		printf("创建元素失败！\n");
		return NULL;
	}
	e->name = (char*) malloc(sizeof(char)*(strlen(name)+1));
	strcpy(e->name, name);
	e->value = value;
	return e;
}

//修改元素的值为新的值。修改成功返回true，修改失败返回false。
bool alterElem(Elem* e, char* newName, int newValue) {
	if(e == NULL || newName == NULL) {
			return false;
	}
	free(e->name);
	e->name = (char* ) malloc(sizeof(char)*(strlen(newName)+1));
	strcpy(e->name, newName);
	e->value = newValue;
	return true;
}

//将元素e的值复制给eCopy。（eCopy仅为一个指针）
bool copyElem(Elem* eCopy, Elem* e) {
	eCopy->name = (char*) malloc(sizeof(char)*(strlen(e->name)+1)); //注意加1，因为有'\0'
	if(eCopy->name == NULL) {
		return NULL;
	}
	strcpy(eCopy->name, e->name); //复制元素名
	eCopy->value = e->value; //复制元素值
	return true;
}

//判断两个元素属性是否相同（元素名和元素值都相同）
bool isSameElem(Elem* e1, Elem* e2) {
	//如果有一个是NULL，返回false
	if(e1 == NULL || e2 == NULL) {
		return false;
	}
	return strcmp(e1->name, e2->name) == 0 ?  e1->value == e2->value : false;
}

//打印元素信息
void printElem(Elem* e) {
	printf("(%s, %d)", e->name, e->value);
}

//创建一个空链表并初始化
LinkList createList() {
	LinkList list = (LinkList) malloc(sizeof(LNode)); //定义头结点
	list->data = NULL; //数据域为NULL，表示不存放数据
	list->next = NULL;
	return list;
}

//释放线性表开辟的内存空间
void releaseList(LinkList list) {
	LNode* p = list;
	while(list != NULL) {
		p = list; //定位要释放的结点
		list = list->next;

		//释放内存，注意根据条件释放多个位置的内存
		if(p->data != NULL) {
			if(p->data->name != NULL) {
				free(p->data->name); //释放元素名指针
			}
			free(p->data); //释放元素指针
		}
		free(p); //释放结点指针
	}
}

//求单链表的长度
int listLength(LinkList list) {
	LNode* p = list;
	int length = 0;
	while(p->next != NULL) {
		length += 1; //这个结点的位置为i
		p = p->next; //往后找一个结点
	}
	return length;
}

//判断插入位置pos（1≤pos≤n）是否非法。非法则返回true，合法则返回false。?
bool isNotLegalPosition(LinkList list, int pos) {
	if(pos < 1 || pos > listLength(list) + 1) {
		return true;
	}
	return false;
}

//返回指向第pos个元素结点的指针
LNode* getPointer(LinkList list, int pos) {
	if(isNotLegalPosition(list, pos)) {
		return NULL;
	}
	LNode* p = list;
	//找到第pos个结点p，并返回指针
	for(int i = 0; i < pos; i++) {
		p = p->next;
	}
	return p;
}

//头插。在表头位置插入元素e。插入成功返回true，失败返回false
bool headInsertList(LinkList list, Elem* e) {
	LNode* node = (LNode*) malloc(sizeof(LNode));
	if(node == NULL || e == NULL) {
		return false; //申请内存失败或元素不存在返回false
	}
	//给结点赋值
	node->data = e;
	//插入链表的头部
	node->next = list->next;
	list->next = node;
	return true;
}

//指定位置插入元素。在单链表的第pos（1≤pos≤n）个位置插入元素e，成功返回true，失败返回false。
bool insertList(LinkList list, int pos, Elem* e) {
	//判断pos是否小于1或者大于链表长度+1
	if(isNotLegalPosition(list, pos)) {
		return false;
	}
	//找到第pos-1个元素结点p
	LNode* p = getPointer(list, pos - 1);
	//创建新结点并赋值
	LNode* newNode = (LNode*) malloc(sizeof(LNode));
	newNode->data = e;
	//将新结点插入到单链表中
	newNode->next = p->next;
	p->next = newNode;
	return true;
}

//打印单链表
void printList(LinkList list) {
	LNode* p = list;
	while(p ->next != NULL) {
		p = p->next; //定位结点
		printf("(%s , %d) ", p->data->name, p->data->value);
	}
	printf("\n");
}