大话数据结构学习笔记-第三章线性表

大话数据结构学习笔记-第三章线性表

目录:

一.大话数据结构电子图书下载地址二.线性表三.顺序存储结构

1.什么是顺序存储结构?2.顺序存储结构索引表常用 *** 作代码

(1) 存和插入 *** 作(增)(2) 删除 *** 作(删)(3) 修改元素 *** 作(改)(4) 获取元素 *** 作(查) 3.线性表顺序存储结构的优缺点 四.链式存储结构

1.顺序存储结构不足的解决办法2.链式存储结构3.单链表

(1).单链表常用 *** 作代码

1.单链表的插入(增)2.单链表的结点删除(删)3.单链表的修改(改)4.单链表的读取(查) (2).单链表的插入和删除分析(3).单链表结构与顺序存储结构优缺点 4.静态链表

(1).什么是静态链表(2).静态链表的组成(3).通过Java代码实现静态链表 5.循环链表

(1).什么是循环链表(2).循环链的组成 6.双向链表

(1).什么是双向链表(2).双向链表的组成(3).双向链表的总结

一.大话数据结构电子图书下载地址

大话数据结构下载链接 百度网盘密码:i70v

二.线性表

什么是线性表?
书上的定义：零个或多个数据元素的有限序列。


星座列表是否为一个线性表:是的

某家公司的组织架构是否为线性表:不是的

本章节框架图如下:
线性表有二种物理结构即顺序存储结构和链式存储结构

三.顺序存储结构 1.什么是顺序存储结构?

书中的定义:线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。

用一段地址连续的存储单元存放数据元素数据元素的数据类型相同

通过上面二点我们可以通过一维数组来实现顺序存储结构:

线性表的索引(线性表的索引从1开始,数组从0开始)

线性表的抽象数据类型

线性表的长度应该小于等于数组的长度

2.顺序存储结构索引表常用 *** 作代码

项目结构:

SequentialStructure.java

package lineartable;

import org.omg.CORBA.IdentifierHelper;

public class SequentialStructure {
	// 数组的容量
	public final int maxSize;
	// 数组
	private T[] array;
	// 数据长度
	public int length;

	// 初始化线性表(对应抽象数据类型表中的InitList(*L))
	@SuppressWarnings("unchecked")
	public SequentialStructure(int maxSize) {
		// 初始化容量
		this.maxSize = maxSize;
		// 创建一个空的线性表
		array = (T[]) new Object[this.maxSize];
		// 初始化数据长度为0
		this.length = 0;
	}

	// insert:插入数据(对应抽象数据类型表中的ListInsert(*L,i,e))
	public boolean insert(int index, T data) {
		// 线性表中数据已满
		if (this.length == this.maxSize) {
			throw new RuntimeException("插入数据失败:线性表中数据已满!");
		}
		// 插入的位置有误
		if (index > this.length + 1 || index < 1) {
			throw new RuntimeException("插入数据失败:插入的位置不在线性表范围内!");
		}
		// 插入的数据不在表尾
		if (index <= this.length) {
			// 将要插入位置后的数据元素向后移动一位
			for (int i = this.length; i >= index - 1; i--) {
				array[i + 1] = array[i];
			}
		}
		array[index - 1] = data;
		this.length++;

		return true;
	}

	public boolean insert(T data) {
		// 线性表中数据已满
		if (this.length == this.maxSize) {
			throw new RuntimeException("插入数据失败:线性表中数据已满!");
		}

		array[this.length] = data;
		this.length++;
		return true;
	}

	// 查找线性表指定索引位置上的数据
	public T getElem(int index) {
		if (index < 1 || index > this.length || this.length == 0) {
			return null;
		}

		return array[index - 1];
	}

	
	//  删除线性表上指定索引位置上的数据
	public boolean delete(int index) {
		if (this.length == 0) {
			return false;
		}
		if (index < 1 || index > this.length) {
			throw new RuntimeException("删除数据失败:删除的位置不在线性表范围内!");
		}
		
				
		// 删除的时候不在末尾,数据要前移
		if (index < this.length) {
			for (int i = index; i < this.length; i++) {
				array[i - 1] = array[i];
			}
		}
		
		this.length--;
		
		return true;
	}

