考研算法实现.md

王道数据结构算法实现

第一章

顺序表

#include<iostream>
using namespace std;
const int max_size = 10;
typedef struct Sqlist{
    int data[max_size];
    int length;
    int max_size;
}Sqlist;
void initList(Sqlist &L) {
    L.length = 0;
}
//构建
int getElem(Sqlist L, int p, int &e){
    if (p < 0 || p >= L.length) {
        return 0;
    }
    e = L.data[p];
    return 1;
}
//插入
int insertElem(Sqlist &L, int p, int e) {
    if (p < 0 || p > L.length || L.length == max_size) {
        return 0;
    }
    for (int i = L.length-1; i >= p; i--) {
        L.data[i+1] = L.data[i];
    }
    L.data[p] = e;
    ++(L.length);
    return 1;
}
//按元素查找
int findElem(Sqlist L, int e) {
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e) {
            return i;
        }
    }
    return -1;
}
//删除
int deleteElem(Sqlist &L, int p, int &e) {
    if (p < 0 || p >= L.length) {
        return 0;
    }
    e = L.data[p];
    for (int i = p; i < L.length-1; i++) {
        L.data[i] = L.data[i+1];
    }
    --(L.length);
    return 1;

}


//题目实现
class Exercises
{
    public:
    void first(Sqlist &a)//第一题
    {
        if(a.length==0)
        {
            cout<<"error"<<endl;
            return;
        }
        int res = a.data[0], pos = 0;//pos是记录删除下标
        for(int i =0;i<a.length;i++)
        {
            if(a.data[i]<res)
            {
                res = a.data[i];
                pos =i;
            }
        }
        a.data[pos] =a.data[a.length-1];
        a.length--;
        cout<<"over"<<endl;
    }

    void second(Sqlist &a)//2
    {
        int tmp;//原理和交换一样就是不停的借助辅助变量实现前后交换
        for(int i =0;i<a.length/2;i++)
        {
            tmp = a.data[i];
            a.data[i] = a.data[a.length-i-1];//第一个和最后一个匹配，第二个和倒数第二个匹配.....
            a.data[a.length-i-1] = tmp;
        }
    }

    //3
    void third_1(Sqlist &a,int x)
    {
        int k =0;//记录下标
        for(int i =0;i<a.length;i++)
        {
            if(a.data[i]!=k)
            {
                a.data[k] = a.data[i];
                k++;//思路就是遇到不等于的就将值赋给当前k下标的，遇到等于目标值的时候k不动，下一个不等于目标值的自然就给目标值覆盖了
            }
        }
        a.length = k;//更新长度
    }

    //3.1,原理是每次往前移动k个，k是出现x的个数，表明前面有k个空位，直接往前移就行(其他都移动好了，可以看作把空位往后移动了)
    void third_2(Sqlist &a,int x)
    {
        int k =0,i =0;
        while(i<a.length)
        {
            if(a.data[i]==x) k++;
            else a.data[i-k] = a.data[i];

            i++;
        }
        a.length = a.length-k;
    }

    //4
    void four(Sqlist &a,int s,int t)
    { 
        if(s>=t||a.length==0)
        {
            cout<<"error";
            return;
        }
        int i =0,j =0;
        for(i =0;i<a.length&&a.data[i]<s;i++); //寻找第一个大于或等于s的元素
        if(i>=a.length)
        {
            cout<<"error";
            return;
        }
        for(int j =i;j<a.length&&a.data[j]<=t;j++);//寻找大于t的第一个元素
        for(;j<a.length;i++,j++)
            a.data[i] = a.data[j];//覆盖元素，类似双指针
        a.length = i;

    }

    //5,原理和第三题差不多
    void five(Sqlist& a,int s,int t)
    {
        if(a.length ==0||s>=t)
        {
            cout<<"error";
            return;
        }
        int i,k =0;
        for(int i = 0;i<a.length;i++)
        {
            if(a.data[i]>=s&&a.data[i]<=t)
                k++;
            else
            a.data[i-k] = a.data[i];
        }
        a.length -=k;
    }

    //6 原理就是碰到当i，j元素相等时j往下移，不相等时i+1的元素存放j位元素(保证了i上元素放的是之前的相同元素)
    void six(Sqlist& a)
    {
        if(a.length==0)
            return;
        int i,j;
        for(int i =0,j =1;j<a.length;j++)
            if(a.data[i]!=a.data[j])
                a.data[++i] = a.data[j];
        a.length =i+1;
    }

    //7,合并，直接双指针比大小谁符合条件谁往前移动
    void seven(Sqlist a,Sqlist b,Sqlist&c)
    {
        if(a.length+b.length>c.max_size) return;
        int i =0,j  =0 ,k =0;
        while(i<a.length&&j<b.length)
        {
            if(a.data[i]<=b.data[j])
                c.data[k++] = a.data[i++];
            else
                c.data[k++] = b.data[j++];
        }
        while(i<a.length)
            c.data[k++] = a.data[i++];
        while(j<b.length)
            c.data[k++] = b.data[j++];
        c.length=k;
    }

    //8方法和上面第二题一样，先反转所有元素，再分别把属于b和a的反转过来即可
    void eight(int a[],int l,int r,int arr_size)
    {
        if(l>=r||r>arr_size) return;
        int mid = l+r>>1;
        for(int i =0;i<mid;i++)
        {
            int tmp = a[l+i];
            a[l+i] = a[r-i];
            a[r-i]  = tmp;
        }

    }
    //反转实现
    void eight_reverse(int a[],int m,int n,int arr_size)
    {
        eight(a,0,m+n-1,arr_size);
        eight(a,0,n-1,arr_size);
        eight(a,n,m+n-1,arr_size);
    }


    //9,原理参考二分法
    void nine(int a[],int x)
    {
        int n;//n表示共有n个元素
        int l = 0,r = n-1;
        int mid;
        while(l<=r)
        {
            mid = (l+r)/2;
            if(a[mid] == x) break;
            else if(a[mid]<x) l = mid+1;
            else r =mid-1;
        }
        if(a[mid] ==x&&mid!=n-1)
        {
            int t = a[mid];
            a[mid] = a[mid+1];
            a[mid+1] = t;
        }
        if(l>r)
        {
            for(int i =n-1;i>r;i--) 
            {
                a[i+1] =a[i];
                a[i+1] =x;
            }
        }
    } 

    //真题部分看书即可，思路不固定，只要能解答出来都能拿个较高分


};
//3.2题解不懂可以看看
void delete_x(int data[8],int x,int length)
    {
        int k =0,i =0,cnt = 1;
        while(i<length)
        {
            if(data[i]==x) 
            {
                k++;
                
            }
            else
            {
                cout<<cnt<<":";
                cout<<"k="<<k;
                cout<<"i="<<i<<endl;
                cout<<"当前数组：";
                for(int i =0;i<length;i++) cout<<data[i]<<" ";
                cout<<endl;
                data[i-k] = data[i];
                cnt++;
            } 

            i++;
            
        }
        length = length-k;
        for(int i =0;i<length;i++) cout<<data[i]<<" ";
        cout<<endl;
        cout<<length<<endl;
    }
int main()
{
   
    return 0;
}

链表

单链表

单链表可以想象成铁链，一环扣一环,下面是代码实现

#include<iostream>
using namespace std;

typedef struct listnode{
    int data;
    listnode *next;
}lnode,*linklist;//lnode 表示结点，linklist表示链表

//头插法创建链表
linklist list_head_insert(linklist& head) //常规头插法构建链表顺序与输入顺序相反
{
    cout<<"使用头插法构建数组"<<endl;
    lnode* s;
    int n = 1;
    head = new lnode;
    head->next = nullptr;
    cout<<"请输入链表的第"<<n<<"个值：";
    int x;
    cin>>x;
    while(x!=-1)
    {
        n++;

        s =new lnode;
        s->data = x;
        s->next = head->next; //新节点下一个指向原本的开端使其成为新的开端
        head->next = s; //头节点再指向新节点完成添加
        cout<<"请输入链表的第"<<n<<"个值：";
        cin>>x;   //保持循环
    }
    return head;
   
}
//尾插法构建链表
linklist list_tail_insert(linklist &a)
{
    cout<<"使用尾插法构建数组"<<endl;
    int x,n =1;
    a = new lnode;
    lnode *s,*r = a;//r是尾指针方便插入
    cout<<"请输入链表的第"<<n<<"个值：";
    cin>>x;
    while(x!=-1)
    {
        n++;
        s = new lnode;
        s->data = x;
        r->next =s;
        r = s;//r指向新表尾节点
        cout<<"请输入链表的第"<<n<<"个值：";
        cin>>x;
    }
    r->next = nullptr;
    return a;

}
//打印链表
void print_list(linklist cur)
{
    if(!cur->next)
    {
        cout<<"链表为空"<<endl;
        return;
    }
    cout<<"当前链表为:";
    while (cur->next) 
    {
        cout<<cur->next->data<<" ";
        cur = cur->next;
    }
    cout << endl;
}
//按序号查找节点
void getelem_byid(linklist a)
{
    cout<<"输入要查找的序号:";
    int x;
    cin>>x;
    if(x<1) 
    {
        cout<<"错误";
        return;
    }
    int j =1;
    lnode *p = a->next;
    cout<<j<<"号元素:"<<p->data<<endl;
    while(p&&j<x)
    {
        p = p->next;
        j++;
    }
    cout<<"找到了"<<j<<"号元素:"<<p->data<<endl;
}
//按值查找元素
void getelem_byval(linklist l)
{
    cout<<"输入要查找的值:";
    int x;
    cin>>x;
    int cnt =0;
    lnode *p=l->next;
    while(p)
    {
        cnt++;
        if(p->data==x)
        {
            cout<<"第"<<cnt<<"号元素"<<p->data<<endl;
            break;
        }else
        {
            p = p->next;
        }
    }
}
//插入节点
void insert(linklist &l)
{
    cout<<"请输入插入位置:";
    int x;
    cin>>x;
    if(x<1)//查询值的操作可以封装但是为了方便有很多输出的语句，避免太乱就再写一次
    {
        cout<<"error"; 
        return;
    }
    lnode* p = l->next;
    int cnt =1;
    while(cnt<x) //查找插入位置，由于是往后插入所以插在第i个位置要找到第i-1个节点
    {
        p = p->next;
        cnt++;
    }
    lnode* s= new lnode;
    cout<<"插入的值：";
    cin>>s->data;
    s->next = p->next;//插入的关键，画图好理解，不能先让p下一个指向s否则会让原本p后的数据丢失
    p->next = s;
    print_list(l);
    
}
//删除节点
void delete_node(linklist &l)
{
    cout<<"请输入删除位置:";
    int x;
    cin>>x;
    if(x<1)
    {
        cout<<"error"; 
        return;
    }
    lnode* p = l->next;
    int cnt =1;
    while(cnt<x) 
    {
        p = p->next;
        cnt++;
    }
    lnode* q = p->next; //找到要删除的节点q
    p->next = q->next;  //让q的前驱节点直接指向q的下一个节点完成删除
    delete(q);//别忘了释放q
    print_list(l);

}
//求表长
void list_len(linklist l)
{
    int cnt =0;
    while(l->next)
    {
        l = l->next;
        cnt++;
    }
    cout<<"表长："<<cnt<<endl;
}
int main()
{
    linklist a;
    a =list_head_insert(a);
    print_list(a);
    //cout<<a->data<<endl;
    //getelem_byval(a);
    //insert(a);
    //delete_node(a);
    list_len(a);
    delete(a);
    
    return 0;
}

双链表

这里就直接用csdn上一位大神的了，具体和单链表比较就只有插入和删除需要注意。

/*
  Author : panxiaolan
  Time : 2021-10-12

  双链表的基本操作(带头节点): 每个节点由三部分组成,只需处理好当前节点与邻接节点的关系即可。
  (1)、双链表的定义
  (2)、双链表的初始化
  (3)、双链表的建立:
    a、头插法建立
    b、尾插法建立 
  (4)、双链表的插入:
    a、后插
    b、前插
    c、指定位置插入 
  (5)、双链表删除:
    a、按位序删
    b、前删
    c、后删 
  (6)、双链表查找:
    a、按位查找
    b、按值查找 
  (7)、双链表长度 
  (8)、双链表输出 





*/
#include <stdio.h>
#include <stdlib.h>

typedef struct DNode {
  int data;
  struct DNode *prior,*next;
} DNode,*DListLink;

// 双链表的初始化(带头节点)
DListLink initDListLink(DListLink &L) {
  L = (DNode *)malloc(sizeof(DNode));
  L->next = NULL;
  L->prior = NULL;
  return L;
}

// 判断双链表是否为空
bool isEmpty(DListLink &L) {
  if(L->next == NULL) return true;
  else return false;
}

// 按位查找 : 返回第 i 个节点
DNode* getElem(DListLink &L,int i) {
  DNode *p;
  p = L;
  int j = 0;
  while(p->next != NULL && j < i) {
    p = p->next;
    j ++;
  }
  return p;
}

// 按值查找 : 返回数据域是 e 的节点
DNode* locateElem(DListLink &L,int e) {
  DNode *p;
  p = L->next;
  while(p && p->data != e) {
    p = p->next;
  }
  return p;
}

// 后插 : 在 p 节点后插入节点 s
bool insertNextNode(DNode *p,DNode *s) {

  if(!p || !s) return false;

  s->next = p->next;
  p->next->prior = s;
  s->prior = p;
  p->next = s;

  return true;
}

// 后插 : 在 p 节点后插入值是 e 的节点
bool insertNextNodeE(DNode *p,int e) {
  DNode *s;
  s = (DNode *)malloc(sizeof(DNode));
  s->data = e;
  s->next = NULL;
  s->next = p->next;
  s->prior = p;
  //p->next->prior = s;
  p->next = s;
//   insertNextNode(p,s);

  return true;
}

// 前插 : 在 p 节点前插入节点 s
bool insertPriorNode(DNode *p,DNode *s) {
  DNode *q = p->prior;
  insertNextNode(q,s);
  return true;
}

// 按位插入 : 在第 i 个位置插入值 e 的节点(位序)
bool insertDListLink(DListLink &L,int i,int e) {
  DNode *p;
  p = getElem(L,i - 1);
  insertNextNodeE(p,e);
  return true;
}

// 删除 : 删除 p 节点的后继节点
bool deleteNextNode(DNode *p) {
  if(p->next == NULL) return false;

  DNode *q = p->next;

  q->next->prior = p;
  p->next = q->next;

  free(q);
  return true;
}

// 删除 : 指定节点 s
bool deleteNode(DNode *s) {
  DNode *p;
  p = s->prior;
  p->next = s->next;
  s->next->prior = p;

  free(s);
  return true;
}

// 删除 : 删除位序 i 的节点, e 是 i 节点的值
bool deletePositionNode(DListLink &L,int i,int &e ) {
  DNode *p = getElem(L,i);
  e = p->data;
  deleteNode(p);
  return true;
}



// 销毁双链表
bool destroyDListLink(DListLink &L) {
  while(L->next != NULL) {
    deleteNextNode(L);
  }
  free(L);
  L= NULL;
  return true;
}

// 尾插法建立双链表:
DListLink tailCreateDListLink(DListLink &L) {
  initDListLink(L);
  DNode *s,*r = L;
  int x;
  while(scanf("%d",&x) != EOF) {
    if(x == -1) break;
    s = (DNode *)malloc(sizeof(DNode));
    insertNextNodeE(r,x);
    r = r->next;
  }
  return L;
}

// 头插法建立双链表
DListLink headCreateDListLink(DListLink &L) {
  initDListLink(L);
  int x;
  while(scanf("%d",&x) != EOF) {
    if(x == -1) break;
    insertNextNodeE(L,x);
  }
  return L;
}

// 双链表的长度:
int length(DListLink &L) {
  int len = 0;
  DNode *p = L->next;
  while(p) {
    len ++;
    p = p->next;
  }
  return len;
}

