数据结构之线性表

迷南。 2022-05-30 00:44 180阅读 0赞

线性结构包括：数组、链表、队列、栈等。

> 线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。

两种实现方式：

> 顺序存储：底层利用数组实现  
> 链式存储

package dream.linearlist;
    /** * 线性表的抽象数据类型描述 */
    public interface IList { 
        boolean isEmpty();
        void clear();
        int length();
    
        //默认在末尾添加元素x
        void insert(Object x);
        //在第i个位置之前插入元素x
        void insert(int i,Object x);
        //移除第i个位置的元素并返回
        void remove(int i);
    
        //获取元素x的索引位置
        int indexOf(Object x);
        //获取第i个位置的元素
        Object get(int i);
    
        void display();
    }

顺序存储的数据结构实现：  
其中，在插入和删除元素的时候，需要判断插入或者删除的位置是否合法，以及顺序表是否满或者是否为空等  
插入元素，则意味着将元素后移（末尾元素开始后移），删除元素，则意味着元素前移（初始位置开始前移）

package dream.linearlist.sequencelist;
    import dream.linearlist.IList;
    /** * 利用数组实现线性表 * 注意：其中传入的参数i均表示位置，所以是从1开始，第i个位置的元素数组中的下标则为i-1 */
    public class SequenceList implements IList { 
        private Object[] listElem;
        private int curlen;  //线性表当前长度
    
        public SequenceList(int maxSize){
            listElem = new Object[maxSize];
            curlen = 0;
        }
        @Override
        public boolean isEmpty() {
            return curlen == 0;
        }
    
        @Override
        public void clear() {
            curlen = 0;
        }
    
        @Override
        public int length() {
            return curlen;
        }
    
        @Override
        public void insert(Object x) {
            if(curlen == listElem.length){
                System.out.println("线性表已满，无法插入元素...");
            }
            listElem[curlen++] = x;
        }
    
        @Override
        public void insert(int i, Object x) {
            if(i < 1 || i > curlen){
                System.out.println("插入位置不合法，无法插入元素...");
            }
            if(curlen == listElem.length){
                System.out.println("线性表已满，无法再插入元素...");
            }
            int j;
            for(j = curlen;j > i - 1;j --){
                listElem[j] = listElem[j - 1];
            }
            listElem[j] = x;
            this.curlen ++;
        }
        @Override
        public void remove(int i) {
            if(i < 1 || i > curlen){
                System.out.println("删除位置不合法，无法删除元素...");
            }
            if(isEmpty()){
                System.out.println("线性表为空，无法删除元素...");
            }
            for(int j = i-1;j < curlen;j++){
                listElem[j] = listElem[j+1];
            }
            this.curlen --;
        }
        @Override
        public int indexOf(Object x) {
            for(int i=0;i<curlen;i++){
                if(x.equals(listElem[i]))
                    return i+1;
            }
            return -1;
        }
        @Override
        public Object get(int i) {
            return listElem[i-1];
        }
        @Override
        public void display() {
            if(isEmpty()){
                System.out.println("[]");
                return;
            }
            System.out.print("[");
            for(int i=0;i<curlen-1;i++){
                System.out.print(listElem[i]+",");
            }
            System.out.println(listElem[curlen-1]+"]");
        }
    }

链表结构的实现：

package dream.linearlist.linkedlist;
    
    import dream.linearlist.IList;
    
    /** * 带头结点的单向列表 */
    public class MyLinkedList implements IList { 
        public Node getHead() {
            return head;
        }
    
        public void setHead(Node head) {
            this.head = head;
        }
    
        private Node head; //头节点
        public MyLinkedList(){
            head = null;  //头节点为空
        }
        @Override
        public boolean isEmpty() {
            return head == null;
        }
        @Override
        public void clear() {
            head = null;
        }
        @Override
        public int length() {
            Node p = this.head.getNext();
            int len = 0;
            while(p != null){
                len++;
                p = p.getNext();
            }
            return len;
        }
        //尾插法
        @Override
        public void insert(Object x) {
            Node newNode = new Node(x);
            if(isEmpty()){
                head = newNode;
                return;
            }
            Node n = head;
            while(n.getNext() != null){
                n = n.getNext();
            }
            n.setNext(newNode);
        }
        //头插法
        public void headInsert(Object x){
            Node newNode = new Node(x);
            if(isEmpty()) {
                head = newNode;
                return;
            }
            newNode.setNext(head);
            head = newNode;
        }
    
        @Override
        public void insert(int i, Object x) {
            Node p = head;
            //首先找到第i个位置的前驱，即第i-1个位置
            int j = 1;
            while(p != null && j < i-1){
                p = p.getNext();
                j++;
            }
            if(j != i-1 || p == null){
                System.out.println("插入位置不合法...");
            }
            Node nn = new Node(x);
            nn.setNext(p.getNext());
            p.setNext(nn);
        }
    
        @Override
        public void remove(int i) {
            Node p = head;
            //找到第i-1个位置
            int j = 1;
            while(p != null && j < i-1){
                p = p.getNext();
                j++;
            }
            if(j != i-1 || p == null){
                System.out.println("移除位置不合法...");
            }
            p.setNext(p.getNext().getNext());
        }
        @Override
        public int indexOf(Object x) {
            //p指向头节点，j是计数器
            Node p = head;
            int j = 1;
            while(p != null && !x.equals(p.getData())){
                p = p.getNext();
                j++;
            }
            //如果p指向null，则表示未找到，返回-1
            if(p == null)
                return -1;
            else
                return j;
        }
    
        @Override
        public Object get(int i) {
            Node p = head;
            int j = 1;
            while(j<i && p!=null){
                p = p.getNext();
                j++;
            }
            if(p == null || i < 1){
                return null;
            }
            return p.getData();
        }
    
        @Override
        public void display() {
            Node p = head;
            while(p != null){
                System.out.print(p.getData()+" ");
                p = p.getNext();
            }
            System.out.println();
        }
     }

