数据结构主要算法.docx

1、数据结构主要算法1、 最大公约数 #include void main() int p,r,n,m; printf(请输入两个正整数：); scanf(%d%d,&n,&m); p=n*m; while(m!=0) r=n%m; n=m; m=r; printf(它们的最大公约数是：%dn,n); printf(它们的最小公倍数是：%dn,p/n);2、 最大公约数递归算法 #include int gcd(int a, int b);void main() int n,m; printf(请输入两个正整数：); scanf(%d%d,&n,&m); printf(%dn,gcd(n,m);

2、int gcd(int a, int b) if(a % b = 0) return b; else return gcd(b,a % b); 3、三种递归遍历及叶子结点数 #include #include #include #include typedef struct node char data; struct node *lchild; struct node *rchild;*BiTree;void creatBT(BiTree &T)/建立一个二叉树的函数 char ch; scanf(%c,&ch); if(ch=.) T=NULL;/ . 代表空子树； else T=(nod

3、e *)malloc(sizeof(node);/分配一个node的空间 if(!T)exit(0); T-data = ch;/给T赋值 creatBT(T-lchild);/给左子树赋值 creatBT(T-rchild);/给右子树赋值 void pre_order(node *T)/前序遍历二叉树 if(T) printf(%c ,T-data); pre_order(T-lchild); pre_order(T-rchild); void mid_order(node *T)/中序遍历二叉树 if(T) mid_order(T-lchild); printf(%c ,T-data);

4、 mid_order(T-rchild); void behind_order(node *T)/后序遍历二叉树 if(T) behind_order(T-lchild); behind_order(T-rchild); printf(%c ,T-data); void CountLeaf (BiTree T, int &count) if ( T ) if (!T-lchild)& (!T-rchild) count+; / 对叶子结点计数 CountLeaf( T-lchild, count); CountLeaf( T-rchild, count); / if / CountLeafin

5、t main() node *T; int count=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); return 0;3、 无向

6、图的深度优先和广度优先遍历 /以邻接表作为图的存储结构，实现连通无向图的深度优先和广度优先遍历。#include#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;typedef struct Node int elem; struct Node *next;Node,*QNode;typedef struct QNode front; QNode rear;Queue;#define MAX 20typedef struct ArcNode

7、/表结点 int adjvex; /该边所指向的顶点的位置 struct ArcNode *nextarc; /指向下一条边ArcNode;typedef struct VNode /头结点 int data; /顶点信息 ArcNode *firstarc; /指向第一条依附该结点的边的指针VNode,AdjListMAX;typedef struct AdjList vertices; /一维数组（头结点） int vexnum; /结点的个数 int arcnum; /边的条数Graph;Status InitQueue(Queue *Q) Q-front=Q-rear=(QNode)m

