0%

一个难题

其实本节的内容,主要围绕着一个问题展开:

  • 是把导师和部门放在一个表inst_dept中,还是放在分开放在两个表instructor,department中呢?

让我们分别看看两种方案吧


方案一:放在一个表中

ID name salary dept_name building budget
22222 Einstein 95000 Physics Waston 70000
12121 Wu 90000 Finance Painter 120000
45565 Katz 75000 Comp.Sci Taylor 10000
10101 Srinivasan 65000 Comp.Sci Taylor 10000
83821 Brandt 92000 Comp.Sci Taylor 10000
inst_dept

一眼看去,表非常的直观,能清楚地了解每个老师的所有信息。而且,在查询时不需要使用join语句,对程序员也十分友好。这种方案看似非常不错,但却有两个非常严重的缺点。

1.先有老师再有系

如果大连理工大学创建了一个干饭系,但是由于这个系没有前景,所以迟迟没有老师愿意加入。我们没办法把干饭系加入到表中,因为每个记录在表中的系,都是有老师的。没有老师,就不能录入表格,在数据库中,要避免使用空值,所以把老师那里录入空值也不太好。

2.有很多废信息

假如大连理工大学有10000名教职工,却只有30个系,现在我们正在看有10000名教职工信息的表格

ID name salary dept_name building budget
1 小陈 95000 软国 信息楼 62000
2 小王 90000 软国 信息楼 62000
3 小夏 75000 软国 信息楼 62000
4 小薛 65000 软国 信息楼 62000
5 小张 92000 软国 信息楼 62000
…… …… …… 软国 信息楼 62000
inst_dept

当我们看完软国的所有老师后,我们一定会想,为什么不单独把软国的办公地点预算列出来呢,在每个老师后面都重复一遍是不是没啥必要😅

实际上,把所有老师后面都加上每个系的办公地点和预算,是对内存空间的浪费。特别是有10000名教职工的时候,每一排的浪费,在✖️10000之后,都会被无限放大。


方案二:放在两个表中

ID name dept_name salary
22222 Einstein Physics 95000
12121 Wu Finance 90000
45565 Katz Comp.Sci 75000
10101 Srinivasan Comp.Sci 65000
83821 Brandt Comp.Sci 92000
instructor
dept_name building budget
Physics Watson 70000
Finance Painter 120000
Comp.Sci Taylor 10000
department

方案二就好很多了,即使录入10000条数据,也不会浪费空间,需要查询老师院系的办公地点时,只需要将两个表连接后再查询就行了。

所以我们得出结论

  • 分开记录比合起来记录要好!❌

这个结论是不严谨的,因为没有考虑分解有损的情况


有损分解

故名思义,有损分解就是把大表分解成小表之后,会损失原始数据的分解

让我们来看一个例子,下面的是原表

ID name street city salary
57766 Kim Main Perryridge 75000
98776 Kim North Hampton 67000
employee

我们把原表分解之后,两个Kim会出现混淆的现象

ID name
57766 Kim
98776 Kim

。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

name street city salary
Kim Main Perryridge 75000
Kim North Hampton 67000

如果现在要把两个表格合在一起,会无法分辨表一中的ID对应表二中的哪个Kim

无损分解

如果分解之后再合成,能够得到跟原来一样的表(没有损失信息),就叫做无损分解

关系代数来表示,就是:


使用函数依赖进行分解

表示方法

关系模式是一个属性集,为了稍作区分,我们用三种不同的方法表示属性集

  • α :表示属性集,但是不知道属性集是不是关系模式
  • r(R):表示属性集,这里的属性集特指关系模式,r代表关系的名字,不在意名字的话,可以省掉r,只写R

超码是一个或多个属性的集合,可以在表中区分不同的实体,某集合只要包含了超码,也会变成超码,所以说超码的超集也是超码

  • K:表示属性集,这里的属性集特指超码

函数依赖

给定r(R)上的一个实例,我们判断这个实例满足函数依赖X→Y的条件是:对实例中所有的元组对t1和t2,若t1[X] = t2[X],有t1[X] = t2[X],则t1[Y] = t2[Y]

通俗来讲就是:

设X,Y是关系R的两个属性集合,当任何时刻R中的任意两个元组中的X属性值相同时,则它们的Y属性值也相同,则称X函数决定Y,或Y函数依赖于X。

  • 例1:A→C在下表中是否成立?C→A呢?
A B C
a1 b1 c1
a1 b2 c1
a2 b2 c2
a2 b3 c2
a3 b3 c2

写这种题要记住一句关键的话,一个X仅有一个Y对应,跟判段是否为函数十分相似

可以看到,a1对应c1,a2对应c2,a3也对应c3,A中的每一个值都仅有唯一的C值对应,所以A→C成立

但是在C中,c2对应a2和a3,所以C→A不成立

  • 例2:在关系模式R中,K→R是否成立?

根据超码的定义,如果两个元组在超码上的值相同,那么这两个元组一定是同一个,所以,K→R成立


平凡函数依赖和非平凡函数依赖

若X→Y且X不包含Y,则称X→Y为非平凡函数依赖;否则若X包含Y,则必有X→Y,称此X→Y为平凡函数依赖.

常见的平凡函数依赖有

  • A→A
  • AB→A

Armstrong公理

自反律:若X为一属性集且Y⊆X,则X→Y成立

增补律:若X→Y成立且Z为一属性集,则ZX→ZY成立

传递率:若X→Y和Y→Z成立,则X→成立

公理推论:

合并律:若X→Y和X→Z成立,则X→YZ成立

分解律:若X→ZY成立,则X→Y和X→Z成立

伪传递律:若X→Y和ZY→M成立,XZ→M成立

让我们通过公理来证明一下推论

  • 合并律:

因X→Y ,所以X→XY (增广律 XX→XY即X→XY)

因X→Z ,所以XY→YZ (增广律)

因X→XY,XY→YZ(增广律)

故X→YZ (传递律)

  • 分解律:

因Y⊆ZY,所以ZY→Y(增广律)

因X→ZY,所以X→Y(传递律)

因Z⊆ZY,所以ZY→Z(增广律)

因X→ZY,所以Z→Y(传递律)

  • 伪传递律:

因X→Y ,所以WX→WY (增广律)

因WY→Z ,所以XW→Z (传递律)


依赖函数集F及其闭包

用通俗的话来讲,F就是给出的依赖关系集,但是给出的依赖集一般给的很简单,往往可以进一步推导出别的依赖关系,把所有推导出来的依赖关系加上原来给出的依赖关系合在一起,就可以得到F的闭包F+

我们不妨来看一道例题

  • 已知关系模式R(ABC),F={A→C,B→C},求F+

这题的关键是,用{A→C,B→C}推导出所有可以推导出的依赖关系

这个过程一般很庞大,我们就只推一部分,主要是为了更好的理解F+

现在已知A→C,我们就可以推出AC→C(增广律),我们把AC→C加入F+中

A→A在F中也没有,也可以加入到F+中

当然,F+远不止这些,因为还有很多依赖关系没有被推导出来,全推出来后合上F,就能得到F+了


范式

第一范式与原子域

  • 原子域:具有原子性的域。
  • 第一范式:在关系模型中,所有的域都应该是原子性的,即数据库表的每一列都是不可分割的原子数据项,而不能是集合,数组,记录等非原子数据项。

例如三围这个属性,是胸围,腰围,臀围的集合,如果一个表中包含了三围这个属性,必须要拆分成胸围,腰围,臀围后才能满足第一范式。

简单来说,满足第一范式是关系模型的基本要求,要是不满足第一范式,就不能被称作是关系模型。后面的BC范式和第三范式都是建立在第一范式的基础上的


BC范式(BCNF)

对F+中的形如X→Y的函数依赖,必须满足下面的两点之一

1.X→Y是平凡的函数依赖

2.X是超码

通过BC范式,我们能够轻松的区分一个表需不需要拆分,只要不满足BC范式,就需要拆分


依据BC范式进行拆分

经过检查,我们发现X→Y不满足BC范式,我们需要把表拆成两个部分

  • (X ∩ Y)
  • (R - (Y - X))

如果套用本文最开头大学的例子,X = dept_name,Y = {building, budget}

  • (X ∩ Y) = (dept_name, building, budget)
  • (R - (Y - X)) = (ID, name, dept_name, salary)