	// 修改数据元素
	public boolean update(int index, T data) {
		if (this.length == 0) {
			return false;
		}
		if (index < 1 || index > this.length) {
			throw new RuntimeException("修改数据失败:修改的位置不在线性表范围内!");
		}

		array[index - 1] = data;

		return true;
	}

}

(1) 存和插入 *** 作(增)

不带索引增 *** 作(存 *** 作)

Java代码如下:

关于不带索引增 *** 作的算法复杂度:
最坏情况复杂度为:O(1)
平均复杂度:O(1)

带索引增 *** 作(插入 *** 作)
插入算法思路:

Java代码实现如下:

关于数据元素后移:

从最后面的元素开始依次向后移动


然后将数据插入到指定位置上即可

运行效果:


关于带索引增 *** 作的算法复杂度:
最坏情况复杂度为:O(n)
平均复杂度:O(n-1/2)=O(n)

(2) 删除 *** 作(删)

删除算法思路:

Java代码实现如下:

关于数据前移：

从离索引最近的一个元素开始依次向前移


将最后一个元素移除

运行效果:


关于删除 *** 作的算法复杂度:
最坏情况复杂度为:O(n)
平均复杂度:O(n-1/2)=O(n)

(3) 修改元素 *** 作(改)

Java代码如下:

运行效果:

关于修改元素的算法复杂度:
最坏情况复杂度为:O(1)
平均复杂度:O(1)

(4) 获取元素 *** 作(查)

线性表索引从1开始,而数组从0开始所以获取线性表指定索引上的元素需要索引要减1

Java代码实现如下:
关于获取元素 *** 作的算法复杂度:
最坏情况复杂度为:O(1)
平均复杂度:O(1)

3.线性表顺序存储结构的优缺点

四.链式存储结构 1.顺序存储结构不足的解决办法

2.链式存储结构

书中的定义:

3.单链表

书中的定义:
数据域: 存储数据元素信息的域
指针域: 存储一个指示其直接后继的信息(即直接后继的存储位置)

对于线性表来说，总得有个头有个尾，链表也不例外。我们把链表中第一个结点的存储位置叫做头指针，那么整个链表的存取就必须是从头指针开始进行了。之后的每一个结点，其实就是上一个的后继指针指向的位置。想象一下，最后一个结点，它的指针指向哪里?
最后一个，当然就意味着直接后继不存在了,所以我们规定，线性链表的最后一个结点指针为“空”(通常用 NULL 或“^”符号表示，如图3-6-3所示)。

有时，我们为了更加方便地对链表进行 *** 作，会在单链表的第一个结点前附设一个结点，称为头结点,头结点的数据域可以不存储任何信息,也可以存储如线性表的长度等附加信息，头结点的指针域存储指向第一个结点的指针,如图3-6-4所示。

关于头指针与头结点的异同?

(1).单链表常用 *** 作代码

线性表链式存储结构代码描述:

若线性表为空表，则头结点的指针域为“空”,如图3-6-6所示。
单链表的存储示意图
带有头节点的单链表示意图
空链表示意图

通过Java代码实现单链表,下面介绍几种常用 *** 作:
项目结构:

Node.java(用于表示结点)

Singlelink.java

package singlelinkedlist;

public class Singlelink {
	private Node head;// 链表的头节点
	private Node last;// 链表的尾节点
	public int length = 0;// 节点数量

	public Singlelink() {
		this.head = null;
		this.last = null;
	}

	public Singlelink(T data) {
		this.head = new Node(data);
		this.last = this.head;
		length++;
	}

