首页
关于
Search
1
图神经网络
44 阅读
2
java期末速成
18 阅读
3
Attention2Transformer
17 阅读
4
CLIP
15 阅读
5
MySQL
15 阅读
默认分类
AI
课内
技能
Search
标签搜索
AI
CS
Tools
paper
DeepLearning
python
DATA
GNN
Transformer
晨旭不想写程序
累计撰写
16
篇文章
累计收到
2
条评论
首页
栏目
默认分类
AI
课内
技能
页面
关于
搜索到
4
篇与
的结果
2024-06-02
fast git
Gitgit命令获取git仓库git init将当前目录转换为Git仓库该命令将创建一个名为 .git 的子目录,这个子目录含有你初始化的 Git 仓库中所有的必须文件,这些文件是 Git 仓库的骨干。 但是,在这个时候,我们仅仅是做了一个初始化的操作,你的项目里的文件还没有被跟踪。git clone当你执行 git clone 命令的时候,默认配置下远程 Git 仓库中的每一个文件的每一个版本都将被拉取下来。$ git clone 克隆仓库指令 (指定名称)文件状态工作目录里的文件无非就是两种状态:已跟踪与未跟踪状态,已跟踪的文件是指那些被纳入了版本控制的文件,在上一次快照中有它们的记录,在工作一段时间后, 它们的状态可能是未修改,已修改或已放入暂存区。简而言之,已跟踪的文件就是 Git 已经知道的文件。当我们初次克隆某仓库的时候,仓库中的所有文件都是已跟踪文件未修改状态,仓库中的文件一旦发生修改,状态将更改为已修改,在工作时,我们可以将已修改文件放入暂存区,状态更改为暂存,然后我们可以一次性提交所有已经暂存的修改。上图就是文件的生命周期图。git status查看文件状态,状态信息中包含所在的分支以及当前所在分支与远程仓库中对应的分支是否存在偏离 如果文件发生了改变,则在下面则会出现Untracked files的列表,提醒我们没有追踪的文件git add使用命令 git add 开始跟踪一个文件。只要在 Changes to be committed 这行下面的,就说明是已暂存状态。 如果此时提交,那么该文件在你运行 git add 时的版本将被留存在后续的历史记录中。 你可能会想起之前我们使用 git init 后就运行了 git add 命令,开始跟踪当前目录下的文件。 git add 命令使用文件或目录的路径作为参数;如果参数是目录的路径,该命令将递归地跟踪该目录下的所有文件。git add是一个多功能的命令,可以使用他对已修改文件进行暂存如若在暂存后再次修改了该文件,则该文件会同时出现在暂存与未暂存区域,这时我们直接提交提交的是第一次暂存的版本,如若要使用当前的版本需要再次add后再提交将这个命令理解为“精确地将内容添加到下一次提交中”git ignore一般我们总会有些文件无需纳入 Git 的管理,也不希望它们总出现在未跟踪文件列表。 通常都是些自动生成的文件,比如日志文件,或者编译过程中创建的临时文件等。 在这种情况下,我们可以创建一个名为 .gitignore 的文件,列出要忽略的文件的模式。范例: # 忽略所有的 .a 文件 *.a # 但跟踪所有的 lib.a,即便你在前面忽略了 .a 文件 !lib.a # 只忽略当前目录下的 TODO 文件,而不忽略 subdir/TODO /TODO # 忽略任何目录下名为 build 的文件夹 build/ # 忽略 doc/notes.txt,但不忽略 doc/server/arch.txt doc/*.txt # 忽略 doc/ 目录及其所有子目录下的 .pdf 文件 doc/**/*.pdfgit diff此命令比较的是工作目录中当前文件和暂存区域快照之间的差异。 也就是修改之后还没有暂存起来的变化内容。若要查看已暂存的将要添加到下次提交里的内容,可以用 git diff --staged 命令。 这条命令将比对已暂存文件与最后一次提交的文件差异请注意,git diff 本身只显示尚未暂存的改动git commit提交命令,执行后会启动你选择的文本编辑器来输入提交说明。Note 启动的编辑器是通过 Shell 的环境变量 EDITOR 指定的,一般为 vim 或 emacs。 当然也可以按照 起步 介绍的方式, 使用 git config --global core.editor 命令设置你喜欢的编辑器。默认的提交消息包含最后一次运行 git status 的输出,放在注释行里,另外开头还有一个空行,供你输入提交说明。 你完全可以去掉这些注释行,不过留着也没关系,多少能帮你回想起这次更新的内容有哪些。另外,你也可以在 commit 命令后添加 -m 选项,将提交信息与命令放在同一行提交后它会告诉你,当前是在哪个分支(master)提交的,本次提交的完整 SHA-1 校验和是什么(463dc4f),以及在本次提交中,有多少文件修订过,多少行添加和删改过。每一次运行提交操作,都是对你项目作一次快照,以后可以回到这个状态,或者进行比较。git commit 加上 -a 选项,Git 就会自动把所有已经跟踪过的文件暂存起来一并提交,从而跳过 git add 步骤git rmgit rm --cached README可以将指定文件从暂存区中移除,但是不会从本地删除,如果本地删除只需要直接 git rm-f即可,这是一种安全特性,用于防止误删尚未添加到快照的数据,这样的数据不能被 Git 恢复。git mvgit mv 被改文件名 文件名相当于执行三句$ mv README.md README $ git rm README.md $ git add README 如此分开操作,Git 也会意识到这是一次重命名,所以不管何种方式结果都一样。 两者唯一的区别在于,git mv 是一条命令而非三条命令,直接使用 git mv 方便得多。 不过在使用其他工具重命名文件时,记得在提交前 git rm 删除旧文件名,再 git add 添加新文件名。git log查看提交历史git log 有许多选项可以帮助你搜寻你所要找的提交, 下面我们会介绍几个最常用的选项。其中一个比较有用的选项是 -p 或 --patch ,它会显示每次提交所引入的差异(按 补丁 的格式输出)。 你也可以限制显示的日志条目数量,例如使用 -2 选项来只显示最近的两次提交,该选项除了显示基本信息之外,还附带了每次提交的变化。 当进行代码审查,或者快速浏览某个搭档的提交所带来的变化的时候,这个参数就非常有用了。 你也可以为 git log 附带一系列的总结性选项。 比如你想看到每次提交的简略统计信息,可以使用 --stat 选项,另一个非常有用的选项是 --pretty=。 这个选项可以使用不同于默认格式的方式展示提交历史。 这个选项有一些内建的子选项供你使用。 比如 oneline 会将每个提交放在一行显示,在浏览大量的提交时非常有用。 另外还有 short,full 和 fuller 选项,它们展示信息的格式基本一致,但是详尽程度不一。当 oneline 或 format 与另一个 log 选项 --graph 结合使用时尤其有用。 这个选项添加了一些 ASCII 字符串来形象地展示你的分支、合并历史:$ git log --pretty=format:"%h %s" --graph * 2d3acf9 ignore errors from SIGCHLD on trap * 5e3ee11 Merge branch 'master' of git://github.com/dustin/grit |\ | * 420eac9 Added a method for getting the current branch. * | 30e367c timeout code and tests * | 5a09431 add timeout protection to grit * | e1193f8 support for heads with slashes in them |/ * d6016bc require time for xmlschema * 11d191e Merge branch 'defunkt' into local总结Table 2. git log 的常用选项 选项 说明 -p 按补丁格式显示每个提交引入的差异。 --stat 显示每次提交的文件修改统计信息。 --shortstat 只显示 --stat 中最后的行数修改添加移除统计。 --name-only 仅在提交信息后显示已修改的文件清单。 --name-status 显示新增、修改、删除的文件清单。 --abbrev-commit 仅显示 SHA-1 校验和所有 40 个字符中的前几个字符。 --relative-date 使用较短的相对时间而不是完整格式显示日期(比如“2 weeks ago”)。 --graph 在日志旁以 ASCII 图形显示分支与合并历史。 --pretty 使用其他格式显示历史提交信息。可用的选项包括 oneline、short、full、fuller 和 format(用来定义自己的格式)。 --oneline --pretty=oneline --abbrev-commit 合用的简写。撤销操作git commit --amend这个命令可能用在我们提交信息错误或者有文件忘记提交时进行使用我们使用这个命令就可以再次进行提交,此时我们这次提交会将上次提交的基础上再次进行提交并且将修改信息加到本次提交上,也就是将提交补全,补全后之前提交将不再存在git reset xxxgit reset命令可以取消对某文件的暂存git checkout撤销修改,将文件退回为之前的样子请务必记得 git checkout -- 是一个危险的命令。 你对那个文件在本地的任何修改都会消失——Git 会用最近提交的版本覆盖掉它。 除非你确实清楚不想要对那个文件的本地修改了,否则请不要使用这个命令。在 Git 中任何 已提交 的东西几乎总是可以恢复的。 甚至那些被删除的分支中的提交或使用 --amend 选项覆盖的提交也可以恢复 (阅读 数据恢复 了解数据恢复)。 然而,任何你未提交的东西丢失后很可能再也找不到了。远程操作git remote add运行 git remote add 添加一个新的远程 Git 仓库,同时指定一个方便使用的简写git remote add jx xxxxxxxxgit fetch这个命令会访问远程仓库,从中拉取所有你还没有的数据。 执行完成后,你将会拥有那个远程仓库中所有分支的引用,可以随时合并或查看git pushgit push 分支 服务器将本地分支内容推送到上游,当你的本地版本并不是最新时,这条命令将不起作用git remote rename改远程仓库名git remote remove删除远程仓库
2024年06月02日
5 阅读
0 评论
0 点赞
2024-06-02
threading多线程
threading在处理多并发问题时,我们通常使用多线程进行处理,Python 实现多线程编程需要借助于 threading 模块基本使用threading 模块中最核心的内容是 Thread 这个类每个对象都代表一个线程,平时我们直接运行的部分就是主线程Thread 的构造方法中,最重要的参数是 target我们使用target将线程的目标指定出来(一个函数)要让一个 Thread 对象启动,调用它的 start() 方法就可以了thread = threading.Thread(target=test,name='name') thread.start()threading.active_count表示目前已经运行了多少个线程threading.enumerate运行的线程有哪些threading.current_thread表示当前运行的线程是哪个join功能在start之后,在某处插入了.join(),则从此处开始至子线程中止都阻塞主线程,执行完当前任务后再继续进行主线程的任务Queue功能我们的线程无法得到返回值所以我们要使用的话我们就要先定义出一个队列def job(data,q): for i in range(len(data)): data[i] = data[i]**2 q.put(l) def multithreading(data): q = Queue() threads = [] data = [[1,2,3],[3,4,5],[4,4,4],[5,5,5]] for i in range(4): t = threading.Thread(target = job,args=(data[i],q)) t.start() threads.append(t) for thread in threads: thread.join() results = [] for _ in range(4): results.append(q.get())多线程的效率问题多线程的任务分配并不是平均分配使用GIL分配方式同一时间只有一个线程在进行,节省效率是因为读写可以与其他线程的运算同时进行LOCK锁的功能lock = threading.Lock() lock.acquire() |运行| lock.release()锁的意义就在于多个线程在对共享数据进行修改时,为了让数据同步做的锁定,让线程获得后进行即可详细查阅 http://www.runoob.com/python3/python3-multithreading.html
2024年06月02日
8 阅读
0 评论
0 点赞
2024-06-02
java期末速成
javajdk jre jvm.java-------->.class----jvm---->机器语言编写源文件 编译源文件生成字节码 加载运行字节码java语句执行顺序 顺序 选择 循环 异常处理基本语法方法格式权限修饰符 返回值声明 方法名称(参数列表){ 方法中封装的逻辑功能; return 返回值; }--权限修饰符--注释//单行注释 /* 多行注释 */ /** 文档注释 **/标识符举例java变量java是一个强类型语言 必须先声明类型后使用java数据类型分两大类 基本数据类型与引用类型引用数据类型:string 数组 接口 类按照声明位置进行定义分为局部变量与成员变量变量的类型转换boolean类型不参与转换自动类型转换容量小的类型自动转换成容量大的类型byte,short,int -> float -> long ->doublebyte short int之间不会互相转换 三者计算时会转化成int类型强制类型转换容量大的类型转换成容量小的类型时需要加上强制转换符变量的作用域在类体内定义的变量称为成员变量 作用域是整个类在一个方法或方法内代码块中定义的变量称为局部变量常量量前加一个final变量赋值注意事项:float a = 133f long a = 22220202l char c = '羊'数组数组初始化方式不允许在前面的[]里写元素个数动态两种int[][] arr = new int[3][]; arr[0] = new int[3] int [][] arr2 = new int[3][2] arr[0][0] = 33静态一种int arr4[][] = new int[][]{{1,2,3},{2,3,4}}arr.length 得到数组长度输入输出scanner类型#输入 Scanner s = new Scanner(System.in); s.nextInt(); s.nextLine(); s.nextfloat(); scanner.next(); #输出 System.out.println("XX");system.out. print() 普通输出 printf()格式化输出 println()换行输出类与对象封装继承多态我们进行一次举例public class Student { private String username; public String getUsername{ return username; } #这个函数存在而不使用直接赋值的意义就是因为username这个变量是私有的 public void setUsername(String username){ this.username = username; } } class Test { public static void main(String[] args) { Student student=new Student(); student.setUsername("张三"); student.getUsername(); System.out.println(); } }类的实例化通过new语句进行创建类的定义格式[修饰符] class 类名 [extends 父类名] [implements 接口名]{ //类体 包括类的成员变量与成员方法 }继承基类object没有选择继承的时候默认继承object,有很多自带方法继承格式public class Parent { private int age; public int getAge() { return age } public void setAge(int age) { this.age = age; } #有参 public Parent(int age){ this.age = age; } #无参 public Parent(){ } public void myprint(){ system.out.println("我是父类的myprint方法"); } } class Son extents Parent{ public static void main(String[]args) { Son son = new son(); son.age = 3; } }类的重写对相同的函数进行再次声明就可以进行重写类的封装将类的某些信息隐藏在内部,不允许直接访问而是提供get set方法public class Person { private intn age; private string name; public String getName(){ return name; } public int getAge(){ return age; } public void setName(String name){ this.name = name; } public void setAge(int age){ this.age = age; } }构造方法 重点构造方法定义主要用来创建对象时 初始化对象的 总与new一起使用在创建对象的运算符中 一个类可以有 多个构造函数 可根据参数个数不同或者参数类型不同区分 即构造函数的重载方法的重载重写重载重写区别this关键字在构造方法中指该构造器所创建的新对象也就是对应对象的属性也可以使用this关键字调出对象本身例如在一个对象的setAge中调用getAge注意:this只能在类的非静态方法中使用 静态方法与静态的代码块中不能出现this 原因 static方法在类加载时就已经存在了 但是对象在创建时才在内存中生成super关键字super关键字主要存在于子类方法中用于子类调用父类的方法例如子类重写了父类的一个方法 但是又想重新调用一次父类的方法就使用super关键字static关键字静态 的关键字静态变量静态方法静态代码块使用了static后的方法变成类方法 不需要new就能直接调用final关键字final修饰的类不能被继承final修饰的方法不能被重写 但是可以直接用final修饰的基本类型变量不可变 但是引用类型变量引用不可改变 但是引用对象的内容可以改变抽象类在class前加一个abstract来修饰抽象方法要在子类里进行实现 不然不正确接口将class替换为interface即可接口里所有定义的方法实际上都是抽象的public abstract变量只能为public static final类型的public abstract void add(); 等效于 void add();抽象类与接口的区别接口要被子类实现 抽象类要被子类继承接口中变量全为公共静态常量 抽象类中可有普通变量接口中全为方法的声明 抽象类中可以有方法的实现接口中不可以有构造函数 抽象类中可以有构造函数接口可多实现 而抽象类必须被单继承接口中方法全为抽象方法 而抽象类中可以有非抽象方法内存机制栈存放局部变量 不可以被多个线程共享系统自动分配空间连续 速度快堆存放对象 可以被多个线程共享每个对象都有锁空间不连续 速度慢 灵活方法区存放类的信息:代码 静态变量 字符串 常量等可以被多个线程共享空间不连续 速度慢 灵活垃圾回收机制程序员不能调用垃圾回收器 但是可以通过system.gc()建议回收未引用的会被回收finallize方法 每个对象都有这个方法 用来释放对象区域资源 一般不去调用递归算法递归头 什么时候不调用自己递归体 什么时候调用自己异常机制:try catch finally catch的顺序 先小后大声明抛出异常:throws手动抛出异常:throw自定义异常: 首先继承Exception 或者它的子类容器:Collection接口: List -》ArrayList LinkedList Vector Set-》HashSet 内部使用HashMap实现Map接口: 采用 key value存储数据 HashMap线程不安全 效率高 HashTable线程安全 效率低Iterator接口:遍历容器中元素泛型:Collections: 包含排序查找的工具类字符串比较中 == 与 equal的区别==:比较的是两个字符串内存地址(堆内存)的数值是否相等,属于数值比较;equals():比较的是两个字符串的内容,属于内容比较。多态多态体现为一个事物的多种形态 例如 父类引用变量可以指向子类对象isinstanceof 向上转型 将子类对象赋值给父类变量 向下转型 将父类对象赋值给子类变量注解也叫元数据 用于描述数据的数据基本注解:@Override 重写 在重写的方法前加入即可@SuppressWarnings 压制警告 在警告内容前加入 可以让我们暂时忽略特定的警告自定义注解[public] @interface 注解名 { 数据类型 成员变量名()[default 初始值] }注解跟类一样 会被编译为 注解名.class的字节码文件成员变量名后面的()必不可少反射机制一段程序在运行过程中 接受一个对象作为形参 该对象的编译时类型与运行时类型不一致 但是程序又需要调用该对象运行时的类中的方法这就需要引用反射机制 保证在程序运行过程中可以知道任意对象的运行时类型可以构造任意类的对象可以调用任意对象的属性和方法其实就是在运行时获取对象的属性与方法,例如对象.getClass内部类将一个类作为成员放在另一个类或者方法的内部嵌套类内部类可以分为 非静态内部类和静态内部类非静态内部类 是指 在非静态类的方法内访问某个变量时 先找局部变量 再找内部类的属性 最后找外部类的属性如果局部变量 内部类属性 外部类三者名字相同静态内部类是用static修饰的内部类都称为静态内部类静态内部类是一个普通类 可以包含静态成员 也可以包含非静态成员静态内部类不能访问外部类的实例成员 只能访问外部类的类成员lambda表达式当接口中只有一个抽象方法 匿名内部类的语法过于频繁这种接口叫做函数式接口表达式 : (形参列表)->{代码块}形参列表:如果形参列表中只有一个参数 形参列表的圆括号也可以忽略异常处理基本语法try{ 执行语句 }catch (ExceptionType e) { 异常处理 }finally{ 无论是否发生异常都会执行的语句 }创建Exception通过继承Exception来创建异常public class CustomException extends Exception{ public CustomException(String message){ super(message) } }throw/throws用于手动抛出异常 需要使用public void processAge(int age) { if (age < 0) { throw new IllegalArgumentException("Age cannot be negative"); } // 其他处理逻辑 }throwspublic String readFile(String fileName) throws IOException { // 读取文件内容的逻辑 }输入输出操作InputStreamInputStream是用于从各种源(如文件、网络连接等)读取字节流的抽象类。它定义了一系列用于读取字节的方法。你可以使用InputStream来读取二进制数据,比如图片、音频或视频文件。OutputStream是用于向各种目标(如文件、网络连接等)写入字节流的抽象类。它定义了一系列用于写入字节的方法。你可以使用OutputStream来写入二进制数据,比如将数据写入文件或通过网络发送。Reader是用于从各种源(如文件、网络连接等)读取字符流的抽象类。它定义了一系列用于读取字符的方法。你可以使用Reader来读取文本数据,比如读取文本文件中的内容。Writer是用于向各种目标(如文件、网络连接等)写入字符流的抽象类。它定义了一系列用于写入字符的方法。你可以使用Writer来写入文本数据,比如将数据写入文本文件。// 使用FileReader读取文件 FileReader fileReader = new FileReader("file.txt"); int data = fileReader.read(); // 读取一个字符 while (data != -1) { System.out.print((char)data); data = fileReader.read(); } fileReader.close(); // 使用FileWriter写入文件 FileWriter fileWriter = new FileWriter("file.txt"); fileWriter.write("Hello, world!"); fileWriter.close();System.in、System.out 和 System.errSystem.in、System.out和System.err是Java中的三个标准I/O流。System.in:标准输入流,通常对应于键盘输入。你可以使用它来从控制台读取用户的输入。System.out:标准输出流,通常对应于控制台输出。你可以使用它向控制台输出信息。System.err:标准错误流,也通常对应于控制台输出。与System.out不同的是,它主要用于输出错误信息。泛型java 中泛型标记符:E - Element (在集合中使用,因为集合中存放的是元素)T - Type(Java 类)K - Key(键)V - Value(值)N - Number(数值类型)? - 表示不确定的 java 类型Collection \<E>Collection 是 Java 集合框架中所有集合类的根接口。它代表了一组对象,这些对象通常称为元素。Collection 接口的主要特点包括:存储一组对象:Collection 是一个容器,可以存储多个对象,这些对象可以是任何类型,包括基本类型的封装类、自定义对象等。无序性:Collection 不保证元素的顺序,即它们不一定按照插入的顺序进行存储和访问。允许重复元素:Collection 允许存储重复的元素,即相同的对象可以被添加多次。常见实现类:Java 中常见的 Collection 实现类包括 List、Set 和 Queue 接口的各种实现类,如 ArrayList、LinkedList、HashSet 等。Map<K,V>Map 接口代表了一种映射关系,它将键映射到值。Map 中的键是唯一的,而值则可以重复。Map 接口的主要特点包括:键值对存储:Map 存储的是键值对,每个键都映射到一个值。通过键可以快速查找对应的值。键的唯一性:Map 中的键是唯一的,每个键最多只能与一个值关联。值的重复性:Map 中的值可以重复,即不同的键可以映射到相同的值。常见实现类:Java 中常见的 Map 实现类包括 HashMap、TreeMap、LinkedHashMap 等。
2024年06月02日
18 阅读
1 评论
0 点赞
2024-06-02
数据结构
树树的前中后序遍历前序遍历 根左右 每次左右可以展开时进行替换中序遍历 左根右后序遍历 左右根前中后序转化前中后序转化看遍历方式决定的顺序结构例如前序遍历的第一个元素一定是根节点 中序遍历的根节点的两边就是左右子树树与二叉树的转化树要变成二叉树,那就将树中的所有兄弟结点进行链接,然后每一层与上一层的连接只留下第一个结点的连接二叉树要变成树,那就反方向来一次,将除了第一个结点的其他结点与根节点连接上,然后将兄弟结点连接,这时候二叉树就变回了原来的树森林与二叉树的转化森林转化为二叉树,森林是由若干个树组成的,可以理解为森林中的每棵树都是兄弟,我们先把森林中的每棵树转化成二叉树,然后将从第二个树起的每个结点作为上一个结点的右孩子二叉树想转化成森林,先要看他可不可以转化,直接看根节点有没有右孩子,有就可以转化,先递归的将每个拥有右节点的根节点都断开 然后将二叉树再转化成树就成了森林树与森林的遍历树的遍历树的遍历很简单,分为先根遍历与后根遍历森林的遍历森林的遍历也分为两种,分别是前序遍历与后序遍历,森林的前序遍历与二叉树的中序遍历相同,森林的后序遍历与二叉树的中序遍历相同图图的表示邻接矩阵typedef struct { Vertextype vexs[MAXVEX]; EdgeType arc[MAXVEX][MAXVEX]; int numNodes, numEdges; }MGraph;邻接表int EdgeType; typedef struct { int adjvex; EdgeType info; struct EdgeNode *next; }EdgeNode; typedef struct { VertexType data; EdgeNode *firstedge; }VertexNode,AdjList[MAXVEX]; typedef struct { Adjlist adjList; int numNodes,numEdges; }AdjList;深度优先搜索深度优先搜索也叫DFS,这种搜索如其名,深度优先,在走之前先确定一个方向,比如先访问最左边的,那就持续往前走,在未遇到过的结点的路中选择最左边的即可//邻接矩阵 #define MAXVEX 9 Boolean visited[MAXVEX] void DFS(MGraph G,int i) { int j; visited[i] = True; printf("%c",G.vexs[i]) for(j = 0;j < MAXVEX;j++) { if(G.arc[i][j] == 1 && visited[i] == False) { DFS(G,j); } } } void DFSTraverse(MGraph G) { int i; for(i = 0;i < G.numvertexes;i++) { visited[i] = False; } for(i = 0;i < G.numvertexes;i++) { if(!visited(i)) { DFS(G,i); } } }//邻接表 void DFS(GraphAdjList GL,int i) { EdgeNode *p; visited[i] = True; printf("%c",GL->adjlist[i].data); p = GL->adjlist[i].firstedge; while(p) { if(!visted[p->adjvex]) { DFS(GL,p->adjvex); } p = p->next; } } void DFSTraverse(GraphAdjlist GL) { int i; for(i = 0;i < GL->numvexes;i++) { visited[i] = False; } for(i = 0;i < GL->numvexes;i++) { if(!visited[i]) { DFS(GL,i); } } }广度优先搜索广度优先搜索,也叫BFS核心思想是一层一层访问结点,使用的是一个栈来作为辅助存储,从入栈第一个节点开始,每次出栈一个结点,就将这个结点邻接的所有未访问顶点入栈,由此来遍历所有顶点void BFSTraverse(MGraph G) { int i; Queue Q; for(i = 0;i < G->numvexes;i++) { visited[i] = False; } InitQueue(Q); for(i = 0;i < G->numvexes;i++) { if(!visited[i]) { visited[i] = True; printf("%c",G->vex[i]) EnQueue(&Q,i); while(!EmptyQueue(Q)) { DeQueue(&Q,&i); for(j = 0;j < G->numvexes;j++) { if(G.arc[i][j]&&!visited[j]) { printf("%c",G->vex[j]); EnQueue(&Q,j); } } } } } }最小生成树prim算法简介prim算法的核心就是迭代,从一个顶点开始构建生成树,每次讲代价最小的新顶点纳入生成树,直到所有顶点都纳入为止。实现思想创建两个数组,一个是标记是否加入的数组isjoin,一个是计算各节点加入最小生成树的最低代价的数组lowcost 在此之前先选取第一个结点,对此结点的相邻边进行遍历,将有权边加入到lowcost中供选择 第一轮循环遍历各个结点,找出lowcost最低的并且未加入树的顶点,将相邻结点加入isjoin数组中并开启下一轮遍历,更新还未加入的各个顶点的lowcost值不断循环直至所有顶点都纳入为止因为要进行n-1轮的循环,每次循环2n次总时间复杂度是O($n^2$)即O($|V|^2$)kruskal算法简介kruskal算法的核心就是全局里去找,每次选择一条权值最小的边,使这条边的两头连通(若原本已经连通则不选)直到所有顶点都连通实现思想初始时先将各条边按照权值进行排序然后使用并查集方法检查是否已连通,若未连通则将新节点加入,一共要执行e轮,美伦判断两结点是否属于同一集合,需要O($log_2e$)最短路径BFS求无权图的单源最短路径简介直接进行广度优先遍历使用两个数组,一个记录最短路径值,一个记录到这个顶点的直接前驱只能用无权图迪杰斯特拉算法简介dijkstra算法是一种一步一步找出最短路径的方法,核心思路就是从初始点开始,一步一步从已确定路径中选取最短的路径作为新的最短路径,并加入新已确定顶点,然后执行多次实现我们选用三个数组,分别是标记各顶点是否已找到最短路径的finals,最短路径长度的dist,以及记录路径上的前驱的path也就是我们每次将可到达的结点找出来,从可获取路径中找到最短路径,并将其前驱记录,标记出结点时间复杂度为O($n^2$)即O($|V|^2$)如果用于负权值带权图,则迪杰斯特拉算法可能会失效弗洛伊德算法简介Floyd算法是求出每一对顶点之间的最短路径使用动态规划思想,将问题的求解分为多个阶段对于个顶点的图G,求任意一对顶点Vi一>Vj之间的最短路径可分为如下几个阶段:初始:不允许在其他顶点中转,最短路径是?0:若允许在Vo中转,最短路径是?1:若允许在Vo、V1中转,最短路径是?2:若允许在Vo、V1、V2中转,最短路径是?......n-1:若允许在Vo、V1、V2.Vn-1中转,最短路径是?例如这样,左边的矩阵就是初始时,不中转获得的个顶点建最短路径长度,右边的矩阵是初始时中转点的记录,因为不中转,所以是-1若允许在V0中转,则新加一编辑 如此经历n轮递推woc,大道至简,本身以为是只有一个节点做中转的情况,但是仔细一想,它并不是单源的算法,而是点到点的算法,并且也从来不是每次加一个这么简单,他是考虑了所有的结点 就好比是需要经过 0 2 4 6才能到这个点,在查找时0->2是最小值不需要中转,0->4是经过2的中转,0到6是经过4的中转,但是到4的中转前已经中转过2了,所以这种算法已经考虑了所有的情况DAG简介有向无环图简称DAG 图DAG描述表达式相同部分可以合并节省存储空间顶点中不能出现重复的操作数,标出来各个运算符的生效顺序,注意分层拓扑排序简介拓扑排序就是找到做事的先后顺序每个AOV网可能有一个或者多个拓扑排序实现①从AOV网中选择一个没有前驱(入度为0)的顶点并输出。②从网中删除该顶点和所有以它为起点的有向边。③重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。使用三个数组进行实现分别是 记录当前顶点入度的数组indegree 记录拓扑序列的数组print 保存度为零的顶点栈s逆拓扑排序将拓扑排序中的入度更换成出度即可,使用邻接表不适合实现逆拓扑排序,应该使用逆邻接表或者邻接矩阵查找查找的衡量方法为平均查找长度顺序查找基本思想是从线性表的一端开始,逐个检查关键字是否满足给定的条件。若查找到某个元素的关键字满足给定条件,则查找成功,返回该元素在线性表中的位置。若查找到表的另一端,仍未找到符合给定条件的元素,则返回查找失败的信息。折半查找基本思想就是二分法散列表基本概念散列函数可能会把两个或两个以上的不同关键字映射到同一地址,称这些情况为冲突,这些发生碰撞的不同关键字称为同义词。散列表建立了关键字和存储地址之间的一种直接映射关系。散列函数不同,散列表不同直接定址法就是直接使用线性函数确定地址,一般不常见除留余数法确定一个数m,所有的数对设定的数m进行取余,取余后进行散列表的排序解决冲突办法如果有重复则将其使用向后推移并记录查找次数的方法进行储存,成为开放定址法,也可使用链表进行存储,称为拉链法查找长度散列表的查找长度取决于三个因素:散列函数、处理冲突的方法和装填因子。装填因子a=表中记录数n/散列表长度m。散列表的平均查找长度依赖于散列表的装填因子α,不直接依赖于n或m。α越大,表示装填的记录越“满”,发生冲突的可能性就越大。排序插入排序直接排序实际上就是进行比较后一步步替换空间复杂度为O(1)时间复杂度为O($n^2$)-->两个嵌套for循环(平均)稳定性 稳定 (遇到相同数字,相对位置保持不变)每次向后移动一次即一趟排序希尔排序希尔排序是通过一个常数d作为增量,然后对于相隔d个增量的记录作为子表进行排序,经过几次排序,使得整个表格基本有序后,对全体进行一次排序即可因为同样使用常数个辅助单元,所以空间复杂度为o(1)时间复杂度依赖于增量d,一般来说是不确定的,所以一般我们不去考虑最后两个相同数字的相对位置也不能保证,所以稳定性也是不稳定的交换排序冒泡排序不做解释,一一交换空间 O(1)时间O($n^2$)快速排序快速排序是选取一个固定数,通常为第一个数,将小于这个数的跟不小于这个数的值进行排序,然后依次进行,是一个递归的过程所以空间复杂度是O($log_2n$)时1间复杂度是O($nlog_2n$)稳定性为不稳定快速排序是所有内部排序算法中平均性能最优的算法但是并不适用于本身就已经有了一定顺序的序列进行排序选择排序简单选择排序就是遍历每个元素,在遍历到第i个元素时,选择从i到n的所有元素中最小的一个,将其与第i个元素进行交换空间复杂度为O(1)时间复杂度为O($n^2$)稳定性为不稳定堆排序对于二叉树的排序结果,我们可以根据根节点存放的是最大结点还是最小结点将堆分为大根堆与小根堆对于大根堆小根堆的构造,都是从$n/2$开始进行的对于堆的删除操作,就是将栈顶元素输出后再次进行构造对于堆的插入操作,我们将其放入栈尾,再次进行构造空间复杂度O(1)时间复杂度O($nlog_2n$)稳定性 不稳定归并排序归并排序是将两个或两个以上的有序表组成一个新的有序表例如二路归并排序,就是将元素两两组合并进行排序空间复杂度是O(n)时间复杂度是O($nlog_2n$)稳定性 为稳定基数排序不基于比较与移动进行排序,而是基于关键字各位的大小进行排序空间效率 O(r)时间复杂度O(d(n+r))稳定性 稳定各种排序算法的比较插帽龟跟统计鸡是很稳定的插帽龟在选冒插的时候,恩慌了恩老说快归堆问题树的度为树中最大的度,例如二叉树的度为2树中的指针域,看图理解即可含有n个结点的树含有n+1个空链域,n-1个非空链域,可以从画图理解,从第一个结点为2个空域,每增加一个结点,空域增加一个前后缀表达式前缀表达式首先先看,前缀表达式是从后往前算,遇到数字一个个放入栈中,遇到符号则拿出栈顶的元素进行计算,后进先算后缀表达式先入先出,从前往后进行计算,也就是通过队列进行实现二叉搜索树(BST,Binary Search Tree),也称二叉排序树或二叉查找树。二叉搜索树:一棵二叉树,可以为空;如果不为空,满足以下性质:非空左子树的所有键值小于其根结点的键值。非空右子树的所有键值大于其根结点的键值。左、右子树都是二叉搜索树。二叉链表用二叉链表存储哈夫曼树,有m个叶子结点,问哈夫曼树中总共多少个空指针域:2m,叶子节点数*2数据的物理存储结构主要包括链式存储与顺序存储二叉排序树插入新节点时间复杂度为O(n),因为最差情况为单链以链表为栈的存储结构出栈时以链表为栈的存储结构出栈时必须判空,不需要判定满栈顺序线性表插入脑残数据的最小单位是数据项归并排序落单丢掉substr(str,int,int)意思是str的第int开始的int个字符层次遍历初始堆无法保证得到一个有序的序列,因为堆的兄弟结点之间无序创建邻接表的时间复杂度无向图中有n个结点e条边,建立该图邻接表的平均时间复杂度为O(n+e)深度为k的完全二叉树中最少有$2^{k-1}$个结点如上一趟排序结束后不一定能选出一个元素在其最终位置上的排序算法希尔排序,可能没有元素在最终位置上连通图是无向图连通图一定是无向图,所以深度优先遍历连通图一定能够访问到所有的顶点链式栈的栈顶元素删除删除栈顶元素操作序列 top = top->next初始化堆筛选法建初始堆必须从第$\frac{n}{2}$个元素开始进行筛选,因为第$\frac{n}{2}$个元素都有孩子结点(对于所有的完全二叉树来讲都是这样)新建元素x = (类型)malloc(sizeof(元素))
2024年06月02日
12 阅读
0 评论
0 点赞