// 双链表的输出:
void print(DListLink &L) {
  DNode *p = L->next;
  while(p) {
    printf("%d ",p->data);
    p = p->next;
    
  }

  printf("\n");
  return ;
}
int main() {
  DListLink L;
  // 头插法建立双链表
//  headCreateDListLink(L);
  printf("------------尾插法建立单链表---------------\n");
  tailCreateDListLink(L);
  print(L);

  printf("------------判断双链表是否为空---------------\n");
  int Empty = isEmpty(L);
  if(Empty) printf("链表是空!\n");
  else printf("链表非空!\n") ;


  printf("------------按位查找 : 返回第 3 个节点---------------\n");
  DNode *p = getElem(L,3);
  printf("第 i 个节点值是 %d \n",p->data);

  printf("------------按值查找 : 返回数据域是 5 的节点---------------\n");
  DNode *q = locateElem(L,5);
  printf("%d",q->data);


  printf("------------后插 : 在 3 节点后插入节点 s---------------\n");
  print(L);
  DNode *s;
  s = (DNode *)malloc(sizeof(DNode));
  s->data = 999999;
  // p 是第 3 个节点 
  insertNextNode(p,s);
  printf("------------后插 : 在 p 节点后插入节点 s 双链表:---------------\n");
  print(L);

  printf("------------后插 : 在 p 节点后插入值是 e 的节点---------------\n");
  print(L);
  insertNextNodeE(p,111111111);
  printf("------------后插 : 在 p 节点后插入值是 e 的节点 双链表:---------------\n");
  print(L);

  printf("------------前插 : 在 p 节点前插入节点 s---------------\n");
  print(L);
  DNode *before;
  before = (DNode *)malloc(sizeof(DNode));
  before->data = 2222222;
  insertPriorNode(p,before);
  printf("------------前插 : 在 p 节点前插入节点 s 双链表:---------------\n");
  print(L);


  printf("------------按位插入 : 在第 i 个位置插入值 e 的节点(位序)---------------\n");
  print(L);
  insertDListLink(L,3,333333) ;
  printf("------------按位插入 : 在第 i 个位置插入值 e 的节点(位序) 双链表:---------------\n");
  print(L);

  printf("------------删除 : 删除 p 节点的后继节点---------------\n");
  print(L);
  deleteNextNode(p) ;
  printf("------------删除 : 删除 p 节点的后继节点 双链表:---------------\n");
  print(L);

  printf("------------删除 : 指定节点 s---------------\n");
  print(L);
  DNode *d = getElem(L,5);
  deleteNode(d);
  printf("------------删除 : 指定节点 s 双链表:---------------\n");
  print(L);

  printf("------------删除 : 删除位序 i 的节点, e 是 i 节点的值--------------\n");
  print(L);
  int e;
  deletePositionNode(L,4,e) ;
  printf("删除节点的值是 %d\n",e);
  printf("------------删除 : 删除位序 i 的节点, e 是 i 节点的值 双链表:--------------\n");
  print(L);
  printf("------------销毁双链表---------------\n");
  destroyDListLink(L);
  return 0;
}

链表习题实现

class exercises{
    public:
    //1，简单递归
    void one(linklist &l,int x)
    {
        lnode* p;
        if(l==nullptr) return;
        if(l->data==x)
        {
            p =l;
            l=l->next;
            delete(p);
            one(l,x);
        }else one(l->next,x);//l-》data不是x的情况
    }
    //2循环删除值直至末尾
    void two(linklist& l,int x)
    {
        lnode* p,*pre = l,*q;//pre是p的前驱节点
        p=l->next;
        while(p)
        {
            if(p->data==x)
            {
                q = p;
                p = p->next;
                pre->next =p;//此时前驱节点是q的前驱节点，直接指向p删除来q
                delete q;
            }else
            {
                pre = p;
                p = p->next;
            }
        }
    }

    //3，方法很多，遍历链表用容器如栈等储存在输出即可，也可以反转链表再来输出，王道上使用了递归
    void three(linklist l)
    {
        if(l->next)
        three(l->next);//递归会先执行这里，直至不符合条件再从内向外输出，就像无限套娃一样直到最后一层再一次返回输出每一层结果
        if(l)
        cout<<l->data<<" ";
    }
    void three_ignore_head(linklist l)
    {
        if(l->next) three(l->next);
    }

    //4，用节点记录最小值的前驱节点，遍历链表找到后删除
    void four(linklist &l)
    {
        lnode *pre=l,*p =pre->next;
        lnode *min_pre =pre,*minp = p;//存储最小前驱和节点
        while(p)
        {
            if(p->data<minp->data)
            {
                minp = p;
                min_pre = pre;
            }
            pre = p;//不断更新
            p = p->next;

        }

        min_pre->next = minp->next;
        delete minp;//完成节点删除
    }

    //5法一是将头节点摘下再将原本的节点依次尾插头节点后
    void five_1(linklist& l)
    {
        lnode *p,*r;
        p = l->next;
        l->next = nullptr;//摘下头节点
        while(p)
        {
            r = p->next;//取到插入节点
            p->next = l->next;//将节点插入头节点后
            l->next = p;//完成插入连接
            p =r;//更新下一个节点
        }
    }
    //法2，记录前驱节点，让p指向前驱节点同时让r = p->next 记录下一个处理的节点
    void five_2(linklist& l)
    {
        lnode* pre,*p = l->next,*r = p->next;
        p = nullptr;
        while(r)
        {
            pre = p;
            p  =r;
            r  =r->next;
            p->next = pre;
        }
        l->next = p;//处理最后一个节点
    }

    // 6 贪心，对每次节点选择插入位置
    void six(linklist &l)
    {
        lnode *p = l->next,*pre;
        lnode *r = p->next; //保证不断链
        p->next = nullptr;
        p = r;
        while(p)
        {
            r = p->next;
            pre = l;
            while(pre->next&&pre->next->data<p->data)
                pre = pre->next;//遍历查找需要插入*p的前驱节点
            p->next = pre->next;
            pre->next = p;
            p =r;
        }

    }

    //7 类似删除特定接节点
    void seven(linklist& l,int a,int b)
    {
        lnode *p = l,*r = l->next; //p是前驱节点，r是处理节点
        while(p)
        {
            if(r->data>=a&&r->data<=b)
            {
                p->next = r->next;
                delete r;
                r = p->next;

            }else
            {
                p = r;
                r = r->next;
            }
        }
    }

    //8可以暴力，王道上用数学思想，计算两条链表长度只差，再让较长的一段链表遍历先走长度之差次，然后一起遍历如果末尾相同则表明有共同域。
    //共同域是指只要某一节点相同则后所有节点都相同。
    int length(linklist&a)
    {
        int cnt =0;
        while(a)
        {
            cnt++;
            a = a->next;
        }
        return cnt;
    }
    bool eight(linklist&a,linklist&b)
    {
        int dist;
        int len1 = length(a),len2 =length(b);//计算长度
        linklist long_list,short_list;
        if(len1>len2)
        {
            long_list = a->next,short_list = b->next;
            dist = len1-len2;
        }
        else
        {
            long_list = b->next,short_list = a->next;
            dist = len2-len1;
        }
        while(dist--)
        {
            long_list = long_list->next;//让长的遍历到剩余结点和短的一样
            
        }
        while(long_list)
            {
                if(long_list==short_list)
                    return true;
                else{
                    long_list = long_list->next;
                    short_list = short_list->next;
                }
            }
            return false;
    }

    //9，直接暴力
    void nine(linklist&l)
    {
        while(l->next)
        {
            lnode *pre = l;
            lnode *p = pre->next;
            lnode *u;//记录要删除的节点
            while(p->next)
            {
                if(p->next->data<pre->next->data)
                    pre = p;
                p = p->next;
            }
            cout<<pre->next->data;
            u = pre->next;
            pre->next = u->next; //删除节点
            delete u;
        }
        delete l;//释放头节点
    }

    //10，以前力扣上好像做过原题，双指针
    void ten(linklist &a)
    {
        int i =0;
        linklist b = new lnode;
        b->next = nullptr;
        lnode* ra = a,*rb = b ,*p;//p是工作指针
        p = a->next;
        a->next = nullptr; //清空a表
        while(p)
        {
            i++;
            if(i%2==0)
            {
                rb->next = p;
                rb = p;
            }else
            {
                ra->next = p;
                ra = p;
            }
            p = p->next;
        }
        ra->next = nullptr;
        rb->next = nullptr;

    }

    //11，可以用10题的思想，区别就是对b用头插法
    void eleven(linklist& a)
    {
        linklist b =new lnode;
        b->next = nullptr;
        lnode *p = a->next,*q;
        lnode* ra = a;
        while(p)
        {
            ra->next = p;
            ra = p;
            if(p)
            {
                q = p->next;//头插法会使p断链，因此使用q记录
                p->next = b->next;
                b->next = p;
                p = q;
            }
        }
        ra->next = nullptr;
    }

    //12,有序表去重，思路就是下一个节点的值和当前节点相同就删除
    void twelve(linklist &l)
    {
        lnode *p =l->next,*q;
        if(!p) return;
        while(p->next)
        {
            q = p->next;
            if(p->data==q->data)
            {
                p->next = q->next;
                delete q;
            }
            else p = p->next;
        }
    }

    //13 将两条递增链表递减归并，用头插法
    void num13(linklist&la,linklist&lb)
    {
        lnode *r,*pa = la->next,*pb = lb->next;
        la->next = nullptr;
        while(pa&&pb)
        {
            if(pa->data<=pb->data)
            {
                r = pa->next; //暂存插入的节点的后续，头插法会导致断链
                pa->next = la->next;
                la->next = pa;
                pa =r;//恢复
            }
            else
            {
                r = pb->next;
                pb->next = la->next;
                la->next = pb;
                pb =r;
            }
        }
        if(pa)
        pb = pa;//剩下只有一条时，直接插入即可
        while(pb)
        {
            r = pb->next;
            pb->next = la->next;
            la->next = pb;
            pb =r;
            
        }
        delete lb;
    }

    //14还是类似双指针,较小指针往前移动
    void num14(linklist& a,linklist&b)
    {
        lnode *p=a->next,*q = b->next,*r,*s;
        linklist c =new lnode;
        r = c;
        while(p&&q)
        {
            if(p->data<q->data)
                p = p->next;
            else if(p->data>q->data)
                q = q->next;
            else//等于的情况
            {
                s = new lnode;
                s->data = p->data;
                r->next = s;
                r = s;
                p = p->next;
                q = q->next;

            }
        }
        r->next = nullptr;
    }
    //15,思路类似上题，归并双指针
    void num15(linklist &la,linklist&lb)
    {
        lnode* pa =la->next,*pb = lb->next;
        lnode* u ,*pc = la;
        while(pa&&pb)
        {
            if(pa->data==pb->data)
            {
                pc->next = pa;
                pc = pa; // 往后移动pc指向
                pa = pa->next;
                u = pb;
                pb = pb->next;
                delete u;
            }
            else if(pa->data<pb->data)
            {
                u = pa;
                pa = pa->next;
                delete u;
            }
            else 
            {
                u = pb;
                pb = pb->next;
                delete pb;
            }
            while(pa)
            {
                u = pa;
                pa = pa->next;
                delete u;
            }
            while(pb)
            {
                u = pb;
                pb = pb->next;
                delete u;
            }
            pc->next = nullptr;
            delete lb;
        }
    }
    
    //16 找到 a中等于b1的元素开始判断，如果直至b末尾都相同则是子链
    bool num16(linklist a,linklist b)
    {
        lnode *p = a;
        lnode *pre = p,*q = b;
        while(p&&q)
        {
            if(p->data==q->data)
            {
                p = p->next;
                q = q->next;
            }
            else
            {
                pre = pre->next;
                p = pre; //p是记录a中即将匹配的新节点
                q = b; //q从头开始
            }
            if(!q)
             return true;
            else return false;
        }
    }
    //17,双链表一个往前遍历一个往后遍历
    bool num17(dlinklist l)
    {
        dnode *p = l->next,*q = l->prior;
        while(p!=q&&q->next!=p)//切记不能写成p->next !=q，这会导致匹配最后一个时出错
        {
            if(p->data==q->data)
            {
                p = p->next;
                q = q->next;
            }
            else return false;
        }
        return true;
    }

    //18画图理解方便，先让第一个链表尾指针指与第二个链表头节点项链再使其循环
    void num18(linklist &h1,linklist &h2)
    {
        lnode *p,*q;
        p = h1;
        while(p->next!=h1)
            p= p->next;//找到尾节点
        q = h2;
        while(q->next!=h2)
            q = q->next;
        p->next = h2;  //第一个链表的尾巴连接到第二个头结点上
        q->next = h1;   //第二个链表尾巴连到第一个头上
    }
    //19，暴力
    void num19(linklist &l)
    {
        lnode *p,*pre,*minp,*minpre;
        while(l->next!=l)
        {
            p = l->next;pre = l;
            minp = p;minpre = pre;
            while(p!=l)
            {
                if(p->data<minp->data)
                {
                    minp = p;
                    minpre = pre;
                }
                pre = p;
                p = p->next;
            }
            cout<<minp->data;
            minpre->next = minp->next;
            delete minp;
        }
        delete l;//结束删除头节点
    }

    //20 多加了个频度元素不好写，就不写了
    //21 力扣上好像写过，快慢指针,一个每次前进两步，一个每次前进一步。如果不含有环，跑得快的那个指针最终会遇到 null，说明链表不含环；如果含有环，快指针最终会超慢指针一圈，和慢指针相遇，说明链表含有环。
    lnode* num21(linklist &head)
    {
        lnode *fast = head,*slow = head;
        while(fast&&fast->next)
        {
            slow=slow->next;
            fast = fast->next->next;//快的走两步
            if(slow==fast) break;
        }
        if(!fast||!fast->next) //没有环的情况
        {
            return;
        }
        lnode *p1 =head,*p2 = slow;
        while(p1!=p2)
        {
            p1 =p1->next;
            p2 = p2->next;
        }
        return p1;
    }
};  

第二章

栈

普通栈的简单实现

#include<iostream>
using namespace std;

#define max_size 10

typedef struct stack
{
    int data[max_size] = {1,2,3,4,5};
    int top;//顶部指针
}sqstack;
void init(sqstack &s)
{
    s.top  =-1;
}
void output(sqstack s)
{
    cout<<"当前栈为：";
    while(s.top>=0)
    cout<<s.data[s.top--]<<" ";
    cout<<endl;
}
//入栈
void push(sqstack &s,int x)
{
    if(s.top==max_size-1)
    {
        cout<<"栈满了"<<endl;
        return;
    }
    s.data[++s.top]  =x; //先加栈顶在加元素
}
//出栈
void pop(sqstack &s)
{
    if(s.top==-1)
    {
        cout<<"栈空，无元素输出"<<endl;
        return;
    }
    cout<<"出栈:"<<s.data[s.top--]<<endl;
    output(s);       
}
//判断栈空
void empty(sqstack s)
{
    if(s.top==-1)
    {
        cout<<"栈空"<<endl;
        
    }
    else
    {
        cout<<"非空"<<endl;
      
    }
}
//读取栈顶元素
void get_top(sqstack s)
{
    
    if(s.top==-1)
    {
        cout<<"栈空"<<endl;
        return;
    }
    cout<<"栈顶元素"<<s.data[s.top];
}
//删除栈
void delete_stack(sqstack &s)
{
    s.top=-1;
}

int main()
{
    //搭建栈
    sqstack s;
    init(s);
    cout<<"开始搭建栈,输入插入数量"<<endl;
    int n;
    cin>>n;
    int cnt = 1;
    for(int i =0;i<n;i++)
    {
        // int x;
        // cout<<"输入插入元素:";
        // cin>>x;
        push(s,cnt);
        cnt++;
    }
    output(s);
    pop(s);

    empty(s);
    get_top(s);
    delete_stack(s);
    output(s);

    return 0;
}

链栈

和头插法的单链表差不多

