数据结构实验四五六

数据结构实验实验四、图遍历的演示。【实验学时】5学时【实验目的】（1） 掌握图的基本存储方法。（2） 熟练掌握图的两种搜索路径的遍历方法。【问题描述】很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示连通的无向图上，遍历全部结点的操作。【基本要求】以邻接多重表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。【测试数据】教科书图7.33。暂时忽略里程，起点为北京。【实现提示】设图的结点不超过30个，每个结点用一个编号表示（如果一个图有n个结点，则它们的编号分别为1，2，n）。通过输入图的全部边输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制。注意，生成树的边是有向边，端点顺序不能颠倒。【选作内容】（1） 借助于栈类型（自己定义和实现），用非递归算法实现深度优先遍历。（2） 以邻接表为存储结构，建立深度优先生成树和广度优先生成树，再按凹入表或树形打印生成树。（3） 正如习题7。8提示中分析的那样，图的路径遍历要比结点遍历具有更为广泛的应用。再写一个路径遍历算法，求出从北京到广州中途不过郑州的所有简单路径及其里程。【源程序】#include #include #include #define MAX_VERTEX_NUM 20#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define TRUE 1#define OK 1#define FALSE 0#define ERROR 0#define OVERFLOW -2typedef enumDG,DN,UDG,UDNGraphKind;/有向图,有向网,无向图,无向网bool visitedMAX_VERTEX_NUM;typedef struct ArcNode int adjvex;/该弧所指向的顶点在数组中的下标 struct ArcNode *nextarc; int *info;/该弧相关信息的指针ArcNode;typedef struct VNode int data;/顶点信息 ArcNode *firstarc;/指向第一条依附该顶点的弧的指针VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices; int vexnum,arcnum;/图的当前顶点数和弧数 int kind;/图的种类标志ALGraph;typedef struct int *base; int *top; int stacksize;SqStack;typedef struct QNode int data; struct QNode *next;QNode,*QueuePtr;typedef struct QueuePtr front; QueuePtr rear;LinkQueue;int LocateVex(ALGraph G,int v)/返回数组下标值 int i; for(i=0;iMAX_VERTEX_NUM;+i) if(G.verticesi.data=v) return i; return -1;void CreateDN(ALGraph &G)/采用邻接表存储表示,构造有向图G(G.kind=DN) int i,j,k;ArcNode *p;int v1,v2; G.kind=DN; printf( 输入顶点数:); scanf(%d,&G.vexnum); printf( 输入弧数:); scanf(%d,&G.arcnum); printf( 输入顶点:n); for(i=0;iG.vexnum;+i) /构造表头向量 scanf(%d,&G.verticesi.data); G.verticesi.firstarc=NULL;/初始化指针 for(k=0;kadjvex=j;p-nextarc=G.verticesi.firstarc; G.verticesi.firstarc=p; scanf(%d,&p-info); /forint Push(SqStack &S,int e) /插入元素e为新的栈顶元素if(S.top-S.base=S.stacksize)/栈满，追加存储空间 S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int); if(!S.base)exit(OVERFLOW); /存储分配失败 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return OK;int InitStack(SqStack &S) /栈的初始化S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int); if(!S.base)exit(OVERFLOW); /存储分配失败 S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK;int Pop(SqStack &S,int &e) /删除栈顶元素/若栈不空，则删除S的栈顶元素，用e返回其值if(S.top=S.base)return ERROR; e=*-S.top; return OK;int GetTop(SqStack S,int &e) /取栈顶元素/若栈不空，则用e返回S的栈顶元素 if(S.top=S.base) return ERROR; e=*(S.top-1); return OK;int StackEmpty(SqStack S) /栈空if(S.top=S.base)return TRUE; else return FALSE;int InitQueue(LinkQueue &Q) /队列初始化 Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode); if(!Q.front)exit(OVERFLOW); Q.front-next=NULL; return OK;int EnQueue(LinkQueue &Q,int e) /插入/插入元素e为Q的新的队尾元素 QueuePtr p=(QueuePtr)malloc(sizeof(QNode); if(!p)exit(OVERFLOW); p-data=e;p-next=NULL; Q.rear-next=p; Q.rear=p; return OK;int DeQueue(LinkQueue &Q,int &e) /若队列不空，则删除Q的队头元素，用e返回其值 if(Q.front=Q.rear) return ERROR; QueuePtr p=Q.front-next; e=p-data; Q.front-next=p-next; if(Q.rear=p)Q.rear=Q.front; free(p); return OK;int QueueEmpty(LinkQueue Q) /队列空 if(Q.front=Q.rear) return TRUE; else return FALSE;int FirstAdjVex(ALGraph G,int u) if(!G.verticesu.firstarc) return -1; return LocateVex(G,G.verticesu.firstarc-adjvex);int NextAdjVex(ALGraph G,int u,int w) ArcNode *p=G.verticesu.firstarc; while(p&LocateVex(G,p-adjvex)!=w) p=p-nextarc; if(!p) return FirstAdjVex(G,u); p=p-nextarc; if(!p) return -1; return LocateVex(G,p-adjvex);void Visit(ALGraph G,int v) printf(%2d,G.verticesv.data);void DFSTraverse(ALGraph G)/按深度优先非递归遍历图G,使用辅助栈S和访问标志数组visited int v,w;SqStack S; for(v=0;vG.vexnum;v+) visitedv=FALSE; InitStack(S); for(v=0;v=0;w=NextAdjVex(G,v,w) if(!visitedw) Visit(G,w); visitedw=TRUE; Push(S,w); GetTop(S,v); /if /for Pop(S,v); GetTop(S,v);/while/if printf(n); void BFSTraverse(ALGraph G)/按广度优先非递归遍历图G,使用辅助队列Q和访问标志数组visited int v,u,w;LinkQueue Q; for(v=0;vG.vexnum;+v) visitedv=FALSE; InitQueue(Q); for(v=0;v=0;w=NextAdjVex(G,u,w) if(!visitedw) /w为u的尚未访问的邻接顶点 visitedw=TRUE;Visit(G,w); EnQueue(Q,w); /if /while /if printf(n);void PrintDN(ALGraph G) /图的显示 int i;ArcNode *p; printf(顶点:n); for(i=0;iG.vexnum;+i) printf(%2d,G.verticesi.data); printf(n弧:n); for(i=0;iadjvex,p-info); p=p-nextarc; printf(n); /if /forvoid main() ALGraph G; printf(*题目：图的遍历*nn); CreateDN(G); PrintDN(G); printf( 深度优先遍历:); DFSTraverse(G); printf(n 广度优先遍历:); BFSTraverse(G);【运行结果】 实验五 查找算法实现【实验学时】5学时【实验目的】熟练掌握顺序查找、折半查找及二叉排序树、平衡二叉树上的查找、插入和删除的方法，比较它们的平均查找长度。【问题描述】查找表是数据处理的重要操作， 试建立有100个结点的二叉排序树进行查找，然后用原数据建立AVL树， 并比较两者的平均查找长度。【基本要求】（1） 以链表作为存储结构，实现二叉排序树的建立、查找和删除。（2） 根据给定的数据建立平衡二叉树。（3） 比较二叉排序树和平衡二叉树的平均查找长度。【测试数据】随机生成。【实现提示】（1） 初始，二叉排序树和平衡二叉树都为空树，操作界面给出查找、插入和删除三种操作供选择。每种操作均要提示输入关键字。每次插入或删除一个结点后，应更新平衡二叉树或二叉排序树的显示。（2） 平衡二叉树或二叉排序树的显示可以采用凹入表形式，也可以采用图形界面画出树形。【源程序】#include#include#include#define EQ(a,b) (a)=(b) #define LT(a,b) (a)(b)typedef int Keytype;typedef struct Keytype key; ElemType;typedef struct BSTnode ElemType data; int bf; struct BSTnode *lchild,*rchild; BSTnode,*BSTree;void InitBSTree(BSTree &T)T=NULL;void R_Rotate(BSTree &p)BSTnode *lc; lc=p-lchild; p-lchild=lc-rchild; lc-rchild=p; p=lc; void L_Rotate(BSTree &p)BSTnode *rc; rc=p-rchild; p-rchild=rc-lchild; rc-lchild=p; p=rc; void Leftbalance(BSTree &T)BSTnode *lc,*rd; lc=T-lchild; switch(lc-bf) case +1: T-bf=lc-bf=0; R_Rotate(T); break; case -1: rd=lc-rchild; switch(rd-bf) case 1: T-bf=-1; lc-bf=0; break; case 0: T-bf=lc-bf=0; break; case -1: T-bf=0; lc-bf=1; break; rd-bf=0; L_Rotate(T-lchild); R_Rotate(T); void Rbalance(BSTree &T)BSTnode *lc,*ld; lc=T-rchild; switch(lc-bf) case 1: ld=lc-lchild; switch(ld-bf) case 1: T-bf=0; lc-bf=-1; break; case 0: T-bf=lc-bf=0; break; case -1: T-bf=1; lc-bf=0; break; ld-bf=0; R_Rotate(T-rchild); L_Rotate(T); case -1: T-bf=lc-bf=0; L_Rotate(T); break; int InsertAVL(BSTree &T,ElemType e,bool &taller) if(!T) T=(BSTree)malloc(sizeof(BSTnode); T-data=e; T-lchild=T-rchild=NULL; T-bf=0; taller=true; else if(EQ(e.key,T-data.key) taller=false; cout结点 e.key 不存在。data.key) if(!InsertAVL(T-lchild,e,taller) return 0; if(taller) switch(T-bf) case 1: Leftbalance(T); taller=false; break; case 0: T-bf=+1; taller=true; break; case -1: T-bf=0; taller=false; break; else if(!InsertAVL(T-rchild,e,taller) return 0; if(taller) switch(T-bf) case 1: T-bf=0; taller=false; break; case 0: T-bf=-1; taller=true; break; case -1: Rbalance(T); taller=false; break; return 1;bool SearchBST(BSTree T,ElemType key,BSTree f,BSTree &p) if(!T) p=f; cout结点不存在。data.key) ) p=T; cout查找成功，存在结点; coutdata.keydata.key) return SearchBST(T-lchild,key,T,p); else return SearchBST(T-rchild,key,T,p);void Leftbalance_div(BSTree &p,int &shorter) BSTree p1,p2; if(p-bf=+1) /p结点的左子树高，删除结点后p的bf减1,树变矮 p-bf=0; shorter=1; else if(p-bf=0)/p结点左、右子树等高，删除结点后p的bf减1,树高不变 p-bf=-1; shorter=0; else p1=p-rchild;/p1指向p的右子树 if(p1-bf=0)/p1结点左、右子树等高,删除结点后p的bf为-2,进行左旋处理，树高不变 L_Rotate(p); p1-bf=1; p-bf=-1; shorter=0; else if(p1-bf=-1)/p1的右子树高，左旋处理后，树变矮 L_Rotate(p); p1-bf=p-bf=0; shorter=1; else p2=p1-lchild; p1-lchild=p2-rchild; p2-rchild=p1; p-rchild=p2-lchild; p2-lchild=p; if(p2-bf=0) p-bf=0; p1-bf=0; else if(p2-bf=-1) p-bf=+1; p1-bf=0; else p-bf=0; p1-bf=-1; p2-bf=0; p=p2; shorter=1; void Rbalance_div(BSTree &p,int &shorter) BSTree p1,p2; if(p-bf=-1) p-bf=0; shorter=1; else if(p-bf=0) p-bf=+1; shorter=0; else p1=p-lchild; if(p1-bf=0) R_Rotate(p); p1-bf=-1; p-bf=+1; shorter=0; else if(p1-bf=+1) R_Rotate(p); p1-bf=p-bf=0; shorter=1; else p2=p1-rchild; p1-rchild=p2-lchild; p2-lchild=p1; p-lchild=p2-rchild; p2-rchild=p; if(p2-bf=0) p-bf=0; p1-bf=0; else if(p2-bf=1) p-bf=-1; p1-bf=0; else p-bf=0; p1-bf=1; p2-bf=0; p=p2; shorter=1; void Delete(BSTree q,BSTree &r,int &shorter) if(r-rchild=NULL) q-data=r-data; q=r; r=r-lchild; free(q); shorter=1; else Delete(q,r-rchild,shorter); if(shorter=1) Rbalance_div(r,shorter); ElemType DeleteAVL(BSTree &p,ElemType key,int &shorter) ElemType k,a,b; a.key=1; b.key=0; BSTree q; if(p=NULL) cout结点不存在。data.key) )/在p的左子树中进行删除 k=DeleteAVL(p-lchild,key,shorter); if(shorter=1) Leftbalance_div(p,shorter); return k; else if(LQ(key.key,p-data.key) )/在p的右子树中进行删除 k=DeleteAVL(p-rchild,key,shorter); if(shorter=1) Rbalance_div(p,shorter); return k; else q=p; if(p-rchild=NULL) /右子树空则只需重接它的左子树 p=p-lchild; free(q); shorter=1; else if(p-lchild=NULL)/左子树空则只需重接它的右子树 p=p-rchild; free(q); shorter=1; else Delete(q,q-lchild,shorter); if(shorter=1) Leftbalance_div(p,shorter); p=q; return a; void Print_BSTTree(BSTree T,int i) if(T) if(T-rchild) Print_BSTTree(T-rchild,i+1); for(int j=1;j=i;j+) cout ; coutdata.keylchild) Print_BSTTree(T-lchild,i+1); int main() BSTree T; ElemType e; InitBSTree(T); bool tall=false; bool choice=true; c