2022年考研数据结构_2 线性表

深碍√TFBOYSˉ_ 2022-12-31 05:22 217阅读 0赞

https://gitee.com/fakerlove/Data-Structure

### 文章目录 ###

*  2. 线性表
 *   *  一、单链表
     *  二、循环链表
     *  三、双向链表

# 2. 线性表 #

## 一、单链表 ##

单链表是链表的基础，链表不同于顺序表，他使用链式结构来关联节点，其示意图如下：  
![链表示意图][c0ab01a1dba69c66ba08d3c8c46a4498.png]  
单链表最重要的是需要搞清楚插入、删除操作

*  插入：插入的示意图如下所示，要在p的后面插入e，关键就是找到p，让p的next指向e，再让e的next指向p的原先的next（注意在p.next=e之前保存）。插入时，要判断是否插入到头结点，如果是的话，**要记得给成员变量头结点重新赋值**。  
    ![单链表的插入][03a86d406a4769e355c407195a7f1993.png]
 *  删除：单链表的删除示意图如下，删除节点p,首先找到p的前一个元素q，然后让q的next指向p的next即可。同样删除时需要注意头结点的问题，删除头结点后需要重新给成员变量头结点赋值。  
    ![在这里插入图片描述][b219b3dbf30907925b278c40af2ea38e.png]  
    单链表其他的操作都比较简单，我这里不再赘述。下面来看用C++和Java实现单链表的代码。
 *  **Java实现**

public class LinkList<T> { 
    
        private Node head=null;//头结点
        private int length=0;//链表的长度
    
    
        /** * 获取链表长度 * @return */
        public int getLength(){ 
            return length;
        }
    
        /** * 获取position位置的节点 * @param position * @return */
        protected Node getNode(int position)
        { 
            if (head==null||position<0||position>=length)
                throw new IndexOutOfBoundsException();
            else { 
                Node curNode=head;
                int tmp=0;
                while (tmp<position){ 
                    curNode=curNode.next;
                    tmp++;
                }
                return curNode;
            }
        }
    
        /** * 获取position下标下的数据内容 * @param position * @return */
        public T get(int position){ 
            return getNode(position).data;
        }
    
        /** * 在链表末尾插入节点 * @param data */
        public void pushBack(T data){ 
            insert(this.length,data);
        }
    
        /** * 在position位置插入数据 * @param position * @param data */
        public void insert(int position,T data){ 
            Node newNode=new Node(data);
            if (position==0){ 
                Node oldFirst=head;
                head=newNode;
                head.next=oldFirst;
            }else { 
                Node node= getNode(position-1);
                Node nextNode=node.next;
                node.next=newNode;
                newNode.next=nextNode;
            }
            this.length++;
        }
    
        /** * 移除链表中的position下标的元素，并返回元素值 * @param position * @return */
        public T remove(int position){ 
            T data=null;
            if (position==0){ 
                data=head.data;
                head=head.next;
            }else if(position<length){ 
                Node node= getNode(position-1);
                Node positionNode=node.next;
                node.next=node.next.next;
                data=positionNode.data;
            }
            length--;
            return data;
        }
    
        /** * 找到第一个出现data的索引位置 * @param data * @return */
        public int indexOf(T data){ 
            Node curNode=head;
            int position=0;
            while (curNode!=null)
            { 
                if (curNode.data.equals(data))
                    return position;
                curNode=curNode.next;
                position++;
            }
            return -1;
        }
    
        @Override
        public String toString() { 
            Node curNode=head;
            String outString="";
            while (curNode!=null)
            { 
                outString+=curNode.toString()+",";
                curNode=curNode.next;
            }
            return outString;
        }
    
        public class Node{ 
            T data;//数据域
            Node next;//后继
    
            public Node(T data){ 
                this.data=data;
                next=null;
            }
    
            @Override
            public String toString() { 
                return data.toString();
            }
        }
    }
    123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136

示例用法为：

LinkList<String> linkList= new LinkList<String>();
     linkList.pushBack("0");
     linkList.insert(0,"1");
     linkList.insert(2,"2");
     System.out.println(linkList);
     System.out.println(linkList.indexOf("2"));
    123456

*  **C++实现**

