数据结构-线性表

摘要 从本篇开始,将为大家带来数据结构的系列博客,也许我所介绍的内容包含的不是很全,但相信一定是最容易理解的,有兴趣的读者可以对本人的博客进行跟踪学习。数据结构简而言之,数据结构是一门描述数据之间逻辑关系和解决数据在计算机中的存储问题,以及定义在这些存储结构上的操作的集合,这些操作集也可以称之为算法,狭义上的数据结构只是指的是数据之间的逻辑结构和物理存储结构,广义上的数据结构还包含算法的定义。 从逻辑关系上,数据结构又可以分为线性结构和非线性结构,而线性表则是线性结构中最基础的内容,下面本文将系统介绍数据结构的线性表的内容。

线性表概述

线性表是线性结构最基本的内容,那么何为线性结构和非线性结构呢?这需要从数据的逻辑关系上来区分,首先,把线性结构数据之间的逻辑关系概括为:

非线性结构就是数据元素有多个直接前驱和直接后继。

线性表分类

前面介绍线性表的逻辑关系,那么从存储上,又可以将线性表分为顺序表链接表。为求简单起见,本文只介绍顺序表和单链表。

顺序表指的是逻辑上相邻的数据元素物理上也相邻,是一种随机存取结构,即节点的位置是其下标的线性函数,顺序表便于查找,但不利于插入和删除;

单链表指的是逻辑上相邻的数据元素物理上不一定相邻,是一种顺序存取结构,即要得到某一节点的位置,必须从开始节点起顺序往后遍历,因此不利于查找,但是易于插入和删除(只需要修改指针或引用即可)。

顺序表解析

顺序表属性操作解析

顺序表的底层就是数组,因此可以用数组来模拟顺序表。顺序表的属性包含:

其操作包含:

下面是顺序表的实现结构。

class SeqList{
	public static final int LIST_SIZE = 100;
	private int data[] = new int[LIST_SIZE];
	private int length = 0;

	public SeqList(){

	}

	public int length(){
		return this.length;
	}

	public boolean isEmpty(){
		return (this.length == 0);
	}

	public boolean isFull(){
		return (this.length == LIST_SIZE);
	}

	/**
	 * [insert description]
	 * @param  pos [insert pos, start from 1 to length]
	 * @param  val [insert value]
	 * @return     [insert successfully or not]
	 */
	public boolean insert(int pos, int val){
		//judge if the pos is correct
		if(pos < 1 || pos > length+1)
			return false;
		//judge if the list is full
		if(this.isFull())
			return false;
		for(int i=length-1;i>=pos-1;i--){
			data[i+1] = data[i];
		}
		data[pos-1] = val;
		this.length++;
		return true;
	}

	/**
	 * [delete description]
	 * @param  pos [delete pos, start from 1 to length]
	 * @return     [delete value]
	 */
	public int delete(int pos){
		//judge if the pos is correct
		if(pos < 1 || pos > length)
			return -1;
		//judge if the list is empty
		if(this.isEmpty())
			return -1;
		int val = data[pos-1];
		for(int i=pos;i<length;i++){
			data[i-1] = data[i];
		}
		this.length--;
		return val;
	}

}

顺序表主要函数解析

类似于求长度和判断是空还是满的函数比较简单,这里就不做过多分析。对于指定位置插入和删除元素,分析如下:

首先是插入元素

  • 首先肯定要判断插入位置pos,注意虽然数组下标是从0开始的,但是这里的pos却是从1开始的,一定要注意区分。
  • pos < 1   pos > length+1 这些位置都是不合格的,显然插入位置小于1肯定不合格,为什么大于length+1才不合格呢,等于length+1难道合格吗,这时候顺序表里只有length个元素,我们当然可以插入最后一个元素的后面一个。
  • 插入位置合格的情况下,还要判断表是否已经满了,因为顺序表有空间限制,如果表满,将不能再执行插入操作。
  • 以上两个条件都满足,就可以进行插入了,要插入的位置是pos,即对于顺序表下标为pos-1的元素,那么对于顺序表中的元素,我们要把下标为pos-1到length-1位置的所有元素统统向右移动一位。
  • 具体移动操作的时候,循环要从后面开始,目的是防止元素覆盖,丧失原始值的情况
  • 全部移动工程结束的时候,直接把要插入的val赋值到pos-1的位置即可,注意一定要将表长加1,这是很容易遗忘的
public boolean insert(int pos, int val){
	//judge if the pos is correct
	if(pos < 1 || pos > length+1)
		return false;
	//judge if the list is full
	if(this.isFull())
		return false;
	for(int i=length-1;i>=pos-1;i--){
		data[i+1] = data[i];
	}
	data[pos-1] = val;
	this.length++;
	return true;
}