下面是一些关于链表的常见面试题：

/** * 翻转链表：需要三个变量用于记录遍历时的当前节点pNode，当前节点的前驱pPrev，当前节点的后继pNext * @param head 旧链表的头节点 * @return 新列表的头节点 */
        public Node reverseNode(Node head){
            Node pReverseHead = head;
            Node pNode = head;   //从头节点开始遍历
            Node pPrev = null;   //当前节点的前驱
            while(pNode != null){
                Node pNext = pNode.getNext();  //当前节点的后继
                if(pNext == null){
                    pReverseHead = pNode;
                }
                pNode.setNext(pPrev);  //使得当前节点的后继指向原来的前驱节点
                //以下实现前驱节点和当前节点向后移
                pPrev = pNode;
                pNode = pNext;
            }
            this.head = pReverseHead;
            return this.head;
        }
    
        /** * 查找单向链表的中间节点思想： * 采用快慢指针，快指针每次走两步，慢指针每次走一步，当快指针走完时，慢指针刚好走一半 * @return 链表的中间节点 */
        public Node searchMid(){
            Node fNode = this.head;
            Node sNode = this.head;
            while(fNode != null && fNode.getNext() != null && fNode.getNext().getNext() != null){
                fNode = fNode.getNext().getNext();
                sNode = sNode.getNext();
            }
            System.out.println(sNode.getData());
            return sNode;
        }
    
        /** *查找倒数第k个元素 * 思想：需要两个引用p1,p2，p1先移动k步，然后p1,p2同时移动，直到p1移动到链表末尾，p2指向的则为倒数第k个元素 * @param k * @param head * @return */
        public Node findLastElem(int k,Node head){
            if(k < 1 || k >this.length()){
                System.out.println("查找位置不对...");
                return null;
            }
            Node p1 = head;
            Node p2 = head;
            for(int i=0;i<k;i++)  //前移k步
                p1 = p1.getNext();
            while(p1 != null){
                p1 = p1.getNext();
                p2 = p2.getNext();
            }
            System.out.println(p2.getData());
            return p2;
        }
        /** *单向链表递增排序 * 思想：遍历链表，并将当前的节点与其后的所有节点值的大小进行比较 * @return */
        public Node orderList(){
            Node nextNode = null;
            Node curNode = head;
            Object temp;
            while(curNode.getNext() != null){  //外层遍历
                nextNode = curNode.getNext();
                while(nextNode != null){  //内层遍历当前节点之后的节点，与当前节点值进行大小比较，如果比当前节点值小则进行互换
                    int cur =(Integer) curNode.getData();
                    int next =(Integer) nextNode.getData();
                    if(cur > next){
                        temp = curNode.getData();
                        curNode.setData(nextNode.getData());
                        nextNode.setData(temp);
                    }
                    nextNode = nextNode.getNext();
                }
                curNode = curNode.getNext();
            }
            return head;
        }
    
        /** * 删除单向链表中重复的节点 * 思想：遍历整个链表，将当前的节点与其后的所有节点进行比较，如果相同则删除。 * 需要两个引用，p用于外层循环中指向当前节点的，ppp用于内层循环中 * @param head */
        public void deleteDuplicateNode(Node head){
            Node p = head;
            while(p != null){
                Node ppp = p;
                while(ppp.getNext() != null){  //判断当前节点的下一个节点是否为空
                    if(p.getData().equals(ppp.getNext().getData())){  //不为空则判断值是否相同。此时节点ppp先不移动
                        ppp.setNext(ppp.getNext().getNext());
                    }else{
                        ppp = ppp.getNext();
                    }
                }
                p = p.getNext();
            }
        }
        /** * 利用递归从尾到头依次输出单向链表的元素 * @param p */
        public void printReverseList(Node p){
            if(p != null){
                printReverseList(p.getNext());   //直到p为null，则表示链表到了尾端
                System.out.print(p.getData()+" ");
            }
        }
    
        /** * 判断链表是否有环 * 思想：两个引用，一个快引用，一个慢引用，如果两个引用经过若干次循环之后指向同一个节点，则证明有环 * （类似于：两个运动员赛跑，一个跑得快，一个跑得慢，两人跑了一段时间，速度快的运动员必然会从 * 速度慢的运动员身后再次追上并超过，原因很简单，因为跑道是环形的。） * @param head * @return */
        public boolean isLoop(Node head){
            Node fast = head;
            Node slow = head;
            while(fast != null && fast.getNext() != null){
                fast = fast.getNext().getNext();
                slow = slow.getNext();
                if(fast == slow) {
                    System.out.println("该链表有环");
                    return true;
                }
            }
            return !(fast == null || fast.getNext() == null);
        }
    
        /** *找出链表的入环口 * 将慢指针（或快指针）移到链表起点，两者同时移动，每次移动一步，那么两者相遇的地方就是环的起点 * 解释：假设起点到环的起点距离为m，已经确定有环，环的周长为n，（第一次）相遇点距离环的起点的距离是k。 * 那么当两者相遇时，慢指针移动的总距离为i，i = m + a * n + k，因为快指针移动速度为慢指针的两倍， * 那么快指针的移动距离为2i，2i = m + b * n + k。其中，a和b分别为慢指针和快指针在第一次相遇时转过的圈数。 * 我们让两者相减（快减慢），那么有i = (b - a) * n。即i是圈长度的倍数。利用这个结论我们就可以理解 * Floyd解法为什么能确定环的起点。将一个指针移到链表起点，另一个指针不变，即距离链表起点为i处，两者同时移动， * 每次移动一步。当第一个指针前进了m，即到达环起点时，另一个指针距离链表起点为i + m。考虑到i为圈长度的倍数， * 可以理解为指针从链表起点出发，走到环起点，然后绕环转了几圈，所以第二个指针也必然在环的起点。即两者相遇点就是环的起点。 * @param head */
        public Node findLoopEnter(Node head){
            Node slow = head;
            Node fast = head;
            while(fast != null && fast.getNext() != null){
                fast = fast.getNext().getNext();
                slow = slow.getNext();
                if(slow == fast)
                    break;
            }
            if(fast == null || fast.getNext() == null) //该链表无环
                return null;
            //表明有环,slow指向head，与fast再次相遇的节点即为入环口
            slow = head;
            while(slow != fast){
                slow = slow.getNext();
                fast = fast.getNext();
            }
            return slow;
        }
        /** * 求环的长度 * 当快慢指针相遇时，继续移动直到第二次相遇，此时快指针移动的距离正好比慢指针多一圈 * @return */
        public int LoopLength(){
            Node slow = head;
            Node fast = head;
            while(fast != null && fast.getNext() != null){
                fast = fast.getNext().getNext();
                slow = slow.getNext();
                if(slow == fast)
                    break;
            }
            if(fast == null || fast.getNext() == null)
                return -1;  //无环
            int len = 0;
            while(fast != null && fast.getNext() != null){
                len++;
                fast = fast.getNext().getNext();
                slow = slow.getNext();
                if(fast == slow)
                    break;
            }
            return len;
        }

