数据结构和算法

数据结构和算法

• 一、稀疏数组和队列
• • 1、稀疏数组
  • • 1.1、基本功能
    • 1.2、处理方法
    • 1.3、转换思路
  • 2、队列
  • • 2.1、定义
    • 2.2、模拟思路
    • • ~1、入队出队操作模拟
      • ~2、实现代码
    • 2.3、环形队列
    • • ~1、代码
• 二、链表
• • 1、单向链表
  • • 1.1、链表的介绍
    • 1.2、实现思路
  • 2、双向链表
  • • 2.1、双向链表
    • 2.2、实现思路
  • 3、循环链表
  • • 3.1、循环链表

一、稀疏数组和队列 1、稀疏数组 1.1、基本功能

当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组

1.2、处理方法

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

如图，把一个6X7的二维数组变为了一个9X3的稀疏数组。其中

• 第一行保存的是原二维数组的行、列以及非0值的个数
• 第二到九行保存的是每个非0值所在的位置及其数值

1.3、转换思路

二维数组转稀疏数组

• 遍历二维数组，得到二维数组中有效值的个数sum
• 创建稀疏数组，有sum+1行，3列（固定）
• 将二维数组中的有效值存入稀疏数组中

稀疏数组转二维数组

• 先读取稀疏数组的第一行（保存二维数组的行列信息），还原二维数组
• 读取稀疏数组的其他行，将值赋给二维数组的对应位置上的数

代码

public class Demo2 {
   public static void main(String[] args) {
      //创建一个二维数组
      int[][] arr1 = new int[11][11];
      //向二维数组里放值
      arr1[1][2] = 1;
      arr1[2][3] = 2;
      arr1[3][4] = 3;

      //打印二维数组
      System.out.println("遍历二维数组");
      for (int i = 0; i < arr1.length; i++) {
         for (int j = 0; j < arr1[0].length; j++) {
            System.out.print(arr1[i][j] + "   ");
         }
         System.out.println();
      }

      //二位数组----->稀疏数组
      //遍历二维数组中有效值的个数,用sum来记录
      int sum = 0;
      for (int i = 0; i < arr1.length; i++) {
         for (int j = 0; j < arr1[0].length; j++) {
            if (arr1[i][j] != 0) {
               //二维数组中元素不为0即为有效值
               sum++;
            }
         }
      }

      //创建稀疏数组
      //行数为sum+1，第一行用于保存二维数组的行列及有效值个数，列数固定为3
      int[][] sparseArr = new int[sum + 1][3];
      //存入二维数组的行列及有效值个数
      sparseArr[0][0] = arr1.length;
      sparseArr[0][1] = arr1[0].length;
      sparseArr[0][2] = sum;

      //再次遍历二维数组，将有效值存入稀疏数组
      //用于保存稀疏数组的行数
      int count = 1;
      for (int i = 0; i < arr1.length; i++) {
         for (int j = 0; j < arr1[0].length; j++) {
            if (arr1[i][j] != 0) {
               //将值存入稀疏数组
               sparseArr[count][0] = i;
               sparseArr[count][1] = j;
               sparseArr[count][2] = arr1[i][j];
               count++;
            }
         }
      }

      //打印稀疏数组
      System.out.println("遍历稀疏数组");
      for (int i = 0; i < sparseArr.length; i++) {
         for (int j = 0; j < sparseArr[0].length; j++) {
            System.out.print(sparseArr[i][j] + "   ");
         }
         System.out.println();
      }


      //稀疏数组------>二维数组
      //先得到二位数组的行列数
      int row = sparseArr[0][0];
      int col = sparseArr[0][1];
      int[][] arr2 = new int[row][col];

      //遍历稀疏数组，同时给二维数组赋值
      for (int i = 1; i < sparseArr.length; i++) {
         row = sparseArr[i][0];
         col = sparseArr[i][1];
         //该位置上对应的值
         int val = sparseArr[i][2];
         arr2[row][col] = val;
      }

      //打印二维数组
      System.out.println("遍历还原后的二维数组");
      for (int i = 0; i < arr2.length; i++) {
         for (int j = 0; j < arr2[0].length; j++) {
            System.out.print(arr2[i][j] + "   ");
         }
         System.out.println();
      }
   }
}

