SatParamita六到彼岸

诵持三藏经律论 勤修六度波罗蜜

数据结构-单链表

一般使用带头结点的单链表。有头结点,head->next是第一个数据。链表操作一般需要借助一两个中间指针,不直接操作传递的参数。函数内修改L的内容,函数参数则用隐式指针&L,取L的地址;不修改内容,只调用数据,函数参数则用L。对于使用了L->next;不需要&L,因为没有修改L,改的是L->next。

两种传参与调用

1
2
3
4
5
6
int InitList(SqList *L)
{
L->length = 0;
return 1;
}
InitList(&L);

隐式指针&L

1
2
3
4
5
6
int InitList(SqList &L)
{
L.length = 0;
return 1;
}
InitList(L);
1
2
3
4
5
6
7
int GetElem(LinkList L, int i, int *e)
{
////
*e = p->data; /* 取第i个元素的数据 */
return 1;
}
GetElem(L, 5, &e);
1
2
3
4
5
6
7
int GetElem(LinkList L, int i, int &e)
{
////
e = p->data; /* 取第i个元素的数据 */
return 1;
}
GetElem(L, 5, 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
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
// 车厢调度问题,用不带头结点的单链表描述站台结构
#include <iostream>
#include <cstring>
#include <stack>
using namespace std;

struct StackNode
{
int data;
struct StackNode *next;
};
typedef struct StackNode *Stack;

int InitStack(Stack &S)
{
S = NULL;
return 0;
}
int push(Stack &S, int data)
{
struct StackNode *p = new StackNode;
p->data = data;
p->next = S; //头插法
S = p;
return 0;
}
int top(const Stack &S)
{
return S->data; //出栈
}
void pop(Stack &S)
{
Stack p = S;
S = S->next;
delete p; //移除
}
int empty(const Stack &S)
{
return S == NULL; //返回0或1
}
int DestroyStack(Stack &S)
{
while (S != NULL)
{
Stack p = S;
S = S->next;
delete p;
}
//或者
//pop(S);
return 0;
}
int main()
{
int command, n = 1, m;
Stack S;
InitStack(S);
//先进后出
cout << "请输入进出栈命令: 0表示车厢进站;1表示车厢出站" << endl;
while (cin >> command)
{
if (command == 0)
{
if (push(S, n) != 0)
cout << "站台已满!" << endl;
else
{
cout << "车厢 " << n << " 运货进入站台。" << endl;
n++;
}
}
else if (command == 1)
{
if (empty(S))
cout << "站台上没有车厢!" << endl;
else
{
m = top(S);
pop(S);
cout << "车厢 " << m << " 运货出站。" << endl;
}
}
}
DestroyStack(S);
return 0;
}

线性表

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
88
89
90
91
92
93
94
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

typedef char DataType;
#define ListSize 10

typedef struct
{
DataType list[ListSize];
int length;
} SeqList;

void InitList(SeqList *L)
/*将线性表初始化为空的线性表只需要把线性表的长度length置为0*/
{
L->length = 0; /*把线性表的长度置为0*/
}
int ListEmpty(SeqList L)
/*判断线性表是否为空,线性表为空返回1,否则返回0*/
{
if (L.length == 0) /*判断线性表的长度是否为9*/
return 1; /*当线性表为空时,返回1;否则返回0*/
else
return 0;
}
int GetElem(SeqList L, int i, DataType *e)
/*查找线性表中第i个元素。查找成功将该值返回给e,并返回1表示成功;否则返回-1表示失败。*/
{
if (i < 1 || i > L.length) /*在查找第i个元素之前,判断该序号是否合法*/
return -1;

*e = L.list[i - 1]; /*将第i个元素的值赋值给e*/
return 1;
}
int LocateElem(SeqList L, DataType e)
/*查找线性表中元素值为e的元素,查找成功将对应元素的序号返回,否则返回0表示失败。*/
{
for (int i = 0; i < L.length; i++) /*从第一个元素开始比较*/
if (L.list[i] == e)
return i + 1;
return 0;
}
int InsertList(SeqList *L, int i, DataType e)
/*在顺序表的第i个位置插入元素e,插入成功返回1,如果插入位置不合法返回-1,顺序表满返回0*/
{
if (i < 1 || i > L->length + 1) /*在插入元素前,判断插入位置是否合法*/
{
printf("插入位置i不合法!\n");
return -1;
}
else if (L->length >= ListSize) /*在插入元素前,判断顺序表是否已经满,不能插入元素*/
{
printf("顺序表已满,不能插入元素。\n");
return 0;
}
else
{
for (int j = L->length; j >= i; j--) /*将第i个位置以后的元素依次后移*/
L->list[j] = L->list[j - 1];
L->list[i - 1] = e; /*插入元素到第i个位置*/
L->length++; /*将顺序表长增1*/
return 1;
}
}
int DeleteList(SeqList *L, int i, DataType *e)
{
if (L->length <= 0)
{
printf("顺序表已空不能进行删除!\n");
return 0;
}
else if (i < 1 || i > L->length)
{
printf("删除位置不合适!\n");
return -1;
}
else
{
*e = L->list[i - 1];
for (int j = i; j <= L->length - 1; j++)
L->list[j - 1] = L->list[j];
L->length--;
return 1;
}
}
int ListLength(SeqList L)
{
return L.length;
}
void ClearList(SeqList *L)
{
L->length = 0;
}

头插法

有头结点的头插法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int InitStudentList(StudentList &L)
{
L = new StudentNode;
L->next = NULL;
return 0;
}
头插法,头结点不变,可以直接使用L->next,不需要引入中间指针。
int Insert(StudentList L, Student aStudent)
{
if (L == NULL)
return 1;
struct StudentNode *q = new StudentNode; // 创建结点
q->data = aStudent;
// 将结点插入指定结点的后面
q->next = L->next;
L->next = q;
return 0;
}

无头结点的头插法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int InitStudentList(StudentList &L)
{
L = NULL;
return 0;
}
//头插法,必须是&L,取址!L改变了!!
int Insert(StudentList &L, struct Student aStudent)
{
struct StudentNode *q = new StudentNode;
q->data = aStudent;
q->next = L; // 将新结点插入表头
L = q; //L还是头结点
return 0;
}

建立单链表

头插法建立单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
void CreateListHead(LinkList *L, int n)
{
*L = (LinkList)malloc(sizeof(Node)); //头结点
(*L)->next = NULL;

for (int i = 0; i < n; i++)
{
LinkList p = (LinkList)malloc(sizeof(Node)); // 生成新结点
p->data = i*i;
p->next = (*L)->next;
(*L)->next = p;
} // 从后往前生成结点,头结点往左运动。
}

尾插法建立单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void CreateListTail(LinkList *L, int n)
{
*L = (LinkList)malloc(sizeof(Node));
LinkList r = *L;

for (int i = 0; i < n; i++)
{
LinkList p = (Node *)malloc(sizeof(Node));
p->data = i*i;
r->next = p;
r = p; // r后移
}
r->next = NULL;
}

单链表基本操作

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
#include <stdio.h>
#include <string.h>
#include <malloc.h>

typedef struct Node
{
int data;
struct Node *next;
} ListNode, *LinkList;//单链表类型定义,一个是结点,一个是链表。

void InitList(LinkList L)
/*将单链表初始化为空。动态生成一个头结点,并将头结点的指针域置为空。*/
{
L = (LinkList)malloc(sizeof(ListNode));
L->next = NULL; //L->next 是第一个元素
}
/*在单链表中第i个位置插入一个结点,结点的元素值为e。插入成功返回1,失败返回0*/
int InsertList(LinkList L, int i, int e)
{
int j = 0;
ListNode *p = L; //指针p指向头结点
while (p->next != NULL && j < i - 1) //找到第i-1个结点,即第i个结点的前驱结点
{
p = p->next;
j++;
}
if (!p) //如果没找到,说明插入位置错误
{
printf("插入位置错");
return 0;
}
/*新生成一个结点,并将e赋值给该结点的数据域*/
ListNode *q = (ListNode *)malloc(sizeof(ListNode));
q->data = e;
/*插入结点操作*/
q->next = p->next;
p->next = q;
return 1;
}
//借助新指针p计算长度,不然链表指针L会指向结尾。
int ListLength(LinkList L)
{
int count = 0;
ListNode *p = L;
while (p->next != NULL)//L->next 是第一个元素
{
p = p->next;
count++;
}
return count;
}
int ListEmpty(LinkList L)
{
if (L->next == NULL) //L->next 是第一个元素
return 1; /*当单链表为空时,返回1;否则返回0*/
else
return 0;
}

ListNode *Get(LinkList L, int i)
/*查找单链表中第i个结点。查找成功返回该结点的指针表示成功;否则返回NULL表示失败。*/
{
if (ListEmpty(L)) /*在查找第i个元素之前,判断链表是否为空*/
return NULL;
if (i < 1) /*在查找第i个元素之前,判断该序号是否合法*/
return NULL;

ListNode *p = L;
int j = 0;
while (p->next != NULL && j < i)
{
p = p->next;
j++;
}
if (j == i)
return p; /*找到第i个结点,返回指针p*/
else
return NULL; /*如果没有找到第i个元素,返回NULL*/
}

void DisplayList(LinkList L) /*输出链表*/
{
int n = ListLength(L);
for (int i = 1; i <= n; i++) /*输出单链表L中的每个元素*/
{
ListNode *p = Get(L, i); /*返回单链表L中的每个结点的指针*/
if (p)
printf("%d\t", p->data); /*输出单链表L中的每个元素*/
}
}
void PrintList(LinkList L) // 输出链表上各结点的数据
{
printf("链表上各结点的数据为:\n");
for (LinkList p = L->next; p != NULL; p = p->next)
printf("%d ", p->data);
printf("\n");
}
/*逆置链表*/
void ReverseList(LinkList L)
{
ListNode *p = L->next; /*p指向链表的第一个结点*/
L->next = NULL;
while (p) /*利用头插法将结点依次插入到链表的头部*/
{
ListNode *q = p->next;
p->next = L->next;
L->next = p;
p = q;
}
}

ListNode *LocateElem(LinkList L, int e)
/*查找线性表中元素值为e的元素,查找成功将对应元素的结点指针返回,否则返回NULL表示失败。*/
{
ListNode *p = L->next; /*指针p指向第一个结点*/
while (p)
{
if (p->data != e) /*找到与e相等的元素,返回该序号*/
p = p->next;
else
break;
}
return p;//查找成功将对应元素的结点指针返回,否则返回NULL表示失败。
}
int LocatePos(LinkList L, int e)
/*查找线性表中元素值为e的元素,查找成功将对应元素的序号返回,否则返回0表示失败。*/
{
if (ListEmpty(L)) /*在查找第i个元素之前,判断链表是否为空*/
return 0;

ListNode *p = L->next; /*指针p指向第一个结点*/
int i = 1;
while (p)
{
if (p->data == e) /*找到与e相等的元素,返回该序号*/
return i;
else
{
p = p->next;
i++;
}
}
if (!p) /*如果没有找到与e相等的元素,返回0,表示失败*/
return 0;
return 0;
}

int DeleteList(LinkList L, int i, int *e)
/*删除单链表中的第i个位置的结点。删除成功返回1,失败返回0*/
{
int j = 0;
ListNode *pre = L;
while (pre->next != NULL && pre->next->next != NULL && j < i - 1) /*判断是否找到前驱结点*/
{
pre = pre->next;
j++;
}
if (j != i - 1) /*如果没找到要删除的结点位置,说明删除位置错误*/
{
printf("删除位置错误");
return 0;
}
/*指针p指向单链表中的第i个结点,并将该结点的数据域值赋值给e*/
ListNode *p = pre->next;
*e = p->data;
/*将前驱结点的指针域指向要删除结点的下一个结点,也就是将p指向的结点与单链表断开*/
pre->next = p->next;
free(p); /*释放p指向的结点*/
return 1;
}

void DestroyList(LinkList L)
{
ListNode *p = L, *q;
while (p != NULL)
{
q = p;
p = p->next;
free(q);
}
}
void MergeList(LinkList A, LinkList B, LinkList *C)
/*单链表A和B中的元素非递减排列,将单链表A和B中的元素合并到C中,C中的元素仍按照非递减排列*/
{
ListNode *pa, *pb, *pc; /*定义指向单链表A,B,C的指针*/
pa = A->next;
pb = B->next;
*C = A; /*将单链表A的头结点作为C的头结点*/
(*C)->next = NULL;
pc = *C;
/*依次将链表A和B中较小的元素存入链表C中*/
while (pa && pb)
{
if (pa->data <= pb->data)
{
pc->next = pa; /*如果A中的元素小于或等于B中的元素,将A中的元素的结点作为C的结点*/
pc = pa;
pa = pa->next;
}
else
{
pc->next = pb; /*如果A中的元素大于B中的元素,将B中的元素的结点作为C的结点*/
pc = pb;
pb = pb->next;
}
}
pc->next = pa ? pa : pb; /*将剩余的结点插入C中*/
free(B); /*释放B的头结点*/
}

int main()
{
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
LinkList L;
InitList(L);
for (int i = 1; i <= 10; i++) /*将数组a中元素插入到单链表L中*/
InsertList(L, i, a[i - 1]); //插入到第i个位置

PrintList(L);
DisplayList(L);
return 0;
}
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
struct List
{
int data;
struct List *next;
};
//创建表头的过程
struct List *createList()
{
struct List *headNode = (struct List *)malloc(sizeof(struct List));
headNode->next = NULL;
//headNode->data 表头特殊,不用数据域,作为差异性
return headNode; //可以返回头结点
}
//插入结点,头插法
void inserListByHead(struct List *headNode, int data)
{
//插入前首先得创建插入的结点
struct List *newNode = (struct List *)malloc(sizeof(struct List));
newNode->data = data;
//实现插入
newNode->next = headNode->next;
headNode->next = newNode;
}
//删除结点,指定位置删除
void deleteByAppoin(struct List *headNode, int data)
{
struct List *p = headNode;
struct List *q = headNode->next;
if (q == NULL)
{
printf("无可用数据,表空\n");
return;
}
while (q->data != data)
{

p = q;//后移
q = p->next; //也就是q->next;
if (q == NULL)
{
printf("未找到相关信息,无法删除\n");
return;
}
}
p->next = q->next;
free(q);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef struct node //定义结点结构
{
int data;
struct node *next;
} LNode, *LinkList; // 结点类型名LNode,指针类型名LinkList

//尾插法
void CreateListRear(LinkList L, int n) /* L为带头结点空链表,且头结点已存在。*/
{
LinkList p = L; //指针p指向头结点;
for (int i = 0; i < n; i++)
{
LinkList q = (LinkList)malloc(sizeof(LNode));
q->data = i * i;
p->next = q; // 将新节点q作为p的后继;
p = q; //让p指向新的表尾结点q;
}
p->next = NULL; // p的next域赋值为NULL
}

头插法;插入到头结点后面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct studentCard *insertLink(struct studentCard *head, int number, struct studentCard *node)
{
struct studentCard *p = head;
if (p == NULL)
printf("该链表为空");
while (p)
{
if (p->cardnum == number)
{
node->next = p->next; //插到p后面
p->next = node;
break;
}
else
p = p->next;
}
return head; //仍然返回头结点
}

删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct studentCard *deleLink(struct studentCard *head, int number)
{
struct studentCard *p = head;
if (p->cardnum == number) //如果删除的是头结点
{
head = p->next;
free(p);
}
//删除的不是头结点
struct studentCard *q = p->next;
while (q->cardnum != number && q->next != NULL)
{
p = q;
q = q->next;
}
if (q->cardnum == number)
{
p->next = q->next;
free(q);
}
return head;
}

链表管理学生的借书卡信息

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
struct studentCard
{
int cardnum;
char studentname[10];
struct studentCard *next;
};
int main(void)
{
int i = 0, number;
char name[10];
struct studentCard *head = NULL, *p;
printf("输入10个学生的借书卡信息:\n卡号\t姓名\n");
while (i < 3)
{
scanf("%d%s", &number, name);
p = (struct studentCard *)malloc(sizeof(struct studentCard));
p->cardnum = number;
strcpy(p->studentname, name);
p->next = head; //头插法
head = p;
i++;
}
printf("\n输出学生借书卡信息\t\n卡号\t姓名\n");
while (p)
{
printf("%d\t%s\n", p->cardnum, p->studentname);
p = p->next;
}
return 0;
}

链表的插入排序

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
void InsertSort(LinkList L)
{
ListNode *p = L->next;
L->next = NULL; /*初始时,已排序链表为空*/
while (p != NULL) /*p是指向待排序的结点*/
{
if (L->next == NULL) /*如果*p是第一个结点,则插入到L,令已排序的最后一个结点的指针域为空*/
{
L->next = p;
p = p->next;
L->next->next = NULL;
}
else /*p指向待排序的结点,在L指向的已经排好序的链表中查找插入位置*/
{
ListNode *pre = L;
ListNode *q = L->next;
while (q != NULL && q->data < p->data) /*在q指向的有序表中寻找插入位置*/
{
pre = q;
q = q->next;
}
q = p->next; /*q指向p的下一个结点,保存待排序的指针位置*/
p->next = pre->next; /*将结点*p插入到结点*pre的后面*/
pre->next = p;
p = q; /*p指向下一个待排序的结点*/
}
}
}

对链表L排序

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
void ListOrder(LinkList L)
{
ListNode *p, *r, *t, *q;
p = L->next; /*p是指向待排序的结点的第一个结点*/
L->next = NULL; /*初始时,已排序链表为空*/
while (p != NULL) /*如果待排序链表不为空*/
{
if (L->next == NULL) /*如果是第一个结点,则作为第一个结点插入L*/
{
L->next = p;
r = p->next;
p->next = NULL;
p = r;
}
else /*p指向待排序的结点,在L指向的已经排好序的链表中查找插入位置*/
{
r = L;
q = L->next;
while (q != NULL && p->data > q->data) /*在q指向的有序表中寻找插入位置*/
{
r = q;
q = q->next;
}
t = p->next; /*t指向p的下一个结点,保存待排序的指针位置*/
p->next = r->next; /*将结点*p插入到结点*r的后面*/
r->next = p;
p = t; /*p指向下一个待排序的结点*/
}
}
}

双链表,环

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
typedef struct DualNode
{
char data;
struct DualNode *prior;
struct DualNode *next;
} DualNode, *DuLinkList;

int InitList(DuLinkList *L)
{
*L = (DuLinkList)malloc(sizeof(DualNode));
(*L)->next = (*L)->prior = NULL;

DualNode *p = *L;

for (int i = 0; i < 26; i++)
{
DualNode *q = (DualNode *)malloc(sizeof(DualNode));
q->data = 'A' + i;

q->next = p->next;
p->next = q;
q->prior = p;
p = q;
}
p->next = (*L)->next; //环
(*L)->next->prior = p;
return OK;
}
InitList(&L);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
typedef struct node
{
int data;
struct node *next;
} sqlist, *linklist;

linklist CreateLinkList()
{
linklist head = NULL;
linklist r = head;
for (int i = 1; i <= CardNumber; i++)
{
linklist s = (linklist)malloc(sizeof(sqlist));
s->data = 0;
if (head == NULL)
head = s;
else //尾插法
r->next = s;
r = s;
}
r->next = head; //形成环
return head;
}

利用快慢指针的方法判断是否循环链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int HasLoop2(LinkList L)
{
int step1 = 1;
int step2 = 2;
LinkList p = L;
LinkList q = L;

while (p != NULL && q != NULL && q->next != NULL)
{
p = p->next;
if (q->next != NULL)
q = q->next->next;
printf("p:%d, q:%d \n", p->data, q->data);
if (p == q)
return 1;
}
return 0;
}
0%