《2022年数据结构课后题目答案 3.pdf》由会员分享，可在线阅读，更多相关《2022年数据结构课后题目答案 3.pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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-data
2、next; /q是第一个不小于 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(p
3、a|pb) if(pa-datadata|!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 分析: 本算法的思想是 , 按从小到大的顺序依次把
4、A和 B的元素插入新表的头部pc 处, 最后处理 A或 B的剩余元素 . 2.25 void SqList_Intersect(SqList A,SqList B,SqList &C)/求元素递增排列的线性表 A和 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 Ele
5、mtype *base2; Elemtype *top2; BDStacktype; /双向栈类型Status Init_Stack(BDStacktype &tws,int m)/初始化一个大小为 m的双向栈tws tws.base0=(Elemtype*)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表示低端栈
6、,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 OK; /push Status pop(BDStacktype &tws,int i,Elemtype &x)/x出栈,i=0表示低端栈,i=1 表示高端栈名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共
7、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()/判断输入的字符串中 & 前和& 后部分是否为逆串 , 是则返回 1, 否则返回 0 InitStack(s); while(e=getchar()!=&) push(s,e); while
8、(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; /g 3.30Status EnCyQueue(CyQueue &Q,int x)/带 length 域的循
9、环队列入队算法 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)
10、 return INFEASIBLE; head=(Q.rear-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
11、 ERROR; return OK; /Palindrome_Test 4.11 void 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,Con
12、cat(r,c); /for /String_Subtract 5.31 void GList_Copy(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
13、.tp,B-ptr.tp); / 复制表尾 /else /GList_Copy 6.33 int Is_Descendant_C(int 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 (I
14、s_Descendant(u,Rv) return 1; /这是个递归算法 return 0; /Is_Descendant_C 7.14Status Build_AdjList(ALGraph &G)/ 输入有向图的顶点数 , 边数, 顶点信息和边的信息建立邻接表 InitALGraph(G); scanf(%d,&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()
15、; /输入各顶点的符号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=NULL; /while return OK; /Build_AdjList 9.32int last=0; void MaxLT_MinGT(BiTree T,int x)/ 找到二叉排序树 T 中小于 x 的最大元素和大于 x 的最小元素 if(
16、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 页 - - - - - - - - -