}
算法的功能： 2、程序设计
(1) 设有一单链表L，结点结构为data|next，编写算法判断该单链表L中的元素是否成等差关系，即：设各元素值次为a1,a2,a3,…,an，判断ai+1-ai=ai-ai-1是否成立。若是返回1，否则返回0。
函数说明为：int dengcha(Node
(2)写出二分查找的非递归算法。(要求统计查找过程中元素的比较次数)
函数说明为： int binsearch(int r[ ], int n,int k)；
(3)设单链表以非递减有序排列，设计算法实现在单链表
中删除值相同的多余结点。
函数说明为：Void Linklist::purge(Node
(4)写出图在邻接表存储结构下广度优先的遍历算法。 函数说明为：
template
函数说明为：void ALGraph ::BFSTraverse(int v)；
（5）编写计算二叉树最大宽度的算法（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。
（5）int Width(BiTree bt)
{if (bt==null) return (0); else {BiTree Q[];
front=1;rear=1;last=1;
temp=0; maxw=0;
Q[rear]=bt;
while(front<=last)
{p=Q[front++]; temp++; if
Q[++rear]=p->lchild;
if
Q[++rear]=p->rchild;
if (front>last) {last=rear;
if(temp>maxw) maxw=temp;
temp=0;
}
}
(p->rchild!=null) (p->lchild!=null)
return (maxw);
}
（6）假设哈希函数为H（key）,编写用链地址法解决冲突的哈希表的插入和删除算法。
void F2( HashTable &H, keytype Key){//哈希
表插入，用链地址法解决冲突
i=H(Key);;// 获取哈希地址
if(H[i]==Null){
s=(Linklist)malloc(sizeof(Lnode))
;
s→data=key; s→next=H[i]; H[i]=s; }//if
else{ p=H[i];// 查找
while(p&&p→data!=key) p=p→
next;
if(p→data==key) exit(1);
else{ s=(Linklist)malloc(sizeof(L
node));// 产生新结点，插入表头
s→next=H[i]; H[i]=s; }// else
}//else
}//F2
void Delete_HS(HashTable &H, KeyType key){
//哈希表删除，用链地址法解决冲突
i=H(key); //获得哈希地址 if(H[i]= =Null) exit(1);
p=H[i];q=p; // p为工作指针，q为p前趋
while(p&&p→data!=key) {//查找
q=p; p=p→next; }//while
if(!p) exit(1);
if(q==H[i]){ //key为第一结点 H[i]p→next; free(p); }// if
else{
q→next=p→next;
free(p);
}//else }//Delete_HS
（7）设计在链式存储结构上交换二叉树中所有结点左右子
树的算法。 typedef
struct
node
{int
data;
struct
node
*lchild,*rchild;} bitree; void swapbitree(bitree *bt) {
bitree *p; if(bt==0) return;
swapbitree(bt->lchild); swapbitree(bt->rchild); p=bt->lchild;
bt->rchild=p;}
bt->lchild=bt->rchild;
