tonglin0325的个人主页

Java数据结构——哈夫曼树(Huffman Tree)

1.哈夫曼树#

给定N个权值作为N个叶子节点,构造一棵二叉树,若该树的带权路径长度****(WPL)达到最小,称这样的二叉树为最优二叉树,也称为**哈夫曼树(Huffman Tree)**。

哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。

参考:霍夫曼树(参考该文章中的概念,其中代码不对)

2.树的带权路径长度(WPL,Weighted Path Length of Tree)#

树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)

如下图中的哈夫曼树,其WPL的值 = (2+3) * 3 + 4 * 2 + 6 * 1 = 29

上图参考:数据结构——哈夫曼树(Huffman Tree)

3.哈夫曼树的应用#

1.哈夫曼编码#

4.哈夫曼编码的实现#

1.哈夫曼编码的步骤:#

  • 根据输入的字符构建哈夫曼树
      1. 统计原始数据中各字符出现的频率; 1. 所有字符按频率降序排列; 1. 建立哈夫曼树:
      1. 将哈夫曼树存入结果数据;
      2. 重新编码原始数据到结果数据

      2.建立哈夫曼树的步骤:#

      1. 初始化:由给定的 N 个权值构造 N 棵只有一个根节点的二叉树,得到一个二叉树集合
      2. 选取与合并:从二叉树集合 PriorityQueue 中选取根节点权值 最小的两棵 二叉树分别作为左右子树构造一棵新的二叉树,这棵新二叉树的根节点的权值为其左、右子树根结点的权值和。
      3. 删除与加入:从 PriorityQueue 中删除作为左、右子树的两棵二叉树,并将新建立的二叉树加入到 PriorityQueue 中。
      4. 重复 2、3 步,当集合中只剩下一棵二叉树时,这棵二叉树就是霍夫曼树。

      3.代码实现:#

      下面的2个网站中的实现都差不多,都借助了优先队列来进行排序(java是PriorityQueue,python是heapq)

  • Java数据结构——有序链表

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    class SortedList{
    private Link_long first;

    public SortedList(){ //构造函数
    first = null;
    }

    public void insert(long key){
    Link_long newLink = new Link_long(key);
    Link_long previous = null; //上一次插入的值
    Link_long current = first; //每插入一次,current就重新赋为表头的值
    while(current != null && key > current.dData){ //没进入这里,pre就是null,也就只进入下面if的上一层
    previous = current;
    current = current.next; //current的位置往后移动
    }
    if(previous == null){ //最开始的情况,给first赋值为newLink,即key
    first = newLink;
    }else{ //
    previous.next = newLink;
    }
    newLink.next = current;
    }

    public long remove(){
    Link_long temp = first;
    first = first.next;
    return temp.dData;
    }

    public void displayList(){
    System.out.println("List (first-->last)");
    Link_long current = first;
    while(current != null){
    current.displayLink();
    current = current.next;
    }
    }

    }

    public class SortedList_demo {

    public static void main(String[] args) {
    // TODO 自动生成的方法存根
    SortedList theSortedList = new SortedList();
    theSortedList.insert(10);
    theSortedList.insert(20);
    theSortedList.insert(30);
    theSortedList.displayList();
    theSortedList.remove();
    theSortedList.remove();
    theSortedList.displayList();
    }

    }

    全文 >>

    Java数据结构——用双端链表实现队列

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    class FirstLastList_long{
    private Link_long first;
    private Link_long last;

    public FirstLastList_long() { //构造函数
    this.first = null;
    this.last = null;
    }

    public boolean isEmpty(){
    return (first == null);
    }

    public void insertFirst(long dd){ //从链表的头开始插入
    Link_long newLink = new Link_long(dd);
    if(isEmpty()){
    last = newLink; //不用改变first
    }
    newLink.next = first;
    first = newLink;
    }

    public void insertLast(long dd){ //从链表的尾开始插入
    Link_long newLink = new Link_long(dd);
    if(isEmpty()){
    first = newLink; //不用改变last
    }else{
    last.next = newLink; //在last后面添加新元素,并修改last的位置
    }
    last = newLink; //注意:只有一个元素的时候,插入要把last也赋为newLink
    }

    public long deleteFirst(){
    Link_long temp = first; //暂存first
    if(first.next == null){ //如果只有一个元素,把last也赋为null
    last = null;
    }
    first = first.next; //把next设为first
    return temp.dData; //返回原来的first
    }

    public void displayList(){
    System.out.println("List(first-->last):");
    Link_long current = first; //用于不断改变位置实现遍历
    while(current != null){
    current.displayLink();
    current = current.next;
    }
    }

    }

    class LinkQueue{
    private FirstLastList_long theList;

    public LinkQueue() { //构造函数
    theList = new FirstLastList_long(); //创建一个双端链表对象
    }

    public void push(long j){ //从链表的尾开始插入,新来的元素在尾部
    theList.insertLast(j);
    }

    public long pop(){
    return theList.deleteFirst(); //从链表的头开始弹出,先进的元素先被弹出
    }

    public boolean idEmpty(){
    return theList.isEmpty();
    }

    public void displayQueue(){
    System.out.println("Queue (front-->rear)");
    theList.displayList();
    }
    }

    public class LinkQueue_demo {

    public static void main(String[] args) {
    // TODO 自动生成的方法存根
    LinkQueue theQueue = new LinkQueue();
    theQueue.push(10);
    theQueue.push(20);
    theQueue.push(30);
    theQueue.displayQueue();

    theQueue.pop();
    theQueue.pop();
    theQueue.displayQueue();
    }

    }

    全文 >>

    Java数据结构——用链表实现栈

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    class Link_long{	//链节点类
    public long dData;
    public Link_long next; //链表中下一个节点的引用

    public Link_long(long dData) {
    super();
    this.dData = dData;
    }

    public void displayLink(){ //显示当前节点的值
    System.out.println("dData"+dData);
    }

    }

    class LinkList_long{
    private Link_long first; //只需要第一个节点,从第一个节点出发即可定位所有节点

    public LinkList_long() { //构造函数
    this.first = null;
    }

    public boolean isEmpty(){
    return (first == null);
    }

    public void insertFirst(long dd){ //插入元素是从链表的头开始插入
    Link_long newLink = new Link_long(dd);
    newLink.next = first;
    first = newLink;
    }

    public long deleteFirst(){ //删除temp.dData
    Link_long temp = first; //暂存first
    first = first.next; //把next设为first
    return temp.dData; //返回原来的first
    }

    public void displayList(){
    System.out.println("List(first-->last):");
    Link_long current = first; //用于不断改变位置实现遍历
    while(current != null){
    current.displayLink();
    current = current.next;
    }
    }

    public Link_long find(int key){ //查找指定的关键字
    Link_long current = first;
    while(current.dData != key){
    if(current.next == null)
    return null;
    else
    current = current.next;
    }
    return current;
    }

    public Link_long delete(int key){ //如果current的值匹配,则删除
    Link_long current = first;
    Link_long previous = first;
    //没有匹配到值
    while(current.dData != key){
    if(current.next == null)
    return null;
    else{ //pre和cur向后移动
    previous = current;
    current = current.next;
    }
    }
    //匹配到值
    if(current == first) //只有一个first,并匹配,则把first设成first.next
    first = first.next;
    else //current的值匹配,则删除,并把cur的next赋给pre的next
    previous.next = current.next;
    return current;
    }
    }

    class LinkStack{ //用链表实现栈,链表从First开始插入,新的元素将变成First,先删除后来元素

    private LinkList_long theList;

    public LinkStack() { //构造函数
    theList = new LinkList_long();
    }

    public void push(long j){ //入栈,即在链表的First插入元素
    theList.insertFirst(j);
    }

    public long pop(){ //出栈,即删除链表的First元素
    return theList.deleteFirst();
    }

    public boolean isEmpty(){ //判断栈是否为空,即判断链表是否为空
    return (theList.isEmpty());
    }

    public void displayStack(){
    System.out.println("Stack(top-->bottom):");
    theList.displayList();
    }

    }

    public class LinkStack_demo {

    public static void main(String[] args) {
    // TODO 自动生成的方法存根
    LinkStack theStack = new LinkStack();
    theStack.push(10);
    theStack.push(20);
    theStack.push(30);
    theStack.displayStack();

    theStack.pop();
    theStack.pop();
    theStack.displayStack();
    }

    }

    全文 >>

    Ubuntu16.04离线安装python3.8

    1.下载python3.8

    1
    2
    3
    cd ~/Download
    wget https://www.python.org/ftp/python/3.8.11/Python-3.8.11.tgz

    解压

    1
    2
    tar -zxvf Python-3.8.11.tgz

    2.创建目录

    1
    2
    3
    4
    5
    cd /usr/local
    sudo mkdir python
    cd ./python
    sudo mkdir python3.8

    3.编译安装

    1
    2
    3
    4
    ./configure prefix=/usr/local/python/python3.8 --enable-optimizations
    make -j 2
    make altinstall >&1|tee make.log

    4.配置环境变量

    1
    2
    3
    # python
    export PATH=$PATH:/usr/local/python/python3.8/bin

    参考:Ubuntu16.04安装Python3.8,3.7,3.9(含卸载方法,支持多版本共存)

    Java排序算法——插入排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    import java.util.Arrays;

    class Arrays_Insert{
    private int[] arrays;
    private int curNum;

    public Arrays_Insert(int max) { //建立一个max长度的空数组
    super();
    arrays = new int[max];
    curNum = 0;
    }

    public void insert(int value){ //往空的数组里面增加元素
    arrays[curNum] = value;
    curNum++;
    }

    public void display(){ //显示数组
    System.out.println(Arrays.toString(arrays));
    }

    private void swap(int one,int two){ //交换
    int temp = arrays[one];
    arrays[one] = arrays[two];
    arrays[two] = temp;
    }

    public void InsertSort(){
    int out,in;

    for(out=1;out<curNum;out++){ //从第2个开始,和第1个比较
    int temp = arrays[out];
    in = out;                        //in等于out,比较从in-1开始
    while(in>0 &amp;&amp; arrays[in-1] >= temp){ //如果大于temp,就往右移动
    arrays[in] = arrays[in-1];        例如:2 3 1 temp=1 -> 2 3 3 temp=1 -> 2 2 3 temp=1 -> 1 2 3 temp=1
    --in;
    }
    arrays[in] = temp;
    }
    }

    }

    public class Insert_Sort {

    public static void main(String[] args) {
    // TODO 自动生成的方法存根
    int maxSize = 100;
    Arrays_Insert arrays_demo = new Arrays_Insert(maxSize);
    arrays_demo.insert(58);
    arrays_demo.insert(57);
    arrays_demo.insert(56);
    arrays_demo.insert(60);
    arrays_demo.insert(59);
    arrays_demo.display();
    arrays_demo.InsertSort();
    arrays_demo.display();
    }

    }

    全文 >>

    Java数据结构——优先级队列

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    class PriorityQueue{
    private int maxSize; //队列的长度
    private long[] queueArray; //创建队列的数组的引用
    private int curNum; //创建当前元素的个数

    public PriorityQueue(int s) { //构造函数
    this.maxSize = s;
    queueArray = new long[maxSize]; //创建对象
    curNum = 0; //当前的元素的个数是0
    }

    public void insert(long item){
    int j;
    if(curNum == 0){ //输入1个数,就是1个数
    queueArray[curNum++] = item;
    }else{ //左边是rear,右边是front,左边总比右边大
    for(j=curNum-1;j>=0;j--){ //当有2个数时,若第2个数比第1个数大,则交换
    if(item>queueArray[j]){ //j在-1的时候停止,rear=0,front=curNum-1
    queueArray[j+1] = queueArray[j]; // 1 2 -> 1 1 -> 2 1
    }else{break;} // 2 1 3 -> 2 1 1 -> 2 2 1 -> 3 2 1
    }
    queueArray[j+1] = item;
    curNum++;
    }

    }

    public long remove(){
    return queueArray[--curNum];
    }

    public long peekFront(){
    return queueArray[curNum-1];
    }

    public boolean isEmpty(){
    return (curNum==0);
    }

    public boolean isFull(){
    return (curNum==maxSize);
    }


    }

    public class PriorityQueue_demo {

    public static void main(String[] args) {
    // TODO 自动生成的方法存根
    PriorityQueue queue_demo = new PriorityQueue(5);
    queue_demo.insert(30);
    queue_demo.insert(10);
    queue_demo.insert(50);
    queue_demo.insert(40);
    queue_demo.insert(20);
    while( !queue_demo.isEmpty()){
    long value = queue_demo.remove();
    System.out.println(value+"、");
    }
    }

    }

    全文 >>