链表与邻接表

【一般实现方式：指针+结构体——动态链表（工程中常用）】

1
2
3
4
5
6
7

struct Node
{
	int val;
    Node *next;
}

new Node(); // 非常慢，若要使用可以初始化n个节点

这里介绍用数组模拟【静态链表】该数据结构的方式——速度快！

单链表

单链表中用的最多的是邻接表——n个单链表：将每个点（共有n个点）的所有邻边存下来

邻接表应用：存储图和树（e.g. 最短路问题、最小生成树问题、……）

单链表基本结构：从头指针开始依次指向若干个节点，每个节点存储一个数值val和一个next指针，沿着next指针不断访问后续数据，直到指向空指针

数组模拟链表存储需要定义（均为整数型数组）：

• e[N]：存储各点数值val
• ne[N]：存储各点next指针——空节点下标用-1表示

二者通过下标关联 ：

事实上，同一下标i对应的e[i]与ne[i]表示一个节点的数值val及其next指针，将其看作一个结构体会更好理解，但在代码实现过程中，为使得代码尽量简洁，选择直接对数组下标进行操作

1
2
3
4
5
6
7
8
9
10
11
12

// 结构体写法
struct Node
{
    int e, ne;
}nodes[N];

// 以删除为例：删除下标是k的节点“后面”的一个节点
void remove(int k)
{
    // 直接让k节点指向的节点变成其后的节点指向的节点
    nodes[k].ne = nodes[nodes[k].ne].ne;   
}

需要注意：一个下标代表一个节点，各节点之间的指向关系仅由next指针（即ne[i]的值）决定

单链表的性质：顺序（单向）访问——可以在O(1)的时间复杂度内找到指定节点的后一个节点（包括完成插入等操作），但如果要找到指定节点之前的节点，则只能从头指针head开始遍历

例题：826. 单链表 - AcWing题库

实现一个单链表，链表初始为空，支持三种操作：

1. 向链表头插入一个数；
2. 删除第 k 个插入的数后面的一个数；
3. 在第 k 个插入的数后插入一个数。

现在要对该链表进行 M 次操作，进行完所有操作后，从头到尾输出整个链表。

注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。

输入格式

第一行包含整数 M，表示操作次数。

接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：

排序

快速排序

主要思想：分治

时间复杂度：O(n*log{2}{n})【平均时间复杂度，最快可以达到n^2】

e.g. 对数组q的序号l至r区域进行排序

1. 确定分界点x（数值）：常用——左边界q[l]、**中心点处值q[(l+r)/2]**、右边界q[r]、随机
2. 调整区间：使所有小于（等于）x的值均位于x左侧，所有大于（等于）x的值都位于x右侧（区间内不要求有序）
   • 暴力做法（时间复杂度仍为O(n)，但会额外耗费空间）：
     1. 新开两个数组a[]，b[]
     2. 对数组q的序号l至r区间进行扫描：
        • 若q[i]≤x，将q[i]放入a[]
        • 若q[i]≥x，将q[i]放入b[]
     3. 将a[]、b[]依次放回q[]中
   • 推荐做法（使用指针）：
     1. 从左边界q[l]处开始，使用指针i向右侧移动，若指针指向的数值大于等于x，停下
     2. 从右边界q[r]处开始，使用指针j向左侧移动，若指针指向的数值小于等于x，停下
     3. 交换指针i、j处的数值
     4. 重复1、2、3步骤（在移动后的指针i、j位置基础上继续向右/左侧移动），直到两个指针相遇
3. 递归处理左右两段

例题：785. 快速排序 - AcWing题库

给定一个长度为 n 的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在 1∼10^9范围内），表示整个数列。

输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

数据范围

1≤n≤100000

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

#include <iostream>

using namespace std;

const int N = 100010; // 保险，防止边界问题

int n;
int q[N];

void quick_sort(int q[], int l, int r)
{
    //判定边界：区间内只有一个数或没有数时不需要排序
    if (l >= r)
        return;
    
    int x = q[(l + r) / 2], i = l - 1, j = r + 1; //取分界值
    //注意：由于每次完成交换（包括初始状态）都自动向中间移动一格，初始时要将两侧指针取在区间外侧1个单位
    while (i < j) //迭代：移动+交换
    {
        do
            i ++ ;
        while (q[i] < x);
        do
            j -- ;
        while (q[j] > x);
        if (i < j)
        {
            //交换两数:swap(q[i], q[j]);
            int t = q[i];
            q[i] = q[j];
            q[j] = t;
        }
    }
    
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
        scanf("%d", &q[i]);
    
    quick_sort(q, 0, n-1);
    
    for (int i = 0; i < n; i ++ )
        printf("%d ", q[i]);
    
    return 0;
}

归并排序

主要思想：分治

时间复杂度：O(n*log{2}{n})

• 时间复杂度计算：每次递归将当前序列分为2份（原序列->2份->4份->8份->……），直到每一份的长度为1时停止；显然这样的递归需要进行log{2}{n}轮，而对于每一轮而言又需要进行时间复杂度为O(n)的归并，因此整体排序算法的时间复杂度为两者相乘，即O(n*log{2}{n})