template<class T>
    class LinkList
    { 
    	struct Node//节点定义
    	{ 
    		T data;
    		Node* next;
    		Node(T data) { 
    			this->data = data;
    			next = NULL;
    		}
    	};
    private:
    	Node* head;
    	int length;
    protected:
    	/** * 获取某位置的节点 */
    	Node* getNode(int position)
    	{ 
    		if (!head || position < 0 || position >= length)
    			throw std::out_of_range("position is out of range");
    		else
    		{ 
    			Node* curNode = head;
    			int tmp = 0;
    			while (tmp<position)
    			{ 
    				curNode = curNode->next;
    				tmp++;
    			}
    			return curNode;
    		}
    	}
    public:
    	LinkList()
    	{ 
    		this->head = NULL;
    		this->length = 0;
    	}
    	/** * 析构函数，此处需要释放链表 */
    	~LinkList()
    	{ 
    		Node* curNode = head;
    		while (curNode)
    		{ 
    			Node* tmp = curNode->next;
    			delete curNode;
    			curNode = tmp;
    		}
    	}
    
    	/** * 获取链表的长度 */
    	int getLength()
    	{ 
    		return length;
    	}
    
    	/** * 获取position位置下的数据 */
    	T get(int position)
    	{ 
    		return getNode(position)->data;
    	}
    
    	/** * 在链表末尾追加元素 */
    	void pushBack(T data)
    	{ 
    		insert(this.length,data);
    	}
    
    	/** * 在position位置增加data数据 */
    	void insert(int position, T data)
    	{ 
    		Node* newNode = new Node(data);
    		if (position == 0) { 
    			Node* oldFirst = head;
    			head = newNode;
    			head->next = oldFirst;
    		}
    		else { 
    			Node* node = getNode(position - 1);
    			Node* nextNode = node->next;
    			node->next = newNode;
    			newNode->next = nextNode;
    		}
    		this->length++;
    	}
    
    	/* *移除链表中的position下标的元素，并返回元素值 */
    	T remove(int position)
    	{ 
    		T data;
    		if (position == 0) { 
    			Node* removeNode;
    			removeNode = head;
    			data = head->data;
    			head = head->next;
    			delete removeNode;
    		}
    		else if (position<length)
    		{ 
    			Node* node = getNode(position - 1);
    			Node* positionNode = node->next;
    			node->next = node->next->next;
    			data = positionNode->data;
    			delete positionNode;
    		}
    		length--;
    		return data;
    	}
    
    	/** *找到第一个出现data的索引位置 */
    	int indexOf(T data) { 
    		Node* curNode = head;
    		int position = 0;
    		while (curNode != NULL)
    		{ 
    			if (curNode->data == data)
    				return position;
    			curNode = curNode->next;
    			position++;
    		}
    		return -1;
    	}
    };
    123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140

使用示例为：

LinkList<std::string> link_list;
    	link_list.pushBack("0");
    	link_list.pushBack("1");
    	link_list.pushBack("2");
    	link_list.insert(0,"3");
    	link_list.remove(0);
    	link_list.remove(1);
    	std::cout <<"元素0所在的下标为"<< link_list.indexOf("0")<<std::endl;
    	for (int i=0;i<link_list.getLength();i++)
    	{ 
    		std::cout << link_list.get(i)<<",";
    	}
    123456789101112

## 二、循环链表 ##

循环链表就是**把最后一个节点的next指向头结点，解决的是如何从某个节点出发，遍历整个链表的问题**，上面的单链表如果要遍历，只能从头结点开始，遍历到尾节点，但循环链表则可以从任意一个节点开始，遍历整个链表。存储结构如下图所示：  
![循环链表示意图][74ec56da259a4d2f107d170bb86092d4.png]  
只有一个节点的循环链如下所示：  
![只有一个节点的循环链表][18401a406a29202d0f3b61363fab2d68.png]  
因为循环链表和单链表间的变化很小，我这里不单独写循环链表的代码了，在双向链表中，我实现了双向循环链表，可以参考。使用循环链表需要注意的一个问题：  
**如何判断循环结束**：单链表是判断节点p的next是否为空，循环链表从p开始循环遍历，判断条件是当前节点是否回到了p。所以不同于单向链表的实现，**在遍历链表时，应该用do while语句**，而不用while语句，否则p元素可能会遍历不到（具体见我双向循环链表java代码中的toString方法的实现）。

## 三、双向链表 ##

双向链表是在单链表的基础上，**给节点增设一个指针域，指向节点的前驱节点**。这样的话，遍历链表的时候，既可以从前往后遍历，又可以从后往前遍历。双向链表也可以是循环链表，双向循环链表的示意图如下所示：  
![双向循环链表][0dcab68c4919cc602aeb2a33ef183b6e.png]  
当只有一个节点时，其示意图为：  
![只有一个节点的双向循环链表][a30d51d3fea0fb12af397d1df6eed922.png]  
因为，单链表和双向链表的操作很多都是重复的，为了节省时间，我这里就只用Java实现双向循环链表，实现其插入、删除、遍历。具体代码如下：

*  **双向循环链表Java实现**

public class DoublyLinkedList<T> { 
    
        protected class Node{ 
            T data;//数据域
            Node pre;//前驱节点
            Node next;//后继节点
    
            Node(T data){ 
                this.data=data;
                pre=next=null;
            }
    
            @Override
            public String toString() { 
                return data.toString();
            }
        }
    
        protected Node head=null;//头结点
        protected int length=0;//链表长度
    
