备案控制台
探索云世界
开发者社区 云计算 文章 正文

数据结构一：数据+链表 （Datawhale 系列）

2019-05-11 1201
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： Task1.1 数组1.1.1实现一个支持动态扩容的数组 public class EnsureCapacityArray { private static final Object[] EMPTY_ELEMENTDATA = {}; private static ...

Task1.1 数组

1.1.1实现一个支持动态扩容的数组

    public class EnsureCapacityArray {

    private static final Object[] EMPTY_ELEMENTDATA = {};

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    transient Object[] elementData; 
    //传入固定值的情况
    public EnsureCapacityArray(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
    //没有传入数组大小的情况
    public EnsureCapacityArray() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    /**
     * 扩容
     * @param minCapacity
     */
    public void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    //数组容量最大的情况
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
}

1.1.2 实现一个大小固定的有序数组，支持动态增删改操作

这里理解，大小固定的有序数组，那也就是说数组大小和内部的元素个数完全相同。那么增的时候，需要扩容，删的时候，需要减容。然后数组有序，也就是说，改的时候需要重新排序。

public class FixedArray{
    
    private static final int DEFAULT_SIZE = 10;
    private static final Object[] EMPTY_ELEMENTDATA = {};
    private static final Object[] DEFAULT_ELEMENTDATA = new Object[DEFAULT_SIZE];
    
    transient Object[] elementData;
    
    private int size;
    
    public FixedArray(){
        this.elementData=DEFAULT_ELEMENTDATA;
    }
    
    public FixedArray(int initialCapacity){
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
    //保证增和删时数组长度和元素长度一致
    private void ensureCapacityInternal(int minCapacity ){
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    public void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    //数组容量最大的情况
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
    //去掉删除之后，重新排序的，空的数组
    public void trimToSize() {
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }
    //判断数组长度
    public int size(){
        return size;
    }
    //判断数组是否为空
    public boolean isEmpty() {
        return size == 0;
    }
    
    //排序
    @SuppressWarnings("unchecked")
    private <E> void sort() {
        Arrays.sort((E[]) elementData, 0, size);
    }
    
    //添加
    public <E> boolean add(E e) {
        ensureCapacityInternal(size + 1);  
        elementData[size++] = e;
        sort();
        return true;
    }
    //删除
    public <E> boolean remove(int index) {
        if (index >= size)
                throw new IndexOutOfBoundsException();
        
        System.arraycopy(elementData, index+1, elementData, index,
                size-1);
        size--;
        trimToSize();
        return true;
    }
    //改
    public <E> boolean set(int index,Object e) {  
        elementData[index] = e;
        sort();
        return true;
    }
    //查
    public Object get(int index) {     
        return elementData[index];
    }
}

1.1.3 合并两个有序的数组

public static int[] mergeArrays(int[]a ,int[]b){
        int alen=a.length;
        int blen=b.length;
        int aindex=0;
        int bindex=0;
        int [] re=new int[alen+blen];
        for(int i=0;i<alen+blen;i++){
            if(aindex<alen && bindex<blen){
                re[i]=a[aindex] > b[bindex] ? b[bindex++] :a[aindex++];
                continue;
            }
            if(aindex==alen && bindex<blen )
                re[i]=b[bindex++];
            if(bindex==blen &&aindex<alen)
                re[i]=a[aindex++];
        }
        return re;
    }

1.1.4学习哈希表思想，并完成leetcode上的两数之和(1)及Happy Number(202)！

哈希表

//两数之和
public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

//Happy Number(202)
class Solution {
    public boolean isHappy(int n) {
        if(n==1) return true;
        while(n!=1 && n!=4){
            int a=0;
            int ans=0;
            while(n>0){
                a=n%10;
                ans+=a*a;
                n /=10;
            }
            n=ans;
        }
        if(n==1) return true;
        else return false;
    }
}

1.1.5 练习

//Three Sum
public List<List<Integer>> threeSum(int[] num) {
    Arrays.sort(num);
    List<List<Integer>> res = new LinkedList<>(); 
    for (int i = 0; i < num.length-2; i++) {
        if (i == 0 || (i > 0 && num[i] != num[i-1])) {
            int lo = i+1, hi = num.length-1, sum = 0 - num[i];
            while (lo < hi) {
                if (num[lo] + num[hi] == sum) {
                    res.add(Arrays.asList(num[i], num[lo], num[hi]));
                    while (lo < hi && num[lo] == num[lo+1]) lo++;
                    while (lo < hi && num[hi] == num[hi-1]) hi--;
                    lo++; hi--;
                } else if (num[lo] + num[hi] < sum) lo++;
                else hi--;
           }
        }
    }
    return res;
}

//Majority Element
public int majorityElement(int[] nums) {
        int res=0;
        int cnt=0;
        for(int num:nums){
            if(cnt==0){
                res=num;
                ++cnt;
            }
            else if(num == res) ++cnt;
            else --cnt;
        }
        return res;
    }

//Missing Positive
 public int firstMissingPositive(int[] nums) {
       if(nums == null&&nums.length==0)
            return 1;
        int i;
        for(i=0;i<nums.length;i++){
           if(nums[i] != i+1){
               while(0<nums[i]&& nums[i] <= nums.length && nums[nums[i]-1] != nums[i]){
                   int temp = nums[i];
                    nums[i] = nums[nums[i]-1];
                    nums[temp-1] = temp;
               }
           }
       }
        for(i=0;i<nums.length;i++) {
            if(nums[i]!=i+1) {
                return i+1;
            }
        }
        return i+1;
    }

TASK1.2 链表

1.2.1 实现单链表、循环链表、双向链表，支持增删操作

//单链表
class singleNode{
    public int data;
    public singleNode next;
    
    public singleNode head =null;
    
    public singleNode(int data){
        this.data=data;
    }
    
    public void addNode(singleNode node){
        singleNode newNode = new singleNode(data);
        if(head == null){
            head = newNode;
            return;
        }
        singleNode temp = head;
        while(temp.next != null){
            temp = temp.next;
        }
        temp.next = newNode;
    }
    
    public boolean removeNode(int index){
        if(index<1 || index>length()){
            return false;
        }
        if(index == 1){//删除头结点
            head = head.next;
            return true;
        }
        singleNode preNode = head;
        singleNode curNode = preNode.next;
        int i = 1;
        while(curNode != null){
            if(i==index){//寻找到待删除结点
                preNode.next = curNode.next;//待删除结点的前结点指向待删除结点的后结点
                return true;
            }
            //当先结点和前结点同时向后移
            preNode = preNode.next;
            curNode = curNode.next;
            i++;
        }
        return true;
    }
     public int length(){
            int length = 0;
            singleNode curNode = head;
            while(curNode != null){
                length++;
                curNode = curNode.next;
            }
            return length;
     }
}
//双向链表
//单向循环链表类
public class CycleLinkList implements List {

    Node head; //头指针
    Node current;//当前结点对象
    int size;//结点个数
    
    //初始化一个空链表
    public CycleLinkList()
    {
        //初始化头结点，让头指针指向头结点。并且让当前结点对象等于头结点。
        this.head = current = new Node(null);
        this.size =0;//单向链表，初始长度为零。
        this.head.next = this.head;
    }
    
    //定位函数，实现当前操作对象的前一个结点，也就是让当前结点对象定位到要操作结点的前一个结点。
    //比如我们要在a2这个节点之前进行插入操作，那就先要把当前节点对象定位到a1这个节点，然后修改a1节点的指针域
    public void index(int index) throws Exception
    {
        if(index <-1 || index > size -1)
        {
          throw new Exception("参数错误！");    
        }
        //说明在头结点之后操作。
        if(index==-1)    //因为第一个数据元素结点的下标是0，那么头结点的下标自然就是-1了。
            return;
        current = head.next;
        int j=0;//循环变量
        while(current != head&&j<index)
        {
            current = current.next;
            j++;
        }
        
    }    
    
    @Override
    public void delete(int index) throws Exception {
        // TODO Auto-generated method stub
        //判断链表是否为空
        if(isEmpty())
        {
            throw new Exception("链表为空，无法删除！");
        }
        if(index <0 ||index >size)
        {
            throw new Exception("参数错误！");
        }
        index(index-1);//定位到要操作结点的前一个结点对象。
        current.setNext(current.next.next);
        size--;
    }

    @Override
    public Object get(int index) throws Exception {
        // TODO Auto-generated method stub
        if(index <-1 || index >size-1)
        {
            throw new Exception("参数非法！");
        }
        index(index);
        
        return current.getElement();
    }

    @Override
    public void insert(int index, Object obj) throws Exception {
        // TODO Auto-generated method stub
        if(index <0 ||index >size)
        {
            throw new Exception("参数错误！");
        }
        index(index-1);//定位到要操作结点的前一个结点对象。
        current.setNext(new Node(obj,current.next));
        size++;
    }

    @Override
    public boolean isEmpty() {
        // TODO Auto-generated method stub
        return size==0;
    }
    @Override
    public int size() {
        // TODO Auto-generated method stub
        return this.size;
    }
}
//双向循环链表
//单向链表类
public class DoubleCycleLinkList implements List {

    Node head; //头指针
    Node current;//当前结点对象
    int size;//结点个数

    //初始化一个空链表
    public DoubleCycleLinkList() {
        //初始化头结点，让头指针指向头结点。并且让当前结点对象等于头结点。
        this.head = current = new Node(null);
        this.size = 0;//单向链表，初始长度为零。
        this.head.next = head;
        this.head.prior = head;
    }

    //定位函数，实现当前操作对象的前一个结点，也就是让当前结点对象定位到要操作结点的前一个结点。
    public void index(int index) throws Exception {
        if (index < -1 || index > size - 1) {
            throw new Exception("参数错误！");
        }
        //说明在头结点之后操作。
        if (index == -1)
            return;
        current = head.next;
        int j = 0;//循环变量
        while (current != head && j < index) {
            current = current.next;
            j++;
        }

    }

    @Override
    public void delete(int index) throws Exception {
        // TODO Auto-generated method stub
        //判断链表是否为空
        if (isEmpty()) {
            throw new Exception("链表为空，无法删除！");
        }
        if (index < 0 || index > size) {
            throw new Exception("参数错误！");
        }
        index(index - 1);//定位到要操作结点的前一个结点对象。
        current.setNext(current.next.next);
        current.next.setPrior(current);
        size--;
    }

    @Override
    public Object get(int index) throws Exception {
        // TODO Auto-generated method stub
        if (index < -1 || index > size - 1) {
            throw new Exception("参数非法！");
        }
        index(index);

        return current.getElement();
    }

    @Override
    public void insert(int index, Object obj) throws Exception {
        // TODO Auto-generated method stub
        if (index < 0 || index > size) {
            throw new Exception("参数错误！");
        }
        index(index - 1);//定位到要操作结点的前一个结点对象。
        current.setNext(new Node(obj, current.next));
        current.next.setPrior(current);
        current.next.next.setPrior(current.next);

        size++;
    }

    @Override
    public boolean isEmpty() {
        // TODO Auto-generated method stub
        return size == 0;
    }

    @Override
    public int size() {
        // TODO Auto-generated method stub
        return this.size;
    }
}

1.2.2 实现单链表反转

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

1.2.3 实现两个有序的链表合并为一个有序链表

 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == NULL) return l2;  
        if(l2 == NULL) return l1;  
        if(l1->val < l2->val) {  
            l1->next = mergeTwoLists(l1->next, l2);  
            return l1;  
        } else {  
            l2->next = mergeTwoLists(l2->next, l1);  
            return l2;  
        }  
    }

1.2.4 实现求链表的中间结点

public ListNode middleNode(ListNode head) {
        ListNode fast=head;
        ListNode low=head;
        while(fast != null && fast.next != null){
            low = low.next;
            fast= fast.next.next;
        }
        return low;
    }

1.2.5 练习

//Linked List Cycle I（环形链表）
public boolean hasCycle(ListNode head) {
        ListNode f=head;
        ListNode s=head;
        if(head == null || head.next == null) return false;
        while(f!=null && f.next!=null){
            f=f.next.next;
            s=s.next;
            if(f == s) return true;
        }
        return false;
    }
//Merge k Sorted Lists（合并 k 个排序链表）
 public ListNode mergeKLists(ListNode[] lists){
        if(lists.length == 0)
            return null;
        if(lists.length == 1)
            return lists[0];
        if(lists.length == 2){
           return mergeTwoLists(lists[0],lists[1]);
        }

        int mid = lists.length/2;
        ListNode[] l1 = new ListNode[mid];
        for(int i = 0; i < mid; i++){
            l1[i] = lists[i];
        }

        ListNode[] l2 = new ListNode[lists.length-mid];
        for(int i = mid,j=0; i < lists.length; i++,j++){
            l2[j] = lists[i];
        }

        return mergeTwoLists(mergeKLists(l1),mergeKLists(l2));

    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        ListNode head = null;
        if (l1.val <= l2.val){
            head = l1;
            head.next = mergeTwoLists(l1.next, l2);
        } else {
            head = l2;
            head.next = mergeTwoLists(l1, l2.next);
        }
        return head;
    }
关键词：
链表数据结构
数据结构链表
数据链表
链表数据
数据结构数据
晓生寒
目录
相关文章
吹吹晚风
|
27天前
|
存储 缓存 算法
数据结构-链表(一)
链表（Linked List）是一种常见的数据结构，用于存储和组织数据。与数组不同，链表的元素（节点）在内存中不必连续存储，而是通过指针链接在一起。 链表由多个节点组成，每个节点包含两部分：数据（存储实际的元素值）和指针（指向下一个节点的引用）。链表的第一个节点称为头节点，最后一个节点称为尾节点，尾节点的指针通常指向空值（null）。
吹吹晚风
31 1
小林熬夜学编程
|
29天前
|
存储 C++
数据结构第六弹---带头双向循环链表
数据结构第六弹---带头双向循环链表
小林熬夜学编程
30 0
起飞的风筝
|
1月前
|
存储
【单链表】数据结构单链表的实现
【单链表】数据结构单链表的实现
起飞的风筝
34 0
程序员林小鹿
|
1月前
|
C++
从0开始回顾数据结构---链表与堆
#include <iostream> #include <algorithm> #include <string.h> using namespace std; const int N = 100010; int h[N], ph[N], hp[N], cnt; void heap_swap(int a, int b) { swap(ph[hp[a]],ph[hp[b]]); swap(hp[a], hp[b]); swap(h[a], h[b]); } void down(int u) { int t = u; if (u * 2 <= cnt &&
程序员林小鹿
30 2
卫卫周大胖
|
1月前
|
存储
【数据结构】双向带头循环链表的实现
【数据结构】双向带头循环链表的实现
卫卫周大胖
24 1
喵~来学编程啦
|
9天前
数据结构—链表（超详细）(山东大学）（数据结构实验三）
数据结构—链表（超详细）(山东大学）（数据结构实验三）
喵~来学编程啦
6 0
吐个泡泡。。。。
|
11天前
数据结构|双向链表|带头结点|头插|尾插|尾删|头删
数据结构|双向链表|带头结点|头插|尾插|尾删|头删
吐个泡泡。。。。
11 0
Mylvzi
|
12天前
数据结构--链表刷题(一)快慢指针（上）
数据结构--链表刷题(一)快慢指针
Mylvzi
16 0
游客i66wb7w7cg4tk
|
21天前
|
缓存 算法 搜索推荐
【数据结构】链表(单链表与双链表实现+原理+源码)
【数据结构】链表(单链表与双链表实现+原理+源码)
游客i66wb7w7cg4tk
19 1
修修修也
|
25天前
|
存储 编译器 C语言
【数据结构】深入浅出理解链表中二级指针的应用
【数据结构】深入浅出理解链表中二级指针的应用
修修修也
27 0

热门文章

最新文章

  • 1
    线性表，双向链表，静态链表，循环链表(约瑟夫环)（上）
  • 2
    【C/C++ 链表结构】探索链表迭代器：C++实现的深入分析与优化策略
  • 3
    【链表】还不会用C++实现链表？一文教会你各种链表的实现
  • 4
    算法系列--递归(一)--与链表有关（上）
  • 5
    【数据结构】链表(单链表与双链表实现+原理+源码)
  • 6
    数据结构期末复习（fengkao课堂）
  • 7
    【优选算法专栏】专题九：链表--------两两交换链表中的节点
  • 8
    数据结构--链表刷题(一)快慢指针（上）
  • 9
    算法系列--链表刷题(二)（下）
  • 10
    【C/C++ 数据结构 】从零开始实现哈希表：C++实践指南
  • 1
    数据结构：1、时间复杂度
    10
  • 2
    《Java 简易速速上手小册》第3章：Java 数据结构（2024 最新版）
    4
  • 3
    数据结构---B+Tree
    18
  • 4
    二叉树和数据结构
    15
  • 5
    二叉树（中）+Leetcode每日一题——“数据结构与算法”“剑指Offer55-I. 二叉树的深度”“100.相同的树”“965.单值二叉树”
    5
  • 6
    堆排序+TopK问题——“数据结构与算法”
    5
  • 7
    单链表——“数据结构与算法”
    6
  • 8
    Pandas数据结构详解：Series与DataFrame的奥秘
    15
  • 9
    python学习-函数模块，数据结构，字符串和列表（下）
    49
  • 10
    数据结构课程设计 仓储管理系统
    8

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法
  • 【算法实战】10. 树回归算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 图解算法小抄
    • 下一篇
    部署LAMP环境（Alibaba Cloud Linux 3）