单链表的初始化

//单链表的存储结构

typedef struct LNode{	//声明结点的类型和指向结点的指针类型
	ELemType data;		//结点的数据域
	struct LNode *next;	//结点的指针域
}LNode, *LinkList;		//LinkList为指向结构体Lnode的指针类型

LinkList L;	//定义链表L
LNode *p;	//定义结点指针p

 
 
单链表的初始化

算法步骤：

1. 生成新结点作为头结点，用头指针L指向头结点
2. 将头结点的指针域置空

Status InitList_L(LinkList &L){
	L = new LNode;
	//或L = (LinkList) malloc (sizeof(LNode))
	L -> next = NULL;
	return OK;
}

判断链表是否为空

思路：判断头结点指针域是否为空

int LintEmpty(LinkList L){	//若L为空表，则返回1，否则返回0
	if(L -> next)			//非空
		return 0;
	else
		return 1;
}

单链表的销毁

思路：从头指针开始，依次释放所有结点

Status DestoryList_L(LinkList &L){		//销毁单链表
	Lnode *p;			//或LinkList p;
	while(L){
		p = L;
		L = L -> next;
		delete p;
	}
	return OK;
}

清空链表

链表存在，但链表中无元素，成为空链表（头指针和头结点依然存在）

思路：依次释放所有结点，并将头结点指针域设置为空

结束条件： p == NULL
循环条件： p！== NULL

Status ClearList(LinkList &L){		//将L重置为空表
	Lnode *p, *q;		//或LinkLsit p,q;
	p = L -> next;
	while(p){			//没到表尾
		q = p -> next;
		delete p;
		p = q;
	}
	L -> next = NULL;	//头结点指针域为空
	return OK;
}

求链表表长

思路：从首元结点开始，依次计数所有结点

int ListLength_L(LinkList L){	//返回L中数据元素个数
	LNode *p;
	p = -> next;		//p指向第一个结点
	i = 0;
	while(p){			//遍历单链表，统计节点数
		i++;
		p = p -> next;		
	}
	return i;
}

取单链表中第i个元素的内容

思路：从链表的头指针出发，顺着链域next逐个结点往下四搜索，直到搜索到第i个结点为止

Status GetElem_L(LinkList L, int i, ElemType &e){
//初始化
	p = L -> next;
	j = 1;
//向后扫描，知道p指向第i个元素或p为空
	while(p && j < i){
		p = p -> next;
		j++;
	}
	if(!p || j > i)    		// j > i：若i为0或为负数，报错
		return ERROR;		//第i个元素不存在
	e = p -> data;			//取第i个元素
	return OK；
}

根据指定值获取该值所在的位置（地址）

思路：从第一个结点其，依次和e相比较（e为指定值），找到一个值与e相等的数据元素，则返回其在链表中的“位置”或地址，没有则返回0或“NULL”

LNode *LocateElem_L(LinkList L, ELemtype e){
	p = L -> next;
	while(p && p -> data != e)
		p = p -> next;
	return p;
}

根据指定值获取该值所在的位置序号

//在线性表L中查找值为e的数据元素的位置序号
int LocateElem_L(LinkList L, Elemtype e){
	p = L -> next;
	j = 1;
//返回L中值为e的数据元素的位置序号，查找失败返回0
	while(p && p -> data != e){
		p = p -> next;
		j++;
	}
	if(p)
		return j;
	else return 0;
}

插入元素

//在L中第i个元素之前插入数据元素e
Status ListInsert_L(LinkList &L, int i, ElemType e){
	p = L;
	j = 0;
	//寻找第i-1个结点，p指向i-1结点
	while(p && j < i-1){		
		p = p -> next;			
		j++;
	}
	if(!p || j > i -1)		//i大于表长+1或者小于1，插入位置非法
		return ERROR;
	s = new LNode;			//生成新结点s，将结点s的数据域置为e
	s -> data = e;
	s -> next = p -> next;	//将结点s插入L中
	p -> next = s;
	return OK;
}

删除第i个结点

//p指向要删除的结点的前驱，q指向要删除的结点
Status ListDelete_L(LinkList &L, int i, ElemType &e){
	p = L;
	j = 0;
	while(p -> next && j < i-1){	//寻找第i个结点，并令p指向其前驱
		p = p -> next;
		j++;
	}
	if(!(p -> next) || j > i-1)		//删除位置不合理
		return ERROR;
	q = p -> next;					//临时保存被删除结点的地址以备释放
	p -> next = q -> next;			//改变删除结点前驱结点的指针域
	e = q -> data;					//保存删除结点的数据域
	delete q;						//释放删除结点的空间
	return OK;
	
}

头插法：元素插入在链表头部

1.从一个空表开始，重复读入数据
2.生成新结点，将读入数据存放到新结点的数据域中
3.从最后一个结点开始，依次将各结点插入到链表前端

void CreateList_H(LinkList &L, int n){
	L= new LNode;
	L -> next = NULL;			//建立一个带头结点的单链表
	for(i = n; i > 0; i--){
		p = new LNode;			//生成新结点p = (LNode*)malloc(sizeof(LNode));
		cin >> p -> data;		//输入元素值scanf(&p -> data);
		p -> next = L -> next;	//插入到表头
		L -> next = p;
	}
}

尾插法：元素插入在链表尾部

1. 从一个空表L开始，将新结点逐个插入到链表的尾部，尾指针r指向链表的尾结点
2. 初始时，r同L均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r指向新结点

void CreateList_R(LinkList &L, int n){
	L = new LNode;
	L -> next = NULL;
	r = L;					//尾指针r指向头结点
	for(i = 0; i < n; i++){
		p = new LNode;		//生成新结点，输入元素值
		cin >> p -> data;
		p -> next = NULL;
		r -> next = p;		//插入到表尾
		r = p;				//r指向新的尾结点
	}
}