缘来我们在这里

乱世天狼的博客


  • 首页

  • 归档

原来是梨

发表于 2018-01-06

演员

小猪(蓝色台词,岳哥),楼兰(橙色台词,岳嫂),硫磺火(加粗台词,郭子媳妇小丽),白堤(倾斜台词,郭子)

参考资料

暴走大事件2017关键词:freestyle 要这么秀的么 令人窒息的操作 打call 在此地不要走动,我去买几个橘子 戏精 贫穷限制了我的想象力 开始你的表演 十九大 新时代 共享 雄安新区 人工智能 人类命运共同体 天舟一号 撸起袖子加油干 不忘初心,牢记使命 好意外好惊喜

剧情简介

地点:岳哥家里
时间:临近过年
剧情梗概:岳哥是拼多多运营,平时在家妻管严,马上要过年,一周前岳嫂给了岳哥1000元钱置办年货,岳哥拿去买了酥梨。岳哥不敢寄到自己家,只好寄到自己好兄弟郭子家里。岳嫂见岳哥微信上钱没了,但是年货却没有置办,在家审问岳哥。这时,没办法解释寄到自己家中梨的郭子,被老婆逼得没有办法,来找岳哥讨个说法,然后发生了一系列的趣事

开场

岳哥上场

岳哥拿着拖把上场,面对观众:大家好,我叫岳帅哥,帅哥的帅,帅哥的哥,平时爱甩锅,也有朋友私下叫我岳甩锅。社会你岳哥,人狠话又多,别的全不怕,就是怕老婆。这不我老婆出门逛街,让我在家作家务。

叮咚(门铃响),岳嫂:开门儿

岳哥:呦,这不我老婆回来了。
说:老婆快坐下歇会,老婆,你这手里拿啥。

岳嫂:这不玩具嘛,过年回家给小孩的

岳哥接过来玩具,放桌子上,说:老婆累坏了吧,快坐着歇一会。
然后继续拿拖把打扫卫生

岳嫂坐下,腿翘到桌子上,说:这走了一天,腿有点酸啊。斜看岳哥一眼。

岳哥:得嘞。上去捶腿

岳嫂:走了一天,这嗓子有点干不舒服啊

岳哥:得嘞,老婆你等着。转身去倒矿泉水,倒了之后双手端给老婆。

岳嫂喝了一口,说:这水味道有点淡啊

岳哥:得嘞,老婆你等着,给你倒杯橙汁。转身过去倒杯橙汁,双手端给老婆。

岳嫂喝了一口,说:怎么突然那么想喝奶茶啊

岳哥:差不多得了啊,爱喝不喝

岳嫂站了起来:岳甩锅,胆挺肥啊,谁给你的勇气?

岳哥笑着贱贱的说:梁静茹啊。


岳嫂站了来,走两步到一边去,生气状

岳哥安抚:老婆你别生气啊,听我给你解释。然后岳哥解释,岳嫂转身,岳哥解释,岳嫂转身。最后面向观众。
岳哥:老婆大人莫生气,气坏身体无人替;为了小事发脾气,回头想想又何必;小人量小不让人,常常气人气自己;君子量大同天地,大事小事包心底。老婆,咱家饮料真的只剩矿泉水和橙汁了,真没了。

岳嫂坐了下去,双臂交叉:说说吧,到底咋回事

岳哥:啥咋回事啊

岳嫂生气:别给我装糊涂,我上周刚给你转了1000块钱,让你去买年货,我今天查了你的银行卡,微信和支付宝,钱没了,货呢?

岳哥:在路上呢,这不下雪了么

岳嫂:那把购物记录给我看下

岳哥:老婆,你还不相信我么?看什么看啊

岳嫂:快点

岳哥:老婆,我跟你说实话吧,钱,我丢了!

岳嫂蔑笑:我微信转你的,你跟我说说你怎么丢的?

岳哥:手机丢了

岳嫂打电话,岳哥手机在兜里响(拼多多之歌)

岳嫂大怒:这一天天的一句实话都没有,这日子没法过了,离婚,跑到卧室去找户口本

岳哥跟着岳嫂到卧室安抚,退场。郭子上场。
郭子,面向观众:我叫郭北,郭北的郭,郭北的北。我是一名程序员,平常老婆管的严。兜里不揣一块钱,支付宝密码老婆管,微信余额不许超过200元。前天家里收了一车梨,岳哥说给我礼物过新年,老婆知道了问我话,问我哪来那么多钱,想来想去怎么办,来他家里问问看
郭子:岳哥,岳哥?嫂子,嫂子?这门咋还没关呢?
走到客厅,听见卧室在乒乒乓乓在响
郭子:这卧室啥声音,不会是~。哎吆卧槽,还挺激烈啊。
郭子趴到门口偷听。声音传来。
砰,卧室门打开,碰到郭子,郭子捂着头叫,哎呦


岳嫂:不给我解释清楚,今天必须离


岳哥:老婆你听我解释。
岳哥看到郭子,忙拉到一边,说:兄弟帮哥个忙,一会你就告诉你嫂子前一阵手里缺钱,借了我一千块钱,千万记住了,事成之后,哥请你大保健


郭子:知道了哥,不过,那梨~


岳嫂正好走过来,说:郭子,你刚说什么?

郭子:梨


岳嫂大怒:好啊,老岳,连郭子都知道了,你这是早有预谋啊,刚才还跟我装什么装

岳哥安抚:老婆,其实不是那回事,对了,我想起来钱哪里去了。这不,前一阵郭子手里缺钱,我就先借给他了,是不是,郭子?使眼色

郭子:对对对,前一阵,岳哥手里缺钱,借了我一千,去做大保健


岳哥,岳嫂:啥?

郭子:瞧我这破嘴,前一阵,我缺钱,借了岳哥一千,去做大保健


岳嫂:啊,你怎么能这样?郭子,不是我说你,小丽在家对你不错吧,你怎么能做对不起她的事呢!等着,我这就给她打个电话。

岳嫂,起身打电话,岳哥拉着郭子到一边

郭子:嫂子,别啊,不是那回事


岳哥拉郭子到一旁:你瞎说啥玩意,还有,你今天到底来干嘛了?

郭子:哥,你的新年礼太重啊,500多斤梨,要这么秀的么,我买梨一次只卖4-5斤,您这一出手就是4,500斤。真是贫穷限制了我的想象力。现在我这早中晚三顿全是梨,现在看到梨想吐,吃了梨拉肚,闻到梨味儿都浑身不舒服。你弟妹还问我哪来的钱,我说你送的礼她也不信啊。这不我就想问问你,咋买了这么多的梨,还都寄给我了?


岳哥:这次,哥要让你刮目相看,你看,拼多多最近上线了‘爱心助农’活动。今天果农大丰收,但是没有销路,可能辛辛苦苦一年,最后还不落钱。你岳哥我也是农民出身,这不饮水思源,想帮他们一把,就把老婆给我置办年货的钱,买了梨,我又不敢让她知道,只能先寄给你了。

郭子:你爱心助农是好事,就是苦了我啊,一会儿还不知道怎么跟小丽解释呢

小丽上场,小丽面向观众:我叫小丽,郭子老婆,我家那位程序员,平时被我管的严,手里从来不存钱,嫂子突然来电话,说他拿钱做大保健。我得过来瞅瞅

咚咚咚,小丽:嫂子


岳嫂:小丽啊,快过来吧,这郭子出事了

小丽:我就说他前天晚上一晚上没回家,没想到,真是反了,看我不收拾他
岳嫂,小丽对着郭子,岳哥
小丽:郭子,说说吧,前天晚上去哪里了?
郭子:老婆,你还不相信我嘛,我怎么可能做对不起你的事呢,前天晚上我们服务上线,我下班的时候,你早上班走了
小丽:那嫂子说你亲口说的大保健咋回事?
郭子:没啥事,大保健是一家新开的酒店,人家是宝剑的宝,宝剑的剑


岳哥:你这说了跟没说有啥区别,人家酒店的名字是,宝剑锋从磨砺出,梅花香自苦寒来的宝剑

郭子:对对对,就是这个。急中生智,拿起那个玩具比划
岳嫂,小丽:你们哪来的钱?
郭子:岳哥,反正也不是啥坏事,咱干嘛偷偷摸摸的,我可说了哈。其实事情是这样的,面向观众:嫂子让岳哥办年货,岳哥就去了拼多多,‘爱心助农’真不错,岳哥一次花了一千多,买梨回来怕嫂子说,就在我家先放着,这令人窒息的操作,可坑苦了郭子我,老婆说我有点虎,人家一年三百六,我这一年二百五。岳甩锅啊岳甩锅,以后锅可别再甩给我。


岳嫂:真的么?

岳哥:老婆,我敢骗你么,给你看,这是购物记录,’郑爷爷的酥梨‘,500斤,这不,真真的!

小丽:嫂子给我看下呗。拿过去看了下
小丽:郭子,岳哥这做的是好事啊,我看我们得再买700斤
郭子摸摸老婆额头,说:老婆你不是发烧了吧,买那么多,可咋整啊
小丽:你忘了我是产品经理了,听我的,没错的。原来500斤,再有700斤,也就是1200斤,拼多多员工1200多个,一人一斤我还怕不够呢
郭子:此情此景,我想作诗一首,啊
小丽:得了吧,别丢人了,还不回去?
郭子:回回回,这就回

岳哥,岳嫂:你俩回来,还没给观众拜年呢?

站位顺序从左到右,小猪,楼兰,白堤,硫磺火
小猪:值此新春佳节之际,我小猪
楼兰:楼兰
白堤:白堤
硫磺火:硫磺火
齐拱手:祝大家新春吉祥,万事如意

react

发表于 2017-12-12

引子

子曰:愚而好自用,贱而好自专。生乎今之世,反古之道。如此者灾及其身者也。

非天子不议礼,不制度,不考文

今天下,车同轨,书同文,行同伦

虽有其位,苟无其德,不敢作礼乐焉。虽有其德,苟无其位,亦不敢作礼乐焉。

子曰:吾说夏礼,杞不足徵也。吾学殷礼,有宋存焉。吾学周礼,今用之,吾从周。

–《中庸》

正文

高阶函数

高阶函数:高阶函数,又称算子(运算符)或泛函,包含多于一个箭头的函数。

原理:在数学和计算机科学中,高阶函数是至少满足下列一个条件的函数:

  • 接受一个或多个函数作为输入
  • 输出一个函数

在数学中它们也叫做算子(运算符)或泛函。微积分中的导数就是常见的例子,因为它映射一个函数到另一个函数

高阶组件

高阶组件(HOC)是一个复用组件逻辑的高级技巧。这并不是react的API,而是和react组件可以自然的组合运用。

具体的说:一个高阶组件就是一个函数,接收一个组件,返回一个新的组件

1
2
3
function(){
console.log(1231231)
}

高效学习

发表于 2017-11-20

引子

大哉圣人之道!

洋洋乎,发育万物,峻极于天。

优优大哉,礼仪三百威仪三千。

待其人而後行。

故曰:苟不至德,至道不凝焉。

故君子尊德性,而道问学,致广大,而尽精微,极高明,而道中庸。温故,而知新,敦厚以崇礼。

是故居上不骄,为下不倍。国有道,其言足以兴;国无道,其默足以容。诗曰:既明且哲,以保其身。其此之谓与?

– 《中庸》

正文

时间

只需要20小时就能不错的掌握一个全新的知识和技能

案例

Scott Young 的学习方法白诗诗整理

关于 Scott Young

可行性

一天的高效学习时间安排在八个小时左右

如何保证利用好自己的高效时间

学习仪式感

人,藉由这种仪式感,来给自己一种强烈的自我暗示—-这种自我暗示能够使自我变革,使自己的专注力、反应能力、运动能力迅速提升。

物质:准备好所有需要的东西,避免需要的时候手忙脚乱
精神:记住第二天又要进行高效学习了,同时如果当天学习很好的化,会在满足和期待中睡去
时间:提前赶到你的常用学习场所

启用仪式感的步骤:

启动

  1. 把准备好的物品摆在桌上
  2. 深呼吸一口气,然后做眼保健操
  3. 闭着眼按摩太阳穴一个八拍

预热

翻看即将在要来到的两个小时内需要学习的内容,心里有个大概。

静心

停止动作,静待时间流逝,时间一到,带着喜悦和平静开始学习工作

正式高效率学习

  1. 看目录,了解这一节大概用来解决什么问题
  2. 看章后习题,圈出术语,术语基本上就是本章的重点了
  3. 根据术语去书中划概念和术语解释
  4. 术语理解后带着术语去理解书中的图标和例题以及案例

为什么不直接阅读文字?

带着问题能更好的掌握要学习的知识和技能

能量分为身体能量和情绪能量

  • 身体能量:零食补充
  • 情绪能量:放松,放松,放松,音乐,健身等

时间一长,我们能记住关于一件事物的主要部分其实就是事物留给我们的感觉而不是事件本身。

如果你在对学习感到糟糕的时候,结束一天的学习,真的很蠢,所以恰如其分的中断学习也很重要。

对人也一样,不要等到他厌烦的时候走,要等他欲拒还迎的时候走,在欢愉的峰值过后的末期撤离

回顾

全面回看一下你所学习的知识点,脑子里同时过一下,知道这一章讲的什么内容。

做题

a计划:找例题,做例题。做完对答案,紧接着完整抄一遍标准答案 –> 去章后看看有没有会做的题目,有就做 –> 没有就回来看例题 –> 循环往复。如果立体抄完依然没有头绪,可以进行b计划。

b计划:圈出重复出现的关键词以及章后含有的术语,再进一步去阅读相关知识点的概念、案例、图表。

当一本教材用如上的方法进行完毕,及时找到测试试卷做一次测试。

成绩达不到目标,要重新巩固提高

制定一个作息时间

其他

  • 下班后,洗完澡就去学习两小时,就能让自己一年后升值几千,甚至几万,这才是聪明的买卖
  • 闭眼前和睁眼后的半个小时,用翻书代替玩手机
  • 制定周目标

名言警句

书山有路勤为径,学海无涯苦作舟

弈秋,通国之善弈者也。使弈秋诲二人弈,其一人专心致志,唯弈秋之为听;一人虽听之,一心以为有鸿鹄将至,思援弓缴而射之。虽与之俱学,弗若之矣。为是其智弗若与?曰:非然也。

c语言简要

发表于 2017-11-13

引子

故至诚无息。

不息则久,久则征。

征则悠远。悠远,则博厚。博厚,则高明。

博厚,所以载物也。高明,所以覆物也。悠久,所以成物也。

博厚,配地。高明配天。悠久,无疆。

如此者,不见而章,不动而变,无为而成。

天地之道,可一言而尽也。其为物不贰,则其生物不测。

天地之道,博也,厚也,高也,明也,悠也,久也。
今夫天斯昭昭之多,及其无穷也,日月星辰系焉,万物覆焉。今夫地一撮土之多,及其广厚载华岳而不重,振河海而不泄,万物载焉。今夫山一石之多,及其广大,草木生之,禽兽居之,宝藏兴焉。今夫水,一勺之多,及其不测,鼋,鼍,蛟,龙,鱼,鳖生焉,货财殖焉。

诗云,【维天之命,于穆不已】。盖曰,天之所以为天也。【于乎不显,文王之德之纯】。盖曰,文王之所以为文也,纯亦不已。

–《中庸》

正文

简介和环境设置

略

程序结构

  • 预处理器指令
  • 函数
  • 变量
  • 语句 & 表达式
  • 注释

示例:

1
2
3
4
5
6
#include <stdio.h>
int main(){
/* 我的第一个c程序 */
printf("Hello, World! \n");
return 0
}

基本语法

c 的令牌(Tokens)

c程序由各种令牌组成,令牌可以是关键字,标志符,常量,字符串值,或者是一个符号。例如下面的c语句包括5个令牌:

1
2
3
4
5
printf
(
"Hello, World! \n"
)
;

分号

在c程序中,分号是语句结束符。也就是说,每个语句必须以分号结束。它表明一个逻辑实体的结束。
例如,下面是两个不同的语句:

1
2
printf("Hello, World! \n");   
return 0

注释

例:

1
/* 我的第一个c程序 */

标识符

c标识符是用来标识变量、函数,或任何其他用户自定义项目的名称。一个标识符以字母A-Z或a-z或下划线_开始,后跟零个或多个字母、下划线和数字(0-9)

c标识符内不允许出现标点字符,比如@、$和%。c是区分大小写的编程语言。例:

1
mkhd zara abc move_name a_123 myname50 _temp j a23b9 retVal

关键字

auto else long switch break enum register typeof case extern return union char float short unsigned const for signed void continue goto sizeof volatile default if static while do int struct _Packed double

c中的空格

只包含空格的行,被称为空白行,可能带有注释,c编译器会完全忽略它。

在c中,空格用于描述空白符、制表符、换行符和注释。空格分隔语句的各个部分,让编译器能识别语句中的某个元素在哪里结束,下一个元素在哪里开始。因此,在下面的语句中:

1
int age;

在这里,int和age之间必须至少有一个空格字符,这样编译器才能够区分它们。另一方面,在下面的语句中:

1
fruit = apples + oranges; // 获取水果的总数

fruit和=,或者=和apples之间的空格字符不是必须的,但是为了增强可读性,您可以根据需要适当增加一些空格。

数据类型

数据类型指的是用于声明不同类型的变量或函数的一个广泛的系统。变量的类型决定了变量存储占用的空间,以及如何解释存储的位模式。

  • 基本类型:整数类型和浮点类型
  • 枚举类型:被用来定义在程序中只能赋予其一定的离散整数值的变量
  • void类型:类型说明符void表明没有可用的值
  • 派生类型:指针类型、数组类型、结构类型、共同体类型和函数类型

变量

变量的定义

语法

1
type variable_list

例子:

1
2
3
4
int i,j,k;
char c,ch;
float f,salary;
double d;

变量可以在定义的时候初始化。例:

1
2
3
4
extern int d = 3, f = 5;
int d = 3, f = 5;
byte z = 22;
char x = 'x';

不带初始化的定义:带有静态存储持续时间的变量会被隐式初始化为NULL(所有的字节都是0),其他所有变量的初始值是未定义的。

变量的声明

  • 需要建立存储空间的。例如:int a在声明的时候已经建立了存储空间。
  • 不需要建立存储空间的,通过使用extern关键字声明变量名而不定义它。例如:extern int a其中变量a是可以在 别的文件中定义的。
  • 除非有extern关键字,否则都是变量的定义
    1
    2
    extern int i; //声明,不是定义
    int i; //声明,也是定义

实例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 变量声明
extern int a,b;
extern int c;
extern float f;
int main(){
/*变量的定义*/
int a,b;
int c;
float f;
/*初始化*/
a = 10;
b = 20;

c = a + b;
printf("value of f : %f \n", f);
return 0
}

C中左值(Lvalues)和右值(Rvalues)

  1. 左值(lvalue):指向内存位置的表达式称为左值(lvalue)表达式。左值可以出现在赋值号的左边或右边。
  2. 右值(rvalue):术语右值(rvalue)指的是存储在内存中的某些地址的数值。右值是不能对其进行赋值的表达式,也就是说,右值可以出现在赋值号的右边,但不能出现在赋值号的左边。

