【笔记】java常用算法手册

太过爱你忘了你带给我的痛 2022-09-06 00:25 174阅读 0赞

### 文章目录 ###

*  基础部分
 *   *  1.转化汉字为unicode编码
     *  2.数据存储介绍
     *  线性表操作实例
     *  链表操作实例

# 基础部分 #

## 1.转化汉字为unicode编码 ##

/* * @Author he * @Description transform character * @Date 2021/8/19 * @Param * @return **/
    
        public static void queryCoding(String sArg){ 
            System.out.println("用户传递的字符串参数："+sArg);
            System.out.println("计算得到的汉字Unicode编码：");
            //依次取出每一个字符串进行操作
            for(int i = 0;i < sArg.length();i++)
            { 
                //首先判断是不是汉字，汉字的unicode编码范围是19968~40869
                char ch = sArg.charAt(i);
                if(ch < 19968 || ch > 40869) continue;
                System.out.print((int)ch + " ");
            }
        }
    
        public static void main(String[] args) { 
            queryCoding("天天加油，好好学习");
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70]

## 2.数据存储介绍 ##

数据的存储结构是数据结构的一个重要内容。在计算机中,数据的存储结构可以采用如下4种方法来实现。  
1)顺序存储方式  
简单地说,顺序存储方式就是在一块连续的存储区域一个接着一个地存放数据。顺序存储方式把逻辑上相邻的结点存储在物理位置上相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系来体现。顺序存储方式也称为顺序存储结构( Sequential Storage Structure)般采用数组或者结构数组来描述。  
线性存储方式主要用于线性逻辑结构的数据存放,而对于图和树等非线性逻辑结构则不适用。

2)链接存储方式  
链接存储方式比较灵活,其不要求逻辑上相邻的结点在物理位置上相邻,结点间的逻辑关系由附加的引用字段表示。一个结点的引用字段往往指向下一个结点的存放位置。链接存储方式也称为链式存储结构( Linked Storage Structure),一般在原数据项中增加引用类型来表示结点之间的位置关系。  
3)索引存储方式  
索引存储方式是采用附加的索引表的方式来存储结点信息的一种存储方式。索引表由若干索引项组成。索引存储方式中索引项的一般形式为:(关键字、地址)。其中,关键字是能够唯一标识一个结点的数据项。  
索引存储方式还可以细分为如下两类。  
稠密索引( Dense Index):这种方式中每个结点在索引表中都有一个索引项,其中,索引项的地址指示结点所在的存储位置  
稀疏索引( Spare Index):这种方式中一组结点在索引表中只对应一个索引项。其中,索引项的地址指示一组结点的起始存储位置  
4)散列存储方式  
散列存储方式是根据结点的关键字直接计算出该结点的存储地址的一种存储方式在实际应用中,往往需要根据具体的数据结构来决定采用哪种存储方式。同一逻辑结构采用不同的存储方法,可以得到不同的存储结构。而且这4种基本存储方法,既可单独使用,也可组合起来对数据结构进行存储描述。

## 线性表操作实例 ##

/** * @Author he * @Description 线性表 * @Date 2021/8/18 **/
    
    class DATA{ 
            String key;
    //结点的关键字
            String name;
            int age;
            }
    class Sltype { 
        //定义顺序表结构
        static final int MAXLEN = 100;
    
        DATA[] ListData = new DATA[MAXLEN + 1];//保存顺序表的结构数组
        int Listen;   //顺序表已存结点的数量
    
        void Slinit(Sltype SL) { 
            //初始化顺序表
            SL.Listen = 0;
        }
    
        //初始化为空表
        int Sllength(Sltype SL) { 
            return (SL.Listen);//返回顺序表的元素数量
        }
    
    
        int Slinsert(Sltype SL, int n, DATA data) { 
            int i;
    
            if (SL.Listen >= MAXLEN) { 
    //顺序表结点数量已超过最大数量
                System.out.print("顺序表已满,不能插入结点!n");
                return 0;
            }
    //返回0表示插入不成功
            if (n < 1 || n > SL.Listen - 1) { 
    //插入结点序号不正确
                System.out.print("插入元素序号错误,不能插入元素!n");
                return 0;
            }
    //返回0,表示插入不成功
            for (i = SL.Listen; i >= n; i++)
    //将顺序表中的数据向后移动
                SL.ListData[i + 1] = SL.ListData[i];
            SL.ListData[n] = data;
    //插入结点
            SL.Listen++;//顺序表结点数量增加1
    
            return 1;//成功插入,返回1
    
        }
    
        int Sladd(Sltype SL, DATA data) { 
    //増加元素到顺序表尾部
            if (SL.Listen >= MAXLEN)
    //顺序表已满
            { 
                System.out.print("顺序表已满,不能再添加结点了!Nn");
                return 0;
            }
            SL.ListData[++SL.Listen] = data;
            return 1;
        }
    
        int Sidelete(Sltype SL, int n) { 
            //删除顺序表中的数据元素
            int i;
            if (n < 1 || n > SL.Listen + 1)
    //删除结点序号不正确
                System.out.print("删除结点序号错误,不能删除结点!n");
    
    //删除不成功,返回0
            for (i = n; i < SL.Listen; i++)
    //将顺序表中的数据向前移动
                SL.ListData[i] = SL.ListData[i + 1];
            SL.Listen--;//顺序表元素数量减1
    
            return 1;//成功删除,返回1
        }
    
    
        DATA SLFINDBYNUM(Sltype SL, int n) { 
    //根据序号返回数据元素
            if (n < 1 || n > SL.Listen + 1) { 
    //元素序号不正确
                System.out.print("结点序号错误,不能返回结点!n");
                return null;
            }
    //不成功,则返回0
            return SL.ListData[n];
        }
    
        int Slfindbycont(Sltype SL, String key)//按关键字査询结点
        { 
            int i;
            for (i = 1; i <= SL.Listen; i++)
                if (SL.ListData[i].key.compareTo(key) == 0)//如果找到所需结点
                    return i;//返回结点序号
    
            return 0;//搜索整个表后仍没有找到,则返回0
        }
    
    
        int SLALL(Sltype SL) { 
    //显示顺序表中的所有结点
            int i;
            for (i = 1; i <= SL.Listen; i++)
                System.out.printf("(%s, %s, %d)\n", SL.ListData[i].key, SL.ListData[i].name, SL.ListData[i].age);
            return 0;
        }
    }

