IT源码网

数据结构(四):符号表讲解

sanshao 2021年06月22日 编程语言 190 0

数据结构(四):符号表

一、 符号表概述

  符号表是存储键及对应值的数据结构,符号表中存储的元素由键,值和指向下一个值的指针域组成,可通过键查找到对应的值。

  符号表中,键必须是唯一的,而值可以不唯一。

  日常生活中,根据关键字百度查找资料,根据目录查找书籍内容,都是符号表使用的体现。

   

二、 符号表的构造

public class Node<Key, Value> {

// 符号表key

public Key key;

// 符号表value

public Value value;

// 指向下一个结点

public Node next;

public Node(Key key, Value value, Node next) {

       this.key = key;

       this.value = value;

       this.next = next;

}

public static void main(String[] args) {

       Node node1 = new Node(1, "A", null);

       Node node2 = new Node(2, "B", null);

       Node node3 = new Node(3, "C", null);

       Node node4 = new Node(4, "D", null);

      

       node1.next = node2;

       node2.next = node3;

       node3.next = node4;

}

}

      

三、 无序符号表

public class SymbolTable<Key,Value> {

      

       //声明头结点

       public Node head;

      

       //元素个数

       public int N;

      

       public SymbolTable() {

              head = new Node(null,null,null);

              N=0;

       }

      

       /**

        * 符号表大小

        * @return

        */

       public int size() {

              return N;

       }

      

       /**

        * 符号表是否为空

        * @return

        */

       public boolean isEmpty() {

              return N==0;

       }

      

       /**

        * 根据key获取value

        * @param key

        * @return

        */

       public Value get(Key key) {

              Node node = head;

              while(node.next!=null) {

                     node = node.next;

                     if(node.key.equals(key)) {

                            return (Value) node.value;

                     }

              }

              return null;

       }

      

       /**

        * 根据key删除value

        * @param key

        */

       public void del(Key key) {

              Node node = head;

              while(node.next!=null) {

                     if(node.next.key.equals(key)) {

                            node.next = node.next.next;

                            N--;

                            return;

                     }

                     node = node.next;

              }

       }

      

       /**

        * 存储键值对

        * @param key

        * @param value

        */

       public void put(Key key,Value value) {

              //符号表中已经存在相同key的情况,替换value值

              Node node = head;

              while(node.next!=null) {

                     node = node.next;

                     if(node.key.equals(key)) {

                            node.value = value;

                            return;

                     }

              }

             

              //符号表中不存在相同key的情况,新增value值

              Node firstNode = head.next;

              Node newFirstNode = new Node(key, value, firstNode);

              head.next = newFirstNode;

             

              N++;

       }

}

 

四、 有序符号表  

  上述的符号表,插入元素时没有根据key进行排序,是无序的。

  日常使用中,会出现需要根据key进行排序的需求,实现思路是在put方法时,去遍历比较key当前结点的key大小,当key当前结点key大时则继续往下走,走到发现没有比key大的当前结点时

  比较两个key是否相等,是则替换value,不是则新增结点,并实现连接。

public class OrderSymbolTable<Key extends Comparable<Key>,Value>{

      

       //声明头结点

       public Node head;

      

       //元素个数

       public int N;

      

       public OrderSymbolTable() {

              head = new Node(null,null,null);

              N=0;

       }

      

       /**

        * 符号表大小

        * @return

        */

       public int size() {

              return N;

       }

      

       /**

        * 符号表是否为空

        * @return

        */

       public boolean isEmpty() {

              return N==0;

       }

      

       /**

        * 根据key获取value

        * @param key

        * @return

        */

       public Value get(Key key) {

              Node node = head;

              while(node.next!=null) {

                     node = node.next;

                     if(node.key.equals(key)) {

                            return (Value) node.value;

                     }

              }

              return null;

       }

      

       /**

        * 根据key删除value

        * @param key

        */

       public void del(Key key) {

              Node node = head;

              while(node.next!=null) {

                     if(node.next.key.equals(key)) {

                            node.next = node.next.next;

                            N--;

                            return;

                     }

                     node = node.next;

              }

       }

      

       /**

        * 存储键值对

        * @param key

        * @param value

        */

       public void put(Key key,Value value) {

              Node curr = head.next;

              Node pre = head;

             

              //发现比符号表中存储的key大,则继续遍历

              while(curr != null && key.compareTo((Key) curr.key)>0) {

                     pre = curr;

                     curr = curr.next;

              }

             

              //上述遍历完成后会出现两种情况

              //1、出现key相等的情况

              if(curr != null && key.equals((Key) curr.key)) {

                     curr.value = value;

                     return;

              }

             

              //2、没有key相等的情况

              Node newNode = new Node<Key, Value>(key, value, curr);

              pre.next = newNode;

             

              N++;

       }

}


发布评论
IT源码网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

数据结构(三):线性表-栈,队列讲解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。