数据结构---Java版

文章目录

• 概述
• 线性表
• • 顺序表
  • 单链表
  • 单链表的循环链表
  • 双向链表

概述

🎈数据结构通常有四种基本类型：集合结构，线性结构（一对一），树形结构（一对多），图形结构或网状结构（多对多）；主要描述的三个方面的内容：数据的逻辑结构、物理结构、数据的操作集合。
🎈数据的逻辑结构与数据在计算机中的具体存储没有关系，主要包括集合、线性、树形、图形结构，有两个要素，数据结构的集合（D）和D上的关系集（反映了D中元素的前驱后继关系）。
🎈数据的物理结构又称存储结构，有顺序和链式两种方式：
🎶顺序存储的特点是数据元素在存储器中的相对位置来说体现数据元素的逻辑关系，通常用一维数组来实现。
🎶链式存储是通过一组任意的存储单元来存储数据元素的，而这些存储单元可以是连续的，也可以是不连续的，这种结构内存利用率低。
🎶在顺序存储结构的基础上，又可以延伸出索引存储（在数据文件的基础上增加了一个索引表的文件）和散列存储（通过数据元素与储存地址之间建立起某种映射关系，使每个数据达到与每一个存储地址之间尽量达到一一对应的目的）。
🎈一个算法应具有五个特征：
🎶有穷性，一个算法在执行若干个操作步骤之后应该能够结束，且每一步在合理时间内完成。
🎶确定性，每个步骤有确切含义，无二义性。
🎶可行性，每个步骤都能经过已经实现的基本运算的有限次执行得以实现。
🎶输入，指算法在执行时，从外界获取的数据。
🎶输出，算法对输入数据处理后的结果，没有输出的算法是无意义的。
🎈算法效率的度量：
🎶正确性，算法的执行结果应满足预先规定的功能和性能要求，且对输入、输出处理的明确而无歧义。
🎶可读性，书写应思路清晰，层次分明，简单明了，易读易懂。
🎶健壮性，有很强的容错能力，输入不合法时，算法能进行适当的处理，尤其是细致考虑边界情况和异常情况，以免引起严重的后果。
🎶运行时间，算法在计算机上运行时所花费的时间，对于同一个问题由多种算法可选择时，尽可能选择执行时间短的。
🎶占用空间，算法占用的存储空间是指算法执行过程中需要的最大存储空间。
🎈算法效率分析：
🎶时间复杂度，记为T(n)=O(f(n))，通常是估算数量级（eg.O(n^3))。
🎶空间复杂度，记为S(n)=O(f(n))，n是问题的规模。

线性表

n个数据元素的有限序列

顺序表

定义：指的是用一组地址连续的存储单元一次存储线性表的数据元素。
顺序表的定义需要深入理解顺序表下标pos和数组下标的关系，顺序表长度length和数组长度的关系。

