经典算法.docx
《经典算法.docx》由会员分享，可在线阅读，更多相关《经典算法.docx（31页珍藏版）》请在冰点文库上搜索。
经典算法
第一块：
排序
#defineN10
1、快速排序
intPartition（intx[],inti,intj）{
intpivot=x[i];
while（iwhile（i=pivot）
j--;
if（ix[i++]=x[j];
while（ii++;
if（ix[j--]=x[i];
}
x[i]=pivot;
returni;
}
voidQuitSort（intx[],intlow,inthigh）{
intpivotpos;
if（lowpivotpos=Partition（x,low,high）;
QuitSort（x,low,pivotpos-1）;
QuitSort（x,pivotpos+1,high）;
}
}
2、希尔排序
voidShellSort（intA[],intn）{
intdt,i,j,temp;
for（dt=n/2;dt>=1;dt-=2）{
for（i=dt;iif（A[i-dt]<=A[i]）
continue;
temp=A[i];
for（j=i-dt;j>=0&&tempA[j+dt]=A[j];
A[j+dt]=temp;
}
}
}
3、冒泡排序
voidBubbleSort（intx[],intn）{
boolswapped;
do{
swapped=false;
for（inti=0;iif（x[i]>x[i+1]）{
inttemp=x[i];
x[i]=x[i+1];
x[i+1]=temp;
swapped=true;
}
}
n--;
}while（swapped）;
}
4、堆排序
voidshift（inta[],inti,intm）{
intk,t;
t=a[i];
k=2*i+1;
while（kif（（kk++;
if（ta[i]=a[k];
i=k;
k=2*i+1;
}
else
break;
}
a[i]=t;
}
voidheap（inta[],intn）{//a为排序数组，n为数组大小（编号0-n-1）
inti,k;
for（i=n/2-1;i>=0;i--）
shift（a,i,n）;
for（i=n-1;i>=1;i--）{
k=a[0];
a[0]=a[i];
a[i]=k;
shift（a,0,i）;
}
}
5、二路归并排序
voidMerge（int*R,intlow,intm,inthigh）{
//将两个有序的子文件R[low..m]和R[m+1..high]
//归并成一个有序的子文件R[low..high]
inti=low,j=m+1,p=0;//置初始值
int*R1;//R1是局部向量
if（（R1=（int*）malloc（（high-low+1）*sizeof（int）））==NULL）
return;//申请空间失败
while（i<=m&&j<=high）//两子文件非空时取其小者输出到R1[p]上
R1[p++]=（R[i]<=R[j]）?
R[i++]:
R[j++];
while（i<=m）//若第1个子文件非空，则复制剩余记录到R1中
R1[p++]=R[i++];
while（j<=high）//若第2个子文件非空，则复制剩余记录到R1中
R1[p++]=R[j++];
for（p=0,i=low;i<=high;p++,i++）
R[i]=R1[p];//归并完成后将结果复制回R[low..high]
}
voidMergeSort（intR[],intlow,inthigh）{
//用分治法对R[low..high]进行二路归并排序
intmid;
if（lowmid=（low+high）/2;//分解
MergeSort（R,low,mid）;//递归地对R[low..mid]排序
MergeSort（R,mid+1,high）;//递归地对R[mid+1..high]排序
Merge（R,low,mid,high）;//组合，将两个有序区归并为一个有序区
}
}
6、双向冒泡排序
voidD_Bubble（intA[],intn）{
inti=0,flag=1,j;
while（flag&&iflag=0;
for（j=n-i-1;j>=1;j--）
if（A[j-1]>A[j]）{
swap（A[j-1],A[j]）;
flag=1;
}
for（j=i+1;jif（A[j]>A[j+1]）{
swap（A[j],A[j+1]）;
flag=1;
}
i++;
}
}
第二块：
顺序表
#defineMaxSize50
structSqList{
intdata[MaxSize];//存放顺序表的元素
intlength;//存放顺序表的长度
};
/*顺序表的插入操作*/
boolInsertList（SqList&L,inti,inte）{
//在顺序表中第i个位置插入数值e
intj;
if（i<1||i>L.length）
returnfalse;
if（L.length>MaxSize）
returnfalse;
for（j=L.length;j>=i;j--）//将第i个起得数据后移
L.data[j]=L.data[j-1];
L.data[j]=e;
L.length++;
returntrue;
}
/*顺序表的删除*/
boolDeleteList（SqList&L,inti）{
//删除顺序表中第i个元素
intj;
if（i<1||i>L.length）
returnfalse;
for（j=i;jL.data[j-1]=L.data[j];
L.length--;
returntrue;
}
/*顺序表的按值查找*/
intLocateElem（SqList&L,inte）{
for（inti=0;iif（L.data[i]==e）
returni+1;
return0;
}
/*顺序表初始化*/
{
SqListlist;
intA[5]={1,4,7,2,10};
for（inti=0;i<5;i++）
list.data[i]=A[i];
list.length=5;
}
/*删除顺序表中最小值*/
boolDel_Min（SqList&L）{
if（L.length==0）
returnfalse;
inttemp=0;
for（inti=0;iif（L.data[i]temp=i;
L.data[temp]=L.data[L.length-1];
L.length--;
returntrue;
}
/*删除顺序表中介于s和t之间的所有元素*/
boolDel_S_T（SqList&L,ints,intt）{
intk=0;
if（s>=t||L.length==0）
returnfalse;
for（inti=0;iif（L.data[i]>=s&&L.data[i]<=t）
k++;
else
L.data[i-k]=L.data[i];
}
L.length-=k;
returntrue;
}
/*删除有序顺序表L中在给定值s和t之间的所有元素*/
boolDel_Sq_S_T（SqList&L,ints,intt）{
inti,j;
if（s>=t||L.length==0）
returnfalse;
for（i=0;iif（i>=L.length）
returnfalse;
for（j=i;jfor（;jL.data[i]=L.data[j];
L.length=i;
returntrue;
}
/*删除循序表中值为e的元素*/
boolDel_E（SqList&L,inte）{
intcount=0;
if（L.length==0）
returnfalse;
for（inti=0;iif（L.data[i]==e）
count++;
else
L.data[i-count]=L.data[i];
}
L.length-=count;
returntrue;
}
第三块：
链表
typedefstructLNode{
intdata;//链表数据
structLNode*next;//链表指针
}LNode,*LinkList;
/*头插法-建立单链表*/
LinkListHeadCreate（LinkListla）{
intnum;
la=（LinkList）malloc（sizeof（LNode））;//建立头结点
la->next=NULL;
scanf（"%d",&num）;
while（num!
=10）{
LNode*p=（LinkList）malloc（sizeof（LNode））;
p->data=num;
p->next=la->next;
la->next=p;
scanf（"%d",&num）;
}
returnla;
}
/*尾插法-建立单链表*/
LinkListTailCreate（LinkListla）{
intnum;
la=（LinkList）malloc（sizeof（LNode））;
la->next=NULL;
LinkLists,r=la;
scanf（"%d",&num）;
while（num!
=10）{
s=（LinkList）malloc（sizeof（LNode））;
s->data=num;
r->next=s;
r=s;
scanf（"%d",&num）;
}
r->next=NULL;
returnla;
}
/*单链表遍历*/
voidTravelList（LinkListla）{
LinkListp=la->next;
while（p!
=NULL）{
printf（"%d->",p->data）;
p=p->next;
}
printf（"\n"）;
}
/*单链表的按位查找*/
LinkListGetElem（LinkListla,inti）{
intj=1;
LNode*p=la->next;
if（i<1）
returnNULL;
while（p&&jp=p->next;
j++;
}
returnp;
}
/*单链表的按值查找*/
LinkListLocalElem（LinkListla,inte）{
LNode*p=la->next;
while（p!
=NULL&&p->data!
=e）
p=p->next;
returnp;
}
/*单链表插入操作*/
boolInsertList（LinkListla,inti,inte）{
//在la链表中的i位置插入数值e
intj=1;
LinkListp=la,s;
while（p&&jp=p->next;
j++;
}
if（p==NULL）
returnfalse;
if（（s=（LinkList）malloc（sizeof（LNode）））==NULL）
returnfalse;
s->data=e;
s->next=p->next;
p->next=s;
returntrue;
}
/*单链表删除操作*/
boolDeleteList（LinkListla,inti）{
intj=1;
LinkListp=la,q;
while（p&&jp=p->next;
j++;
}
if（p==NULL||p->next==NULL）//表示不存在第i-1个和第i的元素
returnfalse;
q=p->next;
p->next=q->next;
free（q）;
returntrue;
}
/*单链表的表长*/
intLengthList（LinkListla）{
intnLen=0;
LinkListp=la->next;
while（p）{
p=p->next;
nLen++;
}
returnnLen;
}
/*合并两单链表*/
LinkListMergeList（LinkListla,LinkListlb）{
LinkListpa=la->next,pb=lb->next,r;
la->next=NULL;//利用la来存储
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;
}
free（lb）;
returnla;
}
/*查找单链表倒数第k个结点的数值*/
intSearch_K（LinkListla,intk）{
intcount=0;
LinkListp=la->next,q=la->next;
while（p）{
if（countcount++;
else
q=q->next;
p=p->next;
}
if（countreturn0;
else{
printf（"倒数第%d个结点值为:
%d\n",k,q->data）;
return1;
}
}
/*以奇偶方式拆分单链表*/
voidSplit（LinkListL,LinkListlist1,LinkListlist2）{
list1=（LinkList）malloc（sizeof（LNode））;//创建头结点
list2=（LinkList）malloc（sizeof（LNode））;
LinkListpa=list1,pb=list2,p=L->next;
list1->data=0;list2->data=0;//用头结点的数据域记录分链表的长度
while（p）{
pa->next=p;//序号为奇数部分
pa=pa->next;
p=p->next;
list1->data++;
if（p）{
pb->next=p;//序号为偶数部分
pb=pb->next;
p=p->next;
list2->data++;
}
}
pa->next=list1;//构成循环链表
pb->next=list2;
}
/*按位找出单链表中第i个结点*/
voidSearch_I（LinkListla,inti）{
intj=1;
LinkListp=la->next;
if（i<1||la->next==NULL）
return;
while（p&&jp=p->next;
j++;
}
printf（"第%d个元素地址为:
%p，值为%d\n",i,p,p->data）;
}
/*查找带头结点链表中最大结点*/
voidSearch_Max（LinkListla）{
if（la->next==NULL）
return;
LinkListmaxp=la->next,p=maxp->next;
while（p）{
if（maxp->data<=p->data）
maxp=p;
p=p->next;
}
printf（"最大值为:
%d\n",maxp->data）;
}
/*查找链表中具有给定值x的所有结点数*/
intCount_X（LinkListla,inte）{
if（la->next==NULL）
return0;
intcount=0;
LinkListp=la->next;
while（p）{
if（p->data==e）
count++;
p=p->next;
}
returncount;
}
/*查找链表中值最小的结点，并将其置于链表最前*/
voidDelInsertMin（LinkListla）{
LinkListpre=la,minp=pre->next,p=minp;
while（p->next）{//找出最小值的结点
if（p->next->datadata）{
minp=p->next;
pre=p;
}
p=p->next;
}
if（minp!
=la->next）{
pre->next=minp->next;//从链表中移除最小值结点
minp->next=la->next;//头插法插入最小值到链表头
la->next=minp;
}
}
/*将链表数据域大于0的结点放在数据域小于等于0的前面*/
boolResort（LinkListla）{
LinkListpre=la,p=pre->next,q=p;
if（la->next==NULL）
returnfalse;
while（q->next）{
if（q->next->data>0）{
p=q->next;
pre=q;
pre->next=p->next;
p->next=la->next;
la->next=p;
}
else
q=q->next;
}
q->next=NULL;
returntrue;
}
/*对单链表按数值域从小到大排序*/
voidSortList（LinkListla）{
LinkListp=la->next->next,r,q;
la->next->next=NULL;
while（p）{
r=p->next;
q=la->next;
if（p->datadata）{
p->next=q;
la->next=p;
}
else{
while（q->next!
=NULL&&q->next->datadata）
q=q->next;
p->next=q->next;
q->next=p;
}
p=r;}}
/*删除数值域为e的结点*/
voidDel_E（LinkListla,inte）{
LinkListpre=la,p=la->next,r;
while（p）{
r=p->next;
if（p->data==e）{
pre->next=r;
free（p）;
p=r;
}
else{
pre=p;
p=r;
}
}
}
/*删除单链表中数据域相同的结点*/
voidDelSame（LinkListla）{
if（la==NULL||la->next==NULL）
return;
LinkLists=la->next,p,r;
while（s）{//从第一个结点开始遍历，到最后一个结点
p=s;
while（p）{
if（p->next）{
r=p->next;
if（r->data==s->data）{
p->next=r->next;//删除相同值的结点
free（r）;
}
else
p=p->next;
}
else//防止p指向最后一个结点而出现死循环
break;
}
s=s->next;
}
}
第四块：
树
第五块：
栈和队列
1、顺序栈
#defineMaxSize50
structSqStack{
intdata[MaxSize];//顺序栈数据
inttop;//栈顶指针
};
/*初始化栈*/
voidInitStack（SqStack&s）{
s.top=-1;
}
/*入栈*/
boolPush（SqStack&s,intx）{
if（s.top==
升级会员 