数据结构主要算法.docx
《数据结构主要算法.docx》由会员分享，可在线阅读，更多相关《数据结构主要算法.docx（26页珍藏版）》请在冰点文库上搜索。
数据结构主要算法
1、最大公约数
#include
voidmain（）
{
intp,r,n,m;
printf（"请输入两个正整数：
"）;
scanf（"%d%d",&n,&m）;
p=n*m;
while（m!
=0）
{
r=n%m;
n=m;
m=r;
}
printf（"它们的最大公约数是：
%d\n",n）;
printf（"它们的最小公倍数是：
%d\n",p/n）;
}
2、最大公约数递归算法
#include
intgcd（inta,intb）;
voidmain（）
{
intn,m;
printf（"请输入两个正整数：
"）;
scanf（"%d%d",&n,&m）;
printf（"%d\n",gcd（n,m））;
}
intgcd（inta,intb）{
if（a%b==0）{returnb;}
else{returngcd（b,a%b）;}
}
3、三种递归遍历及叶子结点数
#include
#include
#include
#include
typedefstructnode
{
chardata;
structnode*lchild;
structnode*rchild;
}*BiTree;
voidcreatBT（BiTree&T）//建立一个二叉树的函数
{
charch;
scanf（"%c",&ch）;
if（ch=='.'）
{
T=NULL;//.代表空子树；
}
else
{
T=（node*）malloc（sizeof（node））;//分配一个node的空间
if（!
T）exit（0）;
T->data=ch;//给T赋值
creatBT（T->lchild）;//给左子树赋值
creatBT（T->rchild）;//给右子树赋值
}
}
voidpre_order（node*T）//前序遍历二叉树
{
if（T）
{
printf（"%c",T->data）;
pre_order（T->lchild）;
pre_order（T->rchild）;
}
}
voidmid_order（node*T）//中序遍历二叉树
{
if（T）
{
mid_order（T->lchild）;
printf（"%c",T->data）;
mid_order（T->rchild）;
}
}
voidbehind_order（node*T）//后序遍历二叉树
{
if（T）
{
behind_order（T->lchild）;
behind_order（T->rchild）;
printf（"%c",T->data）;
}
}
voidCountLeaf（BiTreeT,int&count）{
if（T）{
if（（!
T->lchild）&&（!
T->rchild））
count++;//对叶子结点计数
CountLeaf（T->lchild,count）;
CountLeaf（T->rchild,count）;
}//if
}//CountLeaf
intmain（）
{
node*T;
intcount=0;
printf（"请输按先序序列输入一串字符,当子树为空时,用.来代替\n"）;
creatBT（T）;//建树
printf（"建树成功,T指向二叉树的根!
\n"）;
printf（"\n前序遍历二叉树的结果是:
"）;
pre_order（T）;
printf（"\n中序遍历二叉树的结果是:
"）;
mid_order（T）;
printf（"\n后序遍历二叉树的结果是:
"）;
behind_order（T）;printf（"\n"）;
CountLeaf（T,count）;
printf（"%d",count）;
system（"pause"）;
return0;
}
3、无向图的深度优先和广度优先遍历
//以邻接表作为图的存储结构，实现连通无向图的深度优先和广度优先遍历。
#include
#include
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineOVERFLOW-2
typedefintStatus;
typedefstructNode
{
intelem;
structNode*next;
}Node,*QNode;
typedefstruct
{
QNodefront;
QNoderear;
}Queue;
#defineMAX20
typedefstructArcNode//表结点
{
intadjvex;//该边所指向的顶点的位置
structArcNode*nextarc;//指向下一条边
}ArcNode;
typedefstructVNode//头结点
{
intdata;//顶点信息
ArcNode*firstarc;//指向第一条依附该结点的边的指针
}VNode,AdjList[MAX];
typedefstruct
{
AdjListvertices;//一维数组（头结点）
intvexnum;//结点的个数
intarcnum;//边的条数
}Graph;
StatusInitQueue（Queue*Q）
{
Q->front=Q->rear=（QNode）malloc（sizeof（Node））;
if（!
Q->front）exit（OVERFLOW）;
Q->front->next=NULL;
returnOK;
}
StatusEnQueue（Queue*Q,inte）
{
QNodep=（QNode）malloc（sizeof（Node））;
if（!
p）exit（OVERFLOW）;
p->elem=e;
p->next=NULL;
Q->rear->next=p;
Q->rear=p;
returnOK;
}
StatusDeQueue（Queue*Q,int*e）
{
QNodep;
p=Q->front->next;
Q->front->next=p->next;
if（Q->rear==p）
Q->rear=Q->front;
*e=p->elem;
free（p）;
returnOK;
}
StatusQueueEmpty（QueueQ）
{
if（Q.rear==Q.front）
returnTRUE;
else
returnFALSE;
}
intLocateVex（Graph*G,intv）//返回节点v在图中的位置
{
inti;
for（i=0;ivexnum;++i）
if（G->vertices[i].data==v）break;
elsecontinue;
if（ivexnum）
returni;
else
return-1;
}
StatusCreateGraph（Graph*G）
{//以邻接表形式创建无向连通图G
intm,n,i,j,k,v1,v2,flag=0;
ArcNode*p1,*q1,*p,*q;
printf（"PleaseinputthenumberofVNode:
"）;
scanf（"%d",&m）;
printf（"PleaseinputthenumberofArcNode:
"）;
scanf（"%d",&n）;
G->vexnum=m;//顶点数目
G->arcnum=n;//边的数目
for（i=0;ivexnum;++i）
{
G->vertices[i].data=i+1;//顶点信息
G->vertices[i].firstarc=NULL;
}//顶点信息
printf（"OutputthemessageofVNode:
\n"）;
for（i=0;ivexnum;++i）
printf（"v%d\n",G->vertices[i].data）;
for（k=0;karcnum;++k）
{
printf（"Pleaseinputthe%dedgebeginpointandendpoint:
",k+1）;
scanf（"%d%d",&v1,&v2）;
i=LocateVex（G,v1）;
j=LocateVex（G,v2）;
if（i>=0&&j>=0）
{
++flag;
p=（ArcNode*）malloc（sizeof（ArcNode））;
p->adjvex=j;
p->nextarc=NULL;
if（!
G->vertices[i].firstarc）
G->vertices[i].firstarc=p;
else
{
for（p1=G->vertices[i].firstarc;p1->nextarc;p1=p1->nextarc）;
p1->nextarc=p;
}
q=（ArcNode*）malloc（sizeof（ArcNode））;
q->adjvex=i;
q->nextarc=NULL;
if（!
G->vertices[j].firstarc）
G->vertices[j].firstarc=q;
else
{
for（q1=G->vertices[j].firstarc;q1->nextarc;q1=q1->nextarc）;
q1->nextarc=q;
}
}
else
{
printf（"Nothavathisedge!
\n"）;
k=flag;
}
}
printf（"TheAdjacencyListis:
\n"）;//输出邻接表
for（i=0;ivexnum;++i）
{
printf（"\t%dv%d->",i,G->vertices[i].data）;
p=G->vertices[i].firstarc;
while（p->nextarc）
{
printf（"%d->",p->adjvex）;
p=p->nextarc;
}
printf（"%d\n",p->adjvex）;
}
returnOK;
}
intFirstAdjVex（GraphG,intv）
{//返回v的第一个邻接顶点
if（G.vertices[v].firstarc）
returnG.vertices[v].firstarc->adjvex;
else
return-1;
}
intNextAdjVex（GraphG,intv,intw）
{//返回v中相对于w的下一个邻接顶点
intflag=0;
ArcNode*p;
p=G.vertices[v].firstarc;
while（p）
{
if（p->adjvex==w）
{
flag=1;
break;
}
p=p->nextarc;
}
if（flag&&p->nextarc）
returnp->nextarc->adjvex;
else
return-1;
}
intVisited[MAX];
voidDFS（GraphG,intv）
{//深度优先遍历
intw;
Visited[v]=TRUE;
printf（"v%d",G.vertices[v].data）;
for（w=FirstAdjVex（G,v）;w>=0;w=NextAdjVex（G,v,w））
if（!
Visited[w]）
DFS（G,w）;
}
voidDFSTraverse（GraphG）
{
intv;
for（v=0;vVisited[v]=FALSE;
for（v=0;vif（!
Visited[v]）
DFS（G,v）;//递归
}
voidBFSTraverse（GraphG）
{//广度优先遍历
intv,v1,w;
Queueq;//定义一个队列
for（v=0;vVisited[v]=FALSE;
InitQueue（&q）;//初始化队列
for（v=0;vif（!
Visited[v]）
{
Visited[v]=TRUE;
printf（"v%d",G.vertices[v].data）;
EnQueue（&q,v）;//顶点入队
while（!
QueueEmpty（q））
{
DeQueue（&q,&v1）;//顶点出队
for（w=FirstAdjVex（G,v1）;w>=0;w=NextAdjVex（G,v1,w））
if（!
Visited[w]）
{
Visited[w]=TRUE;
printf（"v%d",G.vertices[w].data）;
EnQueue（&q,w）;
}
}
}
}
main（）
{
GraphG;
CreateGraph（&G）;
printf（"DepthFirstSearch:
\n"）;
DFSTraverse（G）;
printf（"\nBreadthFirstSearch:
\n"）;
BFSTraverse（G）;
printf（"\n"）;
getchar（）;
}
4、二叉排序树
#include
#include
#include
#defineERROR0
#defineTURE1
#defineOK1
typedefstructBiTNode
{
intdata;
structBiTNode*lchild,*rchild;
}BiTNode,*BiTree;
/**************以下是建立一个二叉排序树****************/
BiTreeCreateBST（BiTreeT,intkey）
{
BiTreeOldp=T;
BiTreep=T;intflag;
if（T==NULL）
{
T=（BiTree）malloc（sizeof（BiTNode））;
T->data=key;
T->lchild=T->rchild=NULL;
}
else
{
while（p）
{
Oldp=p;
p=（flag=keydata）?
p->lchild:
p->rchild;
}
if（flag）{
Oldp->lchild=（BiTree）malloc（sizeof（BiTNode））;
Oldp->lchild->data=key;
Oldp->lchild->lchild=Oldp->lchild->rchild=NULL;
}
else
{
Oldp->rchild=（BiTree）malloc（sizeof（BiTNode））;
Oldp->rchild->data=key;
Oldp->rchild->lchild=Oldp->rchild->rchild=NULL;
}
}
returnT;
}
voidInOrder（BiTreeT）
{
if（T）
{
InOrder（T->lchild）;
printf（"%d#",T->data）;
InOrder（T->rchild）;
}
}
/*****************以下是在一个二叉排序树查找一个数是否存在*************************/
intSearchBST（BiTreeT,intkey）
{
BiTreep=T;
if（T==NULL）
return0;
while（p）
{
if（p->data==key）
return1;
if（keydata）
p=p->lchild;//在左子树中继续查找
else
p=p->rchild;//在右子树中继续查找
}
return0;
}
/************以下是在一个二叉排序树插入一个给定的值*********************************/
intInsertBST（BiTreeT,intkey）{
BiTrees,p,f;
p=T;
f=NULL;
if（!
SearchBST（T,key））{
s=（BiTree）malloc（sizeof（BiTNode））;
if（!
s）{
printf（"申请空间失败！
\n"）;
exit（0）;
}
s->data=key;
s->lchild=NULL;
s->rchild=NULL;
while（p）{
f=p;
p=keydata?
p->lchild:
p->rchild;
}
if（key>f->data）{
f->rchild=s;
}
else
f->lchild=s;
InOrder（T）;
printf（"\n"）;
return1;
}
else
return0;
}
/***********以下是在一个二叉排序树删除一个给定的值*********************************/
BiTreeDelete（BiTreep,intkey）
{
BiTrees;
if（p==NULL）
return0;
else
if（keydata）
p->lchild=Delete（p->lchild,key）;
else
if（key>p->data）
p->rchild=Delete（p->rchild,key）;
else
{
if（p->lchild==NULL&&p->rchild==NULL）
{
free（p）;
}
elseif（p->lchild!
=NULL&&p->rchild==NULL）
{
free（p）;
p=p->lchild;}
elseif（p->rchild!
=NULL&&p->lchild==NULL）
{
free（p）;
p=p->rchild;
}
elseif（p->rchild&&p->lchild）
{
s=p->lchild;
while（s->rchild!
=NULL）
s=s->rchild;
p->lchild=Delete（p->lchild,p->data）;
}
}
returnp;
}
/***********主函数*************/
voidmain（）
{
BiTreeT;
inti=0,key;
T=NULL;
for（;i<6;i++）
{
printf（"输入第%d个关键字：
\n",i+1）;
scanf（"%d",&key）;
T=CreateBST（T,key）;
}
printf（"输入要查找的关键字：
\n"）;
scanf（"%d",&key）;
i=SearchBST（T,key）;
printf（"%d",i）;
printf（"输入要插入的关键字：
\n"）;
scanf（"%d",&key）;
i=InsertBST（T,key）;
printf（"%d",i）;
printf（"输入要删除的关键字：
\n"）;
scanf（"%d",&key）;
T=Delete（T,key）;
if（T）i=1;
printf（"%d",i）;
}
5、排序
#include
typedefstruct{
intr[20];
intlength;
}sqlist;
/**************堆排序*******************/
voidheapadjust（sqlist&H,ints,intm）{
intj;
intrc;
rc=H.r[s];
for（j=2*s;j<=m;j*=2）{
if（jj++;
if（!
（rcbreak;
H.r[s]=H.r[j];
s=j;
}
H.r[s]=rc;
}
voidheapsort（sqlist&H）{
inti;
inttemp;
for（i=H.length/2;i>0;i--）
heapadjust（H,i,H.length）;
for（i=H.length;i>1;i--）{
temp=H.r[1];
H.r[1]=H.r[i];
H.r[i]=temp;
heapadjust（H,1,i-1）;
}
}
/*****************快速排序*************/
intpartition（sqlist&H,intlow,inthigh）{
intpivotkey;
H.r[0]=H.r[low];
pivotkey=H.r[low];
pivotkey=H.r[low];
while（lowwhile（low=pivotkey）
high--;
H.r[low]=H.r[high];
while（lowlow++;
H.r[high]=H.r[low];
}
H.r[low]=H.r[0];
returnlow;
}
voidQsort（sqlist&H,intlow,inthi
升级会员 