算法（一）、数据结构

系统管理员 2022-10-02 13:54 152阅读 0赞

**算法（一）、数据结构**

一、线性表

二、链表

三、队列

四、栈

五、串

六、树

七、二叉树

八、图

**一、线性表**

线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号，其具体含义在不同的情况下一般不同。

![线性表.png][.png]

在稍复杂的线性表中，一个数据元素可由多个数据项（item）组成，此种情况下常把数据元素称为记录（record），含有大量记录的线性表又称文件（file）。

线性表中的个数n定义为线性表的长度，n=0时称为空表。在非空表中每个数据元素都有一个确定的位置，如用ai表示数据元素，则i称为数据元素ai在线性表中的位序。

线性表的相邻元素之间存在着序偶关系。如用（a1，…，ai-1，ai，ai+1，…，an）表示一个顺序表，则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1,2，…，n-1时，ai有且仅有一个直接后继，当i=2，3，…，n时，ai有且仅有一个直接前驱。

1、特征

1) 集合中必存在唯一的一个“第一元素”。

2) 集合中必存在唯一的一个 “最后元素” 。

3) 除最后一个元素之外，均有 唯一的后继(后件)。

4) 除第一个元素之外，均有 唯一的前驱(前件)。

2、线性表存储方式——顺序储存

![线性表--顺序存储方式.png][--_.png]

3、线性表存储方式——链式储存

![线性表--链式存储方式.png][--_.png 1]

4、列表的基本操作

5、java中列表的实现

**二、链表**

链表（Linked List）是由许多相同数据类型的元素按照特定顺序排列而成的线性表，其特性是在计算机内存中是不连续与随机存储的，优点是插入和删除数据是方便。

**1、构建单向链表**

1) 创建链表节点 Node.java

public class Node {
        String name;
        int no;
        int score;
        Node next;
        public Node(int no, String name, int score) {
            this.name = name;
            this.no = no;
            this.score = score;
        }
    }

2) 构建单向链表LinkedList.java

public class LinkedList {
        private Node first;
        private Node last;
        public boolean isEmpty() {
            return first == null;
        }
        public void print() {
            Node current = first;
            while (current != null) {
                System.out.println("[" + current.no + "," + current.name + "," + current.score + "]");
                current = current.next;
            }
            System.out.println();
        }
        public void insert(int data, String name, int np) {
            Node newNode = new Node(data, name, np);
            if (this.isEmpty()) {
                first = newNode;
                last = newNode;
            } else {
                last.next = newNode;
                last = newNode;
            }
        }
    }

3) 构建测试类 CH03\_01.java

import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    public class CH03_01 {
        public static void main(String[] args) throws Exception, IOException {
            BufferedReader buf;
            buf = new BufferedReader(new InputStreamReader(System.in));
            int num;
            String name;
            int score;
            System.out.println("请输入5个学生信息:");
            LinkedList list = new LinkedList();
            for (int i = 1; i <= 5; i++) {
                System.out.println("请输入学号：");
                num = Integer.parseInt(buf.readLine());
                System.out.println("请输入姓名:：");
                name = buf.readLine();
                System.out.println("请输入成绩：");
                score = Integer.parseInt(buf.readLine());
                list.insert(num, name, score);
                System.out.println("------------------------------");
            }
            System.out.println("所有学生成绩如下：");
            list.print();
        }
    }

**三、队列**

**四、栈**

栈( stack )是限定仅在表尾进行插入和删除操作的线性表。

其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

1、特征

1) 只能从栈顶端访问数据；

2) 数据的访问符合后进先出的原则。

2、栈的存储方式

![栈的存储结构.png][.png 1]

4、栈的基本操作

1) create 创建一个空栈；

2) push 存放顶端数据，并且返回新的栈；

3) pop 删除顶端数据，并返回删除的那个元素；

4) peek 返回栈顶元素的值

5) empty 判断栈是否为空，若为空返回true，若不为空返回false；

5、java中栈的实现--数组

**五、串**

串( string )是由零个或多个字符组成的有限序列，又名叫字符串。

**六、树**

树是n(n>=0)个结点的有限集。n=O 时称为空树。在任意一棵非空树中: 1) 有旦仅有一个特定的称为根( Root ) 的结点;2) 当n > 1 时，其余结点可分为m ( m>O ) 个互不相交的有限集T1 T2、…… 、Tn， 其中每一个集合本身又是一棵树，并且称为根的子树。

二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^\{i-1\}个结点；深度为k的二叉树至多有2^k-1个结点；对任何一棵二叉树T，如果其终端结点数为n\_0，度为2的结点数为n\_2，则n\_0=n\_2+1。

一棵深度为k，且有2^k-1个节点的二叉树，称为满二叉树。这种树的特点是每一层上的节点数都是最大节点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树。具有n个节点的完全二叉树的深度为log2(n+1)。深度为k的完全二叉树，至少有2^(k-1)个节点，至多有2^k-1个节点。

1、二叉树的存储方式

1) 数组表示

使用一维数组表示二叉树，首先把二叉树看做满二叉树，而且第K个阶度具有2^(k-1)个节点，并且依序存放在一维数组中。

![二叉树数组表示.png][.png 2]

由于简历二叉树必须遵守“小于父节点的值放在左子节点，大于父节点的值放在右子节点”的规则，我们确保左子树的值完全小于树根，右子树的值一定大于树根。

public class BinararyTreeAnnary {
        public static void main(String args[]){
            int i,level;
            int[] data={6,3,5,9,7,8,4,2};
            int[] btree=new int[16];
            for(i=0;i<btree.length;i++)btree[i]=0;
            for(i=0;i<8;i++){
                for(level=1;btree[level]!=0;){
                    if(data[i]>btree[level]){
                        level=level*2+1;
                    }else{
                        level=level*2;
                    }
                }
                btree[level]=data[i];
            }
            System.out.println("aa");
            for(i=0;i<16;i++){
                System.out.print("["+btree[i]+"]  ");
                System.out.println();
            }
        }
    }

2)链表表示

2、二叉树的遍历方式

3、

转载于:https://blog.51cto.com/doublelinux/1974820

[.png]: https://s1.51cto.com/images/20180713/1531453562509415.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=
[--_.png]: https://s1.51cto.com/images/20180713/1531475719394134.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=
[--_.png 1]: https://s1.51cto.com/images/20180713/1531475734773770.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=
[.png 1]: https://s1.51cto.com/images/20180730/1532958410527290.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=
[.png 2]: https://s1.51cto.com/images/20180808/1533691660429115.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=