直接插入排序

本文为了方便理解,先上代码再做解释

插入排序代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void InsertSort(int R[], int n)
{
int i,j, temp;
for(i = 1; i<n; i++)
{
temp = R[i];
j = i-1;
while(j >= 0 && temp < R[j])
{
R[j+1] = R[j];
j--;
}
R[j+1] = temp;
}

}

解释

算法思想

每趟将一个待排序的关键字按其值的大小插入到已经排好的部分有序序列的适当位置上,直到所有的待派关键字都被插入到有序序列中

举例

有一原始序列:

{49, 38, 65, 97, 76, 13, 27, 49}

  • 一开始看49,一个数显然有序

    49 38 65 97 76 13 27 49

  • 插入38。38 < 49 ,所以49向后移动一个位置,38插入到49原来位置

    49 38 65 97 76 13 27 49

  • 插入65。65 > 49,所以不需要移动,65应该在就应该在49后

    38 49 65 97 76 13 27 49

  • 插入97。 97 > 65,所以不需要移动,97就应该在65之后

    38 49 65 97 76 13 27 49

  • 插入76。76 < 97,所以97向后移动一个位置;继续比较,76 > 65,65不需要移动,76应该插入65之后、97之前

    38 49 65 76 97 13 27 49

  • ……

  • 最后插入49,从后向前比较,直到49 = 49 < 65,位置确定,49应该插在49之后65之前

    13 27 38 49 49 65 76 97

链栈的操作

链栈的定义

1
2
3
4
5
6
7
8
9
#include <iostream>
using namespace std;

//链栈,理论上只要内存够大不存在上溢,只存在下溢(栈空后继续取出元素)
typedef struct _QNode
{
int data;
struct _QNode *next;
}StNode;

链栈的操作

初始化

1
2
3
4
5
6
7
bool initStack(StNode* &st)
{
st = new StNode;
if(!st) return false;
st->next = NULL;
return true;
}

判断栈空

1
2
3
4
5
6
7
bool isEmpty(StNode *st)
{
if(st->next == NULL)
return true;
else
return false;
}

入栈

1
2
3
4
5
6
7
8
9
10
11
12
13
bool pushStack(StNode* &st, int e)
{

StNode *node = new StNode;
if(!node) return false;


node->data = e;
node->next = st->next;
st->next = node;

return true;
}

出栈

1
2
3
4
5
6
7
8
9
10
11
12
bool popStack(StNode* &st, int &e)
{
if(!(st->next)) return false; //栈空
StNode *p;
p = st->next;

e = p->data;
st->next = p->next;
delete p;

return true;
}

顺序栈的操作

栈的定义

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#define MAXSIZE 1000

using namespace std;

//顺序栈
typedef struct
{
int data[MAXSIZE]; //存放栈顶元素
int top; //栈顶指针
}SqStack;

栈的操作

初始化

1
2
3
4
5
6
//初始化顺序栈
bool initStack(SqStack &st)
{
st.top = -1;
return true;
}

判断为空

1
2
3
4
5
6
7
8
//判断栈是否为空
bool isEmpty(SqStack st)
{
if(st.top == -1)
return true;
else
return false;
}

入栈

1
2
3
4
5
6
7
8
9
bool pushStack(SqStack &st, int e)
{
if(st.top == MAXSIZE - 1)
return false; //栈已满,再入栈会上溢
//对于入栈,一定要先改指针再入
st.top++;
st.data[st.top] = e;
return true;
}

出栈

1
2
3
4
5
6
7
8
9
10
11
bool popStack(SqStack &st, int &e)
{
if(st.top == -1)
return false; //栈空不能继续出栈,否则下溢

//对于出栈,先出元素再取指针
e = st.data[st.top];
st.top--;

return true;
}

获取栈顶元素

1
2
3
4
5
6
7
8
//获取栈顶元素
bool getStackTopElem(SqStack st, int &e)
{
if(st.top == -1)
return false; //栈空,无元素返回
e = st.data[st.top];
return true;
}

Linux内核链表之共享双链表

说明

共享双链表意义在于,可以用一套函数维护不同数据类型的双链表

准备

定义双链表

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <string>

using namespace std;

//此处并不包含数据域,仅有指针域用于连接结点
typedef struct _DbLinkList
{
struct _DbLinkList *next;
struct _DbLinkList *prev;
}DbLinkList;

定义结构体

1
2
3
4
5
6
7
8
9
10
11
12
//定义数据类型,并挂载双链表的指针
struct num
{
int data;
DbLinkList node; //此处不用指针,以保证在为该结构体分配内存时同时为双链表分配
};