8、alloc(sizeof(Node); if(!Q-front) exit(OVERFLOW); Q-front-next=NULL; return OK;Status EnQueue(Queue *Q,int e) QNode p=(QNode)malloc(sizeof(Node); if(!p) exit(OVERFLOW); p-elem=e; p-next=NULL; Q-rear-next=p; Q-rear=p; return OK;Status DeQueue(Queue *Q,int *e) QNode p; p=Q-front-next; Q-front-next=p-ne

9、xt; if(Q-rear=p) Q-rear=Q-front; *e=p-elem; free(p); return OK;Status QueueEmpty(Queue Q) if(Q.rear=Q.front) return TRUE; else return FALSE;int LocateVex(Graph *G,int v) /返回节点v在图中的位置 int i; for(i=0;ivexnum;+i) if(G-verticesi.data=v) break; else continue; if(ivexnum) return i; else return -1;Status C

10、reateGraph(Graph *G)/以邻接表形式创建无向连通图G int m,n,i,j,k,v1,v2,flag=0; ArcNode *p1,*q1,*p,*q; printf(Please input the number of VNode: ); scanf(%d,&m); printf(Please input the number of ArcNode: ); scanf(%d,&n); G-vexnum=m; /顶点数目 G-arcnum=n; /边的数目 for(i=0;ivexnum;+i) G-verticesi.data=i+1; /顶点信息 G-verticesi

11、.firstarc=NULL; /顶点信息 printf(Output the message of VNode:n); for(i=0;ivexnum;+i) printf(v%dn,G-verticesi.data); for(k=0;karcnum;+k) printf(Please input the %d edge beginpoint and endpoint: ,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

12、(ArcNode); p-adjvex=j; p-nextarc=NULL; if(!G-verticesi.firstarc) G-verticesi.firstarc=p; else for(p1=G-verticesi.firstarc;p1-nextarc;p1=p1-nextarc); p1-nextarc=p; q=(ArcNode *)malloc(sizeof(ArcNode); q-adjvex=i; q-nextarc=NULL; if(!G-verticesj.firstarc) G-verticesj.firstarc=q; else for(q1=G-vertices

13、j.firstarc;q1-nextarc;q1=q1-nextarc); q1-nextarc=q; else printf(Not hava this edge!n); k=flag; printf(The Adjacency List is:n); /输出邻接表 for(i=0;ivexnum;+i) printf(t%d v%d-,i,G-verticesi.data); p=G-verticesi.firstarc; while(p-nextarc) printf(%d-,p-adjvex); p=p-nextarc; printf(%dn,p-adjvex); return OK;

14、int FirstAdjVex(Graph G,int v)/返回v的第一个邻接顶点 if(G.verticesv.firstarc) return G.verticesv.firstarc-adjvex; else return -1;int NextAdjVex(Graph G,int v,int w)/返回v中相对于w的下一个邻接顶点 int flag=0; ArcNode *p; p=G.verticesv.firstarc; while(p) if(p-adjvex=w) flag=1; break; p=p-nextarc; if(flag & p-nextarc) return

15、p-nextarc-adjvex; else return -1;int VisitedMAX;void DFS(Graph G,int v)/深度优先遍历 int w; Visitedv=TRUE; printf(v%d ,G.verticesv.data); for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w) if(!Visitedw) DFS(G,w);void DFSTraverse(Graph G) int v; for(v=0;vG.vexnum;+v) Visitedv=FALSE; for(v=0;vG.vexnum;+v) if(!V

16、isitedv) DFS(G,v); /递归void BFSTraverse(Graph G)/广度优先遍历 int v,v1,w; Queue q; /定义一个队列 for(v=0;vG.vexnum;+v) Visitedv=FALSE; InitQueue(&q); /初始化队列 for(v=0;v=0;w=NextAdjVex(G,v1,w) if(!Visitedw) Visitedw=TRUE; printf(v%d ,G.verticesw.data); EnQueue(&q,w); main() Graph G; CreateGraph(&G); printf(Depth Fi

17、rst Search:n); DFSTraverse(G); printf(nBreadth First Search:n); BFSTraverse(G); printf(n); getchar();4、 二叉排序树 #include#include#include#define ERROR 0#define TURE 1#define OK 1typedef struct BiTNodeint data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;/*以下是建立一个二叉排序树*/BiTree CreateBST(BiTree T,int k

18、ey)BiTree Oldp=T;BiTree p=T;int flag;if(T=NULL)T=(BiTree)malloc(sizeof(BiTNode);T-data=key;T-lchild=T-rchild=NULL;elsewhile(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;elseOldp-rchild

19、=(BiTree)malloc(sizeof(BiTNode); Oldp-rchild-data=key;Oldp-rchild-lchild=Oldp-rchild-rchild=NULL;return T; void InOrder(BiTree T)if(T)InOrder(T-lchild);printf(%d#,T-data);InOrder(T-rchild);/*以下是在一个二叉排序树查找一个数是否存在*/int SearchBST(BiTree T,int key)BiTree p=T;if(T=NULL)return 0;while(p)if(p-data=key)retu

20、rn 1;if(keydata)p=p-lchild;/在左子树中继续查找 elsep=p-rchild;/在右子树中继续查找 return 0; /*以下是在一个二叉排序树插入一个给定的值*/int InsertBST(BiTree T,int key)BiTree s,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-l

21、child:p-rchild;if(keyf-data)f-rchild=s;elsef-lchild=s;InOrder(T);printf(n);return 1;elsereturn 0;/*以下是在一个二叉排序树删除一个给定的值*/BiTree Delete(BiTree p,int key) BiTree s;if(p=NULL)return 0;elseif(keydata)p-lchild=Delete(p-lchild,key);elseif(keyp-data)p-rchild=Delete(p-rchild,key);else if(p-lchild=NULL&p-rchi

22、ld=NULL)free(p);else if(p-lchild!=NULL&p-rchild=NULL)free(p);p=p-lchild;else if(p-rchild!=NULL&p-lchild=NULL)free(p);p=p-rchild; else if(p-rchild&p-lchild)s=p-lchild; while(s-rchild!=NULL)s=s-rchild;p-lchild=Delete(p-lchild,p-data);return p;/*主函数*/void main()BiTree T;int i=0,key;T=NULL;for(;i6;i+)pr

23、intf(输入第%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、 排序 #includetypedef struct int r20;

24、 int length;sqlist; /*堆排序*/void heapadjust(sqlist &H,int s,int m) int j; int rc; rc=H.rs; for(j=2*s;j=m;j*=2) if(jm&(H.rjH.rj+1) j+; if(!(rc0;i-) heapadjust(H,i,H.length); for(i=H.length;i1;i-) temp=H.r1; H.r1=H.ri; H.ri=temp; heapadjust(H,1,i-1); /*快速排序*/int partition(sqlist &H,int low,int high) int pivotkey; H.r0=H.rlow; pivotkey=H.rlow; pivotkey=H.rlow; while(lowhigh) while(low=pivotkey) high-; H.rlow=H.rhigh; while(lowhigh&(H.rlow=pivotkey) low+; H.rhigh=H.rlow; H.rlow=H.r0; return low; void Qsort(sqlist &H,int low,int hi