//基本操作的实现
public class Main {public static void main(String[] args) {L<Character> l = new L<>(5);//输入l.add('a', 1);l.add('b', 2);l.add('c', 3);l.add('d', 4);l.add('f', 5);//输出顺序表l.nextOrder();System.out.println();//顺序表长度System.out.println(l.size());//顺序表是否为空System.out.println(l.isEmpty());//顺序表第三个元素的值System.out.println(l.value(3));//在第5个位置插入el.add('e',5);l.nextOrder();System.out.println();//删除第三个元素l.remove(3);l.nextOrder();//清空表l.clear();}}

//顺序表的定义类
class sequenceList<T> {final int maxSize = 10;private T[] listArray;private int length;public sequenceList() {length = 0;//线性表的初始值listArray= (T[]) new Object[maxSize];}public sequenceList(int n) {if (n <= 0) {System.out.println("error");System.exit(1);}length = 0;listArray = (T[]) new Object[n];}//    插入public boolean add(T obj, int pos) {if (pos < 1 || pos > length + 1) {System.out.println("pos不合法");return false;}if (length == listArray.length) {T[] p = (T[]) new Object[length * 2];for (int i = 0; i < length; i++) {p[i] = listArray[i];}listArray = p;}for (int i = length; i >= pos; i--) {listArray[i] = listArray[i - 1];}listArray[pos - 1] = obj;length++;return true;}//删除public T remove(int pos) {if (isEmpty()) {System.out.println("顺序表为空，无法执行删除操作");return null;} else {if (pos < 1 || pos > length) {System.out.println("pos不合法");return null;}T x = listArray[pos - 1];for (int i = pos; i < length; i++) {listArray[i - 1] = listArray[i];}length--;return x;}}//查找public int find(T obj) {if (isEmpty()) {System.out.println("顺序表为空");return -1;} else {for (int i = 0; i < length; i++) {if (listArray[i].equals(obj)) {return i + 1;}}return -1;}}//获取元素public T value(int pos) {if (isEmpty()) {System.out.println("顺序表为空");return null;} else {if (pos < 1 || pos > length) {System.out.println("pos不合法");return null;}return listArray[pos - 1];}}//判空public boolean isEmpty() {return length == 0;}//更新元素public boolean modify(T obj, int pos) {if (isEmpty()) {System.out.println("顺序表为空");return false;} else {if (pos < 1 || pos > length) {System.out.println("pos不合法");return false;}listArray[pos - 1] = obj;return true;}}//求长度public int size(){return length;}public void nextOrder(){for (int i = 0; i < length; i++) {System.out.println(listArray[i]);}}
}

单链表

此链表的每个节点中只有一个指向后继的指针

力扣（2、两数相加）给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

package test3;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class Main {public static void main(String[] args) {//示例1addTwoNumbers(new ListNode(2,new ListNode(4,new ListNode(3))),new ListNode(5,new ListNode(6,new ListNode(4))));}public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode head = null, tail = null;int carry = 0;//进位while (l1 != null || l2 != null) {int n1 = l1 != null ? l1.val : 0;int n2 = l2 != null ? l2.val : 0;int sum = n1 + n2 + carry;if (head == null) {head = tail = new ListNode(sum % 10);} else {tail.next = new ListNode(sum % 10);tail = tail.next;}carry = sum / 10;if (l1 != null) {l1 = l1.next;}if (l2 != null) {l2 = l2.next;}}if (carry > 0) {tail.next = new ListNode(carry);}//返回的是链表的头节点，head=7，与例子相照应return head;}
}
//结点类的泛型定义
class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) {this.val = val;}ListNode(int val, ListNode next) {this.val = val;this.next = next;}
}

单链表的循环链表

表中最后一个结点的指针域不为空，而是指向表头结点，整个链表形成一个环。

力扣（61、旋转链表）给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

思路：先将给定的链表连接成环，然后将指定位置断开。

public class Main2 {public ListNode rotateRight(ListNode head, int k) {if (head==null||k==0){return head;}int n=1;ListNode p=head;//求出链表长度while (p.next!=null){p=p.next;//循环完后，p指向链表的最后n++;}int i=n-k%n;//链长-移动的位数if (i==n){return head;}p.next=head;//让尾结点的指针域指向头结点,形成环while (i-- >0){p=p.next;}ListNode ret=p.next;//ret=3p.next=null;//把环形链表断开return ret;}
}class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) {this.val = val;}ListNode(int val, ListNode next) {this.val = val;this.next = next;}
}

双向链表

//存储结构
class DuNode<T>{T data;DuNode<T> prior;DuNode<T> next;public DuNode(DuNode<T> n){next=n;prior=null;}public DuNode(T obj,DuNode<T> n,DuNode<T> p){data=obj;next=n;prior=p;}
}

双向链表中结点的插入
p引用双向链表中值为的b结点，s引用待插入的值为x的结点。

s.prior=p.prior;//s的前驱等于p的前驱，data
p.prior.next=s;//p的前驱结点的后继变为了s
s.next=p;//s的后继为p
p.prior=s;//p的前驱更新为s

双向链表中结点的删除
设p引用双向链表中的某结点

p.prior.next=p.next;//p的前驱结点的后继为p的后继
p.next.prior=p.prior;//p的后继结点的前驱为p的前驱

是哪个大怨种在别人已经回家的时候要期中考试，是我呀！

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！