数据结构80题参考答案(下)41-80下载_Word模板_20

is_667597

暂无简介

数据结构80题参考答案(下)41-80广工数据结构80道上机题仅供参考最后缺了几题 41 void swap(ElemType &a,ElemType &b) { ElemType t; t=a; a=b; b=t; } void Rotate(Array1D &a, int n, int k) /* a[n] contains the elements, */ /* rotate them right circlely by k sits */ { int j...

广工数据结构80道上机题仅供参考最后缺了几题 41 void swap(ElemType &a,ElemType &b) { ElemType t; t=a; a=b; b=t; } void Rotate(Array1D &a, int n, int k) /* a[n] contains the elements, */ /* rotate them right circlely by k sits */ { int j,l; k=n-k%n-1; for(j=0,l=k;jB.data[j].i)||(A.data[i].i==B.data[j].i&&A.data[i].j>B.data[j].j))//A中元素位置大于B中 { C.data[k].i=B.data[j].i; C.data[k].j=B.data[j].j; C.data[k].e=B.data[j].e; k++;j++; } else//A中位置小于B { C.data[k].i=A.data[i].i; C.data[k].j=A.data[i].j; C.data[k].e=A.data[i].e; k++;i++; } } while(i<=A.tu) { C.data[k].i=A.data[i].i; C.data[k].j=A.data[i].j; C.data[k].e=A.data[i].e; k++;i++; } while(j<=B.tu) { C.data[k].i=B.data[j].i; C.data[k].j=B.data[j].j; C.data[k].e=B.data[j].e; k++;j++; } C.tu=k-1; return 1; } 43 Status GetElem(T2SMatrix M, int i, int j, ElemType &e) /* 求二元组矩阵的元素A[i][j]的值e */ { int k=M.cpot[i]; if(i>M.mu||i<1||j>M.nu||j<1) return ERROR;//越界 .. e=0; while(ki,p->j,p->e); p=p->right; } } i++; } } 45 int GListDepth(GList ls) /* Return the depth of list */ { int max,dep; GList p; if(!ls) return 1; if(ls->tag==0) return 0; for(max=0,p=ls;p;p=p->un.ptr.tp) { dep=GListDepth(p->un.ptr.hp); max=max>dep?max:dep; } return max+1; } 46 Status Equal(GList A, GList B) /* 判断广义表A和B是否相等,是则返回TRUE,否则返回FALSE */ { if(!A&&!B) return TRUE; if(!A->tag&&!B->tag&&A->un.atom==B->un.atom) return TRUE;//原子时比较 if(A->tag&&B->tag)//不是原子,子表递归 { if(Equal(A->un.ptr.hp,B->un.ptr.hp)&&Equal(A->un.ptr.tp,B->un.ptr.tp)) return TRUE; } return FALSE; } 47 void OutAtom(GList A, int layer, void(*Out2)(char, int)) /* 递归地用函数Out2输出广义表的原子及其所在层次,layer表示当前层次 */ { if(!A) return ; if(!A->tag) Out2(A->un.atom,layer); else { OutAtom(A->un.ptr.hp,layer+1,Out2); OutAtom(A->un.ptr.tp,layer,Out2); } } 48 Status Dencendant(Array1D L,Array1D R,int n,int u,int v) /* If node 'u' is the dencendant of node 'v', */ /* then return 'TRUE' else return 'FALSE'. */ /* L[i] is the left child of the i_th node, */ /* R[i] is the right child of the i_th node */ /* in the Binary Tree which has n nodes. */ { if(u<=0||u>n) return FALSE; if(u==L[v]||u==R[v]) return TRUE; while(L[v]) if(Dencendant(L,R,n,u,L[v])) return TRUE; while(R[v]) if(Dencendant(L,R,n,u,R[v])) return TRUE; return FALSE; } 49 Status Dencend(Array1D L, Array1D R, int n, int u, int v, Array1D T) /******************************************************************/ { int i; if(u>n||u<=0) return FALSE; T[1]=0; for(i=1;i<=n;i++) { if(L[i]) T[L[i]]=i; if(R[i]) T[R[i]]=i; } while(T[u]) { if(T[u]==v) return TRUE; u=T[u]; } return FALSE; } 50 Status Similar(BiTree t1, BiTree t2) /* 判断两棵二叉树是否相似的递归算法 */ { if(!t1&&!t2) return TRUE; if((!t1->lchild&&t2->lchild)||(t1->rchild&&!t2->rchild)) return FALSE; if(Similar(t1->lchild,t2->lchild)&&Similar(t1->rchild,t2->rchild)) return TRUE; return FALSE; } 51 void PreOrder(BiTree bt, void (*visit)(TElemType)) /* 使用栈，非递归先序遍历二叉树bt， */ /* 对每个结点的元素域data调用函数visit */ { Stack s; BiTree p=bt; InitStack(s); while(p||!StackEmpty(s)) { if(p) { visit(p->data);//访问根节点 Push(s,p); p=p->lchild; } else { Pop(s,p); p=p->rchild;//右孩子 } } } 52 void PostOrder(BiTree bt, void (*visit)(TElemType)) /* 使用栈，非递归后序遍历二叉树bt， */ /* 对每个结点的元素域data调用函数visit */ { Stack s; SElemType p,q; p.ptr=bt; InitStack(s); Push(s,p);//根节点入栈 p.tag=0; while(!StackEmpty(s)) { Pop(s,p);//顶点元素出栈 if(p.tag) visit(p.ptr->data);//可访问 else { p.tag=1; Push(s,p);//root入栈 q=p; if(p.ptr->rchild) { q.ptr=p.ptr->rchild; q.tag=0; Push(s,q);//右孩子入栈 } q=p; if(p.ptr->lchild) { q.ptr=p.ptr->lchild; q.tag=0; Push(s,q);//左孩子入栈 } } } } 53 TElemType ans; TElemType f(BiTree bt, int &k) { if(bt&&k==1) return bt->data; else { if(bt->lchild) {k--;ans=f(bt->lchild,k);}//遍历zuo if(bt->rchild) {k--;ans=f(bt->rchild,k);}//遍历右 return ans; } } TElemType PreOrder(BiTree bt, int k) /* bt is the root node of a binary linked list, */ /* Preorder travel it and find the node whose */ /* position number is k, and return its value. */ /* if can't found it, then return '#'. */ { ans='#'; if(k&&bt) ans=f(bt,k); return ans; } 54 int ans=0;//全局变量 void f(BiTree bt, int &x); void Leaves(BiTree bt, int &x) /* Count the leaf node of the BiTree */ /* whose root node is bt to x. */ { ans=0; if(!bt->lchild&&!bt->rchild) x=0; else f(bt,x); } void f(BiTree bt, int &x)//求叶子数目 { if(!bt->lchild&&!bt->rchild) ans++; else if(!bt->lchild) f(bt->rchild,x);//左为空 else if(!bt->rchild) f(bt->lchild,x);//右为空 else//都不空 { f(bt->rchild,x); f(bt->lchild,x); } x=x>ans?x:ans; } 55 void Exchange(BiTree &bt) /* Exchange the left and right leaves of */ /* bitree whose root node is bt */ { BiTree t; if(bt)//不空则交换左右孩子 { t=bt->lchild; bt->lchild=bt->rchild; bt->rchild=t; Exchange(bt->lchild);//遍历左孩子 Exchange(bt->rchild);//右 } } 56 int ans=0; int dep(BiTree T)//求子树深度 { int ld,rd; if(!T) return 0; else { ld=dep(T->lchild); rd=dep(T->rchild); } return (ld>rd?ld:rd)+1; } int Depthx(BiTree T, TElemType x) /* 求二叉树中以值为x的结点为根的子树深度 */ { if(T->data==x)//找到结点计算高度 { ans=dep(T); return ans; } else { if(T) { if(Depthx(T->lchild,x)||Depthx(T->rchild,x)) return ans;//找到则返回结果 else return 0;//找不到返回0 } } } 57 void CopyBiTree(BiTree T, BiTree &TT) /* 基于层次遍历的非递归复制二叉链表 */ { Queue q,cq; BiTree t; QElemType e,ce; if(!T) { TT=NULL; return; } InitQueue(q); InitQueue(cq);//复制树队列 TT=(BiTree)malloc(sizeof(BiTNode)); TT->data=T->data;//复制根结点 TT->lchild=NULL;TT->rchild=NULL; EnQueue(cq,TT); EnQueue(q,T);//根入队 while(!QueueEmpty(q)) { DeQueue(q,e); DeQueue(cq,ce); if(e->lchild)//复制左 { t=(BiTree)malloc(sizeof(BiTNode)); t->data=e->lchild->data; t->lchild=NULL;t->rchild=NULL; ce->lchild=t; EnQueue(q,e->lchild);//左孩子入队 EnQueue(cq,ce->lchild); } if(e->rchild)//复制右 { t=(BiTree)malloc(sizeof(BiTNode)); t->data=e->rchild->data; t->lchild=NULL;t->rchild=NULL; ce->rchild=t; EnQueue(q,e->rchild); //右孩子入队 EnQueue(cq,ce->rchild); } } } 58 void LevelOrder(BiTree bt, char *ss) /* travel BiTree bt by level, Return result by ss. */ { if(!bt) { ss=""; return; } int i=0; Queue q; QElemType e; InitQueue(q); EnQueue(q,bt);//根入队 ss[i++]=bt->data; while(!QueueEmpty(q)) { DeQueue(q,e); if(e->lchild) { ss[i++]=e->lchild->data; EnQueue(q,e->lchild);//左孩子入队 } if(e->rchild) { ss[i++]=e->rchild->data; EnQueue(q,e->rchild);//右孩子入队 } } ss[i]='\0'; } 59 Status CompleteBiTree(BiTree bt) /* judge if the binary tree whose root is bt */ /* is a complete tree. */ { if(!bt) return TRUE; int i=0; Queue q; QElemType e; InitQueue(q); EnQueue(q,bt);//根入队 while(!QueueEmpty(q)) { DeQueue(q,e); if(!e) i=1;//已经到最后 else if(i) return FALSE;//不是完全二叉树 else { EnQueue(q,e->lchild);//左孩子入队 EnQueue(q,e->rchild);//右孩子入队 } } return TRUE; } 60 int find(char c,char *pre,int pos) { int i; for(i=pos;pre[i]!='\0';i++) if(c==pre[i]) return i; return i; } void BuildBiTree(BiTree &bt, int ps, char *pre, int is, char *ino, int n) /* 当前要建立的子树bt的元素总数为n，*/ /* 元素在前序序列pre的起始位置为ps，*/ /* 元素在中序序列ino的起始位置为is */ { int m,llen,rlen; if(n<=0) bt=NULL; else { bt=(BiTree)malloc(sizeof(BiTNode)); bt->data=pre[ps];//创建结点,pre数组中 m=find(pre[ps],ino,is);//在pre中从is起找与pre[ps]相同的元素位置 llen=m-is;//以m为根,左边个数 rlen=n-llen-1;//右边元素个数 BuildBiTree(bt->lchild,ps+1,pre,is,ino,llen);//构造左边 BuildBiTree(bt->rchild,ps+llen+1,pre,m+1,ino,rlen);//右边 } } 61 Status DfsReachable(ALGraph g, int i, int j) /* Judge if it exists a path from vertex 'i' to */ /* vertex 'j' in digraph 'g'. */ /* Array 'visited[]' has been initialed to 'false'.*/ { ArcNode *p; visited[i]=TRUE; for(p=g.vertices[i].firstarc;p;p=p->nextarc) { if(p) { if(p->adjvex==j) return TRUE; if(!visited[p->adjvex]) if(DfsReachable(g,p->adjvex,j)) return TRUE; } } return FALSE; } 62 Status BfsReachable(ALGraph g, int i, int j) /* Determine whether it exists path from vertex i to */ /* vertex j in digraph g with Breadth_First Search. */ /* Array 'visited' has been initialed to 'false'. */ { Queue q; int t; ArcNode *p; InitQueue(q); EnQueue(q,i); while(!QueueEmpty(q)) { DeQueue(q,t); visited[t]=TRUE;//标志走过 for(p=g.vertices[t].firstarc;p;p=p->nextarc) { if(p->adjvex==j) return TRUE;//存在路径 if(!visited[p->adjvex]) EnQueue(q,p->adjvex); } } return FALSE; } 63 void Traverse(Graph dig, VertexType v0, void (*visit)(VertexType)) /* Travel the digraph 'dig' with Depth_First Search. */ { int i,w; if(dig.vexnum==0) return ; for(i=0;i=0;w=NextAdjVex(dig,i,w))//查找v0的邻接点 { if(!visited[w])//未访问则入栈,取栈顶元素 { Push(s,GetVex(dig,w)); break; } } if(w<0) Pop(s,v0); //出栈 } } 64 Status SinglePath(ALGraph g, VertexType sv, VertexType tv, int k, char *sp) /* Judge whether it exists a path from sv to tv with length k */ /* in graph g, return path using string sp if exists. */ { int i,j,q;//从sv开始深搜到tv ArcNode *p; if(sv==tv&&!k)//两点重合 { inpath(sp,sv); return OK; } i=LocateVex(g,sv);//找sv的位置 visited[i]=1; inpath(sp,sv);//sv加入路径 for(p=g.vertices[i].firstarc;p;p=p->nextarc)//遍历i点的邻接点 { q=p->adjvex; if(!visited[q]) { if(SinglePath(g,g.vertices[q].data,tv,k-1,sp)) return OK;//存在路径 else depath(sp,g.vertices[q].data);//从路径中删除 } } visited[i]=0;//重置 return FALSE; } 65 void APath(ALGraph g, VertexType sv, VertexType tv, StrARR &path, int &i,char *sp) { int k,j,q,n;//从sv开始深搜到tv ArcNode *p; k=LocateVex(g,sv);//找sv的位置 visited[k]=1; inpath(sp,sv);//sv加入路径 if(sv==tv)//存在路径 { for(n=0;sp[n]!='\0';n++) { path[i][n]=sp[n]; } path[i][n]='\0';//.....上一组数据会留下杂物,要清掉.. i++; } else for(p=g.vertices[k].firstarc;p;p=p->nextarc)//遍历k点的邻接点 { q=p->adjvex; if(!visited[q]) { APath(g,g.vertices[q].data,tv,path,i,sp); } } depath(sp,sv); visited[k]=0;//重置 } void AllPath(ALGraph g, VertexType sv, VertexType tv, StrARR &path, int &i) /* Get all the paths from vertex sv to tv, save them */ /* into Array path which contains string components. */ /* Return the number of path using i */ { char spa[MAX_VERTEX_NUM+1]; APath(g,sv,tv,path,i,spa); } 66. 67. 68. int Search(SSTable a, KeyType k) /* Index the element which key is k */ /* in StaticSearchTable s. */ /* Return 0 if x is not found. */ { int i; for(i=1;i<=a.length;i++)//下标从1开始..- - if(a.elem[i].key==k) return i; return 0; } 69. int BinSearch(SSTable s, int low, int high, KeyType k) /* Index the element which key is k */ /* in StaticSearchTable s. */ /* Return 0 if x is not found. */ { while(low<=high) { int mid=(low+high)/2; if(s.elem[mid].key==k) return mid; else if(s.elem[mid].key>k) return BinSearch(s,low,mid-1,k); else return BinSearch(s,mid+1,high,k); } return 0; } 70. Status IsBSTree(BiTree t) /* 判别给定二叉树t是否为二叉排序树。*/ /* 若是，则返回TRUE，否则FALSE */ { if(t->lchild) { if(!IsBSTree(t->lchild)) return 0;//左子树不是BST if(t->lchild->data.key>=t->data.key) return 0; } if(t->rchild) { if(!IsBSTree(t->rchild)) return 0;//右子树不是BST if(t->rchild->data.key<=t->data.key) return 0; } return 1; } 71. void OrderOut(BiTree t, KeyType x, void(*visit)(TElemType)) /* Output is to use visit(t->data); */ { if(!t) return; OrderOut(t->rchild,x,visit);//后续遍历输出 if(t->data.key>=x) visit(t->data); OrderOut(t->lchild,x,visit); } 72. void PrintKeys(HashTable ht, void(*print)(StrKeyType)) /* 依题意用print输出关键字 */ { int c,t,k; k=hashsize[ht.sizeindex]; for(c='A';c<='Z';c++) { t=(c-'A')%k; while(ht.elem[t].key[0]>='A'&&ht.elem[t].key[0]<='Z') { if(ht.elem[t].key[0]==c) print(ht.elem[t].key); t=(t+1)%k; } } } 73. int BuildHashTab(ChainHashTab &H, int n, HKeyType es[]) /* 直接调用下列函数 */ /* 哈希函数： */ /* int Hash(ChainHashTab H, HKeyType k); */ /* 冲突处理函数： */ /* int Collision(ChainHashTab H, HLink &p); */ { int i=0,flag=0; HLink t,p; while(idata=es[i]; t->next=NULL; p=H.elem[Hash(H,es[i])]; if(p==NULL)//头结点空 { if(p->data!=es[i])//数据不重复 H.elem[Hash(H,es[i])]=t;//存入数据 } else { if(p->data!=es[i]) { while(p->next!=NULL) {p=p->next;if(p->data==es[i]) flag=1;} p=H.elem[Hash(H,es[i])]; if(!flag) { t->next=p; H.elem[Hash(H,es[i])]=t; } } } i++; } } 74. void InsertSort(SqList &L) { int i,j; for(i=2; i<=L.length; i++) { L.r[0]= L.r[i]; for( j=i ; j>1 && L.r[0].key < L.r[j-1].key ; j--) { L.r[j]=L.r[j-1]; } L.r[j]=L.r[0]; } } 75. void BubbleSort(SqList &L) /* 元素比较和交换必须调用如下定义的比较函数和交换函数：*/ /* Status LT(RedType a, RedType b); 比较："<" */ /* Status GT(RedType a, RedType b); 比较：">" */ /* void Swap(RedType &a, RedType &b); 交换 */ { int i,j,change=1; for(i=L.length;i>1;i=change) { change =1; for(j=1;j1 && L.r[0].key < L.r[j-1].key ; j--) { L.r[j]=L.r[j-1]; } L.r[j]=L.r[0]; } if((L.length+1)/2==0) return '#'; return L.r[(L.length+1)/2].key; } 80. void CountSort(SqList &L) /* 采用顺序表存储结构，L.r存储序列a，L.length为n */ /* 在函数内自行定义计数数组c */ { int i,c[MAXSIZE+1],j,k,n; SqList t; t=L; n=L.length; for(i=1;i<=n;i++) { k=0; for(j=1;j<=n;j++) { if(L.r[j].key

本文档为【数据结构80题参考答案(下)41-80】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。

历史搜索

清空历史搜索

数据结构80题参考答案(下)41-80

热门搜索

历史搜索