C基础知识.doc
《C基础知识.doc》由会员分享，可在线阅读，更多相关《C基础知识.doc（18页珍藏版）》请在冰点文库上搜索。
ACM入门进阶
程序设计语言是学习数据结构的一个重要组成部分，任何算法只有通过程序设计语言实现之后才能真正解决问题。
C++语言凭借其高度的灵活性和强大的功能在大学生竞赛中被非常广泛地使用，在中学生竞赛中的使用也越来越广泛。
本文旨在给初学者一个窗口，通过例题了解什么是ACM，希望能够对刚入门的读者有所帮助（题目是英文的，不用担心，很简单得英文，不懂可以查金山词霸～～）
ACM一般要求在一定的时间内，理解并分析题意，设计符合给定时间和空间复杂度要求的算法，并在计算机上使用一定的程序设计语言正确地实现算法。
由于整个竞赛存在时间限制（特别是ACM/ICPC类竞赛，在解决问题数目相等的情况下以做题累计时间的多少来决定名次），因此所使用的程序设计语言能否正确、快速地实现算法对竞赛的成绩影响颇大。
一般信息学竞赛比较常用的程序设计语言有以下几种：
BASIC、Pascal、C/C++、Java，它们的特点如下表所示：
BASIC
Pascal
C++
Java
学习难度
容易
一般
较难
较难
语言特点
简单
严谨
灵活
高度面向对象
程序运行速度
慢
较快
快
慢
库函数功能
弱
一般
很强
强
在目前的ACM竞赛中，C++和C语言使用较为广泛。
但是C++语言凭借其本身所具有的高度的灵活性，以及它所带的库的强大功能，被越来越多的选手所使用。
本文几乎所有内容都是例子，详细的见一些相关的参考书。
一C++基础知识
1.1 "Hello, world!
"
C++对于大小写是敏感的。
首先，让我们通过一个非常简单的C++程序，来初步地了解C++语言。
#include
using namespace std;//注意如果不使用.h将要增加本行
int main（）
{
cout << "Hello, world!
" << endl;return0;
} ///:
~
这个程序的作用就是在屏幕上输出“Hello,world!
”的字样。
以“#”开始的内容被称为预处理指令，这一行的作用是把一个叫做iostream的头文件包含到我们的程序中来。
C++默认是不包含任何头文件的。
另外，C语言中的头文件都是以.h结尾的，而标准的C++提倡使用没有扩展名的头文件。
第四行让我们可以在程序中直接使用std名字空间内的标识符。
std名字空间包含了所有标准C++提供的类和函数，为了简便起见，一般总在包含头文件的预处理命令后写上这一行。
如果是C语言的话，程序将变成：
#include
int main（）
{
printf（“%s\n”,"Hello, world!
"）;
return0;
} ///:
~
1.2类型
C++提供了基本类型以及程序员可以自定义的类型：
名称
C++类型
范围
大小
布尔型
bool
true/false
1
字符型
char
所有单字节字符
1
8位有符号整型
char
-128..127
1
8位无符号整型
unsignedchar
0..255
1
16位有符号整型
short
-32768..32767
2
16位无符号整型
unsignedshort
0..65535
2
32位有符号整型
int
-2147483648..2147483647
4
32位无符号整型
unsignedint
0..4294967295
4
64位有符号整型
longlong
-263..263-1
8
64位无符号整型
unsignedlonglong
0..264-1
8
单精度浮点型
float
1.17e-38..3.40e38
4
双精度浮点型
double
2.22e-308..1.79e308
8
扩展浮点型
longdouble
3.36e-4932..1.18e4932
10/12
在C++中，很多其他类型的量都可以隐式地转化为布尔型，这时，非零的值都被转化成true，而零被转化成false。
其中VC中没有longlong类型，可用_int64代替，sizeof的作用就是返回括号里的类型的大小（也可以是变量或者常量）。
单个字符的常数要用单引号括起来，一些不能显示的字符可以通过转义符来表示（参见下表）。
另外，从上表中可以看出，在C++中，字符型和单字节的整型实际上是等价的。
举例来说，'A'的数值就是65。
名称
ASCII名称
C++名称
换行
NL（LF）
\n
水平制表符
HT
\t
竖直制表符
VT
\v
退格
BS
\b
回车
CR
\r
复位
FF
\f
铃声
BEL
\a
反斜杠
\
\\
问号
?
\?
1.3操作符
首先，我们来看下表：
操作符名称
C++操作符
加法
+
减法
-
乘法
*
整数除法
/
实数除法
/
取余数
%
小于
<
小于等于
<=
大于
>
大于等于
>=
相等
==
不等
!
=
位非
~
逻辑非
!
位与
&
逻辑与
&&
位或
|
逻辑或
||
位异或
^
位左移
<<
位右移
>>
从中可以看出，C++语言最大的特点就是几乎所有的操作符都是由符号字符构成的。
注意：
1、C++中，整数除法和实数除法都是由“/”来完成的，当两个操作数都是整数时进行整数除法，当至少有一个是实数时进行实数除法；
2、C++中，位运算与逻辑运算的操作符是不同的。
1.4常用的库函数和格式输出
标准C++提供了十分强大的库。
在这一节，我们只介绍一些和Pascal所提供的标准过程和函数功能相似的库函数。
函数定义
头文件
作用
备注
void*memset（void*p,intb,size_tn）;
cstring
把p所指向的连续n个字节的值都设置成b
与FillChar类似，但要注意参数的顺序
void*memmove（void*p,const*q,size_tn）;
cstring
把q所指向的连续n个字节的值复制到p所指向的位置
与Move类似，p、q所指向的内存区域可以部分重叠
doubleatof（constchar*p）;
intatoi（constchar*p）;
longatol（constchar*p）;
cstdlib
把字符串p转化成所表示的数
与Val类似
doublefabs（double）;
cmath
绝对值函数
与Abs类似
doubleceil（double）;
doublefloor（double）;
cmath
取整函数，前者为上取整，后者为下取整
doublesqrt（double）;
cmath
平方根函数
与Sqrt类似
doublepow（doubled,doublee）;
cmath
幂函数，返回d的e次方
doublesin（double）;
doublecos（double）;
doubletan（double）;
cmath
三角函数
doubleasin（double）;
doubleacos（double）;
doubleatan（double）;
cmath
反三角函数
doubleatan2（doubley,doublex）;
cmath
增强型反正切函数，返回点（x,y）的辐角
很有用，会根据点所在的象限调整弧度值
doublesinh（double）;
doublecosh（double）;
doubletanh（double）;
cmath
双曲函数
doubleexp（double）;
cmath
指数函数，以e为底
与Exp类似
doublelog（double）;
doublelog10（double）;
cmath
对数函数，前者以e为底，后者以10为底
与Ln类似
另外，标准C++中并没有提供函数Pi，要获得Pi的值一般这样做：
constdoublepi=acos（0.）*2;
格式化输出
具体参考C＋＋语言等相关书籍
C++的流可以完成控制格式的操作。
指定场宽由成员函数width（）来完成，而指定小数部分的位数则稍微麻烦一些，要先把浮点数的输出方式设置为定点输出方式，然后再设置小数部分的位数。
例如：
cout.setf（ios:
:
fixed,ios:
:
floatfield）;
cout.precision
（2）;
cout<<1.2345<以上程序段中第一个语句的作用就是把浮点数的输出方式设置为定点输出方式，第二个语句的作用是把小数部分的位数设置为2。
和Pascal一样，小数部分的最后一位也会进行四舍五入的处理。
需要注意的是，width（）只对接下来的一个格式化输出有效，如果有多个输出需要指定场宽，那么就要写多个width（）函数。
而precision（）则对之后所有的浮点数输出都有效。
例如：
cout.width（3）;
cout<<1<<2;//1的场宽为3，而2采用实际宽度
cout.width（4）;
cout<<2;
如果你觉得这样写太麻烦，你也可以把它写成：
cout<不过这时不要忘了在程序的最前面加上#include，因为setw是在iomanip中被定义的。
这样，我们就可以完成一般的格式化输出了。
C++中流的格式化输出还有很多内容，如果有兴趣可以参考有关资料。
1.5例子
要求：
每个程序在全部弄懂的前提下，自己编写一次（可以上网AC的都要尽量通过）
例1：
http:
//acm.timus.ru/problem.aspx?
space=1&num=1000A+BProblem
Calculatea+b
输入：
aandb
输出：
a+b
SampleInput
15
SampleOutput
6
程序：
C++：
#include
usingnamespacestd;
intmain（）
{
inta,b;
while（cin>>a>>b）
cout<}
//cin和cout是iostream里面的东西
C：
#include
intmain（）
{
inta,b;
while（scanf（"%d%d",&a,&b）!
=EOF）
printf（"%d\n",a+b）;
}
注意一般程序要求你多次输入的！
！
printf和scanf是stdio.h里面的东西，注意C语言里面没有类的存在，只有函数。
这两个函数要熟练使用的，慢慢来也行，具体见《C和C＋＋帮助》
例2：
1到n求和
输入：
n代表一个非负整数1=输出：
1到n求和
SampleInput
100
SampleOutput
5050
程序：
C：
#include
intn,sum;
intmain（）
{
while（scanf（"%d",&n）!
=EOF）
{
sum=n*（n+1）/2;
printf（"%d",sum）;
}
return0;
}
C＋＋：
#include
usingnamespacestd;
intn,sum;
intmain（）
{
while（cin>>n）
{
sum=n*（n+1）/2;
cout< }
return0;
}
例3：
判断一个数是不是素数1SampleInput
100
31
SampleOutput
NO
YES
程序：
#include
#include
usingnamespacestd;
booltf（intn）
{
inti;
for（i=2;i if（n%i==0）returnfalse;
returntrue;
}
intmain（）
{
intn;
while（cin>>n）
{
if（tf（n））
cout<<"YES"< else
cout<<"NO"< }
return0;
}
例4求两个数的最大公约数和最小公倍数
SampleInput
1218
SampleOutput
636
程序：
#include
#include
usingnamespacestd;
intgcd（intn,intm）//求最大公约数的递归函数
{
if（m==0）returnn;
elsereturngcd（m,n%m）;
}
intmain（）
{
intn,m,g;
while（cin>>n>>m）
{
g=gcd（n,m）;
cout< }
return0;
}
例5排序
输入：
n个整数的序列1=输出：
排好序的序列
SampleInput
5
15324
SampleOutput
12345
程序一（顺序排序）：
#include
usingnamespacestd;
intn,a[10001];
voidsxpx（int*a）//顺序排序函数
{
inti,j,temp;
for（i=1;i<=n;i++）
for（j=i+1;j<=n;j++）
if（a[i]>a[j]）
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
intmain（）
{
while（cin>>n）
{
inti;
for（i=1;i<=n;i++）cin>>a[i];
sxpx（a）;
cout<for（i=2;i<=n;i++）cout<<''<cout< }
return0;
}
程序二（快速排序）：
必懂算法
#include
inta[10000];
intn;
voidquicksort（ints,intt）//总的思想就是第s个节点派到它最后应该排的位置；
{
inti,j,x,t1;
i=s;j=t;x=a[i];
while（i {
while（（a[j]>=x）&&（j>i））j=j-1;
if（j>i）{t1=a[i];a[i]=a[j];a[j]=t1;}
while（（a[i]<=x）&&（i if（i }
a[i]=x;
i=i+1;j=j-1;
if（s if（i}
intmain（）
{
while（EOF!
=scanf（"%d",&n））//也可是这样写：
－>while（EOF!
=0）
{{
for（intp=0;p scanf（"%d",&a[p]）;for（intp=0;p quicksort（0,n-1）;scanf（"%d",&a[p]）;
for（p=0;p printf（"%d",a[p]）;for（p=0;p }printf（"%d",a[p]）;
return0;}
}
比较以上两种排序的方法，哪个比较快呢？
快速排序比较难理解，可以分两步理解：
1：
开数据结构的书，看懂手工是怎么操作的
2：
自己写一组数据，单步跟踪一下，看看数据怎么变化的。
初学时，单步跟踪很重要！
！
！
！
！
！
如果上面蓝色的字体你都做到了，好了，恭喜～！
！
你已经具有自学的能力了，加油加油，以后很多算法只要做这两个工作就行了，再加上一些相关的习题训练就可以灵活运用算法了，再进一步就是成为大牛～～说远了，加油～～
这里插入STL的使用，可以使用系统的排序函数（具体参考相关STL的资料）：
#include
#include
#include
usingnamespacestd;
intn;
intmain（）
{
while（cin>>n）
{
inti,x;
vectora;//a是一个容器
for（i=1;i<=n;i++）
{
cin>>x;
a.push_back（x）;//往容器中塞东西
}
sort（a.begin（）,a.end（））;
cout<for（i=1;icout< }
return0;
}
例6：
级数求和
[问题描述]:
已知：
Sn=1＋1／2＋1／3＋…＋1／n。
显然对于任意一个整数K，当n足够大的时候，Sn大于K。
现给出一个整数K（1<=k<=15），要求计算出一个最小的n；使得Sn＞K。
[输入文件]
输入有多组测试数据，每组一行，一个数k
[输出文件]
输出有多组数据，每组一行，一个数n。
[输入样例]
1
[输出样例]
2
程序：
#include
usingnamespacestd;
intmain（）
{
intk;
while（cin>>k）
{
doubles=1.0;
intn=1;
while（s<=k）
{
n++;
s+=1.0/n;
}
cout< }
return0;
}
建议C和C＋＋语言两个版本都自己编写提交
例7：
IPAddress
简单的说就是8个0或1为一个数，要你转化为十进制数（但是要注意格式）
Supposeyouarereadingbytestreamsfromanydevice,representingIPaddresses.Yourtaskistoconverta32characterslongsequenceof'1s'and'0s'（bits）toadotteddecimalformat.AdotteddecimalformatforanIPaddressisformbygrouping8bitsatatimeandconvertingthebinaryrepresentationtodecimalrepresentation.Any8bitsisavalidpartofanIPaddress.Toconvertbinarynumberstodecimalnumbersrememberthatbotharepositionalnumericalsystems,wherethefirst8positionsofthebinarysystemsare:
27
26
25
24
23
22
21
20
128
64
32
16
8
4
2
1
Input
TheinputwillhaveanumberN（1<=N<=9）initsfirstlinerepresentingthenumberofstreamstoconvert.Nlineswillfollow.
Output
TheoutputmusthaveNlineswithadoteddecimalIPaddress.AdotteddecimalIPaddressisformedbygrouping8bitatthetimeandconvertingthebinaryrepresentationtodecimalrepresentation.
SampleInput
4
00000000000000000000000000000000
00000011100000001111111111111111
11001011100001001110010110000000
01010000000100000000000000000001
SampleOutput
0.0.0.0
3.128.255.255
203.132.
升级会员 