前言

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

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

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

线性表

介绍

最基本+最简单+最常用 de 一个数据结构，一个线性表是

n

个具有相同特性的数据结构的有序序列。

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

数据元素之间具有“一对一”逻辑关系，就是第一个元素没有前驱元素+第

n

个元素没有后继元素+中间所有元素仅有一个前驱&&后继。

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

顺序表

讲解

其实就是数组

数组特征：

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

数组长度：

获取已初始化数组占用空间内存长度使用 sizeof(数组名称)。
获取已初始化数组长度，使用 sizeof(数组名称)/(int)，这里/(int)的作用是除以每个字符占总内存的个数。
初始化后再添加元素只会返回初始化时的长度。

数组风险：

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

插入代码：

CPP

12345678910int 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 是能够存放任意类型的动态数组，和数组差不多。

向量使用

讲解链接

注意

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

定义

CPP

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

添加

CPP

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

赋值

CPP

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

长度

CPP

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

输出

CPP

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

查找

CPP

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

删除

CPP

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

迭代器

相当于遍历数组的指针（for循环中的i），iterator是指针操作封装的类

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

起始

CPP

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

结束

CPP

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

自定义迭代器

定义

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

CPP

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

待续......

链表

讲解

链表的特点：

链式存储
松散

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

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

值域（存储空间）
指针（指向下个）

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

单向链表创建

首先，我们需要定义一个结构体:

CPP

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

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

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

CPP

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

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

CPP

12  head=new Node;
 tail=head;

最后，当你想输入时:

CPP

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

单向链表的遍历：

单向链表的遍历

我们肯定是从头到尾（从尾到头得双向链表）遍历

首先，让

CPP

p=head；

然后，用while循环遍历

CPP

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

是不是很简单？

单向链表的查找：

单向链表的查找

首先，我们需要写出一个遍历的模板：

CPP

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

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

CPP

123456789101112131415int 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
}

单向链表插入：

单向链表插入

很简单，就把上一个的next改为新的，再把新的next改为下一个假设你要插入的地方为p1;

CPP

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

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

关于数据结构

文章操作

前言

线性表

介绍

顺序表