//链栈的结构
typedef struct linkstack
{
  int data;
  struct linkstack* next;
}stacknode, * lstack;
//链栈功能实现
class link_stack
{
    public:
    void output(lstack l)
    {
        stacknode* p = l;
        if (!p)
        {
            cout << "链栈为空！" << endl;
            return;
        }  
        cout << "链栈从顶往下为：";
        while (p)
        {
            cout << p->data << " ";
            p = p->next;
        }
        cout << endl;
    }
    void init(lstack  &l)
    {
        l=NULL;//不能为l = nullptr
    }
    //链栈的入栈
    void push(lstack& l)
    { //在栈顶插入元素e,链栈不需要判断栈满
        stacknode* p = new stacknode; 
        cout<<"输入要插入的值:"<<endl;
        int x;
        cin>>x; 
        p->data = x;    
        p->next = l;    
        l = p;                
    }
    //构建链栈
    void create(lstack &l)
    {
        init(l);
        cout<<"输入创建长度:";
        int n;
        cin>>n;
        for(int i =0;i<n;i++)
        {   
            push(l);
        }
        output(l);
    }
    //出栈元素
    void drop_top(lstack &l)
    {
        if(!l)
        {
            cout<<"为空"<<endl;
            return;
        }
        //直接删除就好了
        stacknode *p;
        p = l;
        l = l->next;
        cout<<"出栈，删除栈顶元素:"<<p->data<<endl;
        delete p;
        output(l);
    }

    //查询栈顶元素
    void get_top(lstack l)
    {
        if(!l)
        {
            cout<<"为空"<<endl;
            return;
        }
        cout<<"当前栈顶元素:"<<l->data<<endl;
    }
};

课后习题

//练习题
class exercises
{
    public:
    //1,不是算法题，画个图推一下就好了
    //2，也是模拟一下就可以了，第一个可以，第二个不行
    //3,写一个栈，如果出现栈空且还有操作数或无后续操作但栈不空就报错
    //官方答案上是直接判断数组，若出栈数大于入栈数则报错，结束后在判断入栈和出栈的次数是否相同
    bool num3(char op[])
    {
        int i =0;
        int j = 0,k = 0;
        while(op[i]!='\0')
        {
            switch (op[i])
            {
            case 'I' : j++;
                break;
            
            case 'O' : k++;
                if(k>j)
                {
                    cout<<"非法"<<endl;
                    exit(0);
                }
                
            }
            i++;
        }
        if(j!=k)
        {
            cout<<"非法"<<endl;
            return false;
        }else
        {
            cout<<"合法"<<endl;
            return true;
        }
           
    }
         //4,判断对称用双指针也可以，用栈,数组也可以，就是从前一半进栈，再出栈看是否和后一半一样
        bool num4(lstack l,int n)//n是长度
        {
            int i;
            char s[n/2];
            stacknode *p = l->next;
            for(int i =0;i<n/2;i++)
            {
                s[i] = p->data;
                p = p->next;
            }
            i--;
            if(n%2==1)
                p=p->next;
            while(p!=NULL&&s[i]=p->data)
            {
                i--;
                p = p->next;
            }
            if(i==-1)
            return true;
            else return false;


            
        }

        //5
        typedef struct 
        {
            int stack[max_size];
            int top[2];//两个栈顶指针
        }stk;
        stk s;
        void push(int i,int x)//i是左右栈标志，0是左边，1是右边
        {
            if(i<0||i>1)
            {
                cout<<"输入错误"<<endl;
                return;
            }
            if(s.top[1]-s.top[0]==1)
            {
                cout<<"栈满"<<endl;
                return;
            }
            //书上用的是switch，麻烦了
            if(i)
            {
                s.stack[--s.top[1]] =x;
                
            }else
            {
                s.stack[++s.top[0]] = x;

            }
            cout<<"插入成功";
        }
        
        //退栈操作
        void pop(int i)
        {
            if(i<0||i>1)
            {
                cout<<"输入错误"<<endl;
                return;
            }
            if(i)
            {
                if(s.top[0]==-1)
                {
                    cout<<"栈空，退无可退"<<endl;
                    return;
                }
                else
                {
                    s.stack[s.top[0]--];
                    cout<<"退栈成功"<<endl;
                }
            }
            else
            {
                if(s.top[0]==max_size)
                {
                    cout<<"栈空，退无可退"<<endl;
                    return;
                }
                else
                {
                    s.stack[s.top[1]++];
                    cout<<"退栈成功"<<endl;
                }
            }
        }

    
};

队列

循环队列

#include<iostream>
using namespace std;
//队列结构
const int max_size = 10;
typedef struct {
    int data[max_size];
    int front,rear;//头指针和尾指针
    int length;//长度，不一定会用
}queue;

void init(queue &q)
{
    q.front = 0,q.rear = 0;
}
//判断队空
bool empty(queue q)
{
   return (q.front==q.rear);
}
//打印队列
void print_queue(queue q)
{
    if(empty(q))
    {
        cout<<"队列为空"<<endl;
        return;
    }
    cout<<"队列元素：";
    while(q.rear-q.front>0)
    {      
        cout<<q.data[q.front]<<" ";
        q.front++;
    }
    cout<<endl;

}
//入队
void push(queue &q)
{
    if((q.rear+1)%max_size == q.front)
    {
        cout<<"队满"<<endl;
        return ;
    }
    cout<<"输入要插入的元素：";
    int x;
    cin>>x;
    q.data[q.rear] = x;
    q.rear = (q.rear+1)%max_size;
}
//出队
void pop(queue &q)
{
    if(empty(q))
    {
        cout<<"队列为空"<<endl;
        return;
    }
    cout<<"删除队头元素:"<<q.data[q.front]<<endl;
    q.front = (q.front+1)%max_size;
}
int main()
{   
    queue q;
    init(q);
    cout<<"输入要创建的数量";
    int n;
    cin>>n;
    for(int i =0;i<n;i++)
    {
        push(q);
    }
    print_queue(q);
    pop(q);
    print_queue(q);

    return 0;
}

链队实现

//链队
typedef struct linkqueue
{
    int data;
    struct linkqueue *next;
}qnode;
//存放指针
typedef struct
{
    linkqueue *front,*rear;
}*lqueue;
class lq
{
    public:
    void init(lqueue &a)
    {
        a->front = a->rear = new linkqueue;
        a->front->next = NULL;
    }
    //判断空
    bool empty(lqueue a)
    {
        return (a->front==NULL&&a->rear==NULL);
    }
    //打印节点
    void print_queue(lqueue a)
    {
        if(empty(a))
        {
        cout<<"链队为空"<<endl;
        return;
        }
        qnode *p = a->front->next;
        cout<<"链队为:";
        while(p)
        {
            cout<<p->data<<" ";
            p = p->next;
        }
        cout << endl;
    }
    //入队
    void push(lqueue &a)
    {
        qnode *p = new linkqueue;
        cout<<"输入入队的值:";
        int x;
        cin>>x;
        p->data = x;
        p->next = nullptr;
        a->rear->next = p;
        a->rear = p;
    }

    //出队
    void pop(lqueue &a)
    {
        if(empty(a))
        {
        cout<<"链队为空"<<endl;
        return;
        }
        qnode *p = a->front->next;
        cout<<"删除队头："<<p->data<<endl;
        a->front->next = p->next;//像链表一样删除
        //注意删除是尾节点的时候
        if(a->rear == p)
            a->rear = a->front;
        delete p;
        
    }

    //清空队列释放空间
    void delete_q(lqueue &a)
    {
        while(a->front)
        {
            a->rear = a->front;
            delete a->front;
            a->front = a->rear;
        }
    }
};

队列课后习题

class exercise
{
    public:
    //1
    void push_1(queue &a,int x)
    {
        if(a.front==a.rear&&a.tag==1)
            return;//队满的情况
        a.data[a.rear] = x;
        a.rear = (a.rear+1)%max_size;
        a.tag  =1;
    }
    void pop_1(queue &q)
    {
        if(q.front==q.rear&&q.tag==0)
            return;//两个条件都满足时为队空的情况
        int x = q.data[q.front];
        q.front = (q.front+1)%max_size;
        q.tag = 0;

    }

    //2 挺简单的，出队入栈，出栈入队
    
    //3用栈两个模拟队列，参考力扣https://leetcode.cn/problems/implement-queue-using-stacks/

    
};

栈的应用

中缀转后缀计算机运算思想:

