38.[题目分析] 将顶点放在两个集合V1和V2。对每个顶点，检查其和邻接点是否在同一个集合中，如是，则为非二部图。为此，用整数1和2表示两个集合。再用一队列结构存放图中访问的顶点。
int BPGraph (AdjMatrix g)
//判断以邻接矩阵表示的图g是否是二部图。
{int s[]; //顶点向量，元素值表示其属于那个集合（值1和2表示两个集合） int Q[];//Q为队列，元素为图的顶点，这里设顶点信息就是顶点编号。
int f=0,r,visited[]; //f和r分别是队列的头尾指针,visited[]是访问数组 for (i=1;i<=n;i++) {visited[i]=0;s[i]=0;} //初始化，各顶点未确定属于那个集合
Q[1]=1; r=1; s[1]=1;//顶点1放入集合S1
while(f {v=Q[++f]; if (s[v]==1) jh=2; else jh=1;//准备v的邻接点的集合号 if (!visited[v]) {visited[v]=1; //确保对每一个顶点，都要检查与其邻接点不应在一个集合中 for (j=1,j<=n;j++) if (g[v][j]==1){if (!s[j]) {s[j]=jh; Q[++r]=j;} //邻接点入队列 else if (s[j]==s[v]) return(0);} //非二部图 }//if (!visited[v]) }//while return(1); }//是二部图 [算法讨论] 题目给的是连通无向图，若非连通，则算法要修改。 39．[题目分析] 连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。若仍连通，继续向下删；直到剩n-1条边为止。 void SpnTree (AdjList g) //用“破圈法”求解带权连通无向图的一棵最小代价生成树。 {typedef struct {int i,j,w}node; //设顶点信息就是顶点编号，权是整型数 node edge[]; scanf( \输入边数和顶点数。 for (i=1;i<=e;i++) //输入e条边：顶点，权值。 scanf(\ for (i=2;i<=e;i++) //按边上的权值大小，对边进行逆序排序。 {edge[0]=edge[i]; j=i-1; while (edge[j].w k=1; eg=e; while (eg>=n) //破圈，直到边数e=n-1. {if (connect(k)) //删除第k条边若仍连通。 {edge[k].w=0; eg--; }//测试下一条边edge[k]，权值置0表示该边被删除 k++; //下条边 }//while }//算法结束。 connect()是测试图是否连通的函数，可用图的遍历实现， 40.根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量pre（初值为null）和全局变量flag，初值为true。若非二叉排序树，则置flag为false。 #define true 1 #define false 0 typedef struct node {datatype data; struct node *llink,*rlink;} *BTree; void JudgeBST（BTree t,int flag） // 判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag得出结论。 { if（t!=null && flag） { Judgebst（t->llink,flag）；// 中序遍历左子树 if（pre==null）pre=t；// 中序遍历的第一个结点不必判断 else if（pre->data 41. 非递归建立二叉排序树，在二叉排序树上插入的结点都是叶子结点。 void Creat_BST（BiTree bst，datatype K[]，int n） // 以存储在数组K中的n个关键字，建立一棵初始为空的二叉排序树。 {for（i=1；i≤n；i++） {p=bst；f=null；//在调用Creat_BST时，bst=null while（p!=null） if（p->data s=（BiTree）malloc（sizeof （BiNode））；// 申请结点空间 s->data=K[i]；s->LLINK=null；s->RLINK=null； if（f==null）bst=s； //根结点 else if（s->data else f->RLINK=s；//右子树根结点的值大于等于根结点的值 }//算法结束 42. int BinSrch（rectype r[ ]，int k，low，high） //在长为n的有序表中查找关键字k，若查找成功，返回k所在位置，查找失败返回0。 {if（low≤high） //low和high分别是有序表的下界和上界 {mid=（low+high）/2； if（r[mid].key==k）return （mid）； else if（r[mid].key>k）return （BinSrch（r,k，mid+1，high））; else return （BinSrch（r,k，low，mid-1））; } else return （0）；//查找失败。 }//算法结束 算法时间复杂度为O（logn）。 43. ．[题目分析] 用链地址法解决冲突的哈希表是一个指针数组，数组分量均是指向单链表的指针，（第i个）单链表结点有两个域，一个是哈希地址为i的关键字，另一个是指向同义词结点的指针。删除算法与单链表上删除算法类似。 typedef struct node {keytype key； struct node *next； }HSNode；*HSList typedef struct node *HLK； void Delete（HLK HT[]，keytype K） //用链地址法解决冲突，从哈希表中删去关键字为K的记录 {i=H（K）；//用哈希函数确定关键字K的哈希地址 if（HT[i]==null）{printf（“无被删除记录\\n”）；exit（0）；} HLK p,q; p=H[i]；q=p； //p指向当前记录（关键字），q是p的前驱 while（p && p->key！=k）{q=p；p=p->next；} if（p==null）{printf（“无被删除记录”）；exit(0); } if（q==H[i]） //被删除关键字是链表中第一个结点 {HT[i]=HT[i].next；free（p）；} else{q->next=p->next；free（p）；} }//结束Delete 44. ．[题目分析]首先计算关键字的散列地址，若该地址为空，则空操作；若该地址有关键字，但与给定值不等，则用解决冲突的方法去查找给定值；若该地址有关键字且与给定值相等，则实行删除。题目要求将所有可以前移的元素前移去填充被删除的空位，以保证探测序列不断裂。由于用线性探测解决冲突，设被删除元素的散列地址为i，则其余m-1（m为表长）个位置均可能是同义词。查找同义词的操作直到碰到空地址或循环一圈回到i才能结束。为了提高算法效率，减少数据移动，应将最后一个同义词前移填充被删除关键字。 void HsDelete（rectype HS[]，K） //在以除余法为散列函数、线性探测解决冲突的散列表HS中，删除关键字K {i=K % P； // 以造表所用的除余法计算关键字K的散列地址 if（HS[i]==null）{printf（“散列表中无被删关键字”）；exit（0）；} // 此处null代表散列表初始化时的空值 switch {case HS[i]==K：del(HS，i，i，K)；break； case HS[i]!=K：di=1；j=(i+ di)%m； // m为 表长 while（HS[j]!=null && HS[j]!=K && j!=i）// 查找关键字K {di=di+1； j=(i+di)%m； }// m为 表长 if（HS[j]==K）del(HS，i，j，K)； else {printf（“散列表中无被删关键字”）；exit（0）;} }// switch }算法结束 void del（rectype HS[]，in i，int j，rectype K） //在散列表HS中，删除关键字K，K的散列地址是i，因解决冲突而将其物理地置于表中j。算法查找关键字K的同义词，将其最后一个同义词移到位置j，并将其同义词的位置置空。 {di=1；last=j；x=(j+di)% m；// 探测地址序列，last记K的最后一个同义词的位置 while（x!=i） //可能要探测一圈 {if（HS[x]==null）break； // 探测到空位置，结束探测 else if（HS[x]%P==i）last=x；// 关键字K的同义词 di=di+1；x=(j+di) % m； // 取下一地址探测 } HS[j]=HS[last]; HS[last]=null; //将哈希地址last的关键字移到哈希地址j } 45. [题目分析] 因为二叉树各结点已标明了平衡因子b，故从根结点开始记树的层次。根结点的层次为1，每下一层，层次加1，直到层数最大的叶子结点，这就是平衡二叉树的高度。当结点的平衡因子b为0时，任选左右一分枝向下查找，若b不为0，则沿左（当b=1时）或右（当b=-1时）向下查找。 int Height（BSTree t） // 求平衡二叉树t的高度 {level=0；p=t； while（p） {level++； // 树的高度增1 if（p->bf<0）p=p->rchild；//bf=-1 沿右分枝向下 //bf是平衡因子，是二叉树t结点的一个域，因篇幅所限，没有写出其存 储定义 else p=p->lchild； //bf>=0 沿左分枝向下 }//while return （level）；//平衡二叉树的高度 } //算法结束 46. ．[题目分析]非零元素个数是100，负载因子取0.8，表长125左右，取p为127，散列地址为0到126。哈希函数用H(k)=(3*i+2*j) % 127，i，j为行值和列值。 #define m 127 typedef struct {int i，j；datatype v;}triple； void CreatHT（triple H[m]） //100个非零元素生成稀疏矩阵的哈希表，表中元素值均初始化为0。 {for（k=0；k<100；k++） {scanf（&i,&j,&val）；//设元素值为整型 h=(3*i+2*j)% m； //计算哈希地址 while（HT[h].v!=0）) h=(h+1) % m; //线性探测哈希地址 HT[h].i=i；HT[h].j=j；HT[h].v=val； //非零元素存入哈希表 } }//算法CreatHT结束 datatype Search（triple HT[m]，int i，int j） //在哈希表中查找下标为i，j的非零元素，查找成功返回非零元素，否则返回零值。 {int h=(3*i+2*j) % m； while ((HT[h].i!=i || HT[h].j!=j) && HT[h].v!=0) h=（h+1）% m； return （HT[h].v）； }//Search 2、画出向小顶堆中加入数据4, 2, 5, 8, 3, 6, 10, 1时，每加入一个数据后堆的变化。 47. void BubbleSort2(int a[],int n) //相邻两趟向相反方向起泡的冒泡排序算法 { change=1;low=0;high=n-1; //冒泡的上下界 while(low { change=0; //设不发生交换 for(i=low;i if(a[i]>a[i+1]){a[i]<-->a[i+1];change=1;} //有交换，修改标志change high--; //修改上界 for(i=high;i>low;i--) //从下向上起泡 if(a[i]a[i-1];change=1;} low++; //修改下界 }//while }//BubbleSort2 48. typedef struct node { ElemType data; struct node *prior,*next; }node，*DLinkedList; void TwoWayBubbleSort(DLinkedList la) //对存储在带头结点的双向链表la中的元素进行双向起泡排序。 {int exchange=1; // 设标记 DLinkedList p,temp,tail; head=la //双向链表头，算法过程中是向下起泡的开始结点 tail=null; //双向链表尾，算法过程中是向上起泡的开始结点 while (exchange) {p=head->next; //p是工作指针，指向当前结点 exchange=0; //假定本趟无交换 while (p->next!=tail) // 向下（右）起泡，一趟有一最大元素沉底 if (p->data>p->next->data) //交换两结点指针，涉及6条链 {temp=p->next; exchange=1;//有交换