【数据结构】-单链表(无头结点）_无头节点单向链表

1.头文件及类型定义

#include<stdio.h>
#include<stdlib.h>
#define ElemType int
1
2
3

2.单链表结点类型定义

typedef struct LNode {
   		//定义单链表结点类型
	ElemType data;			//每个结点存放一个数据元素
	struct LNode* next;		//指针指向下一个结点
}LNode,*LinkList;
1
2
3
4
5

3.函数声明

LinkList InitList(LinkList& L);								//1.初始化单链表(不带头结点)
bool Empty(LinkList L);										//2.判空
bool InsertList(LinkList& L, int i, ElemType e);			//3-1.插入函数-按位序插入：表中第i个位置上插入指定元素e 
bool InsertNextNode(LNode* p, ElemType e);					//3-2.插入函数-指定结点后插：在指定结点之后插入元素e
bool InsertPriorNode1(LinkList& L, LNode* p, ElemType e);	//3-3-1.插入函数-指定结点前插：在指定结点之前插入元素e---法1：老实人O(n)
bool InsertPriorNode2(LNode* p, ElemType e);				//3-3-2.插入函数-指定结点前插：在指定结点之前插入元素e---法2：偷天换日O(1)
bool ListDelete(LinkList& L, int i, ElemType& e);			//4-1.按位序删除
bool DeleteNode1(LinkList& L, LNode* p);					//4-2-1.指定结点的删除：删除指定的元素p---法1：老实人O(n)
bool DeleteNode2(LNode* p);									//4-2-2.指定结点的删除：删除指定的元素p---法2：偷天换日O(1)
LNode* GetElem(LinkList L, int i);							//5-1.查找函数-按位查找：返回第i个元素
LNode* LocateElem(LinkList L, ElemType e);					//5-2.查找函数-按值查找
int Length(LinkList L);										//6.求表的长度
LinkList List_TailInsert1(LinkList& L);						//7-1-1.创建单链表-尾插法1：O(n^2)
LinkList List_TailInsert2(LinkList& L);						//7-1-2.创建单链表-尾插法2：O(n)
LinkList List_HeadInsert(LinkList& L);						//7-2.创建单链表-头插法：O(n)
void PrintList(LinkList L);									//8.遍历单链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

4.基本操作

4.1 初始化单链表

//1.初始化单链表(不带头结点)
LinkList InitList(LinkList& L) {
   
	L = NULL;			//初始化为空，暂时没有任何结点
	return L;
}
1
2
3
4
5
6

4.2 判空

//2.判空
bool Empty(LinkList L) {
   
	if (L == NULL)
		return true;
	else
		return false;
	//或者 return (L==Null);
}
1
2
3
4
5
6
7
8
9

4.3 插入操作

4.3.1 按位插入

//3-1.插入函数-按位序插入：表中第i个位置上插入指定元素e 
bool InsertList(LinkList& L, int i, ElemType e) {
   
	if (i == 1) {
   
		LNode* s = (LNode*)malloc(sizeof(LNode));
		if (s == NULL)		//内存分配失败
			return false;
		s->data = e;
		s->next = L;
		L = s;
		return true;
	}
	/*此段代码=====按位查找操作
		LNode* p;		//指针p指向当前扫描到的结点
		int j = 1;		//当前p指向的是第几个结点
		p = L;			//L指向头指针
		while (p != NULL && j < i - 1) {	//循环找到第i-1个结点
			p = p->next;
			j++;
		}
	*/
	LNode* p = GetElem(L, i - 1);

	/*此段代码====后插操作
		if (p == NULL)
			return false;		//i值不合法
		LNode* s = (LNode*)malloc(sizeof(LNode));		//为要插入的结点申请空间
		if (s == NULL)		//内存分配失败
			return false;
		s->data = e;			//放入数据
		s->next = p->next;		//要插入结点指向i-1的后继结点
		p->next = s;		//i-1的结点指向插入的结点
		return true;
	*/
	return InsertNextNode(p, e);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

4.3.2 指定结点插入

4.3.2.1 指定结点后插

//3-2.插入函数-指定结点后插：在指定结点之后插入元素e
bool InsertNextNode(LNode* p, ElemType e) {
   
	if (p == NULL)
		return false;
	LNode* s = 
1
2
3
4
5