链表：

   存放：在内存中非物理连续，通过指针相连

   取数：通过开头，依次查找，直到找到目标（查改：慢）

   删除：将前一个数据直接指向后一个数据，删除当前（快）

   增加：将新数据先连接到链表上，然后前一个数据更改连接（快）

数组：

   存放：在内存中物理连续

   取数：下标直接访问（查改：快）

   删除/增加：新建数组，平移数据（慢）

int a;

int *p; 创建一个int类型的指针p

a=5;

p=&a;

cout<<p;//a的地址

cout<<*p;//a的地址对应的数据

*p=6;//通过地址更改对应的数据

指针创建时，就在普通变量名前加*,指针指向的数据必须与指针的类型一致

double b;

double *p=&b;

如果涉及到数据频繁的插入和删除，那么链表结构更合适，不容易超时

list

#include <iostream>

using namespace std;

struct student{

   //数据域

   string name;

   int age;

   //指针域

   student *nt;

};

int main(){

   //链表的静态创建

   student a,b,c;

   a.name="laoshi";

   a.age=18;

   b.name="laotian";

   b.age=31;

   c.name="laozhang";

   c.age=55;

   a.nt=&b;

   b.nt=&c;

   c.nt=NULL;//结尾，设为空指针，也可以赋值为nullptr

   student *head=&a;

   //遍历链表（不安全）:head表示头节点/头指针，原则上不允许更改

   /*while(head!=NULL){

       cout<<head->name<<" "<<head->age;

       head=head->nt;

   }*/

   //遍历链表的正确方式

   student *p=head;

   while(p!=NULL){

       cout<<p->name;

       p=p->nt;

   }

   return 0;

}

//静态创建：编译时，直接占用空间

student a;

//动态创建：运行时，运行到当前位置，再临时创建空间，关键字 new 代表新建

student *a=new student;

//动态创建链表

string s;

int a,n;

student *head,*p,*q;

cin>>n;//输入学生的个数

//创建第一个学生的空间

p=new student;

cin>>s>>a;//输入第一个学生的信息并赋值

p->name=s;

p->age=a;

//将第一个学生连接到链表上

head=p;

//输入n-1个同学的信息

for(int i=1;i<n;i++){

   q=new student;//q负责新增，创建一个新的学生空间

   cin>>s>>a;//输入学生信息并赋值

   q->name=s;

   q->age=a;

   p->nt=q;//将新的学生连接到当前链表的末尾

   p=p->nt;//让p永远指向链表的末尾：p指向最新生成的学生

}

p->nt=NULL;//让结尾指向空，如果不做空指针处理，那么该指针为野指针（乱指，不安全）

//遍历输出

p=head;

while(p!=NULL){

   cout<<p->name<<p->age;

   p=p->nt;

}

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

一对一，指向下一个：单链表

双向链表：每个节点既知道下一个数据，也知道上一个数据

struct node{

   string name;

   int age;

   node *nt;

   node *pr;

}

循环链表：尾节点指向头节点

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

设当前链表存放的顺序:head-> 1-> 2-> 3-> 4-> 5-> NULL

删除目标：3

1、先找到3，找到3的前一个节点

node *p=head;

while(p!=NULL){

   if(p->nt->num==3) break;

   else p=p->nt;

}

2、获取3的地址

node *q=p->nt;

3、将3的前一个连接到3的后一个上

p->nt=q->nt;

4、删除3空间

delete q;//删除q这个空间

5、处理野指针

q=NULL;

插入：在4的后面插入一个新的数据99

node *x=new node;

x->num=99;

1、先找到4

node *p=head;

while(p!=NULL){

   if(p->num==4) break;

   p=p->nt;

}

2、先将新的数据连到4的后一个数据上

x->nt=p->nt;

3、将4连到新数据上

p->nt=x;

总结：

   链表与数组的区别

   指针操作

   静态创建链表

   动态创建链表

   链表的删除操作

   链表的插入操作

目前的进度：对应的题目需要陆续做完

   基础（一）全部

   基础（二）前四章

   基础（三）前两章