【单链表基本操作的实现】

单链表基本操作的实现

单链表的初始化（带头结点的单链表）

算法步骤：
1.生成新的结点作为头结点，用头指针L指向头结点。
2.将头结点的指针域置空。

typedef struct LNode {
	ElemType data;
	struct LNode* next;
}LNode,*LinkList;

void InitList(LinkList& L) {
	L = new LNode;
	L->next = NULL;
}
1
2
3
4
5
6
7
8
9

补充单链表的几个简单的常用算法：
【补充算法一】----判断链表是否为空：
空表：链表中无元素，称为空链表（头指针和头结点仍然在）
【算法思路】判断头结点指针域是否为空。

//判断头结点指针域是否为空
int ListEmpty(LinkList L) {
	if (L->next) {//非空
		return 0;
	}
	else {
		return 1;
	}
}
1
2
3
4
5
6
7
8
9

【补充算法二】----单链表的销毁：链表销毁后不存在
【算法思路】从头指针开始，依次释放所有结点。

//销毁单链表
void DestroyList(LinkList &L) {
	LinkList p;
	while (L)
	{
		p = L;
		L = L->next;
		delete p;
	}
}
1
2
3
4
5
6
7
8
9
10

【补充算法三】----清空链表：链表仍存在，但在链表中无元素，成为空链表（头指针和头结点仍然存在）。
【算法思路】依次释放所有结点，并将头结点指针域设置为空。

int ClearList(LinkList& L) {	//将L重置为空表
	LinkList p, q;	//或LNode *p,*q;
	p = L->next;
	while (p) {			//没到表尾
		q = p->next;
		delete p;
		p = q;
	}
	L->next = NULL;//头结点指针域为空
	return 1;
}
}
1
2
3
4
5
6
7
8
9
10
11
12

【补充算法四】----求单链表的表长
【算法思路】从首元结点开始，依次计数所有结点。

//计算单链表的表长
int ListLength(LinkList L) {
	LinkList p;
	p = L->next;//p指向第一个结点
	int i = 0;
	while (p)
	{
		i++;
		p = p->next;//下一个结点的指针域赋值给p；
	}
	return i;
}
1
2
3
4
5
6
7
8
9
10
11
12

回顾：
定义变量：
LinkList L；
LNode *p,*s;
重要操作：
p = L;//p指向头结点
s = L -> next;//s指向首元结点
p = p->next;//p指向下一个结点

算法：取值----取单链表中第i个元素的内容

从链表的头指针出发，顺着链域next逐个结点向下搜索，直至搜索到第i个结点为止。因此，链表不是随机存取的结构。

【算法步骤】
1.从第一个结点（L->next）顺链扫描，用指针p指向当前扫描到的结点，p初值p=L->next.
2.j做计数器，累计当前扫描到过的结点数，j的初值为1。
3.当p指向扫描到的下个节点时，计数器j加一。
4.当j==i时，p所指向的结点就是要找的第i个结点。

//取值
int GetElem(LinkList L, int i, ElemType& e) {//获取线性表L中的某个数据元素的内容，通过变量e返回
	//初始化
	LinkList p = L->next;
	int j = 1;//j做计数器
	while (p==NULL && j < i) {
		//向后扫描，直到p指向第i个元素或p为空
		p = p->next;
		++j;
	}
	if (!p == NULL || j > i) {
		return 0;
	}
	else {
		e = p->data;
		return 1;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

按值查找----根据指定数据获取该数据所在的位置（地址）。

【算法步骤】
1.从第一个结点起，依次和e相比较。
2.如果找到一个其值与e相等的数据元素，则返回其在链表中的“位置”或地址。
3.如果查遍整个链表都没有找到其值和e相等的元素，则返回0或“NULL”。

//查值
LNode* LocateElem(LinkList L,ElemType e ) {
	//在线性表L中查找值为e的数据元素
	//找到，则返回L中值为e的数据元素的地址，查找失败返回NULL
	LinkList p = L->next;
	while (p && p -> data!=e)
	{
		p = p->next;
		return p;
	}
}
1
2
3
4
5
6
7
8
9
10
11

//查值指定该数据位置的序号
int LocateElemi(LinkList L, ElemType e) {
	LinkList p = L->next;
	int j = 1;
	while (p && p->data != e)
	{
		p = p->next;
		j++;
	}
	if (p)
	{
		return j;
	}
	else { 
		return 0;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17