运行结果

遍历二维数组
0   0   0   0   0   0   0   0   0   0   0   
0   0   1   0   0   0   0   0   0   0   0   
0   0   0   2   0   0   0   0   0   0   0   
0   0   0   0   3   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
遍历稀疏数组
11   11   3   
1   2   1   
2   3   2   
3   4   3   
遍历还原后的二维数组
0   0   0   0   0   0   0   0   0   0   0   
0   0   1   0   0   0   0   0   0   0   0   
0   0   0   2   0   0   0   0   0   0   0   
0   0   0   0   3   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0

2、队列 2.1、定义

• 队列是一个有序列表，可以用数组或是链表来实现。
• 遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出

2.2、模拟思路

• 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量
• 因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及 rear分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear则是随着数据输入而改变，如图所示

~1、入队出队操作模拟

当我们将数据存入队列时称为”addQueue”，addQueue 的处理需要有两个步骤：

• 将尾指针往后移：rear+1 , 当 front == rear 时，队列为空
• 若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear所指的数组元素中，否则无法存入数据。rear == maxSize - 1时，队列满

注意：front指向的是队列首元素的前一个位置

~2、实现代码

public class Demo3 {
   public static void main(String[] args) {
      ArrayQueue queue = new ArrayQueue(5);
      queue.addNum(1);
      queue.addNum(2);
      queue.addNum(3);
      queue.addNum(4);
      queue.addNum(5);
      System.out.println(queue.getNum());
      queue.showQueue();
   }
}

class ArrayQueue {
   //队列的大小
   int maxSize;
   //用数组来实现队列
   int[] arr;
   //指向队列首元素的前一个位置
   int front;
   //指向队列的尾元素
   int rear;

   public ArrayQueue(int maxSize) {
      this.maxSize = maxSize;
      arr = new int[this.maxSize];
      //front指向队列首元素的前一个位置
      front = -1;
      rear = -1;
   }


   public boolean isFull() {
      return rear == maxSize - 1;
   }


   public boolean isEmpty() {
      return front == rear;
   }


   public void addNum(int num) {
      if(isFull()) {
         System.out.println("队列已满，无法在进行入队操作");
         return;
      }
      //队尾标记后移，指向要放入的元素的位置
      rear++;
      arr[rear] = num;
   }

   public int getNum() {
      if(isEmpty()) {
         throw new RuntimeException("队列为空，无法出队");
      }
      //队首标记后移，指向队首元素
      System.out.print("出队元素是：");
      front++;
      return arr[front];
   }

   public void showQueue() {
      if(isEmpty()) {
         throw new RuntimeException("队列为空，无法遍历");
      }
      System.out.println("遍历队列");
      //从front+1开始读取元素
      for(int start = front+1; start<=rear; start++) {
         System.out.println(arr[start]);
      }
   }
}

运行结果

出队元素是：1
遍历队列
2
3
4
5

2.3、环形队列

思路：

• front变量指向队首元素，初值为0
• rear变量指向队尾元素的下一个元素，初值为0。规定空出一个位置
• 队列为空的判定条件：front == rear
• 队列为满的判定条件：(rear + 1) % maxSize == front
• 队列中有效元素的个数：(rear - front + maxSize) % maxSize
• 入队和出队时，都需要让标记对maxSize取模

~1、代码

public class Demo4 {
   public static void main(String[] args) {
      ArrayAroundQueue aroundQueue = new ArrayAroundQueue(5);
      aroundQueue.addNum(1);
      aroundQueue.addNum(2);
      aroundQueue.addNum(3);
      aroundQueue.addNum(4);
      aroundQueue.showQueue();
      System.out.println(aroundQueue.getNum());
      System.out.println(aroundQueue.getNum());
      aroundQueue.addNum(5);
      aroundQueue.addNum(6);
      aroundQueue.showQueue();
      aroundQueue.getHead();
   }
}

class ArrayAroundQueue {
   //队列的大小
   int maxSize;
   //用数组来实现队列
   int[] arr;
   //指向队列首元素的前一个位置
   int front;
   //指向队列的尾元素
   int rear;