从左到右开始扫描中缀表达式
遇到数字， 直接输出
遇到运算符
a.若为“(” 直接入栈
b.若为“)” 将符号栈中的元素依次出栈并输出, 直到 “(“, “(“只出栈, 不输出
c.若为其他符号, 将符号栈中的元素依次出栈并输出, 直到遇到比当前符号优先级更低的符号或者”(“。 将当前符号入栈。
扫描完后, 将栈中剩余符号依次输出

//中缀表达式转后缀

#include<iostream>
#include<string>
#include<stack>

using namespace std;

int prio(char op)                   //给运算符优先级排序
{
    int priority;
    if (op == '*' || op == '/')
        priority = 2;
    if (op == '+' || op == '-')
        priority = 1;
    if (op == '(')
        priority = 0;
    return priority;
}
bool Trans(string &str,string &str1)     //引用传递
{
    stack<char> s;                   //定义一个char类型的栈s
    int i;
    for (i = 0; i<str.size(); i++)
    {
        if (str[i] >= '0' && str[i] <= '9'||str[i] >= 'a' && str[i] <= 'z')      //如果是数字，直接入栈
        {
            str1+=str[i];
        }
        else                          //否则不是数字
        {
            if (s.empty())            //栈空则入站
                s.push(str[i]);
            else if (str[i] == '(')   //左括号入栈
                s.push(str[i]);
            else if (str[i] == ')')    //如果是右括号，只要栈顶不是左括号，就弹出并输出
            {
                while (s.top() != '(')
                {
                    str1+= s.top();
                    s.pop();
                }
                s.pop();                 //弹出左括号，但不输出
            }
            else
            {
                while (prio(str[i]) <= prio(s.top()))   //栈顶优先级大于等于当前运算符，则输出
                {
                    str1+= s.top();
                    s.pop();
                    if (s.empty())      //栈为空，停止
                        break;
                }
                s.push(str[i]);   //把当前运算符入栈
            }
        }
    }
    while (!s.empty())        //最后，如果栈不空，则弹出所有元素并输出
    {
        str1+= s.top();
        s.pop();
    }
    return true;
}
int main()                  //主程序
{
    string infix;
    string postfix;
    cout << "请输入中缀表达式：" << infix << endl;
    cin >> infix;
    Trans(infix,postfix);
    cout << "后缀表达式为：" << postfix << endl;
    return 1;
}

中缀转后缀的运算就和Acwing基础课的栈里差不多了.

第三章

串

串的具体实现不在考纲里，实现代码就抄其他大神的了

#include "iostream"

#define MAXSIZE 100
using namespace std;

//定长字符串
struct staticString {
    char str[MAXSIZE + 1];
    int length;
};

//考研常考变长字符串
struct variableString {
    char *str;
    int length;
};

//串赋值
bool variableStringAssign(variableString &variableStr, char *ch);

//获取串长度
int getLength(variableString variableString);

//串比较
int stringCompare(variableString variableString1, variableString variableString2);

//串拼接
bool concat(variableString &result, variableString variableString1, variableString variableString2);

//取子串
bool subString(variableString &result, variableString variableString1, int from, int length);

//清空串
bool clean(variableString &variableString1);

int main() {
    variableString string1{};
    //串赋值
    char ch[MAXSIZE] = {'h', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd', '\0'};
    variableStringAssign(string1, ch);
    for (int i = 0; i < string1.length; ++i) {
        cout << string1.str[i];
    }
    cout << endl;

    //串比较
    variableString string2{};
    string2.str = ch;
    string2.length = string1.length;
    //向string1中添加字符进行测试
//    string1.str[string1.length] = 'a';
//    string1.str[++string1.length] = '\0';
    if (stringCompare(string1, string2) == 0) {
        cout << "string1 equals string2" << endl;
    } else if (stringCompare(string1, string2) > 0) {
        cout << "string1 is bigger than string2";
    } else {
        cout << "string1 is smaller than string2";
    }

    //串拼接
    variableString result1{};
    concat(result1, string1, string2);
    while (*result1.str != '\0') {
        cout << *result1.str++;
    }
    cout << endl;

    //取子串
    variableString result2{};
    subString(result2, string1, 2, 4);
    while (*result2.str != '\0') {
        cout << *result2.str++;
    }
    cout << endl;

    if (clean(string1)) {
        cout << "string1 have been emptied!" << endl;
    }
}

bool variableStringAssign(variableString &variableStr, char *ch) {
    delete variableStr.str;

    int length = 0;
    char *c = ch;

    while (*c != '\0') {
        length++;
        c++;
    }

    if (length == 0) {
        variableStr.str = nullptr;
        variableStr.length = 0;
        return true;
    } else {
        variableStr.str = new char[length + 1];
        if (variableStr.str == nullptr) {
            return false;
        } else {
            c = ch;
            for (int i = 0; i <= length; ++i, ++c) {
                variableStr.str[i] = *c;
            }
            variableStr.length = length;
            return true;
        }
    }
}

int getLength(variableString variableString) {
    return variableString.length;
}

int stringCompare(variableString variableString1, variableString variableString2) {
    for (int i = 0; i < variableString1.length && i < variableString2.length; ++i) {
        if (variableString1.str[i] != variableString2.str[i]) {
            return variableString1.str[i] - variableString2.str[i];
        }
    }

    //前边都一样，比较字符串的长度
    return variableString1.length - variableString2.length;
}

bool concat(variableString &result, variableString variableString1, variableString variableString2) {
    delete result.str;
    result.str = nullptr;

    result.str = new char[variableString1.length + variableString2.length + 1];
    if (result.str == nullptr) {
        cerr << "Your memory is not enough" << endl;
        return false;
    }

    int i = 0;
    while (i < variableString1.length) {
        result.str[i] = variableString1.str[i];
        i++;
    }

    int j = 0;
    while (j <= variableString2.length) {
        result.str[i + j] = variableString2.str[j];
        j++;
    }

    result.length = variableString1.length + variableString2.length;

    return true;
}

bool subString(variableString &result, variableString variableString1, int from, int length) {
    if (from < 0 || from > variableString1.length || length < 0 || length > variableString1.length - from) {
        cerr << "Your parameters is wrong, please check";
        return false;
    }

    delete result.str;
    result.str = nullptr;

    if (length == 0) {
        result.str = nullptr;
        result.length = 0;
        return true;
    } else {
        result.str = new char[length + 1];
        int i = from;
        int j = 0;
        while (i < from + length) {
            result.str[j++] = variableString1.str[i++];
        }

        result.str[j] = '\0';
        result.length = length;
        return true;
    }
}

bool clean(variableString &variableString1) {
    delete variableString1.str;
    variableString1.str = nullptr;
    variableString1.length = 0;

    return true;
}

串的模式匹配

#include<iostream>
#include<string>
using namespace std;

const int N = 100010;
//串的结构
typedef struct
{
    char ch[N];
    int len;
}sstring;
//串的类写法
// class Str{
//     public:
//         char *ch; 
//         int length=0;
//         Str(char *c){
//             ch=c;
//             while(*c){
//                 ++length;
//                 ++c;
//             }
//         }
//     int reassign(char* c){
//         if(ch){
//             ch=NULL;
//             length=0;
//             int len=0;
//             char *temp;
//             temp=c;
//             while(*temp){
//                 ++len;
//                 ++temp;
//             }
//             if(len==0){ // 新字符串为空串 
//                 ch=NULL;
//             }else{
//                 ch=c;
//                 length=len;
//             }
//             return 1;
//         }
//         return 0;
//     }
// };
//打印串
void output(sstring a)
{
    for(int i =0;i<a.len;i++)
    cout<<a.ch[i];
    cout<<endl;
}
//朴素匹配法
void simple(sstring p,sstring s)
{
    cout<<"朴素匹配法-------------------"<<endl;
    cout<<"匹配串:";
    output(s);
    cout<<"模式串:";
    output(p);
    int i = 0,j =0,flag = 0;
    for(i = 0;i<=s.len-p.len;i++)
    {
        int k = i;
        for(j =0;j<p.len;j++)
        {
            if(s.ch[k]==p.ch[j])
            k++;
            else break;
        }
        if(j==p.len)
        {
            cout<<"在第"<<k-p.len<<"位匹配成功 "<<endl;
            flag = 1;
        }
        j=0;
    }
    if(!flag)
    cout<<"匹配失败";
       
}
//kmp
int nxt[N];

void kmp(sstring p,sstring s)
{
    cout<<"kmp匹配法-------------------"<<endl;
    cout<<"匹配串:";
    output(s);
    cout<<"模式串:";
    output(p);
    int i =1,j=0;
    nxt[1] =0;
    //求next数组
    while(i<p.len)
    {
        if(j==0||p.ch[i]==p.ch[j])
        {
            ++i,++j;
            nxt[i] = j;
        }
        else j = nxt[j];
    }
    for(int k = 1;k<=p.len;k++)
    cout<<nxt[k];
    cout<<endl;
    //cout<<"over"<<endl;
    //比较过程
    i = 1,j =1;
    while(i<=s.len&&j<=p.len)
    {
        if(j==0||s.ch[i]==p.ch[j])
        {
            ++i,++j;
        }else j =nxt[j];

        if(j>p.len-1)
        {
            cout<<"在第"<<i-j<<"位匹配成功 "<<endl;
            j = nxt[j];
        }
    }

    //next优化
    int nextval[N];
    i = 1,j =0;
    nextval[1] = 0;
    while(i<p.len)
    {
        if(!j||p.ch[i]==p.ch[j])
        {
            ++i,++j;
            if(p.ch[i]!=p.ch[j]) nextval[i] = j;
            else nextval[i] = nextval[j];
        }else j = nextval[j];
    }
    for(int k = 1;k<=p.len;k++)
    cout<<nextval[k];
    cout<<endl;
}

int main()
{
   
    
    sstring p,s;
    string a = "aaabaaaababaabcaba";
    string b = "abaabcaba";
    for(int i =0;i<a.size();i++)
    {
        s.ch[i] = a[i];
        p.ch[i] = b[i];
    }
    s.len = a.size();
    p.len = b.size();

    //simple(p,s);
    kmp(p,s);
    
    return 0;
}

但是王道上的kmp的nex数组的构建代码似乎有点小问题,还是建议像acwing上的一样从j的下一位匹配

#include<iostream>
//#include<bits/stdc++.h>//万能头文件
#include<vector>
#include<algorithm>
#include<string>
#include<unordered_map>
#include<stack>


using namespace std;
const int N = 1000010,M = N*30;
void getNext(const string& p,int next[])
{

    int len = (int)p.size();
    next[0] = -1;
    int k = -1;
    int j = 0;
    while(j < len)
    {
        if(k == -1 || p[j] == p[k])
        {
            ++j;
            ++k;
            next[j] = k;
        }
        else
        {
            k = next[k];
        }
    }
    for(int x =1;x<=len;x++)//这里的next中的值是前后缀相同的数目，王道中的是相同数目+1即下一次对比的坐标
    cout<<next[x];
    cout<<endl;
}

int kmp(const string& s, const string& pattern)
{
    int n = (int)s.size();
    int ans = -1;
    int i = 0;
    int j = 0;
    int patternLen = (int)pattern.size();

    int next[patternLen] = {0};
    getNext(pattern,next);
    

    while(i < n)
    {
        if(j == -1 || s[i] == pattern[j])
        {
            ++i;++j;
        }
        else
        {
            j = next[j];
        }

        if(j == patternLen)
        {
            ans = i - patternLen;
            break;
        }
    }

    return ans;
}

int main()
{
    string s = "abbbadabaabcabadba";
    string pattern = "abaabcaba";
    cout << kmp(s,pattern) << endl;
    return 0;
}
  

第四章

二叉树

这章节内容很多啊，考的东西也多

#include<iostream>
#include<stack>
#include<queue>
using namespace std;
typedef struct bitnode
{
    int data;
    struct bitnode *l_child,*r_child;
    
}*bitree;


typedef struct Node//用于记录非递归后序
{
  bitree btnode;
  bool isfirst;//提供后序非递归操作标记
}Node,*node;
//线索二叉树
typedef struct threadnode
{
  int data;
  struct threadnode *lchild,*rchild;
  int ltag,rtag;//线索标记
}threadnode,*threadtree;

//普通二叉树
class bi_tree
{
  public:
  bitree t;
  //二叉树的建立
  //思路就是用一个节点从头往下最后一个子树的位置(当且节点大于待插入节点就往左找，反之往右)，
  //找到插入位置后大于根节点的放在右边，小于根节点的放在左边
  void  creat_tree(int a[],int n,bitree &root)
  {
    bitnode *c,*pa=NULL,*p;
    int i;
    root = new bitnode;
    root->data = a[0];
    root->l_child = root->r_child = NULL;
    for(i = 1;i<n;i++)
    {
        p = new bitnode;
        p->l_child = p->r_child = NULL;
        p->data = a[i];
        c = root;
        while(c)
        {
            pa = c;
            if(c->data<p->data)
            c = c->r_child;//如果根节点小于待插入节点就往右遍历
            else c = c->l_child;
        }
        if(pa->data<p->data)
        pa->r_child = p;//右放
        else pa->l_child = p;
    }
    cout<<"二叉树建立完成"<<endl;

  }
  //前序遍历
  void nlr(bitree root)
  {
    if(root)
    {
        cout<<root->data<<" ";
        nlr(root->l_child);
        nlr(root->r_child);
    }
    
  }
  //中序
  void lnr(bitree root)
  {
    if(root)
    {
        lnr(root->l_child);
        cout<<root->data<<" ";
        lnr(root->r_child);
    }
    
  }
  //后序
  void lrn(bitree root)
  {
    if(root)
    {
        lrn(root->l_child);
        lrn(root->r_child);
        cout<<root->data<<" ";
    }
    
  }
  //层序遍历
  void ceng(bitree root)
  {
    if(!root) return;
    queue<bitree> q;
    bitree p = root;
    q.push(p);
    while(!q.empty())
    {
      p = q.front();
      cout<<p->data<<" ";
      q.pop();
      if(p->l_child) q.push(p->l_child);
      if(p->r_child) q.push(p->r_child);
    }

  }

  //非递归实现
  //非递归先序
  void nlr2(bitree root)
  {
    if(!root) return;
    stack<bitree> s;
    bitree p = root;
    while(p||!s.empty())
    {
      if(p)
      {
        cout<<p->data<<" ";
        s.push(p);
        p = p->l_child;
      }else
      {
        p = s.top();
        s.pop();
        p = p->r_child;
      }
    }
  }
  //中序非递归
  void lnr2(bitree root)
  {
    if(!root) return;
    stack<bitree> s;//懒得写栈了，直接用容器
    bitree p = root;
    while(p||!s.empty())
    {
        if(p)
        {
            s.push(p);
            p = p->l_child;
        }
        else
        {
            p = s.top();
            cout<<p->data<<" ";
            s.pop();
            p = p->r_child;
        }
    }
  }

  //非递归后序
  void lrn2(bitree root)
  {
    if(!root) return;
    stack<node> s;
    bitree p = root;
    node tmp;
    while(p||!s.empty())
    {
      while(p)//一定是while，非递归其他也可以用while，但是这里不能用if
      {
        node btn = new Node;
        btn->btnode = p;
        btn->isfirst = true;
        s.push(btn);
        p = p->l_child;
      }
      if(!s.empty())
      {
        tmp = s.top();
        s.pop();
        if(tmp->isfirst==true)//第一次出现在栈顶
        {
          tmp->isfirst = false;
          s.push(tmp);
          p = tmp->btnode->r_child;
        }else
        {
          cout<<tmp->btnode->data<<" ";
          p = NULL;
        }
      }
    }
  }
//实现操作
void test()
{

    int a[8] = { 5, 3, 7, 2, 4, 6, 8, 9 };
    creat_tree(a,8,t);
    cout<<"前序遍历：";
    nlr(t);
    cout<<endl;
    cout<<"中序遍历：";
    lnr(t);
    cout<<endl;
    cout<<"后序遍历：";
    lrn(t);
    cout<<endl;
    cout<<"层序遍历：";
    ceng(t);
    cout<<endl;
    cout<<"非递归先序遍历：";
    nlr2(t);
    cout<<endl;
    cout<<"非递归中序遍历：";
    lnr2(t);
    cout<<endl;
    cout<<"非递归后序遍历：";
    lrn2(t);
    cout<<endl;
    
}
};

//线索二叉树类
class xian_tree
{
  public:
  threadtree x,z,h;
  void  creat_tree(int a[],int n,threadtree &root)
  {
    threadnode *c,*pa=NULL,*p;
    int i;
    root = new threadnode;
    root->data = a[0];
    root->lchild = root->rchild = NULL;
    for(i = 1;i<n;i++)
    {
        p = new threadnode;
        p->lchild = p->rchild = NULL;
        p->data = a[i];
        c = root;
        while(c)
        {
            pa = c;
            if(c->data<p->data)
            c = c->rchild;//如果根节点小于待插入节点就往右遍历
            else c = c->lchild;
        }
        if(pa->data<p->data)
        pa->rchild = p;//右放
        else pa->lchild = p;
    }
    //cout<<"中序线索化二叉树建立完成"<<endl;

  }

  //中序遍历线索化
  void inthread(threadtree &p,threadtree &pre)
  {
    if(p)
    {
      inthread(p->lchild,pre);//中序先处理左子树
      if(!p->lchild)
      {
        p->lchild = pre;//建立前驱索引
        p->ltag = 1;
      }
      if(pre&&!pre->rchild)//若前驱无右子树就让当前p为右子树,建立前驱的后继节点
      {
        pre->rchild = p;
        pre->rtag = 1;
      }
      pre = p;//更新节点
      inthread(p->rchild,pre);
    }
  }

  //建立中序线索二叉树
  void creat_inthread(threadtree t)
  {
    threadtree pre = NULL;
    if(t!=NULL)
    {
      inthread(t,pre);
      pre->rchild = NULL;//处理最后一个节点
      pre->rtag = 1;
    }
  }

  //求中序第一个节点
  threadnode *firstnode(threadnode *p)
  {
    while(!p->ltag)//中序根据左根右的顺序第一个节点是最左下一个节点
    p = p->lchild;
    return p;
  }

  //求中序最后一个节点
  threadnode *finalnode(threadnode *p)
  {
    while(!p->rtag)//中序根据左根右的顺序最后一个节点是最右下一个节点
    p = p->rchild;
    return p;
  }

  //求后继节点
  threadnode *nextnode(threadnode *p)
  {
    if(!p->rtag)
    return firstnode(p->rchild);//有右子树说明右子树中第一个节点就是后继节点
    else return p->rchild;//否则下一个节点就是线索化后指的节点
  }

  //求前驱节点
  threadnode *lastnode(threadnode *p)
  {
    if(!p->ltag)
    return finalnode(p->lchild);
    else return p->lchild;
  }

  //中序遍历
  void lnr(threadnode *t)
  {
    for(threadnode *p=firstnode(t);p!=NULL;p = nextnode(p))
    {
      cout<<p->data<<" ";
    }
    cout<<endl;
  }

  //先序线索化
  void prethread(threadtree &p,threadtree &pre)//根左右
  {
    if(p)
    {
      if(!p->lchild)//没有左子树,处理节点的前驱
      {
        p->lchild = pre;
        p->ltag = 1;
      }
      if(pre&&!pre->rchild)//pre存在并且pre右子树不存在,处理前驱节点的后继
      {
        pre->rchild = p;
        pre->rtag =1;
      }
      pre = p;
      if(p->ltag==0)//避免循环,易错点,没有左子树说明此时p->lchild指向了p的前驱，因此不能再次回到遍历p的前驱节点
        prethread(p->lchild,pre);//遍历左子树
      prethread(p->rchild,pre);//遍历右子树
    }
    //cout<<"先序线索化二叉树建立完成"<<endl;

  }

  //建立先序线索二叉树
  void creat_prethread(threadtree t)
  {
    threadtree pre = NULL;
    if(t)
    {
      prethread(t,pre);
      if(!pre->rchild)
      pre->rchild = NULL;//处理最后一个节点
      pre->rtag =1;
    }
    
  }
  //先序遍历
  void nlr(threadtree root)
  {
    for(threadnode *p = root;p!=nullptr;p = next_prenode(p))
    {
      cout<<p->data<<" ";
    }
    cout<<endl;
  }
  //下一个先序节点
  threadnode* next_prenode(threadtree p)//根左右
  {
    if(p->rtag==1) return p->rchild;//有线索就直接按线索走
    else 
    {
      if(p->lchild&&p->ltag ==0) return p->lchild;//否则按照根左右的顺序有左孩子下一个就是左孩子，不然就找右孩子
      else return p->rchild;
    }
  }

  //后序构造线索二叉树
  void postthread(threadtree root,threadtree pre)
  {
    if(root!=nullptr)
    {
      postthread(root->lchild,pre);
      postthread(root->rchild,pre);
      //建立前驱线索
      if(!root->lchild)
      {
        root->ltag = 1;
        root->lchild = pre;
      }
      //连接后继
      if(pre&&!pre->rchild)
      {
        pre->rtag =1;
        pre->rchild = root;
      }
      pre = root;
    }
  }
  void creat_postthread(threadtree root)
  {
    threadnode* pre;
    if(root)
    {
      postthread(root,pre);
      pre->rchild =nullptr;
      pre->rtag = 1;
    }
  }
  //后序遍历需要三叉链表，有点复杂了就懒得写那么细了
  //只要学会原理都可以推。

  //测试
  void test()
  {
    int a[8] = { 5, 3, 7, 2, 4, 6, 8, 9 };
    creat_tree(a,8,z);
    creat_inthread(z);
    cout<<"中序线索二叉树建立完成-------------------"<<endl;
    cout<<"遍历：";
    lnr(z);
    cout<<endl;
    creat_tree(a,8,x);
    creat_prethread(x);
    cout<<"先序线索二叉树建立完成-------------------"<<endl;
    cout<<"遍历：";
    nlr(x);
    cout<<endl;



  }
};
//课后练习
class exercises
{
  public:
  //3后序非递归在上面实现了，比起其他两个就是要注意设定一个标记为来判断左右指针访问过了
  //4,实现就是用额外空间存储，在反向输出即可，力扣上写过更难的
  void four(bitree t)
  {
    queue<bitree> q;
    stack<bitree> s;
    q.push(t);
    while(!q.empty())
    {
      bitnode *p = q.front();
      q.pop();
      s.push(p);
      if(p->l_child) q.push(p->l_child);
      if(p->r_child) q.push(p->r_child);
    }
    while(!s.empty())
    {
      cout<<s.top()<<" ";
      s.pop();
    }
  }

  //5,非递归写法用类似层次遍历,再用两个指针分别指向下一层和这层的最右或最左的子树，上层往下走等于另一个时层数就加一
  int five(bitree t)
  {
    int res =0;
    if(!t) return res;
    int front =-1, rear = -1;
    int last = 0;
    bitree q[100];//用数组模拟队列
    q[++rear] = t;
    bitree p;
    while(front<rear)//但队列不为空
    {
      p = q[++front];
      if(p->l_child) q[++rear] = p->l_child;
      if(p->r_child) q[++rear] = p->r_child;
      if(front==last)
      {
        res++;
        last = rear;//last更新
      }
    }
    return res;
  }
  //6,两个数组中分别找关系一个一个排
  bitree num6(int a[],int b[],int l1,int h1,int l2,int h2)//l1h1是先序的第一个和最后一个下标，另外两个是中序的
  {
    bitree root = new bitnode;
    root->data = a[l1];//建立根节点
    int l_len,r_len;
    int i;
    for(i =l2;b[i]!=root->data;i++);//找到中序中根节点下标
    
    l_len = i-12;//左子树长度
    r_len = h2-i;
    if(l_len)
      root->l_child =num6(a,b,l1+1,l1+l_len,l2,l2+l_len-1);
    else  root->l_child = NULL;
    if(r_len)
      root->r_child =num6(a,b,h1-r_len+1,h1,h2-r_len+1,h2);

  }
  //7用层序遍历的思想判断，插入所有的节点，遇到NULL检查后面的是否还有非空节点，有就不是
  bool num7(bitree t)
  {
    if(!t) return false;
    queue<bitree>q;
    q.push(t);
    while(!q.empty())
    {
      bitree p = q.front();
      q.pop();
      if(p)
      {
        q.push(p->l_child);
        q.push(p->r_child);
      }
      else//发现null
      {
        while(!q.empty())
        {
          if(q.front()) return false;//发现非空元素
          q.pop();//别忘了检查完后
        }
      }
      return true;
    }
  }

  //8
  //用递归的思想判断
  int num8(bitree t)
  {
    if(!t) return 0;
    else if(t->l_child&&t->r_child)
    return num8(t->l_child)+num8(t->r_child) +1;//出现双分支总数就加1
    else return num8(t->l_child)+num8(t->r_child);//返回值不会改变
  }

  //9
  //还是递归的思路
  void num9(bitree t)
  {
    if(t)
    {
      num9(t->l_child);
      num9(t->r_child);
      auto tmp = t->l_child;
      t->l_child = t->r_child;
      t->r_child = tmp;
    }
  }

  //10
  //经典递归
  int i_10 =1;//遍历序号
  int num10(bitree b,int k)
  {
    if(b==nullptr) return '-1';//设定空标记为-1
    if(i_10==k) return b->data;
    i_10++;
    int ch = num10(b->l_child,k);//往左子树找
    if(ch!=-1) return ch;
    ch = num10(b->r_child,k);//找不到就在右子树找
    return ch;
  }

  //11
  //只是删除节点的子树所以要遍历所有节点，用层序
  void num_11_1(bitree &t)//删除操作，删除二叉树要递归删除，否则只是删除了根结点的，子树上的还会存留
  {
    if(t)
    {
      num_11_1(t->l_child);
      num_11_1(t->r_child);
      delete t;
    }
  }
  void num_11_2(bitree bt,int x)
  {
    queue<bitree> q;
    if(bt)
    {
      if(bt->data ==x)//根节点就是x的情况
      {
        num_11_1(bt);
        return;
      }
    }
    q.push(bt);
    while(!q.empty())
    {
      bitree p = q.front();
      q.pop();
      if(p->l_child)//处理左子树
      {
        if(p->l_child->data==x)
        {
          num_11_1(p->l_child);
          p->l_child =NULL;
        }
      } else q.push(p->l_child);

      if(p->r_child)//处理右子树
      {
        if(p->r_child->data==x)
        {
          num_11_1(p->r_child);
          p->r_child =NULL;
        }
      } else q.push(p->r_child);
    }

  }

  //12
  //非递归后序实现，因为访问到x时，栈内节点都是x的祖先
  struct stack_12
  {
    bitree t;
    bool tag;//判断标志
  };
  void num12(bitree bt,int x)
  {
    stack_12 s[100];
    int top = 0;
    while(bt||top>0)
    {
      while(bt&&bt->data!=x)//左子树节点入栈
      {
        s[++top].t =bt;
        s[top].tag = false;
        bt = bt->l_child;
      }
      if(bt&&bt->data==x)
      {
        cout<<"找到查找结点"<<endl;
        for(int i =1;i<=top;i++)
        cout<<s[i].t->data<<" ";
        exit(1);//结束
      }
      while(top&&s[top].tag==1)//将空结点退栈
      {
        top--;
      }
      if(top)
      {
        s[top].tag =1;
        bt=s[top].t->r_child;
      }
    }
  }

  //13
  //后序非递归遍历p时保存此时的栈内所有p的祖先，再遍历q，用两个不同祖先一次对比，第一个重复元素即为最近公共祖先
  stack_12 s[100],s1[100];//和12题一样
  int top,top1;
  bitree num13(bitree root,bitnode *p,bitnode*q)
  {
    top = 0;
    bitree bt = root;
    while(bt!=NULL||top>0)
    {
      while(bt!=NULL)
      {
        s[++top].t = bt;
        s[top].tag =0;
        bt=bt->l_child;//存放左子树
      }
      while(top!=0&&s[top].tag==1)
      {
        if(s[top].t==p)
        {
          for(int i = 1;i<=top;i++)//遇到p结点时此时栈内元素都是p的祖先，保存起来
          {
            s1[i] = s[i];
            top1=top;
          }
        }
        if(s[top].t==q)
        {
          for(int i =top;i>0;i--)//就是暴力去找,嵌套循环
          {
            for(int j =top1;j>0;j--)
            {
              if(s1[j].t==s[i].t)
              return s[i].t;//找到祖先
            }
            top--;
          }
        }
        if(top!=0)
        {
          s[top].tag=1;
          bt = s[top].t->r_child;
        }
      }
      
    }
    return NULL;//无祖先
  }
  //14
  //层序遍历顺便记录结点的层号，再统计每层的宽度,这种题好像可以用bfs和dfs做
  int num14(bitree b)
  {
    queue<pair<int,bitree>> q;//int用来存储每个节点的层号，这个方式和书上结构体效果差不多
    vector<pair<int,bitree>> v;//存储答案
    int idx = 1;
    q.push({idx,b});//插入第一层
    while(!q.empty())
    {
      auto p = q.front();
      q.pop();
      v.push_back(p);
      idx = p.first;//idx更新为出队的层数，因为每一层出后下一层进来
      if(p.second->l_child)
      {
        q.push({idx+1,p.second->l_child});
      }
      if(p.second->r_child)
      {
        q.push({idx+1,p.second->r_child});
      }
      //idx++;层号++这样或许也可以
    }
    //在v中查找
    int max = 0;idx = 1;
    for(int i =0;i<v.size();i++)
    {
      int n = 0;//统计每层的宽度
      while(v[i].first==idx)
      {
        n++;i++;
      }
      idx = v[i].first;//结束上面循环后i来到了下一层，此时更新层号
      if(n>max) max = n;
    }
    return max;
  }

  //15
  //其他类型数不能由先序得到后序，满二叉树可以，用递归的思想,先找到根节点，剩下的对半，前一半为左子树，后一半为右子树
  void num15(int pre[],int l1,int h1,int post[],int l2,int h2)
  {
    int half;
    if(h1>=l1)
    {
      post[h2] = pre[11];
      half = h1-l1/2;
      num15(pre,l1+1,l1+half,post,l2,l2+half-1);
      num15(pre,l1+half+1,h1,post,l2+half,h2-1);
    }
  }

  //16
  //用中序遍历，遍历到叶节点时就插入链表即可,其他遍历方式因该也可以
  vector<bitree>n;//用vector代替链表,会有些许差异
  void num16(bitree b)
  {
    if(b)
    {
      num16(b->l_child);
      if(b->l_child==NULL&&b->r_child==NULL)
      n.push_back(b);//将叶结点按顺序插入n
      num16(b->r_child);
    }
  }
  //再按n来创建链表即可

  //17
  //经典递归
  bool num17(bitree t1,bitree t2)
  {
    bool flag1,flag2;
    if(t1==NULL&&t2==NULL)
    return true;
    else if(t1==NULL||t2==NULL)
    return false;
    else 
    {
      return num17(t1->l_child,t2->l_child)&&num17(t1->r_child,t2->r_child);//简写了
    }
  }

  //18
  //不好说，看解析
  void num18(threadtree t,threadtree p)
  {
    threadtree q;
    if(p->rtag==0)//有右子树，右子树为前驱
    q = p->rchild;
    else if(p->ltag==0)//无右但有左子树，左为前驱
    q = p->lchild;
    else if(p->lchild==NULL)
    q=NULL;//p是中序第一个结点，无后序前驱
    else//否则往上找线索
    {
      while(p->ltag==1&&p->lchild)
      {
        p = p->lchild;//往上找到有左子树的第一个p的祖宗结点，那么依据左右根的思路p的前驱就是左子树的根结点
      }
      if(p->ltag==0)
      q = p->lchild;
      else q=NULL;//仅有单支树的情况
    }
    return q;
  }
};


int main()
{
    bi_tree tree;
    tree.test();
    // xian_tree t;//不知道为什么一起两个类一起用线索二叉树会缺漏
    // t.test();

    return 0;
}

并查集

王道上写法

//并查集
int f[100];//采用双亲表示法存放数据
int h[100];//优化后根节点的绝对值是该树中结点的总树
//初始化 n个元素 
void Init(int n) {
  //使每个元素的根节点是其本身
  //即初始时每个元素都是单独的 
  for(int i=1; i<=n; i++) f[i]=i;  
}
void init_pro(int n)
{
  for(int i=1; i<=n; i++) f[i]=i,h[i]=0;  
}
//查询操作，本质就是向上查找父节点，直至查到根节点即可表示该点属于哪个树了
int Find(int i) 
{
  while(f[i] >= 0)   //直到元素的父节点<=0，表示已经查询到了树的根，这是王道上的写法
    i = f[i];
  return i; 			//返回根节点对应的元素 
}
//查找优化(路径压缩
int find_pro(int i)
{
  int root = i;
  while(f[root]>=0) root=f[root];//循环找到结点
  while(i!=root)//没有直接指向根节点就压缩,顺便将往上走的所有父节点都压缩，不断减少树的高度
  {
    int t = f[i];
    f[i] = root;
    i =t;
  }
  return root;
}

//合并,本质就是将一个树的根结点修改为另一个树的根节点，象征着合并
void Union(int a, int b) {
  //先找到两个元素对应的根对应的元素 
  int fa = Find(a); 
  int fb = Find(b);
  if(fa==fb) return;
  else f[fa]=fb;  //否则令元素 a的根指向元素 b的根 
} 
//优化思路就是小树合并到大树里，这样高度更低
void union_pro(int a, int b)
{
  int fa = Find(a);
  int fb = Find(b);
  if(fa != fb) {
    if(h[fa] < h[fb]) {
      f[fa] = fb;
    } else {
      f[fb] = fa;
      if(h[fa] == h[fb]) h[fa]++;
    }
  }
}

Acwing写法
网上主流根节点是存储数组的下标和存储的数据相等的点。王道上是根节点存储的是负数，绝对值表示树中结点数目

(1)朴素并查集：

    int p[N]; //存储每个点的祖宗节点

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);//自带了路径压缩，递归写法。借用了除根结点外其他结点下标位置上的数据都是该节点的父节点下标的特性，不断往上直至查询到相同的时候表明找到了根节点，再将原本查询元素存放的数据更改为根节点下标，实现路径压缩。
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);


(2)维护size的并查集：

    int p[N], size[N];
    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }

    // 合并a和b所在的两个集合：
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);