刚好是我们拆分后的两个表!


BC范式的局限

在设计数据库时,我们有的时候需要一些依赖关系如X → Y,这个依赖关系并不满足BC范式的要求,但是我们就是要保留这个依赖关系,这时BC范式就会暴露出要求过严的局限性

让我们看一个例子:

我们有一个大学的E-R图,包含以下要求:

  • 一个教师只能在一个系中
  • 一个学生可以有多个导师
  • 一个学生在一个系中最多有一个导师

根据以上条件和E-R图,我们可以得到两条函数依赖,需要在dept_name中成立

  • i_ID → dept_name
  • s_ID, dept_name → i_ID

如果按照BC范式的要求,i_ID并不是dept_name的超码(因为一个学生可以有多个导师),我们需要对dept_advisor进行拆分

拆分为

  • (s_ID, i_ID)
  • (i_ID, dept_name)

但是拆分后,s_ID, dept_name → i_ID不再成立,与我们的实际要求相违背

所以用BC范式约束dept_advisor是不合理的


第三范式(3NF)

第三范式可以看作是BC范式的宽松版,BC范式可以看作第三范式的特殊形式

第三范式在BC范式两条要求的基础上,加上了第三个条件

对F+中的形如X→Y的函数依赖,必须满足下面的三点之一:

1.X→Y是平凡的函数依赖

2.X是超码

3.Y - X中的每个属性A都包含于R的一个候选码中

如果我们用第三范式的要求来解上面那个例子,会是什么结果呢?

有下面两个函数依赖需要成立

  • i_ID → dept_name
  • s_ID, dept_name → i_ID

我们主要看i_ID → dept_name

很明显,不满足前两条,那满不满足第三条呢?

我们先用dept_name - i_ID = dept_name

接下来,只需要证明dept_name包含于候选码中,就可以满足第三个条件了

由于s_ID, dept_name → i_ID,那么(s_ID, dept_name)至少是一个超码

不存在(s_ID,dept_name)的子集也为超码,所以(s_ID, dept_name)是候选码

所以dept_name包含于(s_ID, dept_name)候选码中,i_ID → dept_name满足第三个条件,不需要进行拆分!


属性集的闭包

函数确定

X是属性集,Y是属性,如果X → Y,则称Y被X函数确定

用函数确定判断超码

我们不妨再回顾一下超码的知识

要证明X是超码,我们需要证明X→R,R是表中所有的属性的集合,所以我们需要证明X可以函数确定所有的属性

首先我们需要计算出F+,也就是所有的依赖关系,然后我们可能会得到诸如X→Z,X→M等依赖关系

当Y,Z,M等合起来能组成R时,就说明X是超码

但是这个做法有一个缺点,就是需要计算F+,很明显F+的计算是非常麻烦的,我们要尽量去避免


属性集闭包

令X为一个属性集,我们将函数依赖集F下被X函数确定的所有属性的集合称为F下X的闭包,记作X+

  • 有关系模式R<U,F>,其中U={A,B,C,D,E},F={AB→C,B→D,C→E,EC→B,AC→B},求(AB)+

首先,我们要从AB开始求,所以令X(0) = AB

第一步,求X(1)。我们要先列出X(0)的非空子集,即AB的非空子集,很显然为{A,B,AB}。然后扫描F集合,寻找包含有{A,B,AB}的函数依赖,就可以得到:AB→C,B→D。我们就可以把C,D合入X(0)中得到X(1),就可以求得X(1)=X(0)∪C∪D=ABCD。如果X(0)等于X(1)就说明继续进行下一步也会得到相同的结果,与离散数学中的传递闭包相似,于是我们可以结束步骤,所求即为答案,如果X(0)不等于X(1)就继续计算。

第二步,求X(2)。同第一步求X(1)的非空真子集,然后在F中一次寻找函数依赖,可以得到:AB→C,B→D,C→E,AC→B。所以X(2)=X(1)∪C∪D∪E∪B=ABCDE。这时候发现X(2)已经等于全部属性集U了,不可能再计算出新的结果,我们就结束计算,得出**(AB)+ =ABCDE。**

让我们来看一下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
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
//首先输入F中的函数依赖对数 
//其次输入具体的函数依赖
//输入要求解的属性集X
//输出:X关于F的闭包:X+

/*输入示例:
比如F={A→C,B→C} 求A+
第一步: 2
第二步: A C
B C
第三步: A
输出: {AC}
*/
#include <iostream>
#include <string>
using namespace std;

struct FunctionDependence
{
string X;
string Y;
};
void Init (FunctionDependence FD[],int n)
{
//函数依赖关系初始化
int i;
string x,y;
cout<<"请输入F中的函数依赖(决定因素在左,被决定因素在右)"<<endl;
//输入函数依赖集合F
for (i=0;i<n;i++)
{
cin>>x>>y;
FD[i].X=x;
FD[i].Y=y;
}
cout<<"函数依赖集合F:";
cout<<"F={" ;
for (i=0;i<n;i++)
{
//显示已知的函数依赖集合F

cout<<FD[i].X<<"->"<<FD[i].Y;
if (i<n-1)cout<<", ";
}
cout<<"}"<<endl;
}

bool IsIn(string f,string zz)
{
bool flag1=false;
int len1=f.length();
int len2=zz.length();
int k=0,t=0,count1=0;
for (k=0;k<len1;k++)
{
for (t=0;t<len2;t++)
{
if (f[k]==zz[t])
{
//flag1=true;break;
count1++;
}
}
}
if (count1==len1)
{
flag1=true;
}
else flag1=false;
return flag1;
}
string CutAndSort(string mm)
{

int size=mm.length();
int kk=0,ii=0;;
string closure;
int a[200]={0};//用来记录各个命题出现的次数
for(kk=0;kk<size;kk++)
{
a[(int)mm[kk]]++;//强制转换类型,储存各个因素的次数
}

for (ii=0;ii<200;ii++)
{
if (a[ii]>=1)//cout<<(char)ii;
closure+=(char)ii;
}
return closure;
}

string X_Fn(FunctionDependence FD[],int n,string &xx)
{
string yy=xx;
for (int i=0;i<n;i++)
{
if (IsIn(FD[i].X,yy)==true)
{
xx+=FD[i].Y;
}
}
yy=CutAndSort(yy);
xx=CutAndSort(xx);
if (xx!=yy)
{
X_Fn(FD,n,xx);//递归
}
return xx;
}

void FD(FunctionDependence FD[],int n)
{
//输入 X
string xx;
int i;

cout<<"\n请输入属性集X:";
cin>> xx;
cout<<"\n"<<xx<<"关于F的闭包:{";
//求X关于F的闭包
cout<<X_Fn(FD,n,xx);

cout<<"}\n";
}

int main()
{
int N;
cout<<"请输入F中函数依赖的组数:";
cin>>N;

FunctionDependence fd[N];
Init(fd,N);
FD(fd,N);
FD(fd,N);
FD(fd,N);
return 0;
}

属性集闭包用途

  • 判断X是否为超码,如果X+包含了R中的所有属性,就说明X是超码
  • 用来判断X→Y,如果Y属于X+,则X→Y成立
  • 计算F+,我们通过计算所有属性的闭包,然后根据闭包得到函数依赖,把所有得到的函数依赖合在一起,就是F+

例题:R{A,B,C,D},D→A,C→A,C→D,B→C
请问候选码是?是否属于BC范式?

(1)首先我们求解A+,B+,C+,D+

使用上面的C++代码会很方便,这里我直接给出结果

A+ = {A},B+ = {ABCD},C+ = {ACD},D+ = {AD}

很明显,B是最小超码,即为候选码

(2)D→A既不满足D是超码,也不满足D包含A,所以R不满足BCNF


结语

本文主要参照《数据库系统概念》这本书,文中很多例子都出自此书,借着写博客的机会,把这本书的第八章又看了一遍。写完文章,看着电脑里面4个G的无声录屏,真是太尴尬了🌝,哈哈哈哈哈哈哈。

前言

这篇文章,主要是想讲明白所有fork函数和threadcreate函数带来的数进程线程问题,变量值是多少的问题。操作系统中有很多这种题,每次做的时候,看着一大串源码,我总是想,发生甚么事了❓所以,借此机会,写一篇文章,看能不能把这种类型的题彻底讲明白。


