仅适用于有一定基础的读者

2025/1/5 XPIPI

第一章 Java概述

1.Java的语言特性：面向对象、平台无关性、多线程、垃圾自动回收机制、安全性

2.Java源文件拓展名为.java，通过编译指令javac后可得到扩展名为.class的字节码文件，字节码可通过运行指令java运行

3.用java命令运行程序不需要添加字节码文件拓展名.class

4.javadoc命令用于生成文档，javap命令用于反汇编，jar命令用于打包Java字节码文件，jdb为命令行式的调试工具

5.使用package来创建一个包

6.使用import来导入一个包，默认已导入java.lang包

第二章 Java语法基础

1.文档注释 / ... / 与多行注释 / / 区分

2.对象实例化时，若成员变量没有显式赋值，则取值为对应数据类型的默认值；若数组没有显式赋值，各元素都取默认值

3.引用数据类型的默认值为null

4.将浮点型转换为整型时，小数点后数据将被截掉，精度下降

5.不推荐用包装类的构造方法创建包装类对象，一般用包装类的valueOf()方法

6.用parseXxx(String s)将字符串转为基本类型，用valueOf(Xxx x)将基本数据类型转化为字符串

7.instanceof为二元运算符，判断左边是不是右边的类型

8.若精度不同，==运算结果也为false

9.&&和||会发生短路现象，&和|不会

10.使用带标签的break语句，应当再break所在循环的外层循环之前定义

11.abstract和final修饰符不能同时使用

12.方法重载的名字一定相同，参数列表一定不同，其它随意

13.多维数组声明并初始化的三种方式

int a[][]=new int[][]{{1,1,1},{2,2,2},{3,3,3}};
int a[][]={{1, 1, 1}, {2, 2, 2}, {3, 3, 3}}
{
    int[][] a = new int[3][3];
    a[0] = new int[]{1, 1, 1};
    a[1] = new int[]{2, 2, 2};
    a[2] = new int[]{3, 3, 3};
}

14.foreach只能遍历访问，不能修改也不能局部访问

第三章 面向对象基础

1.一般来说，成员变量和属性是一个意思，实例与对象是一个意思，创建对象和实例化对象是一个意思

2.类体中不能对成员变量进行操作，只能在代码块中进行操作

3.栈内存和堆内存 类的对象在堆中分配空间

4.既可以用类.Xxx也可以用对象.Xxx来访问类变量

5.类都至少有一个构造方法

6.在程序块中，变量遵循就近原则，即同名的局部变量可以屏蔽外部的成员变量

7.this()调用构造方法时必须放在第一行

8.访问权限：private<default<protected<public

9.类不能用private和protected修饰

10.调用System.gc()方法和Runtime.getRuntime.gc()来强制进行垃圾回收

11.finalize()方法由垃圾回收器调用，不要主动调用

12.Runtime类是一个单例类，通过getRuntime方法来获得这个对象

13.运行顺序：静态块->构造块->构造方法

14.构造块在每次调用构造方法时前都会运行一次

15.没有任何前缀后缀修饰只由大括号{}括起来的就是构造快

第四章 面向对象高级技术

1.Java采用类的单继承可多重继承，接口可以同时多实现

2.方法重写的方法名、参数列表、返回值必须一模一样，而且子类重写的方法访问权限必须大于等于父类

3.方法重写和方法重载是实现多态的重要形式。

4.super调用父类的构造方法也要放在第一句

5.所有类直接或间接继承java.lang.Object类，因此都有toString,equals,hashCode,clone,notify,notifyAll,wait等方法

6.final修饰的类不能被继承

7.一般用static final来修饰常量

8.局部变量声明后必须显式初始化

9.wait,notify,notifyAll,getClass()方法是final修饰的，不能被重写

10.向下转型转换后引用对象可以访问子类成员，而向上转型转换后引用对象不能访问不是重写的子类成员

具体原因点我可看

11.向下转型时，必须确保运行时类型确实是子类对象，否则会抛出 ClassCastException

因此，为了避免产生异常，可以使用instanceof运算符进行目标类型的判断

12.抽象类的子类如果是普通类，必须实现所有抽象类的抽象方法

13.抽象类可以含有属性、方法、构造方法、程序块等

14.抽象类可以没有抽象方法，也可以有非抽象方法

15.接口可以使用extends继承一个或者多个接口，但是不能继承类

16.接口中变量都是常量，必须显式初始化

17.接口中方法都是public abstract修饰

18.如果一个接口中只有一个抽象方法，这个接口称作函数式接口，在lambda表达式中可以用到

19.接口中可以有默认方法，用default修饰

20.如果一个类同时实现接口A和B，接口A和B中有相同的default方法，这时，该类必须重写接口中的default方法

21.如果子类继承父类，父类中有b方法，该子类同时实现的接口中也有b方法（被default修饰），那么子类会继承父类的b方法而不是继承接口中的b方法

22.接口中也可以有静态方法，用static修饰

23.一个类可以同时实现多个接口；一个类只能继承一个类，但是能实现多个接口；一个接口可继承多个接口。

24.充分利用接口可以降低程序各个模块之间的耦合度，提高系统的可拓展性和可维护性

25.内部类可以用static修饰为静态内部类，但是内部类的成员不能声明为static类型

26.内部类名不能与外部类同名

27.

实例化静态内部类对象的模板是： 外部类类名.内部类类名 xxx = new 外部类类名.内部类类名()

实例化非静态内部类对象的模板是：外部类类名.内部类类名 xxx = 外部类对象名.new 内部类类名()

OuterStaticClassName.InnerStaticClassName objectName = new OuterStaticClassName.InnerStaticClassName();
OuterClassName.InnerClassName objectName = new OuterClassName().new InnerClassName();

28.局部内部类定义在方法内，作用域在方法里

29.局部内部类不能使用访问控制修饰符，也不能用static修饰

30.匿名内部类因为没有类名，所以不能复用，不能实例化

第五章 Java API

1.String的subString方法取的是左闭右开的区间，StringBuffer的delete方法也是

2.StringBuffer支持多线程，也是线程安全的

3.StringBuffer的默认缓冲区容量为16个字符

4.StringBuilder线程不安全，但是支持链式操作

5.拼接字符串效率：StringBuilder > StringBuffer > String

6.toString方法在没有重写时默认是返回 getClass().getName() + "@" +Integer.toHexString(hashCode());

7.String类重写了toString 方法

public String toString()  return this

8.String类重写了equals和hashCode方法，但是StringBuffer类和StringBuilder没有重写，equals方法仍然是比较两个对象的地址是否相等

9.StringBuffer类和StringBuilder类用于字符串追加、插入、删除、反转等操作，且其内容可以改变，且字符串拼接的效率明显比String类高

10.java.util.StringTokenizer类用于分割字符串

11.时间与日期相关的三个重要的类：Date、Calendar、DateFormat

12.Date类返回的时间是以毫秒ms为单位的

13.Calendar.DAY_OF_WEEK返回星期几

14.规定的标准时间格式：

日期：yyyy-MM-dd;

时间：HH:mm:ss;

带毫秒的时间：HH:mm:ss.SSS;

日期和时间：yyyy-MM-dd'T'HH:mm:ss; 日期与时间之间用'T'隔开

带毫秒的日期和时间：yyyy-MM-dd'T'HH:mm:ss.SSS

