数据结构和算法——数据结构

数据结构：

线性结构：

顺序存储方式，顺序表

常见的顺序存储结构有：数组、队列、链表、栈

链式存储方式，链表

 队列：

队列可以使用数组结构或者链表结构来存储，先入先出，后进后出。

数组结构的队列：
public class Demo {public static void main(String[] args) {CircleArrayQueue arrayQueue = new CircleArrayQueue(3);char key;Scanner scanner = new Scanner(System.in);boolean loop = true;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':arrayQueue.showQueue();break;case 'a':System.out.println("请输入一个数字");int value = scanner.nextInt();arrayQueue.addQueue(value);break;case 'g':try {int res = arrayQueue.getQueue();System.out.println("取出的数据为=" + res);} catch (Exception e) {System.out.println(e.getMessage());}break;case 'e':loop = false;scanner.close();System.out.println("程序退出...");break;case 'h':try {int res = arrayQueue.headQueue();System.out.println("查看的数据为=" + res);} catch (Exception e) {System.out.println(e.getMessage());}break;default:break;}}}
}class CircleArrayQueue {private int maxSize;// 指向队列头的位置private int front;// 指向队列尾的数据的下一个的位置，它指向的队尾的数据代表有值的private int rear;private int[] arr;public CircleArrayQueue(int arrMaxSize) {// 实际上队列有maxSize个元素，因为空出了一个位置maxSize = arrMaxSize + 1;arr = new int[maxSize];front = rear = 0;}public boolean isFull() {return (rear + 1) % maxSize == front;}public boolean isEmpty() {return front == rear;}public void addQueue(int n) {if (isFull()) {System.out.println("队列为满，不能加入数据");return;}arr[rear] = n;rear++;if (rear % maxSize == 0) {rear = 0;}}public int getQueue() {if (isEmpty()) {throw new RuntimeException("队列为空，不能取值");}int res = arr[front];front++;if (front % maxSize == 0) {front = 0;}return res;}public void showQueue() {if (isEmpty()) {System.out.println("队列为空，没有数据");return;}
//        for (int i = front; i != rear; i = (i + 1) % maxSize) {for (int i = front; i < front + size(); i++) {System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);}}public int headQueue() {if (isEmpty()) {throw new RuntimeException("队列为空，没有头数据");}return arr[front];}private int size() {return (rear + maxSize - front) % maxSize;}
}
链表结构的队列：
public class SingleLinkListDemo {public static void main(String[] args) {HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");HeroNode hero3 = new HeroNode(3, "吴用", "智多星");SingleLinkList singleLinkList = new SingleLinkList();singleLinkList.add(hero3);singleLinkList.add(hero2);singleLinkList.add(hero1);
//        singleLinkList.add(hero3);
//        HeroNode newHero = new HeroNode(3, "张三", "法外狂徒");
//        singleLinkList.update(newHero);HeroNode delHero1 = new HeroNode(1, "", "");singleLinkList.del(delHero1);singleLinkList.reverse();singleLinkList.list();}
}class SingleLinkList {private HeroNode headNode = new HeroNode(0, "", "");// 非递归反转public void reverse3() {if (headNode.getNext() == null || headNode.getNext().getNext() == null) {return;}HeroNode nextNode1, nextNode2, nextNode3;nextNode1 = headNode.getNext();nextNode2 = nextNode1.getNext();nextNode3 = nextNode2.getNext();nextNode2.setNext(nextNode1);nextNode1.setNext(null);while (nextNode3 != null) {nextNode1 = nextNode2;nextNode2 = nextNode3;nextNode3 = nextNode3.getNext();nextNode2.setNext(nextNode1);}headNode.setNext(nextNode2);}// 递归反转public void reverse() {HeroNode nextNode = headNode.getNext();headNode.setNext(reverse2(headNode.getNext()));nextNode.setNext(null);}private HeroNode reverse2(HeroNode heroNode) {if (heroNode.getNext() != null) {HeroNode lastNode = reverse2(heroNode.getNext());heroNode.getNext().setNext(heroNode);return lastNode;}return heroNode;}public void del(HeroNode delHeroNode) {if (headNode.getNext() == null) {System.out.println("链表为空");return;}HeroNode preNode, nextNode;preNode = headNode;nextNode = headNode.getNext();while (nextNode != null) {if (nextNode.getNo() == delHeroNode.getNo()) {preNode.setNext(nextNode.getNext());// nextNode.setNext(null);return;}preNode = nextNode;nextNode = nextNode.getNext();}System.out.println("删除编号= " + delHeroNode.getNo() + " 的元素没有找到");}public void update(HeroNode newHeroNode) {if (headNode.getNext() == null) {System.out.println("链表为空");return;}HeroNode preNode, nextNode;preNode = headNode;nextNode = headNode.getNext();while (nextNode != null) {if (nextNode.getNo() == newHeroNode.getNo()) {newHeroNode.setNext(nextNode.getNext());preNode.setNext(newHeroNode);return;}preNode = nextNode;nextNode = nextNode.getNext();}System.out.println("编号= " + newHeroNode.getNo() + " 的元素没有找到");}public void add(HeroNode heroNode) {HeroNode nextNode, preNode;preNode = headNode;nextNode = headNode.getNext();// 头插法if (nextNode == null) {headNode.setNext(heroNode);heroNode.setNext(null);return;}// 中插法while (nextNode != null) {if (heroNode.getNo() < nextNode.getNo()) {preNode.setNext(heroNode);heroNode.setNext(nextNode);return;}// 相同的数据不能进行插入if (heroNode.getNo() == nextNode.getNo()) {System.out.println("编号=" + heroNode.getNo() + " 已存在，不能添加");return;}preNode = nextNode;nextNode = nextNode.getNext();}// 尾插法preNode.setNext(heroNode);heroNode.setNext(null);}public void list() {HeroNode tmpNode = headNode.getNext();if (tmpNode == null) {System.out.println("链表为空");return;}while (tmpNode != null) {System.out.println("node= " + tmpNode + " -->");tmpNode = tmpNode.getNext();}}
}@Data
class HeroNode {private int no;private String name;private String nickName;private HeroNode next;public HeroNode(int hNo, String hName, String hNickName) {this.no = hNo;this.name = hName;this.nickName = hNickName;}@Overridepublic String toString() {return "HeroNode{" +"no=" + no +", name='" + name + '\'' +", nickName='" + nickName + '\'' +'}';}
}
链表的面试题：
单向链表应用场景：
约瑟夫环问题：

代码：

package org.example.josephu;public class Josephu {public static void main(String[] args) {CircleSingleLinkedList list = new CircleSingleLinkedList();list.addBoy(5);list.countBoy(1, 2, 5);
//        list.showBoy();}
}class CircleSingleLinkedList {private Boy first = null;public void addBoy(int nums) {if (nums < 2) {System.out.println("nums的值不正确");return;}Boy curBoy = null;for (int i = 0; i < nums; i++) {Boy boy = new Boy(i + 1);if (i == 0) {first = boy;first.setNext(first);curBoy = first;} else {curBoy.setNext(boy);boy.setNext(first);curBoy = boy;}}}public void showBoy() {if (first == null) {System.out.println("链表为空");return;}Boy curBoy = first;do {System.out.println("编号= " + curBoy.getNo() + " -->");curBoy = curBoy.getNext();} while (curBoy != first);}/*** @param startNo  从第几个开始* @param countNum 数几下* @param nums     最初有多少个小孩*/public void countBoy(int startNo, int countNum, int nums) {if (first == null || startNo < 1 || startNo > nums) {System.out.println("参数输入有误，请重新输入");return;}Boy helper = first;while (helper.getNext() != first) {helper = helper.getNext();}for (int i = 0; i < startNo - 1; i++) {first = first.getNext();helper = helper.getNext();}while (helper != first) {for (int i = 0; i < countNum - 1; i++) {first = first.getNext();helper = helper.getNext();}System.out.println("小孩 " + first.getNo() + " 出圈");first = first.getNext();helper.setNext(first);
//            nums--;}System.out.println("最后留在圈中的小孩编号 " + first.getNo());}
}class Boy {private int no;private Boy next;public Boy(int no) {this.no = no;}//#region get|setpublic int getNo() {return no;}public void setNo(int no) {this.no = no;}public Boy getNext() {return next;}public void setNext(Boy next) {this.next = next;}//#endregion
}
栈结构：

代码：

package org.example.stack;import java.sql.SQLOutput;
import java.util.Scanner;public class ArrayStackDemo {public static void main(String[] args) {ArrayStack stack = new ArrayStack(4);String key;boolean loop = true;Scanner scanner = new Scanner(System.in);while (loop) {System.out.println("show：表示显示栈");System.out.println("exit：表示退出栈");System.out.println("push：表示压栈");System.out.println("pop：表示出栈");System.out.println("请输入你的选择：");key = scanner.next();switch (key) {case "s":stack.list();break;case "e":loop = false;break;case "pu":try {System.out.println("请输入要压栈的数据");int value = scanner.nextInt();stack.push(value);} catch (Exception e) {System.out.println(e.getMessage());}break;case "po":try {System.out.println(stack.pop());} catch (Exception e) {System.out.println(e.getMessage());}break;default:System.out.println("输入有误");break;}}System.out.println("程序退出了...");}
}class ArrayStack {private int maxSize;private int[] stack;private int top = -1;public ArrayStack(int maxSize) {this.maxSize = maxSize;stack = new int[maxSize];}public boolean isFull() {return top == maxSize - 1;}public boolean isEmpty() {return top == -1;}public void push(int value) {if (isFull()) {System.out.println("栈满");return;}top++;stack[top] = value;}public int pop() {if (isEmpty()) {throw new RuntimeException("栈空，没有数据");}int res = stack[top];top--;return res;}public void list() {if (isEmpty()) {System.out.println("栈空，没有数据");return;}for (int i = top; i >= 0; i--) {System.out.printf("a[%d]=%d\n", i, stack[i]);}}
}
用栈实现一个简单的计算器：

中缀表达式：人阅读的表达式。

package org.example.stack;public class Calculator {public static void main(String[] args) {String expression = "7*2*2-5+1-5+3-4";ArrayStack2 numStack = new ArrayStack2(10);ArrayStack2 operStack = new ArrayStack2(10);int index = 0;int num1 = 0;int num2 = 0;int oper = 0;int res = 0;char ch = ' ';while (true) {ch = expression.substring(index, index + 1).charAt(0);if (operStack.isOper(ch)) {if (!operStack.isEmpty()) {if (operStack.priority(ch) <= operStack.priority(operStack.peek())) {num1 = numStack.pop();num2 = numStack.pop();oper = operStack.pop();res = numStack.cal(num1, num2, (char) oper);numStack.push(res);operStack.push(ch);} else {operStack.push(ch);}} else {operStack.push(ch);}} else {// numStack.push(ch - '0');int keepNum = ch - '0';while (index < expression.length() - 1) {index++;ch = expression.substring(index, index + 1).charAt(0);if (!operStack.isOper(ch)) {keepNum = keepNum * 10 + (ch - '0');} else {index--;break;}}numStack.push(keepNum);}index++;if (index == expression.length()) {break;}}while (true) {if (operStack.isEmpty()) {break;}num1 = numStack.pop();num2 = numStack.pop();oper = operStack.pop();res = numStack.cal(num1, num2, (char) oper);numStack.push(res);}System.out.printf("表达式 %s = %d\n", expression, numStack.pop());}
}class ArrayStack2 {private int maxSize;private int[] stack;private int top = -1;public ArrayStack2(int maxSize) {this.maxSize = maxSize;stack = new int[maxSize];}public boolean isFull() {return top == maxSize - 1;}public boolean isEmpty() {return top == -1;}public void push(int value) {if (isFull()) {System.out.println("栈满");return;}top++;stack[top] = value;}public int pop() {if (isEmpty()) {throw new RuntimeException("栈空，没有数据");}int res = stack[top];top--;return res;}public void list() {if (isEmpty()) {System.out.println("栈空，没有数据");return;}for (int i = top; i >= 0; i--) {System.out.printf("a[%d]=%d\n", i, stack[i]);}}public int priority(int oper) {if (oper == '*' || oper == '/') {return 1;} else if (oper == '+' || oper == '-') {return 0;}return -1;}public boolean isOper(char val) {return val == '+' || val == '-' || val == '*' || val == '/';}public int cal(int num1, int num2, char oper) {int res = 0;switch (oper) {case '+':res = num1 + num2;break;case '-':res = num2 - num1;break;case '*':res = num1 * num2;break;case '/':res = num2 / num1;break;default:break;}return res;}public int peek() {return stack[top];}
}
非线性结构：

常见的非线性结构有：二维数组、多维数组、广义表、树结构、图结构

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.xdnf.cn/news/149273.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

jira 浏览器插件在问题列表页快速编辑问题标题

jira 浏览器插件在问题列表页快速编辑问题标题

jira-issueTable-quicker 这是一个可以帮助我们在问题表格页快速编辑问题的浏览器插件 github 地址 功能介绍 jira 不可否认是一个可以帮助有效提高工作效率的工具&#xff0c;但是我们在使用 jira 时使用问题表格可以让我们看到跟多的内容而不用关注细节&#xff0c;但是目…
阅读更多...
Rabbitmq安装-docker版

Rabbitmq安装-docker版

1.简介 2.安装消息队列 下载地址https://www.rabbitmq.com/download.html 使用docker方式安装 需要先下载docker&#xff0c;参考文章https://blog.csdn.net/weixin_43917045/article/details/104747341?csdn_share_tail%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22arti…
阅读更多...
微服务技术栈-初识Docker

微服务技术栈-初识Docker

文章目录 前言一、Docker概念二、安装Docker三、Docker服务命令四、Docker镜像和容器Docker镜像相关命令Docker容器相关命令 总结 前言 docker技术风靡全球&#xff0c;它的功能就是将linux容器中的应用代码打包,可以轻松的在服务器之间进行迁移。docker运行程序的过程就是去仓…
阅读更多...
MySQL：温备份和恢复-mysqldump （4）

MySQL：温备份和恢复-mysqldump （4）

介绍 温备&#xff1a;同样是在数据库运行的时候进行备份的&#xff0c;但对当前数据库的操作会产生影响。&#xff08;只可以读操作&#xff0c;不可以写操作&#xff09; 温备份的优点&#xff1a; 1.可在表空间或数据文件级备份&#xff0c;备份时间短。 2.备份时数据库依然…
阅读更多...
软件设计师_数据结构与算法_学习笔记

软件设计师_数据结构与算法_学习笔记

文章目录 6.1 数组与矩阵6.1.1 数组6.1.2 稀疏矩阵 6.2 线性表6.2.1 数据结构的定义6.2.2 顺序表与链表6.2.2.1 定义6.2.2.2 链表的操作 6.2.3 顺序存储和链式存储的对比6.2.4 队列、循环队列、栈6.2.4.2 循环队列队空与队满条件6.2.4.3 出入后不可能出现的序列练习 6.2.5 串 6…
阅读更多...
【算法|动态规划No.12】leetcode152. 乘积最大子数组

【算法|动态规划No.12】leetcode152. 乘积最大子数组

个人主页&#xff1a;兜里有颗棉花糖 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 &#x1f354;本专栏旨在提高自己算法能力的同时&#xff0c;记录一下自己的学习过程&#xff0c;希望…
阅读更多...
微信管理系统

微信管理系统

在这个全民微信的时代&#xff0c;微信已成为生活和工作中不可缺少的工具&#xff0c;为了方便&#xff0c;大部分人都不会只有一个微信&#xff0c;很多企业老板和创业者都已经开始用微信管理系统来提升自身的业务效率和客户满意度。 微信管理系统适用哪些行业呢&#xff1f; …
阅读更多...
QScrollArea样式

QScrollArea样式

简介 QScrollBar垂直滚动条分为sub-line、add-line、add-page、sub-page、up-arrow、down-arrow和handle几个部分。 QScrollBar水平滚动条分为sub-line、add-line、add-page、sub-page、left-arrow、right-arrow和handle几个部分。 部件如下图所示&#xff1a; 样式详…
阅读更多...
Python生成器

Python生成器

生成器 Generators 要理解生成器&#xff0c;首先要理解迭代器&#xff0c;迭代器由以下三个部分组成&#xff1a; 可迭代对象&#xff08;iterable&#xff09;迭代器&#xff08;iterator&#xff09;迭代&#xff08;iteration&#xff09; 1. 可迭代对象 只要定义了可以…
阅读更多...
【itext7】使用itext7将多个PDF文件、图片合并成一个PDF文件，图片旋转、图片缩放

【itext7】使用itext7将多个PDF文件、图片合并成一个PDF文件，图片旋转、图片缩放

这篇文章&#xff0c;主要介绍使用itext7将多个PDF文件、图片合并成一个PDF文件&#xff0c;图片旋转、图片缩放。 目录 一、itext7合并PDF 1.1、引入依赖 1.2、合并PDF介绍 1.3、采用字节数组方式读取PDF文件 1.4、合并多个PDF文件 1.5、合并图片到PDF文件 1.6、旋转图…
阅读更多...
1797_GNU pdf阅读器evince

1797_GNU pdf阅读器evince

全部学习汇总&#xff1a; GreyZhang/g_GNU: After some years I found that I do need some free air, so dive into GNU again! (github.com) 近段时间经历了很多事情&#xff0c;终于想找一点技术上的自由气氛。或许&#xff0c;没有什么比GNU的一些软件探索更适合填充这样的…
阅读更多...
Leetcode---114双周赛

Leetcode---114双周赛

题目列表 2869. 收集元素的最少操作次数 2870. 使数组为空的最少操作次数 2871. 将数组分割成最多数目的子数组 2872. 可以被 K 整除连通块的最大数目 一、收集元素的最小操作次数 直接模拟&#xff0c;倒序遍历即可&#xff0c;代码如下 class Solution { public:int mi…
阅读更多...
博客之站项目测试报告

博客之站项目测试报告

项目背景项目功能测试计划Bug总结升级自动化测试正常登录流程 项目背景 1&#xff1a;博客之站系统是采用前后端分离的方式来实现&#xff1b;使用MySQL、Redis数据库储存相关数据&#xff1b;同时部署到云服务器上。 2&#xff1a;包含注册页、登录页、博客列表页、个人列表页…
阅读更多...
CCF CSP认证 历年题目自练 Day22

CCF CSP认证 历年题目自练 Day22

CCF CSP认证 历年题目自练 Day22 题目一 试题编号&#xff1a; 201912-1 试题名称&#xff1a; 报数 时间限制&#xff1a; 1.0s 内存限制&#xff1a; 512.0MB 题目分析&#xff08;个人理解&#xff09; 每一个人都要报多少个数字&#xff0c;我选择字典存储&#xff0…
阅读更多...
堆--数组中第K大元素

堆--数组中第K大元素

如果对于堆不是太认识&#xff0c;请点击&#xff1a;堆的初步认识-CSDN博客 解题思路&#xff1a; /*** <h3>求数组中第 K 大的元素</h3>* <p>* 解体思路* <ol>* 1.向小顶堆放入前k个元素* 2.剩余元素* 若 < 堆顶元素, 则略过* …
阅读更多...
【GO 编程语言】面向对象

【GO 编程语言】面向对象

指针与结构体 文章目录 指针与结构体一、OOP 思想二、继承三、方法四、接口实现五、多态六、空接口七、接口继承八、接口断言九、Type别名 一、OOP 思想 Go语言不是面向对象的语言&#xff0c;这里只是通过一些方法来模拟面向对象&#xff0c;从而更好的来理解面向对象思想 面…
阅读更多...
Win11 安装 Vim

Win11 安装 Vim

安装包&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1Ru7HhTSotz9mteHug-Yhpw?pwd6666 提取码&#xff1a;6666 双击安装包&#xff0c;一直下一步。 配置环境变量&#xff1a; 先配置系统变量中的path&#xff1a; 接着配置用户变量&#xff1a; 在 cmd 中输入…
阅读更多...
小谈设计模式（19）—备忘录模式

小谈设计模式（19）—备忘录模式

小谈设计模式&#xff08;19&#xff09;—备忘录模式 专栏介绍专栏地址专栏介绍 备忘录模式主要角色发起人&#xff08;Originator&#xff09;备忘录&#xff08;Memento&#xff09;管理者&#xff08;Caretaker&#xff09; 应用场景结构实现步骤Java程序实现首先&#xff…
阅读更多...
基于Vue+ELement实现增删改查案例与表单验证（附源码）

基于Vue+ELement实现增删改查案例与表单验证（附源码）

&#x1f389;&#x1f389;欢迎来到我的CSDN主页&#xff01;&#x1f389;&#x1f389; &#x1f3c5;我是Java方文山&#xff0c;一个在CSDN分享笔记的博主。&#x1f4da;&#x1f4da; &#x1f31f;推荐给大家我的专栏《ELement》。&#x1f3af;&#x1f3af; &#x1…
阅读更多...
打开MySQL数据库

打开MySQL数据库

在命令行里输入mysql --version就可以查看&#xff1a; mysql -uroot -p之前设置的密码&#xff08;不用输入&#xff09;就可登录成功&#xff1a;
阅读更多...
最新文章

Copyright @ 2022~2023