chjshen 的博客
数据结构-入门简介
chjshen 教练 LV 5 SU @ 2023-5-31 21:32:25

题目

CCFPB03D01窗口重叠
CCFPB03D02成绩统计
CCFPB03D03离散化基础
CCFPB03D04模拟链表
CCFPB03D05生日相同
CCFPB03D06时间运算
CCFPB03D07集合运算
CCFPB03D08注册账号
CCFPB03D09取数

1. 数据结构

数据结构指计算机存储、组织数据的方式，是相互之间存在一种或多种特定关系的数据元素的集合。简单来讲数据结构是以某种特殊的方式存储数据的容器。这种“存储方式”决定了一个数据结构对于某些操作是高效的，而对于其他操作则是低效的。我们需要了解各种数据结构的优劣和原理，才能在处理实际问题时选取最合适的数据结构。

数据结构的主要研究内容包含三点：逻辑结构、物理结构、操作。

一般说到的数据结构即为逻辑结构。

2. 常见逻辑结构

根据数据元素间关系，逻辑结构基本可分为以下四类：

集合结构：结构的数据元素间的关系是“属于同一个集合”。
线性结构：结构的数据元素之间存在着一对一的关系。
树形结构：结构的数据元素之间存在着一对多的关系。
图形结构：结构的数据元素之间存在着多对多的关系，也称网状结构。

3. 常见物理结构

物理结构即数据在计算机中的存储方式，分以下四类：

顺序存储：最基本的存储结构，用一组地址连续的存储单元依次存储线性数据结构的各个数据元素，如数组。特点：可随机存取；插入和删除要移动元素。
链式存储：在计算机中用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的,也可以是不连续的）。它不要求逻辑上相邻的元素在物理位置上也相邻，结点间的逻辑关系是由附加的指针字段表示的。如链表。特点：每个结点由数据域和指针域构成；逻辑相邻不一定物理相邻；插入删除方便；查找结点要慢于顺序存储；存储密度小。
索引存储：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。索引表由若干索引项组成，如果每个节点在索引表中都有一个索引项，则该索引表就被称为稠密索引。若一组节点在索引表中只对应于一个索引项，则该索引表就成为稀疏索引。索引项的一般形式一般是关键字、地址。常见于数据库中。特点：检索速度快；索引表占用额外空间。
散列存储：又称哈希（hash）存储，将要存储元素的关键值与存储的物理位置建立联系，直接根据关键值算出要存入的地址。如哈希表（散列表）。特点：访问速度快。

4. STL标准库

STL，英文全称 standard template library，中文可译为标准模板库，其包含有大量的模板类和模板函数，是 C++ 提供的一个基础模板的集合，1998年，STL被定为国际标准，正式成为C++程序库的重要组成部分，因此它可以直接在C++里拿来使用，无需安装。

例如－使用STL的vector容器：

#include <vector>

STL被组织为下面的13个头文件：<algorithm>、<deque>、<functional>、<iterator>、<array>、<vector>、<list>、<forward_list>、<map>、<unordered_map>、<memory>、<numeric>、<queue>、<set>、<unordered_set>、<stack>、<utility>。

可分为容器(containers)、迭代器(iterators)、空间配置器(allocator)、配接器(adapters)、算法(algorithms)、仿函数(functors)六个部分，核心是三个部分：

容器(containers)：管理某类对象用，如队列queue、栈stack、向量vector、集合set、映射map等
算法(algorithm)：作用于容器上的算法，如排序(sort)、搜索(upper_bound、...)、交换(swap)等
迭代器(iterators)：用于遍历容器的元素

向量

线性表是指由n个具有相同特性的数据元素组成的的有限序列，是最基本、最简单、也是最常用的一种数据结构，栈、队列、链表等数据结构逻辑上都属于线性表。一般来讲，表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。

1. 特性：