15.Local系列的类(LocalDateTime LocalDate LocalTime)都有parse方法用于进行将字符串转为相应的日期和时间类型

16.Instant.now()从系统时钟获得当前瞬时

17.Duration类和Period都是计算一个时间段，不同的是Duration类基于时间值，而Period类基于日期类，都使用以下方法创建：

Duration duration = Duration.between(time1,time2);

Period period = Period.between(time1.toLocalDate(),time2.toLocalDate());

18.DateFormat是一个抽象类，SimpleDateFormat是其实现类

19.通过SimpleDateFormat的format方法将一个Date对象转化为一个相应格式的字符串，回转用parse方法

20.Math.random()方法生成一个(0.0,1.0)的随机数

21.Random类在构建随机数生成器时可以自定义一个种子，也可以通过无参数来随机一个随机数种子

22.Random类的nextInt方法如果无参数则返回一个任意范围的整数，如果有参数X则返回一个[0,X]的整数

23.基本数据类型都有其对应的包装类

24.将十进制转化为二进制可以用包装类的toBinartString(int i)方法，转化其它进制同理

25.包装类才可以使用泛型，而基本数据类型不可以

26.基本数据类型比包装类占用的内存空间更小，是一种轻量级的

27.在小数点需要保留指定位数时，建议用参数类型为String的构造方法构造BigDecimal对象

28.System类代表当前Java程序的运行平台，Runtime类表示当前JVM的工作信息

29.System的类变量中：out和err属于PrintStream类型，in属于InputStream类型

30.另外，InputStream提供了read方法接受字节数据，因此可以用System.in.read()来读取单个字符

31.打开一个计算器可以用Runtime类的exec方法，记得要捕获异常

32.用Pattern类对正则表达式进行编译，用Matcher类在给定Pattern实例的模式控制下进行字符串的匹配工作

33.String也提供了matches方法，可以使用正则表达式进行匹配

34.Java集合由两个根接口派生：单列结构Collection和双列结构Map

35.List和Set是Collection其中两个应用最为广泛的子接口，List元素有序且可重复，Set元素无序且不能重复

36.集合遍历的方式有以下五种。

基本循环如for/while循环：这种方式功能上最为强大，遍历时也可以修改、删除元素。

Iterator:比较简便的遍历方式，遍历时可以删除元素。

ListIterator:Iterator的子接口，专门用于List集合的遍历，支持双向遍历。

Enumeration:遍历Properties等双列集合的方式，遍历时不能修改、删除元素。

foreach:遍历方式上最为简便，同时功能上也最弱，遍历时不能修改、删除元素。

除了基本循环之外，其他方式遍历时，不可以通过集合对象的方法操作集合中的元素，因为会发生ConcurrentModificationException异常。Iterator提供的方法是有限的，只能对元素进行判断、取出、删除的操作，如果想要其他的操作如添加、修改等，就需要使用其子接口ListIterator。该接口只能通过List集合的listIterator方法获取。Enumeration和foreach方式功能上更为单一，遍历时不能修改、删除元素。

37.ArrayList效率没有数组高，但是可以动态改变大小，可以很方便添加删除修改元素

38.从集合中取出元素进行强制转换可能带来隐患，所以一般使用泛型，例如：

ArrayList<String> list = new ArrayList<String>();

39.TreeSet类在实现Set接口的同时，也实现了SortedSet接口，保证元素为升序

40.HashSet类在使用自定义类的时候，必须重写hashCode和equals方法

41.TreeSet本质上是一个自平衡二叉搜索树，即红黑树的实现 操作元素的时间复杂度为O(logN)

42.基本数据类型对应的包装类，String类都实现了Comparable接口，因此添加到TreeSet中可以按照自然排序的方式进行排序

43.添加其它引用类型的元素，必须实现Comparable接口，重写CompareTo方法，否则TreeSet无法排序，产生ClassCastException异常

44.Map中Key和Value都可以是null，但是Key一定是唯一的

45.Map接口的方法中

keySet 返回包含所有键值的Set集合

values返回Map中所有值组成的Collection集合

entrySet返回所有键值对组成的Set集合

46.HashMap类似于HashTable，但他是不同步的

47.SortedMap接口也有一个实现类TreeMap，对所有的键值对按照键进行排序，同时也需要实现Comparable接口

48.Properties类称为属性列表，继承于Hashtable类

49.泛型方法的类型参数可以用来声明返回值的类型，注意类型参数只能代表引用型类型，不能是基本数据类型

50.Lambda表达式中，一个参数可以不用圆括号，代码只有一个语句可以不用大括号，但是箭头一定有

51.Lambda表达式在很多场合下可以代替匿名内部类

第六章 异常处理机制

1.Throwable类是异常顶层父类，两个直接子类Error类和Exception类

2.Exception类分为运行时异常和编译时异常，编译时异常必须手动处理

3.getMessage方法可以返回异常对象的详细信息，toString方法可以返回异常对象的简短描述，printStackTrace方法将异常及其追踪输出至标准错误流

4.try-catch-finally语句中，finally一定会执行，而且返回值会覆盖掉前面代码的返回值，所以一般用来关闭字节流之类的收尾操作

5.应把捕获子类异常的catch语句放在前，捕获父类异常的语句放在后

6.return语句出现在catch语句内，直接退出方法，而不是回到异常抛出点

7.finally语句不是必须的

8.在方法名后面用throws声明一个或者多个异常，交给调用这个方法的程序来处理异常

9.自定义异常对象无法由系统产生并抛出，所以需要手动生成异常对象并抛出，使用throw语句

10.throw语句抛出的是异常对象，而不是一个异常类，所以需要先实例化异常类再抛出

11.自定义异常类必须继承Throwable类或者其子类，一般不继承Error类

12.当自定义异常类继承RuntimeException及其子类时，是运行时异常，在程序中可以不捕获并处理他

第七章 Java I/O流

1.数据从外部流向程序：输入流 数据从当前程序流向外部：输出流

2.Stream结尾就是字节流，Reader/Writer结尾就是字符流

3.节点流直接在输入输出媒介之上建立，过滤流在节点流类的基础上对节点流功能进行拓展

4.无论是节点流还是字符流，进行读写都是顺序读写的

5.但是也提供了一个随机读写类RandomAccessFile，也在java.io包中

6.标准输入输出流 System类的 in,out,err

7.File类只能对文件本身进行操作，即创建文件、删除文件、返回路径、文件是否存在等

8.File类也可以查看系统磁盘空间信息，以字节为单位返回

9.实现FilenameFilter接口的类实例可以用于过滤文件名，实现抽象方法:

boolean accept(File dir,String name)

10.字节流可以用来处理任何文件，而处理文本文件一般使用字符流

11.InputStream类和OutputStream类是字节流的顶层抽象父类

12.最常用的两个字节流类：FileInputStream和FileOutputStream 通过read和write方法可以对文件数据进行操作

13.实例化FileInputStream，输入参数需要为File类对象或者是一个字符串代表的文件地址

14.I/O流在不使用之后一定要用close关闭

15.FileInputStream找不到文件会抛出FileNotFoundException异常，而FileOutputStream找不到文件会创建一个对应的文件

16.FileOutputStream遇到一个只读文件的时候会抛出IOException异常

