CSP-J 大纲
2024-10-26 19:20:43
发布于：北京
一、字符串
1、字符串属于一个类，可以看成一个struct（结构体）。
2、字符串的本质是一个字符数组，末尾是\0。
C:
#include<stdio.h>
int main(){
char s[100]; //定义一个长度为99的字符数组
scanf("%s",&s); //scanf()函数输入
return 0;
}
C++:
#include<iostream> //输入输出流
#include<cstring> //C风格头文件
using namespace std;
int main(){
string s;
getline(cin,s); //行输入
return 0;
}
二、编码
1、编码主要分机器码和格雷码。
2、机器码是计算机存储一个具体数据的编码方式。
3、格雷码的特点是：两个相邻的二进制位，只有一位不同。
机器码
1、机器码分原码，反码，补码。
2、计算机所有的信息由补码存储。
3、机器码之间的转换方式：
（1）~ 原码 = 反码；
（2）反码 + 1 = 补码；
格雷码
1、格雷码，又叫二进制循环码，或反射二进制码。
格雷码转二进制机器码
1、格雷码的最高位作为二进制的最高位。
2、二进制的其余位为格雷码对应位与二进制上一位相异或。
二进制机器码转格雷码
二进制的最高位作为格雷码的最高位。
2、格雷码的其余位为二进制码对应位与上一位相异或。
三、网络
网络的定义
计算机网络利用通信线路和设备，技术与计算机技术相结合的产物。把分布在不同地理位置上的计算机连接起来，是现代通信技术与计算机技术相结合的产物。
网络的主要功能
1、资源共享：诞生之初，就是为了共享。
2、信息传输：信息共享，本质上就是信息传输。
3、分布式处理：广义上的网络终端，互相独立。
网络的分类
1、按网络的地理范围分类
（1）局域网（LAN）：≤1000m
（2）城域网（MAN）：>1000m,<100000m
（3）广域网（WAN）：全球
2、按网络的拓扑结构分类
网址
Internet 上的计算机地址，有两种表示形式：IP 地址和域名。
1、表达形式有 IPV4 和 IPV6 两类，IPV4 网络使用 32 位地址，IPV6 网络使用 128 位地址，目前常见的是 IPV4 。
（IPV4）例如：43.137.14.18
（IPV6）例如：CDCD:910A:2222:5498:8475:1111:3900:2020
HTML 语言
全称为超文本语言，是一种标记语言，包括一些列标签，通过这些标签可以将网络上的文档格式统一，使分散的 Internet 资源连接为一个逻辑整体。HTML 文本是由 HTML 命令组成的描述文件，HTML 命令可以说明文字，图像，动画，声音，表格，链接等。
四、进制转换
将各个数制之间进行转换，逢几进一就是几进制。
二进制：0 1
八进制：0 1 2 3 4 5 6 7
十进制：0 1 2 3 4 5 6 7 8 9
十六进制：0 1 2 3 4 5 6 7 8 9 A B C D E F
十进制转 n 进制（n<=16）
#include<iostream>
using namespace std;
char i2c[]="0123456789ABCDEF";
char num[100];
int nl=0;
int main(){
int n;
cin>>n;
int f=2; // 目标进制 // 以 f 为基数的数位分离
while(n!=0){
num[++nl]=i2c[n%f]; // 以字符数组形式存储
n/=f;
}
// 逆序输出十进制 n 在 f 进制下的形式
for(int i=nl;i>=1;i--){
cout<<num[i];
}
cout << endl;
return 0;
}
n 进制转十进制
#include<bits/stdc++.h>
using namespace stda;
char i2c[]="0123456789ABCDEF";
int c2i[300];
int main(){
for(int i='0';i<='9';i++) c2i[i]=(i-'0');
for(int i='A';i<='F';i++) c2i[i]=(i-'A')+10;
string s;
cin>>s;
int len=s.size();
long long ans=0; // 累加器
long long f=16; // 目标进制
long long q=1;
for(int i=len-1;i>=0;i--){
ans+=c2i[(int)s[i]]*q;
q*=f;
}
cout<<ans<<endl;
return 0;
}
五、十大排序
排序的概念
在一个数组中，使无序的序列变得有序，这个过程叫排序。
排序的种类
1、基础 O(n²)：冒泡排序、选择排序、插入排序；
2、突破 <O(n²)：希尔排序；
3、桶排序 O(n+k)：桶排序、计数排序、基数排序；
4、进阶 O(nlog(n))：快速排序、归并排序、堆排序；
六、图论
图的概念
图是顶点与边的集合，记为 G(V, E) 。
V 表示顶点集合，E 表示边的集合。
从定义上讲，V 不可以为空，E 可以为空。
根据边的类型不同，可以分为无向图和有向图。
度的定义
一个顶点的邻接边的数量，或邻接顶点的数量，称为该顶点的度。
无向图
图中，边 (A,C) 可以双向通行，且只需通过一条边则称此边为邻接边，称A和C互为临界点；这种可以双向通行的图，称其为无向图。
有向图
边 <A, C> 称为一条有向边，或单向边，书面以尖括号表示。这条边也被称为 弧尾 A 点指向 弧头 C 点的弧。该边指向顶点 C，被称为顶点 C 的入边，<C, D> 是出边。一个顶点的入边数量，被称为入度，出边数量被称为出度。
完全图
1、无向完全图
无向完全图指在一个无向图内，任意两点之间都有一条邻接边的图。任意n个点之间组成的无向完全图是唯一的，其的边的数量为n*(n-1)/2。
2、有向完全图
有向完全图指在一个有向图内，任意两点之间都有两条互为重边的邻接边的图。任意n点之间组成的有向完全图也是唯一的其的边的数量为n*(n-1)。
稀疏图与稠密图
稀疏图：点多边少
稠密图：边多点少
带权图
一个图的边，若有值，称此值为这条边的权值。
自环与重边
自环：自己连自己的一条边。
重边：两个邻接点之间不止一条邻接边。
自环与重边，往往对最短路的计算会有影响。一张图若不存在自环与重边，则称为简单图，否则被称为多重图。
七、二分查找与二分答案
全部评论 35
有几个点需要注意下：机器码之间的转换方式，
! 原码 = 反码的表示不对。这里不是单纯的结果上的取反，而是按位取反。应该写成~原码 = 反码。的形式。2024-08-18 来自 浙江
2
有帮助，赞一个