(3)维护到祖宗节点距离的并查集：

    int p[N], d[N];
    //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x)
        {
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        d[i] = 0;
    }

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
    d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

第五章

图

#include<iostream>
#include<queue>
#include<stack>
#include<cstring>
using namespace std;
const int max_size =100;
const int N = 100010, M = N * 2;
//邻接表构造
struct arcnode
{
    int adjvex;//顶点位置
    struct arcnode *next;//下一条弧的指针
};
typedef struct vnode
{
    int data;//顶点信息
    arcnode *first;//单条表上的头指针
}vnode,adjlist[max_size];
 struct algraph //邻接表本体
{
    adjlist vertices;
    int vexnum,arcnum;//图的顶点数和弧数
};
//创建邻接表
void create_algraph(algraph* g){
  int end, start;
  cout << "请输入结点数和边数："; 
  cin >>g->vexnum>>g->arcnum;
  cout << "请输入每个顶点保存的数据：" << endl;
  for (int i = 0; i < g->vexnum; i++) {
    cout << "vertex" << i << ":";
    cin >> g->vertices[i].data;
    g->vertices[i].first = NULL;//初始化时一定要让每个顶点的指针域为NULL，否则不会默认为NULL
  }
  cout << "请输入每条边的两个顶点在数组中的下标" << endl;
 
  for (int j = 0; j < g->arcnum; j++) {
    cout << "请输入第" << j << "条边:" << endl;
    cin >> start >> end;
        arcnode *node = new arcnode;
    node->adjvex = end;
    node->next = g->vertices[start].first;
    g->vertices[start].first = node;
  }
  
} 
//打印邻接表
void PrintLink(algraph* g ,arcnode* p) {
  while (p != NULL) {
    cout << g->vertices[p->adjvex].data<<" ";
    p = p->next;
  }
  cout << endl;
}

void output(algraph* g) {
  cout << "邻接表为:" << endl;
  for (int i = 0; i < g->vexnum; i++) {
    cout << g->vertices[i].data << " " ;
    PrintLink(g, g->vertices[i].first);
  }
}


// 
// 图的遍历
//例子使用这里的来实现的，转换之间有所差异
//创建邻接矩
// void Creat(GraAdList& G) {
//   int i, j, k;
//   EdgeNode* e = NULL;
//   EdgeNode* q = NULL;
//   cout << "请输入顶点数和边数： " << endl;
//   cin >> G.vexnum >> G.edgenum;
//   cout << "请输入顶点信息" << endl;
//   for (k = 0; k < G.vexnum; k++)
//   {
//     cin >> G.AdList[k].data;
//     G.AdList[k].first = NULL;
//   }
//   for (k = 0; k < G.edgenum; k++)
//   {
//     cout << "请输入边(vi,vj)的下标i,j： " << endl;
//     cin >> i >> j;
//     e = new EdgeNode;
//     e->adjvex = j;
//     e->next = G.AdList[i].first;
//     G.AdList[i].first = e;
//     /*q = new EdgeNode;
//     q->adjvex = i;
//     q->next = G.AdList[j].first;
//     G.AdList[j].first = q;*/
//   }
// }
// void myprint(GraAdList G){
//   cout << endl << "邻接表: " << endl;
//   EdgeNode* p;
//   for (int i = 0; i < G.vexnum; i++)
//   {
//     cout << G.AdList[i].data << ": ";
//     for (p = G.AdList[i].first; p; p = p->next)
//     {
//       cout << p->adjvex << " ";
//     }
//     cout << endl;
//   }
// }
//bfs
bool st_b_n[max_size];//辅助数组
void bfstraverse(algraph g)//和上述格式有点差异，不转换了
{
    memset(st_b_n,false, sizeof st_b_n);//数组初始化

    for(int i = 0;i<g.vexnum;i++) //防止非连通图遍历不完
        if(!st_b_n[i])
        bfs_normal(g,i);

}
void bfs_normal(algraph g,int v)//v表示从哪里开始
{
    
    int front,rear,j;// 队列指针
    int q[max_size];//队列模拟
    front = rear =-1;
    arcnode *p;
    cout<<g.vertices[v].data<<" ";
    st_b_n[v]=true;
    q[++rear] = v;//类似层序遍历，将准备查找的元素插入队列
    while(front!=rear)
    {
        v = q[++front];//取出队头元素并出队
        p = g.vertices[v].first;
        while(p)
        {
            j = p->adjvex;
            if(!st_b_n[j])//和p同链但是没被访问的元素插入队列访问再等待查找后序处理
            {
                cout<<g.vertices[j].data<<" ";
                st_b_n[j]=true;
                q[++rear] = j;
            }
            p =p->next;//往后找
        }
    } 
}

//dfs
//图构造如下
// void matrix_make(Graph &g){ //由邻接表构造邻接矩阵 
//   Arcnode *p = new Arcnode;
//   memset(g.arc_matrix,0,sizeof(g.arc_matrix));
//   for(int i = 1;i <= g.vex_sum;i++)
//   {
//     p = g.vexlist[i].firstarc;
//     while(p){
//       g.arc_matrix[i][p->adjvex] = 1;
//       p = p->nextarc;
//     }
//   }
//   for(int i = 1;i <= g.vex_sum;i++)
//   for(int j = 1;j <= g.vex_sum;j++)
//   if(g.arc_matrix[i][j] == 1)g.arc_matrix[j][i] = 1;
  
