数据结构（一）线性链表、非线性链表、稀疏数组与队列、单向链表

数据结构

数据结构分为逻辑结构和物理结构

逻辑结构

 逻辑结构:是指数据对象中数据元素之间的相互关系。其实这也是我们今后最需要关注的问题。逻辑结构分为以下四种:

1.集合结构：

2 线性结构：

3.树状结构：

4.图形结构：

物理结构：

数据结构和算法的关系

线性链表和非线性链表

非线性结构
非线性结构包括:二 维数组， 多维数组， 广义表，树结构，图结构

稀疏数组和队列

稀疏Sparsearray数组

基本介绍
当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。
稀疏数组的处理方法是: .
1)记录数组一共有几行几列，有多少个不同的值
2)把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模
右图的第一行【0】的6是一共6行，7一共7列，8指一共8个值
原来的数组是67=42大小的数组，可以将其变成93=27的稀疏数组

代码实现：

public class Sparcesearray { 
    public static void main(String[] args) { 
    //第一步 创建一个11*11的二维数组 //给二维数组中添加棋子 //1 表示黑子，2表示蓝色的，0表示没有棋子 int cheersArray[][] = new int[11][11]; cheersArray[1][2] =1; cheersArray[2][3] =2; cheersArray[4][5] =2; for (int[] ints : cheersArray) { 
    for (int i : ints) { 
    System.out.print("\t"+i); } System.out.println(); } // 获取二维数组中元素不为0的个数 sum int sum=0; for (int i = 0; i < 11; i++) { 
    for (int j = 0; j < 11; j++) { 
    if (cheersArray[i][j]!=0){ 
    sum++; } } } System.out.println("sum个数是"+sum); //创建稀疏数组 int specArray[][] =new int[sum+1 ][3]; specArray[0][0] =11; specArray[0][1] =11; specArray[0][2] =sum; //将二维数组中不为0的数放入到稀疏数组中去 int count=0; for (int i = 0; i < 11; i++) { 
    for (int j = 0; j < 11; j++) { 
    if (cheersArray[i][j]!=0){ 
    count++; specArray[count][0]=i; specArray[count][1]=j; specArray[count][2]=cheersArray[i][j]; } } } System.out.println("二维数组变成的稀疏数组是："); for (int[] ints : specArray) { 
    for (int anInt : ints) { 
    System.out.print("\t"+anInt); } System.out.println(); } System.out.println("稀疏数组再次变为原来的二维数组是"); //第三步将稀疏数组再次变成二维数组 int cheersArray2[][] =new int[specArray[0][0]] [specArray[0][1]]; //将稀疏数组中的值再次赋值给二维数组(循环从1开始，因为稀疏数组从第二行开始才是值) for (int i = 1; i <specArray.length ; i++) { 
    cheersArray2[specArray[i][0]][specArray[i][1]] =specArray[i][2]; } for (int[] ints : cheersArray2) { 
    for (int anInt : ints) { 
    System.out.print("\t"+anInt); } System.out.println(); } } } 

队列

