关于数据结构

chicken_egg_zhao · 2025-11-20 21:34:44 · 个人记录

前言

这是我第一次写学习笔记，不会用 markdown，供 chicken egg zhao 学习\ 如有错误请截图私信我谢谢

（部分摘自 ws's 学习笔记，在此感谢 ws）

你需要知道数组、结构体、指针、STL 容器

线性表

介绍

最基本 + 最简单 + 最常用 de 一个数据结构，一个线性表是 n 个具有相同特性的数据结构的有序序列。

分为：前驱元素（在前）&& 后继元素（在后）。

数据元素之间具有“一对一”逻辑关系，就是第一个元素没有前驱元素 + 第 n 个元素没有后继元素 + 中间所有元素仅有一个前驱 && 后继。

线性表 de 分类：数据存储方式分为顺序存储 && 链式存储，也就是我们熟知的顺序表 && 链表。

顺序表

讲解

其实就是数组

数组特征：

长度确定 && 连续 && 元素内存地址连续。

数组长度：

• 获取已初始化数组占用空间内存长度使用 sizeof(数组名称)。

• 获取已初始化数组长度，使用 sizeof(数组名称)/(int)，这里 /(int) 的作用是除以每个字符占总内存的个数。

• 初始化后再添加元素只会返回初始化时的长度。

数组风险：

• 数组未初始化导致随机数（WA），特别地，数组开太大 memset(数组名称) 容易炸。
• 数组开太大内存会爆炸（MLE）。
• 数组开太小访问越界（RE）。
• 数组数据不能直接插入，插入只能从后往前移出一位（TLE）

插入代码：

int index,x;//插入的位置&&插入的数值
cin>>index>>x;//cin输入
for(int i=n/*长度*/;i>=index;i--){
    //不使用sizeof原因前面说过
    //从后往前，每一位都往后移一位
    a[i+1]=a[i];//往后移
}
a[index]=x;//将移出的空位补上
n++;//长度++
//还有，小心越界和TLE

动态数组 vector

真神！！！！

vector 是能够存放任意类型的动态数组，和数组差不多。

::::info[向量使用] 讲解链接

注意

stl 的内置函数的位置的一般是指针 / 迭代器类型！！！

• 定义

//如果已知初始长度，可以这么写
vector<数据类型>数组名称(初始大小);
//已知长度未知长度都可以这么写
vector<数据类型>数组名称;
//接下来我以a数组为例子
vector<int>a;

• 添加

//正常写法
//添加之后，长度也会发生改变
数组名称.push_back(添加的数据);
a.push_back(123);

• 赋值

//像数组一样，直接赋值
数组名称[下标]=添加的数据;
a[0]=114514;

• 长度

//获取长度用.size()
int length=a.size();

• 输出

//同数组
//全部输出用for循环遍历，不再提供框架
for(int i=0/*从0开始*/;i<a.size();i++){
   cout<<a[i]<<" ";//输出
}
//单个直接输出也是可以的
cout<<a[0]<<"\n";

• 查找

//查找某一个数第1次出现在序列中的位置（返回指针/迭代器，用.find()，不再提供框架
//注意指针问题
auto it=find(a.begin(),a.end(),114514)-a.begin();//auto是自动推导类型的类型
//返回的是第一次出现114514的位置（指针/迭代器）
没有返回end迭代器（最后一个+1）

• 删除

//将某个位置的数在数组内删除，用.erase()
//注意，删除之后，长度也会发生改变
数组名称.erase(删除的位置);
a.erase(it);

:::info[迭代器] 相当于遍历数组的指针（for 循环中的 i），iterator 是指针操作封装的类

vector 成员函数（自带的迭代器）

• 起始

//非常常用的函数
//指向第一个元素的位置
数组名称.begin()
a.begin()

• 结束

//注意，是指向数组最后一个元素的位置+1
数组名.end()
a.end();

自定义迭代器

• 定义

  迭代器类型有 iterator(普通)、const_iterator(常量)、reverse_iterator(反向迭代器，相当于头的前一个是尾，这里不过多介绍)

vector<数组类型>::iterator 迭代器名;
vector<int>::iterator it =a.begin();
//也可以用auto
auto 迭代器名 =数组名.xxx(迭代器)
//例如
auto it = a.begin();

待续…… ::: ::::

链表

讲解

链表的特点：

• 链式存储
• 松散

先讲单向链表 链表就是创建若干个结点，并将它们按照逻辑顺序连接起来

首先，链表的节点由两个部分组成：

1. 值域（存储空间）

2. 指针（指向下个）

   链表一般用结构体作为基础，以单向链表为例：

单向链表创建

:::info[单向链表创建] 首先，我们需要定义一个结构体：

  struct Node{
//你要存的数据的类型  我写的是auto；
    auto data;
    //后继指针
    node *next;
}

data 是存储空间，next 就是它的后继。

然后，我们需要创建三个指针：

//head永远指向头，tail永远指向尾，还有一个游走指针p
Node *head,*tail,*p;

接着，创建一个新节点，让头和尾都指向他

  head=new Node;
 tail=head;

最后，当你想输入时：

  p=new Node;
  p->data=a;
  tail->next=p;
  tail=p;
  //注意！！！
  tail->next=NULL;

:::

单向链表的遍历：

:::info[单向链表的遍历] 我们肯定是从头到尾（从尾到头得双向链表）遍历

首先，让

p=head；

然后，用 while 循环遍历

  while(条件){
    操作;
    p=p->next;
}
例如：
  while(p->next!=NULL){
  cout<<p->data;
  p=p->next;
}

是不是很简单？ :::

单向链表的查找：

:::info[单向链表的查找] 首先，我们需要写出一个遍历的模板：

   while(p->next!=NULL){
    cout<<p->data;
    p=p->next;

然后稍微改一改，写成函数：

int find(info* head,int num){
    info* p;
    //其实相当于i，不过是指针
    p=head->next;//指向头指针
    //因为习惯头指针不放东西，所以从头指针往后开始遍历
    //相当于从a[1]开始遍历
    int index=1;//记录位置，从1开始
    while(p!=NULL){//只要不是最后一个就循环
        if(p->data==num)//找到了
            return p;//返回位置
        p=p->next;//指向下一个结点
        index++;//位置++
    }
    return -1;//没找到时返回-1
}

:::

单向链表插入：

:::info[单向链表插入] 很简单，就把上一个的 next 改为新的，再把新的 next 改为下一个 假设你要插入的地方为 p1;

  p=new Node;
  cin>>p;
  p->next=p1->next;
  p1->next=p;
  //注意别搞反了！！！

:::

骚年，模板给出来了，其他的靠你了！

未完待续