// }
bool st_d_n[max_size];

void dfs_n(algraph &g,int v)
{
    st_d_n[v] = true;
    cout<<g.vertices[v].data<<" ";
    for(int i = 0;i<g.vexnum;i++)
        if(!st_d_n[i]) dfs_n(g,i);
}
void dfstraverse(algraph &g)
{
    for(int i =0;i<g.vexnum;i++) st_d_n[i] = false;//初始化
    for(int i =0;i<g.vexnum;i++)
        if(!st_d_n[i]) dfs_n(g,i);
}


//-----------------------------------------------------------------
//以上是常规建立，算法还有一种邻接表用数组模拟

int n, m;//顶点数和表中顶点关系数目
int h[N],e[M],ne[M],idx;
//插入操作
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;//h储存的是a这条链表上的头节点，ne存储列表的索引值，e存放数据
    //插入的时候，像链表的头插法一样，e的第idx位存储数据，ne第idx位存放的是第a条链表的头节点，即h[a]，
    //然后更新这条链表上的头节点的下标值即h[a]=idx++；
}
//树的结构输出出来是这样的
// 1:->4->7->2  表示1连着4，7，2这几个结点
// 2:->5->8->1
// 3:->9->4
// 4:->6->3->1
// 5:->2
// 6:->4
// 7:->1
// 8:->2
// 9:->3

void create_e_alg()
{
    idx = 0;
    memset(h, -1, sizeof h);
    
  cout << "请输入图的两点间关系总数："; 
    cin>>n;
    cout<<"输入格式:两个整数,代表在顶点x中插入的数y";
    for(int i =0;i<n;i++)
    {
        int a,b;
        
        cin>>a>>b;
        add(a,b);
    }
    
}
void print_e()
{
    for(int i=0;i<=n;i++)  
        {
            cout<<i<<":";
            for(int j=h[i];j!=-1;j=ne[j])
            {
                cout<<"->"<<e[j]; 
            }
            cout<<endl;
        }
}

//Acwing上理所当然的也有相应练习模板
bool st[max_size];
int dfs(int u)
{
    st[u] = true; // st[u] 表示点u已经被遍历过

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}

void bfs()
{
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

while (q.size())
{
    int t = q.front();
    q.pop();

    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}
}

//练习题
class exercises
{
    public:
    //6.3.5练习题
    //第一题就是判断边数是否为顶点数-1个，或者判断是不是无回路的连通图即可

    //2
    //使用栈来存储
    void num2(algraph&g,int v)
    {
        int w;
        stack<int> s;
        bool st[max_size];//标记数组
        for(int i =0;i<g.vexnum;i++)
        {
            st[i] = false;
        }

        s.push(v);
        st[v] = true;
        while(!s.empty())
        {
            int k =s.top();
            s.pop();//取栈顶元素
            cout<<g.vertices[k].data<<" ";
            for(auto p = g.vertices[k].first;p->adjvex>=0;p = p->next )//和书上不大一样，类似使用迭代器迭代
            {
                w = p->adjvex;
                if(!st[w])
                {
                    s.push(w);
                    st[w] =true;
                }
                
            }
        }
            
    }

    //4
    //思路就是用广度和深度搜索即可
    bool st_4[max_size];
    void num4_dfs(algraph g,int i,int j,bool &can_reach)
    {
        if(i==j)
        {
            can_reach = true;
            return;
        }
        st_4[i] = true;
        for(auto p = g.vertices[i].first;p->adjvex>=0;p = p->next )
        {
            int w = p->adjvex;
            if(!st_4[2]&&!can_reach)
            num4_dfs(g,w,j,can_reach);
        }
    
    }

    bool num4_bfs(algraph g,int i,int j)
    {
        queue<int> q;
        q.push(i);
        while(!q.empty())
        {
            int u = q.front();
            q.pop();
            st_4[u] = true;
            if(u==j) return true;
            for(auto p = g.vertices[u].first;p->adjvex>=0;p = p->next )
            {
                int w = p->adjvex;
                if(w==j)
                return true;
                if(!st_4[w])
                {
                    q.push(w);
                    st_4[w] = true;
                }
            }
    
        }
        return false;//未找到
    }

    //5
    //经典深度优先搜索,注意要回溯
    bool st_5[max_size];
    void num5(algraph *g,int u,int v,int path[],int d)
    {
        int w;
        arcnode *p;
        d++; //路径长度+1
        path[d] = u;
        st_5[u] = true;
        if(u==v)
        {
            cout<<path<<endl;
        }
        p = g->vertices[u].first;
        while(p)
        {
            w = p->adjvex;
            if(st_5[w]==0)
                num5(g,w,v,path,d);
            p = p->next;
        }
        st_5[u] =0;//回溯
    }

};

int main()
{
    algraph* g = new algraph;
    create_algraph(g);
    output(g);
    
    delete g;//释放结点
    
    // create_e_alg();
    // //打印数据
    // print_e();
    
    return 0;
}

prim找最小生成树

acwing写法

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 510, INF = 0x3f3f3f3f;

int n,m,g[N][N];
bool st[N];
int dist[N];

int prim()
{
    memset(dist, 0x3f, sizeof dist);

    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        if (i && dist[t] == INF) return INF;

        if (i) res += dist[t];
        st[t] = true;

        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
    }

    return res;

}

int main()
{
    
    cin>>n>>m;
    memset(g, 0x3f, sizeof g);
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b] = g[b][a] = min(g[a][b],c);
    }
    int t = prim();
    if(t ==INF) cout<<"impossible";
    else cout<<t;
    
    return 0;
}

Kruskal算法求最小生成树

acwing写法

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100010;
int p[N];//保存并查集
int n,m;
struct e{
    int a;
    int b;
    int w;
    bool operator < (const e& rhs){//通过边长进行排序
        return this->w < rhs.w;
    }

}edg[N * 2];
int res = 0;

int cnt = 0;

int find(int a)
{
    if(p[a]!=a) p[a] = find(p[a]);//并查集找根结点+压缩操作
    return p[a];
}
void klskr()
{
    for(int i =1;i<=m;i++)//每条边都找
    {
        int pa = find(edg[i].a);//a所在的集合
        int pb = find(edg[i].b);
        if(pa!=pb)
        {
            res+=edg[i].w;
            p[pa] = pb;//合并a,b
            cnt++;
        }
        
    }
}
int main()
{
    cin>>n>>m;
    for(int i =1;i<=n;i++) p[i] =i;//初始化并查集
    for(int i =1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        edg[i] = {a,b,c,};
    }
    sort(edg+1,edg+m+1);//按边长排序
    klskr();
    if(cnt<n-1)
    cout<<"impossible";
    else cout<<res;
    return 0;
    
}

Dijkstra求最短路

#include<iostream>
//#include<bits/stdc++.h>//万能头文件
#include<vector>
#include<algorithm>
#include<string>
#include<unordered_map>
#include<stack>
#include<cstring>
#include<queue>
#include<map>
using namespace std;

const int N =510;
int n,m;
int g[N][N];//存放图
int dist[N];//保存源点到其余各个节点的距离
bool st[N];
int dijstra()
{
   memset(dist,0x3f,sizeof dist);
   dist[1]=0;
   for(int i =0;i<n-1;i++)
   {
       int t = -1;
       for(int j =1;j<=n;j++)
       {
           if(!st[j]&&(t==-1||dist[t]>dist[j]))
           t = j;
       }
       
       for(int j = 1;j<=n;j++)
        dist[j] = min(dist[j],dist[t]+g[t][j]);
        
    st[t] =true;
   }
   
   if(dist[n]==0x3f3f3f3f) return -1;
   else return dist[n];
   
}
int main()
{
    cin>>n>>m;
    memset(g, 0x3f, sizeof g);//初始化
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b] = min(g[a][b],c);//迪杰斯特拉算法不能有负权边，所以最小是0
    }
    cout<<dijstra()<<endl;
    return 0;

}

Floyd求最短路

#include<iostream>
using namespace std;

const int N = 210, INF = 1e9;

int n,m,k;
int d[N][N];
void floyd()
{
    for(int k =1;k<=n;k++)
       for(int i =1;i<=n;i++)
         for(int j=1;j<=n;j++)
            d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
}
int main()
{
    cin>>n>>m>>k;
    for(int i =1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i==j) d[i][j] =0;
            else d[i][j] = INF;
    while(m--)
    {
        int x,y,z;
        cin>>x>>y>>z;
        d[x][y] = min(d[x][y], z);
    }
    floyd();
    while(k--)
    {
        int a,b;
        cin>>a>>b;
        int t = d[a][b];
        if(t>INF/2) cout<<"impossible"<<endl;
        else cout<<t<<endl;
    }
    return 0;
}

第六章

查找

顺序查询

void print_arry(vector<int> a)
{
    cout<<"当前数组输出:";
    for(int i :a)
    cout<<i<<" ";
    cout<<endl;
}

//顺序查找
void normal_find(int x,vector<int> a)
{
    cout<<"使用顺序查找"<<x<<" ";
    int cnt = 1;
    for(int i:a)
    {
        if(i==x)
        {
            //cnt++;
            cout<<"找到了在第"<<cnt<<"位"<<endl;
            return;
        }
        cnt++;
    }
    cout<<"无可奉告";
}

二分查找

//二分查找
void erfen_find(int x,vector<int> a)
{   
    vector<int> b = a;
    sort(b.begin(),b.end());
    print_arry(b);
    cout<<"使用二分查找"<<x<<" ";
    int l =0,r = b.size()-1;
    int mid =(l+r)/2;
    while(l<=r)
    {
        
        if(b[mid]<x)
        {
            l = mid+1;
        }else if(b[mid]>x)
        {
            r = mid-1;
        }else
        {
            cout<<"找到了在第"<<mid+1<<"位"<<endl;
            return;
        }
        mid =(l+r)/2;
    }
    cout<<"无可奉告";
}

二叉排序树

//二叉排序树构造
typedef struct {
  int key;//关键子项
  int otherinfo;//其他数据域
}elemtype;
typedef struct bstnode {
  elemtype data;//每个结点的数据域包括关键字项和其他数据项
  struct bstnode* lchild, * rchild;//左右孩子指针
}bstode,*bstree;
//二叉排序树递归查找
bstree searchbst(bstree t,int key)
{
    if(!t||key==t->data.key) return t;//查找结束 
    else if(key<t->data.key) return searchbst(t->lchild,key);//往左子树查找
    else return searchbst(t->rchild,key);
}
//二叉排序树插入
void insert_bst(bstree &t,elemtype e)
{
    if(!t)//如果依据到了叶节点就直接连接上
    {
        bstnode* s =new bstnode;
        s->data = e;
        s->lchild = s->rchild = NULL;
        t = s;
    }
    else if(e.key<t->data.key)//插入小于当前值就往左子树递归
        insert_bst(t->lchild,e);
    else if(e.key>t->data.key)//否则就往右子树递归
        insert_bst(t->rchild,e);
}

//排序二叉树的创建
void create_bst(bstree &t)
{
    t =NULL;
    elemtype e;
    cin>>e.key;
    while(e.key!= -1)//-1是停止标记
    {
        insert_bst(t,e);
        cin>>e.key;
    }
    insert_bst(t,e);//最后一步不可遗忘
}

//二叉排序树的删除
void delete_bst(bstree &t,int key)
{
    //从二叉排序树T中删除关键字等于key的结点
  bstnode* p = new bstnode;
  bstnode* f = new bstnode;
    p =t;f = NULL;//初始化

    while(p)
    {
        if(p->data.key == key) break;
        f = p;//f为p的双亲结点
        if(p->data.key>key) p = p->lchild;//当前结点比查找值小就往左子树找
        else p =p->rchild;//否则往右找
    }
    if(!p) return;

    bstnode* q = new bstnode;

    q = p;
    if(p->lchild&&p->rchild)//存在左右子树的情况
    {
        bstnode *s = new bstnode;
        s = p->lchild;
        while(s->rchild)
        {
            q = s;
            s = s->rchild;//找到最右下的结点，即直接前驱
        }
        p->data = s->data;//s指向被删结点前驱
        if(q!=p) q->rchild = s->lchild;//重接q的右子树
        else q->lchild = s->lchild;//重接左子树
        delete s;
        return ;
    } 
    else if(!p->rchild) //若只有左子树，只需重接左子树即可
        p = p->lchild;
    else if(!p->lchild)
        p = p->rchild;
    /*---------将p所指的子树挂接到其双亲结点*f相应的位置---------*/
    if(!f) t = p;
    else if(q==f->lchild) f->lchild = p;
    else f->rchild = p;
    delete q;
}

/*------------二叉树的中序遍历------------*/
void inorder_bst(bstree T) {
  if (T)
  {
    inorder_bst(T->lchild);
    cout << T->data.key << " ";
    inorder_bst(T->rchild);
  }
}
//测试案例，53 17 78 9 45 70 94 23 60 88 75 -1
void bst_test(bstree &t)
{
    create_bst(t);
    inorder_bst(t);
    cout<<endl;
    cout << "请输入您要查询的元素：" << endl;
  int k = 0;
  cin >> k;
  bstree T1 = NULL;//定义T1用来接收查找结果
  T1 = searchbst(t, k);
  if (T1) cout << "存在此元素！" << endl;
  else cout << "不存在此元素！" << endl;
  int key = 0;
  cout << "请输入您要删除的元素：" << endl;
  cin >> key;
  delete_bst(t, key);//删除元素
  inorder_bst(t);//再次中序遍历二叉树
}

二叉平衡树

