数据结构

数组

稀疏数组

当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组。
稀疏数组的处理方法是:

  1. 记录数组一共有几行几列,有多少个不同的值
  2. 把具有不同值的元素的行列及值记录在一个小规模的数组中,从而缩小程序的规模

    案列
    [二维数组]{.label .info}—》》[稀疏数组]{.label .warning}
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    public static void main(String[] args) {
    //根据二维数组创建稀疏数组
    int[][] a= new int[11][11];
    a[1][2] = 1; a[2][3] = 2;
    //遍历原数组
    int val=0;//有效值数量
    int[] vals = new int[100];//定义一个有效数组存放数据
    for(int i = 0; i < a.length-1; i++){
    for(int j =0; j < a[1].length-1;j++){
    if(a[i][j] != 0){
    val++;

    }
    }
    }
    System.out.println("原数组");
    for(int[] row : a){
    for(int col : row){
    System.out.print(col+"\t");
    }
    System.out.println();
    }

    //创建稀疏数组
    System.out.println("有效数据"+val);
    int[][] b= new int[val+1][3];
    int count=0;
    b[0][0] = 11;b[0][1] = 11; b[0][2]=val;
    for(int i = 0; i < a.length-1; i++){
    for(int j =0; j < a[1].length-1;j++){
    if(a[i][j] != 0){
    count++;
    b[count][0] = i;
    b[count][1] = j;
    b[count][2] = a[i][j];

    }
    }
    }

    for(int[] row : b){
    for(int col : row){
    System.out.print(col+"\t");
    }
    System.out.println("");
    }
    }
    [稀疏数组]{.label .info}—》》[二维数组]{.label .warning}
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    //根据稀疏数组创建二维数组
    int[][] a = new int[3][3];
    a[0][0] = 11;a[0][1]=11;a[0][2]=2;
    a[1][0]=1;a[1][1]=2;a[1][2]=1;
    a[2][0]=2;a[2][1]=3;a[2][2]=2;
    //创建二维数组
    int[][] b = new int[a[0][0]][a[0][1]];
    for(int i = 1; i < a.length;i++ ){
    b[a[i][0]][a[i][1]] = a[i][2];
    }

    for(int[] row : b){
    for(int col : row){
    System.out.print(col+"\t");
    }
    System.out.println("");
    }

    队列

    数组模拟队列

  • 队列是一个有序列表,可以用数组或是链表来实现。
  • 遵循先入先出的原则。即:先存入队列的数据,要先取出。后存入的要后取出
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    private int maxSize;
    private int front;
    private int rear;
    private int[] a;
    public queue(int maxSize){
    this.maxSize = maxSize;
    a = new int[maxSize];
    front = -1;
    rear = -1;
    }
    public boolean isFull(){
    return rear == maxSize;
    }
    public boolean isEmpty(){
    return front == rear;
    }
    public void addQueue(int n){
    if(!isFull()){
    rear++;
    a[rear] = n;
    }else{
    throw new RuntimeException("队列已满");
    }
    }
    public int getQueue(){
    if(!isEmpty()){
    front++;
    return a[front];
    }else{
    throw new RuntimeException("队列为空");
    }
    }
    public void showQueue(){
    if(!isEmpty()){
    for(int i = front+1; i <= rear; i++){
    System.out.println(a[i]);
    }
    }else{
    System.out.println("empty!");
    }

    }

    将队列改进为循环队列

    循环队列队头指针为front,队尾指针为rear;循环队列长度为N。其队内有效长度为?
    +++info
    (rear - front + maxSize) % MaxSize
    +++
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
     public static void main(String[] args) {
    queue2 q = new queue2(3);
    Scanner sc = new Scanner(System.in);
    int n ;
    char chose;
    //测试
    while(true){
    System.out.println("a---添加数据");
    System.out.println("g---弹出数据");
    System.out.println("s---展示数据");
    System.out.println("e---退出程序");
    chose = sc.next().charAt(0);
    switch(chose){
    case 'a':
    System.out.println("请输入增加的值:");
    n = sc.nextInt();
    q.addQueue(n);
    break;
    case 'g':
    System.out.println("data:"+q.getQueue());
    break;
    case 's':
    q.showQueue();
    break;
    case 'e':
    System.exit(0);
    default:
    break;
    }
    }
    }
    }
    class queue2{
    private int maxSize;
    private int front;
    private int rear;
    private int[] a;
    queue2(int maxSize){
    this.maxSize = maxSize;
    a = new int[maxSize];
    front = 0;
    rear = 0;
    }
    private boolean isFull(){
    //判断队列是否已满
    return (rear+1) % maxSize == front;
    }
    private boolean isEmpty(){
    return front == rear;
    }
    void addQueue(int n){
    if(!isFull()){
    a[rear] = n;
    rear = (rear+1) % maxSize;
    }else{
    throw new RuntimeException("队列已满");
    }
    }
    int getQueue(){
    if(!isEmpty()){
    //获取队列的头元素
    int value = a[front];
    front = (front + 1) % maxSize;
    return value;
    }else{
    throw new RuntimeException("队列为空");
    }
    }
    void showQueue(){
    if(isEmpty()){
    throw new RuntimeException("队列为空");
    }
    //从front开始遍历
    int val = (rear+maxSize - front) % maxSize;
    for(int i = front; i < front+ val; i ++){
    System.out.println(a[i % maxSize]);
    }
    }

    }

    链表

    单链表

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147

    public class singleLinkedList {
    /**
    * @Author panther
    * @return 演示单链表
    **/
    public static void main(String[] args) {
    //test
    heroNode hero1 = new heroNode(1,"松江","及时雨");
    heroNode hero2 = new heroNode(3,"林冲","豹子头");
    heroNode hero3 = new heroNode(2,"无用","智多星");

    singlelist slink = new singlelist();
    slink.insert(hero1);
    slink.insert(hero2);
    slink.insert(hero3);

    slink.show();
    slink.update(2);
    slink.show();

    slink.delete(2);
    slink.show();
    }
    }
    //单链表
    class singlelist{
    //创建一个头节点,不存放数据
    private heroNode head = new heroNode(0,"","");
    //添加算法
    public void add(heroNode hn){
    heroNode temp = head;
    while(true){
    if(temp.next ==null){
    break;
    }
    temp = temp.next;
    }
    temp.next = hn;
    }
    //插入算法
    public void insert(heroNode hn){
    heroNode temp = head;
    boolean flag = false;
    while(true){
    if(temp.next == null){
    break;
    }
    if(temp.next.no > hn.no){
    break;
    }else if(temp.next.no == hn.no){
    System.out.println("数据存在");
    flag = true;
    break;
    }
    temp = temp.next;
    }
    if(flag){
    System.out.println("数据存在");
    }else{
    hn.next = temp.next;
    temp.next = hn;
    }

    }
    //删除算法
    public void delete(int hno){
    heroNode temp = head;
    boolean flag = false;
    while(true){
    if(temp.next == null ){
    System.out.println("no data");
    break;
    }
    if(temp.next.no == hno){
    flag = true;
    break;
    }
    temp = temp.next;
    }
    if (flag) {
    temp.next = temp.next.next;
    }else{
    System.out.println("no data");
    }

    }
    //修改算法,根据no修改
    public void update(int hno){
    Scanner sc = new Scanner(System.in);
    heroNode temp = head;
    boolean flag = false;
    while(true){
    if(temp.next == null){
    break;
    }
    if(temp.next.no == hno){
    temp = temp.next;
    flag = true;
    break;
    }
    temp = temp.next;
    }
    if(flag){
    System.out.println("new name:");
    temp.name = sc.nextLine();
    System.out.println("new nickname");
    temp.nickname = sc.nextLine();
    }else{
    System.out.println("无数据");
    }
    }

    //显示算法
    public void show(){
    if(head == null){
    throw new RuntimeException("链表为空");
    }
    heroNode temp = head.next;
    while(true){
    //判断链表是否在末尾
    if(temp == null){
    break;
    }
    System.out.println(temp);
    temp = temp.next;
    }
    }
    }

    //节点数据
    class heroNode{
    public int no;
    protected String name;
    protected String nickname;
    public heroNode next;

    public heroNode(int no, String name,String nickname){
    this.no = no;
    this.name = name;
    this.nickname = nickname;
    }
    @Override
    public String toString(){
    return "hero:" + "no:"+no+"\t"+"name:"+name+"\t"+"nickname:"+nickname;
    }
    }