e.g. 对数组q的序号l至r区域进行排序

1. 确定分界点：以数组中心点mid = (l+r)/2为分界点，将数组q分成Left、Right两部分
2. 对两部分进行递归排序，使其各自成为有序序列
3. 归并：将两个有序数组合并成一个有序数组
   • 双指针算法（时间复杂度为O(n)）：
     1. 对于两个有序数组Left、Right而言，分别在其左端点处放置一个指针
     2. 比较两个数组指针处数值的大小，将更小的那一个放入输出的目标数组（初始为空）
        • 注意：若两个数组指针处数值大小相等，则优先将数组Left中的数值放入输出目标数组，则可保证排序算法的稳定
        • 排序算法的稳定：排序完成后，原数组中值相同的数之间的相对位置不变（归并排序稳定，快速排序不稳定；若想使快速排序稳定，需要在对数值排序的基础上对各元素在原数组中的位置序号进行排序）
     3. 对于更小的数值所在的数组而言，将指针向后移一位，重复步骤2（依次排入输出目标数组中）
     4. 重复步骤3，直到某个数组中所有的数全部被放入输出目标数组，则跳出循环，将另一个数组的所有剩余数值依次排入输出目标数组中，归并完成

tips:请在使用该系统前安装好相应的库文件（详见附录二），并在不同控制台分别运行roscore（ros操作系统内核）、rosbag play –loop –pause all.bag（ros数据包展示）和rosrun gmapping slam_gmapping（任务四建图处理进程）

该系统程序名为final_system，使用以下命令克隆git仓库：

1

git clone https://github.com/Asgard-Tim/ROS-Coding.git

安装好相关库文件后可通过以下命令运行系统程序：

1
2
3
4
5
6
7
8
9
10
11
12
13

//项目构建

cd /home/ubuntu/project/catkin_ws

catkin_make

//程序运行

source /home/ubuntu/project/catkin_ws/devel/setup.bash

cd /home/ubuntu/project/catkin_ws

rosrun final_system final_system

完整代码已上传至Github平台，URL地址：Asgard-Tim/ROS-Coding: 重庆大学明月科创实验班软件设计课程作业 (github.com)

Bilibili同步上传系统演示视频Demo，链接：重庆大学明月科创实验班软件设计作业–ROS数据展示系统_哔哩哔哩_bilibili

程序主要结构与算法分析

在**main()**函数中：

• 创建ROS节点和节点句柄。

• 调用**initialize()**函数显示初始菜单:提示用户选择登录、注册或退出系统。

• 定义一个user类，用于保存用户的用户名和密码信息;根据用户选择执行不同的操作：

• • 登录：要求用户输入用户名和密码，然后检查是否匹配存储在文件中的用户信息。
  • 注册：要求用户输入新的用户名和密码，然后将用户信息保存到文件中。
  • 退出系统：结束程序运行。

• 如果登录成功，调用**systeminitialize()**函数显示登录成功后的菜单:提示用户选择不同的数据可视化选项或退出系统。

• 根据用户选择执行不同的数据可视化操作：

任务一：用命令行窗口显示小车的IMU和里程计（odometry）数据

• • IMU数据：订阅IMU数据的ROS话题，将数据传递给回调函数callback1进行处理。

  • 回调函数callback1，处理IMU数据：

  • • 从接收到的IMU消息中获取线性加速度和角速度信息。
    • 使用std::cout打印出线性加速度和角速度信息。

  • 里程计数据：订阅里程计数据的ROS话题，将数据传递给回调函数callback2进行处理。

  • 回调函数callback2，处理里程计数据：

  • • 从接收到的里程计消息中获取位置和姿态信息。
    • 使用std::cout打印出位置和姿态信息。

任务二：用图形界面显示颜色相机和深度相机的数据（利用OpenCV库）

• • 颜色相机数据：订阅颜色相机数据的ROS话题，将数据传递给回调函数callback3进行处理。

  • 回调函数callback3，处理颜色相机数据：

  • • 将接收到的彩色图像消息转换为OpenCV的图像格式。
    • 使用OpenCV的窗口显示彩色图像。

  • 深度相机数据：订阅深度相机数据的ROS话题，将数据传递给回调函数callback4进行处理。

  • 回调函数callback4，处理深度相机数据：

  • • 将接收到的深度图像消息转换为OpenCV的图像格式。
    • 使用OpenCV的窗口显示深度图像。

任务三：用图形界面显示激光雷达的点云数据（利用PCL库）

• • 点云数据：订阅点云数据的ROS话题，将数据传递给回调函数callback5进行处理。

  • **pcl::visualization::CloudViewer viewer(“Cloud Viewer”);**：创建一个PCL点云可视化器。

  • 回调函数callback5，处理点云数据：

  • • 将接收到的点云消息转换为PCL的点云格式。
• • • 使用PCL的可视化器显示点云。

任务四：自行选择一种高级算法（例如语义分割、三维重建、导航定位（SLAM）等），实现该算法（可以直接利用第三方库），将其集成到系统中