   public ArrayAroundQueue(int maxSize) {
      this.maxSize = maxSize;
      arr = new int[this.maxSize];
      //front指向队列首元素的前一个位置
      front = 0;
      rear = 0;
   }


   public boolean isFull() {
      return (rear+1)%maxSize == front;
   }


   public boolean isEmpty() {
      return front == rear;
   }


   public void addNum(int num) {
      if(isFull()) {
         System.out.println("队列已满，无法在进行入队操作");
         return;
      }
      //先放入元素，在后移队尾标记
      arr[rear] = num;
      rear = (rear+1)%maxSize;
   }

   public int getNum() {
      if(isEmpty()) {
         throw new RuntimeException("队列为空，无法出队");
      }
      //队首标记后移，指向队首元素
      System.out.print("出队元素是：");
      int num = arr[front];
      front = (front+1)%maxSize;
      return num;
   }

   public void showQueue() {
      if(isEmpty()) {
         throw new RuntimeException("队列为空，无法遍历");
      }
      System.out.println("遍历队列");
      //当front + 1 == rear时停止遍历
      int start = front;
      while(start != rear) {
         System.out.println(arr[start]);
         //移动到下一个元素
         start = (start+1)%maxSize;
      }
   }

   public void getHead() {
      if(isEmpty()) {
         throw new RuntimeException("队列为空");
      }

      System.out.println("队首元素为："+arr[front]);
   }
}

运行结果

遍历队列
1
2
3
4
出队元素是：1
出队元素是：2
遍历队列
3
4
5
6
队首元素为：3

二、链表 1、单向链表 1.1、链表的介绍

链表在内存中的存储

特点

• 链表是以节点的方式来存储,是链式存储
• 每个节点包含 data 域 和 next 域。next域用来指向下一个节点
• 链表的各个节点不一定是连续存储的
• 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

带头结点的逻辑示意图

1.2、实现思路

创建（添加）

• 先创建一个Head头节点，表示单链表的头
• 后面我们每添加一个节点，就放在链表的最后

遍历

• 通过一个辅助变量，来遍历整个链表

有序插入

• 先遍历链表，找到应该插入的位置
• 要插入的节点的next指向插入位置的后一个节点
• 插入位置的前一个节点的next指向要插入节点
• 插入前要判断是否在队尾插入

根据某个属性节点修改值

• 先遍历节点，找到修改的位置
• 如果未找到修改节点，则不修改

删除某个节点

• 先遍历节点，找到要删除节点的前一个节点
• 进行删除操作

求倒数第n个节点的信息

• 遍历链表，求出链表的有效长度length（不算头结点）
• 遍历链表到第length-n的节点

翻转链表

• 创建一个新的头结点，作为新链表的头
• 从头遍历旧链表，将遍历到的节点插入新链表的头结点之后
• 注意需要用到两个暂存节点
  一个用来保存正在遍历的节点
  一个用来保存正在遍历节点的下一个节点

逆序打印

• 遍历链表，将遍历到的节点入栈
• 遍历完后，进行出栈操作，同时打印出栈元素

代码

public class Demo1 {
	public static void main(String[] args) {
		linkedList linkedList = new linkedList();
		linkedList.traverseNode();
		System.out.println();
		//创建学生节点，并插入链表
		StudentNode student1 = new StudentNode(1, "Nyima");
		StudentNode student3 = new StudentNode(3, "Lulu");
		linkedList.addNode(student1);
		linkedList.addNode(student3);
		linkedList.traverseNode();
		System.out.println();

		//按id大小插入
		System.out.println("有序插入");
		StudentNode student2 = new StudentNode(0, "Wenwen");
		linkedList.addByOrder(student2);
		linkedList.traverseNode();
		System.out.println();

		//按id修改学生信息
		System.out.println("修改学生信息");
		student2 = new StudentNode(1, "Hulu");
		linkedList.changeNode(student2);
		linkedList.traverseNode();
		System.out.println();

		//根据id删除学生信息
		System.out.println("删除学生信息");
		student2 = new StudentNode(1, "Hulu");
		linkedList.deleteNode(student2);
		linkedList.traverseNode();
		System.out.println();

		//获得倒数第几个节点
		System.out.println("获得倒数节点");
		System.out.println(linkedList.getStuByRec(2));
		System.out.println();

		//翻转链表
		System.out.println("翻转链表");
		linkedList newlinkedList = linkedList.reverseList();
		newlinkedList.traverseNode();
		System.out.println();

		//倒叙遍历链表
		System.out.println("倒序遍历链表");
		newlinkedList.reverseTraverse();

	}
}


