数据结构课后题算法.docx

2.11 设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。 解： Status InsertOrderList(SqList va,ElemType x) { //在非递减的顺序表va中插入元素x并使其仍成为顺序表的算法 int i; if(va.length==va.listsize)return(OVERFLOW); for(i=va.length;i0,xva.elem[i-1];i--) va.elem[i]=va.elem[i-1]; va.elem[i]=x; va.length++; return OK; } 2.14 试写一算法在带头结点的单链表结构上实现线性表操作Length(L)。 解： //返回单链表的长度 int ListLength_L(LinkList L) { int i=0; LinkList p=L; if(p) p=p-next; while(p){ p=p-next; i++; } return i; } 2.21 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表逆置为。 解： // 顺序表的逆置 Status ListOppose_Sq(SqList L) { int i; ElemType x; for(i=0;iL.length/2;i++){ x=L.elem[i]; L.elem[i]=L.elem[L.length-1-i]; L.elem[L.length-1-i]=x; } return OK; } 2.22 解：// 带头结点的单链表的逆置 Status ListOppose_L(LinkList L) { LinkList p,q; p=L; p=p-next; L-next=NULL; while(p){ q=p; p=p-next; q-next=L-next; L-next=q; } return OK; } 3.9 解： void ditui(int j) { if(j1){ coutj; ditui(j-1); } return; } 3.10解： void test(int sum) { Stack s; InitStack(s); int x; do{ cinx; Push(s,x); }while(x0); while(!StackEmpty(s)){ Pop(s,x); sum+=x; coutsumendl; } DestoryStack(s); } 3.24 解： int g(int m,int n); int main() { int m,n; cout请输入m和n的值：; cinmn; if(n=0) coutg(m,n)endl; else coutNo Solution!; return 0; } int g(int m,int n) { if(m0) return(g(m-1,2*n)+n); else return 0; } 假设主函数的返回地址为0，递归函数3条语句的地址分别为1、2、3。 306431323216338344052Status g(int m,int n,int s)//求递归函数g的值s{??if(m==0n=0) s=0;??else if(m0n=0) s=n+g(m-1,2*n);??else return ERROR;??return OK;}//g 3.31解： Status SymmetryString(char* p) { Queue q; if(!InitQueue(q)) return 0; Stack s; InitStack(s); ElemType e1,e2; while(*p){ Push(s,*p); EnQueue(q,*p); p++; } while(!StackEmpty(s)){ Pop(s,e1); DeQueue(q,e2); if(e1!=e2) return FALSE; } return OK; } ((((int Palindrome_Test()//判别输入的字符串是否回文序列,是则返回1,否则返回0{??InitStack(S);InitQueue(Q);??while((c=getchar())!=@)??{????Push(S,c);EnQueue(Q,c); //同时使用栈和队列两种结构??}??while(!Stack