17.过滤字节流相当于一个过滤器，必须连接到一个节点流对象，例如

FileInputStream fis = new FileInputStream("xx.txt");
DataInputStream dis = new DataInputStream(fis);

18.FilterInputStream类和FilterOutputStream类为抽象类，

FilterInputStream有三个子类BufferedInputStream,DataInputStream,PushbackInputStream

FilterOutputStream有三个子类BufferedOutputStream,DataOutputStream,PrintStream

19.FilterInputStream类和FilterOutputStream类分别重写了InputStream类和OutputStream类的所有方法

20.BufferedInputStream为缓冲字节流，提高了读写效率，默认缓冲区为32B

21.缓冲输出字节流链接到节点输出流OutputStream

22.在使用缓冲字节流时，一定要在最后使用flush方法强制清空缓冲器，将最后没填满缓冲区的数据输出到节点输出流

23.PushbackInputStream顾名思义，用来需要对数据进行分析的时候，可能需要超前读入一个字节进行判断，然后再从缓冲区将字节返回

24.PushbackInputStream在顶层父类的基础上增加了unread方法，默认返回一个由低8位构成的字节

25.回退过程中如果缓存区满了就不能进行回退unread操作，否则产生IOException异常

26.PrintStream类捕获抛出IOException，而是通过checkError方法来设置测试的内部标志来检测异常

27.PrintStream可以在写入字节数组之后自动调用flush方法

28.实际上out是System类的一个PrintStream类型的类变量，可以调用println和print方法

29.管道字节流一般用于在互联网上传输数据，必须输入输出流同时使用

30.PipedInputStream类和PipedOutputStream类提供了两种方法进行输入输出流的链接

一个是使用connect方法

一个是在实例化管道流对象时进行链接

31.顺序输入流SequenceInputStream可以将几个输入流按顺序连接起来，也就是将多个不同的输入流统一为一个输入流

32.通过将一个Java类实现Serializable接口来表明这个类的对象是可以被序列化的，以此对该对象进行持久化，并可以使用对象流进行操作

33.序列化只能保存对象的实例变量，不能保存任何类的方法和类变量

34.对于用transient关键字标明的瞬时成员变量，对象也不会保存其状态

35.线程对象或流对象的状态是瞬时的，必须用transient修饰，否则编译出错

36.对象流ObjectInputStream和ObjectOutputStream类分别实现了ObjectInput和ObjectOutput接口

37.对象流的构造方法和使用方法于数据流的构造方法以及使用方法基本相同

38.利用对象流输入输出对象时，也需要与其它字节流作为节点流连接起来使用

39.Java采用16位的二进制字符编码方案：Unicode

40.Reader类和Writer类是所有字符流的顶层抽象父类

41.Reader类的ready方法可以用于判断是否准备读取此流

42.Writer类追加字符到字符流的方法为append

43.转换类：InputStreamReader和OutputStreamWriter类

用于处理字节流转换字符流转换

44.实例化转换类对象的方法：

InputStreamReader(InputStream in,String charsetName)

charsetName为可选的指定字符集

45.缓冲字符流BufferedReader和BufferedWriter和缓冲字节流差不多，但是提供了readline和newline方法，可以一行一行的进行操作，而且在行操作时候会使用到行结束标志

46.因为字节流的兼容性不好，操作Unicode编码的文件一般使用文件字符流FileReader和FileWriter

47.文件输出流在实例化时可以选择参数是否为追加模式

FileWriter(File file,boolean append)

48.管道字符流PipedRead和PipedWriter也必须同时使用

49.PrintWriter类类似于PrintStream，可以对基本数据类型进行处理，还可以接受Writer对象作为输出对象

50.RandomAccessFile可以实现随机读写文件，注意是读写都可以；使用getFilePointer方法返回当前指针位置，使用seek方法调整指针位置

51.RandomAccessFile操作文件的模式

r：制度

rw：读写

rws：同步读写，同步写文件内容和文件属性

rwd：数据同步读写，同步写文件内容，不修改文件属性

52.

InputStream和OutputStream是所有字节流类的“祖先”，读写数据的单位是字节。

Reader和Writer是所有字符流类的“祖先”，读写数据的单位是字符。

File类用于创建、删除指定的文件或目录，并且可以获取该文件或目录的属性信息及所在磁盘的信息等，但File类不能打开文件。

FileInputStream/FileOutputStream、FileReader/FileWriter和RandomAccessFile是处理本地文件的类。可以对文件进行读写操作，RandomAccessFile还可以随机地读写指定文件。

BufferedInputStream/BufferedOutputStream和BufferedReader/BufferedWriter提供了缓冲区，达到一定数量时再送到目的文件，以减少阻塞次数，提高读写效率，适合读写大文件。

PipedInputStream/PipedOutputStream和PipedReader/PipedWriter是管道流，要求管道输入流和管道输出流同时使用，适合网络编程。

HeyHey说在前头

本篇将会结合个人理解，对一些我觉得值得讲的代码进行部分注释

基于严蔚敏版《数据结构(C语言版)》

后面想到什么了再补充

——XPIPI

第二章 线性表

算法2.4 顺序线性表的插入

书中算法

Status ListInsert_Sq(SqList &L,int i,ElemType e)
    // L 线性表 i在第i个位置插入 e需要插入的元素
    // 在顺序线性表L中第i个位置之前插入新的元素e
    // i的合法值为 1 <= i <= ListLength.Sq(L) + 1
    // ①验证合法性
    if(i < 1 || i > L.length + 1) {
        return ERROR;
    }
    // ②存储空间满了 需要增加分配的空间
    if(L.length >= L.listsize){
        // 注意：类似malloc，realloc在调用头文件stdlib.h后返回值为 (void *) 这里使用 (ElemType *) 强制转化为我们需要的数据类型的指针
        newbase = (ElemType *)realloc(L.elem,L.listsize+LISTINCREMENT) * sizeof(ElemType);
        // 此处的LISTINCREMENT为之前宏定义过的
        if(!newbase){
            exit(OVERFLOW);
            /*
            OVERFLOW为math.h的一个宏定义，值为3 也即exit(3); 表示运算溢出,存储分配失败
            当然，你也可以自己宏定义OVERFLOW的值
            */
            // 存储分配成功后进行新地址的赋值操作
               L.elem = newbase;
            L.listsize += LISTINCREMENT;
        }
        // ③找插入位置为q 
        q = &(L.elem[i-1]);
        // 将q之后的元素全部右移
        for(p = &(L.elem[L.length-1]);p >= q;--p){
            *(p+1) = *p;
        }
        // 在q这个位置插入e，并增加表长
        *q = e;
        ++L.length;
        return OK;
    }

实现代码

//函数状态码定义
#define TRUE        1
#define FALSE       0
#define OK          1
#define ERROR       0
#define INFEASIBLE -1
#define OVERFLOW   -2
 
typedef int Status;
 
//顺序表的存储结构定义
#define LIST_INIT_SIZE  100
#define LISTINCREMENT   10
typedef int ElemType;

typedef struct{
    ElemType *elem;
    int length;
    int listsize;
}SqList;

