单链表的实现方式

实现方式：不带头结点和带头结点

为了写代码方便，使用带头结点的策略作为我的算法模板

单链表的类型描述

1
2
3
4
typedef struct LNode{
	int data;
	struct LNode * next;
}LNode, * LinkList;

初始化

1
2
3
4
5
6
7
// 初始化
void InitList(LinkList & list){
	// 1. 给头结点分配内存
	list = (LNode *)malloc(sizeof(LNode));
	// 2. 头结点指向的下一个结点地址为NULL
	list -> next = NULL;
}

判空

1
2
3
4
5
6
// 判空
bool Empty(LinkList list){
	// 如果头结点下一个结点指向NULL，则为空
	if(!list -> next) return true;
	return false;
}

后插操作

1
2
3
4
5
6
7
8
9
10
11
12
13
// 在p结点之后插入元素e
bool InsertNextNode(LNode * p, int e){
	// 1.不能在NULL后面插入元素
	if(!p) return false;
	// 2.创建新节点承载元素e
	LNode * s = (LNode *)malloc(sizeof(LNode));
	s -> data = e;
	// 3.后插
	s -> next = p -> next;
	p -> next = s;
	
	return true;
}

头插法建立单链表

1
2
3
4
5
6
7
8
9
10
11
12
void HeadInsert(LinkList & list){
	// 初始化单链表
	InitList(list);
	// 批量插入
	int x;
	cin >> x;
	
	while(x != 9999){
		InsertNextNode(list, x);
		cin >> x;
	}
}

尾插法建立单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 尾插法建立单链表
void TailInsert(LinkList & list){
	// 初始化单链表
	InitList(list);
	// 需要一个尾指针指向当前单链表的最后一个有效节点
	LNode * r = list; // 最初是头结点
	// 批量输入
	int x;
	cin >> x;
	
	while(x != 9999){
		LNode * s = (LNode *)malloc(sizeof(LNode));
		s -> data = x;
		// 在尾指针指向的节点后面插入新元素
		s -> next = r -> next;
		r -> next = s;
		r = s; // 更新尾指针
		cin >> x;
	}
	// 非常重要！！！！
	r -> next = NULL;// 尾指针指向的节点的next置空
}

按位查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 按位查找
LNode * GetElem(LinkList list, int i){
	// 1. 位置判断(0:取出头结点)
	if(i == 0) return list;
	// 无效非法的位置i
	if(i < 1) return NULL;
	
	// 2. 查找
	// 计数器
	int j = 1;
	// 第一个元素（可能为空）
	LNode * p = list -> next;
	
	while(p && j < i){ // 循环次数为：相距 i - 1 次(从第1位置找到第4位置需要移动3个单位）
		j++;
		p = p -> next;
	}
	
	return p;
}

插入

1
2
3
4
5
6
7
//将x插入到单链表list的第i个位置上
void Insert(LinkList & list, int i, int x){
	// 插入操作需要先找到第 i - 1 个位置的节点，再插入
	LNode * p = GetElem(list,i-1);
	// 在 p 节点后面插入元素x
	InsertNextNode(p, x);
}

删除

1
2
3
4
5
6
7
8
9
10
11
12
13
// 将单链表中的第i个结点删除
void Delete(LinkList & list, int i){
	if(i<1 || i > Length(list)){
		cout<<"delete failed: index is wrong."<<endl;
		return;
	}
	// 找到第 i - 1 个节点
	LNode * p = GetElem(list,i-1);
	// 删除
	LNode * q = p->next;
	p->next = q->next;
	free(q);
}

另外：前插操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//前插操作：在p结点之前插入元素e
bool InsertPriorNode(LNode * p, int e){
    // 不能在NULL之前插入元素
    if(!p) return false;
    // 前插
    // 创建新节点，在p节点后插
    LNode * s = (LNode *)malloc(sizeof(LNode));
    s->next = p->next;
    p->next = s;
    // p给s，e给p
    s->data = p->data;
    p->data = e;
    return true;
}