class linkedList {
	//头节点，防止被修改，设置为私有的
	private StudentNode head = new StudentNode(0, "");

	
	public void addNode(StudentNode node) {
		//因为头节点不能被修改，所以创建一个辅助节点
		StudentNode temp = head;
		//找到最后一个节点
		while (true) {
			//temp是尾节点就停止循环
			if(temp.next == null) {
				break;
			}
			//不是尾结点就向后移动
			temp = temp.next;
		}
		//现在temp是尾节点了，再次插入
		temp.next = node;
	}

	
	public void traverseNode() {
		System.out.println("开始遍历链表");
		if(head.next == null) {
			System.out.println("链表为空");
		}
		//创建辅助节点
		StudentNode temp = head.next;
		while(true) {
			//遍历完成就停止循环
			if(temp == null) {
				break;
			}
			System.out.println(temp);
			temp = temp.next;
		}
	}

	
	public void addByOrder(StudentNode node) {
		//如果没有首节点，就直接插入
		if(head.next == null) {
			head.next = node;
			return;
		}
		//辅助节点，用于找到插入位置和插入操作
		StudentNode temp = head;
		//节点的下一个节点存在，且它的id小于要插入节点的id，就继续下移
		while (temp.next!=null && temp.next.id < node.id) {
			temp = temp.next;
		}
		//如果temp的下一个节点存在，则执行该操作
		//且插入操作，顺序不能换
		if(temp.next != null) {
			node.next = temp.next;
		}
		temp.next = node;
 	}

	
 	public void changeNode(StudentNode node) {
		if(head == null) {
			System.out.println("链表为空，请先加入该学生信息");
			return;
		}
		StudentNode temp = head;
		//遍历链表，找到要修改的节点
		while (temp.next!= null && temp.id != node.id) {
			temp = temp.next;
		}
		//如果temp已经是最后一个节点，判断id是否相等
		if(temp.id != node.id) {
			System.out.println("未找到该学生的信息，请先创建该学生的信息");
			return;
		}
		//修改学生信息
		temp.name = node.name;
	}

	
	public void deleteNode(StudentNode node) {
 		if(head.next == null) {
			System.out.println("链表为空");
			return;
		}
 		StudentNode temp = head.next;
 		//遍历链表，找到要删除的节点
 		if(temp.next!=null && temp.next.id!=node.id) {
 			temp = temp.next;
		}
 		//判断最后一个节点的是否要删除的节点
 		if(temp.next.id != node.id) {
			System.out.println("请先插入该学生信息");
			return;
		}
 		//删除该节点
 		temp.next = temp.next.next;
	}

	
	public StudentNode getStuByRec(int index) {
		if(head.next == null) {
			System.out.println("链表为空!");
		}
		StudentNode temp = head.next;
		//用户记录链表长度，因为head.next不为空，此时已经有一个节点了
		//所以length初始化为1
		int length = 1;
		while(temp.next != null) {
			temp = temp.next;
			length++;
		}
		if(length < index) {
			throw new RuntimeException("链表越界");
		}

		temp = head.next;
		for(int i = 0; i stack = new Stack<>();
		while(temp != null) {
			stack.push(temp);
			temp = temp.next;
		}

		while (!stack.isEmpty()) {
			System.out.println(stack.pop());
		}
	}
}


class StudentNode {
	int id;
	String name;
	//用于保存下一个节点的地址
	StudentNode next;

	public StudentNode(int id, String name) {
		this.id = id;
		this.name = name;
	}

