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

约瑟夫问题

介绍

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

一般形式

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

约瑟夫问题是个有名的问题: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;
}

}

算法题——Cantor表

题目介绍

描述

现代数学的著名证明之一是 Georg Cantor 证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的:

1/1, 1/2 , 1/3, 1/4, 1/5, …

2/1, 2/2, 2/3, 2/4, …

3/1, 3/2, 3/3, …

4/1, 4/2, …

5/1, …

我们以Z字形给表上每一项编号。第一项是1/1,然后是1/2, 2/1, 3/1, 2/2, …

输入格式

整数N(1<= N <=10^7)

输出格式

表中的第N项

样例

输入:

1
7

输出:

1
1/4

分析

规律

我们通过题目可知,在Cantor表中走法为Z字形

不妨将Cantor表转化为下图

Cantor

从左往右数

奇数行分母依次递增,分子依次递减

偶数行分母依次递减,分子依次递增

可知奇偶数行分子分母规律正好相反

所以为使奇偶数行变化规律一致并且符合题中所给的项数规律,我们可以规定

在上图中,奇数行从左往右数,偶数行从右往左数

找查

例如我们要找查第7项,前三行一共有6项,前4行一共有10项

很显然 6 < 7 < 10

所以我们可以很方便地确定第7项在第4行

前几行项数 - 所要找的项数 = 所要找的项所在行的最后一项分子 - 所找项分子

同理

前几行项数 - 所要找的项数 = 所找项分母 - 所找项所在行最后一项分母

这两个等式中我们分别知道任意三个量就可以求其中的第四个量

然后,我们继续根据规律确定第7项的具体的值为 1/4

最后,我们可以轻易得出求任意项的算法如下

解法

以下是笔者的解题方法

先上代码

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
#include <iostream>
using namespace std;

int main()
{
int n = 0, sum = 0, i = 1;
cin >> n;

while(sum < n)
{
++i; //这里一定要让i先自增再求和,否则求出来的和少一项(此处的项指的是等差数列的项)
sum = i*(i - 1)/2; //首项公差均为1的等差数列求和,此处的和为第i行为止的Cantor表的总项数
}

//总项数与所找项的项数的差
int dif = sum - n;

if((i - 1) % 2 != 0)
//如果i-1行为奇数,那么i行为偶数行,偶数行从右开始数(这里在写的时候绕了个弯)
cout << 1 + dif << "/" << i - 1 - dif;
else
//第i行为奇数行,从左边数
cout << i - 1 -dif << "/" << 1 + dif;

}

链表的定义

链表

链表的概念

定义链表是一种物理存储单元上非连续、非顺序的存储结构,由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。

在链表的储存上,每个结点不仅包含所存的元素信息,还包含元素间的逻辑信息

链表的特性

  • 不支持随机访问不能通过知道第一个元素的地址(即储存空间的首地址)可以轻松访问储存的所有数据。
  • 节点的储存空间利用率相对顺序表较低:链表中的每分一个结点需要划出一部分空间来储存指向下一个结点位置指针
  • 支持储存空间的动态分配:链表中当前结点的位置是由其前驱结点中的地址信息所指示的。其结点可以散落在内存中的任意位置,且不需要一次性地划分所有结点所需的空间给它。
  • 在链表中进行插入操作无需移动元素(而顺序表需要)

链表的形式

单链表

在每个结点除了包含的数据域外,还包含一个指针域,用以指向其后继结点。

  • 带头结点的单链表

带头结点的单链表中,头指针head指向头结点,头结点的值域不含任何信息,从头结点的后继结点开始储存信息。头指针head 始终不等于NULLhead->next等于NULL的时候,链表为空。

带头节点的单链表(图片来自网络)

  • 不带头结点的单链表

不带头结点的单链表中的头指针head直接指向开始结点,当head等于NULL时,链表为空。

不带头节点的单链表

双链表

双链表就是在单链表结点上增添了一个指针域,指向当前节点的前驱

相比于单链表,双链表能够从终端结点反向走到开始结点

双链表(图片源自网络)

循环链表

  • 循环单链表

只需要将单链表最后一个指针域(空指针)指向链表中的第一个结点即可。(如果循环单链表带头结点,则指向头结点;不带头结点,则指向开始结点)。

循环单链表可以实现从任何一个结点出发,访问链表中任何结点。(注意:此处应该区分与顺序表随机访问的特点。循环单链表指的是从一个结点出发,而不是知道一个结点从而迅速找到任何一个结点,因此循环单链表不具有随机访问特性。)

