SecondOptimal.h

#include<iostream>
using namespace std;

#define MAX_DATA_NUM 20//最大节点值

typedef struct SSTable //静态查找表存储结构
{
	char name;
	int weight;
} ElemType;

typedef struct BiTreeNode //二叉链表存储结构
{
	ElemType data;
	BiTreeNode *lchild, *rchild;
	BiTreeNode()
	{
		lchild = rchild = NULL;
	}
} *BiTree;

class SOSTree //静态查找树表
{
public:
	SOSTree(); //构造函数
	void SOSTREE(); //接口函数
private:
	void Findsw(); //得到权值和
	void GetSSTable(); //得到静态查找表
	void SecondOptimal(BiTree&, int, int); //得到次优查找树
	void SOSTreeTraverse(BiTree&); //遍历次优查找树
	ElemType r[MAX_DATA_NUM]; //静态查找表
	int sw[MAX_DATA_NUM]; //累计权值和
	int datanum; //表节点数量
};

SOSTree::SOSTree()
{
	datanum = 0;
}

void SOSTree::SOSTREE() //接口函数
{
	BiTree T;
	GetSSTable(); //得到静态查找表
	Findsw(); //得到累计权值和
	SecondOptimal(T, 0, datanum - 1); //得到次优查找树
	SOSTreeTraverse(T); //遍历次优查找树
}

void SOSTree::GetSSTable() //得到静态查找表
{
	cout << "Please Input The SSTable :" << endl << "name weight" << endl;
	char name;
	int weight;
	while (cin >> name >> weight)
	{
		r[datanum].name = name;
		r[datanum].weight = weight;
		datanum++;
	}
	cin.clear();
}

void SOSTree::Findsw() //得到累计权值和
{
	sw[0] = r[0].weight;
	for (int i = 1; i < datanum; i++)
		sw[i] = sw[i - 1] + r[i].weight;
}

void SOSTree::SecondOptimal(BiTree &t, int low, int high) //得到次优查找树
{
	//由有序表r[low,high]及其累计权值和表sw递归建立次优查找树
	int i = low, min = abs(sw[high] - sw[low]); //初始化
	int dw = sw[high] + ((low == 0) ? 0 : sw[low - 1]);
	for (int j = low + 1; j <= high; j++) //找到最小的Δpi
		if (abs(dw - sw[j] - sw[j - 1]) < min)
		{
			i = j;
			min = abs(dw - sw[j] - sw[j - 1]);
		}
	t = new BiTreeNode; //建立新节点
	t->data = r[i];
	if (i == low)
		t->lchild = NULL;
	else
		SecondOptimal(t->lchild, low, i - 1);
	if (i == high)
		t->rchild = NULL;
	else
		SecondOptimal(t->rchild, i + 1, high);
}

void SOSTree::SOSTreeTraverse(BiTree &t) //遍历次优查找树
{
	if (t == NULL)
		return;
	cout << t->data.name << " " << t->data.weight << endl;
	SOSTreeTraverse(t->lchild);
	SOSTreeTraverse(t->rchild);
}

main.cpp

#include"SecondOptimal.h"
 
int main()
{
	SOSTree T;
	T.SOSTREE();
	system("pause");
}