	@Override
	public String toString() {
		return "StudentNode{" +
				"id=" + id +
				", name='" + name + ''' +
				'}';
	}
}

结果

开始遍历链表
链表为空

开始遍历链表
StudentNode{id=1, name='Nyima'}
StudentNode{id=3, name='Lulu'}

有序插入
开始遍历链表
StudentNode{id=0, name='Wenwen'}
StudentNode{id=1, name='Nyima'}
StudentNode{id=3, name='Lulu'}

修改学生信息
开始遍历链表
StudentNode{id=0, name='Wenwen'}
StudentNode{id=1, name='Hulu'}
StudentNode{id=3, name='Lulu'}

删除学生信息
开始遍历链表
StudentNode{id=0, name='Wenwen'}
StudentNode{id=3, name='Lulu'}

获得倒数节点
StudentNode{id=0, name='Wenwen'}

翻转链表
开始遍历链表
StudentNode{id=3, name='Lulu'}
StudentNode{id=0, name='Wenwen'}

倒序遍历链表
StudentNode{id=0, name='Wenwen'}
StudentNode{id=3, name='Lulu'}

2、双向链表 2.1、双向链表

2.2、实现思路

遍历

• 和单向链表的遍历相同，需要一个辅助节点来保存当前正在遍历的节点

添加

• 双向链表多出了一个frnot，所以在添加时，要让新增节点的front指向链表尾节点

修改

• 和单向链表的修改相同

删除

• 使用temp来保存要删除的节点
• temp.pre.next指向temp.next
• temp.next指向temp.pre

代码

public class Demo2 {
   public static void main(String[] args) {
      BidirectionalList bidirectionalList = new BidirectionalList();
      bidirectionalList.addNode(new PersonNode(1, "Nyima"));
      bidirectionalList.addNode(new PersonNode(2, "Lulu"));
      bidirectionalList.traverseNode();
      System.out.println();

      System.out.println("修改节点信息");
      bidirectionalList.changeNode(new PersonNode(2, "Wenwen"));
      bidirectionalList.traverseNode();
      System.out.println();

      //删除节点
      System.out.println("删除节点");
      bidirectionalList.deleteNode(new PersonNode(1, "Nyima"));
      bidirectionalList.traverseNode();
   }
}

class BidirectionalList {
   private final PersonNode head = new PersonNode(-1, "");

   
   public boolean isEmpty() {
      return head.next == null;
   }

   
   public void addNode(PersonNode node) {
      PersonNode temp = head;
      if(temp.next != null) {
         temp = temp.next;
      }
      //插入在最后一个节点的后面
      temp.next = node;
      node.front = temp;
   }

    public void traverseNode() {
       System.out.println("遍历链表");
      if (isEmpty()) {
         System.out.println("链表为空");
         return;
      }
      PersonNode temp = head.next;
      while(temp != null) {
         System.out.println(temp);
         temp = temp.next;
      }
    }

   
    public void changeNode(PersonNode node) {
      if(isEmpty()) {
         System.out.println("链表为空");
         return;
      }
      PersonNode temp = head.next;
      //用于判定是否做了修改
      boolean flag = false;
      while (temp != null) {
         if(temp.id == node.id) {
            //匹配到节点，替换节点
            temp.front.next = node;
            node.next = temp.next;
            flag = true;
         }
         temp = temp.next;
      }
      if(!flag) {
         System.out.println("未匹配到改人信息");
      }

    }

   
    public void deleteNode(PersonNode node) {
      if(isEmpty()){
         System.out.println("链表为空");
         return;
      }
      PersonNode temp = head.next;
      //查看是否删除成功
       boolean flag = false;
      while(temp != null) {
         if(temp.id == node.id) {
            temp.front.next = temp.next;
            temp.next = null;
            flag = true;
         }
         temp = temp.next;
      }
      if(!flag) {
         System.out.println("未找到该节点");
      }
    }


}

class PersonNode {
   int id;
   String name;
   //指向下一个节点
   PersonNode next;
   //指向前一个节点
   PersonNode front;

   public PersonNode(int id, String name) {
      this.id = id;
      this.name = name;
   }

   @Override
   public String toString() {
      return "PersonNode{" +
            "id=" + id +
            ", name='" + name + ''' +
            '}';
   }
}

输出

遍历链表
PersonNode{id=1, name='Nyima'}
PersonNode{id=2, name='Lulu'}

修改节点信息
遍历链表
PersonNode{id=1, name='Nyima'}
PersonNode{id=2, name='Wenwen'}

删除节点
遍历链表
PersonNode{id=2, name='Wenwen'}

3、循环链表 3.1、循环链表

单链表的尾节点指向首节点，即可构成循环链表