fork()函数

什么是fork()

首先,让我们想想,如果我们没有学过操作系统,我们第一眼看到fork,会想到什么?

fork在英文中的意思是叉子,实际上,在操作系统中,虽然fork是进程创建函数,但它的意思还是叉子,不信看我下面这两张图

有没有觉得有一点像,操作系统中,无非是在讨论第二张图的一个点,用一句话说就是,在一个进程分叉为两个的时候究竟发生了什么

那个点到底发生了什么

  • 一个进程调用fork()函数后,系统先给新的进程分配资源,例如存储数据和代码的空间。然后把原来的进程的所有值都复制到新的进程中,只有少数值与原来的进程的值不同。相当于克隆了一个自己。

代码一流程问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <unistd.h>  
#include <stdio.h>
#include <sys/types.h>
#include <sys/wait.h>
int main ()
{
pid_t fpid; //fpid用来储存fork函数返回的值
int count = 0;
fpid = fork();
if (fpid < 0)
printf("出现错误!");
else if (fpid == 0) {
printf("子进程,我的进程号是%d\n我的父进程的进程号是%d\n",getpid(),getppid());
count++;
}
else {
wait(NULL);
printf("父进程,我的进程号是%d\n我的父进程的进程号是%d\n",getpid(),getppid());
count++;
}
printf("统计结果是: %d\n",count);
printf("------\n");
return 0;
}

运行结果为

1
2
3
4
5
6
子进程,我的进程号是5574,我的父进程的进程号是5573
统计结果是: 1
------
父进程,我的进程号是5573,我的父进程的进程号是5562
统计结果是: 1
------

让我们从上往下看代码,首先使用了fork函数,创建了一个子进程,然后出现了一个fpid,用来存储fork()函数的返回值,但是在下面,就有点奇怪。

  • 为什么可以判断一个函数的返回值,然后做出不同的操作呢?

这是因为,fork函数非常的特殊,在虽然是一个函数,但是有两个返回值,fork函数就是通过不同的返回值来区分父进程和子进程,父类的fpid返回的是子类的进程号,子类的fpid中返回的是0,这么做的目的是区分父子函数,前面我们提到,fork函数创建的子进程只有少数值与父类不同,在其他方面相当于克隆了一个父进程,这时,就要通过fork函数的不同返回值来区分父子进程

  • 什么是getpid()函数,什么是getppid()函数?

getpid()函数的作用是返回当前进程的进程号(pid),我们需要注意,在子进程中,虽然用来储存fork()函数返回值的fpid的值为0,但是并不代表子进程的进程号为0

getppid()函数的作用是返回当前进程的父进程号(),这里特殊的是,我们所谓的父进程其实也是别的进程的子进程,就像我们的爹,同时也是我们👴的儿子,所有进程的祖先是init进程,在新版的Linux系统中,init已经改为systemd,以提高启动速度,也就是说,现在在Linux系统中搜索pid = 1的进程,会得到systemd

  • 为什么count的值在经历过两次自加之后,值还是为1?

其实要解决这个问题,只需要仔细看前面**什么是fork()**的部分

系统先给新的进程分配资源,例如存储数据和代码的空间。然后把原来的进程的所有值都复制到新的进程中

类似于复制粘贴一份文件,在修改新文件时,并不会对旧文件中的内容产生影响,在这里,父进程和子进程虽然都有一个count,但是对count值的操作只会影响到本进程的count,而不会影响到另一个进程。


代码二数数问题

1
2
3
4
5
6
7
8
9
10
#include <stdio.h> 
#include <sys/types.h>
int main()
{
fork();
fork();
fork();
printf("hello\n");
return 0;
}

或者是使用for循环

1
2
3
4
5
6
7
8
9
10
#include <stdio.h> 
#include <sys/types.h>
int main()
{
for (int j = 0; j < 3; j++) {
fork();
}
printf("hello\n");
return 0;
}

结果

1
2
3
4
5
6
7
8
hello 
hello
hello
hello
hello
hello
hello
hello

这个就是一个基本的数数问题,在我第一次做这种题的时候,我会去画树状图,但是如果从数学的角度去考虑,所有的可以得到这样一个公式

我们知道,只要经历一次fork函数,总进程数就会翻倍一次,那么经历n次之后,就能得到上面的式子,在上面的代码中,用这个公式就能轻易的算出总进程数是等于8的

  • 在第三步创建了多少新进程?

这也很简单嘛,只需要用第三步的总进程数减去第二步的总进程数,就能得到第三步新创建的进程数


wait()函数

什么是wait()

wait()会暂时停止目前进程的执行,直到有信号来到或子进程结束。如果在调用wait()时子进程已经结束,则wait()会立即返回子进程结束状态值。

简单来说,wait函数就是等待的意思,如果在父进程中使用wait()函数,则父进程会等待子进程结束后再继续执行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <unistd.h>  
#include <stdio.h>
int main ()
{
pid_t fpid; //fpid用来储存fork函数返回的值
int count = 0;
fpid = fork();
if (fpid < 0)
printf("出现错误!");
else if (fpid == 0) {
sleep(2);
printf("子进程,我的进程号是%d\n,我的父进程的进程号是%d\n",getpid(),getppid());
count++;
}
else {
printf("父进程,我的进程号是%d\n,我的父进程的进程号是%d\n",getpid(),getppid());
count++;
}
printf("统计结果是: %d\n",count);
printf("------\n");
return 0;
}

我们不妨把代码一稍稍改一下,去掉父进程中的wait()函数,在子进程中加入sleep()函数,让我们来看看执行结果有什么不同

1
2
3
4
5
6
父进程,我的进程号是7309,我的父进程的进程号是7300
统计结果是: 1
------
子进程,我的进程号是7311,我的父进程的进程号是1770
统计结果是: 1
------

我们发现,跟上面的执行结果有两处不同

  • 第一处是执行的顺序不同了,这次是先输出父进程再输出子进程,而之前是先输出子进程再输出父进程
  • 第二处是子进程的父进程号变了,getppid()函数并没有返回父进程的进程号,而是返回了一个奇怪的进程号1770

第一处问题很好解释,在原版的代码一中,父进程中有wait()函数,是父进程等待子进程执行完,而在改版中的代码一中,由于删去了父进程中的wait()函数,反而在子进程中加入了sleep()函数,这会导致父进程先于子进程执行完,所以先输出父进程的结果,再输出子进程的结果

第二处问题就比较有意思了,我们知道,父进程再执行完之后就会退出,这时子进程还没执行完,子进程就会变成我们所说的孤儿进程

我们知道,孤儿进程的父进程会变成1,代表的是init进程,但是在前面我们提到过,新版的Linux系统采用更加复杂的systemd代替了init,所以在这里情况会有所不同。

让我们来查询一下进程号为1770的进程是什么,在ubuntu终端中输入以下命令

1
ps -e | grep 1770

最终可以得到结果

1
1770  ?  00:00:00  systemd

我们可以知道,虽然新版的Linux系统中不再将孤儿进程的父进程设定为1,但是仍然将孤儿进程的父进程设置为系统守护进程


pthread_create()函数

1
pthread_create(pthread_t*restrict tidp,const pthread_attr_t *restrict_attr,void*(*start_rtn)(void*),void *restrict arg);

我们可以看到,在pthread_create()函数中,一共需要传入四个参数

  • 第一个参数为指向线程标识符的指针。
  • 第二个参数用来设置线程属性。
  • 第三个参数是线程运行函数的起始地址。
  • 第四个参数是运行函数的参数。

其实在这四个当中,我们只需要记住第三个参数用来表示线程运行函数时的起始地址就足够了


代码一流程问题

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
#include <pthread.h> 
#include <stdio.h>
#include <types.h>

int value = 0;
void *runner(void *param); /* the thread */

int main(int argc, char *argv[])
{
pid_t pid;
pthread_t tid;
pthread_attr_t attr;

pid = fork();
if (pid == 0) { /* child process */
pthread_attr_init(&attr);
pthread_create(&tid,&attr,runner,NULL);
pthread_join(tid,NULL);
printf("CHILD: value = %d",value); /* LINE C */
}
else if (pid > 0) { /* parent process */
wait(NULL);
printf("PARENT: value = %d",value); /* LINE P */
}
}

