2022年数据结构课后题目答案 2.pdf

《2022年数据结构课后题目答案 2.pdf》由会员分享，可在线阅读，更多相关《2022年数据结构课后题目答案 2.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2.13 LNode*Locate(LinkList L,int x)/链表上的元素查找,返回指针 for(p=l-next;p&p-data!=x;p=p-next);return p;/Locate 2.19 Status Delete_Between(Linklist&L,int mink,int maxk)/删除元素递增排列的链表 L 中值大于 mink 且小于 maxk的所有元素 p=L;while(p-next-datanext;/p是最后一个不大于mink 的元素if(p-next)/如果还有比 mink 更大的元素 q=p-next;while(q-datanext;/q是第一

2、个不小于 maxk的元素p-next=q;/Delete_Between 2.21 void reverse(SqList&A)/顺序表的就地逆置 for(i=1,j=A.length;ij;i+,j-)A.elemA.elemj;/reverse 2.24 void reverse_merge(LinkList&A,LinkList&B,LinkList&C)/把元素递增排列的链表 A和 B 合并为 C,且 C中元素递减排列,使用原空间 pa=A-next;pb=B-next;pre=NULL;/pa和 pb分别指向 A,B 的当前元素while(pa|pb)if(pa-datadata|!

3、pb)pc=pa;q=pa-next;pa-next=pre;pa=q;/将 A的元素插入新表 else pc=pb;q=pb-next;pb-next=pre;pb=q;/将 B的元素插入新表 pre=pc;C=A;A-next=pc;/构造新表头名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 6 页 -/reverse_merge 分析:本算法的思想是,按从小到大的顺序依次把A和 B的元素插入新表的头部pc 处,最后处理 A或 B的剩余元素.2.25 void SqList_Intersect(SqList A,SqList B,SqList&C)/求元素递增排列的线性表 A

4、和 B的元素的交集并存入C中 i=1;j=1;k=0;while(A.elem&B.elemj)if(A.elemB.elemj)j+;if(A.elem=B.elemj)C.elem+k=A.elem;/当发现了一个在 A,B 中都存在的元素,i+;j+;/就添加到 C中/while/SqList_Intersect 3.15typedef struct Elemtype*base2;Elemtype*top2;BDStacktype;/双向栈类型Status Init_Stack(BDStacktype&tws,int m)/初始化一个大小为 m的双向栈tws tws.base0=(Ele

5、mtype*)malloc(sizeof(Elemtype);tws.base1=tws.base0+m;tws.top0=tws.base0;tws.top1=tws.base1;return OK;/Init_Stack Status push(BDStacktype&tws,int i,Elemtype x)/x入栈,i=0表示低端栈,i=1 表示高端栈 if(tws.top0tws.top1)return OVERFLOW;/注意此时的栈满条件 if(i=0)*tws.top0+=x;else if(i=1)*tws.top1-=x;else return ERROR;return O

6、K;/push Status pop(BDStacktype&tws,int i,Elemtype&x)/x出栈,i=0表示低端栈,i=1 表示高端栈名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 6 页 -if(i=0)if(tws.top0=tws.base0)return OVERFLOW;x=*-tws.top0;else if(i=1)if(tws.top1=tws.base1)return OVERFLOW;x=*+tws.top1;else return ERROR;return OK;/pop 3.17int IsReverse()/判断输入的字符串中&前和&后部

7、分是否为逆串,是则返回 1,否则返回 0 InitStack(s);while(e=getchar()!=&)push(s,e);while(e=getchar()!=)if(StackEmpty(s)return 0;pop(s,c);if(e!=c)return 0;if(!StackEmpty(s)return 0;return 1;/IsReverse 3.24Status g(int m,int n,int&s)/求递归函数 g 的值 s if(m=0&n=0)s=0;else if(m0&n=0)s=n+g(m-1,2*n);else return ERROR;return OK;

8、/g 3.30Status EnCyQueue(CyQueue&Q,int x)/带 length 域的循环队列入队算法 if(Q.length=MAXSIZE)return OVERFLOW;Q.rear=(Q.rear+1)%MAXSIZE;Q.baseQ.rear=x;名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 6 页 -Q.length+;return OK;/EnCyQueue Status DeCyQueue(CyQueue&Q,int&x)/带 length 域的循环队列出队算法 if(Q.length=0)return INFEASIBLE;head=(Q.r

9、ear-Q.length+1)%MAXSIZE;/详见书后注释 x=Q.basehead;Q.length-;/DeCyQueue 3.31int Palindrome_Test()/判别输入的字符串是否回文序列,是则返回 1,否则返回 0 InitStack(S);InitQueue(Q);while(c=getchar()!=)Push(S,c);EnQueue(Q,c);/同时使用栈和队列两种结构 while(!StackEmpty(S)Pop(S,a);DeQueue(Q,b);if(a!=b)return ERROR;return OK;/Palindrome_Test 4.11 v

10、oid String_Subtract(Stringtype s,Stringtype t,Stringtype&r)/求所有包含在串 s 中而 t 中没有的字符构成的新串r StrAssign(r,);for(i=1;i=Strlen(s);i+)StrAssign(c,SubString(s,i,1);for(j=1;jI&STRCOMPARE(C,SUBSTRING(S,J,1);J+);if(k 判断当前字符是否包含在 t 中for(k=1;kStrlen(t)StrAssign(r,Concat(r,c);/for/String_Subtract 5.31 void GList_Co

11、py(GList A,GList&B)/复制广义表的递归算法 if(!A-tag)/当结点为原子时,直接复制 B-tag=0;B-atom=A-atom;else/当结点为子表时 B-tag=1;if(A-ptr.hp)B-ptr.hp=malloc(sizeof(GLNode);GList_Copy(A-ptr.hp,B-ptr.hp);/复制表头 if(A-ptr.tp)B-ptr.tp=malloc(sizeof(GLNode);GList_Copy(A-ptr.tp,B-ptr.tp);/复制表尾 /else/GList_Copy 6.33 int Is_Descendant_C(in

12、t u,int v)/在孩子存储结构上判断u 是否 v 的子孙,名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 6 页 -是则返回 1,否则返回 0 if(u=v)return 1;else if(Lv)if(Is_Descendant(u,Lv)return 1;if(Rv)if(Is_Descendant(u,Rv)return 1;/这是个递归算法 return 0;/Is_Descendant_C 7.14Status Build_AdjList(ALGraph&G)/输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表 InitALGraph(G);scanf(%d,

13、&v);if(v0)return ERROR;/顶点数不能为负G.vexnum=v;scanf(%d,&a);if(a0)return ERROR;/边数不能为负G.arcnum=a;for(m=0;mv;m+)G.verticesm.data=getchar();/输入各顶点的符号for(m=1;m=a;m+)t=getchar();h=getchar();/t为弧尾,h 为弧头if(i=LocateVex(G,t)0)return ERROR;if(j=LocateVex(G,h)nextarc;q=q-nextarc);q-nextarc=p;p-adjvex=j;p-nextarc=N

14、ULL;/while return OK;/Build_AdjList 9.32int last=0;void MaxLT_MinGT(BiTree T,int x)/找到二叉排序树 T 中小于 x 的最大元素和大于 x 的最小元素 if(T-lchild)MaxLT_MinGT(T-lchild,x);/本算法仍是借助中序遍历来实现if(lastdata=x)/找到了小于 x 的最大元素printf(a=%dn,last);if(lastdatax)/找到了大于 x 的最小元素printf(b=%dn,T-data);last=T-data;if(T-rchild)MaxLT_MinGT(T-rchild,x);名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 6 页 -/MaxLT_MinGT 名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 6 页 -