带头结点的循环单链表,当head等于head->next时,链表为空;不带头结点的循环单链表,当head等于NULL时,链表为空。

  • 循环双链表

双链表终端节点的next指针指向链表中第一个结点,将链表中的第一个结点的prior指针指向终端结点。

不带头结点的循环双链表,head等于NULL,链表为空

带头结点的循环双链表是没有空指针的,其为空状态下,head->nexthead->prior必然都等于head,故一下四种语句都可判断为空

1
2
3
4
head->next == head;
head->prior == head;
head->next == head && head->prior == head;
head->next == head || head->prior == head;

静态链表

静态链表借助一维数组表示。

静态链表结点空间来自于一个结构体数组(一般链表结点空间来自整个内存),数组中每个结点含两个分量:

  • 数据元素分量data
  • 指针分量(指示了当前结点直接后继节点在数组中的位置)

注意:静态链表的指针不是通常所说储存内存地址的指针型变量,而是储存数组下标的整型变量,其功能类似于指针,故在此称为指针

顺序表与链表区别

基于空间比较

  • 储存的分配方式

顺序表储存空间时一次性分配的,链表的是多次分配的

  • 存储密度

(注: 存储密度 = 结点值域所占存储量/结点结构所占存储总量

顺序表存储密度 = 1

链表存储密度 < 1

基于时间的比较

  • 存取方式

顺序表可以随机存取,也可以顺序存取

链表只能顺序存取

  • 插入/删除时移动元素个数

顺序表平均需要移动一半元素

链表不需要移动元素,仅需修改指针

顺序表的操作

顺序表的操作

这里先定义个顺序表

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

using namespace std;

#define MAXSIZE 100

typedef struct{
int *elems;
int length;
int size;
}Sqlist;

Sqlist list;

顺序表初始化

  • 定义bool类型函数 initList() ,初始化成功为true,失败为false
1
2
3
4
5
6
7
8
9
10
11
//初始化顺序表,创建一个空表
bool initList(Sqlist &L) //L本身要改变所以为引用型
{
L.elems = new int[MAXSIZE]; //为顺序表分配内存空间
if(!L.elems) return false; //存储分配失败返回false

//分配成功则初始化
L.length = 0;
L.size = MAXSIZE;
return true; //成功并返回true
}
  • 定义函数 outputInfoList() 用于输出顺序表信息
1
2
3
4
5
6
7
8
9
//输出数据表信息
void outputInfoList(Sqlist &L)
{
cout << "顺序表储存空间" << L.size << ",已经保存元素个数" << L.length << endl;
for(int i = 0; i <= L.length - 1;i++){
cout << L.elems[i] << " ";
}
cout << endl;
}

找查元素

  • 定义函数 findElem() 在顺序表中找查一个等于e的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
* 用于找查顺序表中的元素
* 参数e为要找查的元素
* 若找到则返回元素下标
* 若没找到则返回-1
*/
int findElem(Sqlist L, int e) //这里我们不改变L,所以不用引用类型
{
for(int i = 0; i < L.length; i++){
if(e == L.elems[i])
return i; //若找到则返回元素下标
}
return -1; //若没找到则返回-1
}

插入元素

尾部添加元素

在尾部添加元素要考虑以下几点

  • 顺序表是否已满
  • 添加成功后长度要加1
  • 故定义函数 listAppend()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
* 在顺序表尾部插入元素
* 参数e为要插入到尾部的元素
* 若成功则返回true,失败(顺序表已经满了)则返回false
*/
bool listAppend(Sqlist &L, int e)
{
if(L.length == L.size)
//顺序表满了
return false;
//没满则尾部插入元素并返回true
L.elems[L.length] = e;
L.length++;
return true;
}

在特定位置插入元素

在特定位置插入要考虑以下几点

  • 顺序表是否已满
  • 添加成功后长度要加1
  • 要移动后面的元素而不能移动前面的元素,否则后面的元素会被前面的覆盖

定义如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//在顺序表p位置(0 <= p <= length)上插入元素e
bool insertElem(Sqlist &L, int p, int e)
{
if(p < 0 || p > L.length || L.length == MAXSIZE)
/*
* 如果位置错误
* 或者表长已经达到最大允许值
* 此时插入不成功并返回false
*/
return false;
for(int i = L.length - 1; i >= p; --i)
//从后往前将元素相后方移动一个位置
L.elems[i+1] = L.elems[i];
L.elems[p] = e; //插入元素e到p位置
L.length++;

return true; //成功返回true
}

删除元素

删除元素要考虑以下几点

  • 顺序表位置是否正确
  • 成功后长度要减去1
  • 后方元素向前移动一个位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//删除p位置的元素
bool delElem(Sqlist &L, int p, int &e)
{
//位置错误返回false
if(p < 0 || p > L.length - 1) return false;
e = L.elems[p]; //将被删除的元素赋值给e
for(int i = p; i < L.length - 1; i++)
{
//从p开始后方元素向前移动一个位置
L.elems[i] = L.elems[i+1];
}

L.length--; //长度减去1
return true; //成功返回true

}

顺序表的销毁

  • 在初始化函数中,用了new来分配内存,所以在销毁时要释放内存
1
2
3
4
5
6
7
void destroy(Sqlist &L)
{
//内存存在则释放内存
if(L.elems) delete []L.elems;
L.length = 0;
L.size = 0;
}

顺序表的概念及定义

顺序表

结点的概念

结点 :结点是内存中一片由用户分配的储存空间,只有一个地址来表示它的存在,没有显式名称。

在学习顺序表时,一般不会去特别强调结点的概念,此概念往往在链表学习中涉及,但并不代表结点与顺序表无关,所以我特意把结点的概念放在此处以加深对顺序表的理解。

顺序表的概念

定义:把逻辑上相邻的结点储存在物理位置上的相邻储存单元中,结点的逻辑关系由储存单元的邻接关系来体现

通俗来讲,顺序表就是把线性表中的所有元素按照其逻辑顺序,依次储存到从指定的储存位置开始的一块连续的储存空间中。

第一个元素的储存位置就是指定的储存位置,第 i+1 个元素的储存位置在第 i 个元素后面

顺序表的特性

  • 占用连续的储存空间:由定义可知顺序表的储存空间必然连续,并且存储分配只能预先进行,一旦分配完毕,在操作过程中始终不变。
  • 随机访问特性:因为储存空间是连续的,知道第一个元素的地址(即储存空间的首地址)可以轻松访问储存的所有数据。每一个结点对应一个序号,由该序号可以直接算出结点的储存地址。

顺序表三要素

  • 顺序表基地址
  • 顺序表长度
  • 顺序表总空间大小

顺序表结构体定义

1
2
3
4
5
6
typedef struct _Sqlist Sqlist;
struct _Sqlist {
int *elems; //顺序表基地址
int length; //顺序表长度
int size; //顺序表总空间大小
};

当然C语言提供了一种简单的写法(如下,以后以简单写法为例)。

1
2
3
4
5
6
typedef struct{
int *elems; //顺序表基地址
int length; //顺序表长度
int size; //顺序表总空间大小

}Sqlist;

在某些书籍上,有这样定义顺序表的

1
#define MAXSIZE 100
1
2
3
4
typedef struct {
int data[MAXSIZE]; //存放顺序表元素的数组
int length; //存放顺序表的长度
}Sqlist;
  • 实际上这种定义已经为顺序表开辟了一部分内存空间,而前者需要使用函数来顺序表初始化。
  • 但实际上两种代码本质上是一样的,因为前者在顺序表的操作——初始化顺序表中的函数定义中,我们仍需要分配一片储存空间并且定义一个存放顺序表元素的数组;而后者相当于把这一步合并到了定义中。
  • 在学习过程而非实际开发中,我更倾向于前者,因为这更能反应顺序表的三要素,并且与链表代码书写风格相似,有利于感受线性表思想的共性。

结束

我们现在已经成功定义顺序表了,但更重要的是它的操作,所以下一篇文章就来写这部分内容。

C语言结构体指针与结构体变量作形参的区别

区别

结构体变量

  • 结构体变量作为形参,传递的是结构体变量本身,是一种值传递
  • 形参结构体变量成员值的改变不影响对应的实参构体变量成员值的改变

结构体指针

  • 结构体指针作为函数参数,传递的是指向结构体变量的本身
  • 结构体指针指向的变量成员值的改变影响对应的实参构体变量成员值的改变

代码

直接说有些抽象难懂,敲代码演示一遍就很清楚了

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct stru{
int num;
};

//形参为结构体变量
void addNum(struct stru p, int num2)
{
p.num += num2;
}

//形参为结构体指针
void addNum2(struct stru *p, int num2)
{
if(!p) return; //确保指针不为空指针
p->num += num2;
}

int main(){

struct stru t;
t.num = 50;

addNum(t,5000);
printf("形参为结构体变量得到的结果为: %d\n", t.num);

addNum2(&t,5000);
printf("形参为结构体指针得到的结果为: %d\n", t.num);

return 0;

}

输出结果

1
2
形参为结构体变量得到的结果为: 50
形参为结构体指针得到的结果为: 5050

CuteBot智能小车

原因

近期,别人送了我一个CuteBot智能小车,拆开一看做工挺精致的,但是这东西是积木图形编程,显然不适合我这个年龄,所以打算给家里的小孩玩。

那么,你可能会问了,为什么要写这篇文章呢?答案当然是用来水的啊

其实在装的时候遇到了点坑,所以记录下来(说了半天还是水文章(滑稽)

部件

首先看下一个具有完整功能的 CuteBot小车(不算拓展)分为几个部分吧

  • MicroBit主板

这可以说是最核心的部件了,给小车烧录程序也是通过它。Microbit是由英国BBC公司推出的面向青少年编程教育的微型计算机,集成了加速度传感器,磁力传感器,两个可编程按钮,25个单色led,蓝牙等常用传感器设备,有一个micro usb接口用于连接数据线烧写程序和供电,可外接电池盒,底部有多个环孔连接器用于控制外接设备。这个板子不仅仅可以用于小车,官方还有许多套件,如智能家居等。当然也可以仅用这个板子跑程序,亮Led,放音乐等。总之它的功能非常强大。

MicroBit正面 MicroBit反面
  • 电池盒
电池盒
  • SR04超声波模块
超声波模块
  • 小车主体 (电池盒是粘上去的,实在是弄不下来了)
CuteBot Car

组装

  • 首先将电池盒的线接到小车主板上并将电池盒粘到小车上

  • 然后插入超声波模块(注意:超声波模块插槽为8Pin,要插入到插槽的前4个孔上,千万不要插入后四个插孔,否则小车无法跑起来,超声波模块会发烫

    如图:

SR04
  • 最后将MicroBit插入的小车上的蓝色插槽里(MicroBit背面朝电池盒)
  • 组装完成
CuteBotCar

编程

环境

新建项目
  • 输入项目名
  • “高级” -> “扩展”
扩展
  • 搜索CuteBot ,并点击
SearchCute
  • 返回页面你就会发现有了“酷比特小车”一行了
CuteBit
  • 点击“…” -> Connect 根据提示连接小车即可
Connect

Hello World

  • 现在开始编写第一个程序吧,你可以选择图形化的“方块”编程,也可以用JavaScriptPython编程(这里我用JS)
JS
  • 输入代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
这部分是开机执行
*/

//在MicroBit显示屏(Led)上显示字符串 Hello,World!
basic.showString("Hello,World!")

//显示完后,以50%的速度向前方行驶5秒
cuteBot.moveTime(cuteBot.Direction.forward,50,5)

basic.forever(function () {
/*
这里是无限循环的代码块
*/

})
  • 点击“下载” ,代码就开始执行了
  • (注意:如果该网站没有连接到MicroBit,那么你需要下载文件并右键手动发送到MicroBit里)

结束

该小车的优点是不需要焊接电路,并且无需搭配环境,仅需要组装好小车并通过在线编程即可运行

由于篇幅有限,关于API使用可以参考官方文档

使用Visual Studio 2019开发Qt程序

安装Qt

  • 如标题,你首先需要到 http://download.qt.io/ 去下载并安装Qt,并在引导下安装MSVC组件(这里不做过多解释)
QtDownload

Visual Studio 2019 配置

  • 打开VS2019
  • 点击“继续但无需代码”
VS2019
  • “扩展(X)” -> “管理扩展”
VS2019
  • 搜索“Qt”
SearchQt
  • 找到“Qt Visual Studio Tools”,点击“下载”按钮(图中是已经安装好的所以不显示下载)

  • 安装过程中会弹出 VSIX Installer窗口,依据引导安装即可

检查

  • 当我们再次打开 Visual Studio 2019 -> “创建新项目” -> 搜索“Qt”,发现已经能够创建Qt项目了
VS_Qt
  • 但是这还没有完,因为我们还没有添加 Qt Version

添加 Qt Version

  • 点击“上一步” -> “继续但无需代码” -> “扩展(X)” -> “Qt VS Tools” -> “Qt Versions”
  • 点击“add new Qt version”,然后点击Path列下的类似于文件夹的图标
Options
  • 找到你的Qt安装目录,在里面找MSVCqmake.exe (例如我的的Qt安装在D盘根目录,Qt版本是5.14.2,那么对应的就应该为 D:\Qt\Qt5.14.2\5.14.2\msvc2017_64\bin\qmake.exe)
  • 最后点击“确定”按钮保存即可
  • 注:图片中第一行显示的版本是我之前已经配置好的Qt版本,如果你是第一次配置,是不会自动添加Qt版本的