内容有点多，直接抄大佬的了，实现逻辑可以参考另一位大佬的解释及其旋转_快乐江湖的博客-CSDN博客](https://blog.csdn.net/qq_39183034/article/details/121445755))

/*
二叉平衡搜索树(AVL):对于二叉搜索树的所有结点，其左右节点的高度之差不超过 1 
*/ 
#include<iostream>
#include<queue>
using namespace std;
typedef int KeyType;
typedef int ElemType;
typedef struct BSTNode{
  KeyType key;
  int height;
  ElemType data;
  BSTNode *left,*right;
  BSTNode()=default;
  BSTNode(KeyType k):key(k),height(1),data(0),left(NULL),right(NULL){}
}BSTree;

int GetHeight(BSTree *rt){  //得到高度 
  if(rt==NULL)	return 0;
  return rt->height;
}

void UpdateHeight(BSTree *rt){  //更新高度 
  if(rt==NULL)	return;
  rt->height=max(GetHeight(rt->left),GetHeight(rt->right))+1;
}

//左左调整(bf=2)，右旋，左子节点变成父节点，其多余的右子节点变成降级节点的左子节点 
void UpdateLL(BSTree *&rt){
  BSTree *pl=rt->left;
  rt->left=pl->right;
  pl->right=rt;
  rt=pl;
  UpdateHeight(rt->left);
  UpdateHeight(rt->right);
  UpdateHeight(rt);
}

//右右调整(bf=-2),左旋，右子节点变成父节点，其多余的左子节点变成降级节点的右子节点 
void UpdateRR(BSTree *&rt){
  BSTree *pr=rt->right;
  rt->right=pr->left;
  pr->left=rt;
  rt=pr;
  UpdateHeight(rt->left);
  UpdateHeight(rt->right);
  UpdateHeight(rt);
}

//左右调整(bf=2),先对左子节点左旋调整为左左型，再进行左左调整 
void UpdateLR(BSTree *&rt){
  UpdateRR(rt->left);
  UpdateHeight(rt->left->left);
  UpdateHeight(rt->left->right);
  UpdateHeight(rt->left);
  
  UpdateLL(rt);
  UpdateHeight(rt->left);
  UpdateHeight(rt->right);
  UpdateHeight(rt);
}

//右左调整(bf=-2),先对右子节点右旋调整为右右型，再进行右右调整 
void UpdateRL(BSTree *&rt){
  UpdateLL(rt->right);
  UpdateHeight(rt->right->left);
  UpdateHeight(rt->right->right);
  UpdateHeight(rt->right);
  
  UpdateRR(rt);
  UpdateHeight(rt->left);
  UpdateHeight(rt->right);
  UpdateHeight(rt);
}

BSTree* SearchBST(BSTree *rt, KeyType k){    //查找
  if(rt==NULL||k==rt->key)	return rt;
  if(k<rt->key)	return SearchBST(rt->left,k);
  else	return SearchBST(rt->right,k);
}

/*
插入节点操作，先插入节点，再对其影响的祖先节点进行平衡调整，同时更新其节点高度。 
节点A的平衡调整可分为四种情况：
一、LL型：在A节点的左孩子的左子树上插入节点，导致A节点的平衡因子变为2。
可对其进行右旋，将A的左孩子代替A成为根节点，而原A的左孩子的右子树成为A的左子树。 
二、RR型：与LL型相反，是在A节点的右孩子的右子树上插入节点，导致A节点的平衡因子变为-2。
可对其进行左旋，将A的右孩子代替A成为根节点，而原A的右孩子的左子树成为A的右子树。
三、LR型：在A节点的左孩子的右子树上插入节点，导致A节点的平衡因子变为2。
可先对A的左孩子进行左旋操作（RR型），再对A节点进行右旋操作（LL型）。
四、RL型：在A节点的右孩子的左子树上插入节点，导致A节点的平衡因子变为-2。
可先对A的左孩子进行右旋操作（LL型），再对A节点进行左旋操作（RR型）。 
*/
bool InsertBST(BSTree *&rt, KeyType k){    //插入 
  if(rt==NULL){
    rt=new BSTNode(k);
    return true;
  }
  if(k==rt->key)	return false;
  bool res=true;
  if(k<rt->key){
    res=InsertBST(rt->left,k);
    if(res&&GetHeight(rt->left)-GetHeight(rt->right)>1){
      if(k<rt->left->key)	UpdateLL(rt);	//左左
      else	UpdateLR(rt);				//左右 
    }
  }else{
    res=InsertBST(rt->right,k);
    if(res&&GetHeight(rt->left)-GetHeight(rt->right)<-1){
      if(k>rt->right->key)	UpdateRR(rt);	//右右 
      else	UpdateRL(rt);					//右左 
    }
  }
  if(res) UpdateHeight(rt);
  return res;
}

void DeleteBST_(BSTree *&rt, BSTree *pt){    //删除节点有左右子树时处理 
  if(rt->right==NULL){
    BSTree *p=rt;
    pt->key=rt->key;
    rt=rt->left;
    delete p;
  }else{
    DeleteBST_(rt->right,pt);
    if(GetHeight(rt->left)-GetHeight(rt->right)>1){
      UpdateLL(rt);					//左左 
    }
  }
  UpdateHeight(rt);
}

/*
删除节点操作。可先删除节点，再对其影响的祖先节点进行平衡调整，同时更新其节点的高度。 
同二叉排序树相同，删除节点分三种情况
一：被删除节点没有孩子节点，则直接删除即可
二：被删除节点只有一个孩子节点，则将其孩子节点代替删除节点的位置，随后删除节点即可
三：被删除节点有左右孩子，则可移花接木，即取左子树的最大值（也可取右子树的最小值）存放在被删除节点中，随后删除左子树的最大值的节点即可 
对于情况一，可同情况二处理
而对于平衡调整，需先更新其节点的高度，对于情况三处理时也需更新其节点高度，
再对其左右子树高度判断其为哪种平衡调整，调整时同时更新其节点高度 
*/
bool DeleteBST(BSTree *&rt, KeyType k){    //删除
  if(rt==NULL)	return false;
  bool res=true;
  if(rt->key==k){
    if(rt->left==NULL){
      rt=rt->right;
    }else if(rt->right==NULL){
      rt=rt->left;
    }else{
      DeleteBST_(rt->left,rt);
    }
  }else if(k<rt->key){
    res=DeleteBST(rt->left,k);
    if(res&&GetHeight(rt->left)-GetHeight(rt->right)>1){
      if(k<rt->left->key)	UpdateLL(rt);	//左左
      else	UpdateLR(rt);				//左右
    }else if(res&&GetHeight(rt->left)-GetHeight(rt->right)<-1){
      if(k>rt->right->key)	UpdateRR(rt);	//右右 
      else	UpdateRL(rt);					//右左 
    }
  }else{
    res=DeleteBST(rt->right,k);
    if(res&&GetHeight(rt->left)-GetHeight(rt->right)>1){
      if(k<rt->left->key)	UpdateLL(rt);	//左左
      else	UpdateLR(rt);				//左右 
    }else if(res&&GetHeight(rt->left)-GetHeight(rt->right)<-1){
      if(k>rt->right->key)	UpdateRR(rt);	//右右 
      else	UpdateRL(rt);					//右左 
    }
  }
  if(res)	UpdateHeight(rt);
  return res;
}

void InorderTraversal(BSTree *rt){  //中序遍历 
  if(rt==NULL)	return;
  InorderTraversal(rt->left);
  cout<<rt->key<<" ";
  InorderTraversal(rt->right);
}

bool Judge(BSTree *rt){    //判断是否为AVL
  if(rt==NULL)	return true;
  if(Judge(rt->left)&&Judge(rt->right)&&abs(GetHeight(rt->left)-GetHeight(rt->right))<=1)	return true;
  return false;
}

void LevelOrder(BSTree* root) {  //层序遍历 
    if(root==NULL)  return;
    queue<BSTree*> que;
    que.push(root);
    int n;
    BSTree *rt;
    cout<<"层序遍历：当前节点 (高度) = 左节点 右节点"<<endl; 
    while(!que.empty()){
      n=que.size();
      while(n--){
        rt=que.front();	que.pop();
          cout<<rt->key<<" ("<<rt->height<<")\t=\t";
          if(rt->left)	cout<<rt->left->key<<"\t";
          else cout<<"#\t";
          if(rt->right)	cout<<rt->right->key<<"\t";
          else cout<<"#\t";
          cout<<endl;
          if(rt->left)	que.push(rt->left);
          if(rt->right)	que.push(rt->right);
        }
  }
}

int main()
{
  int n=10;
  int a[100]={4,2,6,9,7,1,5,8,10,3};
  cout<<"插入顺序："; 
  for(int i=0;i<n;++i)
    cout<<a[i]<<" ";
  cout<<endl; 
  BSTree *rt=NULL;
  for(int i=0;i<n;++i)
    InsertBST(rt,a[i]);
  cout<<"中序遍历：";
  InorderTraversal(rt);
  cout<<endl;
  cout<<"#############################"<<endl;
  LevelOrder(rt);
  cout<<"#############################"<<endl;
  for(int i=0;i<n;++i)
  {
    DeleteBST(rt,a[i]);
    cout<<"删除 "<<a[i]<<": ";
    InorderTraversal(rt);
    cout<<endl;
  }
  
  return 0;
}

练习题目

//练习题目
class exersises
{
    public:
    //7.3
    //6
    //中序遍历看结果
    int predt = -32767;
    int num6(bstree bt)
    {
        int b1,b2;
        if(bt==NULL)
        return 1;
        else
        {
            b1 = num6(bt->lchild);
            if(b1==0||bt->data.key<=predt)
            return 0;//出现不符合中序顺序的说明不是二叉排序树
            predt = bt->data.key;
            b2 = num6(bt->rchild);
            return b2;
        }
    }

    //7
    //二叉排序树查找一次就下降一层，查找次数即为层数
    int num7(bstree bt,bstnode *p)
    {
        int cnt = 0;
        bstree t = bt;
        if(bt)
        {
            cnt++;
            while(t->data.key!=p->data.key)
            {
                if(p->data.key<t->data.key)
                t = t->lchild;
                else t = t->rchild;
                cnt++;
            }
        }
        return cnt;
    }
    
    //8
    //递归后序遍历从叶节点开始一层一层往上反
    void num8(bstree bt,int &balance,int &h)
    {
        int b1 =0,br =0,h1= 0,hr =0;//h1 ==hl,打错了
        if(bt==NULL)
        {
            h = 0,balance = 1;
        }else if(bt->lchild==NULL&&bt->rchild==NULL)//只有根节点返回1
        {
            h = 1;balance = 1;
        }else
        {
            num8(bt->lchild,b1,h1);
            num8(bt->rchild,b1,hr);
            h = (h1>hr?h1:hr)+1;
            if(abs(h1-hr)<2)
            balance =b1&&br;
            else balance = 0;
        }

    }

    //9
    //最小值在最左下，最大值在最右下
    elemtype num9(bstnode *bt,int flag)
    {
        //flag==1 找最小，否则找最大
        if(flag)
        {
        while(bt->lchild)
        bt = bt->lchild;
        return bt->data;
        }else
        {
        while(bt->rchild)
        bt = bt->rchild;
        return bt->data;
        }
    }

    //10
    //根据左<中<右的特性，先遍历右然后根然后左
    void num10(bstnode *bt,elemtype k)
    {
        if(!bt)
        return ;
        if(bt->rchild)
            num10(bt->rchild,k);
        if(bt->data.key>=k.key)
            cout<<bt->data.key<<" ";
        if(bt->lchild)
            num10(bt->lchild,k);

    }

    //11结构不一样就不写了，看书即可，

};

哈希表

Acwing上开放寻址法和拉链法都有讲解过

开放寻址法

#include<iostream>
//#include<bits/stdc++.h>//万能头文件
#include<vector>
#include<algorithm>
#include<string>
#include<unordered_map>
#include<stack>
#include<cstring>


using namespace std;
//开放寻址法N一般为数据范围的两到三倍，flag是不在范围内的数据用于判断位置是否为空
const int N = 200003,flag = 0x3f3f3f3f;
int h[N];
 // 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
int find(int x)
{   
    int k = (x%N+N)%N;
    while(h[k]!=flag&&h[k]!=x)
    {
        k++;
        if(k==N)
        k = 0;
    }
    return k;
    
}
int main()
{
    int n,x;
    cin>>n;
    memset(h,0x3f,sizeof h);//相当于初始化数组所有位为-1
    while(n--)
    {
        string op;
        cin>>op>>x;
        int k = find(x);
        if(op=="I")
        {
            h[k] = x;
        }else
        {
            if(h[k]!=flag)
            cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
}
  

   

拉连法

/*
 * Project: 11_哈希表
 * File Created:Sunday, January 17th 2021, 2:11:23 pm
 * Author: Bug-Free
 * Problem:AcWing 840. 模拟散列表 拉链法
 */
#include <cstring>
#include <iostream>

using namespace std;

const int N = 1e5 + 3;  // 取大于1e5的第一个质数，取质数冲突的概率最小 可以百度

//* 开一个槽 h
int h[N], e[N], ne[N], idx;  //邻接表

void insert(int x) {
    // c++中如果是负数 那他取模也是负的 所以 加N 再 %N 就一定是一个正数
    int k = (x % N + N) % N;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx++;
}

bool find(int x) {
    //用上面同样的 Hash函数 讲x映射到 从 0-1e5 之间的数
    int k = (x % N + N) % N;
    for (int i = h[k]; i != -1; i = ne[i]) {
        if (e[i] == x) {
            return true;
        }
    }
    return false;
}

int n;

int main() {
    cin >> n;

    memset(h, -1, sizeof h);  //将槽先清空 空指针一般用 -1 来表示

    while (n--) {
        string op;
        int x;
        cin >> op >> x;
        if (op == "I") {
            insert(x);
        } else {
            if (find(x)) {
                puts("Yes");
            } else {
                puts("No");
            }
        }
    }
    return 0;
}

排序

插入排序

1. 从第一个元素开始，该元素可以认为已经被排序；
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
   重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
4. 将新元素插入到该位置；
   重复步骤 2~5。

//插入排序
void insert_sort(vector<int> a)
{
    cout<<"插入排序"<<endl;
    print(a);
    int len = a.size();
    int idx,ret;
    for(int i = 1;i<len;i++)//从第二个元素开始选
    {
        idx = i-1;
        ret = a[i];//处理的元素
        while(idx>=0&&a[idx]>ret)
        {
            a[idx+1] = a[idx];//如果处理的元素应该排在索引前面时，让当前索引指针往后移腾出空位
            idx--;
        }
        a[idx+1] = ret;
    }
    cout<<"排序后:";
    print(a);
}
//插入二分排序
void BinaryInsertSort(vector<int>a) {
    cout<<"插入二分排序"<<endl;
    print(a);
    int len = a.size();
    int i;
    for( i=0; i<len; i++) {
        int low=0;
        int high=i-1;
        int temp=a[i];
        int mid=0;
        while(low<=high) {
            mid=(low+high)/2;
            if(a[mid]<temp) {
                low=mid+1;
            } else {
                high=mid-1;
            }
        }
        int j;
        for(j=i-1; j>=low; j--) {
            a[j+1]=a[j];
        }
        if(i!=low)
            a[low]=temp;
    }
    cout<<"排序后:";
    print(a);
}

希尔排序

类似插入排序，先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

//希尔排序
void shell_sort(vector<int>a)
{
    cout<<"希尔排序"<<endl;
    print(a);
    int len = a.size();
    int i,j,gap;//gap为步长
    for(gap = len/2;gap>0;gap/=2)//每次范围缩小一半
    {
        for(i = 0;i<gap;i++)
        {
            for(int j =i+gap;j<len;j+=gap)//本质上和插排差不多，只是排序范围上发生了变化，希尔是跳着选则排序对象的
            {
                if(a[j]<a[j-gap])//当前值比上一个对象小
                {
                    int tmp=a[j];//存储当前处理对象
                    int k = j-gap;//准备动手将大于处理对象的数往后移动
                    while(k>=0&&a[k]>tmp)
                    {
                        a[k+gap] = a[k];
                        k-=gap;
                    }
                    a[k+gap] = tmp;
                }
            }
        }
    }
    cout<<"排序后:";
    print(a);
}

冒泡排序

像吐泡泡一样，从第一个开始和后一个两两比较交换，让符合条件的逐渐移动到查找范围的末端，在缩小一格查找范围，直至无交换说明完成了排序。

//冒泡排序
void bubble_sort(vector<int> a)
{
    cout<<"冒泡排序"<<endl;
    print(a);
    int len = a.size();
    for(int i =0;i<len-1;i++)
    {
        int idx = a[i];
        bool flag =false;//若直至当前循环结束都没交换过说明已经有序，可提前结束
        for(int j =len-1;j>i;j--)//从后往前开始换
        {
            if(a[j-1]>a[j])
            {
                swap(a[j-1],a[j]);
                flag = true;
            }           
        }
        if(!flag)
        break;
    }
    cout<<"排序后:";
    print(a);
}

快速排序

找一个基准值，让比基准值大的都在右边，比基准值小的在基准值左边。在分别对基准值左右区间重复此操作。

//快速排序
//划分函数
int partition(vector<int>& a,int l,int r)
{
    int pivot = a[l];//基准值
    while(l<r)
    {
        while(l<r&&a[r]>=pivot) r--;//找到比基准小的值放在左边
        a[l] = a[r];
        while(l<r&&a[l]<=pivot) l++;
        a[r] = a[l];
    }
    a[l] = pivot;//基准值放到正确位置
    return l;//返回基准的最终位置
}
void quick_sort(vector<int>& a,int l,int r)
{
    if(l<r)
    {
        int pivotpos = partition(a,l,r);
        quick_sort(a,l,pivotpos-1);
        quick_sort(a,pivotpos+1,r);
    }
    print(a);
}

选择排序

遍历找到最小或最大值，和最终位置交换后范围减一。

//选择排序
void select_sort(vector<int> a)
{
    cout<<"选择排序"<<endl;
    print(a);
    for(int i =0;i<a.size();i++)
    {
        int min_idx = i;//记录最小元素位置
        for(int j =i+1;j<a.size();j++)
        {
            if(a[j]<a[min_idx]) min_idx = j;//更新
        }
        if(min_idx!=i) swap(a[i],a[min_idx]);//当前i所指元素不是最小值就交换
    }
    print(a);
}

堆排序

构造大根堆或小根堆实现排序

/堆排序
//从小到大排序，构建大根堆
void down(vector<int>& a,int i,int n)
{
    int parent =i;//获取父节点
    // for(int child= 2*i;i<=n;i*=2)
    // {
    //     if(i<n&&a[i]<a[i+1])
    //     i++;
    //     if(a[0]>=a[i])
    //     break;
    //     else
    //     {
    //      a[parent] =a[i];
    //      parent =i;   
    //     }
    // }
    // a[parent] = a[0];//被筛选接待你插入最终位置
    int child = 2*i+1;
    while(child<n)
    {
        if(child+1<n&&a[child]<a[child+1])
        child++;//比较左右大小，若左小于右，则较大值为右即child+1

        if(a[parent]<a[child])//将最大值放到父节点上
        {
            swap(a[parent],a[child]);
            parent = child;
        }
        child = child*2+1;//下坠换行
    }
}
//构建大根堆
void build_heap(vector<int>&a)
{
    for(int i =a.size()/2;i>=0;i--)
        down(a,i,a.size());
}
//堆排序实现
void heap_sort(vector<int>a)
{
    cout<<"堆排序"<<endl;
    print(a);
    build_heap(a);
    for(int i = a.size()-1;i>0;i--)
    {
        swap(a[0],a[i]);//最大位置取出来放到最后
        down(a,0,i);
    }
    print(a);
}

归并排序

它的基本思想是把待排序的元素分解成两个规模大致相等的子序列。如果不易分解，将得到的子序列继续分解，直到子序列中包含的元素个数为1。因为单个元素的序列本身就是有序的，此时便可以进行合并，从而得到一个完整的有序序列。

//归并排序
void merge(vector<int>& arr, int left, int mid, int right) {
    int i = left, j = mid + 1, k = 0;
    vector<int> temp(right - left + 1);//辅助数组

    while (i <= mid && j <= right) {//比较两个区域，把较小值插入辅助数组，另一个不动
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];//插入后往后移动
        } else {
            temp[k++] = arr[j++];
        }
    }

    while (i <= mid) {
        temp[k++] = arr[i++];
    }

    while (j <= right) {
        temp[k++] = arr[j++];
    }

    for (i = left, k = 0; i <= right; ++i, ++k) {
        arr[i] = temp[k];
    }
}

void mergeSort(vector<int>& arr, int left, int right) {
    if (left >= right) {
        return;
    }

    int mid = (left + right) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

//归并测试
void merge_test(vector<int> a)
{
    cout<<"归并排序"<<endl;
    print(a);
    int l =0,r = a.size()-1;
    mergeSort(a,l,r);
    print(a);

}

练习题

//练习题
class exercises
{
    public:
    //8.3.3
    //1
    //两边对称冒泡
    void num1(vector<int>a,int n)
    {
        int l =0,r = n-1;
        bool flag =true;
        while(l<r)
        {
            flag= false;
            for(int i=l;i<r;i++)
            {
                if(a[i]>a[i+1])
                {
                    swap(a[i],a[i+1]);
                    flag = true;
                }
            }
            r--;
            for(int i =r;i>l;i--)
            {
                if(a[i]<a[i-1])
                {
                    swap(a[i],a[i-1]);
                    flag = true;
                }

            }
            l++;
        }
    }

    //num2
    //快排的思想，找到一个偶数后和后一个数即奇数交换
    void num2(vector<int> a,int n)
    {
        int i =0,j=n-1;
        while(i<j)
        {
            while(i<j&&a[i]%2!=0)
            i++;
            while(i<j&&a[j]%2!=1) j--;//向后找到一个奇数元素
            if(i<j)
                swap(a[i],a[j]);
            i++,j--;
        }
    }

    //4
    //多加了步随机
    int num4(vector<int> a,int l,int r)
    {
        int rand_idx = l+rand()%(r-l+1);
        swap(a[rand_idx],a[l]);
        int pivot = a[l];
        int i =l;
        for(int j =l+1;j<=r;j++)
        {
            if(a[j]<pivot)
            swap(a[++i],a[j]);

        }
        swap(a[i],a[l]);//将基准元素插入最终位置
        return i;
    }

    //5
    //看解析更清楚
    int num5(vector<int> a,int l,int r,int k)
    {
        int pivot = a[l];
        int l_temp=l;
        int r_temp = r;
        while(l<r)
        {
            while(l<r&&a[r]>=pivot)
                --r;
            a[l] =a[r];
            while(l<r&&a[l]<=pivot)
                ++l;
            a[r] = a[l];
        }
        a[l] =pivot;

        //算法精髓
        if(l==k)
        return a[l];
        else if(l>k)
        return num5(a,l_temp,l-1,k);
        else
        return num5(a,l+1,r_temp,k);
    }

    //6
    typedef enum{red,white,blue} color;//枚举数组
    void num6(color a[],int n)
    {
        int i =0,j = 0,k=n-1;
        while(j<=k)
        switch(a[j])
        {
            case red :swap(a[i],a[j]);i++;j++;break;//红色和i交换
            case white: j++;break;
            case blue: swap(a[j],a[k]);k--;//蓝色和k交换
        }
    }
    

    //8.4
    //4
    //链表省略

    //5
    //遍历
    bool num4_5(vector<int> a,int len)
    {
        if(len%2==0)//len为偶数，有一个单分支节点
        {
            if(a[len/2]>a[len])
            return false;
            for(int i = len/2-1;i>=1;i--)
                if(a[i]>a[i*2]||a[i]>a[2*i]+1)
                return false;
        }
        else
        {
            for(int i =len/2;i>=1;i--)
                if(a[i]>a[i*2]||a[i]>a[i*2+1])
                return false;
        }
        return true;
    }



};

代码总览

#include<iostream>
#include<vector>
using namespace std;

const int max_size = 100;
//打印数组
void print(vector<int>a)
{
    cout<<"当前数组为：";
    for(int i :a)
    {
        cout<<i<<" ";
    }
    cout<<endl;
}

//插入排序
void insert_sort(vector<int> a)
{
    cout<<"插入排序"<<endl;
    print(a);
    int len = a.size();
    int idx,ret;
    for(int i = 1;i<len;i++)//从第二个元素开始选
    {
        idx = i-1;
        ret = a[i];//处理的元素
        while(idx>=0&&a[idx]>ret)
        {
            a[idx+1] = a[idx];//如果处理的元素应该排在索引前面时，让当前索引指针往后移腾出空位
            idx--;
        }
        a[idx+1] = ret;
    }
    cout<<"排序后:";
    print(a);
}
//插入二分排序
void BinaryInsertSort(vector<int>a) {
    cout<<"插入二分排序"<<endl;
    print(a);
    int len = a.size();
    int i;
    for( i=0; i<len; i++) {
        int low=0;
        int high=i-1;
        int temp=a[i];
        int mid=0;
        while(low<=high) {
            mid=(low+high)/2;
            if(a[mid]<temp) {
                low=mid+1;
            } else {
                high=mid-1;
            }
        }
        int j;
        for(j=i-1; j>=low; j--) {
            a[j+1]=a[j];
        }
        if(i!=low)
            a[low]=temp;
    }
    cout<<"排序后:";
    print(a);
}
//希尔排序
void shell_sort(vector<int>a)
{
    cout<<"希尔排序"<<endl;
    print(a);
    int len = a.size();
    int i,j,gap;//gap为步长
    for(gap = len/2;gap>0;gap/=2)//每次范围缩小一半
    {
        for(i = 0;i<gap;i++)
        {
            for(int j =i+gap;j<len;j+=gap)//本质上和插排差不多，只是排序范围上发生了变化，希尔是跳着选则排序对象的
            {
                if(a[j]<a[j-gap])//当前值比上一个对象小
                {
                    int tmp=a[j];//存储当前处理对象
                    int k = j-gap;//准备动手将大于处理对象的数往后移动
                    while(k>=0&&a[k]>tmp)
                    {
                        a[k+gap] = a[k];
                        k-=gap;
                    }
                    a[k+gap] = tmp;
                }
            }
        }
    }
    cout<<"排序后:";
    print(a);
}

//冒泡排序
void bubble_sort(vector<int> a)
{
    cout<<"冒泡排序"<<endl;
    print(a);
    int len = a.size();
    for(int i =0;i<len-1;i++)
    {
        int idx = a[i];
        bool flag =false;//若直至当前循环结束都没交换过说明已经有序，可提前结束
        for(int j =len-1;j>i;j--)//从后往前开始换
        {
            if(a[j-1]>a[j])
            {
                swap(a[j-1],a[j]);
                flag = true;
            }           
        }
        if(!flag)
        break;
    }
    cout<<"排序后:";
    print(a);
}

//快速排序
//划分函数
int partition(vector<int>& a,int l,int r)
{
    int pivot = a[l];//基准值
    while(l<r)
    {
        while(l<r&&a[r]>=pivot) r--;//找到比基准小的值放在左边
        a[l] = a[r];
        while(l<r&&a[l]<=pivot) l++;
        a[r] = a[l];
    }
    a[l] = pivot;//基准值放到正确位置
    return l;//返回基准的最终位置
}
void quick_sort(vector<int>& a,int l,int r)
{
    if(l<r)
    {
        int pivotpos = partition(a,l,r);
        quick_sort(a,l,pivotpos-1);
        quick_sort(a,pivotpos+1,r);
    }
    print(a);
}


//选择排序
void select_sort(vector<int> a)
{
    cout<<"选择排序"<<endl;
    print(a);
    for(int i =0;i<a.size();i++)
    {
        int min_idx = i;//记录最小元素位置
        for(int j =i+1;j<a.size();j++)
        {
            if(a[j]<a[min_idx]) min_idx = j;//更新
        }
        if(min_idx!=i) swap(a[i],a[min_idx]);//当前i所指元素不是最小值就交换
    }
    print(a);
}

//堆排序
//从小到大排序，构建大根堆
void down(vector<int>& a,int i,int n)
{
    int parent =i;//获取父节点
    // for(int child= 2*i;i<=n;i*=2)
    // {
    //     if(i<n&&a[i]<a[i+1])
    //     i++;
    //     if(a[0]>=a[i])
    //     break;
    //     else
    //     {
    //      a[parent] =a[i];
    //      parent =i;   
    //     }
    // }
    // a[parent] = a[0];//被筛选接待你插入最终位置
    int child = 2*i+1;
    while(child<n)
    {
        if(child+1<n&&a[child]<a[child+1])
        child++;//比较左右大小，若左小于右，则较大值为右即child+1

        if(a[parent]<a[child])//将最大值放到父节点上
        {
            swap(a[parent],a[child]);
            parent = child;
        }
        child = child*2+1;//下坠换行
    }
}
//构建大根堆
void build_heap(vector<int>&a)
{
    for(int i =a.size()/2;i>=0;i--)
        down(a,i,a.size());
}
//堆排序实现
void heap_sort(vector<int>a)
{
    cout<<"堆排序"<<endl;
    print(a);
    build_heap(a);
    for(int i = a.size()-1;i>0;i--)
    {
        swap(a[0],a[i]);//最大位置取出来放到最后
        down(a,0,i);
    }
    print(a);
}

//归并排序
void merge(vector<int>& arr, int left, int mid, int right) {
    int i = left, j = mid + 1, k = 0;
    vector<int> temp(right - left + 1);//辅助数组

    while (i <= mid && j <= right) {//比较两个区域，把较小值插入辅助数组，另一个不动
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];//插入后往后移动
        } else {
            temp[k++] = arr[j++];
        }
    }

    while (i <= mid) {
        temp[k++] = arr[i++];
    }

    while (j <= right) {
        temp[k++] = arr[j++];
    }

    for (i = left, k = 0; i <= right; ++i, ++k) {
        arr[i] = temp[k];
    }
}