线性表中的数据元素的个数n定义为线性表的长度，n=0时称为空表。
非空表中必定存在一个“第一元素”和一个“最后元素”。
非空表中的元素，除了最后一个元素之外，均有唯一的后继（后件）。
非空表中的元素，除了第一个元素之外，均有唯一的前驱（前件）。

2. 逻辑结构：

3. 物理结构：

线性表可由顺序存储或链式存储表示，实际应用中常以栈、队列、字符串等特殊形式使用。

4. STL中vector的使用：

#include<vector>  //  引入头文件

  vector<int> v;  //  定义向量v，内部存储类型为int
  
  v.push_back(node);  //  向量尾部添加成员node
  
  cout << v[0];  //  下标访问，下标从0开始
  
  v.size();  //  向量大小
  
  v.begin();  //  获取向量起始位置的指针，用于插入、删除、迭代中
  v.end();  //  获取向量结束位置下一个位置的指针，用于插入、删除、迭代中

  v.insert(指针, 元素);  //  在指针所指位置之前插入元素，后方元素后移
  v.erase(指针);	  //  删除指针所指位置的元素，后方元素前移
  
  vector<int>::iterator i;  //  定义迭代器（指针），用于循环遍历向量
  for(i = v.begin(); i != v.end(); i++)  //  遍历向量
    cout << *i << ' ';
  
  v.clear();	//	清空

结构体

结构体类型属于组合变量类型，它允许编程者自行组合基础变量类型，创造新的变量类型以用于解决问题。

1. 要使用结构体类型变量，需要先设计组合结构（写在全局作用域中）：

struct name {  // struct 声明结构体变量类型，变量类型名称name自行指定
  // 花括号内部声明成员变量类型以及名称
  int a;
  float b;
  double c;
  char d;
  ...
};

2. 定义结构体类型变量

struct node {
  ...
};
node n;  // 定义结构体node类型的变量 n

3. 使用

struct node{
  int a;
  char b;
};
node n;
n.a = 1;  // 变量名 + 小数点 + 成员名，即可存取结构体类型变量
n.b = 'c';

4. 初始化

struct node{
  int a;
  char b;
};

// 普通初始化
node a = {
  a: 1,
  b: 'c',
};

// 快速初始化
node a = {1, 'c'};

5. 高级

5.1结构体类型数据结构

结构体中可以使用结构体类型的数据结构。

5.2成员函数

结构体内部除了可以声明普通的变量外，也可以定义内部的成员函数。

在面向对象编程思想中，成员变量称为属性，成员函数称为方法，将一切事物抽象为属性和方法的集合，。

结构体的成员函数和普通函数一样，可以操作内部的成员变量和全局变量。定义时写在结构体内部，和普通函数一样，使用时通过小数点.操作符使用。

struct node{
    string name;
    void sayHello(){
      cout << "my name is" << name;
    }
};

node a = {"tom"};
a.sayHello();

5.3运算符重载

函数的重载指同名函数因参数不同而能共存并表现出不同的功能。

同样的，运算符重载也是因为参与运算的值的类型不同而表现出不同的功能。

当我们定义了自己的结构体类型变量后，计算机并不知道如何执行该类型变量的算术运算、关系运算。

因此，需要我们自行定义运算方法，即运算符重载。

写法一：写在结构体内部

struct Stu{
  string name;
  int score;
  
  //	写法一
  //	返回值 关键字 运算符 参与运算的第二个值
  bool operator < (Stu t){
    return score < t.score;
  }
  //	const 防止原变量被修改    & 引用类型可加快传递速度
  bool operator >= (const Stu& t) const{
    return score >= t.score;
  }
};

写法二：写在结构体外部

struct Stu{
  string name;
  int score;
};
//	写法二
//	返回值 关键字 运算符 参与运算的两个值
bool operator > (Stu a, Stu b)
{
  return a.score > b.score;
}
//	const 防止原变量被修改    & 引用类型可加快传递速度
bool operator <= (const Stu& a, const Stu& b)
{
  return a.score <= b.score;
}

数据结构-入门简介