数据结构
顺序线性表
顺序线性表是一种在内存空间上分布连续，包含同一种类型数据元素，并且逻辑上相邻物理上也相邻的线性存储结构。
基本属性
- data 用于存储数据元素，其数据元素可以是任意类型（T类型，其为Object或其子类）
- length 用于记录顺序线性表已存储数据元素空间的长度
- MAX_SIZE 开辟的内存空间上限大小
重点方法介绍
无参构造
SeqList()
创建一个空顺序表，为私有属性data开辟内存空间，大小为MAX_SIZE
基本思路
初始化length属性为0，表示此时顺序表元素个数为0，顺序表为空表，但是已经开辟了内存空间
public SeqList(){
//this指针指向私有属性length并初始化值为0
this.length = 0;
//申请一个大小为MAX_SIZE的连续存储空间，其存储数据类型为Object(可以存放所有类型的对象)
data = new Object[MAX_SIZE];
}
有参构造
SeqList(T[] data, int length)
将外界创建好的T类型数组赋值给当前顺序列表，类型T由外界提供，可以是任意类型
基本思路
用已开辟好内存空间的数组T[ ]类型的data对data属性初始化，并且提供一个当前存储数据长度length值对length属性初始化
public SeqList(T[] data,int length){
//为data属性初始化
this.data = data;
//为length属性初始化
this.length = length;
}
按位查找
Get(int i)
提供一个索引值i，根据索引值查找并返回顺序表中的元素值
基本思路
判断索引值是否符合顺序表有效范围，即当前顺序表已存储元素索引范围应当为**[0,length-1]，在此范围之外的都应当视为越界查找**，抛出异常
否则直接返回data[i]
这里使用了**(T)，对Object类型的data[i]进行强制转换，转换为当前顺序表存储元素类型T**，返回类型为T的元素
public T Get(int i){
if (i < 0 || i >= length){
throw new RuntimeException("查找位置异常");
}
return (T)this.data[i];
}
插入元素
insert(int i,T x)
在当前顺序表表尾或是已存储数据元素的位置插入一个新元素，并整理使其依旧连续，这里连续的概念为两个数据元素之间不允许有未存储数据元素的空间
基本思路
- 条件判断
先判断当前顺序表是否已满，如果length==MAX_SIZE则表示顺序表开辟内存空间已被全部使用，无法继续插入新数据元素，抛出上溢异常
再判断i值是否满足插入索引条件[0,length]，即已有数据元素的位置和顺序表尾部的空闲存储位置，如果不满足则抛出插入位置异常
- 向后置换
从length索引位置开始，不断将前一个数据元素置换到当前位置，直到抵达插入位置停止置换
- 插值
然后将插入位置的数据元素替换为需要插入的新值
- 更新顺序表长度
私有属性length++
public void insert(int i,T x){
if (length == MAX_SIZE){
throw new RuntimeException("列表上溢");
}
if (i<0||i>length){
throw new RuntimeException("插入位置异常");
}
//数值向后置换
for(int j = length;j>i;j--){
data[j] = data[j-1];
}
//插入
data[i] = x;
//更新列表长度
length++;
}
删除元素
delete(int i)
删除顺序表指定位置的元素，并整理顺序表使其依旧连续，返回删除的值
基本思路
- 检查删除位置
删除索引值i需要满足**[0,length-1]**，即顺序表已存储数据元素的索引位置
- 返回删除的值
先用一个T类型的x来保存需要删除的值，当删除完毕后返回x
- 删除值
从前向后置换，从需要删除的位置开始，不断将后一个数据元素置换到当前位置，抵达最后一个元素时停止置换
- 更新顺序表长度
私有属性length–
public T delete(int i){
T x = (T)this.data[i];
for (int j = i; j < length - 1; j++) {
data[j] = data[j+1];
}
length--;
return x;
}
代码
package com.os467.list;
public class SeqList<T> {
//最大内存空间
private final int MAX_SIZE = 1024;
//数据元素
private Object[] data;
//长度
private int length;
/**
* 顺序列表构造函数
*/
public SeqList(){
this.length = 0;
data = new Object[MAX_SIZE];
}
/**
* 有参构造函数
* @param data
* @param length
*/
public SeqList(T[] data,int length){
this.data = data;
this.length = length;
}
/**
* 求线性表的长度
* @return
*/
public int getLength(){
return length;
}
/**
* 按位查找，取第i个元素
* @param i
* @return
*/
public T Get(int i){
if (i < 0 || i >= length){
throw new RuntimeException("查找位置异常");
}
return (T)this.data[i];
}
/**
* 在线性表第i个位置插入一个值为x的元素
* @param i
* @param x
*/
public void insert(int i,T x){
if (length == MAX_SIZE){
throw new RuntimeException("列表上溢");
}
if (i<0||i>length){
throw new RuntimeException("插入位置异常");
}
//数值向后置换
for(int j = length;j>i;j--){
data[j] = data[j-1];
}
//插入
data[i] = x;
//更新列表长度
length++;
}
/**
* 删除线性表第i个元素
* @param i
* @return
*/
public T delete(int i){
T x = (T)this.data[i];
for (int j = i; j < length - 1; j++) {
data[j] = data[j+1];
}
length--;
return x;
}
/**
* 求线性表中值为x的元素序号,-1为不存在
* @param x
* @return
*/
public int locate(T x){
for (int i = 0; i < length; i++) {
if (data[i].equals(x)){
return i;
}
}
return -1;
}
/**
* 依次输出线性表各元素
*/
public void printList(){
System.out.print("[");
int len = length - 1;
for (int i = 0; i < len; i++) {
System.out.print(data[i]);
System.out.print(",");
}
if (len >= 0){
System.out.print(data[len]);
}
System.out.println("]");
}
/**
* 设置线性表第i个元素值
* @param i
* @param x
*/
public void set(int i, T x){
if (i < 0 || i >= length){
throw new RuntimeException("设置位置异常");
}
this.data[i] = x;
}
/**
* 返回data数组
* @return
*/
public T[] pData(){
return (T[])this.data;
}
/**
* 设置线性表长度为n
*/
public void setLength(int n){
length = n;
}
}
链式线性表
基本属性
- first 头指针，用来指向单链表头结点，头结点指针域为空时则单链表为空
重点方法介绍
无参构造
LinkList()
创建头结点，first指针指向头结点，头结点指针域为null，表示单链表为空
基本思路
为私有属性first赋值为新建的空结点，结点指针域与数据域为null
public LinkList(){
first = new Node<>();
}
有参构造（前插方式建表）
LinkList(T[] a, int n)
需要提供一个T类型的数据元素数组，以及数组长度，链表将以前插的方式进行构建（后创建的结点更接近头结点），从第一个结点遍历链表值应该为T[] a数组值的逆序
基本思路
- 创建头结点
创建头结点，头指针指向头结点，头结点指针域指向null，表示还没有数据元素存储在链表中
- 遍历数组创建新结点
遍历a数组，创建当前节点s，为其数据域赋值
- 前插新结点
将当前结点与头结点的后续结点连接，s->next_node<-first_node
将头结点的指针域更新为当前结点，first_node->s->next_node
基本思想是，只使用一个指针s存储当前结点，不断插入头结点与后续结点之间
public LinkList(T[] a, int n){
//初始化头结点，指针域为空
first = new Node<>();
first.next = null;
//s指向需要链接入的结点
Node<T> s;
for (int i = 0; i < n; i++) {
//创建新结点
s = new Node<>();
//数据域赋值
s.data = a[i];
//与后续结点链接
s.next = first.next;
//更新当前结点为第一个结点
first.next = s;
}
}
有参构造（后接方式建表）
LinkList(int n, T[] a)
需要提供数组a以及数组a长度n，将以后接方式不断构建链表（后创建的结点更接近表尾），从第一个结点遍历链表值应该为T[] a数组值的顺序
基本思路
- 创建头结点
创建头结点，头指针指向头结点，头结点指针域为null，说明链表为空，暂无数据元素存储
创建两个指针r，s
- 遍历数组，创建新结点
r先指向头结点，然后开始遍历数组，s指向当前新建结点，为新建结点数据域赋值
- 尾接新结点
然后将新建结点与尾结点进行连接，即r指向结点的指针域指向s指向的结点
更新当前尾结点为新连入的结点，即r指向s
结束循环后设置尾结点指针域为空即可
基本思想是使用两个指针r和s分别记录尾结点位置和当前新建结点位置，不断将新建结点接入链表的末尾
public LinkList(int n, T[] a){
//初始化头结点
first = new Node<>();
first.next = null;
//s指向需要链接入的结点，r指向当前链尾结点
Node<T> r,s;
r = first;
for (int i = 0; i < n; i++) {
//创建结点
s = new Node<>();
s.data = a[i];
//后接结点
r.next = s;
r = s;
}
//尾指针设置为空
r.next = null;
}
获取链表长度
getLength()
返回当前单链表已存储数据元素结点个数（不包含头结点），如果链表为空则返回0
基本思路
- 创建指针
创建指针p指向头结点指针域指向的第一个结点
- 遍历判断并计数
判断当前结点是否为null，如果为null则结束循环，停止计数，否则说明当前结点存储了数据元素，计数器len++，p指向下一个结点
- 返回值
返回结点长度计数len值
public int getLength(){
int len = 0;
//指向第一个数据元素结点
Node<T> p = first.next;
//当前指针不为空
while (p != null){
len++;
//检查下一个指针域指向结点
p=p.next;
}
return len;
}
获取元素
get(int i)
获取单链表存储的第i个数据元素，i的范围应该在**[1,length]**
基本思路
- 创建指针
指针p指向头结点的指针域，即第一个存储数据元素的结点
- 遍历链表
循环判断，如果当前结点不为null，并且未到达指定结点位置，不断访问下一结点，并更新当前结点位置计数器j
- 判断位置正确性
退出循环，如果当前p指向空结点，则有可能链表为空，或是抵达末尾结点也没有满足所提供的获取结点位置，因此抛出位置错误异常
- 返回值
否则返回当前结点数据元素值
/**
* 获取链表第i个数据元素
* @param i
* @return
*/
public T get(int i){
Node<T> p = first.next;
int j = 1;
while (p != null && j < i){
//访问下一结点
p = p.next;
j++;
}
if (p == null){
//链表为空
throw new RuntimeException("位置错误");
}
return p.data;
}
插入元素
insert(int i, T x)
在原先第i个结点所在位置插入新结点，并使得链表依旧有序链接
基本思路
引入头结点：插入的条件在任何情况下都具备前一结点
通过访问到第i-1个结点后插入新结点
- 创建指针，计数器，从头结点开始遍历
指针p指向头结点（由于头结点的存在，使得空链表也可以依据此规则插入数据元素），j = 0 表示从头结点开始遍历
- 循环判断并遍历链表
循环判断，如果当前未抵达链表尾部null指针域 并且 访问暂未访问到第i-1个结点，则继续访问下一结点，当前访问结点计数j++
- 判断位置条件并插入新结点
退出循环，判断指针指向结点是否为null，为null则代表插入位置不满足插入条件，抛出位置异常
若满足插入条件，则此时p指向第i-1个结点，创建新节点s，让s与原先的第i个结点链接，s->next_node<-p
再让第i-1个结点与s指向结点链接，p->s->next_node
public void insert(int i, T x){
if (i<1){
throw new RuntimeException("插入位置错误");
}
Node<T> p = first;
int j = 0;
//访问到第i-1个数据元素结点
int m = i - 1;
while (p!= null && j < m){
//访问下一结点
p = p.next;
j++;
}
if (p == null){
throw new RuntimeException("插入位置错误");
}else {
//创建结点
Node<T> s = new Node<>();
s.data = x;
//链接后续结点
s.next = p.next;
//插入到第i-1个结点之后,与第i-1个数据元素结点链接
p.next = s;
}
}
删除元素
delete(int i)
删除第i个结点，重新链接链表并使得链表依旧有序链接，返回被删除结点存储的数据元素
基本思路
和插入思路类似，也是访问到第i-1个结点进行删除操作
- 创建指针，计数器，从头结点开始遍历
创建p指针指向头结点，j = 0 表示从头结点开始遍历
- 循环判断，遍历链表
循环判断如果当前未抵达链表尾部null指针域 并且 未到达第i-1个结点，则继续访问下一结点，访问结点数计数j++
判断当前p是否未null或p的next指针域是否为null（前一种情况代表走到链表尾部，后一种情况代表遍历到头结点），如果不满足位置删除条件则抛出异常
- 重新链接，删除结点
若满足删除条件，则此时p节点指向第i-1个结点，创建指针q指向p节点的下一结点，q->next_node<-p，此时q指向第i个结点，即要删除的结点，保存删除的数据元素data = q.data
链接p节点与q节点指向结点的下一结点，p->next_node<-q
删除q节点
- 返回值
返回被删除的数据元素值data
public T delete(int i){
Node<T> p = first;
int j = 0;
//访问到第i-1个数据元素结点
int m = i - 1;
while (p!= null && j < m){
//访问下一结点
p = p.next;
j++;
}
T data;
if (p == null || p.next == null){
throw new RuntimeException("删除位置错误");
}else {
Node<T> q = p.next;
//保存删除的数据元素
data = q.data;
//链接到下一个元素的指针域指向的结点
p.next=q.next;
//c++ delete q;
}
return data;
}
代码
package com.os467.list;
public class LinkList<T> {
private Node<T> first;
/**
* 无参构造方法，单链表为空
*/
public LinkList(){
first = new Node<>();
}
/**
* 前插法构造函数
*/
public LinkList(T[] a, int n){
//初始化头结点，指针域为空
first = new Node<>();
first.next = null;
//s指向需要链接入的结点
Node<T> s;
for (int i = 0; i < n; i++) {
//创建新结点
s = new Node<>();
//数据域赋值
s.data = a[i];
//与后续结点链接
s.next = first.next;
//更新当前结点为第一个结点
first.next = s;
}
}
/**
* 后接法构造函数
* @param n
* @param a
*/
public LinkList(int n, T[] a){
//初始化头结点
first = new Node<>();
first.next = null;
//s指向需要链接入的结点，r指向当前链尾结点
Node<T> r,s;
r = first;
for (int i = 0; i < n; i++) {
//创建结点
s = new Node<>();
s.data = a[i];
//后接结点
r.next = s;
r = s;
}
//尾指针设置为空
r.next = null;
}
/**
* 获取链表长度
* @return
*/
public int getLength(){
int len = 0;
//指向第一个数据元素结点
Node<T> p = first.next;
//当前指针不为空
while (p != null){
len++;
//检查下一个指针域指向结点
p=p.next;
}
return len;
}
/**
* 获取链表第i个数据元素
* @param i
* @return
*/
public T get(int i){
Node<T> p = first.next;
int j = 1;
while (p != null && j < i){
//访问下一结点
p = p.next;
j++;
}
if (p == null){
//链表为空
throw new RuntimeException("位置错误");
}
return p.data;
}
/**
* 设置第i个结点数据元素的值
* @param i
* @param x
*/
public void set(int i, T x){
Node<T> p = first.next;
int j = 1;
while (p != null && j < i){
//访问下一个结点
p = p.next;
j++;
}
if (p == null){
throw new RuntimeException("位置错误");
}else {
//更新值
p.data = x;
}
}
/**
* 查找数据元素值为x的位置
* @param x
* @return
*/
public int locate(T x){
Node<T> p = first.next;
int i = 1;
while (p != null && !p.data.equals(x)){
//访问下一个结点
p = p.next;
i++;
}
if (p == null){
return -1;
}else {
return i;
}
}
/**
* 在第i-1个数据元素结点位置插入新结点
* @param i
* @param x
*/
public void insert(int i, T x){
if (i<1){
throw new RuntimeException("插入位置错误");
}
Node<T> p = first;
int j = 0;
//访问到第i-1个数据元素结点
int m = i - 1;
while (p!= null && j < m){
//访问下一结点
p = p.next;
j++;
}
if (p == null){
throw new RuntimeException("插入位置错误");
}else {
//创建结点
Node<T> s = new Node<>();
s.data = x;
//链接后续结点
s.next = p.next;
//插入到第i-1个结点之后,与第i-1个数据元素结点链接
p.next = s;
}
}
/**
* 删除第i个数据元素
* @param i
* @return
*/
public T delete(int i){
Node<T> p = first;
int j = 0;
//访问到第i-1个数据元素结点
int m = i - 1;
while (p!= null && j < m){
//访问下一结点
p = p.next;
j++;
}
T data;
if (p == null || p.next == null){
throw new RuntimeException("删除位置错误");
}else {
Node<T> q = p.next;
//保存删除的数据元素
data = q.data;
//链接到下一个元素的指针域指向的结点
p.next=q.next;
//c++ delete q;
}
return data;
}
/**
* 获取到头结点
* @return
*/
public Node<T> getFirst(){
return first;
}
/**
* 设置头结点
* @param p
*/
public void setFirst(Node<T> p){
first = p;
}
/**
* 打印链表
*/
public void printLinkList(){
Node<T> p = first.next;
System.out.print("first->");
while (p != null){
System.out.print(p.data+"->");
p=p.next;
}
System.out.println("null");
}
class Node<T>{
//数据域
private T data;
//指针域
private Node<T> next;
}
}
顺序栈
基本属性
- data 存储栈元素的数组
- top 栈顶指针
- MAX_SIZE 申请的最大内存空间
重点方法介绍
无参构造
Stack()
创建空栈，为data数组和top指针初始化
基本思路
初始化data数组，申请一个长度为MAX_SIZE的连续空间，top指针为-1，表示栈为空栈
public Stack(){
data = (T[])new Object[MAX_SIZE];
top = -1;
}
入栈
push(T x)
栈顶添加一个T类型元素，栈顶指针更新
基本思路
判断栈是否已满，top == MAX_SIZE-1，如果已满则抛出上溢异常
否则更新指针top++，当前top指针指向位置放置入栈元素
public void push(T x){
if (top == MAX_SIZE - 1){
throw new RuntimeException("栈上溢");
}
data[++top] = x;
}
出栈
pop
弹出栈顶元素并返回
基本思路
判断当前top指针是否为-1，如果为-1则表明栈空，抛出下溢异常
top–更新栈顶指针位置，返回**data[top]**，即原先被删除的栈顶元素
public T pop(){
if (top == -1){
throw new RuntimeException("栈下溢");
}
return data[top--];
}
代码
package com.os467.stack;
public class Stack<T> {
private final int MAX_SIZE = 1024;
//存储栈元素的数组
private T[] data;
//栈顶指针
private int top;
/**
* 无参构造
*/
public Stack(){
data = (T[])new Object[MAX_SIZE];
top = -1;
}
/**
* 将元素x入栈
* @param x
*/
public void push(T x){
if (top == MAX_SIZE - 1){
throw new RuntimeException("栈上溢");
}
data[++top] = x;
}
/**
* 将栈顶元素弹出
* @return
*/
public T pop(){
if (top == -1){
throw new RuntimeException("栈下溢");
}
return data[top--];
}
/**
* 取栈顶元素
* @return
*/
public T getTop(){
if (top == -1){
throw new RuntimeException("栈下溢");
}
return data[top];
}
/**
* 栈判空
* @return
*/
public boolean empty(){
return top == -1;
}
/**
* 返回栈顶指针的值
* @return
*/
public int top(){
return top;
}
/**
* 打印栈元素
*/
public void printStack(){
System.out.println("----top----");
for (int i = top; i >= 0; i--) {
System.out.println(data[i]);
}
System.out.println("---bottom---");
}
}
链式栈
基本属性
- top 栈顶结点指针，指向当前链栈结点
重要方法介绍
无参构造
LinkStack()
创建空栈，top指针指向null即可表示当前栈为空
public LinkStack(){
top = null;
}
入栈
push(T x)
在栈顶插入新结点，赋值数据元素
基本思路
- 创建新结点
创建新结点，为数据域赋值
- 链接
让新结点指针域指向当前栈顶结点
- 栈顶指针更新
让栈顶指针指向新创建的结点
public void push(T x){
//创建新结点
Node<T> s = new Node<>();
//赋值数据元素
s.data = x;
//与当前栈顶元素链接
s.next = top;
//栈顶指针更新为当前入栈元素结点
top = s;
}
出栈
pop()
弹出栈顶元素，更新栈顶指针
基本思路
- 判空
判断当前栈是否为空，top == null 表示栈空，无法弹出元素，抛出异常
- 返回值
保存当前栈顶结点数据域值，返回值
- 删除栈顶元素
创建指针p指向当前栈顶结点
栈顶指针指向当前栈顶结点指针域指向的结点
删除栈顶指针指向的结点
public T pop(){
if (top == null){
throw new RuntimeException("栈下溢");
}
//出栈的值
T data = top.data;
//指向需要被删除的栈顶结点
Node<T> p = top;
//摘除栈顶结点
top = top.next;
//c++ delete p;
return data;
}
代码
package com.os467.stack;
public class LinkStack<T> {
//top栈顶结点
private Node<T> top;
/**
* 无参构造
*/
public LinkStack(){
top = null;
}
/**
* 入栈
* @param x
*/
public void push(T x){
//创建新结点
Node<T> s = new Node<>();
//赋值数据元素
s.data = x;
//与当前栈顶元素链接
s.next = top;
//栈顶指针更新为当前入栈元素结点
top = s;
}
/**
* 出栈
* @return
*/
public T pop(){
if (top == null){
throw new RuntimeException("栈下溢");
}
//出栈的值
T data = top.data;
//指向需要被删除的栈顶结点
Node<T> p = top;
//摘除栈顶结点
top = top.next;
//c++ delete p;
return data;
}
/**
* 获取栈顶元素
* @return
*/
public T getTop() {
if (top == null){
throw new RuntimeException("下溢");
}
return top.data;
}
/**
* 栈判空
* @return
*/
public boolean empty(){
return top == null;
}
class Node<T>{
private T data;
Node<T> next;
}
}
循环队列
基本属性
- MAX_SIZE 申请的最大内存空间
- data 存储数据元素的数组
- front 队头指针，负责元素出队
- rear 队尾指针，负责元素入队
重要方法介绍
无参构造
CirQueue()
创建空循环队列，申请连续空间，front指针和rear指针为0
基本思路
以MAX_SIZE规定大小申请空间，实际可用空间为MAX_SIZE-1，有一格空间会用于区别队满和队空的情况
头指针和尾指针相等为0，表示队空
public CirQueue(){
data = (T[])new Object[MAX_SIZE];
front = 0;
rear = 0;
}
元素入队
enQueue(T x)
判断当前队列是否已满，如果已满则抛出上溢异常，否则队尾指针元素入队，队尾指针更新
基本思路
- 判断是否队满
通过判断(rear+1)%MAX_SIZE == front 可以判断当前位置是否为队列最后一个空位，如果是则不使用，用于区分队满和队空，并抛出上溢异常
- 元素入队
如果不是则说明还有存储空间，元素入队，队尾指针更新
通过取模运算可以避免++rear后大于MAX_SIZE的问题
public void enQueue(T x){
if ((rear+1)%MAX_SIZE == front){
throw new RuntimeException("上溢");
}
data[rear] = x;
rear = ++rear%MAX_SIZE;
}
元素出队
deQueue()
判断当前队是否为空，如果为空则抛出下溢异常，否则保存要出队的元素并返回，队头指针更新
基本思路
- 判断是否队空
通过比较front指针是否和rear指针相等判断是否队空，队空没有队头元素因此无法出队，抛出异常
- 元素出队
如果存在元素则保存队头元素值，更新队头指针，返回出队的值
public T deQueue(){
if (front == rear){
throw new RuntimeException("下溢");
}
T x = data[front];
front = ++front%MAX_SIZE;
return x;
}
判空
empty()
public boolean empty(){
return front == rear;
}
代码
package com.os467.queue;
public class CirQueue<T> {
//申请的最大内存空间
private final int MAX_SIZE = 10;
//存储数据元素的数组
private T[] data;
//队头指针，负责出队
private int front;
//队尾指针，负责入队
private int rear;
/**
* 无参构造函数
*/
public CirQueue(){
data = (T[])new Object[MAX_SIZE];
front = 0;
rear = 0;
}
/**
* 元素入队
* @param x
*/
public void enQueue(T x){
if ((rear+1)%MAX_SIZE == front){
throw new RuntimeException("上溢");
}
data[rear] = x;
rear = ++rear%MAX_SIZE;
}
/**
* 元素出队
* @return
*/
public T deQueue(){
if (front == rear){
throw new RuntimeException("下溢");
}
T x = data[front];
front = ++front%MAX_SIZE;
return x;
}
/**
* 取队头元素(不删除)
* @return
*/
public T getQueue(){
if (front == rear){
throw new RuntimeException("下溢");
}
return data[front];
}
/**
* 取判断队列是否为空
* @return
*/
public boolean empty(){
return front == rear;
}
/**
* 取队头指针值
* @return
*/
public int getFront(){
return front;
}
/**
* 取队尾指针值
* @return
*/
public int getRear(){
return rear;
}
/**
* 打印队列
*/
public void printQueue(){
if (rear > front){
System.out.print("front->");
for (int i = front; i < rear; i++) {
System.out.print(data[i]+",");
}
if (front != rear) {
System.out.print(data[rear]);
}
System.out.println("<-rear");
}else {
System.out.print("rear->");
for (int i = rear; i < front; i++) {
System.out.print(data[i]+",");
}
if (front != rear){
System.out.print(data[rear]);
}
System.out.println("<-front");
}
if (front == rear){
System.out.println("front-><-rear");
}
}
}
链队列
基本属性
- front 队头指针，负责队头元素出队
- rear 队尾指针，负责队尾元素入队
重要方法介绍
无参构造
LinkQueue()
创建空队列，队头和队尾指针都指向头结点，队空
基本思路
创建队头结点，队头指针指向队头结点，队尾指针也指向头结点，头结点指向null
public LinkQueue(){
Node<T> s = new Node<>();
s.next = null;
front = s;
rear = s;
}
入队
enQueue(T x)
基本思路
创建新结点，结点指向null，并为数据域赋值
队尾指针指向结点与此新结点链接，rear->node->new_node
更新当前队尾指针指向新结点rear->new_node
public void enQueue(T x){
//创建新结点
Node<T> s = new Node<>();
s.next = null;
s.data = x;
//链接新建结点
rear.next = s;
//更新队尾指针
rear = s;
}
出队
deQueue()
基本思路
创建p指针指向队头元素结点，p->next_node<-front，即队头结点指向的下一结点，需要出队的结点
判断p节点，如果为null则表明队空，抛出异常
队头结点指向p指针指向结点的下一结点
删除p节点，返回data值
public T deQueue(){
//p指向队头数据元素结点
Node<T> p = front.next;
if (p == null){
throw new RuntimeException("下溢");
}
//更新队头结点指向新的队头数据元素结点
front.next = p.next;
//需要返回的数据元素
T data = p.data;
//c++ delete p
return data;
}
清空队列
sellNullQueue()
基本思路
从第一个元素结点开始遍历，如果为null则停止遍历
遍历过程中用q指针保存需要删除的结点，delete q即可
最后更新尾指针指向头结点，头结点指向null
public void sellNullQueue(){
Node<T> p = front.next;
while (p != null){
Node<T> q = p;
//c++ delete q
p = p.next;
}
//头结点指向null
front.next = null;
//队尾指针指向头结点
rear = front;
}
代码
package com.os467.queue;
public class LinkQueue<T> {
//队头指针
private Node<T> front;
//队尾指针
private Node<T> rear;
/**
* 无参构造
*/
public LinkQueue(){
Node<T> s = new Node<>();
s.next = null;
front = s;
rear = s;
}
/**
* 入队
*/
public void enQueue(T x){
//创建新结点
Node<T> s = new Node<>();
s.next = null;
s.data = x;
//链接新建结点
rear.next = s;
//更新队尾指针
rear = s;
}
/**
* 出队
* @return
*/
public T deQueue(){
//p指向队头数据元素结点
Node<T> p = front.next;
if (p == null){
throw new RuntimeException("下溢");
}
//更新队头结点指向新的队头数据元素结点
front.next = p.next;
//需要返回的数据元素
T data = p.data;
//c++ delete p
return data;
}
/**
* 取队头元素
* @return
*/
public T getQueue(){
if (front.next == null){
throw new RuntimeException("下溢");
}
return front.next.data;
}
/**
* 清空队列
*/
public void sellNullQueue(){
Node<T> p = front.next;
while (p != null){
Node<T> q = p;
//c++ delete q
p = p.next;
}
//头结点指向null
front.next = null;
//队尾指针指向头结点
rear = front;
}
/**
* 判空
* @return
*/
public boolean empty(){
return front == rear;
}
/**
* 打印队列
* @return
*/
public void printQueue(){
Node<T> p = front.next;
System.out.print("front->");
while (p != null){
System.out.print(p.data+"->");
p = p.next;
}
System.out.println("<-rear");
}
class Node<T>{
T data;
Node<T> next;
}
}
二叉树
基本属性
- root 根结点指针
重要方法介绍
无参构造
BinaryTree()
由于二叉树需要递归调用，构造函数无法递归调用，因此需要调用私有方法create来递归构造二叉树
基本思路
create方法返回构造的子树根结点
创建新结点，用户输入值，如果输入’#’代表为空结点，之间返回null
否则为当前结点赋值，然后构造左子树，为左结点赋值，再构造右子树，为右结点赋值
public BinaryTree(){
System.out.println("请输入创建一棵二叉树的结点数据");
root = create();
}
private BinaryNode create(){
BinaryNode r = new BinaryNode<>();
Scanner scanner = new Scanner(System.in);
char ch = scanner.next().charAt(0);
if (ch == '#'){
r = null;
}else {
//为当前结点赋值
r.data = ch;
r.lChild = create();
r.rChild = create();
}
return r;
}
前序遍历
递归遍历
private void preOrder(BinaryNode r){
if (r == null){
return;
}
//访问根结点
System.out.print(r.data);
//访问左子树
preOrder(r.lChild);
//访问右子树
preOrder(r.rChild);
}
非递归遍历
preOrder1(BinaryNode r)
使用到栈来记录访问过的结点
根据前序遍历访问特点：root->left->right进行遍历
基本思路
构造栈，top为-1，此时栈空
进入循环，当前结点不为null或栈记录不为空时不断循环
- 访问根
访问到当前结点（子树根）后使当前结点入栈（右结点暂未访问）
- 访问左
然后进入左子树，直到访问到null节点
- 访问右
然后访问右子树，这之前当前根元素应当出栈（决定访问右子树后当前根结点已无记录作用）
当栈内无结点记录并且当前访问到null则表示所有右子树已经访问完毕，此时前序遍历结束
private void preOrder1(BinaryNode r){
int top = -1;
BinaryNode[] stack = new BinaryNode[100];
while (r != null || top != -1){
while (r != null){
//访问根结点
System.out.print(r.data);
//根结点入栈
stack[++top] = r;
//访问左子树
r = r.lChild;
}
//访问右子树
r = stack[top--].rChild;
}
}
中序遍历
递归遍历
private void inOrder(BinaryNode r){
if (r == null){
return;
}
//访问左子树
inOrder(r.lChild);
//访问根结点
System.out.print(r.data);
//访问右子树
inOrder(r.rChild);
}
非递归遍历
inOrder1(BinaryNode r)
使用到栈来记录访问过的结点
根据前序遍历访问特点：left->root->right进行遍历
基本思路
当前遍历不为null且栈不为空时不断循环
- 访问左
先遍历左子树，不断将结点入栈，当访问到null时，返回栈顶结点
- 访问根
此时访问根结点
- 访问右
然后访问右子树，此时根结点已被访问弹出栈
当栈内无结点记录并且当前访问到null则表示所有右子树已经访问完毕，此时中序遍历结束
private void inOrder1(BinaryNode r){
int top = -1;
BinaryNode[] stack = new BinaryNode[100];
while (r != null || top != -1){
while (r != null){
//结点入栈
stack[++top] = r;
//访问左子树
r = r.lChild;
}
//遇到null返回根
r = stack[top];
//访问根结点
System.out.print(r.data);
//访问右子树，根弹出
r = stack[top--].rChild;
}
}
后续遍历
递归遍历
private void postOrder(BinaryNode r){
if (r == null){
return;
}
//访问左子树
postOrder(r.lChild);
//访问右子树
postOrder(r.rChild);
//访问根结点
System.out.print(r.data);
}
非递归遍历
private void postOrder1(BinaryNode r){
Element[] stack = new Element[100];
int top = -1;
while (r != null || top != -1){
//访问左
while (r != null){
stack[++top].pre = r;
stack[top].flag = 1;
r = r.lChild;
}
//访问完左，判断是否访问过此结点左右
while (top!= -1 && stack[top].flag == 2){
r = stack[top--].pre;
System.out.print(r.data);
r = null;
}
//访问右，设置当前结点记录已访问过左右
if (top != -1){
stack[top].flag = 2;
r = stack[top].pre.rChild;
}
}
}
层序遍历
levelOrder(BinaryNode r)
使用队列进行层序遍历
由于队列先进先出的特点，我们可以让第一个结点先进入队列，然后访问此结点，第一层遍历完毕
然后左结点入队，右结点入队，由于先进先出的特点，下一层遍历也将先访问队列中的左结点，然后让其子结点入队，然后才访问右结点，再让其子结点入队，符合层序遍历的需要
基本思路
- 取队头元素
根结点入队，循环判断队列是否为空，不为空则不断取队头元素
- 访问，左孩子右孩子结点入队
访问队头元素，然后将其左孩子结点插入队尾，再将其右孩子结点插入队尾
- 继续访问，直到队为空退出循环
然后访问下一个队头元素，不断循环直到队为空
public void levelOrder(BinaryNode r){
BinaryNode[] q = new BinaryNode[100];
int front = 0;
int rear = 0;
//根结点入队
q[rear++] = r;
while (front != rear){
//结点出队
BinaryNode s = q[front++];
//此结点不为空
if (s != null){
//访问此结点
System.out.print(s.data);
//左结点入队
q[rear++] = s.lChild;
//右结点入队
q[rear++] = s.rChild;
}
}
System.out.println();
}
代码
package com.os467.tree;
import java.util.Scanner;
public class BinaryTree<T> {
//根指针，指向根结点
private BinaryNode<T> root;
/**
* 递归创建树
*/
private BinaryNode create(){
BinaryNode r = new BinaryNode<>();
Scanner scanner = new Scanner(System.in);
char ch = scanner.next().charAt(0);
if (ch == '#'){
r = null;
}else {
r.data = ch;
r.lChild = create();
r.rChild = create();
}
return r;
}
/**
* 非递归前序遍历
*/
private void preOrder1(BinaryNode r){
int top = -1;
BinaryNode[] stack = new BinaryNode[100];
while (r != null || top != -1){
while (r != null){
//访问根结点
System.out.print(r.data);
//根结点入栈
stack[++top] = r;
//访问左子树
r = r.lChild;
}
//访问右子树
r = stack[top--].rChild;
}
}
/**
* 非递归中序遍历
*/
private void inOrder1(BinaryNode r){
int top = -1;
BinaryNode[] stack = new BinaryNode[100];
while (r != null || top != -1){
while (r != null){
//结点入栈
stack[++top] = r;
//访问左子树
r = r.lChild;
}
//遇到null返回根
r = stack[top];
//访问根结点
System.out.print(r.data);
//访问右子树，根弹出
r = stack[top--].rChild;
}
}
/**
* 递归前序遍历
* @param r
*/
private void preOrder(BinaryNode r){
if (r == null){
return;
}
//访问根结点
System.out.print(r.data);
//访问左子树
preOrder(r.lChild);
//访问右子树
preOrder(r.rChild);
}
/**
* 递归中序遍历
* @param r
*/
private void inOrder(BinaryNode r){
if (r == null){
return;
}
//访问左子树
inOrder(r.lChild);
//访问根结点
System.out.print(r.data);
//访问右子树
inOrder(r.rChild);
}
/**
* 递归后序遍历
* @param r
*/
private void postOrder(BinaryNode r){
if (r == null){
return;
}
//访问左子树
postOrder(r.lChild);
//访问右子树
postOrder(r.rChild);
//访问根结点
System.out.print(r.data);
}
/**
* 层序遍历
*/
public void levelOrder(BinaryNode r){
BinaryNode[] q = new BinaryNode[100];
int front = 0;
int rear = 0;
//根结点入队
q[rear++] = r;
while (front != rear){
//结点出队
BinaryNode s = q[front++];
//此结点不为空
if (s != null){
//访问此结点
System.out.print(s.data);
//左结点入队
q[rear++] = s.lChild;
//右结点入队
q[rear++] = s.rChild;
}
}
System.out.println();
}
/**
* 无参构造
*/
public BinaryTree(){
System.out.println("请输入创建一棵二叉树的结点数据");
root = create();
}
/**
* 获取根结点
* @return
*/
public BinaryNode<T> getRoot(){
return root;
}
/**
* 设置根结点
* @param r
*/
public void putRoot(BinaryNode<T> r){
root = r;
}
/**
* 前序遍历
*/
public void preOrder(){
System.out.print("递归：");
preOrder(root);
System.out.println();
System.out.print("非递归：");
preOrder1(root);
System.out.println();
}
/**
* 中序遍历
*/
public void inOrder(){
System.out.print("递归：");
inOrder(root);
System.out.println();
System.out.print("非递归：");
inOrder1(root);
System.out.println();
}
/**
* 后序遍历
*/
public void postOrder(){
System.out.print("递归：");
postOrder(root);
System.out.println();
}
/**
* 层序遍历
*/
public void levelOrder(){
levelOrder(root);
}
class BinaryNode<T>{
private T data;
private BinaryNode<T> lChild;
private BinaryNode<T> rChild;
}
}
无向图
基本属性
- adjacencyList 存放顶点表的数组
- vertexNum 点数量
- edgeNum 边数量
重要方法介绍
有参构造
UndirectedGraphInAdjacencyList(T[] a,int n,int e)
需要提供一个T类型的顶点元素数据数组，还需要提供顶点个数，初始边个数默认为0
基本思路
创建一个MAX_SIZE大小的顶点表数组adjacencyList，并根据数组a为其设置顶点数据域值，其指针域指向null
初始化边数和顶点数
初始化访问表示数组visited
/**
* 有参构造函数
*/
public UndirectedGraphInAdjacencyList(T[] a,int n,int e){
vertexNum = n;
edgeNum = e;
adjacencyList = new VertexNode[MAX_SIZE];
visited = new boolean[MAX_SIZE];
for (int i = 0; i < n; i++) {
//创建新顶点，将顶点加入顶点表
adjacencyList[i] = new VertexNode<>();
//为顶点数据域赋值
adjacencyList[i].vertexInfo = a[i];
//边表头指针为空
adjacencyList[i].firstEdge = null;
}
}
插入边
insertEdge(int i, int j)
基本思路
分别为i索引位置和j索引位置的顶点创建新结点，执行以下逻辑：
- 创建新结点，顶点域赋值为需要指向的顶点索引值
- 新结点继承当前顶点边表的头指针
- 让当前顶点边表头指针指向新结点
边数量增加
/**
* 在两个顶点之间建立无向边
* @param i
* @param j
*/
public void insertEdge(int i, int j){
//创建新边结点
EdgeNode edgeNodeI = new EdgeNode();
//顶点域赋值
edgeNodeI.vertexIndex = j;
//继承头指针
edgeNodeI.next = adjacencyList[i].firstEdge;
adjacencyList[i].firstEdge = edgeNodeI;
EdgeNode edgeNodeJ = new EdgeNode<>();
edgeNodeJ.vertexIndex = i;
edgeNodeJ.next = adjacencyList[j].firstEdge;
adjacencyList[j].firstEdge = edgeNodeJ;
edgeNum++;
}
深度优先遍历
基本思路
先将使用过的visited标记位重置
将0号顶点作为起始顶点开始遍历
每次遍历完毕，再从表中挑选未遍历到的顶点作为新的遍历起始顶点
private void resetVisited() {
for (int i = 0; i < visited.length; i++) {
visited[i] = false;
}
}
/**
* 深度优先遍历
*/
public void dfs(){
System.out.println("递归深度优先遍历：");
//设置未访问
resetVisited();
for (int i = 0; i < vertexNum; i++) {
if (visited[i] == false){
dfs(i);
}
}
System.out.println();
System.out.println("非递归深度优先遍历：");
//设置未访问
resetVisited();
for (int i = 0; i < vertexNum; i++) {
if (visited[i] == false){
dfs1(i);
}
}
System.out.println();
}
递归遍历
dfs(int vertex)
基本思路
判断
- 判断顶点索引值是否合理，如果不合理则抛出异常
访问
- 访问顶点数据域
- 更新此顶点所对应的访问标记
- 获取到边表头节点
遍历递归
- 遍历边表
- 获取到未访问过边表节点存储的顶点索引
- 访问连接的顶点，进入下一层，递归调用
- 递归完毕，在这一层继续遍历
private void dfs(int vertex) {
if (vertex <0 || vertex >= vertexNum){
throw new RuntimeException("位置错误");
}
visited[vertex] = true;
EdgeNode p = adjacencyList[vertex].firstEdge;
//打印遍历到的值
System.out.print(adjacencyList[vertex].vertexInfo);
//遍历边表
while (p != null){
int to = p.vertexIndex;
//进入未访问过的顶点进行递归遍历
if (visited[to] == false){
dfs(to);
}
p = p.next;
}
}
非递归遍历
dfs1(int vertex)
使用栈来实现非递归的深度优先遍历
基本思路
创建栈
- 创建顶点个数的栈空间，第一个遍历顶点入栈，访问第一个顶点数据域
深度优先遍历
- 循环直到栈空
遍历边表
设置边表遍历结束标记位为0（当前深度是否全部遍历完毕），用来控制栈顶元素出栈
遍历边表
访问未遍历到的顶点，设置边表遍历结束标记位为1，打破当前层边表遍历循环，遍历新顶点边表
若边表遍历结束，则弹出栈顶元素，继续深度优先遍历上一层未遍历到的边表顶点
private void dfs1(int vertex) {
int[] s = new int[vertexNum];
int top = -1;
s[++top] = vertex;
visited[vertex] = true;
System.out.print(adjacencyList[vertex].vertexInfo);
EdgeNode p;
while (top != -1){
int tag = 0;
p = adjacencyList[s[top]].firstEdge;
while (p != null){
int v = p.vertexIndex;
if (visited[v] == true){
//寻找连通的下一层深度结点
p = p.next;
}else {
//搜索到下一层深度结点，打破本层寻找循环
visited[v] = true;
System.out.print(adjacencyList[v].vertexInfo);
s[++top] = v;
tag = 1;
break;
}
}
//非深度搜索打破循环，本层深度搜索结束，弹出栈顶顶点元素
if (tag == 0){
top--;
}
}
}
广度优先遍历
bfs()
先将使用过的visited标记位重置
将0号顶点作为起始顶点开始遍历
每次遍历完毕，再从表中挑选未遍历到的顶点作为新的遍历起始顶点
/**
* 广度优先遍历
*/
public void bfs(){
System.out.println("广度优先遍历：");
//设置未访问
resetVisited();
for (int i = 0; i < vertexNum; i++) {
if (visited[i] == false){
bfs(i);
}
}
System.out.println();
}
bfs(int vertex)
使用队列来实现广度优先遍历
基本思路
创建队列
- 创建一个顶点个数长度的队列
- 将第一个顶点放入队列，访问顶点值，设置访问标记位
遍历队列
- 弹出队头元素，拿到边表指针，遍历边表
- 判断边表顶点是否访问过，若未访问则访问此顶点，更新访问标记位
- 将此顶点加入队列
- 循环直到队列为空
private void bfs(int vertex) {
int[] q = new int[vertexNum];
int rear = 0;
int front = 0;
if (vertex <0 || vertex >= vertexNum){
throw new RuntimeException("位置错误");
}
//将结点放入队列
q[rear++] = vertex;
System.out.print(adjacencyList[vertex].vertexInfo);
visited[vertex] = true;
while (front != rear){
int v = q[front++];
EdgeNode p = adjacencyList[v].firstEdge;
while (p != null){
int to = p.vertexIndex;
if (visited[to] == false){
visited[to] = true;
System.out.print(adjacencyList[to].vertexInfo);
//下一层需要遍历的
q[rear++] = to;
}
//遍历这一层
p = p.next;
}
}
}
代码
package com.os467.graph;
public class UndirectedGraphInAdjacencyList<T> {
public static final int MAX_SIZE = 20;
/**
* 表头结点
*/
class VertexNode<T>{
//顶点信息
T vertexInfo;
//边表头指针
EdgeNode firstEdge;
}
/**
* 边表结点
*/
class EdgeNode<T>{
//邻接结点域
int vertexIndex;
//下一边结点
EdgeNode next;
}
//存放顶点表的数组
private VertexNode<T>[] adjacencyList;
//顶点数量
private int vertexNum;
//边数量
private int edgeNum;
private boolean[] visited;
/**
* 无参构造函数
*/
public UndirectedGraphInAdjacencyList(){
vertexNum = 0;
edgeNum = 0;
adjacencyList = new VertexNode[MAX_SIZE];
visited = new boolean[MAX_SIZE];
}
/**
* 有参构造函数
*/
public UndirectedGraphInAdjacencyList(T[] a,int n,int e){
vertexNum = n;
edgeNum = e;
adjacencyList = new VertexNode[MAX_SIZE];
visited = new boolean[MAX_SIZE];
for (int i = 0; i < n; i++) {
//创建新顶点，将顶点加入顶点表
adjacencyList[i] = new VertexNode<>();
//为顶点数据域赋值
adjacencyList[i].vertexInfo = a[i];
//边表头指针为空
adjacencyList[i].firstEdge = null;
}
}
/**
* 在两个顶点之间建立无向边
* @param i
* @param j
*/
public void insertEdge(int i, int j){
//创建新边结点
EdgeNode edgeNodeI = new EdgeNode();
//顶点域赋值
edgeNodeI.vertexIndex = j;
//继承头指针
edgeNodeI.next = adjacencyList[i].firstEdge;
adjacencyList[i].firstEdge = edgeNodeI;
EdgeNode edgeNodeJ = new EdgeNode<>();
edgeNodeJ.vertexIndex = i;
edgeNodeJ.next = adjacencyList[j].firstEdge;
adjacencyList[j].firstEdge = edgeNodeJ;
edgeNum++;
}
/**
* 深度优先遍历
*/
public void dfs(){
System.out.println("递归深度优先遍历：");
//设置未访问
resetVisited();
for (int i = 0; i < vertexNum; i++) {
if (visited[i] == false){
dfs(i);
}
}
System.out.println();
System.out.println("非递归深度优先遍历：");
//设置未访问
resetVisited();
for (int i = 0; i < vertexNum; i++) {
if (visited[i] == false){
dfs1(i);
}
}
System.out.println();
}
private void dfs1(int vertex) {
int[] s = new int[vertexNum];
int top = -1;
s[++top] = vertex;
visited[vertex] = true;
System.out.print(adjacencyList[vertex].vertexInfo);
EdgeNode p;
while (top != -1){
int tag = 0;
p = adjacencyList[s[top]].firstEdge;
while (p != null){
int v = p.vertexIndex;
if (visited[v] == true){
//寻找连通的下一层深度结点
p = p.next;
}else if (v != 0){
//搜索到下一层深度结点，打破本层寻找循环
visited[v] = true;
System.out.print(adjacencyList[v].vertexInfo);
s[++top] = v;
tag = 1;
break;
}
}
//非深度搜索打破循环，本层深度搜索结束，弹出栈顶顶点元素
if (tag == 0){
top--;
}
}
}
private void resetVisited() {
for (int i = 0; i < visited.length; i++) {
visited[i] = false;
}
}
private void dfs(int vertex) {
if (vertex <0 || vertex >= vertexNum){
throw new RuntimeException("位置错误");
}
visited[vertex] = true;
EdgeNode p = adjacencyList[vertex].firstEdge;
//打印遍历到的值
System.out.print(adjacencyList[vertex].vertexInfo);
while (p != null){
int to = p.vertexIndex;
if (visited[to] == false && to != 0){
dfs(to);
}
p = p.next;
}
}
/**
* 广度优先遍历
*/
public void bfs(){
System.out.println("广度优先遍历：");
//设置未访问
resetVisited();
for (int i = 0; i < vertexNum; i++) {
if (visited[i] == false){
bfs(i);
}
}
System.out.println();
}
private void bfs(int vertex) {
int[] q = new int[vertexNum];
int rear = 0;
int front = 0;
if (vertex <0 || vertex >= vertexNum){
throw new RuntimeException("位置错误");
}
//将结点放入队列
q[rear++] = vertex;
System.out.print(adjacencyList[vertex].vertexInfo);
visited[vertex] = true;
while (front != rear){
int v = q[front++];
EdgeNode p = adjacencyList[v].firstEdge;
while (p != null){
int to = p.vertexIndex;
if (visited[to] == false && to != 0){
visited[to] = true;
System.out.print(adjacencyList[to].vertexInfo);
//下一层需要遍历的
q[rear++] = to;
}
//遍历这一层
p = p.next;
}
}
}
/**
* 拿到顶点个数
* @return
*/
public int getVertexNum() {
return vertexNum;
}
/**
* 拿到边的个数
* @return
*/
public int getEdgeNum() {
return edgeNum;
}
public static void main(String[] args) {
Integer[] integers = new Integer[8];
for (int i = 0; i < integers.length; i++) {
integers[i] = i;
}
UndirectedGraphInAdjacencyList<Integer> graph = new UndirectedGraphInAdjacencyList<>(integers,integers.length,0);
graph.insertEdge(0,7);
graph.insertEdge(0,6);
graph.insertEdge(0,5);
graph.insertEdge(5,4);
graph.insertEdge(5,3);
graph.insertEdge(5,2);
graph.insertEdge(2,1);
graph.dfs();
graph.bfs();
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以邮件至 1300452403@qq.com