变量是左值,因此可以出现在赋值号的左边。数值型的字面值是右值,因此不能被赋值,不能出现在赋值号的左边。例

1
int g = 20;

错误:

1
10 = 20

常量

常量是固定值,在程序执行期间不会改变。这些固定的值,又叫做字面量。

常量可以是任何的基本数据类型

把常量定义为大写字母形式,是一个很好的编程实践。

存储类

存储类定义c程序中变量/函数的范围(可见性)和生命周期。这些说明符放置在它们所修饰的类型之前。c程序中可用的存储类:

  • auto
  • register
  • static
  • extern

auto 存储类

auto 存储类是所有局部变量默认的存储类。

1
2
3
4
{
int mount;
auto int month;
}

上面的实例定义了两个带有相同存储类的变量,auto只能用在函数内,即auto只能修饰局部变量。

register 存储类

register 存储类用于定义存储在寄存器中而不是RAM中的局部变量。这意味着变量的最大尺寸等于寄存器的大小(通常是一个词),且不能对它应用一元的’&’运算符(因为它没有内存位置)。

1
2
3
{
register int miles;
}

寄存器只用于需要快速访问的变量,比如计数器。定义为’register’并不意味着变量将被存储在寄存器中,它意味着变量可能存储在寄存器中,这取决于硬件和实现的限制。

static 存储类

static 存储类指示编译器在程序的生命周期内保持局部变量的存在,而不需要在每次它进入和离开作用域时进行创建和销毁。因此,使用static修饰局部变量可以在函数调用之间保持局部的值。

static修饰符也可以应用于全局变量,当static修饰全局变量时,会使变量的作用域限制在声明它的文件内。

static是全局变量的默认存储类

1
2
3
4
5
6
7
static int Count ;
int Road;

main(){
printf("%d\n", Count);
printf("%d\n", Road);
}

实例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>

/*函数声明*/
void func1(void);

static int count=10; /*全局变量 - static是默认的*/
int main(){
while(count--){
func1();
}
return 0;
}

void func1(void){
/* 'thingy'是 'func1' 的局部变量 - 只初始化一次
* 每次调用函数 'func1' 'thingy' 值不会被重置。
*/
static int thingy=5;
thingy++;
printf("thingy 为 %d, count 为 %d\n", thingy, count);
}

extern存储类

extern 存储类用于提供一个全局变量的引用,全局变量对所有的程序文件都是可见的。当您使用‘extern’时,对于无法初始化的变量,会把变量名指向一个之前定义过的存储位置。

当您有多个文件且定义了一个可以在其他文件中使用的全局变量或函数时,可以在其他文件中使用extern来得到已定义的变量或函数的引用。可以这么理解,extern是用来在另一个文件中声明一个全局变量或函数。
extern 修饰符通常用于当有两个或多个文件共享相同的全局变量或函数的时候,如下所示:

第一个文件main.c

实例:

1
2
3
4
5
6
7
#include <stdio.h>
int count;
extern void write_extern();
main(){
count = 5;
write_extern()
}

第二个文件support.c

实例:

1
2
3
4
5
6
#include <stdio.h>
extern int count;

void write_extern(void){
printf("count is %d\n", count);
}

运算符

运算符是一种告诉编译器执行特定的数学或逻辑操作符号。c语言内置了丰富的运算符,并提供了以下类型的运算符:

  • 算数运算符
  • 关系运算符
  • 逻辑运算符
  • 位运算符
  • 赋值运算符
  • 杂项运算符

算数运算符

+ - * / % ++ –

逻辑运算符

&& || !

位运算符

& | ^ ~ << >>

赋值运算符

= += -= *= /= %= <<= >>= &= ^= |=

杂项运算符

  • sizeof():返回变量大小
  • &:返回变量的地址
  • *:指向一个变量
  • ?::条件表达式

C 中的运算符优先级

略

判断

判断语句

  • if语句
  • if…else语句
  • 嵌套if语句
  • switch语句
  • 嵌套switch语句

?:运算符(三元运算符)

1
Exp1? Exp2 : Exp3;

循环

循环类型

  • while循环
  • for循环
  • do…while循环
  • 嵌套循环

循环控制语句

  • break语句:中止循环或switch语句,程序流将继续执行紧接着循环或switch的下一条语句
  • continue语句:告诉一个循环体立刻停止本次循环迭代,重新开始下次循环迭代
  • goto语句:将控制转移到标记的语句。但不建议在程序中使用goto语句

无限循环

1
2
3
4
5
6
7
#include <stdio.h>
int main(){
for(;;){
printf("该循环会永远执行下去!\n");
}
return 0;
}

当条件表达式不存在时,它被假设为真

函数

函数声明告诉编译器函数的名称、返回类型和参数。函数定义提供了函数的实际主体。

定义函数

1
2
3
4
return_type function_name(parameter list)
{
body of function
}

函数所有组成部分:

  • 返回类型
  • 函数名称
  • 参数
  • 函数主体

实例

1
2
3
4
5
6
7
8
9
10
int max(int num1, int num2){
/*局部变量声明*/
int result;

if(num1 > num2)
result = num1;
else
result = num2;
return result;
}

函数声明

函数声明会告诉编译器函数的名称以及如何调用函数。函数的主体可以单独定义。

函数调用

实例:

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
#include <stdio.h>
/*函数声明*/
int max(int num1, int num2);
int main(){
/*局部变量定义*/
int a = 100;
int b = 200;
int ret;
/*调用函数获取最大值*/
ret = max(a, b);

printf("Max value is : %d\n", ret);

return 0;
}

/*函数返回两个数中较大的那个数*/
int max(int num1, int num2){
/*局部变量声明*/
int result;

if(num1 > num2)
result = num1;
else
result = num2;

return result;
}

函数参数

  • 传值调用
  • 引用调用

作用域规则

c语言在三个地方可以声明变量:

  1. 在函数或块内部的局部变量
  2. 在所有函数外部的全局变量
  3. 在形式参数的函数的函数参数定义中

局部变量

在某个函数或块的内部声明的变量成为局部变量。它们只能被该函数或代码块内部的语句使用。局部变量在函数外部是不可知的。下面是使用局部变量的实例:

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

int main(){
/*局部变量声明*/
int a, b;
int c;
/*实际初始化*/
a = 10;
b = 20;
c = a + b;
printf("value of a = %d, b = %d and c = %d\n", a, b, b);
return 0;
}

全局变量

全局变量是定义在函数外部,通常是在程序的顶部。全局变量在整个程序生命周期内都是有效的,再任意的函数内部能访问全局变量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>

/* 全局变量声明 */

int g;

int main()
{
/* 局部变量声明 */
int a, b;

/* 实际初始化 */
a = 10;
b = 20;
g = a + b;

printf("value of a = %d, b = %d and g = %d\n", a, b, g);
return 0;
}

在程序中,局部变量和全局变量的名称可以相同,但是在函数内,局部变量的值会覆盖全局变量的值。实例:

1
2
3
4
5
6
7
8
9
/* 全局变量声明 */
int g = 20;

