数组和链表的共同点，都是按照输入顺序存放的，顺序结构

动态创建链表

静态-动态

静态创建：编译的过程就把空间提前预置好了

动态创建：在运行时，临时创建空间

struct node{

   int val;

   node *nt;

};

静态创建

node a;

a.val=5;

动态创建

node *a;

a=new node;

a->val=5;

-------------

静态创建长度为100的链表，创建100个变量

动态创建链表（任意长度），只需要三个指针

node *head,*p,*q;

p=new node;

p->val=1;

head=p;

for(int i=2;i<10;i++){

   q=new node;

   q->val=i;

   p->nt=q;

   p=q;

}

p->nt=NULL;//nullptr  空指针处理，避免野指针操作数据

输入n，输入n个数字，并用链表存储

查找：输入一个数字m，输出m在链表中是第几个

int ans=-1;

p=head;

for(int i=0;p!=NULL;i++){

   if(p->val==m){

       ans=i;

       break;        

   }

   p=p->nt;

}

cout<<ans;

插入：输入一个数字j，输入一个数字k，在链表的第j个节点后面插入k

p=head;

int i=0;

while(i!=j&&p!=NULL) p=p->nt;

if(p==NULL) return ;

q=new node;

q->val=k;

q->nt=p->nt;//先将新节点连接j+1节点

p->nt=q;//再将j点连接新节点

删除：输入一个数字m，删除值为m的节点

p=head;

if(p->val==m) head=head->nt;

else{

   while(p->nt!=NULL&&p->nt->val!=m) p=p->nt;

   q=p->nt;

   p->nt=q->nt;

}

delete q;//删除q指向的内存空间，此时q变成野指针

q=NULL;//处理成空指针

#include <list> 默认是双向链表

struct node{

   int val;

   node *nt,*pr;

};

容器库：

顺序容器：输入的数据，按顺序存放

array : 数组的类模板

vector : 可变长数组 向量

deque : 双向队列

forward_list : 单向链表

list : 双向链表

关联容器：输入的数据，不按照输入顺序存放，有特定的排序规则（默认从小到大）

set 集合：自动有序，自动去重

map 映射：key-valve成对存放，自动有序（按key排序），自动去重（覆盖或跳过重复key的valve值）

容器适配器：有固定的存取顺序

stack 栈：先进后出，后进先出

queue 队列：先进先出，后进后出

priority_queue 优先队列：默认大顶堆，大的先出，小的后出

动态创建

一对多：树

当前代码指不规则树

struct node{

   char val;

   vector<node*> chi;

};

node *root;

map<char,node*> nm;//该字符对应的节点地址

int main(){

   char a,b;

   node *p,*q;

   int n=5;

   while(n--){

       cin>>a>>b;

       if(nm[a]>0) p=nm[a];

       else{

           p=new node;

           p->val=a;

           nm[a]=p;

       }

       if(nm[b]>0) q=nm[b];

       else {

           q=new node;

           q->val=b;

           nm[b]=q;

       }

       p->chi.push_back(q);

   }

}

树的根、根节点、祖先节点

子节点<->父节点 相对存在

叶子节点：没有子节点的节点

子孙节点：根节点下面的所有节点

兄弟节点：同一层/同一父节点（亲兄弟表兄弟）

层：距离根节点的层数（节点数）

树的深度：max层

度：一个节点的子节点的数量

树的度：max度

边：树中的连线的长度

树的高度：根节点到叶子节点的最远距离