//使用数组模拟队列 public class ArrayQueue { 
    private int maxSize;//队列最大的大小 private int front;//指向队列的头 private int real;//指向队列的尾部 private int array[];//该数组用于数据的存储，模拟队列的存取 //创建队列的构造器 public ArrayQueue(int arraymaxSize){ 
    maxSize=arraymaxSize; array=new int[maxSize]; front=-1;//指向队列头部的前一个位置 real=-1;//指向队列尾部的数据（可能是队列最后一个数据） } //是否是满的 public Boolean isFull(){ 
    return real ==maxSize-1; } //是否是空的 public Boolean isEmpty(){ 
    return front==real; } //向队列中添加数据 public void addQueue(int n){ 
    if (isFull()){ 
    System.out.println("对不起队列满了不能加入数据"); return; } real++;//尾部后移 array[real]=n; } public int getQueue(){ 
    if (isEmpty()){ 
    throw new RuntimeException("对不起，队列没有数据可取"); } front++;//让front后移 return array[front]; } //显示所有的队列数据 public void list(){ 
    if (isEmpty()){ 
    System.out.println("队列中没有数据，请先插入数据"); } for (int i = 0; i <array.length ; i++) { 
    System.out.println(+array[i]); } } //查看队列头部的数据 public int peak(){ 
    if (isEmpty()){ 
    throw new RuntimeException("队列中，没有数据请先插入数据"); } return array[front+1]; } public static void main(String[] args) { 
    ArrayQueue queue = new ArrayQueue(3); Boolean loop=true; char key =' '; Scanner scanner = new Scanner(System.in); while(loop){ 
    System.out.println("s(show) :显示对列"); System.out.println("e(exit) :退出对列"); System.out.println("a(add) :添加对列"); System.out.println("g(get) :获取对列的值"); System.out.println("h(head) :查看队列头部的值"); key= scanner.next().charAt(0); switch (key){ 
    case 's': queue.list(); break; case 'e': scanner.close(); loop=false; break; case 'a': System.out.println("请输入一个数字"); int value =scanner.nextInt(); queue.addQueue(value); break; case 'g': try{ 
    int res =queue.getQueue(); System.out.println("取出的数据是"+res); }catch (Exception e){ 
    e.printStackTrace(); } break; case 'h': try { 
    int head = queue.peak(); System.out.println("查看头部的数据是"+head); }catch (Exception e){ 
    e.printStackTrace(); } break; default:break; } } System.out.println("程序退出"); } } 

数组模拟环形队列

class CircleArray{ 
    int maxSize;//队列最大的大小 //front指向队列的第一个元素 //front=0; int front;//指向队列的头 //real指向队列最后一个元素的下一个位置 //real=0; int real;//指向队列的尾部 private int array[];//该数组用于数据的存储，模拟队列的存取 public CircleArray(int arrymaxSize){ 
    maxSize=arrymaxSize; array=new int[maxSize]; } //是否是满的 public Boolean isFull(){ 
    return ( real +1) % maxSize==front; } //是否是空的 public Boolean isEmpty(){ 
    return front==real; } //向队列中添加数据 public void addQueue(int n){ 
    if (isFull()){ 
    System.out.println("对不起队列满了不能加入数据"); return; } array[real]=n; real=(real+1) % maxSize; } //从队列中取出数据 public int getQueue(){ 
    if (isEmpty()){ 
    throw new RuntimeException("对不起，队列没有数据可取"); } //这里我们分析到front指向的默认是第一个元素 //第一步先将array【front】取出，保存在临时变量里 //第二步front后移 //第三步返回临时的变量 int value= array[front]; front=(front+1)%maxSize; return value; } //显示所有的队列数据 public void list(){ 
    if (isEmpty()){ 
    System.out.println("队列中没有数据，请先插入数据"); } for (int i = front; i <front+numbers() ; i++) { 
    System.out.println("循环队列的数据是："+i%maxSize+array[i]); } } //计算出当前有效数据的个数 public int numbers(){ 
    return (real+maxSize-front)%maxSize; } //查看队列头部的数据 public int peak(){ 
    if (isEmpty()){ 
    throw new RuntimeException("队列中，没有数据请先插入数据"); } return array[front]; } public static void main(String[] args) { 
    CircleArray queue = new CircleArray(3); Boolean loop=true; char key =' '; Scanner scanner = new Scanner(System.in); while(loop){ 
    System.out.println("s(show) :显示对列"); System.out.println("e(exit) :退出对列"); System.out.println("a(add) :添加对列"); System.out.println("g(get) :获取对列的值"); System.out.println("h(head) :查看队列头部的值"); key= scanner.next().charAt(0); switch (key){ 
    case 's': queue.list(); break; case 'e': scanner.close(); loop=false; break; case 'a': System.out.println("请输入一个数字"); int value =scanner.nextInt(); queue.addQueue(value); break; case 'g': try{ 
    int res =queue.getQueue(); System.out.println("取出的数据是"+res); }catch (Exception e){ 
    e.printStackTrace(); } break; case 'h': try { 
    int head = queue.peak(); System.out.println("查看头部的数据是"+head); }catch (Exception e){ 
    e.printStackTrace(); } break; default:break; } } System.out.println("程序退出"); } } 