void *runner(void *param) {
value = 5;
pthread exit(0);
}

这是我们的一道作业题,问题是第C行和第P行的输出值是多少?

其实,这个题最后也没有问任何与线程相关的东西,如果把这题中有关线程的东西去掉,这段代码就会变得通俗易懂

在这道题当中,用了大段的代码来创建一个进程去执行runner函数中的内容,其中比较关键的地方有

1
2
pthread_create(&tid,&attr,runner,NULl);
pthread_join(tid,NULL);

第一行代码指的是,我们可以把目光直接移动到runner函数,至于这个函数是用哪个线程干的,并不影响我们做题

如果仅仅从做题的角度,我们可以把这行代码等同于机组中的jal(误)

1
jal label(label是pthread_create函数中的第三个参数)

那让我们继续看看pthread_join()函数是来干什么的

  • pthread_join()等同于wait()函数,指的是以阻塞的方式等待某一个线程执行结束(tid指向的线程)

如果看懂了这两行关键的代码,从做题家的角度,上面冗长的代码就可以转化为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
#include <types.h>
int value = 0;
int main(int argc, char *argv[])
{
pid = fork();
if (pid == 0) { /* child process */
value = 5;
printf("CHILD: value = %d",value); /* LINE C */
}
else if (pid > 0) { /* parent process */
wait(NULL);
printf("PARENT: value = %d",value); /* LINE P */
}
}

好家伙,代码直接从30行变成15行


代码二数数问题

1
2
3
4
5
6
7
8
pid_t pid;

pid = fork();
if (pid == 0) { / * child process * /
fork();
thread_create( . . .);
}
fork();

这个也是我们的一道作业题,问题是

  • 执行一遍之后,有多少个进程被创建?又有多少个线程被创建?

在做这个题之前,我们首先要弄明白一个问题


线程与进程的关系

这里参考了这篇博客,我来简单转述下

  • 我们不妨来做一个简单的比方
  • CPU是一个工厂
  • 进程是一个车间
  • 线程是车间的工人

  • 一个工厂时刻在运行,但是由于电力原因,一次只能开一个车间

    一个CPU一次只能执行一个进程

  • 一个车间里可以有很多工人一起协同工作

    不同的任务可以分配给不同的线程去做

  • 一个车间中的生产区域,每一个工人都能进去

    一个进程的内存空间是共享的,每一线程都可以进去

  • 车间中的有些房间一次只能容纳一个人,比如厕所

    一个线程使用某些共享内存时,其他线程必须等它结束,才能使用这一块内存。

  • 一个工人进厕所之后会锁门,防止其他的工人进去

    存在互斥锁,防止多个线程同时读写某一块内存区域

  • 一个正在生产中的工厂,至少有一个工人在某一个车间中进行生产

    一个程序至少有一个进程,一个进程至少有一个线程。


让我们来接着看数数问题

1
2
3
4
5
6
7
8
pid_t pid;

pid = fork();
if (pid == 0) { / * child process * /
fork();
thread_create( . . .);
}
fork();

这里我想换一个思路,讲讲在stack overflow中,这个题的三个主流解法

第一种—有6个进程,2个线程被创建

为什么要学习树?

相信大家都听说过一些带的名字,比如二叉搜索树,最小生成树……,这些都是以离散数学中的最简单的为基础的。把树学习好,也能给将来数据结构的学习打下了坚实的基础。

什么是树?

定义1

1.点与点没有成环

2.互相连通

3.简单图

如果无法理解的话,不妨拿生活中的树来举例子

一棵树,首先枝条不能长成环

其次,不能说一棵树在东边长一部分,在西边长一部分,这样也不能叫做一棵树

定义2

图中的任意两点之间有且只有一条简单路,叫那么这个图就是树

这个也很好想象,如果一个图里面点与点已经形成了一个环,那么肯定存在两点,能够用不止一条简单路来连接

跟生活中的树一样,图中的树也有叶子

在树中度数为1的点称为叶

一个树图中一定会有叶

实际上,在图论中的树对叶的定义更加的宽泛

例如,现实生活中的树,到冬天就没有叶子了

但是,在图论中,如果一个树没有叶子,那它必须要成环,但这又与树的定义相违背了,所以一棵树一定会有叶

树的边数

在树中,自环,多重边,以及点与点之间形成环都已经被禁止了

所以,树具有了额外的一条的性质

有n个点的树,一定有n-1条边

最小生成树

所谓生成树,就是要把原本不是树的图,删成树

这里的最小,首先要确定是哪方面最小

比如想要最便宜的生成方法,和想要看到最好风景的生成方法肯定不一样

假如现在甲方的要求是最便宜的生成方法,那么,我们首先对道路成本进行评估

得到不同道路的分数后,就可以开始生成最小树了

Prim’s algorithm

用一句话概括这个算法,就是:走一步看一步

先随便选择一个分值最小的边,连完后,在从相邻的边中选择一条分值低的,按照这个规则进行迭代,直到把所有点连接上为止

Kruskal’s algorithm

用一句话概括这个算法,就是先把分数低的连上

先按照分数把边进行分类,先连接分数低的边,按照这个规则进行迭代,直到所有点都被连接为止

两种算法的关系

如果最小生成树只有一种,那么无论采取什么算法,最后得到的最小生成树都是一样的

但是如果最小生成树不只有一种,那么得到了最小生成树可能不一样,但是从边的总分数来说,生成的树肯定是一样的

有向树

如果一个有向图在不考虑边的方向时是一棵树,那么,这个有向图称为有向树

简单来说,就是把一个有向图的边都换成无向边后,是一棵树,那么这个有向图称为有向树

根树

一棵有向树,如果恰好有一个结点的入度为0,其余所有结点的入度都为1,则称这棵有向树为根树

其中,入度为0的那个点称为根

级数和高度

级数:从一个点到根的路的长度

根据级数的定义,我们可以知道,由于根和自己的长度是0,所以根的级数是0

高度:一个根树中的最大级数

比如一个有九个点的根树,它的最大高度就是8,这个时候,这个树就是一根杆子

画的有点抽象💩

二叉树

顾名思义,指的是一个枝最多分叉两次

类似这种,需要注意的是

二叉树带有方向

至于为什么,到后面就会明白

二叉搜索树

比如我们要做一个小字典,能够实现的功能是可以搜索单词

有这样几个单词

math, computer, power, north, zoo, dentist, book.

该怎么实现这样一个搜索树呢?

让我们先选择一个参考单词math

画出math后,下一个是computer,由于首字母c在m前面,所以把computer排到math的左分支

再下一个是power,由于p比m靠后,所以把power排到math的右分支,math排满后,就可以排子节点computer和power,比如north,n比m靠后,但是比p靠前,所以把north放到power的左分支,按照这个规则进行迭代,就可以得到最终结果

这样,一个简单的二叉搜索树就完成了,芜湖✈️!

这也解决了前面的问题,再看下面这张图,一定能够恍然大悟

最后

今天补上树的部分,算是完成了创博客网站时周更的承诺,还有几天就要考离散了,希望我能没事🙏

写在前面

这篇博客仅包含了图论中比较基础的部分,如果需要较为全面的学习图论,建议购买一本《离散数学》的参考书进行学习。

柯尼斯堡七桥问题(Seven Bridges of Königsberg)

当时东普鲁士柯尼斯堡(今日俄罗斯加里宁格勒)市区跨普列戈利亚河两岸,河中心有两个小岛。小岛与河的两岸有七条桥连接。在所有桥都只能走一遍的前提下,如何才能把这个地方所有的桥都走遍?

在完成对七桥问题的抽象化后,能够知道

其实七桥问题就是一个一笔画问题,能不能一次走完,等于能不能在第三个图里面完成一笔画

首先,对点进行分类,分为起点终点,以及其他点

对于其他点来说,与它们相连的边的个数不能为奇数个

举个例子,我每次回老家,我都会坐飞机从大连出发,到达武汉,再坐火车回荆州

那么武汉就是中间点,我来武汉之后一定会走,不然我一定会停留在武汉

同样的道理,除了起点终点之外的其他点,如果相连的边是奇数个,那这个图一定不能一笔画

近而,得出结论

如果一个图能够一笔画,那么它里面与奇数条边相连的点的个数一定不超过2

