12-13.c

数据结构经典算法一书源代码和习题解答实现代码。

#include "stdio.h"
#include "malloc.h"
//#define n 10
#define QueueSize 100 //假定预分配的队列空间最多为100个元素  
typedef int DataType; //假定队列元素的数据类型为字符
typedef struct node{
	DataType data;
	struct node *next;
}QueueNode;
typedef struct{
	QueueNode *front;  //头指针
	QueueNode *rear;
}LinkQueue;
// 置队列空
void Initial(LinkQueue *Q)
{//将顺序队列置空
    Q->front=Q->rear=NULL;
} 
//判队列空
int IsEmpty(LinkQueue *Q)
{
    return Q->front==NULL&&Q->rear==NULL;
}
//进队列
void EnQueue(LinkQueue *Q,DataType x)
{//将元素x插入链队列尾部
	QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode));//申请新结点
	p->data=x;
	p->next=NULL;
    if(IsEmpty(Q))
		Q->front=Q->rear=p;  //将x插入空队列
	else 
	{ //x插入非空队列的尾
		Q->rear->next=p;     //*p链到原队尾结点后
		Q->rear=p;           //队尾指针指向新的尾
	}
}
//出队列
DataType DeQueue(LinkQueue *Q)
{
	DataType x;
	QueueNode *p;
	if(IsEmpty(Q))
	{
		printf("队列为空");//下溢
		exit(1);
	}
	p=Q->front;                   //指向对头结点
	x=p->data;                    //保存对头结点的数据
	Q->front=p->next;             //将对头结点从链上摘下
    if(Q->rear==p)//原队中只有一个结点，删去后队列变空，此时队头指针已为空
		Q->rear=NULL;
	free(p);   //释放被删队头结点
	return x;  //返回原队头数据
}
// 取队列顶元素
DataType Front(LinkQueue *Q)
{
	if(IsEmpty(Q))
	{
		printf("队列为空"); //下溢,退出运行
		exit(1);
	}
	return Q->front->data;
}
void AddLiveNode(LinkQueue Q, DataType wt,DataType bestw, int i, int n)
{// 如果不是叶节点，则将节点权值w t加入队列Q
	if (i == n) 
	{// 叶子
		if (wt>bestw) 
			bestw = wt;
	}
	else 
		EnQueue(&Q,wt); // 不是叶子
}
DataType MaxLoading(DataType w[], DataType c, int n)
{// 返回最优装载值
// 使用FIFO分枝定界算法
// 为层次1初始化
	DataType Ew = 0, // E-节点的权值
		bestw = 0; // 目前的最优值
	int i = 1; // E-节点的层
	LinkQueue	 Q; // 活节点队列
	EnQueue(&Q,-1); //标记本层的尾部
	// 搜索子集空间树
	while (1) {
		// 检查E-节点的左孩子
		if (Ew + w[i] <= c) // x[i] = 1
			AddLiveNode(Q, Ew + w[i], bestw, i, n);	
		// 右孩子总是可行的
		AddLiveNode(Q, Ew, bestw, i, n); // x[i] = 0
			Ew=DeQueue(&Q); // 取下一个E-节点
		if (Ew == -1) 
		{ // 到达层的尾部
			if (IsEmpty(&Q)) 
				return bestw;
			EnQueue(&Q,-1); //添加尾部标记
			Ew=DeQueue(&Q); // 取下一个E-节点
			i++;
		} // Ew的层
	}
}
void main()
{
	DataType w[10],c;
	//初始化w[n],c,n
	MaxLoading(w,c,10);
}