struct str
{
string data;
DbLinkList node; //此处不用指针,以保证在为该结构体分配内存时同时为双链表分配
};

操作

初始化

1
2
3
4
5
6
7
//因为在保存数据的结构体中未用双链表的指针,所以此处L使用引用而非引用类型的指针
bool initList(DbLinkList &L)
{
L.next = NULL;
L.prev = NULL;
return true;
}

尾插法

1
2
3
4
5
6
7
8
9
10
11
12
bool insertBack(DbLinkList &L, DbLinkList &node)
{
DbLinkList *p = &L;

while(p->next) p = p->next;

node.next = NULL;
p->next = &node;
node.prev = p;

return true;
}

实际操作

对于struct num

main函数

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
int main()
{

num *N = new num;
N->data = -1;

initList(N->node);

//尾插法
num *n = new num;
n->data = 2;
insertBack(N->node, n->node);

//用链表访问结点的数据
DbLinkList *p = &(N->node);
while(p)
{
//获取在结构体中node距离结构体顶点的距离
int offset = offsetof(num, node);
/*
* data地址 = 结构体底地址 - node距离结构体顶点的距离
* 但指针不能直接加减,所以要先转化为size_t类型,得到结果后再转为指针类型
*/
num *tmp = (num *)((size_t)p - offset);
cout << "NUM:" << tmp->data << endl;
p = p->next;
}

return 0;
}

输出结果

1
2
NUM:-1
NUM:2

对于struct str

同理

main函数

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
int main()
{
str *S = new str;
S->data = "hello,world";

initList(S->node);

//尾插法
str *s = new str;
s->data = "你好,世界";
insertBack(S->node, s->node);

//用链表访问结点的数据
DbLinkList *p = &(S->node);
while(p)
{
//获取在结构体中node距离结构体顶点的距离
int offset = offsetof(str, node);
/*
* data地址 = 结构体底地址 - node距离结构体顶点的距离
* 但指针不能直接加减,所以要先转化为size_t类型,得到结果后再转为指针类型
*/
str *tmp = (str *)((size_t)p - offset);
cout << "STR:" << tmp->data << endl;
p = p->next;
}

return 0;
}

输出结果

1
2
STR:hello,world
STR:你好,世界

(注意:本文没有做双链表的销毁操作,虽然程序可以正常运行但这样做是不可取的)

思考

能不能将不同类型的结构体都放在一个双链表上?

如果能该怎么读取数据?

栈的概念及性质

栈的基本概念

栈的定义

栈是一种只能在一端进行插入或删除的线性表。其中插入被称作进栈,删除被称作出栈

允许进行插入或删除操作的一端被称为栈顶,另一段被称为栈底,栈底固定不变。其中,栈顶由一个称为栈顶指针的位置指示器来指示。

(PS:栈顶指针并非传统意义上的指针,比如顺序栈用的是一个整型变量来指示,但是我们依然称其为栈顶指针)

栈的特点

  • 先进后出

栈的数学结构

当n个元素以某种顺序进栈,并且在满足先进后出的前提下可任意时刻出栈,所获得的元素排列数目满足函数 Catalan( )的计算,即:

当然你也可以得到化简形式

栈的储存结构

  • 顺序栈
  • 链栈

(PS:栈是一种稍加限制的线性表,因此顺序栈与链栈就类似于顺序表和链表)

双链表的操作

双链表的代码定义

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
using namespace std;

typedef struct _DLNode
{
int data; //结点数据域
struct _DLNode *next; //指向后继的指针
struct _DLNode *prev; //指向前驱的指针

}DbLinkNode,DbLinkList;

双链表的操作

初始化双链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//初始化双链表
bool initDbLinkList(DbLinkList* &L)
{
L = new DbLinkNode;

//合法性检查,检查内存是否分配成功
if(!L) return false;

L->next = NULL;
L->prev = NULL;
L->data = -1;

return true;
}

插入

前插法

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
//前插法
bool DbListInsertFront(DbLinkList* &L, DbLinkNode *node)
{
//合法性检查
if(!L || !node) return false;

// if(L->next == NULL)
// {
// //若只有头结点,则在头结点后面插入一个结点
// node->next = NULL;
// node->prev = L;
// L->next = node;
// }
// else
// {
// //若有多个结点,则在头结点与其后结点之间插入
// L->next->prev = node; //令第二结点指向前驱的指针指向node
// node->next = L->next;
// node->prev = L;
// L->next = node;
// }

//优化
if(L->next) L->next->prev = node;
node->next = L->next;
node->prev = L;
L->next = node;

return true;
}

