Python类

Share

ython类

iter（迭代器）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class test:
    def __init__(self, data):
        self.__data = data

    def __iter__(self):
        return iter(self.__data)


a = test([1, 2, 3])

for i in a:
    print(i)

运行结果为
1
2
3

contains

contains 方法可以判断子串是否在原字符串中

1
2
3
4
5
6
7
8
9
10
11
12
	接上例代码
    def __contains__(self, n):
    	if n in self.__data:
            return True
        else:
            return False

b = test([4,5,6])
print('4' in b)

运行结果
True

图

Share

图

顶点（vertex)

边（edge）

简单实现： 邻接矩阵实现

1
2
3
4
5
6
7
8
0 # 1 2 3 4 5 6		第一行 第一列代表节点
###############
1 # 0 1 0 0 1 0		如果 表中值为1则代表这两
2 # 1 0 1 1 1 1 	个顶点通路
3 # 0 0 1 0 1 0		2 --> 1 代表顶点1 到    
4 # 0 1 0 1 0 1		顶点2通路
5 # 1 0 1 0 1 0
6 # 1 1 0 1 0 1

更高效的实现方法是：邻接列表

维护一个包含所有顶点的主列表

1
2
3
4
5
6
7
8
[
v0,  -------->  {V1:5,v5:2}
v1,  -------->  {v2:4}
v2,  -------->  {v3:2}
v3,  -------->  {v4:7}
v4,  -------->  
v5   -------->
]# 主列表

广度优先算法Breadth First Search（BFS）

类似与一层一层的遍历

先选择一条路径，走到最深处，若不匹配就回溯知道有另一条路径，知道找到匹配的值

所以bfs

需要三个特有属性

  1. 顶点回溯
  2. 顶点标记（如为走过： 白色 走过： 黑色 当前顶点：红色）

图的应用

寻路、词阶。

六大常用排序算法

Share

六大常用排序算法

1
2
3
4
5
6
7
8
9
排序方法       时间复杂度            空间复杂度      稳定性    代码复杂度
         最坏情况 平均情况  最好情况
冒泡排序   O(N^2)  O(N^2)   O(N)       0(1)       稳定         简单
直接排序   O(N^2)  O(N^2)   O(N^2)     O(1)       不稳定       简单
直接插入   O(N^2)  O(nlogn) O(nlogn)   0(1)       稳定        简单
快速排序   O(N^2)  O(nlogn) O(nlogn) 平均O(logn)  不稳定       较复杂
                                    最坏情况O(n)
堆排序    O(nlogn) O(nlogn) O(nlogn)   O(1)      不稳定        复杂
归并排序  O(nlogn) O(nlogn) O(nlogn)   O(n)       稳定        较复杂

较高级排序算法

希尔排序（shell）

时间复杂度：最坏：O(N^2) 平均：O(N)~O(N^2)

  • 首先去一个整数d1 = n/2,将数据以d1为间隔分组，之后每组进行一次插入排序
  • 取第二个整数d2= d1/2, 重复上述步骤
  • 直至d 的值变为1 ，即完成排序

也可以按{5，3，1}进行增量排序

希尔排序每趟并不是使某些元素有序，而是使整体数据越来越趋近与有序

计数排序

时间复杂度：O(N)

  • 先创建一个范围表例如 [0，n]推荐用字典

  • 设数据都在范围标内，然后然后遍历数据,对每一数据进行计数

  • 最后根据计数创建出排列的好的序列

缺点：对于精度高的数据，消耗的空间多

桶排序（基于计数排序）

时间复杂度：平均：O(n+k) 最坏 O(n^2*k) 空间复杂度：O(nk) 其中k = logmlogn m为桶的容量

将元素分在不同的桶内，再对桶中的元素进行排序

  • 但是对桶内的数据可以以冒泡排序
基数排序

时间复杂度 ： O(nk) 空间复杂度 O(n+K)

  • 若有一整数数列
  • 先按个位排序，再按十位排序

按这个思路发散，即是基数排序

c语言选择语句&循环语句

Share

选择语句

if else分支

1
2
3
4
5
6
7
8
9
10
11
int main()
{
    int input = 0;
    scanf("%d",&input);
    if (input==1)  //选择语句
        printf("ok! input==1");
    else
        printf("input!=1");
    return 0;
}

循环语句

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main()
{
    int line = 0;
    while(line<30000)
    { //不满足一直循环
        printf("keep working!\n");
        line++;
    }
    if  (line ==30000) //满足条件就执行
    {
        printf("good!\n");
    }
    return 0;
}

C语言字符串

Share

字符串

一串字符 由英文双引号“”包含的内容

字符串结束标志为’\0’

数组储存

1
char arr[] = "abc"; // 数组储存

转义字符

转变字符原来的意思

1
2
3
4
5
int main()
{
	printf("c:\tww\tera"); // 转义字符 \t
	return 0;
}

变量作用域与生命周期

Share

作用域

限定变量的使用范围

1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>
int main()
{
    int a = 10;
    {
        int a = 11 ; \\作用域在{}内
    }
    printf("%d",a);
    return 0
}

生命周期

变量：从创建到销毁的时间段

局部变量：进入局部范围开始，出局部范围结束f

全局变量：从程序开始到程序结束

extern

使用同一工程下的变量

C语言 scanf函数

Share

C语言 scanf函数

录入用户通过键盘输入的数据

vscode方言

建议

scanf 可能会不安全，使用scanf_s代替

或者宏定义

#define _CRT_SECURE_NO_WARNINGS 1

1
2
3
4
5
6
7
8
9
10
11
int main()
{
	int a = 0;
	int b = 0;
	int sum = 0;
	scanf("%d %d",&a,&b);
	sum = a + b;
	printf("sum = %d\n",sum);
	return 0;
}