	// 头结点尾插入
	public boolean insert(T data) {
		Node newNode = new Node(data);
		// 一个结点都没有,将当前结点设为头结点
		if (this.length == 0) {
			this.head = newNode;
			this.last = newNode;
		} else {
			// 已经有头结点了,增加新节点
			this.last.next = newNode;
			this.last = newNode;
		}
		length++;
		return true;
	}

	// 头结点前插入
	public boolean insertHead(T data) {
		if (this.length == 0) {
			return insert(data);
		}
		Node temp = this.head;
		this.head = new Node(data);
		this.head.next = temp;
		length++;
		return true;
	}

	// 从指定位置插入
	@SuppressWarnings("unused")
	public boolean insert(int index, T data) {
		if (index < 0) {
			throw new IndexOutOfBoundsException("索引越界:" + index);
		}
		// 插入的位置在头部
		if (index == 0) {
			return insertHead(data);
		} else if (index >= this.length || this.length == 0) {
			// 插入的位置在尾部
			return insert(data);
		} else {
			// 插入中间
			Node upNode=this.head;
			Node currentNode=upNode.next;
			int j=1;
			while(currentNode!=null && j newNode=new Node(data);
			upNode.next=newNode;
			newNode.next=currentNode;
			
			length++;
		}
		return true;
	}

	// 获取结点数据
	public T getElem(int index) {
		// 判断查询的索引是否越界
		if (index < 0 || index > this.length) {
			throw new IndexOutOfBoundsException("索引越界:" + index);
		}

		// 获取头结点
		Node hNode = this.head;
		int i = 1;
		while (hNode != null && i <= index) {
			hNode = hNode.next;
			++i;
		}
		return hNode.data;// 返回index对应结点的数据
	}

	// 从尾节点删除
	@SuppressWarnings("unchecked")
	public boolean deleteLast() {
		if (this.length == 0) {
			// 没有元素。删除失败，抛出异常
			throw new RuntimeException("删除失败,没有元素删除!");
		}
		if (length == 1) {
			// 只有一个元素，头尾元素相同，直接删除
			this.head = null;
			this.last = null;
		} else {
			// 含义多个元素
			@SuppressWarnings("rawtypes")
			Node lastNode = head;
			// lastNode.next不会空指针就执行完毕，以为last存在
			while (lastNode.next != this.last) {
				lastNode = lastNode.next;
			}
			this.last = lastNode;
			this.last.next = null;
		}
		length--;
		return true;
	}

	// 从指定位置删除
	public boolean delete(int index) {
		if (this.length == 0) {
			// 没有元素。删除失败，抛出异常
			throw new RuntimeException("删除失败,没有元素删除!");
		}
		if (index < 0 || index > this.length - 1) {
			// 下标越界
			throw new IndexOutOfBoundsException();
		}
		if (index == 0) {
			// 删除头部
			return deleteHead();
		} else if (index == this.length - 1) {
			// 删除尾部
			return deleteLast();
		} else {
			// 删除中间，至少有3个元素
			// 上一个元素
			Node upNode = this.head;
			// 当前元素
			Node currentNode = upNode.next;
			// 下一个元素
			Node downNode = currentNode.next;
			int j = 1;
			while (currentNode != null && j < index) {
				upNode=currentNode;
				currentNode=upNode.next;
				downNode=currentNode.next;
				++j;
			}
			
			upNode.next=downNode;
			length--;
			return true;
		}
	}

	// 删除头部元素
	public boolean deleteHead() {
		if (this.length == 0) {
			// 没有元素。删除失败，抛出异常
			throw new RuntimeException("删除失败,没有元素删除!");
		}
		if (length == 1) {
			// 只有一个元素，头尾元素相同，直接删除
			this.head = null;
			this.last = null;
		} else {
			// 含义多个元素
			Node currect = this.head.next;
			this.head = currect;
		}
		length--;
		return true;
	}
 	// 修改结点数据
	public boolean update(T data,T newData) {
		Node tempNode=this.head;
		while(tempNode!=null){
			if (tempNode.data.equals(data)) {
				tempNode.data=newData;
				return true;
			}
			tempNode=tempNode.next;
		}
		return false;
	}

}

1.单链表的插入(增)

头结点尾插入
有二种情况,情况一单链表中没有头结点,插入的数据就是头结点,情况二单链表中有头结点,从尾节点插入,尾结点的指针域指向新结点,然后将新结点设为尾节点。
Java代码如下:

头结点前插入
有二种情况,情况一单链表中没有头结点,插入的数据就是头结点,情况二单链表中有头结点,从头结点处插入,插入的数据就是头结点,然后当前头结点指针域指向以前的头结点。
Java代码如下:

指定位置插入
有三种情况,情况一从头结点处插入(index=0),情况二从尾节点处插入(index>=this.length(单链表的长度)),情况三从结点中间插入。
从结点中间插入,通过下面的例子来理解:
需求:
创建一个单链表
创建四个结点(包括头结点),结点数据分别为1,3,4,5
在结点1和结点2之间插入一个新结点(该结点data为2)

在结点1和结点2之间插入新结点只需要将插入位置上的结点前一个结点指向新的结点,新的结点指向该位置下一个结点。指针指向情况如下:

插入之后的指针指向情况如下

Java代码如下:
要实现上面的 *** 作,只需要知道指定位置上的结点和该结点上一结点,然后再修改指向,创建二个结点(当前位置结点(默认为头结点的下一结点),当前位置上一结点(默认为头结点))通过当前位置结点依次向尾结点移动,直到当前结点到达指定位置停止,在移动的过程中当前位置结点和上一结点都会依次变化,最后再修改指针指向。
Java代码如下:

2.单链表的结点删除(删)

从头部元素删除
有三种情况,情况1一个结点都没有,提示用户删除失败,情况2只有一个结点,头尾结点相同，直接删除,情况3有多个结点,只需要获取头结点的下一个结点然后将该结点设为头结点即可。
Java代码如下:

从尾节点删除
有三种情况前面二种情况和从头部元素删除的前二种情况是相同的,最后一种情况,通过获取尾结点前一个结点,然后将该结点设为尾节点即可。
Java代码如下:

从指定位置删除
有三种情况,从头部元素删除,从尾节点删除和从中间结点删除,从中间结点删除思路和前面插入思路差不多。
只需要获取要删除位置的前一个结点和后一个结点,然后将前一个结点的指针指向下一个结点(前一个结点和后一个结点的获取和前面思路一致)。
Java代码如下:

3.单链表的修改(改)

从当前结点开始依次向下一个结点移动,直到有要修改值为止,然后将旧值修改成新值。
Java代码如下:

4.单链表的读取(查)

从当前结点开始依次向下一个结点移动,直到i<=index,然后返回当前index的结点。
Java代码如下:

分析:

(2).单链表的插入和删除分析

(3).单链表结构与顺序存储结构优缺点

4.静态链表 (1).什么是静态链表

问题:

解决办法:

答:用数组描述链表叫做静态链表

(2).静态链表的组成

(3).通过Java代码实现静态链表

项目来源于:【Java】 大话数据结构(3) 线性表之静态链表
项目结构:

SNode.java(相当于单链表中的结点)

Student.java

StaticlinkList.java

package staticlinklist;

public class StaticlinkList {
	private SNode[] nodes;// 结点数组
	private int maxSize;