Status ListInsert_Sq(SqList &L,int pos,ElemType e){
    if(pos < 1 || pos > L.length + 1) return ERROR;
    if(L.length >= L.listsize){
        int *newbase = (ElemType*)realloc(L.elem,(L.listsize + LISTINCREMENT) * sizeof(ElemType));
        if(!newbase) return OVERFLOW;
        L.elem = newbase;
        L.listsize += LISTINCREMENT
    }
    for(int i = L.length;i >= pos - 1;--1){
        L.elem[i + 1] = L.elem[i];
    }
    L.elem[pos-1] = e;
    L.length++;
    return OK;
}

算法2.5 顺序线性表的删除

书中算法

Status ListDelete_Sq(SqList &L,int i,ElemType &e){
    // L 线性表 i在第i个位置删除 e被删除的元素（此处为引用传递)
    // 在顺序线性表L中删除第i个元素，并用e返回值
    // i的合法值为 1 <= i <= ListLength.Sq(L)
    // ①验证合法性
    if(i < 1 || i > L.length) {
        return ERROR;
    }
        // 找删除位置为p
        p = &(L.elem[i-1]);
        // 将p这个位置的值赋给e *p解引用
        e = *p;
        // 表尾元素标记 左边移动一个
        q = L.elem+L.length-1;
        // 将p之后的元素全部左移
        for(++p;p <= q;++p){
            *(p-1) = *p;
        }
        // 减少表长
        --L.length;
        return OK;
}

实现代码

//函数状态码定义
#define TRUE        1
#define FALSE       0
#define OK          1
#define ERROR       0
#define INFEASIBLE -1
#define OVERFLOW   -2
 
typedef int Status;
 
//顺序表的存储结构定义
#define LIST_INIT_SIZE  100
#define LISTINCREMENT   10
typedef int ElemType;

typedef struct{
    ElemType *elem;
    int length;
    int listsize;
}SqList;

Status ListDelete_Sq(SqList &L,int pos,ElemType &e){
    if(pos < 1 || pos > L.length) return ERROR;
    e = L.elem[pos-1];
    for(int i = pos - 1;i < L.length - 1;++i){
        // 不要用L.elem[i-1] = L.elem[i] 因为是从i开始的，如果i=pos-1=0的情况下会出错
        L.elem[i] = L.elem[i+1];
    }
    L.length--;
    return OK;
}

算法2.7 顺序表的合并

书中算法

void MergeList_Sq(SqList La,SqList Lb,SqList &Lc){
    // 原顺序线性表La、Lb为非递减排列顺序表 Lc为结果顺序表
    // 合并后Lc也为非递减排列顺序表（即升序）
    // 用pa和pb表示La和Lb的基址
    pa = La.elem;pb = Lb.elem;
    // 合并后Lc的大小
    Lc.listsize = Lc.length = La.length + Lb.length;
    // 给Lc分配内存 并用pc表示Lc的基址
    pc = Lc.elem = (ElemType *)malloc(Lc.lisesize * sizeof(ElemType));
    // 分配内存溢出情况
    if(!Lc.elem){ // 这里用!pc也是一样的
        exit(OVERFLOW);
    }
    // 用pa_last和pb_last表示La和Lb的最后一个元素
    pa_last = La.elem + La.length - 1;
    pb_last = Lb.elem + Lb.length - 1;
    // 比较当前pa和pb大小，并插入到Lc中
    while(pa <= pa_last && pb <= pb_last){ // La和Lb都还有元素剩余
        if(*pa <= *pb){
            *pc++ = *pa++;
            /* 看不懂？其实这一句等价于：
                *pc=*pa;
                pc++;
                pa++;
                也就是赋值，并分别移动指针
                下面同理
            */
        }
        else *pc++ = *pb++;
    }
    // La和Lb有一个元素插入完了变成空表了 将另外一个还有元素的表直接全部插入到Lc后面
    while(pa <= pa_last) *pc++ = *pa++;
    while(pb <= pb_last) *pc++ = *pb++;
}

实现代码

//函数状态码定义
#define TRUE        1
#define FALSE       0
#define OK          1
#define ERROR       0
#define INFEASIBLE -1
#define OVERFLOW   -2
 
typedef int Status;
 
//顺序表的存储结构定义
#define LIST_INIT_SIZE  100
#define LISTINCREMENT   10
typedef int ElemType;

typedef struct{
    ElemType *elem;
    int length;
    int listsize;
}SqList;

// 冒泡排序 还记得怎么写吗
Status ListSort_Sq(SqList &L){
    for(int i = 0;i < L.length - 1;++i){
        for(int j = 0;j < L.length - 1 - i;++j){
            if(L.elem[j] > L.elem[j+1]){
                swap(L.elem[j],L.elem[j+1]);
            }
        }
    }
    return OK;
}

// 本体在这儿
// 默认我们这里的La Lb已经排序好了（升序）
// !!这里是包含去重操作的 代码自己看
void MergeList_Sq(SqList La,SqList Lb,SqList &Lc){
    // i对应La j对应Lb k对应Lc
    int i = 0, j = 0, k = 0;
    Lc.elem = (ElemType*)malloc((La.length+Lb.length)*sizeof(ElemType));
    if(!Lc.elem) return OVERFLOW;
    while(i < La.length && j < Lc.length){
        if(La.elem[i] < Lb.elem[j]){//当La的i号元素比Lb的j号元素小
            if(k == 0 || Lc.elem[k-1] != La.elem[i]) {
                // 条件：如果 L3 是空表 (k == 0) 或 L3 的最后一个元素不等于 L1.elem[i]
                // 满足这个条件才加入这个元素 达成去重效果√
                Lc.elem[k++] = La.elem[i];
            }
            // 满不满足去重条件La都要移动到下一个元素 i++
            i++;
        }else if (La.elem[i] > Lb.elem[j]) {//以下同理
            if (k == 0 || Lc.elem[k - 1] != Lb.elem[j]){
                Lc.elem[k++] = Lb.elem[j];
            }
            j++;
        }else{//当La的i号元素比Lb的j号元素相等
            if (k == 0 || Lc.elem[k - 1] != La.elem[i]){
                // 满足条件后，随意添加其中一个
                Lc.elem[k++] = La.elem[i];
            } 
            i++;j++;
        }
    }
    // La或Lb还没空
    while(i < La.length){
        if(k == 0 || Lc.elem[k-1] != La.elem[i]) {
            Lc.elem[k++] = La.elem[i];
        }
        i++;
    }
    while(j < Lb.length){
        if(k == 0 || Lc.elem[k-1] != Lb.elem[i]) {
            Lc.elem[k++] = Lb.elem[i];
        }
        j++;
    }
    return OK;
    /*
    最终效果：
    合并两个有序线性表；
    去除重复元素；
    保持结果有序
    */
}

算法2.9 单链表的插入

书中算法 带头节点 i前插入

Status ListInsert_L(LinkList &L,int i,ElemType e){
    // 在带头节点的单链线性表L中第i个位置之前插入元素e
    // 将L赋给p 此时p代表头指针
    p = L;
    // j用于计数 从0开始
    j = 0;
    while(p && j < i-1){//p不为NULL且j比i-1小
        p = p->next;
        ++j;
        // 不断右移，直到到i-1结点结束
    }
    if(!p || j > i - 1){
        // 两种情况：1.i比表长+1还大 p遍历到表尾最后指向NULL 2.i小于1 j>i-1 将一直为true
        return ERROR;
    }
    // 生成新节点s
    s = (LinkList)malloc(sizeof(LNode));
    s->data = e;
    // 将s插入到L中 注意顺序不可变化
    s->next = p->next;
    p->next = s;
}