void mergeSort(vector<int>& arr, int left, int right) {
    if (left >= right) {
        return;
    }

    int mid = (left + right) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

//归并测试
void merge_test(vector<int> a)
{
    cout<<"归并排序"<<endl;
    print(a);
    int l =0,r = a.size()-1;
    mergeSort(a,l,r);
    print(a);

}



//练习题
class exercises
{
    public:
    //8.3.3
    //1
    //两边对称冒泡
    void num1(vector<int>a,int n)
    {
        int l =0,r = n-1;
        bool flag =true;
        while(l<r)
        {
            flag= false;
            for(int i=l;i<r;i++)
            {
                if(a[i]>a[i+1])
                {
                    swap(a[i],a[i+1]);
                    flag = true;
                }
            }
            r--;
            for(int i =r;i>l;i--)
            {
                if(a[i]<a[i-1])
                {
                    swap(a[i],a[i-1]);
                    flag = true;
                }

            }
            l++;
        }
    }

    //num2
    //快排的思想，找到一个偶数后和后一个数即奇数交换
    void num2(vector<int> a,int n)
    {
        int i =0,j=n-1;
        while(i<j)
        {
            while(i<j&&a[i]%2!=0)
            i++;
            while(i<j&&a[j]%2!=1) j--;//向后找到一个奇数元素
            if(i<j)
                swap(a[i],a[j]);
            i++,j--;
        }
    }

    //4
    //多加了步随机
    int num4(vector<int> a,int l,int r)
    {
        int rand_idx = l+rand()%(r-l+1);
        swap(a[rand_idx],a[l]);
        int pivot = a[l];
        int i =l;
        for(int j =l+1;j<=r;j++)
        {
            if(a[j]<pivot)
            swap(a[++i],a[j]);

        }
        swap(a[i],a[l]);//将基准元素插入最终位置
        return i;
    }

    //5
    //看解析更清楚
    int num5(vector<int> a,int l,int r,int k)
    {
        int pivot = a[l];
        int l_temp=l;
        int r_temp = r;
        while(l<r)
        {
            while(l<r&&a[r]>=pivot)
                --r;
            a[l] =a[r];
            while(l<r&&a[l]<=pivot)
                ++l;
            a[r] = a[l];
        }
        a[l] =pivot;

        //算法精髓
        if(l==k)
        return a[l];
        else if(l>k)
        return num5(a,l_temp,l-1,k);
        else
        return num5(a,l+1,r_temp,k);
    }

    //6
    typedef enum{red,white,blue} color;//枚举数组
    void num6(color a[],int n)
    {
        int i =0,j = 0,k=n-1;
        while(j<=k)
        switch(a[j])
        {
            case red :swap(a[i],a[j]);i++;j++;break;//红色和i交换
            case white: j++;break;
            case blue: swap(a[j],a[k]);k--;//蓝色和k交换
        }
    }
    

    //8.4
    //4
    //链表省略

    //5
    //遍历
    bool num4_5(vector<int> a,int len)
    {
        if(len%2==0)//len为偶数，有一个单分支节点
        {
            if(a[len/2]>a[len])
            return false;
            for(int i = len/2-1;i>=1;i--)
                if(a[i]>a[i*2]||a[i]>a[2*i]+1)
                return false;
        }
        else
        {
            for(int i =len/2;i>=1;i--)
                if(a[i]>a[i*2]||a[i]>a[i*2+1])
                return false;
        }
        return true;
    }



};
int main()
{
    vector<int> a = { 3, 6, 2, 9, 10, 7, 4, 8, 5,1 };
    int b[10] = { 3, 6, 2, 9, 10, 7, 4, 8, 5,1 };
    //insert_sort(a);
    // BinaryInsertSort(a);
    // shell_sort(a);
    //bubble_sort(a);
    //quick_sort(a,0,a.size()-1);
    //select_sort(a);
    //heap_sort(a);
    
    merge_test(a);
    return 0;
}

后记

2023年3月7日，数据结构一轮复习，完！