链表（Linked List）

package com.zy.LinkedList; / * Created by MR.ZHANG on 2020/8/6 20:06 */ public class SingleLikedList { 
    //先初始化一个头节点，头节点不要动，不方具体的数据 private HereNode head =new HereNode(0,"",""); //添加节点到单向链表 //思路当不考虑编号顺序时， //1.找到当前链路的节点， //将最后节点的next指向新的节点 public void add(HereNode hereNode){ 
    //因为头节点不能动，所以我们需要一个临时temp去协助遍历 HereNode temp=head; //遍历链表找到最后 while(true){ 
    if (temp.next==null){ 
    break; } //如果没有找到，就将temp后移到下一个节点 temp = temp.next; } //当退出while循环时就表示，temp指向了链表的尾部 //将最后节点的next指向新的节点 temp.next=hereNode; } //第二种添加英雄的方法，按照排名插入 //如果插入的排名已经存在就不能插入成功，并返回一定的提示信息 public void addHereByOder(HereNode hereNode){ 
    //因为头节点不能动，所以我们需要辅助变量帮助我们遍历 //因为是单链表所以temp指向的是要插入结点的前一个节点 HereNode temp =hereNode; Boolean flag =false;//设置英雄是否存在，默认不存在 while(true){ 
    if (temp.next==null){ 
    //表示已经再链表的结尾 break; } if (temp.next.no>hereNode.no){ 
   //找到了可以插入的位置 break; }else if (temp.next.no==hereNode.no){ 
    flag=true;//说明已经存在 break; } temp=temp.next; } if (flag){ 
    System.out.println("角色已存在，插入失败"); }else{ 
    //插入到链表中，temp的后面 hereNode.next=temp.next; temp.next=hereNode; } } //修改节点信息，根据编号修改，不能修改编号只能修改节点的数据 public void update(HereNode newHereNode){ 
    if (head.next==null){ 
    System.out.println("链表为空"); return; } HereNode temp = head.next; boolean flag =false;//表示是否找到 while(true){ 
    if (temp==null){ 
    //表示已经遍历完了链表 break; } if (temp.no==newHereNode.no){ 
    //找到了 flag=true; break; } temp =temp.next; } if (flag){ 
    temp.name=newHereNode.name; temp.nickName=newHereNode.nickName; }else { 
    System.out.println("没有找到角色"); } } //删除链表的某一个节点 public void delete(int no){ 
    HereNode temp =head;//temp是待删除节点的上一个节点 Boolean flag =false;//判断待删除节点是否存在 while(true){ 
    if (temp.next==null){ 
   //已经到了链表的最后 break; } if (temp.next.no==no){ 
    flag=true; break; } temp=temp.next;//temp后移，这样我们才能完成循环遍历 } if (flag){ 
    temp.next=temp.next.next;//让找到的节点指向它下一个节点的下一个节点，这样没人指向它的时候，就会被GC回收掉 return; }else { 
    System.out.println("不好意思，没有找到想过要被删除的节点"); } } //查询链表集合 public void list(){ 
    //判断链表是否为空 if (head.next==null){ 
    System.out.println("链表没有数据无法遍历"); return; } //不为的情况下在再遍历输出链表数据 //因为头节点不能动，所以我们需要辅助变量来帮助我们遍历 HereNode temp =head; while(true){ 
   //判断是否走到了链表的尾部 if (temp==null){ 
    break; } System.out.println(temp); //将temp后移 否则会陷入死循环 temp =temp.next; } } } class HereNode { 
    public int no; public String name; public String nickName; public HereNode next; public HereNode(int no, String name, String nickName) { 
    this.no = no; this.name = name; this.nickName = nickName; } @Override public String toString() { 
    return "HereNode{" + "no=" + no + ", name='" + name + '\'' + ", nickName='" + nickName + '\'' + '}'; } } class test{ 
    public static void main(String[] args) { 
    HereNode hereNode1 = new HereNode(1, "宋江", "及时雨"); HereNode hereNode2 = new HereNode(2, "卢俊义", "玉麒麟"); HereNode hereNode3 = new HereNode(3, "吴用", "智多星"); HereNode hereNode4 = new HereNode(4, "林冲", "豹子头"); //加入到单向链表中 SingleLikedList list = new SingleLikedList(); list.add(hereNode1); list.add(hereNode2); list.add(hereNode3); list.add(hereNode4); // list.addHereByOder(hereNode1); // list.addHereByOder(hereNode4); // list.addHereByOder(hereNode2); // list.addHereByOder(hereNode3); list.list(); //测试更新 HereNode node = new HereNode(2, "小卢", "玉麒麟~~"); list.update(node); //测试删除 list.delete(1); System.out.println("删除后的节点情况"); list.list(); } } 

单链表面试题(新浪、百度、腾讯)

1)求单链表中有效节点的个数

public int getLength(HereNode head){ 
    if (head.next == null){ 
    return 0; } int length = 0; //定义一个辅助的temp 指向头节点的下一个节点，因为头节点没有有效数据 HereNode cur =head.next; while(cur !=null){ 
    length++; cur=cur.next; } return length; } 