但是,如果这句话反说,就不对了

如果一个图里面与奇数条边相连的点个数不超过2,那这个图一定能够一笔画

因为图有可能是断开的

再把上面的话改一下

如果一个连通图里面与奇数条边相连的点个数不超过2,那这个图一定能够一笔画

图的定义

可以说,一个图里面重要的有2点,有哪几个点,有哪几条边,至于点在什么位置,边的长度是多少,这些都不重要

在图中,边可以被分为无向边和有向边,有向边是单方向的,而无向边是双向的

简单图

首先来说,简单图有三个要求

  1. 没有有向边
  2. 没有形成环
  3. 两点之间仅能有一条边

那么,如果一个图是简单图,那么它的边可以被表示为以两端点为元素的集合

如图

一个有n个点的简单图,能够形成多少种不同的边?

首先,由于简单图里面是无向边,而且简单图没有环,所以这是一个排序问题,相当于从有n个球的箱子里取出两个

一个有n个点的简单图,一共有多少种不同的图?

一个图由边和点构成,点有n个已经确定,所以能组成多少种图,与边有多少种有很大的关系,根据上一问,可以得到不同边的集合的子集有

有向图

有向图只有一个要求

所有的边都是有向边

环和多重边,有向图都允许

一个有n个点的有向图,能够形成多少种不同的边?

有向图跟简单图相比,无非是多了一个方向问题,那这题不就简单了吗?

但是,我们常常会忽视的一点是,有向图能够有环,所以,一个点自己形成一条边的可能是有的,所以正解应该是

一个有n个点的简单图,一共有多少种不同的图?

这个就很简单了,跟之前的问题类似

度的定义

顶点度计算的是在放大镜下看时似乎伸出的边数

比如有这样一个图,图中标为2的点的度数是多少?

想象一下,如果拿一个放大镜去看2,会得到一张什么样的图像

这个点的度数是7

从这个问题,可以知道,一个点上环的度数不算1,而算2

入度和出度

如果是一张有向图呢,度该如何计算?

入度(in-degree):指向点的边的个数

出度(out-degree):从点指出的边的个数

下图中,所有的点的入度之和出度之和分别是多少?

很简单,只需要把每个点的入度和出度算出来,然后再分别加到一起

可以得到

入度:7

出度:7

一个图中,入度和出度一定是相等的

很简单,一个有向边,一定代表一个点指向一个点,代表一个点入度加一点同时会有一个点的出度加一,环很特殊,严格来说,环既可以算有向边又可以算无向边,但是无论是有向边还是无向边,都不会影响这个结论成立

度的作用

一个概念的引出,一定有其作用,度的作用就是可以用度来求边的个数

一个图的总边数,等于一个图的点的度数只和

但是,在有向图中,总度数被入度和出度平分了,所以,有可以推导出

有向图的总边数等于所有点的入度之和或者是出度之和

度数在实际问题中的应用

朋友问题:

选取五个人,有没有可能,这五个人只认识其中的另外三个人?

如果学习了度的知识的话,这个问题就迎刃而解

想象一个5个人作为顶点的简单图,边是表示朋友关系的无向边。每个人拥有的朋友数量就是这个人的度数。

根据题设条件,每个人仅仅有三个朋友,所以每个点的度数就是3,这个图的总度数就是15,很显然,度只能是偶数(必须能整除),图才可能存在,所以,这个问题是不可能成立的

结语

对于图论来说,这篇博客只能说是垫脚石,简单介绍了一下单个的图,并没有涉及图与图之间的关系,11月份学校考试较多,关于图与图之间的关系,等我有空一定完成,感兴趣的话,可以收藏我的博客网站哦🌝

简介

在离散数学关系部分的学习中,最难的莫过于5种特殊的关系了,在做题的时候,我开始非常的难受,后来掌握了方法之后,突然就茅塞顿开了,接下来我会用通俗的语言翻译抽象的定义,后面会附上一个例题,以供大家练习,这篇博客参考左孝陵先生的《离散数学》,大家可以买来参考哦

自反性(reflexive)

自反性,令C={(x,y)|x、y属于A},设D是C的某非空子集,如果(x,y)属于D,则称x,y有(由D规定的)关系,记为x ~ y。(符号(,)表示两者组成的有序对)。

定义简直不说人话嘛,我的理解是,集合中必须有所有前后相同的序偶(<x,x>),如

A= {1,2,3}上的关系{<1,1>, <2,2>, < 3,3>, <不重要,不重要>}

用矩阵表示就是

只要一个集合中同时出现了所有前后相同的序偶(<x,x>),就是自反的

反例(凑不齐)

{<1,1>,<2,2>,<没有3,没有3>} 这里没有<3,3>嘛,所以不是自反的

同理,<1,1>, <2,2>,没有也是一样的,只要它们三个不在一起,就不能叫自反

反自反性(irreflexive)

反自反关系(anti-reflexive relation)是一种特殊的关系,指任何事物与其自身之间都不具有的那种关系。用符号表示:R是A上的反自反关系⇔∀a(a∈A→¬(aRa))。当A上的R为反自反关系时,称R在A上是反自反的,或说A上的关系R有反自反性。

有自反,肯定有反自反,还会有不是自反,不是反自反,挺绕的,我们先把反自反学学会,反自反跟自反相对应,用一句话总结,就是对角线上元素都为0,前后相同的序偶(<x,x>)一个都不能有

用矩阵来表示,就是

反例(凑不齐)

{<1,1>,<不重要,不重要>},这个关系肯定不是反自反的

用矩阵表示

因为要想反自反,你矩阵对角线上就一个1都别有嘛,只要出现一个,就不是反自反,只有三个都不出现,才是反自反的

提问

所有的关系,不是自反,就是非自反的,这句话对吗?

当然是错的,自反是对角线上的所有元素都是1,反自反是对角线上的所有元素都是0,中间就会存在一些情况,对角线上有1,但是不全有

如上面的例题的图

第二个问题

这个图的可以用哪些有关自反的词形容?

可以叫它非自反,也可以叫它非反自反,反正属于中间的那个,就像太监,你可以说他不是男的,也可以说他不是女的

简介

这篇博客参考b站黑马程序员刘意老师的Java课程,刘老师讲的很好,写这篇博客是补充说明一些我容易出错的地方,如果你不知道学生管理系统的功能是什么,我会画一个思维导图贴在下面,然后是实现的Java源码,当然,我会把其中重要的部分,单独拿出来讲讲

学生管理系统要实现的功能

需要实现功能的思维导图

整段源码

student_main.java主函数

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
package student_lei;

import java.util.Scanner;
import java.util.ArrayList;

