1、在数组]中查值为K的元素,若到则输出其位置i(1<=i<=n),否则输出数组和链表0作为标志。
int locate(dataytpe ],dateytpe k)
    {  i=n;
      while ((I<=n)&&(A[i]!=k)) I++;
        if (I<=n)  return(i);
        else  return(o);
    }
2、试编写在带头结点的单链表上实现线性表基本运算LOCATE(L,X)、find(L,i)、INSERT(L,X，i)和DELETE(L,i)的算法。
(1)定位LOCATE(L，X)
int locate_lklist(lklist head,datatype x)
/*求表head中第一个值等于x的的序号，不存在这种结点时结果为0*/
{p=head->next;j=1;        /*置初值*/
while((p!=NULL)&&(p->data!=x))
{p=p->next;j++}/*未达表结点又未到值等于X的结点时经，继续扫描*/
if (p->data = =x)  return(j);
else          return(0);
}
(2)按序号查find(L,i)
lklist find_lklist(lklist head , int i);
{ j=1; p=head->next;
while((j<1)&&(p!=NULL)){p=p->next; j++}
if(i= = j) return(p);
else  return(NULL);
}
(3)插入INSERT(L，X，i)
  void insert_lklist(lklist head,datatype x,int I)
/*在表haed的第i个位置上插入一人以x为值的新结点*/
{p=find_lklist(head,i-1);  /*先第i-1个结点*/
if(p= =NULL) error(“不存在第i个位置”)/*若第i-1个结点不存在，退出*/
else{s=malloc(size);s->data=x    /*否则生成新结点*/
s->next=p->next  /*结点*p在链域值传给结点*s的链域*/
p->next=s;      /*修改*p的链域*/
}
}
(4)删除DELDTE(L,i)
void delete_lklist(lklist head,int i) /*删除表head的第i个结点*/
{p=find_lklist(head,i-1)  /*先待删结点的直接前驱*/
if((p!==NULL)&&(p->next!=NULL))/*若直接前趋存在且待结点存在*/
(q=p->next; /*q指向待删结点*/
p->next=q->next/*摘除待结点*/;
free(q);/*释放已摘除结点q*/
}
else error(“不存在第i个结点”)/*否则给出相关信息*/
}
3、假设有两个按数据元素值递增有序排列的线性表A和B，均以单链表作存储结构。编写算法将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表(即A表和B表的)结点空间存放表C。
分析：
（1）当有序表A，B均非空时，出两表中元素最小的一个元素，然后将此结点插入到C表中，重复上述步骤。
（2）当A，B两表有一个为空表时，将另一表中元素顺序地插入到C表中。
（3）由于C按递减排序，因此在C表中插入元素时，应始终插入到C表表头。
Lklist Wlink_lklist(lklist A,lklist B)
{ while((A!=NULL)&&(B!=NULL))
  if(A->data<b->data){p=A;A=A->next;}
    else
  p->next=C;C=p;
}
if(A= =NULL) A=B;
while(A!=NULL)
{p=A;A=A->next;
p->next=C;C=p;}
return(C);
}
4、以二叉链表作存储结构，试编写求二叉树深度的算法。
Int depth (bitreptr BT)
  {if (BT= =null)return（0);
      else {l=depth (BT->lchild);
            r=depth(BT->rchild);
            return((l>r?l:r)+1);
5、以二叉链表作为存储结构，试编写求二叉树中叶子数的算法。
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);
}
6、假设线性表中结点是按健值递增的顺序存放的。试写一顺序查法，将岗哨设在高下标端。然后分别求出等概率情况下查成功和不成功时的平均查长度。
分析：将岗哨设置在高下标端，表示从线性表低端查时，在不成功的情况下，算法自动在岗哨处终止。另外，在等概率前提下，查成功的平均查长度等于每一个元素查次数之和除以结点总数。
  Int sqsearch0 (sqtable A,keytype X)        /*数组有元素n个*/
    { i=1; A.item[n+1].key=X;              /*设置哨兵*/
      while (A.item[n+1].key!=X) i++;
      return (i% (n+1));                    /*不到返回0，到返回其下标*/
    }
  查成功平均查长度为：（1+2+3+…+n）/ n =（1+n）/ 2。
  查不成功平均查长度为：n+1。
7、试写出二分查的递归算法。
Int binlist (sqtable A,int s,t,keytype X)    /*t、s分别为查区间的上、下界*/
{ if(s<t) return(0);        /*查失败*/
  else
  { mid=(s+t)/2;
    switch(mid)
      { case x<A.item[mid].key: return(binlist(A,s,mid-1,X));  /*在低端区间上递归*/
        case x==A.item[mid].key: return(mid);      /*查成功*/
        case x>A.item[mid].key: return(a,mid+1,t,X));  /*在高端区间上递归*/
      }
    }
  }
8、插入排序中插入位置的操作可以通过二分法查的方法来实现。试据此写一个改进后的插入排序方法。
Void straightsort ( list A )     
          {  for ( i =2 ; i <= n ; i + + )
{  low = 1 ; high = i – 1 ;  /* low ,high 分为当前元素上、下界 */
  A[0] . key = A[i] . key ;
  While ( low <= high )
    { mid = ( low + high ) /2 ;
      switch
        { case  A[0] . key <= A[mid] . key : high = mid – 1 ;
                      case  A[0] . key > A[mid] . key : low = mid + 1 ; 
                    }       
}
          for ( j = i-1 ; j >= mid ; j - -) A [j +1] = A [ j ] ; 
                  A[ mid ] = A[ i ] ; 
}
        }

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。