对于顺序表删除元素,其分析也是一样的:

  • 首先判断删除位置是否合法,删除位置的元素一定要存在才行,pos还是从1开始的
  • pos < 1   pos > length 都是不合法的,注意这里pos不是大于length+1而是大于length因为,删除的元素一定要存在。
  • 删除之前还要判断表是否为空,如果表空,则没有元素可删
  • 要删除pos位置的元素,即对应表中下标为pos-1的元素,首先将该位置元素保存起来,为了返回。
  • 还要做的一件事就是将下标从pos到length-1位置的所有元素统统向前移动一位。循环从pos开始同样是为了避免元素覆盖丧失原始值的情况发生。
  • 删除元素之后,需要将表长减1.
public int delete(int pos){
	//judge if the pos is correct
	if(pos < 1 || pos > length)
		return -1;
	//judge if the list is empty
	if(this.isEmpty())
		return -1;
	int val = data[pos-1];
	for(int i=pos;i<length;i++){
		data[i-1] = data[i];
	}
	this.length--;
	return val;
}

单链表解析

单链表属性操作解析

单链表属于链式存储结构,由于每个逻辑相邻的数据元素之间物理位置不一定相邻,因此结点除了存放数据之外,还要额外存放一个指向其后继结点的指针或引用,这里的指针或引用都是后继元素的内存地址。这里的数据结点我们用一个内部类表示。

为了便于操作,通常声明一个实际上不存在的结点指向开始结点,即头结点。单链表的属性包含:

单链表操作包含:

可能有人会问为什么没有判断表是否为满的操作,因为链式存储结构属于动态内存分配,因此不存在表满的情况,如果出现,说明内存已经用完了。下面是单链表的实现结构。

class LinkList{
	private LinkNode head = new LinkNode();
	private int length = 0;

	private class LinkNode{
		private int data = 0;
		private LinkNode next = null;
	}

	public LinkList(){

	}

	public int length(){
		return this.length;
	}

	public boolean isEmpty(){
		return (this.length == 0);
	}

	/**
	 * [insert description]
	 * @param  pos [the pos you want to insert value]
	 * @param  val [insert value]
	 * @return     [if insert successfully or not]
	 */
	public boolean insert(int pos, int val){
		if(pos < 1 || pos > this.length+1)
			return false;

		LinkNode s = new LinkNode();
		s.data = val;
		s.next = null;

		if(head.next == null){

			head.next = s;
			this.length = 1;
			return true;
		}
			
		LinkNode p = head;
		int i;
		for(i=0;i<pos-1;i++)
			p = p.next;
		if(i == pos-1){
			s.next = p.next;
			p.next = s;
			this.length++;
			return true;
		}else{
			return false;
		}
			
	}

	/**
	 * [delete description]
	 * @param  pos [delete pos]
	 * @return     [delete value]
	 */
	public int delete(int pos){
		if(pos < 1 || pos > this.length)
			return -1;
		if(this.isEmpty())
			return -1;
		LinkNode p = head;
		int i;
		for(i=0;i<pos-1;i++){
			p = p.next;
		}
		int val = 0;
		if(i == pos-1){
			val = p.next.data;
			p.next = p.next.next;
		}
		this.length--;
		return val;
	}
}

单链表主要函数解析

同样对插入和删除操作进行解析如下:

首先对于单链表插入元素:

  • 判断插入位置与顺序表是一致的
  • 生成新节点,需要动态分配内存
  • 此时如果开始结点为空,即头结点的下一个结点,将新生成的节点作为开始结点,并返回true
  • 开始结点不为空,顺序找到插入位置pos,循环之前工作结点赋值为头结点,借助循环从0开始步增到pos-2,开始结点对应下标0,那么随着循环的步进,p = p.next,循环进行到pos-2,工作结点p也到达了要插入位置的前一个结点。
  • 循环结束,此时i=pos-1,p到达要插入位置的前一个结点,修改指针链接关系,新节点的next指向p的next,注意此时p的next即为pos-1位置的节点,这样相当于将pos-1位置的节点向后推移了一位,接着修改p的next指向新节点
  • 表长加1,完成插入。
public boolean insert(int pos, int val){
	if(pos < 1 || pos > this.length+1)
		return false;

	LinkNode s = new LinkNode();
	s.data = val;
	s.next = null;

	if(head.next == null){

		head.next = s;
		this.length = 1;
		return true;
	}
		
	LinkNode p = head;
	int i;
	for(i=0;i<pos-1;i++)
		p = p.next;
	if(i == pos-1){
		s.next = p.next;
		p.next = s;
		this.length++;
		return true;
	}else{
		return false;
	}
		
}

对于单链表删除操作:

  • 同样需要先判断删除位置是否合理,与顺序表一致
  • 接着判断表是否为空,如果为空,直接返回
  • 顺序找到要删除位置的前一个位置pos-2
  • 先保存要删除位置的数据val = p.next.data;
  • 直接将pos-1位置的结点摘链,具体实现通过p.next = p.next.next;注意此时p为pos-2位置的结点
  • 表长减1,返回被删元素数据,完成删除。