天天看點
傳回

資料結構——線性表1.順序表2.單連結清單3.雙向連結清單

什麼是線性表？

線性表是具有相同類型的n個元素（n>=0）的有限序列。

1.順序表

  • 線性表采用順序存儲方式
  • 其邏輯順序和實體順序相同

問題：需要連續存儲空間，插入等操作需要移動大量元素，時間複雜度高。

2.單連結清單

線性表采用鍊式存儲方式稱為單連結清單。

鍊式存儲是采用節點來進行存儲的。

每個節點包括data域和next域。（不一定連續存儲）

資料結構——線性表1.順序表2.單連結清單3.雙向連結清單
  • 單連結清單反轉
  • 單連結清單的增删改查
  • 約瑟夫環

單連結清單反轉

資料結構——線性表1.順序表2.單連結清單3.雙向連結清單

資料結構——線性表1.順序表2.單連結清單3.雙向連結清單

單連結清單的增删改查 

import java.util.Stack;

//定義單個節點
class Node
{

    public String data;  //定義資料節點

    public Node next;   //定義指向下一個節點的指針

    public Node() {
    }

    public Node(String data) {
        this.data = data;
    }

    public String getData() {
        return data;
    }

    public void setData(String data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "Note{" +
                "data='" + data + '\'' +
                '}';
    }
}


public class Operation
{
    //初始化頭結點
    private static Node head = new Node();


    private static Node reverseHead = new Node();


    //插入節點（頭插）
    public void insertToHead(Node node)
    {
        Node temp = head;

        //頭插法需要設定head.next和node.next的值。其中nodeNext指向headNext，而headNext指向node。
        //由于是指派的關系，二者順序不可颠倒
        node.next=temp.next;
        temp.next=node;
    }

    //插入節點（尾插）
    public void insertToLast(Node node)
    {
        Node temp = head;

        while (true)
        {
            if(temp.next==null)
            {break;}
            temp=temp.next;
        }
        temp.next=node;
    }

    //插入節點（指定位置k之後）

    public void insertToK(Node node,int k)
    {
        Node temp = head;
        for(int i=0;i<k;i++)
        {
            temp=temp.next;
        }
        node.next=temp.next;
        temp.next=node;
    }


    //删除第m個節點
    public void deleteM(int m)
    {
        Node temp = head;
        for(int i=0;i<m-1;i++)
        {
            temp=temp.next;
        }
        temp.next=temp.next.next;
    }


    //修改第n個節點（n）
    public void updateN(int n)
    {
        Node temp = head;
        for(int i=0;i<n;i++)
        {
            temp=temp.next;
        }
        temp.data="up";
    }


    //遞歸反轉

    public Node reverseLinkedList(Node node) {
        if (node == null || node.next == null) {
            return node;
        } else {
            Node headNode = reverseLinkedList(node.next);
            node.next.next = node;
            node.next = null;
            return headNode;
        }
    }

    //周遊反轉
    public Node reserveByFor(Node head)
    {
        Node cur = head.next;
        Node next = null;
        Node Rhead = new Node();


        while(true)
        {
            if(cur==null)
            {
                break;
            }
            else
            {
                next=cur.next;
                cur.next=Rhead.next;
                Rhead.next=cur;

                cur=next;
            }
        }

        head.next=Rhead.next;

        return head;
    }

    //print(last to first)
    public void printLtoF(Node head)
    {
        Stack<Node>stack = new Stack<>();
        Node cur = head.next;
        while (cur!=null)
        {
            stack.push(cur);
            cur=cur.next;
        }
        while (stack.size()>0)
        {
            System.out.println(stack.pop());
        }
    }




    public static void main(String[] args)
    {
        Operation operation = new Operation();

        operation.insertToHead(new Node("A"));
        operation.insertToHead(new Node("B"));
        operation.insertToHead(new Node("C"));

        operation.insertToLast(new Node("1"));
        operation.insertToLast(new Node("2"));
        operation.insertToLast(new Node("3"));

//        operation.insertToK(new Node("k"),2);

//        operation.deleteM(3);

//        operation.updateN(1);


        Node temp =head;
        //周遊連結清單
        while(true)
        {
            if(temp.next==null)
            {break;}
            else
            {
                temp=temp.next;
                System.out.println(temp.toString());

            }
        }



        System.out.println("//1.求單連結清單中有效節點個數.");

        temp=head;
        int count=0;
        while(true)
        {
            if(temp.next==null)
            {break;}
            else
            {
                temp=temp.next;
                count++;
            }
        }
        System.out.println(count);


        System.out.println("//2.查找單連結清單中倒數第K=3個節點");

        temp=head;

        //擷取連結清單總長
        int length=0;

        while (true)
        {
            if(temp.next==null)
            {break;}
            else
            {
                temp=temp.next;
                length++;
            }
        }


        temp=head;
        for(int i=0;i<length-2;i++)
        {
            temp=temp.next;
        }
        System.out.println(temp.data);


        System.out.println("3.實作單連結清單的反轉");

//      temp=operation.reverseLinkedList(head);


        temp = operation.reserveByFor(head);

        //周遊連結清單
        while(true)
        {
            if(temp.next==null)
            {break;}
            else
            {
                temp=temp.next;
                System.out.println(temp.toString());
            }
        }


        System.out.println("4.從尾到頭列印單連結清單");

        temp = head;
        operation.printLtoF(temp);






    }
}

複制

資料結構——線性表1.順序表2.單連結清單3.雙向連結清單

單向環形連結清單輸出約瑟夫環

資料結構——線性表1.順序表2.單連結清單3.雙向連結清單
//定義單個節點
class Node
{

    public String data;  //定義資料節點