int main(){
/* 局部变量声明 */
int g = 10;
printf("value of g = %d\n", g);
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
#include <stdio.h>

/* 全局变量声明 */
int a = 20;

int main(){
/* 在主函数中的局部变量声明 */
int a = 10;
int b = 20;
int c = 0;
int sum(int, int);

printf("value of a in main() = %d\n", a);
c = sum(a, b);
printf("value of c in main() = %d\n", c);
return 0;
}

/* 添加两个整数的函数 */
int sum(int a, int b){
printf("value of a in sum() = %d\n", a);
printf("value of b in sum() = %d\n", b);

return a + b;
}

初始化局部变量和全局变量

局部变量被定义的时候,系统不会对其初始化,您必须自行对其初始化。定义全局变量的时候,系统会自动对其初始化。

  • int: 0
  • char: ‘\0’
  • float: 0
  • double: 0
  • pointer: NULL

数组

所有的数组都是由连续的内存位置组成,最低的地址对应第一个元素,最高的地址对应最后一个元素。

声明数组

在c中声明一个数组,需要指定元素的类型和元素的数量,如下所示:

1
type arrayName [ arraySize ];

示例:

1
double balance[10];

现在balance是一个可用的数组,可以容纳10个类型为double的数字;

初始化数组

在c中,可以逐个初始化数组,也可以使用一个初始化语句:

1
double balance[5] = {1000.0, 2.0, 3.4, 7.0, 50.0};

如果省略了数组大小,数组的大小则为初始化时元素的个数:

1
double balance[] = {1000.0, 2.0, 3.4, 7.0, 50.0};

访问数组元素

1
double salary = balance[9];

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
int main(){
int n[10]; /* n是一个包含10个整数的数组 */
int i,j;
/* 初始化数组元素 */
for(i =0; i < 10; i++){
n[i] = i + 100; /* 设置元素i为i + 100 */
}
/* 输出数组中每个元素的值 */
for(j = 0; j < 10; j++){
printf("Element[%d] = %d\n", j, n[j]);
}
return 0;
}

指针理解:int b = &a;*表示变量b的值是变量a的地址

指针

学习c语言的指针既简单又有趣。通过指针,可以简化一些c编程任务的执行,还有一些任务,如动态内存分配,没有指针是无法执行的。所以想要成为一名优秀的c程序员,学习指针是很有必要的。

每一个变量都有一个内存位置,每一个内存位置都定义了可使用连字号(&)运算符访问的地址,它表示了在内存中的一个地址。请看下面的实例,它将输出定义的变量地址:

1
2
3
4
5
6
7
8
9
#include <stdio.h>
int main(){
int var1;
char var2[10];

printf("var1 变量的地址: %p\n", &var1);
printf("var2 变量的地址: %p\n", &var2);
return 0;
}

什么是指针

指针是一个变量,其值为另一个变量的地址,即,内存位置的直接地址。就像其他变量或常量一样,您必须在使用指针存储其他变量地址之前,对其进行声明。

1
type *var_name;

在这里,type就是指针的基本类型,它必须是一个有效的c数据类型,var_name是指针变量的名称。用来声明指针的星号*和乘法中使用的星号是相同的。但是,在这个语句中,星号是用来指定一个变量是指针。以下是有效的指针声明:

1
2
3
4
int *ip; /* 一个整数型的指针 */
double *dp; /* 一个double型的指针 */
float *fp; /* 一个浮点型的指针 */
char *ch; /* 一个字符型的指针 */

所有的指针的值的实际数据类型,不管是整型、浮点型、字符型,还是其他的数据类型,都是一样的,都是一个代表内存地址的长的十六进制数,不同数据类型的指针之间唯一的不同是,指针所指向的变量或常量的数据类型不同。

如何使用指针

使用指针时会频繁进行以下几个操作:定义一个指针变量、把变量地址赋值给指针、访问指针变量中可用地址的值。这些是通过使用一元运算符*来返回位于操作数所制定地址的变量的值。实例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>

int main(){
int var = 20; /* 实际变量的声明 */
int *ip; /* 指针变量的声明 */

ip = &var; /* 在指针变量中存储var的地址 */

printf("Address of var variable: %p\n", &var);

/* 在指针变量中存储的地址 */
printf("Address stored in ip variable: %p\n", ip);

/* 使用指针访问值 */
printf("Value of *ip variable: %d\n", *ip);
return 0;
}

C中的NULL指针
在变量声明的时候,如果没有确切的地址可以赋值,为指针变量赋一个NULL值是一个良好的编程习惯。赋为NULL值的指针被称为空指针。
NULL指针是一个定义在标准库中的值为零的常量。

1
2
3
4
5
6
#include <stdio.h>
int main(){
int *ptr = NULL;
printf("ptr 的值 %p\n", ptr);
return 0;
}

检查一个空指针:

1
2
if(ptr) /* 如果p非空,则完成 */
if(!ptr) /* 如果p为空,则完成 */

指针详解

略

每个变量都有自己的内存地址,同时拥有自己的值(内存地址中存储的值,如果没有初始化则是不可知的值)。指针也是变量,但它的值一般是另一个变量的地址。

函数指针与回调函数

函数指针

函数指针是指向函数的指针变量。通常我们说的指针变量是指向一个整型、字符型、或数组等变量,而函数指针是指向函数。函数指针可以像一般函数一样,用于调用函数、传递参数。函数指针变量的声明:

1
typedef int (*fun_ptr)(int, int); //声明一个指向同样参数,返回值的函数指针类型

实例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
int max(int x, int y){
return x > y ? x : y
}
int main(void){
/* p是函数指针 */
int (* p)(int, int) = & max; // &可以省略
int a, b, c, d;
printf("请输入三个数字:");
scanf("%d %d %d", &a, &b, &c);
/* 与直接调用函数等价,d = max(max(a,b), c) */
d = p(p(a,b), c);

printf("最大的数字是:%d\n", d);

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

//回调函数
void populate_array(int *array, size_t arraySize, int (*getNextValue)(void))
{
for(size_t i=0; i<arraySize; i++)
array[i] = getNextValue();
}
//获取随机值
int getNextRandomValue(void)
{
return rand();
}

int main(void)
{
int myarray[10];
populate_array(myarray, 10, getNextRandomValue);
for(int i = 0; i < 10; i++){
printf("%d ", myarray[i]);
}
printf("\n");
return 0;
}

tips

1
2
3
4
5
6
7
8
#include <stdio.h>
void test(){
printf("123456\n")
}
void main(void){
printf("0x%x\n", test);
printf("0x%x\n", &test);
}

按照&运算符本来的意义,它要求其操作数是一个对象,但函数名不是对象(函数是一个对象),本来&test是非法的,但很久以前有些编译器已经允许这样做,
c/c++标准的制定者出于对象的概念已经有所发展的缘故,也承认了&test的合法性。

因此,对于test和&test你应该这样理解,test是函数的首地址,它的类型是void (),&test表示一个指向函数test这个对象的地址,它的类型是void (*)(),因此test和&test所代表的地址值是一样的,但类型不一样。test是一个函数,&test表达式的值是一个指针!

跟此问题类似的还有对一个数组名取地址。

1
2
3
int a[100]; 
printf("%p\n", a);
printf("%p\n", &a[0]);

打印值一样。
但是数组名a,指向的是具有100个int类型的数组;
&a[0]指向的是元素a[0]。
即他们的值相同,但指向的类型不同。

字符串

在c语言中,字符串实际上是使用null字符’\0’终止的一维字符数组。因此,一个以null结尾的字符串,包含了组成字符串的字符。

下面的声明初始化创建了一个“Hello”字符。由于在数组的末尾存储了空字符,所以字符数组的大小比单词“Hello”的字符数多一个。

1
char greeting[6] = {'H', 'e', 'l', 'l', 'o', '\0'};

依据数组初始化规则,还可以写作:

1
char greeting[] = "Hello";

其实,编译器在初始化数组时,自动把“\0”放在字符串的末尾:

1
2
3
4
5
6
7
8
9
10
#include <stdio.h>

int main()
{
char greeting[6] = {'H', 'e', 'l', 'l', '0', '\0'};

printf("Greeting message: %s\n", greeting);

return 0;
}

c语言操作字符串的函数:

  • strcpy(s1, s2)
  • strcat(s1, s2)
  • strlen(s1)
  • strcmp(s1, s2)
  • strchr(s1, ch)
  • strstr(s1, s2)

实例如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
#include <string.h>

int main()
{
char str1[12] = "Hello";
char str2[12] = "World";
char str3[12];
int len;
/* 复制str1 到 str3 */
strcpy(str3, str1);
printf("strcpy(str3, str1) : %s\n", str3);

/* 连接str1 和 str2 */
strcat(str1, str2);
printf("strcat( str1, str2) : %s\n", str1);

/* 连接后, str1的总长度 */
len = strlen(str1);
printf("strlen( str1 ) : %d\n", len);

return 0;
}

英文全称:

  • strcmp: string compare
  • strcat: string catenate
  • strcpy: string copy
  • strlen: string length
  • strlwr: string lowercase
  • strupr: string upercase

结构体

c数组允许定义可存储相同类型数据项的变量,结构是c编程中另一种用户自定义的可用的数据类型,它允许您存储不同类型的数据项。

结构用于表示一条记录,假设你想要跟踪图书馆中书本的动态,您可能需要跟踪每本书的下列属性:

  • Title
  • Author
  • Subject
  • Book ID

定义结构

为了定义结构,您必须使用struct语句。struct语句定义了一个包含多个成员的数据类型,struct语句格式如下:

1
2
3
4
5
6
7
struct [structure tag]
{
member definition;
member definition;
...
member definition;
} [one or more structure variables];

structure tag是可选的,每个member definition是标准的变量定义,例:

1
2
3
4
5
6
7
struct Books
{
char title[50];
char author[50];
char subject[100];
int book_id;
} book;

访问结构成员

为了访问结构的成员,我们使用成员访问运算符(.)。成员访问运算符是结构变量名称和我们要访问的结构成员之间的一个点号。可以使用struct关键字定义结构类型的变量。实例:

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

struct Books
{
char title[50];
char author[50];
char subject[100];
int book_id;
};

int main()
{
struct Books Book1; /* 声明Book1,类型为Books */
struct Books Book2; /* 声明Book2,类型为Books */

/* Book1 详述 */
strcpy( Book1.title, "C Programming");
strcpy( Book1.author, "Nuha Ali");
strcpy( Book1.subject, "C Programming Tutorial");
Book1.book_id = 6495407;

/* Book2 详述 */
strcpy( Book2.title, "Telecom Billing");
strcpy( Book2.author, "Zara Ali");
strcpy( Book2.subject, "Telecom Billing Tutorial");
Book2.book_id = 6495700;

/* 输出Book1的信息 */
printf("Book 1 title: %s\n", Book1.title);
printf("Book 1 author: %s\n", Book1.author);
printf("Book 1 subject: %s\n", Book1.subject);
printf("Book 1 book_id: %d\n", Book1.book_id);

/* 输出Book2信息 */
printf("Book 2 title: %s\n", Book2.title);
printf("Book 2 author: %s\n", Book2.author);
printf("Book 2 subject: %s\n", Book2.subject);
printf("Book 2 book_id: %d\n", Book2.book_id);

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

struct Books
{
char title[50];
char author[50];
char subject[100];
int book_id;
};

/* 函数声明 */
void printBook( struct Books book);

int main()
{
struct Books Book1; /* 声明Book1,类型为Books */
struct Books Book2; /* 声明Book2,类型为Books */

/* Book1 详述 */
strcpy( Book1.title, "C Programming");
strcpy( Book1.author, "Nuha Ali");
strcpy( Book1.subject, "C Programming Tutorial");
Book1.book_id = 6495407;

/* Book2 详述 */
strcpy( Book2.title, "Telecom Billing");
strcpy( Book2.author, "Zara Ali");
strcpy( Book2.subject, "Telecom Billing Tutorial");
Book2.book_id = 6495700;

/* 输出Book1的信息 */
printBook(Book1);

/* 输出Book2信息 */
printBook(Book2);

return 0;
}

void printBook(struct Books book)
{
printf("Book title: %s\n", book.title);
printf("Book author: %s\n", book.author);
printf("Book subject: %s\n", book.subject);
printf("Book book_id: %d\n", book.book_id);
}

指向结构的指针

同其他类型变量的指针

1
2
struct Books *struct_pointer;
struct_pointer = &Book1;

为了使用指向该结构的指针访问结构的成员,必须使用->运算符:

1
struct_pointer->title;

实例:

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

struct Books
{
char title[50];
char author[50];
char subject[100];
int book_id;
};

/* 函数声明 */
void printBook( struct Books *book);

int main()
{
struct Books Book1; /* 声明Book1,类型为Books */
struct Books Book2; /* 声明Book2,类型为Books */

/* Book1 详述 */
strcpy( Book1.title, "C Programming");
strcpy( Book1.author, "Nuha Ali");
strcpy( Book1.subject, "C Programming Tutorial");
Book1.book_id = 6495407;

/* Book2 详述 */
strcpy( Book2.title, "Telecom Billing");
strcpy( Book2.author, "Zara Ali");
strcpy( Book2.subject, "Telecom Billing Tutorial");
Book2.book_id = 6495700;

/* 输出Book1的信息 */
printBook(&Book1);

/* 输出Book2信息 */
printBook(&Book2);

return 0;
}

void printBook(struct Books *book)
{
printf("Book title: %s\n", book->title);
printf("Book author: %s\n", book->author);
printf("Book subject: %s\n", book->subject);
printf("Book book_id: %d\n", book->book_id);
}

位域

有些信息在存储时,并不需要占用一个完整的字节,而只需要占几个或一个二进制位。例如在存放一个开关变量时,只有0和1两种状态,用一位二进制位即可。为了节省空间,并使处理方便,c语言又提供了一种数据结构,称为“位域”或“位段”。

所谓“位域”是把一个字节中的二进位划分为几个不同的区域,并说明每个区域的位数。每个域有一个域名,允许在程序中按域名进行操作。这样就可以把几个不同的对象用一个字节的二进制位域来表示。
典型的实例:

  • 用1位二进位存放一个开关量,只有0和1两种状态
  • 读取外部文件格式 - 可以读取非标准的文件格式。例如:9位的整数。

位域的定义和位域变量的说明

定义:

1
2
3
4
struct 位域结构名
{
位域列表
};

位域列表的形式:

1
类型说明符 位域名:位域长度

例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
struct bs{
int a: 8;
int b: 2;
int c: 6;
} data;
struct packed_struct {
unsigned int f1:1;
unsigned int f2:1;
unsigned int f3:1;
unsigned int f4:1;
unsigned int type:4;
unsigned int my_int:9;
} pack;

  • 一个位域必须存储在同一个字节中,不能跨两个字节。如一个字节所剩空间不够存放另一位域时,应从下一单元起存放 该位域。也可以使某位域从下一单元开始。例:

    1
    2
    3
    4
    5
    6
    struct bs{
    unsigned a:4;
    unsigned :4; /* 空域 */
    unsigned b:4; /* 从下一单员开始存放 */
    unsigned c:4;
    }
  • 位域的长度不能超过8位二进制位

  • 可以使用无名位域
    所以位域在本质上就是一种结构类型,只不过成员是按二进位分配的。

位域的使用

规则:

1
2
位域变量名.位域名
位域变量名->位域名

位域允许使用各种格式输出,实例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
main(){
struct bs{
unsigned a:1;
unsigned b:3;
unsigned c:4;
} bit, *pbit;
bit.a = 1; /* 给位域赋值(赋值不应超过该位域允许范围)*/
bit.b = 7;
bit.c = 15;
printf("%d,%d,%d\n", bit.a, bit.b, bit.c); /*以整型格式输出三个域的内容*/
pbit = &bit;
pbit->a = 0;
pbit->b &= 3;
pbit->c |= 1;
printf("%d,%d,%d\n", pbit->a, pbit->b, pbit->c);
}

所以位域也可以使用指针

其他

内存对齐

共用体

共用体是一种特殊的数据类型,允许您在相同的内存位置储存不同的数据类型。您可以定义一个带有多个成员的共用体,到那时任何时候只能有一个成员的值。共用体提供了一种使用相同的内存位置的有效方式。

定义共用体

使用union语句:

1
2
3
4
5
6
7
union [union tag]
{
member definition;
member definition;
...
member definition;
} [one or more union variables];

union tag是可选的。实例:

1
2
3
4
5
6
union data
{
int i;
float f;
char str[20];
} data;

Data类型的变量可以存储多种类型的数据。共用体占用内存应足够存储共用体中最大的成员,实例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
#include <string.h>

union Data {
int i;
float f;
char str[20];
};
int main()
{
union Data data;
printf("Memory size occupied by data : %d\n", sizeof(data));
return 0;
}

访问共用体成员

为了访问共用体的成员,我们使用成员访问运算符(.)。
实例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
#include <string.h>

union Data {
int i;
float f;
char str[20];
};
int main()
{
union Data data;
data.i = 10;
data.f = 220.5;
strcpy( data.str, "C Programming");

printf("data.i : %d\n", data.i);
printf("data.f : %f\n", data.f);
printf("data.str : %s\n", data.str);
return 0;
}

可以看到i和f的值有损坏,因为最后赋值的变量占用了内存位置。再看一个实例,这次我们在同一时间只是用一个变量,这也演示了共同体的主要目的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <string.h>

union Data {
int i;
float f;
char str[20];
};
int main()
{
union Data data;
data.i = 10;
printf("data.i : %d\n", data.i);

data.f = 220.5;
printf("data.f : %f\n", data.f);

strcpy( data.str, "C Programming");
printf("data.str : %s\n", data.str);

return 0;
}

typedef

c语言提供了typedef关键字,您可以使用它为类型取一个新的名字。下面的实例位单字节数字定义了一个术语BYTE:

1
typedef unsigned char BYTE;

在这个类型定义后,标识符BYTE可作为类型unsigned char的缩写,例如:

1
BYTE b1, b2;

按照惯例,定义使用大写字母。

还可以给自定义数据类型取一个新的名字。实例:

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

typedef struct Books
{
char title[50];
char author[50];
char subject[100];
int book_id;
} Book;

int main()
{
Book book;

strcpy( book.title, "C 教程");
strcpy( book.author, "Runoob");
strcpy( book.subject, "编程语言");
book.book_id = 12345;

printf("书标题 :%s\n", book.title);
printf("书作者 :%s\n", book.author);
printf("书类目 :%s\n", book.subject);
printf("书ID :%d\n", book.book_id);

return 0;
}

typedef vs #define

#define 是c指令,用于位各类数据类型定义别名,与typedef类似,但是有以下几点不同:

  • typedef 仅限于为类型定义符号名称,#define 不仅可以为类型定义别名,也能为数值定义别名,比如您可以定义1 为ONE
  • typedef是由编译器执行解释的,#define语句是由预编译器进行处理的。
    实例:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    #include <stdio.h>

    #define TRUE 1
    #define FALSE 0

    int main(){
    printf("TRUE 的值为:%d\n", TRUE);
    printf("FALSE 的值为:%d\n", FALSE);

    return 0;
    }

输入&输出

标准文件
c语言把所有的设备当作文件,所以设备被处理的方式与文件相同。以下三个文件会在程序执行时自动打开,以便访问键盘和屏幕。
标准文件 文件指针 设备

  • 标准输入 stdin 键盘
  • 标准输出 stdout 屏幕
  • 标准错误 stderr 您的屏幕
    实例:
    1
    2
    3
    4
    5
    6
    #include <stdio.h>
    int main()
    {
    printf("Hello world!");
    return 0;
    }

’%d‘来匹配整型变量,‘%f’格式化输出浮点型数据

1
2
3
4
5
6
7
8
9
#include <stdio.h>
int main()
{
float f;
printf("Enter a number:");
scanf("%f", &f);
printf("Value = %f", f);
return 0;
}

getchar()&putchar()函数
int getchar(void): 函数从屏幕读取下一下可用的字符,并把它返回为一个整数。这个函数在同一个时间内只会读取一个单一的字符。可以在循环内使用这个方法,以便从屏幕中读取多个字符。
int putchar(void): 函数把字符输出到屏幕上,并返回相同的字符。这个函数在同一个时间内只会输出一个单一的字符。可以在循环中使用这个方法,在屏幕上输出多个字符。
实例:

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
int main()
{
int c;
printf("Enter a value:");
c = getchar();

printf("\nYou entered:");
putchar(c);
printf("\n");
return 0;
}

scanf()和printf()

int scanf(const char format, …) 函数从标准输入流stdin读取输入,并根据提供的format来浏览输入。
int printf(const chat
format, …) 函数把输出写入到标准输出流stdout,并根据提供的格式产生输出。

format可以是一个简单的常量字符串,到那时您可以分别指定%s %d %c %f等来输出或读取字符串、整数、字符或浮点数。还有许多其它可用的格式选项,可以根据需要使用。如需了解完整的细节,可以查看这些函数的参考手册。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
int main()
{
char str[100];
int i;

printf("Enter a value:");
scanf("%s %d", str, &i);

printf("\nYou entered: %s %d", str, i);
printf("\n");
return 0;
}

读取字符串的时候,只要遇到空格就会停止读取。

文件读写

打开文件

可以使用fopen()函数来创建一个新的文件或者打开一个已有的文件,这个调用会初始化FILE的一个对象,类型FILE包含了所有用来控制流的必要的信息。函数调用原型如下:

1
FILE *fopen(const char * filename, const char *mode);

在这里,filename是字符串,用来命名文件,访问模式mode的值可以是下列值中的一个:

  • r:打开一个已有的文本文件,允许读取文件
  • w:打开一个文本文件,允许写入文件。如果文件不存在,则会创建一个新文件,从开头写入内容
  • a:打开一个文本文件,以追加模式写入文件。如果文件不存在,则会创建一个新文件
  • r+:打开一个文本文件,允许读写文件
  • w+:打开一个文本文件,允许读写文件。如果文件已存在,则文件会被截断为零长度,如果文件不存在,则创建
  • a+:打开一个文本文件,允许读写文件。如果文件不存在,则创建一个新文件。读取从开头开始,写入则只能是追加模式
    如果处理的是二进制文件,则需要使用下面的访问方式来取代上面的访问模式:
    1
    "rb", "wb", "ab", "rb+", "r+b", "wb+", "w+b", "ab+", "a+b"

关闭文件

1
int fclose(FILE *fp)

如果成功关闭文件,fclose()函数返回零,若关闭文件发生错误,函数返回EOF。这个函数实际上,会清空缓冲区中的数据,关闭文件,并释放用于该文件的所有内存。EOF是一个定义在文件stdio.h中的常量。
c标准库提供了各种函数来按字符或者以固定长度字符串的形式读写文件。

写入文件

1
int fputc(int c, FILE *fp);

函数fputc()把参数c的字符值写入到fp所指向的输出流中。如果写入成功,它会返回写入的字符,如果发生错误,则会返回EOF。可以使用下面的函数来把一个以null结尾的字符串写入到流中:

1
int fputs( const char *s, FILE *fp );

函数fputs把字符串s写入到fp所指向的输出流中。如果写入成功,返回一个非负值,如果发生错误,则会返回EOF。您也可以使用int fprintf(FILE fp, const char format, …)函数来把一个字符串写入到文件中。实例:

1
2
3
4
5
6
7
8
9
10
#include <stdio.h>
int main()
{
FILE *fp = NULL;

fp = fopen("/tmp/test.txt", "w+");
fprintf(fp, "This is testing for fprintf...\n");
fputs("This is testing for fputs...\n", fp);
fclose(fp);
}

读取文件

读取单个字符:

1
int fgetc( FILE *fp);

fgetc()函数从fp所指向的输入文件中读取一个字符。返回值是读取的字符,如果发生错误返回EOF。下面的函数允许从流中读取一个字符:

1
char *fgets(char *buf, int n, FILE *fp);

函数fgets()从fp所指向的输入流中读取n-1个字符。他会把读取的字符串复制到缓冲区buf,并在最后加上一个null字符来终止字符串。

如果这个函数在读取最后一个字符之前就遇到一个换行符”\n”或文件末尾EOF,则只会返回读取到的字符,包括换行符。所以可以使用int fscanf(FILE fp, const char format, …)函数来从文件中读取字符串,但是在遇到第一个空格字符时,它会停止读取。实例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
int main()
{
FILE *fp = NULL;
char buff[255];

fp = fopen("/tmp/test.txt", "r");
fscanf(fp, "%s", buff);
printf("1 : %s\n", buff);

fgets(buff, 255, (FILE *)fp);
printf("2 : %s\n", buff);

fgets(buff, 255, (FILE *)fp);
printf("3 : %s\n", buff);
fclose(fp);
}

二进制I/O函数
下面两个函数用于二进制的输入和输出:

1
2
3
size_t fread(void *ptr, size_t size_elements, size_t number_of_elements, FILE *a_file);

size_t fwrite(const void *ptr, size_t size_of_elements, size_t number_of_elements, FILE *a_file);

这两个函数都是用于存储块的书写-通常是数组或结构体

预处理器

c预处理器不是编译器的组成部分,但它是编译过程中的一个单独步骤,c预处理器只不过是一个文本替换工具而已,它们会指示编译器在实际编译之前完成所需的预处理。我们把c预处理器简写为CPP

所有的预处理器命令都是以#开头。它必须是第一个非空字符,为了增强可读性,预处理指令应从第一列开始。所有重要的预处理器指令:

  • #define 定义宏
  • #include 包含一个源代码文件
  • #undef 取消已定义的宏
  • #ifdef 如果宏已经定义,则返回真
  • #if 如果给定条件为真,则编译下面代码
  • #else #if的替代方案
  • #endif 结束一个#if…#else条件编译块
  • #error 当遇到标准错误时,输出错误信息
  • #prama 使用标准化方法,向编译器发布特殊的命令到编译器中
    实例:
    1
    #define MAX_ARRAY_LENGTH 20

这个指令会告诉cpp把所有的MAX_ARRAY_LENGTH替换为20。使用#define定义常量增加可读性

1
2
#include <stdio.h>
#include "myheader.h"

这些指令告诉cpp从系统库中获取stdio.h,并添加文本到当前的源文件中。下一行告诉cpp从本地目录中获取myheader.h,并添加内容到当前的源文件中。

1
2
#undef FILE_SIZE
#define FILE_SIZE 42

取消原来的FILE_SIZE定义,并重新定义

1
2
3
#ifndef MESSAGE
#define MESSAGE "you wish"
#endif

这个指令告诉cpp只有当MESSAGE未定义时,才定义

1
2
3
#ifdef DEBUG
/* debugging statements */
#endif

这个指令告诉cpp如果定义了DEBUG,则执行处理语句。如果向gcc编译器传递了DEBUG开关量,这个指令就很有用,可以在编译期间随时开关调试。
预定义宏
ANSI C 定义了许多宏。在编译中可以直接使用这些宏,但不能直接修改这些预定义的宏。

  • _DATE_ 当前日期,一个以“MMM DD YYYY”格式表示的字符常量。
  • _TIME_ 当前时间,一个以”HH:MM:SS”格式表示的字符变量。
  • _FILE_ 这会包含当前文件名,一个字符串变量
  • _line_ 这会包含当前行号,一个十进制常量。
  • _STDC_ 当编译器以ANSI标准编译时,则定义为1.
    实例:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    #include <stdio.h>

    main(){
    printf("File : %s\n", __FILE__);
    printf("Date : %s\n", __DATE__);
    printf("Time : %s\n", __TIME__);
    printf("Line : %d\n", __LINE__);
    printf("ANSI : %d\n", __STDC__);
    }

预处理齐运算符

c预处理器提供了下列的运算符帮助您创建宏:

宏延续运算符()

一个宏通常写在一个单行上。但是如果宏太长,一个单行容纳不下,则使用宏延续运算符(),例:

1
2
#define message_for(a, b)\
printf(#a " and " #b ": We love you!\n")

字符串常量化运算符#

在宏定义中,当需要把一个宏的参数转换为字符串常量时,则使用字符串常量化运算符(#)。在宏中使用的该运算符有一个特定的参数或参数列表。例:

1
2
3
4
5
6
7
8
#include <stdio.h>
#define message_for(a, b) \
printf(#a " and " #b ": We love you!\n")

int main(void){
message_for(Carole, Debra);
return 0;
}

标记粘贴运算符(##)

宏定义内的标记粘贴运算符(##)会合并两个参数。它允许在宏定义重两个独立的标记被合并为一个标记。例:

1
2
3
4
5
6
7
8
#include <stdio.h>
#define tokenpaster(n) printf("token" #n " = %d", token##n)

int main(void){
int token34 = 40;
tokenpaster(34);
return 0;
}

defined()运算符

预处理器defined运算符是用在常量表达式中的,用来确定一个标识符是否已使用#define定义过。如果指定的标识符已定义,则值为真(非零)。如果指定的标识符未定义,则值为假(零)。实例:

1
2
3
4
5
6
7
8
9
10
#include <stdio.h>

#if !defined(MESSAGE)
#define MESSAGE "You wish!"
#endif

int main(void){
printf("Here is the message: %s\n", MESSAGE);
return 0;
}

参数化的宏

cpp一个强大的功能时可以使用参数化的宏来模拟函数。例:

1
2
3
int square(int x){
return x*x;
}

可重写为

1
#define square(x) ((x) * (x))

在使用带有参数的宏之前,必须使用#define指令定义。参数列表时括在圆括号内,且必须紧跟在宏名称后面。宏名称和左圆括号之间不允许有空格,例:

1
2
3
4
5
6
7
#include <stdio.h>

#define MAX(x,y) ((x) > (y) ? (x) : (y))
int main(void){
printf("Max between 20 and 10 is %d\n", MAX(10, 20));
return 0;
}

头文件

头文件是扩展名为.h的文件,包含了c函数声明和宏定义,被多个源文件引用共享。有两种头文件:程序员编写的头文件和编译器自带的头文件。

在程序中要使用头文件,需要使用c预处理指令#include来引用她。前面我们已经看过stdio.h头文件,它是编译器自带的头文件。

建议把所有的常量、宏、系统全局变量和函数原型写在头文件中,在需要的时候随时引用这些头文件。

引用头文件的语法

第一种:

1
#include <file>

这种模式适用于引用系统文件。它在系统目录的标准列表里搜索名为file的文件。在编译源代码的时候,可以通过-l选项把目录前置在该列表前。第二种:

1
#include "file"

这种形式适用于引用用户头文件。它在包涵当前文件爱的呢目录中搜索名为file的文件。在编译的时候,可以通过-l选项前置在该列表前。

引用头文件的操作

#include指令会指示c预处理器浏览指定的文件作为输入。预处理器的输出包含了已经生成的输出,被引用文件生成的输出以及#include指令之后的文本输出。例如:

1
char *test (void);

使用了头文件的program.c,如下:

1
2
3
4
5
6
7
int x;
#include "header.h"

int main(void)
{
puts(test());
}

编译器会看到如下的令牌流:

1
2
3
4
5
6
7
int x;
char *test(void);

int main(void)
{
puts(test());
}

只引用一次头文件

如果一个头文件被引用两次,编译器会处理两次头文件的内容,这将产生错误。为了防止这种错误,标准的做法是把整个文件内容放在条件编译语句中,如下:

1
2
3
4
#ifdef HEADER_FILE
#define HEADER_FILE
header file
#endif

有条件引用

多个头文件中选择一个引用到程序中,例:

1
2
3
4
5
6
7
#if SYSTEM_1
#include "system_1.h"
#elif SYSTEM_3
#include "system_2.h"
#elif SYSTEM_3
...
#endif

头文件比较多的时候,这么做是很麻烦的,预处理器使用宏来定义头文件的名称。这就是所谓的有条件饮用。它不是使用头文件的名称作为#include的直接参数,您只需要使用宏名称代替即可:

1
2
3
#define SYSTEM_H "system_1.h"
...
#include SYSTEM_H

SYSTEM_H会扩展,预处理器会查找system_1.h。SYSTEM_H可通过-D选项被Makefile定义。

强制类型转换

强制类型转换符可以显式地从一种类型转换为另一种类型,如下所示:

1
(type_name) expression

实例:

1
2
3
4
5
6
7
8
9
10
#include <stdio.h>

int main(void){
int sum = 17, count = 5;
double mean;

mean = (double) sum / count;
printf("Value of mean: %f\n", mean);
return 0;
}

强制类型转换符的优先级大于除法。类型转换可以是隐式的,也可以是显式的,通过使用强制类型转换符指定。在编程时,有需要类型转换的时候都用上强制类型转换运算符,是一种良好的编程习惯。

整数提升

整数提升是指把小于int或unsigned int的整数类型转换为int或unsigned int的过程。请看下面的实例,在int中添加一个字符:

1
2
3
4
5
6
7
8
9
10
#include <stdio.h>

int main(void){
int i = 17;
char c = 'c';/* ascii值为99 */
int sum;

sum = i + c;
printf("Value of sum : %d\n", sum);
}

常用的算术转换

常用的算术转换是隐式地把值强制转换为相同的类型。编译器首先进行整数提升,如果操作数类型不同,则它们会被转换为下列层次中出现的最高层次的类型,从右往左依次升高

int -> unsigned int -> long -> long long -> unsigned long -> float -> double -> long double

常用的算术转换不适用于赋值运算符、逻辑运算符&&和||。实例:

1
2
3
4
5
6
7
8
9
10
#include <stdio.h>

int main(void){
int i = 17;
char c = 'c';/* ascii值为99 */
float sum;

sum = i + c;
printf("Value of sum : %f\n", sum);
}

在这里c首先被转换为整数,但是最后的值是double型的,编译器会把i和c转换为浮点型,然后相加。

错误处理

c语言不提供对错误处理的直接支持,但是作为一种系统编程语言,它以返回值的形式允许您访问底层数据。在发生错误时,大多数的c或UNIX函数调用返回1或NULL,同时会设置一个错误代码errno,该错误代码是全局变量,表示在函数调用期间发生了错误。可以在<error.h>头文件中找到各种各样的错误代码。

所以,c程序员可以通过检查返回值,然后根据返回值决定采取哪种适当的动作。开发人员应该在程序初始化时,把errno设置为0,这是一种良好的编程习惯,0表示程序中没有错误。

errno、perror()和strerror()

c语言提供了perror()和strerror()函数来显示与errno相关的文本消息。

  • perror()函数显示传给它的字符串,后跟一个冒号、一个空格和当前errno值的文本表示形式。
  • strerror()函数,返回一个指针,指针指向当前errno值的文本表示形式

模拟一种情况,尝试打开一个不存在的文件。这里我们使用函数来演示用法。另外一点需要注意,应该使用stderr文件流来输出所有的错误。例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
#include <errno.h>
#include <string.h>

extern int errno;

int main(){
FILE *pf;
int errnum;
pf = fopen("unexist.txt", "rb");
if(pf == NULL)
{
errnum = errno;
fprintf(stderr, "错误号:%d\n", errno);
perror("通过perror输出错误");
fprintf(stderr, "打开文件错误:%s\n", strerror(errnum));
}
else
{
fclose(pf);
}
return 0;
}

被零除的错误

在进行除法运算时,如果不检查除数是否为零,则会导致一个运行时错误。

为了避免这种情况发生,下面的代码在进行除法运算前会先检查除数是否为零:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#include <stdlib.h>

main(){
int dividend = 20;
int divisor = 0;
int quotient;

if( divisor == 0){
fprintf(stderr, "除数为 0 退出运行...\n");
exit(-1);
}
quotient = dividend / divisor;
fprintf(stderr, "quotient 变量的值为:%d\n", quotient);

exit(0);
}

程序退出状态

通常情况下,程序成功执行完一个操作正常退出的时候会带有值EXIT_SUCCESS。在这里,EXIT_SUCCESS是宏,他被定义为0。

如果程序中存在一种错误情况,当您退出程序时,会带有状态值EXIT_FAILURE,被定义为-1。所以,上面的程序可以写为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#include <stdlib.h>

main(){
int dividend = 20;
int divisor = 5;
int quotient;

if( divisor == 0){
fprintf(stderr, "除数为 0 退出运行...\n");
exit(EXIT_FAILURE);
}
quotient = dividend / divisor;
fprintf(stderr, "quotient 变量的值为:%d\n", quotient);

exit(EXIT_SUCCESS);
}

递归

递归指的在函数的定义中使用函数自身的方法。
语法格式如下:

1
2
3
4
5
6
7
void recursion()
{
recursion(); /* 函数调用自身 */
}
int main(){
recursion();
}

c语言支持递归,即一个函数可以调用其自身。但在使用递归时,程序员需要注意定义一个从函数退出的条件,否则会进入死循环。

递归在解决许多数学问题上起了至关重要的作用,比如计算一个数的阶乘、生成斐波那契数列,等等。

数的阶乘

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

double factorial(unsigned int i){
if(i <= 1){
return 1;
}
return i*factorial(i-1);
}
int main(){
int i = 15;
printf("%d 的阶乘为 %f\n", i, factorial(i));
return 0;
}

斐波那契数列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>

int fibonaci(int i){
if(i == 0){
return 0;
}
if(i == 1){
return 1;
}
return fibonaci(i-1) + fibonaci(i-2);
}
int main(){
int i;
for (i = 0; i < 10; i++) {
printf("%d\t\n", fibonaci(i));
}
return 0;
}

能用数学归纳法解决的问题理论上都能用递归进行表达,递归能解决的问题也可以用循环解决,不过表达要麻烦一点

可变参数

有时,您可能会碰到这样的情况,您希望函数带有可变数量的参数,而不是预定义数量的参数。c语言为这种情况提供了一个解决方案,它允许您定义一个函数,能根据具体的需求接受可变数量的参数。实例:

1
2
3
4
5
6
7
8
9
int func(int, ...){
.
.
.
}
int main(){
func(1,2,3);
func(1,2,3,4);
}

请注意,函数func()最后一个参数写成省略号,即三个点号(…),省略号之前的那个参数时int,代表了要传递的可变参数的总数。为了使用这个功能,,您需要使用stdarg.h头文件,该文件提供了实现可变参数功能的函数和宏。具体步骤:

  • 定义一个函数,最后一个参数为省略号,省略号前面可以设置自定义参数
  • 在函数定义中创建一个va_list类型变量,该类型是在stdarg.h头文件中定义的
  • 使用int参数和va_start宏来初始化va_list变量为一个参数列表。宏va_start是在stdarg.h头文件中定义的
  • 使用va_arg宏和va_list变量来访问参数列表中国年的每个项
  • 使用va_end来清理赋予va_list变量的内存
    实例:
    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
    #include <stdio.h>
    #include <stdarg.h>

    double average(int num,...)
    {

    va_list valist;
    double sum = 0.0;
    int i;

    /* 为 num 个参数初始化 valist */
    va_start(valist, num);

    /* 访问所有赋给 valist 的参数 */
    for (i = 0; i < num; i++)
    {
    sum += va_arg(valist, int);
    }
    /* 清理为 valist 保留的内存 */
    va_end(valist);

    return sum/num;
    }

    int main()
    {
    printf("Average of 2, 3, 4, 5 = %f\n", average(4, 2,3,4,5));
    printf("Average of 5, 10, 15 = %f\n", average(3, 5,10,15));
    }

内存管理

c语言为内存的分配和管理提供了几个函数。这些函数可以在<stdlib.h>头文件中找到。

  1. void calloc(int num, int size): 在内存中动态的分配num个长度为size的连续空间,并将每个字节都初始化为0。所以结果是分配了num\size个字节长度的内存空间,并且每个字节的值都是0。
  2. void free(void *address): 该函数释放address所指向的内存块,释放的是动态分配的内存空间
  3. void *malloc(int num): 在堆区分配一块指定大小的内存空间,用来存放数据。这块内存空间在函数执行完成后并不会被初始化,它们的值是未知的。
  4. void realloc(void address, int newsize): 该函数重新分配内存,把内存扩展到newsize。

动态分配内存

编程的时候,如果预先知道数组的大小,那么定义数组就比较容易。例:

1
char name[100]

但是,如果您预先不知道需要存储的文本长度,例如存储一个主题的详细描述。在这里,我们需要定义一个指针,该指针指向未定义所需内存大小的字符,后续再根据需求来分配内存,如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
char name[100];
char *description;

strcpy(name, "Zara Ali");

/* 动态分配内存 */
description = malloc( 200*sizeof(char));
if(description == NULL){
fprintf(stderr, "Error - unable to allocate required memory\n");
}
else {
strcpy(description, "Zara ali a DPS student in class 10th");
}
printf("Name = %s\n", name);
printf("Description: %s\n", description);
}

用calloc()来编写:

1
calloc(200, sizeof(char));

动态分配内存的时候,我们有完全的控制权,可以传递任何大小的值,但是预定义了大小的数组,一旦定义则无法改变大小

重新调整内存的大小和释放内存

当程序退出时,操作系统会自动释放所有分配给程序的内存,但是,最好在不需要内存的时候,调用free()函数来释放内存。或者调用realloc()来增加或减少已分配的内存大小。实例:

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

int main()
{
char name[100];
char *description;

strcpy(name, "Zara Ali");

/* 动态分配内存 */
description = malloc( 30*sizeof(char));
if(description == NULL){
fprintf(stderr, "Error - unable to allocate required memory\n");
}
else {
strcpy(description, "Zara ali a DPS student.");
}
/* 假设想要存储更大的描述信息 */
description = realloc(description, 100*sizeof(char));
if(description == NULL){
fprintf(stderr, "Error - unable to allocate required memory\n");
} else {
strcat(description, "She is in class 10th");
}
printf("Name = %s\n", name);
printf("Description: %s\n", description);
/* 使用free()函数释放内存 */
free(description);
}

理论上不重新分配额外的内存,strcat() 函数会生成一个错误,因为存储 description 时可用的内存不足。但是实际操作的时候,即使不够,也不报错

命令行参数

执行程序时,可以从命令行传值给c程序。这些值被称为命令行参数,它们对程序很重要,特别是当您想从外部控制程序,而不是在代码内对这些值进行硬编码时,就显得尤为重要了。

命令行参数是使用main()函数参数来处理的,其中,argc是指传入参数的个数,argv[]是一个指针数组,指向传递给程序的每个参数。实例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>

int main(int argc, char *argv[])
{
if(argc == 2){
printf("The argument supplied is %s\n", argv[1]);
}
else if(argc > 2){
printf("Too many arguments supplied.\n");
}
else {
printf("One argument expected.\n");
}
}

应当指出的是,argv[0]存储程序的名称,argv[1]是一个指向第一个命令行参数的指针,*agrv[n]是最后一个参数。如果没有提供任何参数,argc将为1,否则,如果传递了一个参数,argc将被设置为2。

多个命令行参数之间用空格分隔,但是如果参数本身带有空格,那么传递参数的时候应把参数放置在双引号或单引号内部。实例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>

int main(int argc, char *argv[])
{
printf("Program name %s\n", argv[0]);
if(argc == 2){
printf("The argument supplied is %s\n", argv[1]);
}
else if(argc > 2){
printf("Too many arguments supplied.\n");
}
else {
printf("One argument expected.\n");
}
}

体会

  • 字符数组名是一个常量指针,不可操作
  • 字符串指针存放的是字符串常量的地址,所以可以进行操作
  • 指针的+1并非是值+1而是指向内存的位置+1

数据结构

发表于 2017-11-11

引子

诚者自成也,而道自道也。

诚者,物之终始。不诚无物。是故君子诚之为贵。

诚者,非自成己而己也。所以成物也。成己仁也,成物知也。性之德也,合外内之道也。故时措之宜也。

–《中庸》

绪论

数据结构

  • 数据(data): 是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的 总称。
  • 数据元素(data element):是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理
  • 数据对象(data object):是性质相同的数据元素的集合,是数据的一个子集。
  • 数据结构(data structure):又称逻辑结构,是相互之间存在一种或多种特定关系的数据的集合,通常包括四种:集 合、线性结构、树形结构、网状结构。
  • 存储结构:是数据结构在计算机中的表示。
  • 数据类型(data type):是一个值的集合和定义在这个值集上的一系列操作的总称。
  • 抽象数据类型(AbstractData Type):是指一个数据模型以及定义在该模型上的一组操作,可细分为:原子类型、固定聚合类型、可变聚合类型。

算法

算法的5个重要特性:有穷性,确定性,可行性,输入,输出

衡量一个算法是否优秀,一般从以下几个点考虑:正确性,可读性,健壮性,时间复杂度,空间复杂度

一般情况下,算法中基本操作重复执行的次数时问题规模n的某个函数f(n),算法的时间量度记作:T(n) = O(f(n))。他表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称时间复杂度。

类似时间复杂度,基本操作带来的空间消耗和问题规模n通常也有关系,这个关系叫空间复杂度:S(n) = O(f(n))。若输入数据所占空间只取决于问题本身,和算法无关,则只需要分析除输入和程序之外的额外空间,否则应该同时考虑输入本身所需空间。若额外空间相对于输入数据量来说是常数,则称此算法为原地工作。

算法书写规范

  • 算法说明:指明算法功能;参数表中各参量的含义和输入输出属性;算法中引入了哪些全局变量或外部定义的变量,作用入口初值以及应满足哪些限制条件
  • 注释和断言:注释抽象度应高于语句,断言用来陈述算法执行到此处应该满足的条件
  • 输入和输出:scanf和printf语句;参数显示;全局变量或外部变量隐式的传递信息
  • 错误处理:尽可能使用函数返回算法的执行状态,便于调用者处理异常情况,有益于培养良好的程序设计习惯
  • 语句选用和算法结构:尽量不使用goto
  • 基本运算:自己实现
  • 建议:使用图说明算法;用边界条件检测算法

第二章

线性表和单链表

第三章

栈和队列

表达式求值:算符优先法

为了实现算符优先法,可以使用两个工作栈,一个称作OPTR,用来寄存运算符,另一个称为OPND用来寄存操作数或运算结果。

  1. 首先置操作数栈为空栈,表达式起止符‘#’为栈底元素
  2. 依次读入表达式中的每个字符,若是操作数则进OPND栈,若是运算符则和OPTR栈的栈顶运算符比较优先权后作相应操作,直至整个表达式求值完毕(即OPTR的栈顶元素和当前读入字符均为‘#’)

栈与递归的实现

递归:一个直接调用自己或通过一系列的调用语句间接地调用自己的函数,称作递归函数。

hanoi问题:

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 <stdio.h>
int c = 0;
void moveH(char *x, int n, char *z){
printf("%i. Move disk %i from %s to %s\n", ++c, n, x, z);
}
void hanoi(int n, char *x, char *y, char *z){
// 将塔座x上按直径由小到大且自上而下编号为1到n的n个圆盘按规则搬到塔座z上,y可以作为辅助塔座。(c是初值为0的全局变量,对搬动记数)
// 搬动操作move(x,n,z)可定义为: printf("%i. Move disk %i from %c to %c\n", ++c, n, x, z);
if(n == 1){
moveH(x, 1, z);
} else {
hanoi(n-1, x, z, y);
moveH(x, n, z);
hanoi(n-1, y, x, z);
}
}
int main()
{
char first[20] = "第一个柱子";
char second[20] = "第二个柱子";
char third[20] = "第三个柱子";

hanoi(10, first, second, third);
return 0;
}

递归的实现:调用函数和被调用函之间的链接及信息交换需要通过栈来执行

在运行被调用函数之前,系统需要先完成3件事

  1. 将所有的实参、返回地址等信息传递给被调用函数保存
  2. 为被调用函数的局部变量分配存储区
  3. 将控制转移到被调用函数的入口

从被调用函数返回调用函数之前,系统也要完成三件工作

  1. 保存被调用函数的计算结果
  2. 释放被调用函数的数据区
  3. 依照被调用函数保存的返回地址将控制转移到调用函数

队列

循环队列

离散事件模拟

略

第四章 串

kmp算法(克努特-莫里斯-普拉特算法)

思路:模式串本身是已知量,已知量,若和待匹配字符串已经出现部分匹配,则根据这部分匹配我们可以得知,再进行匹配需要滑动的距离。根本目的在于减少重复计算量

关键:next函数

1
2
// j是模式串的下标,k是滑动距离
next[j] = k

tips: 求next函数的过程其实也是一个递归的过程,哈哈哈哈,考虑相同字符问题可以对算法进行修正,得到更好的答案。此算法启示为对细节孜孜不倦的苛求,可以有颠覆的结论。

第五章 数组和广义表

矩阵的压缩存储

压缩存储是指:为多个值相同的元只分配一个存储空间,对零元不分配空间

矩阵运算: 加法,减法,数乘,转置,共轭,共轭转置,乘法,行列式

对称矩阵,三角矩阵,对角矩阵

稀疏矩阵:三元组存储法(位置,值)

广义表

广义表一般记作:LS = $(a_1,a_2,…,a_n)$

$a_i$可以是单个元素,也可以是子表,分别称为原子和子表。习惯上用大写字母表示广义表的名称,用小写字母表示广义表的原子,表非空时,习惯称第一个元素为表头,其余元素组成的表为表尾

广义表的存储结构

通常采用链式存储。

m元多项式的表示

  1. $P(x,y,x) = x^{10}y^3z^2 + 2x^6y^3z^2 + 3x^5y^2z^2 + x^4y^4z + 6x^3y^4z + 2yz + 15$
  2. $P(x,y,x) = ((x^10+2x^6)y^3 + 3x^5y^2)z^2 + ((x^4+6x^3)y^4 + 2y)z + 15$
  3. 广义表表示:$P = z((A,2),(B,1),(15,0))$ (数字代表变元的幂次)
  4. 其中$A = y((C, 3), (D, 2)) C = x((1, 10), (2, 6)) D = x((3, 5)) B = y((E, 4), (F, 1)) E = x((1, 4), (6, 3)) F = x(2, 0)$

广义表的递归算法

分治法设计递归算法

  1. 首先应书写函数的首部和规格说明,严格定义函数的功能和接口(递归调用的界面),对求精函数中所得的和原问题性质相同的子问题,只要接口一致,便可进行递归调用
  2. 对函数中的每一个递归调用都看成只是一个简单的操作,只要接口一致,必能实现规格说明中定义的功能,切忌想的太深太远。

重要的是递归思想的理解和运用

树和二叉树

树的定义:树(Tree)是n(n>=0)个结点的有限集,在任何一个非空树中,树特征:

  • 有且只有一个特定的称为根(Root)的结点
  • 当n>1时,其余结点可分为m(m>0)个互不相交的有限集$T_1,T_2…,T_m$,其中每一个集合本身又是一棵树,并且称为根的子树(subtree)

树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度(Degree)。度为0的结点称为非终端结点或分支结点。除根节点之外,分支结点也称为内部结点。树的度是树内各结点的度的最大值。结点的子树的根的根称为该结点的孩子(Child),相应地,该结点称为孩子的双亲(Parent)。同一个双亲的孩子之间互称为兄弟。结点的祖先是从根到该节点所经分支上的所有结点。以某结点为根的子树中的任一节点都称为该节点的子孙。

结点的层次从根开始定义,根为第一层,根的孩子为第二层。其双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度(Depth)或高度。

如果树的结点的各子树看成从左至右是有次序的(即不能互换),则称该树为有序树,否则称为无序树。在有序树中,最左边子树的根称为第一个孩子,最右边的称为最后一个孩子。

森林(Forest)是m(m>0)棵互不相交的树的集合。对树中的每个结点而言,其子树的集合即为森林。由此,也可以森林和树相互递归的定义来描述树。

Tree = (root, F);$F=(T_1,T_2,…,T_m);T_i=(r_i, F_i)$

二叉树

二叉树是另一种树形结构,它的特点是每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。

二叉树有五种形态:空二叉树,仅有根节点的二叉树,右子树为空的二叉树,左右子树均非空的二叉树,左子树为空的二叉树

二叉树的性质:

  1. 在二叉树第i层上至多有$2^{i-1}$个结点
  2. 深度为k的二叉树至多有$2^k-1$个结点
  3. 对任何一个二叉树,如果其终端结点数为$n_0$,度为2的结点数为$n_2$。则$n_0 = n_2+1$。思路:节点总数为$n = n_0 + n_1 + n_2$;根据分支推出等式:$ n - 1 = B = n_1 + 2n_2$;结合两个等式即可推出。一颗深度为k且有$2^k-1$个结点得二叉树称为满二叉树。深度为k的,有n个结点的二叉树,当且仅当其每一点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称之为完全二叉树。
  4. 具有n个结点的完全二叉树的深度为$\lfloor log_2n\rfloor + 1$
  5. 对于一颗有n个结点的完全二叉树的结点按层序编号,则对任一结点i,有:
    • i=1,此结点为根节点;i>1,则其双亲PARENT(i)是结点$\lfloor i/2 \rfloor$
    • 如果2i>n,则结点i无左孩子;否则其左孩子LCHIL(i)是结点2i
    • 如果2i+1>n,则结点i无右孩子;否则其右孩子RCHILD(i)是结点2i+1
      二叉树的存储结构

顺序存储:最坏的情况,一个深度为k且有k个结点的二叉树却需要长度为$2^k-1$的一维数组

链式存储:二叉链表和三叉链表

遍历二叉树和线索二叉树

特点:先序中序后序是根据根结点的位置定的,顺序是先左后右

  1. 先序遍历二叉树操作定义(DLR):
    1. 访问根结点
    2. 先序遍历左子树
    3. 先序遍历右子树
  2. 中序遍历二叉树的操作定义(LDR):
    1. 中序遍历左子树
    2. 访问根结点
    3. 中序遍历右子树
  3. 后序遍历二叉树的操作定义(LRD):
    1. 后序遍历左子树
    2. 后序遍历右子树
    3. 访问根结点

从中序遍历递归算法执行过程中递归工作栈的状态可见:

  1. 工作记录中包含两项,其一是递归调用的语句编号,其二是指向根结点的指针,则当栈顶记录中的指针非空时,应遍历左子树,即指向左子树根的结点入栈。
  2. 若栈顶记录种的指针值为空,则应退至上一层,若是从左子树返回,则应访问当前层即栈顶记录中指针所指的根结点。
  3. 若是从右子树返回则表明当前层的遍历技术,应继续退栈。从另一角度看,这意味着,遍历右子树时不再需要保存当前层的根指针,可直接修改栈顶记录中的指针即可。

“遍历”是二叉树各种操作的基础,可以在遍历过程中对结点进行各种操作,如:对于一棵已知树可求结点的双亲,求结点的孩子结点,判定结点所在层次,反之,也可在遍历的过程中生成结点,建立二叉树的存储结构。

对二叉树进行遍历的搜索路径除了上述先序、中序、后序外,还可以从上到下、从左到右按层次进行。

显然,遍历二叉树的算法中的基本操作是访问结点,则不论按哪一种次序进行遍历,对含n个结点的二叉树,其时间复杂度均为O(n)。所需辅助空间为遍历过程中栈的最大容量,即树的深度,最坏情况下为n,则空间复杂度也为O(n)。遍历的时候也可以采用二叉树的其他存储结构,如带标志域的三叉链表,此时因存储结构中已存有遍历所需足够信息,则遍历过程中不需另设栈。

线索二叉树

如下规定:若结点有左子树,则其lchild域指示其左孩子,否则令lchild域指示其前驱;若结点有右子树,则其rchild域指示其右孩子,否则令rchild域指示其后继。为了避免混淆,还需要改变结点结构,增加两个标志域:lchild,LTag,data,RTag,rchild。其中LTag取值0,1,分别代表lchild域指示左孩子,前驱。RTag同理。

以这种节点结构构成的二叉链表作为二叉树的存储结构,叫做线索链表,其中指向结点前驱和后继的指针,叫做线索。加上线索的二叉树称之为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。

树和森林

树得存储结构

双亲表示法:一组连续空间存储树的结点,同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置。

孩子表示法:把每个结点的孩子结点排列起来,看成一个线性表,且以单链表作为存储结构,则n个结点有n个孩子链表。而n个头指针又组成一个线性表

孩子兄弟表示法:又称二叉树表示法,或二叉链表示法。即以二叉链表作树的存储结构。链表中结点的两个链域分别指向该节点的第一个孩子结点和下一个兄弟结点。(按照这个思想,所有的树都可以转换为二叉树!!)

森林与二叉树的转换

从树的二叉链表示法可知,任何一课和树对应的二叉树,其右子树必然为空,若把森林中下一棵树看成前一棵树的根结点二叉树表示的右儿子,则同样可以导出二叉树和森林的对应关系

树和森林的遍历

同样分为:先序遍历,中序遍历,后序遍历

树与等价关系

概念:等价关系,等价类,利用树可以划分等价类

赫夫曼树及其应用

从树中一个结点到另一个结点的分支构成这两者之间的路径,路径上的分支数目称为路径长度。树的路径长度是从树根到每一个结点的路径长度之和。树的带权路径长度为树中所有叶子结点的带权路径长度之和,通常记作: $WPL = \sum_{k=1}^{n}w_kl_k$

假设有n个权值${w_1,w_2,…,w_n}$,试构造有n个叶子结点的二叉树,每个叶子结点带权值为$w_i$,其中带权路径长度WPL最小的二叉树称作最优二叉树或赫夫曼树

赫夫曼算法

  1. 根据给定的n个权值${w_1,w_2,…,w_n}$构成n棵二叉树的集合$F={T_1,T_2,…,T_n}$,其中每一棵二叉树$T_i$中只有一个带权为$W_i$的根结点,其左右子树均空
  2. 在F中选取两棵根结点的权值最小的树作为左右子树构造一颗新的二叉树,且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
  3. 在F中删除这两棵树,同时将新得到的二叉树加入到F中
  4. 重复2,3步骤,直到F中只含有一颗树为止。这棵树便是赫夫曼树

赫夫曼编码

若要设计长短不等的编码,则必须是任一个字符的编码都不是另一个字符的编码的前缀,这种编码称做前缀编码

赫夫曼编码

假设每种字符在电文中出现的次数为$w_i$,其编码长度为$l_i$,电文中只有n种字符,则电文总长为$\sum_{i=1}^{n}w_il_i$。对应到二叉树上,若置$w_i$为叶子结点的权,$l_i$恰为从根到叶子的路径长度。则$\sum_{i=1}^{n}w_il_i$恰为二叉树上的带全路径长度。由此可见,设计电文最短的二进制前缀编码即以n种字符出现的频率作权,设计一棵赫夫曼树的问题,由此得到的二进制前缀编码称为赫夫曼编码。

回溯法与树的遍历

在程序设计中,有相当一类求一组解、或求全部解或求最优解的问题,例如:八皇后问题。不是根据某种确定的计算法则,而是利用试探和回溯得搜索技术求解。回溯法也是递归设计的一种重要的方法,它的求解实质上是一个先序遍历一棵‘状态树’的过程,只是这棵树不是遍历前预先建立的,而是隐含在遍历过程中,但如果认识到这点,很多问题的递归过程也就迎刃而解了。

题目:求含n个元素的集合的幂集。
集合A的幂集是由集合A的所有的子集所组成的集合。则A得幂集为$\rho(A)$。

可以利用分治法来设计解法,在此,从另一角度分析问题。幂集的每个元素是一个集合,它或是空集,或含集合A中的一个元素,或集合A中的两个元素,或等于集合A。反之,从集合A的每个元素看,它只有两种状态:它或属于幂集的元素集,或不属于A的幂集元素集。则求$\rho(A)$的元素的过程可看成是依次对集合A中元素进行取或舍的过程,并且可以用一棵树来表示。

回溯法

算法:

1
2
3
4
5
6
7
8
void PowerSet(int i, int n){
//求含n个元素的集合A的幂集$\rho(A)$。进入函数时已对A中前i-1个元素做了取舍处理,现从第i个元素起进行取舍处理。若i>n则求得幂集的一个元素并输出之,初始调用:PowerSet(1, n)
if(i > n) 输出幂集的一个元素;
else {
取第i个元素: PowerSet(i+1, n);
舍第i个元素: PowerSet(i+1, n);
}
} // PowerSet

上述问题的解决是一个满二叉树,树中每个叶子结点的状态都是求解过程中可能出现的状态(即问题的解)。然而很多问题用回溯法和试探求解的时候,描述求解过程的状态树不是一棵满的多叉树。当时谈过程中出现的状态和问题求解产生矛盾时,不再继续试探下去。这时出现得叶子结点不是问题的解的终结状态。这类问题的求解过程可看成是在约束条件下进行先序遍历,并在遍历过程中剪去那些不满足条件的分支。

树的技术

推导过程较麻烦,略,有用到再说

揭露:n个结点的不想似的二叉树有$\frac{1}{n+1}C^n_{2n}$

图

图是一种数据结构,加上一组基本操作,就构成了抽象数据类型。在图形结构中,结点之间的关系可以是任意的,图中任意两个元素之间都有可能相关。

在图中的数据元素通常称为顶点(Vertex),V是顶点的有穷非空集合;VR是两个顶点之间的关系的集合。若$<\nu,\omega>\in VR$,则$<\nu,\omega>$表示从$\nu$到$\omega$的一条弧(Arc)。且称$\nu$为弧尾或初始点(Initial node),称$\omega$为弧头(HEAD)或终端点(Terminal node),此时的图称为有向图(Digraph)。若$<\nu,\omega>\in VR$,则必有$<\omega,\nu>\in VR$。即VR是对称的,则以无序对$(\nu,\omega)$代替这两个有序对,表示$\nu$和$\omega$的一条边(Edge),此时的图称为无向图(Undigraph)。

我们用n表示图中顶点的数目,用e表示边或弧的数目。在下面的讨论中,我们不考虑顶点到其自身的弧或边,即若$<\nu_i, \nu_j> \in VR$则$i \not= j$,那么,对于无向图,e的取值范围是0到$\frac{1}{2}n(n-1)$。有$\frac{1}{2}n(n-1)$条边的无向图称为完全图(Completed graph)。对于有向图e的取值范围是0到$n(n-1)$。具有$n(n-1)$条弧的有向图称为有向完全图。又很少条边或弧(如$e < nlogn$)的图称为稀疏图(Sparse grapth)。反之称为稠密图(Dense grapth)。

有时图的边或弧具有与它相关的数,这种与图的边或弧相关的数叫做权(Weight)。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网(Network)。

假设有两个图G = (V, {E})和G’ = (V’, {E’}),如果$V’\subseteq V$且$E’\subseteq E$,则称G’为G的子图(Subgraph)。

对于无向图G = (V, {E}),如果边$(v, v’) \in E$,则称v,v’互为邻接点(Ajacent)。即v和v’相邻接。边(v,v’)依附(Incident)于定点v和v’,或者说(v,v’)和定点v和v’相关联。顶点v的度(Degree)是和v相关联的边的数目。记为TD(V)。以顶点v为头的弧的数目称为入度(InDegree),记为ID(V)。以v为尾的弧的数目称为v的出度(Outdegree),记为OD(v);顶点v的度为TD(v) = ID(v) + OD(v);

无向图G = (V, {E})中从顶点$\nu$到$\nu’$的路径(Path)。如果G是有向图,则路径也是有向的,顶点序列应该满足$< \nu_{i-1}, \nu_i > \in E$。路径的长度是路径上的边或弧的数目。第一个顶点和最后一个顶点相同的路径称为回路或环。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点,其余顶点不重复出现的回路,称为简单回路或简单环。

在无向图G中,如果从定点v到v’有路径,则称v和v’是连通的。如果对于图中任意两个顶点都是连通的,则称G为连通图(Connected Graph)。连通分量(Connected component),指的是无向图中的极大连通子图。

在有向图中,如果对于每一对顶点,相互之间都存在路径,则称G是强连通图。有向图的极大连通子图称为有向图的强连通分量。

一个连通图的生成树是一个极小连通子图。

如果一个有向图恰有一个顶点的入度为0,其余顶点的入度均为1,则是一棵有向树。一个有向图的生成森林由若干棵有向树组成,含有图中全部定点,但只有足以构成若干棵不相交的有向树的弧。

可对某个顶点的所有邻接点进行排队,在这个排队中自然形成了第一个或第k哥邻接点。若某个顶点的邻接点的排序大于k,则称第k+1个邻接点为第k个邻接点的下一个邻接点,而最后一个邻接点的下一个邻接点为’空’。

图的存储结构

自然采取多重链表的存储结构。由于途中各顶点度不同,最大度数和最小度数可能相差很多,因此,若按度数最大的定点设计结点结构,则会浪费很多单元;反之,按每个顶点自己的度数设计不通的结点结构,又会给操作带来不便。因此,和树类似,在实际应用中不宜采用这种结构,而应根据具体的图和需要进行的操作,设计恰当的结点结构和表结构。常用的有邻接表,邻接多重表和十字链表。

邻接矩阵表示法:使用矩阵存储顶点间相互关系,n个结点构成n*n矩阵。优点:直观,清晰。缺点:占用存储空间大

邻接表: 思路是每个顶点建立一个单链表,存储其邻接边信息。这样若无向图中有n个结点、e条边,则它的邻接表需n个头结点和2e个表结点。显然在边稀疏的情况下,用邻接表表示图比邻接矩阵节省存储空间。当和边相关的信息多时更是如此。邻接表判定两个顶点是否有边或弧链接,没有邻接矩阵方便

十字链表: 弧结点:tailvex | headvex | hlink | tlink | info 顶点结点:data | firstin | firstout。类似邻接表,但更容易找到以顶点为头或尾的弧。在某些有向图中很有用。

邻接多重表:和十字链表类似。无向图的另一种链式存储结构。边结点:mark | ivex | ilink | jvex | jlink | info 。顶点结点:data | firstedge

图的遍历

和树的遍历类似,在此,我们希望从图中的某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次。这一过程叫做图的遍历。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。

通常有两种遍历图的路径:深度优先搜索和广度优先搜索。

深度优先搜索: 此遍历类似于树的先根遍历,是树的先根遍历的推广。深度优先搜索可从图中某个顶点v出发,访问此顶点,然后依次从v的未被访问的邻接点出发深度优先遍历图。

深度优先搜索,邻接矩阵的时间复杂度为$O(n^2)$,邻接表的时间复杂度为O(n+e)。

广度优先搜索: 类似于树的按层遍历的过程。假设从图中某顶点v出发,在访问了v之后依次访问v的各个未曾访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问,直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直到所有顶点被访问到为止。

图的连通性

连通图:从图中任意顶点进行深度优先或广度有限访问,都能访问到所有的顶点

深度优先搜索过程生成的树为深度优先生成树;广度优先搜索过程生成的数为广度优先生成树

非连通图,对应深度优先生成森林,广度优先生成森林

强连通分量: 有向图强连通分量:在有向图G中,如果两个顶点vi,vj间(vi>vj)有一条从vi到vj的有向路径,同时还有一条从vj到vi的有向路径,则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称G是一个强连通图。有向图的极大强连通子图,称为强连通分量(strongly connected components)。

最小生成树: 假设要在n个城市之间建立通信联络网,则n个城市只需要n-1条线路。如何在最节省经费的前提下建立这个通信网。可以用连通网来表示这个问题,我们需要寻找到一棵耗费最小的生成树,这个问题就是最小生成树问题

MST性质:假设 N = (V, {E})是一个连通网,U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值(代价)的边,其中$u \in U,v \in V - U$则必存在一棵包含边$(u, v)$的最小生成树

普里姆算法:假设 N = (V, {E})是一个连通网,TE是N上最小生成树中边的集合。算法从U = { $\mu_0$ }$(\mu_0 \in V)$,TE = {} 开始,重复执行下述操作:在所有$u \in U, v \in V - U$的边$(u,v) \in E$中找一条代价最小的边$(u_0, v_0)$并入集合TE,同时$v_0$并入U,直至U = V为止。此时TE中必有n-1条边,则T = (V, {TE})为N的最小生成树。

普里姆算法时间复杂度为$O(n^2)$(其中n为顶点数)。所以普里姆算法适合求边稠密的网的最小生成树

克鲁斯卡尔算法:假设连通网N = (V, {E}),则令最小生成树的初始状态为只有n个顶点而无边的非联通图T = (V, {}),图中每个顶点自成一个连通分量。在E中选择代价最小的边,若该边依附的顶点落在T中不同的连通分量上,则将此边加入到T当中,否则舍去此边而选择下一条代价最小的边。依次类推,直至T中所有顶点都在同一连通分量上为止。时间复杂度为$O(eloge)$(e为边数),因此适合求边稀疏的网的最小生成树

关节点:假若在删去顶点v以及和v相关联的各边之后,将图的一个连通分量分割成两个或两个以上的连通分量,则称顶点v为该图的一个关节点(articulation point)。

一个没有关节点的连通图称为重连通图(biconnected graph)。若连通图中至少删去k个顶点才能破坏图的连通性,则称此图的连通度为k。

一个无环的有向图称为有向无环图(directed acycline graph),简称DAG图。

有向无环图是描述含有公共子式的表达式的有效工具。例如下述表达式:((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)

有向无环图应用示例

有向无环图也是描述一项工程或系统的进行过程的有效工具。除最简单的情况之外,几乎所有的工程都可分为若干个称作活动的子工程,而这些子工程之间,通常受着一定条件的约束,如其中某些子工程的开始必须在另一些子工程完成之后。对于整个工程和系统,人们关心的是两个方面的问题:一是工程能否顺利进行;二是估算整个工程完成所必需的最短时间。

自反关系:设 R是 A上的一个二元关系,若对于 A中的每一个元素 a, (a,a)都属于 R,则称 R为自反关系。换言之,在自反关系中, A中每一个元素与其自身相关

反对称关系:反对称性是一个关于数学上二元关系的性质。大概地说,集合 X 上的二元关系 R 是反对称的,当且仅当不存在X里的一对相异元素a, b,它们 R-关系于彼此。

传递关系:在逻辑学和数学中,若对所有的 a,b,c 属于 X,下述语句保持有效,则集合 X 上的二元关系 R 是传递的:「若a 关系到 b 且 b 关系到 c, 则 a 关系到 c。」

偏序和全序

偏序和全序是公里集合论中的概念。

首先你要知道什么是二元关系。
比如实数中的“大小”关系,集合的集合中的“包含”关系就是两种二元关系。

所谓偏序,即偏序关系,是一种二元关系。
所谓全序,即全序关系,自然也是一种二元关系。

全序是指,集合中的任两个元素之间都可以比较的关系。比如实数中的任两个数都可以比较大小,那么“大小”就是实数集的一个全序关系。

偏序是指,集合中只有部分元素之间可以比较的关系。比如复数集中并不是所有的数都可以比较大小,那么“大小”就是复数集的一个偏序关系。

显然,全序关系必是偏序关系。反之不成立。

拓扑排序:由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。

这种用顶点表示活动,用弧表示活动间的优先关系的有向图称为顶点表示活动的网(Activity On Vertex Network)。简称AOV-网

拓扑排序

  1. 在有向图中选一个没有前驱的顶点且输出之
  2. 从图中删除该顶点和所有以它为尾的弧

重复上述两步,直至全部顶点均已输出,或者当前图中不存在无前驱的顶点为止,后一种情况说明有向图中存在环

关键路径

与AOV-网相对应的是AOE-网(Activity On Edge)即表示活动的网。AOE-网是一个带权的有向无环图,其中顶点表示事件(Event),弧表示活动,权表示活动持续时间。

AOE-网有待研究的问题是:1,完成整项工程至少需要多少时间。2,哪些活动是影响工程进度的关键

由于在AOE-网中有些活动可以并行的进行,所以完成工程的最短时间是从开始点到完成点的最长路径的长度。路径长度最长的路径叫做关键路径(Critical Path)。

关键路径的算法:

  1. 输入e条弧<j,k>。建立AOE-网的存储结构
  2. 从源点$v_0$出发,令ve[0] = 0,按拓扑有序求其余各顶点的最早发生时间$ ve[i] (1 \le i \le (n-1)) $。如果得到的拓扑有序中顶点个数小于网中顶点数n,则说明网中存在环,不能求关键路径,算法终止;否则执行步骤3
  3. 从汇点$v_n$出发,令vl[n-1] = ve[n-1],按逆拓扑有序求其余各顶点的最迟发生时间$vli$。
  4. 根据各点的ve和vl值,求每条弧s的最早开始时间e(s)和最迟开始时间ls(s)。若某条弧满足条件e(s)=l(s),则为关键活动。

理解要点,求关键活动 –> 各事件最早发生时间和最迟发生时间 –> 求弧的最早发生时间和最迟发生时间 –> 关键弧。2,3步骤一个给出初始值,一个给出终值。但思路都是由后往前推,递归思想。

应用:1956年,美国杜邦公司提出关键路径法,并于1957年首先用于1000万美元化工厂建设,工期比原计划缩短了4个月。杜邦公司在采用关键路径法的一年中,节省了100万美元。

最短路径

假如,一个旅客从A城到B城,他希望选择一条途中中转次数最少的路线。假设图中每一站都要换车,则这个问题反映到图上就是要找一条从顶点A到B所含边的数目最少的路径。我们只需从A出发对图作广度优先搜索,一旦遇到顶点B就终止。由此所得广度优先生成树上,从根顶点A到顶点B的路径就是中转次数最少的路径,路径A与B之间的顶点就是途径的中转站数。

本节将讨论带权有向图,并称路径上的第一个顶点为源点(Sourse),最后一个顶点为终点(Destination)。

从某个源点到其余各顶点的最短路径

迪杰斯特拉算法

首先,引进一个辅助向量D,它的每个分量D[i]表示当前所找到的从始点v到每个终点$v_i$的最短路径的长度。他的初态为:若从v到$v_i$有弧,则D[i]为弧上的权值;否则置D[i]为$\infty$。显然,长度为$D[j] = Min{D[i] | v_i \in V}$的路径就是从v出发的长度最短的一条,此路径为$(v, v_j)$

一般情况下,假设S为已求得最短路径的终点的集合,则可证明:下一条最短路径(设其终点为x)或者是弧(v,x),或者是中间只经过S中的顶点而最后到达顶点x的路径。

因此在一般情况下,下一条长度次短的最短路径的长度必是:$D[j] = Min{D[i] | v_i /in V - S}$。其中,D[i]或者是弧$(v,v_i)$上的权值或者是$Dk$和弧$(v_k, v_i)$上的权值之和。

根据以上分析,可得到如下描述的算法:

  1. 假设用带权的邻接矩阵arcs来表示带权有向图,arcs[i][j]表示弧$(v_i,v_j)$上的权值。若$(v_i,v_j)$不存在,则置arcs[i][j]为$\infty$。S为已找到从v出发的最短路径的终点的集合,它的初始状态为空集。那么,从v出发到图上其余各顶点$v_i$可能达到的最短路径长度的初值为:$D[i] = arcs[Locate Vex(G, v)][i] v_i \in V$。
  2. 选择$v_j$,使得:$D[j] = Min{D[i] | v_i \in V-S }$。$v_j$就是当前求得的一条从v出发的最短路径的终点,令:$S = S \cup {j}$
  3. 修改从v出发到集合V-S上任一顶点$v_k$可达的最短路径长度。如果:D[j] + arcs[j][k] < D[k]。则修改D[k]为D[k] = D[j] + arcs[j][k]
  4. 重复2,3共n-1次。由此求得从v到图上其余各顶点的最短路径是依路径长度递增的序列。

迪杰斯特拉算法时间复杂度$O(n^2)$

每一对顶点之间的最短路径

很简单的方法是每次以一个顶点为源点,重复执行迪杰斯特拉算法n次,这样便可求的每一对顶点之间的最短路径。时间复杂度为$O(n^3)$。

弗洛伊德算法:时间复杂度也是$O(n^3)$,形式上要简单一点。

弗洛伊德算法仍然从带权的邻接矩阵cost出发,其基本思想为:

现在定义一个n阶方阵序列
$D^{-1},D^{0},D^{1},…,D^{k},…,D^{(n-1)}$

其中
$D^{-1}[i][j] = G.arcs[i][j]$
$D^{(k)}[i][j] = Min\{D^{(k-1)}[i][j],D^{(k-1)}[i][k] + D^{(k-1)}[k][i]\} 0 \le k \le n-1$

理解要点:递归思想,根据公式理解

动态存储管理

动态存储管理的基本问题是系统如何应用户提出的‘请求’分配内存?又如何回收那些用户不再使用而‘释放’的内存,以备新的‘请求’产生时重新进行分配?

系统每次分配给用户都是一个地址连续的内存区。为了叙述方便起见,将统称已分配给用户使用的地址连续的内存区为‘占用快’,称未分配的地址连续的内存区为‘可利用空间块’或‘空闲块’。

当系统运行了一段时间后,内存区形成犬牙交错的形态,当有新的用户进入系统请求分配内存,那么系统应该如何做呢?

通常有两种做法:一种策略是系统继续从高地址的空闲块中进行分配,而不理会已分配给用户的内存区是否空闲,直到分配无法进行(即剩余的空间块不能满足分配的请求)时,系统才去回收所有用户不再使用的空闲块,并且重新组织内存,将所有空闲区连接在一起称为一个大的空闲块。另一种策略是用户一旦运行结束,便将它所占用的内存区释放为空闲块,同时,每当新的用户请求分配内存时,系统需要巡视整个内存区中所有空闲块,并从中找出一个‘合适’的空闲块分配之。由此,系统需建立一张记录所有空闲块的‘可利用空间表’,此表的结构可以是‘目录表’,也可以是‘链表’

可利用空间表及分配方法

下面仅讨论链表的情况

可以用空间表又称‘存储池’

根据系统的不同情况,可利用空间表可以有以下3种不同的结构形式:

  1. 系统运行期间所有用户请求分配的存储量大小相同。对此类系统,通常的做法是,在系统开始运行时将归它使用的内存区按所需大小分割成大小相同的块,然后用指针链接成一个可利用空间表。由于表中结点大小相同,则分配时无需查找,只要将第一个结点分配给用户即可;同样,当用户释放内存时,系统只要将用户释放的空间块插入在表头即可。可见,这种情况下的可利用空间表实质上是一个链栈。这是一种最简单的动态存储管理方式。
  2. 系统运行期间,用户请求分配的存储量有若干种大小的规格。对此类系统,一般情况下是建立若干个可利用空间表,同一链表中的结点大小相同。每个结点中第一个字设有链域(link)、标志域(tag)和结点类型域(type)
  3. 系统运行期间分配给用户的内存块的大小不固定,可以随请求而变。因此,可利用空间表中结点即空闲块的大小也是随意的。通常,操作系统中的可利用空间表属这种类型。由于链表中结点大小不同,则结点的结构与前两种情况也有所不同,结点中除标志域和链域之外,尚需有一个结点大小域(size),以指示空闲块的存储量。假设某用户需大小为n的内存,而可利用空间表中仅有一块大小为$m ge n$的空间快,则只需将其中大小为n的一部分分配给申请分配的用户,同时将剩余大小为m-n的部分作为一个结点留在链表中即可。然而,若可利用空间表中有若干个不小于n的空闲块时,该分配哪一块呢?通常,可有3种不同的分配策略:
    • 首次拟合法:从表头指针开始查找可利用空间表,将找到的第一个大小不小于n的空闲块的一部分分配给用户
    • 最佳拟合法:将可利用空间表中一个不小于n且最接近n的空闲块的一部分分配给用户,为了节省时间,预先需要排序
    • 最差拟合法:讲可利用空间表中不小于n且是链表中最大的空闲块的一部分分配给用户,为了节省时间,预先需要排序
      上述三种分配策略个有所长。一般来说,最佳拟合法适用于请求分配的内存大小范围较广的系统。最差拟合法适用于请求分配大小范围较窄的系统。首次拟合介于二者之间,通常适用于系统事先不掌握运行期间可能出现的请求分配和释放的信息的情况。

从时间上来说,首次拟合 < 最差拟合法 < 最佳拟合法

为了更有效的利用内存,就要求系统在回收时应考虑将地址相邻的空闲块合并成尽可能大的结点。

边界标识法

边界标识法(boundary tag method)是操作系统中用以进行动态分区分配的一种存储管理方法。

分配算法(首次拟合法)

  • 假设找到的此块待分配的空闲块的容量为m个字,若每次分配只是从中分配n个字给用户,剩余m-n哥字大小的结点仍留在链表中,则在若干次分配后,链表中会出现一些容量极小总也分配不出去的空闲块,这就大大减慢了分配(查找)的速度。弥补的办法是:选定一个适当的常量e,当$m - n le e$时,就将容量为m的空闲块整块分配给用户;反之,只分配其中n个字的内存块。同时为了避免修改指针,约定将该结点中的高地址部分分配给用户。
  • 如果每次分配都从同一个结点开始查找的话,势必造成存储量小的结点密集在头指针pav所指结点附近,这同样会增加查询较大空闲块的时间。反之,如果每次分配从不同的结点开始查找,使分配后剩余的小块均匀的分布在链表中
    回收算法

一旦用户释放占用块,系统需要立即回收以备新的请求产生时进行再分配。为了使物理地址毗邻的空闲结合成一个尽可能大的结点,则首先需要检查刚释放的占用块的左,右紧邻是否为空闲块。由于本系统在每个内存区的边界上都设有标志值,则很容易辨明这一点。

若释放块的左右邻块均为占用块,则处理最为简单,只要将此新的空闲块作为一个结点插入到可利用空闲表即可;若只有左邻区是空闲块,则应与左邻区合并成一个结点;若是只有右邻区是空闲块,则应与右邻区合并成一个结点;左右邻区都是空闲块,则应将3块合起来称为一个结点留在可利用空间表中。

伙伴系统

伙伴系统(buddy system)是操作系统中用到的另一种动态存储管理方法。它和边界标识法类似,在用户提出申请时,分配一块‘恰当’的内存区给用户;反之,在用户释放内存区时即回收。所不同的是:在伙伴系统中,无论是占用块或空闲块,其大小均为2的k次幂。

可利用空间表的结构

假设系统的可利用内存空间容量为$2^m$个字(地址从0到$2^m - 1$)。则在开始运行时,整个内存区是一个大小为$2^m$的空闲块,在运行一段时间后,被分割成若干占用块和空闲快。为了再分配时查找方便起见,我们将所有大小相同的空闲块建于一张子表中。每个子表是一个双重链表,这样链表可能有m+1个,将这m+1个表头指针用向量结构组织成一个表,这就是伙伴系统中的可利用空间表。

分配算法

当用户提出大小为n的内存请求时,首先在可利用标上寻找结点大小与n相匹配的子表,若此子表非空,则将子表中任意一个结点分配之即可;若此子表为空,则需从结点更大的非空子表中去查找,直至找到一个空闲块,则将其中一部分分配给用户,而将剩余部分插入相应的子表中。

回收算法

在分配的时候经常需要将一个大的空闲块分裂成两个大小相等的存储区,这两个由同一个大块分裂出来的小块就称之‘互为伙伴’。

思路是,内存按照2的倍数划分,如果两个空闲内存分别处于两个不同的2的同倍区间,则不能合并

无用单元回收

有时,系统在不恰当的时候没有进行回收,会产生‘无用单元’和‘悬挂访问’

1
2
p = malloc(size);
p = null;

上述为无用单元

1
2
3
p = malloc(size);
q = p;
free(p);

上述为悬挂访问

结构性问题也会产生‘无用单元’,解决方案:

  • 使用访问计数器:在所有的广义表或字表中增加一个表头结点,并设立一个‘计数域’,它的值为指向该子表或广义表的指针数目。只有当该计数域的值为零时,此子表或广义表中结点才被释放。
  • 收集无用单元:在程序运行过程中,对所有的链表结点,不管它是否还有用,都不回收,直到整个可利用空间表为空。此时才暂时中断执行程序,将所有当前不被使用的结点链接在一起,称为一个新的可利用空间表,而后程序再继续执行。显然在一般情况下,是无法辨别哪些结点是当前未被使用的。然而,对于一个正在运行的程序,哪些结点正在使用是容易查明的,这只要从所有当前正在运行的程序,哪些结点正在使用是容易查明的,这只要从所有当前正在工作的指针变量出发,顺链遍历,那么,所有链结在这些链上的结点都是占用的。反之,可利用存储空间中的其余结点就都是无用的了。由此,收集无用单元应分两步进行:第一步是对所有占用结点加上标志。回顾第五章的广义表存储结构可在每个结点上再加设一个标志(mark)域,假设在无用单元收集之前所有结点的标志域均置为‘0’,则加上标志就是将结点的标志域置为‘1’;第二步是对整个可利用存储空间顺序扫描一遍,将所有标志域为’0‘的结点链接成一个新的可利用空间表。值得注意的是:上述第二步是容易进行的,而第一步是在极其困难的条件下进行的,因此,人们的精力主要集中在研究标志算法上。下面我们介绍3中标志算法。

标志算法

  1. 递归算法:从上面所述可知,加标志的操作实质上是遍历广义表,将广义表中所有结点的标志域赋值‘1’。我们可以写出遍历(加标志)算法的递归定义。这个算法很简单,易于用允许递归的高级语言描述之。但是,它需要一个较大的实现递归用的栈的辅助内存,这部分内存不能用于动态分配。并且,由于列表的层次不定,使得栈的容量不容易确定,除非是在内存区开辟一个相当大的区域留作栈,否则就有可能由于在标志过程中因栈的溢出而使系统瘫痪。
  2. 非递归算法:前序遍历二叉树思想(深度优先搜索),广度有优先搜索。这两种非递归算法中,虽然附设的栈或队列的容量比递归算法中的栈容量小,但和递归算法有同样的问题,仍需要一个不确定量的附加存储,因此也不是理想的方法。
  3. 利用表结点本身的指针域标记遍历路径的算法: 利用指针变换可以解决内存占用问题

三种方法个有利弊。第三种方法进行标志的时候不需要附加存储,使得动态分配的可利用空间得到充分利用,但是时间上开销很大。第二种方法操作简单,时间上要节省很多,然而需要占有一定空间,使动态分配所有的存储量减少。总之,无用单元的收集是很费时间的,不能在实时处理的情况下应用。

可利用内存区只有少量结点为无用结点时,收集无用单元的工作效率很低,当系统回复运行的时候,这些结点又很快被消耗掉,导致另一次无用单元的收集。如此下去有可能导致恶性循环,以致最后整个系统瘫痪。解决的办法可以由系统事先确定一个常数k,当收集到的无用单元数为k或更少时,系统就不再运行下去。

存储紧缩

另一种结构的动态存储管理方法

在整个动态存储管理的过程中,不管在哪个时刻,可利用空间都是一个地址连续的存储区,在编译程序中称之为‘堆’,每次分配都是从这个可利用空间中划出一块。但是回收用户释放的空闲块就比较麻烦。由于系统的可利用空间始终是一个地址连续的存储块,因此回收时必须将所释放的空闲块合并到整个堆上去才能重新使用,这就是‘存储紧缩’的任务。需要四步操作:

  1. 计算占用块的新地址
  2. 修改用户的初始变量表
  3. 检查每个占用块中存储的数据
  4. 将所有占用块迁移到新地址去

可见,存储紧缩法比无用单元收集法更为复杂,前者不仅要传送数据,而且还要修改所有占用块中的指针值,因此,存储紧缩也是一个系统操作,且非迫不得已就不用。

查找

查找表(Search Table):是由同一类型的数据元素(或记录)构成的集合。由于‘集合’中的数据元素之间存在着完全松散的关系,因此查找表是一种非常灵便的数据结构。

对查找表经常进行的操作有:

  1. 查询某个‘特定的’数据元素是否在查找表中
  2. 检索某个‘特定的’数据元素的各种属性
  3. 在查找表中插入一个数据元素
  4. 查找表中删去某个数据元素

若对查找表只作前两种统称为‘查找’的操作,则称此类查找表为静态查找表(Static Search Table)。若存在后两种操作,称为动态查找表(Dynamic Search Table)。

关键字(Key):数据元素(或记录)中某个数据项的的值,用它可以标识(识别)一个数据元素(或记录)。若此关键字可以唯一地标识一个记录,则称此关键字为主关键字(Primary Key)(对不同的记录,其主关键字均不同)。反之,称用以识别若干记录的关键字为次关键字(Secondary Key)

查找:根据给定的某个值,在查找表中确定一个其关键字等于给定值记录或数据元素。若表中存在这样一条记录,则称查找是成功的,此时查找的结果为给出整个记录的信息,或指示该记录在查找表中的位置;若表中不存在关键字等于给定值的记录,则称查找不成功,此时查找的结果可给出一个‘空’记录或‘空’指针

静态查找表

顺序表的查找

顺序查找(Sequential Search)的查找过程为:从表中最后一个记录开始,逐个进行记录的关键字和给定值比较,若某个记录的关键字和给定值比较相等,则查找成功,找到所查记录,反之,若直至第一个记录,其关键字和给定值比较都不等,则表明表中没有所查记录,查找不成功。

查找操作的性能分析

定义:为确定记录在查找表中的位置,需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度(Average Search Length)。

公式:$ASL = \sum_{i=1}^n P_iC_i$ 其中:$P_i$为查找表中第i个记录的概率,且$\sum_{i=1}^n P_i = 1$。

$ASL_{ss} = \frac{n+1}{2}$

有序表的查找

折半查找(Binary Search):先确定待查记录所在的范围(区间),然后逐步缩小范围直到找到或找不到记录为止。

$ASL_{bs} = log_2(n+1) - 1$

可见,折半查找的效率比顺序查找高,但折半查找只适用于有序表,且限于顺序存储结构

以有序表表示静态查找表时,进行查找的方法除折半查找之外,还有斐波那契查找和插值查找。

斐波那契查找的平均性能比折半查找好,但最坏情况下的性能却比折半查找差。它还有一个优点就是分割的时候只需进行加,减运算

插值查找只适用于关键字分布均匀的表,在这种情况下,对表长较大的顺序表,其平均性能比折半查找好。

静态树表的查找

当有序表中各记录的查找概率不等时,如果只考虑查找成功的情况,则使查找性能最佳的判定树是其带权内路径长度之和PH值(PH值和平均查找长度成正比):

$PH = \sum_{i=1}^n w_i h_i$

取最小值的二叉树。其中:n为二叉树上结点的个数(即有序表的长度);$h_i$为第i个结点在二叉树上的层次数;结点的权$w_i = cp_i(i = 1,2…,n)$。其中$p_i$为结点的查找概率,c为某个常量。称PH值取最小的二叉树为静态最优查找树(Static Optimal Search)。静态最优查找树花费的时间代价较高,因此不做详细讨论。在此介绍一种构造近似最优查找数的有效算法。

已知一个按关键字有序的记录序列

$(r_l, r_{l+1}, … , r_h$ (9-8)

其中:$r_{l}.key < r_{l+1}.key < … < r_{h}.key$

与每个记录相应的权值为:${w_{l},w_{l+1}, … , w_{h}}$

现构造一棵二叉树,使这棵二叉树的带权内路径长度PH值在所有具有同样权值的二叉树中近似为最小,称这类二叉树为次优查找树(Nearly Optimal Search Tree)。

构造次优查找树的方法是:首先在式(9-8)所示的记录序列中取第i($l \le i \le h$)个记录构造根结点$r_i$,使得:

$\Delta P_{i} = | \sum_{j=i+1}^h w_j - \sum_{j=l}^{i-1} w_j|$

取最小值($\Delta P_{i} = min{\Delta P_{j}}, l \le j \le h$),然后分别对子序列$(r_l, r_{l+1}, … , r_{i-1}$ 和$(r_{i+1}, … , r_{h}$ 构造两棵次优查找树。分别设为根结点$r_i$的左子树和右子树。

为了便于计算$\Delta P$,引入累计权值和:$sw_i = \sum_{j=l}^i w_j$,并设$w_{l-1} = 0$,则:

$\Delta P_{i} = |(sw_h + sw_{l-1}) - sw_i - sw_{i-1}|$

由此可得构造次优查找树的递归算法。

大量的实验研究表明,次优查找树和最优查找树的查找性能之差仅为1%-2%,很少超过3%,而且构造次优查找树的算法时间复杂度为O(nlogn)。

可见,在记录的查找概率不等时,可用次优查找树表示静态查找树,故又称静态树表。

索引顺序表的查找

索引项组成的索引表按关键字有序,则确定块的查找可以用顺序查找,亦可用折半查找,而块中记录是任意排列的,则在块中只能是顺序查找。由此,分块查找的算法即为两种算法的简单合成

$ASL_{bs} = L_b + L_w$

其中$L_b$为查找索引表确定所在块的平均查找长度。$L_w$为在块中查找元素的平均长度。

一般情况下,为进行分块查找,可以将长度为n的表均匀的分成b块,每块含有s个记录,即$b = \lceil n/s \rceil$;又假定表中每个记录的查找概率相等,则每块查找的概率为1/b,块中的每个记录的查找概率为1/s。

若用顺序查找确定所在块,则平均查找长度为:$ASL_{bs} = \frac{1}{2}(\frac{n}{s} + s) + 1$

若用折半查找确定所在块,则分块查找的平均查找长度为:$ASL_{bs} = log_{2}(\frac{n}{s} + 1) + \frac{s}{2}$

动态查找表

动态查找表的特点就是,表结构本身是在查找过程中动态生成的,即对于给定值key,若表中存在其关键字等于key的记录,则查找成功返回,否则插入关键字等于key的记录。

二叉排序树和平衡二叉树

假设i个关键字小于第一个关键字:
平均查找长度:$P(n,i) = 1 \frac n [1 + i*(P(i) + 1) + (n - i -1)(P(n-i-1)+1)]$
其中P(i)为含有i个结点的二叉排序树的平均查找长度,则P(i)+1为查找左子树中每个关键字所用比较次数的平均值

对上式取平均值:当$n ge 2$时,$ P(n) le 2(1 + 1 /frac n)lnn $

由此可见,在随机的情况下,二叉排序树的平均查找长度和logn是等数量级的,然而在某些情况下(概率约为46.5%),尚需在构成二叉排序树的过程中进行‘平衡化’处理,称为二叉平衡树。

平衡二叉树

平衡二叉树(Balanced Binary Tree)又称AVL树。它或者是一颗空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差绝对值不超过1。若将二叉树上结点的平衡因子BF(Blance Factor)定义为该节点的左子树的深度减去该节点的右子树的深度,则平衡二叉树上所有的平衡因子只可能是-1,0和1。

二叉排序树构成平衡二叉树方法

  1. 单向右旋平衡处理
  2. 单向左旋平衡处理
  3. 双向旋转(先左后右)平衡处理
  4. 双向旋转(先右后左)平衡处理

平衡树查找分析:时间复杂度为O(logn)

B-树和B+树

B-树是一种平衡的多路查找树,它在文件系统中很有用。在此介绍这种树的结构及其查找算法

一棵m阶的B-树,或为空树,或为满足下列特性的m叉树:

  1. 树中每个结点至多有m棵子树
  2. 若根结点不是叶子结点,则至少有两棵子树
  3. 除根之外的所有非终端结点至少有$\lceil m/2 \rceil$棵子树
  4. 所有的非终端结点中包含下列信息数据:$(n, A_0, K_1, A_1, K_2, A_2, … , K_n, A_n)$
    其中:$K_i(i=1, … ,n)$为关键字,且$K_i<K_{i+1}$;$A_i(i=1, … ,n)$为指向子树根结点的指针,且指针$A_{i-1}$所指子树中所有结点的关键字均小于$K_i$,$A_n$所指子树中所有结点的关键字均大于$K_n$。
  5. 所有叶子结点都出现在同一层次上,并且不带信息

由此可见,在B-树上进行查找的过程是一个顺时针查找结点和在结点关键字中进行查找的交叉进行过程

B-树查找分析
B-树上查找包含两种基本操作:1)在B-树中找结点。2)在结点中找关键字。
其中第一步是在磁盘上进行的,因此,在磁盘上进行查找的次数,即待查关键字所在结点再B-树上的层次数,是B-树查找效率的首要因素。

B+树

和B-树的差异

  1. 有n棵子树的结点中含有n个关键字
  2. 所有的叶子结点中包含了全部关键字信息,及指向含这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接
  3. 所有的非终端结点可以看成是索引部分,结点中仅含有其子树中的最大(或最小)的关键字。

键树

键树又称数字查找树(Digital Search Trees)。它是一颗度>=2的树。

哈希表

  1. 哈希函数是一个映像,因此哈希函数的设定很灵活,只要使得任何关键字由此所得的哈希函数值都落在表长允许范围之内即可。
  2. 对不同的关键字可能得到同一哈希地址

    内部排序

排序:将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列。

假设$K_i = K_j$,且在排序前的序列中$R_i$领先于$R_j$。若在排序后的序列中$R_i$仍领先于$R_j$,则称所用的排序方法是稳定的。否则称排序方法是不稳定的。

内部排序:指的是待排序记录存放在计算机随机存储器中进行的排序过程

外部排序:指的是带排序记录数量很大,以致内存一次不能容纳全部记录。在排序过程中需要对外存进行访问的排序过程。

插入排序

  1. 直接插入排序
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    function insertSort(sqList){
    if(sqList.length === 0){
    return sqList
    }
    let newList = [sqList[0]]
    for (let i = 1; i < sqList.length; i++) {
    innerloop:
    for (let j = newList.length-1; j >=0 ; j--) {
    let newEle = sqList[i]
    let ele = newList[j]
    let leftArr = newList.slice(0,j+1)
    let rightArr = newList.slice(j+1, newList.length)
    if(newEle >= ele){
    newList = [].concat(leftArr, newEle, rightArr)
    break innerloop
    }
    if(j === 0 && newEle < ele){
    newList = [].concat(newEle, rightArr)
    break innerloop
    }
    }
    }
    return newList
    }
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 <stdio.h>
int main()
{
int a[]={98,76,109,34,67,190,80,12,14,89,1};
int k=sizeof(a)/sizeof(a[0]);
int j;
for(int i=1;i<k;i++)//循环从第2个元素开始
{
if(a[i]<a[i-1])
{
int temp=a[i];
for(j=i-1;j>=0 && a[j]>temp;j--)
{
a[j+1]=a[j];
}
a[j+1]=temp;//此处就是a[j+1]=temp;
}
}
for(int f=0;f<k;f++)
{
printf("%d\n", a[f]);
}
return 0;
}

关键是第二个循环由后往前走,找到正确的位置必须跳出循环,时间复杂度是$O(n^2)$,注意c语言版本充分利用了原有空间!

  1. 折半插入排序
  2. 2-路插入排序
  3. 希尔排序
    希尔排序(Shell’s Sort)又称‘缩小增量排序’(Diminishing Increment Sort),它也是一种属插入排序类的方法,但在时间效率上较前几种排序方法有较大的改进
    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
    #include<stdio.h>
    #include<math.h>
    #define MAXNUM 10
    void main()
    {
    void shellSort(int array[],int n,int t);//t为排序趟数
    int array[MAXNUM],i;
    for(i=0;i<MAXNUM;i++)
    scanf("%d",&array[i]);
    shellSort(array,MAXNUM,(int)(log(MAXNUM+1)/log(2))); //排序趟数应为log2(n+1)的整数部分
    for(i=0;i<MAXNUM;i++)
    printf("%d ",array[i]);
    printf("\n");
    }

    //根据当前增量进行插入排序
    void shellInsert(int array[],int n,int dk)
    {
    int i,j,temp;
    for(i=dk;i<n;i++)//分别向每组的有序区域插入
    {
    temp=array[i];
    for(j=i-dk;(j>=i%dk)&&array[j]>temp;j-=dk)//比较与记录后移同时进行
    array[j+dk]=array[j];
    if(j!=i-dk)
    array[j+dk]=temp;//插入
    }
    }

    //计算Hibbard增量
    int dkHibbard(int t,int k)
    {
    return (int)(pow(2,t-k+1)-1);
    }

    //希尔排序
    void shellSort(int array[],int n,int t)
    {
    void shellInsert(int array[],int n,int dk);
    int i;
    for(i=1;i<=t;i++)
    shellInsert(array,n,dkHibbard(t,i));
    }

    //此写法便于理解,实际应用时应将上述三个函数写成一个函数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var arr=[49,38,65,97,76,13,27,49,55,04];
var len = arr.length;
//分段缩小循环
for(var fraction = Math.floor(len/2); fraction>0; fraction = Math.floor(fraction/2)){
//基础循环
for(var i = fraction; i<len; i++){
//分段排序循环
for(var j = i - fraction; j >= 0 && arr[j] > arr[fraction+j]; j -= fraction){
var temp = arr[j];
arr[j] = arr[fraction+j];
arr[fraction+j] = temp;
}
}
}
console.log(arr);

快速排序

藉由交换进行排序的方法

  1. 起泡排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    var arr=[49,38,65,97,76,13,27,49,55,04];

    function BubbleSort(arr){
    for (let i = arr.length-1; i > 0; i--) {
    for (let j = 0; j < i; j++) {
    let cur = arr[j];
    let next = arr[j+1];
    if(cur > next){
    arr[j+1] = cur
    arr[j] = next
    }
    }
    }
    console.log(arr)
    }

    BubbleSort(arr)
  2. 快速排序

    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
    let arr = [1, 2, 9, 8, 78, 131, 38, 12]
    function quickSort(arr, left, right){
    let i = left;
    let j = right;
    let k = left;
    while (i < j) {
    while (arr[k] <= arr[j] && j > k) {
    j --
    }
    let temp = arr[k]
    arr[k] = arr[j]
    arr[j] = temp
    k = j
    while (arr[k] >= arr[i] && i < k) {
    i ++
    }
    temp = arr[k]
    arr[k] = arr[i]
    arr[i] = temp
    k = i
    }
    if((k - left) > 1){
    quickSort(arr, left, k-1)
    }
    if((right - k) > 1){
    quickSort(arr, k+1, right)
    }
    }
    quickSort(arr, 0, arr.length - 1)
    console.log(arr)

快速排序平均性能最好,时间复杂度为O(nlogn)。缺点是占用栈空间,经过优化后空间复杂度可以为O(logn)

选择排序

  1. 简单选择排序
  2. 树形选择排序
  3. 堆排序
    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
    /**
    *AuthorJenaszhang
    */
    Array.prototype.buildMaxHeap = function(){
    for(var i = Math.floor(this.length/2)-1 ; i>=0 ; i--){
    this.heapAdjust(i, this.length);
    }
    };

    Array.prototype.swap = function(i,j){
    var tmp = this[i];
    this[i] = this[j];
    this[j] = tmp;
    };

    Array.prototype.heapSort=function(){
    this.buildMaxHeap();
    for(var i = this.length-1;i>0;i--){
    this.swap(0,i);
    this.heapAdjust(0,i);
    }

    return this;
    };

    Array.prototype.heapAdjust=function(i,j){
    var largest=i;
    var left=2*i+1;
    var right=2*i+2;

    if(left<j && this[largest] < this[left]){
    largest = left;
    }

    if(right<j && this[largest] < this[right]){
    largest = right;
    }

    if(largest!=i){
    this.swap(i,largest);
    this.heapAdjust(largest,j);
    }
    };

    var a=new Array();
    [].push.apply(a,[2,3,89,57,23,72,43,105]);
    console.log(a.heapSort());

归并排序

基本思路是,假设要排序的序列本来就是一个个有序数列,然后逐渐合并

归并排序是稳定的排序算法,实现归并排序需要等数量的辅助空间,时间复杂度为O(nlogn)

基数排序

基本思路是,按照关键码分组,由高到低是MSD,由低到高是LSD

基数排序(Radix Sorting)是完全不同的一种排序方法。

各种内部排序方法的比较讨论

排序方法 平均时间 最坏情况 辅助存储

  • 简单排序 $O(n^2)$ $O(n^2)$ O(1)
  • 快速排序 O(nlogn) $O(n^2)$ O(logn)
  • 堆排序 O(nlogn) O(nlogn) O(1)
  • 归并排序 O(nlogn) O(nlogn) O(n)
  • 基数排序 O(d(n + rd)) O(d(n + rd)) O(rd)

外部排序

外存信息的存取

计算机一般有两种存储器:内存储器(主存)和外存储器(辅存)。内存的信息可随机存储,且存取速度快,但价格贵,容量小。外存储器包括磁带和磁盘,前者为顺序存储设备,后者为随机存储设备。

  1. 归并排序
  2. 置换-选择排序

重要概念是,外存是必须要读到内存中进行排序的,外存读取速度慢,容量大

文件

有关文件的基本概念

  • 文件及其类别:操作系统中的文件仅是一维的连续的字符序列,无结构,无解释。它也是记录的集合,这个记录仅仅是一个字符组,用户为了存取、加工方便,把文件中的信息划分称若干组,每一组信息称为一个逻辑记录,且可按顺序编号。数据库中的文件是带有结构的记录的集合;这类记录是由一个或多个数据项组成的集合;这类记录是由一个或多个数据项组成的集合,它也是文件中可存取的数据的基本单位。数据项是最基本的不可分的数据单位,也是文件中可使用的数据的最小单位。若文件中每个记录含有的信息长度相同,则称这类记录为定长记录,由这类记录组成的文件称做定长记录文件。若文件中含有信息长度不等的不定长记录,则称不定长记录文件。数据库文件还分为单关键字文件和多关键字文件。

  • 记录的逻辑结构和物理结构:逻辑结构着眼于用户使用方便;物理结构应该考虑提高存储空间的利用率和减少存取记录的时间。一个物理记录是指计算机用一条I/O命令进行读写的基本数据单位。物理记录和逻辑记录的关系:一个物理记录存放一个逻辑记录;一个物理记录包含多个逻辑记录;多个物理记录表示一个逻辑记录。

  • 文件的操作(运算):文件的操作有两种,检索和修改。
    文件检索的三种方式

    1. 顺序存取
    2. 直接存取
    3. 按关键字存取
  • 文件的物理结构:顺序组织,随机组织和链组织。一个特定的文件应才用何种物理结构应综合考虑各种因素:存储介质的类型、记录的类型、大小和关键字的数目以及对文件作何种操作等。

顺序文件

顺序文件:顺序文件是记录按其在文件中的逻辑顺序依次进入存储介质而建立的,即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的

索引文件

索引文件:除了文件本身(称作数据区)之外,另建立一张指示逻辑记录和物理记录之间一一对应关系的表——索引表。这类包含文件数据区和索引表两大部分的文件称做索引文件。

ISAM文件和VSAM文件

索引顺序存取方法ISAM为 Indexed Sequential Access Methed 的缩写,它是一种专为磁盘存储设计的文件组织方式。由于磁盘是以盘组,柱面和磁道三级地址存取的设备,则可对磁盘上的数据文件建立盘组、煮面和磁道三级索引。

虚拟存储存取方法VSAM是Virtual Storage Access Method 的缩写。这种存取方法利用了操作系统的虚拟存储器的功能,给用户提供方便。

直接存取文件(散列文件)

直接存取文件指的是利用杂凑(Hash)法进行组织的文件。它类似于哈希表,即根据文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录散列到存储设备上,故又称散列文件。

多关键字文件

  • 多重表文件(Multilist File): 构造和修改都很容易,插入一个新纪录也很容易,但是删除一个记录很麻烦
  • 倒排文件:次关键字中存放有序的物理记录,优点是查询方便,缺点是维护困难。

nodejs学习文件操作

发表于 2017-11-10

引子

至诚之道可以前知。国家将兴,必有祯祥;国家将亡,必有妖孽。见乎蓍龟,动乎四体。祸福将至,善必先知之;不善,必先知之。故至诚如神。

–《中庸》

文件操作

两个例子

小文件拷贝

1
2
3
4
5
6
7
8
9
10
11
var fs = require('fs');

function copy(src, dst) {
fs.writeFileSync(dst, fs.readFileSync(src));
}

function main(argv) {
copy(argv[0], argv[1]);
}

main(process.argv.slice(2));

大文件拷贝

1
2
3
4
5
6
7
8
9
10
11
var fs = require('fs');

function copy(src, dst) {
fs.createReadStream(src).pipe(fs.createWriteStream(dst));
}

function main(argv) {
copy(argv[0], argv[1]);
}

main(process.argv.slice(2));

process是一个全局变量,可以通过process.argv获得命令行参数。argv[0]固定等于NodeJS执行程序的绝对路径,argv[1]固定等于主模块的绝对路径。

API

Buffer

js语言只有字符串数据类型,没有二进制数据类型,因此Nodejs提供了一个与String对等的全局构造函数Buffer来提供对二进制数据的操作。除了可以读取文件得到Buffer的实例外,还能够直接构造,例如:

1
var bin = new Buffer([ 0x68, 0x65, 0x6c, 0x6c, 0x6f ]);

Buffer实例与字符串类似,除了可以用.length属性得到字节长度外,还可以用[index]方式读取指定位置的字节,例如:

1
bin[0]; // => 0x68;

Buffer与字符串能够互相转化,例如可以使用指定编码将二进制数据转化为字符串:

1
var str = bin.toString('utf-8);

或者反过来,将字符串转换为指定编码下的二进制数据:

1
var bin = new Buffer('hello', 'utf-8'); // => <Buffer 68 65 6c 6c 6f>

Buffer与字符串有一个重要区别。字符串是只读的,并且对字符串的任何修改得到的都是一个新字符串,原字符串保持不变。至于Buffer,更像是可以做指针操作的C语言数组。例如,可以用[index]方式直接修改某个位置的字节。

1
bin[0] = 0x48

而.slice方法也不是返回一个新的Buffer,而更像是返回了指向原Buffer中间的某个位置的指针,如下所示。

1
2
3
4
[ 0x68, 0x65, 0x6c, 0x6c, 0x6f ]
^ ^
| |
bin bin.slice(2)

因此对.slice方法返回的Buffer的修改会作用于原Buffer,例如:

1
2
3
4
5
var bin = new Buffer([0x68, 0x65, 0x6c, 0x6f]);
var sub = bin.slice(2);

sub[0] = 0x65;
console.log(bin); // => <Buffer 68 65 65 6c 6f>

也因此,如果想要拷贝一份Buffer,得首先创建一个新的Buffer,并通过.copy方法把原Buffer中的数据复制过去。以下是一个例子。

1
2
3
4
5
6
var bin = new Buffer([0x68, 0x65, 0x6c, 0x6c, 0x6c]);
var dup = new Buffer(bing.length)
bin.copy(dup)
dup[0] = 0x48;
console.log(bin); // => <Buffer 68 65 6c 6c 6f>
console.log(dup); // => <Buffer 48 65 65 6c 6f>

总之,Buffer将js的数据处理能力从字符串扩展到了任意二进制数据。

Stream

当内存中无法一次装下需要处理的数据时,或者一边读取一边处理更加高效时,我们就需要用到数据流。NodeJS中通过各种Stream来提供对数据流的操作。

以上面的大文件拷贝程序为例,我们可以为数据创建一个只读数据流,示例如下:

1
2
3
4
5
6
7
8
9
var rs = fs.createReadStream(pathname);

rs.on('data', function(chunk){
doSomeThing(chunk);
})

rs.on('end', function(){
cleanUp();
});

Stream基于事件机制工作,所有Stream的实例都继承于NodeJS提供的EventEmitter

上面代码中的data事件会源源不断地被触发,不管doSomething函数是否处理的过来。代码可以继续如下改造,以解决这个问题。

1
2
3
4
5
6
7
8
9
10
11
12
var rs = fs.createReadStream(src);

rs.on('data', function(chunk){
res.pause();
doSomething(chunk, function(){
res.resume();
})
});

rs.on('end', function(){
cleanUp();
})

以上代码给doSomething函数加上了回调,因此我们可以在处理数据前暂停数据读取,并在处理数据后继续读取数据。

此外,我们也可以为数据目标创建一个只写数据流,示例如下:

1
2
3
4
5
6
7
8
9
10
var rs = fs.createReadStream(src);
var ws = fs.createWriteStream(dst);

rs.on('data', function(chunk){
ws.write(chunk);
});

rs.on('end', function(){
ws.end();
})

我们把doSomething换成了往只写数据流里写入数据后,以上代码看起来就像是一个文件拷贝程序了。但是以上代码存在上面提到的问题,如果写入速度跟不上读取速度的话,只写数据流内部的缓存会爆仓。我们可以根据.write方法的返回值来判断传入的数据是写入目标了,还是临时放在了缓存,并根据drain事件来判断什么时候只写数据流已经将缓存中的数据写入目标,可以传入下一个待写数据了。因此代码可以改造如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var rs = fs.createReadStream(src);
var ws = fs.createWriteStream(dst);
rs.on('data', function(chunk){
if(ws.write(chunk) === false){
rs.pause()
}
});

rs.on('end', function(){
ws.end();
})

ws.on('drain', function(){
res.resume();
});

以上代码实现了数据从只读数据流到只写数据流的搬运,并包括了防爆仓控制。因为这种使用场景很多,例如上边的大文件拷贝程序,NodeJS直接提供了.pipe方法来做这件事,其内部实现的方式与上面的代码类似

File System

NodeJS通过fs内置模块提供对文件的操作。fs模块提供的API基本上可以分为以下三类:

  • 文件属性读写:fs.stat、fs.chmod、fs.chown等
  • 文件内容读写: fs.readFile、fs.readdir、fs.writeFile、fs.mkdir等等
  • 底层文件操作:fs.open、fs.read、fs.write、fs.close等等

NodeJS最精华的异步IO模型在fs模块里有着充分的体现,例如上边提到的这些API都通过回调函数传递结果。以fs.readFile为例:

1
2
3
4
5
6
7
fs.readFile(pathname, function(err, data){
if(err){
// Deal with error.
} else {
// Deal with data.
}
});

如上面代码所示,基本上所有的fs模块API的回调参数都有两个。第一个参数在有错误发生时等于异常对象,第二个参数始终用于返回API方法执行结果。
此外,fs模块的所有一步API都有对应的同步版本,用于无法使用异步操作时,或者同步操作更方便时的情况。同步API除了方法名的末尾多了一个Sync之外,异常对象与执行结果的传递方式也有相应变化。同样以fs.readFileSync为例:

1
2
3
4
5
6
try {
var data = fs.readFileSync(pathname);
// deal with data
} catch (err) {
// deal with error
}

fs模块提供的API很多,需要时自行查阅文档。

Path

操作文件时难免不与文件路径打交道。NodeJS提供了path内置模块来简化路径相关操作,并提升代码可读性。以下分别介绍几个常用的API。

  • path.normalize
    将传入路径转换为标准路径,具体讲的话,出了解析路径中的.与..外,还能去掉多余的斜杠。如果有程序需要使用路径作某些数据的索引,但又允许用户随意输入路径时,就需要使用该方法保证路径的唯一性。以下是一个例子:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    var path = require('path')
    var cache = {}

    function store(key, value){
    cache[path.normalize(key)] = value
    }

    store('foo/bar', 1)
    store('foo//baz//../bar', 2)
    console.log(cache)

    标准化之后的路径里的斜杠在Windows系统下是\,而在linux系统下是/。如果想保证任何系统夏使用/作为路径分隔符的话,需要用.replace(/\\/g, '/') 再替换一下标准路径。

  • path.join
    将传入的多个路径拼接为标准路径。该方法可避免手工拼接字符串的繁琐,并且能在不同系统下正确使用相应的路径分隔符。以下是一个例子:

    1
    path.join('foo/', 'baz/', '../bar'); // => 'foo/bar'
  • path.extname
    当我们需要根据不同文件扩展明做不同的工作时,该方法就显得很好用。以下是一个例子:

    1
    path.extname('foo/bar.js'); // => '.js'

    其余方法请参考官方文档

遍历目录

遍历目录是操作文件时的一个常见需求。比如写了一个程序,需要找到并处理指定目录下的所有js文件时,就需要遍历挣个目录。

递归算法

遍历目录时一般使用递归算法,否则就难以写出简洁的编码。递归算法与数学归纳法类似。通过不断缩小问题的规模来解决问题。例:

1
2
3
4
5
6
7
function factorial(n){
if(n === 1){
return 1
} else {
return n * factorial(n-1)
}
}

上面的函数用于计算N的阶乘。可以看到,当N大于1时,问题简化为计算N乘以N-1的阶乘。当N等于1时,问题达到最小规模,不需要再简化,因此直接返回1。

陷阱:使用递归算法编写的代码虽然简洁,但由于每递归一次就产生一次函数调用,在需要优先考虑性能时,需要把递归算法转换为循环算法,以减少函数调用次数。
遍历算法

目录是一个树状结构,在遍历时一般使用深度优先+先序遍历算法。

nodejs学习基础内容

发表于 2017-11-02

引子

其次致曲。曲能有诚。诚则形。形则著。著则明。明则动。动则变。变则化。唯天下至诚为能化。

–《中庸》

正文

Nodejs基础

运行在nodejs环境中的js作用:操作磁盘文件,搭建http服务,Nodejs提供了fs,http等内置对象

安装,运行,权限问题略

模块

require

require函数用于在当前模块中加载和使用别的模块,传入一个模块名,返回一个模块导出对象。模块名可以使用相对路径和绝对路径。另外,模块名中的.js扩展名可以省略。另外,还可以加载和使用一个JSON文件。

exports

exports对象是当前模块的导出对象,用于导出模块公有方法和属性。别的模块通过require函数使用当前模块时得到的就是当前模块的exports对象(只可以在exports对象上添加属性,不能对它直接赋值,赋值不生效)

module

module对象可以访问到当前模块的一些相关信息,但主要用途是替换当前模块的导出对象。

1
2
3
module.exports = function () {
console.log('Hello World!');
};

模块初始化

一个模块中的js代码仅在模块第一次被使用时执行一次,并在执行过程中初始化模块的导出对象。之后,缓存起来的到处对象被重复利用。

主模块

通过命令行参数传给Nodejs以启动程序的模块被称为主模块。

二进制模块

Nodejs支持使用二进制模块。编译好的二进制模块文件扩展名为.node,使用方法同js模块一致。

代码的组织和部署

模块路径解析规则

require函数支持相对路径和绝对路径。但这两种路径在模块之间建立了强耦合关系,位置变换会变得很麻烦。所以,require函数支持第三种形式的路径,写法类似于foo/bar,并以此按照以下规则解析路径,直到找到模块位置。

  1. 内置模块,如require('fs')
  2. node_modules目录:nodejs定义了一个特殊的node_modules文件夹
  3. NODE_PATH 环境变量:与PATH环境变量类似,NODE_PATH环境变量中包含一到多个目录路径,路径之间在linux下用:分割,在windows下使用;分离。
    例如:
    1
    NODE\_PATH = /home/user/lib:/home/lib

使用require(‘foo/bar’)的方式加载模块时,则NodeJS尝试以下路径。

1
2
/home/user/lib/foo/bar
/home/lib/foo/bar

包(package)

复杂的模块往往由多个子模块组成。为了便于管理和使用,我们可以把多个子模块组成的大模块称为包,并把所有子模块放在同一个目录里。

在组成一个包的所有子模块中,需要有一个入口模块,入口模块的导出对象被称作包的导出对象。例如有以下目录结构。

1
2
3
4
5
- /home/user/lib/
- cat/
head.js
body.js
main.js

其中cat目录定义了一个包,其中包含三个子模块。main.js作为入口模块,其内容如下:

1
2
3
4
5
6
7
8
9
10
var head = require('./head');
var body = require('./body');

exports.create = function(name){
return {
name: name,
head: head.create(),
body: body.create()
}
}

在其他模块里使用包的时候,需要加载包的入口模块。接着上例,使用require('/home/user/lib/cat/main')能达到目的,但是入口模块名称出现在路径里看上去不是个好主意。因此我们需要做点额外的工作,让包使用起来更像是单个模块。

index.js

当模块的文件名是index.js,加载模块时,可以使用模块所在目录的路径代替模块的文件路径,因此接着上例,以下两条语句等价。

1
2
var cat = require('/home/user/lib/cat');
var cat = require('/home/user/lib/cat/index');

这样处理后,就只需要把包目录路径传递给require函数,感觉上整个目录被当作单个模块使用,更有整体感。

package.json

如果想自定义入口模块的文件名和存放位置,就需要在包目录下包含一个package.json文件,并在其中指定入口模块的路径。上例中的cat模块可以重构出来。

1
2
3
4
5
6
7
8
9
- /home/user/lib/
- cat/
+ doc/
- lib/
head.js
body.js
main.js
+ tests/
package.json

其中package.json内容如下

1
2
3
4
{
"name": "cat",
"main": "./lib/main.js"
}

如此一来,就同样可以使用require('/home/user/lib/cat')的方式加载模块。NodeJS会根据包目录下的package.json找到入口模块的位置。

命令行程序

使用Nodejs编写的东西,要么是一个包,要么是一个命令行程序,而前者最终也会用于开发后者。因此我们在部署代码的时候需要一些技巧,让用户觉得自己是在使用一个命令行程序。

例如我们用NodeJS写了个程序,可以把命令行参数原样打印出来。该程序很简单,在主模块内实现了所有功能。并且写好后,我们把程序部署在/home/user/bin/node-echo.js这个位置。为了在任何目录下都能运行该程序,我们需要使用以下终端命令。

1
2
$ node /home/user/bin/node-echo.js Hello World
Hello World

这种方式看起来不怎么像我们使用的命令行程序,下面才是我们期望的方式。

1
$ node-echo Hello World

linux

  1. shell脚本中可以通过 #! 注释来制定当前脚本使用的解析器。

    1
    #! /usr/bin/env node
  2. 然后赋予node-echo.js文件执行权限。

    1
    $ chmod +x /home/user/bin/node-echo.js
  3. 然后在PATH环境变量指定的某个目录下,例如在/usr/local/bin下边创建一个软链文件,文件名与我们希望使用的终端命令同名,命令如下

    1
    $ sudo ln -s /home/user/bin/node-echo.js /usr/local/bin/node-echo

windows

假设node-echo.js存放在C:\Users\user\bin目录,并且该目录已经添加到PATH环境变量里了。接下来需要在该目录下新建一个名为node-echo.cmd的文件,文件内容如下:

1
@node "C:\User\user\bin\node-echo.js" %*

这样处理后,我们就可以在任何目录下使用node-echo命令了。

工程目录

以编写命令行程序为例,一般我们会同时提供命令行模式和api模式两种使用方式,并且我们会借助第三方包来编写代码。除了代码外,一个完整的程序也应该有自己的文档和测试用例。因此,一个标准的工程目录都看起来像下面这样。

1
2
3
4
5
6
7
8
9
10
11
- /home/user/workspace/node-echo/   # 工程目录
- bin/ # 存放命令行相关代码
node-echo
+ doc/ # 存放文档
- lib/ # 存放API相关代码
echo.js
- node_modules/ # 存放三方包
+ argv/
+ tests/ # 存放测试用例
package.json # 元数据文件
README.md # 说明文件

NPM

略

小结

  • 编写代码前先规划好目录结构,才能做到有条不紊。
  • 稍大点的程序可以将代码拆分为多个模块管理,更大些的程序可以使用包来组织模块
  • 合理使用node_modules和NODE_PATH来解耦包的使用方式和物理路径
  • 使用NPM加入Nodejs生态圈互通有无
  • 先到了心仪的报名时请提前在npm上抢注

货币银行学06

发表于 2017-10-31

引子

唯天下至诚为能尽其性。能尽其性,则能尽人之性。能尽人之性,则能尽物之性。能尽物之性,则可以赞天地之化育。可以赞天地之化育,则可以与天地参矣。

– 《中庸》

银行监管的基本内容

商业银行面临的主要风险

对银行监管的目的

  • 维护银行业的稳定
  • 维护存款人利益
  • 加强对货币政策的控制
  • 加强政府对资金流向的引导

商业银行的主要风险

头寸(position)也称为“头衬”就是款项的意思,是金融界及商业界的流行用语。头寸指投资者拥有或借用的资金数量。头寸是一种市场约定,承诺买卖合约的最初部位,买进合约者是多头,处于盼涨部位;卖出合约者为空头,处于盼跌部位。

  1. 信用风险
  2. 国家风险
  3. 市场风险
  4. 利率风险
  5. 流动性风险
  6. 操作风险

银行监管的基本内容

  1. 对商业银行的设立和变更事项的审批
  2. 银行营运过程中的监管:资本充足率要求,流动性要求,资产质量监管,对银行内部控制制度监管,风险集中和风险暴露的监管
  3. 对有问题银行的处理

一些被‘放松’的监管内容

  1. 对商业银行从事证券业务的限制
  2. 对商业银行设置分支机构的限制
  3. 对利率的限制

《巴塞尔协议》

协议内容:银行资本同加权风险资产的比率必须达到8%,核心资本同加权风险的比率不得低于4%

资本的构成与限制
核心资本

  • 股本
  • 公开储备
  • 子银行公司中少数股东权益
    附属资本
  • 未公开储备
  • 资产重估储备
  • 普通准备金
  • 混合资本工具
  • 长期从属债务

eslint规则详解

发表于 2017-10-30

js语法解析探索

发表于 2017-10-29

引子

自诚明,谓之性;自明诚,谓之教。诚则明矣,明则诚矣。

–《中庸》

大纲

现在流行的es6 甚至 es7等特性的写法,通常并不被浏览器所认识,那么就需要一定的parser(转换器)将其转换为浏览器兼容性更好的的es5深知es3。

一种很自然而然的想法是将es6或者es7语法下写成的js代码解析为语法树,让后对应生成相应es5(es3)的代码。

eslint等语法检查就是基于这个原理做的

另外,很多操作,比如压缩,模块化等都需要解析原来的代码,从而进行相应的操作。还有,js并没有反射机制,如果要获取变量名本身字符串,还是需要解析源代码。

解析js最开始是 esprima

还有 acorn

由于eslint用的是espree,所以我们探索的大纲是:esprima –> acorn –> espree

esprima

esprima,bsd协议,是使用ECMAscript编写的高可用,符合标准的转换器,由Ariya Hidayat同其它贡献者共同完成。

特性:

  • 对 ECMAScript 2017 完全支持(ecma-262)
  • 由ESTree project标准化的语法树模式
  • 对jsx实验性的支持,React的语法扩展
  • 可选的语法节点位置的记录(序号和行列)
  • 已经被严格的测试(1500左右的标准测试)

API:

暂时不表,有点多,因为非常底层

1…345…7

乱世天狼

乱世天狼 | 前端 | html | css | html5 | css3 | react | redux | webpack | 哲学 | 精神 | 生活

67 日志
48 标签
© 2020 乱世天狼
由 Hexo 强力驱动
|
主题 — NexT.Muse v5.1.4