链表
结构体定义
1
2
3
4
5
// 单链表结构体
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkedList;
头插法
1
2
3
4
5
6
7
8
9
10
11
12
13
// 头插法
LinkedList HeadInsert(LinkedList &L) {
int x;
L = new LNode; // 创建头结点
L->next = NULL; // 初始化为空链表
while (cin >> x && x != -1) { // 输入-1表示结束
LNode *s = new LNode;
s->data = x;
s->next = L->next;
L->next = s;
}
return L;
}
尾插法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 尾插法
LinkedList TailInsert(LinkedList &L) {
int x;
L = new LNode; // 创建头结点
L->next = NULL; // 初始化为空链表
LNode *r = L; // r为表尾结点
while (cin >> x && x != -1) { // 输入-1表示结束
LNode *s = new LNode;
s->data = x;
r->next = s;
r = s;
}
return L;
}
按序号查找结点值
1
2
3
4
5
6
7
8
9
10
11
12
// 按序号查找结点值
LNode *GetElem(LinkedList L, int i) {
int j = 1; // 计数器
LNode *p = L->next; // p为第1个结点指针
if (i < 0) return NULL; // i无效，返回NULL
if (i == 0) return L; // i=0，返回表头
while (p && j < i) { // 查找第i个结点
p = p->next;
j++;
}
return p; // 返回第i个结点的指针，若i>表长，返回NULL
}
按值查找表结点
1
2
3
4
5
6
7
8
// 按值查找表结点
LNode *LocateElem(LinkedList L, ElemType e) {
LNode *p = L->next;
while (p && p->data != e) { // 从第1个结点查找数据为e的结点
p = p->next;
}
return p;
}
插入操作
1
2
3
4
5
6
7
8
9
// 插入操作
void Insert(LinkedList L, int i, ElemType e) {
LNode *p = GetElem(L, i-1); // 查找i的前驱结点
while (p) {
LNode *q = new LNode;
q->next = p->next;
p->next = q;
}
}
删除操作
1
2
3
4
5
6
7
8
9
// 删除操作
void Delete(LinkedList L, int i) {
LNode *p = GetElem(L, i-1); // 查找i的前驱结点
while (p) {
LNode *q = p->next;
p->next = q->next;
delete q;
}
}
双链表结构体定义
1
2
3
4
5
6
// 双链表结构体
typedef struct DLNode {
ElemType data;
struct DLNode *prev;
struct DLNode *next;
} DLNode, *DLinkedList;
所有代码
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
using namespace std;
typedef int ElemType;
// 单链表结构体
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkedList;
// 头插法
LinkedList HeadInsert(LinkedList &L) {
int x;
L = new LNode; // 创建头结点
L->next = NULL; // 初始化为空链表
while (cin >> x && x != -1) { // 输入-1表示结束
LNode *s = new LNode;
s->data = x;
s->next = L->next;
L->next = s;
}
return L;
}
// 尾插法
LinkedList TailInsert(LinkedList &L) {
int x;
L = new LNode; // 创建头结点
L->next = NULL; // 初始化为空链表
LNode *r = L; // r为表尾结点
while (cin >> x && x != -1) { // 输入-1表示结束
LNode *s = new LNode;
s->data = x;
r->next = s;
r = s;
}
return L;
}
// 按序号查找结点值
LNode *GetElem(LinkedList L, int i) {
int j = 1; // 计数器
LNode *p = L->next; // p为第1个结点指针
if (i < 0) return NULL; // i无效，返回NULL
if (i == 0) return L; // i=0，返回表头
while (p && j < i) { // 查找第i个结点
p = p->next;
j++;
}
return p; // 返回第i个结点的指针，若i>表长，返回NULL
}
// 按值查找表结点
LNode *LocateElem(LinkedList L, ElemType e) {
LNode *p = L->next;
while (p && p->data != e) { // 从第1个结点查找数据为e的结点
p = p->next;
}
return p;
}
// 插入操作
void Insert(LinkedList L, int i, ElemType e) {
LNode *p = GetElem(L, i-1); // 查找i的前驱结点
while (p) {
LNode *q = new LNode;
q->next = p->next;
p->next = q;
}
}
// 删除操作
void Delete(LinkedList L, int i) {
LNode *p = GetElem(L, i-1); // 查找i的前驱结点
while (p) {
LNode *q = p->next;
p->next = q->next;
delete q;
}
}
// 双链表结构体
typedef struct DLNode {
ElemType data;
struct DLNode *prev;
struct DLNode *next;
} DLNode, *DLinkedList;
