数据结构课后题算法

1、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;i>0,x<va.elemi-1;i-)va.elemi=va.elemi-1;va.elemi=x;va.length+;return OK;2.14 试写一算法在带头结点的单链表结构上实现线

2、性表操作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;i<L.length/2;i+)x=L.elemi;L.elemi=L.elemL.length-1-i;L.elemL

3、.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(j>1)cout<<j;ditui(j-1);return;3.10解：void test(int &sum)Stack s;In

4、itStack(s);int x;docin>>x;Push(s,x);while(x>0);while(!StackEmpty(s)Pop(s,x);sum+=x;cout<<sum<<endl;DestoryStack(s);3.24 解：int g(int m,int n);int main()int m,n;cout<<"请输入m和n的值："cin>>m>>n;if(n>=0) cout<<g(m,n)<<endl;else cout<<"

5、;No Solution!"return 0;int g(int m,int n)if(m>0)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=0&&n>=0) s=0;  else if(m>0&&n>=0) s=n+g(m-1,2*n);  

6、else return ERROR;  return OK;/g3.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()/判别输入的字符串是否回文序列

7、,是则返回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)

8、return ERROR;    return OK;/Palindrome_Test 6.41 解：/ 求位于先序序列中第k个位置的结点的值，/ e中存放结点的返回值，i为计数器Status PONodeK(TElemType& e,int& i,int k,BiTree& T)if(T)i+;if(i=k) e=T->data;elsePONodeK(e,i,k,T->lchild);PONodeK(e,i,k,T->rchild);return OK;6.42 解：/ 求二叉树中叶子结点的数目Status

9、POLeafNodeNum(int& i,BiTree& T)if(T)if(!T->lchild && !T->rchild) i+;POLeafNodeNum(i,T->lchild);POLeafNodeNum(i,T->rchild);return OK;7.22 算法基本思想：递归算法，当两个顶点相等时为递归出口。否则递归调用。访问标志数组 DFS_locate(G g,int i,int j) int visitedMAXSIZE;ArcNode *w;int k;if(i=j) return 1;els

10、e visiti=1;for(w=g.verticesi.firstarc;w;w=w->nextarc) k=w->adjvex;if(!visitk&&DFS_locate(g,k,j) return 1;else return 0;7.23 int exist_path_BFS(ALGraph G,int i,int j)/广度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0 。使用辅助队列Q和访问标志数组visited. int k ;ArcNode *p; int visitedMAXSIZE;   InitQueue

11、(Q);   EnQueue(Q,i); / i入队列   while(!QueueEmpty(Q)        DeQueue(Q,u); / 对头元素出队并置为U     visitedu=1;     for(p=G.verticesi.firstarc ; p ;p=p->nextarc)          &#

12、160; k=p->adjvex ;       if(k=j) return 1 ;       if(!visitedk) EnQueue(Q,k); /for /while  return 0;/exist_path_BFS 9.25int Search_Sq(SSTable ST,int key)/在有序表上顺序查找的算法,监视哨设在高下标端 ST.elemST.length+1.key=key;   for(i=1;ST

13、.elemi.key>key;i+);   if(i>ST.length|ST.elemi.key<key) return ERROR;   return i;/Search_Sq分析:本算法查找成功情况下的平均查找长度为ST.length+1/2,不成功情况下为ST.length+2/2. 9.26int Search_Bin_Recursive(SSTable ST,int key,int low,int high)/折半查找的递归算法 if(low>high) return 0; /查找不到时返回0  

14、mid=(low+high)/2;   if(ST.elemmid.key=key) return mid;   else if(ST.elemmid.key>key) return Search_Bin_Recursive(ST,key,low,mid-1);   else return Search_Bin_Recursive(ST,key,mid+1,high);  /Search_Bin_Recursive 9.32int last=0; void MaxLT_MinGT(BiTree T,int x

15、)/找到二叉排序树T中小于x的最大元素和大于x的最小元素 if(T->lchild) MaxLT_MinGT(T->lchild,x); /本算法仍是借助中序遍历来实现   if(last<x&&T->data>=x) /找到了小于x的最大元素     printf("a=%dn",last);   if(last<=x&&T->data>x) /找到了大于x的最小元素    

16、 printf("b=%dn",T->data);   last=T->data;   if(T->rchild) MaxLT_MinGT(T->rchild,x);/MaxLT_MinGT 10.26void Bubble_Sort1(int a ,int n)/对包含n个元素的数组a进行改进的冒泡排序 change=n-1; /change指示上一趟冒泡中最后发生交换的元素的位置 while(change) for(c=0,i=0;i<change;i+) if(ai>ai+1) ai<-

17、>ai+1; c=i+1; /c指示这一趟冒泡中发生交换的元素的位置 change=c; /while/Bubble_Sort110.31 void Divide(int a ,int n)/把数组a中所有值为负的记录调到非负的记录之前  low=0;high=n-1;  while(low<high)      while(low<high&&ahigh>=0) high-; /以0作为虚拟的枢轴记录    alo

18、w<->ahigh;    while(low<high&&alow<0) low+;    alow<->ahigh;  /Divide 10.33void LinkedList_Select_Sort(LinkedList &L)/单链表上的简单选择排序算法 for(p=L;p->next->next;p=p->next) q=p->next;x=q->data; for(r=q,s=q;r->ne