(此文为王道数据结构学习笔记，只供个人后续复习使用，若有错误，还望指出我改正，谢谢）
回顾上一篇文章学习内容：
单链表的定义。
带头结点与不带头结点的区别。
初始化带头结点的单链表。
头/插插法建立单链表。
按序查找，按值查找，按序插入。
?指定结点的后插操作：
先找到指定结点，再将next区域与新结点进行交接即可。
bool InsertNextNode(LNode *p, ElemType e){
if (p==NULL)
return false; //要找的结点不存在
LNode *s = (LNode *)malloc(sizeof(LNode));
if (s==NULL) //新结点内存分配失败
return false;
s->data = e; //结点s保存数据e
s->next=p->next;
p->next=s; //将结点s连接到p之后
return true;
}时间复杂度为O(1)；?
指定结点的后插操作：
1.若有头指针，且链表元素均可一一访问，则一个一个扫描，直到扫描到指定结点p的前一个，再执行插入操作即可。时间复杂度为O(n);
2.若无头指针，或链表前面区域情况未知，则找到p结点后，将p的next指向新结点，同时将p结点数据与新结点数据对调，即可完成了后插入后对调，相当于完成了前插操作。时间复杂度为O(1)；
bool InsertNextNode(LNode *p, ElemType e){
if (p==NULL)
return false; //要找的结点不存在
LNode *s = (LNode *)malloc(sizeof(LNode));
if (s==NULL) //新结点内存分配失败
return false;
s->next=p->next;
p->next=s; //将s连接到p之后
s->data=p->data; //将p中元素复制到s
p->data=e; //将p中元素覆盖为e
return true;
}按照位序删除：
先执行按照位序查找工作，找到想要删除的结点 i 后，将?i - 1 结点的next覆盖为i的next，此时已完成交接工作，然后将 i 结点释放内存即可完成删除，如若需要返回被删除值，可以return第 i 结点的data。
bool ListDelete(LinkList &L, int i, ElemType &e){
if(i<1)
return false;
LNode *p; //指针p用于扫描
int j=0; //当前扫描位置
p = L; //从头结点开始扫描
while (p!=NULL && j<i-1){ //找到第i-1个结点
p=p->next;
j++;
}
if(p==NULL) //i值不合法
return false;
if(p->next == NULL) //第i-1个结点后无结点，即想要删除的那个结点不存在
return false;
LNode *q=p->next; //令q指向被删除的结点
e = q->data; //返回被删除的结点的值
p->next=q->next; //替换掉p的next，完成将q断开的工作
free(q); //释放q，删除成功
return true;
}指定结点的删除：
同样的，如若不知道指定结点前序结点的信息，同样需要替换操作。找到p的后一个结点p+1，将p+1的值覆盖掉p的值，同时将p+1的next变为p的next，再删除p+1结点。将想要删除的结点变成下一个结点，再将下一个结点删除，这样实则完成了删除指定结点的工作。
要注意到的是如果要删除最后一个结点，即其没有后续结点的这种情况，将会出现问题，此时不得不想办法找到前一个结点修改其next为NULL。直接free(p)的话，前一个结点的next将指向不正确。
bool DeleteNode (LNode *p){
if (p==NULL)
return false;
LNode *q=p->next; //令q指向p的下一个结点
p->data=p->next->data; //和后继结点交换数据
p->next=q->next; //将q结点从链中断开
free(q); //释放q
return true;
}双链表
单链表由于只有一个next指针，只能沿着一个方向，有局限性，故引入双链表，加一个prior指针。其他内容与单链表大致相同。双链表可双向遍历。
初始化双链表（带头结点）
type struct DNode{
ElemType data;
struct DNode *prior, *next; //引入prior和next指针
}DNode, *DLinkList;
bool InitDLinkList(DlinList &L){
L = (DNode *)malloc(sizeof(DNode)); //分配一个头结点
if (L==NULL) //分配头结点失败
return false;
L->prior = NULL; //将头结点的prior永远指向NULL
L->next = NULL; //头结点后暂时没有后续结点
return true;
}
void testDLinkList(){ //初始化双链表
DLinkList L;
InitDLinkList(L);
}双链表的插入
在p结点后插入s结点，需要将s结点的prior指向p，将s结点的next指向p原本next指向的结点，然后将p的next指向s。要注意语句顺序。
bool InsertNextDNode(DNode *p, DNode *s){
if (p==NULL || s==NULL)
return false;
s->next=p->next;
if (p->next !=NULL) //如果p结点有后续结点
p->next->prior=s;
s->prior=p;
p->next=s;
return true;
}此为后插操作，但由于双链表的特性，想要执行前插操作，只需找到该结点的前一个结点进行后插操作即可。
双链表的删除
与单链表的删除相类似，不过需要注意的是，要修改被删除的后续结点prior指针。同样的，删除最后一个结点时会有错误。
bool DeleteNextDNode(DNode *p){
if (p==NULL)
return false;
DNode *q = p->next; //找到p的后继
if (q==NULL) //p没有后继
return false;
p->next=q->next;
if (q->next!=NULL) //如果q不是最后一个
q->next->prior=p;
free(q); //释放q
return true;
}如若想删除整个链表，只需从头结点开始一个一个删除即可。
void DestoryList(DLinkList &L){
while (L->next != NULL)
DeleteNextDNode(L);
free(L); //最后释放头结点
L=NULL; //将头指针指向空
}循环链表
循环单链表：只需要将尾结点的next指向头结点即可。这样可以通过向下遍历而达到找到前序结点的功能。判断是否为空即看头结点的next是否指向自己。
循环双链表：头结点prior指向尾结点，尾结点next指向头结点，形成闭环。判断是否为空即看头结点的prior和next是否都指向自己。?
静态链表
用数组的方式实现链表。存储在连续内存空间中，单个结点为：数据+游标 两者组成，游标可以指向在这个内存空间的相对位置，即前一个结点和后一个结点物理位置可以不相接，但前一个结点可以通过游标指向后一个结点的位置。定义一个静态链表的结点的结构体。
#define MaxSize 10 //静态链表的最大长度
struct Node{ //静态链表的结构类型定义
ElemType data; //存储数据
int next; //游标，即下一个元素数组下标
};
void testSLinkList(){
struct Node a[MaxSize];
}#define MaxSize 10 //静态链表的最大长度
typedef struct{ //静态链表的结构类型定义
ElemType data; //存储数据
int next; //游标，即下一个元素数组下标
}SLinkList[MaxSize];
void testSLinkList(){
SLinkList a;
}以上两个方式等价
查找：从头结点出发挨个遍历
插入位序为 i 的结点思路：
1.找到一个空的结点。存入数据元素
2.从头结点出发找到位序为 i-1 的结点
3.修改新结点的next
4.修改i-1号结点的next
顺序表和链表的对比
逻辑结构：
逻辑上都是线性表
存储结构：
顺序表：随机存取 存储密度高 分配空间不方便 改变容量不方便
链表：离散空间分配方便，改变容量方便 不可随机存取 存储密度低
基本操作：?
创建：
顺序表：需要大片空间，浪费空间，不好扩容；静态数组分配容量不可改，动态数组分配需要移动大量元素。
?链表：需要头指针（及头结点），方便扩展；静态数组和动态数组都能改容量，并且不需要移动大量元素。
销毁：
顺序表：将length修改为0。
链表：依次删除各个结点。
静态分配等待系统自动回收，动态分配手动free。
插入/删除：
顺序表：插入删除都需要移动后续大量元素，时间复杂度为O(n)，主要开销为移动元素。
链表：插入删除都只需要修改指针，时间复杂度为O(n)，主要开销为查找目标元素。（效率更高）
查找；
顺序表：按位查找：O(1)；按值查找：O(n)，若有序，可用折半查找等方法让其变成O(log2n）。
链表：按位查找：O(n)；按值查找：O(n)。都需要一个一个遍历。
表长难以估计，经常需要增加删除元素——链表
表长可以估计，查询搜索操作较多——顺序表
练习：
?思路：初步思路：首先遍历一遍链表，计算结点个数，设为n，再重新遍历一遍，倒数第k个结点，即n-k+1个结点即可。改进思路：定义两个指针变量p和q，初始时都在头结点，先让p移动到k号结点后，再让p与q同步进行向后移动，当p移动到最后一个结点时，q刚好比p少移动k个结点，即为倒数第k个结点。
typedef struct LNode{
int data;
struct LNode *link;
}LNode, *LinkList; //定义链表结点结构体
int Search_k(LinkList list, int k){ //查找链表list的倒数第k个结点，输出其值域
LNode *p=list->link, *q=list->link;//p、q指针初始指向头结点
int count=0;
while(p!=NULL){ //遍历链表直到最后一个
if (count<k) //若计数小于k则只有p移动
count++;
else q=q->link; //p、q同步移动
p=p->link;
}
if(count<k)
return 0; //失败
else {
printf("%d",q->data); //打印该结点值域
return 1; //成功
}
}总结：两个指针能同步移动的方法通常会时间开销更少，多往这方面考虑。
?思路：初步思路：设定两个指针变量p、q，初始位于str1和str2处，p指针变量每向后移动一格，与q比对，不同则继续遍历，遍历完成以后，仍未找到，q指针向后移动一格，p重新从头开始遍历。设单词长为a，b，后缀长为k，此方法需要的时间开销为【(a-k)*b+b-k+1】，过于繁琐。优化思路：首先各自遍历一遍，计算各自总长度,较长的为M，较短的为m，再让p从长的那个链表开始移动到第M-m+1个结点，然后pq同步移动，直到出现指向相同。此法时间开销为【2(M+m)?】? ，相对较低，比较合适。
typedef struct Node{
char data;
struct Node *next;
}SNode;
/*求单词长度函数*/
int WordLength(SNode *head){
int len=0;
while(head->next!=NULL){ //如果计数指针未遍历完
len++; //长度加一
head=head->next;
}
return len;
}
/*找出共同后缀起始地址函数*/
SNode* find_addr(SNode *str1, SNode *str2){
int a,b;
int MAX,MIN;
SNode *M, *m;
a=listlen(str1);
b=listlen(str1);//计算二者单词长度
if(a>b){
MAX=a;
M=str1;
MIN=b;
m=str2;
}
else{
MAX=b;
M=str2;
MIN=a;
m=str1;
}//将二者长的长度设为MAX，短的长度设为MIN
//p指向长的链表头结点，q指向短的链表头结点
for( ;MAX>MIN;MAX--)
p=p->next; //p先移动到MAX-MIN+1个结点处
while(p->next!=NULL&&p->next!=q->next){ //p、q同步移动
p=p->next;
q=q->next;
}
return p->next; //返回共同后缀的起始地址
}? ? 总结：与上一题类似，两个指针能同步移动的方法通常会时间开销更少，多往这方面考虑。
? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 思路：
初始思路：从第一个数字开始，选取为备选数字，开始向后遍历，每到下一个数字，判断是否为该数字或该数字的相反数，如果是，执行一次删除结点操作，如果不是继续向后遍历，直到遍历完成。然后选取第二个数字作为备选数字，重复执行上一个操作。直到选取的备选数字无后继或者无下一个备选数字为止。完成操作。该方法需要遍历很多次，不是特别方便。
优化思路 ：用一个辅助数组 q[] 来作为某数字及其绝对值是否出现的表示，将数组大小设置为n+1，，初始全部元素设为0，用 q[|data|]来标记data以及data相反数是否出现过。开始遍历链表，每遍历一个，读取其data，并观察数组中 q[|data|] 的值：如此时?q[|data|] = 0 ，视为该数字或其相反数第一次出现，将之改为0；如此时?q[|data|]??= 1 ，视为已出现过，将遍历到的结点删除。遍历结束后，将 q[] 释放。此方法只需要一次遍历即可，时间复杂度为O(m)（m为整数数量），但需要引入一个辅助数组，空间复杂度为O（n+1）（n为链表中最大整数，题目已给出）。?
typedef struct node{
int data;
struct node *link;
}NODE, *PNODE;
void func(PNODE h, int n){
PNODE p=h,r;
int *q,m;
q=(int *)malloc(sizeof(int)*(n+1));//申请一个大小为n+1的辅助空间q
for(int i=0;i<n+1;i++)
*(q+i)=0;
while(p->link!=NULL){
m=p->link->data>0? p->link->data:-(p->link->data);
if(*(q+m)==0){//判断该结点的data是否已经出现过
*(q+m)=1; //首次出现
p=p->link;//保留
}
else{ //重复出现
r=p->link;
p->link=r->link;
free(r);//删除
}
}
free(q);//释放q占用的空间
}
? ?总结：用空间换时间，此思路值得借鉴反思。
栈和队列
栈的基本概念：
逻辑结构：是一种只允许在一段进行插入或删除操作的线性表
空栈：没有元素? ?栈顶：允许操作的一段? ?栈底：不允许操作的一端
进栈顺序：1 2 3 4 5，出栈顺序：5 4 3 2 1 后进先出
LIFO （Last In First Out）
常用操作：
InitStack(&S); 初始化栈
DestoryStack(&S); 销毁栈
Push(&S, x); 进栈
Pop(&S, &x); 出栈
GetTop(&S, &x); 读栈顶元素
StackEmpty(S); 判断栈是否为空
顺序栈的定义
#define MaxSize 10
typedef struct{
ElemType data[MaxSize]; //静态数组存放栈中数据
int top; //栈顶指针（数组下标）
}SqStack;
void InitStack(SqStack &S){
S.top=-1; //初始化栈顶指针为-1
}
void testStack(){
SqStack S;
InitStack(S);
}
如果要判断栈是否为空，判断栈顶指针是否为-1即可
bool StackEmpty(SqStack S){
if(S.top==-1)
return true; //空
else
return false;//非空
}进栈操作：
先判断栈是否已满，不满则可进栈，并让top加1
bool Push(SqStack &S, ElemType x){
if(S.top==MaxSize-1)；//栈满了
return false;
S.top = S.top+1;//指针加一
S.data[S.top]=x;//元素入栈
//以上两句可以代替为 S.data[++S.top]=x;
return true;
}出栈操作：
先判断栈是否已空，不空则可出栈，并让top减1
bool Pop(SqStack &S, ElemType &x){ //此x需要返回给使用者
if(S.top==-1)；//栈空了
return false;
x=S.data[S.top];//元素入栈
S.top = S.top-1;//指针减一
//以上两句可以代替为 x=S.data[S.top--];
return true;
}读栈顶元素操作：
如同出栈操作,只是不改变top指针
bool GetTop(SqStack &S, ElemType &x){ //此x需要返回给使用者
if(S.top==-1)；//栈空了
return false;
x=S.data[S.top];//用x来记录栈顶元素
return true;
}共享栈：
同一片空间一端是一个栈的栈底部，另一端是另一个栈栈底，共同往中间入栈，当top1+1=top2时，存满
链栈
特殊的但链表，只是只能在一段进行删除/插入，操作与单链表类似。
队列：
只允许在一端进行插入，另一端进行删除的线性表
队头删除，队尾删除，空队列
FIFO （First In First Out）
队列的顺序实现：
引入队头指针front 队尾指针rear，当front =rear 时，为空队列。
队列的各个操作：
#define MaxSize 10
typedef struct{ //创建队结构体
ElemType data[MaxSize];
int front , rear; //引入队头队尾指针
}SqQueue;
void InitQueue(SqQueue &Q){
Q.rear=Q.front=0 ; //初始化队头队尾指针指向0；
}
void testQueue(){
SqQueue Q;
InitQueue(Q);
}
//判断队列是否为空
bool StackQueue(SqQueue Q){
if(Q.rear==Q.front)
return true; //空
else
return false;//非空
}
//入队操作
bool EnQueue(SqQueue &Q, ElemType x){
if(Q.rear+1)%MaxSize==Q.front)；//队满了
//为了不让队头指针和队尾指针指向同一个位置而导致误以为队空
//队满实际上会空出一个位置出来
return false;
Q.data[Q.rear]=x;//将x插入队尾
Q.rear=（Q.rear+1)%MaxSize; //队尾指针加一取模；
//取模加一是为了如果队头有因为出队而出现的空余位置，
//新入队元素可进入该空余位置，即队尾指针会一开始队尾的位置（此时已空闲）
//逻辑上看类似于环状队列
return true;
}
//删除出队操作
bool DeQueue(SqQueue &Q, ElemType &x){ //此x需要返回给使用者
if(Q.rear==Q.front)；//队空了
return false;
x=Q.data[Q.front];//元素出队
Q.front = (Q.front+1)%MaxSize;//队头指针后移
return true;
}
//查询队头元素操作
bool GetHead(SqQueue &Q, ElemType &x){ //此x需要返回给使用者
if(Q.rear==Q.front)；//队空了
return false;
x=Q.data[Q.front];//元素入队
return true;
}前文可知，为了不让队头指针和队尾指针指向同一个位置而导致误以为队空，队满实际上会空出一个位置出来，是浪费空间的行为。为了解决这一问题，可以引入size变量，每入队size+1，每出队size-1，如果当front=rear的时候，只需判断size=0还是MaxSize，为0则代表队空，为MaxSize则代表队满。同样的，可以引入tag变量，每当操作为入队时，令tag=1，出队时，令tag=0，如果当front=rear的时候，只需判断tag=0还1，为0则代表队空，为1则代表队满。
front==rear && size = 0; //空
front==rear && size = MaxSize; //满
front==rear && tag = 0; //空
front==rear && tag = 1; //满想你！！！！
想你！！！！
想你！！！！
想你！！！！
想你！！！！