        /** * 获取position位置的节点 * @param position * @return */
        protected Node getNode(int position)
        { 
            if (head==null||position<0||position>=length)
                throw new IndexOutOfBoundsException();
            else { 
                /*此处充分利用双向链表的优点，首先判断position和half=length/2的大小关系 如果position大于half，则从后往前遍历 如果position小于等于half，则从前往后遍历 */
                int half=this.length/2;
                Node curNode;
                int tmp;
                if (position<=half){ //从前往后遍历
                    curNode=head;
                    tmp=0;
                    while (tmp<position){ 
                        curNode=curNode.next;
                        tmp++;
                    }
                    return curNode;
                }else { //从后往前遍历
                    curNode=head.pre;
                    tmp=length-1;
                    while (tmp>position){ 
                        curNode=curNode.pre;
                        tmp--;
                    }
                    return curNode;
                }
            }
        }
    
        /** * 在position位置插入数据 * @param position * @param data */
        public void insert(int position,T data){ 
            Node newNode=new Node(data);
            if (position==0){ 
                Node oldFirst=head;
                head=newNode;
                //头结点的前驱后继
                head.next=oldFirst;
                if (oldFirst!=null) { 
                    head.pre=oldFirst.pre;
                    //让末尾节点的next指向头结点
                    oldFirst.pre.next=head;
                    //以前头结点的前驱
                    oldFirst.pre=head;
                }else { 
                    newNode.pre=newNode;
                    newNode.next=newNode;
                }
            }else { 
                Node node= getNode(position-1);
                newNode.pre=node;
                if (node.next==null){ //插入位置为空，说明是插入到链表的末尾
                    newNode.next=head;
                    head.pre=newNode;
                }else { //说明插入到两个结点的中间
                    newNode.next=node.next;
                    node.next.pre=newNode;
                }
                node.next=newNode;
            }
            this.length++;
        }
    
        /** * 移除position位置处的元素 * @param position * @return */
        public T remove(int position){ 
            T data=null;
            if (position==0){ //移除的是头结点
                data=head.data;
                if (this.length==1)//如果只有一个元素，直接置空
                    this.head=null;
                else { 
                    Node oldHead=head;
                    head=head.next;
                    //头结点的next
                    head.pre=oldHead.pre;
                    oldHead.pre.next=head;
                }
            }else { //移除是非头结点
                Node node= getNode(position-1);
                if (node.next==null){ //移除的节点是最后一个节点
                    node.next=head;
                    head.pre=node;
                }else { //移除的节点是中间节点
                    Node removeNode=node.next;
                    node.next=removeNode.next;
                    removeNode.next.pre=node;
                }
            }
            this.length--;
            return data;
        }
    
        public T get(int position){ 
            return getNode(position).data;
        }
    
        @Override
        public String toString() { 
            Node curNode=head;
            String outString="";
            if (curNode!=null){ 
                do { 
                    outString+=curNode.toString()+",";
                    curNode=curNode.next;
                }while (curNode!=head);
            }
            return outString;
        }
    }
    123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145

使用示例为：

DoublyLinkedList<String> list=new DoublyLinkedList<String>();
     list.insert(0,"0");
     list.insert(0,"1");
     list.insert(0,"2");
     list.insert(1,"3");
     list.insert(4,"4");
     list.remove(4);
     System.out.println(list);
    12345678

根据上面的代码，需要注意的问题有：

*  遍历：因为是双向循环链表，所以**在遍历时，应充分利用双向循环链表的优势，我上面的getNode函数，根据position位置和链表的长度进行判断，设链表长度的一半为half=length/2，访问第position位置时，当position<=half时，从前往后遍历，否则从前往后遍历**，这样遍历能提高一倍的性能。  
    此外，遍历时，应该判断当前节点是否是开始的节点，如果是，则遍历完成。所以，应该使用do while语句而不是while语句，否则会导致循环直接跳出。此外，上面的toString函数是通过从前往后遍历的，双向链表也可以从后往前遍历，遍历代码为：

do { 
              curNode=curNode.pre;
              outString+=curNode.toString()+",";
       }while (curNode!=head);
    1234

*  插入：双向链表插入时，应该判断插入的位置是头部还是尾部还是中间，根据这三种情况，分别做处理
 *  删除：同上，也要根据删除元素在链表头部、尾部还是中间分别做相应的处理。还要注意，**如果链表只有一个元素，且移除的是第一个元素，那直接将头结点置空**。

[c0ab01a1dba69c66ba08d3c8c46a4498.png]: /images/20221120/1a94b0b34324406cb71c76154819a9eb.png
[03a86d406a4769e355c407195a7f1993.png]: /images/20221120/142ec5ba896d402ea26d8420ccaf23ef.png
[b219b3dbf30907925b278c40af2ea38e.png]: /images/20221120/ccc7e4f2e909433f8b42e0509f975deb.png
[74ec56da259a4d2f107d170bb86092d4.png]: /images/20221120/a42b2d301abe40619a4bc358d8e4d98f.png
[18401a406a29202d0f3b61363fab2d68.png]: /images/20221120/9b355c216c7f41049e276473c6c93b63.png
[0dcab68c4919cc602aeb2a33ef183b6e.png]: /images/20221120/7570455776a743b1a5c407b8fa1710ba.png
[a30d51d3fea0fb12af397d1df6eed922.png]: /images/20221120/566c8b57eab546619680cc6c603f33df.png