• • 选择Gmapping算法（一个基于2D激光雷达使用RBPF（Rao-Blackwellized Particle Filters）算法完成二维栅格地图构建的SLAM算法）
  • 占据栅格地图数据：订阅占据栅格地图数据的ROS话题，将数据传递给回调函数callback6进行处理。
  • 回调函数callback6，处理占据栅格地图数据：
  • • • 从接收到的占据栅格地图消息中获取分辨率、宽度和高度等信息。
      • 创建一个OpenCV的图像对象，用于绘制地图。
      • 遍历地图的每个栅格，根据栅格的值绘制不同的颜色圆点。
      • 使用OpenCV的窗口显示地图。

各功能部分构建过程与实现效果

1.系统界面

（1）登录界面

（2）功能选择界面

2.各部分功能

本项目全部代码已同步上传至Github,仓库链接：Asgard-Tim/Vendition: 重庆大学明月科创实验班软件设计课程作业 (github.com)

一、需求分析

1.1 进销存管理业务概述

随着近年来世界各方面的发展进步和物联网时代的到来及其不断发展，货物销售行业发生了翻天覆地的巨大变革，随着从卖方市场向买方市场的转变，我国的零售行业迅速崛起，并且时时刻刻面临着日益激烈并不断变化的竞争环境。因此，提高进销存管理水平，探索降低成本的方法成为提高企业竞争力的必然选择[1]。

伴随着企业规模的不断扩大和企业效益的进一步发展，原先的管理已经不能跟上企业的发展步伐，更无法满足企业对管理工作快速、准确的要求。在销售业务不断增长的同时，公司日常所需要处理的数据量不断增长，公司内部运转周转的中间传递环节也逐渐增多，进而发展到非常的复杂的经营管理模式，同时，现在复杂多变的市场，人工管理等传统的方法方式在相关方面已无法应对。更为重要的是商品的进销存方面缺乏实时处理的相关分析，管理人员对及时传递资料和命令的需求得无法实现。最后发现如果能够在面对不同种类的货物信息时，能够让管理人员实时掌握销售流程及销售情况，进而支持管理人员对相关商品销售的运营并且可以有效地加速的周转率，从而可以进一步提高行业的服务质量。这时可以组建一个记录、更新、保存数据信息的数据库以建立和支持一个合理高效的软件项目[2]。

具体而言，进销存管理业务的核心是对于商品流动信息的储存与管理，主要涉及到商品品类的新增与删除、进货、商品销售与盘点、平库等相互关联的诸多业务流程。因此，在进销存管理系统中，我们需要让这些业务流程在系统中有所体现，从而达到高效管理的目的。

1.2 功能性需求

1.2.1 商品信息管理

在进销存管理系统中，需要提供渠道给操作管理人员以录入或删除商品信息，同时对于日常的进货与销售过程予以记录，并在需要的时候对库存中已有的商品种类与数量进行盘点，必要时还需要进行平库操作。这些流程会涉及到公司内的诸多部门，诸如采购部、市场部、财务部等，组织架构的复杂性也对软件系统设计的联动能力与处理效率提出了较高的要求。因此，我们不仅需要通过程序设计实现与实际操作对应的相关功能，对于操作人员在系统中输入的文本信息进行读取与必要的处理以模拟上述诸多对于商品实体的实际操作流程，同时还需要建立与实际仓库所对应的商品的数据库，通过对于所有商品的编号、名称、单价、库存数量与计量单位等具体信息进行存储，并在管理人员进行操作的过程中对库中存储的商品信息进行与实际情况同步的改动，实现更加高效的管理。

1.2.2 系统安全

对于公司而言，系统的安全性是软件系统设计过程中一个至关重要的考虑因素，由于系统缺乏维护管理与必要的保护措施所造成的损失与影响将是不可估量且难以弥补的。在进销存管理系统中，系统安全的问题主要可能出现在操作权限与非法输入等方面。基于这样的考虑，软件系统在处理数据时，需要对于非法的输入进行区分并给予用户一定的操作提示；在功能上，需要通过账户密码匹配的机制以对于操作人员的权限进行一定的限制从而保证系统的安全性；在存储数据时，应对于存入的数据在写入文件的同时进行一定的加密操作，防止外部人员盗取或进行修改；同时在用户进行操作时，需要同步保留用户的操作记录，在必要时以供核查。

1.3 非功能性需求

1.3.1 性能需求

1.系统必须具备高可用性，能够保证系统长时间连续运行的需求；

​ 2.系统的响应时间应尽可能的短，系统登陆、信息保存等操作响应时间小于1.5秒，信息查询等复杂操作时间小于2秒；

​ 3.数据库容量要大，能够满足商品采购、销售、库存管理等详细信息长时间保存的需求；

​ 4.可供多个用户分时使用该系统平台。

1.3.2 易用性需求

1.系统的相关提示信息一致，如进货、销售、删除、查询等操作功能，应尽可能使人容易理解；

​ 2.有明确的输入限制提示信息；

​ 3.中英文对应正确。

1.3.3 可扩展性需求

在系统底层设计时，需要强化系统的配置和扩展能力，主要体现在以下方面：

​ 1.系统底层支持的可扩展性；