(此文为王道数据结构学习笔记，只供个人后续复习使用，若有错误，还望指出我改正，谢谢）
回顾上次学习内容：
数据结构的定义、类型、三要素
算法的定义、特性、以及效率评定指标：时间复杂度、空间复杂度。
时间复杂度主要看循环嵌套，空间复杂度看引入的数据结构和自我调用。
线性表的基本操作：创毁增删查改，静态分配，动态分配。
三道统考真题。
单链表：
每个结点：数据元素+指向下一个节点的指针
顺序表：
优点：随机存取，存储密度高
缺点：要求大片连续空间，不好改变容量
单链表：
优点：不要求大片连续空间，改变容量方便
缺点：不可随机存取，存指针耗费空间。
定义一个单链表：（简单定义）
struct LNode{ //定义单链表结点结构
ElemType data; //单个节点存放的数据
struct LNode *next;//指向下一个节点的指针
};更好的定义：（这样定义方便后面定义结构体和指针）
//定义单链表中单个结点的结构体
typedef struct LNode{ //将struct LNode替换（接后文）
ElemType data; //定义结点中的数据域
struct LNode *next;//定义结点中的指针域（用于指向下一个结点）
//该指针类型为struct LNode结构体类型，
//指向的内容也是struct LNode结构体类型
}LNode, *LinkList //（接前文）为LNode，结构体指针定义为了LinkList（等价于LNode *）struct 初始化一个带头结点的单链表（无后续结点）：
头结点：不存放数据（data=NULL），头指针指向头结点，头结点的next指向下一个结点，若无下一个结点，即为NULL。
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList //定义结点结构体
//创立带头结点的空单链表
bool InitList(LinkList &L){ //定义为bool型方便使用者知道是否初始化成功
L = (LNode *)malloc(sizeof(LNode));//创建头结点
if (L==NULL) //内存不足，L未被分配到空间，返回失败
return false;
L->next = NULL; //头结点之后还没有结点，创建带头结点的空单链表成功
return true;
}
void test(){
LinkList L; //声明了一个指向单链表的指针（即头指针），指向想要生成单链表的内存空间
InitList(L);//初始化该内存空间，即创立带头结点的空单链表，返回true则成功
}
头插法建立单链表：
生成新结点，存放数据后，将之插入到表头，但是仍然在头结点后，头结点的next此时指向该新结点
//定义单链表中单个结点的结构体
typedef struct LNode{ //将struct LNode替换（接后文）
ElemType data; //定义结点中的数据域
struct LNode *next;//定义结点中的指针域（用于指向下一个结点）
//该指针类型为struct LNode结构体类型，指向的内容也是struct LNode结构体类型
}LNode, *LinkList //（接前文）为LNode，结构体指针定义为了LinkList（等价于LNode *）
//采用头插法建立单链表
LinkList List_HeadInsert(LinkList &L){ //建立逆向单链表，L为LinkList类型即为结构体指针类型
LNode *s; int x;
L=(LinkList)malloc(sizeof(LNode)); //创建头节点
L->next=NULL; //这里的L->next与L.data类似，
//但箭头用于结构体指针，点用于结构体；
scanf("%d", &x); //输入结点的值；
while(x!=9999){
s=(LNode*)malloc(sizeof(LNode));//创建一个新结点，具体操作如下：
//创建一个LNode类型的结点，并将起始地址赋值给s
s->data=x; //新节点的data赋值为x
s->next=L->next; //将头结点的next赋值给新结点的next
L->next=s; //将头节点的next赋值为s
//上述完成后实现了将新节点s插入了表中，
//并且L继续作为头指针
scanf("%d",&x);
}
return L;
}头插法建立单链表，其中读入数据的顺序与生成链表的元素顺序是相反的，即（除了头结点）单链表第一个结点存的是最后一个读取的数据。
时间复杂度为O(n)
倘如没有引入头结点会怎么样？由于在头部插入了一个结点，导致链表第一个结点的地址变成新的地址，需要将L重新赋值，比较麻烦。
尾插法建立单链表：
头插法比较简便，但生成链表数据顺序相反，如果想要顺序保持一致，可以用尾插法建立单链表。
与头插法类似，只不过是从链表尾部插入，由于链表不具备物理上的连续，故想要知道尾结点是哪个，需要引入一个尾指针r来指示。每次生成新的结点，需要将尾结点指向该节点。
LinkList List_TailInsert(LinkList &L){
int x;
L=(LinkList)malloc(sizeof(LNode));
LNode *s, *r=L; //一开始链表为空，尾指针指向头节点
scanf("%d", &x); //输入结点的值；
while(x!=9999){ //输入9999表示结束
s=(LNode*)malloc(sizeof(LNode));//建立新结点
s->data=x; //给新结点数据域赋值
r->next=s; //将尾结点的next指向新结点
r=s; //将新结点赋值给尾结点，新的尾结点诞生
scanf("%d", &x);
}
r->next=NULL; //创建完毕，将加入的尾结点置空，不再需要
return L;
}尾插法建立单链表增加了一个尾指针，故时间复杂度为n
查找结点：
按序号查找结点：
由于单链表不具备物理连续性，需要依次扫描计数来计算序号。
LNode *GetElem(LinkList L, int i){
int j=1; //定义计数变量j，初始为1
LNode *p=L->next; //定义扫描用的指针p，初始为头结点的next（即1号结点）
if(i==0) //如果要寻找的结点号为0，要找的即为头结点
return L;
if(i<1) //i无效，返回NULL
return NULL;
while(p&&j<i){ //从第1个结点开始找，查找第i个
p=p->next;
j++;
}
return p; //返回找到的结点
}时间复杂度为O(n)
按照值查找结点：
只需要从第一个结点开始，一一比对数据域的值即可。
LNode *LocateElem(LinkList L, ElemType e){
LNode *p=L->next;
while(p!=NULL&&p->data!=e) //从第一个开始找，找到值为e的结点
p=p->next;
return p; //找到则返回该结点指针，没找到返回NULL
}时间复杂度为O(n)
插入结点：
按序号后插入新结点：
由于想要在i号位置插入一个新结点，我们需要知道(i-1)号结点的位置，由于链表不具备物理连续性，我们需要从头开始向后通过next一个一个向后遍历，找到(i-1)号结点后，将新结点的next改为(i-1)号结点此时的next，并且将(i-1)号结点的next指向新结点地址，即可完成在i号位置插入新结点。
bool ListInsert(LinkList &L, int i, ElemType e){ //想要插入的链表，位置，数据
if(i<1)
return false; //除了头结点外，结点编号从1开始，不可插入在头结点前
LNode *p; //定义指针p用来扫描链表
int j=0; //定义变量j代表指针扫描到的结点号
p = L; //使指针p从头结点开始
while (p!=NULL && j<i-1){ //扫描找到i-1号结点
p=p->next;
j++;
}
if(p==NULL) //i不合法
return false;
LNode *s = (LNode *)malloc(sizeof(LNode)); //创建一个新结点
s->data = e; //将其数据域赋值为e
s->next=p->next; //将其next赋值为i-1号结点的next
p->next=s; //将i-1号的next赋值为新结点位置
return true;
}
由于需要依次扫描，时间复杂度为O(n)
明明这两天控制情绪控制的很好。
我不知道为什么我还是忍不住的在教室里面嚎啕大哭，我真的好想你，好想你，好想听你对我说一句加油宇宇。
真的很抱歉，我还是很想你。真的好想见见你。
在楼梯过道大哭了一个小时。
真的对不起。
我浪费了一个小时陷入在这种负面情绪之中。
真的好想你。
