//2015年 删除单链表中data绝对值相等的结点，仅保留第一出现的结点而删除其余绝对值相等的结点
//算法思想：用计数排序思想，借助一个一维数组
void DeleteABS(LNode *L,int n)
{
LNode *p=L->link,*q;//p指向下一节点，q用来指向被删除的结点
int *a=new int[n];//申请辅助数组
int temp;
for(int i=0;i<n;i++)
{
a[i]=0;//初始化辅助数组的元素
}
while(p!=NULL)
{
if(p->data>0)
{
temp=p->data;
}else
{
temp=-p->data;
}
if(a[temp]==0)
{
a[m]=1;//标记，前面已经有这个数了
}else
{
q=p;
p=p->link;
}
}
delete(a);//释放掉a的空间
}
//2016年真题
//用快速排序实现
void Sort(ElemType data[],int n)
{
QuickSort(data,0,n);
//此时，序列已经递增有序
int s1=s2=0;
for(int i=0;i<n;i++)
{
if(i<n/2)
{
s1=s1+i;
}else
{
s2+=i;
}
}
return s2-s1;
}
void QuickSort(ElemType data[],int low,int high);
{
if(low<high)
{
int pivotPosPartition(data,low,high);
QuickSort(data,low,pivotPos-1);
QuickSort(data,pivotPos+1,high);
}
}
int Partition(ElemType data[],int low,int high)
{
ElemType pivot=data[low];//将表中的第一个元素设为枢纽，对表进行划分
while(low<high)
{
while(low<high && data[high]>=pivot)
{
--high;
}
data[low=]=data[high];//将比枢纽小的元素移动到左端
while(low<high && data[low]>=pivot)
{
++low;
}
data[high]=data[low];//将比枢纽打的元素移动到右端
}
data[low]=pivot;
}
//2017年真题 将给定的表达式树转换成等价的中缀表达式(包括括号反映次序)
//算法思想：基于二叉树的中缀遍历，添加适当括号，显然表达式的最外层以及操作数不需要添加括号
void B2E(BTNode *root)
{
}
void B2E(BTNode *root,int deep)
{
if(root==NULL)
{
printf("NULL");
}
else if(root->lchild==NULL && root->rchild==NULL)
{
printf("%s",root->data);
}else
{
if(deep>1)
{
printf("(");
}
B2E(root->lchild,deep+1);
printf("%s",root->data);//输出操作符
B2E(root->=rchild,deep+1);
if(deep>1)
{
printf(")");
}
}
}
//2018年真题，包含n个整数的数组，请设计一个时间上尽可能高效的算法，找出数组中未出现的最小正整数
//算法思想是计数排序，用一个数组计数，也就是用空间换时间
int FindMinNum(int data[],int n)
{
int *help=new int[n];//申请辅助数组
for(int i=0;i<n;i++)
{
help[i]=0;//初始化辅助数组
}
for(int i=0;i<n;i++)
{
if(data[i]>0 && data[i]<=n)
{
help[data[i]-1];
}
}
for(int i=0;i<n;i++)//扫描数组，找到目标值
{
if(help[i]==0)
{
break;
}
}
}
//2019年真题
/*
1.先找出链表的中间结点，为此设置两个指针p和q，指针p每次都一步，指针q每次走两步，当指针q到达链尾时，指针p正好在链表的中间
2.然后将L的后半段结点原地逆置
3.从单链表前后两段中一次各取一个结点按要求排序
*/
typedef struct node
{
int data;
struct node *next;
}Node;
void change_list(Node *head)
{
Node *p,*q,*r,*s;
p=q=head;
while(q->next!=NULL)//寻找中间结点
{
p=p->next;//p走一步
q=q->next;
if(q->next!=NULL)
{
q=q->next;//q走两步
}
}
q=p-next;//p所指的结点为中间结点，q指向后半的首个结点
p->next=NULL;
while(q!=NULL)
{
r=q;
q=q->next;
r.next=p.next;
p.next=r;
}
s=head.next;//s指向前半段的第一个数据结点
q=p->next;//q指向后半段的第一个结点
p->next=NULL;
while(q!=NULL)
{
r=q->next;//将链表后半段的结点插入到指定的位置
q->next=s->next;
s->next=q;
s=q->next;
q=r;
}
}
void func(Node *head)
{
Reverse()
}
void Reverse(Node *head)
{
Node* p=head->next;//p指向第一个结点
Node *q;
head.next=NULL;
while(p!=NULL)
{
q=p;
p=p->next;
q->next=head.next;
head.next=q;
}
}
//2020年真题
//定义三元组(a,b,c)的距离D=|a-b|+|b-c|+|c-a|。给定三个整数数组，按升序存储。设计一个尽可能高效(既要时间上高效，又要在空间上高效)的算法，计算并输出所有可能的三元组(a,b,c)中距离最小
//我的想法：无脑暴力，三层for循环
//时间复杂度O(n^3)
//空间复杂度O(1)
int* func(int s1,int n1,int s2,int n2,int s3,int n3)
{
int *res=new int[3];
int i=j=k=sum=0;
sum=abs(s1[i])+abs(s2[j])+abs(s3[k]);
for(int index1;index1<n1;i++)
{
for(int index2;index2<n2;j++)
{
for(int index3=0;index3<n3;k++)
{
if(abs(s1[index1])+abs(s2[index2])+abs(s3[index3])<sum)
{
i=index1;
j=index2;
k=index3;
sum=abs(s1[i])+abs(s2[j])+abs(s3[k]);
}
}
}
}
res[0]=s1[i];
res[1]=s2[j];
res[2]=s3[k];
return res;
}
int abs(int num)
{
if(num>0)
{
return num;
}else
{
return -num;
}
}
//树的层序遍历
void LevelOrder(BiTree T)
{
InitQueue(Q);//初始化辅助队列
BiTree p;
EnQueue(Q,T);
while(!IsEmpty(Q))
{
DeQueue(Q,p);
visit(p);
if(p->lchild!=NULL)
{
EnQueue(Q,p->lchild);
}
if(p->rchild!=NULL)
{
EnQueue(Q,p->rchild);
}
}
}