链表的使用：

public class LLMain {
        public static void main(String[] args){
            MyLinkedList ll = new MyLinkedList();
            ll.insert(5);
            ll.insert(6);
            ll.insert(6);
            ll.headInsert(2);
            ll.insert(3,8);
            ll.insert(10);
            ll.headInsert(0);
            ll.remove(4);
            ll.display();
            System.out.println("链表第四个位置的值是："+ll.get(4));
            System.out.println("10的位置索引是："+ll.indexOf(10));
            System.out.println("2的位置索引是："+ll.indexOf(2));
            System.out.println("翻转列表");
            ll.reverseNode(ll.getHead());
            ll.display();
            System.out.print("单向列表的中间节点：");
            ll.searchMid();
            System.out.print("单向列表中的倒数第3个节点是：");
            ll.findLastElem(3,ll.getHead());
            System.out.print("单向链表递增顺序排序后：");
            ll.orderList();
            ll.display();
            System.out.println("是否为空："+ll.isEmpty());
            ll.deleteDuplicateNode(ll.getHead());
            System.out.println("删除单向链表中的重复元素：");
            ll.display();
            System.out.print("利用递归从尾带头依次输出单向链表中的元素：");
            ll.printReverseList(ll.getHead());
            System.out.println();
        }
    }

输出结果：  
0 2 5 6 6 10  
链表第四个位置的值是：6  
10的位置索引是：6  
2的位置索引是：2  
翻转列表  
10 6 6 5 2 0  
单向列表的中间节点：6  
单向列表中的倒数第3个节点是：5  
单向链表递增顺序排序后：0 2 5 6 6 10  
是否为空：false  
删除单向链表中的重复元素：  
0 2 5 6 10  
利用递归从尾带头依次输出单向链表中的元素：10 6 5 2 0