	public StaticlinkList() {
		this(1000);
	}

	public StaticlinkList(int maxSize) {
		this.maxSize = maxSize;
		nodes = new SNode[this.maxSize];// 泛型的数组建立似乎有些问题
		for (int i = 0; i < this.maxSize - 1; i++) {
			nodes[i] = new SNode(null, i + 1);
		}
		nodes[maxSize - 1] = new SNode(null, 0);
	}

	
	public int getIndex(int i) {
		if (i < 1 || i > this.getLength())
			throw new RuntimeException("查找位置错误！");
		int k = nodes[maxSize - 1].cur;
		for (int j = 1; j < i; j++)
			k = nodes[k].cur;
		return k;
	}

	
	public SNode getElement(int i) {
		return nodes[getIndex(i)];
	}

	
	public int malloc_sll() {
		int i = nodes[0].cur;
		nodes[0].cur = nodes[i].cur;// 第i个分量要拿来用了，所以指向下一个分量
		// 注意，不是nodes[0].cur=nodes[0].cur+1，下一个分量不一定就是下标加一;
		return i;
	}

	
	public void listInsert(int i, E e) {
		if (i < 1 || i > this.getLength() + 1)
			throw new RuntimeException("插入位置错误！");
		if (getLength() == maxSize - 2)
			throw new RuntimeException("表已满，无法插入！");
		int j = this.malloc_sll();
		nodes[j].data = e;
		int p;  第i-1个元素的下标
		if (i == 1) {
			p = maxSize - 1;
		} else {
			p = getIndex(i - 1);
		}
		nodes[j].cur = nodes[p].cur;
		nodes[p].cur = j;
	}

	
	public SNode listDelete(int i) {
		if (i < 1 || i > getLength())
			throw new RuntimeException("删除位置错误！");
		int m = getIndex(i);
		int p; // 第i-1个元素的下标
		if (i == 1) {
			p = maxSize - 1;
		} else {
			p = getIndex(i - 1);
		}
		nodes[p].cur = nodes[m].cur;
		free_sll(m);
		return nodes[m];
	}

	
	public void free_sll(int i) {
		nodes[i].cur = nodes[0].cur;
		nodes[0].cur = i;
	}

	
	public int getLength() {
		int length = 0;
		int i = nodes[maxSize - 1].cur;
		while (i != 0) {
			i = nodes[i].cur;
			length++;
		}
		return length;
	}

}

StaticlinkListTest.java(测试代码)

package staticlinklist;

public class StaticlinkListTest {
	public static void main(String[] args) {
		StaticlinkList students = new StaticlinkList();
		System.out.println("——————————插入1到5,并读取内容——————————");
		Student[] stus = { new Student("小A", 11), new Student("小B", 12), new Student("小C", 13), new Student("小D", 14),
				new Student("小E", 151) };
		for (int i = 1; i <= 5; i++)
			students.listInsert(i, stus[i - 1]);
		System.out.println("表长：" + students.getLength());
		Student stu;
		for (int i = 1; i <= 5; i++) {
			stu = students.getElement(i).data;
			System.out.println("第" + i + "个位置为：" + stu.name);
		}
		System.out.println("——————————删除小B、小E——————————");
		stu = students.listDelete(2).data;
		System.out.println("已删除：" + stu.name);
		stu = students.listDelete(4).data;
		System.out.println("已删除：" + stu.name);
		System.out.println("当前表长：" + students.getLength());
		for (int i = 1; i <= students.getLength(); i++) {
			stu = students.getElement(i).data;
			System.out.println("第" + i + "个位置为：" + stu.name);
		}
		System.out.println("表长：" + students.getLength());
	}

}

运行效果:

5.循环链表 (1).什么是循环链表

问题:

解决办法:

答：将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表

(2).循环链的组成

循环链头结点(循环链表带有头结点的空链表如图3-13-3)

对于非空的循环链表就如图3-13-4所示。

上面循环链表存在的问题:


采用尾指针可以很好的将二个循环链表组成一个表：
比如下面的这两个循环链表，它们的尾指针分别是 rearA 和 rearB，如图3-13-6所示。

要想把它们合并,只需要如下的 *** 作即可,如图3-13-7所示。
6.双向链表 (1).什么是双向链表

问题:


解决办法:

答:双向链表(double linked list)是在单链表的每个结点中，再设置一个指向其前驱结点的指针。

(2).双向链表的组成

双向链表的循环带头结点的空链表如图3-14-3所示。

非空的循环的带头结点的双向链表如图3-14-4所示。
(3).双向链表的总结