///真题
const int MaxSize = 100;
typedef struct BTNode {int data;struct LNode *lchild;struct LNode *rchild;
} BTNode;
typedef struct LNode{int data;struct LNode *next;
}LNode;//图邻接表
typedef struct ArcNode{int weight;	//边表节点权重int adjvex;struct ArcNode *next;
}ArcNode;
typedef struct VNode{int data;ArcNode *firstarc;
}VNode;
typedef struct ALGraph{VNode adjlist[MaxSize];int arcnum,vexnum;
};//2021计学
/*1.一个二叉查找树，已经告诉非空，有n个节点，节点结构已经给出struct node{
int key;
int n;//n是以该节点为根的子树的所有孩子个数
struct node *left,*right;
}（1）求这个二叉查找树节点的最小关键字和最大关键字是什么？（不能用递归和栈）（2）求这个二叉树第k小的元素关键字(n>=k>=1),要求时间复杂度不超过log2^{^{n}}。
1：二叉查找树 最小的是中序第一个 是最左下结点 最大的是中序最后一个 最右下结点
2. 如果不知道二叉树中每个结点的所有孩子数量，则只能中序遍历，左根右找到第k小的解析：
https://leetcode.cn/problems/kth-smallest-element-in-a-bst/solution/er-cha-sou-suo-shu-zhong-di-kxiao-de-yua-8o07/
*/
int MinKey(BTNode *st) {BTNode *p=st;while(p->lchild!=NULL) p=p->lchild;return p->data;
}
int MaxKey(BTNode *st){BTNode *p=st;while(p->rchild!=NULL) p=p->rchild;return p->data;
}int findNo_k(BTNode *st,int k){BTNode *p;if(p->lchild->n < k-1){	//左子树小于k-1 当前根小于k 看右子树p=p->rchild;k-=p->lchild->n+1;}else if(p->n==k-1)return p->data;else p=p->lchild;
}//2021计学 2
typedef struct MGraph{int Vex[MaxSize];int edge[MaxSize][MaxSize];int vexnum,arcnum;
}MGraph;
int f[MaxSize];
int find(int x){if(x==f[x]) return x;return f[x] = find(f[x]);
}
void Union(int a,int b){a=find(a);b=find(b);if(a!=b){f[a] = b;}
}
typedef struct edge{int u,v,w;
}edge;
int  sortEdge(MGraph *&G,edge Edge[MaxSize]){	//对现有边进行排序int cnt = 0;for(int i=1;i<=G->vexnum;i++)for(int j=i+1;j<=G->vexnum;j++){Edge[++cnt].u=i;Edge[cnt].v = j;Edge[cnt].w = G->edge[i][j];}for(int i=1;i<cnt;i++){for(int j=1;j<=n-i;j++){if(Edge[j] > Edge[j+1]){edge temp = Edge[j];Edge[j] = Edge[j+1];Edge[j+1] = temp;}}}return cnt;	//返回边的条数
}int minTree[MaxSize][MaxSize];	//以邻接矩阵存储的最小生成树
void kurscal(MGraph *G){for(int i=1;i<=G->vexnum;i++){f[i] = i;}edge Edge[MaxSize];int edgesum = sortedge(G,Edge);for(int i=1;i<edgesum;i++){int u=Edge[i].u,v=Edge[i].v;if(find(u)==find(v)) continue;else{Union(u,v);minTree[u][v] = minTree[v][u] = Edge[i].w;}}
}//dfs找u->v路径上最大的边  注意是找最小生成树上的路径而不是整个图
void dfs(int u,int b,int vis[],int curw,int *maxw,int x,int y,int *from,int *to)	//curw是原点a到当前u最大的边数 maxw是a到b最大的边数 x y是记录的a-u的最大的边的两端点 from to是最大边的端点
{vis[u] = 1;if(u==b){if(curw > *maxw){*maxw =  curw;*from =  x;*to = y;}return;}for(int i=1;i<=G->vexnum;i++){if(!vis[i]&&minTree[u][i]!=0){int temp = curw;if(minTree[u][i] > curw) curw = minTree[u][i];dfs(i,b,vis,curw,maxw,u,i,from,to);curw = temp; 		//回溯}}}
void Add_NewEdge(edge newedge){int vis[MaxSize] = {0};int newa=newedge.u,newb=newedge.v,neww=newedge.w;int *maxw = 0;int from,to;	//表示最长边的两个端点 需要删除之前的最大的边，则在邻接矩阵中删除该边即可dfs(newa,newb,vis,0,&maxw,0,0,&from,&to);	//0传入做curw 0 0传入做当前最大边的两端点if(maxw < newedge.w) return;minTree[from][to] = minTree[to][from] = 0;minTree[newa][newb] = minTree[newb][newa] = neww;
}//20计学
//1.
void swap(int a[],int x,int y){int temp=a[x];a[x] = a[y];a[y] = temp;
}
void sort(int a[],int n,int x1,int x2){int l=1,j=n+1;int pivot = x1;while(l<r){i++;while(i<r&&a[i]<pivot) i++;j--;while(j>l&&a[j]>pivot) j--;if(i<j) swap(a,a[i],a[j]);}swap(a[1],a[j]);l=1,j=n+1,pivot=x2;while(l<r){i++;while(i<r&&a[i]<pivot) i++;j--;while(j>l&&a[j]>pivot) j--;if(i<j) swap(a,a[i],a[j]);}swap(a,a[l],a[j]);
}//2
int count(BTNode *T){int cnt=0;BTNode *s[MaxSize],p=T;int top=-1;while(p||top!=-1){if(p){s[++top] = p;p=p->lchild;cnt++;}else{p=s[top--];p=p->rchild;}}return cnt;
}/上为计学 下为软学
/上为计学 下为软学
/上为计学 下为软学//2021软学
//1.
/*思路：先序遍历：根左右，则入栈时为根右左，按根右左的顺序入栈访问结点*/
void preorder(int a[],int n){int s[MaxSize],top=-1; //栈中存放下标//假设数组下标从1开始s[++top] = a[1];while(top!=-1){int i=s[top--];printf("%d ",a[i]);if(2*i+1<n)	s[++top] = 2*i+1;if(2*i<n) 	s[++top] = 2*i;}
}//2.
/*思想：先求出链表长度，再从大到小冒泡排序*/
int length(LNode *st){int res=0;while(st!=NULL){res++;st=st->next;}return cnt;
}
void BubbleSort(LNode *st){int n=length(st);//加入头节点LNode *pre,*p,*dummyHead = (LNode *)malloc(sizeof(LNode));dummyHead->next = st;st=dummyHead;for(int i=1;i<n;i++){p=st;for(int j=1;j<=n-i;j++){if(p->data<p->next->data){int temp = p->data;p->data = p->next->data;p->next->data = temp;}p=p->next;}}
}//最大生成树
/*思路：将Prim算法中的判断小于改为判断大于即可。
注意要把本来为INF的边改为最小这样才能找到实际的最大的*/
void Prim(MGraph *G,int u,int path[MaxSize]){		//path中存放最小生成树int maxcost[MaxSize],vis[MaxSize]={0},path[MaxSize];for(int i=1;i<=G->vexnum;i++)for(int j=1;j<=G->vexnum;j++){if(G->edge[i][j]==INF){G->edge[i][j] = -1;	//把INF改为最小，这样找到的就是实际最大的}}for(int i=1;i<=G->vexnum;i++){maxcost[i] = G->edge[u][i];path[i] = -1;}vis[u] = 1;for(int i=1;i<n;i++){int k=1;for(int j=1;j<=n;j++)if(maxcost[j] > maxcost[k] && !vis[j])k=j;vis[k] = 1;for(int j=1;j<=n;j++){if(maxcost[j] < G->edge[k][j] && !vis[j]){maxcost[j] = G-edge[k][j];path[j] = k;}}}
}/*2020软学
>1.在链表中找到值为k的元素，若找到，则与尾结点交换位置。>2.设计算法，求无向图的连通分量。>3.设计非递归算法，求根结点到二叉树某一p结点的路径。*/void find(LNode *&st,int k){LNode *pre,*r,*p,*dummyHead = (LNode *)malloc(sizeof(LNode));dummyHead->next = st;st=dummyHead;pre = st;r=st;while(r->next!=NULL){if(r->next->data==k) pre=p;r=r->next;}if(pre!=st){p=pre->next;pre->next = p->next;p->next = r->next;}
}/*2.DFS求就行把？ 求图的连通分量*/
void fun(MGraph *G){int vis[MaxSize] = {0},cnt=0;	//cnt=连通分量个数for(int i=1;i<=G->vexnum;i++){if(!vis[i]){DFS(G,i,vis,cnt);}}
}
void DFS(MGraph *G,int u,int vis[MaxSize],int &cnt){int s[MaxSize],top=-1;s[++top] = u;vis[u] = 1;while(top!=-1){u = s[top--];printf("%d ",u);for(int i=1;i<=G->vexnum;i++){if(!vis[i]&&G->edge[u][i]!=INF){vis[i] = 1;s[++top] = i;}}}cnt++;printf("\n");
}//3 求根节点到某一结点的路径或者求两个结点的最近公共祖先，都是用最难的后序遍历，栈中所有元素为栈顶元素祖先
void PostOrder(BTNode *T,BTNode *t){BTNode *p=T,*r=NULL,*s[MaxSize];int top=-1;while(p ||top!=-1){if(p){s[++top] = p;p=p->lchild;}else{p=s[top];if(p==t){for(int i=0;i<=top;i++) 	printf("%d ",s[i]->data);return;}if(p->rchild&&p->rchild!=r){p=p->rchild;}else{top--;r=p;p=NULL;}}}
}/*2019计学
>1.试设计一个算法，改造一个带表头结点的双向链表，所有结点的原有次序保持在各个结点的右链域rLink中，
并利用左链域ILink把所有结点按照其值从大到小的顺序连接起来> 2.二叉树的后序遍历序列存放在数组A中，中序遍历序列存放在数组B中，根据后序和中序序列，创建二叉树。*/
/*
typedef struct DNode{int data;struct DNode *prior,*next;
}DNode;
*/
void sort(DNode *st){DNode *pre,*p=st->next,*r;while(p!=NULL){r=p->next;		//保存p后继节点 防止断链pre=st;while(pre->prior!=NULL && pre->prior->data>p->data)	//找pre前面的结点插入pre=pre->prior;p->prior=pre->prior;pre->prior=p;p=r;}
}BTNode* Build(int in[],int l1,int r1,int post[],int l2,int r2){int root = post[r2];int i=l1;while(i<=r1&&in[i]!=root) i++;BTNode *st = (BTNode *)malloc(sizeof(BTNode));st->data = root;int llen=i-l1,rlen=r1-i;if(llen) st->lchild = Build(st->lchild,in,l1,l1+llen-1,post,l2,l2+llen-1);else st->lchild = NULL;if(rlen)st->rchild = Build(st->rchild,in,r2-rlen+1,r2,post,r2-rlen,r2-1);else st->rchild = NULL;return st;
}//2018计学
/*假定用两个一维数组L[1:n]和R[1:n]作为有n个节点二叉树的存储结构，
L[i]和R[i]分别指示节点i的左儿子和右儿子，0表示空。试写一个算法判断节点u是否为节点v的子孙。*/
int isChild(int L[],int R[],int n,int u,int v){if(u==0) return 0;if(L[u]==v||R[u]==v) return 1;return isChild(L,R,n,L[u],v) || isChild(L,R,n,R[u],v);
}//2017计学
/*A和B是长度为n的两个数组。设计一个算法，该算法输出长度为n的数组C。
要求1：数组C中的每一个元素C[i]=||{A[j]|A[j]<=B[i],1<=j<=n}||，其中||S||表示集合S中的元素个数。
例如：下表给出了长度为4的两个数组A和B，以及满足要求的数组C；要求2：所设计算法的时间复杂度低于O(n2)。i	1	2	3	4
A[i]	6	17	9	10
B[i]	8	2	17	13
C[i]	1	0	4	3
*/
/*思路：先对A数组排序，排完后在A中二分查找对应的数字*/
void QuickSort(int a[],int l,int r){int i=l,j=r+1,pivot=a[l];while(i<j){i++;while(i<=r&&a[i]<pivot) i++;j--;while(j>=l&&a[j]>pivot) j--;if(i<j){int temp = a[i];a[i] = a[j];a[j] = temp;}}int temp = a[l];a[l] = a[j];a[j] = a[l];QuickSort(a,l,j-1);QuickSort(a,j+1,r);
}
int BinarySearch(int a[],int l,int r,int x){int mid = l+r>>1;while(l<=r){mid = l+r>>1;if(a[mid]<x) l=mid+1;else if(a[mid]>x) r=mid-1;else return mid -1 ;}//此时r l 应该看rreturn r;	//未找到
}
void fun(int a[],int b[],int n){int c[MaxSize];QuickSort(a,1,n);for(int i=1;i<=n;i++){	//对于每一个B[i]去A【】中二分查找int k = BunarySearch(a,1,n,b[i]);c[i] = k;printf("%d ",c[i]);}
}/*二叉树的宽度定义为具有结点数最多的那一层上的结点总数。如下图所示，以a为根的二叉树宽度为3。
假设二叉树以链接结构存储，
指针T指向二叉树的根，数中结点的结构为（left,data,right）,写出求二叉树宽度的非递归算法。*/
int width(BTNode *st){BTNode *q[MaxSize],p=st;int last = 1,width = 0,max = 0,front=-1,rear=-1;q[++rear] = p;while(front!=rear){p = q[++front];if(p->lchild!=NULL) q[++rear] = p->lchild;if(p->rchild!=NULL) q[++rear] = p->rchild;if(front==last){if(max<width) max = width;width = 0;last = rear;}}return max;
}//2016计学
int last_k(LNode *st,int k){LNode *pre=st->next,p=st->next;while(k-- && p!=NULL) p=p->next;if(p==NULL) return 0;while(p){pre=pre->next;p=p->next;}printf("%d ",pre->data);return 1;
}//二叉树序列
/*思路：先根遍历，找到几就设置几个孩子*/
BTNode  Build(char s[]){int i=0;BTNode *stack[MaxSize],*p,*st;st = (BTNode *)malloc(sizeof(BTNode));st->lchild = st->rchild = NULL;int top=-1;p=st;while(p || top!=-1){if(p){stack[++top] = p;if(s[i]==2){st->lchild = (BTNode *)malloc(sizeof(BTNode));st->rchild = (BTNode *)malloc(sizeof(BTNode));}else if(s[i] == 1){st->lchild = (BTNode *)malloc(sizeof(BTNode));st->rchild = NULL;}else{st->lchild = st->rchild = NULL;}p=p->lchild;i++;}else{p=stack[top--];p=p->rchild;}}return st;
}//2015
/*(2015计学)给定两个单链表的头指针分别为head1和head2，请设计一个算法判断这两个单链表是否相交.
如果相交则返回第一个交点，要求算法的时间复杂度为O(length1+length2),
其中length1和length2分别为两个链表的长度。*/
//相交一定是Y 往后搞就行了
LNode isConverge(LNode *head1,LNode *head2){int cnt=0,n1=0,n2=0;LNode *p=head1,*q=head2;while(p){n1++;p=p->next;}while(q){n2++;p=p->next;}if(n2>n1){p=head2;q=head1;cnt = n2-n1;}else{p=head1;q=head2;cnt=n1-n2;}while(cnt){p=p->next;cnt--;}while(p!=NULL&&q!=NULL){if(p==q) return p;p=p->next;q=q->next;}return NULL;
}
/*统计二叉树各层中独生叶结点（既是叶结点又无兄弟结点）的数目。
要求：编写函数LeafNoBrotherInEachLevel(root),其中root为指向某二叉树根结点的指针，
该函数的功能是输出以root为根的二叉树各层中独生叶结点的数目。*/
int isLeaf(BTNode *st){return (st->lchild==NULL)&&(st->rchild==NULL) ;
}
void LeafNoBrotherInEachLevel(BTNode *st){BTNode *p=st,*q[MaxSize]int front=-1,rear=-1,level = 0,last=1,cnt=0;q[++rear] = p;while(front!=rear){p=q[++rear];//p的左子树为独生叶节点 首要要保证p的左孩子不为空if(p->lchild && isLeaf(p->lchild)&&p->rchild==NULL) cnt++;	 //if(p->lchildif(p->rchild && isLeaf(p->rchild)&&p->lchild==NULL) cnt++;if(p->lchild) q[++rear] = p->lchild;if(p->rchild) q[++rear] = p->rchild;if(front==last){printf("%d层的独生叶节点数为%d\n",level,cnt);cnt=0;level++;last=rear;}}
}//2014计学
/*1.请设计一个算法，将整数数组S[1…n]中所有的偶数放到所有的奇数之前，要求算法时间复杂性为O(n)。2.设二叉查找树采用链接存储结构，其各结点的关键词均不相同，请编写非递归算法，
按递减次序打印所有左子树非空，右子树为空的结点的关键词。*/
void sort(int s[],int n){int l=1,j=r;while(l<r){while(l<r&&a[l]%2==0) l++;while(l<r&&a[r]%2==1) r--;int temp = a[l];a[l] = a[r];a[r] = temp;}
}void find(BTNode *st){BTNode *s[MaxSoze],p=st;int top=-1;while(top!=-1 || p){if(p){if(p->rchild==NULL && p->lchild!=NULL){printf("%d ",p->data);}s[++top] = p;p=p->rchild;}else{p=s[top--];p=p->lchild;}}
}//2013计学typedef struct node{int coef;	//x的系数int exp;	//x的方幂struct node *next;	//下一指针
}node;
void diff(node *&st){node *pre=st,p=pre->next;while(p!=NULL){if(p->exp==0){pre->next = p->next;free(p);p=pre->next;}else{p->coef *= p->exp;p->exp -=1;pre=p;p=p->next;}}
}
void swap(node *&p,node *&q){int temp = p->coef;p->coef=q->coef;q->coef = temp;temp = p->exp;p->exp = q->exp;q->exp = temp;
}
void sort(node *&st){	//对链表进行排序node *pre=st,*p=st->next,*r;st->next = NULL;while(p!=NULL){r=p->next;pre=st;while(pre->next!=NULL && pre->next->exp > p->exp)pre=pre->next;p->next = pre->next;pre->next = p;p=r;}}
int cmp(node *f,node *g){diff(f);sort(f);sort(g);node *p=f,*q=g;while(p!=NULL&&q!=NULL){if(p->exp==q->exp&&p->coef==q->coef)p=p->next,q=q->next;else return 0;}if(p==NULL&&q!=NULL) return 0;if(p!=NULL&&q==NULL) return 0;return 1;
}/*先根遍历的最后一个结点，是靠右靠下的结点。如果结点只有左孩子，则遍历该孩子
如果左右孩子都有或者只有右孩子，遍历右孩子*/
BTNode lastpre(BTNode *st){BTNode *pre,*p=st;while(true){if(p->rchild!=NULL) p=p->rchild;	//有右孩子向右孩子遍历else if(p->lchild!=NULL) p=p->lchild;	//没有右孩子 有左孩子向左孩子遍历else break;}return p;
}
void del(BTNode *st){if(st==NULL) return;del(st->lchild);del(st->rchild);free(st);
}
//删除二叉查找树中大于等于x的结点
/*
递归删除：记录当前结点及其前驱结点
向右下找，一直找到第一个大于等于x的结点p及其前驱节点pre。将pre->rchild = p->lchild ,递归删除p->rchild
然后p=pre->rchild
如果当前结点小于x，就拖家带口向右下*/
//自己写的
void del_x(BTNode *st,int x){BTNode *p = st,*pre;while(p->rchild!=NULL&&p->rchild->data <= x){pre=p;p=p->rchild;	//找到第一个大于等于x的结点}while(p!=NULL){if(p->data>=x){pre->rchild = p->lchild;p->lchild = NULL;del(p);p=pre->rchild;		//恢复p}else{pre=p;p=p->rchild;}}
}//2012计学
//2
/*采用递归方法，非叶节点 = 左子树的非叶节点+右子树的非叶节点+1*/
int count(BTNode *T){if(T==NULL || T->lchild==NULL&&T->rchild==NULL)return 0;return 1+count(T->lchild) + count(T->rchild);
}//3
// BFS求
void find_k(MGraph *G,int v,int k){int vis[MaxSize] = {0};int p,q[MaxSize][2],front=-1,rear=-1;q[++rear][0] = v;q[rear][1] = 0;while(front!=rear){p=q[++front];for(int i=1;i<=G->vexnum;i++){if(!vis[i]){q[++rear][0] = i;q[rear][1] = q[front][1] + 1;if(q[rear][1] == k)printf("%d ",q[rear][0]);}}}
}//2008 写出字符串的朴素模式匹配算法，并进行时间复杂度分析
/*时间复杂度：假设s长度为n，t长度为m，则平均时间复杂度为O(n*m)*/
int  BF(char s[],char t[])	//s是长串，t是模式串
{int i=0,j=0;while(s[i]!='\0' && t[j]!='\0'){if(s[i]==t[j])i++,j++;else{j=0;i=i-j+1;		//背过}}
}
//延伸：优化的KMP 优化原因：当当前s[i]!=t[j],而t[j] = t[next[j]],则下次匹配s[i]和t[next[j]]没有意义因为t[next[j]]=t[j]
/*KMP算法的时间复杂度：O(m+n)*/
void getNextval(char t[],int nextval[]){int j=0,k=-1;nextval[0] = -1;while(t[i]!='\0'){if(k==-1 || t[j]==t[k]){i++,j++;if(t[j]==t[k])nextval[j] = nextval[k];elsenextval[j] = k;}else k=next[k];}
}
int KMP(char s[],char t[]){int i=0,j=0;int nextval[MaxSize];getNextval(t,nextval);while(s[i]!='\0' && t[j]!='\0'){if(s[i]==t[j])i++,j++;elsej=nextval[j];}if(t[j]=='\0') return 1;
}//中序前序构建树
BTNode *Build(int pre[],int l1,int r1,int in[],int l2,int r2){BTNode *st = (BTNode *)malloc(sizeof(BTNode));st->data = pre[l1];int i=l2;while(in[i]!=pre[l1]) i++;int llen = i-l2;int rlen = r2-i;if(llen) st->lchild = Build(pre,l1+1,l1+llen,in,l2,l2+llen-1);else st->lchild = NULL;if(rlen) st->rchild = Build(pre,r1-rlen+1,r1,in,r2-rlen+1,r2);else st->rchild = NULL;return st;
}//2007：
//2     最长平台 这个题和2002第2题求连续的最长上升序列是一样的， 最后的一段的长度没有和最大长度对比，还需要再对比一次
int maxlen(int a[],int n){int max = 0,len = 1;if(n==0||n==1)return n;       //下面的循环是从2开始的，如果长度不够就越界了 特判！for(int i=2;i<=n;i++){if(a[i]==a[i-1])len ++;else{if(len >max)max = len;len = 1;}}//对结尾进行判断 最后一个平台的len没有和max比if(len > max)max = len;
}//3
int sum(BTNode *st){if(st == NULL) return 0;return st->data + sum(st->lchild) + sum(st->rchild);
}//4
int GetMax(int a[],int i,int n){if(i==n) return a[n];return max(a[i],GetMax(a,i+1,n));
}//5.
void output(){int a[20000] = {0};		//多大？？？a[1] = 1;int i=1;int cnt = 1;while(cnt<=100){if(a[i]){a[2*i] = 1;a[3*i] = 1;cnt+=2;printf("%d ",i);}i++;}
}//6 统计子集 又忘了啊！哎
/*状压dp。同时也要设置一个变量k从0开始增加。如果状态最后一位是1则输出k.不管是不是1，k++看下一个*/
/*n个元素有2^n个子集，每个元素有选与不选两种情况*/void  powerset(int n){n=1<<n;for(int i=0;i<n;i++){int j=i;int k=0;printf("{");while(j){if(j&1) printf("%d ",k);k++;j>>=1;}printf("}\n");}
}//2003计学//1.矩阵旋转
/*
a[i][j] = a[j][n-i-1] i j都从0开始
*/
void rotate(int** matrix, int matrixSize, int* matrixColSize){for(int i=0;i<matrixSize/2;i++){for(int j=0;j<(matrixSize+1)/2;j++){int temp = matrix[i][j];matrix[i][j] = matrix[matrixSize-j-1][i];matrix[matrixSize-j-1][i] = matrix[matrixSize-i-1][matrixSize-j-1];matrix[matrixSize-i-1][matrixSize-j-1] = matrix[j][matrixSize-i-1];matrix[j][matrixSize-i-1] = temp;}}
}//2.
void fun(double x){int a = (int)x;printf("%d %lf\n",a,x-a);
}//3
double jiecheng(int x){double res=1;while(x){res*=x;x--;}return res;
}
double exp(double x){double eps=1;double res = 0;double i=1;while(eps>1e-8){eps = eps * x / i;      //只需要这样就够了res +=  eps;i++;}return res;
}//4
void translate(char s[]){int i=0;int flag = false;   //用来表示译整工作是否结束while(s[i]!='\0'){if(s[i]>='0' && s[i] <='9'){while(s[i]>='0' &&s[i]<='9'){printf("%c",s[i]);i++;}flag = true;if(s[i]=='.' && s[i+1]>=0&&s[i+1]<='9'){printf(".");i++;		//s[i]是. 往后一个while(s[i]>='0'&&s[i]<='9'){printf("%c",s[i]);i++;}}else return;}else if(!flag)i++;else return;}
}//5
void f(double x,double y){double s[MaxSize];int top=-1;while(x>=0){s[++top] = x/y;y=x+y;x-=1;}double res=0;while(top!=-1)res += s[top--];printf("%lf",res);
}void GetArrA(int a[],int b[],int n){    //由b[i]确定a[i]  b[i]表示a[i]~a[i-1]中比a[i]小的的个数int vis[N] = {0};for(int i=n;i>=1;i--){      //倒序得到a[]for(int j=1;j<=n;j++){  //j是1~n的n个数if(vis[j] == 0){    //如果j这个数字被用过了，说明他在当前i的后面 如果没被用过，说明在当前i的前面。b[i] --;if(b[i] < 0){   //b[i] = 0了 此时刚好j从1遍历到j 说明1~j-1都不满足原来的b[i]的个数。  说明a[i] = j.vis[j] = 1;a[i] = j;break;}}}}
}//2002计学
//1.
void insert(int a[],int i,int k){if(a[i] > k){a[i+1] = a[i];insert(a,i-1,k);}else if(i == 0 || a[i-1] <= k)  //a[i-1] <= k 必须是当前i的前一个a[i+1] = k;
}//2 最长上升子序列 子序列不要求连续
void MaxLen(int a[],int n){int f[N] = {0}; //f[i]表示以a[i]结尾的最长上升序列 a[i]必须选int res=0;for(int i=1;i<=n;i++){f[i] = 1;       //没人就他自己for(int j=1;j<i;j++){if(a[j] < a[i])f[i] = max(f[i],f[j] + 1);}res = max(res,f[i]);}printf("%d",res);
}//题目要求连续的最长上升子序列 这个题和2002第2题求连续的最长上升序列是一样的， 最后的一段的长度没有和最大长度对比，还需要再对比一次
void MaxLen(int a[],int n){int len = 1,maxlen = 0;for(int i=1;i<n;i++){if(a[i] < a[i+1])len ++;else {if(len > maxlen) maxlen = len;len = 1;}}if(len > maxlen)    //还是最后一趟没有比较maxlen = len;
}
//链表集合合并LNode SetAdd(LNode *a,LNode *b){LNode *p,*r,*q,*pre,*dummyHead1,*dummyHead2;dummyHead1=(LNode *)malloc(sizeof(LNode));dummyHead2=(LNode *)malloc(sizeof(LNode));dummyHead1->next = a;a=dummyHead1;dummyHead2->next = b;b=dummyHead2;pre=a,p=pre->next,q=b;while(p!=NULL){r=p->next;q=b;while(q->next!=NULL && q->next->data!=p->data)q=q->next;if(q->next->data==p->data){pre->next = p->next;free(p);}else{q->next = p;p->next = NULL;}p=r;}return b->next;
}//4.链表八进制转十进制/*思路：将链表p q逆置，然后合并，当前位对8取余，进位除以8 所以当前位是不是不对？ 是的，当前位应为（当前位+进位）对8取余*/
LNode * reverse(LNode *&st){LNode *p,*dummyHead,*r;dummyHead = (LNode *)malloc(sizeof(LNode));dummyHead->next = st;st=dummyHead;p=st->next;st->next = NULL;while(p){r = p->next;p->next = st->next;st->next = p;p=r;}return st->next;
}
LNode* transfer(LNode *P,LNode *Q){P = reverse(P);Q = reverse(Q);int add = 0;LNode *p = P,*q = Q,*pre;while(p!=NULL && q!=NULL){int now = p->data + q->data + add;p->data = now % 8;add = now / 8;pre=p;p=p->next;q=q->next;}if(p==NULL){pre->next = q;while(q!=NULL){int now = q->data +add;q->data = now % 8;add = now / 8;}}else{while(q!=NULL){int now = q->data + add;q->data = now % 8;add = now / 8;}}return P;
}//5
/*递归出口y >= 100
否则x+=1.5 y+=x;
返回sin(y)
*/
int f(int x,int y){if(y>=100)  return sin(y);f(x+1.5,x+y+1.5);
}//2001
//1.交换后继
void swap(LNode *HEAD,LNode *p){LNode *pre = HEAD,*r;if(p->next == NULL) //p不存在后继 返回return;while(pre->next != p){pre=pre->next;}r=p->next;pre->next = r;p->next = r->next;r->next = p;
}//2.二叉树层次遍历
void LevelOrder(BTNode *st){BTNode *q[MaxSize],*p=st;int front = -1,rear=-1;q[++rear] = p;while(front!=rear){p=q[++front];printf("%d ",p->data);if(p->lchild) q[++rear] = p->lchild;if(p->rchild) q[++rear] = p->rchild;}
}//双向冒泡算法
void BubbleSort(int a[],int n){ //双向冒泡排序int l=1,r=n;int flag = 1;while(l<r&&flag){flag = 0;for(int i=l;i<r;i++)if(a[i] > a[i+1]){swap(a[i],a[i+1]);flag = 1;}r--;for(int i=r;i>l;i--)if(a[i]<a[i-1]){swap(a[i],a[i-1]);flag =1;}l++;}
}//2000//直接插入排序
void insert(int a[],int n){for(int i=1;i<=n;i++){for(int j=i-1;j>=1;j--)if(a[j] > a[i])a[j+1] = a[j];a[j+1] = a[i];}
}void sort(LNode *head)
{LNode *dummyHead,*pre,*p,*r;dummyHead = (LNode )*malloc(sizeof(LNode));dummyHead->next = head;head = dummyHead;pre=head,p=pre->next;pre->next = NULL;while(p!=NULL){r=p->next;pre=head;while(pre->next !=NULL &&pre->next->data < p->data)pre=pre->next;p->next = pre->next;pre->next = p;p=r;}
}//找二叉树两个节点的最近公共祖先
/*找最近公共祖先，根节点到该节点的路径都用后续遍历，栈中的所有元素即为p的所有祖先
假设p在q左边，肯定先便利到p 然后才是q
且为根节点到p的路径*/BTNode * ancestor(BTNode *root,BTNode *p,BTNode *q,BTNode *&r){BTNode *s[MaxSize],s1[MaxSize],*t = root，*last = NULL;int top=-1,top1=-1;while(top!=-1 ||t){if(t){s[++top] = t;t=t->lchild;}else{t=s[top];if(t== p){for(int i=0;i<=top;i++){s1[++top1] = s[i];}}if(t==q){for(int i=top;i>=0;i--){for(int j=top1;j>=0;j--){if(s[i] == s[j])returb s[i];}}}if(t->rchild != NULL&& t->rchild!=last){t=t->rchild;}else{top--;last = p;p=NULL;}}}
}
//公共祖先递归版
// 	https://leetcode.cn/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/solution/er-cha-shu-de-zui-jin-gong-gong-zu-xian-6fdt7/
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q){if(root == NULL || root==p || root==q)return root;struct TreeNode *lchild = lowestCommonAncestor(root->left,p,q);struct TreeNode *rchild = lowestCommonAncestor(root->right,p,q);if(lchild==NULL)    return rchild;if(rchild==NULL)    return lchild;return root;
}//软学
//软学
//软学//2018软学
//1.
int find_k(LNode *Head,int k){if(Head->data == k) //第一个就是值为k，直接返回return false;LNode *dummyHead = (LNode *)malloc(sizeof(LNode));dummyHead->next = Head;Head = dummyHead;LNode *pre = Head,*p;while(p->next !=NULL && p->next->data!=k){pre=p;p=p->next;}LNode *r = p->next;		//节点顺序依次为pre p r(r为data=k的结点)p->next = r->next;r->next = p;pre->next = r;return 1;
}//3 二路归并吧
void sort(int a[],int n,int m){	//前m个升序，后n-m个降序 整体排成降序 要求O(n)int i=1,j=n+1;int b[MaxSize],k=0;for(int i=1;i<=n;i++) b[i] = a[i];while(i<=m&&j<=n){if(b[i] < b[j])a[k++] = b[i++];else a[k++] = b[j++];}while(i<=m) a[k++] = b[i++];while(j<=n) a[k++] = b[j++];}//2017软学
/*写算法的时候写出 算法思想，代码和注释*/
//1.先根遍历二叉树，并输出每个结点的层次  假设根节点从1开始
void PreOrder(BTNode *st,int level){if(st == NULL) return;printf("%d %d",st->data,level);PreOrder(st->lchild,level+1);PreOrder(st->rchild,level+1);
}
//非递归怎么写？
void PreOrder(BTNode *st)//2typedef struct DNode{int Data,Freq;struct DNode *LLink,*RLink;
}DNode;void Locate(DNode *st,int x){DNode *p = st;while(p){if(p->data == x)p->Freq ++;p=p->next;}//对修改完的链表进行排序p=st;while(p!=NULL){if(p->Freq < p->LLink->Freq){DNode *pre = p;while(pre->LLink !=NULL && pre->LLink->Freq < p->Freq)pre=pre->LLink;//将p插入到pre的前面p->LLink->RLink = p->RLink;		//摘下p结点P->RLink->LLink = p->LLink;p->RLink = pre;			//p插入pre左边p->LLink = pre->LLink;pre->LLink->RLink = p;pre->LLink = p;}}
}/*********************************计专真题*****************************************/
//2021计专
> 编写函数，统计一个字符中不同字符出现的次数，若某字符连续出现多次，要求多次出现按只出现一次计算。
如abcbbbd中，b的出现次数为2```cpp
void Times(char s[]){int i=0;char str[MaxSize];int cishu[MaxSize];	//cishu[i]表示str[i]的出现次数int k=-1,j;while(s[i]!='\0'){if(i!=0 && s[i]==s[i-1]){i++;continue;}for(j=0;j<=k;j++){if(s[i] == str[j]){cishu[j] ++;break;}}if(j>k){str[++k] = s[i];cishu[k] = 1;}i++;}}法二 这个算法思想很好
/*b[i]表示这个字符出现的次数（连续字符算一次） */
void Times(char a[],int n){  //统计出现次数int k=0,b[MaxSize],cishu[MaxSize];char str[MaxSize];for(int i=0;i<n;i++)if(i!=n-1 && a[i] == a[i+1])b[i] = 0;else b[i] = 1;for(int i=0;i<n;i++){if(b[i]){cishu[++k] = 1;str[k] = a[i];for(int j=i+1;j<n;j++){if(a[j] == a[i]){cishu[k] += b[j];b[j] = 0;          //后面每个遍历到的设为0，因为他已经加到前面去了}}}}
}

2.编写函数成反转链表，给定一个链表，从表头开始每两个相邻的节点为一对，反转每一对中的两个节点。要求交换借鉴的位置，不是交换结点的值，整体顺序不变。若末尾是单个节点，则该节点的位置不变。如：12345 为21435

void sort(LNode *&st){LNode *p = st,*pre,*r,*dummyHead = (LNode *)malloc(sizeof(LNode));dummyHead->next = st;st=dummyHead;pre=st;p=pre->next;r=p->next;while(r!=NULL){if(p!=NULL && r!=NULL){     //节点为pre p rpre->next = p->next;p->next = r->next;r->next = p;}pre=pre->next->next;       //pre指向原来的rif(pre->next!=NULL) p=pre->next;else break;                 //有偶数个节点 恰好交换完if(p->next!=NULL) r=p->next;else break;                 //有奇数个节点 恰好交换完 只剩最后一个r=NULL}
}

3.给定一颗二叉树，若二叉树中的某个节点，其左子树的所有节点值和与右子树的所有节点之和相等，则称该节点为平衡节点。编写函数，判断节点值为整数的二叉树是否存在平衡节点
/*
思想：递归返回以当前节点为根的所有节点之和。
怎样就有平衡节点呢？
当前节点为平衡节点(st->lchild 返回的节点之和==st->rchild 返回的节点之和) ||左节点为平衡节点|| 右节点为平衡节点
*/
int sum(BTNode *st){ //返回以st为根的所有节点值之和
if(st == NULL) return 0;
return st->data + sum(st->lchild) + sum(st->rchild);
}

int check(BTNode *st){
if(st == NULL) return 0;
if(sum(st->lchild)==sum(st->rchild)) return 1;
else if(check(st->lchild) || check(st->rchild)) return 1;
return 0;
}

4.给定一个元素值都大于0的整数集合，编写函数，计算如下条件的一个最大子集1.子集中元素互不相等 2.子集中任意两个元素大者除以小者的余数为0
/*思想：大的除以小的余数为0，说明大的除以小的是整除。
依旧是二进制的思想(集合一般都要用二进制的思想枚举)
一共n个元素，每个元素有选与不选两种情况，所以有2^n种情况。
如何判断第i个元素取不取？
看二进制表示上第i个元素是0还是1.如何才能看到第i个元素是0是1呢？
设当前状态用state表示，1<<i表示100000(i-1个0)，如果state&(1<<i)==1说明取到了第i个元素
*/

void f(int a[],int n){
for(int i=0;i<n;i++){
for(int j=0;j<n-i-1;j++){
if(a[j] > a[j+1]){
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
int b[MaxSize],count;
int res[MaxSize]; //存储最大子集
int max = 0;
for(int i=0;i<(1<<n);i++){
count = -1;
for(int j=0;j<n;j++){
if(i&(1<<j)) //选第j个元素
b[++count] = a[j];
}
int flag = 1; //检查是否满足最大子集
if(count > max){
//看是否满足互不相等 任意大的除以小的可以整除 所以说这里要排序一下 好判断是否有相等的情况
for(int j=1;j<count;j++){
if(b[j] == b[j-1]){
flag = 0;
break;
}
}
for(int j=1;j<count;j++){
if(b[j] % b[j-1]){
flag = 0;
break;
}
}
if(flag) //满足两个条件
{
for(int j=0;j<=count;j++)
res[j] = b[j];
max = count;
}
}
}
for(int i=0;i<=max;i++) printf("%d ",res[i]);
}

//2020计专

1 判断从u到v是否有路径
//图邻接表
typedef struct ArcNode{
int adjvex;
struct ArcNode *next;
}ArcNode;
typedef struct VNode{
int data;
struct AcrNode *first;
};
typedef struct ALGraph{
VNode adjlist[MaxSize];
int arcnum,vexnum;
};
void IsPath(ALGraph *G,int u,int v,int &find,int vis[]){
//DFS 好写
if(u==v){
find = 1;
return;
}
for(ArcNode *p = G->adjlist[u].first;p!=NULL;p=p->next){
if(!vis[p->adjvex]){
vis[p->adjvex] =1;
IsPath(G,p->adjvex,v,find,vis);
}
}
}

//链表的合并 按升序合并为1个链表
void merge(LNode *st1,LNode *st2){
LNode *st,p,q,r,r1;
st = (LNode *malloc(sizeof(LNode)));
r=st;
p=st1,q=st2;
while(p!=NULL && q!=NULL){
if(p->data < q->data){
r1 = p->next;
r->next=p;
r=p;
p=r1;
}
else{
r1 = q->next;
r->next = q;
r=q;
q=r1;
}
}
if(p!=NULL) r->next = p;
if(q!=NULL) r->next = q;
}

计算数组的最大滑动窗口数 最大连续子集
/f[i]表示以a[i]结尾的连续子集的大小/
void fun(int a[],int n){
int f[MaxSize],max=-1;
f[1] = a[1];
for(int i=2;i<=n;i++){
if(f[i-1] > 0){
f[i] = a[i] + f[i-1];
}
else f[i] = a[i];
if(f[i] > max) max =f[i];
}
}

2删除链表中的重复元素
void del_same(LNode *st){
LNode *pre,*p,*r;
pre=st,p=pre->next;
while(pre!=NULL){
p=pre->next;
while(p->next!=NULL && p->next->data != pre->data)
{
p=p->next;
}
if(p->next->data==pre->data){
r=p->next;
p->next = r->next;
free®;
}
pre=pre->next;
}
}

递归判断一个二叉树是否对称
int symmetry(BTNode *st){
if(stNULL || st->lchildNULL&&st->rchildNULL) return 1;
if(st->lchild!=NULL && st->rchildNULL) return 0;
if(st->rchild!=NULL && st->lchildNULL) return 0;
if(st->lchild->datast->rchild->data)
return symmetry(st->lchild) && symmetry(st->rchild);
return 0;
}

计算数组的连续子集中元素的和，将和最大的数组输出
void fun(int a[],int n){
int f[MaxSize]; //f[i]表示以a[i]结尾的最大连续子集和
f[0] = a[0];
int head=0,tail;
int max = -INF,maxhead,maxtail;
for(int i=1;i<n;i++){
if(f[i-1] > 0){
f[i] = f[i-1] + a[i];
tail = i;
}
else{
if(max < f[i-1]){
max = f[i-1];
maxhaed = head;
maxtail = i-1;
head = i;
}
}
}
}

/软专真题********/

//2021软专
//先序遍历第k个节点
void pre_k(BTNode *st,int k){
BTNode *p = st,s[MaxSize];
int top = -1;
int i=0;
while(p || top !=-1){
if§{
s[++top] = p;
i++;
if(i==k){
printf("%d ",p->data);
break;
}
p=p->lchild;
}
else{
p=s[top–];
p=p->rchild;
}
}
}

//将中缀表达式转为后缀表达式
int priority(char c){if(c=='+' || c=='-')    return 1;else if(c=='*' || c=='/')    return 2;
}
/*从左到右遍历中缀表达式的每个数字和符号，若是数字则直接输出，
若是符号，则判断其与栈顶符号的优先级，是右括号或者优先级低于栈顶符号，则栈顶元素依次出栈并输出
直到遇到左括号或栈空才将低优先级的那个符号入栈*/
void transfer(char *in,char *post){     //中缀表达式转后缀表达式int i=0;char s[MaxSize];int top = -1,k=-1;while(in[i]!='\0'){if(in[i]>='0'&&in[i]<='9')  post[++k] = in[i];else if(in[i] == ')'){  //遇到右括号 栈中一直往外弹，直到左括号while(top!=-1 && s[top] != '('){post[++k] = s[top--];}top--;  //弹出左括号}else if(in[i] == '(') s[++top] = in[i];else{   //说明不是括号 是+-*///当前栈顶元素优先级大于当前的while(top!=-1 && priority(s[top]) > priority(in[i])){post[++k] = s[top--];}s[++top] = in[i];   //当前元素入栈}i++;}while(top!=-1) post[++k] = s[top--];    //栈中可能还有元素 需要全部进入postpost[++k] = '\0';
}

//后缀表达式求解 leecode  https://leetcode.cn/problems/8Zf90G/
int evalRPN(char ** tokens, int tokensSize){int s[tokensSize],top = -1;int i=0;while(i<tokensSize){char *token = tokens[i];if(token[0] >= '0' && token[0] <='9' || strlen(token) > 1)   //是数字(正数或者开头是-的负数！) 直接入栈s[++top] = atoi(token);  //atoi[str] :将str转为intelse{int n2 = s[top--];int n1 = s[top--];int res;switch(token[0]){case '+':   res = n1+n2; break;case '-':   res = n1-n2; break;case '*':   res = n1*n2; break;case '/':    res = n1/n2; break;}s[++top] = res;}i++;}return s[top];
}

高级语言：

1.一个二维数组，每一行存放一个字符串，比较字符串并排序

/*字符串的交换用什么？新建一个字符数组，用strcpy。二维数组就strcpy(des,sour) 交换二维数组中的一行字符串就用str[i]*/
void sort(char s[MaxSize][MaxSize],int n){for(int i=0;i<n;i++){for(int j=0;j<n-i-1;j++){if(strcmp(s[j],s[j+1]) > 0){char temp[MaxSize];strcpy(temp,s[j]);strcpy(s[j],s[j+1]);strcpy(s[j+1],temp);}}}
}

2.一行n个框，三个颜色，每个相邻的框颜色不能相同，用递归写出有多少种方法

int f(int n) //n个框的总方案
{if(n==1)    return 3;return 2*f(n-1);    //第n个选了一个，n-1可以选2个
}

3.定义结构体，链表输入学生数据，再输入到文件中
/*
typedef struct LNode{
char sex[10];
char name[10];
int age;
struct LNode *next;
}LNode;
*/
void build_list(LNode *head){
LNode *p = head;
LNode *t,*r;
t = (LNode *)malloc(sizeof(LNode));
while(scanf(“%s %s %d”,t->sex,t->name,&t->age)!=EOF){
r->next = t;
r = t;
t = (LNode *)malloc(sizeof(LNode)); //在新建一个 方便下次输入数据
}
r->next = NULL; //最后链表尾置为NULL
}

void ListToFile(LNode *head){ //将学生数据从链表输入到文件
FILE *fp = fopen(“student.txt”,“w”);
if(fp == NULL)
return;
LNode *p = head;
while(p!=NULL){
fprintf(fp,“%s %s %d\n”,p->sex,p->name,p->age);
p=p->next;
}
fclose(fp); //关闭水龙头
}

将该链表按性别拆分为两个链表并排序，再写入到两个文件中
void sort(LNode *&st){
LNode *dummyHead = (LNode *)malloc(sizeof(LNode));
dummyHead->next = st;
st = dummyHead;
LNode *pre = st,*p=pre->next,*r;
pre->next = NULL;
while(p!=NULL){
r = p->next;
pre=st;
while(pre->next!=NULL && pre->next->age < p->age)
pre=pre->next;
p->next = pre->next;
pre->next = p;
p=r;
}
}
void split(LNode *head){
LNode *men,*women,*rm,*rw;
men = (LNode *)malloc(sizeof(men));
women = (LNode *)malloc(sizeof(women));
sort(st); //总的按年龄排序
LNode *p = head;
while(p!=NULL){
if(strcmp(p->sex,“女”)==0){ //比较字符串用strcmp 复制字符串用strcpy
rw->next = p;
rw = p;
}
else if(strcmp(p->sex,“男”)==0){
rm->next = p;
rm = p ;
}
p=p->next;
}
rw->next = NULL;
rm->next = NULL; //尾结点分别置空
FILE *fp1 = fopen(“man.txt”,“w”);
FILE *fp2 = fopen(“woman.txt”,“w”);
p=men;
while(p!=NULL){
fprintf(fp1,“%s %s %d\n”,p->name,p->sex,p->age);
p=p->next;
}
fclose(fp1); //打开水龙头就要关上

p=women;
while(p!=NULL){fprintf(fp2,"%s %s %d\n",p->name,p->sex,p->age);p=p->next;
} 
fclose(fp2);	//最后关闭水龙头，open和close相对应 

}

//20软专

1 让一个无序的数列负的在前面 正的在后面，算法，思想，时间复杂度
/双指针算法，l r两个指针。设置temp变量存储a[l]。同时右指针向左遍历直到遍历到第一个负数
直接复制到a[l]处 同理左指针向右遍历直到遍历到第一个正数，直接赋值到a[r]处
最后循环退出时，a[l] 赋值为最开始的temp/
void sort(int a[],int n){
int l=0,r=n-1;
int temp = a[l];
while(l<r){
while(l<r && a[r] > 0) r–;
a[l] = a[r];
while(l<r && a[l] < 0) l++;
a[r] = a[l];
}
a[l] = temp;
}

2.删除一个树里指定节点的子树，写出树的存储结构 代码 算法思想 时间复杂度

思想：先序递归遍历找到u结点，然后递归删除它和他的子树
typedef struct BTNode{
int data;
struct BTNode *lchild,*rchild;
};
void del(BTNode *st){
if(st==NULL) return;
del(st->lchild);
del(st->rchild);
free(st);
}

void del_u(BTNode *st,BTNode *u){
if(st == u){
del(u);
return;
}
del_u(st->lchild,u);
del_u(st->rchild,u);
}