    public Node next;   //定義指向下一個節點的指針


    public Node() {
    }

    public Node(String data) {
        this.data = data;
    }


    @Override
    public String toString() {
        return "Note{" +
                "data='" + data + '\'' +
                '}';
    }


}


public class Operation
{
    //初始化頭結點
    private static Node head = new Node();

    //尾插法
    public void add(Node node)
    {
        Node temp = head;

        while (true)
        {
            if(temp.next==null)
            {break;}
            temp=temp.next;
        }
        temp.next=node;
    }

    //建立單向環形連結清單
    public Node createCircle(int n)
    {
        //建立單連結清單
        for(int i=0;i<n;i++)
        {
            add(new Node("No:"+(i+1)));
        }

        //周遊連結清單
        Node temp = head;
        while(temp.next!=null)
        {
            temp=temp.next;
            System.out.println(temp);
        }

        Node last = temp;
        temp=head;
        last.next=head.next;   //連接配接首尾

        System.out.println("last為最後一個數5：");
        System.out.println(last);


        System.out.println("循環兩遍單向環形連結清單：");
        int count=2*n;
        while(last!=null)
        {
            if(count==0)
            {
                break;
            }
            System.out.println(last.next);
            last=last.next;
            count--;
        }
        System.out.println("last="+last.data);
        return last;
    }

    public static void JosephusProblem(int n, int k, int m, Node last)
    {
        //定位到第k個節點,輸出k+1個節點并删除，并讓last定位到第k個節點

        Node temp = last;
        for(int i=0;i<k;i++)  //定位到第k個節點
        {
            temp=temp.next;
        }
        System.out.println("第一次輸出"+temp.next.data);//輸出

        temp.next=temp.next.next; //删除第K+1個節點
        last=temp.next;



        for(int i=0;i<n-1;i++)
        {
            temp=last;

            System.out.println("第二次輸出"+temp.next.data);

            temp.next=temp.next.next;
            last=temp.next;
        }


    }
    public static void main(String[] args)
    {
        Operation operation = new Operation();

        //定義人數
        int n=5;
        Node last = operation.createCircle(n);


        //定義從第幾個節點開始數
        int k=1;
        //定義數的次數
        int m=2;


        System.out.println("輸出約瑟夫環：");
        JosephusProblem(n,k,m,last);


    }
}

複制

資料結構——線性表1.順序表2.單連結清單3.雙向連結清單

3.雙向連結清單

雙向連結清單與單向連結清單的差別

單向清單隻能從前往後查找，而雙向連結清單可以向前向後查找。

單向連結清單删除節點需要依靠輔助節點，而雙向連結清單可以實作自我删除。

雙向連結清單與單項清單的實際差別在于多了一個pre域。

資料結構——線性表1.順序表2.單連結清單3.雙向連結清單

雙向連結清單增删改查 

import java.util.Stack;

//定義單個節點
class Node
{

    public String data;  //定義資料節點

    public Node next;   //定義指向下一個節點的指針

    public Node pre;    //定義指向上一個節點的指針

    public Node() {
    }

    public Node(String data) {
        this.data = data;
    }


    @Override
    public String toString() {
        return "Note{" +
                "data='" + data + '\'' +
                '}';
    }
}


public class Operation
{
    //初始化頭結點
    private static Node head = new Node();


    //插入節點（尾插法）
    public void addNode(Node node)
    {
        Node temp = head;
        while(true)
        {
            if(temp.next==null)
            {
                break;
            }
            temp=temp.next;
        }
        temp.next=node;
        node.pre=temp;
    }

    //插入節點(頭插法)
    public void addNodeToHead(Node node)
    {
        Node temp = head;


        node.pre=temp;
        node.next=temp.next;
        temp.next.pre=node;
        temp.next=node;
    }

    //插入到第k個節點後
    public void addToK(Node node,int k)
    {
        Node temp = head;
        for(int i=0;i<k;i++)
        {
            temp=temp.next;
        }
        //先建立單連結清單聯系
        node.next=temp.next;
        temp.next=node;
        //建立pre指向
        node.pre=temp;
        node.next.pre=node;
    }

    //删除第n個結點
    public void deleteNode(int n)
    {
        Node temp = head;
        for(int i=0;i<n;i++)
        {
            temp=temp.next;
        }
        temp.next.pre=temp.pre;
        temp.pre.next=temp.next;
    }

    public void list()
    {
        //周遊連結清單
        Node temp = head;
        while(temp.next!=null)
        {
            temp=temp.next;
            System.out.println(temp.toString());
        }
        System.out.println("=============");
    }


    //修改第m個結點
    public void update(int m)
    {
        Node temp = head;
        for(int i=0;i<m;i++)
        {
            temp=temp.next;
        }
        temp.data="up";
    }

    public static void main(String[] args)
    {
        Operation operation = new Operation();

        operation.addNode(new Node("A"));
        operation.addNode(new Node("B"));
        operation.addNode(new Node("C"));
        operation.addNode(new Node("D"));
        operation.addNodeToHead(new Node("head1"));
        operation.addNodeToHead(new Node("head2"));
        operation.addNodeToHead(new Node("head3"));

        //周遊連結清單
        operation.list();

        System.out.println("删除第n個節點");
        operation.deleteNode(3);

        //周遊連結清單
        operation.list();

        System.out.println("修改第m個節點");

        operation.update(3);

        operation.list();

        System.out.println("插入到第k個節點後");
        operation.addToK(new Node("k" ),3);

        operation.list();
    }
}

複制

上一篇: WinRAR目錄穿越神洞複現及防禦
下一篇: 【坑】myeclipse中的包都變成檔案夾