尾插法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//尾插法
bool DbListInsertBack(DbLinkList* &L, DbLinkNode *node)
{
//合法性检查
if(!L || !node) return false;

DbLinkNode *p = L;

//找到尾结点
while(p->next)
{
p = p->next;
}

node->next = NULL;
node->prev = p;
p->next = node;

return true;
}

任意位置插入

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
//任意位置插入
/* 参数: 插入的双向链表, 插入位置, 插入结点数据域的值*/
bool DbListInsert(DbLinkList* &L, int i, int &e)
{
//若链表为空未初始化,返回false
if(!L) return false;

//若只有头结点,但插入位置不等于1,则返回false
if((!L->next && i != 1) || i < 1) return false;

int j = 0;
DbLinkList *p = L, *s;

while(p && j < i)
{
//找查位置为i的结点
p = p->next;
j++;
}

if(!p || j != i)
{
cout << "不存在结点" << i << endl;
return false;
}

cout << "p: " << p << endl;

s = new DbLinkNode; //生成新的结点
s->data = e;

s->next = p;
s->prev = p->prev;
p->prev->next = s;
p->prev = s;

return true;
}

双链表的遍历输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//双向链表的遍历输出
void printDbList(DbLinkList *L)
{
//检查链表是否为空
if(!L)
{
cout << "链表为空" << endl;
return;
}

DbLinkList *p = L;
p = p->next;

while(p)
{
cout << p->data << endl;
p = p->next;
}

}

元素删除与双链表的销毁

本部分操作与单链表一致,请参考《单链表的操作

顺序表应用——逆置问题

顺序表应用——逆置问题

问题描述

给定一个顺序表,将其中的元素逆置

例子

给定一个顺序表,其中有0至10共11个元素从小至大排列,请将这11个元素逆置使其从大到小排列

以下是解题代码

代码

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
#include <iostream>
#define MAXSIZE 100

typedef struct{
int data[MAXSIZE];
int length;
}Sqlist;

//输出元素
void printList(Sqlist L)
{
for(int n = 0; n <= 10; n++)
{
std::cout << L.data[n] << std::endl;
}
}

//置换
void swapList(Sqlist &L)
{
for(int j = 0, k = 10; j < k; j++, k--)
{
int temp = L.data[j]; //临时变量用于临时存放j位置数据
L.data[j] = L.data[k];//将k位置的保存到j位置
L.data[k] = temp; //将k位置的替换为原j位置的值
}

}


