线性链表

在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。链式存储方式即可以用于表示线性结构，也可用于表示非线性结构。
一般来说，在线性表的链式存储结构中，各数据结点的存储符号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致。对于线性链表，可以从头指针开始，沿各结点的指针扫描到链表中的所有结点。

1.线性链表的实现

在实现之前先把需要使用到的库和头文件进行包含
所需的头文件sqlist.h和link_list.h已经在上方提供

#include <stdio.h> 
#include <stdlib.h>   
#include "sq_list.h" 
#include "link_list.h"

1）构造一个空的链表L

void InitList_L(struct LNode * &L){
	//构造一个空的链表L
	L = (struct LNode *)malloc(sizeof(LNode));
	L->next = NULL;
}//InitList_L

2）//销毁表L

void DestoryList_L(struct LNode * &L){
	//销毁表L
	free(L);
	L=NULL;
}//DestoryList_L

3）将表L重置为空表

void ClearList_L(struct LNode * &L){
	//将表L重置为空表
	L->next = NULL; 
}//ClearList_L

4）判断是否为空表

bool ListEmpty_L(struct LNode *&L){
	//判断是否为空表，是返回true,否则返回false;
	if(NULL == L->next)
		return true;
	else
		return false;
}//ListEmpty_L

5）获取链表L中数据元素的个数

int ListLength_L(struct LNode * &L){
	//返回L中数据元素的个数
	int len = 0;//计数
	struct LNode *p = L->next;
	while(NULL != p)
	{
		len++;
		p=p->next;
	}
	return len;
}//ListLength_L

6）获取指定位置元素

Status GetElem_L(struct LNode * &L,int i,ElemType &e){
	//L为带头结点的单链表头指针
	//当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
	struct LNode *p = L->next;//p指向第一个节点
	int j=1;//计数
	while(p != NULL && j<i)
	{
		p = p->next;//p指针后移
		j++;
	}
	if(p==NULL || j>i)
		return ERROR;
	e = p->data;
	return OK;
}//GetElem_L

7）判断两个数据元素是否相等

Status compare_equal_L(ElemType e1,ElemType e2){
	//判断两个数据元素是否相等，相等返回TRUE,否则返回FALSE
	if(e1==e2)
		return TRUE;
	else
		return FALSE;
}//compare_equal_L

8）返回L中第一个与e满足关系的compare()的数据元素的位序

Status LocateElem_L(struct LNode *&L,ElemType e,Status (*compare)(ElemType,ElemType)){
	//单链表L已存在，compare()是数据元素判定函数
	//返回L中第一个与e满足关系的compare()的数据元素的位序，若这样的数据元素不存在，则返回值为0
	struct LNode *p = L->next;//p指向第一个节点
	int i=0;//位序
	while(NULL != p)
	{
		i++;
		if(compare(e,p->data))
			return i;
		p = p->next;
	}
	return 0;
}//LocateElem_L

9）求指定元素前驱

Status PriorElem_L(struct LNode * &L,ElemType cur_e,ElemType &pre_e){
	//要求单链表存在
	//若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义
	int i=0;
	struct LNode *p = L->next;
	while(NULL!=p)
	{
		i=LocateElem_L(L,cur_e,compare_equal_L);
		if(0!=i && 1!=i)
		{
			GetElem_L(L,i-1,pre_e);
			return OK;
		}
		p=p->next;
	}
	return ERROR;
}//priorElem_L

10）求指定元素后继

Status NextElem_L(struct LNode *&L,ElemType cur_e,ElemType &next_e){
	//要求单链表存在
	//若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义
	int i=0;
	struct LNode *p = L->next;
	while(NULL!=p)
	{
		i=LocateElem_L(L,cur_e,compare_equal_L);
		if(i<ListLength_L(L))
		{
			GetElem_L(L,i+1,next_e);
			return OK;
		}
		p = p->next;
	}
	return ERROR;
}//NextElem_L

11） 指定位置插入元素

Status ListInsert_L(struct LNode *&L,int i,ElemType e){
	//要求单链表存在，1<=i<=ListLength_L(L)+1
	//在第i个元素之前插入数据元素e
	struct LNode *p;
	struct LNode *newNode;
	int j;
	p = L;
	j = 0;
	while(NULL!=p && j<i-1)
	{
		//寻找第i-1个结点 
		p = p->next;
		++j; 
	 } 
	 if(NULL==p || j>i-1)
	 	 return ERROR;
	 newNode = (struct LNode *)malloc(sizeof(LNode));//生成新结点 
	 newNode->data = e;
	 newNode->next = p->next;
	 p->next = newNode;
	 return OK;
}//LIstInsert_L

12）删除指定位置元素

Status ListDelete_L(struct LNode *&L,int i,ElemType &e){
	//要求单链表存在，1<=i<=ListLength_L(L)
	//删除L的第i个元素，并用e返回其值
	struct LNode *p;
	struct LNode *del_p;
	int j;
	p = L;
	j = 0;
	while(NULL!=p || j<i-1)
	{
		p = p->next;              //寻找第i个结点，并令p指向其前驱 
		++j;
		
	 } 
	 if(NULL==p->next || j>i+1)
	 {
	 	return ERROR;
	 }
	 del_p = p->next;            //del_p指向被删除的结点
	 p->next = del_p->next;
	 e = del_p->data;
	 free(del_p);
	 del_p = NULL;
	 return e; 
}//ListDelete_L

13）调用visit()函数遍历链表

Status visit_display_L(struct LNode * &L){
	printf("%d",L->data);
	printf("\n");
	return OK;
}//visit_display_L
Status ListTraverse_L(struct LNode * &L,Status (*visit)(struct LNode * &)){
	//要求单链表存在
	//依次对L的每个元素调用函数visit()，一旦visit()失效，则操作失败，返回FALSE,否则返回TRUE
	struct LNode *p;
	p = L->next;//p指向第一个结点L->next;
	while(NULL!=p)
	{
		if(ERROR == visit(p))
		return ERROR;
		p = p->next;
	}
	return OK;
}//ListTraverse_L