前言
本文主要讲解 数据结构中最基础的线性表
内容包括其特点, 结构 (顺序存储结构 & 链式结构) 等, 希望你们会喜欢.
目录
示意图
1. 简介
示意图
其中, 线性表的存储结构最为重要
下面, 我将主要讲解其 顺序存储结构 & 链式存储结构
2. 顺序存储结构
实现方式: 数组
下面, 我将主要讲解其结构特点 & 相关操作
2.1 结构特点
存储线性表的数据元素的方式 = 一段地址连续的存储单元
具备: 起始位置, 数组长度(最大存储容量) & 线性表长度(当前长度)
示意图
示意图
概念说明
概念 | 说明 |
---|---|
数组长度 | 存放线性表的空间长度(固定不变) |
线性表长度 | 存放线性表数据元素的长度(动态变化) |
地址 | 存储单元的编号 |
数组下标 | 第 i 个元素 = 数组下标第 i-1 的位置 |
2.2 对应操作
顺序存储结构的操作包括: 插入 & 删除
操作 1: 插入
示意图
操作 2: 删除
示意图
注: 线性表的存取数据时间性能 = O(1)
2.3 结构优, 缺点
示意图
2.4 应用场景
已知长度, 数据元素个数变化不大, 存, 取数据频率高的场景
2.5 总结
示意图
3. 链式存储结构
实现方式: 链表
下面, 我将主要讲解其结构特点 & 相关操作
3.1 结构特点
示意图
链表示意图(以单链表为例)
示意图
存储元素说明示意图
示意图
下面将主要重点讲解各种链表:(重点讲解)单链表, 双向链表, 循环链表, 静态链表
3.2 单链表
3.2.1 定义
每个结点只有 1 个指针域
3.2.2 示意图
示意图
3.2.3 操作(读取, 插入, 删除, 整表创建, 整表删除)
读取
算法思路: 工作指针向后移
- int j ;
- // 1. 声明 1 动态指针
- LinkList p ;
- // 2. 让 p 指向链表 L 的第一个结点
- // L = 头结点
- p = L ->next
- // 3. 设置计数器
- j = 1;
- while ( p && j<i ){
- p = p->next;// 指向下一个结点
- ++j;
- }
- // 直到到了 i 结点, 直接取出
- e = p->data
插入
通过遍历找到 i 结点, 生成一个空结点, 然后插入
示意图
删除
示意图
整表创建
示意图
整表删除
示意图
单链表实现
- public class UnidirectionalLinkedList<T> {
- /**
- * 设置结点结构
- */
- // a. 结点结构
- private class Node<T>{
- private T data;
- private Node<T> next ;
- public Node(T data){
- this.data = data;
- }
- }
- // b. 头结点
- private Node<T> first;
- // c. 当前结点
- private Node<T> currentNode;
- // d. 链表长度
- private int size;
- /**
- * 构造函数
- * 作用: 初始化结点
- */
- public UnidirectionalLinkedList(){
- currentNode = first = null;
- size = 0;
- }
- /**
- * 1. 添加结点
- * 内容: 在头 / 尾 添加结点 & 在特定位置插入结点
- */
- // a. 在链表头部加入 1 个结点
- // 即, 把新加入的结点设置为第一结点
- public void addFirstNode(T data){
- // 1. 将需添加的内容封装成结点
- Node<T> newNode = new Node<T>(data);
- // 2. 将新添加结点的指针域指向旧第 1 个结点
- newNode.next = first;
- // 3. 将新添加结点设置为第 1 个结点
- first = newNode;
- // 4. 链表长度 + 1
- size++;
- }
- // b. 在链表尾部加入 1 个结点
- // 即, 把新加入的结点设置为最后结点
- public void addNode(T data){
- // 1. 检查当前链表是否为空
- if (isEmpty()){
- addFirstNode(data);
- return;
- }
- // 2. 把当前指针定位到最后一个结点
- locateNode(size-1);
- // 3. 将需添加的内容封装成结点
- currentNode.next = new Node<T>(data);
- // 4. 链表长度 + 1
- size++;
- }
- // c. 在链表中插入结点
- public T insertNode(int index, T data) {
- // 1. 检查当前链表是否为空
- if (isEmpty()){
- addFirstNode(data);
- return null;
- }
- // 2. 把当前指针定位到需插入的结点位置
- locateNode(index);
- // 3. 将需添加的内容封装成结点
- Node<T> insertNode = new Node<T>(data);
- // 4. 把需插入结点位置的下 1 个结点 赋给 插入的结点
- insertNode.next = currentNode.next;
- // 5. 把插入结点 赋给 需插入的结点的位置
- currentNode.next = insertNode;
- // 6. 链表长度 + 1
- size++;
- // 7. 返回插入结点的数据
- return insertNode.data;
- }
- /**
- * 2. 删除结点
- * 内容: 删除第 1 个结点 & 删除特定位置的结点
- */
- // a. 删除第 1 个结点, 并返回该结点数据
- public T removeFirstNode() {
- // 1. 检查当前链表第一个结点是否为空
- if (first == null){
- try {
- throw new Exception("链表为空!");
- } catch (Exception e) {
- e.printStackTrace();
- }
- }
- // 2. 获取被删除结点的数据
- T temp = first.data;
- // 3. 将第 2 个结点设置为第 1 个结点
- first = first.next;
- // 4. 链表长度减 1
- size--;
- // 5. 返回被删除结点的数据
- return temp;
- }
- // b. 删除特定位置的结点, 并将里面的数据返回
- public T removeNode(int index) {
- // 1. 检查当前链表是否为空
- if (isEmpty()){
- try {
- throw new Exception("链表为空!");
- } catch (Exception e) {
- e.printStackTrace();
- }
- }
- // 2. 把当前指针 (currentNode) 定位到 需删除结点 (index) 的前 1 个结点
- locateNode(index-1);
- // 3. 获取被删除结点的数据
- T temp = currentNode.next.data;
- // 4. 将需删除结点 (index) 的前 1 个结点 的下 1 个结点 设置为 需删除结点 (index) 的下 1 个结点
- currentNode.next = currentNode.next.next;
- // 5. 链表长度减 1
- size--;
- // 6. 返回被删除结点的数据
- return temp;
- }
- /**
- * 3. 获取特定位置的结点
- * 内容: 将当前指针 (currentNode) 定位到所需结点位置, 根据索引位置获取结点数据
- */
- // a. 将当前指针 (currentNode) 定位到所需结点位置
- private void locateNode(int index){
- // 1. 判断指针是否越界
- if (index <0 && index>size){
- try {
- throw new IndexOutOfBoundsException("参数越界!");
- } catch (Exception e) {
- e.printStackTrace();
- }
- }
- int i = 0;
- // 2. 通过遍历链表, 寻找索引 index 所指结点
- for(currentNode = first; currentNode.next != null && i <index; i++){
- currentNode = currentNode.next;
- }
- }
- // b. 根据索引位置获取结点数据
- public T getNode(int index) {
- // 1. 判断链表是否为空
- if (isEmpty()){
- try {
- throw new Exception("链表为空!");
- } catch (Exception e) {
- e.printStackTrace();
- }
- }
- // 2. 把当前指针 (currentNode) 定位到 所需索引位置(index)
- locateNode(index);
- // 3. 返回当前指针的数据, 即所需索引位置的数据
- return currentNode.data;
- }
- /**
- * 检查当前链表是否为空
- */
- public boolean isEmpty(){
- if (size == 0){
- return true;
- }else {
- return false;
- }
- }
- public static void main(String[] args){
- // 1. 创建链表 & 加入结点数据
- UnidirectionalLinkedList<Integer> list = new UnidirectionalLinkedList<Integer>();
- list.addNode(1);
- list.addNode(2);
- list.addNode(3);
- list.addNode(4);
- list.addNode(5);
- // 2. 输出当前链表数据
- System.out.println("链表数据如下:");
- for (int i = 0; i < list.size;i++){
- try {
- System.out.print(list.getNode(i)+" ");
- } catch (Exception e) {
- e.printStackTrace();
- }
- }
- System.out.println("-----------------------");
- // 3. 获得某个位置结点的数据
- System.out.println("位置 3 的数据是:" + list.getNode(3));
- System.out.println("-----------------------");
- // 4. 插入结点: 在位置 4 插入, 数据 = 66
- System.out.println("在位置 4 插入的 data:"+list.insertNode(3,66));
- System.out.println("插入后:");
- for (int i = 0; i < list.size;i++){
- try {
- System.out.print(list.getNode(i)+" ");
- } catch (Exception e) {
- e.printStackTrace();
- }
- }
- System.out.println("-----------------------");
- // 5. 删除结点
- System.out.println("删除 index 为 3 的 data:"+list.removeNode(3));
- System.out.println("删除后:");
- for (int i = 0; i < list.size;i++){
- try {
- System.out.print(list.getNode(i)+" ");
- } catch (Exception e) {
- e.printStackTrace();
- }
- }
- }
- }
测试结果
链表数据如下: 1 2 3 4 5
-----------------------
位置 3 的数据是: 4
-----------------------
在位置 4 插入的 data:66
插入后: 1 2 3 4 66 5
-----------------------
删除 index 为 3 的 data:4
删除后: 1 2 3 66 5
3.3 循环链表
定义
将单链表的终端结点的指针指向头结点, 使得单链表头尾相接, 形成 1 个环
也称单循环链表
示意图
示意图
3.4 双向链表
3.4.1 定义
每个结点有 2 个指针域: 1 指向后驱结点元素, 2 指向前驱结点元素
即 在单链表的结点中, 再设置一个指向前驱结点的指针域
3.4.2 示意图
示意图
3.4.3 链表操作(插入 & 删除)
示意图
注: 插入 & 删除都需要同时改变 2 个指针变量
3.4.4 特点
缺点: 占用空间多 = 记录 2 个指针
优点: 算法时间性能高 = 良好对称性(前, 后指针)
即, 用空间换时间
3.5 静态链表
示意图
4. 存储结构对比
示意图
5. 总结
本文主要讲解了数据结构中最基础的线性表
下面我将继续对 数据结构, 有兴趣可以继续关注 Carson_Ho 的安卓开发笔记
请点赞! 因为你的鼓励是我写作的最大动力!
来源: http://www.jianshu.com/p/c229d07db14c