获取单链表中倒数第k个节点

 //查询单链表中倒数第k个节点 //思路：编写一个方法接收head节点，同时接收index //index表示倒数第index节点 //先把链表从头到尾遍历出来，得到链表总长度getlenth（） //得到size以后就可以遍历（size-index）个 //如果找到了就返回节点否则就返回未找到 public HereNode findLastIndexNode(HereNode head ,int index){ 
    //如果链表为空，我们就返回一个null即可 if (head.next==null){ 
    return null; } //第一个遍历得到链表长度，即节点的个数 int size = getLength(head); //第二次遍历，size-index就是我们要找的倒数第k个节点 //先做index的校验 if (index<=0||index>size){ 
    return null; } //定义辅助变量cur，for循环定位到倒数的index HereNode cur = head.next; for (int i = 0; i <size-index ; i++) { 
    cur =cur.next; } return cur; } 

 //将单链表的节点翻转形成新的单链表 public static void reserveList(HereNode head){ 
    //判断，当前链表为空或者当前链表只有一个节点时不用翻转直接输出 if(head.next==null||head.next.next==null){ 
    return; } //定义一个辅助的指针帮助我们去遍历原来的链表 HereNode cur= head.next; HereNode next =null;//指向当前节点的下一个节点 HereNode reverseNode = new HereNode(0,"",""); //遍历原来的列表,并从头遍历原来的链表，将遍历出来的节点依次放入到reverseNode最前端； while(cur!=null){ 
    next=cur.next;//保存当前节点下一个节点，后面会用到 cur.next=reverseNode.next;//将cur的下一个节点指向新的链表的最前端 reverseNode.next=cur; cur=next;//让cur不断的后移 } //将head。next指向reverseNode.next，从而实现了单链表的反转 head.next=reverseNode.next; } 

从尾到头打印链表

/将单向链表从尾到头打印出来 //逆序打印单链表 public void reversePrint(HereNode head) { 
    if (head.next==null){ 
    return;//链表空直接返回 } //创建一个栈，将单向链表的数据都压入栈中 Stack<HereNode> stack = new Stack<>(); HereNode cur =head.next; while(cur!=null){ 
    stack.push(cur); cur=cur.next; } //将栈中数据弹出 while (stack.size()>0){ 
    System.out.println(stack.pop());//stack栈的特点是先进后出 } }