public class student_main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//定义一个集合,装入student类
ArrayList<student> arr = new ArrayList<>();
//定义初使页面,并使用死循环,退出使用system.exit(0)
while (true) {
System.out.println("-----------");
System.out.println("1.添加学生");
System.out.println("2.删除学生");
System.out.println("3.修改学生");
System.out.println("4.查看所有学生");
System.out.println("5.退出");
System.out.println("输入你的选择:");
int n = sc.nextInt();
switch (n) {
//按照输入的数字调用对应的函数
case 1 -> addStudent(arr);
case 2 -> deleteStudent(arr);
case 3 -> updateStudent(arr);
case 4 -> showStudent(arr);
case 5 -> System.exit(0);
}
}
}
//添加学生函数
public static void addStudent(ArrayList<student> arr) {
Scanner sc = new Scanner(System.in);
//定义在外面,使后面的print能够调用
String sid;
//用死循环配合isUsed函数判断是否输入相同学号
while (true) {
System.out.println("学号");
sid = sc.nextLine();
if (isUsed(arr, sid)) {
System.out.println("学号输入重复,请重新输入");
} else break;
}
System.out.println("姓名");
String name = sc.nextLine();
System.out.println("年龄");
String age = sc.nextLine();
System.out.println("居住地");
String address = sc.nextLine();
//装进student类中
student s = new student();
s.setSid(sid);
s.setName(name);
s.setAge(age);
s.setAddress(address);
//把类装到集合中
arr.add(s);
System.out.println("添加学生成功!");
}
//删除学生函数
public static void deleteStudent(ArrayList<student> arr) {
Scanner sc = new Scanner(System.in);
System.out.println("请输入要删除学生的学号:");
String sid = sc.nextLine();
//用boolean来判断是否删除成功,Java中不能把0当作false
boolean index = true;
for (int j = 0; j < arr.size(); j++) {
student s = arr.get(j);
//遍历加if,删除对应的学生
if (s.getSid().equals(sid)) {
arr.remove(j);
index = false;
System.out.println("删除成功!");
break;
}
}
if (index) {
System.out.println("学号输入错误");
}
}
//修改学生函数
public static void updateStudent(ArrayList<student> arr) {
Scanner sc = new Scanner(System.in);
System.out.println("请输入要修改的学生学号");
String n = sc.nextLine();
int temp = 0;
for (int j = 0; j < arr.size(); j++) {
if (arr.get(j).getSid().equals(n)) {
temp = j;
break;
}
}
//修改学生功能菜单
System.out.println("-----------");
System.out.println("1.修改学号");
System.out.println("2.修改姓名");
System.out.println("3.修改年龄");
System.out.println("4.修改居住地");
System.out.println("请输入你的选择");
int s = sc.nextInt();
switch (s) {
case 1 -> {
System.out.println("输入新的学号");
//与which连用时,删除缓存
sc.nextLine();
String newSid = sc.nextLine();
arr.get(temp).setSid(newSid);
System.out.println("修改成功");
}
case 2 -> {
System.out.println("输入新姓名");
sc.nextLine();
String newName = sc.nextLine();
arr.get(temp).setName(newName);
System.out.println("修改成功");
}
case 3 -> {
System.out.println("输入新年龄");
sc.nextLine();
String newAge = sc.nextLine();
arr.get(temp).setAge(newAge);
System.out.println("修改成功");
}
case 4 -> {
System.out.println("输入新居住地");
sc.nextLine();
String newAddress = sc.nextLine();
arr.get(temp).setAddress(newAddress);
System.out.println("修改成功");
}
}
}
//展示学生函数
public static void showStudent(ArrayList<student> arr) {
//判断是否有数据存入其中
if (arr.size() == 0) {
System.out.println("无数据,请先输入数据");
return;
}
//使用制表符制作表格,更好的展示
System.out.println("学号" + "\t" + "姓名" + "\t" + "年龄" + "\t" + "地址");
//可以使用增强for循环,针对只对数组,集合中对象单一遍历操作的函数
for (student s : arr) {
System.out.println(s.getSid() + "\t" + s.getName() + "\t" + s.getAge() + "\t" + s.getAddress());
}
}
//判断是否有相同学号的函数,传入集合和输入的新学号,在studentAdd函数中使用,返回值根据情况有所不同
public static boolean isUsed(ArrayList<student> arr, String sid) {
boolean n = false;
for (student s : arr) {
if (s.getSid().equals(sid)) {
n = true;
break;
}
}
return n;
}
}

student.java类

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
package student_lei;

public class student {
//学号
private String sid;
//姓名
private String name;
//年龄
private String age;
//居住地
private String address;

public student() {}
//使用command + n 自动生成构造函数,配合shift,还能生成get,set函数
public student(String sid, String name, String age, String address) {
this.sid = sid;
this.name = name;
this.age = age;
this.address = address;
}

public String getSid() {
return sid;
}

public void setSid(String sid) {
this.sid = sid;
}

public String getName() {
return name;
}

public void setName(String name) {
this.name = name;
}

public String getAge() {
return age;
}

public void setAge(String age) {
this.age = age;
}

public String getAddress() {
return address;
}

public void setAddress(String address) {
this.address = address;
}
}

如何利用IntelliJ自动生成构造函数,set(),get()函数

相信大家都很厌倦写构造函数和get,set函数了,如果你使用的是intellij,那么可以用一个快捷键来快速解决哦,用完之后我直接感动,以后再也不用像个🤡一样自己写了

Mac快捷键

command + n

Mac我会配合自己的截图,如果使用Windows,我查到快捷键的是alt + insert,用windows的小伙伴如果不清楚的话,可以搜索一下哦

先创建一个Java类,然后随便定义几个变量,按下command + n 后,会有这个界面

选你想选的,这里我选Getter + Setter,然后会有这个界面

一般来说,你只能点一个,但是如果按下shift的同时点击,就能达到我这样的多选效果

最后成果图

省时又省力,芜湖

学生管理系统初始化界面书写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
while (true) {
System.out.println("-----------");
System.out.println("1.添加学生");
System.out.println("2.删除学生");
System.out.println("3.修改学生");
System.out.println("4.查看所有学生");
System.out.println("5.退出");
System.out.println("输入你的选择:");
int n = sc.nextInt();
switch (n) {
//按照输入的数字调用对应的函数
case 1 -> addStudent(arr);
case 2 -> deleteStudent(arr);
case 3 -> updateStudent(arr);
case 4 -> showStudent(arr);
case 5 -> System.exit(0);
}
}

前面一大段输出函数,用来输出一开始的选择界面

这没说明好说的,到后面的switch(Java14增强版switch)才是重点,从一开始就可以看到,整个代码都在死循环中,目的是不断以一个不断循环的方式,执行用户的指令,只有用户输入5(退出),才能够退出系统,在刚开始写这段代码的时候,准备在case5处,写break,但是break与switch连用,被用于跳出switch ,如果在增强switch中写,就被直接提示这个break不需要,所以,需要使用System.exit(0)来直接结束程序

添加学生函数

isUsed函数

使用这个函数,是为了完成添加学生类的附加功能,判断学号是否重合

1
2
3
4
5
6
7
8
9
10
11
public static boolean isUsed(ArrayList<student> arr, String sid) {
boolean n = false;
for (student s : arr) {
if (s.getSid().equals(sid)) {
n = true;
break;
}
}
return n;
}
}

要用一个函数来判断,可以使用boolean来定义,代码中的for循环为增强for循环,一开始传入了要比较多两个数据,新输入的学号,和原来用来存学号的集合,在for循环的遍历下,用equals函数一一比较,如果发现相同,则返回true,如果没有发现相同,则返回false,把这个函数单独写出的原因是,以后可以复用,根据之前的思维导图,只有添加学生时检查了学号是否复用,如果以后有其他函数中需要判断学号是否复用,就可以调用此函数

添加学生

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
public static void addStudent(ArrayList<student> arr) {
Scanner sc = new Scanner(System.in);
//定义在外面,使后面的print能够调用
String sid;
//用死循环配合isUsed函数判断是否输入相同学号
while (true) {
System.out.println("学号");
sid = sc.nextLine();
if (isUsed(arr, sid)) {
System.out.println("学号输入重复,请重新输入");
} else break;
}
System.out.println("姓名");
String name = sc.nextLine();
System.out.println("年龄");
String age = sc.nextLine();
System.out.println("居住地");
String address = sc.nextLine();
//装进student类中
student s = new student();
s.setSid(sid);
s.setName(name);
s.setAge(age);
s.setAddress(address);
//把类装到集合中
arr.add(s);
System.out.println("添加学生成功!");
}

重点在为什么把String sid放到while循环定义外,而不是直接使用

String sid = sc.nextLine()

因为定义在while循环内的变量循环外是无法访问到的,这也是我们容易忽视的一点

删除学生函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void deleteStudent(ArrayList<student> arr) {
Scanner sc = new Scanner(System.in);
System.out.println("请输入要删除学生的学号:");
String sid = sc.nextLine();
//用boolean来判断是否删除成功,Java中不能把0当作false
boolean index = true;
for (int j = 0; j < arr.size(); j++) {
student s = arr.get(j);
//遍历加if,删除对应的学生
if (s.getSid().equals(sid)) {
arr.remove(j);
index = false;
System.out.println("删除成功!");
break;
}
}
if (index) {
System.out.println("学号输入错误");
}
}

这个函数中,比较重要的是对于index的使用,我是第一次碰到,删除成功很好输出,跟在remove的后面就行了,但是输出失败(学号输入错误)的提示该放在哪呢,如果直接放在for循环外,那么输出成功后也会提示输出失败,所以,需要把加一个判断条件index,如果输出成功,就把index赋值为false,这样就不会在输出成功后也提示输出失败了