实现代码

#define ERROR 0 
#define OK 1
typedef int Status;
typedef int ElemType;

typedef struct LNode
{
    ElemType data;
    struct LNode *next;
 } LNode ,*LinkList;

Status ListInsert_L(LinkList &L,int i,ElemType e){
    LNode *p = L;
    // 也可以是 LinkList p = L
    int j = 0;
    while(p && j < i-1){
        p = p->next;
        ++j;
    }
    if(!p || j > i - 1) return ERROR;
    LNode *s = (LinkList)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

算法2.10 单链表的删除

书中算法

Status ListDelete_L(LinkList &L,int i,ElemType &e){
    // 在带头节点单链线性表L中，删除第i个元素，并由e返回对应值
    p = L;j = 0; // p代表头指针 j为计数器
    while(p->next && j < i-1){ //p->next不为NULL且j比i-1小
        p = p->next;
        ++j;
        //找到第i个结点后，这个时候p是第i个结点的前驱
    }
    if(!(p->next) || j > i-1){
        // 两种情况：1.对应i元素不存在 p遍历到表尾最后指向NULL 2.i小于1 j>i-1 将一直为true
        return ERROR;
    }
    // 指针q指向需要删除的元素 下面两行顺序不可换
    q = p->next;
    // 被删除元素的前驱的后驱更改为被删除元素的后驱
    p->next = q->next;
    // 提取被删除的值
    e = q->data;
    // 释放结点内存
    free(q);
    return OK;
}

实现代码

#define ERROR 0 
#define OK 1
typedef int Status;
typedef int ElemType;

typedef struct LNode
{
    ElemType data;
    struct LNode *next;
 } LNode ,*LinkList;

Status ListDelete_L(LinkList &L,int i,ElemType &e){
    LNode *p = L;
    int j = 0;
    while(p->next && j < i-1){
        p = p->next;
        ++j;
    }
    if(!(p->next) || j > i-1) return ERROR;
    LNode *q = p->next;
    p->next = q->next;
    e = q->data;
    free(q);
    return OK;
}

算法2.12 单链表的归并

书中算法

void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
    // La Lb 元素非递减排列（即递增）
    // 归并得到的新Lc也为非递减排列 链表操作均为引用
    // pa和pb用来表示La和Lb的首元结点
    pa = La->next;pb = Lb->next;
    // 用La的头结点作为Lc的头结点 当然你用Lb的也行:)
    Lc = pc = La;
    while(pa && pb){// pa和pb都没指向空
        if(pa->data <= pb->data){// pa指向元素值小于或等于pb指向元素值
            // 将pc指向结点的后驱改为pa指向结点
            pc->next = pa;
            // 将pc指向结点改为pa
            pc = pa;
            // 移动pa指针到下一个元素
            pa = pa->next;
            // 本质上可以理解成插入操作
        }else{
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
        // 类似于顺序表 可能存在剩余元素 因为链表的性质可以利用三目运算符
        // 这里的pa如果是空的话是NULL 运行：pc->next = pb 反之运行：pc->next = pa
        pc->next = pa?pa:pb;
        free(Lb); //释放Lb头结点 如果前面用Lb当头结点了这里就释放La头结点
    }
}

实现代码

typedef int ElemType;

typedef struct LNode{
    ElemType data;
    struct LNode *next;//定义next为指向结构体LNode的指针
}LNode,*LinkList;
//LinkList也为一个指向结构体的指针   相当于 using LinkList = *LNode;

void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
    LinkList pa,pa,pc;
    pa = La->next;
    pb = Lb->next;
    Lc = pc = La;
    while(pa && pb){
        if(pa->data <= pb->data){
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        }else{
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }
    pc->next = pa?pa:pb;
    free(Lb);
}

第三章 栈和队列

栈的入栈与出栈

// 顺序栈的入栈
Status Push(SqStack &S,SElemType e){
    // 元素e入栈 先检查栈是否已满
    if(S.top - S.base >= S.stacksize){ //栈满条件
        // 若栈满，则重新分配存储空间
        S.base = (SElemType*)realloc(S.base,(S.stacksize + STACKINCREMENT)*sizeof(SElemType));
        // 当然也要考虑溢出导致分配失败情况
        if(!S.base) exit(OVERFLOW);
        // 移动栈顶指针到新的地址
        // 因为重新分配的S.base地址发生了改变 所以这个时候S.top也要跟着改变
        // 此时还没入栈 所以top指针就是指向扩充前的最大的那个元素
        S.top = S.base + S.stacksize;
        // 扩充后，栈的容量也要增加
        S.stacksize += STACKINCREMENT;
    }
    // 如果栈没满，或者经过扩充后 在栈顶添加元素e
    // 由于top指向的是栈顶的下一个位置 所以先将e压入栈顶 top指针再+1
    *S.top++ = e;
    // 等效为：*S.top = e; S.top++;
    return OK;
}

// 顺序栈的出栈
Status Pop(SqStack &S,SElemType &e){
    // 出栈一个元素，用e返回这个值 当然要先检查栈是否为空栈
    if(S.top == S.base){ // 判断空栈条件
        return ERROR;
    }
    // 同理，我们先给e赋值，然后top指针再-1
    // 栈容量不变
    e = *--S.top;
    // 等效为： e = *S.top; S.top--;
    return OK;
}

代码实现

#define OK 1
#define ERROR 0
#define OVERFLOW -2

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
// define语句加分号是允许的（编译通过）但可能会出现问题 所以不推荐
typedef int SElemType;
typedef int Status;

typedef struct{
    SElemType *base;
    SElemType *top;
    int stacksize;
}SqStack;

Status Push(SqStack &S,SElemType e){
    if((S.top - S.base) >= S.stacksize){
        S.base = (SElemType*)realloc(S.base,(S.stacksize + STACKINCREMENT)*sizeof(SElemType));
        if(!S.base) exit(OVERFLOW);
        S.top = S.base + S.stacksize;
        S.stacksize += STACKINCREMENT;
    }
    *S.top = e;
    S.top++;
    return OK;
}

Status Pop(SqStack &S,SElemType &e){
    if(S.top == S.base) return ERROR;
    e = *S.top;
    S.top--;
    return OK;
}

算法3.1 栈的应用：进制转换

书上代码

void conversion(){
    // 对于任意一个非负十进制整数，打印输出与其等值的八进制数
    // 原理：取商留余法
    InitStack(S);
    // 输入一个非负十进制整数N
    scanf("%d",N);
    // 入栈，得到八进制数序列
    while(N){ // N没被除成0前一直运行
        // 把当前的N mod 8入栈
        Push(S,N % 8);
        // 每次入栈一个数 N = N/8
        N /= 8;
    }
    // 出栈并打印结果
    while(!(StackEmpty(S)){
        Pop(S,e);
        printf("%d",e);
    }

}

代码实现

一个十进制 -> X进制的示例：

#define OK 1
#define ERROR 0
#define OVERFLOW -2

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef int SElemType;
typedef int Status;

typedef struct{
    SElemType *base;
    SElemType *top;
    int stacksize;
}SqStack;

Status InitStack(SqStack &S)
Status Push(SqStack &S,SElemType e);
Status Pop(SqStack &S,SElemType &e);
Status StackEmpty(SqStack &S);

void conversion(){
    // 输入需要转换为几进制
    cin >> X;
    // 输入需要转换的数字
    cin >> num;
    InitStack(S);

    char ch[16] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
    while(num){
        Push(S,num % X);
        num /= X;
    }
    
    int e;
    while(!StackEmpty(S)){
        Pop(S,e);
        cout << e << " ";
    }
    cout << endl;
}

队列的入队和出队

// 一种链队列
Status EnQueue(LinkQueue &Q,QElemType e){
    // 将元素e插入到队尾 入队
    // 动态申请空间
    p = (QueuePtr)malloc(sizeof(QNode));
    // 存储分配失败
    if(!p) exit(OVERFLOW);
    // p赋值并next指向NULL（作为新的队尾元素)
    p->data = e;
    p->next = NULL;
    // p入队
    Q.rear->next = p;
    // 移动队尾指针
    Q.rear = p;
    return OK;
}

Status DeQueue(LinkQueue &Q,QElemType &e){
    // 若队列不为空，将Q的队头元素出队，并用e返回其值
    // 首先判断是否为空
    // 判断队列是否为空有三种方法，这里使用front=rear来判断，还有使用标记位flag和计数器count的方法
    if(Q.front == Q.rear) return ERROR;
    // 因为这里是链队列，指针p为头指针指向的下一个元素，也即首元元素(此时的队头)
    p = Q.front->next;
    // 此时p指向为即将出队的元素
    e = p->data;
    // 改变队列头指针指向的元素
    // 也可以写成 Q.front->next = Q.front->next->next 这两种等效
    Q.front->next = p->next;
    // 特殊情况：如果此时队尾元素也是即将出队的元素p 就说明这个队列只有一个元素 出队后将队列置空
    if(Q.rear == p) Q.rear = Q.front;
    // 出队操作后释放p
    free(p);
    return OK;
}

代码实现

#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int QElemType;
typedef int Status;

typedef struct QNode{
    QElemType data;
    struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
    QueuePtr front,rear;
}LinkQueue;

Status EnQueue(LinkQueue &Q, QElemType e) {
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    if (!p)
        exit(OVERFLOW);
    p->data    = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
    return OK;
}

Status DeQueue(LinkQueue &Q, QElemType &e) {
    if (Q.rear == Q.front)
        return ERROR;
    QueuePtr p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if (Q.rear == p)
        Q.rear = Q.front;
    free(p);
    return OK;
}

第四章 串

串的模式匹配算法 算法4.5 4.6 4.7

我们都知道子串的定位操作通常称作串的模式匹配，一般来说常用的有BF算法(也称蛮力法）和KMP算法两种实现方式，其中

BF算法：时间复杂度O(n*m) KMP算法：时间复杂度(n+m)

BF算法伪代码

int Index(SString S,SString T,int pos){
    // 返回子串T在主串S中第pos个字符之后的位置，若不存在，则函数值返回0
    // 其中要求：T非空，1<=pos<=StrLength(S)
    
    // 从pos位置开始查找
    // 主串从pos开始 子串从头开始
    i = pos; j = 1;
    // 从起始位置逐个匹配子串与主串的元素
    while(i <= S[0] && j <= T[0]){ // 注意，串的0下标位置存放串的长度，也即StrLength(S)
        // 逐个字符进行匹配
        if(S[i] == T[j]){
            // 若字符匹配成功，主串子串均往后走一个元素
            ++i;
            ++j;
        }else{
            // 若字符匹配不成功，主串回溯到i-j+2位置，子串回到串头重新比较（实际效果：子串整体向下一位移动）
            i = i - j + 2;
            j = 1;
        }
        // 如果找到了这么个子串（也就是j成功走到了子串的最后一个元素的后一位），那就返回这个子串在主串中的起始位置
        if(j > T[0]) return i - T[0];
        // 没找到就返回0
        else return 0;
    }
}

代码实现

#define MAXSTRLEN 255
// 定长顺序串存储表示
typedef char SString[MAXSTRLEN + 1];

int Index(SString S, SString T, int pos) {
    int n = StrLength(S);
    int m = StrLength(T);

    // 边界检查
    if (pos < 0 || pos >= n || m == 0 || m > n) {
        return 0;
    }

    int i = pos;
    int j = 0;
    while (i < n && j < m) {
        if (S[i] == T[j]) {
            ++i;
            ++j;
        } else {
            i = i - j + 1; // 从下一位置重新匹配
            j = 0;
        }
    }

    return (j == m) ? (i - m) : 0;
}

KMP算法伪代码

int Index_KMP(SString S,SString T,int pos){
    // 利用模式串T的next函数求T在主串S中第pos个字符之后位置的KMP算法
    // 其中要求：T非空，1<=pos<=StrLength(S)
    i = pos; j = 1;
    while(i <= S[0] && j <= T[0]){
        if(j == 0 || S[i] == T[j]){ // 与BF算法不同，在KMP算法中模式串回到开头(j==0)时，只能跳过当前主串字符，从主串下一个字符开始匹配
            ++i; ++j;
        }else{
            // 回退到部分匹配的位置
            j = next[j];
        }
    }
    if(j > T[0]) return i-T[0];
    else return 0;
}

emm....看上去跟BF算法基本差距主要在于next数组，那么这个数组怎么求得呢？

next数组与前后缀有关！具体定义可自行查阅资料。

void get_next(SString T,int next[]){
    // 求模式串T的next函数值并存入
    i = 1;
    // 人为定义第一个是0 ，因为模式串T的第一个字符是不存在前后缀的
    // 其实第二位也一定为1，但这里不手动定义
    next[1] = 0;
    // j 表示当前前缀长度（指向当前字符之前的最长相等前后缀的下一个位置）
    j = 0;
    while(i < T[0]){
        if(j == 0 || T[i] == T[j]){
            // 如果：
            // 1. j == 0：表示当前字符没有可以匹配的前缀
            // 2. T[i] == T[j]：表示当前字符与最长前缀的下一个字符匹配
            
            ++i;++j;
            
            // 将当前字符对应的 next 值设为 j（最长相等前后缀长度）
            next[i] = j;
        }else {
            // 如果当前字符与最长前缀的下一个字符不匹配
            j = next[j]; // 回退 j，尝试更短的前缀匹配
        }
    }
}

完整代码实现

#define MAXSTRLEN 255

typedef char SString[MAXSTRLEN + 1];

void get_next(SString T, int next[]) {
    int i = 1, j = 0;
    next[1] = 0;
    while (i < T[0]) {
        if (j == 0 || T[i] == T[j]) {
            ++i;
            ++j;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

int Index_KMP(SString S, SString T, int pos) {
    int next[MAXSTRLEN + 1];
    get_next(T, next);
    int i = pos, j = 1;
    while (i <= S[0] && j <= T[0]) {
        if (j == 0 || S[i] == T[j]) {
            ++i;
            ++j;
        } else {
            j = next[j];
        }
    }
    return (j > T[0]) ? (i - T[0]) : 0;
}

第五章 数组与广义表

算法5.1 稀疏矩阵的普通转置操作 O(nu * tu)

Status TransposeSMartix(TSMatrix M, TSMatrix &T){
    // 稀疏矩阵用三元组存储 求稀疏矩阵M的转置矩阵T
    // T的行数 = M的列数
    T.mu = M.nu;
    // T的列数 = M的行数
    T.nu = M.mu;
    // T的非零元个数 = M的非零元个数
    T.tu = M.tu;
    
    if(T.tu){ // 避免对空矩阵进行操作
        // 初始化指针q，指向T矩阵存储数组的起始位置，用来存储转置后的元素
         q = 1;
        // 外层循环遍历矩阵M的列
         for(col = 1;col <= M.nu;++col)
             // 内层循环遍历矩阵M的非零元素
             for(p = 1;p <= M.tu;++p){
                 // 如果当前非零元素M.data[p]的列索引（M.data[p].j）等于当前列索引col
                 if(M.data[p].j == col){
                      // 将原矩阵M的行索引（M.data[p].i）赋值给转置矩阵T的数据项的列索引
                     T.data[q].i = M.data[p].j;
                     // 将原矩阵M的列索引（M.data[p].j）赋值给转置矩阵T的数据项的行索引
                     T.data[q].j = M.data[p].i;
                     // 将原矩阵M的非零元素值（M.data[p].e）赋值给转置矩阵T的数据项
                     T.data[q].e = M.data[p].e;
                     // 移动指针q，指向下一个位置
                     ++q;
                 }
             }
     }
    return OK;
}

算法5.2 稀疏矩阵的快速转置操作 O(nu+tu)

Status FastTransposeSMatrix(TSMatrix M,TSMatrix &T){
    // 快速将稀疏矩阵M转置为T
    T.mu = M.nu; T.nu = M.mu; T.tu = M.tu;
    if (T.tu) {
    // 步骤 1：初始化并计算每列的非零元素个数
    for (col = 1; col <= M.nu; ++col) {
        num[col] = 0; 
    }
    for (t = 1; t <= M.tu; ++t) {
        // 对于每一个非零元素 M.data[t]，增加其所在列 (M.data[t].j) 的计数
        ++num[M.data[t].j];
    }

    // 步骤 2：计算每一列的第一个非零元素在 T 中的起始位置
    cpot[1] = 1; 
    // cpot 数组用于存储转置后的矩阵 T 中，按列顺序每列第一个非零元素的位置。初始化 cpot[1] 为 1，表示第一列的第一个非零元素在 T 中的位置
    for (col = 2; col <= M.nu; ++col) {
        // 通过累加每列的非零元素个数，计算出第 col 列第一个非零元素在转置矩阵 T 中的位置
        cpot[col] = cpot[col - 1] + num[col - 1];
    }

    // 步骤 3：转置
    for (p = 1; p <= M.tu; ++p) {
        // 获取当前非零元素所在列的列索引
        col = M.data[p].j;
        // 获取当前列 col 在转置矩阵 T 中的当前位置，保存在 q 中
        q = cpot[col];
        // 将 M 中当前非零元素的行列交换，存储到 T 中
        T.data[q].i = M.data[p].j;  // 将 M 中元素的列索引 (M.data[p].j) 存储为 T 中的行索引
        T.data[q].j = M.data[p].i;  // 将 M 中元素的行索引 (M.data[p].i) 存储为 T 中的列索引
        T.data[q].e = M.data[p].e;  // 将 M 中元素的值 (M.data[p].e) 存储到 T 中

        // 将 cpot[col] 递增，表示该列的下一个非零元素在 T 中的位置
        ++cpot[col];
    }  // for
}  // if
}

代码实现

#define OK 1
#define MAXSIZE 255

typedef int ElemType;
typedef int Status;

// 用三元组存储稀疏矩阵
typedef struct{
    int i, j;
    ElemType e;
}Triple;

typedef struct{
    Triple data[MAXSIZE];
    int mu, nu, tu;          //矩阵行数，列数和非0元个数
}TSMatrix;

//稀疏矩阵转置   （适用于 tu << mu × nu 的情况）
Status TransposeSMatrix(TSMatrix M,TSMatrix &T){
    T.mu = M.nu; T.nu = M.mu; T.tu = M.tu;
    if(T.tu){
        int q = 1;
        for(int col = 1; col <= M.nu; ++col){
            for(int p = 1; p <= M.tu; ++p){
                if(M.data[p].j == col){
                    T.data[q].i = M.data[p].j;
                    T.data[q].j = M.data[p].i;
                        T.data[q].e = M.data[p].e;
                    q++;
                }
            }
        }
    }
    return OK;
}

//稀疏矩阵的快速转置算法
Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T){
    int cpot[MAXSIZE + 1], num[MAXSIZE + 1];   //辅助数组  
    T.mu = M.nu; T.nu = M.mu; T.tu = M.tu;
    if(T.tu){
        for (col = 1; col <= M.nu; ++col) {
            num[col] = 0; 
        }
        for(int k = 1; k <= M.tu; k++) {
            num[M.data[k].j]++;
        }
        cpot[1] = 1;
        for(int col = 2; col <= M.mu; col++){
            cpot[col] = cpot[col - 1] + num[col - 1];
        }
        
        for(int p = 1; p <= M.tu; p++){
            int col = M.data[p].j; 
                int q = cpot[col];
            T.data[q].i = M.data[p].j;
            T.data[q].j = M.data[p].i;
            T.data[q].e = M.data[p].e;
            cpot[col]++;
        }
    }
    return OK;
}

第六章 树和二叉树

算法6.3 中序遍历二叉树的非递归（迭代）算法②

有两种方法 这里介绍书中的第二种

Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){
    // 采用二叉链表存储结构，Visit是对数据元素操作的应用函数
    // 中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit
    InitStack(S);
    // 将指针 p 初始化为树的根节点 T，p 用于遍历树
    p = T;

    // while 循环用于遍历树，直到栈为空并且 p 指针为空为止
    while (p || !StackEmpty(S)) {
    if (p) {  // 如果 p 不为空，说明当前节点存在
        // 将当前节点 p 压入栈 S，保存节点，以便后续返回到该节点
        Push(S, p);  
        // 移动到当前节点的左子树，继续向下遍历左子树
        p = p->lchild; 
    } else {  // 如果 p 为空，说明当前节点没有左子树，或者已经遍历完左子树
         // 弹出栈顶元素，将栈顶元素赋值给 p，p 指向栈顶保存的节点
        Pop(S, p); 
        if (!Visit(p->data)){
            return ERROR;
        }
        // 移动到当前节点的右子树，准备遍历右子树
        p = p->rchild; 
    }  // else
}  // while

    return OK;
}

算法6.4 先序序列创建二叉树（递归）

Status CreateBiTree(BiTree &T){
    // 按先序次序输入二叉树中结点的值（一个字符） 空格字符代表空树
    // 构造二叉链表表示的二叉树T
    scanf(&ch);
    // 如果是空字符，表示没有树的根节点，因此将树 T 设置为 NULL（空树）
    if(ch == '') T = NULL;
    else{
        // 动态分配内存给新节点 T
        if(!(T = (BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
        T->data = ch;
        // 递归创建左右子树
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
    return OK;
}

代码实现

#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int TElemType;
typedef int Status;

typedef struct BiTNode{
    TElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

Status InOrderTraverse(BiTree T){
    SqStack S;
    InitStack(&S);
    BiTree p = T;
    while(p || !StackEmpty(&S)){
        if(p != NULL){
            Push(&S,p);
            p = p->lchild;
        }else{
            Pop(&S,p);
            printf("%d ",p->data);
            p = p->rchild;
        }
    }
}

Status CreateBiTree(BiTree &T)
{
    char ch=getchar();
    if(ch=='.') {
        T = NULL;
    } else{
        T = (BiTree)malloc(sizeof(BiTNode));
        if(!T) exit(OVERFLOW);
        T->data = ch;
        CreateBiTree(&((*T)->lchild));
        CreateBiTree(&((*T)->rchild));
    }
    return OK;
}

第七章 图

算法7.4 7.5 深度优先搜索的存储结构和遍历

// 辅助数组，用来记录顶点是否已访问
Boolean visited[MAX];
// 用来访问函数指针
// VisitFunc是一个指向函数的指针 （int v)是这个函数的参数
// 因此这里实际上创建的是全局变量 VisitFunc
Status (*VisitFunc)(int v); 

void DFSTraverse(Graph G, Status (*Visit)(int v)) {
    // 对图G进行深度优先遍历
    // 使用全局变量，使DFS函数不需要设置函数指针参数
    VisitFunc = Visit;
    // 对整个辅助数组进行初始化为未访问
    for (v = 0; v < G.vexnum; ++v) {
        visited[v] = FALSE; 
    }
    // 对每一个顶点进行深度优先遍历
    for (v = 0; v < G.vexnum; ++v) {
        if (!visited[v]) {
            // 对未访问的顶点进行DFS操作
            DFS(G, v); 
        }
    }
}

void DFS(Graph G, int v) {
    // 从顶点v开始深度优先遍历
    visited[v] = TRUE; // 标记为已访问
    VisitFunc(v); // 执行访问操作
    for (w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w)) {
        if (!visited[w]) {
            // 递归访问邻接点
            DFS(G, w); 
        }
    }
}

算法实现（邻接表存储的图）

#define MAX_VERTEX_NUM 20

typedef VertexType int;
typedef InfoType int;

// 顶点访问状态
enum VisitIf { unvisited, visited };

// 边表结点
typedef struct EBox {
    VisitIf mark;      // 访问标记
    int ivex, jvex;    // 关联的顶点
    struct EBox *ilink, *jlink; // 链接到下一个边的指针
    InfoType* info;        // 边的附加信息指针
} EBox;

// 顶点表结点
typedef struct VexBox {
    VertexType data;        // 顶点数据
    EBox* firstedge;  // 指向第一条关联边的指针
} VexBox;

// 图的定义（邻接多重表表示）
typedef struct {
    VexBox adjmulist[MAX_VERTEX_NUM]; // 顶点数组
    int vexnum, edgenum;              // 顶点数和边数
} AMLGraph;

// 辅助数组，用来记录顶点是否已访问
bool visited[MAX_VERTEX_NUM];

// 用来访问顶点的函数指针
void (*VisitFunc)(int);

// 深度优先遍历
void DFSTraverse(AMLGraph& G, void (*Visit)(int)) {
    VisitFunc = Visit; 
    for (int v = 0; v < G.vexnum; ++v) {
        visited[v] = false;
    }
    for (int v = 0; v < G.vexnum; ++v) {
        if (!visited[v]) {
            DFS(G, v);
        }
    }
}

// 从顶点v开始深度优先搜索
void DFS(AMLGraph& G, int v) {
    visited[v] = true;
    VisitFunc(v);
    EBox* p = G->adjmulist[v].firstedge; // 获取顶点v的第一条边
    while (p) { 
        w = 
        int w = (p->ivex == v) ? p->jvex : p->ivex; // 找到顶点v的邻接点
        if (!visited[w]) { 
            DFS(G, w); // 递归访问未访问的邻接点
        }
        p = (p->ivex == v) ? p->ilink : p->jlink; // 移动到下一条边
    }
}

算法7.6 广度优先遍历

void BFSTraverse(Graph G,Status (*Visit)(int v)){
    // 广度优先非递归遍历图G 辅助队列G 访问标志数组visited[]
    for(v = 0;v < G.vexnum;++v){
        visited[v] = FALSE;
    }
    // 初始化访问标志数组
    // 初始化辅助队列
    InitQueue(Q);
    for(v = 0;v < G.vexnum;++v){
        // 遍历访问未访问的结点
        if(!visited[v]){
            // 更改访问标志数组并访问顶点v
            visited[v] = TRUE;
            Visit(v);
            // 将顶点v入队
            EnQueue(Q,v);
            // 如果队列不空
            while(!QueueEmpty(Q)){
                // 队头出列并赋值给u
                DeQueue(Q,u);
                for(w = FirstAdjVex(G,u); w >= 0; w = NextAdjVex(G,u,x)){
                    // w 为 v未访问的邻接顶点
                     if(!Visited[w]){
                         Visited[w] = TRUE;
                         Visit(w);
                         EnQueue(Q,w);
                     } // if
                } // for
            } // while
        } // if
    } // for
} // BFSTraverse

算法实现 （邻接矩阵存储的图）

#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20

typedef VRType int;
typedef InfoType int;
typedef VertexType int;

typedef struct ArcCell{
    VRType adj;                      // 邻接关系（1 表示有边，0 表示无边）
    InfoType* info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct{
    VertexType vexs[MAX_VERTEX_NUM];
    AdjMatrix arcs;
    int vexnum,arcnum;
}MGraph;

bool visited[MAX_VERTEX_NUM];

void BFStraverse(MGraph G){
    for (int v = 0; v < G.vexnum; v++) visited[v] = False;
    SqQueue Q;
    InitQueue(&Q);
    for (int v = 0; v < G.vexnum; v++)    {
        if (!visited[v]){
            visited[v] = True;    Visit(v);
            EnQueue(&Q, v);
            while (QueueEmpty(Q)){
                int u;
                DeQueue(&Q, &u);
                for (int w = 0; w < G.numVertexes; w++){
                    if (G.arc[u][w] == 1 && !visited[w]){
                        visited[w] = True;
                        Visit[w];
                        EnQueue(&Q, w);    
                    }
                }
            }
        }
    }
}

第九章 查找

算法9.2 折半查找（二分查找）

// very Easy
int Search_Bin (SSTable ST,KeyType key){
    // 在有序表ST中查找关键字为key的元素
    // 找到返回对应位置，否则return 0
    low = 1 ; // 左
    high = ST.length; // 右
    while(low <= high){ // 左右相遇终止
        mid = (low + high) / 2; // 相当于逻辑右移一位（速度快点）
        if (EQ(key,St.elem[mid].key)) return mid; // 找到了
        else if (LT(key,St.elem[mid].key)) high = mid - 1; // key比当前的要小，移动high
        else low = mid + 1; // key比当前的要大，移动low
    }
    return 0;
}

算法实现 C

typedef ElemType int;

typedef struct{
    ElemType* elem;
    int length;
}SSTable;

int Search_Bin (SSTable ST,int key){
    int left = 1;
    int right = ST.length - 1;
    while(low <= high && mid = (left+right) >> 1){
        if(St.elem[mid] == key) return mid;
        else if (St.elem[mid] > key) right = mid - 1;
        else left = mid + 1;
    }
    return 0;
}