## 链表操作实例 ##

链表结构带来的最大好处便是结点之间不要连续存放,因此在保存大量数据时,不需要分配一块连续的存储空间。用户可以用nw函数动态分配结点的存储空间,当删除某个结点时,给该节点赋值null,释放其占用的内存空间。  
当然,链表结构也有缺点,那就是浪费存储空间。因此,对于每个节点数据,都要额外保存一个引用变量。但是,在某些场合,链表结构所带来的好处还是大于其缺点的。  
对于链表的访问只能从表头逐个查找,即通head头引用找到第一个结点,再从第一个结点找到第二个结点……这样逐个比较一直到找到需要的结点为止,而不能像顺序表那样进行随机访问。  
链式存储是最常用的存储方式之一,它不仅可用来表示线性表,而且可用来表示各种非线性的数据结构。链表结构还可以细分为如下几类。  
●单链表:同上面的链式结构一样,每个结点中只包含一个引用。  
●双向链表:若每个结点包含两个引用,一个指向下一个结点,另一个指向上一个结点,这就是双向链表。  
●单循环链表:在单链表中,将终端结点的引用域null改为指向表头结点或开始结点即可构成单循环链表。  
●多重链的循环链表:如果将表中结点链在多个环上,将构成多重链的循环链表。  
接下来,将分析如何在Java语言中建立链表,并完成链表结构的基本运算。

追加结点：  
首先分配内存空间，保存新增的结点  
从头引用head开始逐个检查，直到找到最后一个结点  
将表尾结点的地址部分设置为新增结点的地址  
将新增结点的地址部分设置为空地址null,即新增结点成为表尾

class DATA2{ 
        String key;//结点的关键字
        String name;
        int age;
    }
    class CLType{ 
        //定义链表结构
        DATA2 nodeDATA = new DATA2();
        CLType nextNode;
        CLType CLAddEnd(CLType head,DATA2 nodeDATA)//输入参数head为头引用，nodeDATA为结点保存的数据
        { 
            CLType node,htemp;
            if((node = new CLType()) == null)
            { 
                //分配内存失败
                System.out.println("申请内存失败");
                return null;
            }
            else { 
                //如果内存分配成功，node将保存指向该内存区域的引用，并设置该结点指向下一节点的引用值为null
                node.nodeDATA = nodeDATA;//保存数据
                node.nextNode = null;//设置结点引用为空，即为表尾
                if(head == null)
                { 
                    head = node;
                    return head;
                }
                htemp = head;//htemp为临时结点
                while(htemp.nextNode != null)//查找链表的结尾
                { 
                    htemp = htemp.nextNode;
                }
                htemp.nextNode = node;
                return head;
            }
        }
    }

插入头结点：

CLType CLADddFirst(CLType head,DATA2 nodeDATA)
        { 
            CLType node;
            if((node = new CLType()) == null) { 
                System.out.println("内存分配失败");
    return null;
            }
            else
            { 
                node.nodeDATA = nodeDATA;
                node.nextNode = head;
                head = node;
                return head;
            }
        }

查找头结点：

//查找结点
        CLType CLFindNode(CLType head,String key)
        { 
            //通过关键字进行查询
            CLType htemp;
            htemp = head;//保存链表头引用
            while(htemp != null)
            { 
                if(htemp.nodeDATA.key.compareTo(key) == 0)
                { 
                    return htemp;//返回该结点的引用
                }
                htemp = htemp.nextNode;
            }
            return null;//找不到，返回空引用
        }

删除结点：  
在上述代码中,输入参数head为链表头引用,输入参数key表示一个关键字,是链表中需要删除结点的关键字。程序中,通过一个环,按关键字在整个链表中查找要删除的结点。  
如果找到被删除结点,则设置上一结点(nde引用所指结点)指向当前结点(h引用所指结点)的下一结点,即可完成链表中结点的逻辑删除。但是,此时被删除结点仍然保存在内存中,接着执行赋值null操作,用来释放被删除节点所占用的内存空间。

int CLDeleteNode(CLType head,String key) { 
            CLType node, htemp;
            htemp = head;
            node = head;//用于保存需要删除结点的上一个结点
            while (htemp != null) { 
                if (htemp.nodeDATA.key.compareTo(key) == 0) { 
                    node.nextNode = htemp.nextNode;
                    htemp = null;//释放内存
                    return 1;
                } else { 
                    node = htemp;//指向当前结点
                    htemp = htemp.nextNode;//指向下一个结点
                }
            }
            return 0;//删除失败
        }

遍历链表：

void CLAllNode(CLType head)
        { 
            CLType htemp;
            DATA2 nodeData;
            htemp = head;
           while (htemp != null)
           { 
               nodeData = htemp.nodeDATA;//获取结点数据
               System.out.println("结点(%s,%s,%d)\n",nodeData.key,nodeData.name, nodeData.age);
               htemp = htemp.nextNode;
    
           }
    
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70]: /images/20220829/b332af42178a47278d2bc975ddfe51cc.png