修改学生函数

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
public static void updateStudent(ArrayList<student> arr) {
Scanner sc = new Scanner(System.in);
System.out.println("请输入要修改的学生学号");
String n = sc.nextLine();
int temp = 0;
for (int j = 0; j < arr.size(); j++) {
if (arr.get(j).getSid().equals(n)) {
temp = j;
break;
}
}
//修改学生功能菜单
System.out.println("-----------");
System.out.println("1.修改学号");
System.out.println("2.修改姓名");
System.out.println("3.修改年龄");
System.out.println("4.修改居住地");
System.out.println("请输入你的选择");
int s = sc.nextInt();
switch (s) {
case 1 -> {
System.out.println("输入新的学号");
//与which连用时,删除缓存
sc.nextLine();
String newSid = sc.nextLine();
arr.get(temp).setSid(newSid);
System.out.println("修改成功");
}
case 2 -> {
System.out.println("输入新姓名");
sc.nextLine();
String newName = sc.nextLine();
arr.get(temp).setName(newName);
System.out.println("修改成功");
}
case 3 -> {
System.out.println("输入新年龄");
sc.nextLine();
String newAge = sc.nextLine();
arr.get(temp).setAge(newAge);
System.out.println("修改成功");
}
case 4 -> {
System.out.println("输入新居住地");
sc.nextLine();
String newAddress = sc.nextLine();
arr.get(temp).setAddress(newAddress);
System.out.println("修改成功");
}
}
}

看起来有一大段代码,但是重要的只有一行代码,就是

sc.nextLine();

在switch中用nextLine(),需要先用上面的代码,否则在运行的时候会直接当你输入的值为空,具体为什么我没查到,但我猜跟nextInt()和nextLine()一起用的问题相似

展示学生函数

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void showStudent(ArrayList<student> arr) {
//判断是否有数据存入其中
if (arr.size() == 0) {
System.out.println("无数据,请先输入数据");
return;
}
//使用制表符制作表格,更好的展示
System.out.println("学号" + "\t" + "姓名" + "\t" + "年龄" + "\t" + "地址");
//可以使用增强for循环,针对只对数组,集合中对象单一遍历操作的函数
for (student s : arr) {
System.out.println(s.getSid() + "\t" + s.getName() + "\t" + s.getAge() + "\t" + s.getAddress());
}
}

比较重要的就是制表符的使用,在学C语言时就把**\t**叫制表符,这次使用\t按表格输出数据,会有更好的展示效果

后记

到此,需要注意的点都讲完了,这个管理系统虽然简单,但是在写它的过程中,我还是发现了许多我之前不知道的知识,算是有所收获吧,我也会经常拿这篇文章看看,复习一下,如果太长时间不敲,也会忘记,我一般复习的时候,会同时打开intellij和sublime,先用sublime敲一下代码中比较重要的部分,在对照intellij看看写错没有,只需要敲比较重要,容易出错的地方就行,希望大家也能多多复习哦👾

简介

这个博客参考左孝陵先生的《离散数学》,会尽量简单的讲讲笛卡尔积,能够给大家一个更加具体的认识。

什么是序偶

要知道什么是序偶,先得弄明白序偶的作用,我觉得序偶就是带顺序的集合,用来表示一些集合表示不了的东西。比如在小学学的直角坐标系上,有两个点,(2,3)和(3,2),点的坐标就是序偶,因为它自带顺序,为什么每次一个点都先读x坐标再读y坐标?是因为规定了顺序,才能表示更多的点。坐标系如果用集合来表示坐标,那{2,3},{3,2}就是同一个点了。

再举一个例子吧,老师对同学们说报出你们的身高体重,你有一米八,体重190斤。你如果说“190,180”老师会认为你是一米九,体重180斤,因为老师问的时候带了一个顺序,问的是序偶,身高到体重,如果你按体重到身高报,就完全错了

什么是笛卡尔积

令A和B是任意两个集合,若序偶的第一个成员是A的元素,第二个成员是B的元素,所有这样的序偶集合,称为集合A和B的笛卡尔乘积或直积,记做A X B

如果觉得定义太抽象,也没有关系,让我们继续之前老师记身高体重的例子,再没有你这种反着来报体重身高的人后,老师很快就得到了全班同学的身高体重表格,

身高 体重
170 140
180 190
190 180
…… ……

看看这个表来源于什么,来源于全班同学的身高的集合A,体重的集合B。那么,全班同学的体重身高就可以表示为A X B,全班同学的体重身高就可以表示为B X A

更加严谨的表达方式

假设身高集合为A={a1,a2,a3,a4……an},体重集合为B = {b1,b2,b3,b4,b5……},那么A X B = {<a1,b1>, <a1,b2> ,<a1, b3>,……<a1,bn>,<a2,b1>,<a2,b2>……<an,bn> }

具体特征是a永远在前面,b永远在后面,因为是A X B,一共有n X n 个元素,因为A,B数组的元素个数为n,n

笛卡尔积与函数的联动

有这样一个函数,定义域为x,值域为1,那么这个函数可以表示为 R X 1的子集,能不能画出这个题的图像呢?

y = 1函数图像

其实我根据定义域和值域就用y = 1来画这个题的图像是不严谨的,应该说,这题是运气好才能画出图像,但是不可能确定表达式,因为决定函数的是定义域和对应关系。比如这题的函数可以是

但我想表达的是,函数的图像,不可能超过它定义域和值域的笛卡尔积,而是被包含在笛卡尔积的图像之中,我能准确的画出这个题的图像,是因为R X 1这个笛卡尔积,结果是一条直线,导致函数图像的可能性降低,所以能画出图像。

如果我告诉你定义域为[-3,3],值域为[-3,3],是肯定画不出图像,确定不了函数的,但是我可以肯定的是,函数的图像一定在[-3,3] X [-3,3]的正方形图像当中

简单更一下,最近关于插入排序和归并排序的博客还没写完,在写的过程中,难免要用到数学公式,如果要在hexo使用latex写数学公式的话,需要mathjax插件,为了这事,弄了两天,按照别人的教程一步步走,就是一直装不上,不知道是不是Mac Os系统的原因,不过Mac上有ipic这个神器,以后博客的公式部分,我会写好了截图,在用ipic把图片上传。

算法基础的后面一章,是为第三章打基础的,基本上全是数学,没啥算法,所以不用latex完全写不了,这也是我这几天这么急着装mathjax的原因,提前剧透一下,下一章比较硬核哦,这个博客的初衷就是把知识讲简单,但是还是避免不了使用数学公式,请做好心理准备哦~

由于公式渲染不出来,先看看两种效果吧

latex在hexo中直接写公式,渲染失败例

$ a_{1}^n $

在我的typora中这行代码是这样的

悲💩

这篇文章主要是依照《算法导论》这本书来写的,期间边看书边看MIT的公开课 ,课是本书的作者之一讲的,这篇文章我会着重讲讲我听不明白的一些问题,并一一解决,文章篇幅较长,希望能耐心看完哦。

简单的介绍

回忆起第一次接触排序问题,是在大一的C语言课上,老师要我们通过两个for循环把一个数组中的元素从小到大排序,看着网上的技术博客勉勉强强写出来后,才知道这叫做冒泡排序,再后来,学了把两个有序的数组合并成一个大的有序数组,也就是这次归并排序的雏形。学习Java后,遇到排序问题,一般直接调用sort函数。仔细想想,其实我们排序数组的方法有那么多种,怎么写代码去实现的方法就更多了,那种好一些,那种坏一些,我从来没有仔细探究过,但在《算法导论》中,作者并没有强调源码怎么写,而是探究更深层次的问题,代码的性能优劣。

什么是性能

性能就是程序的运行速度,但是,一个程序的优劣,不仅仅要看性能,还要看许多其他的方面,比如安全性,可维护性。

打个比方吧,假如你是一名学霸,每次考数学的时候,你都能提前半个小时把卷子写完,然后潇洒地提前交卷,但是,你总是跟全班第一差10分,你很苦恼,去问数学老师,老师说,你下次写慢点,不确定的题多检查一下,把字迹写工整一些。果然,下一次考试,你虽然没有像以往一样提前交卷,但你成了全班第一。

