数据结构算法题

int locate(dataytpe A,dateytpe k)

 { i=0;

  while ((i<=n-1)&&(A[i]!=k)) 

 i++;

  if (i<=n-1)  return(i);

  else  return(0);

}

2、试编写在无头结点的单链表上实现线性表基本运算LOCATE(L,X)。

int Wlocate(lklist head,datatype X)

/*求表head中第一个值等于x的结点的序号。不存在这种结点时结果为0*/

{ /*置初值*/

while((p!=NULL)&&(p->data!=x))

{p=p->next;j++} /*未达表结点又未找到值等于X的结点时经，继续扫描*/

if( p->data = =X) return(j);

else  return(0);

}

3、试编写在不带头结点的单链表上实现线性表基本运算LENGTH(L)的算法。

Int wlength_lklist(lklist head)　　　/*求表head的长度*/

{p=head;j=0;

while(p!=NULL)

{p=p->next;

j++;

}

r回传表长*/ 

｝

4、以二叉链表作为存储结构，试编写求二叉树中叶子数的算法。

int leafcount (bitreptr T)       /*求二叉树 T的叶子数*/

  { if(T==NULL) leaf=0;      /*当二叉树为空时，叶子数等于0*/

else if(T->lchild==NULL)&&(T->rchild==NULL) leaf=1

                           /*当二叉树仅含一个根结点时，叶子数为1*/

      else{L=leafcount(T->lchild);  /*求左子树的叶子数*/ 

         R=leafcount(T->lchild);   /*求右子树的叶子数*/ 

          leaf=L+R;    /*左、右子树叶子数之和等于二叉树的叶子数*/ 

          }

   return(leaf);

}

5、以二叉链表作存储结构，试编写求二叉树深度的算法。

Int depth (bitreptr BT)

   return（0);

 depth (BT->lchild);

 depth(BT->rchild);

         return((l>r?l:r)+1);

6、假设线性表中结点是按健值递增的顺序存放的。试写一顺序查找法，将岗哨设在高下标端。然后分别求出等概率情况下查找成功和不成功时的平均查找长度。

Int sqsearch  /*数组有元素n个*/

{ i=1; A [/*设置哨兵*/

   while (A [i].key!=X) i++;

return (i % (n+1))/*找不到返回0，找到返回其下标*/

}

查找成功平均查找长度为：（1+2+3+…+n）/ n =（1+n）/ 2。

查找不成功平均查找长度为：n+1。

7、插入排序中找插入位置的操作可以通过二分法查找的方法来实现。试据此写一个改进后的插入排序方法。

Void straight

{ for ( i =2 ; i <= n ; i + + )

{ low = 1 ; high = i – 分为当前元素上、下界 */

  A[0] = A[i] ;

While ( low <= high )

  A[0] . key <= A[mid] . key : high = mid – 1 ; 

 case  A[0] . key > A[mid] . key : low = mid + 1 ;

}

 A[ mid ] = A[0] ;

 }

  }