int main()
{
Sqlist L;

//线性表初始化
L.length = 0;

//插入元素
for(int i = 0; i <= 10;i++)
{
L.data[i] = i;
L.length++;

}

//输出置换前的顺序表内容用于对比
std::cout << "置换前的数据:"<< std::endl;
printList(L);

//置换
swapList(L);

//输出置换后的内容
std::cout << "置换后的数据:" << std::endl;
printList(L);

system("pause");
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
置换前的数据:
0
1
2
3
4
5
6
7
8
9
10
置换后的数据:
10
9
8
7
6
5
4
3
2
1
0

循环链表应用——约瑟夫置换

约瑟夫问题

介绍

约瑟夫问题,又称约瑟夫置换丢手绢问题

一般形式

(本部分内容来自百度百科

约瑟夫问题是个有名的问题:N个人围成一圈,从第一个开始报数,第M个将被杀掉,最后剩下一个,其余人都将被杀掉。例如N=6,M=5,被杀掉的顺序是:5,4,6,2,3。

代码

问题描述

本文以以下问题为例

编号为1-10的10 个人围成一圈,从第一个开始报数,第9个被淘汰出圈,剩下的组成新的圈。依次这样下去,求最后一个人的编号

解决

注意:该段代码与上篇文章——《 循环链表定义及操作 》相接

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
//解答约瑟夫问题
bool Joseph(LinkList* &L, int interval)
{
LinkList *p = L, *q;
int i = 0, j = 0;
int times = 0; //当前轮数
int num = 0;

if(!L || p->next == L)
{
cout << "链表为空\n";
return false;
}

if(interval < 1)
{
cout << "报数淘汰口令不能小于1\n";
return false;
}

do{

i += interval;

//找查第i个结点,p指向该结点的上一个结点
while(p->next){
if(p->next != L)
{
//如果不是头结点的话
j++;
}
if(j >= i) break;
p = p->next;

}
times++;
q = p->next; //临时保存被删结点以备释放空间
num = q->data;

cout << "当前结点:" << q->data
<< " 上一个结点:" << p->data
<<" 下一个结点:" << q->next->data
<< endl;
p->next = q->next;
delete q; //释放被删除结点内存
LinkListPrint(L);
}while(L->next != L); //链表不为空,继续报数

cout << "最后一个出圈者的编号" << num << endl;

return true;
}

完整代码

代码

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
#include <iostream>
#include <string>

using namespace std;


typedef struct _LinkNode
{
int data;
struct _LinkNode *next;
}LinkList;

bool InitList(LinkList* &L)
{
L = new LinkList;

if(!L) return false;

L->next = L;
L->data = 0;

return true;
}

bool ListInsert_back(LinkList* &L, LinkList *node)
{
LinkList *last = NULL;
if(!L || !node) return false;

if(L == L->next)
{
//头结点指针指向了自己(链表只有头结点)
node->next = L;
L->next = node;
}else{
//非空的循环链表
last = L->next;
//寻找尾结点(指向头结点的结点)
while(last->next != L)
{
last = last->next;
}

node->next = L;
last->next = node;
}
return true;
}

void LinkListPrint(LinkList *L)
{
LinkList *p;
if(!L || L == L->next)
{
cout << "链表为空\n";
return;
}

p = L->next;

while(p != L)
{
cout << p->data << "\t";
p = p->next;
}


cout << endl;
}

//解答约瑟夫问题
bool Joseph(LinkList* &L, int interval)
{
LinkList *p = L, *q;
int i = 0, j = 0;
int times = 0; //当前轮数
int num = 0;

if(!L || p->next == L)
{
cout << "链表为空\n";
return false;
}

if(interval < 1)
{
cout << "报数淘汰口令不能小于1\n";
return false;
}

do{

i += interval;

//找查第i个结点,p指向该结点的上一个结点
while(p->next){
if(p->next != L)
{
//如果不是头结点的话
j++;
}
if(j >= i) break;
p = p->next;

}
times++;
q = p->next; //临时保存被删结点以备释放空间
num = q->data;

cout << "当前结点:" << q->data
<< " 上一个结点:" << p->data
<<" 下一个结点:" << q->next->data
<< endl;
p->next = q->next;
delete q; //释放被删除结点内存
LinkListPrint(L);
}while(L->next != L); //链表不为空,继续报数

cout << "最后一个出圈者的编号" << num << endl;

return true;
}

int main()
{
LinkList *L, *s;
int i = 0;
if(InitList(L))
{
cout << "创建一个空的循环链表\n";
}else{
exit(-1);
}

cout << "尾插10个元素...\n";

while((++i)<=10)
{
s = new LinkList;
s->data = i;
s->next = NULL;
if(ListInsert_back(L, s))
{
cout << "success\n";
}else{cout << "default\n";}
}

LinkListPrint(L);

Joseph(L,9);

return 0;

}

输出结果

注: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
创建一个空的循环链表
尾插10个元素...
success
success
success
success
success
success
success
success
success
success
1 2 3 4 5 6 7 8 9 10
当前结点:9 上一个结点:8 下一个结点:10
1 2 3 4 5 6 7 8 10
当前结点:8 上一个结点:7 下一个结点:10
1 2 3 4 5 6 7 10
当前结点:10 上一个结点:7 下一个结点:0
1 2 3 4 5 6 7
当前结点:2 上一个结点:1 下一个结点:3
1 3 4 5 6 7
当前结点:5 上一个结点:4 下一个结点:6
1 3 4 6 7
当前结点:3 上一个结点:1 下一个结点:4
1 4 6 7
当前结点:4 上一个结点:1 下一个结点:6
1 6 7
当前结点:1 上一个结点:0 下一个结点:6
6 7
当前结点:6 上一个结点:0 下一个结点:7
7
当前结点:7 上一个结点:0 下一个结点:0
链表为空
最后一个出圈者的编号7

循环链表定义及操作

循环链表定义

定义与单链表一样,操作时将末结点的指针指向开始结点即可

1
2
3
4
5
typedef struct _LinkNode
{
int data;
struct _LinkNode *next;
}LinkList;

循环链表操作

初始化循环链表

1
2
3
4
5
6
7
8
9
10
11
bool InitList(LinkList* &L)
{
L = new LinkList;

if(!L) return false;

L->next = L;
L->data = 0; //往头结点塞个数据,这时候严格来讲为无头结点循环链表,第一个结点应该叫开始结点

return true;
}

插入(尾插)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool ListInsert_back(LinkList* &L, LinkList *node)
{
LinkList *last = NULL;
if(!L || !node) return false;

if(L == L->next)
{
//头结点指针指向了自己(链表只有头结点)
node->next = L;
L->next = node;
}else{
//非空的循环链表
last = L->next;
//寻找尾结点(指向头结点的结点)
while(last->next != L)
{
last = last->next;
}

node->next = L;
last->next = node;
}
return true;
}

输出数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void LinkListPrint(LinkList *L)
{
LinkList *p;
if(!L || L == L->next)
{
cout << "链表为空\n";
return;
}

p = L->next;

while(p != L)
{
cout << p->data << "\t";
p = p->next;
}


cout << endl;
}

单链表的操作

单链表代码定义

1
2
3
4
5
typedef struct LinkNode
{
int data; //data存放结点的数据域(以int类型为例)
struct LinkNode *next; //结点的指针域
}LinkNode, LinkList;

单链表的操作

初始化单链表

1
2
3
4
5
6
7
8
9
bool initList(LinkList* &L)			//L类型为引用类型的指针
{
L = new LinkNode; //为L分配一个动态内存
if(!L) return false; //若分配失败则返回false

//头结点指针指向空完成初始化,成功创建一个空的单链表并返回true
L->next = NULL;
return true;
}

插入结点

注: L为插入的单链表,node为将要插入的结点

前插法

1
2
3
4
5
6
7
8
bool ListInsert_front(LinkList* &L, LinkNode *node)
{
//合法性检查
if(!L || !node) return false;

node->next = L->next; //把新结点指针指向原来头结点所指向的结点
L->next = node; //把头结点指向新结点
}

尾插法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool ListInsert_back(LinkList* &L, LinkList *node)
{
LinkNode *last = NULL;
if(!L || !node) return false;

last = L;

//找到尾结点
while(last->next) last = last->next;

//重置指针
node->next = NULL;
last->next = node;

return true;
}

任意位置插入

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
//任意位置插入
/*
* 参数: 要插入的单链表, 位置, 取值
*/
bool LinkInsert(LinkList* &L, int i, int &e)
{
if(!L) return false;

int j = 0;
LinkList *p, *s;
p = L;

//让p寻找插入位置
while(p && j<i-1)
{
p = p->next;
j++;
}

//如果插入位置大于链表节点数,最后p为空
//有一种情况为:若i <= 0 ,j<i-1不成立,但此时p为真,所以这里使用 !p || j>i-1
if(!p || j>i-1)
{
return false;
}

//当i = 0时,p为真且 j = i - 1, 此时指向头结点,直接来到下方这一步

s = new LinkNode; //生成新结点
//连接结点
s->data = e; //保存数据
s->next = p->next;
p->next = s;

return true;
}

输出单链表中的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void LinkPrint(LinkList* &L)
{
LNode *p = NULL;
if(!L)
{
cout << "此链表为空\n";
return;
}

p = L->next;

while(p)
{
cout << p->data << "\t";
p = p->next;
}
cout << endl;
}

元素找查

按位置查找

与任意位置插入类似,只不过要注意访问头结点的情况(带头结点的单链表头结点数据域无初始化数据)

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
/*
* 参数: 单链表, 位置, 取值
*/
bool GetLinkListElemAsAddress(LinkList* &L, int i, int &e)
{
if(!L || !L->next) return false;

int j = 0;
LinkList *p;
p = L;

while(p && j < i-1)
{
p = p->next;
j++;
}

if(!p || j >= i - 1) //这里取等号是为了避免访问头结点数据
{
return false;
}

e = p->data;

return true;
}

按值查找

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
/*
* 带头结点的单链表L中找查值为e的元素
* 参数:单链表, 取值, 返回所找元素的位置
*/
bool GetLinkListElemAsValue(LinkList *L, int e, int &index)
{
LinkList *p;
p = L->next;
index = 1;

if(!L || !L->next)
{
index = 0;
return false;
}

while(p && p->data! = e)
{
p = p->next;
index++;
}

if(!p)
{
index = 0;
return false; //查无此值
}
return true;
}

结点的删除

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
bool LinkListDel(LinkList* &L, int i)
{
LinkList *p, *q;
int index = 0;
p = L;

//合法性检查
if(!L || !L->next)
{
return false;
}

while((p->next) && (index < i-1))
{
p = p->next;
index++;
}

//删除位置不合理
if(!p->next || (index > i - 1))
{
return false;
}
q = p->next; //临时存放被删结点地址
p->next = q->next;//改变删除结点前驱指针域
delete q;
return true;

}

单链表的销毁

分配动态内存后,记得销毁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void LinkDestory(LinkList* &L)
{
//定义临时结点指向头结点
LinkList *p = L;

cout << "销毁链表" << endl;

//遍历并删除结点
while(p)
{
L = L->next;
delete p;
p = L;
}

}