通过这个比方,我们可以知道,把卷子写的飞快,但是无法保证正确不行,字迹不工整不行。回到代码,一个程序,一秒钟就执行完了,但是结果是错的,另一个程序,一分钟才执行完,但是保证百分百正确。同样的例子还有很多,性能嘛,跟正确性,安全性等等没法比。**但是就像MIT的公开课里说的,性能就像货币,人要的不是更多的钱,而是钱能买来的东西。**尽管同样的程序,Java写的比C要慢很多,但是我们愿意用Java写程序,因为它能实现更多的功能。性能总是作为牺牲,去满足别的需求,这就是性能为什么处于底层的原因。

让我们通过一个都遇到过的例子来再说明一下吧。学习C语言时,都学多scanf函数吧,当我们兴奋的把写好的程序给同学运行时,同学往往不知道要输入啥,这时,我们需要用printf(“请输入一个XX数:”),来提示同学要输入什么内容,加上这一段代码,程序就变得*“冗余”*了一些,多运行了一段代码,稍微慢了一些,但是,加强了我们代码的可读性。

说了这么多,相信大家都明白了性能的含义和作用,那么让我们来看看第一个算法——插入排序吧!

插入排序

插入排序的伪代码

1
2
3
4
5
6
7
for j = 2 to A.length   //从第二个数遍历到数组末尾,j代表要比较的数
key = A[j] //记录A[j]的初始值
i = j - 1 //i代表j的后一个数
while i > 0 and A[i] > key
A[i + 1] = A[i]
i = i - 1
A[i + 1] = key //把A[j]的初始值赋给最后i前面的一个数

先讲一下伪代码,主要有两个作用,用最简的语言表示算法,让无论学过什么语言的人都能最快看懂。最简不用多说,没分号,没大括号,循环用缩进表示,颇有python内味,我在原书代码的基础上加了一些注释,相信要看懂更加容易了。如果实在看不懂伪代码,可以看这篇博客,里面用各种语言写了插入排序。

我曾经做了一个作死的尝试,写了篇名叫不用代码讲插入排序的文章,后来写的冗长不说,意思也表达不清,索性作罢,用伪代码讲算法,虽然抽象,但是精确,简洁。

让我们用一串数组,来描述这个代码的执行过程

{1, 2, 3, 5, 4}

要把这个数组变成{1, 2, 3, 4, 5}会经历什么过程呢?

1, 2, 3, 5, 5 第一步

1, 2, 3, 4, 5 第二步

我们可以看到,其实,伪代码主要实现两种功能

前提

在上面的例子中,要排序4这个数,前提是4前面的数必须有序,因为排序是从2个数到3个数到4个数……排序3个数的基础是前面的2个数已经排好了,所以不要用类似{2,1,3,5,4}这样的不标准数组来测试代码哦,同时伪代码的数组并非从0开始,而是从1开始,A[5]的元素有A[1,2,3,4,5]而不是A[0,1,2,3,4]。

移动

1
2
3
while i > 0 and A[i] > key
A[i + 1] = A[i]
i = i - 1

先看while中后面的那一部分,A[i] > key,配合后面的i = i - 1,从j的后面一个数开始,从后往前跟A[j]比大小

i > 0是为了确定数组是否到头的,如果i自减到0,while循环就会停止

看前面的文章可以知道,key就是要插入的那个值,假设数组中的第五个数也就是A[5]的值是key,A[4],A[3],都比key大,A[2]比key小,如数组{1,2,4,5,3},那么请拿出一张草稿纸,试着执行一下循环里面的代码。执行完循环之后,会得到这样一个数组{1,2,2,4,5},i最后自减完的值是2,如果细心的话,会发现数组中元素的位置已经移动了,比3大的4和5,已经从原来的位置往后移动了一位,这时,只需要把第3个位置的2换成3,数组的排序就完成了。

插入

实现插入的代码只有一行

1
A[i + 1] = key 

再用{1,2,4,5,3}举例子,我们进行完移动的操作后,得到的成果有{1,2,2,4,5}以及一个i值,i = 2

这里的i为插入操作进行引导,执行完A[i] > key和i的自减后,我们可以知道,i前面的值都比key值小,A[i] = A[i + 1],只需要把A[i + 1]替换为原来的A[j]值,即key,排序就完成了,看似是插入,如果执行过一遍程序后,就知道其实应该叫做替换。

代码运算时间分析

该从哪个角度分析?

运算时间受到的影响太多了,同样的代码,在超算和个人电脑上,运算时间肯定不同,个人电脑中,处理器型号,内存大小,也会导致执行的速度也不一样,但是,现在,我们仅从代码写法的角度来讨论运算时间的问题,而且是在最差的情况下的时间。

为什么是最差的情况

任何一个程序需要尽可能考虑差的情况,比如,一个排序数组的程序,在别人运行的时候,事先说明,本程序排序完全颠倒的数组会很慢(类似{5,4,3,2,1}),其他时候都挺快的,我觉得挺可笑的。一个程序设计的初衷就是要满足客户的各种合理需求的。记得在高考填志愿的时候,我不止一次抱怨填报志愿的网站做的差,好歹是全国人都会用的系统,为什么这么的“简朴”,后来经历过英语六级报名日语n2报名后,发现其实做的网站都这样。后来仔细一想,其实全国的电脑中很大一部分是事业单位,高中机房中的老式电脑,不仅装的是XP系统,还装有360系,毒霸系的流氓软件,要是网页做的跟苹果官网一样,一些电脑真不一定打得开。这些官方报名网站,设计时就考虑了兼容性的情况,同样,我们的代码也要考虑最差的情况。

再看一次伪代码

1
2
3
4
5
6
7
for j = 2 to A.length                a1 
key = A[j] a2
i = j - 1 a3
while i > 0 and A[i] > key a4
A[i + 1] = A[i] a5
i = i - 1 a6
A[i + 1] = key a7

a1,a2……a7对应的每一行代码的执行时间

在输入后,我们规定运算总时间是T,T的值应该为
T =n1a1 + n2a2 + ……n7a7

根据前面,算法要考虑最坏的情况,所以,我们默认排序的数组都是像{5,4,3,2,1}这种完全相反的数组,我们就可以得到n元素数组排序的最长时间。

1
2
3
4
5
6
7
for j = 2 to A.length                  a1		n
key = A[j] a2 n - 1
i = j - 1 a3 n - 1
while i > 0 and A[i] > key a4 2 + …… + n
A[i + 1] = A[i] a5 1 + …… + n - 1
i = i - 1 a6 1 + …… + n - 1
A[i + 1] = key a7 n - 1

后面的数代表执行次数,下面我来逐行讲解
1 从2到n的遍历,看似应该执行n - 1次,但是循环的条件句最后还要判断一下,所以加一,如果这里不明白,可以看第4行代码的讲解
2 每对应一个j值,都执行一次,共有n - 1个j值,执行你n - 1次
3 与第2行一样
4 由于是最差的情况,所以i每次都会自减到0,当i自减到0后,虽然循环内的代码不用执行,但是,是不是大于0还得比较一下,所以第4行代码是j为几就执行几次
5 相比于第4行代码,每个j值都少一次i的值的判断,所以每轮执行次数都为j - 1,所以为从1到n - 1的和
6 与第5行相同
7 与第2行相同

这个博客创立的初衷是记录自己的学习和生活,后续每个星期会更新一篇长文,水品不一定高,但是我一定会竭尽全力把它写好,同时也会写一些生活趣事。如果每年的9月30号,打开博客,能看到自己一年的成长,也是件幸福的事。

为什么要自己建博客,不直接将博客发在类似csdn的博客论坛上?

有自己的博客,能给我一种在经营自己的家的感觉,如果把博客发在csdn,当然可以,但是总觉得少了点什么。这个博客是用hexo框架+next主题搭建github pages上的,博客是免费的,只有www.chinesesheep.com 这个域名花了我55元。虽然有点水,但是也能满足我的基本需求,如果搭建动态博客,需要的自己租服务器,而且也更难配置,我现在刚上大二,等以后学习了一些前端知识,再考虑优化一下这个博客或者再搭建一个动态博客。

一篇长文内容是什么?

以后每个月会有一个总计划,规划一下这个月要写哪些内容,我对自己的要求是写别人写的少的,同时比较重要的知识,会尽量写的详细,有趣一些。

这个博客的目标

就像我之前说的那样,没什么远大的理想,就像写日记一样,用来记录自己的成长,君子耻其言而过其行,决定了什么事,赶紧开始做吧!